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.
Keywords
Subject
Publication details
- Journal
- Not available
- Open access
- Green open access
Cite this article
APA 7
Gan, C. (2026). Square-Root Regret for Adversarial Multiplayer Bandits without Collision Information or Shared Randomness. https://omanscience.com/en/articles/square-root-regret-for-adversarial-multiplayer-bandits-without-collision-information-or-shared-randomness
MLA 9
Gan, Chenyu. "Square-Root Regret for Adversarial Multiplayer Bandits without Collision Information or Shared Randomness." https://omanscience.com/en/articles/square-root-regret-for-adversarial-multiplayer-bandits-without-collision-information-or-shared-randomness.
Chicago (author–date)
Gan, Chenyu. 2026. "Square-Root Regret for Adversarial Multiplayer Bandits without Collision Information or Shared Randomness." https://omanscience.com/en/articles/square-root-regret-for-adversarial-multiplayer-bandits-without-collision-information-or-shared-randomness.
Harvard
Gan, C. (2026) 'Square-Root Regret for Adversarial Multiplayer Bandits without Collision Information or Shared Randomness', Available at: https://omanscience.com/en/articles/square-root-regret-for-adversarial-multiplayer-bandits-without-collision-information-or-shared-randomness.
Vancouver
Gan C. Square-Root Regret for Adversarial Multiplayer Bandits without Collision Information or Shared Randomness. https://omanscience.com/en/articles/square-root-regret-for-adversarial-multiplayer-bandits-without-collision-information-or-shared-randomness
IEEE
C. Gan, "Square-Root Regret for Adversarial Multiplayer Bandits without Collision Information or Shared Randomness," https://omanscience.com/en/articles/square-root-regret-for-adversarial-multiplayer-bandits-without-collision-information-or-shared-randomness.