Deep Policy Gradient Methods

The policy gradient theorem says that for a parameterized policy $\pi_\theta(a|s)$, the gradient of expected return $J(\theta)$ is

where $A^{\pi_\theta}(s,a) = Q^{\pi_\theta}(s,a) - V^{\pi_\theta}(s)$ is the advantage function. In classical actor-critic methods, a critic network estimates $A$ (or $V$) to reduce the variance of this Monte Carlo estimate, and the actor takes a gradient step $\theta \leftarrow \theta + \alpha \nabla_\theta J(\theta)$. The problem is that this update is defined in parameter space, but what actually matters is the induced change in the policy's action distribution. Neural network policies are highly nonlinear reparameterizations of the action distribution, so a small step in $\theta$-space can correspond to an enormous, discontinuous change in behavior — flipping which action is preferred in many states simultaneously. Because policy gradient estimates are themselves computed under the old policy's state distribution, a large behavioral jump invalidates the very data used to compute the gradient, and the next batch of experience can be catastrophically off-policy or simply useless. Unlike supervised learning, there is no fixed dataset to fall back on: a bad step changes the data-generating distribution itself, and can be irrecoverable. Deep policy gradient methods address this by introducing a trust region: an explicit or implicit constraint on the statistical distance between the old policy $\pi_{\theta_{\text{old}}}$ and the new policy $\pi_\theta$, typically measured by KL divergence. TRPO enforces this as a hard constraint solved via a constrained optimization (natural gradient plus line search). PPO approximates the same idea with a clipped objective function that can be optimized with ordinary stochastic gradient ascent, at the cost of only an approximate (rather than guaranteed) trust region. Both methods are built on top of an actor-critic architecture with a variance-reduced advantage estimator, most commonly Generalized Advantage Estimation (GAE), and both use importance sampling to reuse trajectories collected under an older policy for several gradient steps.

Step 1: Collect rollouts. Run the current policy $\pi_{\theta_{\text{old}}}$ in the environment for $T$ timesteps (or until episode end) across possibly many parallel workers, storing states, actions, rewards, and the action log-probabilities under the old policy.

Step 2: Estimate advantages. Use the critic $V_\phi$ and GAE to compute advantage estimates $\hat{A}_t$ with the recursion

Here $\gamma$ is the discount factor and $\lambda \in [0,1]$ trades bias for variance: $\lambda=0$ gives the low-variance, high-bias one-step TD advantage; $\lambda=1$ gives the high-variance, unbiased Monte Carlo advantage.

Step 3: Form the surrogate objective. Define the probability ratio

TRPO maximizes $\mathbb{E}_t[r_t(\theta)\hat{A}_t]$ subject to $\mathbb{E}_t[\mathrm{KL}(\pi_{\theta_{\text{old}}}\|\pi_\theta)] \le \delta$. PPO instead maximizes the clipped surrogate

The clip removes the incentive to push $r_t(\theta)$ far from 1 once it has already moved past $1\pm\epsilon$ in the direction favored by the sign of $\hat{A}_t$.

Step 4: Update. TRPO computes the natural-gradient direction via conjugate gradient on the Fisher-information matrix, then does a backtracking line search to satisfy the KL constraint exactly. PPO simply runs several epochs of minibatch SGD/Adam directly on $L^{\text{CLIP}}$ minus a value-function loss plus an entropy bonus.

