离策略评价与逐步重要性采样

形式陈述

已有一批旧策略的运行日志，想知道另一策略的平均表现，却暂时不能让它重新与环境交互。这是离策略评价：数据由行为策略 $b$ 生成，评价对象是目标策略 $\pi$ 。本页讨论有限时域的轨迹重要性采样，并将“评价一个固定策略”与“从数据中学出最好策略”分开。

观测、目标与覆盖

每个回合有 $H\ge1$ 次决策，动作为有限集中的元素。时刻 $t$ 的可用历史为

\mathcal H_t=(S_0,A_0,R_1,S_1,\ldots,A_{t-1},R_t,S_t), \qquad t=0,\ldots,H-1.

采用历史依赖策略 $b_t(a\mid h)$ 与 $\pi_t(a\mid h)$ ；动作 $A_t$ 之后才产生奖励 $R_{t+1}$ 和下一状态。两种策略共享初始状态分布和环境的奖励—转移核。固定折扣 $0\le\gamma\le1$ ，目标是期望折扣回报

V^\pi=E_\pi\!\left[\sum_{t=0}^{H-1}\gamma^tR_{t+1}\right].

假定 $|R_{t+1}|\le M$ ，并采用一个便于逐步核对的覆盖条件：在每个可能历史上， $\pi_t(a\mid h)>0$ 都蕴含 $b_t(a\mid h)>0$ 。行为概率已知，评价时使用精确比值。目标策略预先固定；若由训练数据生成，则训练数据必须与评价回合独立，以下结论条件于训练结果使用。

在实际采到的动作上定义

\rho_t=\frac{\pi_t(A_t\mid\mathcal H_t)}{b_t(A_t\mid\mathcal H_t)}, \qquad W_{-1}=1,\qquad W_t=\prod_{k=0}^t\rho_k.

数据中出现的动作其行为概率为正；若目标不会选它，相应比值为零。 $W_t$ 是整个前缀的权重，不能只用最后一步的 $\rho_t$ 替代。

两种估计量

对一个行为回合，定义全轨迹和逐步贡献

Z_{\mathrm{full}}=W_{H-1}\sum_{t=0}^{H-1}\gamma^tR_{t+1}, \qquad Z_{\mathrm{pd}}=\sum_{t=0}^{H-1}\gamma^tW_tR_{t+1}.

将每个完整回合视为一个观测，给定 $n$ 个行为策略的独立同分布样本，分别取平均得到 $\widehat V_{\mathrm{full}}$ 和 $\widehat V_{\mathrm{pd}}$ 。在上述条件下，两者都无偏且几乎必然收敛到 $V^\pi$ 。若对应的 $Z$ 有有限二阶矩，则

\operatorname{Var}(\widehat V)=\frac{\operatorname{Var}_b(Z)}n.

例如，若目标可能选的动作都满足 $b_t(a\mid h)\ge\beta>0$ ，固定 $H$ 下各权重不超过 $\beta^{-H}$ ，二阶矩必有限。这个上界可能很大；覆盖保证能够换测度，不能保证少量回合足够精确。

前缀换测度证明

令 $\mathcal F_{t+1}=\sigma(\mathcal H_t,A_t,R_{t+1},S_{t+1})$ 。在离散情形，前缀概率分解为

\mu_0(s_0)\prod_{k=0}^t b_k(a_k\mid h_k)K_k(r_{k+1},s_{k+1}\mid s_k,a_k).

换成目标策略时，只把每个 $b_k$ 改成 $\pi_k$ 。初始分布与环境因子完全相同，逐项相消留下 $W_t$ 。对一般状态和奖励空间，同样的结论由逐层核积分成立：对任意有界前缀函数 $f$ ，依次把 $b_k\rho_k$ 替换为 $\pi_k$ ，得到

E_b[W_tf]=E_\pi[f], \qquad \frac{dP_\pi|_{\mathcal F_{t+1}}}{dP_b|_{\mathcal F_{t+1}}}=W_t.

这正是重要性采样在轨迹前缀上的换测度。取 $f=R_{t+1}$ ，再对有限个时刻相加，便有 $E_bZ_{\mathrm{pd}}=V^\pi$ ；取完整回报和 $t=H-1$ 则得到全轨迹版本。对 $|R_{t+1}|$ 使用同一恒等式可知各项可积，因此大数定律适用于独立回合的平均。证明没有把各步动作或各个奖励假定为相互独立。

