Q-learning的暂态误差有了逐实例解释:最大化残差以n-1/4收敛到随机极限
核心概要
同步Q-learning的收敛分析通常只保留高斯极限,而中心极限归一化会把初始非线性演化产生的较小尺度位移抹掉。该分析把最后一次迭代误差拆成最优策略时序差分分量与最大化造成的非负位移,证明后者在n-1/4尺度上几乎必然收敛到一个随机极限,并用Edgeworth展开给出高斯近似的修正项。在一个两状态算例中,一阶修正密度比中心极限定理的高斯密度更接近经验分布。
深度剖析
同步Q-learning的误差里有一块此前被高斯极限掩盖的部分:最大化操作在策略尚未稳定前产生的残差,会沿后续更新持续传播,形成非负位移。 此前的主流刻画是中心极限定理给出的高斯极限,其归一化把初始非线性演化造成的较小尺度位移去掉了;而一致的最坏情况有限样本保证虽能覆盖暂态,却难以说明单个问题实例上的误差机制。 在有限折扣马尔可夫决策过程、每个状态有唯一最优动作、步长为重标度线性步长的设定下,该位移在n-1/4尺度上几乎必然且依Lp收敛到一个随机极限,该极限只由贪心策略稳定前有限次迭代产生的最大化残差及其传播决定。
把最大化位移与策略正确递推的高斯修正分开处理,需要两者在极限中互不干扰。 策略正确递推的中心化误差本身是n-1/2量级,而最大化暂态是n-1/4量级,二者尺度不同,但若相关就会改变一阶分布修正。 分析证明中心化误差与最大化暂态联合收敛到一对独立极限,其中高斯部分与随机极限独立;据此,最大化暂态在n-1/4阶只通过其均值进入分布展开,一阶修正由初始化偏差、非高斯时序差分涨落和最大化三部分构成。
最大化暂态虽在更小的n-1/4尺度上,却可能相当大,其幅度与最优动作间隙成反比。 这为最大化偏差会显著影响Q-learning性能的经验观察提供了一种渐近解释,说明在动作难以区分时初始阶段的最大化误差会累积。 在一个单状态、两动作、有界奖励的算例中,平均最大化暂态被证明有一个正比于最优性间隙倒数的下界;两状态算例的数值可视化中,经验直方图与中心极限定理高斯密度仍有可见偏差,而一阶修正密度更接近,且修正主要来自正的偏置项。
启示与展望
结论针对有限折扣马尔可夫决策过程上的同步Q-learning,要求每个状态有唯一最优动作,并使用重标度线性步长;数值示例是一个两状态算例,反比间隙下界来自一个单状态两动作算例。
最大化暂态在n-1/4尺度上的极限是随机的,其分布信息在一阶展开中只通过均值体现,更高阶贡献被留作后续。分析限于同步采样;向异步更新和一般非线性随机逼近的推广被列为需要更难证明与系数计算的方向。
