Bayesian Bandits

Corresponds to Lattimore & Szepesvári, Chapters 34–35.

Motivation: average over environments instead of worst-casing them

IntuitionWhy go Bayesian

A policy that is optimal in one environment is usually not optimal in another, so some trade-off between environments is unavoidable. The frequentist answers so far were worst-case (minimax) and instance-dependent bounds for “reasonable” policies. The Bayesian answer: encode beliefs as a prior over environments and minimise expected loss under it. Bayesian methods dominated bandit research from about 1950 to 1980. The authors aren’t interested in Bayesian-versus-frequentist debates, only in the pros and cons of problem definitions and methods.

Statistical decision theory

DefinitionLoss, dominance, admissibility, minimax

Environments $\mathcal E$ , policies $\Pi$ , and a loss $\ell : \mathcal E\times\Pi\to\mathbb R$ .

$\pi$ is dominated if some $\pi'$ has $\ell(\nu,\pi')\le\ell(\nu,\pi)$ for all $\nu$ , strictly for some $\nu$ .
Admissible (Pareto optimal) = not dominated.
Minimax optimal: $\pi\in\arg\min_{\pi'}\sup_\nu\ell(\nu,\pi')$ . Robust, but potentially costly on average.
Bayes optimal for a prior $q$ : $\pi\in\arg\min_\pi\sum_\nu q(\nu)\ell(\nu,\pi)$ (an integral in general).

ExampleWhich policy would you choose?

With $\mathcal E = [0,1]$ and four policies: one is dominated, one is minimax (flat at a moderate loss), and two are admissible, each excellent on part of $[0,1]$ . Minimax buys robustness at the cost of average performance. The Bayesian chooses by weighting environments, which is hard to criticise when the prior is really known and the user is risk-neutral, and often sensible even when it isn’t. Compare the multi-objective view of regret over a class.

TheoremAdmissibility versus Bayes optimality (Exercises 34.12–34.15)

A uniquely Bayes-optimal policy is admissible. So is any Bayes-optimal policy when $\mathcal E$ is countable and the prior has full support. In general, a Bayes-optimal policy is admissible on $\mathrm{Supp}(Q)$ .
A Bayes-optimal policy can be inadmissible, because it may behave badly on prior-null events.
Conversely: with finitely many environments and a convex loss set, every Pareto-optimal policy is Bayes optimal for some prior. The proof uses the supporting hyperplane theorem: the prior is the hyperplane’s normal. In multi-criteria optimisation this is “every Pareto point minimises a convex combination of the criteria”. The same holds for $k$ -armed Bernoulli bandits (Exercise 34.15).
Many classical results go “admissible ⟺ Bayes (or limits of Bayes)”, but counterexamples exist (Berger 1985).

RemarkToo binary

Admissibility is a blunt notion: a policy that is barely dominated is not worthless, especially when the optimal policy is intractable. A more useful view evaluates policy schemas, such as Thompson sampling, across whole families of problems: is the schema near Bayes- or minimax-optimal everywhere? Most bandit algorithm design is really schema design.

Posteriors

ExampleTwo marbles

A bag holds either two white marbles ( $ww$ ) or one white and one black ( $wb$ ), each with prior probability $\frac12$ . Draw one marble blindly. The likelihoods are $\mathbb P(\text{white}\mid ww) = 1$ and $\mathbb P(\text{white}\mid wb) = \frac12$ . By Bayes’ rule,

$\mathbb P(ww\mid\text{white}) = \frac{1\cdot\frac12}{1\cdot\frac12 + \frac12\cdot\frac12} = \frac23$

and $\mathbb P(ww\mid\text{black}) = 0$ . The hypotheses are part of the probability space: that is the Bayesian move.

DefinitionPrior, model, joint measure

Hypothesis space $(\Theta,\mathcal G)$ , prior $Q$ on it, and a model that is a probability kernel $P = (P_\theta)$ from $\Theta$ to the outcome space $(U,\mathcal H)$ . The joint law is $\mathbb P = Q\otimes P$ on $\Theta\times U$ , and $Q$ is its $\Theta$ -marginal. An observation $X$ is a measurable map on $\Theta\times U$ . The posterior is a kernel $Q(\cdot\mid x)$ from observations to $\Theta$ .

WarningNaive Bayes’ rule fails on null events

$Q(A\mid x) = \mathbb P(X = x\mid\theta\in A)\mathbb P(\theta\in A)/\mathbb P(X = x)$ is undefined when $\mathbb P(X = x) = 0$ , which is the usual case: with prior $\mathcal N(0,1)$ and $X\sim\mathcal N(\theta,1)$ , every point has probability 0. Defining $Q(A\mid x) = \mathbb E[\mathbb I\{\theta\in A\}\mid X](x)$ gives an object unique only almost surely, which need not be a measure.

TheoremTheorem 34.1 — Posteriors exist (Borel hypothesis space)

If $(\Theta,\mathcal G)$ is a Borel space, there is a probability kernel $Q$ with $Q(A\mid X) = \mathbb P(\theta\in A\mid X)$ for all $A$ outside a single null set, unique for $\mathbb P_X$ -almost every $x$ . This is the regular conditional distribution theorem in Bayesian notation.

