Reinforcement Learning

Every RL problem is an instance of the Markov Decision Process (MDP), a tuple (S, A, P, R, γ):

• S — the set of possible states the environment can be in.
• A — the set of actions the agent can take.
• P(s' | s, a) — the transition probability: given state s and action a, what is the probability of landing in state s'?
• R(s, a, s') — the reward function: the scalar signal the agent receives after transitioning.
• γ ∈ [0, 1) — the discount factor, which makes future rewards worth less than immediate ones.

The agent at each timestep t observes state sₜ, chooses action aₜ according to its policy π(a|s) (a probability distribution over actions given state), receives reward rₜ, and the environment transitions to sₜ₊₁. The agent's goal is to maximize the expected discounted return:

Gₜ = rₜ + γ·rₜ₊₁ + γ²·rₜ₊₂ + ··· = Σₖ₌₀^∞ γᵏ · rₜ₊ₖ

The Markov property is the key structural assumption: P(sₜ₊₁ | sₜ, aₜ, sₜ₋₁, aₜ₋₁, ...) = P(sₜ₊₁ | sₜ, aₜ). The future depends only on the present state, not on history. This is what makes the problem tractable; without it, the agent would need to remember all of history.

Analogy: Think of a chess player. The board position is the state. The legal moves are actions. The reward is +1 for winning, -1 for losing, 0 otherwise. The Markov property holds because the current board position encodes everything relevant about the game — you don't need to know how you got there.

The policy π is everything the agent is. A deterministic policy maps states to actions: π(s) = a. A stochastic policy gives probabilities: π(a|s) = P(aₜ = a | sₜ = s). Stochastic policies are important for games with mixed strategies and for exploration.

import numpy as np

# A simple GridWorld MDP: 4x4 grid, agent navigates to goal
# States: 0..15 (row-major), Actions: 0=Up,1=Down,2=Left,3=Right
# Terminal states: 0 (top-left) and 15 (bottom-right)

n_states = 16
n_actions = 4
gamma = 0.9

def step(state, action):
    """Returns (next_state, reward, done)"""
    if state in [0, 15]:  # terminal
        return state, 0, True
    row, col = divmod(state, 4)
    dr = [-1, 1, 0, 0][action]
    dc = [0, 0, -1, 1][action]
    new_row = max(0, min(3, row + dr))
    new_col = max(0, min(3, col + dc))
    next_state = new_row * 4 + new_col
    reward = -1  # penalty per step to encourage efficiency
    done = next_state in [0, 15]
    return next_state, reward, done

The value function is the central concept that makes RL computable. There are two flavors:

State-value function V^π(s): the expected return starting from state s, following policy π forever.

V^π(s) = E_π[Gₜ | sₜ = s] = E_π[rₜ + γ·V^π(sₜ₊₁) | sₜ = s]

Action-value function Q^π(s, a): the expected return starting from state s, taking action a, then following π.

Q^π(s, a) = E_π[Gₜ | sₜ = s, aₜ = a] = E[r + γ·Σ_{a'} π(a'|s')·Q^π(s', a') | s, a]

The recursive form of these equations are the Bellman equations — among the most important equations in all of RL. They express the value of a state in terms of the values of successor states. This is the principle of optimality: an optimal policy has the property that, regardless of the initial state and action, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.

The Bellman optimality equations describe the optimal value functions V* and Q*:

V*(s) = max_a Σ_{s'} P(s'|s,a) [R(s,a,s') + γ·V*(s')]

Q*(s,a) = Σ_{s'} P(s'|s,a) [R(s,a,s') + γ·max_{a'} Q*(s',a')]

If you have Q*, the optimal policy is trivially extracted: π*(s) = argmax_a Q*(s, a). The optimal action in any state is the one with the highest Q-value.

Why does this work? The discount factor γ < 1 means the Bellman operator is a contraction mapping (in the L∞ norm). By Banach's fixed-point theorem, repeated application converges to the unique fixed point V* regardless of the initial guess. This is the theoretical guarantee that underpins all DP-based RL methods.

Policy Evaluation (computing V^π for fixed π) and Policy Improvement (making π greedy w.r.t. V^π) alternate in Policy Iteration, provably converging to the optimal policy in finite MDPs in finitely many steps.

import numpy as np

# Policy Evaluation via iterative DP (small finite MDP)
# V[s] = sum_{a} pi(a|s) * sum_{s'} P(s'|s,a) * [R(s,a,s') + gamma * V[s']]

def policy_evaluation(policy, P, R, gamma=0.9, theta=1e-6):
    """P[s,a,s'] = transition prob, R[s,a] = expected reward"""
    n_states = policy.shape[0]
    V = np.zeros(n_states)
    while True:
        delta = 0
        for s in range(n_states):
            v = V[s]
            # Bellman expectation: average over actions (policy) and next states
            V[s] = sum(
                policy[s, a] * sum(
                    P[s, a, s_] * (R[s, a] + gamma * V[s_])
                    for s_ in range(n_states)
                )
                for a in range(policy.shape[1])
            )
            delta = max(delta, abs(v - V[s]))
        if delta < theta:
            break
    return V

def policy_improvement(V, P, R, gamma=0.9):
    """One step of greedy policy improvement"""
    n_states, n_actions = P.shape[:2]
    policy = np.zeros((n_states, n_actions))
    for s in range(n_states):
        q = np.array([
            sum(P[s,a,s_] * (R[s,a] + gamma * V[s_])
                for s_ in range(n_states))
            for a in range(n_actions)
        ])
        policy[s, np.argmax(q)] = 1.0  # deterministic greedy
    return policy

Policy iteration requires a known model (P and R). In most real problems, we don't have a model — we only have the ability to interact with the environment and observe transitions. This is the model-free setting, and it's where Q-learning shines.

Temporal Difference (TD) learning is the key insight: instead of waiting for an entire episode to compute a return (as Monte Carlo methods do), we bootstrap — we update our value estimate using the current estimate of the next state's value. The TD error (also called the Bellman residual) at each step is:

δₜ = rₜ + γ·V(sₜ₊₁) - V(sₜ)

This is the difference between our prediction and a better estimate. We nudge our estimate toward the better one.

Q-learning (Watkins, 1989) is an off-policy TD method for learning Q*:

Q(sₜ, aₜ) ← Q(sₜ, aₜ) + α · [rₜ + γ·max_{a'} Q(sₜ₊₁, a') - Q(sₜ, aₜ)]

The key phrase is off-policy: Q-learning learns the optimal Q-function regardless of how the agent actually behaves. The target uses max_{a'} — the greedy action — even if the agent took a different action to explore. This is in contrast to SARSA (on-policy), which uses the Q-value of the actual next action:

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

Why Q-learning converges: Under standard stochastic approximation conditions (all (s,a) pairs visited infinitely often, learning rates satisfying Σαₜ = ∞ and Σαₜ² < ∞), Q-learning converges to Q* almost surely. This is proven using the theory of stochastic approximation (Robbins-Monro conditions) plus the contraction property of the Bellman optimality operator.

The ε-greedy policy balances exploration and exploitation: with probability ε, take a random action; with probability 1-ε, take the greedy action argmax_a Q(s,a). Typically ε decays over time as the agent gains confidence in its estimates.

import numpy as np
import random

class QLearningAgent:
    def __init__(self, n_states, n_actions, alpha=0.1, gamma=0.99, epsilon=1.0, eps_decay=0.995):
        self.Q = np.zeros((n_states, n_actions))
        self.alpha = alpha
        self.gamma = gamma
        self.epsilon = epsilon
        self.eps_decay = eps_decay
        self.n_actions = n_actions

    def select_action(self, state):
        """Epsilon-greedy action selection"""
        if random.random() < self.epsilon:
            return random.randrange(self.n_actions)  # explore
        return np.argmax(self.Q[state])              # exploit

    def update(self, s, a, r, s_next, done):
        """Q-learning Bellman update"""
        target = r if done else r + self.gamma * np.max(self.Q[s_next])
        td_error = target - self.Q[s, a]
        self.Q[s, a] += self.alpha * td_error

    def decay_epsilon(self):
        self.epsilon = max(0.01, self.epsilon * self.eps_decay)

# Training loop skeleton
def train(env, agent, n_episodes=1000):
    for episode in range(n_episodes):
        state = env.reset()
        done = False
        while not done:
            action = agent.select_action(state)
            next_state, reward, done, _ = env.step(action)
            agent.update(state, action, reward, next_state, done)
            state = next_state
        agent.decay_epsilon()

The exploration-exploitation tradeoff is arguably the deepest conceptual challenge in RL. You cannot optimize what you haven't measured, but you also can't keep measuring forever — you need to act on your best current knowledge. This tension never fully resolves.

Multi-armed bandits are the pure version of this problem: k slot machines ("arms"), each with unknown reward distribution. You pull one arm per timestep. Pull the best arm forever (exploit), and you win — if you knew which was best. Try every arm forever (explore), and you gather perfect information — but waste pulls on bad arms. The regret after T rounds is:

Regret(T) = T·μ* - Σₜ μ_{aₜ}

where μ* is the optimal arm's mean and μ_{aₜ} is the expected reward of the chosen arm at round t. The Lai-Robbins lower bound says any consistent algorithm must incur Ω(log T) regret — no algorithm can do better asymptotically.

UCB (Upper Confidence Bound) achieves this lower bound. The idea: be optimistic in the face of uncertainty. Choose the arm that maximizes:

UCB(a) = Q̂(a) + c · √(ln t / N(a))

where Q̂(a) is the estimated value, N(a) is the number of times arm a was pulled, t is total rounds, and c is a constant. The bonus term is wide when N(a) is small (we're uncertain) and narrow when N(a) is large (we're confident). UCB1 achieves O(log T) regret — optimal up to constants.

Thompson Sampling takes a Bayesian approach: maintain a posterior distribution over arm reward rates, sample one value from each posterior, pick the arm with the highest sample. It is empirically excellent and has strong theoretical guarantees.

In full RL (not just bandits), the exploration problem is much harder because actions have long-horizon consequences — a bad exploration choice now might corrupt future value estimates, and the credit assignment problem (which early action caused this late reward?) is difficult. Modern deep RL uses:

• ε-greedy (simple but effective)
• Boltzmann (softmax) exploration: π(a|s) ∝ exp(Q(s,a)/τ)
• Intrinsic motivation: add a bonus reward for visiting novel states (curiosity-driven exploration, e.g., Random Network Distillation)
• Parameter-space noise: add noise to network weights rather than actions, producing more coherent exploratory behavior

import numpy as np

class UCB1Bandit:
    """UCB1 algorithm for the k-armed bandit"""
    def __init__(self, k):
        self.k = k
        self.counts = np.zeros(k)   # N(a)
        self.values = np.zeros(k)   # Q_hat(a)
        self.t = 0

    def select_arm(self):
        self.t += 1
        # Pull each arm once to initialize
        if self.t <= self.k:
            return self.t - 1
        ucb = self.values + np.sqrt(2 * np.log(self.t) / self.counts)
        return np.argmax(ucb)

    def update(self, arm, reward):
        self.counts[arm] += 1
        # Incremental mean update
        self.values[arm] += (reward - self.values[arm]) / self.counts[arm]

# Thompson Sampling for Bernoulli bandits
class ThompsonSamplingBandit:
    def __init__(self, k):
        self.alpha = np.ones(k)  # Beta distribution shape params
        self.beta  = np.ones(k)

    def select_arm(self):
        samples = np.random.beta(self.alpha, self.beta)
        return np.argmax(samples)

    def update(self, arm, reward):  # reward is 0 or 1
        self.alpha[arm] += reward
        self.beta[arm]  += (1 - reward)

Tabular Q-learning works when the state space is small enough to store Q(s,a) in a table. For Atari games, the state is a 210×160 RGB image — roughly 33,000 pixels, meaning an astronomically large state space. The solution: approximate Q(s,a) with a neural network Q(s, a; θ), where θ are the network weights.

But naively combining Q-learning with neural network function approximation is famously unstable. The 2013 DeepMind paper (Mnih et al.) that introduced DQN identified two root causes and fixed both:

Problem 1: Correlated samples. Online RL generates highly correlated consecutive (s,a,r,s') tuples. Training a neural net on correlated mini-batches leads to oscillation and divergence (it violates the i.i.d. assumption that SGD needs).

Fix: Experience Replay. Store transitions in a replay buffer D (a circular buffer of capacity N, e.g., 1 million). At each training step, sample a random mini-batch of B transitions from D. This breaks temporal correlations and allows each experience to be used multiple times.

Problem 2: Non-stationary targets. The TD target rₜ + γ·max_{a'} Q(sₜ₊₁, a'; θ) uses the same network θ we're updating. This means the target is moving as we update — we're chasing a moving goalposts, causing oscillation.

Fix: Target Network. Maintain a separate target network Q(s, a; θ⁻) with frozen weights. Periodically (every C steps) copy θ → θ⁻. The loss becomes:

L(θ) = E_{(s,a,r,s')~D} [(r + γ·max_{a'} Q(s', a'; θ⁻) - Q(s, a; θ))²]

Architecture: DQN takes a stack of 4 grayscale frames (84×84) as input, processes them through 3 convolutional layers, then 2 fully connected layers, and outputs one Q-value per action. The output layer has no activation — Q-values are unbounded.

Double DQN (van Hasselt et al., 2016): standard DQN has a maximization bias — max_{a'} Q(s', a'; θ⁻) overestimates because it selects and evaluates actions with the same network. Double DQN separates action selection (use θ) from action evaluation (use θ⁻):

target = r + γ · Q(s', argmax_{a'} Q(s', a'; θ); θ⁻)

Prioritized Experience Replay: Sample transitions with probability proportional to their TD error |δ|^α (more surprising transitions are sampled more often). Correct for the resulting bias with importance-sampling weights.

import torch
import torch.nn as nn
import random
from collections import deque
import numpy as np

class DQN(nn.Module):
    def __init__(self, n_obs, n_actions):
        super().__init__()
        self.net = nn.Sequential(
            nn.Linear(n_obs, 128), nn.ReLU(),
            nn.Linear(128, 128),  nn.ReLU(),
            nn.Linear(128, n_actions)
        )
    def forward(self, x):
        return self.net(x)

class ReplayBuffer:
    def __init__(self, capacity=100_000):
        self.buf = deque(maxlen=capacity)
    def push(self, *transition):
        self.buf.append(transition)
    def sample(self, batch_size):
        batch = random.sample(self.buf, batch_size)
        s, a, r, s_, done = map(np.array, zip(*batch))
        return (torch.FloatTensor(s), torch.LongTensor(a),
                torch.FloatTensor(r), torch.FloatTensor(s_),
                torch.FloatTensor(done))
    def __len__(self):
        return len(self.buf)

def train_step(online_net, target_net, optimizer, buffer,
               batch_size=64, gamma=0.99):
    if len(buffer) < batch_size:
        return
    s, a, r, s_, done = buffer.sample(batch_size)

    # Current Q-values for taken actions
    q_vals = online_net(s).gather(1, a.unsqueeze(1)).squeeze()

    # Double DQN target
    with torch.no_grad():
        next_actions = online_net(s_).argmax(dim=1)  # select with online
        next_q = target_net(s_).gather(1, next_actions.unsqueeze(1)).squeeze()
        target = r + gamma * next_q * (1 - done)

    loss = nn.functional.mse_loss(q_vals, target)
    optimizer.zero_grad()
    loss.backward()
    torch.nn.utils.clip_grad_norm_(online_net.parameters(), 10)
    optimizer.step()

Value-based methods (Q-learning, DQN) learn a value function and derive a policy implicitly. Policy gradient methods take a different approach: directly parameterize the policy π(a|s; θ) and optimize the parameters θ to maximize expected return.

Why might this be better? (1) Policy gradients handle continuous action spaces naturally — just have the network output a Gaussian distribution over actions. (2) They can learn stochastic policies (important for games with optimal mixed strategies). (3) They are better behaved theoretically in the function approximation setting.

The Policy Gradient Theorem (Sutton et al., 1999) is the foundation. The gradient of the expected return J(θ) = E_π[G₀] with respect to θ is:

∇_θ J(θ) = E_π [∇_θ log π(aₜ|sₜ; θ) · Gₜ]

This beautiful result says: the gradient of the performance is an expectation of the log-probability of the action times the return. The term ∇_θ log π(a|s; θ) is called the score function (or likelihood ratio gradient).

Intuition: If an action led to high return (Gₜ large), we push the parameters to make that action more probable. If the return was low (or negative), we push parameters away. The log-gradient trick lets us estimate this without needing the environment's model.

REINFORCE is the simplest policy gradient algorithm: run a full episode, compute returns Gₜ for each timestep, then update:

θ ← θ + α · Σₜ ∇_θ log π(aₜ|sₜ; θ) · Gₜ

Baseline subtraction: We can subtract any function b(s) from Gₜ without biasing the gradient (because E[∇ log π · b(s)] = 0). Using b(s) = V(s) gives the advantage Aₜ = Gₜ - V(sₜ), which dramatically reduces variance:

∇_θ J(θ) = E_π [∇_θ log π(aₜ|sₜ; θ) · Aₜ]

The advantage Aₜ > 0 means the action was better than average — increase its probability. Aₜ < 0 means it was worse — decrease. This is more stable than raw returns because it centers the learning signal.

import torch
import torch.nn as nn
import torch.optim as optim
from torch.distributions import Categorical
import numpy as np

class PolicyNetwork(nn.Module):
    def __init__(self, n_obs, n_actions):
        super().__init__()
        self.net = nn.Sequential(
            nn.Linear(n_obs, 64), nn.Tanh(),
            nn.Linear(64, 64),   nn.Tanh(),
            nn.Linear(64, n_actions)
        )
    def forward(self, x):
        return torch.softmax(self.net(x), dim=-1)

def reinforce(env, policy, optimizer, n_episodes=1000, gamma=0.99):
    for ep in range(n_episodes):
        # Collect one episode
        log_probs, rewards = [], []
        state = torch.FloatTensor(env.reset())
        done = False
        while not done:
            probs = policy(state)
            dist  = Categorical(probs)
            action = dist.sample()
            log_probs.append(dist.log_prob(action))
            state, reward, done, _ = env.step(action.item())
            rewards.append(reward)
            state = torch.FloatTensor(state)

        # Compute discounted returns (backward pass)
        G, returns = 0, []
        for r in reversed(rewards):
            G = r + gamma * G
            returns.insert(0, G)
        returns = torch.FloatTensor(returns)

        # Normalize returns (variance reduction)
        returns = (returns - returns.mean()) / (returns.std() + 1e-8)

        # Policy gradient update
        loss = -sum(lp * G for lp, G in zip(log_probs, returns))
        optimizer.zero_grad()
        loss.backward()
        optimizer.step()

REINFORCE has high variance because Gₜ is estimated from a single trajectory. The solution is actor-critic: simultaneously learn a policy (the actor, π(a|s; θ)) and a value function (the critic, V(s; w)), and use the critic's learned baseline to reduce variance.

The update rules are:

• Critic update: minimize TD error — δₜ = rₜ + γ·V(sₜ₊₁; w) - V(sₜ; w), update w to reduce δₜ².
• Actor update: ∇_θ J(θ) = E[∇_θ log π(aₜ|sₜ; θ) · δₜ], where δₜ is used as the advantage estimate.

Because δₜ uses one-step TD (a learned value function) rather than a Monte Carlo return, variance is much lower — though we now have some bias from the critic.

Advantage Actor-Critic (A2C) and its asynchronous variant A3C (Mnih et al., 2016) parallelizes multiple agents in separate environment copies, gathering diverse experience simultaneously. Each worker computes gradients and pushes them to a shared global network, solving both the correlation problem and data efficiency.

Proximal Policy Optimization (PPO) (Schulman et al., 2017) is arguably the most practical RL algorithm today. The key insight: large policy updates can be catastrophic (if you accidentally make a bad action very probable, you may never recover). PPO clips the ratio rₜ(θ) = π(aₜ|sₜ; θ) / π(aₜ|sₜ; θ_old) to stay near 1:

L^CLIP(θ) = E[min(rₜ(θ)·Aₜ, clip(rₜ(θ), 1-ε, 1+ε)·Aₜ)]

This prevents updates that make the policy stray too far from the behavior policy, giving a simple first-order approximation of the trust region constraint. PPO is the algorithm behind OpenAI Five, the early versions of ChatGPT's RLHF training, and most modern continuous control benchmarks.

Soft Actor-Critic (SAC) extends the framework to entropy regularization — adding a term αH(π(·|s)) to the objective encourages the policy to be as random as possible while still maximizing reward. This automatic exploration bonus makes SAC extremely sample-efficient for continuous control.

# Simplified A2C update (single actor-critic with shared trunk)
import torch
import torch.nn as nn

class ActorCritic(nn.Module):
    """Shared trunk, separate actor (policy) and critic (value) heads"""
    def __init__(self, n_obs, n_actions):
        super().__init__()
        self.trunk = nn.Sequential(
            nn.Linear(n_obs, 128), nn.Tanh(),
            nn.Linear(128, 128),  nn.Tanh()
        )
        self.actor  = nn.Linear(128, n_actions)  # logits -> softmax -> pi
        self.critic = nn.Linear(128, 1)           # -> V(s)

    def forward(self, x):
        features = self.trunk(x)
        logits   = self.actor(features)
        value    = self.critic(features).squeeze(-1)
        return logits, value

def a2c_loss(logits, values, actions, returns, gamma=0.99, entropy_coef=0.01):
    """Compute combined actor + critic loss"""
    from torch.distributions import Categorical
    dist = Categorical(logits=logits)
    log_probs = dist.log_prob(actions)
    entropy   = dist.entropy()

    # Advantage: use returns (MC or n-step) minus baseline
    advantages = returns - values.detach()  # stop gradient through baseline
    advantages = (advantages - advantages.mean()) / (advantages.std() + 1e-8)

    actor_loss  = -(log_probs * advantages).mean()
    critic_loss = 0.5 * (returns - values).pow(2).mean()
    entropy_loss = -entropy.mean()  # bonus for exploration

    return actor_loss + 0.5 * critic_loss + entropy_coef * entropy_loss

All methods discussed so far are model-free: they learn directly from environment interactions without building an internal model of the world. Model-based RL learns a transition model P̂(s'|s,a) and/or reward model R̂(s,a), then uses that model for planning.

The advantage is sample efficiency: a model lets you simulate experience without interacting with the real environment, allowing you to extract more learning from each real transition. In environments where each interaction is expensive (robotics, chemistry, medical trials), this is crucial.

Dyna-Q (Sutton, 1991) is the canonical hybrid: interleave real experience with simulated experience. After each real step:

1. Update Q from the real transition.
2. Sample k random previously-seen (s,a) pairs, simulate next states using the learned model, and run k more Q-learning updates.

This amortizes the cost of model learning across many planning steps.

Monte Carlo Tree Search (MCTS) is a powerful planning algorithm that does not need a global value function — it builds a partial search tree online using random rollouts. For each state in the tree:

1. Selection: traverse the tree using UCB to balance exploration and exploitation.
2. Expansion: when reaching a leaf, expand one new node.
3. Simulation (Rollout): simulate to terminal state with a fast rollout policy.
4. Backpropagation: update the win statistics along the path.

MCTS was the state of the art for Go before deep learning, and it remains central to AlphaGo/AlphaZero.

World models (Ha and Schmidhuber, 2018) train a recurrent neural network to model environment dynamics in latent space, then train the controller entirely in the dream — the simulated world. Dreamer (Hafner et al., 2019-2023) is the most successful modern incarnation, achieving state-of-the-art on continuous control and Atari with far fewer real environment interactions than model-free methods.

# Dyna-Q: model-based planning embedded in Q-learning
import numpy as np
import random
from collections import defaultdict

class DynaQAgent:
    def __init__(self, n_states, n_actions, alpha=0.1, gamma=0.95,
                 epsilon=0.1, n_planning_steps=10):
        self.Q = np.zeros((n_states, n_actions))
        self.model = {}           # (s,a) -> (r, s') learned model
        self.alpha = alpha
        self.gamma = gamma
        self.epsilon = epsilon
        self.n = n_planning_steps
        self.seen = set()         # observed (s,a) pairs

    def select_action(self, s):
        if random.random() < self.epsilon:
            return random.randrange(self.Q.shape[1])
        return np.argmax(self.Q[s])

    def step(self, s, a, r, s_next, done):
        # (1) Direct RL update
        target = r if done else r + self.gamma * np.max(self.Q[s_next])
        self.Q[s, a] += self.alpha * (target - self.Q[s, a])

        # (2) Model learning
        self.model[(s, a)] = (r, s_next)
        self.seen.add((s, a))

        # (3) Planning: simulate from model
        seen_list = list(self.seen)
        for _ in range(self.n):
            sim_s, sim_a = random.choice(seen_list)
            sim_r, sim_s_ = self.model[(sim_s, sim_a)]
            sim_target = sim_r + self.gamma * np.max(self.Q[sim_s_])
            self.Q[sim_s, sim_a] += self.alpha * (sim_target - self.Q[sim_s, sim_a])

The defeat of world Go champion Lee Sedol by AlphaGo in March 2016 is a landmark moment in the history of AI, and understanding how it works is a superb illustration of RL in practice.

Go has roughly 10^170 legal board positions — more than atoms in the observable universe. The game tree has an average branching factor of ~250 and typical game lengths of 150 moves, making exhaustive search utterly infeasible. Before AlphaGo, Go was considered the hardest classic board game and professional-level play was decades away.

AlphaGo's four components:

1. Supervised Learning policy network (SL): trained on 30 million positions from human expert games to predict the human move. This gives a strong prior over plausible moves.
2. Reinforcement Learning policy network (RL): starts from the SL network, then plays against previous versions of itself (self-play). Policy gradient updates make winning moves more likely.
3. Value network: trained to predict the game outcome (win/loss) from a given position, using the RL policy for both players. This replaces expensive rollouts with a fast learned evaluation.
4. Monte Carlo Tree Search (MCTS): combines all three. The SL/RL policy guides the tree expansion (which moves to explore), and the value network + rollouts estimate leaf values. UCB selects which branch to traverse.

AlphaZero (2017) improved and generalized this dramatically: it uses no human data at all, starting from random play and purely self-play RL. The SL policy network is gone; a single network simultaneously outputs both a policy (move probabilities) and a value (win probability). MCTS is still used, but now the policy output guides the tree search, and the MCTS visit counts feed back as the training targets for the policy head — a brilliant bootstrapping loop.

AlphaZero mastered chess, shogi, and Go to superhuman level from scratch within 24 hours of training, using architectures and training procedures that are by now well-understood engineering. MuZero further removes even the need for explicit game rules — it learns a latent model of game dynamics as well.

The key RL insight in AlphaZero: Self-play creates an automatic curriculum. As the agent improves, its opponent (a previous version of itself) is always at approximately the right difficulty level — hard enough to teach but beatable. This avoids the problem of having no training signal from a perfect opponent or no challenge from a trivially weak one.

# AlphaZero: conceptual pseudocode for self-play training loop

def alphazero_training(network, n_iterations=1000, games_per_iter=100):
    """
    network: outputs (policy_logits, value) for a given board state
    MCTS uses the network to guide search, returns improved policy.
    """
    replay_buffer = []

    for iteration in range(n_iterations):
        # (1) Self-play: generate training data
        for _ in range(games_per_iter):
            game_history = []  # list of (state, mcts_policy, outcome)
            state = initial_state()
            while not is_terminal(state):
                # MCTS with neural guidance
                mcts_policy = mcts_search(
                    state, network, n_simulations=800
                )  # returns improved policy as visit count distribution
                action = sample(mcts_policy, temperature=1.0)
                game_history.append((state, mcts_policy))
                state = apply_action(state, action)

            outcome = game_result(state)  # +1 or -1
            for s, pi in game_history:
                replay_buffer.append((s, pi, outcome))

        # (2) Network training
        for batch in sample_batches(replay_buffer):
            states, target_pi, target_v = batch
            pred_pi, pred_v = network(states)
            # Combined loss: cross-entropy for policy + MSE for value
            policy_loss = cross_entropy(pred_pi, target_pi)
            value_loss  = mse(pred_v, target_v)
            loss = policy_loss + value_loss
            gradient_step(loss)

    return network

Real RL problems are hard for reasons that go beyond algorithm choice. Understanding these challenges is essential for practitioners.

The Credit Assignment Problem: In a game of chess, the reward (+1/-1) comes at the very end of a 40-move game. Which moves were responsible for the outcome? This temporal credit assignment is hard because reward is sparse and delayed. Solutions:

• Eligibility traces (TD(λ)): a weighted mixture between TD(0) (one-step) and MC (full return). The trace γλ decays credit backwards in time: moves just before a reward get strong credit, moves far before get weak credit.
• Hindsight Experience Replay (HER): for goal-conditioned tasks, relabel failed trajectories as if the agent did achieve whatever state it ended up in. This creates synthetic successes from failures.

Reward Shaping: When natural rewards are sparse, we add a shaping reward F(s, a, s') to help the agent learn. The key theorem (Ng et al., 1999): a shaping reward that is a potential difference F(s, a, s') = γΦ(s') - Φ(s) for any potential function Φ never changes the set of optimal policies (though it changes how quickly the agent learns them). Arbitrary shaping rewards can change optimal behavior, producing pathological reward hacking.

Reward Hacking: The agent finds unintended ways to maximize reward that violate the designer's intent. A cleaning robot rewarded for seeing no mess might learn to cover its camera. A boat racing agent rewarded for hitting checkpoints might go in circles forever between two checkpoints. These are not bugs in the algorithm — they are the algorithm working perfectly. The problem is our reward specification. RLHF attempts to solve this by learning rewards from human preferences, but introduces its own failure modes.

Sample Inefficiency: Deep RL algorithms often require millions of environment interactions to learn tasks that humans solve in minutes. DQN needed 200 million Atari frames (~38 days of gameplay at 60fps) to match human performance. This is a fundamental challenge for real-world deployment.

Non-stationarity in Multi-Agent Settings: When multiple agents learn simultaneously, each agent's environment includes other learning agents. The environment is non-stationary from any single agent's perspective, which breaks convergence guarantees. Multi-agent RL (MARL) is an active research frontier.

# TD(lambda) return computation
import numpy as np

def td_lambda_returns(rewards, values, gamma=0.99, lam=0.95):
    """
    Compute GAE (Generalized Advantage Estimation) lambda-returns.
    rewards: list of R_t
    values:  list of V(s_t), with values[-1] = V(s_T) (bootstrap)
    Returns lambda-weighted advantages and value targets.
    """
    T = len(rewards)
    advantages = np.zeros(T)
    gae = 0.0
    for t in reversed(range(T)):
        # delta_t = r_t + gamma * V(s_{t+1}) - V(s_t)  (TD error)
        delta = rewards[t] + gamma * values[t+1] - values[t]
        # GAE: exponentially weighted sum of TD errors
        gae = delta + gamma * lam * gae
        advantages[t] = gae
    value_targets = advantages + values[:-1]  # V_target = A + V_old
    return advantages, value_targets

# Example: reward shaping with potential function
def shaped_reward(r, state, next_state, phi, gamma=0.99):
    """
    phi(s): potential function (e.g., negative distance to goal)
    Potential-based shaping: F(s,s') = gamma*phi(s') - phi(s)
    Guaranteed to preserve optimal policy.
    """
    F = gamma * phi(next_state) - phi(state)
    return r + F

Reinforcement Learning from Human Feedback (RLHF) is the technique that transformed large language models from next-token predictors into aligned assistants. Understanding it requires everything we've built in this module.

The pipeline has three stages:

Stage 1: Supervised Fine-Tuning (SFT). Start with a pretrained LLM. Fine-tune it on a dataset of high-quality (prompt, response) pairs written by human demonstrators. This gives a well-behaved initial policy.

Stage 2: Reward Model Training. Show human raters pairs of responses (y₁, y₂) to the same prompt x. They indicate which response they prefer. Train a reward model RM(x, y) → scalar to predict human preferences. Typically, RM is the SFT model with the final token prediction head replaced by a scalar head, trained with the Bradley-Terry model:

P(y₁ ≻ y₂) = σ(RM(x, y₁) - RM(x, y₂))

Stage 3: RL Fine-Tuning with PPO. Treat the SFT policy as the RL agent, text tokens as actions, and the reward model's score as the reward signal. Optimize the policy with PPO to maximize RM(x, y).

Crucially, a KL penalty is added to prevent the policy from drifting too far from the SFT model:

r(x, y) = RM(x, y) - β · KL[π_θ(y|x) || π_SFT(y|x)]

Without this, the policy reward-hacks: it quickly learns to produce text that achieves high RM scores while becoming incoherent to humans (the RM is imperfect and the policy finds its failure modes).

Limitations and frontiers: RLHF is expensive (requires many human comparisons), and reward hacking remains a concern. Constitutional AI (CAI) uses an AI to generate its own critiques and revisions, reducing dependence on human labeling. Direct Preference Optimization (DPO) (Rafailov et al., 2023) shows that the RLHF optimization problem can be reparametrized to optimize a simple classification objective directly on preference data, eliminating the separate reward model and PPO entirely — a major simplification.

# RLHF Reward Model training sketch (Bradley-Terry preference model)
import torch
import torch.nn as nn

class RewardModel(nn.Module):
    """Wraps an LLM backbone; outputs scalar reward for a (prompt, response)."""
    def __init__(self, backbone):
        super().__init__()
        self.backbone = backbone
        hidden_dim = backbone.config.hidden_size
        self.reward_head = nn.Linear(hidden_dim, 1)

    def forward(self, input_ids, attention_mask):
        outputs = self.backbone(
            input_ids=input_ids, attention_mask=attention_mask
        )
        # Use last token's representation as reward signal
        last_hidden = outputs.last_hidden_state[:, -1, :]
        return self.reward_head(last_hidden).squeeze(-1)

def preference_loss(reward_model, chosen_ids, chosen_mask,
                    rejected_ids, rejected_mask):
    """
    Bradley-Terry loss: reward(chosen) > reward(rejected)
    Loss = -log sigma(r_chosen - r_rejected)
    """
    r_chosen   = reward_model(chosen_ids,   chosen_mask)
    r_rejected = reward_model(rejected_ids, rejected_mask)
    # Log-sigmoid of reward difference
    loss = -torch.nn.functional.logsigmoid(r_chosen - r_rejected).mean()
    return loss

# PPO RL fine-tuning objective (simplified)
# r(x,y) = RM(x,y) - beta * KL(pi_theta || pi_ref)
def rlhf_reward(rm_score, log_prob_theta, log_prob_ref, beta=0.1):
    kl_penalty = log_prob_theta - log_prob_ref  # per-token KL approx
    return rm_score - beta * kl_penalty.sum(-1)