精读笔记

Problem Setting

论文标题：Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process（arXiv preprint / 2026）。

这篇论文实际处理的是一个此前理论上很尴尬的 setting：average-reward MDP、weakly communicating、没有 generative model、没有 i.i.d. offline dataset、只有一条由固定正行为策略产生的 trajectory，并希望输出全状态空间上的 ε-optimal policy。

真正困难点在于，weakly communicating MDP 允许 transient states。单轨迹从 transient region 出发时，早期样本既不代表长期 average-reward 结构，也不一定会重复出现；但 average-reward optimality 最终由 recurrent behavior 决定。另一方面，一旦进入 recurrent class，样本仍然高度相关，不能直接套 generative-model 或 i.i.d. concentration。以前的分析通常通过 ergodicity / mixing、generative access、finite coverage offline data 或行为策略 ergodic 假设绕过这些问题。

关键矛盾是：average-reward control 的目标由稳态结构决定，但 learner 看到的是一条非稳态、相关、可能先经过 transient states 的路径。论文的工作就是证明在 weakly communicating MDP 中，这条路径仍然足够：只要利用 recurrent-transient 分类和 stopping time，就能恢复足够强的 sample oracle。

Motivation

已有路线不够的原因不是 average-reward Bellman theory 缺失，而是 sampling model 太强。Generative model 直接给每个 state-action 独立采样；offline i.i.d. data 假设覆盖已经存在；ergodic / mixing assumption 保证长轨迹统计好处理。但 weakly communicating MDP 中，transient states 和 multichain-like boundary behavior 会让这些分析失效。

作者的核心观察是：对正策略 π∈Π+，弱连通 MDP 的 recurrent-transient decomposition 具有策略不变性：存在唯一 recurrent class R 和 transient set T，且 T 对所有策略仍 transient。这一点把问题从“任意单轨迹依赖样本”改写为“先等 trajectory 进入稳定 recurrent support，然后只在 R 上学习”。

真正缺口是：如何从一条 trajectory 构造足够接近 per-state-action oracle 的采样机制，而不假设 mixing time oracle 或 generative access。论文的回答是 stopping time + strong Markov property：每次回到某个 state-action 后的 next state，可以作为条件独立的重复样本来使用。

Core Idea

论文的核心思想不是发明新的 average-reward optimizer，而是改变单轨迹数据的使用方式：先通过 hitting / covering argument 把 trajectory 切到 recurrent class，再用 return-time stopping rules 把同一条轨迹拆成 state-action 层面的重复 transition samples。这样原本强相关的时间序列，被重新组织成足以支持 Hoeffding/Azuma 型 concentration 的采样对象。

这和 prior 的本质区别在于，它没有要求外部 oracle 提供 i.i.d. samples，也没有用全局 mixing assumption 平滑依赖性；它利用的是 weakly communicating MDP 的 latent graph structure。inductive bias 很明确：长期控制问题只需要 recurrent class 上的 Bellman residual / policy gradient 信息；transient 部分只需要通过小扰动策略保证从任意初始状态最终到达 learned recurrent behavior。

因此该方法更像是“structural reduction + sample re-indexing”，而不是 scaling。可迁移的 insight 是：在非 i.i.d. RL 数据中，如果能找到稳定 recurrent support，并用 stopping-time 切片，则很多 generative-model 证明可以被移植到 single-trajectory setting。

Method

关键机制可以压缩为四个。

第一，recurrent class identification。RECUR 先运行一段时间逃离 transient states，再继续收集访问到的 states 作为 R 的估计。它解决的是弱连通 MDP 中 transient samples 不可复用的问题。必要性在于，如果直接在全 S 上做 Bellman learning，transient states 的 coverage 和 recurrent states 的稳态 coverage 混在一起，PAC 分析会非常困难。

第二，stopping-time sampling。SAMPLE 对每个 recurrent state-action 收集 m 次访问后的 next-state function value。它解决的是单轨迹依赖性。核心变化是把时间序列索引改为 hitting-time 索引，使 strong Markov property 给出条件独立性，从而获得类似 generative model 的估计误差控制。

