2.1. Definitions and Basic Examples

We start with the most important definition in this book.

The idea behind this definition—whose non-episodic form, as well as naming, dates at least to Blackwell (1951, 1953)—is to formalize a decision-making process that proceeds over episodes, indexed by discrete time points $t\in\mathbb{N}$. Assuming for sake of introduction that we are considering the stochastic variant, this process takes place as follows:

1. At time $t$, a thinking robot,¹ called the learner, chooses an action $a_t\in A$.
2. The learner receives a reward $r(a_t)$, but does not observe this reward.
3. Instead, the learner observes the random feedback $\sigma_t \sim \sigma(r, a_t)$.

At the next time point $t+1$, the learner may then select a new, potentially random, action $a_{t+1}$, based on $\mathcal{R}$, as well as $a_1,..,a_t$ and $\sigma_1,..,\sigma_t$, for which we use the shorthand $a_{1:t}$, $\sigma_{1:t}$. Thus, the learner knows the reward class, the actions it chose, and the history of observations, but not the true reward function itself. In fact, it is precisely this lack of knowledge that formalizes the sense in which the learner is making decisions under uncertainty.

This defines the protocol according to which the learner interacts. It is not the most general form possible—in particular, it excludes adaptive adversaries that react to the learner’s actions, which we will consider in Chapter 7—but we believe it achieves a good balance between being general yet not-too-difficult to define. Let us now consider a set of examples, which will serve to make this otherwise-abstract concept significantly more concrete. We will start with the simplest one—the trivial case in which there is no uncertainty.

Here, the learner knows the reward function, as the function class is so small that one can infer the true reward—or analog thereof, in the non-stochastic variants—from the function class. Therefore, there is no uncertainty, and all the learner needs to do is solve the optimization problem$$a_t = \operatorname*{\arg\max}_{a\in A} r(a) \tag{2.1}$$which they are allowed to do because they possess sufficient information to infer $r\in\mathcal{R}$ from knowledge of $\mathcal{R}$ alone. By doing so, the learner can achieve the best possible reward irrespective of the structure of $\Sigma$ or $\sigma$, without the need to explore different actions or learn anything from the data they observe. A related form of triviality also occurs if $|A|=1$: without distinct actions, there is nothing to learn and no need for exploration. To see these phenomena, we consider the next example.

Here, we have implicitly associated the random function $\sigma : \Omega\times\mathcal{R}\times A\to\Sigma$, where $\Omega$ is a probability space, with its distribution, which we also denote by $\sigma : \mathcal{R}\times A\to\mathcal{M}_1(\Sigma)$, thus ensuring the definition makes sense. See Appendix A for more on the conventions needed to ensure this notation is unambiguous.

The name multi-armed bandit comes from a casino analogy: the idea is that the learner is presented with a collection of slot machines—known in old times as bandits for their tendency to rob casino patrons of their wealth. Each machine has a different reward distribution. At a given round, the learner may choose to play one of them—that is, to pull an arm—and observe the reward it produces. The learner’s aim, intuitively, is to maximize the total rewards they receive.

To do so, the learner must try different arms, and learn which ones perform best by trial and error. Neither the greedy strategy of picking the arm with the best empirical mean according to the history, nor the purely-exploratory strategy of playing arms uniformly at random, are good strategies—at least, according to performance criteria we will introduce shortly in the sequel. Instead, the learner must balance explore with exploit: they must keep trying different arms, but should do so less and less often as information accumulates.

This balance—between explore and exploit—is present in almost all episodic decision problems, but the precise character through which it shows up can differ significantly. Bandits are perhaps the most-important and best-studied problem class: their explore-exploit tradeoffs, and algorithms for balancing them, are well-understood. Indeed, it is often a good idea to first understand how a given setting works by considering its bandit analog, before examining it more generally: we will adopt this approach throughout this book.

There is absolutely nothing which stops us from defining bandits in substantially greater generality.

Here, the action space $A$ and reward function class $\mathcal{R}$ are allowed to be general. Moreover, it makes sense to consider stochastic, Bayesian, and adversarial variants—in the first and second case, often with Gaussian or sub-Gaussian noise—and in the third case, usually with $\varepsilon = 0$ deterministically, which the definition allows. Only the structure of the feedback function—namely, play an action, learn about that specific action—is assumed as part of the definition.

We can contrast bandits with an episodic decision problem with a simpler feedback structure, given as follows.

Here, unlike in a bandit, the learner observes a noisy version of the reward of all arms, not just the ones they played. This means the learner no longer has to explore—at least, as long as the problem variant in question is not adversarial. In Chapter 7, we will see that the adversarial variant of this problem—where, as before, one would typically consider $\varepsilon=0$ deterministically—is surprisingly rich, and provides a good idealized setting within which one can study randomized exploration from a fundamental point of view.

There are many possible episodic decision problems which sit in-between full feedback and bandit feedback—that is, ones where the learner observes the reward of the action they take, potentially up to noise, along with additional side information that the learner can benefit from. These are as follows.

This class is notable because significant work has gone into understanding its theoretical structure, and we know a fair bit about the fundamental quantities—called decision-estimation coefficients—that determine problem difficulty, in spite of its rather general character. We refer the interested reader to Foster and Rakhlin (2023), which provides a comprehensive treatment of these ideas.

Decision-making with structured observations is not the only such class: one can also say a surprising amount about problems where $A$, $\Sigma$, and $\mathcal{R}$ are finite.

The stochastic and Bayesian variants are also known as stochastic partial monitoring games and Bayesian partial monitoring games, respectively. This is somewhat of a misnomer, particularly for the Bayesian variant, which corresponds to a stochastic control problem rather than a bona-fide game with more than one player. This is one motivation behind our choice of the name episodic decision problem,² following Blackwell (1951, 1953), to describe the general case.

A remarkable fact about this problem class is that, in a sense we will soon precisely define, there are only four possible problem difficulties: trivially easy, bandit-like, harder-than-bandit, and impossible. This is in spite of the fact that—except for finiteness of $A$, $\Sigma$, and $\mathcal{R}$—the class is completely general! Comparatively less is known about algorithms for this problem class.

