Exploiting structure of uncertainty for efficient matroid semi-bandits

Pierre Perrault, Vianney Perchet, Michal Valko
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:5123-5132, 2019.

Abstract

We improve the efficiency of algorithms for stochastic combinatorial semi-bandits. In most interesting problems, state-of-the-art algorithms take advantage of structural properties of rewards, such as independence. However, while being minimax optimal in terms of regret, these algorithms are intractable. In our paper, we first reduce their implementation to a specific submodular maximization. Then, in case of matroid constraints, we design adapted approximation routines, thereby providing the first efficient algorithms that exploit the reward structure. In particular, we improve the state-of-the-art efficient gap-free regret bound by a factor sqrt(k), where k is the maximum action size. Finally, we show how our improvement translates to more general budgeted combinatorial semi-bandits.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-perrault19a, title = {Exploiting structure of uncertainty for efficient matroid semi-bandits}, author = {Perrault, Pierre and Perchet, Vianney and Valko, Michal}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {5123--5132}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/perrault19a/perrault19a.pdf}, url = {https://proceedings.mlr.press/v97/perrault19a.html}, abstract = {We improve the efficiency of algorithms for stochastic combinatorial semi-bandits. In most interesting problems, state-of-the-art algorithms take advantage of structural properties of rewards, such as independence. However, while being minimax optimal in terms of regret, these algorithms are intractable. In our paper, we first reduce their implementation to a specific submodular maximization. Then, in case of matroid constraints, we design adapted approximation routines, thereby providing the first efficient algorithms that exploit the reward structure. In particular, we improve the state-of-the-art efficient gap-free regret bound by a factor sqrt(k), where k is the maximum action size. Finally, we show how our improvement translates to more general budgeted combinatorial semi-bandits.} }
Endnote
%0 Conference Paper %T Exploiting structure of uncertainty for efficient matroid semi-bandits %A Pierre Perrault %A Vianney Perchet %A Michal Valko %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-perrault19a %I PMLR %P 5123--5132 %U https://proceedings.mlr.press/v97/perrault19a.html %V 97 %X We improve the efficiency of algorithms for stochastic combinatorial semi-bandits. In most interesting problems, state-of-the-art algorithms take advantage of structural properties of rewards, such as independence. However, while being minimax optimal in terms of regret, these algorithms are intractable. In our paper, we first reduce their implementation to a specific submodular maximization. Then, in case of matroid constraints, we design adapted approximation routines, thereby providing the first efficient algorithms that exploit the reward structure. In particular, we improve the state-of-the-art efficient gap-free regret bound by a factor sqrt(k), where k is the maximum action size. Finally, we show how our improvement translates to more general budgeted combinatorial semi-bandits.
APA
Perrault, P., Perchet, V. & Valko, M.. (2019). Exploiting structure of uncertainty for efficient matroid semi-bandits. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:5123-5132 Available from https://proceedings.mlr.press/v97/perrault19a.html.

Related Material