PaperlayerView exact revision on arXiv

Source-linked AI summary

Introduction to Multi-Armed Bandits

Aleksandrs Slivkins

arXiv:1904.07272v8cs.LGcs.AIcs.DSstat.ML

TL;DR

Multi-armed bandits provide a framework for sequential decisions under uncertainty, and this book offers an introductory, textbook-like treatment of the subject. It develops self-contained technical introductions across IID, adversarial, contextual, and economics-related bandit settings, with regret guarantees that are often near-optimal.

  • Problem

    Multi-armed bandits study how algorithms make decisions over time under uncertainty, motivating a broad range of sequential decision problems.

  • Method

    The book synthesizes self-contained technical introductions to bandit models, algorithms, analyses, and further developments across multiple settings.

  • Results

    The discussed regret bounds are near-optimal, with instance-dependent bounds optimal up to O(log T) factors and logarithmic bounds optimal up to constants.

  • Takeaways & Limitations

    The treatment provides a teachable foundation for understanding bandit algorithms, regret guarantees, and extensions across IID, adversarial, contextual, and economic settings.

  • Takeaways & Limitations

    Some procedures rely on reward-distribution prior shapes for algorithmic input, without requiring those shapes as assumptions about the actual rewards.

Abstract

from arXiv · show

Multi-armed bandits a simple but very powerful framework for algorithms that make decisions over time under uncertainty. An enormous body of work has accumulated over the years, covered in several books and surveys. This book provides a more introductory, textbook-like treatment of the subject. Each chapter tackles a particular line of work, providing a self-contained, teachable technical introduction and a brief review of the further developments; many of the chapters conclude with exercises. The book is structured as follows. The first four chapters are on IID rewards, from the basic model to impossibility results to Bayesian priors to Lipschitz rewards. The next three chapters cover adversarial rewards, from the full-feedback version to adversarial bandits to extensions with linear rewards and combinatorially structured actions. Chapter 8 is on contextual bandits, a middle ground between IID and adversarial bandits in which the change in reward distributions is completely explained by observable contexts. The last three chapters cover connections to economics, from learning in repeated games to bandits with supply/budget constraints to exploration in the presence of incentives. The appendix provides sufficient background on concentration and KL-divergence. The chapters on "bandits with similarity information", "bandits with knapsacks" and "bandits and agents" can also be consumed as standalone surveys on the respective topics.

Introduction: Scope and Motivation

Multi-armed bandits provide a framework for sequential decisions under uncertainty, unifying applications such as news selection, dynamic pricing, and investment. The book examines how feedback, reward models, contexts, structure, constraints, and actions make this framework more expressive.

  • Running examples: News selection, dynamic pricing, and investment instantiate the framework with objectives of maximizing clicks, profit, and wealth, respectively.The corresponding rewards are clicks, sales revenue, and daily changes in stock value.
  • Basic model: Multi-armed bandits model K actions over T rounds, with unknown fixed reward distributions determined by the chosen arm and independent reward draws.The algorithm selects one arm per round and observes its reward.
  • Exploration and exploitation: Because only the chosen arm’s reward is observed in the basic model, algorithms must balance exploration of alternatives with exploitation of available information.Exploration is needed to determine whether an unchosen arm is better.
  • Modeling dimensions: Other modeling dimensions include IID, adversarial, constrained-adversary, and random-process rewards; contexts; Bayesian priors; structured rewards; global constraints; and structured actions.Contexts support policies mapping contexts to arms, while constraints can include limited inventory and actions can require several simultaneous decisions.
  • Modeling dimensions: Feedback ranges from bandit feedback to full and partial feedback, and the book mainly focuses on bandit feedback while using full-feedback results for subsequent bandit results.Partial feedback can improve performance in extensions and special cases.
  • Applications: Bandit problems arise in medical trials and Web applications including website design, content optimization, search, advertising, recommender systems, and sales optimization.The original application sought useful medical data while minimizing patient harm.

Stochastic Bandits

