Chapter 3 Introduction to Reinforcement Learning

Reinforcement Learning (RL) is a paradigm where an agent learns to make sequential decisions by interacting with an environment, receiving rewards as feedback, and optimizing its policy to maximize cumulative reward over time [346]. Unlike supervised learning (which requires labeled input-output pairs), RL discovers optimal behavior through trial and error.

The Markov Decision Process (MDP)

An MDP is a 5-tuple $(S,A,P,R,\gamma )$:

• $S$: State space — all possible configurations of the environment
• $A$: Action space — all actions available to the agent
• $P(s^{\prime }|s,a)$: Transition function — probability of reaching state $s^{\prime }$ from state $s$ after taking action $a$
• $R(s,a,s^{\prime })$: Reward function — immediate scalar feedback for a transition
• $\gamma \in [0,1]$: Discount factor — how much future rewards are valued relative to immediate ones

The Markov Property: The future depends only on the current state, not the history:

This makes the problem tractable.

Core Concepts and Definitions

Policy$\pi (a|s)$: A mapping from states to action probabilities. Deterministic: $a=\pi (s)$. Stochastic: $a\sim \pi (\cdot |s)$.

Return (cumulative discounted reward):

Value Function (expected return from state $s$ under policy $\pi$):

Action-Value Function (expected return from state $s$, taking action $a$, then following $\pi$):

Advantage Function (how much better action $a$ is compared to average):

Bellman Equations (recursive relationship):

Taxonomy of RL Methods

Reinforcement learning algorithms can be classified along several axes. Understanding this taxonomy helps select the right approach for a given problem.

Temporal Difference (TD) Learning

TD learning [347] bootstraps — it updates value estimates using other value estimates, without waiting for the full episode to end.

Understanding TD Error: “Surprise” as a Learning Signal

TD error measures the discrepancy between an agent’s current estimate of future reward and a newly updated estimate after taking one step. Put simply, it is the difference between what the agent thought would happen and what actually happened plus what it expects next. It represents the agent’s “surprise.”

The TD Error Formula

• $R_{t+1}$: The immediate reward received after taking an action.
• $\gamma V(S_{t+1})$: The estimated discounted value of the next state (what the agent expects to get from the next state onward, scaled by discount factor $\gamma$).
• $V(S_t)$: The original estimate of the current state’s value.

The combined term $(R_{t+1}+\gamma V(S_{t+1}))$ is called the TD Target. Therefore:

How the Agent Uses TD Error

The agent adjusts its value function to drive TD error toward zero:

• If ${\delta }_t>0$: outcome was better than predicted $\to$ increase $V(S_t)$ so the agent seeks this state.
• If : outcome was worse than predicted $\to$ decrease $V(S_t)$ so the agent avoids this state.
• If ${\delta }_t=0$: prediction was perfect $\to$ no update needed (convergence).

TD Target: $y_t=r_t+\gamma V(s_{t+1})$ — the “better estimate” we move toward.

Multi-step TD (n-step returns):

Q-Learning

Q-Learning [373] is the foundational off-policy, value-based algorithm. It learns the optimal $Q^{\ast }$ directly, regardless of the policy being followed.

Update rule:

SARSA[311] (on-policy alternative): Uses the action actually taken instead of the max:

Deep Q-Networks (DQN)[259]: Replace tabular $Q(s,a)$ with a neural network $Q_{\theta }(s,a)$. Key innovations: experience replay buffer (off-policy data reuse), target network (stability), $ϵ$-greedy exploration.

DQN Loss Function: The network is trained to minimize the mean squared TD error over mini-batches sampled from the replay buffer:

where $Q_{\overline{\theta }}$ is the target network — a frozen copy of $Q_{\theta }$ updated only every $C$ steps (e.g., $C=\mathrm{10,000}$). This prevents the moving target problem: without it, both the prediction and the target shift simultaneously, causing divergence.

Gradient update: Taking the gradient of the loss w.r.t. $\theta$ (note: the target $y$ is treated as a constant — no gradient flows through $\overline{\theta }$):

Learning scheme (per training step):

