29  Reinforcement Learning and Statistical Learning Theory

Core idea: reinforcement learning is statistical learning with feedback. A policy controls which data are collected, and the learner must estimate long-run values from dependent, policy-dependent samples. Statistical learning theory gives the language for finite-sample guarantees: concentration inequalities, confidence sets, sample complexity, regret, optimism under uncertainty, and generalization.

29.1 Learning goals

After reading this chapter, students should be able to:

• explain why reinforcement learning is statistically harder than supervised learning;
• use concentration inequalities to construct confidence intervals for rewards and transition probabilities;
• define sample complexity, PAC learning, and regret for sequential decision problems;
• derive the upper-confidence-bound idea in multi-armed bandits;
• explain optimism under uncertainty for finite MDPs;
• connect model-estimation error to value-function error;
• distinguish prediction error, control error, and exploration error;
• describe why function approximation introduces generalization and distribution-shift challenges;
• use simulation to study regret, confidence radii, and finite-sample error;
• use AI tools responsibly to check assumptions behind statistical guarantees.

29.2 26.1 Why statistical learning theory is needed in RL

In dynamic programming, we assumed that the transition kernel and reward function were known:

\[ P(s'\mid s,a), \qquad r(s,a)=E[R_{t+1}\mid S_t=s,A_t=a]. \]

Under that assumption, algorithms such as policy iteration and value iteration solve an optimization problem. In reinforcement learning, however, \(P\) and \(r\) are usually unknown. The agent observes samples

\[ (S_t,A_t,R_{t+1},S_{t+1}), \]

and must learn from them.

This creates three statistical difficulties.

First, the samples are dependent. The state \(S_{t+1}\) is generated from \(S_t\) and \(A_t\), so observations are not iid.

Second, the data distribution is policy-dependent. If the agent changes its policy, it changes which states and actions will be observed.

Third, the goal is long-run control, not merely one-step prediction. A small error in transition estimation may be amplified by the planning horizon.

For a discounted problem, the effective horizon is approximately

\[ H_{\mathrm{eff}} \approx \frac{1}{1-\gamma}. \]

Thus the statistical difficulty increases rapidly as \(\gamma\) approaches one.

Statistical viewpoint. Dynamic programming asks: if \(P\) and \(r\) are known, what is optimal? Statistical learning theory asks: if \(P\) and \(r\) are estimated from data, how many samples are needed to act nearly optimally with high probability?

29.3 26.2 From estimation to decision-making

Let \(\pi\) be a fixed policy. The value function satisfies

\[ V^\pi = r_\pi + \gamma P_\pi V^\pi, \]

so

\[ V^\pi=(I-\gamma P_\pi)^{-1}r_\pi. \]

If \(r_\pi\) and \(P_\pi\) are unknown, we may estimate them from data:

\[ \widehat r_\pi, \qquad \widehat P_\pi. \]

The plug-in value estimate is

\[ \widehat V^\pi = (I-\gamma \widehat P_\pi)^{-1}\widehat r_\pi. \]

A central theoretical question is:

\[ \|\widehat V^\pi - V^\pi\|_\infty \quad \text{or} \quad |\mu^T\widehat V^\pi - \mu^T V^\pi|. \]

This is a statistical error. It depends on:

• the number of visits to each state-action pair;
• the variance of rewards;
• the transition-estimation error;
• the discount factor \(\gamma\);
• the state and action space sizes;
• the exploration policy that generated the data.

In supervised learning, the usual goal is prediction error. In RL, prediction error is only an intermediate quantity. The final question is whether the learned policy is good:

\[ V^*(s)-V^{\widehat \pi}(s) \leq \varepsilon. \]

29.4 26.3 Concentration inequalities

A basic finite-sample tool is the concentration inequality. Suppose \(X_1,\ldots,X_n\) are iid random variables with \(X_i\in[0,1]\) and mean \(\mu\). Let

\[ \widehat \mu_n=\frac{1}{n}\sum_{i=1}^n X_i. \]

Hoeffding’s inequality gives

\[ P\left(|\widehat \mu_n-\mu|\geq \varepsilon\right) \leq 2\exp(-2n\varepsilon^2). \]

Equivalently, with probability at least \(1-\delta\),

\[ |\widehat \mu_n-\mu| \leq \sqrt{\frac{\log(2/\delta)}{2n}}. \]

This confidence radius has the form

\[ \text{uncertainty} \approx \sqrt{\frac{\log(1/\delta)}{n}}. \]

More samples decrease uncertainty at rate \(n^{-1/2}\).

29.4.1 Interactive: concentration radius

The radius from Hoeffding’s inequality shrinks like \(1/\sqrt n\). This rate is slow enough that high-confidence learning can require many samples.

import numpy as np

rng = np.random.default_rng(7243)
mu = 0.35
n = 80
delta = 0.05
trials = 20_000

samples = rng.binomial(1, mu, size=(trials, n))
hat_mu = samples.mean(axis=1)
radius = np.sqrt(np.log(2 / delta) / (2 * n))
covered = np.abs(hat_mu - mu) <= radius

print("true mean:", mu)
print("sample size:", n)
print("Hoeffding radius:", round(radius, 4))
print("empirical coverage:", round(covered.mean(), 4))
print("target coverage:", 1 - delta)

true mean: 0.35
sample size: 80
Hoeffding radius: 0.1518
empirical coverage: 0.9975
target coverage: 0.95

Hoeffding’s inequality is often conservative, but it is distribution-free. It does not require knowing the variance of the reward distribution.

29.5 26.4 Confidence sets for rewards and transitions

For a finite MDP, suppose the agent has observed \(N(s,a)\) visits to a state-action pair \((s,a)\). The reward mean can be estimated by

\[ \widehat r(s,a) = \frac{1}{N(s,a)}\sum_{i:S_i=s,A_i=a}R_{i+1}. \]

If rewards lie in \([0,1]\), then a confidence interval is

\[ r(s,a) \in \left[ \widehat r(s,a)-\beta_r(s,a), \widehat r(s,a)+\beta_r(s,a) \right] \]

with radius

\[ \beta_r(s,a) = \sqrt{\frac{\log(2SA/\delta)}{2N(s,a)}}. \]

The factor \(SA\) appears because we want the confidence statement to hold simultaneously over many state-action pairs. This is an example of a union bound.

Transition probabilities can be estimated by empirical frequencies:

\[ \widehat P(s'\mid s,a) = \frac{N(s,a,s')}{N(s,a)}. \]

A simple coordinatewise confidence interval is

\[ |\widehat P(s'\mid s,a)-P(s'\mid s,a)| \leq \sqrt{\frac{\log(2S^2A/\delta)}{2N(s,a)}}. \]

This bound is not always sharp, but it captures the essential dependence on sample size.

29.5.1 Interactive: confidence radius by visit count

Rarely visited state-action pairs have large confidence radii. Exploration is the process of reducing these radii where they matter for control.

import numpy as np

rng = np.random.default_rng(7339)
S = 4
A = 2
delta = 0.05

# True transition distribution for one selected state-action pair.
p_true = np.array([0.10, 0.20, 0.30, 0.40])

for n in [20, 100, 500, 2000]:
    next_states = rng.choice(S, size=n, p=p_true)
    counts = np.bincount(next_states, minlength=S)
    p_hat = counts / n
    l1_error = np.abs(p_hat - p_true).sum()
    coord_radius = np.sqrt(np.log(2 * S / delta) / (2 * n))
    print(f"n={n:4d}, p_hat={np.round(p_hat, 3)}, L1 error={l1_error:.3f}, radius={coord_radius:.3f}")

n=  20, p_hat=[0.05 0.25 0.35 0.35], L1 error=0.200, radius=0.356
n= 100, p_hat=[0.08 0.17 0.31 0.44], L1 error=0.100, radius=0.159
n= 500, p_hat=[0.088 0.202 0.308 0.402], L1 error=0.024, radius=0.071
n=2000, p_hat=[0.095 0.197 0.293 0.415], L1 error=0.030, radius=0.036

29.6 26.5 Error propagation through Bellman equations

A one-step estimation error can become a long-run value error. Suppose two reward functions \(r\) and \(\widetilde r\) satisfy

\[ \|r-\widetilde r\|_\infty \leq \varepsilon_r, \]

and use the same transition matrix \(P\) under a fixed policy. Then

\[ V-r = \gamma PV \]

is not the right way to compare the two systems. Instead, subtract their Bellman equations:

\[ V-\widetilde V = (r-\widetilde r)+\gamma P(V-\widetilde V). \]

Therefore

\[ V-\widetilde V =(I-\gamma P)^{-1}(r-\widetilde r). \]

Using

\[ \|(I-\gamma P)^{-1}\|_\infty \leq \frac{1}{1-\gamma}, \]

we obtain

\[ \|V-\widetilde V\|_\infty \leq \frac{\varepsilon_r}{1-\gamma}. \]

Transition errors can be even more costly. If rewards are bounded by \(R_{\max}\), then a simplified bound has the form

\[ \|V-\widetilde V\|_\infty \lesssim \frac{\varepsilon_r}{1-\gamma} + \frac{\gamma R_{\max}}{(1-\gamma)^2}\varepsilon_P, \]

where \(\varepsilon_P\) measures transition error. The factor \((1-\gamma)^{-2}\) explains why model estimation becomes difficult for long-horizon problems.

29.6.1 Interactive: model error amplification

The same one-step estimation error produces much larger value error when \(\gamma\) is close to one.

import numpy as np

P = np.array([
    [0.80, 0.20],
    [0.10, 0.90]
])
P_tilde = np.array([
    [0.76, 0.24],
    [0.14, 0.86]
])
r = np.array([0.2, 1.0])

for gamma in [0.50, 0.80, 0.95, 0.98]:
    V = np.linalg.solve(np.eye(2) - gamma * P, r)
    V_tilde = np.linalg.solve(np.eye(2) - gamma * P_tilde, r)
    err = np.max(np.abs(V - V_tilde))
    print(f"gamma={gamma:.2f}, value error={err:.4f}, V={np.round(V, 3)}")

gamma=0.50, value error=0.0392, V=[0.646 1.877]
gamma=0.80, value error=0.1616, V=[2.455 4.273]
gamma=0.95, value error=0.6403, V=[13.075 15.463]
gamma=0.98, value error=1.5017, V=[34.968 37.516]

29.7 26.6 Multi-armed bandits as the simplest RL theory model

A multi-armed bandit is a one-state reinforcement learning problem. There are \(K\) actions. Each action \(a\) has an unknown mean reward

\[ \mu_a=E[R\mid A=a]. \]

The optimal action is

\[ a^*\in \arg\max_a \mu_a. \]

At time \(t\), the learner chooses \(A_t\) and observes reward \(R_t\). The regret after \(T\) rounds is

\[ \operatorname{Regret}(T) = T\mu^* - E\left[\sum_{t=1}^T R_t\right], \]

where

\[ \mu^* = \max_a \mu_a. \]

Equivalently, if \(N_T(a)\) is the number of times action \(a\) is selected,

\[ \operatorname{Regret}(T) = \sum_{a=1}^K \Delta_a E[N_T(a)], \]

where

\[ \Delta_a=\mu^* - \mu_a. \]

The regret formula reveals the exploration-exploitation tradeoff. Pulling suboptimal arms creates regret, but without exploration the learner may never discover the best arm.

29.8 26.7 Upper confidence bounds

The upper-confidence-bound principle chooses actions according to optimistic estimates:

\[ A_t \in \arg\max_a \left\{ \widehat \mu_t(a) + \sqrt{\frac{2\log t}{N_t(a)}} \right\}. \]

The first term exploits known high-reward actions. The second term explores uncertain actions.

This is called optimism under uncertainty. If an action has not been sampled much, its upper confidence bound may be large, so the agent tries it. If it turns out to be poor, the confidence interval shrinks and the action becomes less attractive.

29.8.1 Interactive: regret of exploration strategies

UCB explores using a shrinking confidence bonus. Constant-\(\epsilon\) exploration keeps exploring forever, which can lead to linear regret if \(\epsilon\) is not decayed.

import numpy as np

rng = np.random.default_rng(2026)
means = np.array([0.10, 0.20, 0.90, 0.40])
K = len(means)
T = 2000

def run_ucb():
    counts = np.zeros(K)
    sums = np.zeros(K)
    rewards = []
    for t in range(1, T + 1):
        if t <= K:
            a = t - 1
        else:
            avg = sums / np.maximum(counts, 1)
            bonus = np.sqrt(2 * np.log(t) / np.maximum(counts, 1))
            a = int(np.argmax(avg + bonus))
        r = rng.binomial(1, means[a])
        counts[a] += 1
        sums[a] += r
        rewards.append(r)
    return np.array(rewards), counts

def run_epsilon_greedy(eps=0.1):
    counts = np.zeros(K)
    sums = np.zeros(K)
    rewards = []
    for t in range(1, T + 1):
        if rng.random() < eps or np.any(counts == 0):
            a = rng.integers(K)
        else:
            avg = sums / np.maximum(counts, 1)
            a = int(np.argmax(avg))
        r = rng.binomial(1, means[a])
        counts[a] += 1
        sums[a] += r
        rewards.append(r)
    return np.array(rewards), counts

ucb_rewards, ucb_counts = run_ucb()
eg_rewards, eg_counts = run_epsilon_greedy(0.1)

opt_mean = means.max()
ucb_regret = T * opt_mean - ucb_rewards.sum()
eg_regret = T * opt_mean - eg_rewards.sum()

print("UCB action counts:", ucb_counts.astype(int))
print("epsilon-greedy action counts:", eg_counts.astype(int))
print("UCB empirical regret:", round(ucb_regret, 2))
print("epsilon-greedy empirical regret:", round(eg_regret, 2))

UCB action counts: [  22   18 1935   25]
epsilon-greedy action counts: [  38   42 1867   53]
UCB empirical regret: 63.0
epsilon-greedy empirical regret: 94.0

29.9 26.8 Regret in finite MDPs

For episodic or continuing MDPs, regret compares the learner’s accumulated reward to the reward that would have been obtained by an optimal policy.

For a finite-horizon episodic MDP with horizon \(H\), the regret after \(K\) episodes can be written as

\[ \operatorname{Regret}(K) = \sum_{k=1}^K \left[ V_1^*(s_{k,1}) - V_1^{\pi_k}(s_{k,1}) \right], \]

where \(\pi_k\) is the policy used in episode \(k\).

For discounted continuing MDPs, a common state-dependent notion is

\[ \operatorname{Regret}(T) = \sum_{t=1}^T \left[ \rho^* - R_t \right] \]

in average-reward settings, or discounted analogues using value functions.

The exact definition depends on the setting, but the purpose is always the same: regret measures how much reward is lost while learning.

Typical regret bounds for tabular RL have the qualitative form

\[ \operatorname{Regret}(T) = \widetilde O\left(\sqrt{\text{problem size}\times T}\right), \]

where \(\widetilde O\) hides logarithmic factors. Sublinear regret implies

\[ \frac{\operatorname{Regret}(T)}{T}\to 0. \]

Thus the average loss per step vanishes.

29.10 26.9 PAC-MDP learning

PAC stands for probably approximately correct. In RL, a PAC-style statement usually has the following structure.

With probability at least \(1-\delta\), the learner takes more than \(N(\varepsilon,\delta)\) non-\(\varepsilon\)-optimal actions only finitely many times, where \(N(\varepsilon,\delta)\) is polynomial in relevant problem parameters.

A simplified goal is to learn a policy \(\widehat \pi\) such that

\[ \|V^* - V^{\widehat \pi}\|_\infty \leq \varepsilon \]

with probability at least \(1-\delta\).

The number of samples required is the sample complexity.

In tabular discounted MDPs, sample complexity typically worsens as:

• \(S\) increases;
• \(A\) increases;
• \(\varepsilon\) decreases;
• \(\delta\) decreases;
• \(\gamma\) approaches one.

A rough qualitative scaling is

\[ \text{samples} \propto \frac{SA}{(1-\gamma)^c\varepsilon^2} \log\left(\frac{SA}{\delta}\right), \]

where the exponent \(c\) depends on the algorithm and theorem.

29.10.1 Interactive: sample complexity scaling

Even simplified bounds show strong dependence on \(\varepsilon\) and \(1-\gamma\). This helps explain why long-horizon RL is statistically difficult.

29.11 26.10 Optimism under uncertainty for MDPs

The bandit UCB idea extends to MDPs. Instead of choosing the action with the largest estimated reward, an optimistic planner chooses actions that are good in some plausible model.

Suppose the learner constructs a confidence set \(\mathcal{M}_t\) of MDP models consistent with the data:

\[ \mathcal{M}_t = \{M: M \text{ is statistically plausible at time } t\}. \]

An optimistic algorithm computes

\[ (M_t^+,\pi_t) \in \arg\max_{M\in \mathcal{M}_t,\pi} V_M^\pi(s_t). \]

The policy \(\pi_t\) is optimal for the most favorable plausible model. If a poorly understood action might lead to high reward, optimism makes the agent explore it.

A common practical simplification adds an exploration bonus to the reward:

\[ r_t^+(s,a) = \widehat r(s,a)+b_t(s,a), \]

where

\[ b_t(s,a) \approx \sqrt{\frac{\log(SAT/\delta)}{N_t(s,a)}}. \]

Then planning is performed using the optimistic reward \(r_t^+\).

29.11.1 Interactive: optimism under uncertainty

An uncertain action may be chosen even if its empirical mean is lower, because its upper confidence bound is higher.

import numpy as np

S = 3
A = 2
gamma = 0.92

def value_iteration(P, r, gamma, steps=200):
    V = np.zeros(P.shape[0])
    for _ in range(steps):
        Q = r + gamma * np.einsum("sak,k->sa", P, V)
        V = Q.max(axis=1)
    policy = np.argmax(r + gamma * np.einsum("sak,k->sa", P, V), axis=1)
    return V, policy

P_hat = np.array([
    [[0.80, 0.20, 0.00], [0.20, 0.20, 0.60]],
    [[0.10, 0.80, 0.10], [0.00, 0.40, 0.60]],
    [[0.00, 0.00, 1.00], [0.00, 0.00, 1.00]],
])

r_hat = np.array([
    [0.9, 0.0],
    [0.3, 0.0],
    [1.0, 1.0],
])

N = np.array([
    [200, 4],
    [120, 15],
    [400, 400],
])

bonus = 1.2 / np.sqrt(N)
V_plain, pi_plain = value_iteration(P_hat, r_hat, gamma)
V_opt, pi_opt = value_iteration(P_hat, r_hat + bonus, gamma)

print("plain policy:", pi_plain)
print("optimistic policy:", pi_opt)
print("bonus matrix:\n", np.round(bonus, 3))
print("plain V:", np.round(V_plain, 3))
print("optimistic V:", np.round(V_opt, 3))

plain policy: [0 1 0]
optimistic policy: [1 1 0]
bonus matrix:
 [[0.085 0.6  ]
 [0.11  0.31 ]
 [0.06  0.06 ]]
plain V: [11.018 10.918 12.5  ]
optimistic V: [12.419 12.063 13.25 ]

29.12 26.11 Model-based finite-sample intuition

Consider a model-based pipeline.

1. Collect data using an exploration policy.
2. Estimate \(\widehat P\) and \(\widehat r\).
3. Compute an approximately optimal policy \(\widehat \pi\) for the estimated MDP.
4. Deploy \(\widehat \pi\) in the true MDP.

The error can be decomposed as

\[ V^* - V^{\widehat \pi} = \underbrace{V^* - \widehat V^*}_{\text{model estimation}} + \underbrace{\widehat V^* - \widehat V^{\widehat \pi}}_{\text{planning error}} + \underbrace{\widehat V^{\widehat \pi} - V^{\widehat \pi}}_{\text{model estimation}}. \]

This equation is informal because the values live in different models, but it identifies the main sources of error:

• transition and reward estimation error;
• numerical planning error;
• policy-induced distribution shift between the data and the learned policy.

29.12.1 Interactive: model estimation and value error

The plot shows a simplified relationship between transition-estimation error and value-function error for different discount factors.

import numpy as np

rng = np.random.default_rng(5110)
S = 3
A = 2
gamma = 0.9

P_true = np.array([
    [[0.7, 0.3, 0.0], [0.2, 0.5, 0.3]],
    [[0.1, 0.7, 0.2], [0.0, 0.4, 0.6]],
    [[0.0, 0.1, 0.9], [0.0, 0.0, 1.0]],
])
r_true = np.array([
    [0.2, 0.3],
    [0.1, 0.6],
    [1.0, 1.0],
])

def optimal_value(P, r, gamma, steps=500):
    V = np.zeros(P.shape[0])
    for _ in range(steps):
        Q = r + gamma * np.einsum("sak,k->sa", P, V)
        V = Q.max(axis=1)
    return V

V_true = optimal_value(P_true, r_true, gamma)

for n in [10, 30, 100, 300, 1000]:
    P_hat = np.zeros_like(P_true)
    for s in range(S):
        for a in range(A):
            next_states = rng.choice(S, size=n, p=P_true[s, a])
            counts = np.bincount(next_states, minlength=S)
            P_hat[s, a] = counts / n
    V_hat = optimal_value(P_hat, r_true, gamma)
    err = np.max(np.abs(V_hat - V_true))
    transition_l1 = np.max(np.abs(P_hat - P_true).sum(axis=2))
    print(f"n per state-action={n:4d}, max transition L1={transition_l1:.3f}, value error={err:.3f}")

n per state-action=  10, max transition L1=0.200, value error=0.000
n per state-action=  30, max transition L1=0.333, value error=0.119
n per state-action= 100, max transition L1=0.120, value error=0.048
n per state-action= 300, max transition L1=0.100, value error=0.044
n per state-action=1000, max transition L1=0.066, value error=0.015

29.13 26.12 Distribution shift and coverage

In supervised learning, training and test data are often assumed to be drawn from the same distribution. In reinforcement learning, this assumption is fragile.

Let \(d^\pi(s,a)\) denote a state-action occupancy measure under policy \(\pi\). If data were collected by a behavior policy \(\pi_b\) but we evaluate or optimize a target policy \(\pi\), then a key quantity is the mismatch between

\[ d^{\pi_b}(s,a) \quad \text{and} \quad d^\pi(s,a). \]

If \(d^\pi(s,a)>0\) but \(d^{\pi_b}(s,a)=0\), then the dataset contains no direct information about a state-action pair that the target policy may use. This is a coverage failure.

A common concentrability-style coefficient is

\[ C = \sup_{s,a}\frac{d^\pi(s,a)}{d^{\pi_b}(s,a)}. \]

Large \(C\) indicates severe distribution shift.

This idea is especially important in offline reinforcement learning, which is studied in the next chapter.

29.14 26.13 Generalization with function approximation

Tabular theory often gives bounds depending on \(S\) and \(A\). With function approximation, the learner uses a class of value functions or policies:

\[ \mathcal{F}=\{f_\theta:\theta\in\Theta\}. \]

The statistical question becomes: how large is the function class?

In supervised learning, complexity can be measured by VC dimension, covering numbers, Rademacher complexity, or norm-based neural-network measures. In RL, these ideas still matter, but the data distribution is policy-dependent and Bellman targets are bootstrapped.

For a value-function class \(\mathcal{F}\), a schematic generalization statement may have the form

\[ \sup_{f\in\mathcal{F}} \left| E[\ell(f;Z)]-\frac{1}{n}\sum_{i=1}^n \ell(f;Z_i) \right| \leq \text{complexity}(\mathcal{F},n,\delta). \]

For a linear class

\[ f_\theta(s)=\phi(s)^T\theta, \]

the effective complexity often depends on feature dimension, norm constraints, covariance conditioning, and state-distribution coverage.

29.14.1 Interactive: approximation complexity and finite-sample error

Increasing model complexity can reduce approximation bias but increase estimation variance. This is familiar from supervised learning, but RL adds bootstrapping and distribution shift.

import numpy as np

rng = np.random.default_rng(6241)
n_train = 60
n_test = 1000
x_train = rng.uniform(-1, 1, size=n_train)
x_test = rng.uniform(-1, 1, size=n_test)

def true_value(x):
    return np.sin(3 * x) + 0.5 * x

y_train = true_value(x_train) + rng.normal(0, 0.20, size=n_train)
y_test = true_value(x_test)

def poly_features(x, degree):
    return np.column_stack([x ** j for j in range(degree + 1)])

for degree in [1, 2, 3, 5, 9, 14]:
    Phi = poly_features(x_train, degree)
    theta = np.linalg.pinv(Phi) @ y_train
    train_mse = np.mean((Phi @ theta - y_train) ** 2)
    test_mse = np.mean((poly_features(x_test, degree) @ theta - y_test) ** 2)
    print(f"degree={degree:2d}, train MSE={train_mse:.4f}, test MSE={test_mse:.4f}")

degree= 1, train MSE=0.1427, test MSE=0.1761
degree= 2, train MSE=0.1250, test MSE=0.2225
degree= 3, train MSE=0.0335, test MSE=0.0036
degree= 5, train MSE=0.0326, test MSE=0.0044
degree= 9, train MSE=0.0317, test MSE=0.0047
degree=14, train MSE=0.0299, test MSE=22.9395

This example is supervised rather than sequential, but it illustrates the approximation-estimation tradeoff that also appears in approximate RL.

29.15 26.14 Statistical learning theory does not remove modeling judgment

Theorems require assumptions. Common assumptions include:

• bounded rewards;
• finite state and action spaces;
• sufficient exploration;
• correct Markov state representation;
• realizability or approximate realizability;
• mixing or episodic reset conditions;
• accurate optimization of empirical objectives.

When applying RL theory, students should always ask:

1. What is random?
2. What is being estimated?
3. What probability statement is being claimed?
4. What event has probability at least \(1-\delta\)?
5. What norm or performance metric is being bounded?
6. Does the theorem control the policy actually used by the algorithm?
7. Does the data collection policy cover the target policy?

29.15.1 AI-assisted theorem audit

Ask an AI assistant to analyze a proposed RL theorem using the following checklist.

1. Identify the sample space and source of randomness.
2. State whether the data are iid, Markovian, episodic, or adaptively collected.
3. Identify the confidence parameter \(\delta\) and accuracy parameter \(\varepsilon\).
4. Identify whether the theorem bounds value error, policy suboptimality, Bellman error, or regret.
5. List all assumptions that are required but not explicitly stated.
6. Explain whether the theorem is tabular, linear, or nonlinear.
7. Give one example where the theorem would not apply.

Then verify the AI response manually. In RL theory, missing assumptions are often more important than the displayed inequality.

29.16 26.15 Python example: empirical regret curves

The following simulation compares UCB with constant-\(\epsilon\) greedy over repeated bandit experiments.

import numpy as np

rng = np.random.default_rng(2027)
means = np.array([0.10, 0.20, 0.90, 0.40])
K = len(means)
T = 1000
runs = 200
opt = means.max()

def one_run(method):
    counts = np.zeros(K)
    sums = np.zeros(K)
    regret = np.zeros(T)
    total_reward = 0.0
    for t in range(1, T + 1):
        if t <= K:
            a = t - 1
        else:
            avg = sums / np.maximum(counts, 1)
            if method == "ucb":
                bonus = np.sqrt(2 * np.log(t) / np.maximum(counts, 1))
                a = int(np.argmax(avg + bonus))
            elif method == "eps":
                if rng.random() < 0.1:
                    a = rng.integers(K)
                else:
                    a = int(np.argmax(avg))
            else:
                raise ValueError("unknown method")
        reward = rng.binomial(1, means[a])
        counts[a] += 1
        sums[a] += reward
        total_reward += reward
        regret[t - 1] = t * opt - total_reward
    return regret

ucb = np.vstack([one_run("ucb") for _ in range(runs)]).mean(axis=0)
eps = np.vstack([one_run("eps") for _ in range(runs)]).mean(axis=0)

print("Average regret at T=1000")
print("UCB:", round(float(ucb[-1]), 2))
print("epsilon-greedy:", round(float(eps[-1]), 2))
print("First 10 UCB regret values:", np.round(ucb[:10], 2))

Average regret at T=1000
UCB: 46.47
epsilon-greedy: 56.12
First 10 UCB regret values: [0.82 1.52 1.52 2.05 2.33 2.55 2.68 3.11 3.65 4.08]

29.17 26.16 Summary

This chapter introduced the statistical learning theory viewpoint on reinforcement learning.

The main ideas are:

• RL data are dependent and policy-dependent.
• Confidence intervals quantify uncertainty in rewards and transitions.
• Bellman equations amplify estimation error through the effective horizon.
• Regret measures the cost of learning while acting.
• PAC-MDP theory studies the number of samples needed for near-optimal control.
• Optimism under uncertainty turns confidence sets into exploration strategies.
• Function approximation introduces generalization error and distribution shift.
• The meaning of a theorem depends heavily on its assumptions.

A useful mental model is:

\[ \text{RL theory} = \text{concentration} + \text{dynamic programming} + \text{exploration} + \text{generalization}. \]

29.18 Exercises

29.18.1 Conceptual exercises

1. Explain why data collected by a reinforcement learning agent are usually not iid.
2. Give an example where a policy with high empirical reward may still be statistically uncertain.
3. Explain the difference between value-estimation error and policy suboptimality.
4. Why does the effective horizon \(1/(1-\gamma)\) appear in sample-complexity bounds?
5. Explain optimism under uncertainty in your own words.
6. Why is off-policy evaluation statistically difficult when coverage is poor?

29.18.2 Mathematical exercises

1. Use Hoeffding’s inequality to find \(n\) such that \(|\widehat \mu_n-\mu|\leq 0.05\) with probability at least \(0.99\).
2. Prove that if \(\|r-\widetilde r\|_\infty\leq \varepsilon_r\) and \(P\) is fixed, then \(\|V-\widetilde V\|_\infty\leq \varepsilon_r/(1-\gamma)\).
3. Derive the bandit regret identity \(\operatorname{Regret}(T)=\sum_a \Delta_a E[N_T(a)]\).
4. For a two-action bandit, compute the UCB index after the following observations: action 1 has \(10\) successes in \(20\) trials; action 2 has \(3\) successes in \(5\) trials; \(t=25\).
5. Let \(d^\pi\) and \(d^{\pi_b}\) be state-action distributions. Explain why a large ratio \(d^\pi(s,a)/d^{\pi_b}(s,a)\) increases variance in off-policy evaluation.

29.18.3 Computational exercises

1. Modify the UCB simulation to include Thompson sampling for Bernoulli rewards.
2. Compare regret curves for \(K=2\), \(K=5\), and \(K=20\) arms.
3. Simulate plug-in model estimation for a finite MDP and plot value error versus samples per state-action pair.
4. Study how value-estimation error changes as \(\gamma\) varies from \(0.5\) to \(0.99\).
5. Implement an optimistic value-iteration algorithm using reward bonuses.
6. Construct a behavior policy with poor coverage and show that off-policy value estimates become unstable.

29.18.4 AI-assisted exercises

1. Ask an AI assistant to explain the difference between PAC bounds and regret bounds. Then identify one important missing assumption in the response.
2. Give an AI assistant a short proof using Hoeffding’s inequality and ask it to check the union-bound step.
3. Ask an AI assistant to generate a counterexample where high empirical reward does not imply low uncertainty.
4. Ask an AI assistant to inspect UCB code and identify possible division-by-zero or initialization errors.
5. Ask an AI assistant to compare tabular sample-complexity bounds with function-approximation generalization bounds, then rewrite the explanation for a statistics audience.

29.19 Instructor notes

This chapter is intended to connect RL algorithms with finite-sample reasoning. For applied mathematics students, emphasize concentration inequalities, fixed-point perturbation, and regret. For statistics students, emphasize confidence sets, coverage, distribution shift, and the difference between prediction and control.

A useful classroom sequence is:

1. start with Hoeffding’s inequality;
2. apply it to bandit confidence intervals;
3. derive UCB as optimism;
4. show regret simulations;
5. explain why MDPs add transition estimation and horizon amplification;
6. close with function approximation and distribution shift.