mlsanityData to 14 Oct 2026

Recurrent Natural Policy Gradient for POMDPs

arXiv 2405.18221 ↗First posted 28 May 2024math.OC cs.LG stat.MLcited by 8

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Solving partially observable Markov decision processes (POMDPs) remains a fundamental challenge in reinforcement learning (RL), primarily due to the curse of dimensionality induced by the non-stationarity of optimal policies. In this work, we study a natural actor-critic (NAC) algorithm that integrates recurrent neural network (RNN) architectures into a natural policy gradient (NPG) method and a temporal difference (TD) learning method. This framework leverages the representational capacity of RNNs to address non-stationarity in RL to solve POMDPs while retaining the statistical and computational efficiency of natural gradient methods in RL. We provide non-asymptotic theoretical guarantees for this method, including bounds on sample and iteration complexity to achieve global optimality up to function approximation. Additionally, we characterize pathological cases that stem from long-term dependencies, thereby explaining limitations of RNN-based policy optimization for POMDPs.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 37 of its 65 references that are in the map. First posted on arXiv 28 May 2024.

Builds on

37 of 65 references.

References · 37

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2014Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modelingcited by 2,367
  3. 2018On Lazy Training in Differentiable Programmingcited by 675
  4. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  5. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  6. 2014Recurrent Models of Visual Attentioncited by 349
  7. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 306
  8. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  9. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  10. 2013Maxout Networkscited by 187
  11. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 177
  12. 2018Understanding the impact of entropy on policy optimizationcited by 176
25 more
  1. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  2. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  3. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  4. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 150
  5. 2018Independently Recurrent Neural Network (IndRNN): Building A Longer and Deeper RNNcited by 143
  6. 2021Recurrent Model-Free RL Can Be a Strong Baseline for Many POMDPscited by 122
  7. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 121
  8. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  9. 2018Echo state networks are universalcited by 87
  10. 2019Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networkscited by 79
  11. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 68
  12. 2023POPGym: Benchmarking Partially Observable Reinforcement Learningcited by 62
  13. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  14. 2019Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policycited by 43
  15. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  16. 2019Neural tangent kernels, transportation mappings, and universal approximationcited by 30
  17. 2021Convergence of Finite Memory Q-Learning for POMDPs and Near Optimality of Learned Policies under Filter Stabilitycited by 22
  18. 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 20
  19. 2021Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximationcited by 16
  20. 2019Deep Independently Recurrent Neural Network (IndRNN)cited by 14
  21. 2022Finite-Time Analysis of Natural Actor-Critic for POMDPscited by 13
  22. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  23. 2021Sample Complexity and Overparameterization Bounds for Temporal Difference Learning with Neural Network Approximationcited by 10
  24. 2024Rethinking Transformers in Solving POMDPscited by 9
  25. 2024Convergence of Gradient Descent for Recurrent Neural Networks: A Nonasymptotic Analysiscited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 5.

8 papers.

  1. 2025A Theoretical Justification for Asymmetric Actor-Critic Algorithmscited by 6
  2. 2025Scalable Policy-Based RL Algorithms for POMDPscited by 4
  3. 2025Informed Asymmetric Actor-Critic: Leveraging Privileged Signals Beyond Full-State Accesscited by 2
  4. 2026Finite-Time Analysis of Gradient Descent for Shallow Transformerscited by 1
  5. 2026Internal State-Based Policy Gradient Methods for Partially Observable Markov Potential Gamescited by 0
  6. 2026Randomized Advantage Transformation (RAT): Computing Natural Policy Gradients via Direct Backpropagationcited by 0
  7. 2026Reinformed Dreamer: An Asymmetric World Model Efficiently Trained through Latent Guidancecited by 0
  8. 2026ALER: Adaptive Learnable Experience Rewriting for Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Natural Policy Gradient for Average Reward Non-Stationary RL
  2. 2024Efficient Recurrent Off-Policy RL Requires a Context-Encoder-Specific Learning Rate
  3. 2026Policy Gradient Methods for Non-Markovian Reinforcement Learning
  4. 2024Convergence of Natural Policy Gradient for a Family of Infinite-State Queueing MDPs
  5. 2026Does Learning Recurrent Networks Matter in Partially Observable RL?
  6. 2024Linear Function Approximation as a Computationally Efficient Method to Solve Classical Reinforcement Learning Challenges
  7. 2026Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes
  8. 2025Bi-directional Recurrence Improves Transformer in Partially Observable Markov Decision Processes