Deep Reinforcement Learning: MDPs, DQN, Policy Gradients, and PPO

A neural network can assign values to states it has never visited or choose actions from high-dimensional observations. That generalization makes reinforcement learning useful beyond small tables, but it also couples updates: changing a value at one input can change predictions elsewhere, including the targets used for learning. This article develops DQN, policy gradients, and PPO through small executable updates. These checks are building blocks, not a complete agent or an environment-performance benchmark.

The grid examples in Markov Decision Processes and Dynamic Programming introduce states, actions, rewards, discounting, Bellman backups, and offline coverage. We retain that setup here. In online RL, the policy influences the observations collected next; offline RL instead learns from an existing log. Supervised losses, optimizers, and validation remain useful, although dependence and distribution changes require care.

From a table to a shared value network

A Markov state summarizes the history needed for the next-state and reward distribution conditional on an action. Observations such as a single video frame may not supply such a state; stacked frames or memory can help represent missing history. A policy \(\pi(a\mid s)\) specifies action probabilities. Its discounted return is \(G_t=\sum_{k\geq0}\gamma^k r_{t+k+1}\), with \(0\leq\gamma<1\). Bounded rewards make this sum finite. The discount changes the return objective; it does not create a hard limit on what the network can learn.

For a fixed policy, \(Q^\pi(s,a)\) averages future actions under \(\pi\). The optimal action value obeys a different equation: \[Q^*(s,a)=\mathbb E\left[r+\gamma\max_{a’}Q^*(s’,a’)\mid s,a\right].\] The expectation is over the environment response, and the continuation is zero at termination. A DQN network takes a state representation and outputs one value per discrete action. Its greedy action maximizes that output vector.

A sampled transition supplies a target \(y=r+\gamma(1-\mathrm{terminated})\max_{a’}Q_{\theta^-}(s’,a’)\). The online parameters \(\theta\) are optimized to match \(y\), while target parameters \(\theta^-\) are held fixed for the update. Squared error is one option. The code uses Smooth L1 with threshold 1: quadratic near zero TD error and linear for large error. Both are regression losses for the selected action value.

A DQN update that actually runs

A replay buffer stores transitions and samples minibatches, reducing adjacency between consecutive observations and reusing experience. This does not make the underlying data independent, nor does every optimizer require i.i.d. observations. A target network slows movement of the regression target. Together these techniques can improve stability; they do not guarantee convergence of nonlinear off-policy learning.

The buffer below stores detached copies so later edits to observation tensors do not alter past transitions. Sampling converts the deque to a list, as required by current Python’s random.sample. The example uses a small CPU MLP without dropout or batch normalization, two optimizer steps, and a target copy after the second step. The four transitions are synthetic and are not evidence of a learned control policy.

import random
from collections import deque, namedtuple
from copy import deepcopy
import torch
from torch import nn
from torch.nn import functional as F

torch.manual_seed(0)
torch.set_num_threads(1)
Transition = namedtuple("Transition", "s a r s2 terminated")
class ReplayBuffer:
    def __init__(self, capacity=100000, seed=0):
        self.buf = deque(maxlen=capacity)
        self.rng = random.Random(seed)
    def push(self, s, a, r, s2, terminated):
        self.buf.append(Transition(s.detach().cpu().clone(), int(a), float(r),
                                   s2.detach().cpu().clone(), bool(terminated)))
    def sample(self, n):
        return Transition(*zip(*self.rng.sample(list(self.buf), n)))
    def __len__(self):
        return len(self.buf)

def dqn_loss(q_net, target_net, batch, gamma=0.99, double=False):
    param = next(q_net.parameters())
    s = torch.stack(batch.s).to(device=param.device, dtype=param.dtype)
    s2 = torch.stack(batch.s2).to(device=param.device, dtype=param.dtype)
    a = torch.as_tensor(batch.a, device=param.device, dtype=torch.long)
    r = torch.as_tensor(batch.r, device=param.device, dtype=param.dtype)
    terminated = torch.as_tensor(batch.terminated, device=param.device, dtype=torch.bool)
    q = q_net(s).gather(1, a[:, None]).squeeze(1)
    with torch.no_grad():
        target = r.clone()
        live = ~terminated
        if live.any():
            next_values = target_net(s2[live])
            if double:
                choice = q_net(s2[live]).argmax(dim=1, keepdim=True)
                continuation = next_values.gather(1, choice).squeeze(1)
            else:
                continuation = next_values.max(dim=1).values
            target[live] += gamma * continuation
    return F.smooth_l1_loss(q, target), target

