Stochastic Processes, Markov Chains, and Stochastic Bandits

Corresponds to Lattimore & Szepesvári, Chapters 3–4.

Motivation: from i.i.d. trials to adaptive interaction

The probability notes so far mostly handle independent trials, plus one specific dependent process, the Poisson process. A bandit algorithm breaks independence by design. Its $t$ -th choice depends on every reward seen so far, so the sequence of actions and rewards is a stochastic process adapted to a growing history, not an i.i.d. sample.

Question	Tool
Does an infinite sequence with given joint laws even exist?	Borel spaces, projective families, Ionescu–Tulcea
How do we describe “the next state is drawn given the current one”?	Probability kernels, Markov chains
How do we reason about quantities whose mean is preserved (or eroded) over time?	Martingales
Can a data-dependent decision about when to stop beat a fair game?	Stopping times, Doob’s optional stopping
What exactly is a bandit, a policy, and a measure of performance?	The canonical bandit model, regret

IntuitionThe central questions

What does it take, mathematically, for “an agent interacts with an unknown random environment for $n$ rounds” to be a well-defined random experiment? And what single number should judge how well the agent did?

NoteOptional on first reading

The book marks Chapter 3, and Sections 4.6–4.7 (the canonical model), as skippable. Their job is to guarantee that the objects used everywhere else exist and are well defined. The two results used constantly later are the regret decomposition and optional stopping / the maximal inequality.

Existence of infinite sequences

The problem. Writing “let $(X_n)_{n=1}^\infty$ be independent standard Gaussians” assumes there is some probability space carrying infinitely many such variables. With finitely many variables, product measures settle this. With infinitely many, it needs an argument.

DefinitionIsomorphic measurable spaces; Borel space

$(\mathcal X,\mathcal F)$ and $(\mathcal Y,\mathcal G)$ are isomorphic if there is a bijection $f:\mathcal X\to\mathcal Y$ with $f$ $\mathcal F/\mathcal G$ -measurable and $f^{-1}$ $\mathcal G/\mathcal F$ -measurable. A Borel space is a measurable space isomorphic to $(A,\mathfrak B(A))$ for some Borel set $A\in\mathfrak B(\mathbb R)$ .

RemarkNot a strong assumption

$(\mathbb R^n,\mathfrak B(\mathbb R^n))$ is a Borel space, as is every measurable subset of it. Every Polish space (separable and completely metrizable) is Borel. Some authors say “standard Borel space” and define it through Polish spaces. Nothing in the book needs a non-Borel space.

TheoremTheorem 3.1 — i.i.d. sequences exist on the unit interval

Let $\mu$ be a probability measure on a Borel space $\mathcal S$ , and $\lambda$ Lebesgue measure on $([0,1],\mathfrak B([0,1]))$ . There are independent random elements $X_1,X_2,\ldots$ on $([0,1],\mathfrak B([0,1]),\lambda)$ with law $\lambda_{X_t} = \mu$ for every $t$ .

ProofSketch: reshuffle the binary digits of a uniform number (case

\mu

= uniform)

Step 1: Digits of a uniform number are fair coin flips. Write $x = \sum_{t\ge1}F_t(x)2^{-t}$ (binary expansion). Under $\lambda$ , each $F_t$ is Bernoulli $(\frac12)$ , and $F_1,F_2,\ldots$ are independent. Fixing the first $t$ digits pins $x$ to an interval of length $2^{-t}$ .

Step 2: Deal the digits into infinitely many rows. Arrange the digits in a triangular grid, traversing anti-diagonals:

	col 1	col 2	col 3	col 4
row 1	$F_1$	$F_2$	$F_4$	$F_7$
row 2	$F_3$	$F_5$	$F_8$	⋯
row 3	$F_6$	$F_9$	⋯
row 4	$F_{10}$	⋯

Let $X_{m,t}$ be the $t$ -th entry of row $m$ .

Step 3: Reassemble each row into a uniform number. $X_m = \sum_{t\ge1}2^{-t}X_{m,t}$ . Each row is an independent fair-bit sequence, so $X_m$ is uniform. Different rows use disjoint digits, so the $X_m$ are independent.

General $\mu$ on a Borel space: push each uniform $X_m$ through a measurable map with law $\mu$ (inverse CDF, composed with the isomorphism). The missing details are Exercise 3.1.

∎

IntuitionOne uniform number holds infinitely many

A single draw from $[0,1]$ contains infinitely many independent fair bits, which is enough randomness for infinitely many independent uniforms. Compare the probability integral transform: a uniform’s binary digits are incompressible fair bits.

Stochastic processes and projective families

DefinitionStochastic process

A collection $\{X_t : t\in T\}$ of random variables on one probability space $(\Omega,\mathcal F,\mathbb P)$ . In this book $T$ is always countable, and usually $T = \mathbb N$ .

TheoremTheorem 3.2 — Existence from consistent finite-dimensional laws (Daniell)

For each $n\in\mathbb N^+$ let $(\Omega_n,\mathcal F_n)$ be a Borel space and $\mu_n$ a probability measure on $\Omega_1\times\cdots\times\Omega_n$ , with the projective (consistency) condition

$\mu_{n+1}(A\times\Omega_{n+1}) = \mu_n(A)\qquad\text{for all measurable } A\subseteq\Omega_1\times\cdots\times\Omega_n \tag{3.1}$

Then there are a probability space and random elements $X_t:\Omega\to\Omega_t$ with $\mathbb P_{X_1,\ldots,X_n} = \mu_n$ for every $n$ .

IntuitionConsistent snapshots glue into a whole

Condition (3.1) says the law of the first $n$ coordinates, read off from the $(n+1)$ -coordinate law by ignoring the last coordinate, is $\mu_n$ . If every finite-length snapshot agrees with the next one, there is one infinite process whose snapshots they all are. The general version is Kolmogorov’s extension theorem.

