Regret, Bandits, and Guarantees

Chapter 12 left us with a shelf of acquisition functions, each a reasonable answer to the question of where to evaluate next. Choosing among them, or proposing a new one, needs a way to say that one optimizer is better than another. The everyday answer is a benchmark plot: the best value found against the number of evaluations, on a handful of test functions. Later chapters use such plots. This chapter asks for something sturdier: a score that is defined for every problem, and statements about that score that hold for every problem in a stated class.

The score is called regret, and its theory grew up around a problem simpler than Bayesian optimization: the multi-armed bandit, in which a gambler chooses again and again among a few slot machines with unknown payout rates. The bandit strips the exploration and exploitation trade-off of Section 11.3 down to its bones. In that setting we can count how much exploring an algorithm does, show that the best algorithms explore only logarithmically often, and prove that no algorithm can explore less. We then carry the analysis back to functions, where a Gaussian process turns infinitely many correlated arms into a problem with a measurable complexity, and the GP-UCB algorithm comes with a bound in terms of it.

The last section is the one to read even if you skip the proofs. A regret bound is a precise statement about a stylized problem. It says some useful things about practice and is silent about others, and the figures in this chapter let you see how far apart a bound and an algorithm's behavior can be.

13.1 Scoring an optimizer #

Picture two optimizers working on the running objective of Chapter 11. The first spends most of its evaluations near the taller peak. The second wanders over the whole domain for most of its budget and, at the end, recommends the same peak. Which one did better? It depends on whether the evaluations along the way cost something beyond their price: whether we care about the journey or only the destination. Two kinds of regret make the two answers precise.

We maximize an unknown function $f$ over a domain $\X$. Write $f^\star = \max_{\vx \in \X} f(\vx)$ for the best value and $\vx^\star$ for an input that attains it, as in Equation (11.1). An optimizer evaluates $f$ at $\vx_1, \vx_2, \dots$, possibly with noise, and after $T$ evaluations it recommends an input $\hat\vx_T$, usually the best one observed or the maximizer of the posterior mean.

Regret is measured with the true $f$ at the chosen inputs, not with the noisy observations, and the optimizer can never compute it, because it does not know $f^\star$. Regret is the analyst's score: computable on a benchmark whose maximum is known, and the quantity that theorems bound.

Since every $r_t$ is at most the range of $f$, cumulative regret can grow at most linearly in $T$. An optimizer that never learns, such as one that queries uniformly at random forever, does grow linearly: each evaluation costs the same amount on average. An optimizer is called no-regret when its cumulative regret grows sublinearly, more slowly than any straight line, so that the average regret $R_T / T$ tends to zero. A bound of the form $R_T \le C\sqrt{T}$ says the average regret falls like $1/\sqrt{T}$; a bound of the form $R_T \le C \log T$ says almost all late evaluations are spent at nearly optimal inputs.

A bound on cumulative regret also bounds the simple regret of the best input visited. The smallest of $T$ numbers is at most their average, so

This is how cumulative regret bounds become convergence rates for optimization (Srinivas et al., 2010). Two caveats come with it. With noisy observations, the optimizer does not know which of its inputs had the largest $f$, so the best input visited is not the same as the best input it can identify; choosing what to report is a practical problem of its own (Section 14.2). And the converse fails: an optimizer that explores evenly can have small simple regret and linear cumulative regret. In the bandit problems of the next section the gap is sharp. On a fixed problem, the simple regret of uniform exploration falls exponentially with the budget, while algorithms that keep cumulative regret low have simple regret that falls only polynomially, because they stop sampling the near-best competitors as soon as they can (Bubeck et al., 2009; Lattimore and Szepesvári, 2020, ch. 33).

Which score to use depends on who pays for the evaluations. When tuning the hyperparameters of a model, or searching for a material, only the final recommendation is used; the evaluations along the way are a cost measured in compute or lab time, and simple regret is the right score. In an online experiment, every evaluation is a product variant shown to real users, and in a preference study, every option is something a person has to look at, wear, or listen to; there the path matters and cumulative regret is the right score. Section 19.6 describes a preference method with the better final answer and more than 2.5 times the cumulative regret of its competitor (Xu et al., 2024b).

A last distinction concerns what a bound quantifies over. A frequentist bound holds for every function in a stated class, such as all functions of a given smoothness. A Bayesian bound holds on average, or with high probability, over functions drawn from a prior. Both kinds appear in Section 13.4.

13.2 Multi-armed bandits #

Counting exploration requires a setting simple enough to count in. The multi-armed bandit is that setting. There are $K$ actions, called arms after the lever of a slot machine. Pulling arm $i$ returns a random reward whose distribution is fixed but unknown, with mean $\theta_i$. A player pulls one arm per round for $T$ rounds and wants the largest total reward. The earliest rule for such a problem is Thompson's, from 1933 (Thompson, 1933); Robbins stated the problem formally in 1952, as a question in the sequential design of experiments, and introduced the notion of regret (Robbins, 1952; Lattimore and Szepesvári, 2020, ch. 4).

