PaperlayerView exact revision on arXiv

Source-linked AI summary

X-Armed Bandits

Sébastien Bubeck, Rémi Munos, Gilles Stoltz, Csaba Szepesvari

arXiv:1001.4475v2cs.LGeess.SYmath.OCmath.ST

TL;DR

The paper studies stochastic bandits with generic measurable arm spaces and locally Lipschitz mean-payoff functions. It introduces HOO and variants that achieve dimension-independent regret in a Euclidean setting, prove minimax optimality for metric dissimilarities, and reduce computational complexity with a truncated version.

  • Problem

    Stochastic bandits with infinitely many arms require optimization over generic measurable spaces and mean-payoff functions linked to arms through a known dissimilarity.

  • Method

    The paper constructs hierarchical optimistic optimization and proposes truncated HOO, which uses a covering tree and discards sufficiently shallow nodes under weakened assumptions.

  • Results

    HOO achieves regret growth independent of input dimension in the stated Euclidean setting, while truncated HOO retains the basic algorithm’s regret bound with log-linear computational complexity.

  • Takeaways & Limitations

    The results provide dimension-independent regret rates for a class of continuous-arm problems and minimax-optimal guarantees when the dissimilarity is a metric.

  • Takeaways & Limitations

    Overestimating smoothness can violate the weak-Lipschitz assumption, leaving HOO without guarantees and potentially causing it to overexploit a local optimum.

Abstract

from arXiv · show

We consider a generalization of stochastic bandits where the set of arms, $\cX$, is allowed to be a generic measurable space and the mean-payoff function is "locally Lipschitz" with respect to a dissimilarity function that is known to the decision maker. Under this condition we construct an arm selection policy, called HOO (hierarchical optimistic optimization), with improved regret bounds compared to previous results for a large class of problems. In particular, our results imply that if $\cX$ is the unit hypercube in a Euclidean space and the mean-payoff function has a finite number of global maxima around which the behavior of the function is locally continuous with a known smoothness degree, then the expected regret of HOO is bounded up to a logarithmic factor by $\sqrt{n}$, i.e., the rate of growth of the regret is independent of the dimension of the space. We also prove the minimax optimality of our algorithm when the dissimilarity is a metric. Our basic strategy has quadratic computational complexity as a function of the number of time steps and does not rely on the doubling trick. We also introduce a modified strategy, which relies on the doubling trick but runs in linearithmic time. Both results are improvements with respect to previous approaches.

1 Introduction

The paper generalizes stochastic bandits to arbitrary measurable arm spaces using known local regularity of the mean-payoff function, and introduces HOO with improved regret and computational guarantees.

  • Motivation: Continuous-parameter and mixed discrete-continuous optimization problems motivate a unified bandit framework over broad arm spaces.Applications include pricing, transmission-power control, reaction calibration, and sequential search.
  • Problem setting: The model allows an arbitrary measurable arm space and assumes known local constraints on mean-payoff behavior near global maxima.These constraints are expressed through a known dissimilarity function.
  • Contribution: HOO is a hierarchical tree-based policy designed to estimate the mean-payoff function accurately near maxima while improving on previous continuum-armed bandit methods.The approach is motivated by successful tree-based optimization algorithms and is described as easy to implement.
  • Contribution: HOO avoids the doubling trick and covering oracle used by the cited zooming algorithm, while requiring a covering tree and somewhat more restrictive assumptions.A variant reduces total computation from quadratic to O(n ln n), but requires the doubling trick for an anytime guarantee.
  • Computational trade-offs: The basic HOO strategy has quadratic total running time, whereas the modified strategy has linearithmic total complexity and relies on the doubling trick.The paper expects the algorithm to work well in practice because it is close to empirically successful tree-search methods.
  • Results: Under local smoothness near finitely many maxima in a Euclidean unit hypercube, HOO achieves regret growth bounded up to logarithmic factors by sqrt(n), independent of dimension.The paper also states minimax-optimality results for metric dissimilarities.

2 Problem setup

The problem setup models stochastic bandits over measurable arm spaces, with reward distributions and mean payoffs defined for each arm. Performance is evaluated through expected cumulative regret.

  • Bandit environment: A stochastic bandit problem consists of a measurable arm space X and an environment assigning a reward distribution M_x to each arm.Each distribution is required to have a first-order moment.
  • Mean payoff: The mean-payoff function f maps each arm to the expectation of its reward distribution and is assumed measurable with values in [0,1].The bounded-range condition follows from assuming reward supports lie in a fixed bounded interval.
  • Interaction protocol: At each round, the decision maker selects an arm using past observations and receives an independent reward conditional on that arm.Strategies may randomize, and formal strategies are sequences of measurable mappings to probability measures over X.
  • Objective: The objective is to maximize expected cumulative reward, equivalently minimizing expected cumulative regret relative to the best expected single-round payoff.The paper focuses on expected cumulative regret rather than the realized cumulative regret.
  • Regret notions: The paper focuses on cumulative regret, while its results can be extended to simple regret using a uniformly sampled recommendation from the played arms.The recommendation is formed by selecting X_Tn with T_n uniform over the n rounds.

