PaperlayerView exact revision on arXiv

Source-linked AI summary

Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms

Stefan Magureanu, Richard Combes, Alexandre Proutiere

arXiv:1405.4758v1cs.LG

TL;DR

The paper addresses stochastic bandits whose expected rewards vary Lipschitz-continuously with the arm, for discrete and continuous action sets. It derives problem-specific regret lower bounds and proposes OSLB and CKL-UCB, with OSLB asymptotically optimal for discrete problems and discretization-based methods for continuous ones. The analysis uses a new KL-divergence concentration inequality, while numerical experiments report improved performance over existing continuous-bandit algorithms.

  • Problem

    Existing continuous Lipschitz-bandit lower bounds are not problem specific, while efficient algorithms must exploit the revealed Lipschitz structure when selecting and evaluating arms.

  • Method

    The paper derives discrete problem-specific lower bounds, proposes OSLB and CKL-UCB, analyzes them using a new KL-divergence concentration inequality, and discretizes continuous action spaces before applying the algorithms.

  • Results

    OSLB is asymptotically optimal for discrete Lipschitz bandits, while CKL-UCB efficiently exploits the structure with lower computational complexity; numerical experiments compare the methods favorably with existing continuous-bandit algorithms.

  • Takeaways & Limitations

    Lipschitz structure can support problem-specific regret guarantees and efficient algorithms for discrete bandits, with discretization providing an approach to continuous settings.

  • Takeaways & Limitations

    The problem-specific lower bound is established for finite arm sets and cannot easily be generalized to continuous arm sets.

Abstract

from arXiv · show

We consider stochastic multi-armed bandit problems where the expected reward is a Lipschitz function of the arm, and where the set of arms is either discrete or continuous. For discrete Lipschitz bandits, we derive asymptotic problem specific lower bounds for the regret satisfied by any algorithm, and propose OSLB and CKL-UCB, two algorithms that efficiently exploit the Lipschitz structure of the problem. In fact, we prove that OSLB is asymptotically optimal, as its asymptotic regret matches the lower bound. The regret analysis of our algorithms relies on a new concentration inequality for weighted sums of KL divergences between the empirical distributions of rewards and their true distributions. For continuous Lipschitz bandits, we propose to first discretize the action space, and then apply OSLB or CKL-UCB, algorithms that provably exploit the structure efficiently. This approach is shown, through numerical experiments, to significantly outperform existing algorithms that directly deal with the continuous set of arms. Finally the results and algorithms are extended to contextual bandits with similarities.

1. Introduction

The paper studies stochastic bandits whose expected rewards are Lipschitz in the arm, addressing both finite and continuous action sets. It derives structure-aware lower bounds and algorithms, with OSLB asymptotically optimal for discrete problems and numerical evidence supporting the approach for continuous problems.

  • The paper revisits bandits where expected reward is a Lipschitz function of the arm, considering both discrete and continuous arm sets.
  • For discrete Lipschitz bandits, the authors derive asymptotic, problem-specific regret lower bounds that depend explicitly on the expected rewards.
  • OSLB matches the discrete lower bound asymptotically, while CKL-UCB exploits Lipschitz structure with lower computational complexity.
  • The regret analysis uses a new concentration inequality for weighted sums of KL divergences between empirical and true reward distributions.
  • Numerical experiments compare the proposed algorithms with existing algorithms for continuous bandits on discrete and continuous arm sets.
  • The results and algorithms are extended to contextual bandits with similarities.

2. Models

The model uses finitely many ordered arms in [0,1], Bernoulli rewards, and a known Lipschitz constraint on expected rewards. Algorithms are evaluated by expected cumulative regret over a time horizon.

  • The discrete arm set is a finite subset {x1, ..., xK} of [0,1], with arms ordered so that x1 < x2 < ... < xK.
  • Rewards from each arm are i.i.d. Bernoulli with mean θk, and the best expected reward is θ⋆ = maxk∈K θk.
  • A sequential algorithm selects an arm using past observations, with admissible decisions measurable with respect to the observed history.
  • Expected rewards satisfy a known Lipschitz constraint, and the objective is to maximize average cumulative reward through horizon T while exploiting that structure.

3. Regret Lower Bound

