Square-Root Regret for Adversarial Multiplayer Bandits without Collision Information or Shared Randomness

View PDF HTML (experimental)

Abstract:We study adversarial multiplayer bandits with $K$ arms and $2\le m<K$ labeled players, without collision information, shared randomness, or an external communication channel. We design a constructive communication and synchronization protocol with a Monte Carlo public constructor. With probability at least $1-CN^{-32}$ over preprocessing, where $N=2Km(T+1)$, its fixed published output satisfies \[
R_T\le C K^{5/2}\sqrt T\log^2(2Km(T+1)) \] simultaneously for every oblivious reward sequence chosen after preprocessing. Here $R_T$ is expected regret over the players' private execution randomness. Positive reward observations establish a common learning schedule and synchronize players before learning begins. The cost of delayed communication is charged to the support of positive rewards, ensuring that periods with little useful feedback incur only limited regret. A slow--fast learning procedure then maintains valid reward estimates while assignments and scores are exchanged.

Comments:	84 pages, 2 figures
Subjects:	Machine Learning (cs.LG); Multiagent Systems (cs.MA)
Cite as:	arXiv:2610.05688 [cs.LG]
	(or arXiv:2610.05688v1 [cs.LG] for this version)
	https://doi.org/10.48550/arXiv.2610.05688 arXiv-issued DOI via DataCite (pending registration)

Submission history

From: Chenyu Gan [view email]
[v1] Mon, 5 Oct 2026 02:03:44 UTC (81 KB)