Step 5: Repeat, using the newly updated policy to collect the next batch of rollouts. ``` Algorithm: PPO (Clipped Surrogate, Actor-Critic) Input: initial policy parameters θ, value parameters φ, clip range ε, discount γ, GAE parameter λ, rollout length T, epochs K, minibatch size M repeat until convergence:

# 1. Collect experience run policy π_θ_old = π_θ for T timesteps (possibly N parallel actors) store (s_t, a_t, r_t, log π_θ(a_t|s_t)) for each step

# 2. Compute advantages and returns via GAE for each trajectory (backward pass): δ_t = r_t + γ V_φ(s_{t+1}) - V_φ(s_t) A_hat_t = δ_t + γλ * A_hat_{t+1} # recursive, A_hat after terminal = 0 R_hat_t = A_hat_t + V_φ(s_t) # target return for critic normalize A_hat over the batch (mean 0, std 1) # variance reduction, common in practice θ_old ← θ # freeze old policy for ratio computation

# 3. Multiple epochs of minibatch updates on the SAME data for epoch = 1 to K: shuffle the T(N) collected steps into minibatches of size M for each minibatch: r(θ) = exp( log π_θ(a|s) - log π_θ_old(a|s) ) # importance ratio L_clip = mean( min( r(θ)A_hat, clip(r(θ), 1-ε, 1+ε) A_hat ) ) L_value = mean( (V_φ(s) - R_hat)^2 ) L_entropy = mean( entropy(π_θ(·|s)) ) loss = -L_clip + c1 L_value - c2 L_entropy θ, φ ← Adam_step(θ, φ; ∇loss) return θ, φ ``` ``` Algorithm: TRPO (single update) Input: θ_old, rollouts, advantage estimates A_hat, KL budget δ g ← ∇_θ [ E_t( r_t(θ) A_hat_t ) ] evaluated at θ = θ_old # surrogate gradient F ← Fisher information matrix of π_θ at θ_old # implicit, via Hessian-vector products x ← ConjugateGradient(F, g) # solves F x = g approximately, avoiding explicit F^{-1} step_size ← sqrt( 2δ / (x^T F x) ) Δθ ← step_size x for k = 0, 1, 2, ... (backtracking line search): θ_candidate = θ_old + (0.5^k) * Δθ if surrogate improves AND mean KL(π_θ_old || π_candidate) ≤ δ: θ_old ← θ_candidate break ```

Time complexity per iteration. Let $T$ be the rollout length per actor, $N$ the number of parallel actors, and $d$ the number of network parameters. Rollout collection costs $O(NT)$ environment steps and $O(NTd)$ forward-pass compute. For PPO, each of the $K$ epochs performs one backward pass over all $NT$ samples in minibatches, giving $O(K \cdot NT \cdot d)$ compute — essentially the cost of $K$ epochs of ordinary supervised learning, since the clipped objective and GAE recursion add only $O(NT)$ overhead (linear scans and elementwise operations). For TRPO, computing the natural gradient direction requires conjugate gradient, which itself needs $O(m)$ Hessian-vector products (each an $O(NTd)$ forward-backward pass through the network) where $m$ is the number of CG iterations (typically $10$–$20$, independent of $d$); the line search adds a small constant number of extra forward passes to re-evaluate the surrogate and KL. So TRPO costs roughly $O(m \cdot NTd)$ per update — more expensive than PPO by the CG-iteration factor $m$, but still linear in the number of parameters since Hessian-vector products are computed implicitly via automatic differentiation (never materializing the $d\times d$ Fisher matrix).

Space complexity. Both methods store the rollout buffer, $O(NT \cdot (\dim s + \dim a))$, plus the usual $O(d)$ for network weights and optimizer state. TRPO's conjugate gradient needs only a handful of length-$d$ vectors, so it avoids the $O(d^2)$ cost of forming the Fisher matrix explicitly — this implicit Hessian-vector-product trick is what makes natural-gradient methods usable at neural-network scale at all.

Correctness argument — why the trust region works. The theoretical backbone is the policy improvement bound. For any two policies $\pi$ and $\pi'$, define the surrogate advantage

A classical result (used to derive TRPO) shows

for a constant $C$ depending on the reward range and discount factor. The right-hand side is a lower bound on the true improvement in expected return that only depends on quantities computable from data generated by the old policy $\pi$: the surrogate $L_\pi(\pi')$ can be estimated by importance sampling, and the KL term measures the policy's own drift. Maximizing this lower bound with respect to $\pi'$, subject to keeping the KL term small, guarantees $J(\pi') \ge J(\pi)$ — i.e. monotonic improvement — as long as the bound is tight enough that maximizing it does not decrease the true objective. TRPO approximates this by replacing the max-KL penalty with an average-KL constraint (empirically similar and far easier to optimize), turning the update into a constrained quadratic program solved via natural gradient. PPO's clipped objective is a first-order, unconstrained relaxation of the same idea. When $\hat{A}_t > 0$ (action was better than average), the clip caps the objective's gradient once $r_t(\theta) > 1+\epsilon$, removing the incentive to increase the action's probability further — preventing runaway divergence from $\pi_{\theta_{\text{old}}}$ in that direction. Symmetrically for $\hat{A}_t < 0$. This does not provide a formal monotonic-improvement guarantee (there is no bound analogous to TRPO's), but empirically it behaves as an effective trust region: because the pessimistic $\min$ takes the lower of the clipped and unclipped terms, the objective never rewards moving $r_t(\theta)$ further past the clip boundary, only tolerates it, so gradient ascent naturally settles near the boundary rather than blowing past it.

