Bandit Algorithms
Tor Lattimore · Csaba Szepesvári
Cambridge University Press, 2020; existing author-online source maps retained
Bibliographic metadata checked 2026-09-09. Page and theorem mappings are separately audited.Source-mapped reading view
Bandit Book
Ten core teaching routes plus source Chapters 13–17. Broader Bandit classification, techniques, theorem-level bounds and research frontiers are separate linked views rather than pseudo-chapters.
Teaching routes · 01–10
These ten curated routes keep their original numbering. They are not the textbook's chapter numbers and do not cover the entire book.
1. Finite bandits, traces, and regret
Ch. 1 and Ch. 4, especially §4.5 · online pp. 8–16 and 56–69; regret decomposition pp. 62–63
2. Probability, kernels, filtrations, and concentration
Ch. 2, Ch. 3, and Ch. 5 · online pp. 18–42, 46–54, and 74–81
3. Explore-Then-Commit
Ch. 6 · online pp. 91–96
4. UCB: confidence events to regret
Ch. 7; KL-UCB extension in Ch. 10 · online pp. 102–111; KL-UCB pp. 133–141
5. OFUL, self-normalized confidence, and stopping times
Ch. 19–20; stopping times in §3.3 · online pp. 238–262; stopping-time basics pp. 50–54
6. Thompson sampling and Bayesian regret
Ch. 34 and Ch. 36 · online pp. 421–436 and 460–475
7. EXP3 and adversarial concentration
Ch. 11–12 · online pp. 148–172
8. Tsallis-FTRL, corruption, and nonstationarity
Ch. 28 (FTRL and mirror-descent foundation) · online pp. 327–344
9. Finite-horizon reinforcement learning
Ch. 38 · online pp. 512–538
10. Automation, resources, and open routes
Parts VII–VIII as a background index · online pp. 358–538
Source chapters · Part IV, 13–17
Required main-text contracts have prior merged compilation evidence; optional notes and exercises are not all complete. This build's verification banner states the local gate status.
Chapter 17 retains explicit source corrections: Claim 17.6 uses
T_i ≤ n/2; Theorem 17.4 uses 0 < δ ≤ 1/32, c = 1/160 and C = 64.
Chapter 13
Compiled
Lower Bounds: Basic Ideas
155–159 print · 189–194 PDF
Theorem 13.1 compiles through Chapter 15 with c=1/54. Chapter 13 also compiles fixed-class minimax-optimality, the canonical iid Gaussian empirical-mean law, midpoint error events, the Chernoff companion, and both exact Mills-ratio bounds of Eq. (13.4) rescaled to the printed Eq. (13.1). The broader 1-subgaussian class with gaps in [0,1] now has a compiled fixed-horizon MOSS upper bound and constant-factor near-minimax theorem. The frozen main-text contract is complete: PR #105, authoritative-main checks, Pages deployment and live desktop/mobile acceptance pass for b38630c. Notes and Exercises remain optional and unformalized.
Chapter 14 Compiled Foundations of Information Theory 160–169 print · 195–206 PDFThe frozen required body is compiled: Huffman optimality, exact-real arithmetic block coding and converse, finite/partition/common-density KL, the source affinity/overlap route, and Gaussian testing. Independent review, PR #106, main run 33959196451, Pages and live desktop/mobile acceptance passed. The singleton and uniform-code qualifications below are part of the accepted boundary; optional Notes/Exercises are not claimed complete.
Chapter 15 Compiled Minimax Lower Bounds 170–176 print · 207–214 PDFThe frozen required body (§15.1–15.2) is compiled: Lemma 15.1 and Theorem 15.2 use one arbitrary randomized HistoryAlgorithm, the canonical finite-history law, exact unit-Gaussian construction and 1/27 constant, with worst-case and minimax consequences. Optional Exercise 15.7 remains partial: measurable-map KL contraction reuses Chapter 14's trim API, and the fixed-horizon observation corollary compiles; stopped-history information and F_tau factorization remain open. Notes and other exercises are outside the required-body completion contract.
Chapter 16 Compiled Instance-Dependent Lower Bounds 177–184 print · 215–223 PDFDefinition 16.1, Theorem 16.2, Lemma 16.3, and Theorem 16.4 compile with the source quantifiers, information branches, constants, and positive-part placement.
Chapter 17 Compiled High-Probability Lower Bounds 185–190 print · 224–230 PDFAll Chapter 17 body endpoints pass the full Lean/Tests/harness gate, including same-policy hard-law coupling and deterministic matrix extraction; integrated into main via PR #101. Approved corrections: Claim 17.6 uses T_i ≤ n/2; Theorem 17.4 uses 0 < δ ≤ 1/32 with c=1/160, C=64 and a strict CDF tail. This is corrected-chapter closure, not a proof of the unchanged printed statements or every optional exercise.
Beyond the core textbook
This section used to mix a small set of “Extended Chapters” with BanditRLwiki. It is now only a navigation layer: classification, techniques, literature bounds and open problems have different truth contracts and live on separate pages.
Learn the landscape
Bandit Taxonomy
Settings, objectives, methods, resource/oracle models and application bridges—including the full long-tail list and quantum bandits.
Learn the mathematical moves
Technique Map
Which new proof/algorithmic technique each setting needs: robust estimation, zooming, RKHS information gain, combinatorial relaxation, primal–dual control, quantum estimation/testing and more.
Read theorem-level evidence
Bound & Source Atlas
Compatible upper/lower bounds, primary theorem sources, assumptions and the exact local Lean boundary.
Research frontier
Frontier · open problems
Source-traceable posed → partial → resolved histories. Literature openness is never inferred from missing Lean.
Lean formalization frontier → · Functor Hypergraph → · Underlying Lean Graph →