提出基于时序差分评估的策略镜像下降法，证明其收敛性并改进采样复杂度。
On the Convergence of Policy Mirror Descent with Temporal Difference Evaluation
- 用时序差分替代精确价值评估，实现无需蒙特卡洛的策略优化
- 常数步长下保持1/T的次线性收敛，自适应步长可得γ速率线性收敛
- 适用于策略空间收敛，且在生成模型下样本复杂度更优
策略镜像下降（PMD）是强化学习中一类通用策略优化框架，通过指定不同的镜像映射可涵盖多种典型方法。现有分析要求仅基于策略的精确或近似价值评估（如蒙特卡洛无偏估计）。本文研究基于时序差分评估的策略镜像下降（TD-PMD）。在可获得精确策略评估的前提下，证明了无论初始值如何，只要使用常数步长，TD-PMD仍能实现维度无关的$O(1/T)$次线性收敛。为此，提出了新的单调性与平移不变性论证。若步长自适应选择，则可建立维度无关的γ速率线性收敛。对两种常见实例（即TD-PQA和TD-NPG），进一步证明其在策略空间中具有收敛性。此外，在不精确设置下，给出了在生成模型下达到最后迭代ε-最优所需的样本复杂度，改进了传统PMD对$1/(1-γ)$的依赖。
原文摘要 · Abstract (English)
Policy mirror descent (PMD) is a general policy optimization framework in reinforcement learning, which can cover a wide range of typical policy optimization methods by specifying different mirror maps. Existing analysis of PMD requires exact or approximate evaluation (for example unbiased estimation via Monte Carlo simulation) of action values solely based on policy. In this paper, we consider policy mirror descent with temporal difference evaluation (TD-PMD). It is shown that, given the access to exact policy evaluations, the dimension-free $O(1/T)$ sublinear convergence still holds for TD-PMD with any constant step size and any initialization. In order to achieve this result, new monotonicity and shift invariance arguments have been developed. The dimension free $γ$-rate linear convergence of TD-PMD is also established provided the step size is selected adaptively. For the two common instances of TD-PMD (i.e., TD-PQA and TD-NPG), it is further shown that they enjoy the convergence in the policy domain. Additionally, we investigate TD-PMD in the inexact setting and give the sample complexity for it to achieve the last iterate $\varepsilon$-optimality under a generative model, which improves the last iterate sample complexity for PMD over the dependence on $1/(1-γ)$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。