PaperlayerView exact revision on arXiv

Source-linked AI summary

Improved Multiplayer Bandit Algorithm for Bernoulli Rewards

Khang Nguyen, Ricardo Parada, William Chang

arXiv:2609.26213v1cs.AIstat.ML

TL;DR

Prior multiplayer bandit bounds use sub-Gaussian widths that do not adapt to Bernoulli means, even though rewards can have extreme success probabilities. The paper develops three KL-based algorithms for different information asymmetries, improving regret guarantees over sub-Gaussian baselines, with the largest gains at extreme means.

  • Problem

    Prior multiplayer bounds use sub-Gaussian confidence widths that do not adapt to Bernoulli means, despite binary rewards often having extreme success probabilities.

    Source: §I · p. 1

  • Method

    The paper introduces mKL-UCB, mKL-UCB-Intervals, and mKL-DSEE, replacing squared-error terms with KL divergence terms across three information-asymmetry settings.

    Source: §I · p. 1

  • Results

    Across all three settings, KL-based algorithms improve over sub-Gaussian baselines, with the largest gains for extreme reward means.

    Source: §I · p. 1, §VII · p. 5

  • Takeaways & Limitations

    For reward asymmetry, the paper gives a deterministic condition for two KL intervals to separate and an M-fold gain from independent players.

    Source: §VII · p. 5

    For reward-asymmetry elimination, doubling gives an O(log^2 T) bound, and whether O(log T) is possible without knowing T remains open.

    Source: §VII · p. 5

Abstract

from arXiv · show

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.

I. INTRODUCTION

Multiplayer bandits model decentralized decisions without communication, but prior sub-Gaussian bounds do not adapt to Bernoulli reward means. The paper replaces squared-error terms with KL divergence in three algorithms, tightening regret guarantees, especially for extreme means.

Background

  • The MAB’s optimal regret scales as Θ(log T), with a constant determined by KL divergence between arm distributions.For Bernoulli rewards, KL-UCB uses Chernoff-type concentration to obtain tighter finite-time bounds than generic sub-Gaussian analyses.Source: §I · p. 1

Setting

  • The information-asymmetric framework allows players to observe different actions or reward realizations but forbids communication during learning.It models decentralized multiplayer applications such as multi-stakeholder recommendation and network routing.Source: §I · p. 1

Motivation

  • At mean 0.01 the stated improvement factor is 50, and at 0.001 it is 500, while the worst case at 0.5 is 2.Hoeffding-style bounds use the same confidence width for Bernoulli(0.01) and Bernoulli(0.5), whereas the KL exponent adapts to the mean.Source: §I · p. 1

Contributions

  • The paper proposes mKL-UCB for action asymmetry, mKL-UCB-Intervals for reward asymmetry, and phased mKL-DSEE for both.The action-asymmetry leading term matches the Lai–Robbins lower bound; the reward-asymmetry analysis characterizes when KL intervals separate.Source: §I · p. 1

II. PROBLEM SETTING AND PRELIMINARIES

Each round, players choose components of a joint arm and receive Bernoulli rewards, with observations depending on the information-asymmetry setting. Bernoulli KL bounds provide valid confidence intervals that can be tighter than Hoeffding intervals, especially near reward means of zero or one.

Problem setting

  • Across the three settings, players may share a reward, observe one another’s actions, both, or neither, while choosing joint actions from [K]^M.The joint arm has unknown Bernoulli mean; players may agree on a strategy beforehand but cannot communicate during play.Source: §II · p. 1

KL concentration

  • For Bernoulli samples, the upper- and lower-tail probabilities are bounded by exponentials whose rates are n times the corresponding KL divergences.The supplied bounds use DKL(µ+ε, µ) and DKL(µ−ε, µ) for the two tails.Source: §II · p. 2
  • Pinsker’s inequality gives DKL(p, q) ≥ 2(p−q)^2, recovering Hoeffding’s tail bound and making the KL exponent strictly stronger when µ differs from 1/2.The KL interval endpoints trap the true mean with probability at least 1−2e^(−nα); KL monotonicity also supplies quantitative slack for interval tightening.Source: §II · p. 2

Confidence intervals

  • Unlike the Hoeffding interval’s mean-independent width, the KL set narrows as the empirical mean approaches zero or one.The passage describes this KL set as always lying inside the sub-Gaussian interval.Source: §II · p. 2

III. PROBLEM A: ASYMMETRY IN ACTIONS

mKL-UCB applies a KL-UCB index to joint arms, using shared rewards and deterministic tie-breaking to let players reconstruct the actions that generated observations. Its leading regret term matches the Lai–Robbins lower bound, while Pinsker implies a strictly larger sub-Gaussian constant.

Index construction

  • The KL-UCB index is defined over joint arms using the largest mean in the KL confidence set, with threshold log f(t) and f(t)=1+t log^2 t.The threshold is stated to yield a uniform-in-time bound and asymptotic optimality.Source: §III · p. 2

Coordination

  • Because all players share rewards and apply the same deterministic index rule and lexicographic tie-break, each can reconstruct every joint action.Private randomization or randomized tie-breaking would decouple those reconstructions; the resulting single-agent problem has KM joint arms.Source: §III · p. 2

Regret guarantee

  • Algorithm 1’s leading regret term uses Δa/DKL(µa, µ*) and matches the Lai–Robbins lower bound.The proof lifts a single-agent KL-UCB analysis to [K]^M and establishes asymptotic optimality among consistent algorithms.Source: §III · p. 2
  • Pinsker’s inequality makes the sub-Gaussian constant 2/Δa strictly larger than the KL-based constant.The KL bound therefore improves the leading regret constant over the sub-Gaussian comparison.Source: §III · p. 2

IV. PROBLEM B: ASYMMETRY IN REWARDS