CorollaryTheorem 3.1 again

Take $\mu_n = \mu^{\otimes n}$ , the $n$ -fold product. It is obviously projective, so Theorem 3.2 delivers an i.i.d. sequence.

Probability kernels and Markov chains

DefinitionProbability (Markov) kernel

A probability kernel from $(\mathcal X,\mathcal F)$ to $(\mathcal Y,\mathcal G)$ is a map $K:\mathcal X\times\mathcal G\to[0,1]$ such that

$K(x,\cdot)$ is a probability measure for every $x$ , and
$K(\cdot,A)$ is $\mathcal F$ -measurable for every $A\in\mathcal G$ .

Equivalent notations: $K(x,A) = K(A\mid x) = K_x(A)$ .

Component	Detail
Signature	$K:\mathcal X\times\mathcal G\to[0,1]$
First argument	The current state $x$ .
Second argument	An event $A$ in the next space.
Output	The probability the next element lands in $A$ , given $x$ .
Finite-state special case	A transition matrix, $K(i,\{j\}) = P_{ij}$ (Markov chains)
Statistics reading	A parametric family $\{P_\theta\}$ is a kernel from $\Theta$ . A Bayesian posterior $P(\cdot\mid x)$ is a kernel from observations to parameters.

IntuitionA kernel is a randomized function

A function maps $x$ to one $y$ . A kernel maps $x$ to a distribution over $y$ , and the next value is sampled $Y\sim K(x,\cdot)$ . Condition 2 just says that “how likely is $A$ ” depends measurably on where you start.

DefinitionComposing kernels

Measure ⊗ kernel: for a measure $P$ on $\mathcal X$ and a kernel $K$ from $\mathcal X$ to $\mathcal Y$ , $(P\otimes K)(A) = \int_{\mathcal X}\int_{\mathcal Y}\mathbb I_A((x,y))\,K(x,dy)\,dP(x)$ is a measure on $\mathcal X\times\mathcal Y$ : draw $x\sim P$ , then $y\sim K(x,\cdot)$ .
Kernel ⊗ kernel: $(K_1\otimes K_2)(x,A) = \int_{\mathcal Y}\int_{\mathcal Z}\mathbb I_A((y,z))\,K_2(y,dz)\,K_1(x,dy)$ is a kernel from $\mathcal X$ to $\mathcal Y\times\mathcal Z$ .
Chaining: if $K_2$ goes from $\mathcal X\times\mathcal Y$ to $\mathcal Z$ , then $P\otimes K_1\otimes K_2$ is a probability measure on $\mathcal X\times\mathcal Y\times\mathcal Z$ . Each stage may depend on the whole history.

TheoremTheorem 3.3 — Ionescu–Tulcea

Let $(\Omega_n,\mathcal F_n)_{n\ge1}$ be measurable spaces, $K_1$ a probability measure on $\Omega_1$ , and for $n\ge2$ let $K_n$ be a kernel from $\prod_{t<n}\Omega_t$ to $\Omega_n$ . Then there are a probability space and random elements $X_t:\Omega\to\Omega_t$ with

$\mathbb P_{X_1,\ldots,X_n} = \bigotimes_{t=1}^nK_t\qquad\text{for all } n$

ImportantWhy bandits need Ionescu–Tulcea

A bandit interaction is exactly a chain of kernels: the policy picks an action given the history, then the environment draws a reward given the action, then the policy picks again, and so on. Ionescu–Tulcea says such a history-dependent chain defines a genuine infinite random process. Unlike Theorem 3.2, it needs no Borel assumption.

DefinitionHomogeneous Markov chain

A sequence $(X_t)_{t\ge1}$ in a state space $(\mathcal X,\mathcal F)$ with $X_1\sim\mu_0$ and

$\mathbb P(X_{t+1}\in\cdot\mid X_1,\ldots,X_t) = \mathbb P(X_{t+1}\in\cdot\mid X_t) = \mu(X_t,\cdot)\quad\text{almost surely}$

for one fixed kernel $\mu$ from $\mathcal X$ to itself. Given the present, the past is irrelevant for predicting the future.

RemarkThree small points

“Homogeneous” means the kernel doesn’t change with $t$ . A time-varying kernel is a cosmetic generalization: add the time to the state.
I.i.d. is a Markov chain: if $\mu(x,\cdot) = \mu_0$ for all $x$ , Ionescu–Tulcea gives yet another construction of i.i.d. sequences.
Terminology: the book says “Markov chain” for any state space in discrete time. Some authors reserve “process” for uncountable state spaces; everyone says “process” for continuous time.

NoteWhat Markov-chain theory studies

The central questions concern long-run behaviour: does the law of $X_t$ converge to a fixed distribution, and how fast? The book defers this to Chapters 37–38 (finite state spaces). For the information-theoretic view of finite chains, see stationary distributions.

Martingales and stopping times

DefinitionMartingale, supermartingale, submartingale

Let $\mathbb F = (\mathcal F_t)_t$ be a filtration and $(X_t)$ an $\mathbb F$ -adapted sequence ( $X_t$ is $\mathcal F_t$ -measurable). Then $(X_t)$ is an $\mathbb F$ -martingale if

every $X_t$ is integrable, and
$\mathbb E[X_t\mid\mathcal F_{t-1}] = X_{t-1}$ almost surely for all $t\ge2$ .

With $\le$ in place of $=$ it is a supermartingale; with $\ge$ , a submartingale. The index often starts at $t = 0$ .

Process	Conditional drift	Reads as
Martingale	$\mathbb E[X_t\mid\mathcal F_{t-1}] = X_{t-1}$	A fair game.
Supermartingale	$\le X_{t-1}$	Unfavourable to the gambler.
Submartingale	$\ge X_{t-1}$	Favourable to the gambler.

