mlsanityData to 7 Oct 2026

Finite-Time Analysis of Natural Actor-Critic for POMDPs

arXiv 2202.09753 ↗First posted 20 Feb 2022cs.LG math.OC stat.MLcited by 12

Not on the map. Why?

Abstract (arXiv)

We consider the reinforcement learning problem for partially observed Markov decision processes (POMDPs) with large or even countably infinite state spaces, where the controller has access to only noisy observations of the underlying controlled Markov chain. We consider a natural actor-critic method that employs a finite internal memory for policy parameterization, and a multi-step temporal difference learning algorithm for policy evaluation. We establish, to the best of our knowledge, the first non-asymptotic global convergence of actor-critic methods for partially observed systems under function approximation. In particular, in addition to the function approximation and statistical errors that also arise in MDPs, we explicitly characterize the error due to the use of finite-state controllers. This additional error is stated in terms of the total variation distance between the traditional belief state in POMDPs and the posterior distribution of the hidden state when using a finite-state controller. Further, we show that this error can be made small in the case of sliding-block controllers by using larger block sizes.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 14 of its 50 references that are in the map. First posted on arXiv 20 Feb 2022.

Builds on

14 of 50 references.

References · 14

  1. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  2. 2019Stochastic Latent Actor-Critic: Deep Reinforcement Learning with a Latent Variable Modelcited by 228
  3. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  4. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  5. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 146
  6. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 113
  7. 2020Approximate information state for approximate planning and reinforcement learning in partially observed systemscited by 67
  8. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  9. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  10. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  11. 2018Actor-Critic Policy Optimization in Partially Observable Multiagent Environmentscited by 35
  12. 2021Convergence of Finite Memory Q-Learning for POMDPs and Near Optimality of Learned Policies under Filter Stabilitycited by 20
2 more
  1. 2018Regret Bounds for Reinforcement Learning via Markov Chain Concentrationcited by 19
  2. 2017Learning to Represent Haptic Feedback for Partially-Observable Taskscited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 4; 2026: 7.

12 papers.

  1. 2025Partially Observable Reinforcement Learning with Memory Tracescited by 9
  2. 2024Recurrent Natural Policy Gradient for POMDPscited by 8
  3. 2025A Theoretical Justification for Asymmetric Actor-Critic Algorithmscited by 5
  4. 2025Scalable Policy-Based RL Algorithms for POMDPscited by 4
  5. 2025Beyond expected value: geometric mean optimization for long-term policy performance in reinforcement learningcited by 2
  6. 2026Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPscited by 1
  7. 2026Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamicscited by 1
  8. 2026Why Linear Recurrent Memory Works in Partially Observable Reinforcement Learningcited by 1
  9. 2026Internal State-Based Policy Gradient Methods for Partially Observable Markov Potential Gamescited by 0
  10. 2026Is Backpropagation Optimal? When Synthetic Gradients Improve Sample Efficiencycited by 0
  11. 2026Reinformed Dreamer: An Asymmetric World Model Efficiently Trained through Latent Guidancecited by 0
  12. 2026Learning Suffers More Than the Policy Class Under Partial Observability: A Closed-Form Analysiscited by 0