Honest tradeoffs. TRPO's guarantee is real but relies on the KL bound being accurate (it is a first/second-order approximation itself) and the conjugate-gradient solve is fiddly to implement correctly, sensitive to damping coefficients, and expensive per step. PPO trades away the formal guarantee for simplicity, GPU-friendliness, and compatibility with standard deep learning stacks; in practice it matches or exceeds TRPO's sample efficiency on most benchmarks, but it can still suffer instability if the clip range $\epsilon$ is mistuned, if minibatches are reused too many epochs (letting $r_t(\theta)$ drift far outside the clip zone before the objective can react), or if the advantage estimates are poorly normalized.

Consider one PPO update step on a toy bandit-like state with a single state $s$ and two discrete actions, $a_1, a_2$. Suppose $\pi_{\theta_{\text{old}}}(a_1|s) = 0.5$, $\pi_{\theta_{\text{old}}}(a_2|s)=0.5$, clip range $\epsilon=0.2$, and we observe action $a_1$ was taken with advantage estimate $\hat{A}=+2.0$ (a good action), while a separate sample of action $a_2$ had $\hat{A}=-1.5$ (a bad action).

Reading the table: for the good action ($a_1$, positive advantage), the policy tried to push the probability far above the old value ($0.5 \to 0.9$, ratio $1.8$), but the objective clips the reward for doing so at ratio $1.2$ — the gradient of $L^{\text{CLIP}}$ with respect to $\theta$ becomes zero once $r>1.2$, so further increases stop being reinforced. For the bad action ($a_2$, negative advantage), the policy correctly decreased its probability, but the $\min$ picks the more negative (unclipped) term $-0.3$ only when it is smaller — here $-1.2 < -0.3$ so the min picks $-1.2$, meaning the clipped, more pessimistic value is used, which still penalizes overshooting far past the trust region in the direction of decreasing $a_2$'s probability. This asymmetric pessimism (always take the worse of the two candidate objectives) is exactly what prevents a single minibatch of updates from driving the policy arbitrarily far from $\pi_{\theta_{\text{old}}}$, no matter how extreme the raw advantage estimate. Compare to what an unclipped surrogate ($r(\theta)\hat A$ alone) would do: it keeps rewarding ratio $1.8$ fully at value $3.6$, giving unlimited incentive to keep increasing $\pi_\theta(a_1|s)$ toward $1$ every epoch the minibatch is replayed — precisely the runaway behavior that destabilizes vanilla policy gradient with importance-weighted reuse of old data.

Deep policy gradient methods underlie some of the most visible successes of modern reinforcement learning. OpenAI Five, which learned to play the multiplayer game Dota 2 at a professional level, was trained with a large-scale distributed version of PPO. Robotics research groups use PPO and TRPO to train locomotion and manipulation policies, both in simulation and increasingly with sim-to-real transfer. In natural language processing, PPO is the workhorse optimizer inside reinforcement learning from human feedback (RLHF) pipelines that fine-tune large language models toward human preferences, treating the language model itself as the policy and a learned reward model as the environment's reward signal. Continuous-control benchmarking suites such as MuJoCo and physics-based simulators for autonomous driving research routinely use PPO as the default baseline algorithm because of its reliability and minimal hyperparameter sensitivity relative to earlier methods. The trust-region idea itself — constraining policy drift via KL divergence — recurs in later algorithms including Soft Actor-Critic, which folds entropy maximization directly into the objective, and informs methods used in Imitation and Inverse RL, where matching a policy's behavioral distribution to expert demonstrations raises exactly the same drift-control concerns that TRPO and PPO were built to solve.

Ask the tutor: How would you adapt the clipped PPO objective for continuous action spaces with a learned Gaussian policy, and what extra care does the log-probability ratio require there?