q_net = nn.Sequential(nn.Linear(2,16), nn.ReLU(), nn.Linear(16,2))
target_net = deepcopy(q_net).requires_grad_(False).eval()
optimizer = torch.optim.Adam(q_net.parameters(), lr=1e-3)
replay = ReplayBuffer()
for i in range(4):
    replay.push(torch.tensor([i/3.,1.]), i%2, float(i-1),
                torch.tensor([(i+1)/3.,1.]), i==3)
for update in (1,2):
    batch = replay.sample(4)
    loss, targets = dqn_loss(q_net,target_net,batch,gamma=0.9)
    optimizer.zero_grad()
    loss.backward()
    optimizer.step()
    if update==2:
        target_net.load_state_dict(q_net.state_dict())
    print(f"update {update} loss {loss.item():.6f} targets {[round(v,4) for v in targets.tolist()]}")
print("target gradients absent", all(p.grad is None for p in target_net.parameters()))
print("target copied", all(torch.equal(a,b) for a,b in zip(q_net.parameters(),target_net.parameters())))
# update 1 loss 0.578839 targets [2.0, 0.3667, -0.6614, 1.3973]
# update 2 loss 0.576634 targets [2.0, 0.3667, 1.3973, -0.6614]
# target gradients absent True
# target copied True

The input batch is shaped (batch, 2), and the network produces (batch, 2) action values. gather selects the value of the action actually recorded. Actions use integer indices, and rewards and masks are placed on the online network’s device; the target network must be on that device too. Only nonterminal successor observations are evaluated for bootstrapping. A terminal row’s target is exactly its observed reward.

An external rollout time limit is different from termination of the task. At a time-limit truncation, bootstrap from the final observation before reset, not the reset observation. If the time limit is part of the task itself, reaching it is termination, and remaining time belongs in the state. Modern environment APIs expose terminated and truncated separately. This buffer keeps the termination flag needed by the one-step target; the collection loop must still handle both kinds of reset.

Stopping gradients through the target implements the semi-gradient DQN update. Differentiating through a bootstrap target changes the optimization method; it does not universally cause predictions to collapse. Target copies must actually occur during training, and minibatch collection must provide enough transitions before sampling. An end-to-end loop alternates environment interaction, storage, replay updates, scheduled target copies, and separate policy evaluation.

Maximizing noisy action estimates can introduce upward selection bias: for unbiased estimates, \(\mathbb E[\max_a\widehat Q_a]\geq\max_a\mathbb E[\widehat Q_a]\). Neural estimates need not be unbiased, so this is not a guarantee that every DQN prediction is too high. Double DQN uses the online network to select \(a^*=\arg\max_a Q_\theta(s’,a)\) and the target network to evaluate \(Q_{\theta^-}(s’,a^*)\). The double option implements that separation; it can reduce overestimation without eliminating all bias.

Exploration changes which evidence is available

In \(\varepsilon\)-greedy exploration, a random action is selected with probability \(\varepsilon\); otherwise the current maximizing action is selected. A schedule can reduce that probability as learning proceeds, but an endpoint such as 0.05 is not a universal default. Random actions can also select the greedy action. Greedy behavior may miss useful alternatives, although stochastic transitions, initial values, or random starting states can expose alternatives even without explicit random actions.

Explore with the task’s risks and data budget in mind, and evaluate the deployed action rule separately from exploratory behavior. Across training runs, differences can come from initialization, exploration, environment randomness, and optimization. Report the number of seeds, the distribution of evaluation returns, and the interaction budget. A few seeds are useful evidence, but no fixed seed count guarantees a precise algorithm comparison.

A policy gradient has an expected-return objective

For a finite set of actions, enumerating a Q-network’s outputs is easy. Maximizing over continuous actions is harder, so continuous-control methods often learn an actor alongside a critic. This does not make value learning exclusive to discrete actions. A policy network can output categorical logits for discrete actions or parameters of a continuous distribution, with any action transformation accounted for in its log probability.

