# Performance of NPG in Countable State-Space Average-Cost RL

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

## Key facts

- Cited by 5 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 11 of its 43 references that are in the map.
- First posted on arXiv 30 May 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019)
- [Learning Scheduling Algorithms for Data Processing Clusters](https://mlsanity.com/paper/1810.01963/) (2018)
- [Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks](https://mlsanity.com/paper/1909.12292/) (2019)
- [Queueing Network Controls via Deep Reinforcement Learning](https://mlsanity.com/paper/2008.01644/) (2020)
- [The Dynamics of Gradient Descent for Overparametrized Neural Networks](https://mlsanity.com/paper/2105.06569/) (2021)
- [Sample Efficient Reinforcement Learning in Mixed Systems through Augmented Samples and Its Applications to Queueing Networks](https://mlsanity.com/paper/2305.16483/) (2023)
- [Stable Reinforcement Learning with Unbounded State Space](https://mlsanity.com/paper/2006.04353/) (2020)
- [Performance Bounds for Policy-Based Average Reward Reinforcement Learning Algorithms](https://mlsanity.com/paper/2302.01450/) (2023)
- [Dynamic Pricing and Matching for Two-Sided Queues](https://mlsanity.com/paper/1911.02213/) (2019)

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

- [Queue Length Regret Bounds for Contextual Queueing Bandits](https://mlsanity.com/paper/2601.19300/) (2026)
- [Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret](https://mlsanity.com/paper/2606.09668/) (2026)
- [To bootstrap or to rollout? An optimal and adaptive interpolation](https://mlsanity.com/paper/2411.09731/) (2024)
- [Near-Optimal Regret-Queue Length Tradeoff in Online Learning for Two-Sided Markets](https://mlsanity.com/paper/2510.14097/) (2025)
- [Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs](https://mlsanity.com/paper/2610.04117/) (2026)

## Abstract (arXiv)

We consider policy optimization methods in reinforcement learning settings where the state space is arbitrarily large, or even countably infinite. The motivation arises from control problems in communication networks, matching markets, and other queueing systems. Specifically, we consider the popular Natural Policy Gradient (NPG) algorithm, which has been studied in the past only under the assumption that the cost is bounded and the state space is finite, neither of which holds for the aforementioned control problems. Assuming a Lyapunov drift condition, which is naturally satisfied in some cases and can be satisfied in other cases at a small cost in performance, we design a state-dependent step-size rule which dramatically improves the performance of NPG for our intended applications. In addition to experimentally verifying the performance improvement, we also theoretically show that the iteration complexity of NPG can be made independent of the size of the state space. The key analytical tool we use is the connection between NPG step-sizes and the solution to Poisson's equation. In particular, we provide policy-independent bounds on the solution to Poisson's equation, which are then used to guide the choice of NPG step-sizes.