Understand Reinforcement
Learning

Chapter 1: Exploration vs Exploitation

Before we learn any algorithms, we must understand the fundamental dilemma: exploration vs exploitation. Should you go to your favourite restaurant (exploit what you know), or try a new place (explore to find something better)?

The multi-armed bandit problem distills this perfectly. You face N slot machines, each with an unknown payout probability. You want to maximize total winnings. If you always pull the lever that looks best so far, you might miss a better one. If you explore too much, you waste pulls on bad machines.

Chapter 2: Monte Carlo Methods

The simplest approach to estimating how good a state is: play out full episodes, then average the returns you got. If you visited state S and ended up with a total return of 7, and another time you got 3, your estimate of V(S) is (7+3)/2 = 5. That's it. No fancy math.

There are two flavors: first-visit MC (only count the first time you visit a state in an episode) and every-visit MC (count every visit). Both converge to the true value as you play more episodes.

Chapter 3: TD Learning — Learning from Incomplete Episodes

What if you could learn before an episode ends? Temporal Difference (TD) learning does exactly that. Instead of waiting for the full return G, it uses an estimate: the immediate reward plus the current guess of the next state's value.

The TD(0) update rule shifts the value of the current state toward a bootstrapped target: r + γV(s'). The difference between this target and our current estimate is the TD error δ.

Chapter 4: Q-Learning — The Classic

Instead of estimating how good a state is (V), what if we estimated how good a state-action pair is? That's Q-learning. Q(s, a) tells us the expected return of taking action a in state s and then acting optimally afterward. If we know Q perfectly, we can act optimally by always picking argmax_a Q(s, a).

Q-learning is off-policy: it learns the optimal policy regardless of what the agent actually does. The update uses the maximum Q-value of the next state, not the Q-value of the action the agent actually took.

The Q-Table, Concretely

For a gridworld with |S| = 100 states and |A| = 4 actions, Q is simply a [100, 4] array — 400 numbers, initialized to zeros. Each entry Q[s, a] estimates the expected return of taking action a in state s. The entire learning algorithm is one line of NumPy per step:

Python
import numpy as np

# Initialize the Q-table: 100 states × 4 actions = 400 entries
Q = np.zeros((100, 4))

# After observing (s, a, r, s'):
Q[s, a] += alpha * (r + gamma * np.max(Q[s_next, :]) - Q[s, a])
#                   └── TD target ──┘   └── old estimate ┘

# Extract greedy policy: best action per state
policy = np.argmax(Q, axis=1)  # shape [100]

That's the complete Q-learning implementation. The alpha * (target - old) pattern is the same as TD learning from Chapter 3, but now applied to state-action pairs instead of just states.

python
import numpy as np

def q_learning(env, n_episodes=1000, alpha=0.1, gamma=0.99, epsilon=0.1):
    Q = np.zeros((env.n_states, env.n_actions))

    for ep in range(n_episodes):
        state = env.reset()
        done = False

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

            # Take action, observe transition
            next_state, reward, done = env.step(action)

            # Q-learning update (off-policy: uses max)
            if done:
                target = reward  # No future value at terminal
            else:
                target = reward + gamma * np.max(Q[next_state])

            Q[state, action] += alpha * (target - Q[state, action])
            state = next_state

    return Q

Chapter 5: SARSA — On-Policy Q-Learning

SARSA stands for State, Action, Reward, State, Action — exactly what the update uses. Unlike Q-learning, SARSA updates toward the Q-value of the action the agent actually took next, not the maximum. This makes it on-policy: it evaluates and improves the policy it's currently following.

The practical difference? SARSA is more conservative. If the agent explores and sometimes steps into danger, SARSA's values reflect that danger. Q-learning's values assume you'll act optimally after, so they're more optimistic. Near cliffs and traps, SARSA learns to stay further away.

Chapter 6: Deep Q-Networks (DQN)

Q-learning with a table works for small state spaces. But what about Atari games with millions of possible screen configurations? You can't have a table entry for every pixel combination. The breakthrough idea from DeepMind (2015): replace the Q-table with a neural network.

The network takes a state (raw pixels) as input and outputs Q-values for each possible action. But training is tricky — naive approaches diverge because of two problems:

DQN Data Flow

The neural network is the Q-table. Instead of a [|S|, |A|] array (impossible for pixel inputs), a CNN maps raw frames to Q-values:

Architecture
# Input: 4 stacked grayscale frames (motion information)
State:  [4, 84, 84]        # 4 frames × 84×84 pixels = 28,224 values
         ↓
Conv2D(32, 8×8, stride 4)  # → [32, 20, 20]
Conv2D(64, 4×4, stride 2)  # → [64, 9, 9]
Conv2D(64, 3×3, stride 1)  # → [64, 7, 7]
Flatten                      # → [3136]
Dense(512)                  # → [512]  (learned features)
Dense(18)                   # → [18]   (one Q-value per action)

# Action = argmax over these 18 Q-values

Experience Replay, Concretely

The replay buffer stores transitions as tuples (s, a, r, s', done). For Atari: 1 million transitions, each containing two frame stacks of [4, 84, 84]. Naive storage: 1M × (28,224 + 1 + 1 + 28,224 + 1) bytes ≈ 56 GB. In practice, you store each unique frame once and reference them by index — dropping memory to about 7 GB. Training samples a random mini-batch (typically 32) from this buffer, breaking temporal correlations.

Chapter 7: Policy Gradients — REINFORCE

Everything so far learned a value function and derived a policy from it. But what if we optimized the policy directly? Policy gradient methods parameterize the policy as π_θ(a|s) and use gradient ascent to maximize expected reward.

The REINFORCE algorithm is the simplest policy gradient method. The key insight: the gradient of the expected return has a beautiful form called the score function estimator:

Translation: increase the probability of actions that led to high returns; decrease it for actions that led to low returns. It's intuitive, unbiased, but has high variance — returns can vary wildly between episodes, making gradients noisy.

Q-Learning vs Policy Gradient: Side by Side

Chapter 8: Actor-Critic — Best of Both Worlds

REINFORCE uses the full return G_t as a signal, which is high variance. What if we replaced G_t with a learned value estimate? That's the actor-critic architecture: the actor is the policy (decides what to do), and the critic is the value function (evaluates how good the state is).

The critic provides a low-variance baseline, dramatically stabilizing training. The actor updates using the advantage A(s,a) = Q(s,a) - V(s), which tells us: "was this action better or worse than average?"

Actor-Critic Data Flow

Architecture
# Shared backbone (or separate networks)
State s → [Encoder] → features [256]
                              ↓              ↓
                    Actor head            Critic head
                   Dense(256) → [|A|]   Dense(256) → [1]
                   softmax → π(a|s)    linear → V(s)

# Actor loss: -log π(a|s) × advantage
# Critic loss: (r + γ V(s') - V(s))²
# Both trained jointly with a single optimizer

The advantage A(s,a) = r + γ V(s') − V(s) is the TD error from Chapter 3. Positive advantage means "this action was better than expected" — increase its probability. Negative means "worse than expected" — decrease it. The critic provides this signal, replacing the high-variance full return G_t from REINFORCE.

Chapter 9: PPO — Proximal Policy Optimization

Actor-critic methods can be unstable: a bad gradient step can ruin the policy, and you can't undo it. PPO (Schulman et al., 2017) solves this with a brilliantly simple idea: clip the policy update so it can't change too much in one step.

PPO computes the probability ratio r(θ) = π_new(a|s) / π_old(a|s). If the new policy is too different from the old one (ratio far from 1), the objective is clipped, preventing the update from going further.

PPO Training Loop, Concretely

Python
# PPO collects a batch of trajectories, then does multiple
# gradient steps on the SAME data (unlike REINFORCE which
# uses data once and throws it away)

for iteration in range(1000):
    # 1. Collect 2048 steps across 8 parallel environments
    batch = collect_rollouts(envs, policy, n_steps=2048)
    # batch contains: states, actions, rewards, log_probs_old, values

    # 2. Compute advantages using GAE (Generalized Advantage Estimation)
    advantages = compute_gae(batch, gamma=0.99, lam=0.95)

    # 3. Multiple epochs on the same batch (the key PPO trick)
    for epoch in range(4):
        for mini_batch in split(batch, size=64):
            ratio = exp(log_prob_new - log_prob_old)
            clipped = clip(ratio, 1-0.2, 1+0.2)
            loss = -min(ratio * adv, clipped * adv)
            optimizer.step(loss)

Chapter 10: SAC — Soft Actor-Critic

What if the agent was rewarded not just for getting high returns, but also for being as random as possible? That's the idea behind maximum entropy RL. The SAC objective adds an entropy bonus to the reward: explore as much as you can while still maximizing return.

The temperature parameter α controls the trade-off. High α means "explore aggressively" (policy stays broad). Low α means "focus on reward" (policy becomes peaked). SAC can even learn α automatically.

Chapter 11: The RL Landscape

You now know the major families of RL algorithms. But when should you use which? The landscape splits along several axes: model-free vs model-based, on-policy vs off-policy, value-based vs policy-based.

Sample Efficiency: The Practical Divide

The algorithms in this lesson vary by orders of magnitude in how much experience they need:

Off-policy methods (DQN, SAC) reuse data from the replay buffer, so they need fewer environment interactions. On-policy methods (PPO) throw away data after each update, but their gradients are less biased. Model-based methods are the most sample-efficient because they can "imagine" experience — but building an accurate world model is itself a hard problem.