mlsanityData to 14 Oct 2026

Natural Policy Gradient for Average Reward Non-Stationary RL

arXiv 2504.16415 ↗First posted 23 Apr 2025cs.LG stat.MLcited by 0

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

Abstract (arXiv)

We consider the problem of non-stationary reinforcement learning (RL) in the infinite-horizon average-reward setting. We model it by a Markov Decision Process with time-varying rewards and transition probabilities, with a variation budget of DeltaT. Existing non-stationary RL algorithms focus on model-based and model-free value-based methods. Policy-based methods despite their flexibility in practice are not theoretically well understood in non-stationary RL. We propose and analyze the first model-free policy-based algorithm, Non-Stationary Natural Actor-Critic (NS-NAC), a policy gradient method with a restart based exploration for change and a novel interpretation of learning rates as adapting factors. Further, we present a bandit-over-RL based parameter-free algorithm BORL-NS-NAC that does not require prior knowledge of the variation budget DeltaT. We present a dynamic regret of tildemathscr O(|S|1/2|A|1/2DeltaT1/6T5/6) for both algorithms, where T is the time horizon, and |S|, |A| are the sizes of the state and action spaces. The regret analysis leverages a novel adaptation of the Lyapunov function analysis of NAC to dynamic environments and characterizes the effects of simultaneous updates in policy, value function estimate and changes in the environment.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 36 of its 58 references that are in the map. First posted on arXiv 23 Apr 2025.

Builds on

36 of 58 references.

Closest ancestors · 2

Same direction, newest first

  1. 2024Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation3 Jun
  2. 2024Pausing Policy Learning in Non-stationary Reinforcement Learning25 May

Other references · 34

  1. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
  2. 2014New insights and perspectives on the natural gradient methodcited by 443
  3. 2017Bridging the Gap Between Value and Policy Based Reinforcement Learningcited by 182
  4. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  5. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 122
  6. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  7. 2018Learning to Optimize under Non-Stationaritycited by 85
  8. 2019Finite-Sample Analysis for SARSA with Linear Function Approximationcited by 85
  9. 2020Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimismcited by 76
  10. 2020Transient Non-Stationarity and Generalisation in Deep Reinforcement Learningcited by 75
  11. 2020A Survey of Reinforcement Learning Algorithms for Dynamically Varying Environmentscited by 62
  12. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
22 more
  1. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  2. 2020Optimizing for the Future in Non-Stationary MDPscited by 37
  3. 2019Non-Stationary Markov Decision Processes, a Worst-Case Approach using Model-Based Reinforcement Learning, Extended versioncited by 36
  4. 2020Dynamic Regret of Policy Optimization in Non-stationary Environmentscited by 33
  5. 2017Taming Non-stationary Bandits: A Bayesian Approachcited by 32
  6. 2019Variational Regret Bounds for Reinforcement Learningcited by 32
  7. 2020A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spacescited by 32
  8. 2022Finite-time analysis of single-timescale actor-criticcited by 32
  9. 2018A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitionscited by 30
  10. 2020Efficient Learning in Non-Stationary Linear Markov Decision Processescited by 26
  11. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 26
  12. 2020Nonstationary Reinforcement Learning with Linear Function Approximationcited by 23
  13. 2022Non-Stationary Bandit Learning via Predictive Samplingcited by 21
  14. 2021Improved Regret Bound and Experience Replay in Regularized Policy Iterationcited by 18
  15. 2023Smooth Non-Stationary Banditscited by 13
  16. 2020RL-QN: A Reinforcement Learning Framework for Optimal Control of Queueing Systemscited by 11
  17. 2023A Definition of Non-Stationary Banditscited by 9
  18. 2023Performance Bounds for Policy-Based Average Reward Reinforcement Learning Algorithmscited by 7
  19. 2023The complexity of non-stationary reinforcement learningcited by 7
  20. 2024Efficient Reinforcement Learning for Routing Jobs in Heterogeneous Queueing Systemscited by 7
  21. 2019Blind Dynamic Resource Allocation in Closed Networks via Mirror Backpressurecited by 6
  22. 2023Non-stationary Reinforcement Learning under General Function Approximationcited by 6

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Is Prior-Free Black-Box Non-Stationary Reinforcement Learning Feasible?
  2. 2026Policy Gradient Methods for Non-Markovian Reinforcement Learning
  3. 2024MetaCURL: Non-stationary Concave Utility Reinforcement Learning
  4. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
  5. 2024Learning Rate-Free Reinforcement Learning: A Case for Model Selection with Non-Stationary Objectives
  6. 2020Average-reward model-free reinforcement learning: a systematic review and literature mapping
  7. 2025Non-stationary and Varying-discounting Markov Decision Processes for Reinforcement Learning
  8. 2024Recurrent Natural Policy Gradient for POMDPs