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

Abstract

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 no collisions at all between the players (with very high probability), and with near-optimal regret $O(\sqrt{T\log (T)})$. We also argue that the extra logarithmic term $\sqrt{\log (T)}$ should be necessary by proving a lower bound for a full information variant of the problem.

28 pages, 5 figures. V2: minor revision