时序差分学（TD Learning）方法

强化学中的时序差分学（Temporal Difference Learning, TD Learning）是一种核心思想，结合了动态规划和蒙特卡洛方法。它通过当前状态的差分数据来学习策略价值（state value）或行动价值（action value），是强化学中的重要算法框架。

蒙特卡洛方法与时序差分学

蒙特卡洛方法模拟一段情节，在情节结束后根据目标价值（target reward）估计各状态的价值。而时序差分学则模拟一段情节，在每一步或几步后，根据新状态的价值来估计执行前的状态价值。可以认为蒙特卡洛方法是一种单步的时序差分学，而多步的时序差分学在下一章将详细讲解。

TD(0)算法

TD(0)（Temporal Difference with ZeroSteps）是一种最简单的单步时序差分学方法。其公式为：

[ V(S_t) \gets V(S_t) + \alpha [R_{t+1} + \gamma V(S_{t+1}) - V(S_t)] ]

其中，(\alpha)是学习步长，(\gamma)是奖励折扣率，(R_{t+1})是下一步的奖励，(V(S_t))是当前状态的价值估计。

算法描述

初始化所有状态的价值(V(s))任意值。

开始一个新的情节：

初始化当前状态(S_0)（非终态）。

对于每一步(t)：
- 执行策略(\pi)确定当前状态的行动(A_t)。
- 观察下一步的奖励(R_{t+1})和新状态(S_{t+1})。
- 更新当前状态的价值估计：[ V(S_t) \gets V(S_t) + \alpha [R_{t+1} + \gamma V(S_{t+1}) - V(S_t)] ]
- 更新当前状态(S_t)为(S_{t+1})，直到达到终态。

TD(0)通过一次步长更新价值函数，适用于单步学习任务。

多步时序差分学方法

多步时序差分学方法（TD(n)）允许在n步内完成价值函数的更新。其核心思想是利用重要样本（重要采样）来加速学习过程。具体方法包括：

重要样本比率（Importance Sampling Ratio）：[ \rho_{\tau+n}^{(\tau+1)} \gets \prod_{i=\tau+1}^{\tau+n-1} \frac{\pi(A_t|S_t)}{\mu(A_t|S_t)} ]其中，(\mu)是行为策略，(\pi)是目标策略。

价值函数更新：[ V(S_{\tau}) \gets V(S_{\tau}) + \alpha \rho [G - V(S_{\tau})] ]其中，(G)是目标价值，(\rho)是重要样本比率。

算法描述

初始化所有状态的价值(Q(s, a))任意值。

开始一个新的情节：

初始化当前状态(S_0)（非终态）。

对于每一步(t)：
- 执行行为策略(\mu)确定当前状态的行动(A_t)。
- 观察下一步的奖励(R_{t+1})和新状态(S_{t+1})。
- 更新价值函数：[ Q(S_t, A_t) \gets Q(S_t, A_t) + \alpha [R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t)] ]
- 更新当前状态(S_t)为(S_{t+1})，直到达到终态。

Sarsa算法

Sarsa（State-Aggregated Reinforcement Learning）是一种基于策略的时序差分学方法。其核心思想是通过策略(\pi)导出行动价值(Q_{\pi}(s, a))，并通过与行为策略(\mu)结合的方式进行学习。

算法描述

初始化所有状态的行动价值(Q(s, a))任意值。

开始一个新的情节：

初始化当前状态(S_0)（非终态）。

对于每一步(t)：
- 执行策略(\pi)确定当前状态的行动(A_t)。
- 观察下一步的奖励(R_{t+1})和新状态(S_{t+1})。
- 更新价值函数：[ Q(S_t, A_t) \gets Q(S_t, A_t) + \alpha [R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)] ]
- 更新当前状态(S_t)为(S_{t+1})，直到达到终态。

Q-Learning算法

Q-Learning是一种突破性的算法，通过最大化下一步状态的行动价值来学习策略价值。其公式为：

[ Q(S_t, A_t) \gets Q(S_t, A_t) + \alpha [R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t)] ]

算法描述

初始化所有状态的行动价值(Q(s, a))任意值。

开始一个新的情节：

初始化当前状态(S_0)（非终态）。

对于每一步(t)：
- 执行策略(\pi)确定当前状态的行动(A_t)。
- 观察下一步的奖励(R_{t+1})和新状态(S_{t+1})。
- 更新价值函数：[ Q(S_t, A_t) \gets Q(S_t, A_t) + \alpha [R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t)] ]
- 更新当前状态(S_t)为(S_{t+1})，直到达到终态。

Double Q-Learning

Double Q-Learning通过同时维护两个价值函数(Q_1)和(Q_2)，避免了最大化偏差（Maximization Bias）问题。具体方法为：

初始化两个价值函数(Q_1(s, a))和(Q_2(s, a))任意值。

开始一个新的情节：

初始化当前状态(S_0)（非终态）。

对于每一步(t)：
- 选择一个随机的目标函数（以0.5概率选择(Q_1)或(Q_2)）：[ Q_1(S_t, A_t) \gets Q_1(S_t, A_t) + \alpha [R_{t+1} + \gamma \argmax_{a} Q_2(S_{t+1}, a) - Q_1(S_t, A_t)] ][ Q_2(S_t, A_t) \gets Q_2(S_t, A_t) + \alpha [R_{t+1} + \gamma \argmax_{a} Q_1(S_{t+1}, a) - Q_2(S_t, A_t)] ]
- 更新当前状态(S_t)为(S_{t+1})，直到达到终态。

Tree Backup Algorithm

Tree Backup Algorithm通过计算行动价值的期望值来加速学习过程。其核心思想是对所有可能的行动求期望值，具体方法为：

[ Q(S_t, A_t) \gets Q(S_t, A_t) + \alpha [R_{t+1} + \gamma \sum_a \pi(a|S_{t+1}) Q(S_{t+1}, a) - Q(S_t, A_t)] ]

算法描述

初始化所有状态的行动价值(Q(s, a))任意值。

开始一个新的情节：

初始化当前状态(S_0)（非终态）。

对于每一步(t)：
- 执行策略(\pi)确定当前状态的行动(A_t)。
- 观察下一步的奖励(R_{t+1})和新状态(S_{t+1})。
- 更新价值函数：[ Q(S_t, A_t) \gets Q(S_t, A_t) + \alpha [R_{t+1} + \gamma \sum_a \pi(a|S_{t+1}) Q(S_{t+1}, a) - Q(S_t, A_t)] ]
- 更新当前状态(S_t)为(S_{t+1})，直到达到终态。