Machine Learning · Lecture 21a

Lecture 21a
Reinforcement Learning I: Bandits, MDPs and Dynamic Programming

Part VI · Decisions  |  the agent–environment loop, returns and discounting, multi-armed bandits, ε-greedy, UCB and Thompson sampling, regret and its lower bound, logged bandit data and off-policy evaluation, Markov decision processes, value functions, Bellman equations, value iteration and policy iteration  |  reading: Sutton & Barto (2018), ch. 1–4; Lattimore & Szepesvári (2020), ch. 1–8; Auer, Cesa-Bianchi & Fischer (2002)  |  learning from experience follows in Lecture 21b

Cartoon: the favourite restaurantA stick figure stands between two restaurants. One is labelled "my usual", the other "new place". A speech bubble says: the usual is good, but the new place might be better. my usual new place The usual is good.The new place mightbe better.
Exploit what you know, or explore what you might be missing: the dilemma at the heart of reinforcement learning
In this lecture
  1. The agent–environment loop
  2. Multi-armed bandits
  3. Markov decision processes and value functions
  4. Bellman equations and dynamic programming
  5. Summary, exercises, projects, reading

Every method so far learned from a fixed data set. Reinforcement learning (RL) learns by acting: an agent tries actions, sees what happens, and improves. The data now depend on the agent's own choices, and nobody provides the right answer, only a reward. Two tensions run through the subject. Should the agent exploit what it already knows, or explore to learn more? And should it wait for the true outcome of its actions, which is unbiased but noisy, or trust its own estimates, which are stable but biased? This page treats the first tension and the case where the environment is known; Lecture 21b treats learning from experience.

By the end you should be able to define returns, policies and value functions; compare ε-greedy, UCB and Thompson sampling by their regret, and prove the UCB1 regret bound; explain why logged bandit data need importance weighting; write the Bellman equations; and prove that value iteration and policy iteration find an optimal policy.

1 — The agent–environment loop

At each time step \(t\) the agent observes a state \(S_t\), chooses an action \(A_t\), and the environment returns a reward \(R_{t+1}\) and a new state \(S_{t+1}\). A policy \(\pi(a\mid s)\) is the agent's rule for choosing actions. The agent's goal is not the next reward but the total it will collect.

definition 21.1 — return and discounting

The return from time \(t\) is the discounted sum of future rewards,

$$G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\cdots=\sum_{k\ge0}\gamma^kR_{t+k+1},$$

with discount factor \(0\le\gamma\le1\). A reward received \(k\) steps after the next one counts \(\gamma^{k}\) as much as the next reward. With \(\gamma<1\) and bounded rewards the sum is finite; \(\gamma\) close to 1 makes the agent far-sighted.

Three things make RL harder than supervised learning. The feedback is a score, not a label: a reward says how good an action was, not which action would have been best. Rewards are delayed: a move that wins a game may come many steps before the win. And the data are not independent: what the agent sees next depends on what it did.

code — the interaction loop: a random agent on slippery ice
# The agent-environment loop: a random agent on FrozenLake (4 x 4, slippery ice)
import numpy as np, gymnasium as gym, warnings; warnings.filterwarnings('ignore')
env = gym.make('FrozenLake-v1', is_slippery=True)
print("map (S start, F frozen, H hole, G goal):", " / ".join(b"".join(r).decode() for r in env.unwrapped.desc))
print("from the square left of the goal, action 'right' leads to:",
      ", ".join(f"square {s2} with probability {pr:.2f}" + (" (goal, reward 1)" if r else "") for pr, s2, r, _ in env.unwrapped.P[14][2]))
rng = np.random.default_rng(0); wins, lengths = 0, []
for ep in range(10_000):
    s, _ = env.reset(seed=int(rng.integers(1 << 30))); done, t = False, 0
    while not done:
        a = int(rng.integers(4))                                  # the policy: pick one of the four moves at random
        s, r, term, trunc, _ = env.step(a); done = term or trunc; t += 1
    wins += r; lengths.append(t)
print(f"random policy, 10,000 episodes: reaches the goal in {wins / 10_000:.1%}, mean episode length {np.mean(lengths):.1f} steps")
for gam in (0.9, 0.99):
    print(f"discount gamma = {gam}: a reward of 1 after 6 steps is worth {gam ** 5:.3f} now; after 30 steps {gam ** 29:.3f}")
map (S start, F frozen, H hole, G goal): SFFF / FHFH / FFFH / HFFG
from the square left of the goal, action 'right' leads to: square 14 with probability 0.33, square 15 with probability 0.33 (goal, reward 1), square 10 with probability 0.33
random policy, 10,000 episodes: reaches the goal in 1.4%, mean episode length 7.6 steps
discount gamma = 0.9: a reward of 1 after 6 steps is worth 0.590 now; after 30 steps 0.047
discount gamma = 0.99: a reward of 1 after 6 steps is worth 0.951 now; after 30 steps 0.747

