Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity
Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity
复制标题
DOI：
--
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Shaocong Ma;Ziyi Chen;Yi Zhou;Shaofeng Zou
中科院分区：
文献类型：
--
作者：
Shaocong Ma;Ziyi Chen;Yi Zhou;Shaofeng Zou
Greedy-GQ是一种基于值的强化学习（RL）算法。最近，在线性函数逼近和马尔可夫采样下对Greedy-GQ进行了有限时间分析，该算法被证明可以实现$\epsilon$-稳定点，样本复杂度为$\mathcal{O}（\epsilon^{-3}）$。如此高的样本复杂度是由于马尔可夫样本引起的大方差。本文提出了一种用于非策略最优控制的方差减小的贪婪GQ算法。特别地，该算法应用基于SVRG的方差减小方案来减小两个时间尺度更新的随机方差。在线性函数逼近和马尔可夫采样下，研究了VR-Greedy-GQ的有限时间收敛性，并证明了该算法比原Greedy-GQ具有更小的偏差和方差误差.特别是，我们证明了VR-Greedy-GQ实现了改进的样本复杂度，其数量级为$\mathcal{O}（\math ^{-2}）$。我们进一步比较了VR-Greedy-GQ和Greedy-GQ在各种RL实验中的性能，以证实我们的理论研究结果。
Greedy-GQ is a value-based reinforcement learning (RL) algorithm for optimal control. Recently, the finite-time analysis of Greedy-GQ has been developed under linear function approximation and Markovian sampling, and the algorithm is shown to achieve an $\epsilon$-stationary point with a sample complexity in the order of $\mathcal{O}(\epsilon^{-3})$. Such a high sample complexity is due to the large variance induced by the Markovian samples. In this paper, we propose a variance-reduced Greedy-GQ (VR-Greedy-GQ) algorithm for off-policy optimal control. In particular, the algorithm applies the SVRG-based variance reduction scheme to reduce the stochastic variance of the two time-scale updates. We study the finite-time convergence of VR-Greedy-GQ under linear function approximation and Markovian sampling and show that the algorithm achieves a much smaller bias and variance error than the original Greedy-GQ. In particular, we prove that VR-Greedy-GQ achieves an improved sample complexity that is in the order of $\mathcal{O}(\epsilon^{-2})$. We further compare the performance of VR-Greedy-GQ with that of Greedy-GQ in various RL experiments to corroborate our theoretical findings.