FormulaPosterior density

With $p_\theta = dP_\theta/d\mu$ and $q = dQ/d\nu$ (jointly measurable densities always exist when all $P_\theta\ll\lambda$ ; Note 8),

$q(\theta\mid x) = \frac{p_\theta(x)q(\theta)}{\int_\Theta p_\theta(x)q(\theta)\,d\nu(\theta)} \tag{34.2}$

When a dominating measure exists and the denominator is positive, (34.2) defines a valid posterior (Exercise 34.4); the denominator vanishes only on a $\mathbb P_X$ -null set.

WarningNon-uniqueness matters to frequentists (Example 34.2)

Take the prior $\mathcal U[0,1]$ and the observation $X = \theta$ exactly. For any countable $C$ and any measure $\mu$ , the kernel equal to $\delta_x$ off $C$ and $\mu$ on $C$ is a valid posterior. A Bayesian doesn’t care, since $\{X\in C\}$ has prior probability 0. A frequentist proves results for a fixed $\theta$ , which may well lie in $C$ , so the version of the posterior must be specified. In practice there is a canonical choice (continuous densities, the Gaussian posterior for Gaussian models), and “sensible choices yield sensible posteriors”. Related: the Borel–Kolmogorov paradox (Jaynes §15.7).

Conjugate priors

DefinitionConjugate pair

A prior family is conjugate to a model if the posterior stays in the family. This is crucial for computation: Bayesian algorithms need posteriors that can be computed or sampled efficiently, which tempers the advantage of a freely chosen prior.

Model	Conjugate prior	Posterior after observing $x$
$\mathcal N(\theta,\sigma_S^2)$ , $\sigma_S$ known	$\mathcal N(\mu_P,\sigma_P^2)$	$\mathcal N\Big(\frac{\mu_P/\sigma_P^2 + x/\sigma_S^2}{1/\sigma_P^2 + 1/\sigma_S^2},\ \big(\frac1{\sigma_S^2} + \frac1{\sigma_P^2}\big)^{-1}\Big)$
$\mathcal N(\theta_1,\theta_2)$ , both unknown	Gaussian–inverse-gamma	same family
$\mathcal B(\theta)$	$\mathrm{Beta}(\alpha,\beta)$	$\mathrm{Beta}(\alpha + x,\beta + 1 - x)$ , unique (Exercise 34.2)
$\mathcal U(a,b)$ (not an exponential family)	Pareto	Pareto

IntuitionPrecisions add

The Gaussian posterior mean is a precision-weighted average of the prior mean and the data, and the posterior precision is the sum of the precisions. $\sigma_P^2\to0$ : the prior is certain and nothing is learned. $\sigma_P^2\to\infty$ : the prior is washed away after a single sample. $\sigma_S^2\to0$ : one observation reveals $\theta$ . $\sigma_S^2\to\infty$ : data is useless.

DefinitionSingle-parameter exponential family

With a base measure $h$ , sufficient statistic $S$ and natural-parameter map $\eta$ ,

$\frac{dP_\theta}{dh}(x) = \exp\big(\eta(\theta)S(x) - A(\theta)\big),\qquad A(\theta) = \log\int e^{\eta(\theta)S(x)}dh(x)$

on $\Theta = \mathrm{dom}(A)$ . It is regular if $\Theta$ is nonempty and open, and non-singular if $A'' > 0$ .

Example	$h$	$S$ , $\eta$	$A(\theta)$	Family
34.3	$\mathcal N(0,\sigma^2)$	$x/\sigma$ , $\theta/\sigma$	$\theta^2/(2\sigma^2)$	$\mathcal N(\theta,\sigma^2)$
34.4	$\delta_0 + \delta_1$	$x$ , $\theta$	$\log(1 + e^\theta)$	$\mathcal B(\text{logistic}(\theta))$
34.5	$\delta_0 + \delta_1$	$x$ , $\log\frac\theta{1-\theta}$	$-\log(1-\theta)$	$\mathcal B(\theta)$ , the same family reparameterised

TheoremConjugate priors for exponential families

With $S(x) = x$ , the prior density $q(\theta)\propto\exp(n_0x_0\eta(\theta) - n_0A(\theta))$ (34.4) has posterior of the same form with

$(x_0,n_0)\ \mapsto\ \Big(\frac{n_0x_0 + x}{n_0 + 1},\ n_0 + 1\Big)$

$n_0$ acts as a pseudo-count and $x_0$ as a pseudo-mean. For Bernoulli, $\big(\frac\theta{1-\theta}\big)^{n_0x_0}(1-\theta)^{n_0} = \theta^{n_0x_0}(1-\theta)^{n_0(1-x_0)}$ , which is $\mathrm{Beta}(1 + n_0x_0,\ 1 + n_0(1-x_0))$ .

TheoremExponential-family facts (Exercise 34.5, canonical $\eta(\theta) = \theta$ )

