Source-linked AI summary
The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond
Aurélien Garivier, Olivier Cappé
TL;DR
The paper asks how to obtain efficient, horizon-free policies for stochastic bandits under bounded rewards and selected distributional families. It analyzes KL-UCB and adaptations using divergence-based confidence bounds, showing improved bounded-reward guarantees, Bernoulli lower-bound optimality, and strong practical performance.
Problem
Stochastic bandit policies must balance exploration and exploitation, while existing approaches provide limited guarantees across bounded and parametric reward settings.
Method
The paper analyzes KL-UCB, an untuned online index policy, and adapts its divergence to selected reward families including canonical exponential families.
Results
KL-UCB has strictly better theoretical guarantees than UCB for bounded rewards, reaches the Lai–Robbins lower bound for Bernoulli rewards, and performs strongly in numerical comparisons.
Takeaways & Limitations
KL-UCB provides a general-purpose procedure for bounded bandits and an optimal solution for the Bernoulli case, with adaptations covering additional reward families.
Takeaways & Limitations
The core algorithm assumes independent rewards bounded in [0, 1], while the parametric extension is illustrated for canonical exponential families.
Abstract
from arXiv · showhide
This paper presents a finite-time analysis of the KL-UCB algorithm, an online, horizon-free index policy for stochastic bandit problems. We prove two distinct results: first, for arbitrary bounded rewards, the KL-UCB algorithm satisfies a uniformly better regret bound than UCB or UCB2; second, in the special case of Bernoulli rewards, it reaches the lower bound of Lai and Robbins. Furthermore, we show that simple adaptations of the KL-UCB algorithm are also optimal for specific classes of (possibly unbounded) rewards, including those generated from exponential families of distributions. A large-scale numerical study comparing KL-UCB with its main competitors (UCB, UCB2, UCB-Tuned, UCB-V, DMED) shows that KL-UCB is remarkably efficient and stable, including for short time horizons. KL-UCB is also the only method that always performs better than the basic UCB policy. Our regret bounds rely on deviations results of independent interest which are stated and proved in the Appendix. As a by-product, we also obtain an improved regret bound for the standard UCB algorithm.
1. Introduction
The paper frames stochastic bandits as an exploration–exploitation problem and introduces KL-UCB to improve finite-time regret for bounded rewards while achieving Bernoulli optimality. It also extends the approach to distributional families and evaluates it empirically against established competitors.
- Motivation: Bandit policies must balance exploiting the best observed arm against exploring alternatives that may be truly better.The stochastic setting evaluates performance through regret against the best arm known from the start.
- Contribution: KL-UCB is an online, horizon-free index policy requiring no problem- or horizon-dependent tuning for bounded stochastic rewards.The paper targets the non-parametric setting where rewards are assumed only to be bounded.
- Contribution: For bounded rewards, KL-UCB has strictly better theoretical guarantees than UCB and shows significant simulated improvement.Pinsker’s inequality connects the KL divergence bound to the quadratic dependence used by UCB.
- Contribution: For Bernoulli rewards, KL-UCB reaches the Lai–Robbins lower bound and achieves lower regret than UCB-V.The paper presents this as optimality in the binary case.
- Extensions and evaluation: Changing the divergence lets KL-UCB adapt to particular reward families, while numerical experiments report strong performance against UCB, MOSS, UCB-V, UCB-Tuned, and DMED.The reported advantage includes small or moderate horizons, especially in Bernoulli scenarios.
2. The KL-UCB Algorithm
KL-UCB models bounded arm rewards, tracks empirical counts and sums, and computes each arm’s index through a Bernoulli Kullback–Leibler divergence confidence constraint.
- Problem setting: The algorithm assumes independent reward sequences for finitely many arms, with rewards bounded in [0, 1] and arm-specific means µ_a.Rewards in another interval should first be rescaled to [0, 1].
- Statistics: For each arm, the procedure tracks the number of selections N_a(t) and the accumulated reward sum S_a(t).These statistics support the arm’s empirical mean and confidence calculation.
- Index construction: KL-UCB computes an upper-confidence bound for every arm using the Bernoulli Kullback–Leibler divergence d(p, q).The divergence is defined over parameters in [0, 1], with conventions for boundary values.
3. Regret bounds and optimality
The paper establishes finite-time regret and arm-selection bounds for KL-UCB on bounded rewards, proves Bernoulli asymptotic optimality, and derives an improved bound for standard UCB.
- KL-UCB regret bound: Theorem 1 gives a regret bound for KL-UCB on bandit problems with independent rewards bounded in [0, 1].The stated theorem uses c = 3 in the algorithm’s exploration function.
- KL-UCB regret bound: Theorem 2 upper-bounds sub-optimal arm selections using d(µ_a, µ_a*) (1 + ǫ) + C1 log(log(n)) + C2(ǫ).The result is non-asymptotic and applies for any positive horizon n and ǫ > 0.
- Bernoulli optimality: For Bernoulli rewards, KL-UCB is asymptotically optimal because its regret matches the Lai–Robbins and Burnetas–Katehakis lower bound.The result is stated with probability tending to 1.
- General bounded rewards: The same Chernoff bounds apply to all variables with range [0, 1], explaining KL-UCB’s efficiency beyond binary rewards.Thus the algorithm is efficient for general bounded rewards despite using a Bernoulli divergence.
- UCB comparison: A correctly tuned UCB algorithm also receives an improved upper bound, with the logarithmic constant 1/2 identified as unimprovable.The comparison uses the quadratic divergence and Pinsker’s inequality to show KL-UCB dominates UCB.
4. KL-UCB for parametric families of reward distributions
KL-UCB extends beyond bounded rewards by selecting a divergence suited to the reward family, including canonical exponential families. For these families, the divergence equals the corresponding Kullback-Leibler divergence, allowing the adapted algorithm to match the Lai–Robbins bound.
- KL-UCB can be adapted to other reward settings by choosing an appropriate divergence function d.The paper notes that using an upper bound instead of the exact divergence can yield simpler, more versatile policies with only a slight performance loss.
- Canonical exponential families include Exponential, Poisson, Gaussian with fixed variance, Gamma with fixed shape, and Bernoulli rewards.The family is parameterized by θ, with mean µ(θ) = b˙(θ) and a one-to-one parameter-to-mean mapping because b¨(θ) = Var(X) > 0.
- Theorem 11 bounds underestimation of the best arm as in the Bernoulli case after replacing the KL-UCB divergence with the family-specific expression.This supports applying the preceding KL-UCB results to these parametric reward families.
- The resulting adaptations match the Lai–Robbins lower bound for the considered reward families.The proof reduces to establishing the equality between d and the KL divergence of distributions indexed by their means.
- For canonical exponential families, the adapted KL-UCB divergence is chosen so that it equals the Kullback-Leibler divergence between the corresponding reward distributions.Lemma 6 establishes d(µ(β), µ(θ)) = KL(pβ, pθ) = µ(β)(β − θ) − b(β) + b(θ).
5. Numerical experiments and comparisons of the policies
The experiments compare KL-UCB with several competitors across Bernoulli and bounded exponential scenarios, emphasizing regret, variability, and performance under different reward structures. KL-UCB is consistently efficient, while specialized variants can improve performance but may show riskier deviations.
- Scenario 1: two arms: 50,000 independent runs compare six algorithms in the two-arm Bernoulli scenario using mean suboptimal-arm draws and distributions at t = 5,000.The algorithms are KL-UCB, UCB, MOSS, UCB-Tuned, UCB-V, and DMED.
- Scenario 1: two arms: 22.5 versus 50 gives KL-UCB and DMED an expected roughly twofold advantage over UCB, although the observed difference is smaller.The comparison uses d^-1(µ2, µ1) = 22.5 and {2(µ1 −µ2)^2}^-1 = 50.
- Scenario 1: two arms: KL-UCB+ remains preferable to DMED+ after replacing log(t) with log(t/N[a]) in the exploration function.The text reports that both variants improve mean performance, with KL-UCB+ retaining the preference over DMED+.
- Scenario 1: two arms: UCB-Tuned is slightly worse than KL-UCB and exhibits potentially uncontrolled tails, while UCB-V performs disappointingly at moderate horizons.The text attributes UCB-V’s behavior to its non-asymptotic correction term 3 log(t)/N[a].
- Scenario 2: low rewards: In the ten-arm low-reward scenario, KL-UCB and DMED are on par with the Burnetas–Katehakis lower bound, with KL-UCB performing significantly better.KL-UCB+ and DMED+ improve mean regret but show hints of occasional very large deviations.
- Scenario 3: bounded exponential rewards: For truncated exponential rewards, KL-UCB is clearly sub-optimal, whereas KL-UCB-exp is excellent, stable, and catches up with UCB-Tuned.KL-UCB-exp uses the divergence for genuine exponential distributions despite ignoring truncation, producing slightly too-large confidence bounds.
6. Proof of Theorem 2
The proof bounds the expected pulls of a suboptimal arm by decomposing selection events into confidence failures and insufficiently separated empirical divergences. Deviation lemmas then control these terms and yield the regret result.
- Proof strategy: KL-UCB’s upper-confidence bound is the largest q above the empirical mean satisfying N_b(t)d(µ̂_b(t), q) ≤ log(t) + 3 log(log(t)).This index is the central object used to analyze suboptimal-arm selections.
- Proof strategy: The expected number of suboptimal-arm draws is decomposed into underestimation probabilities and indicators where s d+(µ̂_a,s, µ1) remains below the exploration threshold.The decomposition separates failures of the optimal-arm bound from persistence of a suboptimal arm’s index.
- Deviation control: The resulting logarithmic terms include log(t)^2 + 3 log(t) log(log(t)) for a positive constant C′.The supplied proof fragments state this form as part of the confidence-failure bound.
- Deviation control: C2(ε) = O(ε^-2) and β(ε) = O(ε^2) quantify the constants and decay rate in the deviation argument.These orders follow from r(ε) = µ_a + O(ε).
7. Conclusion
The conclusion emphasizes that self-normalized deviation bounds and the paper’s analysis support improved UCB algorithms with broad reward-distribution applicability. These policies are simple, fast, and effective even at short horizons.
- Conclusion: Self-normalized deviation bounds and the paper’s analysis enable improved UCB algorithms requiring only upper bounds on reward deviations or exponential moments.This supports policies for large classes of reward distributions.
- Conclusion: The resulting index policies are simple, fast, and very efficient in practice, including for small time horizons.
Appendix A. Kullback-Leibler deviations for bounded variables with a random number of summands
The appendix develops deviation tools for bounded rewards and extends them to reward distributions with finite exponential moments. These results support confidence control when the number of observed summands is random.
- Bounded deviations: Lemma 9 bounds E[exp(λX)] for X in [0, 1] by 1 + µ(exp(λ) − 1).The proof uses convexity of a function vanishing at 0 and 1.
- Bounded deviations: Theorem 10 treats independent bounded variables with common expectation under predictable Bernoulli sampling and filtration-based independence.Its setting accommodates a random number of observed rewards.
- Proof technique: The peeling trick partitions possible values of N(n) into geometrically increasing slices and analyzes the slices separately.The construction assumes δ > 1 because the δ ≤ 1 case is trivial.
- Proof technique: The deviation analysis controls underestimation events through the relation u(n) < µ only when the empirical mean is below µ and N(n)d(µ̂(n), µ) exceeds δ.This characterizes when the confidence index falls below the true mean.
- Generalization: A general deviation bound is stated for arbitrary reward distributions whose cumulant-generating function is finite on an open interval containing zero.The proof is described as similar to Theorem 10 and omitted.