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

Weichao Mao, Kaiqing Zhang, Ruihao Zhu, David Simchi‐Levi, Tamer Başar

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 $\widetilde{O}(S^{\frac{1}{3}} A^{\frac{1}{3}} Δ^{\frac{1}{3}} H T^{\frac{2}{3}})$, where $S$ and $A$ are the numbers of states and actions, respectively, $Δ>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 nearly optimal by establishing an information-theoretical lower bound of $Ω(S^{\frac{1}{3}} A^{\frac{1}{3}} Δ^{\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.

Introduction

In real-world applications such as online auctions, dynamic pricing, and multi-agent robotics, the environment is rarely static. Standard Reinforcement Learning (RL) typically assumes a stationary Markov Decision Process (MDP), where rewards and transition dynamics are fixed. However, when these elements shift over time, agents face a critical "remembering vs. forgetting" trade-off: using historical data can bias estimates toward an obsolete environment, while using only recent data may lead to insufficient learning.

While model-based solutions—which estimate transition probabilities $P$ and rewards $R$—have been proposed, they often suffer from high computational overhead and "The Perils of Drift." In drifting environments, slightly inaccurate model estimates can lead an agent to erroneously conclude that certain states are unreachable, severely hindering exploration. This research introduces the first model-free approach to non-stationary RL, learning value functions directly to avoid the fragility and complexity of model estimation.

Methods

The authors introduce two primary algorithms designed to navigate environmental drift efficiently:

  1. RestartQ-UCB: This algorithm partitions the total time horizon $T$ into discrete epochs. At the beginning of each epoch, the agent's memory is reset (the "Restart"), effectively discarding potentially stale data. Within each epoch, the agent employs Q-learning with Upper Confidence Bounds (UCB). A key innovation is the inclusion of an "extra optimism" term ($b_\Delta$) in the UCB bonus, proportional to the variation budget ($\Delta$). This ensures the agent remains sufficiently exploratory even as the underlying environment shifts.
  2. Double-Restart Q-UCB: Recognizing that the variation budget $\Delta$ is often unknown in practice, the authors developed a parameter-free version. This algorithm utilizes a "Bandit-over-Bandit" framework (based on Exp3.P) to adaptively determine the optimal restart frequency, treating the choice of epoch length as a meta-learning problem.

Results and Analysis

The proposed algorithms were evaluated against synthetic benchmarks like the "Bidirectional Diabolical Combination Lock" and practical scenarios in multi-agent RL and inventory control.

Comparison of regret bounds and properties for various non-stationary RL algorithms.

Near-Optimality and Theoretical Bounds

A significant contribution of this work is the establishment of the first information-theoretic lower bound for non-stationary episodic RL: $\Omega(S^{1/3} A^{1/3} \Delta^{1/3} H^{2/3} T^{2/3})$. As shown in the comparison table above, RestartQ-UCB achieves a dynamic regret of $\widetilde{O}(S^{1/3} A^{1/3} \Delta^{1/3} H T^{2/3})$, matching the lower bound in all parameters except for a small factor of the episode length $H$.

Computational Efficiency

In empirical simulations, RestartQ-UCB demonstrated remarkable efficiency. It matched the cumulative rewards of state-of-the-art model-based algorithms (such as LSVI-UCB-Restart) while requiring only 0.18% of the computation time. This highlights the practical advantage of model-free methods in dynamic settings.

Robustness

The algorithms significantly outperformed standard stationary RL approaches like vanilla Q-learning and Epsilon-Greedy, which failed to adapt once environmental variations became significant. The "extra optimism" principle effectively treats non-stationarity as a form of uncertainty, allowing the Q-values to remain valid upper bounds of the moving target.

Conclusion

This work provides a rigorous foundation for model-free RL in non-stationary environments. By combining periodic restarts with drift-adjusted optimism, RestartQ-UCB achieves near-optimal performance with high computational efficiency. Future work aims to close the $H^{1/3}$ gap between the current upper and lower bounds and to extend these principles to high-dimensional state spaces using deep neural networks. While the parameter-free Double-Restart version incurs a slightly higher regret ($T^{3/4}$), it offers a practical path forward for environments where the degree of non-stationarity is unknown.

Summary updated

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 $\widetilde{O}(S^{\frac{1}{3}} A^{\frac{1}{3}} Δ^{\frac{1}{3}} H T^{\frac{2}{3}})$, where $S$ and $A$ are the numbers of states and actions, respectively, $Δ>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 $Ω(S^{\frac{1}{3}} A^{\frac{1}{3}} Δ^{\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.
BibTeX
@misc{mao2020model,
  author = {Weichao Mao and Kaiqing Zhang and Ruihao Zhu and David Simchi‐Levi and Tamer Başar},
  title = {{Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Control}},
  year = {2020},
  eprint = {2010.03161},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2010.03161},
}
Figure