Contents

1. Preface

   HTMLPDF

2. Notation

   HTMLPDF

1. Introduction

   HTMLPDF

   Before beginning our journey, we motivate our topic of decision-making under uncertainty quantified by a stochastic model. We introduce the core question of how to use the model’s uncertainty to balance explore-exploit tradeoffs—those between picking known good actions, and trying out new actions in order to learn.

2. 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
   HTMLPDF

   We start by defining an episodic decision problem, leading to the concept of a decision-making algorithm. We examine how to evaluate an algorithm’s performance, and how to determine a problem’s difficulty. We conclude by showing how our theory leads naturally to a set of best practices for empirical benchmarking.

3. Expected Improvement

   1. Bayesian Dynamic Programming
   2. Algorithms via One-step Approximations
   3. General Feedback and Expected Utility Improvement
   HTMLPDF

   We derive the class of improvement-based algorithms from first principles, using greedy approximations to Bayesian dynamic programs. We first do so in a black-box optimization setting, followed by the general case.

4. Gittins Indices

   1. The Pandora’s Box Decision Problem
   2. The Gittins Index in Pandora’s Box
   3. Gittins Indices for General Decision Problems
   HTMLPDF

   We describe a class of Bayesian episodic decision problems that can be solved exactly using Gittins indices—a carefully constructed notion of a fair value. We start with Pandora’s Box, a concrete example, then consider its general analogs.

5. Optimism

   1. Upper Confidence Bounds
   2. Classical Algorithms as Instances of Optimism
   HTMLPDF

   We introduce optimistic algorithms for episodic decision problems, and present the Bayesian upper confidence bound algorithm. We then show how certain classical algorithms, including A^* search, can be seen as instances of optimism.

6. Information-theoretic Algorithms

   1. Entropy Search
   2. Bayesian Algorithm Execution
   HTMLPDF

   We outline the class of entropy search algorithms, which are constructed using information-theoretic quantities. After considering specific variants, we present the general approach of information-based Bayesian algorithm execution.

7. Thompson Sampling

   1. Concentration-based Analysis
   2. Adversarial Analysis
   3. Exploration in Large Language Models
   HTMLPDF

   We study Thompson sampling, which uses randomization to balance explore-exploit tradeoffs in a Bayesian manner. We illustrate some surprising connections, including to the exponential weights algorithm. We discuss implications for exploration in large language models, which operate using random sampling.

8. Appendix

   HTMLPDF

Updates

This monograph is a work-in-progress, and is being written in public. The current version’s compile date can be found in the BibTeX entry below. The most recent major addition was the public launch, consisting of the introduction and Chapter 2. To receive updates when new content is added, please subscribe to the mailing list.

Contact

You can contact me via email or social media for feedback, questions, and suggestions. Please open a GitHub issue if you find any errors, whether related to the book’s technical content, or how it is rendered in any of the available formats.

Citation

To cite the book, please use the following BibTeX entry:

@book{terenin2026,
  title = {Bayesian Decision-making Algorithms},
  author = {Alexander Terenin},
  year = {2026},
  url = {https://bayesianalgorithms.com},
  note = {Working draft: compiled on 2026-09-01}
}

Code

Code is available in two GitHub repositories:

• Reference implementation for benchmarks: BayesianAlgorithms/benchmarks
• The website’s TeX-to-MD-to-HTML pipeline: BayesianAlgorithms/website