Characterizing Oblivious Common-Reward Multi-Player Bandits: Universal Stationarity, Coordination Traps, and Certified Global Rates

Mingxiao Li; Wenhai Lai; Hongyu Wang

cs.LGOct 21, 2026

Characterizing Oblivious Common-Reward Multi-Player Bandits: Universal Stationarity, Coordination Traps, and Certified Global Rates

Authors: Mingxiao Li, Wenhai Lai, Hongyu Wang

Abstract

This paper presents a theoretical analysis of the oblivious common-reward multi-player multi-armed bandit (OC-MPMAB), a minimal multi-player bandit model in which multiple players select arms simultaneously and observe only a shared reward. Crucially, the players are fully oblivious: they do not observe the actions of other players and do not even know whether any other players exist. The contributions of this work are threefold. First, we prove that the independent gradient-bandit updates applied by the players jointly form an unbiased stochastic gradient estimator of a hidden product-policy objective. This property then yields a universal finite-time first-order stationarity guarantee for every instance. Second, we show that stationarity cannot, in general, be strengthened to global optimality. To illustrate this, we identify a product-policy trap obstruction that rules out the guarantee of global optimality. Third, we show that global optimality can be recovered under structural assumptions on the reward table. To make global optimality achievable, we introduce finite-table certificates that separately characterize product-gradient dominance and self-bounding stochastic noise. We then establish certificate-conditioned bounds on the product-policy gap and pseudo-regret. Consequently, the standard $O(1/t)$ product-policy gap and $O(\log T)$ pseudo-regret rates hold when the certificates are uniform.

Figures & tables

Figure 1: Sparse coordination (left), block trap (center), and AI routing (right); bands show 95% CIs.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Instance	Region $c$	$\underline{\lambda}$	$\overline{M}$
Sparse $N=3,K=2$	$0.25$	$2.71{\times}10^{-5}$	$148.76$
Dense additive $N=3,K=2$	$0.25$	$6.94{\times}10^{-3}$	$147.70$
Dense interaction $N=3,K=2$	$0.25$	$2.78{\times}10^{-4}$	$346.23$

Appendix

Table 1: Hybrid analytic and interval certificates for binary-arm tables. The checker combines analytic lower bounds for

\lambda_{\star}(c)

with fixed-depth rational interval upper bounds for

M_{\rm all}(c)

Reference	Online information	Interpretation
Independent update	own arm + common reward	matched learner
Moving-baseline variant	own arm + common reward	matched ablation
Checker	offline reward table	offline certificate or diagnostic check
Centralized learner	joint actions or policy	upper-info reference
Comm. bandit	messages or rewards	different protocol

Appendix

Table 2: Information-model reference. Centralized or communicating methods can serve as upper-information references, but they are not protocol-matched baselines for fully oblivious learners.

Reference	Final gap	$\pi(\bm{a}^{\star})$	Avg. pseudo-regret
Independent default	$0.1037$	$4.77{\times}10^{-6}$	$0.1274$
Centralized joint-action	$0.0270$	$0.7443$	$0.0595$

Appendix

Table 3: Upper-information reference on the block trap. The centralized learner has access to joint-action information and is not protocol matched to the independent update.

Figure 1: Coordinate block trap. Left: trajectories from default and opt-biased initializations. Right: final optimal-profile probability over the initial preference gaps.

Instance	No baseline $\eta$	Gap	Moving baseline $\eta$	Gap
Sparse	$0.30$	$0.0011$	$0.30$	$0.0011$
Additive	$0.20$	$0.0133$	$0.30$	$0.0054$
Block trap	$0.30$	$0.0922$	$0.30$	$0.0963$

Appendix

Table 4: Protocol-matched stepsize and baseline ablation. Both variants use only the sampled local arm and the common reward.

Multi-Agent Bandits

See all 15 papers

Oct 5, 2026

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

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.

Chenyu Gan

Tsinghua University

Multi-Armed Bandits Adversarial Bandits

Ask PDF

Oct 13, 2026

Approximating Optimal Policies in Heterogeneous Asynchronous Multi-player Bandits

Motivated by applications to cognitive radio networks, multi-player multi-armed bandits (MMAB) have attracted considerable attention in recent years. The asynchronous variant, in which players are active only at a fraction of timesteps, better reflects real-world decentralized networks, where devices are not permanently active. Despite its practical relevance, this setting remains relatively understudied. Existing work on asynchronous MMAB has focused on homogeneous players, who share the same activation probability, a setting in which the optimal centralized allocation can be easily characterized. In contrast, efficiently computing the optimal allocation in the heterogeneous setting, where players have different activation probabilities, has remained an open problem. In this work, we investigate this problem and first establish its NP-hardness. We then turn to the greedy algorithm, which runs in polynomial time, and prove that it achieves a

\frac{1}{e}

-approximation of the optimal allocation. Furthermore, when players are processed in decreasing order of their activation probabilities, the approximation guarantee improves to

\frac{1}{\sqrt{e}}

. Overall, our results establish the greedy algorithm as an efficient approximation to the optimal allocation, providing a practical oracle baseline for the design of online algorithms for heterogeneous asynchronous multi-player bandits.

Sacha Arroues-Paykin, Etienne Boursier, Vianney Perchet

Ecole Polytechnique · INRIA, LMO, Université Paris-Saclay · CREST, ENSAE

Multi-Armed Bandits Multi-Agent Bandits Approximation Algorithms Combinatorial Optimization

Ask PDF

Aug 11, 2026

Improved Multiplayer Bandit Algorithm for Bernoulli Rewards

We study the multiplayer multi-armed bandit problem with information asymmetry under Bernoulli rewards, for three information structures: asymmetry in actions, in rewards, and in both. Replacing the Hoeffding-style confidence intervals of prior work with Kullback--Leibler (KL) divergence-based bounds gives strictly tighter regret guarantees in each case. We propose mKL-UCB, mKL-UCB-Intervals and mKL-DSEE, and show that the improvement factor is at least two by Pinsker's inequality and far larger when reward means are near zero or one. For asymmetry in rewards we prove that two arms' KL intervals separate after a deterministic number of samples, and that

M

independent players accelerate elimination further.

Khang Nguyen, Ricardo Parada, William Chang

Dept. of Computer Science University of California, Los Angeles Los Angeles, CA, USA · Dept. of Electrical and Computer Engineering University of California, Los Angeles Los Angeles, CA, USA

Multi-Agent Bandits Multi-Armed Bandits

Ask PDF

Abstract

Multi-Agent Bandits

Explore similar work

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

Approximating Optimal Policies in Heterogeneous Asynchronous Multi-player Bandits

Improved Multiplayer Bandit Algorithm for Bernoulli Rewards