The paper derives a logarithmic asymptotic regret lower bound for uniformly good algorithms in finite Lipschitz bandits. The bound is problem specific, improves on the unstructured benchmark, and does not readily extend to continuous arm sets.

  • The lower-bound analysis considers the asymptotic regime T → ∞ and applies to every uniformly good algorithm.
  • For each suboptimal arm, λk is constructed as the most confusing Lipschitz-compatible reward vector under which that arm becomes optimal.
  • The minimal regret scales logarithmically with the time horizon and can be smaller than the Lai–Robbins lower bound without Lipschitz structure.
  • The lower bound is problem specific because it depends on θ, unlike typical worst-case lower bounds for continuous Lipschitz bandits.
  • The result is valid for finite arm sets and cannot easily be generalized to continuous sets of arms.

4. Algorithms

The paper presents OSLB and CKL-UCB for discrete Lipschitz bandits. OSLB is asymptotically optimal but requires repeated linear-program optimization, whereas CKL-UCB is simpler and computationally lighter.

  • Algorithms: OSLB has regret matching the lower bound asymptotically, while CKL-UCB has weaker guarantees but still exploits Lipschitz structure.
  • OSLB: OSLB maintains empirical rewards, a leader, confidence indexes, and Lipschitz vectors to guide arm selection.
  • OSLB: OSLB forces exploration of apparently suboptimal arms that have been sampled fewer than their estimated target counts, then selects the least-played eligible arm.
  • OSLB: OSLB updates its estimates by solving a linear program similar to the lower-bound optimization at each round.
  • CKL-UCB: CKL-UCB explores apparently suboptimal arms by choosing the least-played arm whose index exceeds the leader's index, with forced log log(n) exploration.
  • CKL-UCB: CKL-UCB computes choices directly from indexes without solving a linear program, making it computationally light.

5. Regret Analysis

The regret analysis establishes finite-time guarantees for OSLB and CKL-UCB using a new concentration inequality, with OSLB approaching the problem-specific asymptotic lower bound and CKL-UCB improving on KL-UCB under stated conditions.

  • 5.1. Concentration Inequalities: A new concentration inequality controls weighted sums of KL divergences between empirical reward distributions and their true distributions.The analysis uses predictable sampling and empirical averages, and the proof also applies stochastic ordering techniques.
  • 5.2. Finite time analysis of OSLB: OSLB’s finite-time regret is bounded by Cδ(θ)(1 + ϵ) log(T) plus lower-order and additive terms under a unique LP-solution assumption.The uniqueness assumption holds on a dense subset of ΘL.
  • 5.2. Finite time analysis of OSLB: For sufficiently small ϵ and suitable δ, OSLB’s leading regret coefficient approaches the fundamental lower-bound coefficient.The paper states that parameters can be chosen so the coefficient is at most (1 + ζ)C(θ).
  • 5.3. Finite Time analysis of CKL-UCB: CKL-UCB’s bound uses an optimization problem based on KL-divergence coefficients and yields an arm-specific logarithmic sampling guarantee.The theorem applies for suboptimal arms and admissible δ values, with an additional constant and log(log(T)) term in the displayed bound.
  • 5.3. Finite Time analysis of CKL-UCB: CKL-UCB plays each suboptimal arm at most as often as KL-UCB, and under additional structural conditions it plays that arm strictly less often.The strict improvement condition applies to triangular and other unimodal reward functions.

6. Contextual Bandit with Similarities

The paper extends Lipschitz bandits to contextual settings in which rewards are Lipschitz in both arms and contexts, with contexts arriving i.i.d. from an unknown distribution. It derives problem-specific lower bounds and extends CKL-UCB to CCKL-UCB.

  • 6.1. Model: Contextual bandits with similarities assume that expected rewards are Lipschitz in both the arm and the observed context.The context process is i.i.d., and its unknown distribution contrasts with the adversarial context processes common in much prior work.
  • 6.1. Model: A freely chosen metric over arm-context pairs can represent stronger Lipschitz structure in arms than in contexts.The paper gives a metric weighting context differences by β > 1 as an example.
  • 6.2. Regret Lower Bound: The contextual regret lower bound applies to uniformly good algorithms and uses the suboptimal-arm sets defined separately for each context.The construction introduces context-specific alternative parameters and an optimization problem whose minimum is denoted C′(θ).
  • 6.2. Regret Lower Bound: The lower bound is problem specific, and asymptotically optimal play samples arm k under context j on the scale cj,k log(T).The lower bound does not depend on the context-distribution ψ.
  • 6.3. CCKL-UCB: CCKL-UCB extends CKL-UCB to contextual bandits by using context-specific empirical averages, play counts, Lipschitz-constrained indices, and a context-specific leader.At each round it plays the current-context leader when its index is highest; otherwise it selects the least-played arm whose index exceeds the leader’s.

