Model-Based Bootstrap of Controlled Markov Chains¶

会议: NeurIPS 2026
arXiv: 2605.12410
领域: 强化学习
关键词: 受控马尔可夫链、模型自举法、离线强化学习、策略评估、渐近正态性

一句话总结¶

针对未知非平稳或依赖历史的行为策略所生成的离线受控马尔可夫链数据，本文提出了基于模型的转移核自举法，证明了单长链与多片段机制下的渐近分布一致性，并通过 Hadamard 可微性推广至离线策略评估与最优策略恢复。

研究背景与动机¶

在离线强化学习与序列决策评估中，对下游策略价值 \(V^\pi\)、\(Q^\pi\) 以及最优值函数 \(V^\star\)、\(Q^\star\) 进行不确定性量化与置信区间构建是确保安全部署的关键环节。经典的统计推断通常依赖中心极限定理（CLT）推导渐近方差并构造代入式区间，但渐近方差包含复杂的逆矩阵与极限占用测度，在有限样本下估计误差极大，容易导致置信区间覆盖率严重失准。自举法（Bootstrap）理论上能够绕过繁琐的渐近方差解析估计并提供更高阶精度的置信区间，但在强化学习领域现有的马尔可夫自举技术仍存在明显空白。

现有的马尔可夫链自举方法（例如 Horowitz 的再生核自举或基于 Nummelin 分裂的再生块自举）绝大多数仅适用于无控制输入的被动马尔可夫链，且严格依赖稳态遍历性、几何遍历混合或平稳分布假设。然而，在离线强化学习的标准设定中，用于采集离线数据的行为策略通常是由未知专家系统、时变探索策略甚至人类操作者交互生成的，往往展现出强烈的非平稳性（Non-stationary）和长历史依赖性（History-dependent）。由于行为策略不是马尔可夫策略，状态-动作对联合序列并不构成时间齐次马尔可夫链；若直接对片段级别进行经典 i.i.d. 自举，在小样本或片段数目有限时极易发生重抽样方差塌缩。

为了解决非平稳行为策略下马尔可夫转移核估计与强化学习下游推断的理论难题，本文提出了针对有限受控马尔可夫链（CMC）的模型自举法。核心 idea：利用单步经验访问频率构造经验行为策略与经验转移核，自举模拟生成结构相同的虚拟轨迹；在理论上证明转移核自举统计量弱收敛于真实渐近高斯分布，并通过 Bellman 算子的 Hadamard 可微性将一致性推广至策略评估与最优策略恢复。

方法详解¶

整体框架¶

本文的方法 pipeline 围绕离线受控马尔可夫链的数据生成、经验估计、自举重采样以及下游策略评估展开。给定由未知且可能非平稳的行为策略生成的离线数据集 \(\mathcal{D}_n\)，算法首先统计每个状态-动作对的转移计数，构建一步经验转移核与经验行为策略；随后在虚拟环境中以真实起点初始化并驱动 CMC 自举轨迹生成，从而获取 \(B\) 组自举转移矩阵副本；最后将经验估计与自举副本分别代入 Bellman 方程或 Bellman 最优方程，计算分位数置信区间。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["离线轨迹数据 Dn<br/>K 个片段，每段长 T"] --> B["1. 经验统计与模型构建<br/>统计转移计数计算经验转移核与经验策略"]
    B --> C["2. 虚拟自举链模拟<br/>复制初始状态生成 B 组自举数据集"]
    C --> D["3. 极限定理与下游推断<br/>利用 Delta 方法与 Bellman Hadamard 导数构建 CI"]
    D --> E["输出目标置信区间<br/>OPE / OPR 的百分位数与枢轴 CI"]

关键设计¶

