Chapter 19: Reinforcement Learning Foundations

Bloom's Taxonomy Progression

Learning Objectives

By the end of this chapter, you will be able to:

• Define the complete RL framework — Agent, Environment, State (S), Action (A), Reward (R), Policy (π), Return (G), and Discount Factor (γ) — and explain how they interconnect
• Derive the Bellman Expectation and Bellman Optimality equations from first principles, and explain why they are the foundation of all RL algorithms
• Implement Q-Learning from scratch in NumPy to solve FrozenLake, understanding every line of the tabular update rule
• Build a Deep Q-Network (DQN) in PyTorch with experience replay and target networks to solve CartPole-v1
• Explain REINFORCE (Monte Carlo Policy Gradient) and Actor-Critic methods, deriving the policy gradient theorem
• Describe how PPO (Proximal Policy Optimization) enables RLHF (Reinforcement Learning from Human Feedback) for training ChatGPT-style models
• Formulate real-world problems as MDPs — including ISRO spacecraft navigation and DeepMind's AlphaGo — and select appropriate RL algorithms
• Analyze the exploration-exploitation trade-off and compare ε-greedy, UCB, and Boltzmann exploration strategies

Opening Hook

The Intuition First

The Cricket Analogy 🏏

Imagine you're Virat Kohli facing Jasprit Bumrah in a T20 match. Here's your RL setup:

• You (Agent): The batsman making decisions
• Environment: The pitch, fielders, bowler, match situation
• State: Current score, balls remaining, field placement, bowler's run-up angle
• Action: Defensive block, cover drive, pull shot, leave the ball
• Reward: +1 for a single, +4 for boundary, +6 for a six, −1 for getting out
• Policy: Your batting strategy — "When the ball is short and outside off, play the cut shot"

Here's the crucial insight: rewards are delayed. You might play five dot balls (reward = 0 each) to set up a boundary on the sixth ball (reward = +4). A greedy batsman who swings at everything might score quickly but get out. A patient batsman builds an innings. RL is about finding the optimal balance between immediate and future rewards.

Three Types of Machine Learning — Final Piece of the Puzzle

Mathematical Foundation & Core Concepts

# ε-greedy action selection
if np.random.random() < epsilon:
    action = env.action_space.sample()   # explore
else:
    action = np.argmax(Q[state])         # exploit

Worked Examples

Worked Example 1: By-Hand Q-Learning (4-State Grid)

Consider a tiny 2×2 grid world. The agent starts at S (top-left), the goal is G (bottom-right). Stepping on a hole H gives reward −1. Reaching G gives reward +1. Each step costs −0.04.

Step-by-step Q-table updates:

Initialize Q(s,a) = 0 for all s, a.

Episode 1, Step 1: State=0, Action=Right(0), reach s'=1, reward=−0.04

Q(0,0) ← 0 + 0.5 × [−0.04 + 0.9 × max(Q(1,0), Q(1,1)) − 0]

Q(0,0) ← 0 + 0.5 × [−0.04 + 0.9 × 0 − 0] = −0.02

Episode 1, Step 2: State=1, Action=Down(1), reach s'=3 (Goal!), reward=+1

Q(1,1) ← 0 + 0.5 × [1 + 0.9 × 0 − 0] = 0.5

Episode 2, Step 1: State=0, Action=Right(0) again, reach s'=1, reward=−0.04

Q(0,0) ← −0.02 + 0.5 × [−0.04 + 0.9 × max(0, 0.5) − (−0.02)]

Q(0,0) ← −0.02 + 0.5 × [−0.04 + 0.45 + 0.02] = −0.02 + 0.215 = 0.195

Notice how the reward from reaching the Goal (s=3) propagates backward through Q(1,1) = 0.5, and then to Q(0,0) = 0.195. This is temporal difference learning in action — rewards flow backward through the Q-table!

Worked Example 2: ISRO Mars Orbiter as an MDP 🇮🇳

