1 背景介绍

在强化学习中的蒙特卡罗方法的案例中，我们对于模型未知的问题，从样本轨迹的经验中估计价值函数，但蒙特卡罗方法需要使用完整的轨迹，而时序差分法（Temporal-Difference, TD）采用贝尔曼方程，从部分轨迹中估计回报，从而寻找最优策略。本案例将基于迷宫游戏，对强化学习的时序差分法进行介绍，并介绍SARSA、Q-Learning和Double Q-Learning三种算法。

2 TD Prediction

2.1 时序差分法的概念

在上一节中，我们介绍了蒙特卡罗算法（Monte Carlo，MC），在MDP状态转移概率未知的情况下，直接从完整的轨迹来估计状态的真实价值，认为某状态的价值等于在多个轨迹中该状态所有回报的平均值。下面我们简单回顾MC的估计方式：

回报：时刻及其之后之后累计奖励，

基本思想：对于策略，从n条轨迹样本中估计和，

以的估计为例：

的估计可以写成增量更新的形式：，其中为迭代过程中出现的次数。

而在时序差分法（Temporal-Difference, TD）中，采用贝尔曼方程，从部分轨迹中估计状态回报，策略迭代形式的贝尔曼方程为：

状态价值函数可以写作迭代更新的形式，根据轨迹对，在第步的更新公式如下：

其中，称为TD目标值（TD target），被称为TD误差（TD error）。

同理，动作价值函数可以表示为：

2.2 TD(0)算法

接下来，我们讲解TD求解预测问题的算法流程，常用TD(0)算法。

2.3 TD和MC的区别

我们可以总结蒙特卡罗方法和时序差分法求解预测问题的区别。

MC的状态价值函数更新公式：，其中为前步中出现的次数。

TD的状态价值函数更新公式：

• TD可以利用不完整的轨迹学习，也可以在持续进行的环境中学习，而MC则要等到轨迹终止后才能利用完整轨迹学习；
• TD在更新状态价值时使用的是TD目标值（），由于，所以TD误差（TD error）的期望值，TD估计是当前状态价值的有偏估计；而MC则使用回报来更新状态价值，因此是某一策略下状态价值的无偏估计；
• TD利用马尔可夫决策过程（MDP）学习，通常更高效；
• 在TD更新公式的与MC的取值相近的情况下，TD从一个随机中的学习，比MC从许多个随机中的学习得到的方差低。

综上所述，TD与MC均是无模型方法 (Model-Free)，虽然TD是状态价值函数的有偏估计，但灵活性更强、效率更高，因此目前主流的强化学习求解方法都是基于时序差分的，例如SARSA、Q-Learning。

2.4 n-Step TD

接下来，我们引入n步自举法（n-step Bootstrapping）统一蒙特卡罗和时序差分法两种方法，是一种介于上述两种方法之间的方法。

TD(0)采用下一步估计状态回报，也可以采用多步，例如向前n步来估计，作为时序差分法在n个步骤上的延伸：

采用替换TD目标值（），得到以下更新公式：

当n趋于无穷时，n步时序差分趋于使用完整的状态序列，此时n-Step TD等价于MC。

2.5 TD()算法

确定n-Step TD的步数𝑛是一个超参数调优问题，为在不增加计算复杂度的情况下，综合考虑所有步数的预测，采用作为的权重，从第一步到最后一步，每一步权重为，从而使完整序列中所有步权重之和为1，综合考虑所有步数的预测：

状态价值函数的迭代公式为：

将展开可以得到：

因此，当，即TD(0)；

当，因此MC也称为TD(1)。

可以采用前向和后向两种视角理解：

