PaperlayerView exact revision on arXiv

Source-linked AI summary

Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems

Sébastien Bubeck, Nicolò Cesa-Bianchi

arXiv:1204.5721v2cs.LGstat.ML

TL;DR

The paper studies exploration–exploitation in stochastic and adversarial multi-armed bandits through regret analysis. It develops optimism-based strategies, establishes upper and lower bounds, and examines extensions including side information.

  • Problem

    Bandit problems require balancing exploitation of actions with past high payoffs against exploration of actions that may yield higher future payoffs.

  • Method

    The survey analyzes stochastic and adversarial bandits using optimism in face of uncertainty, UCB strategies, regret bounds, lower-bound arguments, and extensions with side information.

  • Results

    The survey presents simple, nearly optimal stochastic-bandit algorithms, distribution-dependent lower bounds, and lower-bound techniques for adversarial bandits and side-information settings.

  • Takeaways & Limitations

    Regret analysis provides a framework for comparing exploration–exploitation strategies across stochastic, adversarial, and contextual bandit models.

  • Takeaways & Limitations

    It remains open whether a strategy can achieve regret always better than MOSS and improved UCB.

Abstract

from arXiv · show

Multi-armed bandit problems are the most basic examples of sequential decision problems with an exploration-exploitation trade-off. This is the balance between staying with the option that gave highest payoffs in the past and exploring new options that might give higher payoffs in the future. Although the study of bandit problems dates back to the Thirties, exploration-exploitation trade-offs arise in several modern applications, such as ad placement, website optimization, and packet routing. Mathematically, a multi-armed bandit is defined by the payoff process associated with each option. In this survey, we focus on two extreme cases in which the analysis of regret is particularly simple and elegant: i.i.d. payoffs and adversarial payoffs. Besides the basic setting of finitely many actions, we also analyze some of the most important variants and extensions, such as the contextual bandit model.

Introduction

Multi-armed bandits model sequential allocation under limited information, requiring a balance between exploiting known payoffs and exploring potentially better actions. This survey focuses on stochastic and adversarial settings, their regret analysis, and applications including online services, ad placement, website optimization, and routing.

  • Definition: Bandits are sequential allocation problems in which an agent repeatedly selects actions and receives observable payoffs while maximizing cumulative reward.The term derives from choosing among multiple slot machines.
  • Exploration and exploitation: The central challenge is balancing exploitation of actions that performed well with exploration of actions that may yield higher future payoffs.This trade-off motivates regret analysis in sequential decision making.
  • Applications: Modern applications include ad placement, website optimization, packet routing, and tree-based game playing.These applications adapt choices to visitor behavior, network congestion, or promising game subtrees.
  • Models: Bandit models distinguish stochastic, adversarial, and Markovian reward processes, with this survey focusing on stochastic and adversarial bandits.The survey refers readers elsewhere for Markovian bandits because their analysis uses substantially different techniques.
  • Regret: Regret compares a forecaster’s cumulative performance with an optimal strategy over a horizon of n rounds.The framework allows stochastic rewards and choices, and defines anytime forecasters when the horizon is unknown.
  • Stochastic and adversarial settings: In stochastic bandits, each arm has an unknown reward distribution and independently generated rewards; adversarial bandits instead allow arbitrary gain sequences set by an opponent.An adversary may be oblivious or adaptive to the forecaster’s past behavior, creating ambiguity for regret in the adaptive case.

Stochastic bandits: fundamental results