1. Act: Select action via $ϵ$-greedy: with probability $ϵ$ take random action, otherwise $a=\arg {\max }_a{Q}_{\theta }(s,a)$. Anneal $ϵ$ from 1.0 $\to$ 0.01 over first 1M steps.
2. Store: Save transition $(s,a,r,s^{\prime },d)$ in replay buffer $ℬ$ (capacity $\sim$1M).
3. Sample: Draw mini-batch of 32 transitions uniformly from $ℬ$.
4. Compute target: $y=r+\gamma (1-d){\max }_{a^{\prime }}{Q}_{\overline{\theta }}(s^{\prime },a^{\prime })$ (zero future value if terminal).
5. Update: Gradient descent on ${(y-Q_{\theta }(s,a))}^2$. Clip gradients to $[-1,1]$ (Huber loss variant).
6. Sync target: Every $C$ steps, copy $\overline{\theta }\leftarrow \theta$.

Understanding Replay Buffers

A replay buffer[220] (experience replay) is a data storage mechanism that saves past experiences so an agent can relearn from them later. Instead of discarding data immediately after an action, the agent stores transitions in a memory bank and samples random mini-batches for training.

What’s stored: Each transition is a tuple:

where $d_t$ is a boolean flag indicating if the episode ended.

import random
from collections import deque
 
class ReplayBuffer:
    def __init__(self, capacity):
        self.buffer = deque(maxlen=capacity)  # Bounded queue
 
    def push(self, state, action, reward, next_state, done):
        self.buffer.append((state, action, reward, next_state, done))
 
    def sample(self, batch_size):
        # Break correlation by selecting random experiences
        return random.sample(self.buffer, batch_size)
 
    def __len__(self):
        return len(self.buffer)

Policy Gradient Methods — REINFORCE

Instead of learning a value function and deriving a policy, directly optimize the policy parameters $\theta$ to maximize expected return [379].

Objective: $J(\theta )={𝔼}_{\tau \sim {\pi }_{\theta }}[R(\tau )]={𝔼}_{{\pi }_{\theta }}\left[{\sum }_{t=0}^T{r}_t\right]$

Policy Gradient Theorem:

REINFORCE Algorithm[379] (Williams, 1992):

1. Sample complete trajectory $\tau =(s_0,a_0,r_0,s_1,a_1,r_1,\mathrm{\dots })$ under ${\pi }_{\theta }$
2. Compute return $G_t={\sum }_{k=0}^{T-t}{\gamma }^k{r}_{t+k}$ for each time step
3. Update: $\theta \leftarrow \theta +\alpha {\sum }_t{\nabla }_{\theta }\log {\pi }_{\theta }(a_t|s_t)\cdot G_t$

Variance Reduction with Baseline:

Any baseline $b(s_t)$ that doesn’t depend on $a_t$ keeps the gradient unbiased but reduces variance. Best choice: $b(s_t)=V^{\pi }(s_t)$. Then $G_t-V(s_t)\approx A^{\pi }(s_t,a_t)$ = advantage.

Actor-Critic Methods

Combine policy gradient (actor) with learned value function (critic) to reduce variance while maintaining the flexibility of policy optimization.

Architecture:

• Actor${\pi }_{\theta }(a|s)$: The policy. Proposes actions.
• Critic$V_{\varphi }(s)$ or $Q_{\varphi }(s,a)$: Evaluates how good a state/action is. Provides low-variance baseline.

Actor update (using advantage from critic):

Critic update (minimize TD error):

Generalized Advantage Estimation (GAE)

Motivation: The Actor-Critic framework needs a good estimate of the advantage $A(s,a)=Q(s,a)-V(s)$ — how much better was this action than average? But there’s a fundamental tension:

• 1-step TD advantage ($r_t+\gamma V(s_{t+1})-V(s_t)$): Low variance (only one random step), but biased — if the value function $V$ is wrong, the advantage estimate is systematically off.
• Monte Carlo advantage ($G_t-V(s_t)$): Unbiased (uses actual returns), but high variance — the sum of many random rewards fluctuates wildly between episodes.

