关于强化学习的数学基础

讲个故事

自从谷歌的强化学习机器人AlphaGO战胜了围棋大师后，强化学习进入了人们的视野，这种学习的方式在神经网络的基础上融会贯通，实现了一种探索的方式，这种思路未来可能会应用于元胞自动机的最优解试探中，未来有机会肯定会写一篇这样的论文，不过现在先了解一下什么是强化学习

强化学习简称RL，与ML，DL统称三大学习，他们都使用了ANN结构，知道这些你就知道学习的方向了。

基础

强化学习的本质思想就是通过收益去计算价值进一步估计后来的价值，通过让价值最大化，得到最优解。

强化学习的基础公式为贝尔曼方程，
$$
V(\pi|a)=R(a)+ \gamma\sum p(s’|s)V(s’)
$$
首先解释一下字母的含义，$\pi$表示一个决策的方案，如果他传递的是一个行为，比如吃法，那么返回的就是这个行为的概率，如果什么都不传递，表达的是一种抽象的行为。

s是state的首字母，表达环境或状态，比如阴天或者下雨。V表示价值，R(a)表达动作a产生的回报。$\gamma$一般被叫做折扣因子，或者叫磨损率，削弱过去或未来价值对决策的干扰。

我们简单证明一下

首先我们要知道价值函数在干嘛：他是在估计价值，一般估计都是用平均值，所以我们可以知道价值期望：
$$
V_{n+1}(a)= \frac{1}{n}\sum R_n
$$

$$
V_{n+1}(a)= \frac{1}{n}(R_n + \sum R_{n-1})
$$

$$
V_{n+1}(a)= \frac{1}{n}(R_n + \frac{1}{n-1}(n-1)\sum R_{n-1})
$$

$$
V_{n+1}(a)= \frac{1}{n}(R_n + (n-1)V_{n-1}(a))
$$

$$
V_{n+1}(a)= \frac{1}{n}(R_n + nV_{n-1}(a) - V_{n-1}(a))
$$

$$
V_{n+1}(a)= V_{n-1}(a) + \frac{1}{n}(R_n - V_{n-1}(a))
$$

我们只需要让$\frac{1}{n}$为一个参数即可。使用这种关系，我们可以得到一个关系：
$$
价值=步骤回报+折损·时间内的价值期望
$$
利用这种关系就有贝尔曼方程。这样我们就知道了强化学习的基本方式，就是通过不断计算在当前状态下，采取何种行为才能让V最大化，也就是收益最大化。

---

第二个就是马尔可夫价值，一般使用Q函数表示，写法类似贝尔曼方程:
$$
Q_\pi(s,a)=R(s,a)+\gamma\sum p(s’|s,a)V(s’)
$$
对应含义类似，不过不需要考虑决策方式了，只需使用已知状态递推Q价值即可，当然这些已知的Q我们都会使用一个表格存储起来，我们叫他Q表格，他能够存储环境状态和行为对应的价值。

Q(s,a)	打游戏	吃饭	约会
下雨	10	8	2
晴天	4	7	9

如果你有很好的算法基础，不难看出这种方法和动态规划大同小异，其实马尔可夫价值就是通过动态规划实现的。

---

第三个，我们先思考强化学习的目的是为了得到最优的步骤，我们可以通过定义行为的价值，通过让价值最大化完成我们的步骤。但是如何获取我们的步骤呢？

我们首先给Q函数变形我们期望的样子：
$$
Q_k(s,a)=R(s,a)+\gamma \sum p(s’|s,a)V_k(s’)
$$
其中的$V_k$函数就是我们获取最佳行为的途径，我们知道V和Q都表示价值，所以我们可以使用递推方式改变Q函数，最佳的方法肯定是价值最大的方向，所以我们获取一下最大价值。
$$
V_k(s)={max} Q_k(s,a)
$$
这样我们就得到了最佳策略的表达式：
$$
\pi(s)=argmax [R(s,a)+\gamma \sum p(s’|s,a)V(s’)]
$$

小小总结一下

通过这些不同价值函数的写法，我们能看出其中精髓部分就是形如：
$$
Q_{n+1} = Q_n + \gamma(R_n-Q_n)
$$
的递推公式。$R_n$为n步的收益，$Q_n$为n步的价值。

方法

动态规划是最基础的方法，首先我们需要有一个专家系统，能实时评估我们行为的价值，当然这个专家可以是各种东西，神经网络、苦命的工具人、传感器，都可以。策略评估使用历史预测未来的价值，计算使用贝尔曼方程。

