# Acting in Delayed Environments with Non-Stationary Markov Policies

arXiv: https://arxiv.org/abs/2101.11992 · HTML: https://mlsanity.com/paper/2101.11992/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 35 references that are in the map.
- First posted on arXiv 28 Jan 2021.

## Builds on (most cited first, 14 of 14)

- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures](https://mlsanity.com/paper/1802.01561/) (2018)
- [Challenges of Real-World Reinforcement Learning](https://mlsanity.com/paper/1904.12901/) (2019)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Learning to Simulate Dynamic Environments with GameGAN](https://mlsanity.com/paper/2005.12126/) (2020)
- [Real-Time Reinforcement Learning](https://mlsanity.com/paper/1911.04448/) (2019)
- [Delay-Aware Model-Based Reinforcement Learning for Continuous Control](https://mlsanity.com/paper/2005.05440/) (2020)
- [Thinking While Moving: Deep Reinforcement Learning with Concurrent Control](https://mlsanity.com/paper/2004.06089/) (2020)
- [At Human Speed: Deep Reinforcement Learning with Action Delay](https://mlsanity.com/paper/1810.07286/) (2018)
- [Delay-Aware Multi-Agent Reinforcement Learning for Cooperative and Competitive Environments](https://mlsanity.com/paper/2005.05441/) (2020)
- [Improved and Generalized Upper Bounds on the Complexity of Policy Iteration](https://mlsanity.com/paper/1306.0386/) (2013)
- [26ms Inference Time for ResNet-50: Towards Real-Time Execution of all DNNs on Smartphone](https://mlsanity.com/paper/1905.00571/) (2019)
- [Towards Safety-Aware Computing System Design in Autonomous Vehicles](https://mlsanity.com/paper/1905.08453/) (2019)
- [Bandits with Delayed, Aggregated Anonymous Feedback](https://mlsanity.com/paper/1709.06853/) (2017)

## Built on by (most cited first, 30 of 31)

- [When Do Transformers Shine in RL? Decoupling Memory from Credit Assignment](https://mlsanity.com/paper/2307.03864/) (2023)
- [A Survey of Sim-to-Real Methods in RL: Progress, Prospects and Challenges with Foundation Models](https://mlsanity.com/paper/2502.13187/) (2025)
- [Off-Policy Reinforcement Learning with Delayed Rewards](https://mlsanity.com/paper/2106.11854/) (2021)
- [Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback](https://mlsanity.com/paper/2201.13172/) (2022)
- [Revisiting State Augmentation methods for Reinforcement Learning with Stochastic Delays](https://mlsanity.com/paper/2108.07555/) (2021)
- [Delayed Reinforcement Learning by Imitation](https://mlsanity.com/paper/2205.05569/) (2022)
- [Reinforcement Learning from Delayed Observations via World Models](https://mlsanity.com/paper/2403.12309/) (2024)
- [Neural Laplace Control for Continuous-time Delayed Systems](https://mlsanity.com/paper/2302.12604/) (2023)
- [Boosting Reinforcement Learning with Strongly Delayed Feedback Through Auxiliary Short Delays](https://mlsanity.com/paper/2402.03141/) (2024)
- [Planning and Learning with Adaptive Lookahead](https://mlsanity.com/paper/2201.12403/) (2022)
- [DEER: A Delay-Resilient Framework for Reinforcement Learning with Variable Delays](https://mlsanity.com/paper/2406.03102/) (2024)
- [Enabling Realtime Reinforcement Learning at Scale with Staggered Asynchronous Inference](https://mlsanity.com/paper/2412.14355/) (2024)
- [Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedback](https://mlsanity.com/paper/2305.07911/) (2023)
- [Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2310.18919/) (2023)
- [Model-Based Reinforcement Learning under Random Observation Delays](https://mlsanity.com/paper/2509.20869/) (2025)
- [Tree Search-Based Policy Optimization under Stochastic Execution Delay](https://mlsanity.com/paper/2404.05440/) (2024)
- [Finding the Time to Think: Learning Planning Budgets in Real-Time RL](https://mlsanity.com/paper/2606.26463/) (2026)
- [Evaluating the progress of Deep Reinforcement Learning in the real world: aligning domain-agnostic and domain-specific research](https://mlsanity.com/paper/2107.03015/) (2021)
- [Off-Beat Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2205.13718/) (2022)
- [Twice Regularized Markov Decision Processes: The Equivalence between Robustness and Regularization](https://mlsanity.com/paper/2303.06654/) (2023)
- [Adaptive PD Control using Deep Reinforcement Learning for Local-Remote Teleoperation with Stochastic Time Delays](https://mlsanity.com/paper/2305.16979/) (2023)
- [Control in Stochastic Environment with Delays: A Model-based Reinforcement Learning Approach](https://mlsanity.com/paper/2402.00313/) (2024)
- [Reinforcement Learning via Conservative Agent for Environments with Random Delays](https://mlsanity.com/paper/2507.18992/) (2025)
- [Synthetic POMDPs to Challenge Memory-Augmented RL: Memory Demand Structure Modeling](https://mlsanity.com/paper/2508.04282/) (2025)
- [Trajectory Planning for Teleoperated Space Manipulators Using Deep Reinforcement Learning](https://mlsanity.com/paper/2408.05460/) (2024)
- [Overcoming Slow Decision Frequencies in Continuous Control: Model-Based Sequence Reinforcement Learning for Model-Free Control](https://mlsanity.com/paper/2410.08979/) (2024)
- [Delayed homomorphic reinforcement learning for environments with delayed feedback](https://mlsanity.com/paper/2604.03641/) (2026)
- [Structural Equivalence and Learning Dynamics in Delayed MARL](https://mlsanity.com/paper/2605.04345/) (2026)
- [LangLoc: "Tell Me What You See"](https://mlsanity.com/paper/2607.05077/) (2026)
- [Sim2Signal: Sim-to-Real Benchmarks for Traffic Signal Control](https://mlsanity.com/paper/2609.01676/) (2026)

## Abstract (arXiv)

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/rldelaybasic and github.com/galdl/rldelayatari.