Chapter 3: Value-Based Methods

3.1 Introduction to Value-Based Methods

Value-based methods learn the value of being in each state (or taking each action in each state) and derive a policy from these values. The key idea is: if we know Q*(s,a), we can act optimally by simply choosing argmax_a Q*(s,a).

3.2 Monte Carlo Methods

Monte Carlo (MC) methods learn from complete episodes of experience. They estimate value functions by averaging sample returns.

First-Visit MC Prediction

def first_visit_mc_prediction(policy, env, episodes=1000, gamma=0.99):
    """
    Estimate V^π using first-visit Monte Carlo.
    """
    V = defaultdict(float)
    returns = defaultdict(list)

    for episode in range(episodes):
        # Generate episode following policy
        states, actions, rewards = generate_episode(policy, env)

        G = 0
        visited = set()

        # Process episode backwards
        for t in reversed(range(len(states))):
            s = states[t]
            r = rewards[t]

            G = gamma * G + r

            # First-visit check
            if s not in visited:
                visited.add(s)
                returns[s].append(G)
                V[s] = np.mean(returns[s])

    return V

MC Control with Epsilon-Greedy

def mc_control_epsilon_greedy(env, episodes=10000, gamma=0.99, epsilon=0.1):
    """
    Find optimal policy using Monte Carlo control.
    """
    Q = defaultdict(lambda: defaultdict(float))
    returns = defaultdict(lambda: defaultdict(list))

    for episode in range(episodes):
        # Generate episode with epsilon-greedy policy
        states, actions, rewards = [], [], []
        state = env.reset()

        while True:
            # Epsilon-greedy action selection
            if random.random() < epsilon:
                action = env.action_space.sample()
            else:
                action = max(Q[state], key=Q[state].get)

            next_state, reward, done, _ = env.step(action)

            states.append(state)
            actions.append(action)
            rewards.append(reward)

            if done:
                break

            state = next_state

        # Update Q-values
        G = 0
        visited = set()

        for t in reversed(range(len(states))):
            s, a, r = states[t], actions[t], rewards[t]
            G = gamma * G + r

            if (s, a) not in visited:
                visited.add((s, a))
                returns[s][a].append(G)
                Q[s][a] = np.mean(returns[s][a])

    return Q

3.3 Temporal Difference Learning

Temporal Difference (TD) learning combines ideas from Monte Carlo and dynamic programming. TD methods can learn from incomplete episodes by bootstrapping.

TD(0) Prediction

V(sₜ) ← V(sₜ) + α[rₜ₊₁ + γV(sₜ₊₁) - V(sₜ)]
              ↑           ↑      ↑              ↑
           old value  learning  TD target    old value
                        rate

TD target = rₜ₊₁ + γV(sₜ₊₁)
TD error  = rₜ₊₁ + γV(sₜ₊₁) - V(sₜ)

TD vs MC

3.4 Q-Learning

Q-Learning is the most important TD control algorithm. It's off-policy: learns about the optimal policy while following an exploratory policy.

Q-Learning Algorithm

Q(sₜ,aₜ) ← Q(sₜ,aₜ) + α[rₜ₊₁ + γ max_a Q(sₜ₊₁,a) - Q(sₜ,aₜ)]

Key points:
1. Off-policy: learns Q* regardless of behavior policy
2. Bootstraps: uses estimate Q(s',a') to update Q(s,a)
3. Converges to optimal Q* under certain conditions

Complete Q-Learning Implementation

import numpy as np
import gym

def q_learning(env, episodes=5000, alpha=0.1, gamma=0.99, epsilon=0.1):
    """
    Q-Learning algorithm for discrete state/action spaces.

    Args:
        env: OpenAI Gym environment
        episodes: number of training episodes
        alpha: learning rate
        gamma: discount factor
        epsilon: exploration rate
    """
    # Initialize Q-table
    Q = np.zeros([env.observation_space.n, env.action_space.n])

    # Training statistics
    episode_rewards = []

    for episode in range(episodes):
        state = env.reset()
        total_reward = 0
        done = False

        while not done:
            # Epsilon-greedy action selection
            if np.random.random() < epsilon:
                action = env.action_space.sample()  # Explore
            else:
                action = np.argmax(Q[state])        # Exploit

            # Take action
            next_state, reward, done, _ = env.step(action)
            total_reward += reward

            # Q-Learning update
            best_next_action = np.argmax(Q[next_state])
            td_target = reward + gamma * Q[next_state, best_next_action]
            td_error = td_target - Q[state, action]
            Q[state, action] += alpha * td_error

            state = next_state

        episode_rewards.append(total_reward)

        # Decay epsilon
        epsilon = max(0.01, epsilon * 0.995)

        if (episode + 1) % 500 == 0:
            avg_reward = np.mean(episode_rewards[-100:])
            print(f"Episode {episode+1}, Avg Reward: {avg_reward:.2f}")

    return Q, episode_rewards

