6.Learning from Experience: Monte Carlo & Temporal-Difference

6.1 No model, no problem — the Monte Carlo idea

Chapter 5 needed $p(s',r\mid s,a)$ to compute expectations. Without it, one option remains: sample.

The value $v_\pi(s)$ is by definition an average of returns. So run episodes, record the returns that actually followed each state, and average them. That is Monte Carlo prediction, and its correctness follows from the law of large numbers rather than from any property of the MDP.

First-visit MC averages the returns following the first visit to $s$ in each episode. Its estimator is unbiased: each first-visit return is an independent sample from the distribution whose mean is $v_\pi(s)$, so the average converges to $v_\pi(s)$ as the number of visits grows, with standard error falling as $1/\sqrt{n}$.

6.2 Off-policy evaluation and importance sampling

A robot often needs to evaluate one policy while behaving according to another — estimate the value of an aggressive policy while running a safe one, or reuse data collected last week. This is off-policy learning, and it is the setting that dominates robotics because data is expensive enough that you want to reuse all of it.

Let $b$ be the behaviour policy generating the data and $\pi$ the target policy we want to evaluate. The returns we observe come from the wrong distribution. Importance sampling reweights them by the ratio of trajectory probabilities:

$\rho_{t:T-1} \doteq \prod_{k=t}^{T-1} \frac{\pi(A_k \mid S_k)}{b(A_k \mid S_k)}.$

Notice that the environment dynamics cancel: $p(s'\mid s,a)$ appears identically in numerator and denominator. Only the policy probabilities survive, which is what makes this usable without a model. Then

$v_\pi(s) = \mathbb{E}_b\left[\rho_{t:T-1} G_t \mid S_t = s\right],$

so ordinary importance sampling — averaging $\rho G$ — is unbiased.

6.3 Temporal difference: learning a guess from a guess

Monte Carlo waits for the episode to end. TD does not, and the trick is disarmingly simple.

The return recursion from Chapter 4 says $G_t = R_{t+1} + \gamma G_{t+1}$. Monte Carlo uses the observed $G_t$ as its target. TD substitutes the current estimate for the tail:

$V(S_t) \leftarrow V(S_t) + \alpha \underbrace{\Big[\,\underbrace{R_{t+1} + \gamma V(S_{t+1})}_{\text{TD target}} - V(S_t)\Big]}_{\text{TD error } \delta_t}.$

That is TD(0). It updates immediately after one transition, needs no episode boundary, and works on continuing tasks.

The quantity $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ is the TD error, and it deserves a name because it recurs everywhere in this book. It measures the surprise: how much better or worse the transition turned out than the current estimate predicted. When $\delta = 0$ everywhere, the value function is self-consistent and satisfies the Bellman equation.

6.4 Control: SARSA, Expected SARSA, Q-learning

To control rather than merely predict, learn action values and follow the GPI pattern from Chapter 5: estimate $Q$, act greedily-ish with respect to it, repeat.

Three algorithms differ only in what they put in the target.

SARSA uses the action actually taken next:

$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\left[R_{t+1} + \gamma\, Q(S_{t+1}, A_{t+1}) - Q(S_t,A_t)\right].$

It is on-policy: the target evaluates the same $\varepsilon$-greedy policy the agent is executing, exploration included.

Q-learning uses the best action available, whether or not it is taken:

$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\left[R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t,A_t)\right].$

It is off-policy: the target evaluates the greedy policy while the agent behaves $\varepsilon$-greedily.

Expected SARSA replaces the sample with its expectation under the policy:

$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\left[R_{t+1} + \gamma \sum_a \pi(a\mid S_{t+1}) Q(S_{t+1},a) - Q(S_t,A_t)\right],$

eliminating the variance due to sampling $A_{t+1}$ at the cost of a sum over actions. It usually dominates SARSA, and reduces to Q-learning when $\pi$ is greedy.

Press play and watch the mechanism directly. Value appears at the dock and bleeds backwards, one cell per episode-ish, because that is how far a one-step TD error can carry information. Early arrows are nonsense — every $Q$ is zero and ties break randomly. The policy sharpens only where the TD error has actually reached.

Then set $\varepsilon = 0$ and watch the run stall. With no exploration, Rusty commits to the first corridor that ever paid off and never discovers the better one. This is the Chapter 3 dilemma, now with states.

6.5 Does it converge?

Yes, under conditions worth knowing precisely.

The proof combines the two things Chapter 2 built. The Bellman optimality operator is a $\gamma$-contraction, so the expected update moves $Q$ toward $q_*$; stochastic approximation theory then shows the noisy sampled updates track the expected ones almost surely, given Robbins–Monro step sizes. The full argument is in Watkins and Dayan and in Bertsekas & Tsitsiklis.

Condition 1 is the one that bites. "Visited infinitely often" requires persistent exploration, which is why $\varepsilon$ must decay slowly — the GLIE conditions (Greedy in the Limit with Infinite Exploration): explore forever, but let exploration vanish so the policy becomes greedy in the limit. A schedule like $\varepsilon_t = 1/t$ satisfies both.

6.6 Maximization bias and the double estimator

One more phenomenon, because it explains a family of algorithms in Chapter 9.

Q-learning's target contains $\max_a Q(S_{t+1},a)$. Suppose all the $Q$ estimates are unbiased but noisy. Is the max unbiased?

No. By Jensen's inequality applied to the convex max function,

$\mathbb{E}\left[\max_a Q(s,a)\right] \ge \max_a \mathbb{E}\left[Q(s,a)\right] = \max_a q(s,a).$

Taking the maximum of noisy estimates systematically overestimates the true maximum. The max operator preferentially selects whichever action got lucky, and luck does not persist — but the inflated estimate does, and it propagates through every subsequent backup.

This is maximization bias, and it is not a small effect. With many actions and noisy returns, the overestimation compounds through bootstrapping until the value function is meaningfully optimistic everywhere.

Double Q-learning implements this by keeping two tables and flipping a coin each step to decide which is updated and which evaluates. It costs twice the memory and nothing in computation, and the fix carries directly into deep RL: Double DQN in Chapter 9 is this exact idea with the target network playing the role of the second estimator, and TD3's clipped double-Q in Chapter 11 is the continuous-control version.

use rl_core::{Env, Transition};
 
pub struct QLearning {
    q: Vec<f64>,          // flat: state * n_actions + action
    n_actions: usize,
    alpha: f64,
    gamma: f64,
}
 
impl QLearning {
    #[inline]
    fn idx(&self, s: usize, a: usize) -> usize { s * self.n_actions + a }
 
    fn max_q(&self, s: usize) -> f64 {
        (0..self.n_actions)
            .map(|a| self.q[self.idx(s, a)])
            .fold(f64::NEG_INFINITY, f64::max)
    }
 
    /// One off-policy update. Returns the TD error δ — the learning signal.
    pub fn update(&mut self, s: usize, a: usize, t: &Transition<usize>) -> f64 {
        // The target bootstraps from the GREEDY action, whatever we actually do next.
        let target = if t.done {
            t.reward
        } else {
            t.reward + self.gamma * self.max_q(t.next_state)
        };
 
        let i = self.idx(s, a);
        let delta = target - self.q[i];
        self.q[i] += self.alpha * delta;
        delta
    }
}

6.7 Chapter bridge

Rusty can now learn without a map. He samples, bootstraps, and improves — the GPI pattern of Chapter 5 with expectations replaced by samples.

But we have accepted a stark choice. Monte Carlo waits for the whole return: unbiased, high variance, no bootstrapping. TD(0) uses one step: low variance, biased, fast. Nothing in the mathematics says those are the only options, and they are not.

Chapter 7 puts a dial between them. The $\lambda$-return blends every $n$-step return at once; eligibility traces make the blend cheap enough to compute online. And then a second idea: if we can learn a model from experience, we can plan with it as in Chapter 5 while continuing to learn as in this chapter — Dyna, the architecture that unifies both halves of Part I.

References