在文章强化学习与马尔可夫决策中，介绍了使用马尔可夫决策模型对强化学习的过程进行建模，本篇文章将介绍基于这一模型而引出的一些强化学习的经典算法。
Q-learning
Q-learning是强化学习的经典算法之一，它是一个value-based算法，同时也是一个model-free的算法。这里的Q指的是动作价值，即当前状态下，通过策略
采取动作
之后，能够获得的奖励
。
算法原理
该算法的主要思想很简单。假设强化学习过程中所有状态的集合为，动作空间为
。首先建立一张Q值表，记录强化学习过程中每一个时刻
的状态
下，采取不同的动作
的收益。一张Q值表的示例如下：
| state | a1 | a2 |
|---|---|---|
| s1 | q(s1,a1) | q(s1,a2) |
| s2 | q(s2,a1) | q(s2,a2) |
| s3 | q(s3,a1) | q(s3,a2) |
之后，根据这一张Q值表来选取能够获得最大的收益的动作，一般是通过-greedy的方式选取当前状态下，Q值最大的动作。
Q-learning的整个迭代过程实际上就是去更新这张Q值表，当Q值表收敛时，通过-greedy选取的Q值就是最优动作价值函数
，其对应的策略就是最优策略
。
这里需要注意的是，由于Q-learning是model-free的算法，因此不用考虑环境的状态转移模型，也就不用关心状态价值函数。
Q-learning是使用时序差分TD来更新Q值表的，时序差分的更新公式如下：
其中表示TD目标，
是TD误差。
算法流程
随机初始化所有的状态和动作对应的价值𝑄。 对于终止状态其𝑄值初始化为0。然后执行下面的流程，迭代
次。
初始化
为当前状态序列的第一个状态。
用
-greedy在当前状态
。
在状态
和奖励
。
更新价值函数
:
；
如果
SARSA
SARSA和Q-learning非常相似，除了价值函数的更新方式，其他都是一模一样。其算法流程如下：
初始化
用
在状态
用
更新价值函数
如果
两者的不同之处是上述第4步和第5步。
Q-learning在根据当前状态下执行动作
之后，直接用贪婪算法选择在新状态
下，回报最大的动作
对应的
值来更新
值表，但是这个动作
没有被立刻执行，真正在新状态
下执行的动作是根据更新之后的
值表选择出来的。
反观SARSA，使用的是-greedy从新状态
下选择出动作
，再更新完
值表之后，SARSA在下一轮迭代中更是直接去执行了动作
，基本上是“说到做到”。因此，两者在新状态
下得到的
值会有一些差别。
由于SARSA这种“说到做到”的特性，因此被称为在线学习算法，而Q-learning这一类的算法，被称为离线学习算法。
Sarsa(lambda)
Sarsa(lambda)是Sarsa的增强版。与普通的Sarsa不同，Sarsa(lambda)在更新完当前状态的
值之后，还会将之前所走过的所有状态的
值一起给更新了。也就是说，Sarsa(lambda)不但思考纠正当前状态的选择，还对以往的记忆状态进行反思纠正。因此，Sarsa(lambda)的收敛速度，比普通的Sarsa快。其算法流程如下：
其中是一个矩阵，用来保存其经历过的所有状态的信息。参数
是一个值为[0,1]的衰减值，通过
对矩阵
进行更新，增强离当前状态比较近的记忆，疏远那些太久之前的记忆。
由于Sarsa(lambda)会保存状态记忆，因此除了提高收敛速度之外，还可以解决在训练过程中，智能体反复执行无意义动作的问题，例如老鼠在寻找奶酪的时候，绕着柱子转圈圈的行为就没什么意义了。怎么解决呢，在这一步之前，直接将矩阵
中这个状态
对应的行置为0即可。
最后，无论是Q-learning还是Sarsa，都是基于值表去解决强化学习的问题，因此他们都是基于value的方法。
