Reinforcement Learning

The Reinforcement Learning Framework

Reinforcement Learning (RL) trains an agent to make sequential decisions by interacting with an environment to maximize cumulative reward.

Unlike supervised learning, there are no labeled $(X, y)$ pairs — the agent must discover good behavior through trial and error.

Core Components

Component	Description
Agent	The learner and decision maker
Environment	Everything the agent interacts with
State $s$	Current observation of the environment
Action $a$	What the agent can do
Reward $r$	Scalar feedback signal from environment
**Policy $\pi(a	s)$**

The Agent-Environment Loop

Agent observes state s_t
→ Agent selects action a_t using policy π
→ Environment transitions to s_{t+1}
→ Environment emits reward r_t
→ Agent updates policy based on (s_t, a_t, r_t, s_{t+1})
→ Repeat

Markov Decision Processes (MDPs)

The formal framework for RL problems is the MDP, defined by the tuple $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$:

• $\mathcal{S}$: state space
• $\mathcal{A}$: action space
• $P(s'|s, a)$: transition probability
• $R(s, a)$: expected reward
• $\gamma \in [0,1)$: discount factor (how much to value future rewards)

Return and Value Functions

The discounted return from timestep $t$: $G_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + ... = \sum_{k=0}^{\infty} \gamma^k r_{t+k}$

State-value function $V^\pi(s)$: expected return from state $s$ under policy $\pi$

Action-value function $Q^\pi(s, a)$: expected return from taking action $a$ in state $s$ then following $\pi$

The Bellman Equation

$V^\pi(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a)\left[R(s,a) + \gamma V^\pi(s')\right]$

Value-Based Methods

Value-based methods learn the value function and derive a policy from it (usually greedy: $\pi(s) = \arg\max_a Q(s,a)$).

Q-Learning (Tabular)

A model-free, off-policy algorithm that updates a Q-table:

$Q(s, a) \leftarrow Q(s, a) + \alpha \left[r + \gamma \max_{a'} Q(s', a') - Q(s, a)\right]$

The bracketed term is the TD error (Temporal Difference error).

Deep Q-Network (DQN)

When the state space is too large for a table (e.g., images), approximate $Q(s,a)$ with a neural network:

• Experience Replay: store $(s, a, r, s')$ tuples in a buffer; sample random mini-batches to break correlations
• Target Network: use a slowly-updated copy of the Q-network as the target to stabilize training
• ε-greedy: explore with probability ε, exploit with probability 1-ε

DQN beat human performance on 49 Atari games (DeepMind, 2015).

Policy-Based Methods

Policy-based methods directly optimize the policy $\pi_\theta(a|s)$ parameterized by $\theta$.

REINFORCE (Monte Carlo Policy Gradient)

$\nabla_\theta J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta}\left[\sum_t G_t \nabla_\theta \log \pi_\theta(a_t|s_t)\right]$

• High variance (needs many episodes to estimate gradient)
• Subtract a baseline $b(s)$ (usually $V(s)$) to reduce variance: Actor-Critic

Proximal Policy Optimization (PPO)

The most widely used modern RL algorithm:

• Clips the policy update to stay close to the old policy (prevents destructive updates)
• Used to train ChatGPT/Claude (RLHF stage) and game-playing agents
• Stable, sample-efficient, easy to implement

$\mathcal{L}^{CLIP} = \mathbb{E}_t\left[\min\left(r_t(\theta) \hat{A}_t,\ \text{clip}(r_t(\theta), 1-\epsilon, 1+\epsilon)\hat{A}_t\right)\right]$

where $r_t(\theta) = \frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_{old}}(a_t|s_t)}$ is the probability ratio.

Algorithm Comparison

Algorithm	Type	On/Off Policy	Key Strength
Q-Learning	Value-based	Off-policy	Simple, guaranteed convergence (tabular)
DQN	Value-based	Off-policy	Handles image/continuous state spaces
REINFORCE	Policy-based	On-policy	Direct policy optimization
Actor-Critic (A2C/A3C)	Both	On-policy	Lower variance than REINFORCE
PPO	Policy-based	On-policy	Stable, state-of-the-art general purpose
SAC	Both	Off-policy	Best for continuous action spaces
TD3	Value-based	Off-policy	Stable continuous control

When to Use RL

• Sequential decision making over many steps
• No labeled training data but can define a reward signal
• Game playing, robotics, recommendation systems, RLHF
• Don't use RL when supervised learning can solve it — RL is data-hungry and complex

import numpy as np

# Simple 4x4 grid: 0=empty, -1=wall, +10=goal, -10=pit
# State: (row, col), Actions: 0=up, 1=right, 2=down, 3=left

class GridWorld:
    def __init__(self, size=4):
        self.size = size
        self.goal = (3, 3)
        self.pit = (1, 3)
        self.reset()

    def reset(self):
        self.pos = (0, 0)
        return self.pos

    def step(self, action):
        moves = [(-1,0),(0,1),(1,0),(0,-1)]
        dr, dc = moves[action]
        r, c = self.pos
        new_r = max(0, min(self.size-1, r + dr))
        new_c = max(0, min(self.size-1, c + dc))
        self.pos = (new_r, new_c)

        if self.pos == self.goal:
            return self.pos, +10.0, True
        elif self.pos == self.pit:
            return self.pos, -10.0, True
        else:
            return self.pos, -0.1, False

# Q-Learning
env = GridWorld()
Q = np.zeros((4, 4, 4))   # Q[row, col, action]
alpha, gamma, epsilon = 0.1, 0.9, 0.3

for episode in range(5000):
    s = env.reset()
    for _ in range(50):
        r, c = s
        # ε-greedy action selection
        if np.random.random() < epsilon:
            a = np.random.randint(4)
        else:
            a = np.argmax(Q[r, c])

        s_next, reward, done = env.step(a)
        r2, c2 = s_next

        # TD update
        td_target = reward + gamma * np.max(Q[r2, c2]) * (not done)
        Q[r, c, a] += alpha * (td_target - Q[r, c, a])

        s = s_next
        if done:
            break

# Evaluate learned policy
s = env.reset()
path = [s]
for _ in range(20):
    r, c = s
    a = np.argmax(Q[r, c])
    s, reward, done = env.step(a)
    path.append(s)
    if done:
        break

print("Optimal path:", path)
print("Reached goal:", path[-1] == (3, 3))

Summary

• RL is about agents learning to maximize cumulative reward through interaction
• MDPs formalize the environment; the Bellman equation expresses value recursively
• Q-Learning / DQN: learn value functions, derive greedy policy
• REINFORCE / PPO: directly optimize the policy — PPO is the current industry standard
• RL is powerful but data-hungry — supervised learning is preferable when you have labeled data

Next: Semi-Supervised & Self-Supervised Learning — getting more from less labeled data.