Worked Example 3: DeepMind AlphaGo/AlphaZero 🇺🇸/🇬🇧

Python Implementation: From Scratch

Implementation 1: Q-Learning on FrozenLake (NumPy)

Let's implement Q-Learning from scratch — no RL library, just NumPy. We'll solve OpenAI Gym's FrozenLake-v1 environment.

Python — Q-Learning from Scratch
import numpy as np
import gymnasium as gym

# ── Environment Setup ──
env = gym.make('FrozenLake-v1', is_slippery=True, render_mode=None)
n_states = env.observation_space.n    # 16 states (4x4 grid)
n_actions = env.action_space.n        # 4 actions (L, D, R, U)

# ── Hyperparameters ──
alpha = 0.1         # learning rate
gamma = 0.99        # discount factor
epsilon = 1.0       # initial exploration rate
epsilon_min = 0.01  # minimum exploration rate
epsilon_decay = 0.995  # decay per episode
n_episodes = 10000  # training episodes

# ── Initialize Q-Table ──
# Shape: (16 states, 4 actions) — initialized to zeros
Q = np.zeros((n_states, n_actions))

# ── Training Loop ──
rewards_per_episode = []

for episode in range(n_episodes):
    state, _ = env.reset()
    total_reward = 0
    done = False
    
    while not done:
        # ε-greedy action selection
        if np.random.random() < epsilon:
            action = env.action_space.sample()  # explore
        else:
            action = np.argmax(Q[state])        # exploit
        
        # Take action, observe result
        next_state, reward, terminated, truncated, info = env.step(action)
        done = terminated or truncated
        
        # ── Q-Learning Update (the core equation!) ──
        # Q(s,a) ← Q(s,a) + α[r + γ·max_a' Q(s',a') - Q(s,a)]
        td_target = reward + gamma * np.max(Q[next_state]) * (not terminated)
        td_error = td_target - Q[state, action]
        Q[state, action] += alpha * td_error
        
        state = next_state
        total_reward += reward
    
    # Decay exploration rate
    epsilon = max(epsilon_min, epsilon * epsilon_decay)
    rewards_per_episode.append(total_reward)

# ── Evaluate the Learned Policy ──
print("Learned Q-Table:")
print(np.round(Q, 3))
print(f"\nAvg reward (last 1000 episodes): {np.mean(rewards_per_episode[-1000:]):.3f}")

# Extract the optimal policy
policy = np.argmax(Q, axis=1)
action_names = ['←', '↓', '→', '↑']
print("\nLearned Policy (4×4 grid):")
for i in range(4):
    row = [action_names[policy[i*4 + j]] for j in range(4)]
    print("  ".join(row))

# ── Test the trained agent ──
n_test = 1000
successes = 0
for _ in range(n_test):
    state, _ = env.reset()
    done = False
    while not done:
        action = np.argmax(Q[state])
        state, reward, terminated, truncated, _ = env.step(action)
        done = terminated or truncated
        if terminated and reward == 1.0:
            successes += 1

print(f"\nTest success rate: {successes/n_test*100:.1f}%")

Implementation 2: DQN for CartPole (PyTorch)

Python — DQN from Scratch with PyTorch
import torch
import torch.nn as nn
import torch.optim as optim
import numpy as np
import gymnasium as gym
from collections import deque
import random

# ── Neural Network for Q-function ──
class DQN(nn.Module):
    def __init__(self, state_dim, action_dim):
        super().__init__()
        self.network = nn.Sequential(
            nn.Linear(state_dim, 128),
            nn.ReLU(),
            nn.Linear(128, 128),
            nn.ReLU(),
            nn.Linear(128, action_dim)
        )
    
    def forward(self, x):
        return self.network(x)

# ── Experience Replay Buffer ──
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):
        batch = random.sample(self.buffer, batch_size)
        states, actions, rewards, next_states, dones = zip(*batch)
        return (np.array(states), np.array(actions),
                np.array(rewards, dtype=np.float32),
                np.array(next_states),
                np.array(dones, dtype=np.float32))
    
    def __len__(self):
        return len(self.buffer)

