PaperlayerView exact revision on arXiv

Source-linked AI summary

Contextual Bandits with Similarity Information

Aleksandrs Slivkins

arXiv:0907.3986v5cs.DScs.LG

TL;DR

Large or infinite arm sets require structural assumptions for tractable bandit learning, and contextual bandits add payoff-relevant information before each round. This paper models similarity through a Lipschitz metric over context-arm pairs and develops adaptive-partition algorithms that exploit benign contexts and payoffs while retaining worst-case guarantees. It also identifies limitations in weakening the Lipschitz requirements and in settings without numeric payoff-difference bounds.

  • Problem

    Bandit learning with exponentially or infinitely large arm sets needs structural assumptions, while prior contextual methods use potentially wasteful uniform partitions.

  • Method

    The paper models similarity with a metric over context-arm pairs and adaptively refines partitions around frequent contexts and high-paying arms.

  • Results

    The algorithms exploit benign context arrivals and expected payoffs without sacrificing worst-case performance, with nearly matching lower bounds for the stochastic setting.

  • Takeaways & Limitations

    Adaptive partitioning yields improved, nearly optimal contextual-bandit bounds and extends to temporal constraints, sleeping bandits, and bandit learning-to-rank.

  • Takeaways & Limitations

    The analysis relies heavily on the Lipschitz condition, and it is unclear whether meaningful guarantees persist under weaker similarity information or without numeric payoff-difference bounds.

Abstract

from arXiv · show

In a multi-armed bandit (MAB) problem, an online algorithm makes a sequence of choices. In each round it chooses from a time-invariant set of alternatives and receives the payoff associated with this alternative. While the case of small strategy sets is by now well-understood, a lot of recent work has focused on MAB problems with exponentially or infinitely large strategy sets, where one needs to assume extra structure in order to make the problem tractable. In particular, recent literature considered information on similarity between arms. We consider similarity information in the setting of "contextual bandits", a natural extension of the basic MAB problem where before each round an algorithm is given the "context" -- a hint about the payoffs in this round. Contextual bandits are directly motivated by placing advertisements on webpages, one of the crucial problems in sponsored search. A particularly simple way to represent similarity information in the contextual bandit setting is via a "similarity distance" between the context-arm pairs which gives an upper bound on the difference between the respective expected payoffs. Prior work on contextual bandits with similarity uses "uniform" partitions of the similarity space, which is potentially wasteful. We design more efficient algorithms that are based on adaptive partitions adjusted to "popular" context and "high-payoff" arms.

1 Introduction

The paper studies contextual bandits with similarity information, where contexts hint at payoffs and expected payoffs vary smoothly over a metric space. It replaces potentially wasteful uniform partitions with adaptive partitions that exploit frequent contexts and high-paying arms.

  • Motivation: Large or infinite arm sets make bandit learning intractable without structural assumptions such as similarity information.The paper frames this difficulty as searching for a high-payoff arm among many alternatives.
  • Model: Contextual bandits provide a context before each round, making the context-specific best arm the regret benchmark.The context can describe a webpage and user, while arms can represent advertisements and payoffs can represent clicks.
  • Model: Similarity is represented by a metric space over feasible context-arm pairs, with expected payoffs satisfying a Lipschitz condition.The model also allows product similarity spaces that combine context and arm metrics through D((x, y), (x′, y′)) = min(1, DX(x, x′) + DY(y, y′)).
  • Prior work: Prior methods use separate uniform partitions of contexts or arms, with granularity determined by the horizon, metric space, and underlying bandit guarantee.The paper argues that uniform partitioning can disregard benign payoff and context-arrival structure.
  • Contributions: Contextual zooming jointly and adaptively partitions the similarity space, refining regions containing frequent contexts and high-paying arms.For stochastic payoffs it captures benign context arrivals and expected payoffs, matches the uniform algorithm in the worst case, and has nearly matching lower bounds.
  • Contributions: For adversarial payoffs, a contextual meta-algorithm adaptively partitions contexts and uses an arbitrary adversarial bandit algorithm as a subroutine.Its guarantees exploit benign context arrivals while retaining worst-case dependence on context-space covering dimension.
  • Discussion: Adaptive partitions extend zooming to the entire similarity space and yield improved, nearly optimal contextual-bandit bounds while unifying applications beyond advertisement placement.The paper discusses temporal constraints, sleeping bandits, and bandit learning-to-rank as applications or reductions.
  • Discussion: A separate context partition with one zooming instance per region can undermine adaptation because any a priori zooming bound is pessimistic.This pessimism negates zooming’s ability to adapt to benign expected payoffs.

