TRPO

TRPO is a policy gradient method in RL that ensures policy parameters don’t change too much from one step to the next with the help of KL-divergence as a constraint.

We maximize the surrogate objective (instead of directly maximizing rewards):

$$\begin{array}{rl}\underset{\theta }{\mathrm{maximize}}& {\hat{\mathbb{E}}}_t\left[\frac{{\pi }_{\theta }(a_t\mid s_t)}{{\pi }_{{\theta }_{\text{old}}}(a_t\mid s_t)}{\hat{A}}_t\right]\\ \text{subject to}& {\hat{\mathbb{E}}}_t[\text{KL}[{\pi }_{{\theta }_{\text{old}}}(\cdot \mid s_t),{\pi }_{\theta }(\cdot \mid s_t)]]\le \delta \end{array}$$

Trust Region Policy Optimization

The objective function $J(\theta )$ measures the expected advantage of policy ${\pi }_{\theta }$ relative to a baseline, which in this case is the old policy parameters ${\theta }_{old}$. This baseline serves as a reference point for measuring improvement - we want to know if our new policy performs better than our previous one. The objective can be written as:

$$J(\theta )=\sum _{s\in S}{p}^{{\pi }_{old}}\sum _{a\in A}\left({\pi }_{\theta }(a|s){\hat{A}}_{{\theta }_{old}}(s,a)\right)$$

where $p^{{\pi }_{old}}$ is the state visitation distribution under the old policy. The estimated advantage ${\hat{A}}_{{\theta }_{old}}(s,a)$ measures how much better taking action $a$ in state $s$ is compared to the average value of that state.
Since we collect data using a behavior policy $\beta$ that differs from our target policy ${\pi }_{\theta }$, we need to account for this mismatch. We can do this by introducing an importance sampling ratio:

$$J(\theta )=\sum _{s\in S}{p}^{{\pi }_{old}}\sum _{a\in A}\left(\beta (a|s)\frac{{\pi }_{\theta }(a|s)}{\beta (a|s)}{\hat{A}}_{{\theta }_{old}}(s,a)\right)$$

We can express this as an expectation over state-action pairs sampled according to the behavior policy. Note that when we convert from the sum to an expectation, the $\beta (a|s)$ term becomes implicit in our sampling distribution $a\sim \beta$, leaving us with:

$$J(\theta )={\mathbb{E}}_{s\sim p^{{\pi }_{old}},a\sim \beta }\left(\frac{{\pi }_{\theta }(a|s)}{\beta (a|s)}{\hat{A}}_{{\theta }_{old}}(s,a)\right)$$

Even in an on-policy example, where the current policy is used to collect trajectories, the actor policy can sometimes get out of sync, i.e. $\beta ={\pi }_{{\theta }_{\text{old}}}$

TRPO introduces a trust region constraint for the distance between the old and the new policy to be within a parameter $\delta$:

$${\mathbb{E}}_{s\sim p^{{\pi }_{{\theta }_{\text{old}}}}}[D_{\text{KL}}({\pi }_{{\theta }_{\text{old}}}(\cdot \mid s)\Vert {\pi }_{\theta }(\cdot \mid s))]\le \delta$$

We measure this distance using states sampled from the old policy’s distribution, since those represent the actual states where we have data to evaluate policy performance.

As a second order method (approximating the KL divergence by computing hessian through fisher information matrix), TRPO can be computationally expensive, which motivated the development of simpler first-order alternatives like PPO that achieve similar performance.

The theory justifying TRPO actually suggests using a penalty instead of a constraint, i.e., solving the unconstrained optimization problem:

$$\underset{\theta }{\mathrm{maximize}}{\hat{\mathbb{E}}}_t\left[\frac{{\pi }_{\theta }(a_t\mid s_t)}{{\pi }_{{\theta }_{\text{old}}}(a_t\mid s_t)}{\hat{A}}_t-\beta \text{ KL}[{\pi }_{{\theta }_{\text{old}}}(\cdot \mid s_t),{\pi }_{\theta }(\cdot \mid s_t)]\right]$$

for some coefficient β. This follows from the fact that a certain surrogate objective (which computes the max KL over states instead of the mean) forms a lower bound (i.e., a pessimistic bound) on the performance of the policy π. TRPO uses a hard constraint rather than a penalty because it is hard to choose a single value of β that performs well across different problems—or even within a single problem, where the the characteristics change over the course of learning.

The objective (without the constraint) was first introduced in conservative policy iteration.