Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Control

Abstract

We consider model-free reinforcement learning (RL) in non-stationary Markov decision processes. Both the reward functions and the state transition functions are allowed to vary arbitrarily over time as long as their cumulative variations do not exceed certain variation budgets. We propose Restarted Q-Learning with Upper Confidence Bounds (RestartQ-UCB), the first model-free algorithm for non-stationary RL, and show that it outperforms existing solutions in terms of dynamic regret. Specifically, RestartQ-UCB with Freedman-type bonus terms achieves a dynamic regret bound of $\tilde{O}(S^{\frac{1}{3}}{A}^{\frac{1}{3}}{\Delta }^{\frac{1}{3}}H{T}^{\frac{2}{3}})$, where $S$ and $A$ are the numbers of states and actions, respectively, $\Delta >0$ is the variation budget, $H$ is the number of time steps per episode, and $T$ is the total number of time steps. We further present a parameter-free algorithm named Double-Restart Q-UCB that does not require prior knowledge of the variation budget. We show that our algorithms are \emph{nearly optimal} by establishing an information-theoretical lower bound of $\Omega (S^{\frac{1}{3}}{A}^{\frac{1}{3}}{\Delta }^{\frac{1}{3}}{H}^{\frac{2}{3}}{T}^{\frac{2}{3}})$, the first lower bound in non-stationary RL. Numerical experiments validate the advantages of RestartQ-UCB in terms of both cumulative rewards and computational efficiency. We demonstrate the power of our results in examples of multi-agent RL and inventory control across related products.

arXiv commentA preliminary version of this work has appeared in ICML 2021

References in corpus (17)

• A Survey of Reinforcement Learning Algorithms for Dynamically Varying Environments
• Fast Convergence of Regularized Learning in Games
• Sample Complexity of Multi-task Reinforcement Learning
• On Lower Bounds for Regret in Reinforcement Learning
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free
• Hedging the Drift: Learning to Optimize under Non-Stationarity
• A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitions
• A Simple Approach for Non-stationary Linear Bandits
• Variational Regret Bounds for Reinforcement Learning
• Provably Efficient Q-Learning with Low Switching Cost
• Independent Policy Gradient Methods for Competitive Reinforcement Learning
• Learning to Collaborate in Markov Decision Processes
• Regime Switching Bandits
• Dynamic Regret of Policy Optimization in Non-stationary Environments
• Learning and Optimization with Seasonal Patterns
• Efficient Learning in Non-Stationary Linear Markov Decision Processes