3 The Hierarchical Optimistic Optimization (HOO) strategy

HOO incrementally builds a binary covering tree and selects arms by recursively following children with the highest optimistic B-values. Its bounds reflect both statistical uncertainty and regional payoff variation.

  • Tree representation: HOO maintains a binary tree whose nodes represent increasingly smaller measurable regions of the arm space.At every level, child regions cover their parent, and regions at each level cover X.
  • Node statistics: Each node stores traversal counts, empirical reward averages, and statistics used to construct optimistic upper bounds.The active tree grows incrementally as rounds proceed.
  • Optimistic bounds: The B-value is an estimated upper bound on the best mean payoff in a node’s region, obtained recursively from local estimates and child bounds.Taking the minimum of valid bounds makes the estimate tighter than either source alone.
  • Node selection: The confidence term accounts for reward randomness, while ν1ρ^h bounds possible mean-payoff variation within a depth-h region.Leaf B-values equal their U-values, while recursive bounds can be tighter near the root.
  • Node selection: At each internal node, HOO follows the child with the larger B-value until reaching a node whose selected child has infinite B-value, then plays an arm in that child’s region.The selection uses B-values available at the end of the previous round.
  • Computational complexity: Basic HOO updates every active node each round, giving O(n) per-round time and quadratic total time through round n.With a known horizon, truncated HOO reduces total complexity to O(n0 ln n0) while retaining essentially the same regret bound.

4 Main results

HOO analyzes stochastic bandits on generic measurable arm spaces using tree coverings, dissimilarities, and weak local smoothness assumptions. These assumptions connect shrinking regions to near-optimal payoffs and support regret analysis.

  • Assumptions: HOO is analyzed under a dissimilarity-based smoothness framework rather than an ordinary metric framework.A dissimilarity need only be nonnegative and vanish on identical arms; it need not be symmetric or satisfy the triangle inequality.
  • Assumptions: The algorithm’s theoretical analysis uses a dissimilarity, while its user selects a tree and parameters intended to satisfy the assumptions for a given dissimilarity.The dissimilarity is not required as an explicit algorithm input.
  • Assumptions: Assumption A1 requires covering regions to shrink geometrically, with bounded diameters and suitable representative points at every tree depth.For hyper-rectangles, splitting each region along its longest side yields valid parameters for Euclidean- and supremum-norm power dissimilarities.
  • Assumptions: Weak Lipschitzness imposes a one-sided local payoff-decrease bound at global maxima and a milder constraint around increasingly suboptimal arms.It can hold even for discontinuous functions because it rules out sudden large drops near global maxima rather than requiring global ordinary Lipschitzness.
  • Consequences: Weak Lipschitzness can be illustrated by lower bounds on f(y) around an optimum and around any ε–optimal arm.The figure contrasts the bound f∗−ℓ(x∗, y) near an optimum with bounds involving f∗−2ε and f(x) elsewhere.
  • Consequences: If a tree region’s suboptimality factor is at most cν1ρ^h, every arm in that region is max{2c, c + 1}ν1ρ^h–optimal.This lemma links node-level suboptimality and geometric region size to the quality of all arms within the region.

4.2 Upper bound for the regret of HOO

HOO’s regret analysis uses near-optimality dimension to quantify the size of nearly optimal arm sets. The resulting bound applies when that dimension is finite, while parameter tuning and infinite dimension limit the guarantee.

  • Near-optimality dimension: The near-optimality dimension measures the growth of packing numbers for cε–optimal arms as ε decreases.It captures the metric entropy of near-optimal regions using the dissimilarity and packing rather than covering numbers.
  • Near-optimality dimension: A dissimilarity can reduce near-optimality dimension substantially compared with a metric.For f(x)=1−∥x∥^a and ℓ(x,y)=∥x−y∥^a, the c–near-optimality dimension is 0 for every c>0.
  • Parameter tuning: For the example f(x)=1−∥x∥^a, the zero near-optimality dimension follows because the near-optimal set is an ℓ-ball whose ε-packing number is bounded by a constant.This example demonstrates why a dissimilarity can better match local function geometry than a metric.
  • Regret bound: Theorem 6 gives HOO a regret bound governed by any exponent d′ greater than the mean-payoff function’s near-optimality dimension d.The guarantee is vacuous when d is infinite, and its constant depends on HOO parameters, assumptions, and the bandit environment.
  • Parameter tuning: Good regret depends critically on tuning HOO’s parameters so the assumptions hold and the near-optimality dimension is minimized.The paper leaves adaptive parameter selection based on preliminary observations for future work.

