Safety
On the Sublinear Regret of Continuous K-Max Bandits
arXiv:2502.13467v2 Announce Type: replace Abstract: The K-Max combinatorial multi-armed bandit problem arises in applications such as recommendation and distributed decision making, where the reward i
arXiv:2502.13467v2 Announce Type: replace Abstract: 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.
Source: arXiv cs.LG | 2026-07-16