$A'(\theta) = \mathbb E_\theta[S]$ , and the MGF is $\mathbb E_\theta[e^{\lambda S}] = e^{A(\theta + \lambda) - A(\theta)}$ .
$D(P_\theta,P_{\theta'}) = A(\theta') - A(\theta) - (\theta' - \theta)A'(\theta)$ (34.12): the relative entropy is the Bregman divergence of the log-partition function $A$ .
Chernoff: if $A'(\theta')\ge A'(\theta)$ , then $\mathbb P_\theta(\hat S\ge A'(\theta'))\le e^{-nD(P_{\theta'},P_\theta)}$ , the exponential-family form of the large-deviation rate and of KL-UCB’s confidence intervals.

DefinitionSufficient statistic (Note 9)

$Y = y(X)$ is sufficient if $\mathbb P_\theta(X\in\cdot\mid Y)$ doesn’t depend on $\theta$ : once you know $Y$ , $X$ carries no more information about $\theta$ . Fisher–Neyman: with a common dominating measure, sufficiency is equivalent to the factorisation $\frac{dP_{X,\theta}}{d\mu}(x) = h(x)g_\theta(y(x))$ . The exponential family’s $S$ is sufficient in this sense.

Sequential posteriors

FormulaPredictive distribution and the Markov view

If $Q_t$ is the posterior after $X_1, \ldots, X_t$ , the tower rule gives

$\mathbb P(X_{t+1}\in B\mid X_{1:t}) = \int_\Theta P_\theta(X_{t+1}\in B\mid X_{1:t})\,Q_t(d\theta\mid X_{1:t}) \tag{34.5}$

which reduces to $\int P_\theta(B)\,Q_t(d\theta)$ for i.i.d. models: the posterior summarises everything useful for prediction. Under regularity, $Q_1, Q_2, \ldots$ is a (time-inhomogeneous) Markov chain.

ExampleTwo posterior Markov chains

Beta–Bernoulli (Example 34.6): $Q_t = \mathrm{Beta}(\alpha + S_t,\beta + t - S_t)$ with $S_t = \sum_{s\le t}X_s$ , and $S_{t+1} = S_t + 1$ with probability $\frac{\alpha + S_t}{\alpha + \beta + t}$ (a Pólya urn).
Gaussian (Example 34.7): prior $\mathcal N(\mu,\sigma^2)$ , model $\mathcal N(\theta,1)$ , $Q_t = \mathcal N(\mu_t,\sigma_t^2)$ with $\mu_t = \frac{\mu/\sigma^2 + S_t}{1/\sigma^2 + t}$ and $\sigma_t^2 = (1/\sigma^2 + t)^{-1}$ . Here $S_{t+1}\mid S_t\sim\mathcal N(S_t + \mu_t,\ 1 + \sigma_t^2)$ .

Definition $k$ -armed Bayesian bandit environment

A tuple $(\mathcal E,\mathcal G,Q,P)$ : a measurable space of environments, a prior $Q$ , and a kernel $P = (P_{\nu i})$ from $\mathcal E\times[k]$ to $(\mathbb R,\mathfrak B(\mathbb R))$ giving each arm’s reward distribution. With policy $\pi$ , random elements $\nu, A_t, X_t$ satisfy:

$\nu\sim Q$ ;
$A_t\mid\nu,A_1,X_1,\ldots,X_{t-1}\sim\pi_t(\cdot\mid A_1,X_1,\ldots,X_{t-1})$ : the policy doesn’t see $\nu$ ;
$X_t\mid\nu,A_1,\ldots,A_t\sim P_{\nu A_t}$ .

Existence follows from Ionescu–Tulcea (Exercise 34.9); write $\mathbb P_{QP\pi}$ . Rewards are now dependent through the shared random $\nu$ . The kernel notation (rather than Chapter 4’s tuples) ensures that regret is measurable in $\nu$ (Exercise 34.7).

FormulaBandit posterior

If all $P_{\nu a}\ll\lambda$ with densities $p_{\nu a}$ , the canonical density $\prod_t\pi_t(a_t\mid\cdot)p_{\nu a_t}(x_t)$ gives

$Q(B\mid a_1,x_1,\ldots,a_t,x_t) = \frac{\int_B\prod_{s\le t}p_{\nu a_s}(x_s)\,dQ(\nu)}{\int_{\mathcal E}\prod_{s\le t}p_{\nu a_s}(x_s)\,dQ(\nu)} \tag{34.7}$

The policy terms cancel, exactly as in the divergence decomposition: the posterior depends on the actions only through which arms produced which rewards. The denominator is almost surely nonzero (Exercise 34.11).

ExampleBeta–Bernoulli bandits (Examples 34.8–34.9)

$\mathcal E = [0,1]^k$ , $P_{\nu i} = \mathcal B(\nu_i)$ , and a product $\mathrm{Beta}(\alpha,\beta)$ prior. The posterior is again a product:

$q(\theta\mid h_t)\propto\prod_{i=1}^k\theta_i^{\alpha + s_i(h_t) - 1}(1 - \theta_i)^{\beta + t_i(h_t) - s_i(h_t) - 1}$

with $s_i$ the successes and $t_i$ the pulls of arm $i$ . Each arm’s Beta is updated only from its own data.