For a fixed initial-state distribution and finite episode length \(T\), define \(J(\theta)=\mathbb E_{\tau\sim\pi_\theta}[\sum_{t=0}^{T-1}\gamma^t r_{t+1}]\). With environment dynamics independent of \(\theta\), the likelihood-ratio identity gives \[\nabla_\theta J=\mathbb E\left[\sum_{t=0}^{T-1}\gamma^t\nabla_\theta\log\pi_\theta(a_t\mid s_t)G_t\right],\quad G_t=\sum_{k=t}^{T-1}\gamma^{k-t}r_{k+1}.\] The outer \(\gamma^t\) matches this discounted start-state objective. Other conventions use discounted state sampling or an undiscounted episodic objective and must state their convention.

REINFORCE replaces that expectation with sampled trajectories. Its loss uses negative log probabilities weighted by observed returns, so gradient descent performs a sampled ascent step on expected return. The policy-dependent data distribution is already accounted for by the log-probability identity. The scalar loss on one frozen batch is a surrogate for the update; its value is not a direct measure of policy quality, and optimizing stale samples indefinitely is not the same as following the current on-policy gradient.

A fixed, action-independent baseline \(b(s)\) has zero expected score contribution because \(\mathbb E_{a\sim\pi}[\nabla\log\pi(a\mid s)b(s)]=b(s)\nabla\sum_a\pi(a\mid s)=0\). A suitable baseline can reduce variance; an arbitrary poor one need not. The true advantage is \(A^\pi=Q^\pi-V^\pi\); \(G_t-V_\phi(s_t)\) is a noisy estimate using a learned baseline. Positive estimated advantage increases the sampled action’s probability locally, and negative advantage decreases it, subject to shared-parameter effects.

An actor and critic update on a two-step episode

An actor chooses actions; a critic estimates their future consequences. They can use separate networks or share an encoder. The following tiny environment has two known states in sequence, regardless of action. Choosing action 0 earns 1 in the first state; choosing action 1 earns 2 in the second. The example samples one episode, computes reward-to-go backward, and performs one joint update. The illustrated episode earns rewards 1 and 2, giving returns 2.8 and 2 at discount 0.9.

import torch
from torch import nn
from torch.nn import functional as F
from torch.distributions import Categorical

torch.manual_seed(2)
actor = nn.Sequential(nn.Linear(2,8), nn.Tanh(), nn.Linear(8,2))
critic = nn.Sequential(nn.Linear(2,8), nn.Tanh(), nn.Linear(8,1))
optimizer_ac = torch.optim.SGD(list(actor.parameters())+list(critic.parameters()), lr=0.05)
states = torch.eye(2)
distribution = Categorical(logits=actor(states))
actions = distribution.sample()
rewards = (actions == torch.tensor([0,1])).float()*torch.tensor([1.,2.])
gamma = 0.9
returns = torch.empty(2)
acc = 0.0
for t in (1,0):
    acc = float(rewards[t])+gamma*acc
    returns[t] = acc
values = critic(states).squeeze(1)
advantages = (returns-values).detach()
weights = gamma**torch.arange(2,dtype=torch.float32)
actor_loss = -(weights*distribution.log_prob(actions)*advantages).sum()
critic_loss = F.mse_loss(values,returns.detach())
optimizer_ac.zero_grad()
(actor_loss+0.5*critic_loss).backward()
optimizer_ac.step()
print("actions",actions.tolist(),"rewards",rewards.tolist())
print("returns",[round(v,4) for v in returns.tolist()])
print(f"actor loss {actor_loss.item():.6f} critic loss {critic_loss.item():.6f}")
print("advantages detached",not advantages.requires_grad)
# actions [0, 1] rewards [1.0, 2.0]
# returns [2.8, 2.0]
# actor loss 3.644472 critic loss 7.857560
# advantages detached True

The actor loss treats the advantage as a constant weight; it must not train the critic through the actor term. The critic fits a detached return target. A single sampled episode can give a noisy update and does not establish improvement in expected return. This code uses full episodic returns. Bootstrapped actor-critic methods instead use value estimates before an episode has finished, trading variance against error in the critic.

A common one-step advantage estimate is the TD residual \(\delta_t=r_{t+1}+\gamma(1-\mathrm{terminated}_t)V_\phi(s_{t+1})-V_\phi(s_t)\). Generalized advantage estimation combines residuals along a contiguous rollout: \(\widehat A_t=\sum_l(\gamma\lambda)^l\delta_{t+l}\), truncated at the rollout boundary. The parameter \(\lambda\) controls how far residuals are propagated. At an external truncation, retain the bootstrap from the final observation but do not carry the advantage recursion into the reset episode. These masks serve different purposes.