Stochastic bandits model sequential choices among K arms over T rounds with unknown IID, bounded rewards and bandit feedback. The chapter develops increasingly adaptive algorithms, improving regret from T^2/3-scale guarantees to logarithmic-in-T bounds and extending modeling through structural assumptions on mean rewards.

  • Model: The model has K arms and T rounds; each chosen arm yields an independently sampled reward in [0, 1], while rewards of unchosen arms remain unobserved.The reward distributions are initially unknown, and the objective is to maximize total reward.
  • Explore-first: Explore-first achieves regret E[R(T)] ≤ T^2/3 × O(K log T)^1/3.This provides the chapter’s initial nonadaptive benchmark.
  • Epsilon-greedy: Epsilon-greedy with exploration probabilities ϵ_t = t^-1/3 · (K log t)^1/3 achieves E[R(t)] ≤ t^2/3 · O(K log t)^1/3 for each round t.Its exploration schedule decreases over time while retaining the same t^2/3 dependence as Explore-first.
  • Adaptive exploration: Adaptive algorithms use observations to phase out very under-performing arms sooner, enabling regret bounds with logarithmic dependence on T.The chapter contrasts this with the T^2/3 dependence of Explore-first.
  • Successive Elimination: Successive Elimination achieves logarithmic-in-T regret, with an instance-dependent constant that can be as large as O(K/∆).The distinction between absolute and instance-dependent constants is presented as typical for multi-armed bandits.
  • UCB1: UCB1’s regret bounds are near-optimal: the instance-dependent bound is optimal up to O(log T) factors, while the logarithmic bound is optimal up to constant factors.Later analyses improve the multiplicative constant, ultimately reaching 1/2 ln 2.

Lower Bounds

The chapter establishes fundamental regret lower bounds that apply to all bandit algorithms, showing that the rates achieved earlier are essentially unimprovable. It also derives stronger limits for non-adaptive exploration and instance-dependent logarithmic regret bounds.

  • Worst-case lower bounds: Sampling each arm Ω(1/ϵ2) times is necessary to distinguish good from bad arms, yielding regret Ω(K/ϵ).The argument sets ϵ = Θ(K/T) to complete the lower-bound proof.
  • Non-adaptive exploration: Non-adaptive exploration has essentially unavoidable T 2/3 regret, matching the chapter’s earlier upper bounds in order.A stronger theorem applies to algorithms satisfying non-adaptive exploration and gives a problem instance with a corresponding regret lower bound.
  • Non-adaptive exploration: For algorithms with regret at most C · T γ, randomly permuting the arms yields a lower bound involving T 2/3 · K1/3 across problem instances.The result applies for γ ∈[2/3, 1) and C > 0; Explore-first and Epsilon-greedy incur similar regret under random arm permutations.
  • Instance-dependent lower bounds: No algorithm can achieve regret E[R(t)] = o(cI log t) for every problem instance when cI depends on the instance but not on time.For sufficiently large t, the lower bound takes the form E[R(t)] ≥CI ln(t).
  • Instance-dependent lower bounds: The instance-dependent lower bound is optimal up to a constant factor for UCB1 and Successive Elimination when µ∗∈[ 1/4, 3/4 ].A stronger version is approached arbitrarily closely by several algorithms, including a version of Thompson Sampling.

Bayesian Bandits and Thompson Sampling

This section introduces Bayesian stochastic bandits, where instances are drawn from a known prior, and presents Thompson Sampling as a posterior-based algorithm. It develops Bayesian updating, establishes posterior sufficiency and update compositionality, and summarizes computational and regret guarantees, including fake-prior applications to ordinary stochastic bandits.

  • Bayesian bandit model: Bayesian bandits draw the problem instance initially from a known prior distribution and optimize expected regret under that prior.The horizon T and number of arms K are fixed; Bayesian regret is expected regret for a particular problem under the prior.
  • Bayesian updating: The posterior distribution is independent of which history-consistent algorithm collected the observed action-reward history.This follows because action probabilities depend on history, while reward distributions depend on the selected action.
  • Bayesian updating: Sequential Bayesian updates compose exactly: updating on H and then H′ gives the same posterior as updating once on the concatenated history H ⊕ H′.Once the posterior is computed, it contains all pertinent information from the history about mean rewards, so the prior and history can be discarded.
  • Thompson Sampling: Thompson Sampling selects each arm with its posterior probability of being the best arm.At round t, it draws arm a independently from p_t(· | H), where p_t(a | H) := Pr[a∗ = a | H_{t−1} = H].
  • Thompson Sampling: Thompson Sampling has Bayesian regret bounds and can be applied without a built-in prior by using independent uniform or standard Gaussian fake priors.The two fake-prior approaches use 0-1 rewards or unit-variance Gaussian rewards, respectively, and the prior acts as an algorithm parameter rather than an assumption about actual rewards.