2 Related work

Related work places this paper among regret-minimizing bandits with large arm sets, similarity structure, and contextual settings. It distinguishes its expected-payoff Lipschitz assumption from stronger realized-payoff conditions and relates its model to prior algorithms and simpler bandit problems.

  • Bandit foundations: The paper follows regret-minimization work on bandits while distinguishing it from Bayesian treatments.It directs readers to standard surveys for background and to Bayesian references for an alternative perspective.
  • Structured bandits: Prior large-arm bandit research commonly assumes structure such as similarity information, linear payoffs, or convex payoffs.These assumptions are presented as routes to efficient learning algorithms.
  • Structured bandits: The paper’s structured adversarial-payoff condition is less restrictive than conditions imposed directly on realized payoffs.It assumes Lipschitz continuity for expected payoffs, which generalizes stochastic payoffs in the authors’ comparison.
  • Contextual bandits: Earlier contextual-bandit work studies linear contexts, bandits with covariates, or online labeling under additional assumptions and narrower settings.The cited stochastic covariate studies consider two arms and a random context correlated with payoffs.
  • Contextual bandits: Experimental contextual-bandit work includes studies by Pandey et al. and Li et al.
  • Closest prior work: For product similarity spaces, Lu et al. essentially recover the uniform algorithm and a matching lower bound; EXP4 can also reproduce the prior guarantee.The paper notes that improvements from less-distinct-expert methods are not clearly concrete.
  • Connections: When contexts are time-invariant, this setting reduces successively to Lipschitz MAB, continuum-armed bandits on a real line, or ordinary stochastic MAB without similarity information.
  • Publication context: The paper’s preliminary publication was concurrent and independent of the cited works marked with that note.

3 Preliminaries

The preliminaries define contextual-bandit notation, metric-space complexity measures, similarity access, and horizon assumptions. These concepts support the paper’s adaptive-partition analysis and its regret guarantees.

  • Notation: The badness of a context-arm pair is its gap from the context-specific best expected payoff.The paper denotes this gap by ∆(x, y) ≜ µ∗(x) − µ(x, y).
  • Notation: Compactness of the similarity space ensures that the context-specific maximum is attained by some feasible arm.Ties are resolved using an arbitrary but fixed rule.
  • Metric spaces: An r-covering uses subsets of diameter less than r, and its minimum size defines the r-covering number N_r(P).Covering dimension is the smallest d for which N_r(P) ≤ c r^-d across radii.
  • Metric spaces: Packing numbers are essentially equivalent to covering numbers, while doubling constants measure how many half-radius balls cover any ball.The doubling dimension is the logarithm of the doubling constant.
  • Metric spaces: A Lipschitz function changes by at most its Lipschitz constant times the distance between two points.This formalizes the smoothness assumption used for expected payoffs.
  • Assumptions: The analysis assumes full and computationally unrestricted access to similarity information, formally representable through oracle access.Efficient representation is left to application-specific treatment.
  • Assumptions: The time horizon is fixed and known in advance, with the doubling trick converting fixed-horizon algorithms into indefinite ones with essentially the same regret bound.

4 The contextual zooming algorithm

