aiqbench analysis
This paper advances the theoretical foundations of distributed machine learning by introducing tighter regret guarantees for multiplayer bandit problems with information asymmetry. By substituting standard Hoeffding bounds with Kullback-Leibler divergence-based intervals, the proposed algorithms achieve significantly improved performance, particularly in scenarios involving Bernoulli rewards near extreme probabilities. The work offers a rigorous contribution to the field of multi-agent reinforcement learning and collaborative decision-making under uncertainty.
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.
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.
Artificial Intelligence (cs.AI); Machine Learning (stat.ML)
arXiv:2609.26213 [cs.AI]
(or arXiv:2609.26213v1 [cs.AI] for this version)
https://doi.org/10.48550/arXiv.2609.26213 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 199 words
Related coverage
Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent
arXiv · Sep 30, 2026
Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms
arXiv · Aug 17, 2026
Latent Order Bandits
arXiv · Aug 20, 2026
RepUCB: Representation Learning-Based UCB for Heterogeneous Multi-Task Linear Bandits
arXiv · Sep 23, 2026