Bandits with Similarity Information

Lipschitz bandits model stochastic rewards whose unknown means vary smoothly over a known metric, enabling similarity-based exploration across finite or infinite arm sets. Uniform discretization yields dimension-dependent regret, while adaptive zooming concentrates probes on promising regions and achieves near-optimal bounds.

  • Uniform discretization: In continuum-armed bandits, uniform discretization attains expected regret bounded by L^1/3 · T^2/3 · (1 + c_ALG)(log T)^1/3.The discretization step is ϵ = (T L^2 / log T)^−1/3.
  • Uniform discretization: The continuum-armed worst-case lower bound matches the uniform-discretization rate, with some instance yielding expected regret at least Ω(T^2/3).The lower-bound construction applies to any algorithm through a suitable continuum-armed instance.
  • Model: Lipschitz bandits impose a known metric-based similarity structure on stochastic arms whose expected rewards satisfy a Lipschitz condition.The arm set may be finite or infinite, and the metric represents an abstract notion of similarity.
  • Uniform discretization: For covering dimension d, optimized uniform discretization attains regret bounded by (1 + c_ALG) · T^((d+1)/(d+2)) · (c log T)^(1/(d+2)).These upper bounds are worst-case optimal up to O(log T) factors.
  • Zooming algorithm: Adaptive discretization, implemented by zooming, places more probes in regions that appear promising and fewer elsewhere.Its self-adjusting property makes the algorithm zoom in precisely where arms are played often and have high mean rewards.
  • Zooming algorithm: The zooming algorithm achieves near-optimal regret, with its raw upper bound optimal up to logarithmic factors for any algorithm, metric space, and bound value.The result also establishes optimality in terms of zooming dimension, under the stated relationship to covering dimension.

Full Feedback and Adversarial Costs

The section develops full-feedback online learning with adversarial costs, distinguishing oblivious and adaptive adversaries and introducing weighted-majority methods and Hedge. In expert prediction, randomized Hedge achieves the optimal O(√T log K) regret scale, while deterministic algorithms can fail completely.

  • Problem setting: Full feedback reveals the costs of every arm after each round, while an adversary may choose costs that change arbitrarily over time.The protocol has K arms and T rounds: the adversary chooses costs, the algorithm selects an arm, incurs its cost, and then observes all costs.
  • Adversaries: Adaptive adversaries may make each round’s costs depend on past algorithm choices, modeling environments altered by actions.Examples include website layouts, news recommendations, dynamic pricing, and repeated-auction parameters.
  • Experts advice: log2 K mistakes suffice for majority vote with a perfect expert, and Ω(min(T, log K)) mistakes are unavoidable for any algorithm.The lower bound shows the majority-vote guarantee is optimal in this setting.
  • Weighted majority: WMA handles imperfect experts with a cost-dependent mistake bound, but its guarantee does not imply sublinear regret when cost∗= Ω(T).When cost∗=0, the bound recovers O(ln K) mistakes; majority vote fails once every expert has made a mistake.
  • Hedge: Any deterministic algorithm can incur total cost T against a deterministic oblivious adversary, even when cost∗≤T/K.Randomization is therefore necessary for general online learning with experts, motivating Hedge’s randomized weighted selection rule.
  • Hedge: O(√T log K) regret is the best possible for Hedge and for regret in full generality.The section also notes that logarithmic-in-T regret bounds from the IID setting do not extend to the general case.

Adversarial Bandits

