RL-Ch4-Policy Gradient

2020-10-24

RL-Ch4-Policy Gradient

策略梯度(Policy Gradient)

强化学习的例子

Scene	Agent	Env	Reward Function
Video	游戏手柄	主机	杀1怪得20分
Go	AlphaGo	李世石	the Rule of Go

在上述例子中，策略(policy)$\pi$的具体表现形式可认为是神经网络从输入层到输出层之间的参数矩阵$\theta$。

下图为一个加入了action的马尔可夫链，

记Trajectory $\tau={s_1,a_1,…,s_T,a_T}$，则

$$
p_\theta(\tau)=p(s_1)p_\theta(a_1|s_1)p(s_2|s_1,a_1)p_\theta(a_2|s_2)p(s_3|s_2,a_2)…\
=p(s_1)\prod_{t=1}^Tp_\theta(a_t|s_t)p(s_{t+1}|s_t,a_t)
$$

同时决策需要考虑到收益，我们在上图中加入reward。
$$
R(\tau)=\sum_{t=1}^Tr_t
$$

则期望收益为
$$
\bar{R_\theta}=\sum_\tau R(\tau)p_\theta(\tau)=\mathbb{E}{\tau\sim p_\theta(\tau)}[R(\tau)]
$$
求期望收益的梯度有
$$
\nabla \bar{R_\theta}=\sum_\tau R(\tau)\nabla p_\theta(\tau)=\sum_\tau R(\tau)p_\theta(\tau)\frac{\nabla p_\theta(\tau)}{p_\theta(\tau)}\
=\sum_\tau R(\tau)p_\theta(\tau)\nabla \log p_\theta(\tau)\
=\mathbb{E}{\tau\sim p_\theta(\tau)}[R(\tau)\nabla \log p_\theta(\tau)]
$$

策略梯度的计算

有两种计算方法：

蒙特卡洛采样，式(4)可以改写为如下式(5)

$$
\nabla \bar{R_\theta}\approx \frac{1}{N}\sum_{n=1}^N R(\tau^n)\nabla\log p_\theta(\tau^n)\overset{\text{式(1)}}{=}\frac{1}{N}\sum_{n=1}^N\sum_{t=1}^{T_n}R(\tau^n)\nabla\log p_\theta(a_t^n|s_t^n)
$$

时序差分更新，式(4)可以改写为如下式(6)

$$
\nabla \bar{R_\theta}\approx \frac{1}{N}\sum_{n=1}^N\sum_{t=1}^{T_n}Q^n(s_t^n,a_t^n)\nabla\log p_\theta(a_t^n|s_t^n)
$$

两者区别是策略的更新频率：MC为一回合更新一次，TD为一步更新一次。

Policy Gradient算法

基本概念

Policy Gradient算法的目的就是对$\theta$进行更新：
$$
\theta<–\theta+\eta\nabla\bar{R_\theta}
$$
不断采样，交替完成数据收集和模型参数更新两个过程。

如何理解式(5)呢？

我们记$-\sum_iY’_i·logY_i$的形式为$(Y’_i,Y_i)$两个向量之间的交叉熵，以图像分类与强化学习的损失函数为例子

图像分类问题：从损失函数到梯度计算
$$
\frac{1}{N}\sum_{n=1}^N\sum_{t=1}^{T_n}\log p_\theta(a_t^n|s_t^n)–>\frac{1}{N}\sum_{n=1}^N\sum_{t=1}^{T_n}\nabla\log p_\theta(a_t^n|s_t^n)
$$

强化学习问题：从损失函数到梯度计算
$$
\frac{1}{N}\sum_{n=1}^N\sum_{t=1}^{T_n}R(\tau^n)\log p_\theta(a_t^n|s_t^n)–>\frac{1}{N}\sum_{n=1}^N\sum_{t=1}^{T_n}R(\tau^n)\nabla\log p_\theta(a_t^n|s_t^n)
$$