IntuitionThe names favour the casino

“Super” is the casino’s view: a supermartingale is a game that is super for the house. A useful mental model: $\mathcal F_t$ is everything known at time $t$ , and a martingale is a quantity whose best forecast of tomorrow is today’s value.

ExampleExample 3.5 — Fair coin winnings

$Y_1,Y_2,\ldots$ are independent Rademacher variables ( $\mathbb P(Y_t = \pm1) = \frac12$ ), $S_t = \sum_{s\le t}Y_s$ , and $\mathcal F_t = \sigma(Y_1,\ldots,Y_t)$ . Then $\mathbb E[S_t\mid\mathcal F_{t-1}] = S_{t-1} + \mathbb E[Y_t] = S_{t-1}$ , so the winnings are a martingale.

RemarkA martingale we’ve already met

In the portfolio note, the ratio of any causal investor’s wealth to the log-optimal investor’s, $S_n/S_n^*$ , is a positive supermartingale. That is exactly the statement that no strategy expects to gain on the log-optimal one.

Stopping times

The question. Can a gambler turn a fair game into a profitable one by choosing cleverly when to stop? At the end of round $t$ they set $\delta_t = 1$ (stop) or $0$ (continue) using only what they have seen, and stop at $\tau = \min\{t:\delta_t = 1\}$ .

DefinitionStopping time; stopped σ-algebra (Def. 3.6)

A random variable $\tau$ with values in $\mathbb N\cup\{\infty\}$ is an $\mathbb F$ -stopping time if $\mathbb I\{\tau\le t\}$ is $\mathcal F_t$ -measurable for all $t$ . The information at time $\tau$ is

$\mathcal F_\tau = \{A\in\mathcal F_\infty : A\cap\{\tau\le t\}\in\mathcal F_t\ \text{for all } t\}$

Component	Detail
Signature	$\tau:\Omega\to\mathbb N\cup\{\infty\}$
Requirement	Whether you have stopped by time $t$ is decided by time- $t$ information.
Forbidden	Peeking at the future, and injecting outside randomness beyond what $\mathbb F$ contains.
$\infty$ allowed	The book lets $\tau = \infty$ with positive probability. Some authors require $\tau < \infty$ a.s. and call the general version a Markov time. Also called optional times.

ExampleExample 3.7 — Which rules are stopping times

$\tau = \min\{t : S_t = 100\}$ (“stop when up $100”) is a stopping time: you know when you hit 100.
$\tau = \min\{t : S_{t+1} = -1\}$ (“stop just before losing”) is not: it needs tomorrow’s result.

NoteProperties of $\mathcal F_\tau$ (Exercise 3.7)

$\mathcal F_\tau$ is a σ-algebra. If $\tau\equiv k$ then $\mathcal F_\tau = \mathcal F_k$ . If $\tau_1\le\tau_2$ then $\mathcal F_{\tau_1}\subseteq\mathcal F_{\tau_2}$ . $\tau$ is $\mathcal F_\tau$ -measurable. For adapted $(X_t)$ , $X_\tau$ is $\mathcal F_\tau$ -measurable, and $\mathcal F_\tau$ is the smallest σ-algebra with this property for all adapted sequences. Limits of increasing stopping times are stopping times (Exercise 3.6).

TheoremTheorem 3.8 — Doob’s optional stopping

Let $(X_t)_{t\in\mathbb N}$ be an $\mathbb F$ -martingale and $\tau$ an $\mathbb F$ -stopping time, with at least one of:

bounded time: $\mathbb P(\tau > n) = 0$ for some $n$ ;
finite mean time, bounded increments: $\mathbb E[\tau] < \infty$ and $\mathbb E[|X_{t+1} - X_t|\mid\mathcal F_t]\le c$ a.s. on $\{\tau > t\}$ ;
bounded stopped process: $|X_{t\wedge\tau}|\le c$ a.s. for all $t$ .

Then $X_\tau$ is a.s. well defined and $\mathbb E[X_\tau] = \mathbb E[X_0]$ . For a super- or submartingale, the equality becomes $\le$ or $\ge$ respectively.

ImportantYou can’t beat a fair game by stopping cleverly

If $S_\tau$ is well defined, then either $\mathbb E[\tau] = \infty$ or $\mathbb E[S_\tau] = 0$ . “Gamblers trying to outsmart the casino would need to live a very long life.”

ExampleThe conditions can’t be dropped: doubling bets (Exercise 3.2)

Let $S_t = \sum_{s\le t}X_s2^{s-1}$ with $X_s$ Rademacher, so the stake doubles each round. This is a martingale. Stop at $\tau = \min\{t : S_t = 1\}$ . If the first win comes at round $t$ , then $S_t = 2^{t-1} - (2^{t-1} - 1) = 1$ . So $\tau$ is Geometric $(\frac12)$ : finite, with $\mathbb E\tau = 2$ . Yet $\mathbb E[S_\tau] = 1\ne0 = \mathbb E[S_0]$ . There’s no contradiction: the increments $2^t$ are unbounded (condition 2 fails), and the stopped process can sink arbitrarily low before recovering (condition 3 fails). This is the martingale (“double after a loss”) betting system, and it needs unlimited credit. (Worked here; the book leaves it as an exercise.)

ExampleGambler’s ruin, the martingale way

Start a fair $\pm1$ walk at $i$ and stop at $\tau$ , the first time it hits 0 or $N$ . The stopped walk stays in $[0,N]$ , so condition 3 holds and $\mathbb E[S_\tau] = i$ . But $S_\tau\in\{0,N\}$ , so $N\cdot\mathbb P(\text{reach } N) = i$ , i.e. $\mathbb P(\text{reach }N) = i/N$ . This matches the $p = \frac12$ case of first-step analysis with no recursion. (Not in the book.)

