Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time

Thibaut Cuvelier, Richard Combes, Eric Gourdin
Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:505-528, 2021.

Abstract

We consider combinatorial semi-bandits with uncorrelated Gaussian rewards. In this article, we propose the first method, to the best of our knowledge, that enables to compute the solution of the Graves-Lai optimization problem in polynomial time for many combinatorial structures of interest. In turn, this immediately yields the first known approach to implement asymptotically optimal algorithms in polynomial time for combinatorial semi-bandits.

Cite this Paper

BibTeX
@InProceedings{pmlr-v132-cuvelier21a, title = {Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time}, author = {Cuvelier, Thibaut and Combes, Richard and Gourdin, Eric}, booktitle = {Proceedings of the 32nd International Conference on Algorithmic Learning Theory}, pages = {505--528}, year = {2021}, editor = {Feldman, Vitaly and Ligett, Katrina and Sabato, Sivan}, volume = {132}, series = {Proceedings of Machine Learning Research}, month = {16--19 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v132/cuvelier21a/cuvelier21a.pdf}, url = {https://proceedings.mlr.press/v132/cuvelier21a.html}, abstract = {We consider combinatorial semi-bandits with uncorrelated Gaussian rewards. In this article, we propose the first method, to the best of our knowledge, that enables to compute the solution of the Graves-Lai optimization problem in polynomial time for many combinatorial structures of interest. In turn, this immediately yields the first known approach to implement asymptotically optimal algorithms in polynomial time for combinatorial semi-bandits. } }
Endnote
%0 Conference Paper %T Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time %A Thibaut Cuvelier %A Richard Combes %A Eric Gourdin %B Proceedings of the 32nd International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Vitaly Feldman %E Katrina Ligett %E Sivan Sabato %F pmlr-v132-cuvelier21a %I PMLR %P 505--528 %U https://proceedings.mlr.press/v132/cuvelier21a.html %V 132 %X We consider combinatorial semi-bandits with uncorrelated Gaussian rewards. In this article, we propose the first method, to the best of our knowledge, that enables to compute the solution of the Graves-Lai optimization problem in polynomial time for many combinatorial structures of interest. In turn, this immediately yields the first known approach to implement asymptotically optimal algorithms in polynomial time for combinatorial semi-bandits.
APA
Cuvelier, T., Combes, R. & Gourdin, E.. (2021). Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time. Proceedings of the 32nd International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 132:505-528 Available from https://proceedings.mlr.press/v132/cuvelier21a.html.

Related Material