Research map / Reinforcement learning / MDPs and planning
Tree Search-Based Policy Optimization under Stochastic Execution Delay
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces stochastic execution-delay MDPs (SED-MDPs) and DEZ, an EfficientZero-based MCTS agent that handles random action delays by forecasting pending actions, showing Markov policies suffice for optimality.
Problem
Reinforcement learning where agent actions are executed after a random, observed delay, causing previously chosen actions to be overwritten or duplicated; state augmentation grows exponentially with delay and does not generalize to random delays.
Approach
Formalizes random execution delay as SED-MDP without state augmentation, proves Markov policies (conditioned on observed delays) suffice for optimality, and uses a learned forward model over the action queue inside EfficientZero's MCTS to predict the state at execution time.
Key results
- Under constant delays, DEZ achieves the best average score in 39 of 45 experiments versus baselines.
- Under stochastic delays, DEZ achieves the highest average score in 42 of 45 experiments.
- Delayed-Q achieves at least 85% of DEZ's score in 21 of 45 constant-delay experiments, mainly due to limited sample budget.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DEZ to account explicitly for constant execution delay instead of oblivious EfficientZero or Delayed-Q | Atari policy optimization · Atari suite, constant delays 5, 15, and 25 | average score | Helped |
| Use DEZ to account explicitly for stochastic execution delay instead of the baselines | Atari policy optimization · Atari suite, stochastic delays with maximal delay 5, 15, and 25 | average score | Helped |
| Increase stochastic maximum delay in DEZ to 35 or 45 | DEZ on Asterix · Asterix, stochastic delay | learning performance | Hurt |
| Increase stochastic maximum delay in DEZ | DEZ on Atari games · Asterix and Hero, stochastic delay up to M=45 | score | Hurt |
Surprising findings
- Delayed-Q suffers more from stochastic delays than oblivious EfficientZero, even though it does better under constant delays.
Limitations
- Relies on a learned world model whose compounding errors grow with environment stochasticity
- Assumes delay values are observed in real time and delay process is independent of the MDP
- Performance degrades for very large delays (e.g., Asterix at M=35 and 45)
Experimental setup
Datasets: Atari 2600 games (15 games)
Benchmarks: Atari (15 games) with constant delays 5, 15, 25 Atari (15 games) with stochastic delays up to 5, 15, 25 Asterix and Hero with delays up to 45
Metrics: average score standard deviation
Baselines: Oblivious EfficientZero Delayed-Q Delayed DQN
Builds on: EfficientZero MuZero Delayed-Q ED-MDP formulation
Closest papers by meaning
- SPOT: Scalable Policy Optimization with Trees for Markov Decision Processes (NeurIPS 2025 · similarity 0.87)
- A Surprisingly Simple Continuous-Action POMDP Solver: Lazy Cross-Entropy Search Over Policy Trees (AAAI 2024 · similarity 0.87)
- Power Mean Estimation in Stochastic Continuous Monte-Carlo Tree Search (ICML 2025 · similarity 0.86)
- Threshold UCT: Cost-Constrained Monte Carlo Tree Search with Pareto Curves (AAAI 2025 · similarity 0.86)
- Sequential Monte Carlo for Policy Optimization in Continuous POMDPs (NeurIPS 2025 · similarity 0.86)
- Solving Robust Markov Decision Processes: Generic, Reliable, Efficient (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.