Optimal Arm Elimination Algorithms for Combinatorial Bandits

Yuxiao Wen, Yanjun Han, Zhengyuan Zhou
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:1621-1629, 2026.

Abstract

Combinatorial bandits extend the classical bandit framework to settings where the learner selects multiple arms in each round, motivated by applications such as online recommendation and assortment optimization. While extensions of upper confidence bound (UCB) algorithms arise naturally in this context, adapting arm elimination methods has proved more challenging. We introduce a novel elimination scheme that partitions arms into three categories (confirmed, active, and eliminated), and incorporates explicit exploration to update these sets. We demonstrate the efficacy of our algorithm in two settings: the combinatorial multi-armed bandit with general graph feedback, and the combinatorial linear contextual bandit. Matching lower bounds are also provided. In both cases, our approach achieves near-optimal regret, whereas UCB-based methods can provably fail due to insufficient explicit exploration.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-wen26a, title = { Optimal Arm Elimination Algorithms for Combinatorial Bandits }, author = {Wen, Yuxiao and Han, Yanjun and Zhou, Zhengyuan}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {1621--1629}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/wen26a/wen26a.pdf}, url = {https://proceedings.mlr.press/v300/wen26a.html}, abstract = { Combinatorial bandits extend the classical bandit framework to settings where the learner selects multiple arms in each round, motivated by applications such as online recommendation and assortment optimization. While extensions of upper confidence bound (UCB) algorithms arise naturally in this context, adapting arm elimination methods has proved more challenging. We introduce a novel elimination scheme that partitions arms into three categories (confirmed, active, and eliminated), and incorporates explicit exploration to update these sets. We demonstrate the efficacy of our algorithm in two settings: the combinatorial multi-armed bandit with general graph feedback, and the combinatorial linear contextual bandit. Matching lower bounds are also provided. In both cases, our approach achieves near-optimal regret, whereas UCB-based methods can provably fail due to insufficient explicit exploration. } }
Endnote
%0 Conference Paper %T Optimal Arm Elimination Algorithms for Combinatorial Bandits %A Yuxiao Wen %A Yanjun Han %A Zhengyuan Zhou %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-wen26a %I PMLR %P 1621--1629 %U https://proceedings.mlr.press/v300/wen26a.html %V 300 %X Combinatorial bandits extend the classical bandit framework to settings where the learner selects multiple arms in each round, motivated by applications such as online recommendation and assortment optimization. While extensions of upper confidence bound (UCB) algorithms arise naturally in this context, adapting arm elimination methods has proved more challenging. We introduce a novel elimination scheme that partitions arms into three categories (confirmed, active, and eliminated), and incorporates explicit exploration to update these sets. We demonstrate the efficacy of our algorithm in two settings: the combinatorial multi-armed bandit with general graph feedback, and the combinatorial linear contextual bandit. Matching lower bounds are also provided. In both cases, our approach achieves near-optimal regret, whereas UCB-based methods can provably fail due to insufficient explicit exploration.
APA
Wen, Y., Han, Y. & Zhou, Z.. (2026). Optimal Arm Elimination Algorithms for Combinatorial Bandits . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:1621-1629 Available from https://proceedings.mlr.press/v300/wen26a.html.

Related Material