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

Chenyu Gan

cs.LGOct 5, 2026

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

Authors: Chenyu Gan

Organizations: Tsinghua University

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.

Figures & tables

Panel of Figure 1 — Figure 1: Physical workflow. The reference correction (Algorithm 2 ) and logical learner (Algorithm 3 ) are only used for analysis, so they are not included.

Slot	Probability	Role
DATA	$1/2$	Play arms and possibly record one reward.
DOWN	$1/4$	Send an assignment and confirm that its recipient decoded it.
UP	$1/4$	Return a score, or certify that the coordinator received all assignment receipts.

Table 2

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Component	Stored data	Detailed construction
Masks	$C=(C_{q,t})_{q\in[M],\,t\in[T]}$ , with $C_{q,t}\in\{0,1\}$ .	Algorithm 10 .
Code	$G\in\mathbb{F}_{2}^{H_{\rm arr}\times B_{\rm arr}}$ , shared by all bootstrap columns.	Subsection B.3 and Lemma 28 .
Bootstrap arrays	For each player $s$ , block $b$ , and column $w$ , the published permutation $\pi_{s,b,w}$ ; for each position $t$ , the variables $\lambda_{s,b,w,t}$ , $b_{s,b,w}(t)$ , $(a_{0,s,b,w,t},a_{1,s,b,w,t})$ , $j_{s,b,w,t}$ , and $z_{s,b,w,t}$ , determining the arm maps $c_{s,b,w,t}(\nu)$ and $d_{s,b,w,t}(\nu)$ .	Subsections B.2 and B.3 ; Figure 2 .
Control rows	$(R_{q})_{q\in[M]}$ , with the finite coordinate and hash namespaces specified in Subsection B.4 .	Subsection B.4 .

Appendix

Table 1: Components of the public table on the construction branch.

Panel of Figure 2 — Figure 2: One public arm-array column, where $I_{b}^{+}=\{t_{1}<\cdots<t_{r}\}$ . The code matrix $G$ is shared across columns; $a_{0},a_{1}$ in the candidate formula are the pair stored at position $t$ . Player and block indices are suppressed inside the column.

Explore similar work

Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization
Aug 4, 2026Taira TsuchiyaFollow-the-Regularized-Leader Regret Minimization
The University of Tokyo and RIKEN
m-Set Adversarial Bandits with Winner Feedback
Oct 7, 2026Nicolò Cesa-Bianchi, Matteo PapiniMulti-Armed Bandits Adversarial Bandits
Universit`a degli Studi di Milano · Politecnico di Milano
Constant Swap Regret in General-Sum Games via Optimistic Transition Matrices
Sep 15, 2026Tung MaiGame Theory Decentralized Learning
Adobe Research

Aug 4, 2026, cs.GTJ/K move · Enter open · S save

Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization

Taira Tsuchiya

The University of Tokyo and RIKEN

Follow-the-Regularized-Leader Regret Minimization

Open paper AskPDF arXiv

Swap regret governs the rate at which uncoupled learning dynamics converge to correlated equilibria in multiplayer general-sum games. Under full-information feedback, the best previous guarantee when every player follows the same dynamics grows logarithmically in the horizon

T

. We construct uncoupled dynamics under which every player incurs only

O(nm^2\sqrt{\log m\log T})

swap regret, where

n

is the number of players and

m

bounds the number of actions per player. To our knowledge, this is the first sublogarithmic individual guarantee in this setting, and it implies that the time-averaged product distribution of play is an

O(nm^2\sqrt{\log m\log T}/T)

-approximate correlated equilibrium. The key algorithmic choice is to combine the Blum--Mansour reduction with optimistic follow-the-regularized-leader using a hybrid regularizer that separately weights negative Shannon entropy and the log-barrier: the entropy controls the optimistic prediction error, whereas the log-barrier controls the transition-matrix movement through its Bregman divergence. A new sensitivity theorem for stationary distributions of Markov chains, which involves neither mixing parameters nor the smallest transition probability, transfers this control to the played strategies and yields a simpler analysis without local-norm or self-concordance arguments. The guarantee is preserved by an adversarially robust variant that additionally ensures

O(nm^2\sqrt{\log m\log T}+\sqrt{mT\log m})

swap regret against arbitrary utility sequences, and by a horizon-free variant that requires no prior knowledge of

T

Abstract

Explore similar work

Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization

m-Set Adversarial Bandits with Winner Feedback

Constant Swap Regret in General-Sum Games via Optimistic Transition Matrices