We now turn to examples of a different kind—namely, problems that capture the structure of numerical algorithms used for various purposes in the mathematical and computer sciences.

In this example, the learner’s aim is to minimize a convex function. They are allowed to evaluate it at every time point, and observe its pointwise value and gradient (in the subdifferential sense). Note that the term stochastic variant here is somewhat of a misnomer, as observations are noiseless. Note also that $\mathcal{R}$ includes all convex functions: one could modify this to include only $\alpha$-strongly-convex and $\beta$-smooth functions, if desired. Thus, we see that episodic decision problems include many forms of convex optimization as a special case.

This example should immediately evoke the level of generality that episodic decision problems capture: it is clear that there is nothing stopping one from similarly defining other kinds of optimization problems such as black-box global optimization, Lipschitz optimization, or more general kinds of numerical problems such as computation of Nash equilibria and related notions.

Among such problems, in this book, we will focus on the class of black-box optimization—where we note that black-box optimization problems can also be seen as bandits where $A = [0,1]^d$ and $\mathcal{R}$ consists of continuous functions with an additional prescribed degree of smoothness. There is one more problem class which is very much worthy of mention in our overview.

There are many possible variants on this definition. In this one, the idea is that, at each episode, we try out a new policy and observe a rollout under that policy. Our algorithmic aim is to find the optimal policy. This definition therefore formalizes policy learning by trial and error, given known dynamics. One can easily consider formulations where the dynamics are not known and must be learned, by including them in $\mathcal{R}$. Stochastic contextual bandits also constitute a variant: these have a time horizon of one, and a random initial state.

This shows that episodic decision-making is general-enough to include episodic Markov decision processes as a special case. As consequence, if we had a comprehensive understanding of how to construct strong algorithms in complete generality, this understanding would tell us how to construct sample-efficient reinforcement learning algorithms with the optimal degree of exploration. Thus, episodic decision-making provides a candidate paradigm for understanding exploration in the context of artificial intelligence.

By now, we hope the showcased examples have provided a concrete grounding to the abstract concept introduced as Definition 2.1. We also hope they have made a self-evident case for how many interesting phenomena throughout various technical disciplines can be viewed in a unified way using the introduced mathematical language. We encourage you—that is, the reader—to pick out a special case of particular interest to think about, as you continue.

This book, however, is about algorithms rather than problems, and so we will conclude our examples here. In particular, it is about algorithms that quantify uncertainty—which arises through knowledge of only the function class $\mathcal{R}$ rather than the true reward function $r$—through probabilistic models, with learning performed using Bayes’ Rule. To understand this, we proceed to understand what constitutes an algorithm, what kind of algorithms are Bayesian, and how to assess an algorithm’s performance.

2.2. Algorithms for Decision-making

We now define the notion of an algorithm, previously used informally during our survey of episodic decision problems. Let $\operatorname{Seq}(\cdot )$ be the space of finite-length sequences, defined over an underlying set.

Algorithms are also sometimes called policies or strategies, and we may use these terms interchangeably, unless this would become ambiguous in the given context. The simplest possible algorithm one should generally consider consists of playing actions uniformly at random, without any learning.

It is clear that random search will not be a strong algorithm for many problems, as it behaves in an anti-greedy, purely-exploratory fashion, and doesn’t learn anything from the data. We will shortly make this claim precise. At the same time, random search is often empirically stronger than one expects: in black-box optimization—especially if the objective’s domain is high-dimensional—experience has shown that it can take a surprising amount of work to construct algorithms which are stronger in practice.

In formulating an algorithm, recall that the learner is allowed to use the reward function class $\mathcal{R}$ and feedback function $\sigma$, but not the true reward $r$. We now take the first step to introducing the class of algorithms this book is named after. Let $\mathcal{M}_1(\cdot \mid\cdot )$ be the space of all conditional distributions—formally, the space of probability kernels—over a given pair of sets.

A Bayesian model describes a general way by which the learner quantifies uncertainty about the unknown quantity of interest—that is, in an episodic decision problem, the unknown reward function. In adversarial settings, we allow ourselves to also consider Bayesian models defined over sequences of reward functions—where each time step has its own prior, and its own likelihood—but omit this here to ease presentation.

Throughout this book, we assume that $A$, $\mathcal{R}$, and $\Sigma$ are regular enough to ensure that the necessary posterior distributions exist for all datasets, and defer mathematical questions of this kind to further study on a model-specific basis. In cases where the respective spaces are finite sets—or even (subsets of) $\mathbb{R}^d$—questions of existence tend to not be difficult. But, even more importantly, the mathematics behind them is essentially never of a decision-theoretic character. Thus, in doing so, we hand-wave in exactly the cases where this is safe to do.

By itself, a Bayesian model only describes how to learn. It does not describe what to do with what has been learned—how to use the obtained representation of the learner’s uncertainty to select future actions. This additional ingredient must be specified in order to obtain an actual algorithm.

Thus, the extra ingredient which is part of a Bayesian algorithm is a rule by which one transforms distributions over unknown reward functions into distributions over actual actions. This rule tells the learner how to translate what they know into what they do. We say a decision rule is deterministic if its image consists of Dirac measures. Additionally, we note that one can also consider time-varying Bayesian algorithms, but omit this here to ease notation.

It is extremely important to note that Bayesian algorithms can be used on non-Bayesian problems—so much so that we will state it with emphasis:

Thus, throughout this book, we will find ourselves thinking about Bayesian algorithms for non-Bayesian problems—this will constitute a form of model-mismatch, meaning that the model differs from reality. We will return to this concept in the sequel, once we have developed an understanding of how to evaluate models under different forms of reality. The vast majority of Bayesian algorithms in current use come from the following class.