The maximal inequality

TheoremTheorem 3.9 — Maximal inequality for nonnegative supermartingales

If $(X_t)_{t\ge0}$ is a supermartingale with $X_t\ge0$ a.s., then for any $\varepsilon > 0$ ,

$\mathbb P\Big(\sup_{t\in\mathbb N}X_t\ge\varepsilon\Big)\le\frac{\mathbb E[X_0]}\varepsilon$

ProofStop at the first crossing, then apply optional stopping

Step 1: A bounded stopping time. Let $A_n = \{\sup_{t\le n}X_t\ge\varepsilon\}$ and $\tau = (n+1)\wedge\min\{t\le n : X_t\ge\varepsilon\}$ , with $\tau = n+1$ if there is no crossing. Then $\tau\le n+1$ surely, so condition 1 applies.

Step 2: Optional stopping, then drop the no-crossing part.

$\mathbb E[X_0]\ge\mathbb E[X_\tau]\ge\mathbb E[X_\tau\mathbb I\{\tau\le n\}]\ge\mathbb E[\varepsilon\,\mathbb I\{\tau\le n\}] = \varepsilon\,\mathbb P(A_n)$

The second inequality uses $X\ge0$ . The third holds because at a crossing time $X_\tau\ge\varepsilon$ .

Step 3: Let $n\to\infty$ . The $A_n$ increase to $\{\sup_tX_t\ge\varepsilon\}$ , so continuity of probability finishes it.

∎

IntuitionMarkov’s inequality for the whole path, for free

Markov’s inequality plus the supermartingale property bound one time: $\mathbb P(X_n\ge\varepsilon)\le\mathbb E[X_0]/\varepsilon$ (3.2). The maximal inequality bounds the chance of ever crossing, at no extra cost. The proof is Markov’s inequality applied to $X_\tau$ , with optional stopping supplying the expectation. It is what makes “with probability $1-\delta$ , at all times simultaneously” statements possible, which matters for anytime-valid confidence bounds later.

WarningNonnegativity is essential (Exercise 3.4)

Without $X_t\ge0$ , the bound fails for supermartingales in general.

TheoremTheorem 3.10 — Submartingale version

If $(X_t)_{t=0}^n$ is a submartingale with $X_t\ge0$ , then $\mathbb P\big(\max_{t\le n}X_t\ge\varepsilon\big)\le\frac{\mathbb E[X_n]}\varepsilon$ . The bound uses the last value rather than the first (the proof is Exercise 3.8).

Conditional distributions done properly

WarningConditional expectations are only unique almost surely

For each fixed event $A$ , $\mathbb P(X\in A\mid Y)$ is determined only up to a null set, and that null set may depend on $A$ . With uncountably many $A$ ‘s, the exceptions can pile up, so $A\mapsto\mathbb P(X\in A\mid Y)$ need not be a measure for any particular outcome.

TheoremTheorem 3.11 — Regular conditional distributions exist

If $X$ takes values in a Borel space, there is a probability kernel $K$ from the space of $Y$ to that of $X$ with $K(\cdot\mid Y) = \mathbb P(X\in\cdot\mid Y)$ almost surely. It is unique up to a $\mathbb P_Y$ -null set of $y$ ‘s. Write $\mathbb P_{X\mid Y}$ for $K$ . Then

$\mathbb P_{X,Y} = \mathbb P_Y\otimes\mathbb P_{X\mid Y}$

This is the chain rule for probability measures, the converse of Ionescu–Tulcea. Borel is sufficient but not necessary; Halmos gives an example where no regular version exists.

TheoremTheorem 3.12 — Disintegration

If $K$ is a regular version of $\mathbb P(X\in\cdot\mid\mathcal G)$ , $Y$ is $\mathcal G$ -measurable, and $\mathbb E|f(X,Y)| < \infty$ , then

$\mathbb E[f(X,Y)\mid\mathcal G] = \int_{\mathcal X}f(x,Y)\,K(dx\mid\cdot)\quad\text{a.s.}$

With $\mathcal G = \sigma(Y)$ : to average $f(X,Y)$ given $Y$ , freeze $Y$ and integrate $x$ against the conditional law. This is the measure-theoretic version of conditional LOTUS.

Stochastic bandits: core assumptions

DefinitionStochastic bandit

A stochastic bandit is a collection of reward distributions $\nu = (P_a : a\in\mathcal A)$ , one per action (arm) in the action set $\mathcal A$ .

flowchart LR
  L["Learner (policy)"] -->|"action A_t"| E["Environment nu"]
  E -->|"reward X_t drawn from P_A_t"| L
  L --> H["History A1 X1 ... At Xt feeds the next choice"]

DefinitionThe interaction protocol

Over $n$ rounds (possibly $n = \infty$ ), the learner picks $A_t\in\mathcal A$ , and the environment returns $X_t\in\mathbb R$ . The outcomes must satisfy:

Environment: the conditional law of $X_t$ given $A_1,X_1,\ldots,A_{t-1},X_{t-1},A_t$ is $P_{A_t}$ . The reward depends only on the arm pulled now.
Learner: the conditional law of $A_t$ given $A_1,X_1,\ldots,A_{t-1},X_{t-1}$ is $\pi_t(\cdot\mid A_1,X_1,\ldots,A_{t-1},X_{t-1})$ , for a sequence of kernels $\pi_1,\pi_2,\ldots$ called the policy. The learner can’t see the future.

IntuitionTwo kernels taking turns

The policy is a kernel from the history to actions; the environment is a kernel from actions to rewards. Their alternation is exactly the setting of Ionescu–Tulcea, which is why a joint law on $A_1,X_1,A_2,X_2,\ldots$ exists (The canonical bandit model).