7. Numerical Experiments

The experiments compare Lipschitz-aware algorithms with baselines on discrete and continuous arms. CKL-UCB reduces regret by exploiting structure, although discretization near the optimum remains a key limitation.

  • 7.1. Discrete Lipschitz Bandits: CKL-UCB explores suboptimal discrete arms less often than KL-UCB and has lower regret throughout the example.KL-UCB's regret is typically twice CKL-UCB's in this example.
  • 7.2. Continuous Lipschitz Bandits: The continuous experiments evaluate triangular and quadratic reward functions using discretized arms and comparisons with existing continuous-bandit algorithms.The experiments use a uniform discretization and average regret over 100 independent runs up to T = 25000 rounds.
  • 7.2. Continuous Lipschitz Bandits: CKL-UCB clearly outperforms KL-UCB and the other algorithms on both continuous problem instances.KL-UCB, which does not exploit Lipschitz structure, nevertheless outperforms some structure-exploiting algorithms.
  • 7.2. Continuous Lipschitz Bandits: For quadratic rewards, using the optimized discretization further reduces CKL-UCB's regret.The reported optimal discretization has roughly (log(T)/T)1/4 arms.
  • 7.2. Continuous Lipschitz Bandits: CKL-UCB's main source of regret is insufficient discretization around the top arm, unlike Zooming and HOO, whose regret is attributed to loose confidence bounds.The paper proposes combining adaptive discretization with CKL-UCB-style confidence bounds in future work.

8. Conclusion

The paper develops Lipschitz-aware bandit methods for discrete and continuous arms, combining problem-specific theory, algorithms, concentration analysis, discretization, and contextual extensions. Its experiments report substantial improvements over existing algorithms.

  • 8. Conclusion: The paper derives asymptotic regret lower bounds for discrete Lipschitz bandits and proposes OSLB and CKL-UCB to exploit the structure.OSLB is asymptotically optimal, while CKL-UCB has lower computational complexity.
  • 8. Conclusion: The regret analysis uses a new concentration inequality for sums of KL divergences that may apply to bandit problems with correlated arms.The inequality concerns weighted sums of KL divergences between empirical and true reward distributions.
  • 8. Conclusion: For continuous Lipschitz bandits, the paper adapts OSLB and CKL-UCB through discretization and reports significant experimental improvements over state-of-the-art algorithms.The results and algorithms are also extended to contextual bandits with similarities.

Appendix A. Proof of Theorem 1

The proof embeds the Lipschitz bandit problem in a controlled Markov-chain framework and characterizes statistically indistinguishable alternatives. A linear program then supplies the asymptotic lower-bound constant.

  • Appendix A. Proof of Theorem 1: The lower-bound argument uses Graves and Lai's techniques for efficient adaptive decision rules in controlled Markov chains.The parameter space is restricted to Lipschitz reward vectors.
  • Appendix A. Proof of Theorem 1: The framework defines regret through the gap between the expected reward of the selected control law and the optimal control law.The general controlled-Markov-chain formulation compares sequential control decisions with always applying the optimal law.
  • Appendix A. Proof of Theorem 1: The proof models each arm as a constant control law in a two-state Markov chain whose transitions encode the arm's Bernoulli mean.The observed reward is the Markov-chain state.
  • Appendix A. Proof of Theorem 1: Bad parameters are those where the original optimal arm is no longer optimal but remains statistically indistinguishable from the true parameter.These alternatives form the set B(θ) used in the lower-bound construction.
  • Appendix A. Proof of Theorem 1: The asymptotic lower-bound constant is obtained as the minimum of a linear program derived from the controlled-Markov-chain theorem.The proof concludes by using monotonicity of x 7→I(θk, x).

