1. RL几个应用

Learning to play AlphaGo

Supervised（监督学习的方式）
- 从老师那里学习，即通过打标签的方式学习
- 比如看棋谱学，但棋谱是人下的，人下的那一步就是最优的吗？
Reinforement Learning
- 从经验中学习，其实人可能都不知道哪一步是最优的
AlphaGo的学习方式
- 先做Supervised Learning，从高手棋谱中学习
- 通过Supervised Learning训练出两个模型，他们互相博弈

Learning a Chat-Bot

如何评判生成句子的好坏是关键问题，总不能一直“See you”循环下去。
预测将来可能出现的做法
- 在RL中引入生成对抗网络
- 判别生成的句子是否符合真实数据的分布

Playing Video Game

两个常用的游戏平台
- Gym
- Universe
episode，一局游戏，从开始到结束

2. RL的概念

RL的难点

Reward Delay 奖励延迟

比如，打飞机游戏中，只有开火才会拿到Reward，但左右操作不会。但左右操作又会影响最后得分的高低，毕竟就算一直开火而不躲避也会导致被子弹击中从而导致游戏结束。所以，这就需要机器能够合理规划以获得长期的利益。
Agent采取的行为会影响之后的行为

Agent需要充分的探索它所处的环境。还是以打飞机游戏为例，若是Agent从来都没有尝试过开火，那么它永远无法得到高分。

RL常用的做法

Policy-Based，主要目的是学习一个Actor
Value-Based，主要目的是学习一个Critic
那现在比较流行的做法是：Actor + Critic

3. RL三个步骤

Neural Network as Actor

Input：机器的观察，Vector或者是Matrix
OutPut：输出层每一个神经元代表一个动作

Goodness of Actor 1

给定一个Actor $\pi\theta(s)$，神经网络就是Actor，参数为$\theta$ 。使用$\pi\theta(t)$来玩游戏，那么总体的Reward如下：
$Total~Reward : R_\theta = \sum_{t=1}^Tr_t$
由于环境是一直在变化的（输入会变），比如打游戏玩家不同的位置、画面等，所以就算是同一个Actor玩千百次游戏最后得到的$R\theta$也会不一样。而强化学习的目的是最大化Reward从而选择出最佳的Actor，那么直接最大化$R\theta$是没有意义的，而应该最大化所有$R_\theta$的期望。
定义$\bar{R}\theta$为$R\theta$的期望值，所以最终的目的应该是最大化$\bar{R}_\theta$。当玩的所有局获得的Reward期望最大时，就说明这个Actor整体上达到了较好的能力。（可用随机放回采样钞票来类比，若是整体期望很大，那么盒子里钞票值普遍都比较大，即Reward普遍比较大）。

Goodness of Actor 2

将一个episode考虑为一个$\tau$，即一场游戏的开始到结束这个过程。这个过程有千百种，有些经常出现，有些不太出现。$\tau$的定义如下：
$\tau = \{s_1, a_1, r_1, s_2, a_2, r_2, ..., s_T, a_T, r_T\}$
其中$s_i$代表当前的状态，$a_i$代表采取的动作，$r_i$代表收获的Reward。
当一个Actor开始玩游戏的时候，每一个$\tau$都有一定的概率出现，我们用$P(\tau|\theta)$来代表不同的$\tau$出现的概率。那么所有$R_\theta$的期望为：
$\bar{R}_\theta = \sum_{\tau}R(\tau)P(\tau|\theta)$
这个公式的理解方式类比于离散随机变量求期望：假设可以穷举所有的$\tau$，那么$\bar{R}_\theta$应该为每种$\tau$出现的机率乘上该$\tau$能够获取的总体Reward的总值。
对$\bar{R}\theta$的进一步思考：由于总体的目标是希望选择的Actor在不同的$\tau$下都能够获得尽可能高的$Reward$，那么使得$\bar{R}\theta$最大的那个Actor就是我们所需要的。
由于前穷举所有的$\tau$可能性很低，那么只能用一个Actor玩N场游戏得到$\{\tau^1, \tau^2, …, \tau^3\}$来类比所有的$\tau$。也就相当于从$P(\tau|\theta)$中采样N次，那么每个$\tau$出现的概率应该为$\frac{1}{N}$，所以$\bar{R}_\theta$近似为：
$\bar{R}_\theta = \sum_tR(\tau)P(\tau|\theta) \approx \frac{1}{N}\sum_1^NR(\tau^n)$
相当于把N个$\tau$的$R(\tau)$求和并取平均。