The chapter studies adversarially chosen costs, including expert advice, under a deterministic oblivious adversary with bounded per-round costs. Its algorithm reduces the problem to full feedback and obtains an essentially optimal regret bound that improves the IID result by replacing log T with log K.

  • Problem and approach: The chapter analyzes multi-armed bandits with adversarially chosen costs and explicitly includes expert advice.The algorithm is based on a reduction to the full-feedback problem.
  • Problem and approach: The exposition assumes a deterministic, oblivious adversary whose costs are fixed in advance, with regret measured against the best-in-hindsight arm.Per-round costs satisfy c_t(a) ≤ 1 for every round and arm.
  • Regret guarantee: The regret upper bound matches the IID-bandit result while replacing log T with log K.The passage states that this replacement slightly improves the IID bound.
  • Regret guarantee: The regret bound is essentially optimal.The passage attributes this optimality to a lower bound beginning with Ω, but its remainder is not provided.

Recap from Chapter 5

The chapter recaps adversarial bandits as a reduction from full-feedback learning with experts, using exploration and unbiased fake costs to control true regret. It then extends the framework to expert advice and several changing-environment settings, while identifying both near-optimal guarantees and fundamental limitations.

  • Reduction to full feedback: Adversarial bandits reduce to full-feedback learning by creating one always-recommending expert per arm and feeding Hedge unbiased fake costs.Exploration ensures sufficient sampling, while fake costs provide valid inputs to Hedge and estimate the true costs without bias.
  • Bandits with expert advice: The reduction extends to bandits with expert advice, where experts may recommend different arms each round and regret is measured against the best expert.The stated protocol uses K arms, N experts, and T rounds under a deterministic, oblivious adversary.
  • Bandits with expert advice: The regret bound has logarithmic dependence on N, allowing the method to handle many experts, and is essentially optimal through a nearly matching lower bound.The lower bound holds for any given triple of parameters K, T, and N.
  • Exp4 guarantees: Exp4 achieves regret with parameters γ = T −1/4 K1/2 (log N)1/4 and ϵ = ϵu under a deterministic-oblivious adversary.The theorem applies to adversarial bandits with expert advice; the supplied passage gives the parameter choice but the displayed regret expression is incomplete.
  • Exp4 guarantees: Uniform exploration is unnecessary: the analysis extends to γ = 0 because Hedge assigns every expert non-zero probability.This removes the earlier need to guarantee qt(at,e) > 0 through explicit uniform exploration.
  • Extensions and limitations: For shifting policies, Exp4 gives ˜O(KST) regret, while nonstationary environments with total variation V have optimal regret rate ˜O(V 1/3T 2/3) when V is known.The shifting-policy result treats each S-shifting policy as an expert with N ≤(KT)S; unrestricted adversaries can make sublinear counterfactual regret impossible, although memory-restricted adversaries permit ˜O(mK1/3T 2/3).

Linear Costs and Semi-Bandits

This chapter introduces online routing, combinatorial semi-bandits, linear bandits, and online linear optimization through bandit problems with linear costs. It formalizes actions as low-dimensional vectors and examines full-feedback and semi-bandit settings.

  • Chapter scope: The chapter jointly introduces online routing, combinatorial (semi-)bandits, linear bandits, and online linear optimization.Its common framework is bandit problems in which actions are represented by vectors in R^d and costs are linear in that representation.
  • Feedback regimes: The problem is challenging under full feedback and becomes more difficult with bandit feedback, motivating the intermediate semi-bandit feedback regime.The chapter studies these related feedback settings within the linear-cost framework.
  • Model: The framework has K actions over a fixed horizon T, with each action a ∈[K] yielding nonnegative cost c_t(a) at round t ∈[T].Actions lie in the unit hypercube [0, 1]^d and are represented by low-dimensional real vectors.
  • Model: Costs are linear in each action’s vector representation: c_t(a) = a · v_t for a weight vector v_t ∈R^d.The weight vector is shared across actions at a given time step but can depend on the current time step.

Recap: bandits-to-experts reduction