The ice is slippery: the intended move happens only a third of the time, and the agent slides sideways otherwise. Acting at random, it reaches the goal in 1.4% of episodes; most end within a few steps in a hole (mean length 7.6 steps). The discount sets how much the far future matters: with \(\gamma=0.9\) a reward 30 steps away is worth 0.047 of a reward now, with \(\gamma=0.99\) it is worth 0.747.

2 — Multi-armed bandits

The simplest RL problem has a single state. A multi-armed bandit (after the "one-armed bandit", a slot machine) has \(K\) actions, or arms. Pulling arm \(a\) gives a random reward with unknown mean \(\mu_a\). Which advert to show, which version of a web page to serve, which treatment to give the next patient: each is a bandit problem. A good policy must find the best arm while not wasting too many pulls on the others.

definition 21.2 — regret

Let \(\mu^*=\max_a\mu_a\) and \(\Delta_a=\mu^*-\mu_a\) be the gap of arm \(a\). The regret of a policy after \(T\) rounds is the expected reward lost by not always pulling the best arm,

$$\mathcal R_T=T\mu^*-\mathbb E\Big[\sum_{t=1}^TR_t\Big]=\sum_a\Delta_a\,\mathbb E[N_a(T)],$$

where \(N_a(T)\) is the number of pulls of arm \(a\). Good policies have regret that grows like \(\log T\): they eventually stop pulling bad arms, except rarely.

Three classic policies:

ε-greedy pulls the arm with the best average reward so far, except that with probability \(\varepsilon\) it pulls a random arm. It is simple, but it keeps exploring at the same rate forever, so its regret grows linearly in \(T\).

UCB1 (upper confidence bound; Auer, Cesa-Bianchi and Fischer, 2002) pulls the arm with the largest optimistic estimate

$$\hat\mu_a+\sqrt{\frac{2\ln t}{N_a}} .$$

The bonus is large for arms tried rarely and shrinks as \(N_a\) grows: optimism in the face of uncertainty.

Thompson sampling (Thompson, 1933) keeps a posterior distribution for each \(\mu_a\), draws one sample from each, and pulls the arm whose sample is largest. Each arm is pulled with exactly the probability that it is the best, given the data so far.

theorem 21.1 — UCB1 has logarithmic regret (Auer et al., 2002)

For rewards in \([0,1]\), every suboptimal arm \(a\) satisfies

$$\mathbb E[N_a(T)]\;\le\;\frac{8\ln T}{\Delta_a^2}+1+\frac{\pi^2}{3},$$

so the regret of UCB1 is

$$\mathcal R_T\;\le\;\sum_{a:\Delta_a>0}\Big(\frac{8\ln T}{\Delta_a}+\big(1+\tfrac{\pi^2}{3}\big)\Delta_a\Big)=O(\log T).$$

Write \(c_{t,s}=\sqrt{2\ln t/s}\) and \(\ell=\lceil8\ln T/\Delta_a^2\rceil\). After arm \(a\) has been pulled \(\ell\) times, it can be pulled again at time \(t\) only if its index beats the best arm's:

$$\hat\mu^*_{s}+c_{t,s}\;\le\;\hat\mu_{a,s_a}+c_{t,s_a}\qquad\text{for some }s\lt t,\ \ell\le s_a\lt t .$$

This requires at least one of three events:

  1. \(\hat\mu^*_s\le\mu^*-c_{t,s}\): the best arm is badly underestimated;
  2. \(\hat\mu_{a,s_a}\ge\mu_a+c_{t,s_a}\): arm \(a\) is badly overestimated;
  3. \(\mu^*<\mu_a+2c_{t,s_a}\): the gap is smaller than twice the bonus.

Event 3 is impossible once \(s_a\ge\ell\), because then \(2c_{t,s_a}\le2\sqrt{2\ln T/\ell}\le\Delta_a\). By Hoeffding's inequality, events 1 and 2 each have probability at most \(e^{-4\ln t}=t^{-4}\).

Summing over all \(t\), \(s\) and \(s_a\),

$$\mathbb E[N_a(T)]\le\ell+\sum_{t\ge1}\sum_{s=1}^{t}\sum_{s_a=1}^{t}2t^{-4}\le\ell+\sum_{t\ge1}2t^{-2}=\ell+\frac{\pi^2}{3}.$$

Since \(\ell\le8\ln T/\Delta_a^2+1\), this gives the bound. Multiplying by \(\Delta_a\) and summing over arms gives the regret. \(\square\)

theorem 21.2 — the Lai–Robbins lower bound (1985)

For Bernoulli arms, every policy whose regret is \(o(T^\alpha)\) for all \(\alpha>0\) on every instance satisfies

$$\liminf_{T\to\infty}\frac{\mathcal R_T}{\ln T}\;\ge\;\sum_{a:\Delta_a>0}\frac{\Delta_a}{\mathrm{KL}(\mu_a,\mu^*)},$$

