# Tree Search-Based Policy Optimization under Stochastic Execution Delay

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 16 references that are in the map.
- First posted on arXiv 8 Apr 2024.

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

- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Mastering Diverse Domains through World Models](https://mlsanity.com/paper/2301.04104/) (2023)
- [Model-Based Reinforcement Learning for Atari](https://mlsanity.com/paper/1903.00374/) (2019)
- [Transformers are Sample-Efficient World Models](https://mlsanity.com/paper/2209.00588/) (2022)
- [Challenges of Real-World Reinforcement Learning](https://mlsanity.com/paper/1904.12901/) (2019)
- [Mastering Atari Games with Limited Data](https://mlsanity.com/paper/2111.00210/) (2021)
- [Reinforcement Learning with Random Delays](https://mlsanity.com/paper/2010.02966/) (2020)
- [Setting up a Reinforcement Learning Task with a Real-World Robot](https://mlsanity.com/paper/1803.07067/) (2018)
- [Acting in Delayed Environments with Non-Stationary Markov Policies](https://mlsanity.com/paper/2101.11992/) (2021)
- [Reinforcement Learning from Delayed Observations via World Models](https://mlsanity.com/paper/2403.12309/) (2024)

## Built on by (most cited first, 2 of 2)

- [Model-Based Reinforcement Learning under Random Observation Delays](https://mlsanity.com/paper/2509.20869/) (2025)
- [Inverse Delayed Reinforcement Learning](https://mlsanity.com/paper/2412.02931/) (2024)

## Abstract (arXiv)

The standard formulation of Markov decision processes (MDPs) assumes that the agent's decisions are executed immediately. However, in numerous realistic applications such as robotics or healthcare, actions are performed with a delay whose value can even be stochastic. In this work, we introduce stochastic delayed execution MDPs, a new formalism addressing random delays without resorting to state augmentation. We show that given observed delay values, it is sufficient to perform a policy search in the class of Markov policies in order to reach optimal performance, thus extending the deterministic fixed delay case. Armed with this insight, we devise DEZ, a model-based algorithm that optimizes over the class of Markov policies. DEZ leverages Monte-Carlo tree search similar to its non-delayed variant EfficientZero to accurately infer future states from the action queue. Thus, it handles delayed execution while preserving the sample efficiency of EfficientZero. Through a series of experiments on the Atari suite, we demonstrate that although the previous baseline outperforms the naive method in scenarios with constant delay, it underperforms in the face of stochastic delays. In contrast, our approach significantly outperforms the baselines, for both constant and stochastic delays. The code is available at http://github.com/davidva1/Delayed-EZ .