RL: Proximal policy optimization (PPO)

Review

On-policy v.s. Off-policy

If the actor to train and the actor for interacting is the same, we call it on-policy. In other words, if the actor himself does training to gain experience, it is on policy; if the actor gains experience by watching other actors train, it is off-policy.

An advantage of off-policy is that it can be trained with the experience of other actors, so there is no need to constantly collect data, which can greatly improve the training efficiency.

All the previous ones were on-policy. The actor goes back to the environment to collect a lot of $\tau$ and updates the parameters according to the following equation:

$$\mathrm{\nabla }{\bar{R}}_{\theta }=E_{\tau \sim p_{\theta }(\tau )}[R(\tau )\mathrm{\nabla }log{p}_{\theta }(\tau )]$$

If you can use another actor to interact with the environment and use the data it collects to train the theta (the data it collects can be stored and used multiple times), you can do multiple gradients with the same set of data.

Theory

Importance Sampling

$x$ follows the distribution $p$, and to approximate the expectation of $f(x)$:

$$E_{x\sim p}[f(x)]\approx \frac{1}{N}\sum _{i=1}^{N}f(x^i)$$

However, if you cannot sample from $p$, but can only sample from another distribution $q$, you cannot directly use the above formula, but make the following correction:

The expectation of $f$ on $p$ is satisfied:

$$E_{x\sim p}[f(x)]=\int f(x)p(x)dx$$$$\int f(x)p(x)=\int f(x)\frac{p(x)}{q(x)}q(x)dx=E_{x\sim q}[f(x)\frac{p(x)}{q(x)}]$$

And that translates into expectations on the $q$ distribution.

The fact that there is only one $\frac{p(x)}{q(x)}$ difference between $E_{x\sim p}[f(x)]$ and $E_{x\sim q}[f(x)\frac{p(x)}{q(x)}]$ is a correction for the difference between the two different distributions.

This makes their expectations equal, but not their variances equal:

$$Va{r}_{x\sim p}[f(x)]\ne Va{r}_{x\sim q}[f(x)\frac{p(x)}{q(x)}]$$

According to:

$$Var(x)=E(x^2)-E[x{]}^2,$$$$Va{r}_{x\sim p}[f(x)]=E_{x\sim p}[f(x{)}^2]-E_{x\sim p}[f(x){]}^2$$$$Va{r}_{x\sim q}[f(x)\frac{p(x)}{q(x)}]=E_{x\sim q}\left[{(f(x)\frac{p(x)}{q(x)})}^2\right]-{\left(E_{x\sim q}[f(x)\frac{p(x)}{q(x)}]\right)}^2$$$$=E_{x\sim p}[f(x{)}^2\frac{p(x)}{q(x)}]-E_{x\sim p}[f(x){]}^2$$

The equivalent is still missing a correction term. If $p$ and $q$ are too far apart, the effect of the difference can be very large.

We let ${\theta }^{\prime }$ interact with the environment, and then we tell $\theta$ what to expect.

The $\tau$ on this side is sampled from ${\theta }^{\prime }$:

which is different from the target distribution $\theta$, so it can be converted using the above formula:

$$\mathrm{\nabla }{\bar{R}}_{\theta }=E_{\tau \sim p_{\theta }^{\prime }(\tau )}[\frac{p_{\theta }(\tau )}{p_{{\theta }^{\prime }}(\tau )}R(\tau )\mathrm{\nabla }log{p}_{\theta }(\tau )]$$

This is equivalent to saying that we can sample ${\theta }^{\prime }$ multiple times to train the same $\theta$, and when this $\theta$ is nearly trained, we can change another ${\theta }^{\prime }$ to train other $\theta$.

On-policy $\to$ Off-policy Gradient for update

from note "RL overview and basic policy gradient", we know that:

$$\mathrm{\nabla }{\bar{R}}_{\theta }=E_{(s_t,a_t)\sim {\pi }_{\theta }}[A^{\theta }(s_t,a_t)\mathrm{\nabla }log{p}_{\theta }(a_t^n|s_t^n)]$$

The $s_t$ and $a_t$ on this side are derived from the interaction between $\theta$ and the environment. If we replace $\theta$ with ${\theta }^{\prime }$, the gradient becomes:

$$\mathrm{\nabla }{\bar{R}}_{\theta }=E_{(s_t,a_t)\sim {\pi }_{{\theta }^{\prime }}}[\frac{P_{\theta }(s_t,a_t)}{P_{{\theta }^{\prime }}(s_t,a_t)}{A}^{{\theta }^{\prime }}(s_t,a_t)\mathrm{\nabla }log{p}_{\theta }(a_t^n|s_t^n)]$$

