Bdq的IT技术博客

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

Q-learning

Q-learning是强化学习的经典算法之一，它是一个value-based算法，同时也是一个model-free的算法。这里的Q指的是动作价值，即当前状态$s$下，通过策略$\pi$采取动作$a$之后，能够获得的奖励$r$。

算法原理

该算法的主要思想很简单。假设强化学习过程中所有状态的集合为$S$，动作空间为$A$。首先建立一张Q值表，记录强化学习过程中每一个时刻$t$的状态$s_t\epsilon S$下，采取不同的动作$a_i\epsilon A$的收益。一张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值表来选取能够获得最大的收益的动作，一般是通过$\epsilon$-greedy的方式选取当前状态下，Q值最大的动作。

Q-learning的整个迭代过程实际上就是去更新这张Q值表，当Q值表收敛时，通过$\epsilon$-greedy选取的Q值就是最优动作价值函数$q_*(s,a)$，其对应的策略就是最优策略$\pi_*(a|s)$。

这里需要注意的是，由于Q-learning是model-free的算法，因此不用考虑环境的状态转移模型，也就不用关心状态价值函数$v_\pi(s)$。

Q-learning是使用时序差分TD来更新Q值表的，时序差分的更新公式如下：

$Q(S,A)+\alpha(R+\gamma\max_aQ(S',a)-Q(S,A))$

其中$R+\gamma\max_aQ(S',a)$表示TD目标，$R+\gamma\max_aQ(S',a)-Q(S,A)$是TD误差。

算法流程

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

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

2. 用$\epsilon$-greedy在当前状态$S$选择出动作$A$。

3. 在状态$S$执行当前动作$A$，得到新状态$S'$和奖励$R$。

4. 更新价值函数$Q(S,A)$:

   $Q(S,A)+\alpha(R+\gamma\max_aQ(S',a)-Q(S,A))$

5. $S=S'$；$A=A'$

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

SARSA

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

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

2. 用$\epsilon$-greedy在当前状态$S$选择出动作$A$。

3. 在状态$S$执行当前动作$A$，得到新状态$S'$和奖励$R$。

4. 用$\epsilon$-greedy在新状态$S'$选择出动作$A'$

5. 更新价值函数$Q(S,A)$:

   $Q(S,A)+\alpha(R+\gamma Q(S',A')-Q(S,A))$

6. $S=S'$；$A=A'$

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

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

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

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

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

Sarsa(lambda)

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

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

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

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