On the Sublinear Regret of Continuous K-Max Bandits

Yu Chen, Siwei Wang, Longbo Huang, Wei Chen
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:1200-1229, 2026.

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{\mathcal{O}}(T^{3/4})$ regret bound, the first sublinear guarantee in this setting. Numerical experiments show its superior performance over baseline methods. Furthermore, for the specific case of exponential distributions under full-bandit feedback, we propose MLE-Exp algorithm that attains a near-optimal $\widetilde{\mathcal{O}}(\sqrt{T})$ regret bound. This work establishes fundamental theoretical guarantees and provides a powerful algorithmic solution for continuous combinatorial bandits.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-chen26d, title = {On the Sublinear Regret of Continuous K-Max Bandits}, author = {Chen, Yu and Wang, Siwei and Huang, Longbo and Chen, Wei}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {1200--1229}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/chen26d/chen26d.pdf}, url = {https://proceedings.mlr.press/v337/chen26d.html}, 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{\mathcal{O}}(T^{3/4})$ regret bound, the first sublinear guarantee in this setting. Numerical experiments show its superior performance over baseline methods. Furthermore, for the specific case of exponential distributions under full-bandit feedback, we propose MLE-Exp algorithm that attains a near-optimal $\widetilde{\mathcal{O}}(\sqrt{T})$ regret bound. This work establishes fundamental theoretical guarantees and provides a powerful algorithmic solution for continuous combinatorial bandits.} }
Endnote
%0 Conference Paper %T On the Sublinear Regret of Continuous K-Max Bandits %A Yu Chen %A Siwei Wang %A Longbo Huang %A Wei Chen %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-chen26d %I PMLR %P 1200--1229 %U https://proceedings.mlr.press/v337/chen26d.html %V 337 %X 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{\mathcal{O}}(T^{3/4})$ regret bound, the first sublinear guarantee in this setting. Numerical experiments show its superior performance over baseline methods. Furthermore, for the specific case of exponential distributions under full-bandit feedback, we propose MLE-Exp algorithm that attains a near-optimal $\widetilde{\mathcal{O}}(\sqrt{T})$ regret bound. This work establishes fundamental theoretical guarantees and provides a powerful algorithmic solution for continuous combinatorial bandits.
APA
Chen, Y., Wang, S., Huang, L. & Chen, W.. (2026). On the Sublinear Regret of Continuous K-Max Bandits. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:1200-1229 Available from https://proceedings.mlr.press/v337/chen26d.html.

Related Material