PPO reuses a recent batch with a clipped surrogate

PPO first collects transitions under a snapshot \(\pi_{\mathrm{old}}\), storing actions, observations, old log probabilities, and value estimates. Advantages and value targets are computed for that rollout and treated as fixed while doing several minibatch epochs. For the same sampled action and state, the probability ratio is \(\rho_t(\theta)=\exp[\log\pi_\theta(a_t\mid s_t)-\log\pi_{\mathrm{old}}(a_t\mid s_t)]\). It adjusts action probabilities on the old data; it does not fully correct the state distribution after an arbitrarily large policy change.

The clipped actor surrogate is \[L^{\mathrm{clip}}=\mathbb E_{\mathrm{old}}\left[\min\left(\rho_t\widehat A_t,\operatorname{clip}(\rho_t,1-\epsilon,1+\epsilon)\widehat A_t\right)\right].\] It removes part of the incentive to keep moving an already-improved sampled action probability farther. Implementations minimize its negative, usually alongside a value loss and optionally an entropy term encouraging a broader action distribution. The code averages sampled transitions uniformly. Matching the earlier discounted start-state gradient would require its corresponding \(\gamma^t\) weighting; uniform rollout averaging is a different practical convention. Clipping is not a hard constraint on parameter movement or policy divergence.

import torch

def ppo_loss(logp, logp_old, advantages, eps=0.2):
    if logp.ndim!=1 or logp.shape!=logp_old.shape or logp.shape!=advantages.shape:
        raise ValueError("Use one scalar log probability and advantage per sampled transition")
    ratio = torch.exp(logp-logp_old.detach())
    advantage = advantages.detach()
    direct = ratio*advantage
    clipped = ratio.clamp(1-eps,1+eps)*advantage
    return -torch.minimum(direct,clipped).mean()

logp_old = torch.tensor([-0.7,-0.7,-0.7],requires_grad=True)
logp = torch.tensor([-0.2,-0.7,-1.6],requires_grad=True)
advantage = torch.ones(3,requires_grad=True)
loss_ppo = ppo_loss(logp,logp_old,advantage)
loss_ppo.backward()
print(f"actor surrogate loss {loss_ppo.item():.4f}")
print("current log-prob gradients",[round(v,4) for v in logp.grad.tolist()])
print("old log-prob and advantage gradients absent",logp_old.grad is None and advantage.grad is None)
# actor surrogate loss -0.8689
# current log-prob gradients [0.0, -0.3333, -0.1355]
# old log-prob and advantage gradients absent True

With positive advantage, the per-sample surrogate is \(A\min(\rho,1+\epsilon)\); its improving-direction slope vanishes above the upper boundary. With negative advantage, it is \(A\max(\rho,1-\epsilon)\); the slope vanishes below the lower boundary. The opposite direction still has a corrective slope. Exercise 3 checks both signs and distinguishes the nondifferentiable boundary from a flat region.

Other samples, shared parameters, momentum, or value and entropy losses can still move a probability whose own actor-surrogate term is flat. Clipping therefore does not ensure that all ratios stay in the interval or that KL divergence stays small. Monitor policy change and returns; practical implementations can stop batch reuse when an estimated KL threshold is exceeded. Learning rates, rollout length, value estimation, and update count remain consequential choices.

After those epochs, collect new data under the updated policy. This recent-rollout use differs from DQN’s reuse of older transitions. Recovering from a poor update may involve restoring a checkpoint or collecting different data; deterioration is not inherently irreversible. A reliable implementation verifies old-log-prob snapshots, action log probabilities, masks, and detached targets before interpreting a return curve.

What to measure beyond a training loss

Evaluate the intended deployed policy on separate episodes and report both the return objective and environment-step budget. Check episode length, termination versus truncation, task success, and original task reward when shaping is used. A lower TD loss or PPO surrogate loss need not imply higher return. Baselines, multiple training seeds, evaluation variation, and sensitivity to important settings help separate improvements from favorable runs.