Convergence Conditions

Q-Learning converges to Q* if:

• All state-action pairs are visited infinitely often
• Learning rate α decays appropriately: Σα = ∞, Σα² < ∞
• The environment is a finite MDP

3.5 SARSA (On-Policy TD Control)

SARSA is the on-policy version of Q-Learning. It learns the value of the policy being followed, including exploration.

Q(sₜ,aₜ) ← Q(sₜ,aₜ) + α[rₜ₊₁ + γQ(sₜ₊₁,aₜ₊₁) - Q(sₜ,aₜ)]

The name SARSA comes from the tuple (sₜ, aₜ, rₜ₊₁, sₜ₊₁, aₜ₊₁)

SARSA Implementation

def sarsa(env, episodes=5000, alpha=0.1, gamma=0.99, epsilon=0.1):
    """
    SARSA algorithm (on-policy TD control).
    """
    Q = np.zeros([env.observation_space.n, env.action_space.n])

    for episode in range(episodes):
        state = env.reset()

        # Choose initial action using epsilon-greedy
        if np.random.random() < epsilon:
            action = env.action_space.sample()
        else:
            action = np.argmax(Q[state])

        done = False

        while not done:
            # Take action
            next_state, reward, done, _ = env.step(action)

            # Choose next action using epsilon-greedy
            if np.random.random() < epsilon:
                next_action = env.action_space.sample()
            else:
                next_action = np.argmax(Q[next_state])

            # SARSA update: uses actual next action
            td_target = reward + gamma * Q[next_state, next_action]
            td_error = td_target - Q[state, action]
            Q[state, action] += alpha * td_error

            state = next_state
            action = next_action

    return Q

Q-Learning vs SARSA

3.6 Deep Q-Networks (DQN)

DQN extends Q-Learning to high-dimensional state spaces using deep neural networks as function approximators.

Key Innovations

1. Experience Replay: Store transitions in buffer, sample mini-batches randomly
2. Target Network: Separate network for TD targets, updated periodically
3. Neural Network: Approximate Q(s,a) instead of tabular storage

DQN Architecture

import torch
import torch.nn as nn
import torch.optim as optim
from collections import deque
import random

class DQN(nn.Module):
    def __init__(self, state_dim, action_dim, hidden_dim=128):
        super(DQN, self).__init__()
        self.network = nn.Sequential(
            nn.Linear(state_dim, hidden_dim),
            nn.ReLU(),
            nn.Linear(hidden_dim, hidden_dim),
            nn.ReLU(),
            nn.Linear(hidden_dim, action_dim)
        )

    def forward(self, state):
        return self.network(state)

class ReplayBuffer:
    def __init__(self, capacity=10000):
        self.buffer = deque(maxlen=capacity)

    def push(self, state, action, reward, next_state, done):
        self.buffer.append((state, action, reward, next_state, done))

    def sample(self, batch_size):
        return random.sample(self.buffer, batch_size)

    def __len__(self):
        return len(self.buffer)

DQN Training Loop

