Near-Optimal Regret Bounds for Model-Free RL in Non-Stationary Episodic MDPs

Weichao Mao, Kaiqing Zhang, Ruihao Zhu, David Simchi-Levi, Tamer Basar

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}} \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 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.

Introduction

In the world of Reinforcement Learning (RL), we often assume the "rules of the game" are fixed. We train an agent in a static environment, and it eventually learns the optimal policy. However, real-world scenarios—like ad auctions, dynamic pricing, and traffic management—are inherently non-stationary. When the environment shifts while the agent is still playing, traditional algorithms often fail to adapt. This research addresses the challenge of non-stationary RL, providing a breakthrough in how agents can navigate environments where both rewards and transition physics change over time.

The Challenge of Non-Stationarity

The fundamental difficulty in non-stationary RL is the trade-off between remembering and forgetting. If an agent relies too much on old data, it might follow a policy that is no longer effective because the environment has shifted—a phenomenon known as "The Perils of Drift." Conversely, if it forgets too quickly, it won't have enough data to learn anything useful.

Existing solutions have primarily been model-based, meaning they attempt to estimate the entire transition physics of the environment. While effective, these methods are often computationally heavy and "space-inefficient," making them difficult to scale to modern deep RL architectures. This paper introduces a more efficient model-free alternative.

Proposed Algorithms: RestartQ-UCB and Double-Restart Q-UCB

The authors propose RestartQ-UCB, a model-free algorithm based on Q-learning. It relies on two key mechanisms:

  1. Restarting Strategy: The algorithm divides time into "epochs." At the start of each epoch, it wipes its memory and starts fresh. This ensures the agent isn't led astray by obsolete data from a previous version of the environment.
  2. Upper Confidence Bound (UCB) Exploration: To handle the exploration-exploitation dilemma, it uses Freedman-type bonus terms. These are tighter than standard bonuses because they account for the variance of the rewards, allowing for more efficient learning.

For scenarios where the degree of environmental change is unknown, the authors introduce Double-Restart Q-UCB. This "parameter-free" version uses a multi-armed bandit "master" procedure to adaptively learn the best restart frequency on the fly, removing the need for prior knowledge of the "variation budget" ($\Delta$).

Theoretical Landscape and Key Results

A major contribution of this work is the establishment of the first information-theoretical lower bound for non-stationary RL. This provides a "speed limit" for how well any algorithm can possibly perform. The proposed RestartQ-UCB algorithm is shown to be nearly optimal, matching this lower bound in terms of states ($S$), actions ($A$), and time ($T$).

Comparison of regret bounds for non-stationary RL algorithms across different settings.

As shown in the table above, RestartQ-UCB is the first model-free algorithm to achieve these competitive regret bounds in the episodic setting. Beyond theoretical performance, the algorithm is remarkably efficient. In simulations, RestartQ-UCB matched the cumulative rewards of the state-of-the-art model-based solution (LSVI-UCB-Restart) while requiring only 0.18% of the computation time.

Experimental Validation

The researchers evaluated their approach using a synthetic but challenging benchmark: the Bidirectional Diabolical Combination Lock. This task is specifically designed to be difficult for exploration, consisting of two paths where one leads to a high reward and the other to a low reward. They tested the algorithms against both abrupt variations (periodically switching which path is "good") and gradual variations (slowly shifting transition probabilities). In both cases, RestartQ-UCB demonstrated superior adaptability and efficiency.

Conclusion and Future Work

This work proves that model-free approaches are sufficient for handling non-stationarity effectively. By using a well-tuned restarting mechanism, agents can achieve near-optimal dynamic regret without the computational overhead of model-based methods.

While a small theoretical gap of $H^{1/3}$ remains between the upper and lower regret bounds, the authors suggest that closing this gap and extending these bounds to function approximation (Deep RL) are the next frontiers. Future work may also explore "soft" forgetting mechanisms, such as sliding windows or discounted weights, to further refine performance in environments with gradual changes.

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}} \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.
BibTeX
@misc{mao2020near,
  author = {Weichao Mao and Kaiqing Zhang and Ruihao Zhu and David Simchi-Levi and Tamer Basar},
  title = {{Near-Optimal Regret Bounds for Model-Free RL in Non-Stationary Episodic MDPs}},
  year = {2020},
  eprint = {2010.03161},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2010.03161},
}
Figure