Bandits and Reinforcement Learning · Study tools

InteractiveLattimore–Szepesvári, Ch. 4: Stochastic Bandits

The bandit problem and regret

There are $K$ slot machines (arms). Each pull pays a random reward; each arm has its own average, which you never get to see. You have $T$ pulls. Every pull of a worse arm costs you something, and the bill is called regret.

The idea

Stochastic bandit. Arms

\mathcal A=\{1,\dots,K\}

. Pulling arm

a

gives an independent reward

X

with mean

\mu_a=\mathbb E[X]

, in

[0,1]

here. In round

t=1,\dots,T

the learner picks

A_t

, based only on the rewards it has seen so far, and receives

X_t

. Write

\mu^\star=\max_a\mu_a

for the best mean.

Regret. The expected shortfall against always pulling the best arm:

R_T \;=\; T\mu^\star-\mathbb E\Big[\sum_{t=1}^T X_t\Big].

Maximizing total expected reward and minimizing regret are the same goal; regret just measures it against the best you could have done if you had known the means.

Regret decomposition (Lattimore–Szepesvári, Ch. 4). With gaps

\Delta_a=\mu^\star-\mu_a\ge0

and

n_a(T)

the number of pulls of arm

a

,

R_T=\sum_{a=1}^K \Delta_a\,\mathbb E[n_a(T)].

So

0\le R_T\le T

for rewards in

[0,1]

. Good algorithms pull bad arms rarely, and very bad arms even more rarely.

Why you can't see your own regret. Regret is defined through the means, and the means are exactly what you don't know. Flip a coin twelve times and get eleven heads: your estimate is $11/12\approx0.92$ , but the coin could be fair-ish with $p=0.6$ and you were lucky. After a thousand flips the estimate is better, never exact. A bandit algorithm only ever sees estimates; the figure below lets you see both.

Explore

Arms

Click an arm (or press 1, 2, 3) to pull it. Dots are the rewards you got, 0 or 1; the bar is the empirical mean. true mean, once revealed.

Worked example

Three arms with $\mu=(0.8,\,0.5,\,0.7)$ . In five rounds a learner pulls $a_1,a_2,a_3,a_1,a_3$ . Compute the regret two ways.

Find $\mu^\star$ and the gaps.

$\mu^\star=0.8$ , so $\Delta_1=0$ , $\Delta_2=0.3$ , $\Delta_3=0.1$ . A gap is never negative because $\mu^\star$ is the largest mean.
Add up the regret round by round.

Each round costs the gap of the arm pulled: $0+0.3+0.1+0+0.1=0.5$ . The actual rewards don't enter: this is the regret in expectation.
Now use the decomposition.

$n_1=2$ , $n_2=1$ , $n_3=2$ : $R_5=2(0)+1(0.3)+2(0.1)=0.5$ . Same answer, grouped by arm instead of by round.

Key terms

Arm: One of the options you can choose each round, with a fixed but unknown average payoff.
Bandit feedback: You see the reward of the option you chose and nothing about the ones you didn't.
Gap: How much worse an option's average is than the best option's average.
Regret: The expected total reward you gave up by not always choosing the best option.
Empirical mean: The average of the rewards an option has actually paid so far: an estimate, never the truth.

Check your understanding

A learner happens to get lucky rewards from a bad arm. Can its regret $R_T$ be negative?

Yes, if the rewards it got add up to more than $T\mu^\star$ .That compares realized rewards; $R_T$ is defined with an expectation.
No: $R_T=\sum_a\Delta_a\mathbb E[n_a(T)]$ is a sum of nonnegative terms.

Luck affects the realized reward, not the expectation. In expectation no algorithm beats always pulling the best arm, so

R_T\ge0

, with equality only if suboptimal arms are never pulled.

An algorithm that pulls arms uniformly at random forever, with $\mu=(0.8,0.5,0.7)$ , has regret:

$O(\log T)$ Each arm gets about $T/3$ pulls, forever.
$\tfrac{0.4}{3}\,T\approx0.13\,T$ , linear in $T$ .
$0$ , because it tries every arm.Trying every arm is good; continuing to try them is the cost.

\mathbb E[n_a]=T/3

for each arm, so

R_T=\tfrac T3(0+0.3+0.1)

. Pure exploration has linear regret; so does pure exploitation of a wrong guess. The interesting algorithms have regret that grows sublinearly, so the average regret per round tends to 0.

Why can't a bandit algorithm compute its own regret as it goes?

It would take too long to compute.The formula is a short sum.
The formula needs the true means $\mu_a$ , and it only has estimates.
Rewards are hidden from the learner.It sees the reward of every arm it pulls.

Regret is an analysis tool: we, knowing the instance, use it to grade algorithms. The algorithm itself only has empirical means, which converge to the truth but never equal it.

Practice

The decompositionProve it

Prove $R_T=\sum_a\Delta_a\mathbb E[n_a(T)]$ .

Hint

Write $\sum_t X_t=\sum_a\sum_t X_t\mathbf 1\{A_t=a\}$ and condition on $A_t$ in each term.

Solution

$\mathbb E[X_t\mathbf 1\{A_t=a\}]=\mathbb E\big[\mathbf 1\{A_t=a\}\,\mathbb E[X_t\mid A_t,\text{past}]\big]=\mu_a\mathbb P(A_t=a)$ , because given the past and the choice $A_t=a$ , the new reward is a fresh draw from arm $a$ . Summing over $t$ : $\mathbb E[\sum_tX_t]=\sum_a\mu_a\mathbb E[n_a(T)]$ . Since $T=\sum_a\mathbb E[n_a(T)]$ , $R_T=\sum_a(\mu^\star-\mu_a)\mathbb E[n_a(T)]$ .

Two arms, one gapBounds from counts

Two arms with gap $\Delta=0.1$ . An algorithm pulls the bad arm at most $50\log T$ times in expectation. Bound its regret at $T=10^6$ , and compare with uniform play.

Solution

$R_T\le0.1\cdot50\log(10^6)\approx0.1\cdot50\cdot13.8\approx69$ . Uniform play has $R_T=0.1\cdot T/2=50{,}000$ . Logarithmic dependence on $T$ is what the algorithms in the next modules achieve.

SimulationLattimore–Szepesvári, Ch. 6: Explore-Then-Commit; Sutton–Barto, Ch. 2

Explore or exploit

Pulling the arm that looks best (exploiting) earns reward now. Pulling an arm that looks worse (exploring) buys information, because it may only look worse by bad luck. Every bandit algorithm is a rule for splitting rounds between the two.

The idea

Think of giving a new student a first project. If it goes badly, was it the student or bad luck with the project? One bad outcome isn't enough to know, so you give a second chance, maybe a third. But you can't give chances forever: at some point the evidence is good enough to act on. Randomness is why you must explore; cost is why you must stop.

Greedy. Pull each arm once, then always pull the arm with the highest empirical mean

\hat\mu_a

.

$\varepsilon$ -greedy. Each round, with probability

\varepsilon

pull a uniformly random arm, otherwise act greedily.

Explore-then-commit (ETC). Pull each arm

m

times, then commit for the rest of the game to the arm with the best empirical mean.

What goes wrong, and what doesn't. Greedy can lock onto a bad arm forever: if the best arm's first rewards are unlucky, its estimate is low and it is never pulled again to correct it. That happens with constant probability, so greedy has linear regret. Constant

\varepsilon

-greedy never locks in, but keeps exploring at rate

\varepsilon

, so its regret is at least about

\varepsilon T\cdot\frac1K\sum_a\Delta_a

: linear again. ETC with two arms and

1

-sub-Gaussian rewards satisfies (Lattimore–Szepesvári, Ch. 6)

R_T\le m\Delta+(T-2m)\,\Delta\,e^{-m\Delta^2/4},

and choosing

m\approx\frac4{\Delta^2}\log\frac{T\Delta^2}4

gives regret of order

\frac{\log T}\Delta

. The catch: that

m

depends on

\Delta

, which you don't know.

Explore

Arms (Bernoulli means)

ε for ε-greedy m for ETC

Average regret over 200 runs of 2000 rounds. greedy ε-greedy explore-then-commit. Shaded: the middle 80% of runs.

Worked example

Two Bernoulli arms with means $0.6$ and $0.4$ . Greedy pulls each once and then follows the higher estimate (ties broken at random). Estimate the chance that greedy never pulls the good arm after round 2.

Which first two outcomes make greedy prefer arm 2?

Arm 1 pays 0 and arm 2 pays 1: probability $0.4\times0.4=0.16$ . Then $\hat\mu_1=0<\hat\mu_2=1$ .
Once that happens, can greedy ever return to arm 1?

Only if $\hat\mu_2$ drops below $\hat\mu_1=0$ , which can't happen (estimates are averages of 0s and 1s, and a tie at 0 needs every arm-2 reward to be 0). With mean $0.4$ , arm 2's average stays positive with high probability. So arm 1 is abandoned for good.
What does that do to the regret?

With probability at least about $0.16$ (more, counting the tie cases), greedy pays $\Delta=0.2$ every round: $R_T\ge0.16\cdot0.2\,(T-2)\approx0.03\,T$ . Linear, however large $T$ is.