The learning objective

The learner wants a large total reward $S_n = \sum_{t=1}^nX_t$ . This is not yet an optimization problem, for three reasons:

Obstacle	Resolution
Unknown horizon $n$	Usually mild: design for known $n$ , then convert generically (e.g. the doubling trick) with little loss.
$S_n$ is random, so “maximize” needs a utility on distributions	Default: maximize $\mathbb E[S_n]$ (risk-neutral). Variance and tails come up occasionally.
The reward distributions are unknown	The real heart of the bandit problem: Knowledge and environment classes.

ExampleExpected value is a choice, not a law of nature

Learner B has a higher mean revenue than learner A, but a real chance of earning less than A’s worst outcome. A risk-averse company might prefer A. The book’s default is the expected value.

RemarkRisk and utility

Prescriptive theory: the von Neumann–Morgenstern axioms say a rational (self-consistent) decision maker maximizes expected utility, so decision makers differ only in their utility functions.
Descriptive theory: people don’t actually behave that way. Prospect theory (Kahneman–Tversky) describes how people really weigh small probabilities.
Finance: Markowitz rejected expected return, since maximizing it puts everything in a single stock, and proposed mean–variance portfolios. Value-at-risk and conditional value-at-risk (CVaR, favoured for its optimization properties) are relatives. Compare the log-utility argument for reinvested wealth.

Knowledge and environment classes

The problem. A policy that is optimal for one bandit can be terrible for another. What the learner knows in advance is encoded as an environment class $\mathcal E$ with $\nu\in\mathcal E$ guaranteed.

DefinitionUnstructured bandits

$\mathcal E$ is unstructured if $\mathcal A$ is finite and $\mathcal E = \times_{a\in\mathcal A}\mathcal M_a$ , a product of per-arm sets of distributions. Playing arm $a$ then reveals nothing about any other arm.

Name	Symbol	Arms are
Bernoulli	$\mathcal E_B^k$	$\mathcal B(\mu_i)$ , $\mu\in[0,1]^k$
Uniform	$\mathcal E_U^k$	$\mathcal U(a_i,b_i)$ , $a_i\le b_i$
Gaussian, known variance	$\mathcal E_N^k(\sigma^2)$	$\mathcal N(\mu_i,\sigma^2)$
Gaussian, unknown variance	$\mathcal E_N^k$	$\mathcal N(\mu_i,\sigma_i^2)$
Finite variance	$\mathcal E_V^k(\sigma^2)$	any $P_i$ with $\mathrm{Var}\le\sigma^2$
Finite kurtosis	$\mathcal E_{\mathrm{Kurt}}^k(\kappa)$	$\mathbb E[(X-\mathbb EX)^4]/\mathrm{Var}[X]^2\le\kappa$
Bounded support	$\mathcal E_{[a,b]}^k$	$\mathrm{Supp}(P_i)\subseteq[a,b]$
Subgaussian	$\mathcal E_{SG}^k(\sigma^2)$	$\sigma$ -subgaussian (concentration-of-measure-for-bandits)

DefinitionParametric versus nonparametric

A class is parametric if finitely many numbers describe each member (Bernoulli, Gaussian) and nonparametric otherwise (finite variance, subgaussian). Classes nest: Bernoulli ⊂ bounded support ⊂ subgaussian, and Bernoulli ⊂ finite variance.

IntuitionBigger classes are harder

A learner that must work for every member of a larger class has less to exploit. Much of finite-armed bandit theory quantifies exactly how much harder.

DefinitionStructured bandits

Any class that is not a product set is structured: pulling one arm can reveal information about others.

ExampleThree structured classes

Example 4.1 — Mirror-image arms: $\mathcal E = \{(\mathcal B(\theta),\mathcal B(1-\theta)):\theta\in[0,1]\}$ . Playing either arm teaches you both means.
Example 4.2 — Stochastic linear bandit: $\mathcal A\subseteq\mathbb R^d$ , and arm $a$ pays $\mathcal N(\langle a,\theta\rangle,1)$ for an unknown $\theta\in\mathbb R^d$ . Even with a huge action set, playing $d$ actions that span $\mathbb R^d$ identifies $\theta$ .
Example 4.3 — Paths through a failing graph: each edge $e$ survives independently with unknown probability $\theta_e$ . The actions are paths from vertex 1 to vertex $|V|$ , and a path pays $\mathcal B\big(\prod_{e\in a}\theta_e\big)$ (success iff every edge survives). Paths share edges, so each trial is informative about many paths. This is the series reliability model turned into a learning problem.

ImportantInformation without play

The defining feature of structured bandits: the learner can learn about an action without ever playing it.

The regret

DefinitionMeans, optimal mean, regret

$\mu_a(\nu) = \int x\,dP_a(x)$ and $\mu^*(\nu) = \max_a\mu_a(\nu)$ . Assume all means exist and are finite, and that the argmax is nonempty. The regret of policy $\pi$ on $\nu$ over $n$ rounds is

$R_n(\pi,\nu) = n\mu^*(\nu) - \mathbb E\Big[\sum_{t=1}^nX_t\Big] \tag{4.1}$

with the expectation under the joint law induced by $\pi$ and $\nu$ .

Component	Detail
Signature	$R_n : \Pi\times\mathcal E\to[0,\infty)$
Inputs	A policy, an environment, a horizon.
Output	Expected shortfall relative to always pulling a best arm.
Equivalent to	Maximizing $\mathbb E[S_n]$ ; the normalization just makes results readable.

LemmaLemma 4.4 — Basic properties

$R_n(\pi,\nu)\ge0$ for every policy.
The policy that always plays an arm in $\arg\max_a\mu_a$ has $R_n = 0$ .
If $R_n(\pi,\nu) = 0$ , then $\mathbb P(\mu_{A_t} = \mu^*) = 1$ for all $t\le n$ .