Delayed rewards complicate credit assignment; replay distributions can differ from the current policy’s visitation; value errors can propagate through bootstrap targets. These are specific obstacles, not a reason to discard all supervised-learning intuition. Labeled demonstrations can support imitation or initialize an agent, while offline RL can use existing reward-bearing logs. The useful approach depends on available feedback, exploration cost, and whether sequential decisions materially affect outcomes.

Language-model preference training is one application. PPO-based RLHF uses a token-generating policy, prompts and generated sequences, a reward signal that may come from a learned preference model, and often a reference-policy penalty. A reward model supplies feedback; it does not replace every part of the interaction process. RLHF is not synonymous with PPO, and DPO is a particular preference-optimization alternative. The separate Fine-Tuning and Alignment article develops that setting.

Exercises

1. Discount weights are not a hard horizon. Compute the sum of discount weights and the weight on a reward at exponent 100. Distinguish objective choice from numerical difficulty.

for gamma in (0.9,0.99,0.999):
    print(f"gamma {gamma:.3f} weight sum {1/(1-gamma):.1f} weight at exponent 100 {gamma**100:.6f}")
# gamma 0.900 weight sum 10.0 weight at exponent 100 0.000027
# gamma 0.990 weight sum 100.0 weight at exponent 100 0.366032
# gamma 0.999 weight sum 1000.0 weight at exponent 100 0.904792

2. A two-state off-policy instability. Examine the expected update of a linear value function when the behavior and target policies visit states differently. Compare bootstrapped TD with regression to the known zero return.

import numpy as np

alpha, gamma = 0.1, 0.99
feature = np.array([1.,2.])
behavior = np.array([0.99/1.99,1/1.99])
td_direction = feature*(gamma*2-feature)
coefficient = behavior@td_direction
fixed_coefficient = -(behavior@(feature**2))
print(f"expected TD coefficient {coefficient:.6f} multiplier {1+alpha*coefficient:.6f}")
w = 1.0
for step in range(1,201):
    w *= 1+alpha*coefficient
    if step%50==0:
        print(f"step {step:3d} bootstrapped weight {w:.4e}")
w_fixed = (1+alpha*fixed_coefficient)**200
print(f"fixed-zero-target weight {w_fixed:.4e}")
# expected TD coefficient 0.467437 multiplier 1.046744
# step  50 bootstrapped weight 9.8179e+00
# step 100 bootstrapped weight 9.6391e+01
# step 150 bootstrapped weight 9.4636e+02
# step 200 bootstrapped weight 9.2912e+03
# fixed-zero-target weight 8.4123e-26

3. PPO slopes on both sides of the clipping interval. Compute the ascent surrogate and its derivative with respect to the probability ratio. Mark a kink where an ordinary derivative does not exist.

import torch

eps = 0.2
for advantage in (1.0,-1.0):
    print(f"advantage {advantage:+.0f}")
    for value in (0.5,0.8,1.0,1.2,1.5):
        ratio = torch.tensor(value,dtype=torch.float64,requires_grad=True)
        objective = torch.minimum(ratio*advantage,ratio.clamp(1-eps,1+eps)*advantage)
        kink = (advantage>0 and abs(value-(1+eps))<1e-12) or (advantage<0 and abs(value-(1-eps))<1e-12)
        if kink:
            slope = "kink"
        else:
            objective.backward()
            slope = f"{ratio.grad.item():+.1f}"
        print(f"  ratio {value:.1f} objective {objective.item():+.3f} derivative {slope}")
# advantage +1
#   ratio 0.5 objective +0.500 derivative +1.0
#   ratio 0.8 objective +0.800 derivative +1.0
#   ratio 1.0 objective +1.000 derivative +1.0
#   ratio 1.2 objective +1.200 derivative kink
#   ratio 1.5 objective +1.200 derivative +0.0
# advantage -1
#   ratio 0.5 objective -0.800 derivative +0.0
#   ratio 0.8 objective -0.800 derivative kink
#   ratio 1.0 objective -1.000 derivative -1.0
#   ratio 1.2 objective -1.200 derivative -1.0
#   ratio 1.5 objective -1.500 derivative -1.0

Further reading

The Double DQN paper investigates maximization bias. Gymnasium’s time-limit guide explains bootstrapping at truncation. The policy-gradient derivation in Spinning Up develops the likelihood-ratio and baseline identities, while the PPO paper describes rollout reuse and clipped optimization.