Source-linked AI summary
A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences
Odalric-Ambrym Maillard, Rémi Munos, Gilles Stoltz
TL;DR
Finite-time bandit analyses often rely on means or variances rather than the full empirical distributions relevant to Kinf. This paper analyzes a Kinf-based algorithm for finite supports, obtaining finite-time bounds whose main terms improve on prior UCB-type analyses.
Problem
Prior finite-time algorithms use moments of reward distributions, so their bounds are expressed through means and variances rather than the Kinf quantity appearing in lower bounds.
Source: §1 · p. 2Method
The paper analyzes a Kinf-based strategy that uses the full empirical reward distribution, with explicit bounds for Bernoulli arms and finite-time bounds for finitely supported distributions whose supports need not be known.
Source: §1 · p. 2Results
The finite-time bounds improve on prior analyses, with the main-term dependency scaling with Kinf(νa, µ⋆) rather than the moment-based quantities used by UCB-type algorithms.
Source: §1 · pp. 2–3Takeaways & Limitations
For finitely supported distributions, the finite-time guarantees also imply the asymptotic results of Burnetas and Katehakis (1996) and Honda and Takemura (2010a).
Source: §1 · p. 2Extending the analysis to general distributions is difficult under the current Kinf definition, including because the proof needs a non-asymptotic Sanov theorem and conditions on θa(γ) that may not hold.
Source: §4.2 · p. 13
Abstract
from arXiv · showhide
We consider a Kullback-Leibler-based algorithm for the stochastic multi-armed bandit problem in the case of distributions with finite supports (not necessarily known beforehand), whose asymptotic regret matches the lower bound of \cite{Burnetas96}. Our contribution is to provide a finite-time analysis of this algorithm; we get bounds whose main terms are smaller than the ones of previously known algorithms with finite-time analyses (like UCB-type algorithms).
1 Introduction
The introduction frames stochastic bandits as decisions under uncertainty, balancing exploration and exploitation, and evaluates strategies through regret. It motivates using Kinf-based methods that exploit full empirical reward distributions and presents finite-time analyses for Bernoulli and finitely supported distributions.
1 Introduction
- The stochastic bandit setting models sequential arm choices with unknown fixed reward distributions and observed payoffs.The motivating exploration–exploitation tradeoff is learning about the environment while maximizing payoff.Source: §1 · p. 1
- Expected regret measures cumulative loss from pulling sub-optimal arms and thus quantifies the exploration needed to find a best arm.It scales with the expected number of sub-optimal pulls.Source: §1 · p. 1
- Earlier finite-time UCB bounds use gap-based or moment-based quantities, whereas the paper targets the Kinf dependence appearing in lower bounds.UCB1’s multiplicative constant depends on the squared gap rather than Kinf; UCB-V incorporates empirical variance and improves over UCB1 for small-variance arms.Source: §1 · pp. 2–3
- The proposed Kinf-based algorithm uses the full empirical reward distribution, unlike UCB methods that rely on one or two moments.The introduction reports that prior moment-based bounds depend on arm means and variances rather than Kinf(νa, µ⋆); cited experiments found Kinf-based algorithms more efficient.Source: §1 · p. 2
- Finite-time bounds are obtained for Bernoulli and finitely supported distributions, including supports unknown in advance, and the analysis points toward general finite-dimensional parametric distributions.The paper says these results improve on prior asymptotic results by Burnetas and Katehakis (1996) and Honda and Takemura (2010a), and on Auer et al. (2002) and Audibert et al. (2009) through Kinf-dependent main terms.Source: §1 · pp. 2–3
2 Definitions and tools
This section defines distances and divergences between probability distributions, then introduces empirical distributions and a non-asymptotic deviation tool. The lemma characterizes how unlikely it is for an empirical distribution to fall in a set separated from its generating distribution.
2 Definitions and tools
- The distance on P(X) is induced by a norm defined through a supremum over Lipschitz functions on X.The functions take values in [−1, 1] and have Lipschitz constant smaller than 1.Source: §2 · p. 3
- The Kullback-Leibler divergence is defined using the density when one distribution is absolutely continuous with respect to the other, and is +∞ otherwise.Source: §2 · p. 3
- The non-asymptotic Sanov lemma bounds the probability that an empirical distribution lies in a set, with a geometric rate determined by Λ(C).When the generating distribution ν lies outside the closure of C, Λ(C) is positive, making that event unlikely.Source: §2 · p. 3
3 Finite-time analysis for Bernoulli distributions
The Bernoulli analysis gives an upper bound for the K-strategy’s expected regret, with closed-form terms; its proof also treats boundary cases and notes that the explicit bound is tailored to Bernoulli distributions.
3.1 Reminder of some useful results for Bernoulli distributions
- The Bernoulli setup denotes the law placing mass p on 1 by β(p), and indexes probabilities and expectations by p.The section presents a self-contained analysis with closed-form terms, as a warm-up; its resulting bound is slightly worse than the general-case bound.Source: §3.1 · pp. 3–4, §3 · p. 3
3.2 Strategy and analysis
- For µ⋆∈(0, 1), Theorem 3 upper-bounds the K-strategy’s expected regret by an infimum over analysis parameters c_a, for non-decreasing f with f(1) ≥ 1.The analysis can choose each c_a proportional to (log T)^−1/3 for a particular f, yielding a regret bound whose second-order term is of order (log T)^2/3; its optimality is unknown.Source: §3.2 · pp. 4–5
- When µ⋆ = 0, regret is zero; when µ⋆ = 1, the analysis bounds regret by 2(|A| − 1).For µ⋆ = 0, all arms have a Dirac distribution at zero, so every strategy has zero regret.Source: §3.2 · pp. 4, 8
- The proof decomposes the events in which a suboptimal arm is selected and bounds the remaining probabilities using Sanov’s lemma.It handles the case µ_a = 0 separately, where a deterministic bound improves on the general Step 4 bound.Source: §3.2 · pp. 5, 6, 8
- Step 5’s explicit upper bound on Γ_a(c_a) is designed for Bernoulli distributions; obtaining one in the general case seems more involved.The authors note that this explicit bound does not directly provide the corresponding general-case expression.Source: §3.2 · p. 8
4 A finite-time analysis in the case of distributions with finite support
The section develops properties of Kinf and uses them to analyze a Kinf-based strategy for finitely supported reward distributions. Its finite-time guarantee covers supports not required to be known in advance, while the extension to general distributions remains difficult.
4.1 Some useful properties of Kinf and its level sets
- Kinf is continuous and non-decreasing in its second argument, lower semi-continuous in its first, and has bounded variation under the stated conditions.The section gives bounds on its variation in both arguments and notes continuity and lower semi-continuity.Source: §4.1 · p. 8
- For γ > 0 and µ in (0, 1), the level set Cµ,γ is non-empty, open, and convex.These properties are established in Lemma 8.Source: §4.1 · p. 9
4.2 The Kinf–strategy and a general performance guarantee
- The Kinf–strategy uses empirical reward distributions, and its finite-support computations do not require advance knowledge of the arms’ supports.The passage says the computation can restrict candidate distributions to the empirical support, up to one point.Source: §4.2 · p. 9
- For finitely supported suboptimal arms, Theorem 9 gives an expected-pull upper bound with a displayed (1 + c_a) log T term.The theorem assumes the optimal arm is finitely supported with expectation in (0, 1), and the suboptimal arm has positive expectation.Source: §4.2 · pp. 9–10
- The analysis recovers the asymptotic results of Burnetas and Katehakis (1996) and Honda and Takemura (2010a), with h(c) finite and independent of T.The passage states that h(c) depends on c and the arm distributions.Source: §4.2 · p. 10
- Extending the analysis to general distributions is difficult because its proof needs a non-asymptotic Sanov result and finite, positive θ_a(γ) values.The conclusion leaves such extensions for future work and mentions histogram-based approximations as one possible direction.Source: §4.2 · p. 13
A Appendix beyond the COLT page limit
The appendix supplies material mentioned in the COLT’11 conference version but omitted there because of the page limit.
A Appendix beyond the COLT page limit
- The appendix details material alluded to in the COLT’11 conference version but omitted because of its page limit.A conference version appeared in the Proceedings of the Twenty-Fourth Annual Conference on Learning Theory.Source: A Appendix beyond the COLT page limit · p. 15
A.1 Proof of Lemma 2
The proof constructs a martingale and combines a peeling argument with KL-divergence bounds to obtain the stated inequality. It handles endpoint cases separately and chooses the peeling parameter to simplify the bound.
A.1 Proof of Lemma 2
- For p = 0 or p = 1, b_{p,s} = p almost surely; the remaining proof treats p ∈ (0, 1).The proof reduces the second bound to the first by decomposing according to N_t, then uses symmetry and a union bound.Source: §A.1 · p. 15
- A log-Laplace transform defines a martingale, and the proof uses Doob’s maximal inequality to bound it.The cited related proof is described as yielding a maximal inequality rather than only a self-normalized-average inequality.Source: §A.1 · pp. 15–16
- Geometric time points t_k = ⌊γ^k⌋ organize a peeling argument, whose number of elements is bounded by K.The proof applies a union bound over the peeling intervals.Source: §A.1 · p. 15
- Continuity of Bernoulli KL divergence supplies p_ε, while its variational formula provides a λ_k for each peeling index.The proof uses the implication q ≥ p to obtain q ≥ p_ε.Source: §A.1 · p. 15
- Choosing γ = ε/(ε − 1) substitutes into the obtained bound to give the stated expression.The passage gives this choice after substituting the value of K.Source: §A.1 · p. 16
A.2 Details of the adaptation leading to Lemma 1
The appendix adapts a non-asymptotic Sanov bound and establishes properties of Kinf and its level sets. It also derives bounds under an explicit separation assumption on Kinf values.
A.2 Details of the adaptation leading to Lemma 1
- The adaptation applies a non-asymptotic Sanov lemma to open convex sets, using a limiting sequence of distributions to obtain the desired inequality.The proof uses C ⊆ C_δ and Λ(C_δ) ≤ Λ(C) < ∞, then takes a convergent subsequence and passes to the limit.Source: §A.2 · p. 16
- The proof treats λ_ν below and at 1/(1 − μ) separately, using continuity and concavity properties of φ_λ.In the strict case φ_λ is bounded; the equality case uses the variational formulation and concavity to bound differences.Source: §A.3 · p. 17
- Assuming Kinf(ν, μ) − Kinf(ν′, μ) ≥ α Kinf(ν, μ), the proof chooses λ = (1 − α/2)/(1 − μ) to derive a bound.The bound uses a rewriting of Kinf and integrates a bound under the support condition [0, 1].Source: §A.3 · pp. 17–18
- The set C_μ(γ) is shown to be nonempty, convex, and open using convexity of KL divergence and a reformulation of Kinf.The set contains the Dirac mass δ_μ; the proof also establishes the relevant infimum is achieved under the reformulation.Source: §A.3 · p. 18
A.4 The method of types
The method-of-types appendix relates empirical distributions to finite collections of possible types. It uses the finite-support condition to control the number of types and a KL-based probability bound.
A.4 The method of types
- For finite support S, the number of possible empirical types is bounded by (k + 1)|S|.The types are the possible values of the empirical distribution after k observations.Source: §A.4 · p. 19
- The type-based bound gives P_ν{K(b_{ν,k}, ν) > γ} ≤ |E_k|e^(−kγ), with |E_k| bounded under finite support.Combining the displayed bound with the type-count bound yields a finite-support probability control.Source: §A.4 · p. 19