(Proof: Exercise 4.1.)

IntuitionZero regret means knowing the answer

Part 3 says regret 0 is possible only if the learner already knows an optimal arm. Every real learner pays something to find out. The question is how little.

DefinitionRegret targets, from weak to strong

Target	Statement	Meaning
Sublinear	$\lim_n R_n(\pi,\nu)/n = 0$ for all $\nu\in\mathcal E$	Eventually picks an optimal arm almost every round.
Uniform polynomial	$R_n(\pi,\nu)\le Cn^p$ for all $\nu$ , some $p < 1$ (4.2)	Worst-case guarantee.
Instance-dependent	$R_n(\pi,\nu)\le C(\nu)f(n)$ for all $n,\nu$ (4.3)	Separates instance difficulty from horizon growth.

Both $C$ and $f$ should be as small as possible. Most of the book is about finding the achievable $(C, f)$ pairs.

IntuitionEvery algorithm is an estimation schedule

To keep regret small, find the best arm: play each arm enough to estimate its mean, then favour the apparent best. The whole question is how many pulls of each arm buy enough statistical certainty (explore-then-commit-and-ucb-algorithms).

DefinitionBayesian regret

Given a prior $Q$ on a σ-algebra over $\mathcal E$ ,

$BR_n(\pi,Q) = \int_{\mathcal E}R_n(\pi,\nu)\,dQ(\nu) \tag{4.4}$

provided $R_n$ is measurable. Once the prior and horizon are fixed, minimizing it is a plain optimization problem. The book mostly studies the frequentist regret (4.1), and treats Bayesian methods in Chapters 34–36.

DefinitionRandom regret and pseudo-regret

$\hat R_n = n\mu^* - \sum_{t=1}^nX_t\quad(\text{random regret}),\qquad \bar R_n = n\mu^* - \sum_{t=1}^n\mu_{A_t}\quad(\text{pseudo-regret})$

$R_n = \mathbb E[\hat R_n] = \mathbb E[\bar R_n]$ . Expectations erase randomness, so risk measures must be built on one of these random versions. The pseudo-regret filters out reward noise and so arguably measures the policy’s skill. Both are highly skewed, so variance is a poor risk summary: it penalizes upside risk and misses the skew.

Decomposing the regret

DefinitionGap and pull count

The suboptimality gap (action gap, immediate regret) of arm $a$ is $\Delta_a = \mu^* - \mu_a\ge0$ , which is zero for optimal arms. The pull count after round $t$ is $T_a(t) = \sum_{s=1}^t\mathbb I\{A_s = a\}$ .

WarningPull counts are random even for deterministic policies

After round 1, $A_t$ depends on the random rewards already seen, so $T_a(n)$ inherits their randomness.

TheoremLemma 4.5 — Regret decomposition

For any policy and environment with $\mathcal A$ finite or countable,

$R_n = \sum_{a\in\mathcal A}\Delta_a\,\mathbb E[T_a(n)] \tag{4.5}$

ProofConvert a sum over rounds into a sum over arms

Step 1: Insert indicators. For each $t$ , $\sum_a\mathbb I\{A_t = a\} = 1$ , so $S_n = \sum_t\sum_aX_t\mathbb I\{A_t = a\}$ and

$R_n = n\mu^* - \mathbb E[S_n] = \sum_{a}\sum_{t=1}^n\mathbb E\big[(\mu^* - X_t)\mathbb I\{A_t = a\}\big] \tag{4.6}$

Step 2: Condition on the action. Given $A_t$ , the reward has mean $\mu_{A_t}$ (assumption 1 of the protocol), so

$\mathbb E\big[(\mu^* - X_t)\mathbb I\{A_t = a\}\mid A_t\big] = \mathbb I\{A_t = a\}(\mu^* - \mu_{A_t}) = \mathbb I\{A_t = a\}\Delta_a$

Step 3: Total expectation, then sum over $t$ . $\sum_t\mathbb E[\mathbb I\{A_t = a\}]\Delta_a = \Delta_a\mathbb E[T_a(n)]$ .

∎

ImportantThe identity behind almost every bandit proof

Regret is a gap-weighted count of mistakes. To keep it small, pull each suboptimal arm a number of times that shrinks as its gap grows. Analyzing an algorithm almost always reduces to bounding $\mathbb E[T_a(n)]$ for each suboptimal $a$ .

TheoremLemma 4.6 — Uncountable action sets

With $(\mathcal A,\mathcal G)$ measurable, define the expected-pull measure $G(U) = \mathbb E\big[\sum_{t=1}^n\mathbb I\{A_t\in U\}\big]$ . Then, provided everything is measurable,

$R_n = \mathbb E\Big[\sum_{t=1}^n\Delta_{A_t}\Big] = \int_{\mathcal A}\Delta_a\,dG(a)$

The sum over arms becomes an integral against how often each region of the action space is played. (Proof: Exercise 4.6.)

The canonical bandit model

The problem. Usually the underlying probability space is never mentioned. Occasionally a concrete one is convenient, for instance to change measure between two environments in lower-bound proofs.

Finite horizon

DefinitionOutcome space and coordinate maps

For $t\le n$ , let $\Omega_t = ([k]\times\mathbb R)^t\subseteq\mathbb R^{2t}$ and $\mathcal F_t = \mathfrak B(\Omega_t)$ . The outcome $H_n = (A_1,X_1,\ldots,A_n,X_n)$ is given by coordinate projections: $A_t(a_1,x_1,\ldots,a_n,x_n) = a_t$ and $X_t(\ldots) = x_t$ .

DefinitionDefinition 4.7 — Policy