第三，anchored value iteration + variance reduction。SAVIC 用 Halpern / anchored update 控制 average-reward Bellman operator 非收缩带来的 finite-time 问题；同时只估计 successive Bellman differences P(h_k-h_{k-1})，避免每一轮从零估计 TQ_k。这里 anchoring 是 average-reward setting 下 residual 收敛的关键，variance reduction 是 ε^{-2} 复杂度的关键。

第四，policy completion / perturbation。因为学习主要发生在 R 上，输出策略需要在全 S 上定义，并且要保持正性。Lemma 3.1 表明，如果 recurrent class 上 Bellman residual 小，且 greedy policy 被轻微扰动为正策略，则全状态空间 average reward 仍接近最优。这一步把 recurrent-only learning 转化为 whole-MDP guarantee。

SAVIC+ 的核心是 communicating MDP 中 R=S，因此不需要 transient discovery 和 policy perturbation；再用 SAMPLE+ 自动收集足够样本，并以 empirical Bellman residual 停止，从而摆脱若干问题常数先验。SCPMA 则是在同一采样基础上做 policy evaluation，再接 α-clipped PMA；其技术新意主要在 single-trajectory policy evaluation，而非 mirror ascent 本身。

Key Insight / Why It Works

最核心的有效性来自两个事实的组合。

第一，弱连通 MDP 在正策略下有稳定的 recurrent-transient decomposition。只要行为策略 π_b 对所有动作给正概率，trajectory 最终进入唯一 recurrent class，并且不会离开。于是 average-reward learning 可以聚焦在 R 上；transient states 只影响 hitting-time overhead，而不改变最终 Bellman / policy-gradient 结构。

第二，return-time samples 可以替代 generative samples。对固定 state-action，定义 successive hitting times τ_i，则 s_{τ_i+1} 在 strong Markov property 下可作为重复 transition draws 使用。论文的 Lemma 2.3 本质上是把单轨迹 concentration 转成 stopping-time concentration，并用 k-cover time 保证每个 state-action 都拿到足够样本。这是全文最实质的技术贡献。

SAVIC 的 ε^{-2} 主要不是来自“更聪明的 control”，而是来自把 [38] 一类 anchored variance-reduced VI 分析嫁接到 single trajectory oracle 上。Anchoring 负责非收缩 fixed-point 的 finite-time residual；variance reduction 负责不把每轮估计误差线性累积；stopping-time 采样负责让这些估计在单轨迹下合法。三者缺一不可，但最新增的是第三者。

SCPMA 的贡献相对弱一些：α-clipped PMA 的优化骨架来自已有工作，论文主要补上 single-trajectory policy evaluation。复杂度中 Cα、Qα、tα 等常数非常重，说明 policy-based 部分更像理论 completeness：证明 policy-gradient family 也能在该 sampling model 下工作，而不是给出一个竞争性的 practical 方法。

这不是 scaling，不是 retrieval，也不是 representation alignment；它是 latent Markov structure exploitation。若硬要类比，它最像把 hidden recurrent support 当作可识别的 latent structure，再通过 memory reuse / trajectory slicing 复用同一条长轨迹。

Relation To Prior Work

最接近的谱系有三条。

第一是 average-reward VI / anchored VI / Halpern iteration。SAVIC 的 optimizer 部分明显继承 [38,39] 一类 anchored Q-value iteration：通过 anchor term 获得 span-seminorm residual 的非渐近收敛。这里看似新的 value iteration，其实主要是已有 anchored VI 在新 sampling model 下的重组。

第二是 variance-reduced value iteration。递归估计 T(Q_k)-T(Q_{k-1}) 的思想来自 generative-model 下的 variance reduction。本文的新增点是证明这些差分估计可以由一条 trajectory 经 stopping-time sampling 得到，而不是需要 oracle。

第三是 clipped policy mirror ascent / average-reward policy gradient。SCPMA 在优化结构上与 [39] 很近，实质差异是把 policy evaluation 换成 SAVIPE，使其适配 weakly communicating single trajectory。这里的创新不是 PMA，而是 policy evaluation 的单轨迹 concentration。

