整体总结
- 一篇很古早的论文，主要探讨了如何在 Off-policy 场景下使用 资格迹（eligibility traces） 进行策略评估
- 包含了同一个轨迹来自不同行为策略的处理方式
研究背景与动机
- 在强化学习中，策略评估是指估计一个策略 \(\pi\) 的值函数 \(Q^\pi(s,a)\)
- 传统方法如 TD(0) 和 TD(\(\lambda\)) 通常是在 On-policy Setting 下工作，即数据由当前正在评估的策略生成
- 在许多实际场景中，我们希望从由 行为策略（behavior policy） \(b\) 生成的数据中学习 目标策略（target policy） \(\pi\) 的值函数，这就是 Off-policy learning
- 本文就聚焦于Off-policy 评估这一子问题，提出并分析了几种基于资格迹的算法，重点研究了它们与 重要性采样（importance sampling） 的关系
问题定义与符号说明
- 环境为 episodic MDP ，每幕从初始状态开始，直到终止状态
- 行为策略 \(b\) 满足对所有状态-动作对，\(b(s,a) > 0\)
- 目标策略 \(\pi\) 可以是任意的
- 目标：估计 \(Q^\pi(s,a)\)，即在状态 \(s\) 下执行动作 \(a\) 后，按照 \(\pi\) 行动的期望折扣累积奖励
重要性采样方法
经典重要性采样（Importance Sampling, IS）
- 对于每个包含 \((s,a)\) 的幕 \(m\)，定义：
- \(R_m\)：从 \((s,a)\) 之后的折扣回报
- \(w_m\)：重要性权重，表示从该点之后，按照 \(\pi\) 而非 \(b\) 行动的概率比
$$
Q^{IS}(s,a) = \frac{1}{M} \sum_{m=1}^{M} R_m w_m
$$ - 该估计是无偏且一致的，但方差大
加权重要性采样（Weighted Importance Sampling, WIS）
- WIS 的定义
$$
Q^{WIS}(s,a) = \frac{\sum_{m=1}^{M} R_m w_m}{\sum_{m=1}^{M} w_m}
$$- 该估计是有偏但一致的，方差更小，实践中更稳定
Per-Decision 重要性采样算法
核心思想
- 将回报分解为每一步的奖励，并对每个奖励单独加权：
$$
Q^{PD}(s,a) = \frac{1}{M} \sum_{m=1}^{M} \sum_{k=1}^{T_m - t_m} \gamma^{k-1} r_{t_m + k} \prod_{i=t_m+1}^{t_m+k-1} \frac{\pi_i}{b_i}
$$ - Theorem 1 ：该估计是 \(Q^\pi\) 的无偏一致估计
- 注：在此之前，人们通常对整条轨迹计算一个总的重要性权重
$$ W = \prod \frac{\pi(a_i|s_i)}{\mu(a_i|s_i)}$$- 如果轨迹很长，方差会爆炸
- 本文没有明确提到，但事实上作者的证明不要求同一个轨迹来自同一个策略，即不需要整条轨迹都来自同一个策略（同一轨迹可以不同策略/不同行为策略）
- 只要在每一个时间步 \(t\)，都知道生成该动作 \(a_t\) 的特定策略 \(\mu_t\) 的概率，就可以通过累积乘积的方式来修正价值估计
- 即，作者从数学上证明了，即使 \(t=1\) 的 \(\mu_1\) 和 \(t=2\) 的 \(\mu_2\) 不同，只要记录了各自的概率，就可以通过加权来无偏地估计目标策略 \(\pi\) 的 Value
- 核心：将回报分解为每个时间步的奖励，并对每个奖励单独加权，权重只依赖于到该奖励为止的轨迹，而不依赖于未来的行为策略
加权版本
- Per-Decision 重要性采样算法的加权版本
$$
Q^{PDW}(s,a) = \frac{\sum_{m=1}^{M} \sum_{k=1}^{T_m - t_m} \gamma^{k-1} r_{t_m + k} \prod_{i=t_m+1}^{t_m+k-1} \frac{\pi_i}{b_i} }{\sum_{m=1}^{M} \sum_{k=1}^{T_m - t_m} \gamma^{k-1} \prod_{i=t_m+1}^{t_m+k-1} \frac{\pi_i}{b_i} }
$$ - 该估计是有偏一致估计
算法1：Per-Decision 重要性采样的资格迹版本
- 每个状态-动作对维护一个 eligibility trace \(e_t(s,a)\)
- 每一步更新：
$$
\begin{align}
e_t(s,a) &= e_{t-1}(s,a) \cdot \gamma \lambda \cdot \frac{\pi(s_t,a_t)}{b(s_t,a_t)} \\
\delta_t &= r_{t+1} + \gamma \frac{\pi(s_{t+1},a_{t+1})}{b(s_{t+1},a_{t+1})} Q_t(s_{t+1},a_{t+1}) - Q_t(s_t,a_t) \\
Q_{t+1}(s,a) &= Q_t(s,a) + \alpha e_t(s,a) \delta_t
\end{align}
$$ - Theorem 2 ：在离线更新下，该算法收敛到 \(Q^\pi\)
Tree Backup 算法
核心思想
- Tree Backup 不依赖于行为策略的显式概率，只需行为策略非饥饿（non-starving） ，即每个状态-动作对都会被无限次访问
- 在每一步，它考虑所有可能的动作，并根据目标策略的概率加权更新：
$$
Q_n^{TB}(s,a) = \frac{1}{M} \sum_{m=1}^{M} \left[ \gamma^n Q(s_{t_m+n}, a_{t_m+n}) \prod_{i=t_m+1}^{t_m+n} \pi_i + \sum_{k=t_m+1}^{t_m+n} \gamma^{k-t_m+1} \prod_{i=t_m+1}^{k-1} \pi_i \left( r_k + \gamma \sum_{a \neq a_k} \pi(s_k,a) Q(s_k,a) \right) \right]
$$ - 当 \(n=1\) 时，退化为 TD(0)
算法2：Tree Backup 的资格迹版本
- 更新 eligibility trace：
$$
e_t(s,a) = e_{t-1}(s,a) \cdot \gamma \lambda \pi(s_t,a_t) \\
e_t(s,a) = 1 \quad \text{If } \quad (s,a) \text{ is current state-action pair}
$$ - TD 误差：
$$
\delta_t = r_{t+1} + \gamma \sum_{a} \pi(s_{t+1},a) Q(s_{t+1},a) - Q(s_t,a_t)
$$ - 更新 Q：
$$
Q_{t+1}(s,a) = Q_t(s,a) + \alpha e_t(s,a) \delta_t
$$ - Theorem 3 ：对于任意非饥饿行为策略，算法收敛到 \(Q^\pi\)
作者实验结果
- 作者在 100 个随机生成的 MDP 上比较了以下方法：
- 重要性采样（IS）
- 加权重要性采样（WIS）
- 每决策重要性采样（PD）
- 加权每决策重要性采样（PDW）
- 单步 TD（TD(0)）
- Tree Backup（TB）
作者的结果总结
- IS 收敛慢，方差大
- WIS 显著优于 IS，更稳定
- PD 在行为策略均匀时表现良好，但在行为策略与目标策略差异大时表现较差
- PDW 在差异大的情况下优于 PD，但整体不如 TB
- Tree Backup（TB） 在所有设置中表现最好 ，尤其在中长期收敛速度和稳定性方面
建议：理论统一与扩展
- 论文还提出了 Tree Backup 和 Per-Decision 方法的统一视角：
- 在已知行为策略的地方，使用 Per-Decision 方法；
- 在未知或非平稳行为策略的地方，使用 Tree Backup；
- 两者可以结合，形成更鲁棒的 Off-policy 评估算法