强化学习入门

由于项目需要，开始跟着李宏毅《强化学习》学习强化学习的一些内容。

强化学习

基础组件：

• Actor：决定下一步要做什么？游戏中的移动方向或攻击与否、围棋中的下棋位置等
• 环境：对手，游戏中的主机AI、围棋中的对手等
• 奖励函数：游戏中的杀怪得分、围棋中的规则等

其中，环境和奖励函数是固定的，无法控制的，唯一能控制的就是Actor采取的行为，使得奖励reward最大。

例：

observation：由环境输出，在本例中就相当于游戏画面，基本就相当于另一个说法state

这样做许多轮后，直到游戏结束(游戏规则决定，如角色被杀死等)就结束了，这称为一个episode

整个episode的奖励和为： \[ R = \sum_{t=1}^Tr_t \] 目标就是要使得\(R\)越大越好

Actor,Environment,Reward

轨迹(trajectory)：\(\tau = \{s_1,a_1,s_2,a_2,\cdots,s_T,a_T\}\)

总奖励：\(R(\tau)=\sum_{t=1}^\tau r_t\)

训练一个Actor

调整Actor使得奖励\(R(\tau)\)越大越好

使用神经网络作为Actor

输入：向量或矩阵形式的observation，对于上述例子而言就是游戏画面的像素矩阵

输出：各种可以采取的行动对应的概率，对于上述例子而言就是控制角色向左、向右或开火

最后采取概率最高的行动执行

而由于其中的Reward和Env可能相对未知，无法直接梯度下降，所以这里采用策略梯度下降(Policy Gradient)

Actor的损失

使用\(\pi_\theta(s)\)表示一个Actor，其中\(\theta\)表示网络参数，使用这个Actor去执行任务，如玩上述例子中的游戏，定义完成一局后的奖励\(R_\theta = \sum_{t=1}^T r_t\)

但是，即使是同一个Actor，每次\(R_\theta\)也是不一样的，因为Actor和游戏本身环境都具有随机性

因此，定义\(\bar R_\theta\)为\(R_\theta\)的期望值

而对于一个回合，使用\(\tau\)表示轨迹\(\{s_1,a_1,r_1,\cdots,s_T,a_T,r_T\}\)，\(R(\tau)=\sum_{n=1}^Nr_n\)，如果使用一个Actor来玩这个游戏，则每个\(\tau\)有一个被采样的概率，这个概率依赖于Actor的参数\(\theta\)：\(P(\tau | \theta)\)，所以：\(\bar R_\theta \sum_{\tau} R(\tau) P(\tau|\theta)\)

使用\(\pi_\theta\)去玩N局游戏，获得\(\{\tau^1,\tau^2,\cdots,\tau^N\}\)，相当于从\(P(\tau |\theta)\)中采样N次\(\tau\) \[ \bar R_\theta \sum_{\tau} R(\tau) P(\tau|\theta) \approx \frac{1}{N} \sum_{n=1}^N R(\tau^n) \]

Gradient Ascent

问题声明： \[ \theta^*=\arg \max_\theta \bar R_\theta \qquad \bar R_\theta=\sum_\tau R(\tau)P(\tau|\theta) \] 梯度上升：

• 开始时\(\theta^0\)
• \(\theta^1 \leftarrow \theta^0 + \eta \nabla \bar R_{\theta^0}\)
• \(\theta^2 \leftarrow \theta^1 + \eta \nabla \bar R_{\theta^1}\)
• \(\cdots\)

假设\(\theta = \{w_1,w_2,\cdots,b_1,\cdots \}\)

\(\nabla \bar R_\theta = \begin{bmatrix}\partial \bar R_\theta / \partial w_1 \\ \bar R_\theta / \partial w_2 \\ \cdots \\ \bar R_\theta / \partial b_1 \cdots \end{bmatrix}\) \[ \begin{align} \nabla \bar R_\theta &= \sum_\tau R(\tau) \nabla P(\tau|\theta) \\ R(\tau)&与\theta无关，因此不需要进行微分 \\ &=\sum_\tau R(\tau)P(\tau|\theta)\frac{\nabla P(\tau|\theta)}{P(\tau|\theta)} \\ 又因为&\frac{d \log(f(x))}{dx} = \frac{1}{f(x)}\frac{df(x)}{dx} \\ 所以\nabla \bar R_\theta &=\sum_\tau R(\tau)P(\tau|\theta)\nabla \log P(\tau|\theta) \\ &=\frac{1}{N}\sum_{n=1}^N R(\tau^n)\nabla \log P(\tau^n|\theta) \end{align} \] 而如何计算\(\nabla \log P(\tau|\theta)\)呢？ \[ \begin{align} P(\tau|\theta)&=p(s_1)p(a_1|s_1,\theta)p(r_1,s_1|s_1,a_1)p(a_2|s_2,\theta)p(r_2,s_3|s_3,a_2)\cdots \\ &=p(s_1)\prod_{t=1}^Tp(a_t|s_t, \theta)p(r_t,s_{t+1}|s_t,a_t) \\ 其中&p(s_1)、p(r_t,s_{t+1}|s_t,a_t)与Actor无关 \\ \log P(\tau|\theta)&= \log p(s_1)+\sum_{t=1}^T\log p(a_t|s_t,\theta)+\log p(r_t,s_{t+1}|s_t,a_t) \\ \nabla \log P(\tau|\theta) &= \sum_{t=1}^T\nabla \log p(a_t|s_t,\theta) \end{align} \] 所以： \[ \nabla \bar R_\theta=\frac{1}{N}\sum_{n=1}^N\sum_{t=1}^{T_n} R(\tau^n)\nabla \log P(a_t^n|s_t^n,\theta) \]