where \(\mathrm{KL}(p,q)=p\ln\frac pq+(1-p)\ln\frac{1-p}{1-q}\). (Statement.) Thompson sampling and KL-UCB attain this constant; UCB1 attains the \(\log T\) rate with a larger constant.

code — ε-greedy, UCB1 and Thompson sampling, 200 runs of 50,000 rounds
# Multi-armed bandits: epsilon-greedy, UCB1 and Thompson sampling on five arms with click rates of 4-12%
mu = np.array([0.12, 0.10, 0.08, 0.06, 0.04])                    # arm 0 is best
K, T, runs = len(mu), 50_000, 200; best = mu.max()
def play(policy, seed):
    g = np.random.default_rng(seed); n = np.zeros((runs, K)); s = np.zeros((runs, K)); regret = np.zeros(T); idx = np.arange(runs)
    for t in range(T):
        if policy == 'ucb1':
            a = np.where(n.min(1) == 0, n.argmin(1), (s / np.maximum(n, 1) + np.sqrt(2 * np.log(t + 1) / np.maximum(n, 1))).argmax(1))
        elif policy == 'thompson':
            a = g.beta(1 + s, 1 + n - s).argmax(1)                         # sample a click rate per arm from its posterior
        else:
            eps = float(policy.split('=')[1]); greedy = (s / np.maximum(n, 1) + 1e-9 * g.random((runs, K))).argmax(1)
            a = np.where(g.random(runs) < eps, g.integers(K, size=runs), greedy)
        r = g.random(runs) < mu[a]; n[idx, a] += 1; s[idx, a] += r; regret[t] = best - mu[a].mean()
    return np.cumsum(regret), n.mean(0)
res = {pol: play(pol, 1) for pol in ['eps=0.1', 'eps=0.01', 'ucb1', 'thompson']}
print(f"{K} arms, best click rate {best}, {T:,} rounds, averaged over {runs} runs")
print("policy          regret after 1,000 / 10,000 / 50,000 rounds   growth per unit of ln T (10k-50k)   pulls of the best arm")
for pol, (R, pulls) in res.items():
    print(f"{pol:14s}  {R[999]:7.1f} {R[9999]:7.1f} {R[-1]:7.1f}               {(R[-1] - R[9999]) / np.log(T / 10_000):6.1f}                       {pulls[0] / T:.0%}")
kl = lambda p, q: p * np.log(p / q) + (1 - p) * np.log((1 - p) / (1 - q))
lr = sum((best - m) / kl(m, best) for m in mu[1:])
print(f"Lai-Robbins lower bound: for any consistent policy, regret eventually grows by at least {lr:.1f} per unit of ln T")
5 arms, best click rate 0.12, 50,000 rounds, averaged over 200 runs
policy          regret after 1,000 / 10,000 / 50,000 rounds   growth per unit of ln T (10k-50k)   pulls of the best arm
eps=0.1            20.3    96.1   289.9                120.5                       84%
eps=0.01           25.5   151.2   362.5                131.3                       73%
ucb1               34.0   247.6   719.0                292.9                       61%
thompson           21.1    61.9    85.6                 14.7                       94%
Lai-Robbins lower bound: for any consistent policy, regret eventually grows by at least 19.7 per unit of ln T

Thompson sampling wins clearly: regret 85.6 after 50,000 rounds, with 94% of pulls on the best arm. Its regret grows by about 14.7 per unit of \(\ln T\) late in the run, close to the Lai–Robbins constant of 19.7 (the bound holds only in the limit, so a finite run can sit a little below it). ε-greedy with \(\varepsilon=0.1\) learns quickly, but its regret keeps rising in a straight line (289.9), because it never stops pulling bad arms one time in ten. The surprise is UCB1, the worst here (719.0). Its bonus \(\sqrt{2\ln t/N_a}\) is built for the worst case, rewards spread over \([0,1]\); with click rates near 0.1 the bonus dwarfs the differences between arms, so it explores for a long time. Its regret is still logarithmic, but with a large constant. KL-UCB (Exercise 6) fixes this by using a confidence bound suited to rare clicks.

010,00020,00030,00040,00050,0000200400600round tcumulative regretε-greedy, ε = 0.1ε-greedy, ε = 0.01UCB1Thompson sampling
Cumulative regret of the four policies on the five-arm problem, averaged over 200 runs.

Bandit arena

Three agents play the same five-armed bandit for 5,000 rounds, facing the same random clicks. Watch the regret curves and how each agent spreads its pulls. Change ε, or the seed, and run again.

bayes — Thompson sampling is posterior sampling

For click/no-click rewards, put a Beta(1, 1) prior on each click rate. After \(s\) clicks in \(n\) pulls the posterior is Beta\((1+s,1+n-s)\) (Lecture 5). Thompson sampling draws one rate from each posterior and acts as if the draws were true. Uncertain arms produce widely spread draws and are sometimes chosen; well-known bad arms almost never are. Exploration falls out of the posterior with no tuning parameter. The same idea extends to whole MDPs: posterior sampling for reinforcement learning (Osband, Russo and Van Roy, 2013) samples one MDP from the posterior at the start of each episode and follows its optimal policy. The fully Bayesian alternative, planning in a Bayes-adaptive MDP whose state includes the posterior, is optimal but usually intractable.

