前言

 前两期我们介绍了动态规划算法，还有蒙特卡洛算法，不过它们对于状态价值函数的估值都有其缺陷性，像动态规划，需要从最下面向上进行递推，而蒙特克洛则需要一个Episode(回合)结束才能对其进行估值，有没有更直接的方法，智能体能边做动作，边估值一次，不断学习策略？答案是有的。这就是本期需要介绍的算法，时间差分法（Time Difference，TD）法。本期将介绍两个典型经典的TD算法，SARSA算法 和 Q-learing算法。它们都是无模型强化学习方法，直接跟环境进行交互来估算动作价值函数。

前期回顾

强化学习:基础知识篇(包含Gym库的简单实践)——手把手教你入门强化学习（一）
强化学习:Markov决策过程(MDP)——手把手教你入门强化学习(二)
强化学习:实践理解Markov决策过程(MDP)——手把手教你入门强化学习(三)
强化学习:动态规划求解最优状态价值函数——手把手教你入门强化学习(四)
强化学习:蒙特卡罗求解最优状态价值函数——手把手教你入门强化学习(五)

一、SARSA算法

我们可以看到SARSA其实就是“状态/动作/奖励/状态/动作”(State-Action-Reward-State-Action）。该算法利用
$$R_{t}+1+\gamma q_{t}(S_{t+1},A_{t+1})$$
得到单步时序差分目标Ut，进而更新q(St,At)。该算法的更新式为：

简单来看，实际上公式就是：更新后的Q值=更新前的Q值+某种修正，这个某种修正里，我们用了部分真实值，不像蒙特卡洛方法用了全部的真实值。部分真实值就是R，同理这里a是学习率。
通俗意义上，我们可以这样理解，举个例子，我们开车从A->B，现在初始值Q(A->B)是100min，一般是我们跑完A->B看看花了多少时间，然后用真实值去更新这个结果，但这个需要跑完全程，现在我们可以换个思路，我们在A-B中间找个C，A->C->B，我们只跑A->C，然后用A->C+Q(C,B)系统给的初始值，用这个跟Q(A，B）去做差，然后用这个去更新Q(A,B)，这样我们每一步走的都可以去更新，不用跑完全程，这个就类似于这个算法，我们跑到C就是获得真实奖励R，然后用这个+$\gamma Q(S',A')-Q(S,A)$去更新Q(S,A)，也就是去修正Q。

还有一个重要的点，这是个On-Policy算法，也就是同策略算法，它的行动策略和评估策略是同一套策略。这个我们需要跟待会的Q-Learning算法做对比。
行动策略，就是我们Q(s,a)里的a我们应该怎么选择，SARSA这里采取的方法就是ε-greedy方法，方法有两个要点。
· 令ε取一个0和1之间的数字，ε是概率。我们用ε概率随机选择一个动作。
· 以1− ε的概率，让机器人做
$$a^{*}=argmax_{a\in A}Q(s,a)$$
的动作，也就是选择Q(s,a)中能够产生最高估值的动作a。
举个例子：假设你在选走哪条路，有两条路，一条是新路线，一条是你已知最快的路线，如果 ε=0.1，表示你有 10% 的概率随机选路，90% 概率选当前已知最快的路。很好理解这个策略吧，能保证我们拥有一定的好奇心，但大部分还是向更好的路线走。
而评估策略就是Q(s',a')，这里的a‘我们应该怎么选择，这个SARSA选择的是同策略，还是ε-greedy方法。
我们可以看一下SARSA算法的伪代码：

初始化函数Q(sa)，令任何一个终止状态的Q值都为0
对于每个Episode循环
      设置初始状态S
      根据Q函数与状态S，选择动作A（例如ε−greedy方法）
      对于每个Step循环
          做一个动作A，观测R和S′
          根据Q函数和状态S′，选择动作A′（例如ε−greedy方法）
          赋值：Q(S,A)←Q(S,A)+a[R+γQ(S′,A′)−Q(S,A)]
          赋值：S←S′,A←A′
      直到S是终止状态

这个根据上面的推导过程，我们已经很清楚了，用某种修正去更新Q。

二、Q-Learning算法

Q-Learning算法仍然是一个TD算法。它与SARSA算法不同，它是Off-Policy（离线），也就是离线的，区别就是它的行动策略跟评估策略不同。我们先看一下它的更新公式：

它跟SARSA算法唯一的不同就是它多了一个max，也就是评估策略的不同，Q-Learning这里很明确，转移的下一个状态，我只看哪个动作a’能取得最大的估值，我就才用哪一个，而不是我们之前提到的ε-greedy策略。
再以上面选路举例子：还是面临两个选择，现在这个策略告诉我们，我们应该只选最快到底的，不管路况怎么样，如果它堵车我们也选择它。
我们看一下伪代码：

我们可以看到跟SARSA算法，唯一不同的就是行动策略的不同。
SARSA是保守派，我这次发现堵车，可能下次我就不走这里了。而Q-learning如果这次堵车，下次我还选这里，因为这里最快啊。

三、总结

好的，至此，两个算法都讲清楚了，我们现在做个总结，它们两都是TD算法，TD算法是介于蒙特卡罗方法和动态规划之间的强化学习方法，它结合了动态规划的自举更新以及蒙特卡洛算法的样本更新。

写在最后

 如果想要更深入强化学习的内容，关注我，下期更精彩，感兴趣的友友也可以关注我的csdn账号。
 https://blog.csdn.net/qq_53769632?spm=1000.2115.3001.5343