Reinforcement Learning For Non-stationary Markov Decision Processes: The Blessing Of (more) Optimism

Abstract

We consider un-discounted reinforcement learning (RL) in Markov decision processes (MDPs) under drifting non-stationarity, i.e., both the reward and state transition distributions are allowed to evolve over time, as long as their respective total variations, quantified by suitable metrics, do not exceed certain variation budgets. We first develop the Sliding Window Upper-Confidence bound for Reinforcement Learning with Confidence Widening (SWUCRL2-CW) algorithm, and establish its dynamic regret bound when the variation budgets are known. In addition, we propose the Bandit-over-Reinforcement Learning (BORL) algorithm to adaptively tune the SWUCRL2-CW algorithm to achieve the same dynamic regret bound, but in a parameter-free manner, i.e., without knowing the variation budgets. Notably, learning non-stationary MDPs via the conventional optimistic exploration technique presents a unique challenge absent in existing (non-stationary) bandit learning settings. We overcome the challenge by a

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keycheung2020reinforcement

Related papers

• Non-stationary Reinforcement Learning: The Blessing Of (more) Optimism (2019)0.00
• Asymptotically Optimal Reinforcement Learning In Block Markov Decision Processes (2025)0.00
• Non-stationary Risk-sensitive Reinforcement Learning: Near-optimal Dynamic Regret, Adaptive Detection, And Separation Design (2022)3.58
• Nonstationary Reinforcement Learning With Linear Function Approximation (2020)0.00
• Efficient Learning In Non-stationary Linear Markov Decision Processes (2020)6.77
• DOPE: Doubly Optimistic And Pessimistic Exploration For Safe Reinforcement Learning (2021)0.00
• Optimistic Policy Optimization Is Provably Efficient In Non-stationary Mdps (2021)0.00
• Fundamental Limits Of Reinforcement Learning In Environment With Endogeneous And Exogeneous Uncertainty (2021)0.00