Square-Root Regret for Adversarial Multiplayer Bandits without Collision Information or Shared Randomness
Chenyu Gan
cs.LG
Oct 5, 2026 · v3
cs.MA
TL;DR
The paper's mathematical results, excluding the computational complexity claims, are formalized in Lean, with a public repository.
Abstract
We study cooperative multiplayer bandits with adversarial rewards and no collision information. In each of $T$ rounds, each of $m$ labeled players picks one of $K>m$ arms. A player alone on its arm receives that arm's reward in $[0,1]$; players who share an arm receive $0$. Each player observes only its own reward, so it cannot distinguish a collision from an arm with zero reward, and there is neither shared randomness nor a communication channel. Bubeck, Li, Peres and Sellke (2020) obtained regret $\widetilde O(KT^{3/4})$ for two players and $\widetilde O(mK^{3/2}T^{1-1/(2m)})$ for $m$ players, and conjectured that regret $Ω(T^{2/3})$ is unavoidable already for two players. We refute this conjecture. We give a strategy whose expected regret against every oblivious adversary is $O(m^{3/2}\sqrt{KT}\log^2(KmT))$, which is optimal in $K$ and $T$ up to logarithmic factors. Three ideas make this possible. (i) Bits are sent through deliberate collisions as random parity checks, and the regret spent while a message is delayed is charged to the number of arms with positive reward rather than to elapsed time: an adversary that jams the channel with zero rewards forfeits the regret it could inflict. (ii) An exponential-weights learner over sets of arms combines a frequently resampled coordinator arm with a follower assignment that changes only $O(\sqrt{mT/K})$ times in expectation; delayed updates are reconstructed exactly. (iii) We teach the followers a privately chosen row index in a fixed public table using reward observations alone, allowing them to coordinate without shared randomness. The bound holds simultaneously for all reward matrices, even ones chosen with knowledge of the table, and a random table works with probability $1-O(1/(KmT))$.
Problem
In cooperative adversarial multiplayer bandits, m players choose among K arms and a collision yields zero reward. Players get no collision information and have no shared randomness. Bubeck, Li, Peres and Sellke conjectured that regret Ω(T^{2/3}) is unavoidable already for two players.
Approach
Players send bits through deliberate collisions that act as random parity checks. Regret incurred while a message is delayed is charged to the number of arms with positive reward rather than to elapsed time. An exponential-weights learner over sets of arms pairs a frequently resampled coordinator arm with slowly changing follower assignments. Followers learn a privately chosen row of a fixed public table from reward observations alone, which replaces shared randomness. The mathematical results are formalized in Lean.
Results
Expected regret against every oblivious adversary is O(m^{3/2} sqrt(KT) log^2(KmT)), which is optimal in K and T up to logarithmic factors and refutes the conjecture. A random public table works with probability 1-O(1/(KmT)).