用马里奥推导RL基础理论

基础定义

• $\pi(a| s)$: 在状态$s$下，做出策略$a$的概率分布，这就是一个策略函数，采样选择策略；在马里奥游戏中，就是只当前状态下，是选择左右移动还是选择跳；

• $V(s)$: 价值函数，指在状态$s$下，之后所能累计取得收益的期望；在游戏中，指当前位置下，到游戏结束，所能拿到的分数总和；

• On Policy: 在收集数据的同时优化当前策略。在游戏中，指当前游戏还没结束，就开始根据历史分数奖励优化策略；

• Off Policy：在收集完整的一组数据后才开始优化策略。在游戏中，就是指一定要玩完一整局游戏，拿到最终的分数之后，才把历史数据汇总，优化策略；

• 优势函数：$A(s_t, a_t) = Q(s_t, a_t) - V(s_t)$: $Q(s_t, a_t)$表示在状态$s_t$下采用$a_t$策略，进入下一个状态后，未来所能累计取得的收益的期望，那么明显，如果当前采取的策略$a_t$，比当前状态$s_t$的平均未来收益更高，那就是个好策略。比如，马里奥的头顶有个金币，选择跳能在未来提供更多分数，选择不跳就错过了，未来分数就少，那肯定是跳更好。

RL的所有理论推导，都在围绕一件事，如何优化$\pi(a|s)$策略函数，让$\pi(a |s)$在每个状态都能选择对未来最有利的策略。

假如存在全知全能的价值函数$V(s_t)$, 知道每个状态下的价值，那就好办了，在当前状态下，遍历所有可能的策略，看哪个策略进入的下一个状态，所能带来的优势增量最多就好了。可惜，$V(s_t)$是很难直接定义的, 每人可以预知未来。

蒙特卡洛方法

基于蒙特卡洛方法进行RL训练,就是希望找到一个策略$\pi(a |s)$，可以最大化奖励分数。

在S状态下，采用a动作后，未来所能获得的收益分数的总和：$Q(s, a) = E_{\pi} [\sum_{k = 0} \gamma^k r_{t + k +1}]$

在马里奥玩完一整局游戏后，得到序列$[s_1, a_1, r_2, s_2, a_2, .... ]$ ，游戏的每一时刻的奖励都记录在案，那么某一状态下的未来累计收益期望也就好算了：$G_t = r_{t + 1} + \gamma r_{t + 1} + \gamma^2 r_{t + 2} + ...$

下面就是用蒙特卡洛方法来优化策略函数了: $Q(s, a) \leftarrow Q(s_t, a_t) + \alpha \cdot (G_t - Q(s_t, a_t))$

解释：

• 原来的$Q(s_t, a_t)$是预估出来的，预估未来能拿到这么多的累计收益；

• $G_t$是游戏结束后，真真实实算出来的，在$s_t$状态，采用$a_t$动作，未来拿到的累计收益

• 那么按照差值去更新，拟合真实值就好啦

• $\alpha$为学习步长

这样就完成了一次策略函数的更新。那么下一步呢？再玩一局马里奥，再拿到一轮的序列和每一个过程的分数。

不过，为了保证模型不陷入局部最优解，可以考虑让马里奥再状态$s$下，$\pi(a |s)$按照$1 -\epsilon$ 的概率取最大值，确保可以有一定概率尝试新动作。

时间差分方法

蒙特卡洛方法虽好，但是玩一整局游戏才能训练一次，在大型游戏中，玩完一局不知道要耗时多久，所以希望有一种方式，在游戏中，就能根据历史状态序列进行策略函数的优化，这里就是时间差分。

一样滴，也是希望找到一个$\pi(a |s)$能够使$Q(s, a)$能够最大

更新策略：$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \cdot[r_{t + 1} + \gamma Q(s_{t + 1}, a_{t + 1}) - Q(s_t, a_t)]$

训练过程：在状态$s_t$， 采用动作$a_t$, 获取奖励$r_{r + 1}$, 进入下一个状态$s_{t + 1}$, 那么就能对$Q(s_t, a_t)$进行更新

注意：$Q(s_t, a_t)$都是随机初始化的，但即使是随机初始化的，用$Q(s_{t + 1}, a_{t + 1})$来更新$Q(s_t, a_t)$也是合理的，在足够长时间的训练，$Q(s_t, a_t)$的更新是依赖真是环境的奖励函数和状态转移概率的，是可以收敛的。

更严谨的证明是贝尔曼期望方程的递归性质，由于这个推导复杂了，这里就不再深入。

在训练一轮完成后，下一轮采样动作的时候，依然和蒙特卡洛方法类似，需要进行$\epsilon$贪心策略，确保仍然有机会探索新策略

PPO（Proximal Policy Optimization）

在解决了训练慢的问题，RL的训练依然存在很多其他问题，比如训练不稳定，策略梯度更新过大时，就很容易让模型策略崩塌，从一个极端走向另外一个极端。举个例子，马里奥发现不动就不会死，干脆直接摆烂，这样分数至少不是负数。

现象理解了，那么解决办法也就浮出水面了，限制策略函数的更新幅度，步子不能太大，那么可以采用KL散度来量化两个分布的差异，限制到一定范围即可。

推导：