Algorithms based on acquisition functions, therefore, are those for which the Bayesian model’s posterior distribution $p_{r \mid a_{1:t},\sigma_{1:t}}$ is used to form a function $\alpha_t$ which ranks the actions according to which is the most-promising. The algorithm proceeds by choosing the highest-ranking action. We allow for both deterministic and randomized tie-breaking rules, but suppress them from notation unless their role is critical to the situation at hand. Every Bayesian algorithm class considered in this book will turn out to have the presented form.

2.3. Evaluating Performance via Regret

Having formalized the notion of a decision-making algorithm, and introduced the class of algorithms we will study, we now turn to the question of what it means for an algorithm to perform well, starting from the stochastic variant where there is a single ground-truth reward function $r$.

Regret, therefore, is the difference between how well the algorithm actually did, and how well it could have done if it knew what the ground-truth reward actually was. It is always non-negative, and minimizing regret is equivalent to maximizing rewards. Our rewards are assumed non-stochastic: in situations where stochastic rewards are of central interest, this definition is sometimes called pseudo-regret. We choose this notation in particular to emphasize that it depends critically on three key quantities:

1. The learner’s strategy $p$.
2. The true reward function $r$.
3. The time horizon $T$.

This book’s central questions will focus on how to construct strong algorithms. In most cases, we will take this to mean algorithms that perform well no matter what the true reward function actually is, as long as it is contained in the reward function class $\mathcal{R}$. Ideally, we will want this to hold for any time horizon—but it will be interesting to study how behavior should change according to different horizons. This will allow us, for example, to make precise the intuitive idea that, if one has more time to learn, they should explore more.

The above notion of regret is formulated in expectation. It is also possible to study random regret—that is, the random variable inside the expectation above. In doing so, it is typical to consider high-probability behavior: this can be used, for instance, to show that an algorithm works well with probability $1-\varepsilon$, not just on average. The remaining $\varepsilon$-probability might correspond to extremely rare cases—for instance, hopeless situations where a large set of Gaussian draws are all simultaneously positive, and the data is completely misleading.

The notion presented above is sometimes called cumulative regret, since it counts all rewards at all time points. This is not the only reasonable choice: one can just as well restrict attention to the reward obtained at the final time point.

Compared to cumulative regret, this notion effectively disregards the suboptimality of the points the algorithm chooses to explore. We will see that its overall behavior is similar—but, for a given algorithm class, it can be much more convenient to work with either simple regret, or cumulative regret, depending on the situation.

Both of the preceding notions are finite-horizon notions, in the sense that they are defined for a given $T\in\mathbb{N}$. It can be just as natural to instead work with an infinite-horizon discounted formulation, as follows.

One advantage of a discounted formulation is that it is stationary with respect to time. On the other hand, a disadvantage is that discount factors can be slightly less intuitive to think about than time horizons. One way to reconcile this is to view discounting as finite-horizon with a fixed termination probability, and consider regret in expectation. Note that, for bounded rewards—concretely, those with $|r|\leq 1$—discounted cumulative rewards are uniformly bounded by$$\sum_{t=1}^\infty \gamma^{t-1} r(a_t) \leq \frac{1}{1-\gamma} . \tag{2.8}$$This is related to the finite-horizon bound$$\sum_{t=1}^T r(a_t) \leq T . \tag{2.9}$$A clean way, therefore, to think about discounting is that it gives rise to an effective time horizon$$T_\gamma = \frac{1}{1-\gamma} \tag{2.10}$$arising from the geometric series formula. For almost all of this book, we will work with undiscounted formulations, but it is not difficult to develop discounted analogs of the ideas presented.

A second way to introduce stationarity with respect to time is to allow the algorithm to choose $T$. To facilitate non-trivial behavior, we introduce a strictly positive cost function $c : A \to \mathbb{R}$. We can then define the following notion.

For this to be well-defined, together with actions, the algorithm must also output a binary variable which determines whether to continue to the next episode, or to stop: we refer to this as the stopping policy, and to the actual action $a_t$ as the steering policy, in contexts where the distinction applies. We require the stopping policy to be defined with respect to the same history of observations as the steering policy, and implicitly extend the notion of a Bayesian algorithm to also cover this case. This formulation is called the cost-per-sample problem.

These notions can be extended to allow for a cost function class $\mathcal{C}$ which plays a similar role to $\mathcal{R}$—here, we work with a fixed cost function to ease notation. We use simple rather than cumulative regret to ensure stopping immediately is not optimal, but other formulations are also possible. In general, one can mix-and-match the definitions of this chapter as needed, in essentially all cases where it makes sense to do so. We now turn to regret for non-stochastic variants.

Thus, Bayesian regret is simply regret averaged over the reward functions sampled from the reward distribution $q$. For a Bayesian algorithm $p$, if the prior $p_r$ matches the true reward distribution $q$, and the likelihood $p_{s\mid r,a}$ matches the distribution induced by the feedback function $\sigma$, we say that we are in the model-matched setting. Otherwise, we say there is model mismatch: the Bayesian model’s assumptions differ from the exact nature of ground-truth reality. Both settings lead to a rich and interesting theory, each with their own specifics.

We have used the term Bayesian to refer to several distinct concepts: (i) episodic decision problems of the Bayesian variant, (ii) Bayesian algorithms for general episodic decision problems, and (iii) the above notion of Bayesian regret. When the first and third concepts are combined, something very special happens: the formulation gives rise to a Markov decision process.

Here, states correspond to the data gathered so far by the algorithm. In turn, algorithms for the episodic decision problem are equivalent to policies for its underlying Markov decision process. Moreover, the value function is equivalent to Bayesian regret up to a negation and constant shift, meaning$$V^{(p)}_{\operatorname{MDP}}(s_0) = C - R_T(p,q) \tag{2.13}$$where $C = \operatorname*{\mathbb{E}}_{r\sim q} \sup_{a\in A} \sum_{t=1}^T r(a)$ depends only on $q$ and not on $p$, and is viewed as a prior-dependent constant. This statement extends from the initial state $s_0$ to general states $s$, as long as the Bayesian regret term is understood to be conditioned on the corresponding history: in doing so, $C$ continues to be a constant, in the sense that it depends on $s$ but not on $p$.

