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

arXiv:2610.05688v1 Announce Type: new Abstract: We study adversarial multiplayer bandits with K arms and 2le 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_Tle C K^{5/2}sqrt Tlog^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.

Source: arXiv cs.LG | 2026-10-06