Back to Articles Reinforcement Learning • 24 min read

Reinforcement Learning: From Q-Learning to Deep RL

In 2016, AlphaGo defeated 18-time world champion Lee Sedol at Go — a game with more board configurations than atoms in the observable universe. In 2019, AlphaStar reached Grandmaster level at StarCraft II, beating 99.8% of human players. In 2022, the same principles that powered these game-playing agents were used to align ChatGPT with human values. The common thread? Reinforcement Learning.

---

1. Why RL Is Different

Supervised learning is like studying from solved textbook problems. Unsupervised learning is like exploring data without a guide. Reinforcement learning is like learning to ride a bike — you try things, fall down, try again, and gradually improve through trial and error. The key differences:

• No labeled data: The agent discovers correct behavior by interacting with the environment, not from pre-labeled examples.
• Delayed rewards: In chess, you only know if a move was good after the game ends. In supervised learning, feedback is immediate per example.
• Sequential decisions: Each action changes the state of the world, affecting future observations and future rewards.
• Exploration vs. Exploitation: The agent must balance trying new actions (exploration) with repeating actions known to be good (exploitation).

---

2. The Markov Decision Process (MDP)

The formal mathematical framework for RL is the Markov Decision Process. An MDP is defined by a 5-tuple (S, A, P, R, γ):

• S — State space: all possible configurations of the environment (e.g., every board position in chess).
• A — Action space: all actions the agent can take from any state (e.g., moving a piece).
• P(s'|s,a) — Transition probability: the probability of reaching state s' when taking action a in state s. In deterministic environments (chess), this is always 0 or 1.
• R(s,a,s') — Reward function: the immediate scalar reward received when transitioning from s to s' via action a.
• γ — Discount factor (0 ≤ γ ≤ 1): how much future rewards are valued relative to immediate rewards. γ = 0.99 makes the agent care significantly about future consequences; γ = 0 makes it myopic.

The "Markov" property states that the future is conditionally independent of the past given the present state. Knowing the current state is sufficient — you don't need the full history. This critical assumption makes the MDP mathematically tractable.

---

3. Value Functions

The central quantity in RL is the value function — a measure of "how good" it is to be in a given state (or to take a given action).

State Value Function V(s)

V(s) is the expected total discounted return an agent will receive starting from state s and following policy π thereafter:

Action Value Function Q(s,a)

Q(s,a) is the expected return starting from state s, taking action a first, then following policy π. Q-values allow the agent to compare actions: choose the action with the highest Q-value.

The Bellman Equation

The Bellman equation gives us a recursive relationship that unlocks practical computation of value functions:

Read: "The value of taking action a in state s equals the immediate reward plus the discounted value of the best action I can take from the resulting state s'." This recursive definition is the foundation of Q-learning.

---

4. Q-Learning: The Algorithm

Q-Learning is a model-free, off-policy algorithm that learns Q-values by iteratively applying the Bellman equation as a target for a running estimate:

The term in brackets is the TD error (temporal difference error): the gap between the current Q estimate and the target. Learning rate α controls how aggressively we update toward the new target.

import numpy as np

# Grid World: 4x4 grid, goal at (3,3), holes at (1,1) and (2,3)
# States: 0-15, Actions: 0=Up, 1=Down, 2=Left, 3=Right

class GridWorld:
    def __init__(self):
        self.n_states = 16
        self.n_actions = 4
        self.goal = 15
        self.holes = [5, 11]

    def step(self, state, action):
        row, col = state // 4, state % 4
        if action == 0 and row > 0: row -= 1   # Up
        elif action == 1 and row < 3: row += 1  # Down
        elif action == 2 and col > 0: col -= 1  # Left
        elif action == 3 and col < 3: col += 1  # Right
        next_state = row * 4 + col
        if next_state == self.goal: return next_state, 1.0, True
        if next_state in self.holes: return next_state, -1.0, True
        return next_state, -0.01, False  # Small step penalty

# Q-Learning
env = GridWorld()
Q = np.zeros((env.n_states, env.n_actions))
alpha, gamma, epsilon = 0.1, 0.99, 0.1
n_episodes = 5000

for ep in range(n_episodes):
    state = 0  # Start top-left
    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])
        next_state, reward, done = env.step(state, action)
        # Bellman update
        td_target = reward + gamma * np.max(Q[next_state]) * (not done)
        Q[state, action] += alpha * (td_target - Q[state, action])
        state = next_state

