Proximal Policy Optimization

Policy gradient methods optimize a parameterized policy $\pi_\theta(a\mid s)$ by ascending an estimate of the gradient of expected return. The classical REINFORCE-style estimator has high variance, and taking a step of fixed size in parameter space can produce an arbitrarily large change in policy space, since the mapping from parameters to the resulting distribution over trajectories is highly nonlinear. TRPO addresses this by optimizing a surrogate objective — the expected advantage under the new policy, reweighted by the importance-sampling ratio $r_t(\theta) = \pi_\theta(a_t\mid s_t) / \pi_{\theta_{\text{old}}}(a_t\mid s_t)$ — subject to a constraint that the average KL divergence between old and new policy stays below a threshold $\delta$. PPO keeps the same surrogate objective but replaces the explicit KL constraint with a clipped objective:

Here $\hat{A}_t$ is an advantage estimate (typically computed with GAE), and $\epsilon$ is a small hyperparameter (commonly $0.1$–$0.3$). The clip function truncates the ratio $r_t(\theta)$ to the interval $[1-\epsilon, 1+\epsilon]$. Taking the minimum of the clipped and unclipped terms produces a pessimistic lower bound: when the advantage is positive, the objective flattens out once $r_t$ exceeds $1+\epsilon$, removing the incentive to keep increasing the probability of that action indefinitely. When the advantage is negative, symmetric clipping prevents the ratio from collapsing below $1-\epsilon$. The result is an objective that behaves like the unclipped surrogate near $r_t = 1$ (small policy changes are essentially the same as in vanilla policy gradient) but flattens once the policy has moved "far enough," discouraging further movement in that direction. Because this is achieved purely by reshaping the loss function, it requires no second-order information, no KL penalty coefficient tuning (in the clipped variant), and no constrained optimization solver — only ordinary minibatch stochastic gradient ascent, repeated for several epochs over each batch of collected trajectories.

PPO is an on-policy actor-critic algorithm. It alternates between two phases: (1) collecting a batch of trajectories using the current policy, and (2) performing several epochs of minibatch gradient updates on that fixed batch using the clipped objective plus auxiliary terms for the value function and entropy.

Step 1 — Rollout. Run the current policy $\pi_{\theta_{\text{old}}}$ in the environment for $T$ timesteps (across possibly many parallel actors), recording states, actions, rewards, and the log-probabilities $\log \pi_{\theta_{\text{old}}}(a_t\mid s_t)$.

Step 2 — Advantage estimation. Using the critic $V_\phi(s)$, compute TD residuals $\delta_t = r_t + \gamma V_\phi(s_{t+1}) - V_\phi(s_t)$, then compute GAE advantages

and return targets $\hat{R}_t = \hat{A}_t + V_\phi(s_t)$ for the value regression loss.

Step 3 — Multi-epoch minibatch update. For $K$ epochs, shuffle the batch into minibatches and, for each minibatch, compute the combined loss

where $L^{VF}(\phi) = (V_\phi(s_t) - \hat{R}_t)^2$ is the value function loss and $S$ is the policy entropy bonus (lightly foreshadowing Entropy Regularization, which encourages continued exploration). Take a gradient ascent step on $L$ using Adam or a similar first-order optimizer.