动态规划有两个迭代，一个是策略迭代：
$$
\pi(s)=argmax [R(s,a)+\gamma \sum p(s’|s,a)V(s’)]
$$
另一个就是价值迭代：
$$
V(s)=max_a\sum p(s’|s,a)[r+\gamma V(s’)]
$$
迭代可以获得最优的策略，使用这个策略能获得价值最大，这就是我们所需要的方法。

---

第二种就是蒙特卡洛方法，这种方法是一种随机采样的方法，核心的计算为：
$$
G=\gamma G + R_{t+1}
$$
G为历史的收益期望，R为当前回报。这种方法意味着我们需要单独为收益进行试探，通过得到何种步骤的价值最大进行决策。

方法的获取我们需要一个策略，在进行计算价值的过程中，根据我们所使用探索体的数目区分为同轨策略和离轨策略，前者意味着学习和探索都是一个函数来完成的，后者表示学习过程拆分为探索体和学习体，学习体负责记忆和整合，探索体就负责计算价值。这样我们可以使用一种取得函数局部最大值方法：梯度上升，计算最多价值的行为。

不同关于强化学习的书对这两种名字叫法都不一样，同策略就是同轨策略，异策略就是离轨策略，目的相同

学习

学习主要使用的就是时序差分方法，我们看到Q函数的价值是基于全局的价值，如果只截取部分值就可以得到部分价值的递推，也就是小区域时间内的最优解。
$$
G=r+\sum r^nV(s)
$$
经过对比贝尔曼方程的差别，我们发现这种方法满足最开始证明的格式。
$$
V(s_t)=V(s_t)+\alpha (r+\gamma V(s_{t+1}) - V(s_t))
$$
这种方法会有一定误差，我们截取后面差的部分作为迭代差，通过它就可以让模型趋于收敛：
$$
\delta = r_{t+1}+\gamma V(s_{t+1}) - V(s_t)
$$
同理蒙特卡洛方法可以升级为：
$$
V(s_t) = V(s_t)+\alpha (G_t-V(s_t))
$$
我们可以实现一种异策略或离轨策略的时序差分学习，这种学习叫他Q学习，我们需要一个学习体和探索体。
$$
Q(s_t,a_t)=Q(s_t,a_t)+\alpha[R_{t+1}+\gamma max_aQ(s_{t+1.a})-Q(s_t,a_t))]
$$
如果提取Q学习的规律使用同轨策略或者叫同策略，就有Sarsa方法，与时序差分法一样，我们将V函数换做Q函数。
$$
Q(s,a) = Q(s,a)+\alpha (r+\gamma Q(s’,a’) - Q(s,a))
$$
我们定义Sarsa的回报为$Q_t^\lambda$：
$$
Q_t^\lambda=(1-\lambda)\sum_{n}^∞ \lambda ^{n-1}Q_t^n
$$
所以我们可以简化Sarsa的写法为：
$$
Q(s_t,a_t)=Q(s_t,a_t)+\alpha (Q_t^\lambda - Q(s_t,a_t))
$$
其中状态下的最佳策略为：
$$
\pi(s_{t+1})=argmax_aQ(s_{t+1},a’)
$$
所以我们又可以进行一次变形：
$$
Q(s_t,a_t)=Q(s_t,a_t)+\alpha (r_{t+1} + \gamma[max_aQ(s_{t+1},a)] - Q(s_t,a_t))
$$
一般的时序差分学习(TD)，也可以叫做Q学习，这与后面的深度Q网络有密不可分的关系。

Q学习还有一种特殊的情况，如果我们把s拆分为两部分，一部分是成立状态，另一部分反之，这样我们就可以同时使用两个Q学习进行学习了
$$
Q_1(s_t,a_t)=Q_1(s_t,a_t)+\alpha [R_{t+1}+\gamma Q_2]
$$

对比	Sarsa	Q学习
更新方向	使用下一步的行为	使用探索体得到的动作
过程	选取下一步的a，观测r和s’并计算Q，更新s,a	从所有s中选择a，执行观测s’和a计算Q值，更新s

---

更泛化的例子

如果我们假设对于时序差分学习有有限步骤的，那么我们叫它n步自举法，我们知道收益本身是按照状态-回报序列加权求和得到的，我们取其中的部分得到了某一步的回报，如果他是n步且我们让这n步的回报最大，我们就得到了回报更新公式：
$$
G_t=(1+R_{t+n})^n=R_{t+1}+\gamma R_{t+2}+\gamma ^2R_{t+3}…+\gamma ^{T-t-1}R_T
$$

$$
V_{t+n}(s_t)=V_{t+n-1}(s_t)+\alpha [G_{t:t+n}-V_{t+n-1}(s_t)]
$$

