Exploiting Structure of Uncertainty for Efficient Matroid Semi-Bandits
This work addresses efficiency issues in combinatorial semi-bandit algorithms for researchers and practitioners in machine learning, offering incremental improvements in regret bounds.
The paper tackles the inefficiency of algorithms for stochastic combinatorial semi-bandits by reducing their implementation to submodular maximization and designing adapted approximation routines for matroid constraints, resulting in an improved efficient gap-free regret bound by a factor of √m/log m, where m is the maximum action size.
We improve the efficiency of algorithms for stochastic \emph{combinatorial semi-bandits}. In most interesting problems, state-of-the-art algorithms take advantage of structural properties of rewards, such as \emph{independence}. However, while being optimal in terms of asymptotic regret, these algorithms are inefficient. In our paper, we first reduce their implementation to a specific \emph{submodular maximization}. Then, in case of \emph{matroid} constraints, we design adapted approximation routines, thereby providing the first efficient algorithms that rely on reward structure to improve regret bound. In particular, we improve the state-of-the-art efficient gap-free regret bound by a factor $\sqrt{m}/\log m$, where $m$ is the maximum action size. Finally, we show how our improvement translates to more general \emph{budgeted combinatorial semi-bandits}.