提出两种新算法，实现在线马尔可夫数据下的高效策略优化。
Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Data
- 结合时序差分学习与镜面下降，设计两类离策略优化算法。
- 在小步长下达到 $ ilde{O}(\varepsilon^{-2})$ 的样本复杂度。
- 自适应步长使最后迭代结果达 $O(\varepsilon^{-2})$，适合高精度强化学习场景。
本文研究策略镜面下降（PMD）方法在强化学习中的样本复杂度，针对在线马尔可夫采样模型，提出两种算法：期望时序差分-PMD（Expected TD-PMD）和近似时序差分-PMD（Approximate TD-PMD），分别为离策略与混合策略算法。在足够小的固定策略更新步长下，二者均可实现平均时间 $\ ilde{O}(\varepsilon^{-2})$ 的样本复杂度以达成 $\ar{\varepsilon}$-最优性（$\ar{\varepsilon}$ 为平均时间误差）。通过采用自适应策略更新步长，样本复杂度进一步提升至 $O(\varepsilon^{-2})$，实现最后迭代点的 $\ar{\varepsilon}$-最优性，显著优于现有结果。
原文摘要 · Abstract (English)
This paper studies the policy mirror descent (PMD) method, which is a general policy optimization framework in reinforcement learning and can cover a wide range of policy gradient methods by specifying difference mirror maps. Existing sample complexity analysis for policy mirror descent either focuses on the generative sampling model, or the Markovian sampling model but with the action values being explicitly approximated to certain pre-specified accuracy. In contrast, we consider the sample complexity of policy mirror descent with temporal difference (TD) learning under the Markovian sampling model. Two algorithms called Expected TD-PMD and Approximate TD-PMD have been presented, which are off-policy and mixed policy algorithms respectively. Under a small enough constant policy update step size, the $\tilde{O}(\varepsilon^{-2})$ (a logarithm factor about $\varepsilon$ is hidden in $\tilde{O}(\cdot)$) sample complexity can be established for them to achieve average-time $\varepsilon$-optimality. The sample complexity is further improved to $O(\varepsilon^{-2})$ (without the hidden logarithm factor) to achieve the last-iterate $\varepsilon$-optimality based on adaptive policy update step sizes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。