Exploiting structure of uncertainty for efficient matroid semibandits
[edit]
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:51235132, 2019.
Abstract
We improve the efficiency of algorithms for stochastic combinatorial semibandits. In most interesting problems, stateoftheart 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 stateoftheart efficient gapfree 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 semibandits.
Related Material