Step 4 — Repeat. Discard the batch, set $\theta_{\text{old}} \leftarrow \theta$, and collect a fresh batch with the updated policy. ``` Algorithm: Proximal Policy Optimization (PPO-Clip) Input: initial policy parameters θ, value parameters φ, clip range ε, discount γ, GAE parameter λ, epochs K, minibatch size M, learning rate η for iteration = 1, 2, ... do

# --- Step 1: Rollout with current policy --- θ_old ← θ collect trajectories {(s_t, a_t, r_t, logπ_old(a_t|s_t))} by running π_θ_old in the environment for T steps (across N parallel actors if available)

# --- Step 2: Compute advantages and returns via GAE --- for each trajectory, t = T-1 down to 0: δ_t ← r_t + γ V_φ(s_{t+1}) - V_φ(s_t) # δ_T = r_T - V_φ(s_T) at episode end A_t ← δ_t + γ λ * A_{t+1} # A_T = δ_T R_t ← A_t + V_φ(s_t) # value regression target normalize advantages: A_t ← (A_t - mean(A)) / (std(A) + 1e-8)

# --- Step 3: K epochs of minibatch SGD on the fixed batch --- for epoch = 1 .. K do shuffle all timesteps, partition into minibatches of size M for each minibatch B do for t in B: r_t(θ) ← exp( logπ_θ(a_t|s_t) - logπ_old(a_t|s_t) ) unclipped ← r_t(θ) A_t clipped ← clip(r_t(θ), 1-ε, 1+ε) A_t L_clip_t ← min(unclipped, clipped) L_clip ← mean_t( L_clip_t ) L_vf ← mean_t( (V_φ(s_t) - R_t)^2 ) L_ent ← mean_t( entropy(π_θ(·|s_t)) ) L ← L_clip - c1 L_vf + c2 L_ent (θ, φ) ← (θ, φ) + η * ∇_{θ,φ} L # ascent on L_clip, L_ent;

# descent on L_vf via the minus sign end for end for end for ``` Two implementation details matter for correctness. First, the ratio $r_t(\theta)$ must be computed with the same actions that were sampled during rollout — it is an importance-sampling ratio, not a re-sampling of new actions. Second, advantages should be computed once per rollout (using $\theta_{\text{old}}$'s value function) and held fixed across all $K$ epochs; only the policy and value parameters are updated, not the advantage targets themselves, since those were already used to fix the training batch.

Time complexity per iteration. Rollout costs $O(T \cdot N)$ environment steps across $N$ parallel actors, each involving one forward pass through the policy and value networks — call this $O(TN \cdot C_{\text{net}})$ where $C_{\text{net}}$ is the per-step network cost. GAE computation is a single backward pass over the trajectory, $O(TN)$. The update phase runs $K$ epochs over a batch of size $TN$ split into minibatches of size $M$, each requiring one forward-backward pass, giving $O\!\big(K \cdot \frac{TN}{M} \cdot C_{\text{net}} \cdot M\big) = O(K \cdot TN \cdot C_{\text{net}})$. Since $K$ is a small constant (typically 3–10), total per-iteration cost is linear in the number of collected environment steps, $O(TN)$ up to network cost, with no polynomial blow-up from any linear-system solve — this is precisely the computational advantage over TRPO, which additionally requires $O(\text{CG iterations} \times \text{Hessian-vector products})$ per update, each Hessian-vector product itself costing $O(TN \cdot C_{\text{net}})$.

Space complexity. The batch of $TN$ transitions (states, actions, rewards, log-probabilities, advantages, returns) must be held in memory simultaneously, giving $O(TN \cdot d)$ where $d$ is the dimensionality of a state/action pair — the same as any batch-based policy gradient method, and substantially less than replay-buffer-based off-policy methods, which store data across many iterations.

Why clipping approximates a trust region. TRPO's guarantee rests on the surrogate objective inequality: for the true objective $J(\theta)$ and surrogate $L_{\theta_{\text{old}}}(\theta) = \mathbb{E}[r_t(\theta)\hat{A}_t]$,

for a constant $C$ depending on the reward range and discount. Maximizing $L$ subject to a KL bound provably yields monotonic improvement. PPO's clipped objective is a heuristic that mimics this bound's qualitative behavior without computing KL directly: consider a single timestep with advantage $\hat{A}_t > 0$. The unclipped term $r_t \hat{A}_t$ increases without bound as $r_t$ grows, but the clipped term saturates at $(1+\epsilon)\hat{A}_t$. Taking the minimum means that once $r_t > 1+\epsilon$, the gradient of $L^{\text{CLIP}}$ with respect to $\theta$ in that term is exactly zero — increasing the action's probability further yields no objective gain, so SGD has no incentive to push $r_t$ higher. Symmetric reasoning holds for $\hat{A}_t < 0$: the objective flattens once $r_t < 1-\epsilon$, discouraging the policy from decreasing that action's probability further. The min (rather than clipping alone) ensures the bound is a pessimistic (lower) estimate of the true unclipped objective whenever the ratio moves in the "wrong" direction relative to clipping, which is important because it means the algorithm never rewards moving outside the trust region even transiently within an epoch of optimization.

Honest tradeoffs. This is a heuristic, not a proof: PPO carries no formal monotonic-improvement guarantee analogous to TRPO's, since the clipping bound is local (per-timestep, per-action) rather than a global KL bound on the joint action distribution over an entire trajectory. In practice this means PPO can still occasionally take destructive steps, especially with large minibatches reused for many epochs (the ratio $r_t$ for some (s,a) pairs can end up far outside $[1-\epsilon,1+\epsilon]$ by the final epoch, since the clip only zeroes the gradient, not the ratio itself, and epoch $k{+}1$ starts from parameters already shifted by epoch $k$). PPO also remains strictly on-policy: each collected batch is used for only a handful of gradient epochs before being discarded, making it considerably less sample-efficient than off-policy alternatives, a cost paid deliberately in exchange for implementation simplicity and stability.

Consider a single timestep with clip range $\epsilon = 0.2$, advantage estimates from GAE, and three different scenarios for how far the new policy's action probability has moved from the old one. We compute the clipped surrogate term $L^{\text{CLIP}}_t = \min(r_t \hat A_t,\ \text{clip}(r_t, 0.8, 1.2)\hat A_t)$ in each case.

Walk through Case B in detail. The advantage is strongly positive ($\hat A_t = 2.0$), meaning action $a$ was much better than average at state $s$; an unconstrained policy gradient step would push $\pi_\theta(a|s)$ up aggressively. The ratio has already grown to $r_t = 1.5$, well past $1+\epsilon = 1.2$. The unclipped surrogate value is $3.00$, but the clipped surrogate caps at $(1+\epsilon)\hat A_t = 1.2 \times 2.0 = 2.40$. Since PPO takes the minimum, the effective objective is $2.40$, and — critically — because this minimum is achieved by the constant clipped branch on this data point, its derivative with respect to $\theta$ (through $r_t$) is zero: this timestep contributes no gradient signal in this minibatch, exactly as intended, because the policy has already moved far enough in the profitable direction for this action. Case C shows the symmetric protection: the advantage is negative, so the policy gradient wants to decrease $\pi_\theta(a|s)$, and it already has, aggressively ($r_t = 0.40 \ll 0.8$). The clipped branch, $\text{clip}(r_t,0.8,1.2)\hat A_t = 0.8 \times (-1.5) = -1.2$, is larger than the unclipped value $-0.60 \times$ wait — recompute: unclipped is $r_t \hat A_t = 0.40 \times (-1.5) = -0.60$, clipped is $0.8 \times (-1.5) = -1.20$. The min of $\{-0.60, -1.20\}$ is $-1.20$, so again the clipped (flattened) branch is selected, and gradient flow stops — the policy is not punished further for having already decreased this action's probability substantially. Cases A and D show the "normal" regime: $r_t$ stays inside $[0.8, 1.2]$, so the unclipped and clipped branches coincide, the min equals the ordinary surrogate value, and gradients flow exactly as in unclipped policy gradient — this is the region where PPO behaves identically to a plain surrogate objective, only intervening once the ratio threatens to leave the trust region.

PPO's combination of stability and implementation simplicity has made it the default choice across a wide range of production and research RL systems. OpenAI Five used a large-scale distributed variant of PPO to train agents that defeated professional Dota 2 teams, relying on PPO's robustness to scale across thousands of parallel actors. OpenAI's Dactyl used PPO to train a robotic hand for in-hand manipulation transferred from simulation to the real world, where training instability would be catastrophic given the cost of physical rollouts. In reinforcement learning from human feedback (RLHF), the dominant paradigm for aligning large language models such as instruction-tuned chatbots, PPO fine-tunes a language model policy against a learned reward model, with the clipped objective preventing the policy from drifting so far from its pretrained initialization that fluent, coherent text degenerates. Physics-based character animation, continuous-control benchmarks (MuJoCo, Isaac Gym), and general-purpose RL libraries (Stable-Baselines3, RLlib, CleanRL) all ship PPO as a default baseline, precisely because it tends to work reasonably well with minimal hyperparameter tuning across very different domains — a property few other deep RL algorithms share as consistently.

Ask the tutor: How does changing the clip parameter ε or the number of epochs K affect the empirical KL divergence between successive PPO policies?