Monte Carlo, TD, and Q-Learning

Dynamic programming requires knowing $P$ and $R$ exactly. In most real problems — games, robotics, dialogue — you cannot write down the transition model. Model-free methods learn directly from interaction: sample $(s_t, a_t, r_t, s_{t+1})$ tuples and update value estimates from those samples alone.

No model means you replace the expectation over $P$ with sampled experience. The price is variance: random samples are noisy. The reward is generality: the same algorithm applies whether you're playing Atari or controlling a power grid. Model-free methods are the workhorses of modern deep RL.

Two families differ in how much experience they use per update: Monte Carlo waits for a full episode; TD methods update after each step.

Monte Carlo (MC) policy evaluation runs the policy until the episode ends, computes the actual return $G_t = \sum_{k=0}^{T-t-1} \gamma^k r_{t+k+1}$, and uses it to update:

$V(s_t) \leftarrow V(s_t) + \alpha\bigl[G_t - V(s_t)\bigr].$

Properties:

• Unbiased: $G_t$ is a true sample of the return under $\pi$ — no approximation.
• High variance: a single trajectory can be wildly atypical.
• Episodic only: requires terminal states; useless for continuing tasks.
• No bootstrapping: each update uses only real rewards, never other value estimates.

MC is the right baseline for finite-horizon problems where variance is manageable. For long episodes, the variance compounds multiplicatively and learning slows to a crawl.

TD(0) bootstraps: it updates after one step, using the estimated value of the next state as a proxy for the rest of the return:

$V(s_t) \leftarrow V(s_t) + \alpha\bigl[\underbrace{r_t + \gamma V(s_{t+1})}_{\text{TD target}} - V(s_t)\bigr].$

The bracketed term $\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$ is the TD error — positive means the next state was better than expected, negative means worse.

Properties vs MC:

Bias is the price; low variance and online learning are the payoff.

A value-function learner must also act. A greedy agent — always pick $\arg\max_a Q(s,a)$ — exploits current knowledge but never discovers better actions. An agent that always explores learns the environment but never cashes in.

$\epsilon$-greedy is the simplest balance:

$\pi(a \mid s) = \begin{cases} \arg\max_{a'} Q(s,a') & \text{with probability } 1-\epsilon \\ \text{uniform random} & \text{with probability } \epsilon \end{cases}$

Typical schedule: start $\epsilon = 1.0$, anneal to $0.01$–$0.1$ over training. Smarter alternatives exist (UCB, Thompson sampling, intrinsic motivation) but $\epsilon$-greedy is the de-facto baseline because it's simple, fast, and hard to beat on standard benchmarks.

To learn $Q^\pi$ model-free, apply TD to action values. SARSA (State-Action-Reward-State-Action) uses the actual next action $a_{t+1}$ sampled from the behavior policy:

$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha\bigl[r_t + \gamma\, Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t)\bigr].$

SARSA is on-policy: the target $Q(s_{t+1}, a_{t+1})$ is evaluated at the action the agent actually took under $\pi$. This means SARSA learns the value of the exploratory policy (including those random $\epsilon$-greedy moves). In cliff-walking environments, SARSA learns a safer path away from the cliff because it accounts for its own exploration mistakes.

Q-learning replaces $Q(s_{t+1}, a_{t+1})$ with the greedy maximum — regardless of what action was actually taken:

$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha\bigl[r_t + \gamma \max_{a'} Q(s_{t+1}, a') - Q(s_t, a_t)\bigr].$

This is off-policy: the target is the value of the greedy policy even though the agent behaves $\epsilon$-greedily. Q-learning directly approximates $Q^\star$ — it converges to the optimal action-value function under mild conditions (all state-action pairs visited infinitely, learning rates satisfying Robbins-Monro).

The key distinction: SARSA is safer in execution but Q-learning converges to the globally optimal policy. Deep RL (DQN and successors) is built on Q-learning.

A complete tabular Q-learning loop:

import numpy as np

def q_learning(env, n_episodes, alpha=0.1, gamma=0.99,
               eps_start=1.0, eps_end=0.01, eps_decay=0.995):
    Q = np.zeros((env.n_states, env.n_actions))
    eps = eps_start
    for ep in range(n_episodes):
        s = env.reset()
        done = False
        while not done:
            # epsilon-greedy action selection
            if np.random.rand() < eps:
                a = np.random.randint(env.n_actions)
            else:
                a = Q[s].argmax()
            s_next, r, done = env.step(a)
            # Q-learning update (off-policy: uses max, not actual a')
            td_target = r + gamma * Q[s_next].max() * (not done)
            Q[s, a] += alpha * (td_target - Q[s, a])
            s = s_next
        eps = max(eps_end, eps * eps_decay)
    return Q

Swap Q[s_next].max() for Q[s_next, a_next] (where a_next is sampled from $\pi$) and you have SARSA.

TD(0) updates from one-step returns; MC uses the full return. TD($\lambda$) interpolates via the $\lambda$-return:

$G_t^\lambda = (1-\lambda)\sum_{n=1}^{\infty} \lambda^{n-1} G_t^{(n)},$

where $G_t^{(n)}$ is the $n$-step return. At $\lambda=0$ you recover TD(0); at $\lambda=1$ you recover MC.

Eligibility traces implement this efficiently without storing all returns: each state gets a running trace $e_t(s)$ that fades geometrically at rate $\gamma\lambda$ and spikes when $s$ is visited. The TD error propagates backward to all recently visited states proportionally to their trace. TD($\lambda$) is strictly more data-efficient than TD(0) for most problems — it's the basis of the forward/backward view in classical RL.

The on-policy / off-policy distinction matters deeply:

Off-policy methods are more powerful (can learn from any behavior policy, replay buffers, multiple agents) but require importance sampling corrections or bootstrapping tricks when the behavior and target policies diverge sharply.

Three gotchas practitioners encounter:

• Tabular convergence requires infinite visits. Every $(s,a)$ pair must be visited infinitely often. In large state spaces, this is impossible without function approximation — and approximation breaks the convergence proof.
• Learning rate scheduling matters. The Robbins-Monro conditions ($\sum_t \alpha_t = \infty$, $\sum_t \alpha_t^2 < \infty$, e.g. $\alpha_t = 1/t$) guarantee convergence in theory. In practice, a fixed $\alpha = 0.001$ often beats the schedule once you use replay buffers and mini-batches.
• Maximisation bias. Q-learning's $\max_{a'} Q(s',a')$ is an overestimate when $Q$ is noisy: $\mathbb{E}[\max_a X_a] \ge \max_a \mathbb{E}[X_a]$. Double Q-learning (DQN's key fix) decouples action selection from value estimation to remove this bias.