常见强化学习方法总结

原文: http://zhuanlan.zhihu.com/p/98962807

花了一天时间大致了解了强化学习一些经典算法，总结成如下笔记。笔记中出现不少流程图，不是我自己画的都标了出处。
另外，如果知乎显示不正常，可以去我的博客查看这篇文章。
版权声明：本文为原创文章，未经允许不得转载！

铺垫

1. Bellman方程

在介绍强化学习算法之前先介绍一个比较重要的概念，就是Bellman方程，该方程表示动作价值函数，即在某一个状态下，计算出每种动作所对应的value（或者说预期的reward）。

![ \begin{aligned} v(s) &=\mathbb{E}\left[G_{t}

S_{t}=s\right] \\ &=\mathbb{E}\left[R_{t+1}+\lambda R_{t+2}+\lambda^{2} R_{t+3}+\ldots

S_{t}=s\right] \\ &=\mathbb{E}\left[R_{t+1}+\lambda\left(R_{t+2}+\lambda R_{t+3}+\ldots\right)

S_{t}=s\right] \\ &=\mathbb{E}\left[R_{t+1}+\lambda G_{t+1}

S_{t}=s\right] \ \&=\mathbb{E}\left[R_{t+1}+\lambda v\left(S_{t+1}\right)

S_{t}=s\right] \end{aligned}](https://www.zhihu.com/equation?tex=+%5Cbegin%7Baligned%7D+v%28s%29+%26%3D%5Cmathbb%7BE%7D%5Cleft%5BG_%7Bt%7D+%7C+S_%7Bt%7D%3Ds%5Cright%5D+%5C%5C%5C+%26%3D%5Cmathbb%7BE%7D%5Cleft%5BR_%7Bt%2B1%7D%2B%5Clambda+R_%7Bt%2B2%7D%2B%5Clambda%5E%7B2%7D+R_%7Bt%2B3%7D%2B%5Cldots+%7C+S_%7Bt%7D%3Ds%5Cright%5D+%5C%5C%5C+%26%3D%5Cmathbb%7BE%7D%5Cleft%5BR_%7Bt%2B1%7D%2B%5Clambda%5Cleft%28R_%7Bt%2B2%7D%2B%5Clambda+R_%7Bt%2B3%7D%2B%5Cldots%5Cright%29+%7C+S_%7Bt%7D%3Ds%5Cright%5D+%5C%5C%5C+%26%3D%5Cmathbb%7BE%7D%5Cleft%5BR_%7Bt%2B1%7D%2B%5Clambda+G_%7Bt%2B1%7D+%7C+S_%7Bt%7D%3Ds%5Cright%5D+%5C+%5C%5C%26%3D%5Cmathbb%7BE%7D%5Cleft%5BR_%7Bt%2B1%7D%2B%5Clambda+v%5Cleft%28S_%7Bt%2B1%7D%5Cright%29+%7C+S_%7Bt%7D%3Ds%5Cright%5D+%5Cend%7Baligned%7D)

上面公式中：

s表示一个具体的状态值,很自然 $S_t,S_{t+1},…$ 就是表示当前时刻，下一时刻和下下一时刻,…,的状态
$R_{t+1}$ 表示在t+1时刻所获得的奖励，其他同理
$G_t$ 表示t时刻总的回报奖励，因为当前时刻做的某一个决定，未来不同时刻都会有不同形式的奖励。（或者也可以这么理解：前面 $G_t$ 代表的是当前时刻某一个动作所带来的的奖励，而 $v(s)$ 就表示在当前时刻的一个奖励期望，即综合考虑所能采取的所有动作之后我们所能获得的奖励，我们把 $v(s)$ 称为value function

上面这个公式就是Bellman方程的基本形态。从公式上看，当前状态的价值和下一步的价值以及当前的反馈Reward有关。它表明价值函数（Value Function）是可以通过迭代来进行计算的!!!

2. 动作价值函数

前面介绍的Bellman方程是价值函数，它直接估计的是某个状态下所有动作的价值期望，但是如果我们能够知道某个状态下每个动作的价值岂不是更好？这样我们可以选择价值最大的那个动作去执行，所以就有了动作价值函数（action-value function），它的表达形式其实是类似的：

![\begin{aligned} Q^{\pi}(s, a) &=\mathbb{E}\left[r_{t+1}+\lambda r_{t+2}+\lambda^{2} r_{t+3}+\ldots

s, a\right] \ \&=\mathbb{E}_{s^{\prime}}\left[r+\lambda Q^{\pi}\left(s^{\prime}, a^{\prime}\right)

s, a\right] \end{aligned} ](https://www.zhihu.com/equation?tex=%5Cbegin%7Baligned%7D+Q%5E%7B%5Cpi%7D%28s%2C+a%29+%26%3D%5Cmathbb%7BE%7D%5Cleft%5Br_%7Bt%2B1%7D%2B%5Clambda+r_%7Bt%2B2%7D%2B%5Clambda%5E%7B2%7D+r_%7Bt%2B3%7D%2B%5Cldots+%7C+s%2C+a%5Cright%5D+%5C+%5C%5C%26%3D%5Cmathbb%7BE%7D_%7Bs%5E%7B%5Cprime%7D%7D%5Cleft%5Br%2B%5Clambda+Q%5E%7B%5Cpi%7D%5Cleft%28s%5E%7B%5Cprime%7D%2C+a%5E%7B%5Cprime%7D%5Cright%29+%7C+s%2C+a%5Cright%5D+%5Cend%7Baligned%7D+)

上面公式中的 $\pi$ 表示动作选择策略(例如以0.1的概率随机选择action，以0.9的概率按照Q网络选择value值最大的action)

其实我们最初的目的是找到当前状态下应该执行哪个action，但是如果我们求解出最优的 $Q^{\pi}(s, a)$ ,其实也就等价于找到了这个action，这种求解方法也叫value-based方法。

其实还有policy-based(直接计算策略函数) 和 model-based(估计模型，即计算出状态转移函数，进而求解出整个MDP(马尔科夫过程)过程) 方法,下面主要以介绍value-based为主。

最优的动作价值函数为：

![Q^{}(s, a)=\max {\pi} Q^{\pi}(s, a)= \mathbb{E}{s^{\prime}}\left[r+\lambda \max _{a^{\prime}} Q^{}\left(s^{\prime}, a^{\prime}\right)

s, a\right]](https://www.zhihu.com/equation?tex=Q%5E%7B%7D%28s%2C+a%29%3D%5Cmax+%7B%5Cpi%7D+Q%5E%7B%5Cpi%7D%28s%2C+a%29%3D+%5Cmathbb%7BE%7D%7Bs%5E%7B%5Cprime%7D%7D%5Cleft%5Br%2B%5Clambda+%5Cmax+_%7Ba%5E%7B%5Cprime%7D%7D+Q%5E%7B%7D%5Cleft%28s%5E%7B%5Cprime%7D%2C+a%5E%7B%5Cprime%7D%5Cright%29+%7C+s%2C+a%5Cright%5D)

有一点要注意的是 $Q^{*}(s, a)$ 表示的是在t时刻的动作价值最优值，而仔细看看上面的等式可以发现，我们还需要求解出下一个状态S’所对应的动作价值最优解。我们还在计算当前的Q值，怎么能有下个状态的Q值呢？所以，在实际运用时，我们会使用之前的Q值，也就是说每次我们会根据新得到的reward和原来的Q值来更新现在的Q值，具体的可以看看下面的算法介绍。

Q-Learning

1. 算法总结

2. 算法流程图

初始化环境状态S
将当前环境状态S输入到Q网络(即策略网络，保存了action和value对应关系的table)，然后输出当前状态的动作A
更新Q网络
$Q_{target}=R+\gamma \max _{a} Q\left(S^{\prime}, a\right)$ 表示Q真实值，简单理解就是我在S状态下采取了action，从环境中获得了R的奖励，然后对下一时刻的Q值应该也是有影响的，这个影响因子就是γ。另外这次是是一个递归的表达式，所以也可以看出离当前时刻越远，我所采取动作的影响力就越低。
$Q_{target}-Q(S,A)$ 就是常说的TD(temporal difference) error，这个error在后面的DQN中会作为损失函数。
更新当前状态为S’
返回第二步重复执行，直到满足限定条件

图片来源:[1]

Sarsa

1. 算法总结

2.算法流程图

图片来源:[1]

3. 和Q-learning的区别

其实可以看到Q-learning和Sarsa的最大区别就是对Q网络的更新策略，Sarsa使用的是使用下次状态所采取的的动作所对应的Q值来更新Q值，而Q-learning使用下次状态S2的最大Q值用于更新。

感性的理解就是Sarsa会探索更多的可能性，而Q-learning会铁定心地选择最大可能性的选择。因此，Q-learning虽然具有学习到全局最优的能力，但是其收敛慢；而Sarsa虽然学习效果不如Q-learning，但是其收敛快，直观简单。因此，对于不同的问题，我们需要有所斟酌。

DQN(Deep Q-learning Network)

通过计算每一个状态动作的价值，然后选择价值最大的动作执行。

1. 深度学习如何和强化学习结合？

前面介绍的Q-learning和Sarsa的action和state都是在离散空间中，但是有的情境下无法用离散空间表达，而且如果真的用离散空间表达，那么空间会非常巨大，这对计算机来说会很难处理。例如自动驾驶车的state和action，我们不可能用一个表格来记录每个state和对应action的value值，因为几乎有无限种可能。那么如何解决这种问题呢？

我们以自动驾驶为例，仔细想想可以知道，车的状态是高维表示的（例如，当前的位置，车的油耗，路况等等数据来表示当前状态），而动作相对来说可能是低维的（为方便说明，假设速度恒定，最后的动作只有方向盘旋转角度）。

因为我们要做的是针对某一时刻的状态选择最合适的动作，所以我们可以把车状态当做高维输入数据，车的当前时刻的动作当做是低维输出，我们可以对二者构建一个映射关系。

\[\begin{array}{l}{x \rightarrow f(x | W) \rightarrow y} \\ {S \rightarrow f(S | W) \rightarrow A}\end{array}\]

上面等式的含义就是对把状态S作为输入数据，然后经过映射函数 $f(S

W)$ 后得到一个向量 $\left[Q\left(s, a_{1}\right), Q\left(s, a_{2}\right), Q\left(s, a_{3}\right), \ldots, Q\left(s, a_{n}\right)\right]$ ，这个卷积神经网络做图像分类任务时的输出值的含义类似，每个位置代表不同action的value，我们可以选择value值最大的作为S状态的action。

那么这个映射函数就可以用 “万能” 的神经网络代替，也就是后面要介绍的DQN了。

2. 如何训练DQN？

1） loss函数构造

我们知道，要训练一个神经网络，那么我们就需要构建loss函数，而这个loss函数的构建又需要真实的label和预测的label。

预测的label很好理解，其实就是最终得到的输出向量嘛，那么真实的label是什么呢？其实就是前面Q-learning算法中介绍到的 $Q_{target}$ ,所以TD error表达式如下：

$L(w)=\mathbb{E}[\underbrace{r+\gamma \max {a^{\prime}} Q(s^{\prime}, a^{\prime}, w)}{\text {Target }}-Q(s, a, w))^{2}]$

2）训练算法

Playing Atari with Deep Reinforcement Learning

具体的算法还涉及到很多细节，例如Experience Replay，也就是经验池的技巧，就是如何存储样本及采样问题。按照脑科学的观点，人的大脑也具有这样的机制，就是在回忆中学习。那么上面的算法看起来那么长，其实就是反复试验，然后存储数据。接下来数据存到一定程度，就每次随机采用数据，进行梯度下降！也就是在DQN中增强学习Q-Learning算法和深度学习的SGD训练是同步进行的！通过Q-Learning获取无限量的训练样本，然后对神经网络进行训练。样本的获取关键是计算y，也就是标签。

Policy Network

一个神经网络，输入是状态，输出直接就是动作（不是Q值）。

前面三种算法都是基于价值(value)的方法，即输入当前状态，然后计算出每个action的价值，最后输出价值最大的action。而policy network则是根据某种策略直接输出action,即 $A=\pi(S,\theta)$ 或者表示为

\[A^*=\underset{A}{\operatorname{argmax}}\,\pi(A|S,\theta)\]

1. loss函数构造

和前面算法类似，一个比较直观的损失函数构造方式如下

\[L(\theta)=\mathbb{E}\left(r_{1}+\gamma r_{2}+\gamma^{2} r_{3}+\ldots | \pi(, \theta)\right)\]

但是上面的loss函数有个问题是式子中的 $r_1,r_2,…$ 都是从环境中获取的，那么如何对策略 $\pi(\theta)$ 做参数更新呢？

我们换个角度想，如果一个action得到的reward多，我们就应该加大这个action的概率，反之就减少。所以目标函数可以写成如下形式：

$E_x[f(x)]=\sum_xp(x)f(x)$

其中x表示某个action，p(x)和f(x)分别表示该action的概率和对应的reward。

更一般地说，f(x)应该是对action的评价指标，我们可以用reward，当然也可以用其他的指标，如Q值等等。换句话说Policy Network的核心就是这个评价指标的选取。

我们继续分析上面的目标函数，将目标函数对策略网络的参数 $\theta$ 做求导：

$\begin{aligned} \nabla_{\theta} E_{x}[f(x)] &=\nabla_{\theta} \sum_{x} p(x) f(x) & \text { definition of expectation } \\ &=\sum_{x} \nabla_{\theta} p(x) f(x) & \text { swap sum and gradient } \ \&=\sum_{x} p(x) \frac{\nabla_{\theta} p(x)}{p(x)} f(x) & \text { both multiply and divide by } p(x) \\ &=\sum_{x} p(x) \nabla_{\theta} \log p(x) f(x) & \text { use the fact that } \nabla_{\theta} \log (z)=\frac{1}{z} \nabla_{\theta} z \ \ &=E_{x}\left[f(x) \nabla_{\theta} \log p(x)\right] & \text { definition of expectation } \end{aligned}$

由上面的求导可知，其实目标函数也可以写成

\[\begin{aligned} L(\theta)&=-\sum \log p(x) f(x) \ \\&=-\sum \log \pi(A | S, \theta) f(A|S) \end{aligned}\]

下图是文献中的截图，总结了多种评价指标，如Q,reward,TD等。

2. 算法流程图

下图中的A表示策略输出的action，P表示该action对应的概率。

Actor-Critic

上面的policy gradient的loss函数中其实仅仅使用了环境返回的reward，而没有用到Q值。而如果我们希望用到Q值的话就需要用到Actor-critic网络来实现。简单理解，policy network其实就是actor，用来输出动作，而critic则对应评价网络，即评估actor选择的动作的好坏，进而引导actor下次做出更好的选择。

Actor的更新方法和上面policy network可以一样。

critic的评价指标我们可以用Q来表示，那么真实值就用 $Q_{target}$ 表示，和前面算法一样，可以用Q-learning或者Sarsa的思路加上环境返回的reward作为真实Q值，或者也可以直接使用reward，最后采用one step Monte Carlo来更新critic。