cs.AIAug 11, 2026

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

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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 MM independent players accelerate elimination further.

Figures & tables

 Sub-Gaussian [ 4 , 6 ]KL (ours)
A2Δalog⁡T(Δa−ε)2\displaystyle\frac{2\Delta_{\bm{a}}\log T}{(\Delta_{\bm{a}}-\varepsilon)^{2}}Δalog⁡TDKL(μa+ε,μ∗)\displaystyle\frac{\Delta_{\bm{a}}\log T}{D_{KL}(\mu_{\bm{a}}+\varepsilon,\mu^{*})}
B4Δalog⁡T(Δa−ε−δ)2\displaystyle\frac{4\Delta_{\bm{a}}\log T}{(\Delta_{\bm{a}}-\varepsilon-\delta)^{2}}2Δalog⁡TDKL(μa+ε,μ∗ ⁣− ⁣δ)\displaystyle\frac{2\Delta_{\bm{a}}\log T}{D_{KL}(\mu_{\bm{a}}+\varepsilon,\mu^{*}\!-\!\delta)}
Ct−K0ε2/(2ln⁡2)t^{-K_{0}\varepsilon^{2}/(2\ln 2)}t−K0DKL(μa+ε,μa)/(2ln⁡2)t^{-K_{0}D_{KL}(\mu_{\bm{a}}+\varepsilon,\mu_{\bm{a}})/(2\ln 2)}
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,000T=100{,}000 .

Explore similar work

CardsList

  1. Trading off rewards and errors in multi-armed bandits

    May 1, 2026Akram Erraqabi, Alessandro Lazaric, Michal Valko +2Multi-Armed BanditsExploration-Exploitation Tradeoff

    Inria SequeL · CMU · EnLearn

  2. Robust Multi-Agent Bandits with Heavy-Tailed Rewards and Information Asymmetry

    Aug 11, 2026Daphne Feng, Ricardo Parada, Lily Jiang +2Multi-Armed BanditsRobust Multi-Armed Bandits

    Department of Mathematics, University of California, Los Angeles, Los Angeles, CA, USA · Department of Mathematics, University of California, Riverside, Riverside, CA, USA

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

    Oct 5, 2026Chenyu GanMulti-Armed BanditsAdversarial Bandits

    Tsinghua University