Proximal Policy Optimisation

reinforcement-learning

Definition

Proximal Policy Optimisation

Let $\mathcal{M}=(\mathcal{S},\mathcal{A},P,R,\gamma )$ be a Markov decision process. Let ${\pi }_{\theta }$ be a parameterised stochastic policy with parameters $\theta$, let ${\pi }_{{\theta }_{\text{old}}}$ be the policy from the previous iteration, and let ${\hat{A}}_t$ be an estimator of the advantage function at timestep $t$.

PPO maximises the clipped surrogate objective

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

where $r_t(\theta )=\frac{{\pi }_{\theta }(a_t\mid s_t)}{{\pi }_{{\theta }_{\text{old}}}(a_t\mid s_t)}$ is the probability ratio and $\epsilon \in (0,1)$ is a clipping hyperparameter.

Problem Setup

Formal setup

An agent interacts with an environment modelled as a Markov decision process $\mathcal{M}=(\mathcal{S},\mathcal{A},P,R,\gamma )$, where:

• $\mathcal{S}$ is the state space,
• $\mathcal{A}$ is the action space,
• $P(s^{\prime }\mid s,a)$ is the transition probability,
• $R(s,a)$ is the immediate reward,
• $\gamma \in [0,1]$ is the discount factor.

A stochastic policy ${\pi }_{\theta }(a\mid s)$ gives the probability of taking action $a$ in state $s$, parameterised by $\theta \in {\mathbb{R}}^d$.

The return from timestep $t$ is

$$G_t=\sum _{k=0}^{\infty }{\gamma }^{k}R(s_{t+k},a_{t+k}).$$

The objective is to find ${\theta }^{\ast }$ that maximises the expected return from the start distribution:

$$J(\theta )={\mathbb{E}}_{\tau \sim {\pi }_{\theta }}\left[G_0\right].$$

Policy Gradient

Policy Gradient Theorem

The gradient of $J(\theta )$ with respect to $\theta$ is

$${\nabla }_{\theta }J(\theta )={\mathbb{E}}_{\tau \sim {\pi }_{\theta }}\left[\sum _{t=0}^{\infty }{\nabla }_{\theta }\log {\pi }_{\theta }(a_t\mid s_t){\hat{A}}_t\right]$$

where ${\hat{A}}_t$ is an estimate of the advantage function

$$A^{{\pi }_{\theta }}(s,a)=Q^{{\pi }_{\theta }}(s,a)-V^{{\pi }_{\theta }}(s).$$

Why the advantage?

The action-value $Q^{{\pi }_{\theta }}(s,a)$ tells you the expected return after taking $a$ in $s$. The value $V^{{\pi }_{\theta }}(s)$ tells you the expected return from $s$ under the current policy. The advantage $A(s,a)$ measures how much better $a$ is than the average action in $s$. Using the advantage instead of the raw return reduces variance without introducing bias.

Vanilla policy gradient

Naively following ${\nabla }_{\theta }J(\theta )$ with a fixed step size is brittle. A step that is too large can collapse performance, because the policy changes too much and the data collected under ${\pi }_{{\theta }_{\text{old}}}$ no longer represents ${\pi }_{\theta }$. A step that is too small wastes samples.

From Trust Region to Clipping

The trust region idea

Trust Region Policy Optimization (TRPO) constrains each update to a KL divergence ball:

$$\begin{array}{rl}\underset{\theta }{\max }& {\mathbb{E}}_t\left[r_t(\theta ){\hat{A}}_t\right]\\ \text{s.t.}& {\mathbb{E}}_t\left[D_{\text{KL}}({\pi }_{{\theta }_{\text{old}}}(\cdot \mid s_t)\Vert {\pi }_{\theta }(\cdot \mid s_t))\right]\le \delta .\end{array}$$

This ensures monotonic improvement in theory, but the constrained optimisation requires conjugate gradient and a line search, making it computationally heavy.

PPO's solution: clipping

PPO replaces the hard constraint with a clipped surrogate objective that penalises large policy changes directly in the loss. Define the probability ratio

