Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 14 min ago
PreprintCC BY 4.0arXiv

Improved Multiplayer Bandit Algorithm for Bernoulli Rewards

  • Khang Nguyen
  • Ricardo Parada
  • William Chang
Open at sourcePDFDOICite

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 \texttt{mKL-UCB}, \texttt{mKL-UCB-Intervals} and \texttt{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.

Related

  1. Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization
    Shion Takeno, Shogo Iwazaki
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  2. An Adaptive Symplectic Proximal Point Algorithm: Faster Convergence and Improved Numerical Performance
    Yi Zhang
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  3. Accelerating the Improved Arrow--Hurwicz Iteration via the Anderson Algorithm for Steady-State Navier--Stokes Equations
    Sinan Ergen, Mustafa Ağgül, Mustafa Türkyılmazoğlu
    arXivPreprintCC0Full textNumerical analysis & scientific computingarXiv
  4. A novel deep learning prediction method for PM2.5 integrating improved MSTL decomposition and FATA optimization algorithm
    Xiaoliang Zhao, Pinyuan Qiao, Bandna Bharti +5
    PLOS OnePeer-reviewedCC BY 4.0Full textEnvironmental science & pollutionStatisticsPLOS
  5. An improved randomized algorithm for finding sinks of Acyclic Unique Sink Orientations of the binary hypercube
    Thomas Dueholm Hansen, Uri Zwick
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{nguyen2026improved,
  title = {{Improved Multiplayer Bandit Algorithm for Bernoulli Rewards}},
  author = {Khang Nguyen and Ricardo Parada and William Chang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.26213},
  eprint = {2609.26213},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.26213},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Improved Multiplayer Bandit Algorithm for Bernoulli Rewards
AU  - Khang Nguyen
AU  - Ricardo Parada
AU  - William Chang
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.26213
UR  - https://arxiv.org/abs/2609.26213
AB  - 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 \texttt{mKL-UCB}, \texttt{mKL-UCB-Intervals} and \texttt{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.
ER  -