This correspondence—between episodic decision problems and Markov decision processes—is unique to the Bayesian setting. It has significant consequences, including the existence of an optimal value function $V^*_{\operatorname{MDP}}$, and an optimal policy whose respective algorithm we call the Bayesian-optimal algorithm. Other kinds of episodic decision problems correspond to families of Markov decision processes with different reward functions. This technical difference should not be understated, and its themes will recur throughout this book’s chapters.

One rather powerful consequence of having a Markov decision process formalism is that it allows us to check whether basic properties that one would intuitively expect to hold are actually true—if they were not, it would be evidence our definitions were poorly chosen. For instance, consider two episodic decision problems which are identical except for the feedback functions $\sigma_1$ and $\sigma_2$, where the latter is strictly more noisy—meaning, for example, that given the same history and actions the observed feedback satisfies$$\sigma_t^{(2)} = \sigma_t^{(1)} + \varepsilon \tag{2.14}$$in distribution, where $\varepsilon\sim\operatorname{N}(0,1)$. Then, we would expect learning to be more difficult, and the Bayesian-optimal algorithm to achieve less reward in expectation under $\sigma_2$. One would expect the same if $\sigma_1$ represents full feedback, and $\sigma_2$ represents bandit feedback, both with the same noise distribution for each action. Not only are these comparisons true—but, when reformulated in a general rather than specific manner, the implication actually goes in both directions.

To see this, we will need a little bit of setup, because it does not suffice to directly compare $\sigma_1$ with $\sigma_2$. Instead, we need to associate each with the class of all other analogous feedback functions $\sigma'_1$ and $\sigma'_2$ which, in some sense, carry the same information—including ones that occur under different episodic decision problems. Defining what it means to be analogous is tricky, because a given feedback function $\sigma : \mathcal{R}\times A\to\mathcal{M}_1(\Sigma)$ includes $\mathcal{R}$ in its definition.

To handle this, the rough idea is to start with $\sigma$, and replace each reward $r\in\mathcal{R}$ by some $r'\in\mathcal{R}'$: this completely changes the rewards, but preserves feedback structure, since the rest of $\sigma$ is kept the same. These rewards $r'$ can potentially include new actions $a'\notin A$, as long as they are assumed to be non-informative.

We will also need a suitable notion of what it means to add noise. For a probability kernel $g\in\mathcal{M}_1(\Sigma\mid\Sigma\times A)$, define its action on measures $\mu\in\mathcal{M}_1(\Sigma)$ by integration in the standard manner, namely $g(\mu,a) = \int_\Sigma g(\cdot \mid s, a) \mathop{}\!\mathrm{d}\mu(s) \in \mathcal{M}_1(\Sigma)$ for all $a\in A$. This generalizes the previously-seen example of adding Gaussian noise, by allowing the noise distribution to be arbitrary and action-dependent.

We will also consider a third way to compare feedback functions. For an episodic decision problem and an algorithm $p$, define $\lambda_p$ to be the function that maps rewards $r$ to the distribution of actions played during a rollout—with actions generated in the environment where $r$ is ground-truth. Using this, define the set of all feasible action-sequence distributions $\Lambda = \{\lambda_p : \mathcal{R}\to\mathcal{M}_1(\operatorname{Seq}(A)) : p\in\mathcal{P}\}$. Observe that this set differs for different $\sigma$: the more feedback is given, the more ways an algorithm can change its behavior using that feedback.

With these concepts at hand, we are finally ready to state the key result.

This result tells us that there are three ways of thinking about informativeness of feedback functions: (1) with more information, Bayesian-optimal algorithms achieve more reward in expectation, (2) more-informative feedback functions contain less noise, and (3) under a more-informative feedback function, algorithms can choose a wider range of possible distributions over actions. We view the fact that all three are actually equivalent as a strong piece of evidence that our definitions are the right ones and lead to a rich mathematical theory.

We defer the proof to Section 2.7, noting briefly that: (a) quantifying over families of episodic decision problems is necessary for equivalence as opposed to implication in one direction, (b) finiteness is not essential, and is assumed only to focus attention on decision-theoretic rather than regularity aspects, and (c) there are extensions of this result to other settings, beyond our model-matched Bayesian setting, for example through the concept of Le Cam deficiency—see Le Cam (1986, Ch. 2, Sec. 3, Theorem 2) for a non-sequential variant.

We now briefly examine adversarial problems. Here, there is a major subtlety that one must wrangle with: we do not have a single ground-truth reward, not even a randomly-sampled one. In all cases before, we compared ourselves with the optimal point, but for a sequence there is no single optimal point. What should one compare themselves to? The idea will be to introduce a single action $a$ with respect to which to compare the algorithm’s performance.

In particular, the regret against the best action in hindsight is defined as$$R_T(p, r_1,..,r_T) = \operatorname*{\mathbb{E}}_{a_t\sim p} \sup_{a\in A} \sum_{t=1}^T r_t(a) - r_t(a_t) \tag{2.16}$$where we emphasize that we are comparing $\sum_{t=1}^T r_t(a_t)$ with the supremum of the sum, and not the sum of suprema over individual functions.

Why this notion in particular? At first, it may look rather idiosyncratic. On the face, it is not obvious whether it ought to exhibit any kind of interesting behavior. It will turn out that the seemingly-more-obvious notion, involving the aforementioned sum of suprema, is an impossibly difficult benchmark and does not give rise to non-trivial algorithms. On the other hand, the above notion, as we will see in Chapter 7, does: it will turn out to provide a natural setting for studying exploration by random actions.

More generally, one can think beyond comparator points, and also consider comparator sequences with various constraints, as well as even-more-general notions. For some of these, note that regret can be negative. As these notions are more advanced, we defer them for the moment: the critical thing to understand, for now, is simply that comparing an algorithm’s performance with strategies that are not necessarily optimal is possible, and is often a very useful way to benchmark performance or facilitate understanding.