A bandit is Bayesian optimization with two simplifications. The domain is a finite set of $K$ inputs, and the inputs are unrelated: pulling arm 3 says nothing about arm 4. Everything else carries over, including the noise, the budget, and the tension between trying the arm that looks best and checking the ones that might be better.

In this section each reward is a coin flip: a pull of arm $i$ pays 1 with probability $\theta_i$ and 0 otherwise. Write $\theta^* = \max_i \theta_i$ for the best arm's mean and $\Delta_i = \theta^* - \theta_i$ for the gap of arm $i$, how much is lost on average each time it is pulled instead of the best arm. (In this section $\theta_i$ is an arm's mean reward; the symbol $\mu$ stays reserved for the posterior mean of a Gaussian process.)

The regret of a bandit algorithm is cumulative regret with the arm means in the role of $f$: $R_T = \sum_{t} (\theta^* - \theta_{a_t})$, where $a_t$ is the arm pulled in round $t$. Because it uses the means rather than the coin flips that happened, it is sometimes called the pseudo-regret. Let $N_i(T)$ count the pulls of arm $i$ in the first $T$ rounds. Grouping the sum by arm gives

The decomposition turns the problem into bookkeeping. Regret is the number of times each worse arm is pulled, weighted by how much worse it is. An algorithm keeps regret low by pulling bad arms rarely, but it can only learn that an arm is bad by pulling it. The whole subject is the question of how many pulls are enough.

Before reading about algorithms, try it yourself. The figure below hides the payout rates of five arms; you have 50 pulls.

You probably formed a favorite after two or three pulls per arm. Did you go back to an arm that started with two losses? With payout rates between 0.15 and 0.6, two losses in a row happen for the best arm 16% of the time, so abandoning an arm that early is a gamble. Each algorithm below is a rule for that decision.

13.2.1 Greedy and epsilon-greedy #

The simplest rule is greedy: pull every arm once, then always pull the arm with the highest average reward so far. It fails in an instructive way. If the best arm happens to pay 0 on its first pull, its average is 0, some worse arm's average is positive, and greedy may never pull the best arm again. That happens with a fixed positive probability, and when it does the regret grows linearly forever.

Epsilon-greedy repairs this by forcing exploration: in each round, with probability $\varepsilon$ pull an arm chosen uniformly at random, and otherwise pull the greedy arm. Every arm is now pulled infinitely often, so every average converges to its mean. But the repair has a price that never stops being paid. With constant $\varepsilon$, every round spends probability $\varepsilon$ on a uniformly random arm, which costs $\frac{\varepsilon}{K} \sum_i \Delta_i$ in expected regret per round, so regret grows linearly with slope at least that (Exercise 13.1). Auer, Cesa-Bianchi, and Fischer showed that letting $\varepsilon$ decay as $\varepsilon_n = \min\{1, cK/(\Delta_0^2 n)\}$ in round $n$ gives logarithmic regret, but only if $\Delta_0$ (written $d$ in their paper) is a lower bound on the gap between the best and the second-best arm, which a player does not know. In their experiments no value of $c$ worked well for all the reward distributions they tried (Auer et al., 2002).

13.2.2 Where confidence bounds come from #

Forcing exploration at a fixed rate keeps pulling arms that are already known to be bad. A better rule explores an arm only while the evidence about it is still weak, and for that it needs a number: after $n$ pulls, how far from the arm's mean can its average plausibly be? The answer comes from concentration inequalities, bounds on the probability that an average strays from its mean by more than a given distance. Every upper bound on regret in this chapter rests on one, and the choice of inequality decides the constants and the logarithms in the algorithms built on it.

Fix one arm with mean $\theta$, and let $Y_1, \dots, Y_n$ be $n$ of its rewards, independent and each in $[0, 1]$, with average $\hat\theta_n = \frac1n \sum_{s=1}^{n} Y_s$. The question is how large the tail probability $\Prob(\hat\theta_n \ge \theta + a)$ can be for a deviation $a > 0$. The lower tail, $\Prob(\hat\theta_n \le \theta - a)$, works the same way, so we treat only the upper one.

Markov's inequality. A quantity that is never negative and has a small mean cannot often be large: if it were at least $c$ more than a fraction $\E[Z]/c$ of the time, those occasions alone would push its mean above $\E[Z]$. For $Z \ge 0$ and $c > 0$,

To see it, note that $Z$ is at least $c$ times the indicator of the event $Z \ge c$ (1 when the event happens, 0 when not), and take expectations of both sides. The average $\hat\theta_n$ is never negative and has mean $\theta$, so $\Prob(\hat\theta_n \ge \theta + a) \le \theta/(\theta + a)$. For a fair coin and $a = 0.1$ that is $0.83$, and it stays $0.83$ however many rewards are averaged. Markov's inequality knows only the mean, and the mean of an average does not change with $n$.

Chebyshev's inequality. The cure is to apply Markov's inequality to something that does shrink with $n$. The squared deviation $(\hat\theta_n - \theta)^2$ has mean $\Var[\hat\theta_n] = \Var[Y]/n$, because the variance of a sum of independent terms is the sum of their variances (Section 2.7) and dividing a sum by $n$ divides its variance by $n^2$. The event $\hat\theta_n \ge \theta + a$ implies $(\hat\theta_n - \theta)^2 \ge a^2$, so

