# Improved Multiplayer Bandit Algorithm for Bernoulli Rewards

arXiv: https://arxiv.org/abs/2609.26213 · HTML: https://mlsanity.com/paper/2609.26213/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 10 references that are in the map.
- First posted on arXiv 11 Aug 2026.

## Builds on (most cited first, 4 of 4)

- [Online Learning for Cooperative Multi-Player Multi-Armed Bandits](https://mlsanity.com/paper/2109.03818/) (2021)
- [Optimal Cooperative Multiplayer Learning Bandits with Noisy Rewards and No Communication](https://mlsanity.com/paper/2311.06210/) (2023)
- [Multiplayer Information Asymmetric Bandits in Metric Spaces](https://mlsanity.com/paper/2503.08004/) (2025)
- [Multiplayer Information Asymmetric Contextual Bandits](https://mlsanity.com/paper/2503.08961/) (2025)

## Abstract (arXiv)

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 textttmKL-UCB, textttmKL-UCB-Intervals and textttmKL-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.