精读笔记
Problem Setting
论文题目：A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averaging（arXiv preprint / 2026）。它实际处理的是 discounted finite MRP 下 linear TD(0) 的 finite-time high-probability 分析，数据来自单条 Markov trajectory，而不是 i.i.d. stationary samples。关键矛盾是：未投影 TD 的噪声大小随 ‖θ_t‖ 增长，但高概率 concentration 又需要先有 uniform bounded updates；如果用 curvature ω 来稳定轨迹，就失去 curvature-free robust rate；如果用 projection，则算法和先验半径都变了。以前方法卡在这里：projection 路线绕开了路径稳定性，contractive LSA 路线把 stability 常数绑到 ω 或 λ_min 上，导致“fast”和“robust”通常需要不同 stepsize 或额外算法修改。
Motivation
已有路线不够的地方不是 rate 形式本身，而是它们没有同时满足三个条件：plain unprojected TD(0)、high probability、stepsize independent of ω。作者的核心观察是，robust rate 所需的稳定性不应该依赖 strong convexity；TD mean update 已经有足够的 one-sided alignment，可用于防止系统性发散，剩下的问题只是 Markovian noise 的路径偏差如何控制。关键缺口是一个不使用 curvature 的 all-time pathwise stability argument。Poisson equation 被引入不是为了更漂亮地处理 mixing，而是为了把“条件均值非零”的 Markov bias 转成可浓缩的 martingale 加可控 remainder，从而关闭 boundedness 的自举循环。
Core Idea
真正核心思想是把 TD 的稳定性证明从 contraction-based unrolling 改写成 energy expansion + Markov-noise decomposition + self-bounding bootstrap。energy expansion 中 mean TD term 只提供非正漂移，不提供 ω 级别的收缩；所有可能导致爆炸的项都被归约为 η_t²‖g_t‖² 和 Markov bias。前者靠 square-summable stepsize 控制，后者靠 Poisson decomposition 控制。
这与 prior 的本质区别在于：prior 多数把线性递推 e_t=(I−ηA_z)e_{t−1}+noise 当作随机矩阵乘积来分析，并从 exponential stability 中获得 boundedness；本文反过来不要求矩阵乘积收缩，而是证明只要过去没爆，噪声项在同一半径尺度内就不会把下一步推出去。它引入的 inductive bias 是“路径稳定性来自噪声累计的可分解性和步长平方可和”，而不是“系统有足够 curvature 所以自动收缩”。
Method
1. Potential/energy identity：使用 f(θ)−f(θ*)=eᵀAe 作为 TD fixed-point error 的势函数，关键作用是把 mean update 与 θ*−θ 的 inner product 精确对应起来。它解决的是 TD 非梯度、A 非对称时如何获得 descent-like 结构；核心变化是只需要 one-sided monotonicity，而不必在 boundedness 证明中动用 ω。
2. Poisson equation decomposition：对随 θ_t 冻结的 forcing term h_t(z) 解 u_t−P_Zu_t=h_t，把 Markov bias ∑η_t h_t(Z_t) 分成 martingale 和 telescoping remainder。它解决的是单轨迹 Markov noise 条件均值非零的问题；核心变化是把 temporal dependence 转化为 mixing-time 放大的 bounded martingale 问题。
3. Self-bounding localization：先停止在半径 R_max 内，证明在 stopped process 上 martingale/remainder/gradient-square 都是 O(R_max²)；然后选 c 和 ρ 让 bootstrap inequality 反推 sup_t‖θ_t‖≤R_max，进而 stopping time 永不触发。它解决的是 unprojected TD 的 circular boundedness 问题；核心变化是 projection 从算法中移到 proof localization 中，且最后被证明不触发。
4. PR averaging decomposition：对 e_t 递推重排得到 A ē_T=I1+I2+I3，其中 I1 是 telescoping，I2 是 additive noise，I3 是 multiplicative Markov noise。它解决的是如何在 η_t≈1/√t 这种不含 ω 的 stepsize 下仍得到 1/(ωT) fast rate；核心变化是 fast rate 来自 averaged linear equation residual，而不是单步 contraction。
Key Insight / Why It Works
最重要的 insight 是：robust boundedness 不需要 strong convexity，只需要 mean direction 不做坏事，加上 Markov noise 的累计偏差不会超过当前半径尺度。TD update 的坏处是 update magnitude ∝‖θ_t‖；但这恰好也允许 self-bounding：如果假设 ‖θ_t‖≤R，则所有 Poisson solution、martingale increments、remainder Lipschitz drift 都是 R 或 R² 量级，再通过 η_t² 可和把累计误差压成常数量级。这个闭环是论文真正的贡献。
PR averaging 的 fast rate 部分相对不新，更多是把已有 averaged stochastic approximation 思路接到新获得的 bounded-iterates event 上。它真正依赖 boundedness 事件来控制 I2/I3 的 Poisson martingale项；ω 只在最后用 ‖ē_T‖≤‖Aē_T‖/ω 把 residual 转成 function error。换句话说，fast rate 的新意不在 PR，而在“同一个 curvature-agnostic stepsize 仍能安全运行到可以做 PR analysis”。
这不是 scaling、retrieval、data coverage 或 representation alignment 类型的增益；它是 proof architecture 的改变。可能只是 auxiliary 的部分是大量显式常数和具体 log schedule；核心是 Poisson + stopped bootstrap。τ_mix² 的 fast-rate 代价很可能是分析 artifact，也可能是不用 data dropping/curvature 先验的真实代价；文中未充分说明哪一种更接近最优。
Relation To Prior Work
最接近的路线有三类。第一类是 Bhandari et al.、Liu-Olshevsky 等 projection-based finite-time TD：它们能得到 robust/fast 形式，但 boundedness 是外加的，半径通常隐含依赖 θ* 或 curvature。本文的不同点是 projection-free，而且 boundedness 是 theorem 而不是 assumption。
第二类是 Srikant-Ying、Patil、Samsonov、Durmus 等 LSA/exponential-stability 路线：它们通过随机矩阵乘积收缩或 Lyapunov stability 控制 iterates，适合 fast regime，但 stability 常数、stepsize 或 burn-in 与 curvature/λ_min 纠缠。本文的本质差异是完全不用 contraction 来证明 bounded iterates，因此能保留 curvature-free robust bound。
第三类是 Lee-Orabona 2025 的 expectation-level curvature-free unprojected TD boundedness：本文可以看作其高概率版本，但不是简单 Markov inequality 升级。高概率要求处理 pathwise Markov bias，Poisson toolkit 和 localized martingale bootstrap 是实质新增信息。
Poisson equation 本身不是新工具，PR averaging 也不是新工具；实质创新是把 Poisson decomposition 用在 self-bounding stability loop 中，并让它支撑 simultaneous robust/fast high-probability guarantee。
Dataset / Evaluation
这篇论文没有常规实验或 benchmark evaluation；evaluation 是数学保证。它验证的 claim 很窄但清晰：在 finite discounted ergodic MRP、full-rank linear features、bounded rewards/features、geometric mixing 的设定下，plain TD(0)+PR averaging 用同一 stepsize 可以同时得到 high-probability boundedness、robust rate 和 fast rate。
因此它不验证实际 deep RL、off-policy policy evaluation、large-scale function approximation 或未知 τ_mix 下的可用性。文中 Appendix E 给了不依赖 τ_mix 的 stepsize，但常数双指数依赖 τ_mix，更多是理论完备性而非实际算法建议。没有真实世界或多任务 evidence，也不存在 benchmark leakage 问题；核心 claim 的支撑来自 proof consistency 而不是 empirical superiority。
Limitation
1. 设定较强：finite state、discounted γ<1、ergodic aperiodic、full-column-rank Φ、bounded feature/reward。Remark 中提到 singular/γ=1 可扩展的可能性，但文中未充分说明完整条件和 rate 形式。
2. stepsize 依赖 τ_mix。主结果避免了 ω，但没有做到完全 parameter-free；τ_mix 在实践中通常也未知。Appendix E 的 mixing-free schedule 以双指数 τ_mix 常数为代价，实际价值很弱。
3. fast rate 的 τ_mix² 依赖弱于部分 prior 的 τ_mix 依赖。作者承认可能来自 Poisson analysis，也可能来自不用 data dropping/λ_min 的代价；目前增益来源和代价归因不清。
4. 初始误差项没有 exponential decay。因为作者刻意避免 contraction-based argument，初始误差只以 1/T 方式进入 averaged bound；这对短 horizon 或大 initialization error 可能不如 stability-based fast-rate work。
5. 常数很大，c_min 与 ρ 的形式非常保守。论文保留显式常数有理论透明度，但也暴露出该 proof 对实际 stepsize selection 的指导性有限。
6. 结果是 policy evaluation 的 linear TD，不说明 control、off-policy、bootstrapped nonlinear approximation 中类似 self-bounding 是否还能闭合。尤其 off-policy 下 A 的 one-sided positivity 和 noise structure 会明显不同。
Takeaway
- 1. 最值得迁移的不是具体 TD bound，而是“Poisson decomposition + stopped self-bounding bootstrap”这个证明模式：当 stochastic approximation 的噪声幅度依赖 iterate 且 projection 不自然时，可以尝试用路径分解而非 curvature contraction 来证明稳定。
- 2. 对 TD finite-time theory 来说，这篇把 curvature-free robust rate 和 curvature-aware fast rate 放进同一个 unprojected algorithm/stepsize 下，推进的是分析范式，而不是算法结构。
- 3. 未来真正值得做的是去掉 τ_mix 先验且不付双指数代价，并澄清 τ_mix² 是否必要；如果能做到 additive mixing cost，会比当前结果更接近实际 Markovian sampling 的统计极限。
- 4. 这篇提示一个更一般的问题：很多 SA/RL 算法的 projection 可能只是 proof artifact；但要移除它，需要能把 dependent noise 的累计效应控制在 self-bounding 半径内，而不是简单套用 concentration。
一句话总结
这篇论文在 unprojected linear TD(0) finite-time theory 中的定位是：用 Poisson-equation 驱动的 self-bounding pathwise stability 取代 curvature/projection 稳定性，从而让一个 ω-agnostic stepsize 同时支持 robust 和 fast PR-averaged high-probability rates。