A policy is a sequence $\pi = (\pi_t)_{t=1}^n$ , where $\pi_t$ is a probability kernel from $(\Omega_{t-1},\mathcal F_{t-1})$ to $([k],2^{[k]})$ . Write $\pi_t(i\mid a_1,x_1,\ldots,a_{t-1},x_{t-1})$ for the probability of choosing arm $i$ .

Component	Detail
Signature	$\pi_t:\Omega_{t-1}\times2^{[k]}\to[0,1]$
Input	The full history of the first $t-1$ rounds.
Output	A distribution over arms, so randomized policies are included.

TheoremProposition 4.8 — The two assumptions pin down the law

If $\mathbb P$ and $\mathbb Q$ on any measurable space both satisfy the protocol’s assumptions (actions from $\pi_t$ given the history, rewards from $P_{A_t}$ given the history and the action), then

$\mathbb P_{A_1,X_1,\ldots,A_n,X_n} = \mathbb Q_{A_1,X_1,\ldots,A_n,X_n}$

(Proof: Exercise 4.2.)

IntuitionOnly the law of the outcome matters

Regret depends only on the law of the outcome $H_n$ . By Proposition 4.8 that law is fixed by $\pi$ and $\nu$ alone, so any construction carrying the outcome is as good as any other. We may pick whichever is most convenient.

FormulaThe canonical density

First, Bernoulli rewards. With $p_i(1) = \mu_i$ and $p_i(0) = 1-\mu_i$ , the distribution

$p_{\nu\pi}(a_1,x_1,\ldots,a_n,x_n) = \prod_{t=1}^n\pi_t(a_t\mid a_1,x_1,\ldots,a_{t-1},x_{t-1})\,p_{a_t}(x_t) \tag{4.7}$

on $([k]\times\{0,1\})^n$ satisfies both assumptions. In general: choose a σ-finite $\lambda$ with every $P_i\ll\lambda$ , let $p_i = dP_i/d\lambda$ (the Radon–Nikodym derivative), take $\rho$ = counting measure on $[k]$ , and read (4.7) as a density with respect to $(\rho\times\lambda)^n$ :

$\mathbb P_{\nu\pi}(B) = \int_Bp_{\nu\pi}\,d(\rho\times\lambda)^n,\qquad B\in\mathcal F_n$

Choosing $\lambda$ : $\lambda = \sum_iP_i$ always works. Counting measure (for discrete rewards) or Lebesgue measure (for continuous rewards) is usually more convenient. (Verification: Exercise 4.3, via Fubini and the Radon–Nikodym property.)

IntuitionThe chain rule, written as a product

The density alternates: policy probability, reward density, policy probability, and so on. It is the multiplication rule applied along the interaction. Comparing two environments $\nu,\nu'$ under the same policy, the $\pi$ factors cancel in the likelihood ratio, leaving only the reward densities of the arms actually pulled. That is the engine of later lower bounds.

DefinitionTwo more constructions with the same law

Random-table model: draw an independent table $(X_{si})_{s\le n,i\le k}$ with $X_{si}\sim P_i$ (on $\Omega = \mathbb R^{nk}$ ), and set $X_t = X_{tA_t}$ , the round- $t$ entry of the chosen arm’s column.
Reward-stack model: the same table, but $X_t = X_{T_{A_t}(t),A_t}$ : each arm has a pre-drawn stack of rewards, and every pull takes the next one off that arm’s stack.

Both induce the same law of the outcome (Exercise 4.4, where the stack version uses optional stopping). The stack model is handy when what an arm reveals should depend only on how often it has been pulled.

Infinite horizon and uncountable action sets

RemarkInfinite horizon

The canonical model is never needed for $n = \infty$ . But a space carrying infinite sequences $A_1,X_1,A_2,\ldots$ that satisfy both assumptions exists, directly by Ionescu–Tulcea.

DefinitionUncountable action sets (Section 4.7)

$(\mathcal A,\mathcal G)$ is a measurable space, and $\nu = (P_a)$ must be a probability kernel from $(\mathcal A,\mathcal G)$ to $(\mathbb R,\mathfrak B(\mathbb R))$ .
Each $\pi_t$ is a kernel from $\big(\prod_{s<t}(\mathcal A\times\mathbb R),\bigotimes_{s<t}(\mathcal G\otimes\mathfrak B(\mathbb R))\big)$ to $(\mathcal A,\mathcal G)$ .
$\mathbb P_{\nu\pi}$ is the Ionescu–Tulcea product of $\pi_1,P_1,\ldots,\pi_n,P_n$ , where $P_t(\cdot\mid a_1,x_1,\ldots,a_t) = P_{a_t}(\cdot)$ .

No density is used, because a common dominating measure may not exist. When one does, the density construction works as before. Proposition 4.8 and Lemma 4.6 continue to hold (Exercise 4.6), and $n$ need not be finite.

RemarkExtensions

The construction extends easily, for example to contextual bandits: in each round a context $C_t$ is observed, then $A_t$ is chosen and $X_t\sim P_{A_t,C_t}$ (Exercise 4.7, including contexts that depend on the past). Non-stationary bandits, with arm distributions changing over time, need assumptions such as rare changes or slow drift (Chapter 31).

Two useful exercises

TheoremMixing policies (Exercise 4.5)

For a finite set of policies $\Pi$ and a distribution $p$ on $\Pi$ , there is a single policy $\pi^\circ$ with $\mathbb P_{\nu\pi^\circ} = \sum_{\pi\in\Pi}p(\pi)\mathbb P_{\nu\pi}$ for every bandit $\nu$ :

$\pi_t^\circ(a_t\mid h_{t-1}) = \frac{\sum_\pi p(\pi)\prod_{s\le t}\pi_s(a_s\mid h_{s-1})}{\sum_\pi p(\pi)\prod_{s<t}\pi_s(a_s\mid h_{s-1})}$

