Lesson 3: Monte Carlo & Temporal Difference Learning

Reinforcement Learning: From Basics to Advanced

Part 1: RL Foundation — Markov Decision Process & Tabular Methods

xdev.asia

Introduction

Monte Carlo and Temporal Difference (TD) are two core model-free methods — no need to know transition probabilities. This is an important transition from DP to actual RL.

---

1. Monte Carlo Prediction

Estimate V(s) by averaging returns from multiple episodes:

from collections import defaultdict

def mc_prediction(policy, env, num_episodes, gamma=1.0):
    returns_sum = defaultdict(float)
    returns_count = defaultdict(int)
    V = defaultdict(float)
    
    for _ in range(num_episodes):
        episode = generate_episode(policy, env)
        G = 0
        visited_states = set()
        
        for t in reversed(range(len(episode))):
            state, action, reward = episode[t]
            G = gamma * G + reward
            
            if state not in visited_states:  # First-visit MC
                visited_states.add(state)
                returns_sum[state] += G
                returns_count[state] += 1
                V[state] = returns_sum[state] / returns_count[state]
    return V

---

2. Monte Carlo Control

MC + ε-greedy policy improvement:

def mc_control(env, num_episodes, gamma=1.0, epsilon=0.1):
    Q = defaultdict(lambda: np.zeros(env.action_space.n))
    returns_sum = defaultdict(float)
    returns_count = defaultdict(int)
    
    for _ in range(num_episodes):
        episode = generate_episode_epsilon_greedy(Q, env, epsilon)
        G = 0
        
        for t in reversed(range(len(episode))):
            state, action, reward = episode[t]
            G = gamma * G + reward
            sa_pair = (state, action)
            returns_sum[sa_pair] += G
            returns_count[sa_pair] += 1
            Q[state][action] = returns_sum[sa_pair] / returns_count[sa_pair]
    return Q

---

3. TD(0) Learning

Update V after each step (no need to wait for the episode to end):

$$V(s) \leftarrow V(s) + \alpha [r + \gamma V(s') - V(s)]$$

def td_prediction(policy, env, num_episodes, alpha=0.1, gamma=0.99):
    V = defaultdict(float)
    
    for _ in range(num_episodes):
        state, _ = env.reset()
        done = False
        while not done:
            action = policy(state)
            next_state, reward, terminated, truncated, _ = env.step(action)
            done = terminated or truncated
            
            # TD update
            td_target = reward + gamma * V[next_state] * (1 - done)
            td_error = td_target - V[state]
            V[state] += alpha * td_error
            
            state = next_state
    return V

---

4. SARSA — On-policy TD Control

def sarsa(env, num_episodes, alpha=0.1, gamma=0.99, epsilon=0.1):
    Q = np.zeros((env.observation_space.n, env.action_space.n))
    
    for _ in range(num_episodes):
        state, _ = env.reset()
        action = epsilon_greedy(Q, state, epsilon)
        done = False
        
        while not done:
            next_state, reward, terminated, truncated, _ = env.step(action)
            done = terminated or truncated
            next_action = epsilon_greedy(Q, next_state, epsilon)
            
            # SARSA update: Q(s,a) += α[r + γQ(s',a') - Q(s,a)]
            Q[state, action] += alpha * (
                reward + gamma * Q[next_state, next_action] * (1-done) - Q[state, action]
            )
            state, action = next_state, next_action
    return Q

---

5. MC vs TD Comparison

Aspect	Monte Carlo	TD(0)
Model-free	✅	✅
Online	❌ (needs full episode)	✅ (every step)
Bias	Unbiased	Biased (bootstrapping)
Variance	High	Low
Works with continuing tasks	❌	✅

---

Summary

Method	Key Ideas	Update
MC	Average complete returns	After episode
TD(0)	Bootstrap from next state	Every step
SARSA	On-policy TD control	Q(s,a) with actual next action