data — the Open Bandit Dataset (ZOZOTOWN)

Saito, Aihara, Matsutani and Narita (NeurIPS Datasets and Benchmarks, 2021) released about 26 million impressions from ZOZOTOWN, a large Japanese fashion e-commerce site, collected in a seven-day experiment in late November 2019. Each impression records which of 80 items was shown in one of three positions, whether it was clicked, and the probability (propensity) with which the logging policy chose it. Two policies ran side by side: uniform random and Bernoulli Thompson sampling. The obp package (PyPI) ships a 10,000-impression sample from each policy, which we use; the full archive is too large for the build environment.

code — off-policy evaluation with inverse propensity weighting
# Logged bandit feedback from ZOZOTOWN: estimate one policy's click rate from another policy's logs
import pandas as pd
base = 'data/obd_raw/obp/dataset/obd'
rnd = pd.read_csv(f'{base}/random/all/all.csv', index_col=0); bts = pd.read_csv(f'{base}/bts/all/all.csv', index_col=0)
print(f"uniform-random policy logs: {len(rnd):,} impressions, {rnd.click.sum()} clicks, click rate {rnd.click.mean():.4f}")
print(f"Bernoulli Thompson sampling logs: {len(bts):,} impressions, {bts.click.sum()} clicks, click rate {bts.click.mean():.4f}")
print(f"items: {rnd.item_id.nunique()}; logged propensity under the random policy {rnd.propensity_score.iloc[0]:.4f} (= 1/80); "
      f"under Thompson sampling from {bts.propensity_score.min():.5f} to {bts.propensity_score.max():.2f}")
# estimate the random policy's click rate from the Thompson-sampling logs alone
w = (1 / 80) / bts.propensity_score.values; c = bts.click.values
naive, ipw = c.mean(), np.mean(w * c)
g = np.random.default_rng(0); boot = [np.mean((w * c)[i]) for i in (g.integers(0, len(c), len(c)) for _ in range(2000))]
print(f"\nestimating the random policy's click rate from the Thompson logs:")
print(f"  naive (average click of the logs)          {naive:.4f}")
print(f"  inverse propensity weighting               {ipw:.4f}   (95% bootstrap interval {np.percentile(boot, 2.5):.4f} to {np.percentile(boot, 97.5):.4f})")
tr = rnd.click.mean(); se = np.sqrt(tr * (1 - tr) / len(rnd))
print(f"  truth, from the random policy's own logs   {tr:.4f}   (95% interval {tr - 1.96 * se:.4f} to {tr + 1.96 * se:.4f})")
print(f"  importance weights range from {w.min():.3f} to {w.max():.1f}; effective sample size {w.sum() ** 2 / (w ** 2).sum():,.0f} of {len(w):,}")
uniform-random policy logs: 10,000 impressions, 38 clicks, click rate 0.0038
Bernoulli Thompson sampling logs: 10,000 impressions, 42 clicks, click rate 0.0042
items: 80; logged propensity under the random policy 0.0125 (= 1/80); under Thompson sampling from 0.00005 to 0.95

estimating the random policy's click rate from the Thompson logs:
  naive (average click of the logs)          0.0042
  inverse propensity weighting               0.0024   (95% bootstrap interval 0.0010 to 0.0043)
  truth, from the random policy's own logs   0.0038   (95% interval 0.0026 to 0.0050)
  importance weights range from 0.013 to 277.8; effective sample size 340 of 10,000

The naive estimate, 0.0042, is simply the Thompson policy's own click rate: it answers the wrong question. Inverse propensity weighting reweights each logged click by how much more (or less) often the random policy would have shown that item. Its estimate, 0.0024, has an interval (0.0010 to 0.0043) that contains the truth from the random policy's own logs (0.0038), but the interval is wide. Some items were almost never shown by Thompson sampling, so their weights reach 277.8, and the 10,000 impressions are worth an effective sample of only 340. With 38 and 42 clicks in the two samples, even the truth is uncertain (0.0026 to 0.0050). On the full data set (millions of impressions) these intervals shrink; the bias–variance trade-off of off-policy evaluation does not go away.

causal — logged bandit data are observational data

A log records outcomes only for the actions the logging policy chose. Estimating how another policy would have done is a counterfactual question, like estimating a treatment effect from observational data (Lecture 13). If the logging policy chose action \(a\) in context \(x\) with known probability \(\pi_0(a\mid x)\), the inverse propensity weighting (IPW) estimate of a new policy \(\pi\)'s value,

