Is Model-Free Learning Nearly Optimal for Non-Stationary RL?

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}} \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 show that our algorithm is 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 further demonstrate the power of our results in the context of multi-agent RL, where non-stationarity is a key challenge.

Introduction

Most classical Reinforcement Learning (RL) assumes a stationary environment where rewards and state transitions remain constant. However, real-world applications—such as online advertising, traffic management, and multi-agent systems—are inherently non-stationary. In these environments, an agent must navigate the trade-off between remembering past data to learn and forgetting it to avoid obsolescence.

While model-based algorithms have addressed non-stationarity by building explicit maps of the environment, they are often computationally expensive and sensitive to model drift. This research introduces RestartQ-UCB, the first model-free algorithm designed for non-stationary RL, offering a robust and efficient alternative that matches the theoretical performance of complex model-based methods.

Methodology: RestartQ-UCB

The proposed algorithm, RestartQ-UCB, is a variant of Q-learning that employs two core strategies to handle environmental shifts:

  1. Periodic Restarting: The total time horizon $T$ is divided into epochs. At the start of each epoch, the algorithm resets its memory. This "forgetting" mechanism prevents the agent from being misled by outdated data from previous environmental states.
  2. Optimistic Exploration (UCB): The algorithm uses Freedman-type bonus terms to encourage exploration. Crucially, it incorporates an additional optimism term specifically designed to account for potential environmental variations occurring within a single epoch.

For practical scenarios where the "variation budget" ($\Delta$) is unknown, the authors developed Double-Restart Q-UCB. This parameter-free version utilizes a multi-armed bandit "master" algorithm to dynamically determine the optimal restart frequency.

Theoretical Performance and Near-Optimality

A central contribution of this work is proving that model-free methods can achieve parity with model-based methods in non-stationary settings. The authors established the first information-theoretical lower bound for non-stationary RL: $\Omega(S^{1/3} A^{1/3} \Delta^{1/3} H^{2/3} T^{2/3})$.

Comparison of regret bounds and model-free status across various RL settings.

As shown in the table above, RestartQ-UCB achieves a dynamic regret bound that matches this lower bound in all parameters except for a small factor of $H^{1/3}$. This demonstrates that estimating a full transition matrix is not necessary to achieve near-optimal performance in a changing world.

Empirical Results and Efficiency

The researchers evaluated RestartQ-UCB using a Bidirectional Diabolical Combination Lock, a benchmark designed to be exceptionally difficult for exploration. The environment was modified to include both abrupt variations (switching reward paths) and gradual variations (shifting transition probabilities).

Key findings include:

  • Computational Speed: RestartQ-UCB matched the cumulative rewards of state-of-the-art model-based solutions (like LSVI-UCB-Restart) while requiring only 0.18% of the computation time.
  • Regret Scaling: The algorithm maintains a regret scaling of $T^{2/3}$, significantly outperforming standard RL algorithms that suffer from linear regret ($T$) when faced with non-stationarity.

Conclusion and Future Directions

RestartQ-UCB proves that model-free learning is not only viable but highly efficient for non-stationary RL. This has significant implications for decentralized multi-agent RL, where an agent perceives the environment as non-stationary due to the changing behaviors of others. Future work aims to close the $H^{1/3}$ theoretical gap and extend these near-optimal guarantees to deep RL using neural network function approximation.

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 show that our algorithm is \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 further demonstrate the power of our results in the context of multi-agent RL, where non-stationarity is a key challenge.
BibTeX
@misc{mao2020is,
  author = {Weichao Mao and Kaiqing Zhang and Ruihao Zhu and David Simchi‐Levi and Tamer Başar},
  title = {{Is Model-Free Learning Nearly Optimal for Non-Stationary RL?}},
  year = {2020},
  eprint = {2010.03161},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2010.03161},
}
Figure