Randomizing over which policy to run is itself a policy. It acts like a posterior over “which policy am I”, updated from the actions taken so far. (Substitute into the canonical density and induct.)

ExampleFollow-the-leader can fail forever (Exercises 4.9, 4.12–4.13)

Follow-the-leader (also called “stay with the winner” or greedy) plays each arm once, then always plays the arm with the highest empirical mean, breaking ties at random.

Take Bernoulli arms with $\mu_1 = 0.5$ and $\mu_2 = 0.6$ . With probability $0.5\times0.4 = 0.2$ , the first pull of arm 1 pays 1 and the first pull of arm 2 pays 0. From then on arm 2’s average stays at 0 because it is never pulled again, while arm 1’s average stays positive forever. FTL locks onto the worse arm and pays regret $0.1$ every round.

So the pseudo-regret histogram at $n = 100$ has a lump near $0.1\times99\approx10$ , and the expected regret grows linearly: $R_n\ge0.2\times0.1(n-1) = 0.02(n-1)$ from this one event alone. Pure exploitation never revisits an arm that started unlucky. Fixing that is the whole point of explore-then-commit-and-ucb-algorithms. (The lock-in calculation is worked here; the book poses it as an exercise.)

NoteOther exercises

Exercise 4.10: sublinear regret need not mean every realization behaves well. Decide whether $\mathbb E[T^*(n)]/n\to1$ and $\mathbb P(\Delta_{A_t} > 0)\to0$ .
Exercise 4.11 (one-armed bandits): one arm pays a known constant. Retirement policies (once you take the safe arm, keep it) are without loss for a fixed $n$ , but no retirement policy has sublinear regret on all Bernoulli instances.

Quick reference

Object	Statement	Note
Borel space	isomorphic to a Borel subset of $\mathbb R$	$\mathbb R^n$ and Polish spaces qualify
Theorem 3.1	i.i.d. sequences exist on $([0,1],\lambda)$	binary digits dealt into a grid
Theorem 3.2	projective $(\mu_n)$ ⇒ a process exists	Daniell / Kolmogorov extension
Kernel	$K(x,\cdot)$ a measure; $K(\cdot,A)$ measurable	a randomized function
Ionescu–Tulcea	history-dependent kernels ⇒ a process exists	no Borel assumption
Markov chain	$\mathbb P(X_{t+1}\in\cdot\mid X^t) = \mu(X_t,\cdot)$	homogeneous: $\mu$ fixed
Martingale	$\mathbb E[X_t\mid\mathcal F_{t-1}] = X_{t-1}$	super: $\le$ ; sub: $\ge$
Stopping time	$\{\tau\le t\}\in\mathcal F_t$	may be $\infty$
Optional stopping	$\mathbb E X_\tau = \mathbb E X_0$	bounded $\tau$ , or $\mathbb E\tau<\infty$ with bounded increments, or bounded stopped process
Maximal inequality	$\mathbb P(\sup X_t\ge\varepsilon)\le\mathbb E X_0/\varepsilon$	nonnegative supermartingale
Regular conditional law	$\mathbb P_{X,Y} = \mathbb P_Y\otimes\mathbb P_{X\mid Y}$	$X$ Borel
Bandit	$\nu = (P_a)_{a\in\mathcal A}$	rewards depend only on the current arm
Policy	kernels $\pi_t$ : history → arms	no peeking at the future
Regret	$R_n = n\mu^* - \mathbb E\sum X_t$	$\ge0$ ; zero iff the optimal arm is known
Decomposition	$R_n = \sum_a\Delta_a\mathbb E[T_a(n)]$	integral form for uncountable $\mathcal A$
Canonical density	$\prod_t\pi_t(a_t\mid h_{t-1})p_{a_t}(x_t)$	w.r.t. $(\rho\times\lambda)^n$
Proposition 4.8	the protocol determines the outcome’s law	any construction is fine
Pseudo-regret	$n\mu^* - \sum\mu_{A_t}$	filters out reward noise
FTL failure	$R_n\ge0.02(n-1)$ for $\mu = (0.5,0.6)$	lock-in on an unlucky start

Facts to keep to hand

Existence comes from consistency and kernels. Projective families give processes on Borel spaces; Ionescu–Tulcea gives history-dependent processes anywhere. That is exactly what makes “a policy interacting with a bandit” a well-defined random experiment.
Martingales formalize “no free lunch”. Optional stopping (under one of its three conditions) says clever stopping can’t beat a fair game. The doubling strategy shows why the conditions matter.
The maximal inequality controls the whole path for the price of one time. It is Markov’s inequality at a stopping time, and it powers anytime-valid confidence statements.
Regret is a gap-weighted count of mistakes. Every stochastic-bandit analysis bounds $\mathbb E[T_a(n)]$ for suboptimal arms, with a target of $C(\nu)f(n)$ .
Only the law of the outcome matters. The canonical, random-table and reward-stack models are interchangeable. The canonical density makes change-of-measure arguments mechanical.
Structure is information. Unstructured classes make each arm an island; structured classes (linear, mirror-image, shared-edge paths) let the learner learn about arms it never plays.

References

Lattimore & Szepesvári, Bandit Algorithms — Chapters 3–4

Related

Stochastic Processes, Markov Chains, and Stochastic Bandits

Motivation: from i.i.d. trials to adaptive interaction

Existence of infinite sequences

Stochastic processes and projective families

Probability kernels and Markov chains

Martingales and stopping times

Stopping times

The maximal inequality

Conditional distributions done properly

Stochastic bandits: core assumptions

The learning objective

Knowledge and environment classes

The regret

Decomposing the regret

The canonical bandit model

Finite horizon

Infinite horizon and uncountable action sets

Two useful exercises

Quick reference

References

Mentioned in