Bather分解驱动的多链MDP平均奖励强化学习：三个算法实现几乎必然收敛并改善瞬态表现
核心概要
该工作针对平均奖励多链MDP提出三个异步值迭代强化学习算法：基础算法利用Bather唯一层次分解将状态空间划分为通信子系统与瞬态状态，用RVI Q学习估计各子系统增益、用Q学习求解聚合最优停止问题，几乎必然收敛到最优增益并在有限时间后产生增益最优策略；另两个算法分别近似求解平均最优方程以获得近增益最优策略、以及通过折扣近似最优偏差函数以获得近偏差最优策略，实验显示后两者在保持近增益最优的同时改善瞬态表现。
Figure 2 : Comparison of the Phase 1 greedy policies and Phase 2 policies of Algorithm 3 . Curves show the fraction of runs producing a bias-optimal policy across five random seeds. (a) Performance after 10 6 10^{6} iterations for different discount factors β \beta . (b) Performance during learning for β = 0.999 \beta=0.999 .
arXiv深度剖析
基础算法在仅知转移图（不知转移概率）的条件下，几乎必然收敛到最优增益向量，并在有限时间后产生增益最优策略。 此前多链平均奖励问题多通过折扣因子趋于1的归约求解，或仅处理单一通信类且依赖模型；该工作直接利用Bather唯一层次分解，将全局问题重构为各通信子系统内的平均奖励子问题与一个聚合最优停止问题，无需折扣归约。 作者给出定理3.1（增益估计收敛）与定理3.2（有限时间达到增益最优）的证明，证明依赖RVI Q学习在通信MDP中的收敛结果、聚合OSP中所有平稳策略的properness（引理7.2）以及停止奖励误差消失。
第二个算法通过扩展子MDP的平均最优方程解，近似求解完整多链平均最优方程，得到近增益最优策略，并给出以算法参数刻画的增益次优性上界。 基础算法只得到子MDP层面的部分相对值解，无法组合成完整平均最优方程解；该算法用双阈值机制使动作约束集与三类划分在有限时间内稳定，并对特定状态施加惩罚以保证无折扣总奖励Q学习的稳定性。 定理4.1给出Q学习迭代几乎必然收敛到扰动平均最优方程的唯一解，定理4.2给出诱导策略的增益次优性上界，并指出参数足够小时策略最终增益最优。
第三个算法通过折扣近似最优偏差函数并求解诱导的平均奖励多链MDP，得到近偏差最优策略，在保持近增益最优的同时改善瞬态表现。 偏差最优性比增益最优性更强，可在多个增益最优策略之间按瞬态奖励区分；该算法利用基础算法得到的精确最优增益对奖励做平移，使折扣值函数一致有界，避免直接折扣近似中值函数随折扣因子增大而发散。 定理5.2给出增益最优性条件与偏差最优性误差界，命题5.1给出增益最优状态上的逐状态偏差界，命题5.2给出偏差最优性的充要条件。
在100个随机生成的多链MDP上，基础算法增益最优状态覆盖率最高，算法2瞬态表现最好但增益最优性略降，算法3在两者之间取得折中，瞬态表现接近算法2与偏差最优基准。 实验直接比较三个算法与折扣Q学习基线，并以使用真实模型的折扣策略迭代算法作为偏差最优精确基准，同时报告逐MDP结果以验证聚合趋势。 实验为初步结果，作者声明更广泛的实证评估正在进行；采用轮询更新以保证可复现性，理论结果本身适用于一般异步探索方案。
启示与展望
该工作面向有限状态、有限动作的多链MDP，算法假设已知转移图（每个状态-动作对的可能后继状态集合），但不需要转移概率。作者指出该假设在仿真环境中具有实际意义，因为后继状态可从仿真器接口枚举，而转移概率可能难以计算或依赖未观测因素。分解仅依赖转移结构，因此作者认为它适合偏好演化或转移概率随时间变化但转移结构稳定的持续学习场景；结合量化近似方法后，也可用于连续时间随机控制问题经马尔可夫链近似得到的无限空间MDP，且不需要强遍历性条件。作者还指出，子策略与选项框架类似，为选项发现与复用提供了原则性基础。
性能保证是最终性的：算法在有限时间后几乎必然达到所述最优性，但不提供何时达到的认证，这与高概率策略识别结果不同。实验为初步结果，作者声明更广泛的实证评估正在进行，且未直接比较策略偏差，而是用进入常返类之前的期望累积奖励衡量瞬态表现。作者指出，逐MDP结果中算法2和算法3偶有增益次优性偏差，预期源于近似误差，未来工作将验证这些偶发大偏差的原因并研究算法对参数选择的敏感性。此外，转移图假设的移除、Bather分解的在线发现与维护、以及自适应参数调节均被列为未来方向。