Stochastic bandit analysis addresses exploration–exploitation by comparing arms through pseudo-regret and optimistic estimates. UCB strategies achieve logarithmic pseudo-regret under suitable assumptions, while KL-based arguments establish matching lower-bound structure for Bernoulli rewards.

  • Model: The stochastic model assigns each arm an unknown distribution ν_i, and each selected arm produces an independent reward with mean μ_i.The forecaster chooses an arm at each time step and observes only its reward.
  • Regret measure: Pseudo-regret is preferred because stochastic analysis naturally compares performance with the arm that is optimal in expectation.Expected regret also includes fluctuations from realized rewards and generally cannot be bounded below their typical magnitude.
  • Upper Confidence Bound strategies: Logarithmic pseudo-regret can be achieved in the stochastic setting, and the (α, ψ)-UCB theorem provides a formal bound when α > 2.For bounded rewards, the method is called α-UCB; Hoeffding’s lemma yields a concrete specialization.
  • Optimism in face of uncertainty: Optimism in face of uncertainty constructs plausible environments from observed data and selects the action optimal in the most favorable plausible environment.The principle supports simultaneous exploration and exploitation and underlies UCB strategies.
  • Upper Confidence Bound strategies: UCB constructs confidence-based upper estimates of arm means and selects the arm that appears best under those estimates.The analysis uses concentration assumptions and a Legendre-Fenchel transform of ψ to form the estimates.
  • Lower bounds: For Bernoulli rewards, a KL-based lower bound shows that the preceding stochastic results are essentially unimprovable up to logarithmic factors.The proof compares an original bandit with a modified one in which a suboptimal arm becomes optimal and uses change-of-measure arguments.

Second step: P(Cn) = o(1).

The proof’s second step establishes that the event C_n has probability tending to zero. It uses inequalities under the original and modified bandit assumptions.

  • Second step: P(C_n) = o(1).: The strategy assumption that suboptimal-arm pulls satisfy E T_i(n) = o(n^a) is applied to the modified bandit, where arm 2 is uniquely optimal.This supports the conclusion that P(C_n) = o(1).

Third step: P (T2(n) < fn) = o(1).

This section completes the stochastic-bandit discussion by establishing asymptotic sampling behavior and reviewing refinements to UCB regret guarantees.

  • Third step: P (T2(n) < fn) = o(1).: P(T2(n) < fn) = o(1), so the second arm is sampled fewer than fn times only with vanishing probability.The proof invokes the maximal strong law for independent random variables with positive mean.
  • UCB refinements: Peeling improves the UCB proof to logarithmic regret for any α > 1, instead of requiring α > 2.This replaces a union bound over time steps.
  • UCB refinements: KL-UCB attains the optimal finite-time rate for Bernoulli distributions and strictly dominates α-UCB for bounded reward distributions.The comparison is stated for the regret guarantees discussed in this section.
  • Distribution-free bounds: MOSS removes the extraneous logarithmic factor from a distribution-free α-UCB upper bound, although its second term depends only on the smallest gap.Improved UCB can outperform MOSS in some regimes but does not attain the minimax-optimal rate.
  • Distribution-free bounds: It remains open to find a strategy that always improves on both MOSS and improved UCB.The text presents a plausible conjecture for a better regret order but does not establish it.
  • High probability bounds: Anytime strategies cannot generally improve polynomial concentration to classical exponential concentration, unlike strategies using the known horizon.This makes anytime strategies weaker for high-probability bounds.

Adversarial bandits: fundamental results

Adversarial bandits remove stochastic assumptions and seek sublinear regret uniformly over gain sequences. Randomized forecasters, especially Exp3 and Exp3.P, provide the central guarantees, with stronger bounds when the horizon is known or confidence is handled explicitly.

  • Setting and objective: Adversarial bandits assume bounded rewards assigned by an adversary and aim for sublinear regret uniformly over all assignments.The framework can be expressed equivalently using gains or losses.
  • Setting and objective: Deterministic forecasters can suffer regret at least n/2, motivating randomization to prevent the adversary from exploiting predictable choices.The adversarial construction assigns losses based on the forecaster’s current arm.
  • Exp3: Exp3 estimates every arm’s loss unbiasedly from bandit feedback and updates arm probabilities through exponential reweighting of cumulative estimated losses.Only the played arm’s loss is observed, so the estimator and exponential weighting are the two core ideas.
  • Exp3 bounds: Exp3’s pseudo-regret bound has a better constant when the horizon is known; its anytime version does not require knowing n.The supplied bounds scale with nK ln K, with separate expressions for the two settings.
  • Exp3.P: Exp3.P mixes exponential weights with a uniform distribution and uses modified estimates to control estimator variance for high-probability guarantees.The mixing keeps arm probabilities bounded below, while the gain formulation introduces a bias enabling a high-probability statement.
  • Exp3.P: Exp3.P offers one bound requiring confidence level δ as input and another valid for any confidence level, which is important for expected-regret bounds.The latter property is highlighted as particularly useful when deriving expected regret.

