Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time
This addresses the computational bottleneck for implementing asymptotically optimal algorithms in combinatorial semi-bandits, which is incremental but practically important for bandit optimization.
The paper tackled the problem of computing asymptotically optimal strategies for combinatorial semi-bandits with uncorrelated Gaussian rewards, achieving the first polynomial-time method for solving the Graves-Lai optimization problem for many combinatorial structures.
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.