Bandit Algorithms
Tor Lattimore and Csaba Szepesvári
- Edition
- Cambridge University Press 2020; author-hosted formal PDF
- Publisher
- Cambridge University Press, 2020
Canonical textbook sequence
Textbook Spine / Part IV: Lower Bounds
A chapter-by-chapter, source-faithful formalization of finite-armed bandit lower bounds. This layer is separate from the curated ten-chapter Book Map and reports compiled, partial, planned, and blocked evidence without implying that the whole textbook is formalized.
Scope boundary. This is a separate chapter-by-chapter lower-bound spine. The existing ten-chapter Book Map remains a curated curriculum and is not relabeled as a completed formalization of the entire book.
Canonical source
Chapters 13–17
Work advances in source order. A chapter can expose compiled leaves while its broader source theorem remains partial or planned.
Chapter 13
Partial
Lower Bounds: Basic Ideas
155–159 print · 189–194 PDF
The Chapter 13 semantic and deterministic slice and Chapter 15 same-policy history KL bridge are compiled. Theorem 13.1 remains blocked on the Gaussian regret/event and caller-free minimax terminal.
Chapter 14 Partial Foundations of Information Theory 160–169 print · 195–206 PDFThe source-faithful §14.2 relative-entropy and Bretagnolle–Huber spine is compiled. Entropy/source coding in §14.1 and full sub-sigma-algebra data processing remain outside this scoped gate.
Chapter 15 Partial Minimax Lower Bounds 170–176 print · 207–214 PDFLemma 15.1 now compiles for finite arms, a countably generated reward space, arbitrary Markov arm laws, and one common randomized history policy. The unit-Gaussian dependency slice also compiles; Theorem 15.2 and the 1/27 minimax terminal remain blocked.
Chapter 16 Partial Instance-Dependent Lower Bounds 177–184 print · 215–223 PDFDefinition 16.1, Theorem 16.2, Lemma 16.3, and Theorem 16.4 are source-frozen. Generic consistency, d_inf, Gaussian-candidate, eventual power, and eventual log-growth leaves compile; the bandit information, liminf, and finite-time terminals remain blocked.
Chapter 17 Partial High-Probability Lower Bounds 185–190 print · 224–230 PDFClaim 17.5's first-moment witness and reusable threshold, event-subtraction, and deterministic Eq. (17.8) algebra compile. The stochastic tail terminals and clipped-normal adversarial construction remain blocked.
Part IV dependency spine
The graph is a route map, not proof evidence. Each chapter page names the declarations and missing bridges that determine its status.
flowchart LR C13["Chapter 13 · basic ideas<br/>partial: deterministic leaves compiled"] C14["Chapter 14 · information theory<br/>partial: event/KL leaves compiled"] C15["Chapter 15 · minimax lower bounds<br/>partial: Gaussian/tuning leaves compiled"] C16["Chapter 16 · instance-dependent bounds<br/>partial: consistency/d_inf leaves compiled"] C17["Chapter 17 · high-probability bounds<br/>partial: tail-transfer leaves compiled"] L13["minimax semantics<br/>least-explored arm<br/>two-environment algebra"] KL["relative entropy<br/>binary/event KL<br/>history change of measure"] MM["testing and tuning<br/>Gaussian minimax terminal"] ASY["policy consistency + d_inf<br/>liminf terminal blocked"] HP["Claim 17.5 + event subtraction<br/>source terminals blocked"] L13 --> C13 C13 --> C14 C14 --> KL KL --> C15 C15 --> MM MM --> C16 C16 --> ASY ASY --> C17 C17 --> HP classDef compiled fill:#dff5e7,stroke:#247249,color:#123b29 classDef partial fill:#fff2cc,stroke:#9a6b00,color:#563c00 classDef planned fill:#eef2f7,stroke:#64748b,color:#334155 class L13 compiled class C13,C14,C15,C16,C17,KL,MM,ASY,HP partial