3.3 Lower Bound

The lower-bound section shows that adversarial-bandit regret guarantees are essentially unimprovable up to logarithmic factors, using a probabilistic construction and Kullback–Leibler divergence.

  • Lower-bound strategy: The lower bound is proved by constructing a reward distribution under which every forecaster has high pseudo-regret on average.The proof uses the probabilistic method and parallels the stochastic-bandit lower-bound technique.
  • Formal result: The lower bound implies that the preceding adversarial-bandit results are essentially unimprovable up to logarithmic factors.This conclusion is stated directly before the theorem’s proof development.
  • Formal result: Theorem 3.4 formalizes a minimax lower bound over i.i.d. Bernoulli rewards and all forecasters, with expectations over rewards and forecaster randomization.The theorem takes a supremum over reward distributions and an infimum over forecasters.
  • Lower-bound strategy: The construction compares all arms with Bernoulli parameter 1/2 against environments where one arm’s parameter is increased.Kullback–Leibler divergence and Pinsker’s inequality relate the forecaster’s behavior across these environments.
  • Lower-bound strategy: Because at least one arm is pulled fewer than n/K times, its increased mean is difficult to distinguish from the baseline distribution.This limited observation prevents reliable identification of the better arm.

Third step: Computation of KL(P0, Pi).

The survey develops regret guarantees across adversarial bandit settings, including adaptive strategies, alternative feedback, and policy classes with switches. It also highlights the trade-off between worst-case robustness and stronger guarantees under stochastic or structured reward sequences.

  • Adversarial strategies: INF generalizes Exp3 by assigning arm probabilities through a potential function, with implicit normalization achieved by translating losses.Choosing ψ(x) = (−ηx)^−q for q > 1 gives the key minimax-optimal pseudo-regret construction, whereas Exp3 uses ψ(x) = exp(ηx).
  • Adversarial strategies: Log-free pseudo-regret does not directly extend to expected or high-probability regret against general non-oblivious adversaries.Log-free expected regret is available for oblivious adversaries, while log-free high-probability regret is available for fully oblivious adversaries.
  • Policy classes: Exp3.P obtains expected and high-probability regret of order nKS ln(nK/S) when competing with policies making at most S switches.Switching regret is a broader comparator than consistently playing the best fixed arm.
  • Stochastic versus adversarial bandits: SAO combines, up to logarithmic factors, Exp3-like adversarial guarantees with UCB-like stochastic guarantees.This addresses the motivation for strategies that adapt between stochastic and adversarial models, although the standard fixed-arm regret notion can become vacuous under nonstationarity.
  • Alternative feedback structures: With graph-based feedback, Exp3 achieves minimax pseudo-regret of order α(G)n up to logarithmic factors, where α(G) is the independence number.The setting can model applications such as website advertisement placement, where displayed alternatives may provide related feedback.

Contextual bandits

