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

• 成果类型: Article
• 署名作者: Mao, Weichao; Zhang, Kaiqing; Zhu, Ruihao; Simchi-Levi, David; Basar, Tamer
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign; University System of Maryland; University of Maryland College Park; University System of Maryland; University of Maryland College Park; Massachusetts Institute of Technology (MIT)
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2022.02533
• 发表日期: 2025
• 关键词: Reinforcement learning; data-driven decision making; Nonstationarity; multiagent learning; INVENTORY CONTROL

摘要

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)Delta(HT2/3)-H-1/3), where S and A are the numbers of states and actions, respectively, Delta>0 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(1/3)A(1/3)Delta(HT2/3)-H-1/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.