用分布展开精确刻画 Q-learning 的瞬态误差
Understanding the Asymptotic Transience of Q-Learning via Distributional Expansion
如果你调过 Q-learning 会被初始阶段的大误差困扰，这篇把误差拆成 TD 和最大化两块，告诉你瞬态从哪来、为什么高斯近似够不着。做强化学习理论或想理解算法收敛细节的研究者会很受益。
一篇新论文针对有限折扣 MDP 中的同步 Q-learning，把 last-iterate 误差分解为最优策略的 TD 分量和最大化操作带来的非负位移两部分。中心化的 TD 分量在 n^{-1/2} 尺度上呈高斯波动，而最大化瞬态是 n^{-1} 阶，经 n 缩放后几乎必然收敛到一个随机极限，代表贪心策略稳定前最大化误差的传播效应。
作者结合 TD 分量的 Edgeworth 展开识别高斯近似的修正项，把初始化、非高斯 TD 波动和最大化三种效应分开。这解释了为什么中心极限定理的高斯极限抓不住瞬态误差——中心极限归一化抹掉了初始非线性演化产生的较小尺度位移；最坏情况有限样本保证虽覆盖瞬态，却看不出具体问题实例上的误差机制。
Understanding the Asymptotic Transience of Q-Learning via Distributional Expansion
Q-learning has been empirically observed to exhibit substantial transient error. This transient remains uncaptured by the leading Gaussian limit because the central-limit normalization removes the smaller-scale displacement generated by the initial nonlinear evolution. On the other hand, worst-case finite-sample guarantees, while accounting for transient effects, can obscure the mechanisms responsible for the error on a particular problem instance. We develop a finer asymptotic analysis that gives an asymptotically exact characterization of this transient for a fixed instance. Specifically, for synchronous Q-learning in finite discounted Markov decision processes, we separate the last-iterate error into an optimal-policy temporal-difference (TD) component and a nonnegative displacement caused by maximization. The centered TD component has Gaussian fluctuations at scale $n^{-1/2}$, whereas the maximization transient is of order $n^{-1}$ and converges almost surely, after rescaling by $n$, to a random limit. This limit represents the propagated effect of maximization errors generated before the greedy policy stabilizes. We combine this characterization with an Edgeworth expansion of the TD component to identify the corrections to its Gaussian approximation, separating the effects of initialization, non-Gaussian TD fluctuations, and maximization. The results reveal how transient errors arise for individual Q-learning instances and how their effects persist below the central-limit scale.
This report is categorized under AITOP's "Papers" desk. Key entities and technical topics under continuous tracking include Q-learning, 强化学习, 马尔可夫决策过程, Edgeworth展开.
Source attribution: curated from arXiv cs.LG (@Shengbo Wang).