The section presents an abstract reduction from bandit feedback to full feedback by treating each arm as an expert and supplying an arbitrary full-feedback algorithm with bounded fake costs. Under the theorem’s regret assumption, this reduction transfers the algorithm’s guarantee to adversarial bandits, and Hedge provides a concrete instantiation.

  • Reduction setup: The reduction identifies each arm with an expert that always recommends that arm, allowing an arbitrary full-feedback algorithm ALG to operate on fake costs.Algorithm 7.1 is framed for adversarial bandits with K arms and T rounds, with experts corresponding to arms.
  • Guarantee: Theorem 7.1 assumes ALG achieves E[R(T)] ≤ f(T, K, u) against an adaptive u-bounded adversary, with known u > 0.Fake costs are assumed bounded from above and satisfy the stated condition, while the reduction’s unspecified steps do not affect the Chapter 6 analysis.
  • Algorithm 7.1: Algorithm 7.1 samples an expert from ALG’s distribution, follows it with probability 1 − γ, explores otherwise, observes bandit feedback, and returns fake costs to ALG.The exploration rule, extra feedback, and fake-cost construction are left unspecified in the abstract algorithm and are instantiated later for special cases.
  • Hedge instantiation: With Hedge, the reduction uses f(T, K, u) = O(u · T ln K) and sets γ = T −1/4 √u · log K.These choices follow from Theorem 5.16 and yield the corollary’s regret guarantee for Algorithm 7.1.

Contextual Bandits

Contextual bandits model decisions whose rewards depend on observable contexts and chosen actions, with change over time explained by contexts. The chapter develops Lipschitz, linear, and policy-class approaches, offline evaluation, and scalable deployment practices.

  • Contextual Bandits: Each round observes a context, selects an arm, and receives a reward whose distribution depends on the context–action pair.Contexts are chosen by an oblivious adversary, while rewards are independently drawn from a fixed distribution for each context–action pair.
  • Lipschitz assumptions: Lipschitz contextual bandits with uniform discretization achieve regret E[R(T)] = O(T 2/3(LK ln T)1/3).The chapter also gives context-specific regret E[Rx(T)] = O(√Knx ln T).
  • Linearity assumptions: LinUCB provides rigorous worst-case and gap-dependent regret guarantees for linear contextual bandits.The supplied passage reports worst-case regret as ˜O(d … dT) and gap-dependent regret as (d2/∆) · polylog(T).
  • Fixed policy classes: Exp4 supports arbitrary policy classes, with regret depending logarithmically on |Π|, while oracle-based methods retain logarithmic |Π| dependence and ˜O(T 2/3) dependence on T.For many special cases, the number of policies is |Π| = Kc, independent of the number of contexts.
  • Offline learning: Inverse-propensity scoring is unbiased and can evaluate policies in a model-independent way, including policies derived under deterministic-oblivious-adversary rewards.The methodology provides high-probability accuracy when sampling probabilities are sufficiently large.
  • Large-scale applications: Scalable systems separate fast front-end policy execution and logging from slower back-end training and evaluation, with deployment proceeding through preparation and a small-traffic pilot.Preparation includes framing the application, checking data availability, and planning infrastructure integration.

Bandits and Games

This section studies repeated zero-sum games in which bandit algorithms play against adversaries, focusing on convergence toward minimax and approximate Nash equilibria. Sublinear regret yields equilibrium guarantees, including a self-contained minimax-theorem proof and extensions to correlated equilibria.

  • Arbitrary adversary: For an arbitrary adversary, ALG’s total average cost is at most v∗ + R(T)/T.With expected sublinear regret, ALG’s expected average cost is asymptotically upper-bounded by the minimax value v∗.
  • Best-response adversary: Against a best-response adversary, sublinear expected regret makes ALG’s expected average play asymptotically achieve the minimax property of p∗.The best-response adversary chooses each column to maximize expected reward given the history.
  • Minimax theorem: Minimax and maximin strategies form a Nash equilibrium: M(p∗, q∗) = v∗.The equality v∗ = v♯ supports the conclusion that p∗ and q∗ form a Nash equilibrium and provides an alternative proof of von Neumann’s minimax theorem.
  • Both players minimize regret: If ALG and ADV have regrets R(T) and R′(T), their average play forms an ϵT-approximate Nash equilibrium with ϵT := R(T)+R′(T).The corresponding average costs and rewards converge, and high-probability guarantees follow by replacing regrets with high-probability bounds.
  • High-probability guarantees: Hedge and Exp3 provide high-probability regret bounds of O(√T log K) with full feedback and O(√TK log K) with bandit feedback.These bounds yield the guarantees of Theorem 9.5 when the relevant high-probability conditions hold.
  • Coarse correlated equilibrium: The distribution ¯σ defined in (9.18) forms an ϵT-approximate coarse correlated equilibrium, where ϵT = E[R(T)].The argument also characterizes ¯σ as an approximate equilibrium with ϵ = E[R(T)].