To conclude our overview of regret, we will now state the book’s first set of actual results, which will not be difficult: we will study the regret of random search, as well as the obviously-bad algorithm that picks some arbitrary point over and over again. This might seem like a rather dry exercise, but it is worth doing, because certain details carry implications for benchmarking and are therefore worth drawing attention to.

We have noted that random search is almost never a strong algorithm: it ignores the data, does not attempt to balance tradeoffs between explore and exploit, and instead only explores. Nonetheless, its performance should be compared to an even-worse algorithm: one that picks some arbitrary point over and over again. Let us show how to carry this comparison out—under finite actions and bounded rewards, for concreteness.

This seemingly-trivial pair of calculations already shows that random search can be much better than picking some arbitrary action. While both methods achieve $\Theta(T)$ regret, for random search, the constant factor hidden in the $\Theta$-notation is exactly the gap between the best action and the average action with respect to the uniform distribution. This is usually smaller than the worst possible regret, and for this reason random search can be a good initial baseline to benchmark for problems where it is otherwise not clear what to do.

Intuitively, one might expect that learning is necessary in order to achieve good performance on an episodic decision problem. One can therefore ask: by itself, does it suffice? Arguably the simplest possible decision rule which actually uses a Bayesian model in its construction is that of maximizing (posterior) expected value, which is defined up to an arbitrary tie-breaking rule as$$a_t = \operatorname*{\arg\max}_{a\in A} \operatorname*{\mathbb{E}}(r(a) \mid a_{1:t-1}, \sigma_{1:t-1}) . \tag{2.24}$$Let us see how this performs on a simple non-trivial example.

The proof, given in Section 2.7, works by constructing a constant-probability unlucky event which causes the algorithm to never try the optimal action more than once. It is not difficult to construct similar failures for other problems, or for other models—indeed, an analogous result even holds for Bayesian regret in the model-matched setting! This suggests that the issue is fundamental: in sufficiently non-trivial situations, maximizing expected value simply does not produce sufficient exploration, and can be just as bad as learning nothing.

If maximizing posterior expected value doesn’t work, what alternatives do? This question turns out to be mathematically rich, and it will take the whole of this book for us to develop an incomplete but reasonably-comprehensive sense for what is possible. We will see that several approaches, including ones with exploration mechanisms of very different-looking character, can work. To get there, we first need to understand a bit more about episodic decision problems, by developing a sense for what levels of performance are possible.

2.4. Problem Difficulty and Lower Bounds

We have now explored a wide set of notions of regret, which provide a metric by which to evaluate the performance of a particular decision-making algorithm on a particular instance of an episodic decision problem. In order to be able to determine whether an algorithm is performing well, we need to be able to assess the difficulty of a given problem. We therefore study how to do that.

For a given notion of regret, the difficulty of an episodic decision problem depends chiefly on three factors:

1. The function class $\mathcal{R}$.
2. The feedback function $\sigma$.
3. The time horizon $T$.

In particular, the structure of the action space $A$ is encoded in the definition of $\mathcal{R}$, and the structure of the observation space $\Sigma$ is encoded in the definition of $\sigma$. Thus, this list covers all components of Definition 2.1, along with the key hyperparameter arising from the regret’s definition itself. As a rule, we generally do not consider dependence on the true reward function $r$, nor on the actual sample $r\sim q$ in the event that it is random. Instead, the way we handle this part of the definition differs according to the problem variant:

1. In the stochastic variant, we consider the worst case $r\in\mathcal{R}$.
2. In the Bayesian variant, we consider the average case $r\sim q$.

Other variants are handled analogously: for instance, in adversarial variants, we might consider worst-case fixed reward sequences, or worst-case reward sequences generated adaptively by an adversary based on the same information available to the learner. This perspective does not preclude one from studying dependence on a particular reward function instance $r\in\mathcal{R}$, but instead asks one to encode the relevant properties of the instance in the definition of the function class $\mathcal{R}$. We will soon see an example that illustrates this.

We are now ready to cast the intuitive description above into a formal definition. The final ingredient we need to consider is some parameter that we can change in order to make the problem easier or harder, so that different problems become comparable to one another quantitatively. This could be the time horizon $T$, or for instance the size of the action space $|A|$. We will call the set of these variables $V$.

This means the difficulty is defined according to the best performance achievable by any algorithm, assuming it plays against the worst-case function within the given function class. We assume throughout that the episodic decision problem is regular enough for this value to be well-defined. The difficulty of a Bayesian variant is defined similarly, but where we do not consider worst-case performance, and replace it with average-case performance with respect to the reward function’s distribution.

This definition coincides with the optimal value function of the problem’s underlying Markov decision process up to constants, as seen previously. Thus, we can now reinterpret Theorem 2.23 as characterizing the manner in which less-informative feedback functions lead to more-difficult problems.

An important part of both of these definitions is that we focus our attention on the rate, which describes how difficulty varies with the family’s parameters. In particular, we can consider how the rate varies with the time horizon $T$, or with parameters such as the size of the action space $|A|$, assuming we are considering a finite-action problem. This notion of difficulty therefore mirrors perspectives commonly found in complexity theory and theoretical computer science.

To aid understanding, we now briefly state the rate of the two most basic examples considered previously—the latter, under two different reward function classes. We will omit various restrictions on the variables to ease notation, and will defer proofs of the necessary statements to later.

This illustrates how both the reward function class and the feedback function can affect an episodic decision problem’s difficulty. We choose these three examples because the arguments involved are sufficiently simple that it is reasonable to present them as part of an introductory chapter—we will do so once a little bit more of the necessary machinery is established.

At this stage, it is reasonable to ask: what is gained by studying rates, rather than one episodic decision problem by itself? Why not just compute the saddle point arising in the minimax regret, and look at the resulting algorithm? If this were feasible, it would be fantastic—but, unfortunately, there are only a few problems where computing this quantity, or its analog for other variants, is possible. Working with rates gives us the freedom to study a much larger class of possible algorithms, many of which will turn out to be interesting.

