Acting in Delayed Environments with Non-Stationary Markov Policies
Preprint
Abstract
The standard Markov Decision Process (MDP) formulation hinges on the assumption that an action is executed immediately after it was chosen. However, assuming it is often unrealistic and can lead to catastrophic failures in applications such as robotic manipulation, cloud computing, and finance. We introduce a framework for learning and planning in MDPs where the decision-maker commits actions that are executed with a delay of $m$ steps. The brute-force state augmentation baseline where the state is concatenated to the last $m$ committed actions suffers from an exponential complexity in $m$, as we show for policy iteration. We then prove that with execution delay, deterministic Markov policies in the original state-space are sufficient for attaining maximal reward, but need to be non-stationary. As for stationary Markov policies, we show they are sub-optimal in general. Consequently, we devise a non-stationary Q-learning style model-based algorithm that solves delayed execution tasks without resorting to state-augmentation. Experiments on tabular, physical, and Atari domains reveal that it converges quickly to high performance even for substantial delays, while standard approaches that either ignore the delay or rely on state-augmentation struggle or fail due to divergence. The code is available at github.com/galdl/rl_delay_basic and github.com/galdl/rl_delay_atari.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Delay-aware model-based reinforcement learning for continuous controlNeurocomputing, 2021
- Challenges of real-world reinforcement learning: definitions, benchmarks and analysisMachine Learning, 2021
- Improved and Generalized Upper Bounds on the Complexity of Policy IterationMathematics of Operations Research, 2016
- Deep Reinforcement Learning with Double Q-LearningProceedings of the AAAI Conference on Artificial Intelligence, 2016
- TEXPLORE: real-time sample-efficient reinforcement learning for robotsMachine Learning, 2012
- Time-delay systems: an overview of some recent advances and open problemsAutomatica, 2003
- Explicit Solution of Inventory Problems with Delivery LagsMathematics of Operations Research, 1995