@inproceedings{chen2026on,
author = {Chen, Yu and Wang, Siwei and Huang, Longbo and Chen, Wei},
title = {On the Sublinear Regret of Continuous K-Max Bandits},
booktitle = {42nd Conference on Uncertainty in Artificial Intelligence (UAI)},
year = {2026},
month = {August},
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 e 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 e O(T^[1/2]) regret bound. This work establishes fundamental theoretical guarantees and provides a powerful algorithmic solution for continuous combinatorial bandits.},
url = {http://approjects.co.za/?big=en-us/research/publication/on-the-sublinear-regret-of-continuous-k-max-bandits/},
}