Finite-sample analysis of nonlinear stochastic approximation with applications in reinforcement learning-猫眼课题宝

DOI：

10.1016/j.automatica.2022.110623

发表时间：

2019-05

期刊：

Autom.

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Zaiwei Chen;Sheng Zhang;Thinh T. Doan;J. Clarke;S. T. Maguluri

基于在强化学习（RL）中的应用，研究了一种马尔可夫噪声下的非线性随机逼近（SA）算法，并建立了该算法在不同步长下的有限样本收敛界。具体地说，我们证明了当使用恒定步长（即α k≡α）时，算法在期望的极限点附近实现指数级快速收敛到一个邻域（半径为O (α log (1/α))）。当采用适当衰减率的递减步长时，算法收敛速度为O （log (k)/k）。我们的证明是基于李雅普诺夫漂移参数的，为了处理马尔可夫噪声，我们利用了底层马尔可夫链的快速混合。为了证明我们关于markov SA的理论结果的普遍性，我们利用它推导了流行的线性函数近似q -学习算法在行为策略条件下的有限样本界。重要的是，我们不需要假设样本是id的，也不需要在算法中进行人工投影步骤。数值模拟证实了我们的理论结果。

Motivated by applications in reinforcement learning (RL), we study a nonlinear stochastic approximation (SA) algorithm under Markovian noise, and establish its finite-sample convergence bounds under various stepsizes. Specifically, we show that when using constant stepsize (ie, α k≡ α), the algorithm achieves exponential fast convergence to a neighborhood (with radius O (α log (1/α))) around the desired limit point. When using diminishing stepsizes with appropriate decay rate, the algorithm converges with rate O (log (k)/k). Our proof is based on Lyapunov drift arguments, and to handle the Markovian noise, we exploit the fast mixing of the underlying Markov chain. To demonstrate the generality of our theoretical results on Markovian SA, we use it to derive the finite-sample bounds of the popular Q-learning algorithm with linear function approximation, under a condition on the behavior policy. Importantly, we do not need to make the assumption that the samples are iid, and do not require an artificial projection step in the algorithm. Numerical simulations corroborate our theoretical results.

Finite-sample analysis of nonlinear stochastic approximation with applications in reinforcement learning

文献摘要

相似文献