mlsanityData to 14 Oct 2026

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

arXiv 2405.20467 ↗First posted 30 May 2024cs.LG math.OCcited by 5

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

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.

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.

Builds on

11 of 43 references.

References · 11

  1. 2019A Theory of Regularized Markov Decision Processescited by 286
  2. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 250
  3. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 150
  4. 2018Learning Scheduling Algorithms for Data Processing Clusterscited by 134
  5. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 121
  6. 2020Queueing Network Controls via Deep Reinforcement Learningcited by 41
  7. 2021The Dynamics of Gradient Descent for Overparametrized Neural Networkscited by 11
  8. 2023Sample Efficient Reinforcement Learning in Mixed Systems through Augmented Samples and Its Applications to Queueing Networkscited by 9
  9. 2020Stable Reinforcement Learning with Unbounded State Spacecited by 8
  10. 2023Performance Bounds for Policy-Based Average Reward Reinforcement Learning Algorithmscited by 7
  11. 2019Dynamic Pricing and Matching for Two-Sided Queuescited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 1; 2026: 3.

5 papers.

  1. 2026Queue Length Regret Bounds for Contextual Queueing Banditscited by 4
  2. 2026Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regretcited by 2
  3. 2024To bootstrap or to rollout? An optimal and adaptive interpolationcited by 0
  4. 2025Near-Optimal Regret-Queue Length Tradeoff in Online Learning for Two-Sided Marketscited by 0
  5. 2026Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Convergence of Natural Policy Gradient for a Family of Infinite-State Queueing MDPs
  2. 2026Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes
  3. 2024Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reduction
  4. 2024Fast Convergence of Softmax Policy Mirror Ascent
  5. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
  6. 2024Linear Convergence of Independent Natural Policy Gradient in Games with Entropy Regularization
  7. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space
  8. 2024Recurrent Natural Policy Gradient for POMDPs