直觉

一条日志里，早期选择会影响后来走到哪里，所以评价后期奖励时必须补偿整段过去的动作选择。但奖励一旦已经发生，再往后的随机选择并没有改变这笔收入。逐步权重就在该奖励产生时停止累乘。

两步轨迹中，第一笔奖励只乘到 W0，第二笔奖励乘到 W1；路径 AB 的后续权重为零，但第一笔奖励仍留下贡献。 — 每笔奖励使用自己的轨迹前缀

这种处理来自条件期望。因为

E_b[\rho_t\mid\mathcal H_t] =\sum_{a:b_t(a\mid\mathcal H_t)>0}\pi_t(a\mid\mathcal H_t)=1,

后续比值从最后一步向前依次积分为一。故

E_b[W_{H-1}\mid\mathcal F_{t+1}]=W_t, \quad E_b[W_{H-1}R_{t+1}\mid\mathcal F_{t+1}]=W_tR_{t+1}.

每一笔奖励的全轨迹贡献都被替换成自己的条件期望；二阶矩有限时，它的方差不会增加。不过，各时刻使用的条件信息不同，整笔回报的协方差也会改变。总方差必须另算，不能只把这些单项结论相加。

例子与边界

四条路径的一本完整账

取 $H=2$ 、 $\gamma=1$ 。行为策略每次独立地以 $1/2$ 选 $A$ 或 $B$ ，目标两次都选 $A$ 。设

R_1=\mathbf1_{\{A_0=A\}},\qquad R_2=2\mathbf1_{\{A_1=A\}}.

可把环境状态取为决策时刻，奖励由该时刻动作决定。四条行为路径等概率，目标回报为 $1+2=3$ 。

路径	$(R_1,R_2)$	$(W_0,W_1)$	$Z_{\mathrm{full}}$	$Z_{\mathrm{pd}}$
$AA$	$(1,2)$	$(2,4)$	$12$	$10$
$AB$	$(1,0)$	$(2,0)$	$0$	$2$
$BA$	$(0,2)$	$(0,0)$	$0$	$0$
$BB$	$(0,0)$	$(0,0)$	$0$	$0$

$AB$ 是两种记账法的关键差异。第一步确实执行了目标动作并收到奖励；第二步偏离目标，使完整轨迹权重归零，但逐步方法仍保留第一笔加权奖励 $2$ 。 $BA$ 则从第一步就偏离目标，所以后续前缀权重保持零，不能只因第二步选了 $A$ 就重新赋正权。

两种贡献的均值均为 $3$ ，方差分别为

\operatorname{Var}(Z_{\mathrm{full}})=\frac{12^2}{4}-3^2=27, \qquad \operatorname{Var}(Z_{\mathrm{pd}})=\frac{10^2+2^2}{4}-3^2=17.

这是一个逐步方法确实减少总方差的环境。对 $n$ 个独立回合平均后，方差分别为 $27/n$ 与 $17/n$ ；一次实际采样均值仍不必等于 $3$ 。

总方差排序为什么会反转

保持策略与路径概率，只把第二笔奖励改为 $R_2=-\mathbf1_{\{A_1=A\}}$ 。目标总回报为零。全轨迹权重只有 $AA$ 路径非零，而这条路径的奖励恰好 $1-1=0$ ，所以四条路径的 $Z_{\mathrm{full}}$ 全为零。

逐步贡献在 $AA,AB,BA,BB$ 上依次为 $-2,2,0,0$ 。因此两者仍无偏，但

\operatorname{Var}(Z_{\mathrm{full}})=0, \qquad \operatorname{Var}(Z_{\mathrm{pd}})=2.

单看第一笔奖励，其方差确实由 $3$ 降为 $1$ ；第二笔贡献的方差仍为 $3$ 。变化发生在两笔贡献的协方差：由 $-3$ 变为 $-1$ ，原来完全抵消的波动不再完全抵消。这个例子说明逐项条件平均的精确作用，也排除了“逐步 IS 总回报方差总是不大于全轨迹 IS”的普遍说法。

最后一笔奖励仍可能需要指数多的轨迹

