引言

时序差分（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算法的更新规则为：

\[ \begin{equation}\begin{aligned}v_{t+1}(s_t) &= v_t(s_t) - \alpha_t(s_t)[v_t(s_t) - (r_{t+1} + \gamma v_t(s_{t+1}))]\\ v_{t+1}(s) &= v_t(s), \text{for all}\ s \neq s_t\end{aligned}\end{equation} \]

其中：

$v_t(s_t)$ 是 $t$ 时刻对 $v_\pi(s_t)$ 的估计
$\alpha_t(s_t)$ 是 $t$ 时刻状态 $s_t$ 的学习率
只有被访问的状态 $s_t$ 的值会被更新，其他状态的值保持不变
TD算法可以看作是应用Robbins-Monro算法来解决贝尔曼方程。其中的贝尔曼方程有时可以被称作贝尔曼期望方程，表示为

\[ \begin{equation}v_\pi(s) = E[R_{t+1} + \gamma v_\pi(S_{t+1})|S_t = s], s \in S\end{equation} \]

🧾 时序差分算法的推导

TD算法的属性分析

首先，文章重新审视TD算法的表达式，将其写为：

$$
\begin{equation}\underbrace{v_{t + 1}( {s}{t}) }{new estimate} = \underbrace{v_{t}(s_t) }{current estimate} - {\alpha }{t}( s_t) \left[\overbrace{ v_t({s}{t}) - (\underbrace{r{t + 1} + \gamma v_t(s_{t+1})}{TD\ target \ \bar{v}{t})) })}^{TD\ error \ \delta_t}\right]\end{equation}

其中：

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？
**TD error **

TD Vs MC

下面这张表详细对比了时序差分(TD)学习和蒙特卡洛(MC)学习的关键特性差异

收敛性分析

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的更新规则为：

\[ \begin{equation}\begin{aligned}q_{t+1}(s_t, a_t) &= q_t(s_t, a_t) - \alpha_t(s_t, a_t)[q_t(s_t, a_t) - (r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1}))] \\q_{t+1}(s, a) &= q_t(s, a), \text{for all} (s, a) \neq (s_t, a_t)\end{aligned}\end{equation} \]

Sarsa名称来源于算法每次迭代所需的五元组：状态-动作-奖励-状态-动作(State-Action-Reward-State-Action)。

和TD算法相同， Sarsa算法可以看作是解决动作值形式的贝尔曼方程的随机近似算法（stochastic approximation）：

\[ q_\pi(s, a) = E[R + \gamma q_\pi(S', A')|s, a], \text{for all} (s, a) \]

这个方程建立了动作值之间的关系，可以重写为:

\[ q_\pi(s, a) = \sum_r r p(r|s, a) + \gamma \sum_{s'} \sum_{a'} q_\pi(s', a') p(s'|s, a) \pi(a'|s') \]

上述方程是贝尔曼动作值方程得另一种形式。

收敛性分析

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的一个变体，其更新规则为：

\[ \begin{aligned}q_{t+1}(s_t, a_t) &= q_t(s_t, a_t) - \alpha_t(s_t, a_t)[q_t(s_t, a_t) - (r_{t+1} + \gamma E[q_t(s_{t+1}, A)])]\\ q_{t+1}(s, a) &= q_t(s, a), \text{for all} (s, a) \neq (s_t, a_t)\end{aligned} \]

其中：

\[ E[q_t(s_{t+1}, A)] = \sum_a \pi_t(a|s_{t+1})q_t(s_{t+1}, a) = v_t(s_{t+1}) \]

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 也可以看作是在解决贝尔曼方程的随机近似问题：

\[ \begin{equation}{q}_{\pi }\left( {s,a}\right) = \mathbb{E}\left\lbrack {{R}_{t + 1} + \gamma \mathbb{E}\left\lbrack {{q}_{\pi }\left( {{S}_{t + 1},{A}_{t + 1}}\right) | {S}_{t + 1}}\right\rbrack|{S}_{t} = s,{A}_{t} = a}\right\rbrack , for \ all\ s,a \end{equation} \]

上面的式子第一眼看比较奇怪，看不出是一个贝尔曼方程的形式，实际上，它是另一种贝尔曼方程的表达形式：

\[ \mathbb{E}\left\lbrack {{q}_{\pi }\left( {{S}_{t + 1},{A}_{t + 1}}\right)|{S}_{t + 1}}\right\rbrack = \mathop{\sum }\limits_{{A}^{\prime }}{q}_{\pi }\left( {{S}_{t + 1},{A}^{\prime }}\right) \pi \left( {{A}^{\prime } | {S}_{t + 1}}\right)=v_\pi(S_{t+1}) \]

带入到 (6)式中，得

\[ {q}_{\pi }\left( {s,a}\right) = \mathbb{E}\left\lbrack {{R}_{t + 1} + \gamma {v}_{\pi }\left( {S}_{t + 1}\right) | {S}_{t} = s,{A}_{t}}=a\right] \]

这显然是一个贝尔曼方程。

n-step Sarsa

算法描述与理论基础

n步Sarsa是Sarsa的扩展版本，它结合了多步回报来更新动作值。回忆动作值定义为：

\[ q_\pi(s, a) = E[G_t|S_t = s, A_t = a] \]

其中 $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的更新规则为：

\[ q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - \alpha_t(s_t, a_t)[q_t(s_t, a_t) - (r_{t+1} + \gamma r_{t+2} + ... + \gamma^n q_t(s_{t+n}, a_{t+n}))] \]

当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的更新规则为：

\[ \begin{equation}\begin{aligned}q_{t+1}(s_t, a_t) &= q_t(s_t, a_t) - \alpha_t(s_t, a_t)[q_t(s_t, a_t) - (r_{t+1} + \gamma \max_{a \in A(s_{t+1})} q_t(s_{t+1}, a))] \\q_{t+1}(s, a) &= q_t(s, a), \text{for\ all} (s, a) \neq (s_t, a_t)\end{aligned}\end{equation} \]

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是一种解决贝尔曼最优方程的随机近似算法：

\[ \begin{equation}q(s, a) = E[R_{t+1} + \gamma \max_a q(S_{t+1}, a)|S_t = s, A_t = a]\end{equation} \]

这是用动作值表示的贝尔曼最优方程，可参考下面解释

🧾 Q-learning与贝尔曼最优方程的关系

Off-policy vs on-policy

强化学习中存在两种策略：行为策略（用于生成经验样本）和目标策略（不断更新以收敛到最优策略）。

on-policy：行为策略与目标策略相同，如Sarsa和MC学习
off-policy：行为策略与目标策略不同，如Q-learning
Q-learning是off-policy的根本原因是它直接解决贝尔曼最优方程，而不是给定策略的贝尔曼方程。

off-policy学习的优势：

可以基于其他策略生成的经验样本学习最优策略
行为策略可以选择具有强探索能力的策略，提高学习效率

区分和在线学习与离线学习

在线学习(Online Learning):

指代理在与环境交互的同时更新值函数和策略
特点是实时性，代理边行动边学习
例如：机器人在实际环境中边移动边调整其控制策略
离线学习(Offline Learning):