• 前向视角：基于当前状态向前看，考虑利用未来状态信息，更新当前状态的价值函数的方法。在更新的回报时，需要得到完整序列，与MC算法具有相同的劣势，因此当时该算法为TD(0)，当时为MC算法。
• 后向视角：基于当前状态向后看，考虑利用当前状态信息，更新历史状态的价值函数的方法。
• 首先，定义资格迹（Eligibility Traces）：
• 举例来说，老鼠在连续接受了3次响铃和1次亮灯信号后遭到了电击，那么在分析遭电击的原因时，是响铃的因素还是亮灯的因素更重要呢？问题可以归因为频率启发式（frequency heuristic），频率最高的状态为原因，即响铃是电击的原因；另一种归因方式是就近启发（recency heuristic），最近几次状态为原因，即亮灯是电击的原因。
• 定义资格迹，同时考虑上述两种启发，表示状态在时对后续状态的影响，,
• 后向视角基于当前状态的TD误差，更新历史状态的值函数，对于当前状态，,
  
  

3 TD Control

3.1 SARSA

首先，我们介绍基于TD的on-policy算法SARSA。

SARSA是一种on-policy策略，“SARSA”实际上是State、Action、Reward、State'、Action'的组合，表示迭代的流程，在当前状态选择动作，获得奖励并到达新的状态，在新状态选择新动作来更新价值函数。SARSA算法采用同一个-Greedy策略更新价值函数和选择新的动作，除了的计算方式不同，SARSA与MC on-policy -Greedy Policy算法的求解方法基本一致。

3.2 Q-Learning

Q-Learning是一种off-policy策略，采用行为策略例如策略选择新的动作，而采用贪心法更新价值函数。

算法流程与SARSA基本一致，区别在动作选择和更新价值函数两个环节：

• 动作选择：使用一种行为策略，在选择，比如基于当前的-贪心策略
• 更新价值函数：更新

与MC Off-Policy不同，Q-Learning不需要进行重要性采样，因为行为策略只用来生成，也就是确定被更新的，的更新则采用，而MC Off-Policy则采用行为策略生成整个轨迹。

3.3 Double Q-Learning

虽然Q-Learning得到的是的无偏估计，即，但最优动作价值函数的更新依赖于最大化，而导致过估计，可以采用双估计器方法（Double Estimator）来缓解高估的问题。

设有和是的两个独立非偏估计，，则有

因此，Double Q-Learning维护两个Q表，每个Q表都会使用另一个Q表的值更新下一个状态。两个Q表需要分别从不同的经验集中学习，但动作选择的行为策略则可以同时使用两个Q表，进行贪心策略探索，因此该算法的数据效率不低于Q-Learning。

4 迷宫游戏实战

下面我们基于第一节所定义的迷宫游戏，分别采用SARSA、Q-Learning和Double Q-Learning三种算法，求解最优的迷宫行进策略。

4.1 SARSA

SARSA算法采用TD思想估计动作价值函数，并使用同一个-Greedy策略更新价值函数和选择新的动作。

我们首先使用SARSA算法来解决迷宫问题，分别令、，绘制不同和取值下每一轮策略的累计奖励。

在本案例中，当时，SARSA算法在50轮迭代附近找到最优路线，提高学习率有助于加快收敛速度，较小的使策略在后期轮次中更加稳定。

4.2 Q-Learning

接下来，我们使用Q-Learning算法来寻找最优策略，采用不同的行为策略和目标策略（ -贪心策略），绘制每一轮策略的累计奖励如图3和图4所示。

与SARSA算法的结果相似，当时，Q-Learning算法在50轮迭代附近找到最优路线。

4.3 Double Q-Learning

最后，我们使用Double Q-Learning算法来寻找最优策略，采用两个Q表，每个Q表都使用另一个Q表的值更新下一个状态，绘制每一轮策略的累计奖励。

当时，Double Q-Learning算法在100轮迭代附近找到最优路线，与SARSA和Q-Learning算法相比收敛速度较慢。

5 总结

本案例介绍了时序差分法的基本概念，对比了时序差分法和蒙特卡罗算法的区别，讲解了SARSA、Q-Learning和Double Q-Learning三种算法，并使用python在迷宫游戏中分别采用这三种算法，求解最优行进策略。

6 参考资料

[1] 魏轲. (2024). Algorithmic and Theoretical Foundations of RL [Handouts]. 复旦大学. https://makwei.github.io/rlIndex.html

[2] Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction. MIT Press.

[3] Silver, D. (2015). Introduction to reinforcement learning.

[4] Hasselt, H. V. . (2010). Double q-learning. Mit Press, 2613-2621.