Pick the best Actor 1

根据前文，已将问题转化为：
$\theta^* = arg~\underset{\theta}{max}\bar{R}_\theta = arg~\underset{\theta}{max}~\sum_{\tau}R(\tau)P(\tau|\theta)$
那么就可以采用梯度上升来更新模型的参数
- Start with $\theta^0$
- $\theta^1 = \theta^0 + \eta\nabla\bar{R}_{\theta^0}$
- $\theta^2 = \theta^1 + \eta\nabla\bar{R}_{\theta^1}$
- ……
其中$\nabla\bar{R}\theta = \left[\begin{matrix} \part\bar{R}\theta/\part W1 \\ \part\bar{R}\theta/\part W2 \\ … \\ \part\bar{R}\theta/\part b_1\end{matrix}\right]$

Pick the best Actor 2

那么$\nabla\bar{R}_\theta$到底该怎么求呢？

根据$\bar{R}_\theta$的公式，可以得到：
- 其中，$R(\tau)$和$\theta$并没有关系，所以不需要求梯度。因为Reward是环境给的，比如游戏中的计分板，我们不需要计分的具体过程和规则，只要拿到值就可以了。
- 所以即使$R(\tau)$不可微，不知道其具体的$function$也没有关系，只要给了输入能够给输出就行。
再进一步看上面的式子，可以推导出：
$\nabla\bar{R}_\theta = \sum_\tau R(\tau)\nabla P(\tau|\theta) \\ = \sum_\tau R(\tau)P(\tau|\theta)\frac{\nabla P(\tau|\theta)}{P(\tau|\theta)} \\ \approx \frac{1}{N}\sum_{n=1}^N R(\tau^n) \nabla\log P(\tau^n|\theta)$
约等于已在上文解释，因为无法穷取所有的$\tau$，故只能采样类比。那么每个$\tau$出现的概率应该为$\frac{1}{N}$，可以提到求和前面。

Pick the best Actor 3

根据上文的推导，问题就转化为了$\nabla\log P(\tau^n|\theta) = ?$，那么该怎么求呢？

前文定义$\tau = \{s_1, a_1, r_1, s_2, a_2, r_2, …, s_T, a_T, r_T\}$，故可以得到：
- $P(s_1)$代表游戏开始画面出现的几率
- $P(a_1|s_1, \theta)$代表$\theta_1$下的Actor，在$s_1$状态下，取动作$a_1$的机率
- $P(r_1,s_2|s_1, a_1)$代表，在$s_1$状态下采取动作$a_1$，获取$r_1$并指向状态$s_2$的概率
那么，上面的式子可以进一步写为：
$P(\tau|\theta) = P(s_1)\prod_{t=1}^TP(a_t|s_t, \theta)P(r_t, s_{t+1}|s_t, a_t) \\ = \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)$
其中$\log P(s1)$和$\log P(r_t, s{t+1}|s_t, a_t)$都是与$\theta$无关的项，与游戏环境相关。
于是，可以得到：
$\nabla \log P(\tau|\theta) = \sum_{t=1}^T \nabla \log P(a_t|s_t, \theta)$

Pick the best Actor 4

根据上文的推导，最终的问题可以转化为如下式子：

$\nabla \bar{R}_\theta \approx \frac{1}{N}\sum_{n=1}^N R(\tau^n) \nabla\log P(\tau^n|\theta) \\ = \frac{1}{N}\sum_{n=1}^N R(\tau^n) \sum_{t=1}^{T_n} \nabla \log P(a_t^n|s_t^n, \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)$

最后得到的一项式子是非常直觉的，可以体现学习过程中很多重要的信息，将在下面一一列出。