(Chebyshev's inequality bounds both tails together, and so each one.) For a coin, $\Var[Y] = \theta(1 - \theta)$, at most $\tfrac14$ (Section 2.6.2). The bound now falls like $1/n$, but turned around it is expensive. Setting the right side to a target failure probability $\delta$ gives the width $a = \sqrt{\Var[Y]/(n\delta)}$, which grows like $1/\sqrt{\delta}$. Bandit algorithms need very small failure probabilities, as small as $t^{-4}$ in round $t$ for the algorithm of the next subsection, and a width that grows like $t^2$ would keep every arm in play forever. The truth is much better. By the central limit theorem an average of many independent terms is close to Gaussian (Section 4.1.2), and a Gaussian's tail falls like $e^{-c^2/2}$ in the number $c$ of standard deviations, not like $1/c^2$.

The Chernoff method. Markov's inequality applied to an exponential captures that behavior (Lattimore and Szepesvári, 2020, ch. 5). For any $\lambda > 0$, the event $\hat\theta_n - \theta \ge a$ is the same as the event $e^{\lambda n(\hat\theta_n - \theta)} \ge e^{\lambda n a}$, and the exponential turns the sum inside the average into a product, $e^{\lambda n(\hat\theta_n - \theta)} = \prod_{s=1}^{n} e^{\lambda(Y_s - \theta)}$. The expectation of a product of independent factors is the product of their expectations, because their joint distribution factorizes (Definition 2.8). What remains is a bound on one factor, and the condition that supplies it has a name.

A Gaussian with mean zero and standard deviation $R$ satisfies this with equality, so the condition says that the tails of $Z$ are no heavier than that Gaussian's. Bounded variables qualify too. By Hoeffding's lemma, a variable with mean zero that always lies in an interval $[l, u]$ is $\tfrac12(u - l)$-sub-Gaussian (Lattimore and Szepesvári, 2020, ch. 5). A reward in $[0, 1]$ minus its mean is therefore $\tfrac12$-sub-Gaussian, and noise with mean zero that is never larger than $\sigma$ in absolute value is $\sigma$-sub-Gaussian. (The letter $R$ follows the papers cited below; it is not the regret $R_T$.)

With this condition the Chernoff method gives Hoeffding's inequality, which Hoeffding proved for sums of bounded random variables (Hoeffding, 1963): for rewards in $[0, 1]$,

Turned around, Hoeffding's inequality says that with probability at least $1 - \delta$, the average is below $\theta + \sqrt{\ln(1/\delta)/(2n)}$. The failure probability now enters through its logarithm. Shrinking $\delta$ from 0.05 to $10^{-6}$ widens a Hoeffding interval by a factor of 2.1 and a Chebyshev interval by a factor of 224. Applied to a Gaussian $Z$ with standard deviation 1, the same method gives $\Prob(Z \ge c) \le e^{-c^2/2}$, and a direct calculation halves this (Srinivas et al., 2010, Lemma 5.1), so both tails together have probability at most $e^{-c^2/2}$. That is the Gaussian bound in step 1 of the GP-UCB proof in Section 13.4.3.

The union bound. An algorithm does not use one interval. It uses one per arm in every round, and its analysis needs them all to hold, or at least needs to count how often one fails. The tool is elementary: the probability that at least one of several events happens is at most the sum of their probabilities,

because an outcome in which any of the events happens is counted at least once on the right. This union bound asks nothing about how the events depend on one another. To make $m$ intervals hold together with probability at least $1 - \delta$, give each the failure probability $\delta/m$. With Hoeffding's inequality the width becomes

so the number of intervals enters as an additive $\ln m$ under the square root. With Chebyshev's inequality the width would grow like $\sqrt{m}$. An exponential tail is what makes many simultaneous intervals affordable.

This is where the logarithms in bandit algorithms come from. An interval that must hold in every round up to a horizon $T$ needs $m = T$ and pays $\ln T$; one for each of $K$ arms in every round pays $\ln(KT)$. When the horizon is not known in advance, the budget $\delta$ can be spread unevenly instead, giving round $t$ the share $6\delta/(\pi^2 t^2)$. The shares add up to $\delta$ because $\sum_{t \ge 1} 1/t^2 = \pi^2/6$, and the width in round $t$ has $\ln(\pi^2 t^2/(6\delta))$ in place of $\ln(m/\delta)$, so it grows like $\sqrt{\ln t}$. GP-UCB's $\beta_t$ is this construction with one more union, over the $|\X|$ inputs (Section 13.4.3). UCB1, in the next subsection, sets the failure probability of each interval to $t^{-4}$ in round $t$. Solving $e^{-2na^2} = t^{-4}$ for $a$ gives $a = \sqrt{2\ln t / n}$, the bonus of Equation (13.9). The exponent 4 pays for a union of its own: in round $t$ two arms being compared can have been pulled any numbers of times up to $t$, about $t^2$ combinations of counts, and $t^2 \cdot t^{-4} = t^{-2}$ still adds up to a finite total over all rounds.

When the data choose the sample size. Hoeffding's inequality is about an average of $n$ rewards with $n$ fixed before the rewards are seen. A bandit algorithm decides how often to pull an arm from the rewards it has seen, and an arm that starts badly is pulled less. A reader may wonder whether that matters, since each reward is still an honest draw. It does. Flip a fair coin and stop as soon as heads lead tails. The average at the moment of stopping is always above one half, and stopping is likely: it happens within 100 flips with probability 0.92, and within 1000 flips with probability 0.97. For every fixed $n$, Hoeffding's inequality still holds for the average of the first $n$ flips; it says nothing about the average at an $n$ chosen by looking at the flips.

The bandit analyses repair this with the union bound. Picture each arm's rewards as a list drawn before play begins, with the algorithm choosing only how far down each list to read; this model gives the same probabilities to everything the algorithm sees (Lattimore and Szepesvári, 2020, sec. 4.6). For each fixed $n$, the first $n$ entries of a list are $n$ independent rewards, so Hoeffding's inequality applies to every $n$ separately, and a union over $n = 1, \dots, t$ covers whichever count the algorithm reaches. That union is the $t^2$ above. It is not a formality. If the single-round width $\sqrt{\ln(1/\delta)/(2n)}$ is used at every count, the interval of a fair coin with $\delta = 0.05$ fails at least once within 1000 pulls with probability 0.11, more than twice $\delta$, and within 10,000 pulls with probability 0.15, because the largest swings of a running average shrink slightly more slowly than $1/\sqrt{n}$ (see Lattimore and Szepesvári, 2020, ex. 20.9). With the width of the uneven split above, the same probability within 1000 pulls is $8.5 \times 10^{-6}$: the union bound is safe, and here very cautious. (These probabilities, like those for the fair coin above, are computed exactly, by tracking the distribution of the number of heads flip by flip.) A Gaussian process is harder still, because each evaluation changes the estimate everywhere, with weights that depend on where the algorithm chose to look; Section 13.4.5 gives the tool for that case.

The figure puts the three inequalities side by side for a coin.

Some things to try.

Read the default. For a fair coin and $a = 0.1$, the chance that 100 flips average 0.6 or more is 0.028. Hoeffding's inequality bounds it by 0.14, Chebyshev's by 0.25, and Markov's by 0.83. The readout gives the number of flips from which each curve stays below 0.05: 76 for the exact probability, 150 for Hoeffding's bound, 500 for Chebyshev's, and never for Markov's.

Move the marker to $n = 1000$. The exact probability is $1.4 \times 10^{-10}$ and Hoeffding's bound $2.1 \times 10^{-9}$, while Chebyshev's is still 0.025. The exact curve and Hoeffding's fall at nearly the same exponential rate, and the gap between them grows only slowly, from a factor of about 5 at $n = 100$ to 15 at $n = 1000$; Chebyshev's is a straight line on these axes, falling only like $1/n$.

Set the union to 1000. Every bound is multiplied by 1000. Hoeffding's now stays below 0.05 from 496 flips instead of 150, an extra $\ln 1000/(2a^2) \approx 345$; Chebyshev's from 500,000 instead of 500, a thousand times as many. The exact probability for 1000 independent averages needs 381 flips. This is the $\ln m$ of Equation (13.8), seen from the side of the sample size.

Move the mean to 0.1, with the union back at 1. A coin that rarely pays has variance 0.09 instead of 0.25, and its exact probability stays below 0.05 from 36 flips. Chebyshev's bound, which uses the variance, improves to 180 flips; Hoeffding's, which knows only that rewards lie in $[0, 1]$, stays at 150, and at $n = 100$ it gives 0.14 against an exact 0.002. Inequalities that use the variance as well, such as Bernstein's, recover much of this gap (Lattimore and Szepesvári, 2020, ex. 5.14).

13.2.3 Optimism: UCB1 #

A better rule follows from the principle that Section 12.4 called optimism in the face of uncertainty. For each arm, compute the largest mean that is still plausible given its rewards so far, and pull the arm whose plausible best is largest. An arm pulled often has a tight interval, so its plausible best is close to its average. An arm pulled rarely has a wide interval and a generous plausible best, so it gets another look. A clearly bad arm stops being pulled once its interval has shrunk below the best arm's mean.

How wide should the interval be? For rewards in $[0, 1]$, Hoeffding's inequality (Equation (13.6)) says that the average $\hat\theta_{i}$ of $n$ independent rewards overestimates the mean by more than $a$ with probability at most $e^{-2na^2}$, and likewise underestimates it. Choosing the width so that this probability is $t^{-4}$ in round $t$, for the reason given in Section 13.2.2, gives the UCB1 rule of Auer et al. (2002): after pulling each arm once, pull

where $N_i$ is the number of times arm $i$ has been pulled so far and $\hat\theta_i$ is its average reward. The bonus shrinks like $1/\sqrt{N_i}$ as an arm is pulled and grows like $\sqrt{\ln t}$ for arms left alone, so no arm is abandoned for good, yet a bad arm is revisited only rarely.

The proof is worth seeing in outline, because the same three moves reappear in the Gaussian process bound of Section 13.4: a confidence interval that holds with high probability, an argument that optimism costs at most the width of the interval, and a count of how often intervals can be wide.

The bound depends on the problem through the gaps. Arms that are much worse than the best are discarded quickly and contribute little; arms that are nearly as good contribute $\ln T / \Delta_i$ each, which is large for small $\Delta_i$. The upper confidence bound rule of Section 12.4 is the same idea with the posterior standard deviation of a Gaussian process in place of the Hoeffding width.

13.2.4 Thompson sampling #

The oldest rule is Bayesian. Treat each unknown mean $\theta_i$ as a random quantity with a prior, keep its posterior up to date, and in each round pull each arm with the probability that it is the best one. Thompson's trick is that this probability never has to be computed: draw one plausible mean from each arm's posterior, and pull the arm whose draw is largest (Thompson, 1933).

For coin-flip rewards the posterior is a Beta distribution. Starting from a uniform prior, an arm with $S_i$ wins and $F_i$ losses has posterior $\mathrm{Beta}(1 + S_i, 1 + F_i)$, the conjugate update of Section 5.2. Its mean is close to the arm's average, and its spread shrinks as the arm is pulled.

Exploration comes from the randomness of the draws. An arm with few pulls has a wide posterior and sometimes produces a high draw; an arm with many pulls and a low average almost never does. Thompson's rule was not widely circulated, and it became popular only after several groups rediscovered it around 2010 and found it strong in experiments, before any proof existed (Lattimore and Szepesvári, 2020, ch. 36). Agrawal and Goyal (2012) then gave the first proof that its expected regret grows logarithmically, and Kaufmann et al. (2012) and Agrawal and Goyal (2013) showed that for Bernoulli rewards its leading constant is the best possible, the constant of the lower bound in the next section. The Gaussian process version of the rule, which draws a whole function from the posterior and evaluates where the draw is largest, is the Thompson sampling of Section 12.5.

13.2.5 Watching them play #

The figure below runs the three algorithms on the same arms many times and plots the average cumulative regret of each, with a band covering the middle 80% of runs. All three start from the same payout sequences in each run, so the differences come from the rules and not from luck.

Some things to try.

Switch on the log time axis. On a logarithmic time axis, regret that grows like $\ln t$ is a straight line, and regret that grows linearly curves sharply upward. Thompson sampling settles onto a straight line after a few hundred rounds, and ε-greedy turns upward. UCB1 is still in between at this horizon: with a gap of 0.1, its cautious bonus keeps the second-best arm in play for thousands of rounds, and its curve straightens only later.

Set ε to 0. This is the greedy rule. The band widens: most runs settle on the best arm, and a few lock onto a worse arm and stay there. Set the runs to 1 and press New arms a few times to see individual outcomes.

Compare UCB1 and ε-greedy at the default horizon. With these arms, ε-greedy with $\varepsilon = 0.1$ has lower regret than UCB1 after 1000 rounds: UCB1's bonus is conservative and buys its guarantee with extra exploration. Raise the gap to 0.3 and the horizon to 5000. The straight line of ε-greedy eventually overtakes the logarithm of UCB1.

Show the UCB1 guarantee. The scale stretches to hold it. At the default settings, the bound of Theorem 13.1 is about 1100 at $T = 1000$, more than twice the 450 that the worst possible play, always pulling the worst arm, would lose. The guarantee is true and, at this horizon, uninformative.

Watch Thompson sampling. It has the lowest regret here, and for most settings its curve sits below the dashed Lai-Robbins line. The next section explains why this is not a contradiction.

13.3 Lower bounds #

UCB1 and Thompson sampling both have regret that grows like $\ln T$. Could a cleverer algorithm do better, with regret bounded by a constant? Lai and Robbins (1985) answered no.

The intuition is about evidence. To stop pulling a worse arm, an algorithm must be confident that the arm is not secretly the best. Abandoning the best arm by mistake costs on the order of $\Delta T$ over the remaining rounds, so the probability of that mistake must be of order $1/T$. The amount of evidence needed to rule out an alternative at that level grows like $\ln T$, and every pull of arm $i$ adds a fixed expected amount of evidence: the Kullback-Leibler divergence $\mathrm{kl}(\theta_i, \theta^*)$, the average log-likelihood ratio per pull between the hypothesis that the arm pays at rate $\theta_i$ and the hypothesis that it pays at rate $\theta^*$. For coins,

which is zero when $p = q$ and grows as the two coins become easier to tell apart (Section 6.2 treats the divergence in general). Dividing the evidence needed by the evidence per pull gives about $\ln T / \mathrm{kl}(\theta_i, \theta^*)$ pulls of arm $i$.

To make this a theorem, one has to exclude algorithms that are lucky on one problem by being terrible on others, such as the rule that always pulls arm 1, which has zero regret whenever arm 1 is best. An algorithm is consistent if on every bandit in the class its regret grows more slowly than every power of $T$: $\E[R_T] / T^a \to 0$ for every $a > 0$.

This is the special case of a general result for reward distributions in a parametric family; Lattimore and Szepesvári state and prove the modern form (Lai and Robbins, 1985; Lattimore and Szepesvári, 2020, Thm. 16.2).

Three remarks connect the theorem to the algorithms above. First, UCB1 is logarithmic but not optimal. Pinsker's inequality gives $\mathrm{kl}(p, q) \ge 2(p - q)^2$, so each term of $c^*$ is at most $1/(2\Delta_i)$, while the corresponding term of Theorem 13.1 is $8/\Delta_i$, at least 16 times larger. Thompson sampling with Beta posteriors attains $c^*$ exactly, in the limit (Kaufmann et al., 2012; Agrawal and Goyal, 2013).

Second, the theorem is about the limit, and the $\liminf$ is doing real work. It says that the ratio of regret to $\ln T$ cannot stay below $c^*$ forever. It does not say that $\E[R_T] \ge c^* \ln T$ at every finite $T$, and an algorithm whose lower-order terms are negative can sit below that curve for a long time. That is what Thompson sampling does in Figure 13.3. The comparison the theorem licenses is between slopes on a logarithmic time axis, as $t$ grows large.

Third, the bound depends on the instance through its gaps, and it blows up as a gap shrinks. That does not mean regret becomes large when arms are nearly equal, since each pull of a nearly equal arm costs little. The worst case over all instances is a different quantity: for any algorithm and any $T \ge K

• 1$ there is a $K$-armed bandit with Gaussian rewards on which its regret is at least $\frac{1}{27}\sqrt{(K - 1)T}$ (Lattimore and Szepesvári, 2020, Thm. 15.2). The gap that does the damage shrinks with $T$, like $\sqrt{K/T}$: large enough to matter, small enough to be hard to detect. Instance-dependent bounds grow like $\ln T$ with a problem-dependent constant; worst-case bounds grow like $\sqrt{T}$. Both views return for functions.

13.4 From arms to functions #

Bayesian optimization has an arm for every input, infinitely many on a continuous domain. The bandit bounds above grow with the number of arms, either through the sum over gaps or through the $\sqrt{K}$ of the worst case, and they say nothing when $K$ is infinite. What rescues the analysis is that the arms are no longer independent. A Gaussian process prior says that nearby inputs have similar values, so evaluating one input teaches about its neighbors. The number of arms has to be replaced by a measure of how many effectively different arms there are, and the maximum information gain is that measure.

13.4.1 The setting #

The analysis of Srinivas et al. (2010), which this section follows, takes the model of Section 8.3 at face value. The function is a draw from a Gaussian process, $f \sim \GP(0, k)$, with $k(\vx, \vx) \le 1$ so that the prior standard deviation is at most 1 everywhere. Each evaluation returns $y_t = f(\vx_t) + \varepsilon_t$ with independent noise $\varepsilon_t \sim \N(0, \sigma_n^2)$ of known variance. For now the domain $\X$ is finite, for instance a fine grid (the paper writes $D$ for this set); Section 13.4.4 relaxes this. A $K$-armed bandit with Gaussian rewards is the special case of a kernel that is 1 on the diagonal and 0 elsewhere.

After $t - 1$ evaluations, the posterior has mean $\mu_{t-1}(\vx)$ and standard deviation $\sigma_{t-1}(\vx)$, computed as in Equation (8.6). The GP-UCB rule is the optimism of UCB1 with the posterior in place of the Hoeffding interval:

The posterior mean plays the part of the empirical average, the posterior standard deviation plays the part of the bonus, and $\beta_t$ sets how many standard deviations of optimism to allow. This is the rule of Equation (11.3) with a weight that may change from round to round. As there and in Srinivas et al. (2010), $\beta_t$ multiplies the variance, so its square root multiplies the standard deviation; some texts and libraries call the multiplier of the standard deviation itself $\beta$.

13.4.2 Maximum information gain #

How much can $T$ noisy evaluations teach about $f$? Section 6.5 answered this question, and the bound needs three facts from there. First, the mutual information between the observations $\vy_A$ at a set of inputs $A$ and the function, the part of the observations' uncertainty that reflects $f$ and not the noise, is

where $\mK_A$ is the kernel matrix of $A$ (Equation (6.15)). It depends on where we evaluate, not on what we observe, because the posterior variance of a Gaussian process does not depend on the observed values (Section 8.1). Second, the most that any $T$ evaluations could teach is the largest value this quantity can take.

$\gamma_T$ is a property of the kernel, the domain, and the noise level, fixed before any data arrive.

Two extreme cases show its range. If all $T$ evaluations are made at the same input, they gain $\tfrac12 \log(1 + T/\sigma_n^2)$, which grows only logarithmically: repeating an evaluation teaches less and less, as Exercise 8.2 showed. If the kernel is diagonal, as in a $K$-armed bandit, spreading the evaluations evenly over the arms is best, and $\gamma_T$ grows like $\tfrac{K}{2}\log(1 + T/(K\sigma_n^2))$ (Exercise 13.3). A smooth kernel lies between these: observations at nearby inputs are largely redundant, so the information grows much more slowly than for $T$ independent arms. A short lengthscale, a rough kernel, a high dimension, or low noise each make more of the domain distinguishable and increase $\gamma_T$.

Third, although computing the maximum exactly is intractable, it is easy to approximate. A new evaluation at $\vx$ adds exactly $\tfrac12 \log(1 + \sigma_n^{-2}\sigma_{t-1}^2(\vx))$ to the information (Equation (6.16)), so the greedy rule of always evaluating where the posterior variance is largest (uncertainty sampling, Section 6.5.1) reaches at least a fraction $1 - 1/e \approx 0.63$ of $\gamma_T$ (Srinivas et al., 2010). That is how the figure in Section 13.5 estimates $\gamma_T$.

13.4.3 The GP-UCB bound #

With $\gamma_T$ in hand, the bound reads like a bandit bound with $K$ replaced.

The proof follows the same three moves as the UCB1 sketch, and every step is elementary.

Reading the result: $\beta_T$ grows like $\log T$ (and $\log |\X|$), and $\gamma_T$ grows sublinearly for the kernels used in practice, so $R_T$ grows like $\sqrt{T}$ times slowly growing factors. GP-UCB is therefore no-regret, and by Equation (13.2), with probability at least $1 - \delta$, the best input it has evaluated is within $\sqrt{C_1 \beta_T \gamma_T / T}$ of the maximum.

A finite domain is not only a mathematical convenience. In the experiments of Srinivas et al. (2010), the inputs were the 46 temperature sensors of a sensor network at Intel Research Berkeley, and in a second test the 357 traffic sensors along a stretch of the I-880 highway in California, where the goal was to find the most congested point. The kernel matrix was not a formula: it was the empirical covariance of the sensors' readings over the first two thirds of the recorded data, and the functions to optimize were snapshots from the remaining third. On the temperature data GP-UCB and expected improvement clearly outperformed the other heuristics, with no significant difference between the two; the authors summarize that GP-UCB performed at least on par with existing approaches that had no regret bounds. The bound also connects two traditions. Step 4 says that a GP-UCB step can be expensive only when it is informative, so an optimizer's regret is controlled by how much there is to learn about $f$, which is the currency of experimental design (Section 6.4).

How fast $\gamma_T$ grows decides how good the bound is. Table 13.1 collects the known rates for a domain in $d$ dimensions, which follow from how fast the eigenvalues of the kernel decay (Section 10.5); $\nu$ is the smoothness parameter of the Matérn kernel (Section 9.1).

For the RBF kernel, the dimension appears only as the exponent of $\log T$, so the bound grows like $\sqrt{T}(\log T)^{(d+2)/2}$ (a factor $(\log T)^{(d+1)/2}$ from $\gamma_T$ and one more $(\log T)^{1/2}$ from $\beta_T$): very smooth functions are learned quickly even in several dimensions (Srinivas et al., 2010). For Matérn kernels the original rate was loose; the 2021 rate of Vakili et al. (2021a) matches the known lower bounds up to logarithmic factors.

13.4.4 Other settings #

The finite-domain theorem extends in three directions, each with its own assumptions. This subsection is a map of results for readers who will meet them in papers. It can be skipped on a first reading; the one idea used later, the reproducing kernel Hilbert space, is explained again in Section 21.3, and Chapter 10 treats it in depth.

Continuous domains. For a compact, convex domain in $d$ dimensions, such as a box, Srinivas et al. (2010) prove a bound of the same form, with $\beta_t$ gaining a term of order $d \log t$ and the bound gaining an additive constant. The proof discretizes the domain more finely as $t$ grows, which requires sample paths smooth enough that values at nearby grid points are close. The RBF kernel and Matérn kernels with $\nu > 2$ qualify. The rough Matérn 1/2 kernel violates the assumption, and the authors conjecture that no result of this form holds for it.

Fixed functions. The theorems above are Bayesian: they hold with high probability for functions drawn from the prior. A frequentist version asks for a guarantee for one fixed function from a class. The natural class is the reproducing kernel Hilbert space (RKHS) of the kernel, a space of functions built from sums of kernel bumps like Equation (8.4), whose norm $\lVert f \rVert_k$ measures how rough $f$ is relative to the kernel (Section 10.2 constructs the space and its norm). (Sample paths of the Gaussian process itself are rougher than this, with infinite norm, so neither setting contains the other.) If $\lVert f \rVert_k^2 \le B$ and the noise is bounded, GP-UCB with $\beta_t = 2B + 300\gamma_t \log^3(t/\delta)$ has regret of order $\sqrt{T}(\sqrt{B\gamma_T} + \gamma_T)$ up to logarithmic factors (Srinivas et al., 2010). Chowdhury and Gopalan (2017) sharpened this analysis and proved a regret bound for a Gaussian process version of Thompson sampling. Section 13.4.5 shows where widths of this kind come from.

Lower bounds. In the RKHS setting, Scarlett et al. (2017) proved that every algorithm has cumulative regret of at least order $T^{(\nu + d)/(2\nu + d)}$ on some function in the Matérn class. For the RBF kernel they showed that cumulative regret is at least of order $\sqrt{T(\log T)^{d/2}}$, which matches the upper bounds up to replacing $d/2$ by $2d + O(1)$ in the exponent of $\log T$ under the square root. The lower bounds play the role of Lai and Robbins for functions: they say how much exploring the class forces on any algorithm.

The same machinery, with comparisons in place of evaluations, gives the kernelized dueling bandit bounds of Section 21.3 and the theory of Chapter 29, where some of the basic lower bounds are still missing (Section 29.7).

13.4.5 Confidence for a fixed function #

The confidence step of Theorem 13.3 used two tools from Section 13.2.2. A Gaussian lands more than $\beta^{1/2}$ standard deviations from its mean with probability at most $e^{-\beta/2}$, and a union bound over the $|\X|$ inputs and over rounds, giving round $t$ the share $6\delta/(\pi^2 t^2)$ of $\delta$, asks for $|\X|\, e^{-\beta_t/2} = 6\delta/(\pi^2 t^2)$. Solving for $\beta_t$ gives the theorem's $\beta_t = 2 \log\!\big(|\X|\, t^2 \pi^2/(6\delta)\big)$. The adaptive choice of inputs did no harm there: given the observations so far, the inputs chosen from them are fixed, and $f(\vx)$ is Gaussian with mean $\mu_{t-1}(\vx)$ and standard deviation $\sigma_{t-1}(\vx)$ whatever rule chose them (Srinivas et al., 2010, Lemma 5.1).

The frequentist results of Section 13.4.4 remove that support. There $f$ is one fixed function with $\lVert f \rVert_k^2 \le B$, and the only randomness is the noise. The error $\mu_t(\vx) - f(\vx)$ is a bias, from the prior pulling the estimate toward zero, plus a weighted sum of the noise terms $\varepsilon_1, \dots, \varepsilon_t$, and the weights depend on where the algorithm chose to look, which depended on earlier noise. That is not a sum of independent terms with weights fixed in advance, so Hoeffding's inequality does not apply, and on a continuous domain there is no finite list of inputs to take a union over. This subsection shows the tool that replaces both and how it produces a width that grows with $\gamma_t$ and $\log(1/\delta)$. Like the map above, it can be skipped on a first reading.

Martingales. Consider a running sum $M_t = \sum_{s \le t} g_s \varepsilon_s$ in which each weight $g_s$ may depend on everything observed before round $s$ but is fixed before $\varepsilon_s$ is drawn, and each $\varepsilon_s$ has mean zero given everything before it. Such a sum is a martingale: the fortune of a gambler in a fair game who chooses each stake by looking at the history. The stakes are adaptive, and the game is still fair. The Chernoff method survives the adaptivity. Given the past, $g_t$ is a fixed number and $\varepsilon_t$ is $R$-sub-Gaussian (Definition 13.2), so $\E\big[e^{\lambda g_t \varepsilon_t} \given \text{past}\big] \le e^{\lambda^2 g_t^2 R^2/2}$. Peeling off one round at a time, starting from the last, shows that

has expectation at most 1 for every $t$. Where the derivation of Equation (13.6) factored an expectation over independent terms, this one factors it over rounds, each conditioned on the rounds before. More is true: $Z_t$ is never negative and does not drift upward on average from one round to the next, and for such a process Markov's inequality holds in a stronger form, the maximal inequality: the probability that $Z_t$ ever reaches $1/\delta$ is at most $\delta$ (Lattimore and Szepesvári, 2020, Thm. 3.9). A bound for all rounds at once then needs no union over rounds.

Two problems remain. The best $\lambda$ depends on $V_t$, which is random. And a Gaussian process estimate is not of the form $M_t$: its weight on the observation $y_s$ depends on inputs chosen after round $s$. The first problem is solved by averaging $Z_t$ over $\lambda$ instead of choosing it, the method of mixtures.

The result reads as a statement in standard deviations. $R^2 V_t$ plays the role of the variance of $M_t$, so the sum stays within about one standard deviation, $R\sqrt{V_t + c}$, times $\sqrt{2\log(1/\delta) + \log(1 + V_t/c)}$. The $2\log(1/\delta)$ is the price of confidence that every Chernoff bound pays. The $\log(1 + V_t/c)$ is the price of not knowing in advance how large the variance would be, and it grows only like the logarithm of the variance. A bound of this kind is called self-normalized: the sum is measured against its own accumulated variance.

The second problem is solved by working with vectors. Write the kernel through features, $k(\vx, \vx') = \boldsymbol{\phi}(\vx)^\T\boldsymbol{\phi}(\vx')$, the weight-space view of Section 5.4.2 with the prior covariance of the weights set to $\mI$. Two quantities summarize the first $t$ rounds: the posterior precision of the weights, and the noise pushed along the features of the inputs that received it,

Each term of $\mathbf{s}_t$ has its weight vector $\boldsymbol{\phi}(\vx_s)$ fixed before its noise is drawn, so $\mathbf{s}_t$ is a martingale with vector values. Averaging over a Gaussian distribution of directions, in place of the Gaussian distribution of $\lambda$ in the box above, gives the following bound.