1. 经验统计与模型构建：消除对复杂历史依赖策略建模的依赖 离线数据生成过程中的行为策略可能依赖任意长的历史决策，若试图显式拟合一个复杂的时变策略生成器不仅会引入严重的模型误设误差，而且在计算上难以实现。本文的关键洞察在于：尽管数据生成策略具有非平稳或历史依赖特征，受控马尔可夫链的状态转移核本身仍具有条件一阶马尔可夫性，其渐近协方差仅取决于行为策略诱导的遍历占用测度 \(p_s^{(a)}\)。因此，方法仅需从数据集 \(\mathcal{D}_n\) 统计状态-动作访问频次 \(N_s^{(a)} = \sum_{t} N_{s,t}^{(a)}\) 以及状态跳转频次 \(N_{s,t}^{(a)}\)，直接构建一步经验转移估计 \(\hat{M}_{s,t}^{(a)} = N_{s,t}^{(a)} / N_{s}^{(a)}\) 与经验行为策略 \(\hat{\pi}_b(a \mid s) = N_s^{(a)} / N_s\)。对于零计数的未访问状态-动作对，采用将其视为自环（\(\hat{M}_{s,\cdot}^{\text{sim},(a)} = \delta_s\)）的修正策略，保证了有限样本模拟的稳健性且不改变大样本渐近性质。

2. 虚拟自举链模拟：保持真实片段初始分布与拼接单链统一 在离线多片段强化学习场景中，各 episode 的重置机制往往由外部环境决定，可能存在跨片段依赖且无法通过有限数据完全识别。为此，自举生成过程直接复制原始数据集每个片段的真实初始状态 \(X_0^{\ast(k)} := X_0^{(k)}\)，并在自举转移中采用经验核 \(\hat{\mathbf{M}}\) 与经验策略 \(\hat{\pi}_b\) 独立模拟生成 \(B\) 组自举数据集 \(\mathcal{D}_n^{\ast(j)}\)。为了建立多片段条件下的理论收敛性，论文设计了一种在连续片段之间插入伪重置动作 \(a_\dagger\) 的单链嵌入技术，将总长度为 \(n=KT\) 的片段数据转化为等价的拼接单链 \(\tilde{\mathcal{D}}\)。该虚拟单链继承了原始链的弱混合性（Weak \(\bar{\eta}\)-Mixing）与子线性返回时间增长性质，使得自举访问计数满足自举大数定律：

\[ \frac{N_s^{\ast(a)}}{n} \xrightarrow{\text{a.s.}} p_s^{(a)} \]

3. 极限定理与下游推断：基于鞅差分解与 Hadamard 可微性的 Delta 推广 为了证明自举转移核统计量 \(\sqrt{n}\,\mathrm{vec}(\hat{\mathbf{M}}^\ast - \hat{\mathbf{M}})\) 条件弱收敛于真实渐近正态分布 \(\mathcal{N}(0, \bar{\Lambda})\)，本文将估计误差分解为主导鞅差和与高阶残差项，通过构造联合滤波并验证 Lindeberg 条件，利用鞅中心极限定理克服了自举样本间的时序依赖性。进一步地，为了将分布一致性推广到离线策略评估（OPE）的目标值函数 \(V^\pi, Q^\pi\) 以及最优策略恢复（OPR）的目标 \(V^\star, Q^\star\)，本文严格证明了 Bellman 逆算子映射 \(\mathbf{M} \mapsto (I-\gamma\Pi\mathbf{M})^{-1}g\) 在连续扰动下的 Hadamard 可微性：

\[ V_{\mathbf{M}}^\prime(H) = \gamma (I - \gamma \Pi \mathbf{M})^{-1} \Pi H V_\pi(\mathbf{M}) \]

对于含有非平稳非线性 \(\arg\max\) 操作的最优策略恢复，利用最优动作间隙非退化条件证明了最优策略在真实转移矩阵邻域内的局部常数性，使得经典自举 Delta 方法得以适用，确保了百分位数置信区间 \([q_{\alpha/2}^\ast, q_{1-\alpha/2}^\ast]\) 在 \(n \to \infty\) 下的渐近严格有效性。

