统一TD、FQI等离策略算法的数学本质,揭示收敛关键机制。
A Unifying View of Linear Function Approximation in Off-Policy RL Through Matrix Splitting and Preconditioning
- 用矩阵分解与预条件化统一分析多种值函数逼近方法。
- 发现增加更新次数相当于从固定预条件转为数据自适应预条件。
- 首次证明大学习率失效时小学习率可能有效,适用于算法设计者。
在离策略策略评估任务中,传统观点认为时间差分学习(TD)仅进行一次更新,拟合Q迭代(FQI)进行无限次更新,部分拟合Q迭代(PFQI)则执行有限次。本文通过线性值函数近似提出新视角:这些方法实为求解同一线性系统的迭代过程,仅采用不同的矩阵分裂方式与预条件器。我们证明,在相同目标值函数下增加更新次数,等价于从常数预条件转向数据-特征自适应预条件。这首次阐明为何TD收敛不保证FQI收敛,并建立三者间紧密的收敛关联。本框架获得比以往更紧的理论结果,刻画各算法收敛条件,且无需依赖特征线性独立等假设。我们还提出编码-解码视角理解TD收敛性,并首次证明当大学习率无效时,减小学习率可能改善性能。框架还揭示了影响收敛的新特征条件,表明在线策略设置下,即使放弃特征线性独立假设,随机TD仍可保持收敛性。本工作首次将矩阵分裂引入此类算法的收敛分析。
原文摘要 · Abstract (English)
In off-policy policy evaluation (OPE) tasks within reinforcement learning, Temporal Difference Learning(TD) and Fitted Q-Iteration (FQI) have traditionally been viewed as differing in the number of updates toward the target value function: TD makes one update, FQI makes an infinite number, and Partial Fitted Q-Iteration (PFQI) performs a finite number. We show that this view is not accurate, and provide a new mathematical perspective under linear value function approximation that unifies these methods as a single iterative method solving the same linear system, but using different matrix splitting schemes and preconditioners. We show that increasing the number of updates under the same target value function, i.e., the target network technique, is a transition from using a constant preconditioner to using a data-feature adaptive preconditioner. This elucidates, for the first time, why TD convergence does not necessarily imply FQI convergence, and establishes tight convergence connections among TD, PFQI, and FQI. Our framework enables sharper theoretical results than previous work and characterization of the convergence conditions for each algorithm, without relying on assumptions about the features (e.g., linear independence). We also provide an encoder-decoder perspective to better understand the convergence conditions of TD, and prove, for the first time, that when a large learning rate doesn't work, trying a smaller one may help. Our framework also leads to the discovery of new crucial conditions on features for convergence, and shows how common assumptions about features influence convergence, e.g., the assumption of linearly independent features can be dropped without compromising the convergence guarantees of stochastic TD in the on-policy setting. This paper is also the first to introduce matrix splitting into the convergence analysis of these algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。