Natural Policy Gradient for Average Reward Non-Stationary RL

2025/04/23 by Jali, Neharika, Pathak, Eshika, Sharma, Pranay +2
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2504.16415

Abstract

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 Δ_T. 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 Δ_T. We present a dynamic regret of \mathscr O(|S|^1/2|A|^1/2Δ_T^1/6T^5/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.

Related

• Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Control
• Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism
• Dynamic Regret of Policy Optimization in Non-stationary Environments
• A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
• Finite-time Convergence Analysis of Actor-Critic with Evolving Reward