Module 4 — Dynamic programming and Monte Carlo methods

The Bellman equations of module 3 are a specification. This module turns them into algorithms in two very different regimes: when the model P is known (dynamic programming) and when it is not (Monte Carlo). The pair frames every learning method that follows.

Value iteration: sweeping the optimality equation

Value iteration takes the Bellman optimality equation and treats it as an update rule until convergence:

$$V_{k+1}(s) \leftarrow \max_a \sum_{s'} P(s'|s,a) \, [\, R(s,a,s') + \gamma V_k(s') \,]$$

Repeat until max_s |V_{k+1}(s) - V_k(s)| < tol. The theorem says this fixed-point iteration converges to V* for any initialization, at a rate governed by γ. On FrozenLake it takes about 250 sweeps.

def value_iteration(P, n_states, n_actions, gamma=0.99, tol=1e-8):
    V = np.zeros(n_states)
    while True:
        V_new = V.copy()
        for s in range(n_states):
            action_values = []
            for a in range(n_actions):
                q = sum(prob * (r + gamma * V[s_next] * (not done))
                        for prob, s_next, r, done in P[s][a])
                action_values.append(q)
            V_new[s] = max(action_values)
        if np.max(np.abs(V_new - V)) < tol:
            break
        V = V_new
    # Recover the optimal policy from V*.
    pi = np.zeros(n_states, dtype=int)
    for s in range(n_states):
        pi[s] = np.argmax([
            sum(prob * (r + gamma * V[s_next] * (not done))
                for prob, s_next, r, done in P[s][a])
            for a in range(n_actions)
        ])
    return V, pi

On slippery FrozenLake this returns a policy that reaches the goal about 74 % of the time from the start — the best any policy can do against 33 % slip on every action.

Policy iteration: alternate evaluation and improvement

Policy iteration keeps the two steps of the Bellman logic separate. Evaluation solves V^π for the current policy (the linear system of module 3). Improvement replaces π(s) by argmax_a Q^π(s, a), which is guaranteed to produce a policy at least as good. Alternate until the policy stops changing.

Policy iteration typically converges in fewer sweeps than value iteration — often three or four on FrozenLake — but each sweep is more expensive. The two are worth naming because deep RL keeps their vocabulary: actor-critic in module 9 is policy iteration in disguise.

Monte Carlo: when the model is missing

Everything above assumes you can enumerate P[s][a]. In every problem worth solving that assumption fails: a robot has no transition table, a market has no dynamics equation. Monte Carlo replaces the expectations of the Bellman equations by averages over sampled episodes.

The first-visit Monte Carlo estimator for V^π is:

for each episode generated by pi:
    G ← 0
    for t = T-1 down to 0:
        G ← r_{t+1} + gamma * G
        if s_t is the first visit to that state in this episode:
            append G to Returns(s_t)
V(s) ← average of Returns(s)

The theorem: as the number of episodes grows, V(s) converges to V^π(s) for every state visited infinitely often. Two things to notice. First, Monte Carlo needs the episode to end — no updates until the terminal state, which rules it out for continuing tasks. Second, it uses actual returns, so its updates are unbiased but potentially of high variance.

from collections import defaultdict

def monte_carlo_v(env, policy, n_episodes=50_000, gamma=0.99):
    returns_sum = defaultdict(float)
    returns_count = defaultdict(int)
    for _ in range(n_episodes):
        state, _ = env.reset()
        trajectory = []
        done = False
        while not done:
            action = policy(state)
            next_state, reward, term, trunc, _ = env.step(action)
            done = term or trunc
            trajectory.append((state, reward))
            state = next_state
        G = 0.0
        visited = set()
        for state, reward in reversed(trajectory):
            G = reward + gamma * G
            if state not in visited:
                visited.add(state)
                returns_sum[state] += G
                returns_count[state] += 1
    return {s: returns_sum[s] / returns_count[s] for s in returns_sum}

The variance problem

Run the code above with 1 000 episodes, then 10 000, then 100 000, and plot V(0) at each scale. Two observations recur.

The estimator converges slowly: to get V(0) accurate to 0.01 on FrozenLake, you need tens of thousands of episodes. The reason is that the return G is a sum of many random rewards, and its variance grows with the horizon.

The estimator wastes information: an episode that touches ten states updates only ten cells, whereas a single Bellman sweep updates all sixteen using the current estimate for the neighbors. Trading a little bit of that unbiasedness for a bootstrapped estimate — using V(s_{t+1}) in place of the tail of G — is exactly what temporal difference will do in module 5.

Model-based vs model-free, and why it matters

Value and policy iteration are model-based — they need P and R — and they exploit that model to converge in a handful of sweeps. Monte Carlo is model-free and needs orders of magnitude more data. The trade is not academic: in robotics, learning a model of the environment sometimes pays back in fewer real-world interactions, which is the entire premise of model-based deep RL. In this course we stay model-free from module 5 onwards, because that is where the interesting failure modes live.

Summary

• Value iteration iterates the Bellman optimality update until V stops moving, then reads off π* from a one-step lookahead.
• Policy iteration alternates policy evaluation (a linear system) and policy improvement; it converges in fewer sweeps but sweeps are heavier.
• Monte Carlo replaces expectations by averages over full episodes; unbiased, high variance, needs episodes to terminate.
• Bootstrapping — using the current V estimate as part of the target — is the trade-off that turns MC into TD in the next module.

Next module: temporal difference learning, and its two most famous incarnations, SARSA and Q-learning.