Chap6 TD
第6章：时序差分学习
一、P119 MC误差可写为TD误差之和
1）证明
2）为什么如果V变化了，此式就不成立？
当V变化时，TD 误差中的$V(S_k)$ 和$V(S_{k+1})$不再是同一版本的价值函数。这会破坏原推导中相邻项相互抵消的机制，导致等式失效。
二、MC vs. TD
图6.1通过对比蒙特卡洛（MC）方法和时序差分（TD）方法在预测“开车回家”各阶段时间时的调整方式，直观体现了TD方法的两个核心优势：在线更新和更高效的偏差-方差权衡。以下是基于图中箭头的具体分析：
1. 箭头方向：TD方法即时修正，MC方法延迟修正
TD方法（右图）：
每个状态（如“离开办公室”“上车”）的预测值（实线）通过指向下一个状态的箭头进行调整。
示例：
- 当从“离开办公室”转移到“上车”时，TD方法立即根据转移后的实际耗时（如交通状况）和下一状态的预测值（“上车”到“离开高速”的预估时间），修正当前状态的预测值（箭头从当前预测指向调整后的值）。
- 这种逐状态更新使预测值（实线）在每一步都向实际时间（虚线）靠拢，形成平滑的调整轨迹。
MC方法（左图）：
所有状态的预测值仅在最终到家后（通过指向终止状态的箭头）一次性调整。
示例：
- 假设实际到家时间比预测长，MC方法需等到整个回合结束后，将每个中间状态（如“离开办公室”“上车”）的预测值统一向上修正（箭头从初始预测直接指向最终调整后的值）。
- 这种批量更新导致预测值在整个过程中保持固定，直到回合结束才突然跳跃到新值，无法反映中途的实时变化。
2. 箭头长度：TD方法的低方差与MC方法的高方差
TD方法（右图）：
箭头长度较短，表明每次更新幅度较小。
原因：
TD方法仅依赖相邻状态的局部信息（如“上车”到“离开高速”的实际耗时），其修正量受单步随机性影响较小（低方差），调整更稳定。
MC方法（左图）：
箭头长度较长（尤其是终止状态附近），表明更新幅度较大。
原因：
MC方法依赖整个回合的累积奖励（如最终到家时间），其修正量受所有中间状态随机性的叠加影响（高方差）。例如，交通拥堵、绕路等事件会累积到最终误差中，导致预测值大幅波动。
三、批量更新
在有限经验数据（如10幕或100个时间步）的情况下，传统增量方法和批量方法的核心区别在于更新策略和数据利用方式。以下是两种方法的详细对比：
传统增量方法（Incremental Methods）
- 更新机制：
- 每处理一个经验样本（如一个时间步或一幕）后，立即更新价值函数 $V(s)$。
- 使用学习率$\alpha$和当前样本的目标值（如MC的回报 $G_t$ 或TD的 $r + \gamma V(s’)$ 计算增量：
$\Delta V(s) = \alpha \left( \text{目标值} - V(s) \right)$ - 直接应用增量更新：$V(s) \leftarrow V(s) + \Delta V(s)$
- 数据利用方式：
- 当数据量有限时，系统会反复多次遍历整个数据集（如循环使用10幕数据）。
- 每次遍历的顺序可能影响结果。例如，先处理样本A再处理样本B时，样本B的更新会基于样本A已调整后的 V(s) 。
- 特点：
- 在线更新：实时利用新经验，适合动态变化的环境。
- 更新路径依赖顺序：不同遍历顺序可能导致不同的收敛路径。
- 可能不稳定：小样本下频繁更新可能导致价值函数波动。
示例：
假设有3个状态 $s_1, s_2, s_3$ ，每个状态出现在不同的时间步中。传统方法会在每次遍历时逐个处理每个时间步：
- 处理 s_1 → 更新 V(s_1) ；
- 处理 s_2 → 更新 V(s_2) （基于更新后的 $V(s_1)$ ）；
- 处理 s_3 → 更新 V(s_3) （基于更新后的 $V(s_1) , V(s_2)$ ）；
- 重复上述过程，直到价值函数收敛。
批量方法（Batch Methods）
- 更新机制：
- 先处理全部数据，累积所有样本的增量，再统一更新价值函数。
- 对每个状态 s ，计算该状态在所有相关样本中的增量总和或均值：
$\Delta V(s) = \alpha \cdot \frac{1}{N_s} \sum_{i=1}^{N_s} \left( \text{目标值}_i - V(s) \right)$
其中 N_s 是状态 s 在批次中出现的次数。 - 一次性应用所有增量：$V(s) \leftarrow V(s) + \Delta V(s)$ 。
- 数据利用方式：
- 每个迭代周期（epoch）内，使用同一版本的价值函数处理所有样本。
- 所有样本的增量基于当前 V(s) 计算，更新仅在批次处理完成后进行。
- 特点：
- 离线更新：更稳定，每次更新基于全局信息。
- 收敛到最小二乘解：在无限次迭代后，会收敛到对批次数据的最优拟合（如样本平均）。
- 计算效率高：适合小样本，避免频繁更新带来的波动。
示例：
同样以3个状态 $s_1, s_2, s_3$ 为例：
- 第一次迭代：
- 处理所有样本，计算每个状态的增量（基于初始 V(s) ）。
- 统一更新： $V(s_1), V(s_2), V(s_3)$ 同时调整。
- 第二次迭代：
- 用更新后的 V(s) 重新处理所有样本，计算新增量。
- 再次统一更新。
- 重复直到收敛。
四、Sarsa vs. Q-learning
Q-learning方法的待学习的动作价值函数Q采用了对最优动作价值函数q*的直接近似作为学习 目标，而与用于生成智能体决策序列轨迹的行动策略是什么无关(作为对比，Sarsa的学习目标中使用的是待学习的动作价值函数本身，由于它的计算需要知道下一时刻的动作A+1,因此与生成数据的行动策略是相关的)。
1. Q-learning 的学习目标
Q-learning 采用最优动作价值函数 q∗作为学习目标：
$Q(s,a) ←Q(s,a) +\alpha \left ( r + \gamma \max_{a’} Q(s’, a’) - Q(s, a) \right)$
- 这里的学习目标是$r+γmaxa′Q(s′,a′)$ ，其中$maxa′Q(s′,a′)$ 代表的是当前估计的最优状态-动作值。
- 由于它使用了 最大 Q 值的动作，而不管这个动作是否是智能体当前的行动策略选择的，所以 Q-learning 是 off-policy（与行为策略无关）的。
换句话说：
Q-learning 学习的是最优策略，即使数据是由其他非最优策略（比如 ε-greedy）收集的，它的学习目标还是始终向着最优策略靠拢。
2. Sarsa 的学习目标
Sarsa 采用的是自身的 Q 值 作为学习目标：
$Q(s,a)←Q(s,a)+α(r+γQ(s′,a′)−Q(s,a))$
- 这里的学习目标是$r+γQ(s′,a′)$，其中 a’ 是智能体实际采取的下一个动作。
- 由于这个目标值依赖于下一步智能体执行的动作 a’，而这个动作是由行为策略（如 ε-greedy） 选出来的，因此 Sarsa 是 on-policy（依赖于行为策略）。
换句话说：
Sarsa 学到的是与当前策略一致的 Q 值，如果行为策略是 ε-greedy，它学到的就是 ε-greedy 下的 Q 值，而不是最优 Q 值。
五、为何TD比MC收敛更快？
六、最大化偏差&双学习
1）最大化偏差
- Q值估计的噪声：Q-learning等基于值函数的方法通过采样估计动作价值 Q(s,a)，这些估计可能因采样不足或环境随机性存在误差。
- 最大化操作放大误差：在更新Q值时，算法会选择当前状态下具有最大Q值的动作（即 maxaQ(s′,a)）。如果某个动作的Q值被偶然高估，最大化操作会持续选择该动作，进一步放大高估误差。
2）双学习
双学习通过解耦动作选择与价值评估来消除最大化偏差。具体来说，它维护两组独立的Q值估计（如 ( Q1 和 Q2 ），并交替使用它们：
- 动作选择：用一组Q值（如 Q1）选择当前最优动作。
- 价值评估：用另一组Q值（如 Q2）评估所选动作的价值。