Covariance-adapting algorithm for semi-bandits with application to sparse rewards

Pierre Perrault, Vianney Perchet, Michal Valko

We investigate stochastic combinatorial semi-bandits, where the entire joint distribution of outcomes impacts the complexity of the problem instance (unlike in the standard bandits…