DefinitionBayesian regret and Bayes-optimal policy

$\mathrm{BR}_n(\pi,Q) = \int_{\mathcal E}R_n(\pi,\nu)\,dQ(\nu),\qquad\mathrm{BR}_n^*(Q) = \inf_\pi\mathrm{BR}_n(\pi,Q)$

Minimising Bayesian regret is equivalent to maximising $\mathbb E_{QP\pi}\sum_tX_t$ , the Bayes-optimal policy. It need not exist, but $\varepsilon$ -optimal policies always do. Deterministic policies suffice (Exercise 34.10).

ExampleBayes-optimal regret can be strictly positive (Exercise 34.8)

Prior $\frac12\delta_{(1,0)} + \frac12\delta_{(0,1)}$ on two Bernoulli arms. Round 1 is a coin flip from the learner’s point of view, so every policy pays $\frac12$ : $\mathrm{BR}_n^*\ge\frac12 > 0$ . Zero Bayesian regret would require knowing $\nu$ ‘s best arm in advance. (Example worked here.)

WarningBayesian regret is less informative than frequentist regret

$R_n(\pi,\nu)\le f(\nu)$ for all $\nu$ implies $\mathrm{BR}_n\le\mathbb E_Q[f]$ , but a Bayesian regret bound says nothing about any particular $\nu$ . This argues for analysing Bayesian algorithms in the frequentist sense, not against using them.

TheoremWorst prior = minimax (Note 6; Sion; Exercise 34.16)

With $L(S,Q) = \iint R_n(\pi,\nu)\,Q(d\nu)\,S(d\pi)$ , which is bilinear in a distribution $S$ over policies and a prior $Q$ , Sion’s theorem gives $\sup_Q\inf_SL = \inf_S\sup_QL$ . For Bernoulli bandits, with a suitable topology on priors,

$\max_Q\mathrm{BR}_n^*(Q) = R_n^*(\mathcal E)$

The minimax regret equals the Bayesian regret under the least favourable prior. This bridges the adversarial and Bayesian views (Chapter 36).

RemarkBayesian interpretations of familiar algorithms (Note 5)

Ridge regression is the posterior mean under a Gaussian model with prior $\mathcal N(0,I/\lambda)$ , the same Gaussian prior behind the method of mixtures.
Exponential weights under log loss is Bayesian mixture prediction. Experts $\mu\in\mathcal M$ give predictive distributions. With prior $Q$ , the Bayes-optimal forecast is the posterior mixture $\xi(\cdot\mid y_{<t}) = \sum_\mu\mu(\cdot\mid y_{<t})\frac{\mu(y_{<t})Q(\mu)}{\sum_\nu\nu(y_{<t})Q(\nu)}$ (34.10), and the posterior is exactly exponential weights with $\eta = 1$ on cumulative log loss. With a uniform prior, $\xi(y_{1:n})\ge\mu(y_{1:n})/k$ , so the regret is at most $\log k$ for every sequence (Exercise 34.6). This is mixture coding in learning-theory clothing. For general losses the learning rate must be much more conservative.

Bayesian optimal regret (Chapter 35)

TheoremHow large is $\mathrm{BR}^*_n$ ?

For Bernoulli bandits:

Worst prior: $\sup_Q\mathrm{BR}_n^*(Q) = \Theta(\sqrt{kn})$ . The upper bound comes from MOSS, the lower bound from the prior implicit in the Assouad-style proof (Exercise 15.2).
Theorem 35.1 (fixed prior): for every $Q$ , $\limsup_n\mathrm{BR}^*_n(Q)/\sqrt n = 0$ , but some prior has $\liminf_n\mathrm{BR}^*_n(Q)/n^{1/2-\varepsilon} = \infty$ for all $\varepsilon > 0$ .
Regular priors: $\mathrm{BR}^*_n(Q) = \Theta(\log^2n)$ (Lai 1987).

Contrast: for each fixed $\nu$ the regret is $\Theta(\log n)$ . Averaging $\log n/\Delta$ over a prior with mass near $\Delta = 0$ is what produces the extra growth. The bad prior puts mass at least $c/\log(1/\Delta)$ on $\{\Delta_{\min}\le\Delta\}$ .

ProofFirst part (Exercise 35.1 hint)

Use a policy with $R_n(\nu)\le C\min\{\sqrt{kn},\ k\log n/\Delta_{\min}(\nu)\}$ . Split $\mathcal E$ into $\mathcal E_n = \{\Delta_{\min}\le\varepsilon_n\}$ and its complement. On $\mathcal E_n^c$ , $\frac{k\log n}{\varepsilon_n} = o(\sqrt n)$ . On $\mathcal E_n$ , $Q(\mathcal E_n)\sqrt{kn}$ , and $Q(\mathcal E_n)\to Q(\{\Delta_{\min} = 0\})$ , where ties cost nothing. Choose $\varepsilon_n\to0$ slowly.

∎

Optimal stopping

DefinitionFinite-horizon optimal stopping and the Snell envelope