对比两式可以看出

图像分类的问题中使用的是独立同分布的样本，每个样本等同看待；

而Policy Gradient问题中每个样本有单独的权重$R(\tau^n)$：若相对较重要，则$R(\tau^n)\uparrow$，反之$R(\tau^n)\downarrow$。

编程技巧

Tip1：加一个baseline（在使用时当成bias更为恰当）

若$\nabla \bar{R_\theta}$总为正数，则$R_\theta$总是在增加，因为采样的随机性往往导致不均匀的采样，没有被采样的action最终被采取的可能性相较其他action低。示意图如下：

所以不要让weight总为正数，即更改weight为$(\nabla \bar{R_\theta}-b)$，其中可以取$b=\mathbb{E}(R(\tau))$。

Tip2：正确地对不同的(state,action)的reward赋权

若是因为一个好的动作被后续坏的动作连累，或坏的动作被好的动作提携，这种现象是需要考虑道德，所以一种想法是当前的(状态,动作)对应的参数应由之后的(状态,动作)序列的收益和进行更新。

$$ \nabla \bar{R_\theta}\approx \frac{1}{N}\sum_{n=1}^N\sum_{t=1}^{T_n}[(·)-b]\nabla\log p_\theta(a_t^n|s_t^n) $$

b可以取独立于状态的值，(·)可以取$\sum_{t’=t}^{T_n}r_{t’}^n$，若是考虑未来奖励的衰减（discount $\gamma$），则(·)可以取$\sum_{t’=t}^{T_n}\gamma^{t’-t} r_{t’}^n$。

若记式(9)中[~]的式子为Advantage Function，即
$$
A^{\theta}(s_t,a_t)=\sum_{t’=t}^{T_n}\gamma^{t’-t}r_{t’}^n-b
$$
Advantage Function表现的是在$s_t$时采用$a_t$比其他action有多好。

重要性采样

on-policy与off-policy回顾

on-policy vs. off-policy

on-policy：环境互动的agent与要学习的agent是同一个（自己玩自己学）
off-policy：环境互动的agent与要学习的agent是不同的（看别人玩自己学）

policy gradient是on-policy的更新算法，但on-policy的缺点就是每次模型更新后都要采集新的训练数据，而off-policy就可以做到数据的重复使用。而on-policy转化为off-policy的重要方法就是：重要性采样。

我们从一个式子出发：
$$
\mathbb{E}{x\sim p}[f(x)]\approx\frac{1}{N}\sum{i=1}^Nf(x_i)\
=\int f(x)p(x)dx=\int f(x)\frac{p(x)}{q(x)}q(x)dx=\mathbb{E}_{x\sim q}[f(x)\frac{p(x)}{q(x)}]
$$

$x_i$是从p(x)中取样得到的样本。

这是一个统计学技巧，可以变换样本的分布。

左右两个均值只有在取样足够多的情况下才相同，若是取样不够多，则两者数值相差很大。

由于$Var[x]=E[x^2]-(E[x])^2$，

而
$$
Var_{x\sim p}[f(x)]=E_{x\sim p}[f(x)^2]-(E_{x\sim p}[f(x)])^2
$$

$$
\begin{align}
Var_{x\sim q}[f(x)\frac{p(x)}{q(x)}]&=E_{x\sim q}[(f(x)\frac{p(x)}{q(x)})^2]-(E_{x\sim q}[f(x)\frac{p(x)}{q(x)}])^2\
&=\int f^2(x)\frac{p(x)}{q(x)}p(x)dx-(E_{x\sim q}[f(x)\frac{p(x)}{q(x)}])^2\
&=E_{x\sim p}[f(x)^2\frac{p(x)}{q(x)}]-(E_{x\sim p}[f(x)])^2\

\end{align}
$$

对比式(12)与式(15)，可以看出有差距。具体sample实例可以看李宏毅老师的强化学习课程讲解。