和 Li et al. 这类 ergodic single-trajectory 方法相比，本文放宽到了 weakly communicating，但代价是显式处理 hitting / covering / recurrent support。和 Tuynman et al. 的 communicating model-based fixed-confidence 方法相比，本文是 model-free 且提供 weakly communicating value-based guarantee，但 prior-free 只在 communicating case 做到。和 Lee et al. offline fitted Q-iteration 相比，本文不需要 finite coverage + behavior ergodicity 的额外 offline assumption，并显著改善 ε 依赖。

真正新增的信息是：weakly communicating average-reward MDP 的 single trajectory 不是不可分析的；只要行为策略正、状态动作有限，stopping-time oracle 足以承载 PAC learning。

Dataset / Evaluation

论文没有实验，属于纯理论 paper。没有真实世界环境、没有 benchmark、多任务泛化或 empirical scalability 验证。

从 claim 支撑角度，这没有问题，因为主要 claim 是 finite-sample guarantee。但也意味着论文没有验证：隐藏常数是否可接受、RECUR 在实际 sparse recurrent structure 中是否高效、SAVIC+ 的 stopping rule 是否保守、SCPMA 的 α-clipping 是否导致严重 bias、以及这些算法相较 model-based 方法在 wall-clock / trajectory length 上是否有实际优势。

因此 evaluation 只支持理论可行性，不支持 practical competitiveness。若读者关心真实 deployment，这篇论文没有给证据。文中未充分说明这些 bound 在典型 benchmark MDP 上的数量级是否可用。

Limitation

最大限制是所有漂亮的 ε 依赖都被问题常数包住了。thit、tcov、dmin、tα、Cα、Qα、span(Q*) 在弱连通或近退化 MDP 中可能极大；单轨迹 learning 的瓶颈被从 ε-dependence 转移到了 coverage / recurrence constants。严格说，这不是解决了 exploration 难题，而是在给定正行为策略覆盖的情况下证明了统计复用可行。

正行为策略 π_b∈Π+ 是强前提。它保证所有动作最终有机会被访问，但如果某些动作概率极小，dmin 会把复杂度打爆。换句话说，方法没有学习如何探索，只是要求行为策略已经以非零概率探索了所有动作。

Weakly communicating 下 SAVIC 仍需要 thit、tcov、dmin、∥Q*∥sp 等先验来设参数；prior-free 的 SAVIC+ 只对 communicating MDP 成立。这个差异很关键，不能把 SAVIC+ 的无先验性质泛化到 weakly communicating case。

SCPMA 的理论上限更明显：α 要随 ε 变小以逼近最优策略，但 Cα、Qα、tα 可能随 α 恶化。文中给出的 ε^{-4} 是在隐藏这些依赖时才好看；如果展开 α-dependence，实际复杂度可能很差。这里的 policy-gradient result 更像存在性证明。

此外，所有结果都是 tabular finite MDP。扩展到 function approximation 时，stopping-time i.i.d. 化并不能自动解决 representation error、off-policy distribution shift、稀疏 coverage 或 bootstrapping stability。所谓 model-free 也不等于 scalable；它只是没有显式估计 P。

Takeaway

• 1. 这篇真正推动的是 sampling model：把 average-reward weakly communicating MDP 的 PAC learning 从 generative / i.i.d. setting 推到 single trajectory setting。
• 2. 最值得迁移的 insight 是 stopping-time re-indexing：在 Markov 数据中，与其强行 mixing，不如利用 recurrent structure 构造条件独立样本。
• 3. Anchored VI + variance reduction 是当前 average-reward finite-sample theory 的强基线；本文说明它可以和单轨迹采样机制兼容。
• 4. 后续真正值得做的不是再堆一个 policy-gradient 变体，而是降低或自适应覆盖常数、处理行为策略探索、以及把 recurrent-support/stopping-time 技术扩展到 function approximation。

一句话总结

这篇论文在 average-reward RL 理论中把 weakly communicating MDP 的单轨迹学习从“缺少 finite-sample PAC 保证”推进到“可通过 recurrent-structure reduction 与 stopping-time sampling 接上 anchored / policy optimization 方法”的阶段，核心贡献是采样分析而不是新的优化算法。