For adapted integrable $(U_t)_{t\le n}$ , solve $\sup_{1\le\tau\le n}\mathbb E[U_\tau]$ over stopping times (35.1). The Snell envelope is

$E_n = U_n,\qquad E_t = \max\{U_t,\ \mathbb E[E_{t+1}\mid\mathcal F_t]\}$

the best value achievable from time $t$ on.

TheoremTheorem 35.2 — Stop when the envelope touches

$\tau = \min\{t : U_t = E_t\}$ is optimal. Proof idea (Exercise 35.2): $E_t$ is a supermartingale, it is a martingale while you shouldn’t stop, and optional stopping finishes the argument (Theorem 3.8).

DefinitionMarkov optimal stopping

For an infinite horizon, use Markov structure: a chain $S_t$ with kernel $(P_x)$ and reward $U_t = u(S_t)$ . The value function is $v(x) = \sup_\tau\mathbb E_x[U_\tau]$ (35.2).

TheoremTheorem 35.3 — Wald–Bellman equation

If $U_\infty = \lim_nU_n$ exists a.s. and $\sup_n\lvert U_n\rvert$ is integrable, then

$v(x) = \max\Big\{u(x),\ \int v(y)P_x(dy)\Big\}$

$v(S_n)\to U_\infty$ , and any $\tau$ that stops when $u(S_t)$ exceeds the continuation value $\int v\,dP_{S_t}$ and continues when it is below is optimal; either choice is fine at indifference, e.g. $\tau = \min\{t : v(S_t) = U_t\}$ . The conditions hold for ergodic chains with bounded utility, and for discounted reward sums. The proof is measure-theoretically delicate (Peskir–Shiryaev; Exercise 35.3).

IntuitionDynamic programming

Optimal stopping is dynamic programming: trade memory (value functions) for computation. The challenge is always the size of the state space on which the value function lives, so we look for sufficient statistics that shrink it.

One-armed Bayesian bandits

DefinitionSetting

Two arms: arm 2 is a Dirac at a known $\mu_2$ , arm 1 is uncertain with a prior. By Exercise 4.11, for a known horizon, retirement policies (play arm 1 until some time, then arm 2 forever) dominate all others, and deterministic ones suffice (Exercise 34.10). Retirement policies correspond bijectively to stopping times $\tau$ for arm 1’s reward stream $Z_1, Z_2, \ldots$ :

$\text{Bayesian reward} = \mathbb E[U_\tau],\qquad U_t = \sum_{s<t}Z_s + (n - t + 1)\mu_2$

The Bayesian one-armed bandit is an optimal stopping problem.

TheoremProposition 35.4 — Bayes-optimal retirement

If $Z_1$ is integrable, retire at $\tau = \min\{t : U_t = E_t\}$ (Snell envelope with $E_{n+1} = U_{n+1}$ ). Equivalently, with the value to go $W_t = E_t - \sum_{s<t}Z_s$ ,

$W_{n+1} = 0,\qquad W_t = \max\big\{(n - t + 1)\mu_2,\ \mathbb E[Z_t + W_{t+1}\mid\mathcal F_t]\big\} \tag{35.3}$

Retire at the first $t$ with $W_t = (n - t + 1)\mu_2$ : continue only while exploring is worth at least the sure payoff. If a sufficient statistic $S_t$ exists, then $W_t = w_t(S_t)$ (Exercise 35.4).

AlgorithmBernoulli rewards, Beta prior: exact $O(n^2)$ backwards induction

With $S_t = \sum_{s<t}Z_s$ and $p_t(s) = \frac{\alpha + s}{\alpha + \beta + t - 1}$ (the posterior mean): $w_{n+1}\equiv0$ and

$w_t(s) = \max\big\{(n - t + 1)\mu_2,\ p_t(s) + p_t(s)w_{t+1}(s + 1) + (1 - p_t(s))w_{t+1}(s)\big\}$

Compute for $s\in\{0, \ldots, t\}$ from $t = n$ down to 1. This is $O(n^2)$ , versus $O(n)$ for a frequentist stopping rule.

ExampleExperiment 35.1 — Bayesian versus frequentist retirement

$n = 500$ , $\mu_2 = \frac12$ , uniform prior. Frequentist rule: retire at the first $t\ge2$ with $\hat\mu_{t-1} < \mu_2$ and $d(\hat\mu_{t-1},\mu_2)\ge\frac{\log(n/t)}{t-1}$ (35.4, a KL confidence test). The Bayes-optimal rule has lower prior-averaged regret. The frequentist rule stops later because of its conservative interval, so it wins for $\mu_1 > \frac12$ and loses more for $\mu_1 < \frac12$ . Both are asymmetric even though the prior is symmetric: the problem itself is asymmetric.

AlgorithmGaussian rewards: approximate dynamic programming

Arm 1 is $\mathcal N(\nu,1)$ with prior $\mathcal N(\mu_P,\sigma_P^2)$ . After $t$ observations the posterior is $\mathcal N(\mu_t,\sigma_t^2)$ with

