时序差分算法

无模型的强化学习

动态规划算法要求马尔可夫决策过程是已知的，即要求与智能体交互的环境是完全已知的（例如迷宫或者给定规则的网格世界）。在此条件下，智能体其实并不需要和环境真正交互来采样数据，直接用动态规划算法就可以解出最优价值或策略。这就好比对于 有监督学习任务，如果直接显式给出了数据的分布公式，那么也可以通过在期望层面上直接最小化模型的泛化误差来更新模型参数，并不需要采样任何数据点。

但这在大部分场景下并不现实，机器学习的主要方法都是在数据分布未知的情况下针对具体的数据点来对模型做出更新的。对于大部分强化学习现实场景（例如电子游戏或者一些复杂物理环境），其马尔可夫决策过程的状态转移概率是无法写出来的，也就无法直接进行动态规划。在这种情况下，智能体只能和环境进行交互，通过采样到的数据来学习，这类学习方法统称为 无模型的强化学习（model-free reinforcement learning）。

不同于动态规划算法，无模型的强化学习算法不需要事先知道环境的奖励函数和状态转移函数，而是直接使用和环境交互的过程中采样到的数据来学习，这使得它可以被应用到一些简单的实际场景中。这里要讲的无模型的强化学习中的两大经典算法：Sarsa 和 Q-learning，它们都是基于时序差分（temporal difference，TD）的强化学习算法。

还会引入一组概念：在线策略学习和离线策略学习。通常来说，在线策略学习要求使用在当前策略下采样得到的样本进行学习，一旦策略被更新，当前的样本就被放弃了，就好像在水龙头下用自来水洗手；而离线策略学习使用经验回放池将之前采样得到的样本收集起来再次利用，就好像使用脸盆接水后洗手。因此，离线策略学习往往能够更好地利用历史数据，并具有更小的样本复杂度（算法达到收敛结果需要在环境中采样的样本数量），这使其被更广泛地应用。

时序差分方法（TD 学习）

时序差分是一种用来估计一个策略的价值函数的方法，它结合了蒙特卡洛和动态规划算法的思想。时序差分方法和蒙特卡洛的相似之处在于可以从样本数据中学习，不需要事先知道环境；和动态规划的相似之处在于根据贝尔曼方程的思想，利用后续状态的价值估计来更新当前状态的价值估计。

这里先介绍 TD(0)，全称为时序差分学习的零阶方法（Temporal Difference learning of order zero），是强化学习中一种基础的时序差分学习方法。

在TD(0)中，价值函数的更新是基于下一个状态的估计价值和当前状态的价值之间的差异（即时序差分误差）。更新规则可以表示为：

V(S_t) \leftarrow V(S_t) + \alpha \left[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right] $$ 其中： - $V(S_t)$ 是在时间 $t$ 对状态 $S_t$ 的价值估计。 - $\alpha$ 是学习率，决定了新信息覆盖旧信息的速度。 - $R_{t+1}$ 是在转移到状态 $S_{t+1}$ 时获得的奖励。 - $\gamma$ 是折扣因子，它决定了未来奖励的当前价值。 :::tip 在数学和计算机科学中，符号 $\leftarrow$ 用于表示赋值或更新操作。在时序差分学习的上下文中，这个符号用来表示一个变量的当前值被新计算出的值所更新。 ::: 假设有一个4x4的网格世界，其中有一个开始状态、一个结束状态和一些普通状态。智能体从开始状态出发，目标是到达结束状态。每个步骤，智能体可以选择上、下、左、右移动。每次移动获得的即时奖励是-1，除非它到达了结束状态，这种情况下即时奖励是0。智能体的任务是学习每个状态的价值，即达到结束状态的预期累积奖励。 在使用 TD(0) 的情况下，智能体会根据其在网格中的移动来更新每个状态的价值估计。例如，如果智能体从状态A移动到状态B，并从状态B接收到奖励（比如-1），那么它会更新状态A的价值估计，反映从状态A出发到达目标状态的预期总奖励。随着智能体的移动和学习，这些价值估计会逐渐收敛到它们的真实值。 ## Sarsa 算法 既然我们可以用时序差分方法来估计价值函数，那一个很自然的问题是，我们能否用类似策略迭代的方法来进行强化学习。策略评估已经可以通过时序差分算法实现，那么在不知道奖励函数和状态转移函数的情况下该怎么进行策略提升呢？答案是时可以直接用时序差分算法来估计动作价值函数 $Q(S, A)$ 使用时序差分（TD）方法来估计动作价值函数（即Q函数）通常涉及到一种称为 SARSA（State-Action-Reward-State-Action）的算法。SARSA 是一种在线策略TD控制算法，用于学习一个给定策略的动作价值函数。它在每一步更新策略的估计值，基于当前状态（S）、所采取的动作（A）、获得的奖励（R）、下一个状态（S'）以及在下一个状态采取的动作（A'）。 下面是 SARSA 算法的基本步骤： 1. **初始化：** 对于所有状态-动作对 (s, a)，初始化 Q(s, a)。通常这些值初始化为零或者某个小的随机值。 2. **策略选择：** 根据当前的 Q表和一个策略（如ε-贪婪策略）选择一个动作。 3. **环境交互：** 执行动作，观察奖励和下一个状态。 4. **再次选择动作：** 在新状态下，根据当前策略选择下一个动作。 5. **更新Q值：** 使用以下公式更新Q值：

Q(S, A) \leftarrow Q(S, A) + \alpha [R + \gamma Q(S', A') - Q(S, A)]

其中： - $Q(S, A)$ 是当前状态-动作对的估计价值。 - $\alpha$ 是学习率。 - $R$ 是观察到的奖励。 - $\gamma$ 是折扣因子。 - $Q(S', A')$ 是下一个状态-动作对的估计价值。 6. **循环：** 将 $S$ 和 $A$ 更新为 $S'$ 和 $A'$，重复步骤 2-5，直到达到终止条件（如一个情节结束）。 ### 重新测试冰壶环境 我们来实现 Sarsa 算法，主要维护一个表格 Q_table()，用来储存当前策略下所有状态动作对的价值，在用 Sarsa 算法和环境交互时，用 ε-贪婪策略进行采样，在更新 Sarsa 算法时，使用时序差分的公式。我们默认终止状态时所有动作的价值都是 0，这些价值在初始化为 0 后就不会进行更新。 ## References * [动手学习强化学习-第 5 章 时序差分算法](https://hrl.boyuai.com/chapter/1/%E6%97%B6%E5%BA%8F%E5%B7%AE%E5%88%86%E7%AE%97%E6%B3%95)