4.3 Improving the running time when the time horizon is known

The paper reduces HOO’s computational cost when the horizon is known while preserving nearly the same regret guarantee, and develops local-assumption variants with dimension-independent square-root regret in stated settings.

  • Running-time improvement: n0 ln n0 total computational complexity replaces the basic HOO algorithm’s quadratic scaling when the horizon is known.Truncating the tree to depth of order ln n0 limits each round’s updates to logarithmic depth while retaining linear memory.
  • Regret preservation: The truncated HOO algorithm retains Theorem 6’s regret bound at round n0 up to an additional additive 4√ term.The paper describes this as almost the same cumulative regret bound as basic HOO.
  • Local assumptions: Local assumptions require smoothness only near the maxima, enlarging the class of mean-payoff functions considered.The local condition is expressed through ε0-local weak Lipschitzness and a near-optimality-dimension assumption.
  • Local-regret result: O(√n) regret is obtained for functions smooth around their maxima, including functions locally equivalent to ∥x − x∗∥α for known α > 0.For the unit-hypercube setting with finitely many global maxima, the regret rate is independent of ambient dimension, up to logarithmic factors.
  • Algorithmic adaptations: The local-HOO adaptation does not require knowledge of ε0, while z–HOO starts exploration directly at a prescribed depth z.z–HOO avoids shallow nodes, addressing the restricted scale at which the weakened smoothness assumptions apply.

4.5 Minimax optimality in metric spaces

The paper establishes matching regret rates for HOO in metric spaces: its upper bound is optimal up to a multiplicative logarithmic factor under packing-dimension conditions.

  • Geometric complexity: Packing dimension depends on the arm space and dissimilarity, not on the mean-payoff function’s specific form.For normed compact subsets of R^D with non-empty interiors, the packing dimension is D.
  • Uniformity: The uniform upper-bound proof converts the distribution-dependent constant into a quantity depending only on geometric and algorithmic parameters.This establishes uniformity across the class of environments rather than only for one mean-payoff function.
  • Uniform upper bound: Finite packing dimension yields a uniform upper bound on HOO’s regret over weak-Lipschitz bandit environments.For every D′ greater than the packing dimension D, the bound uses a constant independent of the underlying mean-payoff function.
  • Minimax optimality: Metric-space lower bounds show that HOO’s upper bound is optimal up to a multiplicative logarithmic factor.The result applies when packing numbers satisfy N(X, ℓ, ε) ≥ c ε−D ≥ 2 for ε ≤ 1.

5 Discussion

The discussion situates HOO among continuum-armed bandit methods and shows how local smoothness assumptions yield dimension-independent regret rates in key settings. It also compares theoretical guarantees, oracle requirements, and computational trade-offs with prior approaches.

  • Examples of regret bounds: eO(√n) expected regret is obtained when the true smoothness around maxima is known, with a rate independent of ambient dimension D.This uses β = α and gives near-optimality dimension d = 0.
  • Examples of regret bounds: Underestimated smoothness β < α yields near-optimality dimension d = D(1/β −1/α) and a corresponding HOO regret guarantee.
  • Examples of regret bounds: Overestimated smoothness violates weak Lipschitzness, so HOO has no guarantee and may remain at a local optimum while missing global optima.The discussion attributes this risk to insufficient exploration caused by excessive exploitation.
  • Relation to previous works: The √n regret rate extends from one-dimensional examples to any dimension D, although dimension affects the multiplicative factor through the cost of global exploration.
  • Relation to previous works: Under Assumption A2, HOO has essentially the same theoretical guarantees as zooming while avoiding its oracle requirement.
  • Relation to previous works: Truncated HOO runs in O(n log n), while basic HOO avoids the doubling trick and matches the zooming algorithm’s computational complexity.The doubling trick can cause repeated sharp performance drops when the algorithm restarts.

A.1 Proof of Theorem 6 (main upper bound on the regret of HOO)

