Statistically Efficient, Polynomial Time Algorithms for Combinatorial Semi Bandits

Thibaut Cuvelier, Richard Combes, Eric Gourdin

We consider combinatorial semi-bandits over a set of arms $\mathcal{X}\subset \{0,1{\}}^d$ where rewards are uncorrelated across items. For this problem, the algorithm ESCB yields the…