引言
时序差分（Temporal-Difference，TD）方法是强化学习中的一类核心算法，它结合了动态规划与蒙特卡洛方法的优点。TD方法是无模型（model-free）学习方法，不需要环境模型即可学习价值函数和最优策略。
TD方法的核心特点是通过比较不同时间步骤的估计值之间的差异来更新价值函数，这种差异被称为"时序差分误差"（TD error）。TD方法可以被视为解决贝尔曼方程或贝尔曼最优方程的特殊随机逼近算法。
基础TD算法：状态值函数学习
给定策略 \(\pi\)，基础TD算法用于估计状态值函数\(v_\pi(s)\)。假设我们有一些按照策略\(\pi\)生成的经验样本\((s_0, r_1, s_1, ..., s_t, r_{t+1}, s_{t+1}, ...)\)，TD算法的更新规则为：
其中：
- \(v_t(s_t)\) 是 \(t\) 时刻对 \(v_\pi(s_t)\) 的估计
- \(\alpha_t(s_t)\) 是 \(t\) 时刻状态 \(s_t\) 的学习率
- 只有被访问的状态 \(s_t\) 的值会被更新，其他状态的值保持不变
TD算法可以看作是应用Robbins-Monro算法来解决贝尔曼方程。其中的贝尔曼方程有时可以被称作贝尔曼期望方程，表示为
时序差分算法的推导
为了求解这个方程，可以将其重写为：
目标是通过迭代方法找到使 \(g(v_\pi(s_t)) = 0\) 的解，即 \(v_\pi(s)\)。
Robbins-Monro 算法是一种随机逼近方法，适用于求解期望形式的方程。对于上述 \(g(v_\pi(s_t)) = 0\)，我们可以定义一个随机过程来逐步逼近解。
- \(g(v_\pi(s_t))\) 是目标函数，表示当前估计值与真实值的偏差。
- 我们无法直接计算 \(E[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s_t]\)，但可以通过采样获得其近似值。
在时间步 \(t\)，我们可以从环境中采样得到：
- 即时奖励 \(r_{t+1}\)（\(R_{t+1}\) 的样本）
- 下一状态 \(s_{t+1}\)（\(S_{t+1}\) 的样本）
基于这些样本，\(g(v_\pi(s_t))\) 的“噪声观测值”可以表示为：
Robbins-Monro 算法的基本思想是逐步调整估计值，使其逼近真实值。更新规则为：
将 \(\tilde{g}(v_t(s_t))\) 的表达式代入，得到：
将 \(v_\pi(s_{t+1})\) 替换为 \(v_t(s_{t+1})\) 后，是否仍能保证算法收敛？
答案是肯定的。后续会证明 在满足一定条件（如学习率 \(\alpha_t\) 的选择）时，TD算法中的估计值 \(v_t(s_t)\) 将几乎必然收敛到真实值 \(v_\pi(s_t)\)。
TD算法的属性分析
首先，文章重新审视TD算法的表达式，将其写为：
其中：
- TD target：\(\bar{v}_t = r_{t+1} + \gamma v_t(s_{t+1})\)
- TD error：\(\delta_t = v_t(s_t) - \bar{v}_t = v_t(s_t) - (r_{t+1} + \gamma v_t(s_{t+1}))\)
新的估计值 \(v_{t+1}(s_t)\) 是当前估计值 \(v_t(s_t)\) 与 TD误差 \(\delta_t\) 的组合。
- 为什么 \(\bar{v}_t \) 被称为TD target？
从(4) 中减去\(\bar{v}_t\)：
取绝对值， 得：
由于\(\alpha_t(s_t)\) 是一个小的正数，所以\(0 < 1 - \alpha_t(s_t) < 1\)，因此：
这个不等式表明，新的估计值 \(v_{t+1}(s_t)\) 比旧的估计值 \(v_t(s_t)\) 更接近TD目标 \(\bar{v}_t\)。换句话说，算法在数学上驱使估计值 \(v_t(s_t)\) 向目标值 \(\bar{v}_t\) 靠近。这就是为什么 \(\bar{v}_t\) 被称为"TD target"。
- TD error
TD误差 \(\delta_t = v_t(s_t) - (r_{t+1} + \gamma v_t(s_{t+1}))\) 有两个重要的解释：
- 时序差分：
- 这个误差被称为"时序差分"是因为它反映了两个时间步（\(t\)和\(t+1\)）之间的差异。
- 它衡量了当前状态估计值与下一状态估计值（经过折扣和奖励调整）之间的差距。
- 估计准确性指标：
- 当状态值估计准确时，TD误差的期望值为零。
- 当 \(v_t = v_\pi\) 时（即估计值等于真实值）：
上面第三个等号是因为根据期望贝尔曼方程(2)。
因此，TD error 不仅反映了两个时间步之间的差异，更重要的是，它反映了当前估计值 \(v_t\) 与真实状态值 \(v_\pi\) 之间的差异。
TD Vs MC
下面这张表详细对比了时序差分(TD)学习和蒙特卡洛(MC)学习的关键特性差异
特性 | TD Learning | MC Learning |
|---|---|---|
增量性 | 增量的：TD学习可以在接收到经验样本后立即更新状态/动作值。 | 非增量的：MC学习必须等待整个回合（episode）完全收集后才能更新。这是因为它需要计算回合的折扣回报。 |
任务类型适应性 | 持续任务和回合任务：由于TD学习是增量的，它可以处理两种类型的任务。持续任务可能没有终止状态。 | 仅回合任务：由于MC学习是非增量的，它只能处理回合任务，即回合在有限步数后终止的任务。 |
自举特性 | 自举：TD学习具有自举特性，因为状态/动作值的更新依赖于该值的先前估计。因此，TD学习需要对值进行初始猜测。 | 非自举：MC学习不是自举的，因为它可以直接估计状态/动作值，不需要初始猜测。 |
估计方差 | 低估计方差：TD的估计方差低于MC，因为它涉及的随机变量较少。例如，要估计动作值 \(q_\pi(s_t,a_t)\)，Sarsa仅需要三个随机变量的样本：\(R_{t+1}\)、\(S_{t+1}\) 和 \(A_{t+1}\)。 | 高估计方差：MC的估计方差较高，因为涉及许多随机变量。例如，要估计\(q_\pi(s_t,a_t)\)，我们需要 \(R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+...\) 的样本。假设每个回合的长度为\(L\)，且每个状态的动作数相同为 \(|A|\)，则按照软策略可能有 \(|A|^L\) 种可能的回合。如果我们仅使用少量回合进行估计，估计方差自然会很高。 |
收敛性分析
TD 收敛性定理：给定策略 \(\pi\)，如果对所有 \(s \in S\) 满足 \(\sum_t \alpha_t(s) = \infty\) 且 \(\sum_t \alpha_t^2(s) < \infty\)，则TD算法中的 \(v_t(s)\) 几乎必然收敛到\(v_\pi(s)\)。
收敛条件要求每个状态被访问足够多次，这需要探索性起始条件或探索性策略。在实践中，学习率\(\alpha_t\) 通常选择为小的正常数，此时算法在期望意义上收敛。
证明过程可以参考 Mathematical Foundations of Reinforcement Learning
Sarsa算法：动作值函数学习
算法描述
Sarsa算法用于估计给定策略 \(\pi\) 下的动作值函数 \(q_\pi(s,a)\)。假设我们有经验样本\((s_0, a_0, r_1, s_1, a_1, ..., s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1}, ...)\)，Sarsa的更新规则为：
Sarsa名称来源于算法每次迭代所需的五元组：状态-动作-奖励-状态-动作(State-Action-Reward-State-Action)。
和TD算法相同， Sarsa算法可以看作是解决动作值形式的贝尔曼方程的随机近似算法（stochastic approximation）：
这个方程建立了动作值之间的关系，可以重写为:
上述方程是贝尔曼动作值方程得另一种形式。
收敛性分析
Sarsa 收敛性定理：给定策略 \(\pi\)，如果对所有 \((s,a)\) 满足 \(\sum_t \alpha_t(s,a) = \infty\) 且 \(\sum_t \alpha_t^2(s,a) < \infty\)，则Sarsa算法中的 \(q_t(s,a)\) 几乎必然收敛到动作值 \(q_\pi(s,a)\)。
证明方式和TD算法得收敛证明相似。
Sarsa结合策略改进
SARSA算法只能估计给定策略的动作值。为了找到最佳政策，我们可以将其与policy improvement 步骤相结合。
这种实现基于广义策略迭代的思想，每次只更新访问的状态-动作对的值，然后立即更新策略。
Expected Sarsa
Expected Sarsa是Sarsa的一个变体，其更新规则为：
其中：
Expected Sarsa 与 Sarsa 的主要区别在于TD目标：Expected Sarsa使用期望值 \(r_{t+1} + \gamma E[q_t(s_{t+1}, A)]\)，而Sarsa使用样本 \(r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1})\)。
相比Sarsa， 尽管计算期望值可能会稍微增加计算复杂性，但从某种意义上说，它会降低估计方差，因为它可以将Sarsa 中的随机变量从\(\{s_t，r_t，r_{t+1}，s_{t+1}，a_{t+1}\}\)降低到\(\{s_t，r_t，r_{t+1}，s_{t+1}\}\)
和Sarsa相同， Expected Sarsa 也可以看作是在解决贝尔曼方程的随机近似问题：
上面的式子第一眼看比较奇怪，看不出是一个贝尔曼方程的形式， 实际上，它是另一种贝尔曼方程的表达形式：
带入到 (6) 中，得
这显然是一个贝尔曼方程。
n-step Sarsa
算法描述与理论基础
n步Sarsa是Sarsa的扩展版本，它结合了多步回报来更新动作值。回忆动作值定义为：
其中 \(G_t\) 是折扣回报。\(G_t\) 可以有不同的分解形式：
- Sarsa：\(G_t^{(1)} = R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1})\)
- n步Sarsa：\(G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + ... + \gamma^n q_\pi(S_{t+n}, A_{t+n})\)
- MC：\(G_t^{(\infty)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ...\)
可以注意到，\(G_t =G_t^{(1)}=G_t^{(2)}=G_t^{(n)}=G_t^{(\infty)}\), 只是其分解得形式不同。
n步Sarsa的更新规则为：
- 当\(n=1\)时，\(n\)步Sarsa退化为标准Sarsa算法
- 当\(n=∞\)时，n步Sarsa等同于MC学习算法（设置\(\alpha_t=1\)）
总而言之，N-Step Sarsa是一种更通用的算法，性能介于Sarsa和MC学习之间：
- 较大的\(n\)：接近MC学习，估计方差高但偏差小
- 较小的\(n\)：接近Sarsa，估计偏差大但方差低
Q-learning
算法描述
Q-learning是一种经典的强化学习算法，可以直接估计最优动作值并找到最优策略。Q-learning的更新规则为：
Q-learning与Sarsa的主要区别在于TD target：Q-learning使用\(r_{t+1} + \gamma \max_a q_t(s_{t+1}, a)\)，而Sarsa使用 \(r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1})\)。进一步，给定 \((s_t,a_t)\)， Sarsa 需要 \((r_{t+1}, s_{t+1},a_{t+1})\)，而Q-Learning 仅仅需要 \((r_{t+1}, s_{t+1})\)。
实际上，Q-learning是一种解决贝尔曼最优方程的随机近似算法：
这是用动作值表示的贝尔曼最优方程，可参考下面解释
Q-learning与贝尔曼最优方程的关系
根据期望的定义， (8)可以写成下面这种形式：
对方程两边取最大值，建立动作值和状态值之间的联系：
定义状态值函数 \(v(s) = \max_{a \in A(s)} q(s, a)\)，上述方程可以重写为：
引入策略 \(\pi\)，方程可以进一步表示为：
这个方程正是贝尔曼最优方程的状态值形式。
Off-policy vs on-policy
强化学习中存在两种策略：行为策略（用于生成经验样本）和目标策略（不断更新以收敛到最优策略）。
- on-policy：行为策略与目标策略相同，如Sarsa和MC学习
- off-policy：行为策略与目标策略不同，如Q-learning
Q-learning是off-policy的根本原因是它直接解决贝尔曼最优方程，而不是给定策略的贝尔曼方程。
off-policy学习的优势：
- 可以基于其他策略生成的经验样本学习最优策略
- 行为策略可以选择具有强探索能力的策略，提高学习效率
区分和在线学习与离线学习
在线学习(Online Learning):
- 指代理在与环境交互的同时更新值函数和策略
- 特点是实时性，代理边行动边学习
- 例如：机器人在实际环境中边移动边调整其控制策略
离线学习(Offline Learning):
- 指代理使用预先收集的经验数据进行学习，无需与环境实时交互
- 也称为"批量学习"或"回放学习"
- 例如：自动驾驶系统使用预先收集的驾驶数据进行训练，而不是在实际道路上边开车边学习
on-policy 算法的实现限制:
- on-policy算法只能以在线方式实现
- 不能使用由其他策略生成的预先收集的数据，因为on-policy学习要求评估和改进的策略必须是生成样本的同一策略
off-policy算法的实现灵活性:
- off-policy算法可以以在线或离线方式实现
- 可以使用实时交互生成的数据（在线）
- 也可以使用预先收集的数据（离线）
- 原因：off-policy学习不要求行为策略与目标策略相同
Q-Learning 实现
Q-learning可以有在策略和离策略两种实现方式：
on-policy 版本：
off-policy版本：
在off-policy版本中，行为策略 \(\pi_b\) 可以是任何策略，只要它能生成足够的经验样本。通常希望\(\pi_b\)具有探索性。目标策略 \(\pi_T\) 是贪婪策略而非 \(\epsilon\)-贪婪策略，因为它不用于生成样本，因此不需要具有探索性。
Q-learning的性能受以下因素影响：
- 初始值：由于Q-learning具有自举特性，算法性能依赖于动作值的初始猜测。当初始猜测接近真实值时，估计收敛更快。
- 行为策略的探索性：当行为策略不具有探索性时，学习性能显著下降。例如，\(\epsilon\)-贪婪策略中\(\epsilon\)值越小，探索能力越弱，学习速度越慢，因为经验样本不足。
TD算法的统一视角
所有TD算法可以用统一的表达式表示：
其中 \(\bar{q}_t\) 是TD目标，不同算法有不同的TD目标：
算法 | TD target \(\bar{q}_t\) |
|---|---|
Sarsa | \(r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1})\) |
n-step Sarsa | \(r_{t+1} + \gamma r_{t+2} + \cdots + \gamma^n q_t(s_{t+n}, a_{t+n})\) |
Q-learning | \(r_{t+1} + \gamma \max_a q_t(s_{t+1}, a)\) |
MC学习 | \(r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots\) |
算法 | 所解方程 |
|---|---|
Sarsa | BE:\(q_π(s,a)=q_\pi(s, a) = E [R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1})\mid S_t = s, A_t = a]\) |
n-step Sarsa | BE:\(q_\pi(s, a) = E[R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^n q_\pi(S_{t+n}, A_{t+n})\mid S_t = s, A_t = a]\) |
Q-learning | BOE:\(q(s, a) = E[R_{t+1} + \gamma \max_a q(S_{t+1}, a)\mid S_t = s, A_t = a]\) |
Monte Carlo | BE:\(q_\pi(s, a) = E[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \ldots \mid S_t = s, A_t = a]\) |
这些算法可以看作是解决统一方程 \(q(s, a) = E[\bar{q}_t|s, a]\) 的随机逼近算法。除Q-learning外，所有算法都旨在解决贝尔曼方程，而Q-learning旨在解决贝尔曼最优方程。