Name
Title | ||
|---|---|---|
Cooperative and Stochastic Multi-Player Multi-Armed Bandit - Optimal Regret With Neither Communication Nor Collisions. |
Abstract | ||
|---|---|---|
We consider the cooperative multi-player version of the stochastic multi-armed bandit problem. We study the regime where the players cannot communicate but have access to shared randomness. In prior work by the first two authors, a strategy for this regime was constructed for two players and three arms, with regret $\tilde{O}(\sqrt{T})$, and with no collisions at all between the players (with very high probability). In this paper we show that these properties (near-optimal regret and no collisions at all) are achievable for any number of players and arms. At a high level, the previous strategy heavily relied on a $2$-dimensional geometric intuition that was difficult to generalize in higher dimensions, while here we take a more combinatorial route to build the new strategy. |
Year | Venue | DocType |
|---|---|---|
2021 | COLT | Conference |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sébastien Bubeck | 1 | 1472 | 92.28 |
| Thomas Budzinski | 2 | 0 | 0.34 |
| Mark Sellke | 3 | 14 | 2.11 |