PaperlayerView exact revision on arXiv

Source-linked AI summary

Explore First, Exploit Next: The True Shape of Regret in Bandit Problems

Aurélien Garivier, Pierre Ménard, Gilles Stoltz

arXiv:1602.07182v3math.STcs.LG

TL;DR

The paper asks how regret lower bounds behave before the asymptotic regime in multi-armed bandits. It develops non-asymptotic, distribution-dependent bounds using simple KL-divergence inequalities, showing three successive phases: initial near-linear exploration, transition, and final logarithmic confirmation. These results make the initial linear phase rigorous and show that the logarithmic phase may be out of reach in applications, particularly with many arms.

  • Problem

    Existing theory emphasizes logarithmic regret growth, but experiments show that this shape is not visible on small horizons and that asymptotic lower bounds can remain experimentally out of reach.

  • Method

    The paper derives distribution-dependent regret lower bounds non-asymptotically using simple information-theoretic arguments based on well-known KL-divergence properties.

  • Results

    The bounds identify three successive regret phases: an initial near-linear phase, a transition phase, and a final logarithmic phase.

  • Takeaways & Limitations

    The logarithmic regret regime may be unreachable in applications, especially when the number of arms is large.

  • Takeaways & Limitations

    The analysis imposes restrictions on considered strategies, and uniform fast convergence is described as a strong assumption.

Abstract

from arXiv · show

We revisit lower bounds on the regret in the case of multi-armed bandit problems. We obtain non-asymptotic, distribution-dependent bounds and provide straightforward proofs based only on well-known properties of Kullback-Leibler divergences. These bounds show in particular that in an initial phase the regret grows almost linearly, and that the well-known logarithmic growth of the regret only holds in a final phase. The proof techniques come to the essence of the information-theoretic arguments used and they are deprived of all unnecessary complications.

1. Introduction.

The paper makes the initial near-linear regret phase rigorous for general bandit problems and develops simple KL-based lower-bound proofs. It presents regret as three phases—linear exploration, transition, and final logarithmic confirmation—and extends lower bounds beyond asymptotic statements.

  • Motivation: The paper addresses the mismatch between widely accepted logarithmic asymptotic regret and experiments showing non-logarithmic behavior on visible horizons.Small horizons show no logarithmic shape, while second-order terms can keep regret below the asymptotic lower bound even at larger horizons.
  • First contribution: Linear distribution-dependent lower bounds hold for small horizons in general bandit problems without restrictions on arm-distribution shapes or expectations.The paper formalizes a previously widely believed initial linear-regret phenomenon.
  • Regret phases: Regret has three successive phases: initial near-uniform exploration, transition as differences become observable, and final logarithmic confirmation of the best arms.The final phase may be unreachable in applications, especially with many arms.
  • Proof technique: The paper gives simple KL-divergence proofs that re-derive several asymptotic distribution-dependent lower bounds and provide non-asymptotic large-horizon versions.The second-order term has optimal order −ln(lnT).
  • Initial regime: Its fundamental inequality yields initial-regime lower bounds for all bandit problems, not only selected difficult instances.The initial bounds explain quasi-linear regret and relate the exploration-phase length to arm count and KL gaps.
  • Large-horizon regime: For large T, the paper studies non-asymptotic logarithmic lower bounds whose second-order terms are explicitly analyzed.The paper also reports independent regularity results for Kinf.

2. The fundamental inequality, and re-derivation of earlier lower bounds.

The paper introduces a fundamental inequality for comparing bandit problems and uses it to simplify distribution-dependent lower-bound proofs. Applying it recovers the general asymptotic lower bound under uniform fast convergence.

  • The fundamental inequality: The fundamental inequality applies to any strategy, two bandit problems, and a measurable random variable bounded in [0,1].The paper typically uses Z = Nψ,k(T)/T, linking the divergence term to expected arm draws.
  • The fundamental inequality: The resulting approach avoids well-chosen events and Markov–Chernoff bounds used in previous distribution-dependent lower-bound proofs.The authors emphasize that implicit changes of measure and the fundamental inequality suffice for their exposition.
  • The fundamental inequality: Its proof combines the chain rule for Kullback-Leibler divergences with the data-processing inequality for pushforward measures.The data-processing step is the key simplification relative to earlier explicit-change-of-measure proofs.
  • Re-derivation of earlier lower bounds: For uniformly fast convergent strategies, the paper re-derives the asymptotic distribution-dependent lower bound of Burnetas and Katehakis.The proof modifies the problem so a selected suboptimal arm becomes uniquely optimal, then applies the inequality with its normalized draw count.

3. Non-asymptotic bounds for small values of T.