Focusing on the rate means that, to compute the difficulty of an episodic decision problem, it suffices to compute a sufficiently-sharp regret lower bound$$C \leq R_T(p,r) \tag{2.29}$$in the sense that for any algorithm $p$ there is a reward $r$ for which the inequality holds. For the given algorithm-specific reward, we automatically have$$C \leq R_T(p,r) \leq \sup_{r\in\mathcal{R}} R_T(p,r) , \quad \forall p\in\mathcal{P} \tag{2.30}$$and since the statement is universally quantified over $p$, it is equivalent to$$C \leq \inf_{p\in\mathcal{P}} \sup_{r\in\mathcal{R}} R_T(p,r) . \tag{2.31}$$If the lower bound is sharp up to constants, the specific form of $C$ therefore reveals the correct rate. Thus, by itself, a lower bound shows a problem to be at least of a certain difficulty. Showing it to be exactly a given difficulty requires one to have a matching upper bound or some other way to attest sharpness.

So, how does one actually obtain lower bounds? We need to prove that, for any algorithm $p$, there is some kind of difficult reward function. As we will see in this book, there are many algorithms one can consider—ones whose principles look sufficiently different from one another. From this viewpoint, finding a universal construction for difficult reward functions may seem daunting. We will bypass this challenge rather than solving it directly, through a fundamental idea which recurs in many different guises throughout computer science.

The key idea is to not look for a family of difficult reward functions directly, but to instead look for a hard distribution $q\in\mathcal{M}_1(\mathcal{R})$ over reward functions. Such a distribution should certify a regret lower bound in expectation. The key observation is that the existence of such a distribution implies the existence of a difficult reward function which certifies the required regret lower bound.

We can therefore pass from working with deterministic reward functions to working with randomized ones, and study what properties the corresponding distributions need to have. Naturally, these properties must be studied in full detail case-by-case. But there is a central principle to how they operate. Let us illustrate a special case of it through the following observation.

For reward distributions $q$ with this property, no matter what an algorithm does, the conditional expected rewards of each action remain the same. There is nothing an algorithm can learn, it may as well play at random. Non-constant reward distributions with this property are rarely available: for most episodic decision problems, it is possible for the learner to learn at least something about the randomly-drawn rewards, even if they are zero in expectation. One important exception is the adversarial full feedback setting.

In presenting these results, we defer proofs to Section 2.7. The key reason for this is they represent a jump in difficulty—not a large one, but enough that we would rather focus attention on showcasing what is known, before seeing how.

Constructions of this kind are fundamental in adversarial online learning, including generalizations where the action space $A$ has a richer structure. If the adversary is playing random noise at every iteration, the learner has no hope of finding the best point, so their performance will be controlled by the typical gap between the best point and an average point. The bound follows by quantifying this gap using standard tools developed for analyzing expected suprema of random processes, here the sum of rewards over time.

In non-adversarial settings with a sufficiently-rich feedback function $\sigma$, we cannot expect to find an equalizing reward distribution. The problem is that $r\sim q$ is sampled once at the beginning, which means it will be possible for the algorithm to learn at least something from the data. But, we can instead find a nearly-equalizing distribution, and try to quantify how much it was possible to learn. This leads to the following general principle for deriving lower bounds:

This idea can be made precise in many distinct ways, and the guise through which it shows up in a given context can vary significantly depending on its details. As a result, we will develop this idea through presenting it in a number of relatively simple cases—though, in doing so, will try to cast as much emphasis on the broader picture as we can. We start with the setting that mirrors the preceding one—namely, stochastic online learning.

The hard distribution is constructed using random spike rewards that are all-zero, except for one special action whose reward is $\Delta$, where the optimal action is chosen uniformly at random. The rewards at each point are the same in expectation at the beginning, and the observations are nearly the same: the reward of the best action differs only a small amount, namely $\Delta$, and this is hard to separate from variability. In this sense, this reward distribution is nearly-equalizing.

The proof operates by introducing and considering information-theoretic quantities such as Kullback–Leibler divergences and mutual informations, and rests on an explicit calculation for how different the observations would have looked if two different arms were optimal—this is how $\Delta$ makes an appearance. There are many possible variations on the argument, some of which may avoid restrictions on $N$ and $T$ at cost of being more tricky. We used rewards in $[0,1]$, rather than $[-1,1]$ as before, to simplify algebra.

It turns out that the exact same reward distribution $q$ is also the hard instance for stochastic bandits, with a proof that is similar in spirit, but slightly different in terms of its technical details.

For bandits, the argument presented in this chapter goes through Pinsker’s inequality, whereas for online learning, it went through Fano’s inequality. For more details on these and other technical aspects, see the proofs in Section 2.7.

We now turn to the final example we will work out in detail: stochastic bandits, but where the reward function class only includes functions with some gap $\Delta>0$. The most important aspect we will see is that this changes the rate.

This reveals that, if our lower bounds are tight, then multi-armed bandits with rewards that have a gap of at least $\Delta$ are an easier problem class than those which do not have a gap. Thus, the function class $\mathcal{R}$ plays a critical role in controlling problem difficulty. We will later see, by way of algorithms developed in Chapter 5, that they are indeed tight. The proof here is essentially the same as that of the preceding result, except that the gap is now specified rather than tuned, and minor modifications are made for sharpness.

This concludes our presentation of lower bounds—specifically those for which we will prove the respective claims. There are as many lower bound arguments in the literature as there are variations of episodic decision problems and related mathematical constructions, many with a rich and intricate structure. There is, however, one more result which we believe deserves presentation, because of how surprising it is.

We will not formally define what is meant by global and local observability, other than to say that these notions formalize the essence of the question: must the learner play strictly-suboptimal actions in order to learn what the optimal action is? If not, the game is locally observable. If yes, the game is globally but not locally observable. The other two possibilities are corner cases which handle situations where the optimal action can be inferred without needing to look at data, or ones where it cannot be learned, even in principle.