$$\hat V_{\text{IPW}}(\pi)=\frac1n\sum_{i=1}^n\frac{\pi(a_i\mid x_i)}{\pi_0(a_i\mid x_i)}\,r_i ,$$

is unbiased, provided \(\pi_0\) gives every action that \(\pi\) might take a positive probability. The weights reweight the logged population into the one the new policy would have produced, exactly as propensity scores do in causal inference. The price is variance: rare actions get huge weights. Doubly robust estimators (Dudík, Langford and Li, 2011) add a reward model to reduce it.

big picture — bandits in production

Bandits are the most widely deployed form of RL. Web companies use them instead of fixed A/B tests, so that traffic moves to the better version while the test runs. Yahoo!'s front page chose news articles with contextual bandits (Li, Chu, Langford and Schapire, 2010), and the same approach selects adverts, thumbnails and notifications. Adaptive clinical trials shift patients towards better-performing treatments as evidence accumulates, an idea that goes back to Thompson's 1933 paper, written with medical trials in mind. In all these settings the logs are later reused to evaluate new policies offline, with the weighting of the causal box above.

3 — Markov decision processes and value functions

Bandits have one state. In most problems actions also change the situation: a move in a game changes the board, a step on the ice changes where you stand. The standard model is the Markov decision process.

definition 21.3 — Markov decision process

A Markov decision process (MDP) consists of states \(\mathcal S\), actions \(\mathcal A\), transition probabilities and expected rewards