$\mu_t = \frac{\mu_P/\sigma_P^2 + \sum_{s\le t}x_s}{t + \sigma_P^{-2}},\qquad\sigma_t^2 = \big(t + \sigma_P^{-2}\big)^{-1} \tag{35.5}$

The posterior variance is deterministic, so the state is just the posterior mean: $W_t = w_t(\mu_{t-1})$ , with $w_{n+1} = 0$ and

$w_t(\mu) = \max\Big\{(n - t + 1)\mu_2,\ \mu + \mathbb E\big[w_{t+1}(\mu + \xi_t)\big]\Big\},\qquad\xi_t\sim\mathcal N\big(0,\ \sigma_{t-1}^2 - \sigma_t^2\big)$

The posterior mean moves by a Gaussian increment whose variance is the drop in posterior variance, $\sigma_{t-1}^2 - \sigma_t^2 = \sigma_{t-1}^2\sigma_t^2$ . There is no closed form, but $w_t$ is increasing, convex, tends to $(n - t + 1)\mu_2$ at $-\infty$ , and has slope $n - t + 1$ at $+\infty$ (Lemma 35.5). Approximate it piecewise quadratically on a grid $x_1 < \cdots < x_N$ , matching the endpoints and midpoint of each cell, so that the Gaussian integrals are analytic; use $(n - t + 1)\mu_2$ below $x_1$ and the linear asymptote above $x_N$ . Cost $O(Nn)$ .

RemarkUndiscounted one-armed Gittins index (Notes 7–8)

With horizon $n$ , the index $g_n(s) = \sup_{2\le\tau\le n}\frac{\mathbb E_s\sum_{t<\tau}r(S_t)}{\mathbb E_s[\tau - 1]}$ solves the one-armed problem: retire at the first $t$ with $g_{n-t+1}(S_t)\le\mu_2$ . Using $\arg\max_ig_{n-t+1}(S_i(t))$ for $k$ arms is no longer Bayes optimal, but works well and, for Gaussians, enjoys UCB-like frequentist regret (Lattimore 2016). Asymptotically the index behaves like the KL-UCB upper confidence bound (Burnetas–Katehakis 1997): optimism emerges from Bayesian optimality.

The Gittins index

WarningWhy $k$ arms are hard

Backwards induction on the joint sufficient statistics of all arms grows exponentially with $k$ . The finite-horizon Bayes-optimal policy is generally not an index policy. Gittins showed that changing the objective to geometrically discounted infinite-horizon reward makes the optimal policy an index policy, where each arm’s index depends only on that arm’s own state.

The discounted retirement game

DefinitionRetirement game and Gittins index

A Markov chain $(S_t)$ on a Borel space with kernel $(P_x)$ and reward $r : \mathcal S\to\mathbb R$ . Each round, either retire or pay a fixed charge $\gamma$ to collect $r(S_t)$ . With discount $\alpha\in(0,1)$ ,

$v_\gamma(x) = \sup_{\tau\ge1}\mathbb E_x\Big[\sum_{t=1}^{\tau-1}\alpha^{t-1}(r(S_t) - \gamma)\Big] \tag{35.7}$

assuming $\mathbb E_x\sum_t\alpha^{t-1}\lvert r(S_t)\rvert < \infty$ (Assumption 35.6). $v_\gamma(x)\ge0$ and is decreasing in $\gamma$ . The Gittins index (fair charge) is the largest charge at which you would still play at least once:

$g(x) = \inf\{\gamma : v_\gamma(x) = 0\} = \sup_{\tau\ge2}\frac{\mathbb E_x\big[\sum_{t=1}^{\tau-1}\alpha^{t-1}r(S_t)\big]}{\mathbb E_x\big[\sum_{t=1}^{\tau-1}\alpha^{t-1}\big]} \tag{35.8–35.9}$

(equivalence: Exercise 35.6).

Component	Detail
Signature	$g : \mathcal S\to\mathbb R$ , per arm, using only that arm’s chain
Meaning (35.9)	best achievable discounted average reward rate over a stopping time
Meaning (35.8)	the per-round fee that makes you indifferent to starting

LemmaLemma 35.7 — Structure of the retirement game

$v_\gamma(x) = \max\{0,\ r(x) - \gamma + \alpha\int v_\gamma(y)P_x(dy)\}$ (Wald–Bellman).
If $\gamma\le g(x)$ , the max is attained by continuing: $v_\gamma(x) = r(x) - \gamma + \alpha\int v_\gamma\,dP_x$ .
$\tau = \min\{t\ge2 : g(S_t)\le\gamma\}$ attains the supremum in (35.9): play while the index stays above the charge you started with.

The index theorem

DefinitionDiscounted bandit with Markov payoffs

$k$ independent chains on a common space with a common kernel (no loss of generality: take a disjoint union). Each round, observe all states, play $A_t$ , receive $r(S_{A_t}(t))$ . Only the played chain moves; the others are frozen. Maximise $\mathbb E_\pi\sum_t\alpha^{t-1}r(S_{A_t}(t))$ .

ExampleBayesian Bernoulli bandits as Markov chains (Example 35.8)