损失函数 / 训练策略¶

该方法为基于经验频率计数与动态规划解析求解的非参数自举框架，不需要梯度下降训练神经网络。在下游推断中，针对策略评估直接利用逆矩阵求解线性方程组：\(\hat{V}_\pi^{\ast(j)} = (I - \gamma \Pi \hat{\mathbf{M}}^{\ast(j)})^{-1} g\)；针对最优策略求解通过策略迭代或值迭代求解最优 Bellman 算子固定点。单次自举轨迹模拟时间复杂度为 \(O(Bn)\)，下游 Bellman 求解开销为 \(O(B S^3)\) 或多项式级，整体计算效率高且易于完全并行化。

实验关键数据¶

主实验¶

实验基于经典的强化学习探索基准 RiverSwim 环境（\(S=6\) 个状态，\(A=2\) 个动作，折扣因子 \(\gamma=0.95\)）。行为策略设定为倾向向右游动的平稳策略 \(\pi_b(1 \mid s) = 0.8\)；由于上游状态（状态 6）访问频次极低且左端状态 1 处最优动作间隙极小，对统计推断的覆盖率校准构成严峻考验。实验设置自举次数 \(B=1,000\)，蒙特卡洛重复试验 \(N_{\text{reps}}=1,000\) 次，考察名义水平为 95%（\(\alpha=0.05\)）的置信区间覆盖率。下表展示了均匀目标策略下 OPE 在片段长度 \(T=50\) 时的各方法对比：

数据集 / 样本规模 \(n\)	指标 / 参数目标	本文模型自举 (Percentile)	经典片段自举 (Episodic)	渐近正态代入 (Plug-in CLT)	提升 / 相对表现
RiverSwim (\(n=50, T=50, K=1\))	\(V^\pi(1)\) 覆盖率	0.896	0.000	0.849	片段自举完全崩溃，本文最接近名义值
RiverSwim (\(n=50, T=50, K=1\))	\(Q^\pi(1,0)\) 覆盖率	0.896	0.000	0.849	单片段下重采样零方差，本文保持有效方差
RiverSwim (\(n=100, T=50, K=2\))	\(V^\pi(2)\) 覆盖率	0.938	0.519	0.929	显著改善小片段数目下的严重欠覆盖
RiverSwim (\(n=500, T=50, K=10\))	\(V^\pi(1)\) 覆盖率	0.950	0.910	0.948	达到严格的名义 95% 覆盖率水平
RiverSwim (\(n=500, T=50, K=10\))	\(Q^\pi(3,1)\) 覆盖率	0.961	0.921	0.957	各状态动作表现均衡且方差更稳健
RiverSwim (\(n=1000, T=50, K=20\))	\(V^\pi(6)\) 覆盖率	0.966	0.936	0.922	稀疏访问的上游状态依然逼近名义值

消融实验¶

实验对比了不同自举区间构建形式（百分位数 Percentile CI vs. 枢轴 Pivot CI）以及在最优策略恢复（OPR，目标为 \(V^\star, Q^\star\)）中不同片段长度 \(T\) 与样本总量 \(n\) 对置信区间质量的影响（名义覆盖率 95%）：

配置 / 任务设定	关键指标 (\(Q^\star(1,0)\))	关键指标 (\(V^\star(5)\))	关键指标 (\(V^\star(6)\))	说明
模型自举 (Percentile, \(T=50, n=500\))	0.957	0.964	0.970	完整模型：各状态均达到或接近 95% 名义覆盖率
模型自举 (Pivot, \(T=50, n=500\))	0.468	0.827	0.834	枢轴区间在非退化边界处发生对称性假设偏差导致欠覆盖
模型自举 (Percentile, \(T=50, n=100\))	0.667	0.669	0.555	样本量降至 100 时因遍历估计偏差覆盖率有所回落
模型自举 (Percentile, \(T=10, n=500\))	0.457	0.884	0.892	短片段长降低了遍历混合效率，稀疏区域收敛变缓
片段自举 (Percentile, \(T=50, n=500\))	0.886	0.880	0.899	片段级别重抽样忽略内部依赖，系统性欠覆盖约 6-7%
代入式 CLT (Plug-in, \(T=50, n=500\))	0.489	0.882	0.880	有限样本协方差估计误差导致置信区间显著偏窄