Policy Gradient

给定Actor参数\(\theta\)，收集如下数据： \[ \begin{align} \tau^1 :&(s_1^1,a_1^1) \qquad R(\tau^1) \\ &(s_2^2,a_2^1) \qquad R(\tau^1) \\ & \cdots \qquad \qquad \cdots \\ \tau^2: &(s_1^2,a_1^2) \qquad R(\tau^2) \\ &(s_2^2,a_2^2) \qquad R(\tau^2) \\ & \cdots \qquad \qquad \cdots \end{align} \] 更新参数\(\theta\)： \[ \begin{align} & \theta \leftarrow \theta + \eta \nabla \bar R_\theta \\ & \nabla \bar R_\theta = \frac{1}{N}\sum_{n=1}^N \sum_{t=1}^{T_n} R(\tau^n)\nabla\log p(a_t^n|s_t^n, \theta) \end{align} \] 使用更新后的Actor再去生成新数据，重复上述操作

如何理解这个\(\nabla \log p(a_t^n|s_t^n,\theta)\)呢？

我们知道，对于上述案例，假设它是一个分类问题，最终需要\(\min -\sum_{i=1}^3\hat y_i\log y_i\)，而这就相当于\(\max \log y_i\)

进一步：\(\log y_1 = \log p('left'|s)(s表示state)\)

即：\(\theta \leftarrow \theta + \eta \nabla \log p('left'|s)\)

用这个去解释Policy Gradient中的梯度更新过程：

假设\(R(\tau^n)=1\)，即所有奖励为1，则\(\nabla \bar R_\theta = \frac{1}{N}\sum_{n=1}^N \sum_{t=1}^{T_n} \nabla\log p(a_t^n|s_t^n, \theta)\)，\(\nabla\log p(a_t^n|s_t^n, \theta)\)表示训练数据中有一个\((s_1^1, a_1^1)\)，再假设\(a_1^1='left'\)，则希望将\(s_1^1\)输入到神经网络中后得到的输出和\(left:right:fire=1:0:0\)越接近越好，这也就变成了一个分类问题

而这里每项前面乘了一个\(R(\tau^n)\)，就相当于给这些项加了一个权重，或者是将上述的分类问题复制了对应的\(R(\tau^n)\)遍

小建议

1. 添加一个基线(baseline)

   \(\theta \leftarrow \theta + \eta \nabla \bar R_\theta\)

   \(\nabla \bar R_\theta \approx \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)\)

   有可能\(R(\tau^n)\)总是正的，理想情况所以情况都会被考虑到，对结果是没有影响的

   但实际上由于是采样，所以可能会有一些action从来都没有被采样到，这样就会导致没有被采样到的action的概率会下降，因此需要让reward并不总是正的，一种简单的方法就是：

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

   一种决定b的值方法是：\(b\approx E(R(\tau))\)

