精读笔记

Problem Setting

Performance Bounds for Rollout Policies in Stochastic Shortest Path Problems（arXiv preprint / 2026）处理的是 SSP 中的 rollout policy 认证问题：已知一个近似 cost-to-go V，用它做 one-step greedy control，问 induced stationary policy π_R 相对 V* 的损失如何界定。

真正困难点在于 SSP 是 undiscounted transient problem。discounted MDP 中，局部 Bellman / value 误差天然被 1/(1-γ) 控制；finite horizon 中被 H 控制；而 SSP 中没有外生收缩或终止长度，误差能积累多久完全由执行策略自己的闭环 hitting time 决定。这意味着 rollout 的性能不是单靠 value approximation accuracy 可以说明的，还必须同时知道 greedy policy 是否 proper、以及它在非终端状态停留多久。

以前路线的卡点是视角错位：residual-based SSP bounds 更像是在分析 value iteration 或 Bellman equation 近似；经典 rollout improvement 往往相对 base policy 给保证；而这里的问题是一个任意 surrogate V 诱导出的 greedy closed loop 到底有多坏。关键矛盾是：局部 ε 级误差在每一步都很小，但 SSP 没有 discount，若策略长期不终止，小误差会线性累积成大损失。

Motivation

作者的核心观察是：SSP 中 approximate rollout 的有效 horizon 是 endogenous 的，不是问题设定给出的。换言之，应该把误差传播从“operator iteration / contraction”改写为“closed-loop occupation measure accumulation”。这正是 discounted ADP intuition 在 SSP 中缺失的一块。

已有分析不够的地方不是缺一个更紧的 Bellman residual inequality，而是缺一个 policy-specific certificate：给定已经形成的 rollout policy，如果它确实 transient，那么 value approximation error 会沿它自己的访问分布累积多少。这个问题在实际 planning 中很自然，因为 planner 真正执行的是 greedy policy，而不是 value iteration 的中间 iterate。

因此论文试图补的缺口是：从局部 value error 到全局 closed-loop cost gap 的直接通道。它不尝试解决 V 怎么来，也不尝试解决全局 SSP existence/selection/stability，而是把这些问题剥离出去，只刻画 rollout certificate 的结构。

Core Idea

论文最核心的思想是把 SSP rollout bound 写成 discounted approximate policy improvement bound 的 transient analog：局部误差 2ε，每访问一个非终端状态就可能付一次，直到 hitting terminal state。因此总损失 ≤ 2ε × expected number of nonterminal visits。这个形式非常干净，也基本是该问题中应有的答案。

本质区别在于建模方式的改变：prior 常把误差传播交给 Bellman operator 的 contraction 或 residual iteration；这篇把误差传播交给 induced policy 的 occupation measure。也就是说，信息流不是“V 经 T 反复传播”，而是“π_R 执行时经过哪些状态，局部 advantage 在这些状态上累加”。这使得 bound 既是 a posteriori 的，也是 policy-specific 的。

从 inductive bias 角度看，它强调的是 transient stability rather than contraction。对 SSP 来说，这比强行套 discounted 直觉更自然：只要闭环很快吸收，即使局部 value 近似不完美也可控；反之，即便 ε 很小，长 hitting time 也会把误差放大。

Method

1. Sup-norm non-expansiveness：解决从 ||V-V*||∞ 到 Bellman one-step error 的转换问题。因为 SSP 没有 contraction，作者只需要 non-expansiveness，而不是收缩。这一步的作用是证明 TV 距 V* 至多 ε。

2. One-step rollout inequality：解决 greedy w.r.t. V 是否也近似 greedy w.r.t. V* 的问题。由于 rollout 在 V 下最优，而 V 与 V* 相差 ε，TV 与 V* 又相差 ε，所以单步 Bellman advantage 被控制在 2ε。这里的 2ε 是整个主定理的局部误差来源。

3. Stopped-sum telescoping：解决 undiscounted infinite horizon 下如何合法累积误差的问题。通过 τ∧m 截停，把 V*(x_k)-V*(x_{k+1}) telescoping 成 V*(x)-V*(x_{τ∧m})，再用 properness 与 dominated/monotone convergence 令 m→∞。这一步把局部 inequality 转成全局 cost gap。

4. Performance-difference identity：解决 bound 是否只是松的 sup-norm artifact 的问题。它证明任意 proper stationary policy 的 suboptimality 精确等于 optimal advantage A*(x,u) 在 transient occupation measure 下的积分。这是论文最有解释力的部分。

5. Hitting-time / Lyapunov corollaries：解决 E[τ] 如何被 checkable 上界替代的问题。uniform E[τ]≤N 给 2Nε；Foster–Lyapunov drift 给 E[τ]≤L(x)/c。它们不是新算法，而是把 certificate 变成可用形式。

6. CE rollout extension：解决 certainty-equivalent lookahead 中用 nominal w̄ 替代 expectation 的额外误差。δ 衡量 one-step nominal evaluation 与 true expectation 的差异；最终只是把 ε 替换成 ε+δ，并同样按 hitting time 累积。

Key Insight / Why It Works

最关键 insight 是：SSP rollout 的误差传播对象不是 Bellman operator，而是 rollout policy 的 transient occupation measure。这个判断非常重要，因为它解释了为什么 discounted / finite-horizon 的直觉在 SSP 中不完整：没有 γ 或 H 时，唯一能截断误差的就是闭环到达 terminal 的速度。

真正有效的原因是 three-part decomposition 很干净：value approximation error → one-step optimal advantage bound → occupation-measure accumulation。第一步是普通 sup-norm stability；第二步是 rollout greedy 性质带来的局部控制；第三步是 SSP 特有的 transient telescoping。核心贡献主要在第二、第三步的组合，以及用 performance-difference identity 明确说明 hitting-time factor 是结构性的。