使用重要性采样的方法，则由式(4)和式(12)可以将policy gradient的参数梯度计算公式进行修改：
$$
\nabla \bar{R_\theta}=\mathbb{E}{\tau\sim p_\theta(\tau)}[R(\tau)\nabla \log p_\theta(\tau)]–>\mathbb{E}{\tau\sim p_{\theta’}(\tau)}[\frac{p_\theta(\tau)}{p_{\theta’}(\tau)}R(\tau)\nabla \log p_\theta(\tau)]
$$

用$\theta’$进行取样，因为参数更新的是$\theta$的策略，所以通过$\theta’$取样的样本能够重复使用。

由于
$$
\nabla \bar{R_\theta}=\mathbb{E}{(s_t,a_t)\sim \pi{\theta}}[A^\theta(s_t,a_t)\nabla\log p_\theta(a_t^n|s_t^n)]\
=\mathbb{E}{(s_t,a_t)\sim \pi{\theta’}}[\frac{p_{\theta}(s_t,a_t)}{p_{\theta’}(s_t,a_t)}A^\theta(s_t,a_t)\nabla\log p_\theta(a_t^n|s_t^n)]\
=\mathbb{E}{(s_t,a_t)\sim \pi{\theta’}}[\frac{p_{\theta}(a_t|s_t)}{p_{\theta’}(a_t|s_t)}\frac{p_{\theta}(s_t)}{p_{\theta’}(s_t)}A^{\theta’}(s_t,a_t)\nabla\log p_\theta(a_t^n|s_t^n)]
$$

上式求原函数得到
$$
J_t^{\theta’}(\theta)=\mathbb{E}{(s_t,a_t)\sim\pi{\theta’}}[\frac{p_{\theta}(a_t|s_t)}{p_{\theta’}(a_t|s_t)}A^{\theta’}(s_t,a_t)]
$$

state出现的概率无法学习，直接认定各状态出现的概率相同，所以对于$\frac{p_{\theta}(s_t)}{p_{\theta’}(s_t)}$认定为常数1.

由以上我们可以看到，要避免$p_\theta$和$p_\theta’$差太多，而这里面先后出现了两种思路来达到这个目的，分别是TRPO和PPO。

Trust Region Policy Optimization(TRPO)

$$
J_{TRPO}^{\theta’}(\theta)=\mathbb{E}{(s_t,a_t)\sim\pi{\theta’}}[\frac{p_{\theta}(a_t|s_t)}{p_{\theta’}(a_t|s_t)}A^{\theta’}(s_t,a_t)]\
s.t. \quad KL(\theta,\theta’)<\delta
$$

通过一个距离度量函数$KL(·)$来度量行为上的距离，而不是参数上的距离。

Proximal Policy Optimization(PPO)

$$
J_{PPO}^{\theta’}(\theta)=\mathbb{E}{(s_t,a_t)\sim\pi{\theta’}}[\frac{p_{\theta}(a_t|s_t)}{p_{\theta’}(a_t|s_t)}A^{\theta’}(s_t,a_t)]-\beta KL(\theta,\theta’)
$$

初始化策略参数\theta^0
在每次迭代中，
	\theta^k去取样(s_t,a_t)以此计算A^{(\theta^k)}(s_t,a_t)
	最优化J_{PPO}(\theta):式(22)/(23)

$$
J_{PPO}^{\theta^k}(\theta)=\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)-\beta KL(\theta,\theta^k)
$$

这里的超参数$\beta$可以使用到Adaptive KL Penalty的技巧进行选取：

KL>KL_max，$\beta\uparrow$

KL<KL_min，$\beta\downarrow$

PPO2

$$
J_{PPO2}^{\theta^k}(\theta)=\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-\epsilon,1+\epsilon)\times A^{\theta^k}(s_t,a_t))
$$
其中clip(x,a,b)函数图像如下：