Contextual zooming adaptively partitions the similarity space, focusing on frequently occurring contexts and high-payoff arms. Its regret guarantees use refined zooming measures that can be smaller than worst-case packing or covering measures.

  • 4 The contextual zooming algorithm: Contextual zooming adaptively partitions the similarity space to focus on popular context regions and high-payoff arm regions.
  • 4.1 Provable guarantees: The algorithm’s refined performance measures account for benign expected payoffs and context arrivals through packing-based quantities.
  • 4.1 Provable guarantees: The r-zooming number can equal the full packing number in the worst case but become much smaller when near-optimal context-arm pairs are sparse.
  • 4.1 Provable guarantees: Theorem 4.1 gives contextual regret bounds using the r-zooming number and the corresponding contextual zooming dimension.
  • 4.1 Provable guarantees: The same algorithm supports the dimension-type bound for every c > 0, unlike the prior uniform algorithm, which essentially requires c as input.
  • 4.2 Description of the algorithm: The algorithm starts with one radius-1 active ball and maintains counters, rewards, average payoffs, and uncertainty-based indices.
  • 4.2 Description of the algorithm: Each round selects a relevant active ball with maximal index, chooses a feasible arm, and may activate a smaller ball when confidence becomes sufficiently tight.
  • 4.4 Improved regret bounds: The adjusted r-zooming number excludes r-winners, and Theorem 4.6 gives regret bounds in terms of this refined quantity and its covering-type dimension.

5 Lower bounds

The paper constructs contextual-bandit instances showing that its upper bounds are nearly tight. The lower bounds use needle-in-a-haystack instances distributed across contexts and arms.

  • 5 Lower bounds: The lower bound matches the upper bound in Theorem 4.1 up to O(log T) factors and applies broadly to product similarity spaces.
  • 5 Lower bounds: A distribution over instances is necessary because an algorithm that already knows every context’s needle arm would achieve zero regret.
  • 5 Lower bounds: For any R ≤ RUB(T), Theorem 5.1 constructs a distribution whose instances have upper bound O(R), while every algorithm incurs expected regret Ω(R/log T).
  • 5.1 Lower-bound construction: The instances use 0-1 payoffs, with one slightly higher-payoff needle arm per context and smoothed payoffs satisfying the Lipschitz condition.
  • 5.1 Lower-bound construction: The construction uses an r-packing of context-arm pairs and creates Θ(N) instances by assigning an independently chosen needle arm to each packed context.
  • 5.2 Matching lower bound: For T0 = N r−2, every constructed instance has upper bound O(N/r)(log T0), while some instance incurs expected regret at least Ω(N/r).
  • 5.2 Matching lower bound: The lower-bound argument decomposes regret by context and applies a KL-divergence technique to the resulting context-free bandit problems.

6 Applications of contextual zooming

The paper applies contextual zooming to drifting, stochastically evolving, and sleeping bandits, obtaining regret guarantees tailored to these settings.

  • Drifting MAB: For drifting MAB with spatial arm constraints, the regret bound depends on the covering dimension of the arms space.The similarity metric combines temporal volatility with spatial arm distance.
  • Stochastically evolving payoffs: For Dynamic MAB with equal volatility, the expected average dynamic regret is O(kσ log^2 T0), matching the prior main-case bound.The model uses independent random walks with reflecting boundaries and step ±σ.
  • Sleeping bandits: For sleeping MAB, contextual zooming reduces to the highest awake index algorithm and re-derives the stochastic-payoff result.The contextual formulation additionally supports similarity information on arms.

7 Bandits with stochastically evolving payoffs: missing proofs

The missing proofs derive adjusted zooming-number bounds for stochastically evolving payoffs and use them to recover the stated dynamic-regret guarantees.

  • Proof strategy: The proofs reduce periodic contextual zooming to bounding average regret for one non-periodic period.The inequality ˆR(T) ≤ 2ˆR(T0) makes this reduction sufficient.
  • Uniform marginals: For uniform marginals, the proof bounds the expected number of near-best arms in each time interval using independent uniform payoff distributions.A key auxiliary result gives expected near-maximal-arm count kr for k independent uniform variables.
  • Dynamic MAB: For Dynamic MAB, a high-probability Hölder temporal constraint converts the random walk into a suitable deterministic similarity metric.The proof uses DX(t,t′)=σ|t−t′|^(1/2) log T0 and treats failure of the event as negligible.
  • Dynamic MAB: The Dynamic MAB analysis obtains EΓ[ˆR(T)] ≤ O(kσ log^2 T0) under the stated period condition.This completes the proof of the corresponding corollary.

