Improved Multiplayer Bandit Algorithm for Bernoulli Rewards
Authors: Khang Nguyen, Ricardo Parada, William Chang
Organizations: 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
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.
Figures & tables
Sub-Gaussian [ 4 , 6 ]
KL (ours)
A
(Δa−ε)22ΔalogT
DKL(μa+ε,μ∗)ΔalogT
B
(Δa−ε−δ)24ΔalogT
DKL(μa+ε,μ∗−δ)2ΔalogT
C
t−K0ε2/(2ln2)
t−K0DKL(μa+ε,μa)/(2ln2)
TABLE I: Leading Regret Terms: Sub-Gaussian vs. KL-Based Bounds
Figure 1: Cumulative regret (solid: Hoeffding baseline; dashed: KL algorithm). Average over 10 runs, T=100,000 .
In multi-armed bandits, the most-explored arms are the most informative, while reward maximization typically pulls only the best arm. We study the tradeoff between identifying arm means accurately and accumulating reward, and present an algorithm with regret guarantees that interpolates between the two objectives. We provide both upper and lower bounds and validate empirically.
Akram Erraqabi, Alessandro Lazaric, Michal Valko +2
The multi-armed bandit problem is a central framework in sequential decision-making, extensively studied under sub-Gaussian reward assumptions. However, real-world applications often involve heavy-tailed reward distributions and decentralized, information-asymmetric interactions. We study multi-agent multi-armed bandits with heavy-tailed rewards under three information-asymmetry regimes: unobserved actions with common rewards, observed actions with independent rewards, and unobserved actions with independent rewards. We develop robust decentralized algorithms for each setting and derive regret guarantees that nearly match centralized heavy-tailed rates. Experiments on a Pareto-distributed reward environment validate our theoretical findings and illustrate the trade-offs between synchronization, coordination, and exploration across the three regimes.
Daphne Feng, Ricardo Parada, Lily Jiang +2
Department of Mathematics, University of California, Los Angeles, Los Angeles, CA, USA · Department of Mathematics, University of California, Riverside, Riverside, CA, USA
We study adversarial multiplayer bandits with K arms and 2≤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
RT≤CK5/2Tlog2(2Km(T+1))
simultaneously for every oblivious reward sequence chosen after preprocessing. Here RT 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.