Contextual bandits attach side information to arms and evaluate performance against the best policy mapping contexts to arms. The section surveys adversarial and stochastic variants, including Exp3-based forecasters for contexts and experts.

  • Contextual regret compares a forecaster with the best policy mapping contexts to arms, rather than with a single best arm.
  • In the basic adversarial contextual model, contexts are arbitrary but fixed, and running a separate Exp3 instance for each context yields a pseudoregret bound.
  • S-Exp3 is optimal up to constants when a constant fraction of contexts accounts for a constant fraction of rounds.
  • The expert case: Exp4 mixes expert advice with an Exp3 distribution over experts, achieving pseudoregret of order √(nK ln N) rather than the naive √(nN ln N).
  • Competing against the best context set: The Exp4-over-Exp3 construction has rate n^2/3, worse than the usual n^1/2 bandit rate, and it is unknown whether this can be improved while retaining logarithmic dependence on |Θ|.
  • Stochastic contextual bandits: For VC-classes, the rate d/n excluding logarithmic factors matches the optimal supervised-learning rate, making the price of bandit information essentially zero in this case.
  • The multiclass case: Banditron is introduced as a bandit multiclass Perceptron, with a mistake guarantee for normalized examples under a specified exploration parameter.

Linear bandits

Linear bandits replace finitely many arms with a compact subset of R^d and losses represented by functions on that set. Regret analysis depends on structural assumptions and feedback type, including bandit and full-information feedback.

  • Linear bandits choose arms from a compact set K ⊂ R^d and seek arms close to the minimum of each loss function.
  • Sublinear regret with infinitely many arms requires structure on the loss functions.
  • The finite-arm adversarial bandit model is recovered by taking K as the canonical basis and L=[0,1]^d.
  • The analysis focuses on bandit feedback, where only the incurred loss is observed, while also discussing full information and other feedback models.
  • A compact arm set can be discretized with O(nd) points at vanishing extra cumulative regret, but the resulting strategy may be computationally inefficient.

5.1 Exp2 (Expanded Exp) with John’s exploration

Exp2 with John’s exploration adapts Exp3 to linear bandits by using geometric contact points to construct exploration and unbiased loss estimates. This replaces dependence on a potentially exponential discretization size with polynomial dependence on dimension.

  • A trivial Exp3 application on a discretized arm set gives regret scaling with nN ln N, which can be exponential in dimension.
  • The construction achieves polynomial regret of order nd ln N instead of the discretization-dependent nN ln N scaling.
  • John’s theorem supplies contact points with a distribution that is sufficiently well spread to support exploration in the transformed arm geometry.
  • Exp2 samples from a distribution over arms, forms an unbiased estimate of the loss vector, and uses the estimated losses in an Exp3-style update.
  • Theorem 5.2 gives a pseudoregret guarantee for Exp2 with John’s exploration when ηd ≤ γ.

5.2 Online Mirror Descent (OMD)

Online Mirror Descent generalizes gradient descent by updating in a dual space and projecting back through a Bregman divergence. The chapter develops regret guarantees for Legendre and suitable non-Legendre regularizers, then motivates stochastic-gradient extensions for bandit feedback.

  • Convex-analytic foundations: The Bregman divergence is defined from a convex function and is nonnegative, vanishing when its two arguments coincide.
  • Convex-analytic foundations: The gradient of the Legendre transform maps dual variables back to the primal space, linking primal and dual Bregman geometries.
  • OMD selects a Legendre function, performs a gradient update in the dual space, and projects back to the arm set using its Bregman divergence.
  • Computational caveat: Bregman projection is a convex program but may not be computationally efficient when the feasible set has exponentially many constraints.
  • Regret guarantees: Theorem 5.3 provides a general regret bound for OMD with a Legendre function under the stated consistency condition.
  • Regret guarantees: A Legendre regularizer is not necessary when the function has effective domain K and a differentiable Fenchel dual, as covered by Theorem 5.4.

5.3 Online Stochastic Mirror Descent (OSMD)