$$r_t(\theta )=\frac{{\pi }_{\theta }(a_t\mid s_t)}{{\pi }_{{\theta }_{\text{old}}}(a_t\mid s_t)}.$$

When ${\pi }_{\theta }={\pi }_{{\theta }_{\text{old}}}$, we have $r_t(\theta )=1$. The unconstrained surrogate ${\mathcal{L}}^{\text{CPI}}(\theta )={\mathbb{E}}_t[r_t(\theta ){\hat{A}}_t]$ would allow $r_t$ to grow unboundedly. PPO clips $r_t$ to $[1-\epsilon ,1+\epsilon ]$:

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

The $\min$ ensures the objective is a pessimistic bound on the unconstrained surrogate:

• When ${\hat{A}}_t>0$ (the action was good): increasing $r_t$ beyond $1+\epsilon$ yields no further gain — the clip caps the incentive.
• When ${\hat{A}}_t<0$ (the action was bad): decreasing $r_t$ below $1-\epsilon$ yields no further gain — the clip caps the penalty.

In both cases, PPO ignores changes to $r_t$ that would move the new policy too far from the old one.

Algorithm

PPO with clipped objective

Instance: MDP $\mathcal{M}$, initial policy parameters ${\theta }_0$, value function parameters ${\varphi }_0$, clipping $\epsilon$, number of epochs $K$, minibatch size $M$.

Repeat for each iteration:

1. Collect: Run ${\pi }_{{\theta }_{\text{old}}}$ for $T$ timesteps, collecting trajectories $\{s_t,a_t,r_t\}$.
2. Compute advantage estimates ${\hat{A}}_1,\dots ,{\hat{A}}_T$ using generalised advantage estimation.
3. Compute returns ${\hat{G}}_t={\hat{A}}_t+V_{\varphi }(s_t)$.
4. For $k=1,\dots ,K$ epochs:
   • Shuffle the $T$ samples into minibatches of size $M$.
   • For each minibatch $\mathcal{B}$:
     • Update $\theta$ by gradient ascent on ${\mathcal{L}}^{\text{CLIP}}(\theta )$ over $\mathcal{B}$.
     • Update $\varphi$ by gradient descent on $\frac{1}{|\mathcal{B}|}{\sum }_{t\in \mathcal{B}}(V_{\varphi }(s_t)-{\hat{G}}_t{)}^2$.
5. Set ${\theta }_{\text{old}}\leftarrow \theta$.

Hyperparameters

Typical settings: $\epsilon \in [0.1,0.3]$, $K\in [3,10]$, $M\in [64,256]$, and $T$ chosen so that the total collected experience is a few thousand timesteps.

Properties

On-policy

PPO is an on-policy algorithm: each batch of data is collected under the current policy and discarded after one (or a few) gradient steps. This ensures the probability ratio $r_t(\theta )$ is computed with respect to the policy that generated the data.

Model-free

PPO does not learn or use a model of the transition dynamics $P(s^{\prime }\mid s,a)$. It is a model-free method.

Actor-critic

PPO maintains both a policy (actor) with parameters $\theta$ and a value function (critic) with parameters $\varphi$. The critic provides the baseline for advantage estimation, reducing variance.

Monotonic improvement

Unlike TRPO, PPO does not provide a theoretical guarantee of monotonic improvement. The clipping heuristic is an empirical approximation of the trust region constraint, but in practice it achieves comparable or better stability with a simpler implementation.

Variance reduction via GAE

PPO typically uses generalised advantage estimation (GAE) to compute ${\hat{A}}_t$, which trades off bias and variance through a parameter $\lambda \in [0,1]$:

$${\hat{A}}_t^{\text{GAE}(\gamma ,\lambda )}=\sum _{l=0}^{\infty }(\gamma \lambda {)}^l{\delta }_{t+l}$$

where ${\delta }_t=r_t+\gamma V_{\varphi }(s_{t+1})-V_{\varphi }(s_t)$ is the temporal-difference error.