The proof bounds HOO’s regret by controlling visits to suboptimal nodes, counting near-optimal regions, and decomposing the tree into depth-based subsets. Concentration inequalities and near-optimality dimension bounds are combined to obtain the theorem’s final rate.

  • Concentration arguments: The proof uses optional skipping, Hoeffding-Azuma concentration, union bounds, and stopping times for pulls in relevant regions.
  • Visit bounds: Lemma 17 bounds the expected visits to every suboptimal node whose gap exceeds ν1ρh.It combines Lemmas 14, 15, and 16.
  • Tree decomposition: Near-optimal nodes are grouped into Ih, while J contains nodes outside Ih whose parents are near-optimal; Lemma 17 controls visits to J-h nodes.
  • Tree decomposition: The infinite tree is partitioned into T1, T2, and T3 to separately bound regret from deep near-optimal descendants, finite near-optimal nodes, and descendants of boundary nodes.
  • Final rate: Choosing H so that ρH is of order (n/ln n)^−1/(d′+2) balances the regret terms and yields the desired bound.

A.2 Proof of Theorem 8 (regret bound for truncated HOO)

The truncated-HOO proof adapts the main HOO argument to a tree cut at depth Dn0. The truncation preserves the main bounds and adds only a controlled terminal-depth regret term.

  • Proof adaptation: Truncated HOO cuts the tree at depth Dn0 and restricts the sets Ih, I, J, and Jh to nodes no deeper than that cutoff.
  • Proof adaptation: The bounds for T1 and T3 remain unchanged because these sets include descendants of their base nodes.
  • Terminal-depth contribution: 4√n0 bounds the cumulative regret from nodes at the truncation depth over n0 rounds.
  • Final bound: The final truncated-HOO regret bound differs from Theorem 6 by only this additional additive 4√n0 factor, absorbed into O notation.

A.3 Proof of Theorem 9 (regret bound for z–HOO)

The z–HOO proof extends the main argument under local assumptions beginning at depth z. It uses a four-way tree partition and balances deep near-optimal and boundary contributions to derive the final regret bound.

  • Local optimality: Lemma 18 converts a region’s suboptimality bound into an L max{2c, c + 1}ν1ρh–optimality bound for all sufficiently deep nodes.For optimal nodes, the bound improves when c = 0.
  • Visit bounds: Lemma 19 bounds visits to sufficiently deep suboptimal nodes under Assumptions A1 and A2’.
  • Tree decomposition: The proof partitions nodes at depths at least z into T1 through T4, including deep near-optimal descendants and descendants of suboptimal depth-z nodes.
  • Regret decomposition: The T3 contribution is controlled using both the number of boundary nodes, |Jh| ≤ 2|Ih−1|, and Lemma 19’s visit bound.
  • Final bound: The final analysis chooses H to balance the T1 and T3 terms and then obtains the z–HOO regret bound.

A.4 Proof of Theorem 10 (regret bound for local-HOO)

The proof applies an earlier regret result to regimes after a fixed threshold, while bounding earlier rounds directly. The resulting expression is simplified because the dominant n-dependent term determines the final order.

  • Proof setup: The proof chooses a threshold r0 so Theorem 9 applies for all regimes r >= r0.Earlier regimes are handled separately rather than by applying Theorem 9.
  • Proof setup: Earlier regimes contribute at most 2r0 rounds of regret.
  • Regime indexing: The regime containing round n is indexed by rn = floor(log2(n + 1)), and its endpoint is 2^(rn+1) - 2.
  • Final bound: The constants C1 and C2 depend only on the problem parameters and not on n.
  • Final bound: The final equality uses that the first n-dependent term dominates the second, yielding the displayed asymptotic order up to logarithmic factors.

A.6 Proof of Theorem 13 (minimax lower bound in metric spaces)

The lower-bound proof embeds difficult finite-armed bandit instances into the general arm space using disjoint metric balls. It preserves the reward and regret distributions while exploiting metricity to obtain weakly Lipschitz environments.

  • Finite-bandit construction: The proof constructs K difficult environments for a finite {1, ..., K + 1}-armed bandit problem.The environments are product distributions with one arm having mean 1/2 + η and the others mean 1/2.
  • Environment construction: K disjoint balls of radius η provide centers used to define corresponding environments over X.The required disjoint balls exist under the packing-dimension assumption for a suitable K.
  • Environment construction: Each constructed mean-payoff function is maximized at its designated center with value 1/2 + η and equals 1/2 outside the associated ball.Because ℓ is a metric, these functions are 1-Lipschitz and therefore weakly Lipschitz.
  • Strategy reduction: Any strategy on X is transformed into a randomized strategy for the finite bandit through a mapping from X to distributions over the finite arms.The mapping assigns probability mass according to membership in the disjoint balls.
  • Strategy reduction: The transformed strategy has the same reward and regret distributions as the corresponding X-armed strategy under the constructed environment.The equality is established by matching conditional Bernoulli reward distributions and induction over rounds.
Loading 1001.4475v2…