~vaibhav

Bandit Algorithms

My annotations of the book "Bandit Algorithms" (Lattimore & Szepesvári).

· 1 min read · 19 words
Open document ↗

Annotated copy of Lattimore & Szepesvári, Bandit Algorithms — the source text behind the algorithms/bandits notes that cite it.

Reading order

  1. 1Stochastic Processes, Markov Chains, and Stochastic BanditsExistence of infinite sequences of random variables (Borel spaces, the binary-digit construction, projective families); probability kernels, product kernels and the Ionescu–Tulcea theorem; homogeneous Markov chains; filtrations, martingales, super- and submartingales, stopping times and the stopped σ-algebra; Doob's optional stopping theorem and the maximal inequality for nonnegative supermartingales; regular conditional distributions and disintegration. Then the formal stochastic bandit model; the learning objective and why expected reward is a choice; unstructured and structured environment classes; regret, its basic properties, sublinear and instance-dependent targets, and Bayesian regret; the regret decomposition into gaps times expected pulls; the canonical bandit model, its uniqueness, the random-table and reward-stack models; uncountable action sets; risk, pseudo-regret, mixing policies, and the failure of follow-the-leader.
  2. 2Concentration of Measure for BanditsHow fast a sample mean learns the true mean. Tail probabilities of the empirical mean; Markov and Chebyshev and why their 1/(nε²) decay is too slow; calibrating against the central limit theorem with the Gaussian tail bound, and why the CLT is asymptotic, unreliable for rare events, and fails for Bernoulli(1/n); the Cramér–Chernoff method, moment- and cumulant-generating functions, light and heavy tails; σ-subgaussian random variables, their Gaussian-like tails, closure under scaling and independent sums, and the deviation-form confidence bounds µ ≤ µ̂ + √(2σ²log(1/δ)/n); examples (Gaussian, bounded, exponential); and the results from the notes and exercises — Hoeffding's lemma and inequality, Bennett and Bernstein, large-deviation rate functions and the Bernoulli KL rate, the Bernoulli subgaussianity constant, χ² tails, the expected maximum of subgaussians, and the Bretagnolle–Huber–Carol inequality.
  3. 3Explore-Then-Commit and the Upper Confidence Bound AlgorithmsThe core finite-armed stochastic bandit algorithms in order of sophistication. Explore-Then-Commit (ETC) and its regret bound; tuning the commitment time; worst-case versus gap-dependent bounds; anytime algorithms, the doubling trick, ε-greedy and phased elimination. The optimism principle and UCB(δ), the random-sample-size subtlety, the good-event proof of the O(Σ log n/Δᵢ) and O(√(nk log n)) bounds. Asymptotically optimal UCB with confidence level f(t) = 1 + t log²t and the optimal constant 2/Δᵢ. MOSS, Doob's maximal inequality, the peeling device and the O(√(kn)) minimax bound, and MOSS's two weaknesses (suboptimality relative to UCB, instability of the regret distribution). Bernoulli concentration through the relative entropy d(p,q), Pinsker's inequality, the Chernoff bound and KL confidence intervals; KL-UCB and its asymptotic regret Σ Δᵢ/d(μᵢ,μ*). Extensions to known per-arm scales, empirical Bernstein (UCB-V), median-of-means and bounded rewards.
  4. 4The Exp3 and Exp3-IX AlgorithmsAdversarial (assumption-free) finite-armed bandits. Why models, and when to drop stochasticity; why randomization is necessary (deterministic policies suffer n(1−1/k)); the adversarial protocol, regret against the best fixed arm, and the reduction showing adversarial regret bounds stochastic regret (so the minimax regret is at least c√(nk)). Importance-weighted estimators (reward-based and loss-based), unbiasedness, the 1/P variance blow-up, and why every unbiased estimator is importance-weighted. Exp3 (exponential weights on loss-based estimates), the telescoping-potential proof of 2√(nk log k) and the sharper √(2nk log k), and its heavy-tailed regret distribution. Exp3-IX: implicit exploration by adding γ to the denominator, a bias–variance trade, a concentration lemma exploiting negatively correlated estimates, and high-probability regret O(√(nk log(k/δ))). Notes on Hedge, oblivious versus reactive adversaries, policy regret, non-stationarity, first-order and quadratic-variation bounds, Exp3.P, the Gumbel trick and follow-the-perturbed-leader.
  5. 5Lower Bounds for Finite-Armed BanditsWhy no algorithm can beat certain regret rates. Worst-case versus instance-dependent lower bounds; minimax regret, minimax optimality and Pareto optimality; reducing bandits to two-point hypothesis testing (competition versus similarity). The information-theoretic toolkit — relative entropy for general measures, the Bretagnolle–Huber inequality and its proof via Le Cam's inequality, Pinsker, Hellinger and χ², chain rule and data processing, Neyman–Pearson. The divergence decomposition D(Pν,Pν′) = Σ E[Tᵢ(n)] D(Pᵢ,Pᵢ′); the minimax bound √((k−1)n)/27 for Gaussian bandits, Fisher information and why KL is quadratic in the gap, Le Cam and Assouad methods, and lower bounds for Bernoulli bandits, small horizons and ETC. Consistency, d_inf and the Lai–Robbins/Burnetas–Katehakis asymptotic lower bound c*(ν) = Σ Δᵢ/d_inf; finite-time instance-dependent bounds for nearly minimax-optimal policies; sharpness of UCB-V and a variance–optimality trade-off. High-probability lower bounds for stochastic and adversarial bandits, why knowing δ in advance helps, and the near-tightness of Exp3-IX.
  6. 6Contextual BanditsBandits with side information. Why ignoring context makes the benchmark too weak, and the general trade-off of choosing a competitor class (meaningful benchmark versus learnability). Adversarial k-armed contextual bandits; regret against the best context-to-arm map; one Exp3 per context and its 2√(nk|C| log k) worst case. Shrinking the competitor class with partitions, similarity constraints, or supervised-learning predictors. Bandits with expert advice; Exp4 (exponential weights over experts, importance-weighted action estimates propagated through the advice matrix), its √(2nk log M) regret, recovering the per-context bound with M = k^|C|, and the agreement-adaptive √(E*ₙ log M) bound with a time-varying learning rate. Notes on computation (O(M + k) per round), optimisation oracles, reduction of stochastic contextual bandits to cost-sensitive ERM, Exp4-IX, non-oblivious experts, finite-memory policies, epoch-greedy ETC at O(n^{2/3}), and VC-class competitors.
  7. 7Stochastic Linear BanditsBandits where each action is a feature vector and the mean reward is linear in an unknown parameter. Stochastic contextual bandits with feature maps (and why unstructured contexts are hopeless); the stochastic linear bandit model and its special cases (finite-armed, contextual, combinatorial); LinUCB/OFUL — optimism over an ellipsoidal confidence set around the regularised least-squares estimate; the elliptical potential lemma and the O(d√n log n) regret bound; computation (the bonus form ⟨θ̂,a⟩ + √β‖a‖_{V⁻¹}, Sherman–Morrison, rarely-switching updates); kernels, generalised linear models, spectral bandits and Lipschitz contexts. Fixed finite action sets: phased elimination with G-optimal (Kiefer–Wolfowitz) exploration and O(√(dn log(nk))) regret, changing finite action sets, and misspecification. Sparse parameters: selective explore-then-commit on the hypercube with O(‖θ‖₀√(n log n)) regret, and online-to-confidence-set conversion turning a sparse online regression algorithm into OLR-UCB with O(√(dnm₀) log n) regret.
  8. 8Confidence Bounds and Optimal Design for Least Squares EstimatorsThe statistical machinery behind linear bandits. Fixed-design least squares — per-direction subgaussian widths √(2‖x‖²_{V⁻¹} log(1/δ)), covering numbers, and the √d price of a uniform bound. Why adaptive (sequential) designs break this; the linearisation ½‖S‖²_{V⁻¹} = maxₓ ⟨x,S⟩ − ½‖x‖²_V; the exponential supermartingale; Laplace's method; the method of mixtures with a Gaussian prior giving the self-normalised bound ‖Sₜ‖²_{Vₜ(λ)⁻¹} ≤ 2 log(1/δ) + log(det Vₜ(λ)/λᵈ) uniformly in time, and the resulting confidence ellipsoids. Variance versus bias terms, why √d is unavoidable, and why fixed-direction widths need √d under sequential design. Coverings and packings, Hoeffding–Azuma, anytime bounds and the law of the iterated logarithm via mixtures, sequential likelihood-ratio confidence sets. G- and D-optimal designs, the Kiefer–Wolfowitz theorem (min g = d, core set of at most d(d+1)/2 points), the minimum-volume enclosing ellipsoid, and Frank–Wolfe/Fedorov–Wynn computation.
  9. 9Lower Bounds for Stochastic Linear BanditsHow the geometry of the action set shapes what is achievable in stochastic linear bandits. Minimax Ω(d√n) lower bounds on the hypercube (sign-flipping and an averaging hammer) and on the unit ball (stopping at a per-coordinate exploration budget, Pinsker plus the stopped chain rule), so LinUCB is optimal up to logs; the convex-hull reduction; Ω(√(pdn)) for p-sparse parameters via the multi-task bandit; and the impossibility of adapting to misspecification (O(√n) on linear instances forces Ω(k√n) on non-linear ones). The asymptotic lower bound for fixed finite action sets — every consistent policy must shrink ‖a‖²_{Ḡₙ⁻¹} below Δₐ²/(2 log n), giving the constant c(A,θ) from an allocation optimization that is achievable — and the "clouds looming for optimism" example, where optimistic algorithms (and Thompson sampling) pay Ω(log n/ε) against an optimal 2γ² because they refuse informative but statistically suboptimal actions.
  10. 10Convex Analysis for BanditsThe convex-analysis toolkit behind adversarial linear bandit algorithms (mirror descent, follow-the-regularised-leader). Convex sets, convex hulls, extended-real-valued convex functions via epigraphs, domains and properness, strict convexity, Hessian characterisation, the Fenchel dual and biduality; Jensen's inequality with a graphical proof; the Bregman divergence (nonnegativity, convexity in its first argument, squared Euclidean and unnormalised-negentropy/relative-entropy examples); Legendre functions ("dishes" with ever-steepening edges), gradient maps as bijections inverse to the dual's, duality of Bregman divergences, and interior minimisers; exact second-order (Hessian) forms of Bregman divergences and the key inequality ⟨x−y,u⟩ − D_f(x,y)/η ≤ (η/2)‖u‖²_{(∇²f)⁻¹}; first-order optimality for constrained convex problems; Bregman projections and the generalised Pythagorean inequality. Worked duals for −2Σ√x and the negentropy.
  11. 11Adversarial Linear BanditsAdversarial linear bandits, in which an adversary picks loss vectors and the learner sees only the scalar loss of the action it played. Exp3 for linear action sets uses least-squares importance-weighted estimates Q_t⁻¹A_tY_t and needs mixed-in Kiefer–Wolfowitz exploration, giving O(√(dn log k)) regret; continuous exponential weights over convex action sets (log-concave sampling) gives O(d√(n log n)). Online linear optimisation is solved by mirror descent and follow-the-regularised-leader (FTRL); the two coincide for Legendre potentials, both run as a mirror-map step followed by a Bregman projection, and both obey the regret bounds diam_F/η plus a local dual-norm term, recovering online gradient descent and exponential weights as special cases. Applying them to bandits uses unbiased estimates and randomised rounding. On the unit ball, FTRL with the potential −log(1−‖a‖)−‖a‖ gets O(√(dn log n)). Also covered: anytime Exp3, the √(kn) INF/Tsallis algorithm, log-barrier first-order bounds, Sion's minimax theorem via no-regret learning, and how adversarial and stochastic linear bandits relate (an augmented reduction, parameter noise and why the unit-ball rates differ, and the open problem of contextual adversarial regret).
  12. 12Combinatorial BanditsLinear bandits whose actions are binary vectors in {0,1}ᵈ with at most m ones — paths, m-subsets, one choice per task. Losses lie in [0,1]ᵈ and actions are compared to the best fixed action in hindsight. Applications covered are online shortest paths, ranking/selection, and multi-task bandits. With bandit feedback, linear Exp3 gives m^{3/2}√(12dn log(ed/m)), which is tight in m but computationally hopeless in general (repeated TSP is hard to approximate). With semi-bandit feedback (each chosen coordinate's loss is seen), mirror descent with negentropy on co(A) gives √(2nmd(1+log(d/m))), but it needs a convex projection and a decomposition into a distribution over A. Follow-the-perturbed-leader needs only a linear-optimisation oracle; it is mirror descent with the potential whose dual is a smoothed support function, uses geometric resampling to estimate inverse probabilities, and achieves m√(2(1+e²)nd(1+log d)) with Laplace perturbations. Notes cover lower bounds (m^{3/2} for bandits, √(mdn) for semi-bandits), √m improvements for m-sets, oracle complexity, efficient m-set and shortest-path implementations, and stochastic combinatorial models.
  13. 13Non-Stationary BanditsBandits whose environment changes over time, so regret is measured against a comparator that may switch arms. Standard adversarial regret becomes vacuous when losses shift. Tracking regret competes with the best action sequence that has at most m−1 switches. Exp4 over all switching sequences achieves Õ(√(nmk)), matching an Ω(√(nmk)) lower bound even for learners told the change points, but it is computationally infeasible. Mirror descent with negentropy restricted to the clipped simplex Pₖ₋₁ ∩ [α,1]ᵏ is efficient: the clipping prevents over-commitment and keeps every restart cost at most log(1/α), giving √(mnk log(nk/m)) + √(mnk); plain Exp3 has linear tracking regret. In stochastic bandits with abrupt changes, any policy with o(n) regret Rₙ on a stationary instance suffers n/(22Rₙ) on some two-change instance, so logarithmic stationary regret forces Ω(n/log n). Notes cover contextualising time, discounted and sliding-window UCB and their tuning problem, adaptive multi-scale algorithms, Brownian drift, total-variation budgets with (Vk log k)^{1/3}n^{2/3} rates, and history (Gittins, restless bandits, fixed share, Exp3.S).
  14. 14Ranking BanditsOnline learning to rank. Each round the learner shows an ordered shortlist of m out of ℓ items, observes clicks, and is scored against the best ranking's expected click count. Click models factor the click probability into attractiveness and examination (document-based, position-based, cascade), and a generic model assumes only four properties of v(a,k). TopRank maintains a graph of statistically certified "i beats j" relations, ranks the items in topological layers, shuffles within each layer, and certifies a new pair when the click difference between two items sharing a layer crosses an anytime ternary-martingale boundary. The analysis shows conditional click differences are at least Δᵢⱼ/(α(i)+α(j)), so the order is learned with no wrong certifications and a uniformly randomised block captures the optimal clicks. Regret is O(Σⱼ Σ_{i≤min(m,j−1)} α(i) log n/Δᵢⱼ) and O(√(m³ℓn log n)), robust to time-varying click models. Notes cover the cascade model with CascadeUCB/KL-UCB, linear features, and adversarial ranked bandits (NP-hard offline, greedy (1−1/e) guarantees, semi-bandit reductions), plus the diversity critique.
  15. 15Pure Exploration and Best-Arm IdentificationBandits with a different objective: the learner is judged only on its final recommendation, not on reward collected along the way. Simple regret; uniform exploration's exponential decay but extra √(log k) in the worst case; recommending by empirical play frequencies turns any cumulative-regret algorithm into simple regret Rₙ/n, giving the minimax √(k/n) — while low-cumulative-regret policies misidentify the best arm with only polynomially small probability. Fixed-confidence best-arm identification: sound triples (policy, stopping time, selection rule), the change-of-measure lower bound E[τ] ≥ c*(ν) log(1/(4δ)) with the characteristic time c*(ν)⁻¹ = sup_α inf_alt Σ αᵢ D(νᵢ,ν′ᵢ), Gaussian examples (8/Δ² for two arms; heteroscedastic bounds), and track-and-stop (generalised likelihood-ratio stopping, tracking the optimal proportions with √t forced exploration) achieving it as δ→0. Fixed-budget identification: sequential halving with error 3 log₂k · exp(−n/(16 H₂ log₂k)), the complexity measures H₁ and H₂, and when it beats uniform exploration. Notes on PAC (ε,δ) identification, multiple optimal arms, ordinal optimisation, zeroth-order optimisation, ranking and selection, and open problems.
  16. 16Bayesian BanditsThe Bayesian approach to bandits. Statistical decision theory covers loss, dominance, admissibility, minimax versus Bayes-optimal policies, and how they relate. Posteriors are introduced via a two-marble example and then made rigorous with regular conditional distributions, posterior densities, and the non-uniqueness of posteriors and why it matters to frequentists. Conjugate priors cover Gaussian–Gaussian, Beta–Bernoulli and one-parameter exponential families, where the log-partition function's Bregman divergence is the KL divergence; posterior sequences form Markov chains. The Bayesian bandit environment and its product-form posteriors lead to Bayesian regret, Bayes-optimal policies, and the gap between Bayesian and frequentist guarantees. Further topics: the sup over priors equals minimax regret (Sion); the Bayes-optimal regret's √(kn) worst case and o(√n) for any fixed prior; optimal stopping via the Snell envelope and the Wald–Bellman equation; one-armed Bayesian bandits as optimal stopping, solved by backwards induction on sufficient statistics (Bernoulli exactly, Gaussian approximately); and discounted retirement games, the Gittins index as a fair charge, the Gittins index theorem via prevailing charges and interleavings, Varaiya's algorithm, and where index policies break.
  17. 17Thompson SamplingThompson sampling (posterior sampling) samples an environment from the posterior and plays its optimal action, so exploration comes from posterior randomness. The note covers its Bayesian regret O(√(kn log n)) for any prior, via the key identity that the played action and the optimal action have the same conditional law, which reduces the analysis to UCB's. The frequentist analysis views Thompson sampling as stochastic follow-the-perturbed-leader with per-arm perturbation distributions, and bounds pull counts by an optimism term Σ(1/G₁ₛ − 1) plus an over-sampling term Σ 𝕀{Gᵢₛ > 1/n}; this gives asymptotic optimality (2/Δᵢ) and O(√(nk log n)) for Gaussian Thompson sampling with a flat prior, with higher regret variance than AdaUCB in experiments. Linear Thompson sampling has Bayesian regret O(d√n log n), and its computational advantage is that it needs only a linear optimisation, whereas LinUCB needs a bilinear one. The information-theoretic analysis bounds Bayesian regret by information ratio × information gain; the posterior over the optimal action is a martingale whose expected Bregman divergence telescopes, giving √(kn log k/2) against Bayesian adversaries and √(2kn) with the Tsallis potential. Notes cover information-directed sampling, BayesUCB, sensitivity to misspecified priors, the variance inflation needed for frequentist linear guarantees, and minimax adversarial bounds via Sion's theorem.
  18. 18Partial MonitoringPartial monitoring is online learning in which the learner never sees its loss, only a signal fixed by a known feedback matrix; bandits, full information, label-efficient prediction, dynamic pricing and apple tasting are all special cases. The geometry is a cell decomposition of the outcome simplex into Pareto-optimal, degenerate, dominated and duplicate actions, with neighbours joined in a connected neighbourhood graph. Observability asks whether neighbours' loss differences have unbiased importance-weighted estimators, globally (using any action) or locally (using only actions on the shared face), which is a linear-algebra test ℓₐ − ℓ_b ∈ im(Sᵀ). Every finite game is trivial (0), easy (Θ(√n)), hard (Θ(n^{2/3})) or hopeless (Ω(n)). Lower bounds come from stochastic adversaries that are indistinguishable without playing costly actions. The upper bound uses exponential weights with an optimised exploration distribution and estimator (a convex program balancing regret against stability), in-trees of estimators, and a water-transfer argument for locally observable games; it recovers Exp3 and Hedge. Notes cover stochastic and contextual variants, refined regret for hopeless games, and open problems.
  19. 19Markov Decision Processes — From Bandits to Reinforcement LearningMarkov decision processes as bandits whose actions also move a state. Covers the setup (states, actions, transitions, deterministic rewards), histories and policies (memoryless, deterministic, Markov), traps, strong connectivity and the diameter; the average-reward criterion, with gain, stationary transition matrix, differential value function as a Cesàro sum, the Poisson equation, the Bellman optimality equation (existence, optimality of greedy policies, non-uniqueness, span ≤ diameter) and the Bellman operator. Planning with known dynamics uses two linear programs for the optimal gain and an optimal value function, solved in polynomial time by the ellipsoid method with a separation oracle; value and policy iteration are noted. Learning with unknown transitions measures regret nρ* − Σ rewards. UCRL2 combines L1 confidence sets, the extended MDP trick for optimism and doubling phases to get regret O(D S √(An log(nSA/δ))), proved via optimism, Bellman telescoping, Azuma and phase counting. A lower bound of Ω(√(DSAn)) comes from a tree-to-good/bad-state construction reducing MDPs to bandits with about SA arms. Notes cover episodic MDPs, POMDPs, discounting and the vanishing-discount method, traps and maximal end components, unknown rewards, the √(DS) gap, and the reinforcement learning literature.

← All notes