Check your understanding

In the simulation, greedy's average regret can look fine while its shaded band is wide. Why?

Most runs lock onto the right arm and pay almost nothing; a few lock onto a wrong one and pay a lot.
The rewards are noisy, so every run pays about the same.Then the band would be narrow.

Greedy's regret is a mixture: near zero when the first pulls happen to favour the best arm, linear when they don't. The average sits in between and describes no actual run. That is why regret bounds that hold in expectation can hide a real risk, and why the stats under the figure also count the runs that ended on a wrong arm.

ETC with $m$ too small, on arms whose means are very close, mostly fails by:

Committing to the wrong arm, then paying its gap for the rest of the game.
Exploring for too long.That's the failure when $m$ is too large.

With few samples, the noise in

\hat\mu_a

is about

1/\sqrt m

, larger than the gap, so the commit is close to a coin flip. Too large an

m

wastes

m\Delta

per bad arm instead. The best

m

balances the two, and depends on

\Delta

.

ε-greedy with a fixed $\varepsilon=0.1$ on three arms with gaps $0, 0.3, 0.1$ has regret at least about:

$\log T$ It explores in a fixed fraction of rounds, forever.
$0.1\cdot T\cdot\tfrac{0.4}3\approx0.013\,T$

In a

\varepsilon

fraction of rounds it picks uniformly, paying the average gap

0.4/3

. Letting

\varepsilon_t

decay like

1/t

fixes this, again with a constant that depends on the gaps.

Practice

The ETC trade-offChoose m

Using the bound $R_T\le m\Delta+T\Delta e^{-m\Delta^2/4}$ , find the $m$ that minimizes the right-hand side, and the resulting regret.

Solution

Differentiate in $m$ : $\Delta-\frac{T\Delta^3}4e^{-m\Delta^2/4}=0$ , so $e^{-m\Delta^2/4}=\frac4{T\Delta^2}$ and $m=\frac4{\Delta^2}\log\frac{T\Delta^2}4$ . Then $R_T\le\frac4\Delta\log\frac{T\Delta^2}4+\frac4\Delta$ , of order $\frac{\log T}\Delta$ . (Round $m$ up to an integer; if $T\Delta^2\le4$ , take $m=1$ , and the regret is at most $T\Delta\le2\sqrt T$ .)

When does greedy work?An easy instance

Suppose rewards are deterministic: arm $a$ always pays exactly $\mu_a$ . What is the regret of greedy?

Solution

After one pull of each arm the estimates are exact, so greedy commits correctly: $R_T=\sum_a\Delta_a\le K-1$ , constant in $T$ . Exploration is only needed because of noise; the noisier the rewards, the more it costs.

SimulationVershynin, Ch. 2: Concentration of Sums of Independent Random Variables

Concentration of sums

A sum of $n$ independent terms with values in $[0,1]$ exceeds its mean by $s$ with probability at most $e^{-2s^2/n}$ , for every $n$ , not just in the limit. Hoeffding, Chernoff and Bernstein are three versions of this, and the differences between them matter exactly when some terms are rare.

The idea

Hoeffding. If

\varepsilon_1,\dots,\varepsilon_N

are independent random signs and

a\in\R^N

, then

\mathbb P\big(\sum a_i\varepsilon_i\ge t\big)\le\exp\!\big(-t^2/2\|a\|_2^2\big)

. If instead

X_i\in[m_i,M_i]

are independent,

\mathbb P\Big(\sum_{i=1}^N(X_i-\mathbb E X_i)\ge t\Big)\le\exp\Big(-\frac{2t^2}{\sum_i(M_i-m_i)^2}\Big).

Chernoff. If

X_i

are independent Bernoulli

(p_i)

,

S=\sum X_i

and

\mu=\mathbb E S

, then for

t>\mu

,

\ \mathbb P(S\ge t)\le e^{-\mu}(e\mu/t)^t

. For small

\mu

this behaves like a Poisson tail and is far smaller than Hoeffding's bound.

All of these come from one move: apply Markov to $e^{\lambda S}$ , factor $\mathbb E e^{\lambda S}$ using independence, and optimise over $\lambda$ .

Subgaussian.

\|X\|_{\psi_2}=\inf\{K>0:\mathbb E\exp(X^2/K^2)\le2\}

. Finite

\psi_2

norm is equivalent, up to absolute constants, to tails

\mathbb P(|X|\ge t)\le2e^{-t^2/K^2}

, to moments

\|X\|_{L^p}\lesssim K\sqrt p

, and (for mean zero) to

\mathbb E e^{\lambda X}\le e^{CK^2\lambda^2}

.

General Hoeffding. For independent mean-zero subgaussian

X_i

,

\ \mathbb P\big(|\sum X_i|\ge t\big)\le2\exp\big(-ct^2/\sum\|X_i\|_{\psi_2}^2\big)

.

Bernstein. For independent mean-zero subexponential

X_i

(

\|X\|_{\psi_1}=\inf\{K:\mathbb E e^{|X|/K}\le2\}

finite), with

K=\max\|X_i\|_{\psi_1}

,

\mathbb P\Big(\Big|\sum_{i=1}^N X_i\Big|\ge t\Big)\le2\exp\Big(-c\min\Big(\frac{t^2}{\sum_i\|X_i\|_{\psi_1}^2},\ \frac tK\Big)\Big):

a Gaussian tail for moderate $t$ , an exponential one far out.

Key terms in plain words

The ideas above without the symbols. Switch to Quiz me to test yourself: you see an explanation and pick the term it describes.

Hoeffding's inequality: A sum of independent bounded variables rarely strays far from its mean: the chance of straying by $t$ falls off like $e^{-t^2}$ , scaled by the ranges of the variables.
Chernoff bound: A sharper tail bound for sums of independent yes-or-no variables, especially when successes are rare: it behaves like a Poisson tail.
Subgaussian: Describes a random variable whose tails die off at least as fast as a normal distribution's. Bounded variables and normal ones are examples.
ψ₂ norm: A single number measuring the spread of a variable with normal-like tails: the scale at which its tails look like a normal's.
Subexponential: Describes a variable whose tails may be heavier than a normal's but still fall off exponentially, like the square of a normal variable.
Bernstein's inequality: A tail bound for sums of independent variables with exponential tails: it looks like a normal tail for moderate deviations and only exponential far out.

Explore

Number of trials n Success probability p Threshold k

exact

\mathbb P(S\ge k)

,

S\sim\mathrm{Bin}(n,p)

simulated Chebyshev Hoeffding Chernoff

Worked example

An A/B test estimates a click rate $p$ by the fraction $\hat p$ of $N$ independent users who click. We want $|\hat p-p|<0.01$ with probability at least $0.999$ . How many users are needed?

Use Chebyshev, knowing only $p(1-p)\le1/4$ .

$\mathbb P(|\hat p-p|\ge0.01)\le\dfrac{p(1-p)}{N\cdot 10^{-4}}\le\dfrac{1}{4N\cdot10^{-4}}$ . Setting this to $10^{-3}$ gives $N\ge2\,500\,000$ .
Use Hoeffding (each click indicator lies in $[0,1]$ ).

Two-sided: $\mathbb P(|\hat p-p|\ge\varepsilon)\le2e^{-2N\varepsilon^2}$ . We need $2e^{-2N\cdot10^{-4}}\le10^{-3}$ , i.e. $N\ge\ln(2000)/(2\cdot10^{-4})\approx38\,005$ . Sixty-five times fewer users.
Suppose you also know $p\le0.02$ . Bernstein's inequality for variables with $|X_i-p|\le1$ reads $\mathbb P(|\sum(X_i-p)|\ge t)\le2\exp\big(-\tfrac{t^2/2}{N\sigma^2+t/3}\big)$ . What $N$ does it give?

Here $\sigma^2=p(1-p)\le0.02\cdot0.98=0.0196$ and $t=N\varepsilon$ , so the exponent is $N\varepsilon^2/\big(2(\sigma^2+\varepsilon/3)\big)$ . We need it to be at least $\ln2000\approx7.60$ :

$N\ \ge\ \frac{2\,(0.0196+0.00333)\cdot7.60}{10^{-4}}\ \approx\ 3487.$

Another factor of 11. Hoeffding pays for the worst-case variance $1/4$ ; Bernstein pays only for the actual variance.
How does each answer scale with the failure probability $\delta$ ?

Chebyshev needs $N\propto1/\delta$ ; Hoeffding and Bernstein need $N\propto\log(1/\delta)$ . Asking for $\delta=10^{-6}$ instead of $10^{-3}$ multiplies the Chebyshev answer by 1000, but the Hoeffding answer by less than 2.

Check your understanding

Which of these random variables is not subgaussian?

A random variable with $|X|\le 5$ almost surelyBounded variables are subgaussian: $\mathbb E e^{X^2/K^2}\le e^{25/K^2}$ , which is at most 2 for large $K$ .
$N(0,\sigma^2)$ The Gaussian is the model subgaussian variable, with $\|X\|_{\psi_2}$ a constant times $\sigma$ .
An exponential random variable
A sum of 100 independent random signsThat sum is bounded by 100, and better, it has $\psi_2$ norm of order $\sqrt{100}$ .

