Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms
Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms
复制标题
DOI：
--
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Tengyu Xu;Yingbin Liang
中科院分区：
文献类型：
--
作者：
Tengyu Xu;Yingbin Liang
两个时间尺度的随机逼近（SA）已广泛应用于基于值的强化学习算法中。在策略评估设置中，它可以将梯度校正（TDC）算法的线性和非线性时间差异学习分别建模为线性SA和非线性SA。在策略优化设置中，两个时间尺度的非线性SA还可以对贪婪梯度Q（Greedy-GQ）算法进行建模。在之前的研究中，线性 TDC 和 Greedy-GQ 的非渐近分析已经在马尔可夫环境中进行了研究，步长递减或依赖于精度。对于非线性TDC算法，仅建立了渐近收敛性。在本文中，我们研究了马尔可夫采样和精度无关的常数步长下两个时间尺度线性和非线性TDC和Greedy-GQ的非渐近收敛速度。对于线性 TDC，我们提供了一种新颖的非渐近分析，并表明它在恒定步长下获得了 $\epsilon$ 精确的解，最佳样本复杂度为 $\mathcal{O}(\epsilon^{-1}\log(1/\epsilon))$。对于非线性 TDC 和 Greedy-GQ，我们表明这两种算法都获得了 $\epsilon$ 精确的稳态解，样本复杂度为 $\mathcal{O}(\epsilon^{-2})$。这是在马尔可夫采样下为非线性 TDC 建立的第一个非渐近收敛结果，并且我们的 Greedy-GQ 结果按顺序优于之前的结果 $\mathcal{O}(\epsilon^{-1}\log(1/\epsilon))$。
Two timescale stochastic approximation (SA) has been widely used in value-based reinforcement learning algorithms. In the policy evaluation setting, it can model the linear and nonlinear temporal difference learning with gradient correction (TDC) algorithms as linear SA and nonlinear SA, respectively. In the policy optimization setting, two timescale nonlinear SA can also model the greedy gradient-Q (Greedy-GQ) algorithm. In previous studies, the non-asymptotic analysis of linear TDC and Greedy-GQ has been studied in the Markovian setting, with diminishing or accuracy-dependent stepsize. For the nonlinear TDC algorithm, only the asymptotic convergence has been established. In this paper, we study the non-asymptotic convergence rate of two timescale linear and nonlinear TDC and Greedy-GQ under Markovian sampling and with accuracy-independent constant stepsize. For linear TDC, we provide a novel non-asymptotic analysis and show that it attains an $\epsilon$-accurate solution with the optimal sample complexity of $\mathcal{O}(\epsilon^{-1}\log(1/\epsilon))$ under a constant stepsize. For nonlinear TDC and Greedy-GQ, we show that both algorithms attain $\epsilon$-accurate stationary solution with sample complexity $\mathcal{O}(\epsilon^{-2})$. It is the first non-asymptotic convergence result established for nonlinear TDC under Markovian sampling and our result for Greedy-GQ outperforms the previous result orderwisely by a factor of $\mathcal{O}(\epsilon^{-1}\log(1/\epsilon))$.