This result should be seen as a major achievement of the theory of partial monitoring games, and is remarkable because of how simple it is. Its main limitation is that it only offers a classification with respect to time, not the number of actions, or properties of the reward function class $\mathcal{R}$. Nonetheless, we view it as a key mathematical hint that studying episodic decision-making at our level of generality is not hopeless—a hint that suggests a relatively universal understanding ought to be possible.

2.5. Empirical Benchmarking

The preceding sections introduced the notion of an episodic decision problem, and defined algorithms for such problems, including the class of Bayesian algorithms that will be our main focus. We introduced notions of regret that can be used to distinguish between algorithms that perform well and ones that perform poorly, along with notions of difficulty through regret lower bounds that allow us to know what is possible. All of these notions were mathematical in character.

In Chapter 1, we noted that our focus throughout this book will be on definitions, and not on proofs and analysis techniques. This choice is not made by accident. There are at least two completely different ways that one can conclude a decision-making algorithm is strong:

1. Prove a theoretical guarantee on its regret, ideally in the form of a sharp upper bound in the setting of interest.
2. Implement and test the algorithm on a comprehensive suite of benchmarks, and check that it performs well in practice.

Our perspective will be to take both approaches seriously, as each one has different strength and weaknesses, and thereby helps us see different parts of the overall picture. These include:

• Scope. Mathematical guarantees are rigid: they hold exactly as stated. The degree to which a guarantee in one situation generalizes to another situation, in the absence of a proof, is a matter of speculation and personal judgment. The same is true of performance on a set of benchmarks.
• Realism. Performance guarantees are only possible for settings which are simple enough that mathematical tools can say something non-trivial about them. In contrast, benchmarks can be performed on arbitrarily-complex and realistic problems, so long as running them is practical.
• Comprehensiveness. A regret lower bound can reveal what degrees of performance are outright impossible. In contrast, if no algorithm performs well on a benchmark, it is not obvious whether this is because the problem is impossible, or because the known algorithms are not good enough.
• Accessibility. A theoretical result requires a certain degree of mathematical literacy in order to interpret. Benchmarks, in contrast, require one to be able to distinguish good experimental practices from poor ones. Both require a non-trivial degree of skill, but the skills themselves differ.
• Reproducibility. A correct theorem is by definition perfectly reproducible. In contrast, benchmarks have hyperparameters and implementation details, and are typically randomized. It is possible for these factors to influence performance as much as the benchmark or algorithm itself does.

These differences are by no means complete, and we refer the reader to Hardt (2026) for a systematic introduction to machine learning benchmarking, as well as an overview of the properties a well-designed benchmark suite should have.

2.5.1. Best Practices and Implementation Details for Bayesian Optimization

We now discuss several decision-making-specific best practices. These help ensure that an empirical benchmark suite provides useful information about an algorithm’s performance. Where possible, we will relate each best practice back to the theory seen so far, in order to contextualize it and justify the need to use it from first principles.

Bayesian optimization refers to the use of Bayesian algorithms to solve black-box optimization problems and generalizations thereof. Garnett (2023) provide a comprehensive treatment of such algorithms, along with the models they are most commonly used with. We start with our most basic recommendation.

Random search baseline. One should always compare how an algorithm performs to an implementation of random search. One would expect any reasonable algorithm to be stronger than random search, and verifying that this occurs can be seen as the most basic test a good algorithm should pass. The justification for this principle is that, from a theoretical perspective, random search provides an upper bound on a problem’s difficulty.

An algorithm can fail to outperform random search for at least four distinct reasons. First, there might be a bug in the implementation. Second, the problem might be impossible, in which case random search might be near-optimal. Third, the algorithm’s hyperparameters might be poorly-tuned. Fourth, the algorithm might be a weak algorithm for the given setting.

To distinguish between these, one can examine the actions that an algorithm picks. In a reasonable problem, a good algorithm should typically pick points which balance expected performance with uncertainty. In addition, selected actions’ posterior uncertainty should be neither zero nor maximal. One can compute and display appropriate quantities, such as posterior means and standard deviations, to evaluate whether this happens. If it does not, it can be an indication of a poorly-chosen model or poor tuning.

As a second, closely-related baseline, it can be worthwhile to consider max-variance search: this algorithm chooses the point of highest uncertainty at each iteration. Similar to random search, if this algorithm is strong, it gives an indication that the episodic decision problem under study is not particularly rich.

In spite of how basic these comparisons are, and how easy they are to carry out, our experience is that they are not always performed—even in published research. It is also our experience that outperforming random search in relatively sophisticated practical settings, for instance those with a sufficiently high-dimensional action space, is often much harder than one would expect.

Problem randomization. To the extent it makes sense, in light of computational costs and other concerns, a benchmark should be randomized: this ensures an algorithm cannot perform well purely because it prefers certain actions, independent of any learning. Concretely, in global optimization, algorithms that tend to pick points near zero, no matter what happens, will perform better on objective functions whose optimum is at zero. This can be counteracted by randomizing the location of the optimum.

The principle here is that a benchmark should define a non-trivial episodic decision problem: its function class should not be a singleton. If one considers average-case performance, randomization corresponds to the Bayesian episodic decision problem variant. It can also be used to approximate performance of a stochastic variant, where the function class $\mathcal{R}$ is defined by the distribution’s support: to do this, one should not average, but instead compute worst-case performance over all random samples.

Model evaluation. A Bayesian decision-making algorithm involves multiple moving parts: the Bayesian model, its numerical implementation, and the decision rule built on top of the model. We recommend evaluating these by assessing the model’s performance first: if a model is not working well, there is no reason to expect a decision-making algorithm built on top of it to work well.