关键发现¶

在小样本量（\(n=50, K=1\)）极端场景下，基于完整轨迹重抽样的经典片段自举法（Episodic Bootstrap）由于无法产生轨迹间变异，其方差估计完全退化为 0（覆盖率为 0.000）；而本文模型自举法通过在估计出的转移核上模拟新轨迹，依然能够提供高达 0.896 的可靠覆盖率。
在置信区间类型选择上，基于经验分位数的百分位数置信区间（Percentile CI）在各项任务中均显著优于枢轴置信区间（Pivot CI）；尤其是在 RiverSwim 状态 1 处，最优动作间隙趋于零（\(Q^\star(1,0) \approx Q^\star(1,1)\)），枢轴法受高阶项不对称性影响出现显著欠覆盖，而百分位数法在 \(n \ge 500\) 时仍能恢复近乎名义水平（0.957）的优异表现。
覆盖率对片段长度 \(T\) 呈现单调递增趋势；当 \(T=10\) 时，各状态混合不充分导致稀疏状态转移核估计方差偏大，而在 \(T=50\) 与 \(T=100\) 时，模型自举法在 \(n \ge 500\) 下的覆盖率稳定收敛在 0.92 至 0.97 之间。

亮点与洞察¶

打破了马尔可夫链自举必须依赖稳态或齐次行为策略的长期理论局限，巧妙证明了一步经验统计量在非平稳甚至任意历史依赖行为策略下依然能够一致逼近极限占用测度。
将 Bellman 方程矩阵反演与最优 Bellman 算子局部常数性紧密结合，成功打通了从底层转移矩阵正态极限定理到高层强化学习价值函数推断的 Delta 方法理论桥梁。
相比需要估计高维复杂渐近协方差逆矩阵的经典 CLT 方法，模型自举法完全规避了繁琐的协方差代入估计，以 \(O(Bn)\) 的低计算代价换取了更精准的有限样本置信区间。

局限与展望¶

论文目前假设奖励函数 \(r(s,a)\) 为已知确定量；尽管作者指出若奖励估计量依概率收敛则结论依然成立，但在有限样本下奖励与转移联合估计带来的双重方差叠加效应仍需进一步分析。
理论结果仅严格建立在有限状态与动作空间（Tabular Case）中；对于采用深度神经网络或连续状态空间函数逼近的现代强化学习场景，模型自举的有效性与收敛性尚未得到理论证明。
在片段机制下，当前渐近分析仅针对固定 \(T\) 且片段数 \(K \to \infty\) 的制度；对于片段数固定而片段长 \(T \to \infty\) 的混合渐近机制，理论自举一致性仍属开放问题。

评分¶

新颖性: ⭐⭐⭐⭐☆ 首次为非平稳控制策略下的受控马尔可夫链与强化学习下游任务建立了严格的模型自举极限定理。
实验充分度: ⭐⭐⭐☆☆ 在经典的 RiverSwim 难探索基准上进行了多维度多区间的细致检验，但缺乏复杂环境或连续控制任务实验。
写作质量: ⭐⭐⭐⭐⭐ 数学推导严密规范，从大数定律、鞅 CLT 到 Hadamard 微分与 Delta 方法的逻辑链条极其清晰。
价值: ⭐⭐⭐⭐☆ 为离线强化学习安全部署、离线策略评估与高置信度策略优化提供了扎实的统计推断理论工具。