OSMD adapts online mirror descent to bandit feedback by playing perturbed actions and constructing unbiased loss-gradient estimates. The section develops its general pseudo-regret theorem and relates OSMD to Exp2 on finite action sets.

  • Core strategy: OSMD replaces unavailable gradients with unbiased loss estimates obtained from perturbed plays.The perturbation is chosen so the observed loss can be used to estimate the gradient.
  • Core strategy: OSMD runs on a compact convex action set with a learning rate and Legendre regularizer.The algorithm is presented for repeated rounds over K, using a Legendre function F.
  • Connection to Exp2: For finite arms, Exp2 with exploration and mixing is equivalent to OSMD on the simplex with negative entropy.The OSMD projection becomes standard probability normalization in this representation.
  • Regret guarantee: The pseudo-regret theorem follows directly from the preceding OSMD theorem, with the linear-loss case requiring the same computations.The proof invokes Theorem 5.3 and then specializes the argument.
  • Regret guarantee: Theorem 5.5 establishes a general pseudo-regret bound for OSMD under an estimate satisfying the stated condition.The theorem also gives a specialization for linear losses.

5.4 Online combinatorial optimization

The section applies OSMD to online combinatorial optimization under full-information, semi-bandit, and bandit-style structures. Negative entropy and more general potentials yield regret guarantees, including an improved bound for suitable combinatorial sets.

  • Problem setting: Combinatorial actions are represented by C ⊆ {0, 1}^d with linear losses in [0, 1]^d and fixed cardinality m.The framework covers selecting m items and path-planning problems.
  • Feedback models: Semi-bandit feedback reveals only the losses of coordinates active in the chosen action, making it weaker than full information but stronger than bandit feedback.The basic multi-armed bandit is recovered when C consists of the canonical basis vectors.
  • Semi-bandit strategy: Randomly selecting an action from a distribution over C makes its average point lie in Conv(C), enabling OSMD to use the random action as an unbiased perturbation.The construction does not require additional perturbations for the stated estimate.
  • Regret guarantees: Theorem 5.6 gives an OSMD guarantee on Conv(C) using negative entropy.The section then introduces more general potentials to obtain tighter bounds.
  • Regret guarantees: A 0-potential defines a Legendre regularizer, and Theorem 5.7 bounds OSMD pseudo-regret for non-negative loss estimates.For a specific potential, the result includes the log-free adversarial multi-armed bandit bound discussed earlier.

5.5 Improved regret bounds for bandit feedback

This section improves bandit-feedback regret bounds for selected convex action sets using carefully chosen Legendre functions within OSMD. In particular, it obtains an order-dimension bound for the Euclidean ball up to logarithmic factors.

  • Improved rates: General compact convex sets have pseudo-regret of order √n up to logarithmic factors, and this rate is unimprovable in general.The simplex is an important exception with a smaller dimension dependence.
  • Improved rates: The simplex admits pseudo-regret of order √(dn), and this rate is also unimprovable.The section contrasts this with the general convex-set rate.
  • Euclidean ball: The Euclidean ball admits pseudo-regret of order d√n up to a logarithmic factor using OSMD with a carefully chosen Legendre function.The strategy operates on a shrunk ball and uses a radial regularizer.
  • Estimator construction: The perturbation of an interior point is unbiased, satisfying E[perturbed action] = x_t.The perturbation uses Bernoulli, uniform-coordinate, and Rademacher randomization.
  • Euclidean ball: For the Euclidean ball, OSMD uses the regularizer F(x) = −ln(1 − ∥x∥) − ∥x∥ and an unbiased loss estimate.The theorem states the construction for K = L equal to the Euclidean unit ball and K′ = (1 − γ)K.

5.6 Refinements and bibliographic remarks

The section places the chapter’s online linear-optimization results in context through prior work, lower bounds, and open problems. It also notes remaining gaps concerning high-probability regret and incomplete understanding of the area.

  • Prior work: Mirror descent can achieve optimal bandit regret bounds, despite earlier suboptimal dimension dependence from self-concordant-barrier methods.The cited comparison contrasts O(d^2√n) with O(d√n) regret dependencies.
  • Open directions: Online linear optimization is still far from completely understood, with additional topics and open problems omitted from the chapter.The section directs readers to a broader list of open problems.
  • Lower bounds: Exp2 with John’s exploration matches the cited minimax lower bounds in the relevant full-information and bandit settings.The surrounding discussion attributes the lower bounds and matching results to prior work.
  • Combinatorial results: In combinatorial optimization, negative-entropy OSMD matches lower bounds for full-information and semi-bandit feedback.For bandit feedback, the best known bound in the cited discussion is instead obtained by Exp2 with John’s exploration.
  • Combinatorial results: Exp2 is provably suboptimal in the combinatorial bandit setting.This limitation is attributed to Audibert et al. [2011].
  • Open directions: High-probability regret bounds remain more important and less developed than the chapter’s pseudo-regret analysis.The section cites partial results for Exp2 and OSMD rather than a complete treatment.