In particular, a Bayesian model’s performance can be assessed by considering how accurate its predictions are on a held-out test set. Moreover, a model’s marginal likelihood, if it can be computed, directly indicates how typical or atypical a model views the data it has seen, which in turn provides a sense of how well the model expects itself to perform. For more about Bayesian model evaluation in Gaussian process models, which are the most-common models used in Bayesian optimization, see Rasmussen and Williams (2006).

Normalization. A given algorithm for an episodic decision problem can either be implemented directly according to its equations, or with normalization, defined as follows. At each time point, we compute the normalized observations$$\sigma_{1:t}^{(\operatorname{std})} = \frac{\sigma_{1:t} - \operatorname{mean}(\sigma_{1:t})}{\operatorname{std}(\sigma_{1:t})} \tag{2.47}$$and provide these to the model instead of the original observations, where we have assumed that computing means and standard deviations actually makes sense in the given setting. Note that the rescaling this gives is time-dependent.

By changing the behavior of a Bayesian model, normalization will change how an algorithm explores, and will generally do so in a non-obvious manner. We are not aware of any general theoretical study of its behavior. Nonetheless, there is strong empirical evidence that using it often significantly improves performance and reliability in practice, and as a result it is usually enabled by default in practical black-box optimization packages.

It is difficult to speculate whether these observations are due to better algorithmic behavior, or due to better-behaved models or other aspects of problem formulation. When benchmarking an algorithm, we therefore recommend trying it both with and without normalization, and reporting both results.

Numerical stability. Almost all Bayesian models require computational methods in order to actually obtain their posterior distribution in practice. These can involve everything from numerical linear algebra, for instance to solve linear systems arising in Gaussian process models, to optimization and sampling algorithms. For each numerical algorithm used, one should consider carefully whether its behavior will change significantly if implemented in 64-bit floating point arithmetic instead of 32-bit arithmetic.

For an introduction to these considerations, we refer the reader to Higham (1996). At the same time, there are enough algorithms one might use under-the-hood for Bayesian computation, that no single treatment can hope to cover all that one might encounter—especially new or recently-popularized algorithms. Thus, we omit further details. In practice, one should expect to need to think about the situation at hand, at least a little bit, in every case individually.

There is, however, one very useful fact about floating-point arithmetic that one can use to improve numerical stability of many implementations: there are about as many floating-point numbers in the interval $[0,1)$ as in $[1,\infty)$. Thus, where choices are possible, it is often a good idea to standardize the numerical representation of actions and other variables to ensure they live near the origin.

Acquisition function optimization. In practice, for algorithms based on acquisition functions—as all algorithms considered in this book are—one needs to solve their respective optimization problems numerically. These optimization problems are essentially-never convex. The standard approach for solving them is to apply multi-start gradient-based optimization: one picks a set of random initial points, runs an optimization algorithm on each point in parallel, and picks the best achieved value.

In practice, both stochastic optimization methods such as Adam, and more classical quasi-Newton methods such as L-BFGS, are commonly used—the latter only for purely-deterministic acquisition functions which do not involve random sampling in their computations, where its use actually makes sense. For such algorithms, we recommend trying both approaches, comparing performance, and choosing whatever method is strongest in practice.

Evaluation with and without model mismatch. We recommend that Bayesian algorithms are evaluated both with and without model-mismatch, to quantify the effect that it has on performance. The principle here is that good algorithms should be general: their performance should not be fundamentally tied to the reward function class or distribution.

To evaluate a model without model-mismatch, one can randomly sample reward functions from it. In some model classes, this may require appropriate approximations, which are safe to make as long as the error they induce is comparable to other sources of errors in the total setup.

To evaluate a model under model-mismatch, one can benchmark it against reward functions from a standard benchmark suite. We discuss this in more detail next. For now, though, we emphasize that performance under model-mismatch can change in model-specific ways, and can also be affected by numerical implementation aspects, such as training algorithm convergence.

Use of both synthetic and empirical benchmarks. When evaluating an algorithm on a benchmark suite of reward functions, we recommend using a combination of both synthetic benchmark functions, and those constructed to resemble real-world problems. The implied reward function classes that such examples come from can be significantly different from one another. As a result, understanding how performance differs in both cases can provide information about an algorithm’s overall reliability.

Use of both community-standard and original benchmarks. Finally, when evaluating an algorithm’s performance, we recommend considering both standard benchmarks widely used in the literature, such as the well-known Ackley and Rosenbrock functions, and bespoke benchmarks which are different from those considered by others. A good algorithm should perform similarly in both cases, and should avoid overfitting to the specific instances the community has collectively decided to test most algorithms on.

2.5.2. Benchmarking Bayesian Optimization

To conclude this section, we present a simple comparison of each of the decision-making algorithms studied in this book’s chapters, using a from-scratch implementation written in a manner that aims to be long-term reproducible. In doing so, our goal is to provide a simple snapshot of how well the methods studied in today’s era actually work. We describe our benchmark suite and full experimental details in Appendix B.

🚧 Under construction. 🚧

2.6. Exercises

The exercises in this book will be of a somewhat non-standard character: they are not intended to be attempted in isolation by the reader, but are instead designed for cooperative use with an AI assistant. Thus, they are somewhat less precisely specified than typical mathematical exercises. The intention is that, in working together with the AI system to complete them, you apply an appropriate degree of effort to engage deeply with the material, thinking carefully about what is going on.

Some of our exercises will focus on constructing definitions and exploring their properties. When working through these, you should instruct the AI to never reveal an exercise’s answer to you—instead, when tempted to do so, it should ask you a carefully-chosen guiding question in response. Thinking about this question should help you realize what you need to do to make progress towards the answer. You should allow the AI to perform calculations for you, but should also rely solely on your own thinking to tell it what calculations to perform.

Other exercises will require you to implement a minimal software package to put the definitions into practice. The purpose here is to learn how the mathematical ideas map onto software, and gain command over all of the details involved in such an implementation. You should take a central role in designing your package’s structure, abstractions, and interface, and think carefully about how to make them as clean as possible. You should hand over low-level numerical details to AI, and then verify that they are implemented correctly.

2.7. Deferred Proofs