Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms
Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms
复制标题
DOI：
--
复制
发表时间：
2020-04
期刊：
影响因子：
--
通讯作者：
Tengyu Xu;Zhe Wang-;Yingbin Liang
中科院分区：
文献类型：
--
作者：
Tengyu Xu;Zhe Wang-;Yingbin Liang
ACTOR CRITIC（actor-critic）算法是一种在强化学习中寻找最优策略的流行方法。在无限水平的情况下，有限样本收敛速度的AC和自然演员批评（NAC）算法最近已经建立，但在独立同分布（i.i.d.）采样和单样本更新在每次迭代。相比之下，本文的特征的收敛速度和样本复杂性的AC和NAC下马尔可夫抽样，与小批量数据的每次迭代，并与演员具有一般的政策类近似。我们表明，一个小批量AC达到$\mathcal{O}精确平稳点的总体样本复杂度提高了AC的最佳已知样本复杂度。（\n ^{-1}\log（1/\n））$，小批量NAC达到$\N $-精确全局最优点的总体样本复杂度将现有NAC的样本复杂度提高了$\N的数量级mathcal{O}（\log ^{-2}/\log（1/\log））$.此外，AC和NAC的样本复杂度在这项工作中的特点是优于策略梯度（PG）和自然策略梯度（NPG）的一个因素，分别为$\mathcal{O}（（1-\gamma）^{-3}）$和$\mathcal{O}（（1-\gamma）^{-4}\log ^{-2}/\log（1/\gamma））$。这是第一个理论研究，建立AC和NAC实现有序性能改善PG和NPG无限地平线下，由于纳入批评。
The actor-critic (AC) algorithm is a popular method to find an optimal policy in reinforcement learning. In the infinite horizon scenario, the finite-sample convergence rate for the AC and natural actor-critic (NAC) algorithms has been established recently, but under independent and identically distributed (i.i.d.) sampling and single-sample update at each iteration. In contrast, this paper characterizes the convergence rate and sample complexity of AC and NAC under Markovian sampling, with mini-batch data for each iteration, and with actor having general policy class approximation. We show that the overall sample complexity for a mini-batch AC to attain an $\epsilon$-accurate stationary point improves the best known sample complexity of AC by an order of $\mathcal{O}(\epsilon^{-1}\log(1/\epsilon))$, and the overall sample complexity for a mini-batch NAC to attain an $\epsilon$-accurate globally optimal point improves the existing sample complexity of NAC by an order of $\mathcal{O}(\epsilon^{-2}/\log(1/\epsilon))$. Moreover, the sample complexity of AC and NAC characterized in this work outperforms that of policy gradient (PG) and natural policy gradient (NPG) by a factor of $\mathcal{O}((1-\gamma)^{-3})$ and $\mathcal{O}((1-\gamma)^{-4}\epsilon^{-2}/\log(1/\epsilon))$, respectively. This is the first theoretical study establishing that AC and NAC attain orderwise performance improvement over PG and NPG under infinite horizon due to the incorporation of critic.