Appendix B. Proof of Theorem 2

The proof establishes concentration for adaptive arm counts and empirical KL divergences by combining exponential-martingale arguments with multivariate stochastic ordering. A geometric discretization of count vectors then yields the theorem.

  • Appendix B. Proof of Theorem 2: The concentration proof assumes a preliminary lemma and treats the case where every arm has been sampled at least once.The proof is organized around Lemmas 6, 7, and 8.
  • Appendix B. Proof of Theorem 2: Theorem 2 partitions possible count vectors into a geometric grid and applies Lemma 6 to each grid point.The proof sets η = 1/(δ − 1) and uses δ ≥ K + 1 to justify the application.
  • Appendix B. Proof of Theorem 2: Lemma 6 converts an empirical KL-deviation event into coordinatewise bounds using the monotonicity of the inverse KL relation.The construction defines x_k(t) so that tI+(x_k(t), θ_k) matches the target threshold.
  • Appendix B. Proof of Theorem 2: Lemma 7 bounds empirical deviations using a variational representation of KL divergence and an exponential martingale.The martingale has conditional expectation equal to its previous value and expectation one.
  • Appendix B. Proof of Theorem 2: Lemma 8 compares the relevant random vector with independent exponential variables through multivariate stochastic ordering.Lemma 9 supplies equivalent characterizations of that ordering.

Appendix C. Proof of Theorem 3

The proof bounds the expected number of rounds in which suboptimal arms are selected by partitioning such rounds into controlled cases. Concentration inequalities and a cardinality lemma then yield the regret bound for OSLB.

  • Case analysis: The proof analyzes suboptimal-arm selections through three scenarios determined by the leader and the algorithm’s candidate arms.The cases are: the suboptimal arm is leader, neither it nor the optimal arm is leader, or the optimal arm is leader.
  • Case analysis: The round sets A, B, E, and F isolate estimation and sampling events whose expected cardinalities can be bounded.The concentration inequality gives E[|A|] ≤ C1 log log(T), while Lemma 12 controls the other sets.
  • Cardinality bounds: The expected cardinalities of Ek and Fk are bounded by 1/δ2 and 2/δ2, respectively.These bounds follow from applications of Lemma 12 to rounds involving inaccurate estimates.
  • Residual rounds: For rounds outside A ∪ B ∪ E ∪ F, each possible selection case is shown to be impossible or reducible to additional controlled sets Ck and Dk.The proof uses accurate empirical estimates and OSLB’s sampling rules to constrain how often these residual cases occur.
  • Conclusion: The proof combines the bounds for all event sets to obtain the announced regret bound.The final expression aggregates E[|A|], E[|B|], E[|E|], and E[|F|], together with the remaining terms controlled through Ck and Dk.
  • Technical continuity result: A continuity lemma establishes that the linear-program objective is continuous and its solution map is upper hemicontinuous.The result is obtained under nondegeneracy conditions on the matrix rows and columns.

D.2. Proof of (ii)

The proof derives an upper bound on the asymptotic sampling rate of each suboptimal arm by analyzing normalized play counts and their limiting constraints. It then uses concentration and convergence of the optimal arm’s index to complete the argument.

  • Optimal-arm behavior: The optimal arm’s index converges to θ⋆ because its play count is T − O(log(T)) and its empirical mean converges to θ⋆.Consequently, f(T)/tk⋆(T) tends to zero as T grows.
  • Optimal-arm behavior: The proof uses the eventual leader identity L(n) = k⋆ to derive constraints on the sampling rates of other arms.After a sufficiently large time, both the optimal-arm index and empirical means lie within δ of their true values.
  • Normalized sampling rates: For every suboptimal arm k, the normalized play count satisfies tk(T)/log(T) ≤ βk(θ).The bound follows by considering limit points of αk(n) = tk(n)/f(n) and the necessary constraints they satisfy.
  • Structural condition: The final strict inequality rules out ek(A, α0) = 0 under the stated structural assumption.The contradiction arises because the left-hand side of the relevant condition is zero and therefore cannot be strictly positive.
Loading 1405.4758v1…