2. 给每个action合适的credit

   一个得分更高的游戏记录不一定每个行动都是最好的，而一个得分不高的记录同样也不一定每个行动都是不好的，即一边要防止学出的action仅仅是为了得分，另一边也要防止给得负分的action也分相同的权重 。

   为了给其一个合理的权重，在计算一个\((s,a\))时不将整场游戏的奖励加起来，而是只计算从该a执行后所得到的奖励，即\(\nabla \bar R_\theta \approx \frac{1}{N}\sum_{n=1}^N\sum_{t=1}^{T_n}(\sum_{t'=t}^{T_n}r_{t'}^n-b)\nabla \log p_\theta(a_t^n|s_t^n)\)

   此外，考虑到时间的因素，还会加入衰减因子\(\gamma<1\)，即

   \(\nabla \bar R_\theta \approx \frac{1}{N}\sum_{n=1}^N\sum_{t=1}^{T_n}(\sum_{t'=t}^{T_n}\gamma^{t'-t} r_{t'}^n-b)\nabla \log p_\theta(a_t^n|s_t^n)\)

   使得，离的越远，影响越小

   这里可以用\(A^\theta(s_t,a_t)\)来表示\(\sum_{t'=t}^{T_n}\gamma^{t'-t} r_{t'}^n-b\)则

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

训练一个Critic

Critic本身并不决定要采用哪个行动，而是给定一个行动\(\pi\)，评估这个actor的好坏

Critic的一种是状态价值函数(State value function)\(V^\pi (s)\)：给定actor\(\pi\)时，看到observation(state) s后直到游戏结束时累计奖励的期望值

例如：

如何估计\(V^\pi (s)\)

• 蒙特卡罗方法(Monte-Carlo based approach)

  Critic看着\(\pi\)玩游戏，例如当看到行动\(s_a\)后，直到结束累计奖励\(G_a\)，则对于\(V^\pi(s_a)\)需要和\(G_a\)越接近越好，当看到\(s_b\)后，直到结束累计奖励\(G_b\)，则对于\(V^\pi (s_b)\)需要和\(G_b\)越接近越好

• 时序差分方法(Temporal-difference approach)

  对于\(\cdots s_t,a_t,r_t,s_{t+1}\cdots\)

  \(V^\pi (s_t) = V^\pi (s_{t+1})+r_t\)

  在训练神经网络时，则对于\(V^\pi (s_t)\)和\(V^\pi(s_{t+1})\)，\(V^\pi(s_t)-V^\pi(s_{t+1})\)与\(r_t\)越接近越好

  这样就比较适合需要太多步骤的游戏或任务

另一种Critic

• 状态行动价值函数\(Q^\pi (s,a)\)

  给定actor \(\pi\)，在observation s采取行动\(a\)，到游戏结束时会得到的奖励的期望

  

• Q-Learning

  使用上述\(Q^\pi(s,a)\)就可以找出比较好的actor，这种方法就称为Q-Learning

  • 最开始是有一个初始actor \(\pi\)，使用这个\(\pi\)去和环境互动(玩游戏)
  • critic去观察actor和环境的互动，然后使用TD或MC去学出\(Q^\pi (s,a)\)
  • 找到一个比\(\pi\)更好的新的\(\pi '\)
  • \(\pi=\pi'\)，重复上述

  什么叫\(\pi'\)比\(\pi\)好？

  对于所有state s，\(V^{\pi'} \ge V^\pi (s)\)，而使用\(Q^\pi(s,a)\)去找\(\pi'\)的方法就是：\(\pi'(s)=\arg \max_a Q^\pi (s,a)\)

Actor+Critic

• Advantage Actor-Critic

  就是actor不通过奖励学习，而是通过critic学习

  

  A3C方法的第三个A：Asynchronous(异步)

  • 首先有一个全局网络(Global Network)
  • 然后复制全局网络的参数\(\theta^1\)，假设有n个分身，则复制n次
  • 每个分身分别和环境进行互动，然后分别传回\(\theta\)的更新\(\Delta \theta\)
  • 然后全局网络将所有的更新和起来一起做更新

其它

路径导向策略梯度(Pathwise Derivative Policy Gradient)

一种和GAN类似的方法

\(\pi'(s)=\arg \max_a Q^\pi (s,a)\)，其中\(a\)是一个actor的输出

逆强化学习(Inverse Reinforcement Learning)

模仿学习(Imitation Learning)

逆强化学习是模仿学习的一种，在逆强化学习中，强化学习中所谓的奖励(reward)没有了，有的只是专家的演示，以游戏为例，就是有游戏高手玩游戏给模型看

动机

事实上多数现实中的例子都是没有reward的，例如自动驾驶、聊天机器人等都无法明确的规定reward的值，因此如果强行加入reward就会导致学出一些不适合的模型。

逆强化学习

在逆强化学习中，存在：

• 专家的演示：\(\hat \tau_1,\hat \tau_2,\cdots,\hat \tau_N\)
• 环境env

然后推出奖励函数(reward function)，然后使用推出的奖励函数去找到最优actor

存在一个原则：老师永远是对的

基本思想：(也有点类似GAN)

• 初始化一个actor
• 在每次迭代中：
  • 这个actor与环境交互，获得一些游戏记录
  • 定义一个奖励函数，来使得老师的游戏记录比actor的游戏记录更好
  • 基于新的奖励函数，actor学习得到最大化奖励
• 输出奖励函数和从奖励函数学到的actor