线性函数逼近下的Q学习有了收敛条件:折扣越重,学习策略的信息只能外推到越近的贪心策略
核心概要
在状态空间无限、Q函数无法逐项存储的马尔可夫决策问题里,线性函数逼近的Q学习此前缺乏收敛保证。分析给出一个充分条件:学习策略诱导的马尔可夫链一致遍历、特征有界且线性无关,并且贪心动作特征二阶矩被学习策略动作的二阶矩按折扣因子留出余量,此时参数估计以概率1收敛到投影后的不动点。折扣越接近1,学习策略的信息只能安全外推到越近的贪心策略。
深度剖析
线性函数逼近的Q学习在固定学习策略下可以以概率1收敛,极限点满足一个带正交投影的类贝尔曼递归关系。 此前值函数型强化学习与函数逼近结合时通常表现很差,Q学习加函数逼近的收敛性长期是未解问题;已有的收敛分析针对TD学习,并未覆盖随机控制中的Q学习。 收敛结论依赖一个显式条件:对每个折扣因子,贪心动作特征的二阶矩要被学习策略所选动作的二阶矩按一定余量支配,同时步长序列满足随机逼近的常规要求。
算法用时间差分作为误差、沿特征的梯度方向更新参数向量,从而在无限状态空间中以有限维参数表示Q函数。 原始Q学习要求把每个状态-动作对的Q值显式存成矩阵,状态或动作无限时无法这样做,因此需要线性函数逼近这类紧凑表示。 收敛性通过常微分方程论证建立:算法轨迹被证明紧跟一个关联常微分方程,该方程在给定条件下收缩并具有全局渐近稳定的唯一平衡点。
同策略的SARSA加线性函数逼近在探索策略随参数平滑变化时同样以概率1收敛。 前述Q学习结果要求学习策略与贪心策略足够接近,这在实际中很少满足,因此转向对策略本身随估计变化的同策略算法做分析。 结论要求学习策略对参数满足利普希茨连续性、对应马尔可夫链一致遍历,且利普希茨常数足够小;这与已有SARSA收敛结果一致,但这里处理的是持续任务而非分幕任务。
启示与展望
结论针对状态空间紧致、动作集有限、Q函数用固定基函数线性张成的马尔可夫决策问题,并要求固定学习策略诱导的链一致遍历、特征有界且线性无关。SARSA部分进一步要求学习策略对参数利普希茨连续且常数足够小,分析在持续任务设定下进行。
所有条件都只是充分的,条件不满足时仍可能收敛。Q学习的收敛条件被明确指出相当严格:若各动作特征范数相同,该条件只能在折扣因子为0时成立,一般情况下很少满足。SARSA的收敛保证依赖探索策略保持平滑,而把探索衰减到零会使平滑性条件难以满足,并使分析所用的策略下界失效。误差界未在本文中推导,作者只是预期已有TD误差界可小幅修改后沿用。
