Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism
By Wang Chi Cheung, David Simchi-Levi, Ruihao Zhu. 2020
122 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Management Science and Operations Research
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Matthew Riemer
- Irina Rish
- Doina Precup
- Sergey Levine
- Khimya Khetarpal
- Pascal Vincent
- Ahmed Touati
- Yoshua Bengio
In Electrical and Electronic Engineering
- Na Li
- Steven H. Low
- Ahmed Touati
- Pascal Vincent
- Yujie Tang
- David Simchi-Levi
- Doina Precup
- Kaiqing Zhang
In Management Science and Operations Research
- Ahmed Touati
- Pascal Vincent
- Doina Precup
- David Simchi-Levi
- Kaiqing Zhang
- Michal Valko
- Ruihao Zhu
- Pierre M'enard
Citations in the corpus
- Towards Continual Reinforcement Learning: A Review and Perspectives (2020, background): “In this framework, it then possible to consider assumptions around variation budgets in tabular (Cheung, Simchi-Levi, and Zhu, 2020; Domingues, Ménard, Pirotta, Kaufmann, and Valko, 2020) and linear function (Touati and Vincent, 2020) MDPs to improve learning in the face of non-stationarity.”
- Near-Optimal Model-Free Reinforcement Learning in Non-Stationary Episodic MDPs (2021, methodology): “To resolve the aforementioned challenges, Ortner et al. (2019) and Cheung et al. (2020) have proposed algorithms to guide learning in non-stationary MDPs.”
- Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challenges (2021, background): “Nonstationary MDP [14] and related RL algorithms [15] could be the potential directions.”
- A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces (2020, methodology): “Recent works provide algorithms with regret bounds for non-stationary RL in the tabular setting (Gajane et al., 2018; Ortner et al., 2019; Cheung et al., 2020).”
- Efficient Learning in Non-Stationary Linear Markov Decision Processes (2020, methodology): “We can use the Bandit-over-Reinforcement-Learning framework (BoRL) (Cheung et al., 2020) to tune the forgetting parameter online.”