Bandits with Knapsacks

Bandits with knapsacks (BwK) generalizes bandit problems to global resource constraints, motivated by dynamic pricing with limited inventory. The framework models each arm’s outcome as a reward-and-consumption vector and highlights how resource use complicates exploration and benchmark choice.

  • General framework: BwK is a general framework for bandit problems with global constraints, including supply constraints in dynamic pricing.The chapter also presents solutions based on Chapter 9 machinery, successive elimination, and optimism under uncertainty.
  • General framework: Each round yields a reward and consumption of d resources, with the algorithm stopping when any resource exceeds its budget.The outcome vector lies in [0, 1]^(d+1), and each arm’s vector is sampled IID from a fixed distribution.
  • Discussion: Resource consumption during exploration can limit later exploitation, so Explore-first fails when budgets are too small.BwK also requires objectives beyond per-round expected reward because resource consumption affects an arm’s desirability.
  • Benchmarks: Alternating between two resource-specific arms can be twice as good as using either fixed arm.In the example, both arms yield reward 1, while each consumes a different one of two resources.
  • Benchmarks: BwK compares performance against three benchmarks: the best arm, the best distribution over arms, and the best algorithm.These benchmarks are defined uniformly relative to an all-knowing benchmark.

E [ REW(ALG | I) ] , (10.1)

LagrangeBwK uses a repeated Lagrangian game to solve bandits with knapsacks, with its LP value providing an upper bound on the optimal benchmark. With EXP3.P.1 and Hedge, it achieves a regret bound that is essentially optimal up to logarithmic factors, while extensions have regime-specific guarantees and limitations.

  • LP benchmark: T · OPTLP ≥ OPT, so the linear-program value supplies an upper bound on the best expected BwK reward.The LP solution also satisfies OPTLP = r(D∗) = L(D∗, λ∗).
  • Algorithm: LagrangeBwK is a repeated Lagrangian game whose primal algorithm receives bandit feedback and dual algorithm receives full feedback.Each round’s outcome vector suffices to generate both feedback streams, making the algorithm implementable.
  • Regret guarantee: Theorem 10.14 gives LagrangeBwK a high-probability regret bound when EXP3.P.1 is used as ALG1 and Hedge as ALG2.The bound is optimal in the worst case up to logarithmic factors when B = Ω(T).
  • Special regimes: LagrangeBwK achieves optimal ˜O(KT) regret when resource consumption is zero, because the T/B factor vanishes.More generally, the optimal regret expression depends on the unknown optimum OPT and budget B rather than only the time horizon T.
  • Limitations: The regret bound is essentially optimal for each (K, B, T), combining stochastic-bandit regret with a global-constraints term and only logarithmic dependence on d.However, guarantees can be suboptimal when min(B, OPT) ≪Ω(T), and ALG1 requires an adaptive-adversary bound for Lagrangian rewards.

Bandits and Agents

