Trust Region Policy Optimization

Definition

The performance of DDPG does not improve monotonically. TRPO addresses the problem by adopting two concepts: Minorize-Maximization Algorithm and trust region. TRPO updates the policy parameter $\theta$ on a trust region in the policy space, guaranteeing monotonic improvement of the objective function (expected return). Although TRPO has achieved high performance, its implementation is very complex so being not practical.

TRPO starts from the maximization problem of expected return $\eta (\pi ):=E_{\tau }[\sum _{t=0}^{\infty }{\gamma }^t(s_t)]$

The original problem is approximated multiple times to find a surrogate function and be solved by MM Algorithm. The surrogate function satisfying the trust region constraint is found using the conservative policy iteration update. $\eta (\pi )\ge L_{{\pi }_{\text{old}}}(\pi )-\frac{4ϵ\gamma }{(1-\gamma {)}^2}{\max }_s{D}_{KL}({\pi }_{{\theta }_{\text{old}}}(\cdot |s)||{\pi }_{\theta }(\cdot |s))$ where $L_{{\pi }_{\text{old}}}(\pi )=\eta (\pi )+\sum _s{\rho }_{{\pi }_{\text{old}}}(s)\sum _a\pi (a|s)A_{{\pi }_{\text{old}}}(s,a)$ is a local approximation of $\eta (\pi )$, and ${\rho }_{\pi }(s)$ is a State Visitation Frequency.

The KL penalized optimization problem is transformed to a constrained optimization problem by Duality. ${\max }_{\theta }{L}_{{\pi }_{{\theta }_{\text{old}}}}({\pi }_{\theta })\text{subject to}{\max }_s{D}_{KL}({\pi }_{{\theta }_{\text{old}}}(\cdot |s)||{\pi }_{\theta }(\cdot |s))\le \delta$

By approximations, the final optimization problem is $E_{s\sim {\rho }_{{\theta }_{\text{old}}},a\sim {\pi }_{{\theta }_{\text{old}}}}\left[\frac{{\pi }_{\theta }(a|s)}{{\pi }_{{\theta }_{\text{old}}}(a|s)}{A}_{{\theta }_{\text{old}}}(s,a)\right]\text{subject to }{E}_{s\sim {\rho }_{{\theta }_{\text{old}}}}[D_{KL}({\pi }_{{\theta }_{\text{old}}}(\cdot |s)||{\pi }_{\theta }(\cdot |s))]\le \delta$

The optimization problem is solved by the natural policy gradient and check the monotonic improvement with Backtracking Line Search $\theta ={\theta }_{\text{old}}+\sqrt{\frac{2\delta }{g^{⊺}{F}^{-1}g}}{F}^{-1}g$ where $g={\nabla }_{\theta }{L}_{{\theta }_{\text{old}}}(\theta ){|}_{\theta ={\theta }_{\text{old}}}={\nabla }_{\theta }\left(\frac{{\pi }_{\theta }(a|s)}{{\pi }_{{\theta }_{\text{old}}}(a|s)}{A}_{{\theta }_{\text{old}}}(s,a)\right){|}_{\theta ={\theta }_{\text{old}}}$ is a policy gradient, $F$ is the Fisher Information Metric, and $\delta$ is the constraint threshold.

TRPO is performed by repeating 3 steps in each iteration

1. Collect trajectories on ${\pi }_{\text{old}}$, and update $Q$-values.
2. By averaging over samples, construct the estimated objective and constraint.
3. Approximately solve the constrained optimization by natural policy gradient and Backtracking Line Search to update the policy parameter $\theta$.

Algorithm

1. Initialize policy parameters ${\theta }_0$.
2. For $k=0,1,\dots ,K$:
   1. Collect a set of trajectories under current policy ${\pi }_k=\pi ({\theta }_k)$.
   2. Compute advantages $A^{{\pi }_k}(s,a)$ using an advantage estimation algorithm.
   3. Compute policy gradient $g_k$ and Fisher Information Metric $F_k$.
   4. Compute natural gradient $x_k\approx F_k^{-1}{g}_k$.
   5. Estimate proposed step ${\Delta }_k\leftarrow \sqrt{\frac{2\delta }{x_k^{⊺}{F}_k{x}_k}}{x}_k$
   6. Perform Backtracking Line Search to obtain final update: 2. Find minimum $j\in {\mathbb{Z}}_0^{+}$ such that the KL constraint is satisfied. $\underset{j}{\min }j\in {\mathbb{Z}}_0^{+}\text{such that}{D}_{KL}({\pi }_{{\theta }_k}(\cdot |s)||{\pi }_{{\theta }_k+{\alpha }^j{\Delta }_k}(\cdot |s))\le \delta$
   7. Update the policy ${\theta }_{k+1}\leftarrow {\theta }_k+{\alpha }^j{\Delta }_k$