Coordination without communication: optimal regret in two players multi-armed bandits

Sébastien Bubeck, Thomas Budzinski

We consider two agents playing simultaneously the same stochastic three-armed bandit problem. The two agents are cooperating but they cannot communicate. We propose a strategy with…