The section studies bandit learning when sequential agents have their own knowledge and incentives, showing that naive information sharing can prevent exploration. It develops incentive-compatible recommendation-based algorithms and characterizes when exploration is feasible and how costly it can be.

  • Motivation: Recommendation systems motivate the model because users consume information from previous users and generate observations that future users can consume directly or through aggregation.Examples include restaurant reviews, photos, tweets, summaries, and recommendations.
  • Failure of Greedy: Myopic Bayesian-greedy agents can stop exploring after observing one favorable arm, potentially never trying another arm even when it is optimal.Under mild assumptions, this behavior causes Ω(T) Bayesian regret; with independent positive-density priors, regret is at least cP · T.
  • Incentive-Compatible Exploration: The model combines Bayesian bandit learning with agents’ knowledge and incentives, and its algorithms seek Bayesian incentive compatibility while preserving exploration.The framework treats algorithmic and economic components as distinct parts, and RepeatedHE reduces ordinary bandit algorithms to BIC bandit algorithms.
  • Information Revelation: The principal need only issue recommendations rather than reveal supporting information, while full-history revelation fails because agents independently follow Bayesian-greedy behavior.This recommendation-only conclusion is presented as a version of Myerson’s direct revelation principle, subject to subtle model assumptions.
  • Complexity and Incentive Costs: The C-optimal sample complexity is OC(K) when minsupp(C) > ΦC and exp ( ΩC(K) ) when minsupp(C) < ΦC.For Beta and truncated-Gaussian priors, it is exponential in σmin(C), while performance penalties from incentives depend on the chosen benchmark and measure.

A Concentration inequalities

This appendix introduces concentration inequalities as high-probability statements that independent-variable averages remain close to their expectations. It presents Hoeffding-type bounds and extensions to bounded intervals, bounded variance, Gaussian variables, and martingale-style dependence.

  • A Concentration inequalities: Concentration inequalities formalize that the average X_n is close to its expectation μ_n with high probability.They concern statements bounding the probability that |X_n − μ_n| is small.
  • A Concentration inequalities: Hoeffding’s inequality gives Pr[E_α,β] ≥ 1 − 2 · T^−2α with β = 1 when X_1, …, X_n ∈ [0,1].Here T can represent the bandit time horizon, and α = 2 suffices for most applications in the book.
  • A Concentration inequalities: The same probability bound extends to bounded intervals, bounded variance, and Gaussian variables under appropriate β values.The listed cases are X_i ∈ [a_i,b_i] with β = 1, X_i ∈ [0,1] with Variance(X_i) ≤ β/8, and Gaussian variance at most β/4.
  • A Concentration inequalities: A martingale-style conditional-mean assumption yields the same bound with β = 4 even when variables are dependent or non-identically distributed.The assumption requires E[X_i | X_1 ∈ J_1, …, X_{i−1} ∈ J_{i−1}] = μ_i for interval histories.

B Properties of KL-divergence

This section proves two core properties of KL-divergence: nonnegativity with equality exactly for identical distributions, and a chain rule for product distributions.

  • Gibbs’ Inequality: KL(p, q) ≥ 0 for any distributions p and q, with equality if and only if p = q.This is Gibbs’ inequality, established using the convexity of f(y) = y ln(y) and Jensen’s inequality.
  • Chain rule for product distributions: For product distributions over Ω = Ω1 × · · · × Ωn, KL-divergence satisfies a chain rule relating KL(p, q) to the component distributions.The distributions factor as p = p1 × · · · × pn and q = q1 × · · · × qn, with pj and qj defined on Ωj.

APPENDIX B. PROPERTIES OF KL-DIVERGENCE 163

This appendix develops properties of KL-divergence, including a proof of Pinsker’s inequality and bounds for divergences between slightly biased random coins.

  • Pinsker’s inequality: Pinsker’s inequality is established for a fixed event A ⊂ Ω.The proof first derives an intermediate relation for restricted distributions and then applies it to A and its complement.
  • Pinsker’s inequality: The proof defines conditional distributions p_B(x) = p(x)/p(B) and q_B(x) = q(x)/q(B) for x ∈ B.These restricted distributions provide the intermediate step used in the Pinsker proof.
  • Random-coins bounds: KL(RC_ϵ, RC_0) ≤ 2ϵ^2 and KL(RC_0, RC_ϵ) ≤ ϵ^2 for random coins with bias ϵ/2.RC_ϵ is distributed over {0, 1} with expectation (1 + ϵ)/2.
  • Random-coins bounds: The coin calculation bounds the relevant logarithmic expression by 2ϵ/(1 − ϵ), yielding ϵ^2/(1 − ϵ) ≤ 2ϵ^2.The final inequality applies under the stated range implicit in the derivation.
Loading 1904.07272v8…