Policy Gradient Methods

Proximal Policy Optimization, or PPO, is a policy gradient method for reinforcement learning. The motivation was to have an algorithm with the data efficiency and reliable performance of TRPO, while using only first-order optimization. Let $r\_{t}\left(\theta\right)$ denote the probability ratio $r\_{t}\left(\theta\right) = \frac{\pi\_{\theta}\left(a\_{t}\mid{s\_{t}}\right)}{\pi\_{\theta\_{old}}\left(a\_{t}\mid{s\_{t}}\right)}$, so $r\left(\theta\_{old}\right) = 1$. TRPO maximizes a “surrogate” objective: $$ L^{\text{CPI}}\left({\theta}\right) = \hat{\mathbb{E}}\_{t}\left[\frac{\pi\_{\theta}\left(a\_{t}\mid{s\_{t}}\right)}{\pi\_{\theta\_{old}}\left(a\_{t}\mid{s\_{t}}\right)})\hat{A}\_{t}\right] = \hat{\mathbb{E}}\_{t}\left[r\_{t}\left(\theta\right)\hat{A}\_{t}\right] $$ Where $CPI$ refers to a conservative policy iteration. Without a constraint, maximization of $L^{CPI}$ would lead to an excessively large policy update; hence, we PPO modifies the objective, to penalize changes to the policy that move $r\_{t}\left(\theta\right)$ away from 1: $$ J^{\text{CLIP}}\left({\theta}\right) = \hat{\mathbb{E}}\_{t}\left[\min\left(r\_{t}\left(\theta\right)\hat{A}\_{t}, \text{clip}\left(r\_{t}\left(\theta\right), 1-\epsilon, 1+\epsilon\right)\hat{A}\_{t}\right)\right] $$ where $\epsilon$ is a hyperparameter, say, $\epsilon = 0.2$. The motivation for this objective is as follows. The first term inside the min is $L^{CPI}$. The second term, $\text{clip}\left(r\_{t}\left(\theta\right), 1-\epsilon, 1+\epsilon\right)\hat{A}\_{t}$ modifies the surrogate objective by clipping the probability ratio, which removes the incentive for moving $r\_{t}$ outside of the interval $\left[1 − \epsilon, 1 + \epsilon\right]$. Finally, we take the minimum of the clipped and unclipped objective, so the final objective is a lower bound (i.e., a pessimistic bound) on the unclipped objective. With this scheme, we only ignore the change in probability ratio when it would make the objective improve, and we include it when it makes the objective worse. One detail to note is that when we apply PPO for a network where we have shared parameters for actor and critic functions, we typically add to the objective function an error term on value estimation and an entropy term to encourage exploration.

Trust Region Policy Optimization, or TRPO, is a policy gradient method in reinforcement learning that avoids parameter updates that change the policy too much with a KL divergence constraint on the size of the policy update at each iteration. Take the case of off-policy reinforcement learning, where the policy $\beta$ for collecting trajectories on rollout workers is different from the policy $\pi$ to optimize for. The objective function in an off-policy model measures the total advantage over the state visitation distribution and actions, while the mismatch between the training data distribution and the true policy state distribution is compensated with an importance sampling estimator: $$ J\left(\theta\right) = \sum\_{s\in{S}}p^{\pi\_{\theta\_{old}}}\sum\_{a\in\mathcal{A}}\left(\pi\_{\theta}\left(a\mid{s}\right)\hat{A}\_{\theta\_{old}}\left(s, a\right)\right) $$ $$ J\left(\theta\right) = \sum\_{s\in{S}}p^{\pi\_{\theta\_{old}}}\sum\_{a\in\mathcal{A}}\left(\beta\left(a\mid{s}\right)\frac{\pi\_{\theta}\left(a\mid{s}\right)}{\beta\left(a\mid{s}\right)}\hat{A}\_{\theta\_{old}}\left(s, a\right)\right) $$ $$ J\left(\theta\right) = \mathbb{E}\_{s\sim{p}^{\pi\_{\theta\_{old}}}, a\sim{\beta}} \left(\frac{\pi\_{\theta}\left(a\mid{s}\right)}{\beta\left(a\mid{s}\right)}\hat{A}\_{\theta\_{old}}\left(s, a\right)\right)$$ When training on policy, theoretically the policy for collecting data is same as the policy that we want to optimize. However, when rollout workers and optimizers are running in parallel asynchronously, the behavior policy can get stale. TRPO considers this subtle difference: It labels the behavior policy as $\pi\_{\theta\_{old}}\left(a\mid{s}\right)$ and thus the objective function becomes: $$ J\left(\theta\right) = \mathbb{E}\_{s\sim{p}^{\pi\_{\theta\_{old}}}, a\sim{\pi\_{\theta\_{old}}}} \left(\frac{\pi\_{\theta}\left(a\mid{s}\right)}{\pi\_{\theta\_{old}}\left(a\mid{s}\right)}\hat{A}\_{\theta\_{old}}\left(s, a\right)\right)$$ TRPO aims to maximize the objective function $J\left(\theta\right)$ subject to a trust region constraint which enforces the distance between old and new policies measured by KL-divergence to be small enough, within a parameter $\delta$: $$ \mathbb{E}\_{s\sim{p}^{\pi\_{\theta\_{old}}}} \left[D\_{KL}\left(\pi\_{\theta\_{old}}\left(.\mid{s}\right)\mid\mid\pi\_{\theta}\left(.\mid{s}\right)\right)\right] \leq \delta$$