机器在$\tau^n$过程中，在$s_t^n$的状态下采取行动$a_t^n$导致
- $R(\tau^n)$为正，则希望这个$a_t^n$出现的机率越大越好，需调整$\theta$来增加$P(a_t^n|s_t^n)$
- $R(\tau^n)$为负，则希望这个$a_t^n$出现的机率越小越好，需调整$\theta$来降低$P(a_t^n|s_t^n)$
$P(a_t^n|s_t^n, \theta)$的意思是：在某一$\tau$过程中，在$t$时刻的所观测的状态$s_t^n$，采取动作$a_t^n$的概率。
- 但$P(a_t^n|s_t^n, \theta)$乘以的是该$\tau$整体的Reward $R(\tau^n)$，而不是当前时刻$t$采取行动后的Reward $R(\tau^n_t)$
- 所以，训练完毕后的Actor每次采取的动作往往是为了最大化整体的利益，而不是局部的利益。这就可以避免前文提到的问题：打飞机只有开火才能获得Reward，而左移、右移不会有任何Reward，但会对最大化Reward有帮助，所以机器每次做的决策要考虑全局而不是一直开火。
$\nabla \log P(a_t^n|s_t^n, \theta)$为什么要取$\log$?分母$P(a_t^n|s_t^n, \theta)$的作用是什么呢？
- 举个例子，如有以下的$\tau$过程
  - $\tau^{13}$，采取行动a，$R(\tau^{13}) = 2$
  - $\tau^{15}$，采取行动b，$R(\tau^{15}) = 1$
  - $\tau^{17}$，采取行动b，$R(\tau^{17}) = 1$
  - $\tau^{33}$，采取行动b，$R(\tau^{33}) = 1$
- 虽然动作a会有更高的Reward，但由于动作b出现次数很多，在求和所有R之后，b动作带来的总Reward会更高；这就导致机器将b出现的机率调高，以获得总体的Reward更高。故虽然a可以获取更高的Reward，机器也会限制它的发生机率。
在看了上述例子之后，我们再回头解释分母$P(a_t^n|s_t^n, \theta)$存在的意义，其实$\frac{\nabla P(a_t^n|s_t^n, \theta)}{P(a_t^n|s_t^n, \theta)}$相当于对各种action出现的次数做了normalize，从而使得机器不会偏好出现次数过高的action，而是综合评价出现次数和单次行动获得的Reward。

通过上述对目标函数直观的解释和理解，我们可以发现目标函数不仅保证了全局利益，也能保证得到做出合理决策的Actor。

Add a Baseline 1

若是$R(\tau)^n$一直为正，会发生什么事情？

理想状态下，不会有什么问题。若有三个动作a、b、c，通过充分的采样，三个动作都发生了，那么三个动作在进行梯度下降的时候都会有相应的提升。
但若采样不充分，导致某个动作没有发生如动作a没有发生，就会使得动作b、c的机率增加，而a的机率减小。所以，我们希望$R(\tau^n)$有正有负，那么可以添加一项$b \approx E(R(\tau^n))$。
$\nabla \bar{R}_\theta = \frac{1}{N}\sum_{n=1}^N \sum_{t=1}^{T_n} (R(\tau^n) - b)\nabla \log P(a_t^n|s_t^n, \theta)$

Add a BaseLine 2

假设有两个$\tau$的片段如下：
- $(s_a, a_1, r=5),~(s_b, a_2, r=0),~(s_c, a_3, r=-2), ~ R=3$
- $(s_a, a_1, r=-5),~(s_b, a_2, r=0),~(s_c, a_3, r=-2), R=-7$
在上面两个例子中，执行$a_2$并不会获得太差的Reward。但在原始的Policy Gradient中，乘上的权重为$R(\tau^n)$，即一场游戏的总Reward，这虽然能考虑全局收益，但同时拉低了某些好的action出现的概率，从而使得当前Actor出现偏好。
如在上述的例子中，$a_2$之前采取的动作其实和$a_2$将产生的结果并没有任何关系，$a_2$之后产生的结果只和$a_2$之后的动作相关。故可以修改Policy Gradient为：
$\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 logP_\theta(a_t^n|s_t^n)$
即将权重从全局的Reward修改为，采取动作$a_t$之后所有Reward的总和
再进一步，由于当前的action对后续动作的影响会随着时间的推移而逐渐减弱，故需要乘上一个衰减因子$\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 logP_\theta(a_t^n|s_t^n)$
中间的那一项称之为Advantage Function，即
$A^\theta(s_t, a_t) = \sum_{t^{'}=t}^{T_n}\gamma^{t^{'}-t} r_{t^{'}}^n - b$