deep reinforcement learning:on-policy off-policy PPO

on-policy
与环境交互的agent和学习的agent是同一个agent
off-policy
与环境交互的agent和学习的agent是不同的agent

shortcoming：on-policy方法，在每次做gradient ascent需要重新sample training data。

off-policy方法与环境交互的agent参数 $\theta$ 是固定的，sample的training data可以多次使用。

Import sampling

从概率分布p中sample $x^i$ ， $f(x)$ 期望为
$\approx \frac{1}{N} \sum_{i=1}^{N} f\left(x^{i}\right)$
在不能对p直接采样的情况下，有
$E_{x \sim p}[f(x)] =\int f(x) p(x) d x=\int f(x) \frac{p(x)}{q(x)} q(x) d x=E_{x \sim q}\left[f(x) \frac{p(x)}{g(x)}\right]$

因此，我们对概率分布q进行采样，能够得到相同的 $f(x)$ 的期望。

但注意Variance并不是一致的，对原概率分布p采样和对q采样的Variance如下：

$\begin{array}{l} \operatorname{Var}_{x \sim p}[f(x)]=E_{x \sim p}\left[f(x)^{2}\right]-\left(E_{x \sim p}[f(x)]\right)^{2} \\ \begin{aligned} \operatorname{Var}_{x \sim q}\left[f(x) \frac{p(x)}{q(x)}\right] &=E_{x \sim g}\left[\left(f(x) \frac{p(x)}{q(x)}\right)^{2}\right]-\left(E_{x \sim q}\left[f(x) \frac{p(x)}{q(x)}\right]\right)^{2} \\ &=E_{x \sim p}\left[f(x)^{2} \frac{p(x)}{q(x)}\right]-\left(E_{x \sim p}[f(x)]\right)^{2} \end{aligned} \end{array}$

在上式中，可以看到两项Variance的第二项相同，第一项相差 $\frac{p(x)}{q(x)}$ 。

在采样过少的情况下，分布p与q相差过大时， $f(x)$ 期望可能会不准确，如下图所示，当没有采样到p右边的点时，期望为负值，只有当采样到足够多次数，采样到q左边点，会有一个较大的weight使得期望一致。

捕获.PNG

因此，p和q相差不能太多。

公式

从on-policy到off-policy，有
$\nabla \bar{R}_{\theta}=E_{\tau \sim p_{\theta}(\tau)}\left[R(\tau) \nabla \log p_{\theta}(\tau)\right]$

Use $\pi_{\theta}$ to collect data. When $\theta$ is updated, we have to sample training data again.
Goal: Using the sample from $\pi_{\theta^{\prime}}$ to train $\theta . \theta^{\prime}$ is fixed, so we can re-use the sample data.

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

sample the data from $\theta^{\prime}$ .
use the data to train $\theta$ many times.

实际上，policy gradient时，不会整个trajectory一个分数，而是每一个 state-action pair来计算分数。结合重要采样，实际整体公式为：

$\begin{array} \\ \text{Gradient for update} &= E_{\left(s_{t}, a_{t}\right) \sim \pi_{\theta}}\left[A^{\theta}\left(s_{t}, a_{t}\right) \nabla \log p_{\theta_{0}}\left(a_{t}^{n} \mid s_{t}^{n}\right)\right] \\ &= E_{\left(s_{t}, a_{t}\right) \sim \pi_{\theta^{\prime}}}\left[\frac{P_{\theta}\left(s_{t}, a_{t}\right)}{P_{\theta^{\prime}}\left(s_{t}, a_{t}\right)} A^{\theta}\left(s_{t}, a_{t}\right) \nabla \log p_{\theta}\left(a_{t}^{n} \mid s_{t}^{n}\right)\right] \end{array}$

注意这里 $A^{\theta}$ ，应为 $A^{\theta^{\prime}}$ ，为与环境交互的agent得到的价值。

