Further Adaptive Best-of-Both-Worlds Algorithm for Combinatorial Semi-Bandits
Taira Tsuchiya, Shinji Ito, Junya Honda
Abstract
We consider the combinatorial semi-bandit problem and present a new algorithm with a best-of-both-worlds regret guarantee; the regrets are bounded near-optimally in the stochastic and adversarial regimes. In the stochastic regime, we prove a variance-dependent regret bound depending on the tight suboptimality gap introduced by Kveton et al. (2015) with a good leading constant. In the adversarial regime, we show that the same algorithm simultaneously obtains various data-dependent regret bounds. Our algorithm is based on the follow-the-regularized-leader framework with a refined regularizer and adaptive learning rate. Finally, we numerically test the proposed algorithm and confirm its superior or competitive performance over existing algorithms, including Thompson sampling under most settings.
BibTeX
@InProceedings{pmlr-v206-tsuchiya23a,
title = {Further Adaptive Best-of-Both-Worlds Algorithm for Combinatorial Semi-Bandits},
author = {Tsuchiya, Taira and Ito, Shinji and Honda, Junya},
booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics},
pages = {8117--8144},
year = {2023},
editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem},
volume = {206},
series = {Proceedings of Machine Learning Research},
month = {25--27 Apr},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v206/tsuchiya23a/tsuchiya23a.pdf},
url = {https://proceedings.mlr.press/v206/tsuchiya23a.html},
abstract = {We consider the combinatorial semi-bandit problem and present a new algorithm with a best-of-both-worlds regret guarantee; the regrets are bounded near-optimally in the stochastic and adversarial regimes. In the stochastic regime, we prove a variance-dependent regret bound depending on the tight suboptimality gap introduced by Kveton et al. (2015) with a good leading constant. In the adversarial regime, we show that the same algorithm simultaneously obtains various data-dependent regret bounds. Our algorithm is based on the follow-the-regularized-leader framework with a refined regularizer and adaptive learning rate. Finally, we numerically test the proposed algorithm and confirm its superior or competitive performance over existing algorithms, including Thompson sampling under most settings.}
}