取一般 $H$ ，行为仍每次等概率选 $A/B$ ，目标始终选 $A$ 。前 $H-1$ 笔奖励为零，只有全部动作均为 $A$ 时最后奖励为 $1$ 。用一个“截至当前是否全为 $A$ ”的状态位即可实现这个 MDP。

两种估计量此时完全相同：

Z=2^H\mathbf1_{\{\text{全部动作均为 }A\}},\quad E_bZ=1,\quad \operatorname{Var}_b(Z)=2^H-1.

$n$ 个行为回合没有任何有效轨迹的概率是 $(1-2^{-H})^n$ 。即使动作覆盖完整，也可能很长时间只看到估计值零，然后被一个巨大加权回报改变结果。逐步方法能去掉奖励之后的权重，却不能删去最后奖励所需的全部历史。

没有覆盖时，问题先失去可识别性

在单步环境中，若行为总选 $B$ ，目标总选 $A$ ，构造两个候选环境：两者的 $B$ 奖励均为零，但 $A$ 奖励分别为零和一。行为日志在任意样本量下分布完全相同，目标价值却不同。任何只读取这些日志的估计量也具有相同分布，因而不可能在两个环境中分别一致趋向不同答案。

这说明缺少覆盖不只是“分母为零不好计算”。在没有额外环境模型或结构信息时，日志本身没有决定目标价值。

推论与应用

执行与成本

对每个回合，令 $w=1,z=0$ ，按时间顺序计算比值、更新 $w\leftarrow w\rho_t$ ，再累加 $z\leftarrow z+\gamma^twR_{t+1}$ 。完成后把 $z$ 加入跨回合总和。可同时累加原始回报，最后乘终值权重以得到全轨迹版本。

当每步策略概率查询为常数成本时， $n$ 个长度 $H$ 回合共需 $O(nH)$ 次算术操作。除日志、策略表示和所需历史外，流式加权只需常数个累加器；若策略读取全历史，其存储和求值成本应另外计入。浮点乘积可能上溢、下溢；改用对数可稳定权重表示，但包含正负奖励的求和仍需相应数值处理。

评价协议决定保证针对什么

若策略由独立训练集得到，条件于该训练集就能把它视为固定策略，再应用本页证明。若在同一评价日志上比较大量策略并选取估计最高者，固定策略的无偏性不会自动变成最终所选策略的无偏评价。总体换测度对每个固定策略成立，数据选择带来的误差则需要另行控制。

本页也没有假设行为概率可以从日志频率无误恢复。把估计概率代入分母、截断大权重或进行自归一化，都会改变估计量，需重新分析误差。利用价值模型构造控制变量是另一条改进方向；不能把横断面的双重稳健公式不经序贯推导直接复制过来。

与TD 学习相比，这里的估计不使用下一状态的拟合价值作为自举目标；与REINFORCE相比，它评价价值而非计算策略梯度。它们都用轨迹数据，却承担不同的输出任务。

自测

在四路径正奖励例中，若只取得两个回合 $AA$ 与 $AB$ ，全轨迹和逐步估计各为多少？答案分别为 $(12+0)/2=6$ 和 $(10+2)/2=6$ 。本次两者相同且都高于真值，并不否定总体方差的 $27/n$ 与 $17/n$ 比较；方差评价的是全部可能数据集。

参考资料

Doina Precup, Richard S. Sutton, and Satinder Singh, “Eligibility Traces for Off-Policy Policy Evaluation”, Proceedings of ICML 2000, pp. 759–766，§4、Theorem 1 及附录证明：逐奖励前缀权重与无偏一致性。原文采用平稳 Markov 策略；本文在固定有限时域下用核分解给出允许历史依赖策略的证明。
Art B. Owen, Monte Carlo Theory, Methods and Examples, Chapter 9, 2013，§§9.1–9.3：重要性采样的覆盖、矩条件及自归一化区别。逐步总方差反例与指数时域算例由本文逐路径计算。

形式陈述 ​

观测、目标与覆盖 ​

两种估计量 ​

前缀换测度证明 ​

四条路径的一本完整账 ​

总方差排序为什么会反转 ​

最后一笔奖励仍可能需要指数多的轨迹 ​

没有覆盖时，问题先失去可识别性 ​

执行与成本 ​

评价协议决定保证针对什么 ​

自测 ​

反向链接