# Finite-Time Analysis of Natural Actor-Critic for POMDPs

arXiv: https://arxiv.org/abs/2202.09753 · HTML: https://mlsanity.com/paper/2202.09753/

## Key facts

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

## Builds on (most cited first, 14 of 14)

- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Stochastic Latent Actor-Critic: Deep Reinforcement Learning with a Latent Variable Model](https://mlsanity.com/paper/1907.00953/) (2019)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019)
- [Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs](https://mlsanity.com/paper/1909.02769/) (2019)
- [Approximate information state for approximate planning and reinforcement learning in partially observed systems](https://mlsanity.com/paper/2010.08843/) (2020)
- [Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games](https://mlsanity.com/paper/2102.04540/) (2021)
- [Provable Reinforcement Learning with a Short-Term Memory](https://mlsanity.com/paper/2202.03983/) (2022)
- [Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2101.10506/) (2021)
- [Actor-Critic Policy Optimization in Partially Observable Multiagent Environments](https://mlsanity.com/paper/1810.09026/) (2018)
- [Convergence of Finite Memory Q-Learning for POMDPs and Near Optimality of Learned Policies under Filter Stability](https://mlsanity.com/paper/2103.12158/) (2021)
- [Regret Bounds for Reinforcement Learning via Markov Chain Concentration](https://mlsanity.com/paper/1808.01813/) (2018)
- [Learning to Represent Haptic Feedback for Partially-Observable Tasks](https://mlsanity.com/paper/1705.06243/) (2017)

## Built on by (most cited first, 13 of 13)

- [Partially Observable Reinforcement Learning with Memory Traces](https://mlsanity.com/paper/2503.15200/) (2025)
- [Recurrent Natural Policy Gradient for POMDPs](https://mlsanity.com/paper/2405.18221/) (2024)
- [A Theoretical Justification for Asymmetric Actor-Critic Algorithms](https://mlsanity.com/paper/2501.19116/) (2025)
- [Scalable Policy-Based RL Algorithms for POMDPs](https://mlsanity.com/paper/2510.06540/) (2025)
- [Beyond expected value: geometric mean optimization for long-term policy performance in reinforcement learning](https://mlsanity.com/paper/2508.21443/) (2025)
- [Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPs](https://mlsanity.com/paper/2604.01024/) (2026)
- [Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamics](https://mlsanity.com/paper/2605.06377/) (2026)
- [Why Linear Recurrent Memory Works in Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2605.31261/) (2026)
- [A Representation Optimization Dichotomy, Lie-Algebraic Policy Optimization](https://mlsanity.com/paper/2603.25525/) (2026)
- [Internal State-Based Policy Gradient Methods for Partially Observable Markov Potential Games](https://mlsanity.com/paper/2604.00433/) (2026)
- [Is Backpropagation Optimal? When Synthetic Gradients Improve Sample Efficiency](https://mlsanity.com/paper/2605.27946/) (2026)
- [Reinformed Dreamer: An Asymmetric World Model Efficiently Trained through Latent Guidance](https://mlsanity.com/paper/2607.26040/) (2026)
- [Learning Suffers More Than the Policy Class Under Partial Observability: A Closed-Form Analysis](https://mlsanity.com/paper/2608.07228/) (2026)

## 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.