  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.