The paper develops non-asymptotic, distribution-dependent lower bounds showing that suboptimal arms are explored nearly uniformly early, before the logarithmic regime emerges. These bounds characterize absolute, relative, and collective exploration behavior under mild strategy restrictions.

  • Initial regime: Suboptimal arms are expected to be pulled about T/K times when T is small, before sufficient information permits the logarithmic regime.The paper describes this as the initial exploration phase preceding identification of the best arm.
  • Absolute lower bound: The absolute lower bound remains of order T/K while T is at most of order 1/Kinf(νa,µ⋆,D), although the initial phase may last until approximately K/Kinf(νa,µ⋆,D).The latter scale captures the expected dependence on the number of arms that the absolute bound misses.
  • Relative lower bound: The relative lower bound shows that a suboptimal arm is not played much less than an optimal arm when T is at most of order K/KL(νa,νa⋆).Thus, the number of arms affects the length of the initial exploration phase proportionally to K.
  • Collective lower bound: The third result gives a collective lower bound on the sampling of all suboptimal arms, with scale involving T(1−A⋆ν) and a Kullback-Leibler divergence.The supplied passage identifies this as a collective rather than arm-specific bound.
  • Strategy conditions: The results apply under mild symmetry, smarter-than-uniform, or monotonicity conditions satisfied by standard strategies including UCB, KL-UCB, Thompson Sampling, and EXP3.These restrictions exclude strategies that perform well only on particular bandit problems while preserving broad distribution-dependent validity.
  • Numerical illustrations: Numerical illustrations place expected pulls of the considered suboptimal arms between T/(2K) and T/K initially, while suggesting that this phase lasts longer than quantified.For many arms, the regret lower bound derived from Theorem 4 is larger than the bound obtained from Theorem 2 and regret decomposition.

4. Non-asymptotic bounds for large T.

Under well-behaved models and uniformly super-fast convergent strategies, the paper derives non-asymptotic distribution-dependent lower bounds for sufficiently large horizons. The bounds apply across several model classes and refine the asymptotic logarithmic result with an optimal second-order term.

  • Model assumptions: Well-behaved models require local Lipschitz continuity of Kinf in its second variable, including regular exponential families and bounded-support distributions.The paper formalizes this property through Definition 5 and gives examples covering both parametric and broader distribution classes.
  • Proof strategy: The proof combines uniform super-fast convergence with a modified bandit problem and an optimization over alternative distributions whose optimality gaps are at least ε.The analysis sets ε_T=(lnT)^−4 and relates Kinf(ν_a,µ⋆+ε,D) to Kinf(ν_a,µ⋆,D).
  • General lower bound: Theorem 5 gives a non-asymptotic lower bound for every uniformly super-fast convergent strategy on a well-behaved model, for each suboptimal arm and sufficiently large T.The theorem uses a problem-dependent quantity H(ν) and requires conditions involving ε_D(µ⋆) and logarithmic terms.
  • Second-order behavior: The lower bound's second-order term has optimal order −ln(lnT), matching the order recently obtained by non-asymptotic upper bounds for relevant bounded-support models.Earlier upper bounds used +(lnT)^α with α∈(0,1), whereas the cited newer result has second-order order −ln(lnT).
  • Bounded-support distributions: For distributions supported on [0,M], the corresponding increase is bounded by 4εM/(M−µ⋆), under the model restriction that the expectation is not M.The construction mixes a candidate distribution with a Dirac measure to raise its expectation while controlling KL divergence.
  • Regular exponential families: For regular exponential families, Kinf(ν_µ,µ⋆+ε,D) is at most Kinf(ν_µ,µ⋆,D)+ε under the stated range of µ and ε.The bound relies on the convex representation of KL divergence and the interval restriction µ⋆+ε∈I.

Appendix A: Reminder of some elements of information theory.

The appendix recalls KL-divergence tools used throughout the paper, including data processing and a local refinement of Pinsker’s inequality. These results support compact information-theoretic proofs of bandit lower bounds.

  • Data-processing inequality: The data-processing inequality states that applying a measurable random variable cannot increase the KL divergence between two distributions.The appendix presents it through conditional Jensen’s inequality and distributions induced by the random variable.
  • Pinsker refinement: A local Bernoulli refinement gives kl(p,q)≥(1/2) max_{x∈[p,q]}x(1−x)(p−q)^2.The classical Pinsker form follows by replacing x(1−x) with its global upper bound 1/4.
  • Proof ingredients: The appendix derives the refinement using derivatives of the Bernoulli KL divergence and bounds on r(1−r).These elementary calculations establish the stated lower bound and its comparison with the classical form.

Appendix B: Re-derivation of other earlier lower bounds