Nonlinear bandits

Nonlinear bandits extend bandit feedback to losses that need not be linear, using local or global perturbations to estimate gradients. Two-point feedback supports a stronger regret rate than one-point feedback, while stochastic unimodal losses admit a separate one-dimensional analysis.

  • Model: Nonlinear bandits use adversarial loss functions from a set of real-valued functions on a convex action set, rather than necessarily linear losses.The bandit constraint prevents direct gradient computation when losses can only be accessed through queried values.
  • Two-point feedback: Two-point feedback queries the played point and an additional point, enabling gradient estimation through nearby perturbations.OSGD uses two queried points and randomly plays one of them; its gradient estimate targets a smoothed loss.
  • Stochastic nonlinear bandits: In one-dimensional stochastic bandits with unimodal Lipschitz mean loss, the SGS algorithm provides a pseudo-regret bound under the stated smoothness condition.This stochastic setting differs from the nonstochastic case because the mean loss is Lipschitz and unimodal but not necessarily convex.
  • Two-point feedback: The two-point gradient estimate is unbiased for the gradient of a smoothed loss, E egt(x) = ∇E ℓt(x + δB).Lipschitzness controls the discrepancy between the original and smoothed losses.
  • Two-point feedback: OSGD obtains a pseudo-regret bound of order √n under convex differentiable Lipschitz losses and suitable geometric assumptions on the action set.The theorem assumes a closed convex set bounded between scaled Euclidean balls and uses perturbation parameters to keep queried points feasible.
  • One-point feedback: One-point feedback achieves a pseudo-regret bound of order n3/4, and whether √n regret is possible in this setting remains unknown.The worse rate arises from the inverse dependence on the perturbation radius in the one-point estimator's second-moment analysis.

Variants

Bandit variants alter payoff dynamics, feedback, available actions, objectives, or application constraints. The survey covers Markovian and restless models, pure exploration, dueling bandits, and truthful ad placement, each requiring distinct performance criteria or algorithms.

  • Variant dimensions: Bandit models vary along payoff evolution, payoff-function structure, feedback structure, context, and the notion of regret.These extensions broaden the potential application space beyond the basic stochastic and adversarial settings.
  • Markovian and restless bandits: Markovian bandits associate each arm with a reward process whose state and reward evolve according to an arm-specific Markov transition model.Restless bandits additionally allow unchosen arms to undergo unobserved transitions.
  • Change-points: Bandits with abruptly changing reward distributions can achieve regret of order √n, matched by Exp3.P, but they cannot be represented as MDPs.The survey distinguishes this change-point model from restless bandits despite their superficial similarity.
  • Pure exploration: Pure exploration replaces cumulative-reward maximization with identifying or estimating arms, making simple regret fundamentally different from pseudo-regret.Successive Rejects removes the arm with the smallest empirical mean across K −1 phases, while Successive Elimination targets an ε-accurate arm with probability at least 1 −δ.
  • Dueling bandits: Dueling bandits select arm pairs and reveal only relative performance, with optimal regret of order K∆log n where ∆ = min_i≠j ∆i,j.A Successive Elimination-based strategy attains this rate.
  • Truthful bandits: Truthful bandits model ad placement with advertiser bids and private values, seeking algorithms that give advertisers no incentive to bid below their true values.This adds strategic bidding constraints to the usual click-reward bandit formulation.
Loading 1204.5721v2…