基于Value的强化学习算法

在文章强化学习与马尔可夫决策中，介绍了使用马尔可夫决策模型对强化学习的过程进行建模，本篇文章将介绍基于这一模型而引出的一些强化学习的经典算法。

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误差。

算法流程

image

随机初始化所有的状态和动作对应的价值𝑄。 对于终止状态其𝑄值初始化为0。然后执行下面的流程，迭代次。

1. 初始化为当前状态序列的第一个状态。

2. 用-greedy在当前状态选择出动作。

3. 在状态执行当前动作，得到新状态和奖励。

4. 更新价值函数:
   

5. ；

6. 如果是终止状态，当前轮迭代完毕，否则转到步骤2。

SARSA

SARSA和Q-learning非常相似，除了价值函数的更新方式，其他都是一模一样。其算法流程如下：

image

1. 初始化为当前状态序列的第一个状态。

2. 用-greedy在当前状态选择出动作。

3. 在状态执行当前动作，得到新状态和奖励。

4. 用-greedy在新状态选择出动作

5. 更新价值函数:
   

6. ；

7. 如果是终止状态，当前轮迭代完毕，否则转到步骤2。

两者的不同之处是上述第4步和第5步。

Q-learning在根据当前状态下执行动作之后，直接用贪婪算法选择在新状态下，回报最大的动作对应的值来更新值表，但是这个动作没有被立刻执行，真正在新状态下执行的动作是根据更新之后的值表选择出来的。

反观SARSA，使用的是-greedy从新状态下选择出动作，再更新完值表之后，SARSA在下一轮迭代中更是直接去执行了动作，基本上是“说到做到”。因此，两者在新状态下得到的值会有一些差别。

由于SARSA这种“说到做到”的特性，因此被称为在线学习算法，而Q-learning这一类的算法，被称为离线学习算法。

Sarsa(lambda)

Sarsa(lambda)是Sarsa的增强版。与普通的Sarsa不同，Sarsa(lambda)在更新完当前状态的值之后，还会将之前所走过的所有状态的值一起给更新了。也就是说，Sarsa(lambda)不但思考纠正当前状态的选择，还对以往的记忆状态进行反思纠正。因此，Sarsa(lambda)的收敛速度，比普通的Sarsa快。其算法流程如下：

image

其中是一个矩阵，用来保存其经历过的所有状态的信息。参数是一个值为[0,1]的衰减值，通过对矩阵进行更新，增强离当前状态比较近的记忆，疏远那些太久之前的记忆。

由于Sarsa(lambda)会保存状态记忆，因此除了提高收敛速度之外，还可以解决在训练过程中，智能体反复执行无意义动作的问题，例如老鼠在寻找奶酪的时候，绕着柱子转圈圈的行为就没什么意义了。怎么解决呢，在这一步之前，直接将矩阵中这个状态对应的行置为0即可。

最后，无论是Q-learning还是Sarsa，都是基于值表去解决强化学习的问题，因此他们都是基于value的方法。