sharpness example 很有说服力：deterministic chain 中 V 对所有非终端状态给一个小负偏置，greedy policy 就会被诱导不断 continue，每步付 ε/2，最终损失线性随链长增长。这说明问题不是证明技巧保守，而是 rollout 决策本身会把均匀小误差转化为每步小偏差，并沿轨迹累积。

哪些部分更像辅助？Lyapunov drift corollary 是标准 Foster–Lyapunov 工具；CE 扩展也是直接把 nominal-model mismatch 作为额外 local error 累加。它们有用，但不是概念上最核心的新东西。真正可迁移的是 occupation-measure view。

这篇不是 scaling、不是 retrieval、不是 data coverage，也没有 test-time compute 的实证论点。它属于理论 certification paper。若硬要类比，贡献是 better problem-specific inductive bias：把 SSP 的有效 horizon 建模为 closed-loop hitting time，而不是沿用 discounted contraction。

Relation To Prior Work

最接近的谱系有三条：discounted / finite-horizon approximate dynamic programming 的 approximate policy improvement bounds；SSP Bellman residual / value-iteration error bounds；classic rollout / policy improvement analysis。

和 discounted ADP 的本质差异是 amplifier 从 1/(1-γ) 变成 E_{π_R}[τ]。这不是简单替换符号，因为 E[τ] 是 policy-induced、需要 properness、且可能随近似 V 改变。也就是说，bound 的 horizon 与被认证策略耦合。

和 SSP residual bounds 的差异是对象不同。Residual bounds 通常问一个 value iterate 离 V* 多远；这篇问一个由 V 贪心化得到的 closed-loop policy 离最优 cost 多远。前者是 operator-centric，后者是 policy/occupation-centric。

和传统 rollout improvement 的差异是比较基准不同。经典 rollout 常强调相对 base policy 的 improvement；这里直接比较 V*，但代价是要求 V uniformly approximates V*，并要求 rollout policy proper。这个假设比 base-policy improvement 更强，也使结论更像 certification 而非 improvement theorem。

看似新的 CE rollout bound，本质是已有 simulation lemma / model mismatch accumulation 思想在 SSP hitting-time setting 下的重写；实质新增信息在于 mismatch δ 与 value error ε 进入同一个 transient occupation amplifier。

Dataset / Evaluation

没有数据集、实验 benchmark 或真实系统评估。论文包含机器人导航和 minimum expected hitting time 的解释性例子，但这些不是 empirical evaluation，也没有验证实际 planner 的性能。

从理论论文角度，evaluation 是 theorem + sharpness construction。它确实验证了核心 claim：hitting-time amplification 不可避免，且 occupation measure 是正确的误差累积对象。deterministic chain 反例足以排除不依赖 E[τ] 的 universal O(ε) bound。

但它没有验证几个实践层面的 claim：如何估计 ε；learned V 的统计误差是否能达到全局 sup-norm；CE mismatch δ 是否可计算；在机器人导航这种高维连续系统中 Lyapunov drift / properness 如何验证。文中相关应用描述更像 motivation，不构成 empirical support。

Limitation

最核心限制是 properness 被作为条件假设。SSP 中最难的稳定性问题没有被解决：rollout policy 可能因为近似误差而进入长循环甚至不终止；此时 theorem 不给有意义保证。换句话说，论文把“策略是否安全到达终端”与“到达后损失多大”分开了，后者被很好刻画，前者仍需外部证明。

第二个限制是全局 sup-norm error ||V-V*||∞≤ε 很强，尤其在连续/高维 SSP 中通常不可验证。作者提到 local / weighted extensions，但正式主结果仍依赖 boundedness 与 uniform approximation。实际 learned value function 更可能只有 distributional 或 high-probability error；如何转成 occupation-weighted bound 文中未充分说明。

第三，E[τ] 本身是 rollout policy 下的量，可能难以事前知道。Lyapunov drift 是标准可检验替代，但找到 L 和 c 往往不比分析策略容易。若只靠模拟估计 E[τ]，certificate 又变成统计估计问题，论文未覆盖。

第四，CE 的 δ 定义为对所有 state-action 的 sup mismatch，可能极端保守；而若只在 visited region 上估计 δ，又需要知道访问分布。这里的问题被转移为 model mismatch certification。文中未充分说明 δ 在真实 nominal-model planning 中是否可操作。

最后，这不是一个算法贡献。它不会让 rollout 更好，只告诉你在给定 V、给定 properness、给定 hitting-time control 时性能如何。实际增益来源不涉及 scaling / data，而在于理论解释；若把它用于 learned planners，核心能力很可能仍主要来自 value/model 的数据覆盖，本文只提供误差如何累积的外壳。

Takeaway

• 1. SSP rollout 的正确误差放大因子是 closed-loop hitting time / transient occupation measure；不要在 undiscounted problem 中套 discounted contraction 直觉。
• 2. Performance-difference identity 是比主 bound 更值得记住的结构：suboptimality = optimal advantage under occupation measure。
• 这个公式可迁移到 state-dependent error、weighted norm、model mismatch、inexact planning 等场景。
• 3. 对 learned value / learned model 的下一步不是再证明一个 2εE[τ]，而是把 ε、δ、E[τ] 都变成可统计认证、局部化、policy-dependent 的量。

一句话总结

这篇论文把 SSP rollout 的性能分析从 Bellman-residual / contraction 视角转到 closed-loop occupation-measure 视角，明确证明局部 value/model 误差必须按 hitting time 线性累积，是一篇理论型 rollout certification work。