Non-Stationary Markov Decision Processes a Worst-Case Approach using Model-Based Reinforcement Learning

By Erwan Lecarpentier, Emmanuel Rachelson. 2019

100 citations recorded by the source corpus.

This work tackles the problem of robust zero-shot planning in non-stationary stochastic environments. We study Markov Decision Processes (MDPs) evolving over time and consider Model-Based Reinforcement Learning algorithms in this setting. We make two hypotheses: 1) the environment evolves continuously with a bounded evolution rate; 2) a current model is known at each decision epoch but not its evolution. Our contribution can be presented in four points. 1) we define a specific class of MDPs that we call Non-Stationary MDPs (NSMDPs). We introduce the notion of regular evolution by making an hypothesis of Lipschitz-Continuity on the transition and reward functions w.r.t. time; 2) we consider a planning agent using the current model of the environment but unaware of its future evolution. This leads us to consider a worst-case method where the environment is seen as an adversarial agent; 3) following this approach, we propose the Risk-Averse Tree-Search (RATS) algorithm, a zero-shot Model-Based method similar to Minimax search; 4) we illustrate the benefits brought by RATS empirically and compare its performance with reference Model-Based algorithms.

Subfields: Artificial Intelligence, 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

In Management Science and Operations Research

Citations in the corpus

Dynamic Dialogue Policy for Continual Reinforcement Learning (2022, background): “Generally speaking, the agent faces a sequence of Markov decision processes {Mz}z=1 (Lecarpentier and Rachelson, 2019; Chandak et al., 2020; Khetarpal et al., 2020b) with possibly different transition dynamics, reward functions or even state or action spaces.”
Towards Continual Reinforcement Learning: A Review and Perspectives (2020, background): “Even mild assumptions such as restricting the change in an MDP to be slow or Lipschitz can provide a basis for robust worst case optimization (Lecarpentier and Rachelson, 2019; Li, Wang, Jin, Sheng, and Zha, 2021).”
Deep Reinforcement Learning for Task Offloading in Mobile Edge Computing Systems (2020, unknown): “, [33]) and lifelong reinforcement learning [34].”
Towards Safe Policy Improvement for Non-Stationary MDPs (2020, unknown): “To avoid arbitrary changes, previous works typically require the transition function Pk and the reward functionRk to be Lipschitz smooth over time [39, 30, 40, 16].”
Reactive Exploration to Cope with Non-Stationarity in Lifelong Reinforcement Learning (2022, methodology): “Other strategies include memory-based exploration strategies such as episodic memory (Badia et al., 2020) or planning with worst-base planning evolution (Lecarpentier & Rachelson, 2019), GoExplore (Ecoffet et al., 2019), and optimal experiment design (Cohn, 1994; Storck et al., 1995).”
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.”
Reset-Free Lifelong Learning with Skill-Space Planning (2020, background): “Lecarpentier & Rachelson (2019) tackles nonstationarity in zero-shot for simple discrete MDPs by using risk-averse planning; our experiments generally suggested that accurate and scalable planning was more important than explicit risk aversion for our settings.”