8 Contextual bandits with adversarial payoffs

For adversarial contextual bandits, the paper builds a meta-algorithm that adaptively partitions the context space and invokes a fixed-context bandit algorithm.

  • Algorithm: ContextualBandit maintains adaptive context balls and calls a fresh Bandit subroutine for each active ball.Balls are selected when they contain the current context and are not full; full balls are limited by their convergence time.
  • Model: The adversarial model assumes time-specific payoff distributions fixed in advance, with Lipschitz expected payoffs over the product similarity space.The context space is compact and all context-arm pairs are feasible.
  • Guarantees: The framework is flexible because Bandit can be instantiated with algorithms for adversarial bandits with linear, convex, or finitely many-arm payoffs.The resulting parameters depend on the selected fixed-context bandit guarantee.
  • Guarantees: The regret guarantee depends on the relaxed covering dimension of the observed context arrivals rather than the entire context space.The relaxed dimension permits a limited number of outliers through a slack function.
  • Analysis: The adaptive-ball construction ensures correctness, bounded selections per ball, separation among equal-radius balls, and bounded branching.Each ball’s local regret is at most 3rT0(r).

9 Conclusions

The paper develops adaptive-partition algorithms for contextual bandits with similarity information, covering stochastic and adversarial payoffs. It identifies unresolved extensions involving weaker similarity assumptions and benign expected payoffs in adversarial settings.

  • Conclusions: The stochastic algorithm adaptively refines a joint partition of context-arm similarity space to exploit frequently occurring contexts and high-paying arms.This differs from maintaining separate partitions for contexts and arms.
  • Conclusions: The adversarial algorithm adaptively refines context partitions to exploit benign context arrivals without sacrificing worst-case performance.It can use essentially any off-the-shelf non-contextual bandit algorithm as a subroutine.
  • Open questions: The main open questions are whether the guarantees extend under weaker Lipschitz conditions or similarity information without numeric payoff-difference bounds.The paper states that its analysis relies heavily on the Lipschitz condition.
  • Open questions: For adversarial payoffs, extending adaptive partitions to exploit benign expected payoffs remains open, and analogous results are not known for the non-contextual problem.The current adversarial technique takes advantage of benign context arrivals but not benign expected payoffs.

Appendix A: The KL-divergence technique, encapsulated

The appendix presents a KL-divergence lower-bounding technique for feasible multi-armed bandits and restates a theorem to make the argument self-contained. The construction uses structured ensembles of payoff functions whose distinguishing regions correspond to children in a ball-tree.

  • Technique: The lower bound extends a KL-divergence technique attributed to Auer et al. and formalized in later work.The appendix states the theorem and relevant definitions so the paper is self-contained.
  • Framework: A feasible MAB problem consists of a strategy set X and feasible payoff functions F; Lipschitz functions provide one example.The lower-bound construction depends on a collection of subsets of F with specified properties.
  • Ensemble construction: An (ε, k)-ensemble organizes feasible payoff functions into k subsets associated with disjoint strategy subsets and a shared payoff level μ0.The supplied definition continues by specifying how functions agree outside these subsets and differ within them.
  • Lower-bound intuition: Distinguishing which ensemble subset contains the payoff function requires repeated play in its associated region, while playing other regions incurs regret when the hypothesis is wrong.In the application, these regions are children of a ball-tree node, and each function family is induced by ends in the corresponding subtree.
  • Theorem: Theorem A.2 applies the ensemble construction to feasible MABs with 0-1 payoffs and guarantees substantial regret for any bandit algorithm on at least k/2 ensemble members.The theorem is identified as Theorem 5.6 from Kleinberg et al. (2013).
  • Relation to prior work: The construction generalizes the special ensemble analyzed by Auer et al., where each family contains one payoff function with a distinguished arm.That earlier case uses k arms and assigns one arm a higher expected payoff than the others.
Loading 0907.3986v5…