GAE [318] (Schulman et al., 2016) provides a smooth interpolation between these extremes via a single parameter $\lambda \in [0,1]$. It takes an exponentially-weighted average of $n$-step advantage estimates for all $n$, giving a principled way to trade bias for variance.

Core idea: Compute the 1-step TD error ${\delta }_t$ at each timestep, then blend them with exponentially decaying weights ${(\gamma \lambda )}^l$ — recent TD errors get full weight, distant ones are down-weighted:

Intuitive Mapping of Bias and Variance in GAE

In supervised learning, bias and variance stem from structural model assumptions. In reinforcement learning via GAE, they stem from how much you trust a flawed model versus how much you trust a chaotic environment:

• Bias (Systemic Misalignment): Arises when the estimator relies on the structural assumptions and imperfect predictions of the value network $V_{\theta }$. If $\theta$ is under-trained or lacks capacity, the baseline guesses are systematically wrong.
• Variance (Sample Jitteriness): Arises when the estimator relies on long, unconstrained environmental trajectories. Stochastic transitions, random seeds, and policy execution noise accumulate over long horizons, causing empirical sample rewards to swing wildly between rollouts.

The Architectural Spectrum: Boundary Analysis

The hyperparameter $\lambda$ serves as a slide-rule between two fundamental estimation paradigms.

The Trade-off Matrix

By selecting $\lambda \in [0.95,0.99]$, GAE minimizes the total mean squared error of the advantage estimate:

Diagnostics for Tuning λ\lambda

Monitoring training curves yields direct insight into whether bias or variance dominates:

1. High Variance Indicators: Policy entropy drops precipitously while explained variance of the value function becomes highly negative or erratic $\to$ policy updates are noisy. Remedy: Lower $\lambda$ to smooth target updates.
2. High Bias Indicators: Agent achieves early stable training but completely fails to discover complex delayed reward sequences $\to$ under-estimating long-horizon dependencies due to bootstrapping. Remedy: Raise $\lambda$ closer to $1.0$ to expose policy to real downstream trajectory signals.

On-Policy vs Off-Policy — Detailed Comparison

On-PolicyOff-PolicyData sourceCurrent policy ${\pi }_{\theta }$ onlyAny policy (replay buffer)After updateOld data is invalid, must regenerateOld data still usableSample efficiencyLow (data used once)High (data reused many times)StabilityMore stable (consistent distribution)Can diverge (distribution mismatch)ExamplesREINFORCE, PPO, A2C, GRPOQ-Learning, DQN, SAC, DPOFor LLMsPPO, GRPO (generate fresh each step)DPO (static preference dataset)

Model-Based vs Model-Free

Model-FreeModel-BasedWhat’s learnedPolicy $\pi$ and/or value $V$/$Q$ directlyEnvironment model $\widehat{P}(s^{\prime }|s,a)$PlanningNo planning, reactive decisionsCan simulate future trajectoriesSample efficiencyLow (must experience everything)High (can plan in imagination)AccuracyNo model biasModel errors compoundWhen to useComplex/unknown dynamicsSimple dynamics, need efficiencyExamplesPPO, DQN, SAC [129]MuZero [316], Dreamer [130], AlphaGo [331]

Reward Shaping

Reward shaping[265] is a technique where a developer modifies or supplements the environment’s original reward function. Its primary objective is to transform a sparse reward scenario — where the agent receives feedback only upon final task completion — into a dense reward scenario with intermediate feedback signals to accelerate convergence.

The Mathematical Framework

Let the original reward at time step $t$ be $R_t(s,a,s^{\prime })$. The reshaped reward adds an auxiliary shaping function $F$:

Potential-Based Reward Shaping (PBRS)

To mathematically guarantee that reshaping does not alter the optimal policy, use Potential-Based Reward Shaping. The shaping function $F$ is constrained to the difference in a scalar potential function $\mathrm{\Phi }$ across states:

where $\mathrm{\Phi }:𝒮\to ℝ$ is a real-valued potential function evaluating the desirable proximity of a state to the goal, and $\gamma$ is the discount factor.

The complete PBRS reward:

Theoretical Guarantees