当然对于Sarsa方法也可以使用n步自举法，它可以写作一个严格的TD形式：
$$
Q_{t:t+n}=Q_{t-1}(s_t,a_t)+\sum_{k=t}^{min(t+n,T)-1}\gamma ^{k-t}[R_{k+1}+\gamma Q_k(s_{k+1},a_{k+1})-Q_{k-1}(s_k,a_k)]
$$
这两种泛例的使用依然是选取a观察下一时刻的R和S保存，如果步骤大于n则使用Q函数递推最大的A，否则就使用存储的动作。

---

逼近价值函数可以有两种办法，第一种是同轨逼近，我们定义它为V函数，假设状态的分布遵循规律μ，我们有误差VE：
$$
\bar {VE}(\theta)=\sum_{s∈S}\mu(s)[v_\pi(s)-\hat v(s,\theta)]^2
$$
定义损失函数我们的目的是优化$\theta$，它可以是任意参数所以我们需要一种和梯度下降法相似的方法：随机梯度下降。
$$
\theta_{t+1}=\theta_t+\alpha[v_\pi(S_t)-\hat v(S_t,\theta_t)]\nabla\hat v(S_t,\theta_t)
$$
我们给梯度加入一个参数，我们就得到了一般的半梯度方法：
$$
\theta_{t+1}=\theta_t+\alpha \rho_t\delta_t \nabla\hat v(S_t,\theta_t)
$$

$$
\rho_t=\frac{\pi(A_t|S_t)}{\pi_{old}(A_t|S_t)}
$$

$$
\delta_t=R_{t+1}+\gamma \hat v(S_{t+1},\theta_t)-\hat v(S_t,\theta _t)
$$

而Sarsa方法的半梯度写起来也十分简单：
$$
\theta_{t+1}=\theta_t+\alpha \delta_t \nabla\hat q(S_t,A_t,\theta_t)
$$

$$
\delta_t=R_{t+1}+\gamma \sum \pi(a|S_{t+1})\hat q(S_{t+1},a,\theta_t)-\hat q(S_t,A_t,\theta_t)
$$

对于持续性的Sarsa我们需要修改为：
$$
\delta_t=R_{t+1}-R_t+\sum \pi(a|S_{t+1})\hat q(S_{t+1},a,\theta_t)-\hat q(S_t,A_t,\theta_t)
$$

策略梯度与PPO

我们知道了Q学习是使用下一状态最大收益的价值进行更新，Sarsa穷举了所有的状态进行更新，我们接下来介绍一下策略梯度的算法，我们给出一个状态s，在分布f的影响下得到对应行为a的概率p(a|s)，其中f包含参数$\theta$，我们列举出整条轨迹概率的变化得到资格迹：
$$
p_\theta(\tau)=p(s_1)\Pi_{t=1}^Tp_\theta(a_t|s_t)p(s_{t+1}|s_t,a_t)
$$
我们得到期望收益的关系（使用了概率的意义）：
$$
\hat R_\theta=\sum_\tau R(\tau)p_\theta(\tau)
$$
我们求出它的梯度为：
$$
\nabla \hat R_\theta = \sum_\tau R(\tau)\nabla p_\theta(\tau)
$$
因为p是不可以微的，所以我们需要使用对数进行计算，如同似然函数一样。
$$
\nabla \hat R_\theta = E[R(\tau)\nabla logp_\theta(\tau)]
$$
打开表达式就得到了：
$$
\nabla \hat R_\theta=\frac{1}{N} \sum_{n=1}^N\sum_{t=1}^TR(\tau ^n)\nabla log p_\theta(a_t^n|s_t^n)
$$
这样我们得到了策略梯度。PPO算法也是使用这样的方式进行的，我们已经知道是$\tau$的分布，我们更改为状态和行为，同时引入一个控制项，我们就得到了PPO的J函数，他和策略梯度是一样的。
$$
J^{\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)
$$

$$
J_{PPO}^{\theta^k}(\theta)=J^{\theta^k}(\theta)-\beta KL(\theta,\theta’)
$$

因为$\theta$需要逼近$\theta’$，所以使用KL散度来衡量距离，同时加入了类似于正则化的写法，可以用作损失函数。

最后关于奖励的设置需要遵守以下规则：

• 使用合理的方式指定相关的价值逼近，如果是走迷宫则距离变近，价值增加
• 奖励根据需要实现的目标来设置，同时需要考虑系数奖励
• 奖励不能过去全局化，也需要加入势能项

总结

这篇博文我们着重介绍了强化学习主要使用的方程和学习的方法，阅读这篇博文后读者可以清楚的了解到贝尔曼方程的诞生，以及强化学习的目的：得到能够获得更多价值的策略。

文中详细介绍了贝尔曼方程，时序差分学习，Q学习和Sarsa。只要完成这些内容的代码，读者也可以写出一个媲美AlphaGO的机器人。