Accelerated Policy Gradient: On the Convergence Rates of the Nesterov Momentum for Reinforcement Learning

• URL: http://arxiv.org/abs/2310.11897v3
• Date: Thu, 6 Jun 2024 10:06:24 GMT
• Title: Accelerated Policy Gradient: On the Convergence Rates of the Nesterov Momentum for Reinforcement Learning
• Authors: Yen-Ju Chen, Nai-Chieh Huang, Ching-Pei Lee, Ping-Chun Hsieh,
• Abstract summary: We adapt the celebrated Nesterov's accelerated gradient (NAG) method to policy optimization in Reinforcement Learning (RL) We prove that APG converges to an optimal policy at rates: (i) $tildeO (1/t2)$ with constant step sizes; (ii) $O(e-ct)$ with exponentially-growing step sizes.
• Score: 12.987019067098412
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Various acceleration approaches for Policy Gradient (PG) have been analyzed within the realm of Reinforcement Learning (RL). However, the theoretical understanding of the widely used momentum-based acceleration method on PG remains largely open. In response to this gap, we adapt the celebrated Nesterov's accelerated gradient (NAG) method to policy optimization in RL, termed \textit{Accelerated Policy Gradient} (APG). To demonstrate the potential of APG in achieving fast convergence, we formally prove that with the true gradient and under the softmax policy parametrization, APG converges to an optimal policy at rates: (i) $\tilde{O}(1/t^2)$ with constant step sizes; (ii) $O(e^{-ct})$ with exponentially-growing step sizes. To the best of our knowledge, this is the first characterization of the convergence rates of NAG in the context of RL. Notably, our analysis relies on one interesting finding: Regardless of the parameter initialization, APG ends up entering a locally nearly-concave regime, where APG can significantly benefit from the momentum, within finite iterations. Through numerical validation and experiments on the Atari 2600 benchmarks, we confirm that APG exhibits a $\tilde{O}(1/t^2)$ rate with constant step sizes and a linear convergence rate with exponentially-growing step sizes, significantly improving convergence over the standard PG.

Related papers

• The Role of Baselines in Policy Gradient Optimization [83.42050606055822]
  We show that the emphstate value baseline allows on-policy. emphnatural policy gradient (NPG) to converge to a globally optimal. policy at an $O (1/t) rate gradient. We find that the primary effect of the value baseline is to textbfreduce the aggressiveness of the updates rather than their variance.
  arXiv  Detail & Related papers  (2023-01-16T06:28:00Z)
• An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods [40.657905797628786]
  We revisit and improve the convergence of policy gradient (PG), natural PG (NPG) methods, and their variance-reduced variants. We show that a state-of-the-art variance-reduced PG method, which has only been shown to converge to stationary points, converges to the globally optimal value up to some inherent function approximation error. We have also made variance-reduction for NPG possible, with both global convergence and an efficient finite-sample complexity.
  arXiv  Detail & Related papers  (2022-11-15T06:47:06Z)
• On the Global Convergence of Momentum-based Policy Gradient [9.622367651590878]
  Policy gradient (PG) methods are popular and efficient for large-scale reinforcement learning. We study the global convergences of PG methods with momentum terms, which have been demonstrated to be efficient recipes for improving PG methods. Our work is the first one that obtains global convergence results for the momentum-based PG methods.
  arXiv  Detail & Related papers  (2021-10-19T17:16:29Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  Policy gradient (PG) is one of the most popular reinforcement learning (RL) problems. "vanilla" theoretical understanding of PG trajectory is one of the most popular methods for solving RL problems.
  arXiv  Detail & Related papers  (2021-07-23T19:38:17Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• Softmax Policy Gradient Methods Can Take Exponential Time to Converge [60.98700344526674]
  The softmax policy gradient (PG) method is arguably one of the de facto implementations of policy optimization in modern reinforcement learning. We demonstrate that softmax PG methods can take exponential time -- in terms of $mathcalS|$ and $frac11-gamma$ -- to converge.
  arXiv  Detail & Related papers  (2021-02-22T18:56:26Z)
• Proximal Policy Gradient: PPO with Policy Gradient [13.571988925615486]
  We propose a new algorithm PPG (Proximal Policy Gradient), which is close to both VPG (vanilla policy gradient) and PPO (proximal policy optimization) The performance of PPG is comparable to PPO, and the entropy decays slower than PPG.
  arXiv  Detail & Related papers  (2020-10-20T00:14:57Z)
• Momentum-Based Policy Gradient Methods [133.53164856723782]
  We propose a class of efficient momentum-based policy gradient methods for the model-free reinforcement learning. In particular, we present a non-adaptive version of IS-MBPG method, which also reaches the best known sample complexity of $O(epsilon-3)$ without any large batches.
  arXiv  Detail & Related papers  (2020-07-13T20:44:15Z)
• Zeroth-order Deterministic Policy Gradient [116.87117204825105]
  We introduce Zeroth-order Deterministic Policy Gradient (ZDPG) ZDPG approximates policy-reward gradients via two-point evaluations of the $Q$function. New finite sample complexity bounds for ZDPG improve upon existing results by up to two orders of magnitude.
  arXiv  Detail & Related papers  (2020-06-12T16:52:29Z)
• Stochastic Recursive Momentum for Policy Gradient Methods [28.277961340108313]
  We propose a novel algorithm named STOchastic Recursive Momentum for Policy Gradient (Storm-PG) Storm-PG enjoys a provably sharp $O (1/epsilon3)$ sample bound for STORM-PG, matching the best-known convergence rate for policy gradient algorithm. Numerical experiments depicts the superiority of our algorithm over comparative policy gradient algorithms.
  arXiv  Detail & Related papers  (2020-03-09T17:59:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.