Model-based Bootstrap of Controlled Markov Chains

📄 arXiv: 2605.12410v1 📥 PDF

作者: Ziwei Su, Imon Banerjee, Diego Klabjan

分类: stat.ML, cs.LG, math.OC, math.ST

发布日期: 2026-05-12

备注: 45 pages, 7 figures, 19 tables

💡 一句话要点

提出基于模型的Bootstrap方法，用于控制马尔可夫链的离线策略评估与优化。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 离线强化学习 Bootstrap方法 控制马尔可夫链 策略评估 置信区间 模型不确定性 重采样

📋 核心要点

  1. 离线强化学习中，行为策略未知导致难以准确评估和优化策略，现有方法在小样本量下表现不佳。
  2. 论文提出基于模型的Bootstrap方法，通过重采样转移核来估计不确定性，从而构建更可靠的置信区间。
  3. 实验表明，该方法在RiverSwim问题上优于现有Bootstrap方法和CLT方法，置信区间覆盖率更接近标称值。

📝 摘要（中文）

本文提出并分析了一种基于模型的Bootstrap方法，用于有限控制马尔可夫链（CMCs）中的转移核估计。该方法适用于具有非平稳或历史依赖控制策略的情况，这在离线强化学习（RL）中很常见，尤其是在生成数据的行为策略未知时。我们证明了Bootstrap转移估计器在单条长链和情景式离线RL机制下的分布一致性。关键技术包括：访问计数的Bootstrap大数定律（LLN）以及Bootstrap转移增量的鞅中心极限定理（CLT）。通过验证贝尔曼算子的Hadamard可微性，我们将Bootstrap分布一致性扩展到离线策略评估（OPE）和最优策略恢复（OPR）的下游目标，通过delta方法为价值函数和Q函数产生渐近有效的置信区间。在RiverSwim问题上的实验表明，所提出的Bootstrap置信区间（CIs），特别是百分位CIs，优于情景式Bootstrap和plug-in CLT CIs，并且通常接近标称覆盖率（50％，90％，95％），而基线在小样本量和短episode长度下校准不良。

🔬 方法详解

问题定义：论文旨在解决离线强化学习中，由于行为策略未知，导致无法准确评估和优化策略的问题。现有的方法，如plug-in估计和情景式Bootstrap，在小样本量和短episode长度下，置信区间的校准效果较差，无法提供可靠的策略评估和优化依据。

核心思路：论文的核心思路是利用Bootstrap方法对控制马尔可夫链的转移核进行重采样，从而估计转移核的不确定性。通过对转移核进行多次重采样，可以构建价值函数和Q函数的置信区间，从而更准确地评估策略的性能。这种方法的核心在于，它直接对模型的不确定性进行建模，而不是仅仅依赖于经验数据。

技术框架：整体框架包括以下几个主要步骤：1) 基于观测到的数据，估计控制马尔可夫链的转移核；2) 使用Bootstrap方法对转移核进行重采样，生成多个转移核的样本；3) 对于每个重采样的转移核，计算价值函数和Q函数；4) 基于价值函数和Q函数的样本，构建置信区间。该框架的关键在于如何有效地进行转移核的重采样，以及如何利用重采样的结果构建置信区间。

关键创新：论文的关键创新在于提出了一个适用于控制马尔可夫链的Bootstrap方法，并证明了该方法在单条长链和情景式离线RL机制下的分布一致性。此外，论文还提出了一个新的Bootstrap大数定律（LLN）用于访问计数，并利用鞅中心极限定理（CLT）分析了Bootstrap转移增量的性质。与现有方法的本质区别在于，该方法直接对模型的不确定性进行建模，而不是仅仅依赖于经验数据，从而能够更准确地估计策略的性能。

关键设计：论文的关键设计包括：1) 使用最大似然估计来估计转移核；2) 使用多项式分布对转移核进行重采样；3) 使用delta方法将Bootstrap分布一致性扩展到离线策略评估和最优策略恢复的下游目标；4) 使用百分位法构建置信区间。这些设计保证了Bootstrap方法的有效性和可靠性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，所提出的Bootstrap置信区间在RiverSwim问题上优于情景式Bootstrap和plug-in CLT CIs。特别是百分位CIs，其覆盖率更接近标称值（50％，90％，95％），表明该方法能够更准确地估计策略的性能，并提供更可靠的置信区间。在小样本量和短episode长度下，基线方法的校准效果较差，而该方法仍然能够保持良好的性能。

🎯 应用场景

该研究成果可应用于各种离线强化学习场景，例如医疗诊断、金融交易、推荐系统等。在这些场景中，通常难以获取大量的在线交互数据，因此离线强化学习方法具有重要的应用价值。通过使用该方法，可以更准确地评估和优化策略，从而提高决策的质量和效率，降低风险。

📄 摘要（原文）

We propose and analyze a model-based bootstrap for transition kernels in finite controlled Markov chains (CMCs) with possibly nonstationary or history-dependent control policies, a setting that arises naturally in offline reinforcement learning (RL) when the behavior policy generating the data is unknown. We establish distributional consistency of the bootstrap transition estimator in both a single long-chain regime and the episodic offline RL regime. The key technical tools are a novel bootstrap law of large numbers (LLN) for the visitation counts and a novel use of the martingale central limit theorem (CLT) for the bootstrap transition increments. We extend bootstrap distributional consistency to the downstream targets of offline policy evaluation (OPE) and optimal policy recovery (OPR) via the delta method by verifying Hadamard differentiability of the Bellman operators, yielding asymptotically valid confidence intervals for value and $Q$-functions. Experiments on the RiverSwim problem show that the proposed bootstrap confidence intervals (CIs), especially the percentile CIs, outperform the episodic bootstrap and plug-in CLT CIs, and are often close to nominal ($50\%$, $90\%$, $95\%$) coverage, while the baselines are poorly calibrated at small sample sizes and short episode lengths.