提出新算法解决连续选最大值的强化学习难题，首次实现亚线性损失增长。
On the Sublinear Regret of Continuous K-Max Bandits
- 用自适应离散化加偏差修正，设计高效算法DCK-UCB
- 理论证明在T次试验下损失为O(T^{3/4})，首次达亚线性
- 适用于推荐系统等需选最优子集的场景，尤其适合连续奖励
K-Max组合多臂老虎机问题出现在推荐系统与分布式决策中，其奖励由选定的K个臂中最大值决定。当结果为连续变量且仅可观测最大值及其对应臂索引时，该问题带来前所未有的挑战：离散化误差、非确定性平局处理及严重估计偏差。为此，我们提出DCK-UCB算法，结合自适应离散化与偏差修正置信区间。理论证明，DCK-UCB可达到 ilde{O}(T^{3/4})的损失界，是该设定下的首个亚线性保证。数值实验表明其性能显著优于基线方法。此外，针对指数分布下全反馈情形，我们提出MLE-Exp算法，实现近似最优的 ilde{O}( \sqrt{T})损失界。本工作建立了连续组合老虎机问题的基本理论框架，并提供了强有力的算法解决方案。
原文摘要 · Abstract (English)
The $K$-Max combinatorial multi-armed bandit problem arises in applications such as recommendation and distributed decision making, where the reward is determined by the maximum outcome among $K$ selected arms. When outcomes are continuous and only the maximum value together with the winner's index is observed, this problem introduces unprecedented difficulties including discretization errors, non-deterministic tie-breaking, and severe estimation biases. To overcome these barriers, we introduce DCK-UCB, an efficient algorithm combining adaptive discretization with bias-corrected confidence bounds. We prove that DCK-UCB achieves a $\widetilde{O}(T^{3/4})$ regret bound, the first sublinear guarantee in this setting. Numerical experiments show strong performance over baseline methods. Furthermore, for the specific case of exponential distributions under full-bandit feedback, we propose the MLE-Exp algorithm that attains a near-optimal $\widetilde{O}(\sqrt{T})$ regret bound. This work establishes fundamental theoretical guarantees and provides a powerful algorithmic solution for continuous combinatorial bandits.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。