# Bayesian Decision-making Algorithms

> An in-progress book by Alexander Terenin on the mathematics of
> decision-making under uncertainty and explore-exploit tradeoffs,
> available online in HTML, PDF, and Markdown as it is written.

The BibTeX entry below gives the compilation date of the current version.

The Markdown uses Zola shortcodes as a light extension: constructs like
{% theorem(kind="definition", name="...") %} delimit theorem environments,
and math is written as TeX, inline in `$...$` and display in $$...$$ blocks.
Citation keys resolve in the BibTeX file at https://bayesianalgorithms.com/md/BDMA.bib.
Chapters marked under construction contain planned section headings only.

To report errors, whether in the book's technical content or in how it is
rendered in any of the available formats, please open a GitHub issue at
https://github.com/bayesianalgorithms/website/issues/, checking the
repository first for any further instructions.

© 2026 Alexander Terenin. All rights reserved. These apply only to the presentation and
other forms of expression, not to formal mathematical content, which by
its nature is not copyrightable.

To cite this book:
```
@book{terenin2026,
  title = {Bayesian Decision-making Algorithms},
  author = {Alexander Terenin},
  year = {2026},
  url = {https://bayesianalgorithms.com},
  note = {Working draft: compiled on 2026-08-23}
}
```

The links below are Markdown versions of each chapter.

## Chapters

- [Notation](https://bayesianalgorithms.com/md/0-notation.md)
- [Introduction](https://bayesianalgorithms.com/md/1-intro.md): 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.
- [Decision-making Under Uncertainty](https://bayesianalgorithms.com/md/2-decision.md): 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.
- [Expected Improvement](https://bayesianalgorithms.com/md/3-ei.md) (under construction): 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.
- [Gittins Indices](https://bayesianalgorithms.com/md/4-gittins.md) (under construction): 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.
- [Optimism](https://bayesianalgorithms.com/md/5-optimism.md) (under construction): 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<sup>\*</sup> search*, can be seen as instances of optimism.
- [Information-theoretic Algorithms](https://bayesianalgorithms.com/md/6-info.md) (under construction): 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*.
- [Thompson Sampling](https://bayesianalgorithms.com/md/7-ts.md) (under construction): 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.
- [Appendix](https://bayesianalgorithms.com/md/A-appendix.md) (under construction)


## Bibliography

- [BDMA.bib](https://bayesianalgorithms.com/md/BDMA.bib): BibTeX entries for every citation key used in the chapters

## Optional

- [Markdown edition, as a single file](https://bayesianalgorithms.com/llms-full.txt)
- [HTML edition](https://bayesianalgorithms.com/)
- [PDF edition](https://bayesianalgorithms.com/book.pdf)