State $(x,y)$ = Beta posterior parameters, starting at $(1,1)$ . Transition to $(x+1,y)$ with probability $\frac x{x+y}$ , or to $(x,y+1)$ with probability $\frac y{x+y}$ . Reward $r(x,y) = \frac x{x+y}$ , the posterior mean. The state is the sufficient statistic and the reward is the posterior expected reward. A product prior makes the chains independent, and a frozen arm’s posterior doesn’t change: exactly the setting above (Exercise 35.8).

TheoremTheorem 35.9 — Gittins index theorem

Under Assumption 35.6 for every chain, the Gittins index policy $A_t\in\arg\max_ig(S_i(t))$ (ties arbitrary) maximises the expected discounted reward over all policies. For discounted Bayesian bandits with a product prior, it is Bayes optimal.

ProofPrevailing charges and interleavings

Notation: the prevailing charge of arm $i$ is $G^i(t) = \min_{s\le t}g(S_i(s))$ , the lowest index seen so far, which is non-increasing.

Part 1: Reward ≤ prevailing charge, with equality for Gittins. For each arm $i$ , $\mathbb E_\pi\sum_t\alpha^{t-1}r(S_i(t))\mathbb I\{A_t = i\}\le\mathbb E_\pi\sum_t\alpha^{t-1}G^i(t)\mathbb I\{A_t = i\}$ . Split arm $i$ ‘s plays into excursions $\mathcal T_j$ that start whenever its index drops to a new low $\gamma_j$ . During an excursion, $g(S_i(t))\ge\gamma_j = G^i(t)$ , so by Lemma 35.7(b), $r - \gamma_j = v_{\gamma_j}(S_i(t)) - \alpha\mathbb E[v_{\gamma_j}(S_i(t+1))\mid\mathcal F_t]$ . Summing over the excursion telescopes (frozen chains make consecutive plays of arm $i$ consecutive states), and since $v\ge0$ and $v_{\gamma_j}(S_i(\tau_j)) = 0$ , each excursion contributes at most 0. The Gittins policy plays each excursion to completion, exactly the optimal stopping time of Lemma 35.7(c), so its contribution is exactly 0.

Part 2: Interleaving decreasing sequences. Let $H_{iu} = \min_{v\le u}g(S_{iv})$ , arm $i$ ‘s prevailing charge after $u$ of its own plays. Its law doesn’t depend on the policy, and each $H_i$ is decreasing. Any policy collects the interleaving $I_t(H,A)$ , and by Hardy–Littlewood (Lemma 35.10) the discounted sum of an interleaving of decreasing sequences is maximised by greedily taking the largest available head. For Gittins, $\text{reward} = \mathbb E\sum\alpha^{t-1}I_t^*(H)$ . For any $\pi$ , $\text{reward}\le\mathbb E\sum\alpha^{t-1}I_t(H,A)\le\mathbb E\sum\alpha^{t-1}I_t^*(H)$ , the same value.

∎

IntuitionWhy an index can be optimal

Each arm can be summarised by a single “fair price per unit of discounted time”. Because discounting is geometric and idle arms are frozen, an arm’s future value stream doesn’t depend on when you play it, only on the order. Greedily playing the highest prevailing charge then maximises the discounted sum, by the rearrangement inequality.

WarningThe index theorem is brittle (Notes 6, 9)

Geometric discounting is essential. With a non-exponential $\alpha(t)$ , an arm’s index can change while you play other arms, which breaks the interleaving argument, and the optimal policy needn’t be an index policy.
Multiple plays per round: the theorem fails.
Restless bandits (all chains move, Whittle 1988): not index-optimal in general.
Finite horizon, no discounting: generally intractable. This is widely believed, though no lower bound on the complexity is known. Small cases are feasible: $n = 50$ , $k = 5$ Beta–Bernoulli is about $10^{11}$ states, storable on disk, which may be worth it in mission-critical applications.
Prior misspecification: Bayesian methods exploit their assumptions fully, which makes them brittle when the prior is wrong. Overly aggressive confidence is very costly in bandits.

RemarkDiscounting

Discounting models time preference (pizza tomorrow beats pizza next year), formalised by Samuelson (1937), who himself doubted its normative and descriptive value. It is rare in frequentist bandits but common in reinforcement learning, where it brings technical advantages. Discounted Markov-payoff bandits are special discounted MDPs (Chapter 38).

Computing the Gittins index: Varaiya’s algorithm

AlgorithmVaraiya’s algorithm (finite state space)

With transition matrix $P$ , reward vector $r$ , and for a continuation set $C$ , $(Q_C)_{ij} = P_{ij}\mathbb I_C(j)$ . By Lemma 35.7(c), state $i$ ‘s optimal stopping time stops on leaving the continuation region $C_i = \{j : g(j) > g(i)\}$ , so

$g(i) = \frac{\sum_{t\ge1}\alpha^{t-1}e_i^\top Q_{C_i}^{t-1}r}{\sum_{t\ge1}\alpha^{t-1}e_i^\top Q_{C_i}^{t-1}\mathbf 1} = \frac{e_i^\top(I - \alpha Q_{C_i})^{-1}r}{e_i^\top(I - \alpha Q_{C_i})^{-1}\mathbf 1}$

