1. Preface
  2. Notation
  3. Introduction
  4. Decision-making Under Uncertainty
    1. Definitions and Basic Examples
    2. Algorithms for Decision-making
    3. Evaluating Performance via Regret
    4. Problem Difficulty and Lower Bounds
    5. Empirical Benchmarking
    6. Exercises
    7. Deferred Proofs
  5. Expected Improvement
    1. Bayesian Dynamic Programming
    2. Algorithms via One-step Approximations
    3. General Feedback and Expected Utility Improvement
  6. Gittins Indices
    1. The Pandora’s Box Decision Problem
    2. The Gittins Index in Pandora’s Box
    3. Gittins Indices for General Decision Problems
  7. Optimism
    1. Upper Confidence Bounds
    2. Classical Algorithms as Instances of Optimism
  8. Information-theoretic Algorithms
    1. Entropy Search
    2. Bayesian Algorithm Execution
  9. Thompson Sampling
    1. Concentration-based Analysis
    2. Adversarial Analysis
    3. Exploration in Large Language Models
  10. Appendix

Chapter 4

Gittins Indices

🚧 Under construction. Headings indicate planned content. 🚧

4.1. The Pandora’s Box Decision Problem

4.2. The Gittins Index in Pandora’s Box

4.3. Gittins Indices for General Decision Problems

3. Expected Improvement5. Optimism

© 2026 Alexander Terenin. All rights reserved.