# ── DQN Agent ──
class DQNAgent:
    def __init__(self, state_dim, action_dim):
        self.action_dim = action_dim
        self.epsilon = 1.0
        self.epsilon_min = 0.01
        self.epsilon_decay = 0.995
        self.gamma = 0.99
        self.batch_size = 64
        self.target_update = 10  # update target net every N episodes
        
        # Online network (updated every step)
        self.online_net = DQN(state_dim, action_dim)
        # Target network (frozen copy, updated periodically)
        self.target_net = DQN(state_dim, action_dim)
        self.target_net.load_state_dict(self.online_net.state_dict())
        self.target_net.eval()
        
        self.optimizer = optim.Adam(self.online_net.parameters(), lr=1e-3)
        self.buffer = ReplayBuffer(capacity=50000)
    
    def select_action(self, state):
        # ε-greedy action selection
        if random.random() < self.epsilon:
            return random.randrange(self.action_dim)
        
        with torch.no_grad():
            state_t = torch.FloatTensor(state).unsqueeze(0)
            q_values = self.online_net(state_t)
            return q_values.argmax(dim=1).item()
    
    def train_step(self):
        if len(self.buffer) < self.batch_size:
            return None
        
        # Sample random mini-batch from replay buffer
        states, actions, rewards, next_states, dones = \
            self.buffer.sample(self.batch_size)
        
        states_t = torch.FloatTensor(states)
        actions_t = torch.LongTensor(actions).unsqueeze(1)
        rewards_t = torch.FloatTensor(rewards)
        next_states_t = torch.FloatTensor(next_states)
        dones_t = torch.FloatTensor(dones)
        
        # Current Q-values: Q(s, a; θ)
        current_q = self.online_net(states_t).gather(1, actions_t).squeeze()
        
        # Target Q-values: r + γ · max_a' Q(s', a'; θ⁻)
        with torch.no_grad():
            next_q = self.target_net(next_states_t).max(dim=1)[0]
            target_q = rewards_t + self.gamma * next_q * (1 - dones_t)
        
        # MSE Loss between current and target Q-values
        loss = nn.MSELoss()(current_q, target_q)
        
        # Gradient descent step
        self.optimizer.zero_grad()
        loss.backward()
        # Gradient clipping for stability
        nn.utils.clip_grad_norm_(self.online_net.parameters(), 1.0)
        self.optimizer.step()
        
        return loss.item()
    
    def update_target_network(self):
        # Copy online network weights to target network
        self.target_net.load_state_dict(self.online_net.state_dict())
    
    def decay_epsilon(self):
        self.epsilon = max(self.epsilon_min, self.epsilon * self.epsilon_decay)

# ── Training Loop ──
env = gym.make('CartPole-v1')
agent = DQNAgent(state_dim=4, action_dim=2)

n_episodes = 500
reward_history = []

for ep in range(n_episodes):
    state, _ = env.reset()
    total_reward = 0
    done = False
    
    while not done:
        action = agent.select_action(state)
        next_state, reward, terminated, truncated, _ = env.step(action)
        done = terminated or truncated
        
        # Store transition in replay buffer
        agent.buffer.push(state, action, reward, next_state, done)
        
        # Train on a mini-batch from buffer
        agent.train_step()
        
        state = next_state
        total_reward += reward
    
    agent.decay_epsilon()
    
    # Update target network periodically
    if ep % agent.target_update == 0:
        agent.update_target_network()
    
    reward_history.append(total_reward)
    
    if (ep + 1) % 50 == 0:
        avg = np.mean(reward_history[-50:])
        print(f"Episode {ep+1}, Avg Reward: {avg:.1f}, ε: {agent.epsilon:.3f}")