\mathbb P(X\ge t)=e^{-t}

decays only exponentially, so

\mathbb E e^{X^2/K^2}=\infty

for every

K

. The exponential is the model subexponential variable, which is where Bernstein's inequality takes over.

$S\sim\mathrm{Bin}(10^4,10^{-4})$ , so $\mathbb E S=1$ . Hoeffding bounds $\mathbb P(S\ge10)$ by about $0.98$ ; Chernoff by about $8\times10^{-7}$ . Why is Hoeffding so weak here?

It only uses that each term lies in $[0,1]$ , not that each term is almost always 0.
Hoeffding needs identically distributed terms.It doesn't, and these terms are identically distributed anyway.
Hoeffding needs symmetric terms.The version for bounded variables needs only independence and the ranges.
Hoeffding only holds for large $n$ .It holds for every $n$ . It is a true bound here, just a useless one.

Hoeffding's exponent

2t^2/n

is what you'd get if every term had the largest variance a

[0,1]

variable can have, namely

1/4

. Here the variance is

10^{-4}

. Chernoff (or Bernstein) sees the true variance. Try

p=0.005

in the explorer.

Let $X_i=g_i^2-1$ with $g_i$ i.i.d. standard normal, so the $X_i$ are mean-zero subexponential. For which deviations $t$ does Bernstein give a Gaussian-type bound $e^{-ct^2/N}$ for $\mathbb P(|\sum_{i\le N}X_i|\ge t)$ ?

For $t\lesssim N$
For $t\gtrsim N$ Compare $t^2/N$ with $t$ : which is smaller when $t$ is large?
For all $t$ Then $\sum X_i$ would be subgaussian, but $\mathbb P(X_1\ge t)$ alone already decays like $e^{-t/2}$ .
Only for $t\lesssim\sqrt N$ $\sqrt N$ is the typical size of the sum, but the Gaussian regime extends much further.

The minimum of

t^2/N

and

t

is

t^2/N

exactly when

t\le N

. So the sum looks Gaussian (scale

\sqrt N

) well into its tail, and only beyond

t\approx N

does the exponential tail of a single term take over.

Practice

Two subgaussian normsComputing ψ₂ from the definition

(a) Show that if $|X|\le M$ , then $\|X\|_{\psi_2}\le M/\sqrt{\ln2}$ , with equality for $X=\pm M$ with equal probability. (b) Compute $\|g\|_{\psi_2}$ for $g\sim N(0,1)$ .

Hint

For (b), $\mathbb E e^{sg^2}=(1-2s)^{-1/2}$ for $s<1/2$ .

Solution

(a) $\mathbb E e^{X^2/K^2}\le e^{M^2/K^2}\le2$ once $K^2\ge M^2/\ln2$ ; for $X=\pm M$ the first inequality is an equality, so this $K$ is the smallest. (b) Set $(1-2/K^2)^{-1/2}=2$ : then $1-2/K^2=1/4$ , $K^2=8/3$ , $\|g\|_{\psi_2}=\sqrt{8/3}\approx1.633$ .

From MGFs to a tail boundThe exponential moment method

Suppose $X_1,\dots,X_N$ are independent and $\mathbb E e^{\lambda X_i}\le e^{\lambda^2\sigma_i^2/2}$ for all $\lambda\in\R$ . Prove $\mathbb P(\sum X_i\ge t)\le\exp\big(-t^2/2\sum\sigma_i^2\big)$ for $t\ge0$ .

Solution

For $\lambda>0$ , Markov and independence give $\mathbb P(S\ge t)\le e^{-\lambda t}\prod\mathbb E e^{\lambda X_i}\le\exp(-\lambda t+\lambda^2V/2)$ with $V=\sum\sigma_i^2$ . The exponent is smallest at $\lambda=t/V$ , where it equals $-t^2/2V$ . Random signs satisfy the hypothesis with $\sigma_i=|a_i|$ , because $\cosh x\le e^{x^2/2}$ ; this recovers Hoeffding.

From Vershynin, High-Dimensional Probability (2nd ed., Cambridge, pre-publication version, 2025)

Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.

Exercise 2.13Chernoff for Poisson

Let $X\sim\mathrm{Pois}(\mu)$ . Prove: (a) $\mathbb P\{X\ge t\}\le e^{-\mu}(e\mu/t)^t$ for $t\ge\mu$ ; (b) $\mathbb P\{X\le t\}\le e^{-\mu}(e\mu/t)^t$ for $0<t\le\mu$ ; (c) $\mathbb P\{|X-\mu|\ge\delta\mu\}\le2e^{-\delta^2\mu/3}$ for $\delta\in[0,1]$ ; (d) $\mathbb P\{X=t\}\ge e^{-\mu}(\mu/t)^t$ for integers $t>0$ .

Hint

$\mathbb Ee^{\lambda X}=\exp(\mu(e^\lambda-1))$ . Optimise Markov's inequality over $\lambda$ ; the optimum is $e^\lambda=t/\mu$ .

Solution

(a) For $\lambda\ge0$ , $\mathbb P\{X\ge t\}\le e^{-\lambda t}e^{\mu(e^\lambda-1)}$ . With $e^\lambda=t/\mu\ge1$ this is $(\mu/t)^te^{t-\mu}=e^{-\mu}(e\mu/t)^t$ .

(b) For $\lambda\ge0$ , $\mathbb P\{X\le t\}=\mathbb P\{e^{-\lambda X}\ge e^{-\lambda t}\}\le e^{\lambda t}e^{\mu(e^{-\lambda}-1)}$ . With $e^{-\lambda}=t/\mu\le1$ we get the same expression.

