最后迭代TD学习仅需O(H³/ε²)次转移，单轨迹高概率逼近最优解！
Sharp Statistical Rates for Asynchronous TD Learning with Markovian Data
📖 AI 总结
本文研究标准表格型时序差分（TD）学习在有限马尔可夫奖励过程单条轨迹下的最后迭代收敛问题。作者证明，在折扣因子γ、有效时域H=(1-γ)⁻¹、最小平稳概率μ_min和全变差混合时间t_mix下，最后迭代TD以高概率达到ε的无穷范数误差，所需转移次数为Õ(H³/(μ_min ε²)+t_mix/μ_min)，该速率对为目标精度选定的常数步长和与目标精度无关的递减步长均成立，后者还给出超过显式暂态阈值后所有时刻的同时保证。统计项保留了同步TD的三次有效时域依赖，加性混合暂态不含额外时域因子。结果允许非可逆链、任意初始状态分布及依赖下一状态的有界奖励。证明采用反向时间锚定局部泊松方程控制随机波动，并用命中时间补偿恒等式约束初始化误差。三状态构造给出统计项与混合项的匹配极小极大下界。
🔑 关键词速览
| 时序差分学习 (TD Learning) | 一种基于自举法的强化学习价值函数估计方法，利用后续状态的估计值更新当前状态的价值。 |
| 马尔可夫奖励过程 (Markov Reward Process) | 由状态空间、转移概率、奖励函数和折扣因子组成的随机过程，是马尔可夫决策过程的无动作版本。 |
| 混合时间 (Mixing Time) | 马尔可夫链从任意初始分布收敛到平稳分布所需的时间，通常用全变差距离度量。 |
| 最后迭代 (Last Iterate) | 指算法运行结束后最终输出的参数估计值，而非迭代平均或遍历平均。 |
| 极小极大下界 (Minimax Lower Bound) | 在给定模型类中，任何算法所能达到的最优误差下界，用于衡量算法的统计最优性。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