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 3

Expected Improvement

🚧 Under construction. Headings indicate planned content. 🚧

3.1. Bayesian Dynamic Programming

3.2. Algorithms via One-step Approximations

3.3. General Feedback and Expected Utility Improvement

2. Decision-making Under Uncertainty4. Gittins Indices

© 2026 Alexander Terenin. All rights reserved.