Compute indices in decreasing order:

the top state is $\arg\max_jr_j$ , with $g = \max_jr_j$ (stop after one step);
given the set $C$ of the $j$ states with the largest indices, the next is $\arg\max_{i\notin C}\frac{e_i^\top(I - \alpha Q_C)^{-1}r}{e_i^\top(I - \alpha Q_C)^{-1}\mathbf 1}$ , and that ratio is its index.

Cost $O(\lvert\mathcal S\rvert^4)$ with Gauss–Jordan elimination. For moderate $\alpha$ , truncating the sums (and pruning states unreachable before discounting makes them irrelevant) works well. Infinite state spaces are often discretised using their topology. Better algorithms exist (Chakravorty–Mahajan survey; Niño-Mora; Sonin), as do continuous-time and free-boundary approximations.

RemarkHistory

The first fully Bayesian analysis is the finite-horizon one-armed bandit by backwards induction (Bradt et al. 1956). The Gittins index appeared in 1979, with at least four proofs: Gittins, Whittle (1980), Weber (1992), Tsitsiklis (1994), surveyed by Frostig–Weiss (1999). Books: Gittins et al. (2011), Berry–Fristedt (1985, full of counterintuitive exact-Bayes results), Presman–Sonin (1990). Burnetas and Katehakis (2003) showed Bayes-optimal one-armed rules are asymptotically frequentist-style retirement rules.

Quick reference

Object	Statement	Note
Admissible	not dominated	Bayes-optimal (unique / full support) ⇒ admissible
Pareto ⇒ Bayes	finite $\mathcal E$ , convex loss set	supporting hyperplane = prior
Posterior existence	regular conditional distribution	Borel $\Theta$ ; unique a.e.
Posterior density	$q(\theta\mid x)\propto p_\theta(x)q(\theta)$	defines a version
Non-uniqueness	arbitrary on prior-null sets	matters for frequentist use
Gaussian conjugate	precisions add; precision-weighted means
Beta–Bernoulli	$(\alpha + x,\ \beta + 1 - x)$	unique
Exponential family	$e^{\eta S - A}$ ; conjugate $(x_0,n_0)\to(\frac{n_0x_0 + x}{n_0 + 1}, n_0 + 1)$	KL = Bregman of $A$
Bandit posterior	$\propto\prod_sp_{\nu a_s}(x_s)\,dQ$	policy cancels
Bayesian regret	$\int R_n(\pi,\nu)\,dQ(\nu)$	weaker than frequentist bounds
Worst prior	$\max_Q\mathrm{BR}_n^* = R_n^*$	Sion
Rates	$\sup_Q = \Theta(\sqrt{kn})$ ; fixed $Q$ : $o(\sqrt n)$ ; regular $Q$ : $\Theta(\log^2n)$
Snell envelope	$E_t = \max\{U_t,\mathbb E[E_{t+1}\mid\mathcal F_t]\}$	stop at $U_t = E_t$
Wald–Bellman	$v = \max\{u,\ \int v\,dP\}$	Markov stopping
One-armed	retirement = optimal stopping; $W_t$ recursion	Bernoulli $O(n^2)$
Gittins index	$\sup_{\tau\ge2}\frac{\mathbb E\sum_{t<\tau}\alpha^{t-1}r}{\mathbb E\sum_{t<\tau}\alpha^{t-1}}$	fair charge
Index theorem	$\arg\max_ig(S_i(t))$ optimal	geometric discount, frozen arms
Varaiya	$g(i) = \frac{e_i^\top(I - \alpha Q_C)^{-1}r}{e_i^\top(I - \alpha Q_C)^{-1}\mathbf 1}$	$O(\lvert\mathcal S\rvert^4)$

Facts to keep to hand

The Bayesian move puts the environment in the probability space. The prior trades off environments, and Bayes rules are (nearly) the admissible ones. The least favourable prior’s Bayes regret equals the minimax regret.
Posteriors need care, but rarely bite. Regular conditional distributions guarantee existence and densities give formulas. Non-uniqueness on null sets only matters when a frequentist analyses a fixed environment. Conjugate families (exponential families, with KL = Bregman of $A$ ) keep posteriors finite dimensional.
Bayesian regret is an average, not a guarantee. It is $o(\sqrt n)$ for any prior and about $\log^2n$ for regular ones, but it bounds no individual instance. Bayesian algorithms deserve frequentist analysis.
Bayes optimality is dynamic programming. One-armed problems are optimal stopping on sufficient statistics: exact for Beta–Bernoulli, approximate for Gaussians. Many arms are intractable, except that geometric discounting with frozen arms collapses everything to per-arm Gittins indices, by an interleaving (rearrangement) argument.

References

Lattimore & Szepesvári, Bandit Algorithms — Chapters 34–35
Ghosal & van der Vaart, Fundamentals of Nonparametric Bayesian Inference (2017) — rigorous posteriors
Gittins, Glazebrook & Weber, Multi-armed Bandit Allocation Indices (2011)
Peskir & Shiryaev, Optimal Stopping and Free-Boundary Problems (2006)