精读笔记

Problem Setting

这篇论文实际解决的是 deterministic discrete-time infinite-horizon optimal control 中 VI 的“有限停止后果”问题：不是问 V_i 是否渐近收敛到 V_*，而是问在某个有限 i 停下后，H_{γ,i} 产生的 feedback law 是否稳定、V_i 距 V_* 多远、以及 stopping rule 是否一定会被触发。

真正困难点在于，一般系统和一般 stage cost 下，VI 的经典收敛通常不足以支撑常用 stopping criterion 的有限满足性。相邻 value function 差小并不是局部数值现象，而是需要某种 uniform control；否则即便点态收敛成立，也不能保证在整个兴趣集 X 上存在统一有限 i。

关键矛盾是：实际计算必须有限步停止，但控制保证通常建立在无限步最优 value 或收敛极限上。传统路线把 stopping tolerance 当作数值误差阈值，而本文把它当成闭环稳定性和性能界的一部分来设计。

Motivation

已有 VI / ADP 文献常用 ||V_{i+1}-V_i||∞≤ε 或类似准则，但通常只把它作为 implementation convention，没有回答两个核心问题：这个准则什么时候有限步满足；满足后得到的 policy 是否稳定、性能损失是否可量化。

作者的核心观察是，停止准则不能只看“value 变化小不小”，还必须看这个差异在 Lyapunov 下降不等式里以什么形式出现。如果 c_stop 是常数，就自然得到 practical stability；如果 c_stop 随 σ(x) 缩放，就可能得到 asymptotic / exponential stability；如果再随 γ^i 缩放，就能改善近最优界的可调性。

关键缺口是 stopping criterion 的设计理论，而不是 VI 更新本身。论文试图填的是“finite computation → closed-loop guarantee”的断层。

Core Idea

论文的核心思想是把 VI 的停止误差解释为 Lyapunov 下降中的可设计扰动。由于 V_{γ,i} 可由有限时域最优控制问题解释，且在 detectability / stabilizability 条件下满足 α_lower(σ(x))≤V_{γ,i}(x)≤α_upper(σ(x))，所以 V_{γ,i} 可以作为非最优但可用的 Lyapunov-like 证书。

一旦 stopping rule 保证 |V_{i+1}-V_i|≤c_stop，greedy policy 的 Bellman 等式可以转化为 V_i(f(x,h_i(x)))-V_i(x)≤-α(σ(x))/γ_*+c_stop/γ_*。这就是整篇论文的机制核心：c_stop 不再只是停机条件，而是稳定裕度的扰动项。

与 prior 的本质差异在于，经典分析多关注 VI 极限或给 discounted MDP 中的误差界；本文关注 finite final iterate，并且让 stopping rule 的函数形状决定稳定和性能类型。这不是 scaling，也不是新的优化算法，而是一个 certificate-oriented reformulation。

Method

1. Well-posedness / recursive feasibility：先确保每一轮 Bellman backup 的 infimum 实际达到 minimum，从而 H_{γ,i}(x) 非空。这个步骤解决的是 policy 在有限迭代中是否存在的问题，否则后续谈稳定性没有对象。

2. Detectability + stabilizability bounds：用 stage cost 下界 ℓ(x,u)≥α_lower(σ(x)) 和 value 上界 V_i,V_*≤α_upper(σ(x)) 建立 value 与状态度量 σ 的等价控制。它的作用是把 value iteration 产生的 V_i 转化为 Lyapunov 证书，而不是仅作为 cost approximation。

3. Generalized stopping criterion：定义 |V_{i+1}-V_i|≤c_stop(x,θ,γ,i)，允许 c_stop 依赖状态、折扣、迭代数和参数。这个泛化的关键变化是让停止准则可以匹配稳定性需求，例如常数型给 practical，σ(x) 型给 asymptotic / exponential 的可能。

4. Finite termination conditions：Condition 1 给出 c_stop 下界形式，证明在相应集合上存在有限停止迭代。这里的关键是利用 V_i 与 V_* 的统一夹逼估计，把相邻迭代差控制到 c_stop 以下。

5. Stability via embedding：把最终 greedy closed-loop 嵌入到更大的差分包含系统 \hat H 中。这样只要证明嵌入系统稳定，原系统自动继承。这个技巧避免了处理 argmin 非唯一和 stopping-satisfied policy 的细节。

6. Near-optimality bounds：将 stopping error 沿有限 / 无限闭环轨迹传播，得到显式依赖 c_stop 的 |V_i−V_*| 界。重要点是这些界在 γ=1 时不必像经典 discounted bound 那样爆炸。

Key Insight / Why It Works

最核心的贡献是把 stopping tolerance 的“形状”与控制保证建立了精确对应。常数 tolerance 只能保证 practical stability，因为在接近 attractor 时 c_stop 不消失，会破坏严格下降；状态相关 tolerance 如 θσ(x) 在 x→attractor 时同步消失，因此可以恢复渐近甚至指数稳定。这是本文最值得迁移的 insight。

方法成立的根本原因不是 VI 算得更好，而是 cost detectability 让 stage cost 能观测 σ(x)，stabilizability 让所有 V_i 被 σ(x) 上界控制，二者共同把 Bellman residual 变成 Lyapunov residual。换言之，论文利用的是 optimal control problem 自身的 dissipativity / Lyapunov structure，而非数值迭代的特殊技巧。