print(f"\nFinal avg reward (last 100): {np.mean(reward_history[-100:]):.1f}")
print("Solved!" if np.mean(reward_history[-100:]) >= 475 else "Not yet solved.")

# Bug: Can you find the mistake?
def train_step(self):
    states, actions, rewards, next_states, dones = self.buffer.sample(64)
    
    current_q = self.online_net(states_t).gather(1, actions_t)
    
    # BUG IS HERE ↓
    next_q = self.online_net(next_states_t).max(dim=1)[0]
    target_q = rewards_t + self.gamma * next_q * (1 - dones_t)
    
    loss = nn.MSELoss()(current_q, target_q)
    loss.backward()
    self.optimizer.step()

Implementation 3: REINFORCE Policy Gradient (PyTorch)

Python — REINFORCE from Scratch
import torch
import torch.nn as nn
import torch.optim as optim
from torch.distributions import Categorical
import numpy as np
import gymnasium as gym

# ── Policy Network ──
class PolicyNetwork(nn.Module):
    def __init__(self, state_dim, action_dim):
        super().__init__()
        self.network = nn.Sequential(
            nn.Linear(state_dim, 128),
            nn.ReLU(),
            nn.Linear(128, action_dim),
            nn.Softmax(dim=-1)  # output action probabilities
        )
    
    def forward(self, x):
        return self.network(x)

# ── REINFORCE Agent ──
class REINFORCEAgent:
    def __init__(self, state_dim, action_dim, lr=1e-3, gamma=0.99):
        self.gamma = gamma
        self.policy = PolicyNetwork(state_dim, action_dim)
        self.optimizer = optim.Adam(self.policy.parameters(), lr=lr)
        self.log_probs = []   # store log π(aₜ|sₜ)
        self.rewards = []      # store rewards
    
    def select_action(self, state):
        state_t = torch.FloatTensor(state)
        probs = self.policy(state_t)           # π(·|s)
        dist = Categorical(probs)               # categorical distribution
        action = dist.sample()                   # sample action
        self.log_probs.append(dist.log_prob(action))  # store log π(a|s)
        return action.item()
    
    def update(self):
        # Compute discounted returns Gₜ for each time step
        returns = []
        G = 0
        for r in reversed(self.rewards):
            G = r + self.gamma * G
            returns.insert(0, G)
        
        returns = torch.FloatTensor(returns)
        # Normalize returns (acts as a baseline, reduces variance)
        returns = (returns - returns.mean()) / (returns.std() + 1e-8)
        
        # Compute policy gradient loss
        # Loss = -Σ log π(aₜ|sₜ) · Gₜ  (negative because we minimize)
        policy_loss = []
        for log_prob, G in zip(self.log_probs, returns):
            policy_loss.append(-log_prob * G)
        
        loss = torch.stack(policy_loss).sum()
        
        self.optimizer.zero_grad()
        loss.backward()
        self.optimizer.step()
        
        # Clear episode data
        self.log_probs = []
        self.rewards = []
        
        return loss.item()

# ── Training ──
env = gym.make('CartPole-v1')
agent = REINFORCEAgent(state_dim=4, action_dim=2)

for ep in range(1000):
    state, _ = env.reset()
    done = False
    
    while not done:
        action = agent.select_action(state)
        state, reward, terminated, truncated, _ = env.step(action)
        agent.rewards.append(reward)
        done = terminated or truncated
    
    total_reward = sum(agent.rewards)
    agent.update()  # update AFTER full episode (Monte Carlo)
    
    if (ep + 1) % 100 == 0:
        print(f"Episode {ep+1}, Reward: {total_reward:.0f}")

Visual Diagrams

The RL Algorithm Taxonomy

Comparison: Value-Based vs Policy-Based Methods

The DQN Training Pipeline

Common Misconceptions

GATE/Exam Corner

Formula Sheet for Quick Revision

Previous Year Questions (PYQ) — GATE CS/DA

GATE Prediction Table

Interview Prep

