79 citations · 93 across the 9 of their papers we have counts for
7 papers · 1 filter
Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time
Thibaut Cuvelier, Richard Combes, Eric Gourdin
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 s…
On the Suboptimality of Thompson Sampling in High Dimensions
Raymond Zhang, Richard Combes
In this paper we consider Thompson Sampling (TS) for combinatorial semi-bandits. We demonstrate that, perhaps surprisingly, TS is sub-optimal for this problem in the sense that its…
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 where rewards are uncorrelated across items. For this problem, the algorithm ESCB yields the…
Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling
Cindy Trinh, Emilie Kaufmann, Claire Vernade +1
Stochastic Rank-One Bandits (Katarya et al, (2017a,b)) are a simple framework for regret minimization problems over rank-one matrices of arms. The initially proposed algorithms are…
Computationally Efficient Estimation of the Spectral Gap of a Markov Chain
Richard Combes, Mikael Touati
We consider the problem of estimating from sample paths the absolute spectral gap of a reversible, irreducible and aperiodic Markov chain over a fi…
Minimal Exploration in Structured Stochastic Bandits
Richard Combes, Stefan Magureanu, Alexandre Proutiere
This paper introduces and addresses a wide class of stochastic bandit problems where the function mapping the arm to the corresponding reward exhibits some known structural propert…