Convergence and Iteration Complexity of Policy Gradient Method for Infinite-horizon Reinforcement Learning
Convergence and Iteration Complexity of Policy Gradient Method for Infinite-horizon Reinforcement Learning
复制标题
DOI：
10.1109/cdc40024.2019.9030265
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
K. Zhang;Alec Koppel;Hao Zhu;T. Başar
中科院分区：
文献类型：
--
作者：
K. Zhang;Alec Koppel;Hao Zhu;T. Başar
我们主要研究连续空间上强化学习问题中的策略搜索问题，其中的价值定义为无限水平的折扣报酬累积。这是Bellman提出的规范设置[3]。策略搜索，特别是策略梯度(PG)方法，可以很好地解决连续空间的问题，并允许深度网络参数化；然而，从实验上看，它是易失性的，其有限时间行为并不被很好地理解。这一差距的一个主要来源是无偏上升方向是难以捉摸的，因此只有渐近收敛到平稳性才能通过链接到常微分方程组来显示[4]。在这项工作中，我们提出了一种新的PG方法的变体，它使用一个随机的展开期来估计政策梯度，我们建立的这种估计产生了一个无偏的政策搜索方向。此外，我们从非凸优化的角度进行了全局收敛分析：(I)我们首先通过另一种上鞅方法恢复了文献中关于渐近收敛到平衡点政策的结果；(Ii)我们给出了无限水平环境下政策梯度的迭代复杂性，即收敛速度，证明了它在非凸且步长不变的情况下表现出与随机梯度方法相当的收敛速度。对倒立摆的数值实验验证了我们结果的有效性。
We focus on policy search in reinforcement learning problems over continuous spaces, where the value is defined by infinite-horizon discounted reward accumulation. This is the canonical setting proposed by Bellman [3]. Policy search, specifically, policy gradient (PG) method, scales gracefully to problems with continuous spaces and allows for deep network parametrizations; however, experimentally it is known to be volatile and its finite-time behavior is not well understood. A major source of this gap is that unbiased ascent directions are elusive, and hence only asymptotic convergence to stationarity can be shown via links to ordinary differential equations [4]. In this work, we propose a new variant of PG methods that uses a random rollout horizon for the Monte-Carlo estimation of the policy gradient, which we establish yields an unbiased policy search direction. Furthermore, we conduct global convergence analysis from a nonconvex optimization perspective: (i) we first recover the results of asymptotic convergence to the stationary-point policies in the literature through an alternative supermartingale argument; (ii) we provide iteration complexity, i.e., convergence rate, of policy gradient in the infinite-horizon setting, showing that it exhibits comparable rates to stochastic gradient method in the nonconvex regime for diminishing and constant stepsize rules. Numerical experiments on the inverted pendulum demonstrate the validity of our results.