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 novel confidence widening technique that incorporates additional optimism.

arXiv commentTo appear in proceedings of the 37th International Conference on Machine Learning. Shortened conference version of its journal version (available at: arXiv:1906.02922)

References in corpus (13)

• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
• Efficient Contextual Bandits in Non-stationary Worlds
• Online Convex Optimization in Adversarial Markov Decision Processes
• Hedging the Drift: Learning to Optimize under Non-Stationarity
• A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitions
• Variational Regret Bounds for Reinforcement Learning
• Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes
• Optimal No-regret Learning in Repeated First-price Auctions
• Deterministic MDPs with Adversarial Rewards and Bandit Feedback
• Blind Dynamic Resource Allocation in Closed Networks via Mirror Backpressure
• Regime Switching Bandits
• Spectral State Compression of Markov Processes

Cited by in corpus (9)

• Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challenges
• Hedging the Drift: Learning to Optimize under Non-Stationarity
• Structure in Deep Reinforcement Learning: A Survey and Open Problems
• Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach
• Efficient Learning in Non-Stationary Linear Markov Decision Processes
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• CaiRL: A High-Performance Reinforcement Learning Environment Toolkit
• Lifetime policy reuse and the importance of task capacity
• Fundamental Limits of Reinforcement Learning in Environment with Endogeneous and Exogeneous Uncertainty