(c) At $t=(1\pm\delta)\mu$ the bounds read $\exp(-\mu\,h(\pm\delta))$ with $h(u)=(1+u)\ln(1+u)-u$ . Elementary calculus gives $h(\delta)\ge\delta^2/3$ and $h(-\delta)\ge\delta^2/2$ on $[0,1]$ (compare derivatives: $h'(u)=\ln(1+u)$ , $h''(u)=1/(1+u)\ge1/2$ ). Add the two tails.

(d) $\mathbb P\{X=t\}=e^{-\mu}\mu^t/t!\ge e^{-\mu}(\mu/t)^t$ , since $t!\le t^t$ .

Exercise 2.25Distributions that aren't subgaussian

Explain why the exponential, Poisson, geometric, chi-squared, Gamma, Cauchy and Pareto distributions are not subgaussian.

Hint

Subgaussian means $\mathbb P\{|X|\ge t\}\le2e^{-t^2/K^2}$ for some $K$ . Compare each tail with $e^{-ct^2}$ .

Solution

For each, find a lower bound on the tail that decays slower than any $e^{-ct^2}$ :

Exponential: $\mathbb P\{X>t\}=e^{-t}$ .
Geometric: $\mathbb P\{X>k\}=(1-p)^k$ , again exponential.
Poisson: $\mathbb P\{X\ge t\}\ge\mathbb P\{X=t\}\ge e^{-\mu}(\mu/t)^t=e^{-t\ln(t/\mu)-\mu}$ , which is $e^{-O(t\log t)}$ .
Chi-squared with $k$ degrees of freedom: $X\ge g_1^2$ , and $\mathbb P\{g_1^2>t\}\approx e^{-t/2}$ .
Gamma $(k,\theta)$ : density $\propto x^{k-1}e^{-x/\theta}$ , tail of order $t^{k-1}e^{-t/\theta}$ .
Cauchy: $\mathbb P\{X>t\}\sim1/(\pi t)$ ; it doesn't even have a mean.
Pareto: polynomial tail $t^{-\alpha}$ .

Since $e^{-ct}/e^{-c't^2}\to\infty$ , none of these can satisfy a subgaussian tail bound. (The first five are subexponential; Cauchy and Pareto are heavier still.)

InteractiveLattimore–Szepesvári, Ch. 7: The Upper Confidence Bound Algorithm

UCB: optimism under uncertainty

Give each arm the benefit of the doubt: score it by the most it could plausibly be worth, its empirical mean plus a bonus that shrinks as it is pulled. Pull the arm with the highest score. Exploration then happens exactly where the uncertainty is, and stops on its own.

The idea

UCB. After arm

a

has been pulled

n_a

times with empirical mean

\hat\mu_a

, its index is

\mathrm{UCB}_a=\hat\mu_a+\sqrt{\frac{4\log T}{n_a}},

and

\mathrm{UCB}_a=\infty

if

n_a=0

. Each round, pull the arm with the largest index. (UCB1 uses

\sqrt{2\log t/n_a}

with the current round

t

instead; the analysis is the same in spirit.)

The bonus is the width of a confidence interval. By the concentration module, for $1$ -sub-Gaussian rewards (rewards in $[0,1]$ qualify),

\mathbb P\big(|\hat\mu-\mu|\ge\varepsilon\big)\le2e^{-n\varepsilon^2/2},

and with

\varepsilon=\sqrt{4\log T/n}

the right-hand side is

2/T^2

. So with high probability every arm's true mean lies below its index. An arm is pulled for one of two reasons: its mean is high (exploitation) or its bonus is high (exploration). Either way, pulling it is a reasonable bet.

Regret of UCB. For

1

-sub-Gaussian rewards,

R_T\le\sum_{a:\Delta_a>0}\Big(\frac{16\log T}{\Delta_a}+(2K+1)\Delta_a\Big)\qquad\text{and}\qquad R_T\le\sqrt{KT\,(16\log T+2K+1)}\approx4\sqrt{KT\log T}.

The first bound is logarithmic in

T

but blows up for tiny gaps; the second needs no gaps at all. No algorithm can beat

c\sqrt{KT}

on every instance (Lattimore–Szepesvári, Ch. 15), so UCB is optimal up to

\sqrt{\log T}

.

Explore

Bonus

Each arm: empirical mean and interval, true mean. The highlighted arm has the highest upper end and is pulled next.

Pulls of each arm so far. The best arm's count grows linearly; the others' grow like

\log t

.

Worked example

Two arms, $T=5$ , bonus $\sqrt{4\log5/n}$ . Rounds 1 and 2 pull arm 1 then arm 2 (both indices start at $\infty$ ) and pay $0.7$ and $0.3$ . Round 3 pays $0.5$ , round 4 pays $0$ . Follow UCB.

Compute both indices before round 3. Which arm is pulled?

$\sqrt{4\log5}\approx2.54$ . $\mathrm{UCB}_1=0.7+2.54=3.24$ , $\mathrm{UCB}_2=0.3+2.54=2.84$ . Arm 1.
Arm 1 paid $0.5$ . Indices before round 4?

$\hat\mu_1=0.6$ with $n_1=2$ : bonus $\sqrt{4\log5/2}\approx1.79$ , so $\mathrm{UCB}_1=2.39$ . Arm 2 is unchanged at $2.84$ . Arm 2 is pulled: its interval is wider, so it might still be the better arm.
Arm 2 paid $0$ . Which arm is pulled in round 5?

$\hat\mu_2=0.15$ , $\mathrm{UCB}_2=0.15+1.79=1.94<2.39$ . Arm 1. With equal counts, the arm with the higher mean wins: the bonus only matters while counts differ.

The proof, step by step

Prove $\mathbb E[n_a(T)]\le\frac{16\log T}{\Delta_a^2}+1+2K$ for every suboptimal arm $a$ . Write $\hat\mu_{a,s}$ for the mean of the first $s$ rewards of arm $a$ and $b_s=\sqrt{4\log T/s}$ .

Define a “good event” $G$ on which every confidence interval is correct, and bound $\mathbb P(G^c)$ .

$G=\{|\hat\mu_{a,s}-\mu_a|<b_s\ \text{for all arms }a\text{ and all }s\le T\}$ . Each of the $KT$ bad events has probability at most $2e^{-sb_s^2/2}=2/T^2$ . By the union bound, $\mathbb P(G^c)\le KT\cdot2/T^2=2K/T$ .
On $G$ , show the optimal arm's index is always at least $\mu^\star$ .

$\mathrm{UCB}_{a^\star}=\hat\mu_{a^\star}+b_{n}>(\mu^\star-b_n)+b_n=\mu^\star$ . Optimism: the best arm is never underrated.
On $G$ , when can a suboptimal arm $a$ with $n_a$ pulls so far be chosen?

It needs $\mathrm{UCB}_a\ge\mathrm{UCB}_{a^\star}>\mu^\star$ . But on $G$ , $\mathrm{UCB}_a<\mu_a+2b_{n_a}$ . So $\mu_a+2\sqrt{4\log T/n_a}>\mu^\star$ , that is, $n_a<\frac{16\log T}{\Delta_a^2}$ . Once arm $a$ has that many pulls it is never chosen again, so $n_a(T)\le\frac{16\log T}{\Delta_a^2}+1$ .
Combine the two events.

$\mathbb E[n_a(T)]\le\mathbb E[n_a(T)\mathbf 1_G]+T\,\mathbb P(G^c)\le\frac{16\log T}{\Delta_a^2}+1+2K$ . Multiply by $\Delta_a$ and sum: the gap-dependent bound.
Remove the gaps with Cauchy–Schwarz.

$R_T=\sum_a\Delta_a\sqrt{\mathbb E n_a}\cdot\sqrt{\mathbb E n_a}\le\sqrt{\sum_a\Delta_a^2\mathbb E n_a}\sqrt{\sum_a\mathbb E n_a}$ . The second factor is $\sqrt T$ ; by the previous step each $\Delta_a^2\mathbb E n_a\le16\log T+(1+2K)\Delta_a^2\le16\log T+2K+1$ . So $R_T\le\sqrt{KT(16\log T+2K+1)}$ .

Check your understanding

Why does UCB keep pulling a suboptimal arm occasionally, even late in the game?

Its bonus grows relative to the others' while it sits unpulled ( $\log t$ grows, $n_a$ doesn't), until its upper end overtakes the best arm's.
It pulls a random arm with some fixed probability.That is ε-greedy. UCB is deterministic given the history.

With UCB1's

\sqrt{2\log t/n_a}

, an unpulled arm's index creeps up. With

\log T

fixed, the comparison is with the best arm's index, which falls toward

\mu^\star

as it is pulled. Either way the suboptimal arm is checked about

\log T/\Delta^2

times in total.

In the proof, what goes wrong without the optimism step ( $\mathrm{UCB}_{a^\star}\ge\mu^\star$ )?

The best arm could be underrated, so a suboptimal arm could beat it without needing a large bonus.
The union bound fails.The union bound is about the good event, which doesn't involve the algorithm.

The argument compares

\mathrm{UCB}_a

to

\mu^\star

, not to

\mathrm{UCB}_{a^\star}

. That comparison only works because the best arm's index is above its true mean.

Two suboptimal arms with gaps $0.4$ and $0.04$ . Which one costs UCB more regret?

The gap $0.4$ arm: each pull costs ten times more.But it is pulled about a hundred times less.
The gap $0.04$ arm: about $16\log T/0.04$ versus $16\log T/0.4$ .

Pulls scale like

1/\Delta^2

, so regret scales like

1/\Delta

. Near-optimal arms are hard to rule out, and every lower bound says the same (Lai–Robbins:

\liminf R_T/\log T\ge\sum_a\Delta_a/\mathrm{KL}(\mu_a,\mu^\star)

).

Practice

Where the 16 comes fromTracking constants

Redo step 3 of the proof with bonus $\sqrt{c\log T/n}$ . What constant replaces 16, and which $c$ are allowed by step 1?

Solution

Step 3 gives $n_a<4c\log T/\Delta_a^2$ . Step 1 needs $2e^{-c\log T/2}=2T^{-c/2}$ to be summable over $KT$ events with a total of $O(K/T)$ , so $c\ge4$ . Smaller $c$ explores less and often works better in practice (as in the figure with UCB1), but this proof no longer covers it.

See it runOn this site

The Bandits Lab project races UCB, Thompson sampling and others against the Lai–Robbins lower bound. Find an instance where Thompson sampling clearly beats UCB, and explain it with the third concept check above.

Hint

UCB's bonus uses a sub-Gaussian bound, which is loose for Bernoulli arms with means near 0 or 1; the KL in Lai–Robbins is much larger there than $\Delta^2/2$ .

InteractiveLattimore–Szepesvári, Ch. 19: Stochastic Linear Bandits; Ch. 20

Contextual bandits and LinUCB

Arms now come with feature vectors, and an arm's mean reward is a linear function of its features. Instead of estimating $K$ separate means, you estimate one vector $\theta^\star$ , so pulling one arm teaches you about all of them.

The idea

Linear contextual bandit. In round

t

each arm

a

shows a feature vector

x_t(a)\in\R^d

(the context: a user's profile combined with an item's description, say). The reward of the chosen arm

A_t

is

X_t=\langle x_t(A_t),\theta^\star\rangle+\eta_t,\qquad\mathbb E[\eta_t]=0,

with

\theta^\star\in\R^d

unknown. The best arm can change from round to round: with

\theta^\star=(1,-1)

, features

(2,3)

and

(4,-1)

score

-1

and

5

; swap them and the winner flips.

The mean is least squares in disguise. The empirical mean of rewards $r_1,\dots,r_n$ minimizes $\sum_i(x-r_i)^2$ : set the derivative $2\sum_i(x-r_i)$ to zero. The contextual version replaces the number $x$ by the vector $\theta$ :

\hat\theta_t=\arg\min_\theta\sum_{s\le t}\big(X_s-\langle A_s,\theta\rangle\big)^2+\lambda\|\theta\|^2=V_t^{-1}b_t,\qquad V_t=\lambda I+\sum_{s\le t}A_sA_s^{\top},\quad b_t=\sum_{s\le t}A_sX_s,

writing $A_s$ for the feature vector actually played. The ridge term $\lambda\|\theta\|^2$ makes $V_t$ invertible from the start; each round adds a positive semidefinite $A_sA_s^\top$ , so $V_t$ only grows.

Confidence ellipsoid (Lattimore–Szepesvári, Ch. 20). For a suitable

\beta_t

growing like

d\log t

, with high probability

\theta^\star

lies in

\mathcal E_t=\big\{\theta:(\theta-\hat\theta_t)^\top V_t(\theta-\hat\theta_t)\le\beta_t\big\}.

Its semi-axes point along the eigenvectors of

V_t

and have lengths

\sqrt{\beta_t/\lambda_i(V_t)}

: directions you have played a lot have large eigenvalues, so the ellipsoid is thin there.

LinUCB. Be optimistic over the ellipsoid:

\max_{\theta\in\mathcal E}\langle x,\theta\rangle=\langle x,\hat\theta\rangle+\sqrt\beta\,\|x\|_{V^{-1}}

with

\|x\|_{V^{-1}}=\sqrt{x^\top V^{-1}x}

. Pull

A_t=\arg\max_a\ \underbrace{\langle x_t(a),\hat\theta_{t-1}\rangle}_{\text{exploit}}+\underbrace{\sqrt{\beta_t}\,\|x_t(a)\|_{V_{t-1}^{-1}}}_{\text{explore}}.

The bonus is large for features pointing in directions you have rarely seen. Its regret is of order

d\sqrt T\log T

, with no dependence on the number of arms.

Explore

Noise level σ

Drag

\theta^\star

.

\hat\theta

and the confidence ellipse

\mathcal E

(here

\beta=1

). Grey arrows are the five arms' features; the teal one is LinUCB's next pull, and the teal dot is the optimistic

\theta

in

\mathcal E

that makes it look best.

Worked example

Two arms with fixed features $x_1=(1,0)$ , $x_2=(0,1)$ , $\lambda=1$ , $\beta=1$ . Arm 1 pays $0.6$ every time it is pulled. Ties go to arm 1. Run LinUCB.

Round 1: $V_0=I$ , $\hat\theta_0=0$ . Indices?

Both $0+\sqrt{1}=1$ . Tie: arm 1, reward $0.6$ . Now $V_1=\mathrm{diag}(2,1)$ , $b_1=(0.6,0)$ , $\hat\theta_1=(0.3,0)$ .
Round 2: indices?

$\mathrm{UCB}_1=0.3+\sqrt{1/2}\approx1.007$ , $\mathrm{UCB}_2=0+1=1$ . Arm 1 again, reward $0.6$ : $V_2=\mathrm{diag}(3,1)$ , $\hat\theta_2=(0.4,0)$ .
Round 3?

$\mathrm{UCB}_1=0.4+\sqrt{1/3}\approx0.977<1=\mathrm{UCB}_2$ . Arm 2, which has never been tried, wins on its bonus alone: its direction is the long axis of the ellipse.
With orthogonal features like these, LinUCB reduces to something you have seen. What?

$V$ is diagonal with entries $1+n_a$ , so $\hat\theta_a=\frac{\sum r}{1+n_a}$ (a mean shrunk toward 0 by the ridge term) and the bonus is $\sqrt{\beta/(1+n_a)}$ . That is UCB with one coordinate per arm. LinUCB gains when features overlap, so one pull informs several arms.

Check your understanding

You have played $x=(1,0)$ a hundred times and $x=(0,1)$ twice. The confidence ellipse is:

Thin along the first axis and long along the second.
Long along the first axis and thin along the second.More data in a direction means more certainty there.
A circle, since $\beta$ is the same in every direction. $\beta$ is one number, but $V$ is not a multiple of $I$ .

V=\mathrm{diag}(101,3)

, so the semi-axes are

\sqrt{\beta/101}

and

\sqrt{\beta/3}

. The axes shrink like

1/\sqrt{\text{data in that direction}}

.

Why does LinUCB's regret not grow with the number of arms $K$ ?

It estimates the $d$ coordinates of $\theta^\star$ , and every arm's mean is determined by them.
It only ever pulls $d$ of the arms.It can pull any arm; it just doesn't need to try each one separately.

With many arms, plain UCB must try each one. LinUCB learns

\theta^\star

, and a good estimate of

\theta^\star

ranks all arms at once, even arms (or contexts) it has never seen.

What is $\max_{\theta\in\mathcal E}\langle x,\theta\rangle$ ?

$\langle x,\hat\theta\rangle+\sqrt\beta\|x\|$ That is the answer for a ball of radius $\sqrt\beta$ , i.e. $V=I$ .
$\langle x,\hat\theta\rangle+\sqrt\beta\,\|x\|_{V^{-1}}$

Write

\theta=\hat\theta+V^{-1/2}u

with

\|u\|\le\sqrt\beta

. Then

\langle x,\theta\rangle=\langle x,\hat\theta\rangle+\langle V^{-1/2}x,u\rangle

, maximized by Cauchy–Schwarz at

\sqrt\beta\|V^{-1/2}x\|=\sqrt\beta\sqrt{x^\top V^{-1}x}

.

Practice

Least squaresDerive the formula

Show that $\hat\theta=V^{-1}b$ minimizes $\sum_s(X_s-\langle A_s,\theta\rangle)^2+\lambda\|\theta\|^2$ .

Solution

The gradient is $-2\sum_s(X_s-A_s^\top\theta)A_s+2\lambda\theta$ . Using $(A_s^\top\theta)A_s=A_sA_s^\top\theta$ , setting it to zero gives $(\lambda I+\sum_sA_sA_s^\top)\theta=\sum_sA_sX_s$ , i.e. $V\theta=b$ . The objective is strictly convex for $\lambda>0$ ( $V$ is positive definite), so this is the unique minimizer.

Reading an ellipseFrom V to a picture

With $\hat\theta=0$ , $\beta=1$ and $V=\mathrm{diag}(9,4)$ , describe $\mathcal E$ and compute the bonus of $x=(1,0)$ and $x=(0,1)$ .

Solution

$9\theta_1^2+4\theta_2^2\le1$ : an ellipse with semi-axes $1/3$ along $\theta_1$ and $1/2$ along $\theta_2$ . Bonuses: $\sqrt{1/9}=1/3$ and $\sqrt{1/4}=1/2$ , exactly the semi-axis in the feature's direction. (Note it is $V$ , not $V^{-1}$ , in the ellipse: with $V^{-1}$ the set would grow as data arrives.)

InteractiveSutton–Barto, Ch. 3: Finite Markov Decision Processes

MDPs, policies and trajectories

A bandit is a single state. A Markov decision process has many, and your action decides not only the reward but also, at random, which state you land in next. Good choices now have to account for where they send you.

The idea

Episodic MDP. A finite set of states arranged in layers

h=0,1,\dots,H-1

, a set of actions at each state, a reward

r_h(x,a)

and transition probabilities

P_h(x'\mid x,a)

to the next layer. An episode starts at

x_0

; at each layer you take an action, collect its reward and are moved to a random next state; after layer

H-1

the episode ends and a new one starts from

x_0

.

Policy. A rule

\pi

that says which action to take in each state:

\pi_h(x)\in\mathcal A

, or more generally a probability distribution over actions. A deterministic policy is the special case that puts probability 1 on one action.

Trajectory. The states, actions and rewards one episode actually visits:

x_0,a_0,r_0,x_1,a_1,r_1,\dots

. The same policy gives different trajectories on different episodes, because transitions are random. The return of an episode is

\sum_h r_h

; the value of the policy is its expected return.

What the learner actually sees. The figure shows every reward and transition probability so you can follow along. A learner sees none of them: only the state it is in, the action it took, the reward it got and the next state. To learn that an action sends you up with probability $0.9$ , it must take that action many times and count.

Real problems. For a self-driving car the state is everything that matters right now (position, speed, the cars nearby, the weather) and an action might be a steering angle and an acceleration, a rectangle of choices. States and actions are then continuous rather than a handful of circles, but the definitions on this page are the same.

Explore

Feedback

Each circle is a state with two actions. Next to each action: its reward, then its probabilities of going [up, down]. Click an action to put it in your policy (filled dot). the agent.

Worked example

Take the policy “always the first action” ( $a_1$ everywhere) in the MDP above. Find the probability of each trajectory that starts $x_0\to y_1$ , and the policy's expected return.

What is the probability of $x_0\to y_1\to z_2$ , and what does that episode earn?

$0.9\times0.6=0.54$ . Rewards $0.2+0.3+0.7=1.2$ .
List all four trajectories with their probabilities.

$x_0y_1z_1$ : $0.9\cdot0.4=0.36$ , return $0.8$ . $x_0y_1z_2$ : $0.54$ , return $1.2$ . $x_0y_2z_1$ : $0.1\cdot0.1=0.01$ , return $1.0$ . $x_0y_2z_2$ : $0.1\cdot0.9=0.09$ , return $1.4$ . The probabilities add to 1.
Expected return?

$0.36(0.8)+0.54(1.2)+0.01(1.0)+0.09(1.4)=0.288+0.648+0.01+0.126=1.072$ . Run this policy for 1,000 episodes in the figure and the average lands near $1.072$ , never exactly on it.

Check your understanding

How many deterministic policies does the MDP in the figure have?

$2\times3=6$ A policy chooses at every state, not every layer.
$2^3=8$ There are five states with choices, not three.
$2^5=32$

Five states, two actions each, chosen independently. In general the count is

|\mathcal A|^{|\mathcal S|}

, which is why no one finds the best policy by trying them all.

You run the same policy twice and get returns $1.6$ and $2.0$ . What changed?

The policy picked different actions.A deterministic policy picks the same action every time it is in the same state.
The random transitions sent the agent to different states.

Same policy, different trajectories. That is why a policy is judged by its expected return, and why estimating that expectation takes many episodes.

In the “total only” mode the learner sees one number per episode. What is lost?

Nothing: the total is what we want to maximize.It is the objective, but it hides which step earned it.
Credit assignment: which actions along the way were responsible for a good or bad total.

With aggregate (or end-of-episode, success/failure) feedback, a crash at the last step and a bad choice at the first step look the same. Learning is harder and needs more episodes; robotics tasks with a single success signal are like this.

Practice

A bandit is a one-state MDPFit the definitions

Describe a $K$ -armed bandit played for $T$ rounds as an episodic MDP. What are $H$ , the states, and the episodes?

Solution

$H=1$ , a single state $x_0$ , $K$ actions with rewards drawn from the arms, and each episode is one round, so there are $T$ episodes. Transitions play no role: there is no next state to influence. Everything new in MDPs comes from transitions.

Simulating by handEstimate a probability

You take action $a_2$ at $x_0$ fifteen times and go up 8 times. What is your estimate of $P(y_1\mid x_0,a_2)$ , and roughly how far from the truth (0.8) could it reasonably be?

Solution

$8/15\approx0.53$ . The standard deviation of a 15-sample average of a Bernoulli $(0.8)$ is $\sqrt{0.8\cdot0.2/15}\approx0.10$ , so $0.53$ is about 2.6 standard deviations low: unlucky but possible. Hoeffding gives a two-sided 95% radius of $\sqrt{\log(2/0.05)/30}\approx0.35$ . With fifteen samples you know the probability only roughly.

Animated lessonSutton–Barto, Ch. 4: Dynamic Programming; Jin et al. (2018), §2

Value functions and backward induction

At the last layer the best action is obvious: take the bigger reward. Knowing the value of the last layer makes the layer before it easy too, and so on back to the start. That is the whole of dynamic programming.

The idea

Value functions. For a policy

\pi

, the value of state

x

at layer

h

is the expected sum of rewards from there to the end, following

\pi

:

V_h^\pi(x)=\mathbb E\Big[\sum_{h'=h}^{H-1}r_{h'}\big(x_{h'},\pi(x_{h'})\big)\ \Big|\ x_h=x\Big].

The Q-value is the same, except that the first action is fixed to

a

and

\pi

is followed afterwards:

Q_h^\pi(x,a)=\underbrace{r_h(x,a)}_{\text{now}}+\underbrace{\sum_{x'}P_h(x'\mid x,a)\,V_{h+1}^\pi(x')}_{\text{expected future}},\qquad V_h^\pi(x)=Q_h^\pi\big(x,\pi(x)\big),

with

V_H\equiv0

after the last layer. (Jin et al. number the layers from 1; we start at 0 to match the figure.)

Bellman optimality. Define

V_H^\star\equiv0

and, going backwards,

Q_h^\star(x,a)=r_h(x,a)+\sum_{x'}P_h(x'\mid x,a)\,V_{h+1}^\star(x'),\qquad V_h^\star(x)=\max_aQ_h^\star(x,a).

Then

V_h^\star(x)\ge V_h^\pi(x)

for every policy

\pi

, and the greedy policy

\pi^\star_h(x)=\arg\max_aQ_h^\star(x,a)

attains it. One backward sweep finds an optimal policy, at a cost of

|\mathcal S|\,|\mathcal A|

multiply-adds per next state, instead of trying

|\mathcal A|^{|\mathcal S|}

policies.

Why does weighting by transition probabilities give the right answer? After taking $a$ you land in $x'$ with probability $P(x'\mid x,a)$ , and from there, by definition, you expect $V_{h+1}(x')$ more. The expected future is the average of these, and the reward of $a$ itself is added on top.

Watch

The MDP from the previous module. Values

V^\star

are written above each state as they are found; the chosen action is filled.

Start at the end. After the last layer there is nothing left to earn, so $V^\star=0$ at the terminal state.
Layer 2, state $z_1$ : both actions end the episode, so $Q^\star$ is just the reward: $0.3$ and $0.4$ . Take the larger: $V^\star(z_1)=0.4$ .
Layer 2, state $z_2$ : $Q^\star=0.7$ and $0.8$ , so $V^\star(z_2)=0.8$ .
Layer 1, state $y_1$ . Now the future matters: $Q^\star(y_1,a_1)=0.3+0.4(0.4)+0.6(0.8)=0.94$ and $Q^\star(y_1,a_2)=0.4+0.5(0.4)+0.5(0.8)=1.00$ . So $V^\star(y_1)=1.00$ .
Layer 1, state $y_2$ : $Q^\star=0.5+0.1(0.4)+0.9(0.8)=1.26$ and $0.6+0.3(0.4)+0.7(0.8)=1.28$ . So $V^\star(y_2)=1.28$ .
Layer 0: $Q^\star(x_0,a_1)=0.2+0.9(1.00)+0.1(1.28)=1.228$ and $Q^\star(x_0,a_2)=0.8+0.8(1.00)+0.2(1.28)=1.856$ . $V^\star(x_0)=1.856$ .
Read the optimal policy off the filled dots: $a_2$ everywhere. No other policy has a higher expected return than $1.856$ .

Worked example

Evaluate the policy $\pi=$ “ $a_1$ everywhere” by the same backward recursion (no max: use the policy's action). Then compute its regret per episode.

Layer 2.

$V^\pi(z_1)=0.3$ , $V^\pi(z_2)=0.7$ .
Layer 1.

$V^\pi(y_1)=0.3+0.4(0.3)+0.6(0.7)=0.84$ ; $V^\pi(y_2)=0.5+0.1(0.3)+0.9(0.7)=1.16$ .
Layer 0, and the gap to optimal.

$V^\pi(x_0)=0.2+0.9(0.84)+0.1(1.16)=1.072$ , matching the trajectory-by-trajectory computation in the previous module. The regret of one episode of $\pi$ is $V^\star(x_0)-V^\pi(x_0)=1.856-1.072=0.784$ .

Check your understanding

Why start at the last layer rather than the first?

At the last layer $Q^\star$ is just the reward; every earlier $Q^\star$ needs the values of the layer after it.
It's a convention; going forward works equally well.Forward, you would need the future values before you have them.

The recursion expresses layer

h

in terms of layer

h+1

. Going backwards, everything on the right-hand side is already known.

$V_h^\pi(x)$ and $Q_h^\pi(x,a)$ are equal when:

$a=\pi_h(x)$ , the action the policy takes anyway.
$a$ is the action with the higher reward.Reward alone ignores the future.
Always. $Q$ lets the first action differ from $\pi$ 's.

Q^\pi(x,a)

asks “what if I take

a

now and follow

\pi

after?” If

a

is what

\pi

would do, nothing changes.

In this MDP the optimal action at $x_0$ also has the higher immediate reward. Is that always so?

Yes: a bigger reward now can only help.It can send you to worse states.
No: a smaller reward can be optimal if it leads to more valuable states.

Q^\star

adds the reward to the expected future value. The first practice problem below builds an example where the smaller reward wins.

Practice

When greedy is wrongChange one action

Suppose action $a_1$ at $x_0$ always led to $y_2$ (probability 1) and paid reward $r$ . Everything else is unchanged. For which $r$ is $a_1$ the optimal first action, even though $r<0.8$ ?

Solution

Layers 1 and 2 are unchanged, so $V^\star(y_2)=1.28$ and $Q^\star(x_0,a_1)=r+1.28$ . $Q^\star(x_0,a_2)=1.856$ as before. So $a_1$ is optimal when $r>0.576$ . For $0.576<r<0.8$ , the optimal first action has the smaller reward: it buys a guaranteed trip to the better state $y_2$ .

Counting the workWhy the recursion is cheap

An MDP has $H$ layers of $S$ states each and $A$ actions per state, with any state reachable from any state in the previous layer. How many multiplications does backward induction need, and how does that compare with evaluating every deterministic policy?

Solution

Each $Q^\star_h(x,a)$ is a sum over $S$ next states: $S$ multiplications. There are $HSA$ of them, so $HS^2A$ in total. There are $A^{HS}$ deterministic policies. For $H=10$ , $S=10$ , $A=2$ : 2,000 multiplications versus $2^{100}$ policies.

SimulationJin et al. (2018); Sutton–Barto, Ch. 6

Learning an unknown MDP

Backward induction needs the rewards and transition probabilities. A reinforcement-learning agent has to estimate them by playing, and the estimates are only ever approximately right. It is the bandit problem again, now with states: explore enough to learn, exploit enough to earn.

The idea

Regret over episodes (Jin et al. 2018). The agent plays

K

episodes, using policy

\pi_k

in episode

k

. Its regret is

\mathrm{Regret}(K)=\sum_{k=1}^K\Big(V_0^\star(x_0)-V_0^{\pi_k}(x_0)\Big).

Each term is the expected shortfall of that episode's policy against the optimal one; as for bandits, it is nonnegative and measured in expectation, and the agent cannot compute it.

Plug-in learning. Keep counts. Estimate $\hat r(x,a)$ as the average reward seen and $\hat P(x'\mid x,a)$ as the fraction of times $a$ led to $x'$ . Run backward induction on the estimates and follow the resulting policy. This is “certainty equivalence”: act as if the estimates were the truth. It has greedy's weakness: an action whose first outcomes were unlucky gets a low estimate and may never be tried again.

Optimism again. Add a bonus

c/\sqrt{n(x,a)}

to each estimated reward, where

n(x,a)

counts visits, and run backward induction on the optimistic model. Rarely tried actions look good until they have been tried enough. Algorithms built this way (UCB-VI, and the optimistic Q-learning of Jin et al.) have regret of order

\sqrt{K}

times a polynomial in

H

,

S

and

A

.

Model-free learning. Q-learning skips $\hat P$ and updates $Q(x,a)$ directly from each observed step, $Q\leftarrow(1-\alpha)Q+\alpha\big(r+\max_{a'}Q(x',a')\big)$ : a running average of one-sample Bellman updates. Jin et al. show that with an optimistic bonus it is also provably efficient.

Explore

Bonus constant c

The MDP of the previous modules, with Bernoulli rewards. Average regret of 100 agents over 400 episodes. plug-in (no bonus) optimistic (bonus

c/\sqrt n

). Shaded: the middle 80%.

Worked example

After a few episodes the plug-in agent has tried $a_2$ at $x_0$ four times, always reaching $y_1$ with total reward $1.6$ each time ( $0.8+0.4+0.4$ ), and has tried $a_1$ at $x_0$ once, getting reward $0$ (a Bernoulli $(0.2)$ reward came up 0) and reaching $y_1$ .

What are $\hat r(x_0,a_1)$ and $\hat r(x_0,a_2)$ ?

$\hat r(x_0,a_1)=0$ from one sample; $\hat r(x_0,a_2)$ is the average of four rewards with mean $0.8$ , say $0.75$ .
Here the plug-in agent is right to prefer $a_2$ . In which situation would the same mechanism hurt it?

When the unlucky action is the good one. In the “when greedy is wrong” variant of the previous module, $a_1$ is optimal; one unlucky sample makes $\hat Q(x_0,a_1)$ small, and the agent may stop trying it for a long time.
What does the optimistic agent compute for $a_1$ with $c=1$ ?

$\hat r+c/\sqrt n=0+1/\sqrt1=1$ at $x_0$ , plus optimistic values downstream: $a_1$ now looks attractive, so it is tried again until its count makes the bonus small. The bonus is the price of being sure.

Check your understanding

An agent's estimate $\hat P(y_1\mid x_0,a_2)$ is $8/15$ , but the truth is $0.8$ . The best way to close the gap is to:

Take $a_2$ at $x_0$ more often: the estimate converges as the count grows.
Run backward induction more carefully.Planning is exact; the input is what's wrong.

By the law of large numbers the estimate converges, with error of order

1/\sqrt n

. An RL agent controls its own data: it only learns about actions it takes. That is the root of the exploration problem.

With a very large bonus constant $c$ , the optimistic agent's regret is high early. Why?

It keeps exploring actions it already knows are worse, because the bonus still dominates their estimates.
Large bonuses make backward induction unstable.The bonus just adds to the rewards; nothing becomes unstable.

Too little optimism risks locking in; too much wastes episodes. Theory picks

c

large enough for the confidence intervals to be valid; in practice it is tuned. Try both ends of the slider.

Regret per episode $V_0^\star(x_0)-V_0^{\pi_k}(x_0)$ uses expected values. If an agent follows $\pi^\star$ and gets an unlucky return of 1.2, its regret for that episode is:

$1.856-1.2=0.656$ That uses the realized return.
$0$

Regret compares policies, not outcomes. Following the optimal policy costs nothing, however the dice fall.

Practice

Where regret comes fromA simulation-lemma view

Suppose the agent's estimates are within $\varepsilon$ of the truth in every reward and within $\varepsilon$ in total variation in every transition, and values lie in $[0,H]$ . Argue that the policy planned on the estimates loses at most about $2H^2\varepsilon$ in value.

Hint

Compare $V^\pi$ under the true and estimated models one layer at a time: each layer adds a reward error $\varepsilon$ and a transition error of at most $\varepsilon H$ .

Solution

For any fixed policy, the true and estimated values differ by at most $\varepsilon+\varepsilon H$ per layer, so by at most $H(1+H)\varepsilon$ overall. The planned policy $\hat\pi$ is optimal for the estimate, so $V^\star-V^{\hat\pi}\le(V^\star-\hat V^{\pi^\star})+(\hat V^{\pi^\star}-\hat V^{\hat\pi})+(\hat V^{\hat\pi}-V^{\hat\pi})\le2H(1+H)\varepsilon$ , the middle term being $\le0$ . Accurate models give near-optimal policies; the hard part is getting accurate where it matters.

Bandits inside MDPsA lower bound

Explain why an RL algorithm on episodic MDPs with $A$ actions must have regret at least of order $\sqrt{AK}$ in the worst case.

Solution

Take $H=1$ and one state: the MDP is an $A$ -armed bandit played for $K$ rounds, and the bandit lower bound $c\sqrt{AK}$ applies. Richer MDPs contain such bandits at every state, which is how the lower bounds that grow with $H$ and $S$ are built.

InteractiveGoodfellow–Bengio–Courville, Ch. 6: Deep Feedforward Networks

Neural networks as functions

A neural network is just a family of functions with adjustable weights, and machine learning, at its core, is picking the member of the family that fits the data. The family is built from one simple principle: an affine map followed by a nonlinearity, repeated. (In reinforcement learning, this is how value functions and policies are represented once states are continuous.)

The idea

Learning is function fitting. Given data $(x_i,y_i)$ , find a function $f$ with $f(x_i)\approx y_i$ , then predict $f(x)$ at inputs you haven't seen. The family of functions you search matters: if it only contains straight lines and the data curve, every prediction will be off.

Feedforward network. Each node takes a weighted sum of every node in the previous layer plus a bias, and applies an activation

\sigma

. In matrix form, one layer is

h\mapsto\sigma(Wh+b)

, and a network with two hidden layers is

f_\theta(x)=W_3\,\sigma\big(W_2\,\sigma(W_1x+b_1)+b_2\big)+b_3,

where

\theta

collects every weight matrix and bias vector. The input layer's size is the input dimension (two nodes means

x\in\R^2

); the width is the number of nodes in a hidden layer and the depth is the number of hidden layers.

Without an activation, depth buys nothing. If

\sigma

is the identity,

W_3(W_2(W_1x+b_1)+b_2)+b_3=Mx+c

: a composition of affine maps is affine. However many layers, the network draws a plane.

Universal approximation (Cybenko 1989; Leshno et al. 1993; Goodfellow et al. §6.4.1). With any continuous activation that is not a polynomial, for example

\mathrm{ReLU}(z)=\max(0,z)

, one hidden layer suffices: for every continuous

g

on a compact set

K

and every

\varepsilon>0

there is a network with

\sup_{x\in K}|f_\theta(x)-g(x)|<\varepsilon

.

The theorem says a good network exists; it does not say how wide it must be, or how to find its weights. Smaller $\varepsilon$ generally needs more parameters, and under smoothness assumptions on $g$ one can say how many. In the figure, a ReLU network with $n$ hidden units is the piecewise-linear interpolant at $n+1$ points; for twice-differentiable $g$ its error falls like $1/n^2$ .

Explore

Target

Activation

Hidden units n

target

g

network

f_\theta

. The faint lines are the hidden units' contributions, each a scaled

\max(0,x-k)

with its kink at a knot

k

.

Worked example

A network $\R^2\to\R$ with one hidden layer of two ReLU units: $h_1=\mathrm{ReLU}(x_1-2x_2+0.1)$ , $h_2=\mathrm{ReLU}(-x_1+x_2)$ , output $y=h_1+3h_2-1$ . Evaluate it at $x=(1,-1)$ and $x=(-1,1)$ .

Forward pass at $(1,-1)$ .

$h_1=\mathrm{ReLU}(1+2+0.1)=3.1$ , $h_2=\mathrm{ReLU}(-2)=0$ . $y=3.1+0-1=2.1$ .
Forward pass at $(-1,1)$ .

$h_1=\mathrm{ReLU}(-1-2+0.1)=0$ , $h_2=\mathrm{ReLU}(2)=2$ . $y=0+6-1=5$ .
Count the parameters, and say what the network looks like as a function.

First layer: a $2\times2$ matrix and 2 biases (6); output: 2 weights and 1 bias (3). Total 9. Each ReLU is zero on one side of a line and linear on the other, so $f$ is piecewise linear with at most four pieces, cut by the lines $x_1-2x_2+0.1=0$ and $x_2=x_1$ . Large networks are the same thing with far more pieces.

Check your understanding

A network has ten hidden layers of width 100, but no activation functions. It can represent:

Any continuous function, given enough layers.Composing affine maps never leaves the affine maps.
Only affine functions $x\mapsto Mx+c$ .

The nonlinearity is what lets layers build on each other. Even the very simple

\max(0,z)

, two linear pieces glued together, is enough for universal approximation.

Universal approximation guarantees that:

Training by gradient descent will find a network within $\varepsilon$ of the target.It says nothing about training.
Some network within $\varepsilon$ of the target exists, of some size.
A network with a fixed number of units can approximate every continuous function.The size depends on $\varepsilon$ and on the target.

Existence, not construction and not size. Rates (how many parameters for a given

\varepsilon

) need extra assumptions on the target, and they are what make bigger models more expressive.

In the figure, the steep step needs many more units than sin for the same error. Why?

Piecewise-linear interpolation error is controlled by the target's slope and curvature, and the step is very steep in one place.
ReLU networks cannot represent increasing functions.Each unit is increasing; sums of them certainly can be.

With knots spaced

h

apart, the error is at most

\tfrac{h^2}8\max|g''|

, or

\tfrac h2\max|g'|

. Spending knots evenly wastes them on the flat parts; putting them where the function bends is what training (or adaptive knots) does.

Practice

The hat functionThree ReLUs make a bump

Write the hat $g(x)=\max(0,1-|x|)$ as a combination of ReLUs $\max(0,x-k)$ .

Solution

$g(x)=\mathrm{ReLU}(x+1)-2\,\mathrm{ReLU}(x)+\mathrm{ReLU}(x-1)$ . Check: for $x\le-1$ all are 0; on $[-1,0]$ it is $x+1$ ; on $[0,1]$ it is $x+1-2x=1-x$ ; for $x\ge1$ , $x+1-2x+x-1=0$ . Three hidden units. Sums of shifted hats are exactly the piecewise-linear interpolants, which proves universal approximation in one dimension.

Error versus widthA rate

Using $n$ equally spaced pieces on $[-1,1]$ , how many hidden units are needed to approximate $g(x)=\sin(3x)$ to within $10^{-3}$ ?

Solution

$h=2/n$ , $|g''|\le9$ , so the error is at most $\frac{(2/n)^2}{8}\cdot9=\frac{4.5}{n^2}$ . Need $n^2\ge4500$ : $n\ge68$ . Ten times more accuracy costs only about $\sqrt{10}\approx3.2$ times more units, because $g$ is smooth.

InteractiveGoodfellow–Bengio–Courville, Ch. 8: Optimization for Training Deep Models

Gradient descent, momentum and mini-batches

Fitting a network means minimizing a loss over its weights. Gradient descent does it by walking downhill: from wherever you are, take a small step in the direction in which the loss decreases fastest.

The idea

Why the negative gradient? The rate of change of $L$ in a unit direction $v$ is the directional derivative $\nabla L\cdot v=\|\nabla L\|\,\|v\|\cos\phi$ , where $\phi$ is the angle between them. It is most negative when $\cos\phi=-1$ , that is, when $v$ points opposite to $\nabla L$ . So

w_{t+1}=w_t-\alpha\,\nabla L(w_t).

The gradient says which way to go, not how far: the learning rate $\alpha$ is a choice. In machine learning $L(\theta)=\frac1N\sum_{i=1}^N\ell\big(f_\theta(x_i),y_i\big)$ is the average loss over the data, and computing its gradient through the network's layers is backpropagation.

Quadratics, one direction at a time. For

L(w)=\tfrac12(w-w^\star)^\top H(w-w^\star)

with

H

symmetric positive definite,

\nabla L=H(w-w^\star)

, so

w_{t+1}-w^\star=(I-\alpha H)(w_t-w^\star).

Along an eigenvector of

H

with eigenvalue

\lambda

, the error is multiplied by

1-\alpha\lambda

each step. Steep directions (large

\lambda

) need

\alpha<2/\lambda_{\max}

or the iterates blow up; flat directions (small

\lambda

) then crawl at rate

1-\alpha\lambda_{\min}

. The ratio

\kappa=\lambda_{\max}/\lambda_{\min}

sets the speed: about

\kappa

steps per factor of

e

.

Momentum (heavy ball). Keep part of the previous step:

w_{t+1}=w_t-\alpha\nabla L(w_t)+\beta\,(w_t-w_{t-1}).

In a flat valley the steps all point the same way and add up; across a narrow valley they alternate and cancel. Well tuned, it needs about

\sqrt\kappa

steps instead of

\kappa

.

Mini-batches. With millions of data points, use the average gradient over a random batch

B_t

of

|B|

of them:

g_t=\frac1{|B|}\sum_{i\in B_t}\nabla\ell_i

. It is unbiased,

\mathbb E[g_t]=\nabla L

, but noisy, with variance shrinking like

1/|B|

. The noise is the price of cheap steps, and it keeps the iterates jittering near the minimum unless

\alpha

is decreased.

Explore

Steepness ratio κ Learning rate α Momentum β Batch noise

Contours of

L(w)=\tfrac12(w_1^2+\kappa w_2^2)

; the minimum is at the centre. Drag the start. the first 60 steps.

Worked example

$L(w)=\tfrac12(w_1^2+10w_2^2)$ , so $H=\mathrm{diag}(1,10)$ . Start at $w_0=(1,1)$ .

With $\alpha=0.1$ : the per-step factors in each coordinate, and $w_t$ .

$1-0.1\cdot1=0.9$ and $1-0.1\cdot10=0$ . So $w_1=(0.9,0)$ : the steep coordinate is solved in one step, and $w_t=(0.9^t,0)$ after that. Reaching $|w_1|<10^{-3}$ takes $t\ge66$ steps.
With $\alpha=0.25$ ?

Factors $0.75$ and $1-2.5=-1.5$ . The second coordinate flips sign and grows by 1.5 each step: divergence, since $\alpha>2/\lambda_{\max}=0.2$ .
What is the best fixed $\alpha$ , and how fast is it?

Balance the two factors: $1-\alpha=-(1-10\alpha)$ , so $\alpha=2/11$ and both have size $9/11=\frac{\kappa-1}{\kappa+1}\approx0.82$ . About 35 steps for three digits. Momentum improves this to roughly $\frac{\sqrt\kappa-1}{\sqrt\kappa+1}\approx0.52$ per step.

Check your understanding

Why step against the gradient rather than along it?

$\nabla L\cdot v=\|\nabla L\|\|v\|\cos\phi$ is smallest at $\phi=\pi$ : the loss falls fastest opposite to the gradient.
Along the gradient the step would be too long.Length is set by $\alpha$ ; direction is the issue.

The gradient points uphill, in the direction of fastest increase. Gradient ascent (

+\alpha\nabla L

) maximizes, as in policy-gradient methods that maximize expected return.

On an ill-conditioned quadratic ( $\kappa=100$ ) plain gradient descent is slow because:

$\alpha$ must be below $2/\lambda_{\max}$ for the steep direction, which makes progress in the flat direction tiny.
The gradient points away from the minimum.It points downhill, just not at the minimum: it zigzags across the valley.

One learning rate serves all directions. Momentum, preconditioning and adaptive methods (Adam) are different ways around this.

Doubling the batch size $|B|$ changes the mini-batch gradient's standard deviation by a factor of:

$1/2$ That is the variance, not the standard deviation.
$1/\sqrt2$
$1$ : the noise comes from the data, not the batch.Averaging more independent samples reduces it.

The average of

|B|

independent gradients has variance

\sigma^2/|B|

. Twice the work per step buys only

\sqrt2

less noise, which is one reason small batches are popular.

Practice

The gradient of a quadraticThree lines

For $L(w)=\tfrac12w^\top Hw-q^\top w$ with $H$ symmetric, show $\nabla L=Hw-q$ , find the minimizer, and rewrite gradient descent as $w_{t+1}-w^\star=(I-\alpha H)(w_t-w^\star)$ .

Solution

$\partial_k\tfrac12\sum_{ij}H_{ij}w_iw_j=\tfrac12\sum_j(H_{kj}+H_{jk})w_j=(Hw)_k$ by symmetry, and $\partial_kq^\top w=q_k$ . The minimizer solves $Hw^\star=q$ . Then $w_{t+1}=w_t-\alpha(Hw_t-q)=w_t-\alpha H(w_t-w^\star)$ ; subtract $w^\star$ .

Momentum on a lineThe characteristic equation

Apply heavy ball to $L(w)=\tfrac\lambda2w^2$ . Show that $e_t=w_t$ satisfies $e_{t+1}=(1+\beta-\alpha\lambda)e_t-\beta e_{t-1}$ , and find when it converges for $\beta=0.5$ , $\lambda=1$ .

Solution

Substitute $\nabla L=\lambda w$ . The roots of $z^2-(1+\beta-\alpha\lambda)z+\beta=0$ have product $\beta=0.5$ ; the iteration converges iff both have modulus below 1, which (Jury's test) means $|1+\beta-\alpha\lambda|<1+\beta$ : $0<\alpha<3$ . Momentum enlarges the stable range from $\alpha<2$ to $\alpha<2(1+\beta)$ .