Where $s_t$ and $a_t$ are derived from the interaction between ${\theta }^{\prime }$​ and the environment.

The advantage term should also be replaced, because ${\theta }^{\prime }$is now interacting with the environment and should be given an advantage value of $A^{{\theta }^{\prime }}$​​.

If we assume that the two distributions are similar, then the above equation is equal to:

$$=E_{(s_t,a_t)\sim {\pi }_{{\theta }^{\prime }}}[\frac{p_{\theta }(s_t|a_t)}{p_{{\theta }^{\prime }}(s_t|a_t)}\frac{\bcancel{p_{\theta }(s_t)}}{\bcancel{p_{{\theta }^{\prime }}(s_t)}}{A}^{{\theta }^{\prime }}(s_t,a_t)\mathrm{\nabla }log{p}_{\theta }(a_t^n|s_t^n)]$$

Invert the objective function from the gradient function:

$$\mathrm{\nabla }f(x)=f(x)\mathrm{\nabla }logf(x),$$$$J^{{\theta }^{\prime }}(\theta )=E_{(s_t,a_t)\sim {\pi }_{{\theta }^{\prime }}}[\frac{p_{\theta }(s_t,a_t)}{p_{{\theta }^{\prime }}(s_t,a_t)}{A}^{{\theta }^{\prime }}(s_t,a_t)]$$

PPO

The goal is to avoid a big difference between the two distributions.

$$J_{PPO}^{{\theta }^{\prime }}(\theta )=J^{{\theta }^{\prime }}(\theta )-\beta KL(\theta ,{\theta }^{\prime })$$

$\beta KL(\theta ,{\theta }^{\prime })$ is a measure of how similar the two distributions are.

Algorithm

Pseudocode of PPO

initial policy parameters ${\theta }^0$  in each iteration   using ${\theta }^k$ to interact with the environment to collect $\{s_t,a_t\}$ and compute advantage $A^{{\theta }^k}(s_t,a_t)$   find $\theta$ optimizing $J_{PPO}(\theta )$   $J_{PPO}^{{\theta }^k}(\theta )=J^{{\theta }^k}(\theta )-\beta KL(\theta ,{\theta }^k)$ //update parameters several times   if $KL(\theta ,{\theta }^k)>K{L}_{max}$, increase $\beta$   if $KL(\theta ,{\theta }^k)<K{L}_{min}$, decrease $\beta$

$$J^{{\theta }^k}(\theta )\approx \sum _{(s_t,a_t)}\frac{p_{\theta }(a_t|s_t)}{p_{{\theta }^k}(a_t|s_t)}{A}^{{\theta }^k}(s_t,a_t)$$

The acceptable range of $KL$ values is set in advance. If $KL$ is too small, it means that $\theta$ and ${\theta }^k$​ are too close, and the effect is not obvious.

PPO2

The objective function of PPO2:

$$J_{PPO2}^{{\theta }^k}\approx \sum _{(s_t,a_t)}min(\frac{p_{\theta }(a_t|s_t)}{p_{{\theta }^k}(a_t|s_t)}{A}^{{\theta }^k}(s_t,a_t),clip(\frac{p_{\theta }(a_t|s_t)}{p_{{\theta }^k}(a_t|s_t)},1-ϵ,1+ϵ)A^{{\theta }^k}(s_t,a_t))$$

clip(a, min, max) refers to: if a < min, let a = min; if a > max, let a = max.

The main purpose of this function is to keep the gap between $p_{\theta }$ and $p_{{\theta }^k}$​ from getting too wide.

In this image:

blue line is $clip(\frac{p_{\theta }(a_t|s_t)}{p_{{\theta }^k}(a_t|s_t)},1-ϵ,1+ϵ)$;

green line is $\frac{p_{\theta }(a_t|s_t)}{p_{{\theta }^k}(a_t|s_t)}{A}^{{\theta }^k}(s_t,a_t)$;

and the red line is $min(\frac{p_{\theta }(a_t|s_t)}{p_{{\theta }^k}(a_t|s_t)}{A}^{{\theta }^k}(s_t,a_t),clip(\frac{p_{\theta }(a_t|s_t)}{p_{{\theta }^k}(a_t|s_t)},1-ϵ,1+ϵ)A^{{\theta }^k}(s_t,a_t))$.

We can see that $\frac{p_{\theta }(a_t|s_t)}{p_{{\theta }^k}(a_t|s_t)}$ will be controlled when it's too large or small.