Contents

1. Preface

   PDF

2. Notation

   PDF

1. Introduction

   PDF

   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

   PDF

   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

   PDF

   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

   PDF

   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

   PDF

   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

   PDF

   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

   PDF

   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

   PDF

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-08-23}
}

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