$$p(s'\mid s,a),\qquad r(s,a)=\mathbb E\big[R_{t+1}\mid S_t=s,A_t=a\big],$$

and a discount factor \(\gamma\). It is Markov: what happens next depends on the history only through the current state and action.

definition 21.4 — value functions and optimal policies

The state value of policy \(\pi\) is the expected return from state \(s\), and the action value is the expected return after taking action \(a\) in \(s\) and following \(\pi\) afterwards:

$$v_\pi(s)=\mathbb E_\pi\big[G_t\mid S_t=s\big],\qquad q_\pi(s,a)=\mathbb E_\pi\big[G_t\mid S_t=s,A_t=a\big].$$

A policy \(\pi^*\) is optimal if \(v_{\pi^*}(s)\ge v_\pi(s)\) for every state and every policy. All optimal policies share the optimal value functions \(v^*\) and \(q^*\), and acting greedily with respect to \(q^*\) is optimal:

$$\pi^*(s)=\arg\max_aq^*(s,a).$$

Value functions turn a long-horizon problem into a one-step one. If you knew \(q^*\), you would never need to look ahead: the best action now is the one with the largest \(q^*\). Most of RL is about estimating these functions.

4 — Bellman equations and dynamic programming

The value of a state equals the reward of the next step plus the discounted value of where you land. Written out, this gives a system of equations, one per state.

definition 21.5 — Bellman equations

For a policy \(\pi\), the value function is the unique solution of the Bellman expectation equation

$$v_\pi(s)=\sum_a\pi(a\mid s)\Big[r(s,a)+\gamma\sum_{s'}p(s'\mid s,a)\,v_\pi(s')\Big].$$

The optimal value function solves the Bellman optimality equation \(v^*=\mathcal Tv^*\), where

$$(\mathcal Tv)(s)=\max_a\Big[r(s,a)+\gamma\sum_{s'}p(s'\mid s,a)\,v(s')\Big].$$

When the MDP is known, the Bellman equations can be solved by dynamic programming (Bellman, 1957). Value iteration applies the operator repeatedly, \(v_{k+1}=\mathcal Tv_k\). Policy iteration alternates two steps: evaluate the current policy exactly (a linear system), then improve it by acting greedily with respect to its value.

theorem 21.3 — the Bellman optimality operator is a contraction

For \(\gamma<1\) and any two value functions \(u\), \(v\),

$$\lVert\mathcal Tu-\mathcal Tv\rVert_\infty\;\le\;\gamma\,\lVert u-v\rVert_\infty .$$

Hence \(\mathcal T\) has a unique fixed point \(v^*\), and value iteration converges to it from any start, geometrically:

$$\lVert v_k-v^*\rVert_\infty\le\gamma^k\lVert v_0-v^*\rVert_\infty .$$

For any two functions of \(a\), \(|\max_af(a)-\max_ag(a)|\le\max_a|f(a)-g(a)|\). Apply this in each state with \(f\) and \(g\) the bracketed terms for \(u\) and \(v\); the rewards cancel:

$$|(\mathcal Tu)(s)-(\mathcal Tv)(s)|\le\gamma\max_a\sum_{s'}p(s'\mid s,a)\,|u(s')-v(s')|\le\gamma\lVert u-v\rVert_\infty ,$$

because the probabilities sum to 1. Take the maximum over \(s\).

The space of bounded value functions with the sup norm is complete, so Banach's fixed-point theorem gives a unique fixed point. Applying the contraction \(k\) times to \(v_0\) and \(v^*=\mathcal Tv^*\) gives the geometric rate. \(\square\)

theorem 21.4 — policy improvement; policy iteration terminates

Let \(\pi\) and \(\pi'\) be deterministic policies with

$$q_\pi\big(s,\pi'(s)\big)\;\ge\;v_\pi(s)\qquad\text{for all }s .$$

Then \(v_{\pi'}(s)\ge v_\pi(s)\) for all \(s\). In a finite MDP, policy iteration therefore reaches an optimal policy after finitely many improvements.

Start from the assumption and expand \(q_\pi\) one step, then apply the assumption again in the next state:

$$v_\pi(s)\le q_\pi(s,\pi'(s))=\mathbb E_{\pi'}\big[R_{t+1}+\gamma v_\pi(S_{t+1})\mid S_t=s\big]\le\mathbb E_{\pi'}\big[R_{t+1}+\gamma R_{t+2}+\gamma^2v_\pi(S_{t+2})\mid S_t=s\big]\le\cdots$$

The limit of the right-hand side is \(\mathbb E_{\pi'}[G_t\mid S_t=s]=v_{\pi'}(s)\).

The greedy policy \(\pi'(s)=\arg\max_aq_\pi(s,a)\) satisfies the assumption, so each improvement step never makes any state worse. If it makes no state strictly better, then \(v_\pi\) satisfies the Bellman optimality equation, so \(\pi\) is optimal. Otherwise the new policy is strictly better somewhere, so no policy repeats. A finite MDP has finitely many deterministic policies (\(|\mathcal A|^{|\mathcal S|}\)), so the process stops. \(\square\)

code — value iteration and policy iteration on FrozenLake
# Dynamic programming on FrozenLake: value iteration and policy iteration from the transition table
def tables(env):
    P = env.unwrapped.P; nS, nA = len(P), len(P[0]); Pm = np.zeros((nS, nA, nS)); Rm = np.zeros((nS, nA))
    for s in P:
        for a in P[s]:
            for pr, s2, r, term in P[s][a]: Pm[s, a, s2] += pr; Rm[s, a] += pr * r
    for s in range(nS):                                           # holes and the goal are absorbing: no further reward
        if env.unwrapped.desc.ravel()[s] in b'HG': Pm[s] = 0; Pm[s, :, s] = 1; Rm[s] = 0
    return Pm, Rm
def value_iteration(Pm, Rm, gamma, tol=1e-10):
    v = np.zeros(Pm.shape[0]); gaps = []
    while True:
        v_new = (Rm + gamma * Pm @ v).max(1); gaps.append(np.abs(v_new - v).max()); v = v_new   # Bellman optimality operator
        if gaps[-1] < tol: return v, (Rm + gamma * Pm @ v).argmax(1), gaps
def policy_iteration(Pm, Rm, gamma):
    nS = Pm.shape[0]; pi = np.zeros(nS, int); k = 0
    while True:
        k += 1; Ppi, Rpi = Pm[np.arange(nS), pi], Rm[np.arange(nS), pi]
        v = np.linalg.solve(np.eye(nS) - gamma * Ppi, Rpi)                    # policy evaluation: solve the Bellman equation exactly
        new = (Rm + gamma * Pm @ v).argmax(1)                                 # policy improvement: act greedily
        if np.all((Rm + gamma * Pm @ v)[np.arange(nS), new] <= (Rm + gamma * Pm @ v)[np.arange(nS), pi] + 1e-12): return v, pi, k
        pi = new
arrow = np.array(['<', 'v', '>', '^'])
for name in ['4x4', '8x8']:
    e = gym.make('FrozenLake-v1', map_name=name, is_slippery=True); Pm, Rm = tables(e); gamma = 0.99
    v, pi, gaps = value_iteration(Pm, Rm, gamma); v2, pi2, k = policy_iteration(Pm, Rm, gamma)
    ratio = max(gaps[i + 1] / gaps[i] for i in range(len(gaps) - 1) if gaps[i] > 1e-12)
    wins = 0
    for ep in range(10_000):
        s, _ = e.reset(seed=ep); done = False
        while not done: s, r, term, trunc, _ = e.step(int(pi[s])); done = term or trunc
        wins += r
    print(f"FrozenLake {name}, gamma = {gamma}: value iteration converged in {len(gaps)} sweeps (largest ratio of successive changes "
          f"{ratio:.4f} <= gamma); policy iteration in {k} improvements; same optimal values: {np.allclose(v, v2, atol=1e-6)}")
    print(f"  value of the start {v[0]:.3f}; the optimal policy reaches the goal in {wins / 10_000:.1%} of 10,000 simulated episodes (episodes stop after {e.spec.max_episode_steps} steps)")
    if name == '4x4':
        desc = e.unwrapped.desc.ravel()
        print("  optimal policy:", " / ".join("".join(c.decode() if c in b'HG' else arrow[pi[i * 4 + j]] for j, c in enumerate(desc[i * 4:(i + 1) * 4])) for i in range(4)))
FrozenLake 4x4, gamma = 0.99: value iteration converged in 571 sweeps (largest ratio of successive changes 0.9900 <= gamma); policy iteration in 8 improvements; same optimal values: True
  value of the start 0.542; the optimal policy reaches the goal in 73.7% of 10,000 simulated episodes (episodes stop after 100 steps)
  optimal policy: <^^^ / <H<H / ^v<H / H>vG
FrozenLake 8x8, gamma = 0.99: value iteration converged in 662 sweeps (largest ratio of successive changes 0.9897 <= gamma); policy iteration in 5 improvements; same optimal values: True
  value of the start 0.415; the optimal policy reaches the goal in 62.6% of 10,000 simulated episodes (episodes stop after 100 steps)

Both methods find the same optimal values. Value iteration needs 571 sweeps on the 4 × 4 map, and the ratio of successive changes is 0.9900: the error shrinks by a factor \(\gamma\) per sweep, exactly the rate of Theorem 21.3. Policy iteration needs only 8 improvements, each one solving a linear system. The optimal policy raises the success rate from 1.4% to 73.7%, and it is cautious in an instructive way: from the start it pushes left, into the wall. Since the ice slips sideways, pushing into a wall means the only possible slips are up or down, never into a hole. On the 8 × 8 map the optimal policy succeeds in 62.6% of episodes.

Gridworld: watch value iteration

Click cells to place walls, pits (−1) and goals (+1), choose how slippery the floor is, then sweep. Each sweep applies the Bellman optimality operator once: value spreads outwards from the goal, and the arrows show the greedy policy. With a slippery floor and a small step cost, the best path keeps away from pits even if it is longer.

spot check 21.1

A state gives reward 1 at every step forever, with \(\gamma=0.9\). What is its value?

Sum the geometric series \(1+\gamma+\gamma^2+\cdots\).
\(1/(1-0.9)=10\). The quantity \(1/(1-\gamma)\) is often called the effective horizon: with \(\gamma=0.99\) the agent looks about 100 steps ahead.
history — from cats in boxes to the Turing Award

Edward Thorndike's cats (1898) escaped from puzzle boxes faster with practice, and his "law of effect" (actions followed by satisfaction are repeated) is reinforcement in its plainest form. William Thompson proposed posterior sampling for medical trials in 1933. Richard Bellman named dynamic programming and the equation that bears his name in the 1950s (Dynamic Programming, 1957). Arthur Samuel's checkers program (1959) improved by playing itself, and Donald Michie's MENACE (1961) learned noughts and crosses with 304 matchboxes of coloured beads. Christopher Watkins introduced Q-learning in his 1989 PhD thesis; Gerald Tesauro's TD-Gammon (1992) reached expert backgammon by temporal-difference learning; and DeepMind's DQN (Mnih et al., 2015) learned dozens of Atari games from pixels. Andrew Barto and Richard Sutton received the 2024 Turing Award for the conceptual and algorithmic foundations of reinforcement learning.

quantum — a quadratic speed-up for exploration

Finding the best arm with a classical algorithm needs about \(\sum_a1/\Delta_a^2\) pulls. Wang, You, Li and Childs (AAAI, 2021) showed that if each arm can be pulled as a quantum oracle, in superposition, quantum amplitude estimation finds it with about \(\sqrt{\sum_a1/\Delta_a^2}\) queries: a quadratic gain, the same as Grover search. The assumption is strong. A real advert or treatment cannot be "pulled in superposition"; the oracle model fits simulated or physical systems that are themselves quantum. As elsewhere in this course, the speed-up is real but lives in a specific access model.

5 — Summary, exercises, projects, reading

summary
exercises
  1. Show that ε-greedy with a fixed \(\varepsilon>0\) has regret at least \(\varepsilon\,T\,\bar\Delta\), where \(\bar\Delta=\frac1K\sum_a\Delta_a\).

    In every round, with probability \(\varepsilon\) the policy pulls an arm uniformly at random, which costs \(\bar\Delta\) in expectation. The greedy rounds cost at least 0. Summing over \(T\) rounds, \(\mathcal R_T\ge\varepsilon T\bar\Delta\), which grows linearly. A schedule \(\varepsilon_t\propto1/t\) removes the linear term, but the constant must be tuned to the unknown gaps.

  2. An arm has a Beta(1, 1) prior on its click rate and has been shown 200 times with 9 clicks. What is its posterior, and its posterior mean? Why does Thompson sampling still sometimes choose an arm with a lower posterior mean than another?

    The posterior is Beta\((1+9,\,1+191)=\)Beta(10, 192), with mean \(10/202\approx0.050\).

    Thompson sampling chooses the arm with the largest draw. An arm shown only a few times has a wide posterior, so its draw is sometimes large even if its mean is lower. As evidence accumulates the posteriors narrow and such choices become rare. This is how exploration fades out on its own.

  3. Derive the Bellman expectation equation of Definition 21.5 from the definition of \(v_\pi\), using \(G_t=R_{t+1}+\gamma G_{t+1}\) and the Markov property.

    \(v_\pi(s)=\mathbb E_\pi[R_{t+1}+\gamma G_{t+1}\mid S_t=s]\). Condition on the action and the next state:

    $$v_\pi(s)=\sum_a\pi(a\mid s)\sum_{s'}p(s'\mid s,a)\big(\mathbb E[R_{t+1}\mid s,a,s']+\gamma\,\mathbb E_\pi[G_{t+1}\mid S_{t+1}=s']\big).$$

    By the Markov property, the expected return from \(s'\) does not depend on how we got there, so it equals \(v_\pi(s')\). Summing the reward term over \(s'\) gives \(r(s,a)\).

  4. A two-state MDP: in state 1 the agent can stay (reward 1, remain in 1) or move (reward 0, go to state 2); state 2 gives reward 2 per step forever. With \(\gamma=0.9\), find \(v^*\) and the optimal action in state 1. For which \(\gamma\) does the answer change?

    \(v^*(2)=2/(1-0.9)=20\). In state 1, staying forever is worth \(1/(1-0.9)=10\), moving is worth \(0+0.9\times20=18\). So \(v^*(1)=18\) and the agent moves.

    In general staying gives \(1/(1-\gamma)\) and moving \(2\gamma/(1-\gamma)\). Moving is better when \(2\gamma>1\), that is \(\gamma>0.5\). A short-sighted agent takes the immediate reward.

  5. Show that the IPW estimate in the causal box is unbiased when \(\pi_0(a\mid x)>0\) whenever \(\pi(a\mid x)>0\).

    For one logged round, with \(x\) drawn from the context distribution, \(a\sim\pi_0(\cdot\mid x)\) and \(r\) drawn given \((x,a)\):

    $$\mathbb E\Big[\frac{\pi(a\mid x)}{\pi_0(a\mid x)}r\Big]=\mathbb E_x\sum_a\pi_0(a\mid x)\frac{\pi(a\mid x)}{\pi_0(a\mid x)}\bar r(x,a)=\mathbb E_x\sum_a\pi(a\mid x)\bar r(x,a)=V(\pi).$$

    If \(\pi_0(a\mid x)=0\) for an action that \(\pi\) uses, that action never appears in the log, and no reweighting can recover its reward.

  6. (Code.) Implement KL-UCB, which pulls the arm maximising the largest \(q\) with \(N_a\,\mathrm{KL}(\hat\mu_a,q)\le\ln t\) (solve for \(q\) by bisection), and add it to the bandit comparison. How does its regret compare with UCB1 and Thompson sampling?

    For each arm, bisect on \(q\in[\hat\mu_a,1]\) until \(N_a\,\mathrm{KL}(\hat\mu_a,q)\) reaches \(\ln t\). KL-UCB's confidence bound adapts to the small variance of rare clicks, unlike UCB1's \(\sqrt{2\ln t/N_a}\), which is designed for the worst case of rewards spread over \([0,1]\). Expect regret close to Thompson sampling's and far below UCB1's: KL-UCB attains the Lai–Robbins constant (Garivier and Cappé, 2011).

student projects

Each project uses this lecture's methods and public data, and has a clear result.

1. Off-policy evaluation on the Open Bandit Dataset

question
Can logs from one policy predict how another would have performed, and which estimator comes closest to the truth?
data
The full Open Bandit Dataset (about 26 million impressions, two logging policies, three campaigns), with each policy's own logs as the ground truth for the other.
method
Direct method (a click model), IPW, self-normalised IPW and doubly robust estimators, with the obp package; bootstrap intervals; how accuracy depends on sample size and on clipping large weights.
outcome
A comparison of estimators against the on-policy ground truth, reproducing and extending Saito et al. (2021).

2. Bandits for choosing practice problems

question
If a tutoring system chose the next practice problem with a bandit, how quickly would students reach mastery compared with a fixed sequence?
data
A public ASSISTments data set of student answers, used to fit a simple model of how each skill's success probability grows with practice.
method
A simulator built from the fitted model; ε-greedy, UCB and Thompson sampling over skills, with reward defined as learning gain; comparison with the order used in the data; sensitivity to the simulator's assumptions.
outcome
Simulated time to mastery for each policy, with a frank discussion of how far a simulator built from logs can be trusted.

Reading and sources

Data. Open Bandit Dataset samples (10,000 impressions each from the uniform-random and Bernoulli Thompson sampling policies, "all" campaign) shipped with the obp package (PyPI, version 0.4.1), from Saito et al. (2021); the full data are at research.zozo.com/data.html. FrozenLake: Gymnasium (Farama Foundation), FrozenLake-v1. The bandit problems are simulated.

numbers in the text not printed by a code box are computed in verify_L21a.py, figures in figs_L21a.py; code-box outputs are pasted from actual runs (numpy, pandas and Gymnasium on two CPU cores)