Acting in Delayed Environments with Non-Stationary Markov Policies

2021/01/28 by Esther Derman, Derman, Esther, Gal Dalal +3 · 3 citations
Computer Science · #Adversarial Robustness in Machine Learning #Age of Information Optimization #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2101.11992

openalex publication_date 2021/01/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures
• Challenges of Real-World Reinforcement Learning

Cited by

• Model-Based Reinforcement Learning under Random Observation Delays
• Synthetic POMDPs to Challenge Memory-Augmented RL: Memory Demand Structure Modeling
• Reinforcement Learning via Conservative Agent for Environments with Random Delays

Related

• Tree Search-Based Policy Optimization under Stochastic Execution Delay
• Delays in Reinforcement Learning
• Markov Decision Processes under External Temporal Processes
• Modular Deep Reinforcement Learning with Temporal Logic Specifications
• Faster Reinforcement Learning by Freezing Slow States