Conceptual Questions

Coding Challenge (Interview Style)

import numpy as np

class UCBBandit:
    def __init__(self, n_arms, c=2.0):
        self.n_arms = n_arms
        self.c = c
        self.counts = np.zeros(n_arms)     # N(a): times each arm pulled
        self.values = np.zeros(n_arms)     # Q(a): estimated value
        self.t = 0
    
    def select_arm(self):
        self.t += 1
        # Pull each arm once first
        for i in range(self.n_arms):
            if self.counts[i] == 0:
                return i
        
        # UCB1: a = argmax[Q(a) + c·√(ln(t)/N(a))]
        ucb_values = self.values + self.c * np.sqrt(
            np.log(self.t) / self.counts
        )
        return np.argmax(ucb_values)
    
    def update(self, arm, reward):
        self.counts[arm] += 1
        # Incremental mean update
        self.values[arm] += (reward - self.values[arm]) / self.counts[arm]

# Simulate
true_probs = [0.1, 0.3, 0.7, 0.2, 0.5]  # arm 2 is best
bandit = UCBBandit(n_arms=5)

for _ in range(1000):
    arm = bandit.select_arm()
    reward = np.random.binomial(1, true_probs[arm])
    bandit.update(arm, reward)

print(f"Estimated values: {np.round(bandit.values, 3)}")
print(f"Pull counts: {bandit.counts}")
print(f"Best arm: {np.argmax(bandit.values)} (true best: 2)")

Hands-On Lab / Mini-Project

Exercises

Connections

Chapter Summary

Further Reading

🇮🇳 Indian Resources

• NPTEL Course: "Reinforcement Learning" by Prof. Balaraman Ravindran (IIT Madras) — comprehensive course covering bandits to deep RL, available free on NPTEL/Swayam
• NPTEL Course: "Introduction to Machine Learning" by Prof. Sudeshna Sarkar (IIT Kharagpur) — RL module in the ML course, good for GATE preparation
• IISc RL Lab: Research on RL for autonomous systems, papers on arXiv by Prof. Shalabh Bhatnagar's group
• GATE Reference: "Pattern Recognition and Machine Learning" by Christopher Bishop — Chapter on MDPs and RL
• AI4Bharat: Projects applying RL to Indian-language processing and robotics

🌍 Global Resources

• 📖 Textbook: "Reinforcement Learning: An Introduction" by Richard Sutton and Andrew Barto (2nd edition, 2018) — the definitive RL textbook, freely available online. Read Chapters 1-6 alongside this chapter.
• 📖 Textbook: "Deep Reinforcement Learning Hands-On" by Maxim Lapan (2nd edition, Packt) — practical PyTorch implementations
• 📄 Paper: Mnih et al., "Human-level Control through Deep Reinforcement Learning," Nature 2015 — the DQN paper
• 📄 Paper: Schulman et al., "Proximal Policy Optimization Algorithms," 2017 — the PPO paper
• 📄 Paper: Silver et al., "Mastering the Game of Go without Human Knowledge," Nature 2017 — AlphaZero
• 📄 Paper: Ouyang et al., "Training Language Models to Follow Instructions with Human Feedback," NeurIPS 2022 — InstructGPT/RLHF
• 📄 Paper: Rafailov et al., "Direct Preference Optimization," NeurIPS 2023 — DPO, the RLHF alternative
• 🎥 Video: David Silver's RL course (UCL/DeepMind, YouTube) — 10 lectures covering the full RL spectrum
• 🎥 Video: 3Blue1Brown — "But what is a neural network?" + "Gradient descent" (foundational)
• 🌐 Interactive: OpenAI Spinning Up — excellent tutorials on policy gradient, PPO, SAC with clean implementations
• 🌐 Interactive: CleanRL — single-file implementations of RL algorithms for learning
• 🌐 Distill.pub: "Attention and Augmented Recurrent Neural Networks" — interactive visualizations relevant to RL with memory