For reward-asymmetric players, mKL-UCB-Intervals uses KL confidence intervals and observable deviations to eliminate suboptimal joint arms. The resulting intervals separate far sooner than Hoeffding intervals, and independent players improve the suboptimal-arm count bound.

IV. PROBLEM B: ASYMMETRY IN REWARDS

  • Players cycle through a shared desired set of joint arms; a player signals a dominated arm by deviating, and all players observe the deviation and remove that arm.Players update their own intervals from independent rewards while observing the joint action.Source: §IV · pp. 2–3
  • The analysis uses a fixed 2 log T threshold because permanent elimination makes an early exclusion of the optimal arm costly: every later round then incurs ∆max regret.The paper notes that an anytime threshold can briefly exclude the true mean early on.Source: §IV · p. 2
  • ≈535 KL samples versus ≈28,800 Hoeffding samples (≈54×) at the stated parameter values; KL intervals separate within O(10^3) samples while Hoeffding intervals do not separate within the horizon.The parameters are µ_a = 0.05, µ* = 0.15, ε_1 = ε_2 = 0.02, and T = 10^5.Source: §IV · p. 3
  • The expected average suboptimal-arm count satisfies E[barκ] ≤ 2 log T / D_KL(µ_a + ε_1, τ′) + 1 / [M D_KL(µ_a + ε_1, µ_a)].Step (⋆) is where M enters the exponent rather than the prefactor.Source: §IV · p. 3
  • 0.0227 versus 0.0018 (12.6×): the KL divergence term exceeds the sub-Gaussian analogue at µ_a = 0.1 and µ* = 0.2, with ε_1 = ε_2 = 0.02.The paper also reports that the 1/M term improves analogously and that the asymptotic constant is twice the Lai–Robbins bound because of the fixed threshold.Source: §IV · p. 4

V. PROBLEM C: ASYMMETRY IN BOTH

mKL-DSEE synchronizes deterministic exploration so players can identify sampled joint arms despite unshared actions and rewards. Its KL-based analysis yields stronger tail exponents, with a regret bound independent of T when f(λ) = λ.

V. PROBLEM C: ASYMMETRY IN BOTH

  • With a unique optimal joint action, players explore in an agreed sequence and use only exploration samples to select their exploitation action.Exploration starts at powers of two; tied optima can cause different commitments and linear regret.Source: §V · p. 4
  • With f(λ) = λ, K0(t) = Θ((log2 t)^2) and the regret bound is independent of T.The bound combines exploration cost across phases with the probability of a suboptimal exploitation choice, controlled by KL-tail exponents.Source: §V · p. 4
  • KL exponents dominate the sub-Gaussian exponent, so fewer exploration samples suffice for the same error, though the optimal f still depends on the unknown minimum gap.The faster decay permits a slower-growing f; the unknown-gap dependence remains a cost of having no shared information.Source: §V · p. 4

VI. EXPERIMENTS

Across the simulated settings, KL variants substantially reduced regret in Problems A and B, while Problem C showed only a marginal gap at the fixed exploration schedule. The experiments used low-mean instances, and the predicted advantage varies with reward means.

VI. EXPERIMENTS

  • The simulations used T = 100,000 and means in [0.02, 0.15]; Problem A had 9 joint arms, while Problems B and C used 3 players and 4 arms.Results were averaged over 10 runs; the variants changed confidence bounds in Problems A and B, not the Problem C procedure.Source: §VI · p. 4
  • ≈7.6×: mKL-UCB reduced Problem A regret from 1,900 to 250; on Problem B, mKL-UCB-Intervals plateaued near 700 while the Hoeffding variant grew past 3,000.The Problem A reduction was close to the predicted factor of ≈9.1; the Problem B plateau followed interval separation.Source: §VI · p. 5, Figure 1 · p. 5
  • Problem C showed only a marginal gap: at the fixed schedule both variants pay the same exploration cost, which dominates at this horizon.The KL exponent permits a smaller exploration schedule, but both variants used f(λ) = λ.Source: §VI · pp. 4–5
  • The predicted improvement factor is 2 at μ = 1/2, exceeds 5.6 for μ < 0.1 or μ > 0.9, and implies a smaller visible gap in Problem C.The factor stays within 20% of 2 for μ in [0.30, 0.70]; in Problems A and B it multiplies the leading log T term.Source: §VI · p. 5

VII. DISCUSSION AND CONCLUSION

The three Bernoulli algorithms improve on sub-Gaussian baselines, with the largest gains at extreme means. The discussion bounds where those gains apply and identifies costs of irreversible elimination and limits on pooling players’ samples.

VII. DISCUSSION AND CONCLUSION

  • All three algorithms improve on sub-Gaussian baselines, with the largest gains for extreme reward means.The centerpiece for reward asymmetry is a deterministic condition for two KL intervals to separate, plus an M-fold gain from independent rewards.Source: §VII · p. 5
  • The KL arguments extend to any one-parameter exponential family, but gains are largest for Bernoulli and at most constant when variance stays bounded away from zero.The gain factor is 1/(2V(µ)); for Bernoulli, V(µ) = µ(1 − µ) shrinks at the boundary.Source: §VII · p. 5
  • Because elimination is irreversible, one wrong removal of a* costs Θ(T), requiring the probability of any interval ever excluding its mean to be O(1/T).Source: §VII · p. 5
  • Doubling yields O(log^2 T), while whether O(log T) anytime elimination can avoid knowing T remains open.Source: §VII · p. 5
  • The M-fold gain sits in the additive term: the leading log T term depends on one player’s interval-separation samples, and no communication prevents pooling.All players pull the same joint arm each round, and pooling those samples would divide the leading term by M.Source: §VII · p. 5
Loading 2609.26213v1…