print("Learned Q-Table (action values per state):")
print(Q.reshape(4, 4, 4).round(2))
print("\nOptimal Policy (0=Up, 1=Down, 2=Left, 3=Right):")
print(np.argmax(Q, axis=1).reshape(4,4))
            

---

5. Exploration vs. Exploitation

A critical challenge in RL is that the agent must explore to discover good strategies, but must also exploit what it knows to earn rewards. Key strategies:

• ε-greedy: With probability ε, take a random action (explore); otherwise take the best known action (exploit). ε typically decays from 1.0 to 0.01 over training.
• Upper Confidence Bound (UCB): Selects actions with high uncertainty bonus: Q(s,a) + c√(log(t)/N(s,a)). Naturally balances exploration and exploitation — uncertain actions get a boost that decays as they are tried more.
• Thompson Sampling: Maintains a probability distribution over Q-values. At each step, sample from the distribution and choose the highest-sampled value. Theoretically optimal for many settings.

---

6. Deep Q-Networks (DQN): Atari from Pixels

Classic Q-learning uses a table — one entry per (state, action) pair. For complex environments (Atari games with millions of pixel-state combinations), this is impossible. Deep Q-Networks replace the Q-table with a deep neural network that approximates Q(s,a) from raw pixel inputs.

DeepMind's 2013 DQN paper introduced two critical innovations that make neural Q-learning stable:

1. Experience Replay: Store transitions (s, a, r, s') in a replay buffer. Sample random mini-batches to train on. This breaks temporal correlations that otherwise destabilize training.
2. Target Network: Maintain two copies of the network: the online network (updated every step) and the target network (updated every N steps). Use the target network to compute the Bellman target — this prevents the target from chasing itself and causing divergence.

With these innovations, a single DQN agent trained purely on 84×84 pixel frames achieved superhuman performance on 29 of 49 Atari games — with no game-specific engineering, just raw pixels and the score.

---

7. Policy Gradient Methods

Q-learning learns the value of actions. Policy gradient methods take a fundamentally different approach: directly optimize the parameters of the policy itself. The policy π_θ(a|s) is a neural network outputting action probabilities.

REINFORCE

The simplest policy gradient algorithm. Run an episode, collect the return G (total discounted reward), then update policy parameters to increase the probability of actions that led to high returns and decrease the probability of actions that led to low returns:

Proximal Policy Optimization (PPO)

PPO is the most widely used policy gradient algorithm in modern RL. It improves on earlier methods by constraining the policy update to a "trust region" — preventing updates so large that the policy collapses. PPO uses a clipped surrogate objective that effectively limits how much the policy changes per update. PPO is the algorithm used to train the ChatGPT and Claude reward models in the RLHF pipeline.

---

8. Famous RL Milestones

Year	Achievement	Significance
1992	TD-Gammon masters Backgammon	First superhuman RL agent for a complex board game
2013	DQN plays 49 Atari games	First RL agent to learn from raw pixels at superhuman level
2016	AlphaGo defeats Lee Sedol	Mastered Go — long considered impossible for AI
2019	AlphaStar reaches Grandmaster	Real-time strategy game with imperfect information
2021	AlphaFold2 solves protein folding	50-year biology grand challenge solved with RL+deep learning
2022	ChatGPT via RLHF	PPO used to align LLMs with human preferences

---

9. Real-World Applications Beyond Games

• Robotics: Boston Dynamics uses RL to teach Atlas to navigate uneven terrain. OpenAI trained a robot hand to solve a Rubik's cube using only simulation-trained RL policies transferred to physical hardware.
• Drug Discovery: RL agents design novel molecules by sequentially adding atoms and bonds, optimizing for predicted binding affinity and drug-like properties.
• Chip Design: Google used RL to design the floor plan of its TPU v5 chip — the agent places components on a grid to minimize wire length and congestion. The RL-designed chip outperformed human experts in days rather than months.
• Recommendation Systems: YouTube and TikTok use RL to optimize long-term user engagement rather than just immediate click-through rates — accounting for the long-term effects of recommendations on user retention.
• Autonomous Driving: Waymo uses RL to train driving policies in simulation before transferring to real vehicles, generating millions of driving miles per day in virtual environments.