def train_dqn(env, episodes=1000, batch_size=64, gamma=0.99):
    state_dim = env.observation_space.shape[0]
    action_dim = env.action_space.n

    # Initialize networks
    policy_net = DQN(state_dim, action_dim)
    target_net = DQN(state_dim, action_dim)
    target_net.load_state_dict(policy_net.state_dict())

    optimizer = optim.Adam(policy_net.parameters(), lr=1e-3)
    replay_buffer = ReplayBuffer(capacity=10000)

    epsilon = 1.0
    epsilon_decay = 0.995
    epsilon_min = 0.01

    for episode in range(episodes):
        state = env.reset()
        total_reward = 0

        while True:
            # Epsilon-greedy action selection
            if random.random() < epsilon:
                action = env.action_space.sample()
            else:
                with torch.no_grad():
                    state_tensor = torch.FloatTensor(state).unsqueeze(0)
                    q_values = policy_net(state_tensor)
                    action = q_values.argmax().item()

            next_state, reward, done, _ = env.step(action)
            total_reward += reward

            # Store transition
            replay_buffer.push(state, action, reward, next_state, done)

            # Training step
            if len(replay_buffer) > batch_size:
                # Sample mini-batch
                batch = replay_buffer.sample(batch_size)
                states, actions, rewards, next_states, dones = zip(*batch)

                states = torch.FloatTensor(states)
                actions = torch.LongTensor(actions)
                rewards = torch.FloatTensor(rewards)
                next_states = torch.FloatTensor(next_states)
                dones = torch.FloatTensor(dones)

                # Compute Q(s,a)
                q_values = policy_net(states).gather(1, actions.unsqueeze(1))

                # Compute target: r + γ max Q(s',a')
                with torch.no_grad():
                    next_q_values = target_net(next_states).max(1)[0]
                    targets = rewards + gamma * next_q_values * (1 - dones)

                # Compute loss and update
                loss = nn.MSELoss()(q_values.squeeze(), targets)
                optimizer.zero_grad()
                loss.backward()
                optimizer.step()

            if done:
                break

            state = next_state

        # Update target network
        if episode % 10 == 0:
            target_net.load_state_dict(policy_net.state_dict())

        # Decay epsilon
        epsilon = max(epsilon_min, epsilon * epsilon_decay)

        print(f"Episode {episode}, Reward: {total_reward}, Epsilon: {epsilon:.3f}")

    return policy_net

3.7 DQN Improvements

Double DQN

Addresses overestimation bias in Q-Learning by decoupling action selection and evaluation:

# Standard DQN
target = r + γ max_a Q_target(s', a)

# Double DQN
a* = argmax_a Q_policy(s', a)        # Select using policy network
target = r + γ Q_target(s', a*)       # Evaluate using target network

Dueling DQN

Separates value and advantage streams:

class DuelingDQN(nn.Module):
    def __init__(self, state_dim, action_dim, hidden_dim=128):
        super(DuelingDQN, self).__init__()

        self.feature = nn.Sequential(
            nn.Linear(state_dim, hidden_dim),
            nn.ReLU()
        )

        # Value stream
        self.value_stream = nn.Sequential(
            nn.Linear(hidden_dim, hidden_dim),
            nn.ReLU(),
            nn.Linear(hidden_dim, 1)
        )

        # Advantage stream
        self.advantage_stream = nn.Sequential(
            nn.Linear(hidden_dim, hidden_dim),
            nn.ReLU(),
            nn.Linear(hidden_dim, action_dim)
        )

    def forward(self, state):
        features = self.feature(state)
        value = self.value_stream(features)
        advantages = self.advantage_stream(features)

        # Q(s,a) = V(s) + A(s,a) - mean(A(s,·))
        q_values = value + (advantages - advantages.mean(dim=1, keepdim=True))
        return q_values

Prioritized Experience Replay

Sample important transitions more frequently:

class PrioritizedReplayBuffer:
    def __init__(self, capacity, alpha=0.6):
        self.capacity = capacity
        self.alpha = alpha  # Priority exponent
        self.buffer = []
        self.priorities = []
        self.position = 0

    def push(self, transition):
        max_priority = max(self.priorities) if self.priorities else 1.0

        if len(self.buffer) < self.capacity:
            self.buffer.append(transition)
            self.priorities.append(max_priority)
        else:
            self.buffer[self.position] = transition
            self.priorities[self.position] = max_priority

        self.position = (self.position + 1) % self.capacity

    def sample(self, batch_size, beta=0.4):
        # Compute sampling probabilities
        priorities = np.array(self.priorities)
        probabilities = priorities ** self.alpha
        probabilities /= probabilities.sum()

        # Sample indices
        indices = np.random.choice(len(self.buffer), batch_size, p=probabilities)

        # Compute importance sampling weights
        weights = (len(self.buffer) * probabilities[indices]) ** (-beta)
        weights /= weights.max()

        samples = [self.buffer[idx] for idx in indices]
        return samples, indices, weights

    def update_priorities(self, indices, td_errors):
        for idx, error in zip(indices, td_errors):
            self.priorities[idx] = abs(error) + 1e-6

3.8 Rainbow DQN

Rainbow combines multiple DQN improvements:

• Double Q-Learning
• Dueling Networks
• Prioritized Experience Replay
• Multi-step Learning (n-step returns)
• Distributional RL (C51)
• Noisy Networks (for exploration)

3.9 Practical Tips

Hyperparameter Tuning

Common Pitfalls

• Overestimation: Use Double DQN
• Instability: Tune learning rate, use gradient clipping
• Poor Exploration: Adjust epsilon decay, try noisy networks
• Correlation: Use larger replay buffer
• Catastrophic Forgetting: Increase buffer size, use experience replay