118 citations · 405 across the 29 of their papers we have counts for
31 papers
Exponential Backoff: Meta-Stability and Implicit Admission Control
Richard Combes, Fabien Mathieu, Thomas Bonald
We analyze exponential backoff, an algorithm used to share a single communication channel in a distributed manner between several users, in a similar way as many networking standar…
Towards Optimal Algorithms for Multi-Player Bandits without Collision Sensing Information
Wei Huang, Richard Combes, Cindy Trinh
We propose a novel algorithm for multi-player multi-armed bandits without collision sensing information. Our algorithm circumvents two problems shared by all state-of-the-art algor…
A High Performance, Low Complexity Algorithm for Multi-Player Bandits Without Collision Sensing Information
Cindy Trinh, Richard Combes
Motivated by applications in cognitive radio networks, we consider the decentralized multi-player multi-armed bandit problem, without collision nor sensing information. We propose…
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…
Solving Random Parity Games in Polynomial Time
Richard Combes, Mikael Touati
We consider the problem of solving random parity games. We prove that parity games exibit a phase transition threshold above , so that when the degree of the graph that define…