有限终止证明依赖一个关键统一收敛型估计：V_i 与 V_* 的差可被 ξ(σ(x),i) 控制，且 ξ 随 i 下降到 0。这个结果绕开了一般 VI 只有点态收敛的问题，但它不是免费午餐；它建立在较强的可稳定性和比较函数结构上。

哪些是核心，哪些是辅助：核心是 c_stop 作为 Lyapunov perturbation；辅助是各种 Condition 1/2 的枚举和具体 c_stop 表格。γ^i 因子本身不是深层创新，但它是一个有效工程化设计：让 near-optimality bound 中的 γ^{-i} 抵消，从而得到更干净、可调的误差界。

这篇论文不属于 scaling / data / retrieval / representation alignment 路线；它是 certificate design。增益来源很清楚：不是更强 optimizer，而是把 stopping rule 设计成满足稳定性证明所需的残差结构。若用于近似 RL，核心能力不会自动迁移，因为这里完全没有处理 function approximation error。

Relation To Prior Work

最接近的谱系是动态规划 / ADP 中的 VI stopping criterion、MPC 稳定性分析、以及 discounted infinite-horizon optimal control 的 Lyapunov 分析。它和经典 Bertsekas / Puterman 式 VI 结果的区别在于，后者多关注收敛或误差界，本文关注有限停止时刻的闭环性质。

与 MPC 文献的关系很强：V_i 被解释为有限时域 optimal control 的 value，初始 value function 是 terminal cost。稳定性证明本质上借用了 MPC 中 finite-horizon value as Lyapunov function 的思路，只是这里 horizon 是 VI iteration index，停止准则成为 suboptimality / early termination residual。

相对于作者早期工作 [14]/[16]，本文实质扩展在于允许 discounted cost、非零初始 value function、更一般的 c_stop，并将 finite termination、stability、near-optimality 放在一个统一 stopping-design 框架下。

看似新的地方如 c_stop=γ^iθσ(x) 并非完全新思想，LQ / Riccati 迭代里已有类似递减阈值；真正新增的是把这些选择纳入一般非线性确定性系统，并给出可验证条件下的稳定和性能定理。

Dataset / Evaluation

这篇是理论控制论文，evaluation 不是数据集驱动。数值例子使用 discrete cubic integrator，并在网格化状态 / 输入空间上比较几类 stopping criteria 的最终迭代数、稳定性保证和 near-optimality bound。

实验覆盖范围很窄，主要是 sanity check：它展示不同 c_stop 形状确实影响停止迭代和理论 guarantee，尤其 γ^iθσ(x) 在该例子中看起来计算代价没有明显增加但保证更强。

它不能验证大规模泛化、函数逼近、采样误差、真实系统部署或高维 scalability。benchmark 支持的是“理论设计有可见行为差异”，不是“该方法可直接用于实际 RL / ADP 大规模问题”。

文中未充分说明在连续状态空间中如何可靠检查 ∀x∈X 的 stopping criterion；数值上用网格近似，这对理论 claim 只是演示，不是实际可扩展 certificate。

Limitation

最核心限制是 exact VI。论文明确假设每轮 value function 精确计算、Bellman minimization 精确求解、stopping condition 可在整个 X 上验证。这在一般非线性连续系统中是强理想化，实际困难被转移到了精确求解和全域验证上。

第二个限制是条件强且偏控制理论：SA2/SA3/SA4、K∞ 上下界、radially unbounded σ、Assumption 1 等在 LQ 或结构良好的非线性系统中合理，但对一般 RL benchmark 或未知动力学问题并不自然。可测试不等于易测试。

第三，stability guarantee 对 X 的 forward invariance 很敏感。如果 stopping 只在有限兴趣集 X 上检查，闭环轨迹离开 X 后保证失效；论文给出一些 invariance 条件，但实际中这仍可能是主要瓶颈。

第四，near-optimality bounds 虽然显式，但可能保守，并且有些依赖沿闭环轨迹的 summability 或 V_*−V_0 条件。理论上干净，不代表数值上 tight。

第五，scalability 上限不在迭代次数，而在 certificate 的全局性。高维系统中验证 |V_{i+1}-V_i|≤c_stop for all x∈X 可能比继续迭代 VI 更难。

Takeaway

• 1. 最值得记住的是：stopping criterion 应该按 Lyapunov residual 设计，而不是按数值收敛习惯设计。
• 2. 常数 tolerance 与状态相关 tolerance 的差别是本质性的：前者天然只给 practical stability，后者才可能给真正渐近 / 指数稳定。
• 3. γ^i 型 stopping rule 的价值在于抵消 near-optimality bound 中的迭代折扣项，使性能界更可调；这是一条可迁移到 PI、MPC early termination、ADP residual design 的设计原则。
• 4. 未来真正有价值的方向不是再枚举更多 c_stop，而是把 approximation error、sampled verification 和 probabilistic certificates 纳入同一个 Lyapunov-residual 框架。

一句话总结

这篇论文把 VI 的 stopping rule 从经验性数值阈值提升为可设计的 Lyapunov / performance certificate，是 finite-computation dynamic programming 向可证明闭环控制保证演化的一步。