Improved Multiplayer Bandit Algorithm for Bernoulli Rewards
cs.AI, stat.ML
Submitted: 2026-08-11
Updated: 2026-08-11
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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.
Terminology
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 M independent players accelerate elimination further.
Sources
- Optimal Cooperative Multiplayer Learning Bandits with Noisy Rewards and No Communication
- Multiplayer Information Asymmetric Bandits in Metric Spaces
- Multiplayer Information Asymmetric Contextual Bandits
Related papers
- MAVEN-T: Reinforced Heterogeneous Distillation for Real-Time Multi-Agent Trajectory Prediction
- Model Discovery Agent: LLM-assisted Bayesian experiment design for data-efficient discovery of mechanistic world models
- The Clinician's Veto: Navigating Trust, Liability, and Uncertainty in Autonomous AI Prescribing
- MindHelper: Closed-Loop Embodied Mental-State Reasoning for Precision Intervention
- Incumbent Advantage: Brand Bias and Cognitive Manipulation Dynamics in LLM Recommendation Systems
- VSAL: A Vision Solver with Adaptive Layouts for Graph Property Detection