进一步拆解有
$E_{\left(s_{t}, a_{t}\right) \sim \pi_{\theta^{\prime}}}\left[\frac{p_{\theta}\left(a_{t} \mid s_{t}\right)}{p_{\theta^{\prime}}\left(a_{t} \mid s_{t}\right)} \frac{p_{\theta}\left(s_{t}\right)}{p_{\theta^{\prime}}\left(s_{t}\right)} A^{\theta^{\prime}}\left(s_{t}, a_{t}\right) \nabla \log p_{\theta}\left(a_{t}^{n} \mid s_{t}^{n}\right)\right]$

另外，可以认为不同的agent下state出现的概率对问题没有影响，（实际上state过多且稀疏，如都每个state均为image，该项计算也非常困难） $\frac{p_{\theta}\left(s_{t}\right)}{p_{\theta^{\prime}}\left(s_{t}\right)}$ 可以舍去。

又有公式
$\nabla f(x)=f(x) \nabla \log f(x)$

最终有公式形式为：

$J^{\theta^{\prime}}(\theta)=E_{\left(s_{t}, a_{t}\right) \sim \pi_{\theta^{\prime}}}\left[\frac{p_{\theta}\left(a_{t} \mid s_{t}\right)}{p_{\theta^{\prime}}\left(a_{t} \mid s_{t}\right)} A^{\theta^{\prime}}\left(s_{t}, a_{t}\right)\right]$

PPO

由重要采样部分我们可知，分布 $p$ 和 $q$ 相差不能太多，因此PPO添加了一个约束两个分布相似性，形式为：
$\begin{aligned} J_{P P O}^{\theta^{\prime}}(\theta)=J^{\theta^{\prime}}(\theta)-& \beta K L\left(\theta, \theta^{\prime}\right) \\ J^{\theta^{\prime}}(\theta) &=E_{\left(s_{t}, a_{t}\right) \sim \pi_{\theta^{\prime}}}\left[\frac{p_{\theta}\left(a_{t} \mid s_{t}\right)}{p_{\theta^{\prime}}\left(a_{t} \mid s_{t}\right)} A^{\theta^{\prime}}\left(s_{t}, a_{t}\right)\right] \end{aligned}$
注意 $KL$ 描述的是两个agent行为上的距离，而不是参数上的距离。

PPO algorithm

初始化参数 $\theta^0$
迭代：使用 $\theta_k$ 与环境交互，收集 ${s_t, a_t}$ ,，以及计算 $A^{\theta^{k}}\left(s_{t}, a_{t}\right)$

$J_{P P O}^{\theta^{k}}(\theta)=J^{\theta^{k}}(\theta)-\beta K L\left(\theta, \theta^{k}\right)$

$J^{\theta^{k}}(\theta) \approx \sum_{\left(s_{t}, a_{t}\right)} \frac{p_{\theta}\left(a_{t} \mid s_{t}\right)}{p_{\theta^{k}}\left(a_{t} \mid s_{t}\right)} A^{\theta^{k}}\left(s_{t}, a_{t}\right)$

对于超参数 $\beta$ ，有自适应方法，设定最大和最小阈值，当大于最大阈值，减少 $\beta$ ，小于最小阈值，增大 $\beta$ 。

PPO2 algothrim

$J_{P P O 2}^{\theta^{k}}(\theta) \approx \sum_{\left(s_{t}, a_{t}\right)} \min \left(\frac{p_{\theta}\left(a_{t} \mid s_{t}\right)}{p_{\theta^{k}}\left(a_{t} \mid s_{t}\right)} A^{\theta^{k}}\left(s_{t}, a_{t}\right)\right.,\left.\operatorname{clip}\left(\frac{p_{\theta}\left(a_{t} \mid s_{t}\right)}{p_{\theta^{k}}\left(a_{t} \mid s_{t}\right)}, 1-\varepsilon, 1+\varepsilon\right) A^{\theta^{k}}\left(s_{t}, a_{t}\right)\right)$

clip的意思是，三个参数，第一项小于第二项，就输出第二项 $1-\epsilon$ ，第一项大于第三项，输出第三项 $1+\epsilon$ ，否则在两者之间输出为第一项。

image.png

PPO2不用计算KL，通过上式的目标函数限制p和q的分布的差异。