The appendix re-derives earlier lower bounds from the paper’s fundamental inequality (6) to demonstrate its power and versatility. These appendix bounds are weaker than the main-body bounds.

  • Appendix re-derivations: The appendix uses inequality (6) to re-derive the bounds discussed earlier in the paper.The stated purpose is to illustrate the inequality’s power and versatility.
  • Scope of results: The re-derived lower bounds have the well-chosen form rather than the stronger all form used for the main results.The paper explicitly characterizes the appendix results as much weaker than the main-body bounds.

B.1. Distribution-free lower bound.

The appendix recovers a distribution-free lower bound using the same Bernoulli construction, KL chain rule, and Pinsker inequality as earlier proofs. The compact argument places distribution-dependent and distribution-free bounds under one information-theoretic framework.

  • Proof comparison: The compact proof reuses the Bernoulli distributions, KL chain rule, and Pinsker’s inequality from the original argument of Auer et al.Its presentation unifies distribution-dependent and distribution-free lower bounds under inequality (6).
  • Distribution-free construction: The proof considers a Bernoulli bandit with all arms having parameter 1/2 and one arm having parameter 1/2+ε.This construction supplies the difficult alternative bandit problem used in the lower-bound argument.
  • Distribution-free bound: The resulting worst-case regret is lower bounded for every strategy over the model of all distributions supported on [0,1].The appendix states the bound after averaging the number of pulls across arms and optimizing ε.
  • Constant refinement: The appendix notes that the constant 1/20 can be improved to 1/8.The improvement is attributed to Cesa-Bianchi and Lugosi.

B.2. Lower bounds for the case when µ⋆or the gaps ∆are known.

This section develops distribution-dependent lower bounds for settings where either the largest expected payoff or the gap is known. The bounds apply broadly, remain nonnegative for small horizons, and use symmetry together with a fundamental information-theoretic inequality.

  • Known largest expected payoff µ⋆ but unknown gap ∆: For known µ⋆ and unknown gap ∆, bounded regret is achievable, while the paper’s lower bound is of order 1/∆.The section notes that an initially claimed ln T dependency is incorrect and that regret can be as small as ln(1/∆)/∆.
  • Proof technique: The proof uses Inequality (6), Kullback–Leibler divergence identities, Pinsker’s inequality, binary-entropy bounds, and the Lambert function.The authors emphasize that this proof is simple and direct compared with standard approaches based on explicit changes of measure.
  • Known gap ∆ but unknown largest expected payoff µ⋆: For known gap ∆ and unknown largest expected payoff µ⋆, the lower bound establishes the optimality of Improved–UCB’s ln(T∆^2)/∆ regret rate.When the gap is known between Gaussian arms with variance 1, the leading constant is ln(T∆^2)/(2∆).
  • General lower-bound framework: The lower bounds cover all strategies through a maximum of two regrets and also give a separate result for symmetric, translation-invariant strategies.Translation invariance means shifting every payoff distribution by the same constant preserves the relevant strategy behavior.
  • Comparison with prior bounds: For small T or small ∆, the paper’s bound remains nonnegative whereas the compared logarithmic bound can become void.Asymptotically, the paper’s bound is smaller by a factor of 2, and the additional minimum term is dominated by the elementary regret bound T∆.

Appendix C: A finite-regret algorithm when µ⋆is known.

The appendix analyzes an algorithm that uses known µ⋆ to obtain finite regret in sub-Gaussian bandit problems. It combines candidate-arm selection with forced rounds and controls empirical-mean deviations through concentration arguments.

  • Algorithm and setting: The algorithm assumes sub-Gaussian reward distributions and known largest expected payoff µ⋆.It first samples every arm once, then constructs candidate arms from empirical means and confidence conditions.
  • Algorithm and setting: When the candidate set is nonempty, the algorithm randomly plays a candidate; when empty, it plays all arms sequentially.The forced sequence ensures continued sampling when no arm meets the candidate criterion.
  • Regret guarantee: Theorem 9 states a regret bound for this algorithm on all sub-Gaussian K-armed bandit problems.The proof fixes an optimal arm and bounds the expected number of pulls of each suboptimal arm.
  • Proof strategy: The proof bounds the candidate-selection and forced-play contributions, then controls the resulting sums using an integer threshold n0 and integral comparison.The final bound follows after upper-bounding n0, including separate handling of whether the threshold exists.
  • Proof strategy: The analysis uses optional sampling to treat rewards observed from each arm as an i.i.d. sequence and applies concentration bounds to empirical averages.The empirical average µa,n is defined from the first n rewards obtained from arm a during the game.
Loading 1602.07182v3…