Model-Free Nonstationary Reinforcement Learning: Near-Optimal Regret and Applications in Multiagent Reinforcement Learning and Inventory Control

Weichao Mao (), Kaiqing Zhang (), Ruihao Zhu (), David Simchi-Levi () and Tamer Başar ()
Additional contact information
Weichao Mao: Department of Electrical and Computer Engineering & Coordinated Science Laboratory, University of Illinois Urbana-Champaign, Urbana, Illinois 61801
Kaiqing Zhang: Department of Electrical and Computer Engineering & Institute for Systems Research, University of Maryland, College Park, Maryland 20740
Ruihao Zhu: Cornell SC Johnson College of Business & Nolan School of Hotel Administration, Ithaca, New York 14853
David Simchi-Levi: Institute for Data, Systems, and Society, Department of Civil and Environmental Engineering, Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Tamer Başar: Department of Electrical and Computer Engineering & Coordinated Science Laboratory, University of Illinois Urbana-Champaign, Urbana, Illinois 61801

Management Science, 2025, vol. 71, issue 2, 1564-1580

Abstract: We consider model-free reinforcement learning (RL) in nonstationary 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 nonstationary 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 O ˜ ( S 1 3 A 1 3 Δ 1 3 H T 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 1 3 A 1 3 Δ 1 3 H 2 3 T 2 3 ) , the first lower bound in nonstationary 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 multiagent RL and inventory control across related products.

Keywords: reinforcement learning; data-driven decision making; nonstationarity; multiagent learning; inventory control (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.2022.02533 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:71:y:2025:i:2:p:1564-1580

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().