
KN
Khang Nguyen, Ricardo Parada, William Chang
· 1 min read
ResearcharXiv cs.AI
Improved Multiplayer Bandit Algorithm for Bernoulli Rewards
arXiv:2609.26213v1 Announce Type: new
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.
Original source
This story was published by arXiv cs.AI and written by Khang Nguyen, Ricardo Parada, William Chang. SyncAI.news shows a preview; the complete article is on the publisher's site.
Read the full story on arxiv.org


