Tree Search-Based Policy Optimization under Stochastic Execution Delay
Authors: David Valensi
Esther Derman
Shie Mannor
Gal Dalal
Venue: ICLR 2024 poster (2024)
Keywords: Reinforcement Learning
Delay
EfficientZero
Tree-search
Sample efficiency
Primary area: reinforcement learning
TL;DR: We prove results for Reinforcement Learning with stochastic delay, devise a corresponding tree-search based algorithm, and successfully test it on such environments.

Abstract: 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 empirical analysis, we stress that none of the prior benchmarks consistently outperforms others across different delays. We demonstrate that our algorithm surpasses all benchmark methods in Atari games when dealing with constant or stochastic delays. The code is available at \url{https://github.com/davidva1/Delayed-EZ}.

Published as a conference paper at ICLR 2024
TREE SEARCH-BASED POLICY OPTIMIZATION UNDER STOCHASTIC EXECUTION DELAY
David Valensi
Esther Derman Technion
Technion
davidvale ensi campuus www.:sietttttttnneccc ac. i1
estheerddeman@ccmpuss hwt.://aeeeeceessetcceeo.ooooo..
Shie Mannor
Gal Dalal
Technion & Nvidia Research shielee. technion.
Nvidia Research
gdalal@nvidia com
ABSTRACT
The standard formulation Markov decision processes (MDPs) assumes that the agent's decisions executed immediately. However, in numerous realis- tic applications such as robotics or healthcare, actions are performed with a de- lay 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 or- der reach optimal performance, thus extending the deterministic fixed delay case. Armed with this insight, we devise DEZ, model- algorithm that optimizes over the class of Markov policies. DEZ leverages Monte-Carld tree search similar to its non-delayed variant EfficientZero to accurately infer future states from the action queue. Thus, it handles delayed execution while pre- serving the sample efficiency of EfficientZero. Through series of experiments on the Atari suite, we demonstrate that although the previous baseline outper- forms 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 https: ftttps://githu..comm com wtt.hhub.coo//aaaaaaaa/b.aa.....
EZ
INTRODUCTION
The conventional Markov decision process (MDP) framework commonly assumes that all of information necessary for the next decision step is available in real time: the agent's current state immediately observed, its chosen action instantly actuated, and the corresponding reward feed- back concurrently perceived (Puterman 2014). However, these input signals often delayed in real-world applications such as robotics (Mahmood et al. 2018), healthcare (Politi et al. 2022), or autonomous systems, where they can manifest in different ways. Perhaps the most prominent exam- ple where delay can be stochastic is in systems that rely on data transmission. Oftentimes, there is some interference in transmission that stems from internal or external sources. Internal sources may be due to temperature or pressure conditions that influence the sensing hardware, whereas external sources of interference occur when a policy infers actions remotely (e.g.. from a cloud). For ex- ample, an autonomous vehicle may experience delay from its perception module in recognizing the environment around This initial recognition delay is known as observation delay. Additional de- lays can occur when taking action according to previously made decision. This delay in response is termed execution delay. As highlighted in (Katsikopoulos & Engelbrecht 2003) and despite their distinct manifestations, both types of delay functionally equivalent and can be addressed using similar methodologies.
In addition to its existence, the delay's 's nature is often overlooked its nature. In complex systems, delays exhibit stochastic properties that add layers complexity to the decision decision-making process (Dulac-Arold al. 2019). This not only mirrors their unpredictability, but also warrants novel

---

Published as a conference paper at ICLR 2024
approach to reinforcement learning (RL) that does not rely state augmentation. This popular method consists of augmenting the last observed state with the sequence of actions that have been selected by the agent, but whose result has not yet been observed (Bertsekas) 2012 Altman & Nain, 1992 Katsikopoulos & Engelbrecht] 2003). Although it presents the advantage of recovering partial observability, this approach has two major limitations: (i) its computational complexity inevitably grows exponentially with the delay value (Derman et al., 2021); (ii) it structurally depends on that value, which prevents from generalizing introduced in (Bouteiller et al. 2020) to address random delays was practically tested on small delay values and/or small support.
random delays. In fact, the augmentation method
In this work, we tackle the following question: How does one effectively engage in an environment where action repercussions are subject to random delays? We introduce the paradigm of stochastic execution delay MDPs (SED-MDPs). We then establish significant finding: To address stochastic delays in RI,, it is sufficient to optimize within the set of Markov policies, which is exponentially smaller than that of history-dependent policies. Our result improves upon the one in (Derman al. 202T that tackled the narrower scope of deterministic delays.
Based on the observation above, we devise Delayed EfficientZero (DEZ). This model-based algo- rithm builds on the strengths of its predecessor, EfficientZero, by using Monte Carlo tree search to predict future actions (Ye et al. 202I). In practice, DEZ keeps track of past actions and their delays using two separate queues. It utilizes these queues to infer future states and make decisions accordingly. We also improve the way the algorithm stores and uses data from previous experi- ence, enhancing its overall accuracy. In essence, DEZ offers a streamlined approach to managing stochastic delays in decision-making. We accordingly modify the Atari suite incorporate both deterministic and stochastic delays, where the delay value follows a random walk. In both cases, our algorithm surpasses 'oblivious' EfficientZero that does not explicitly account for delay, and 'Delayed-'' from Derman et al. (202T).
In summary, our contributions are as follows.
1. We formulate the framework of MDPs with stochastic delay and address the principled approach of state augmentation.
2. We prove that if the realizations of the delay process are observed by the agent, then it suffices to restrict policy search to the of Markov policies to attain optimal performance.
3. We devise DEZ, model-based algorithm that builds upon the prominent EfficientZero. DEZ yields non-stationary Markov policies, as expected by our theoretical findings. It is agnostic to the delay distribution, so no assumption is made about the delay values them- selves. Our approach is adaptable and can be seamlessly integrated with any of the alterna- tive model-based algorithms.
4. We thoroughly test DEZ on the Atari suite under both deterministic and stochastic delay schemes. In both cases, our method achieves significantly higher reward than the original EfficientZeeoo and 'Delayed-Q" from Derman et al. (202T).
2 RELATED WORK
Although it is critical for efficient policy implementation, the notion of delayed execution remains scarce in the RL literature. One way address this is through state-space augmentation, which consists of concatenating all pending actions to the original state. This brute-force method presents the advantage of recovering the Markov property, but its computational cost increases exponentially with the delay value (Walsh et al. 2009 Derman et al. 2021)
Previous work that addressed random delay using state embedding includes Katsikopoulos En- gelbrecht (003);; Bouteiller et al.] (2020). The work Katsikopoulos & Engelbrecht (2003) simply augments the MDP with the maximal delay value to recover all missing information. In (Bouteiller et al. 2020), such augmented MDP is approximated by a neural network, and trajectories are sampled to compensate for the actual realizations of the delay process during training. The proposed method is tested on a maximal delay of 6 with high likelihood near 2. This questions the viability of their approach to (i) higher delay values; and (ii) delay distributions that are more evenly dis- tributed over the support. Differently, by assuming the delay process to be observable, our method
2

---

Published as a conference paper at ICLR 2024
augments the state space by one dimension only, regardless of the delay value. It also shows effi- ciency for delay values of up to 25, which we believe comes from the agnosticism of our network structure to the delay.
To avoid augmentation, Walsh et al. 2009) alternatively proposes inferring the most likely present state and deterministically transitioning to it. Their model-based simulation (MBS) algorithm quires the original transition kernel to be almost deterministic for tractability. Additionally, MBS proceeds offline and requires finite discretized state space, which raises the curse of dimen- sionality. (Derman et al. 202T) address the scalability issue through their Delayed DQN algorithm. which presents two main features: (i) In the same spirit as MBS, Delayed DQN learns forward model to estimate the state induced by the current action queue; (ii) This estimate is stored as next- state observation in the replay buffer, thus resulting in time shift for the Bellman update. Although (Walsh et al., 2009) Derman et al. 202T) avoid augmentation, these two works focus on a fixed and constant delay value, whereas DEZ allows it to be random. In related study, Karamzade et al. 2024) investigate method similar to ours, focusing continuous control tasks in the mujoco and DMC environments. Notably, they adopt our latent space imagination approach in their adaptation of Dreamer- V3 to manage delays.
DEZ leverages the promising results obtained from tree-search- based learning and planning algo- rithms (Schrittwieser et al., 2020; Ye et al.] 202T). Based on Monte Carlo tree search (MCTS), MuZero (Schrittwieser et al.) 2020) and EfficientZero (Ye et al. 2021) perform multi-step lookahead and in-depth exploration of pertinent states. This is performed alongside latent space representations to effectively reduce the state dimensions. MuZero employs MCTS as a policy improvement oper- ator by simulating multiple hypothetical trajectories within the latent space of a world model. On the other hand, EfficientZero builds upon MuZero's foundation by introducing several enhance- ments. These enhancements include a self-supervised consistency loss, the ability to predict re- turns over short horizons in a single step, and the capacity to rectify off off-policy trajectories using its world model. Yet, none of these methods account for the delayed execution of prescribed deci- sions, whereas DEZ takes advantage of the world model to infer future states and accordingly adapt decision-makinn
3 PRELIMINARIES
A discounted infinite-horizon MDP is a tuple (S.A, P.r,,,,,, where S, A are finite state and action spaces, respectively. P is a transition kernel P : S - As that maps each state-action pair to a distribution over the state space, r S x A + IR is reward function, E As an initial state distribution, and y E [0, 1) a discount factor that diminishes the weight of long-term rewards.
At each decision step t, agent observes state 5t, draws an action âe that generates reward r(5r, āe), then progresses to 5t+1 according to P(. ā.). The action āe follows some prescribed decision rule ny which itself has different possible properties. More precisely, decision rule can be Markovian (M) or history-dependent (H) depending on whether it takes the current state or the entire history input. It can be randomized (R) deterministic (D) depending on whether its output distribution supports multiple or single action. This yields four possible classes of decision rules: HR, MR, HD, MD. A policy classes of policies are denoted by IR 1I ID MD and determined by their decision rules. When म. = To, Vt e N. the resulting policy is said to be stationary. We simply denote by II the set of stationary policies.
(Tt) is sequence of decision rules. The different
The value function under given policy E I is defined as
" (s) = T Σ (r(,,,
where the expectation is taken with respect to the process distribution induced by the policy. Ulti- mately, our objective is to find x² E arg ma (s) =: (s), Vs E S. It is well-known that optimal stationary deterministic policy exists in this standard MDP setting (Puterman 2014).
3

---

Published as a conference paper at ICLR 2024
Duplicated
Discard action
Expocted Peoding Actions
0
1
2
3
4
5
7
8
9
10
(8: 1.)
00
01
0/
03
04
0g
2,
5
5
4
5
3
4
Efftetive decision timos [fp.o Feezy)
2
At
Expected pending action queue
Gg
Q2
G4
Q4
decieon times Teeny
2
4
4
5
5
Expected pending action
02
04
04
0g
45
Figure I: Pending queue resolution in a SED-MDP. The policy input 8t+2, corresponds to the state inferred by forward model (see Section 5). For clarity, effective decision times are shown for t t {5, 6} only.
STOCHASTIC EXECUTION-DELAR MDP
In this section, we introduce stochastic execution-delas MDPs (SED-MDPs), which formalize stochastic delays and MDP dynamics
distinet processes. We adopt the ED-MDP formu- lation of (Derman et al. 2021) that sidesteps state augmentation and extend it to the random delay case. With this perspective, we proceed in steps: (1) we define the SED-MDP framework with suitable probability space: (2) we introduce the concept of effective decision time; (3) we prove the sufficiency of Markov policies achieve optimal return SED-MDP.
A SED-MDP is a tuple (S, P. 7, S. ā) such that (S, A, 7) is an infinite-horizon MDP and Ç [IM] distribution over possible delay values, where [M] := {0, 1, 1. .M. The last element à E A models default queue of actions to be used in case of null assignment At each step delay value ž, is generated according Ç; the agent observes Σ and state 5c. prescribes an action ā, receives reward r(ā,, āz) and transits to $1+1 according to P(- āz). Unlike the constant delay case, the action ā, executed at time t sampled according to policy that had been prescribed at previous random time. This requires us to introduce the notion of effective decision time, which we shall describe Section 4.1
For any E IHHR the underlying probability space is Ω (S x [[M] x A) which we assume equipped with d-algebra and a probability measure pa Its elements are of the form
(so, 20, do, 21, ......). ). For all & N, let the random variables 3, Ω S, & Ω + [M] and ā. Ω - be respectively given by (w) 8t, ār(w) = 2, and (w)) = a, Clearly, = (ā, ee and = (že)eN are dependent, the distribution of à, depends on past realizations of 2., for all N. On the other hand, in this framework, the delay process is independent of the MDP dynamics while it is observed in real-time by the agent. The latter assumption is justified in applications such as communication networks, where delay can be effectively managed and controlled through adjustments in transmission power. We finally define the random variables of the history (he)ee according to (w)) = (so. 20) and (w) (So. 20, ao. St, 2t),,, Vt 1.
4.1 EFFECTIVE DECISION TIME
To deal with random delays, we follow (Bouteiller et al. 2020 and assume that the SED-MDP actuates the most recent action that is available at that step. This implies that previously decided
One may use sequence of M distributions instead of deterministically preserihed actions, but we restrict actions for notation brevity.
4

---

Published as a conference paper at ICLR 2024
actions be overwritten or duplicated. Fig. showw the queue dynamics resulting from successive realizations of the delay process. Concretely, at each step t, the delayed environment stores two distinct queues: one queue of M past actions (a--Mr Mr az- 1e-M- ,0-11 and one queue of M past execution delays (Zt- M, 2t +1, 2t-1). Then, we define the effective decision time at as:
Ti = max (t' 20 St..
(e(l-MM:1]
It is a stopping time in the sense that 7i is (h2) meassurabl. Notably, it also determines the distri- bution that generated each executed action: given a policy π = =Tx) (2)0 for any step t, the action at time t is generated through the decision rule d, n Intuitively, answers the question "What the most recent action available for execution, given past and current delays"? Alternatively, we may define e t 24 as the earliest execution time resulting from decision taken at time t.
Example. Let M = and assume that the following table gives the first realizations decision rules and delays:
t
0
2
4
Zt
5
4
Cx
5
a2
00
01
02
03
04
As result, the effective decision time at t 5 is given by T3 1. (a,>0) + (s6=0)) From the agent's perspective, the pending queue at time = 5 depends on the delay value 25:
If 25 then the pending queue is (a1, 022 04, 04; a4].
If 25 4, then the pending queue is [a1, 022 a,, an).
*
If 3, then the pending queue is (a1, 022 04).
If 25 2, then the pending queue is (a1, 02].
If 25 = 1, then the pending queue is [a1].
If 25 0, then the pending queue is
4.2 SED-MDP PROCESS DISTRIBUTION
We now study the process distribution generated from any policy, which will lead us to establish the sufficiency of Markov policies for optimality. To begin with, the earliest time at which some action preseribed by the agent's policy is executed corresponds min 20, 21 +1, 1,..., M 1 2M-1) } or equivalently, to (en, c1,..,, 4M-1) From there on, the SED-MDP performs switch and uses the agent policy instead of the fixed default queue. Denoting l == min 20. + 1 1,..., M +
zM -. for any policy π E IR we have:
pa (ār aah, (h4-1. 01),
(1),(a)
ift min + 1, ..... 24 t). Tr. (a) otherwise.
We formulate the probability of sampled trajectory in the following theorem. A proof is given Appendix A.I
Theorem 4.1. For any policy π. = (Tt)SE E HR the probability of observing history h; =
(so, 20, 4n. ar-1, (k-1,,t: St, 2t) is given by:
PP (50 80. 2g = 20, āg = 4o, ".. ūt-1 = 04-1,8 = 8t, -1, =2)
=(u(s))
II La, (ax) P(ssHll) a1) O=
II Jm
क (hi)
II m==
((Em)
Extending the result of DDerman et al. from any history-dependent policy can equivalently generated from a Markov policy. The proof given in Appendix A.2
202 establish that the process distribution generated
5

---

Published as a conference paper at ICLR 2024
II be history-dependent policy. For all so S, there exists a Markov policy it E IIMR that yields the same process distribution as T, i.e, pa (ST, = =s' 0g = a0 = 8p, 2 = = ( =8, = al80 = 80, 2 = 2), for all a E A, s E S,t 2 0, and 2 (2 the whole delay process.
Theorem 4.2. Let
We can now devise policy training in the smaller class MR without impairing the agent's return. The algorithm we propose next does exactly this.
5 STOCHASTIC-DELL EFFICIENTZERO
We introduce novel algorithm designed address the challenges posed by stochastic execution delay. Drawing inspiration from the recent achievements of EfficientZero on the Atari 100k bench- mark (Ye al. 202T),
its architectural framework infer future states with high accuracy. Its notable sample efficiency enables us to quickly train the forward model. We note that recent ad- vancements in model-based approaches extend beyond lookahead search methods such MuZero and EfficientZero. Depending on the task at hand, alternatives such as IRIS (Micheli et al. 2022), SimPLE (Kaiser et al., 2019), or DreamerV3 (Hafner al., 2023) exhibit distinct characteristics that can also be considered. Our approach is adaptable and can be seamlessly integrated with any of these algorithms.
Algorithm description. DEZ is depicted in Fig. It adapts EfficientZero (Ye et al. 2021] to act and learn in environments with stochastic delays. At any time t, we maintain two queues of length M. One is the ac- tion queue of previous realizations M [a-M,...,, a-11. The second is the delay value queue observed for these ob-
Figure 2: Interaction diagram between DEZ and the delayed environment
Tree-search Policy
M actions, [z M,..... :M..-..2-----. 2-1-- During inference, serve state 8t and delay Zt, and aim to estimate the future state St+s, To do so. we take the expected pending actions denoted by [āz...., a1+ and suc- cessively apply the learned forward model: $1+1
Qt
85+21
(st, â....... S1t2, = G( a1), using nota- tions from Ye et al. (202T). Finally, we perform an MCTS search to output = Te (8t+2) and add ur, 2t to the re- spective queues.
the other hand, the action executed in the delayed environment is a,,, Since future action can overwrite the first expected action â, we note that a,, â,. The reward of the system is then stored form a transition (St, Tt,,?t). Tt).
Delayed env
Forward model
Pending actions resolution. Fig. depicts the action and delay queues, together with the relation between effective decision times and pending actions. At each time step, the actual pending actions are calculated using the effective decision times from Eq. (I)
Future state prediction. To make accurate state predictions, we embrace the state representation network s (o,) and the dynamics network 6t+1 G(s,, a,) from EfficientZero (Ye et al., 2021). For simplicity, we do not distinguish between observation and state representation as do Ye al. (202I). However, all parts of the network-ffrree in the latent space. Moreover, the replay buffer contains transition samples with states 8t, 8 in the same space. The pseudo-code in Algo. depicts how self-play samples episodes the stochastic delayed environment.
dynamics, value, and
Corrections in the replay buffer. (st, Tt) are stored in the game histories that contain state, action, and reward per step. However, to insert the right transitions into the replay buffer, we proteps the game histories using all execution delays {2 of the episode of length L, enabling to compute effective decision times and store (st, ar, rr) instead. More details about the episode processing can found in Appx. B
the original version of EfficientZero, episode transitions

---

Published as a conference paper at ICLR 2024
Learning a policy in delayed environment. Action selection is carried out using the same MCTS approach as in EfficientZero. The output of this search denoted by (5t+2a,) also serves as the policy target in the loss function. The primary alteration occurs in the policy loss, which takes the form:
cp (( (e
where is the policy network at time Although the MCTS input relies on a predicted version of S142, this loss remains justified due to the exceptional precision exhibited by the dynamics model within the latent space. Other loss components remain unchanged.
EXPERIMENTS
The comprehensive framework that we construct around EfficientZZero accommodates both constant and stochastic execution delays. We consider the delay values (5, 15, 25} to be either the constant value of delay its maximal value when dealing with stochastic delays, in (Derman et al. 2021]. For both constant and stochastic delays, we refrain from random initialization of the initial model determines the first M actions. This is achieved through the iterative application of the forward and the policy networks. In practice, the agent observes the initial state so, infers the policy through ün and predicts the subsequent state 81 G( ao). similarly infers 8 8M and selects actions ū2,...,, 4M-1 through this iterative process.
action queue in (Derman al. (021). Instead,
Efficien(Zero sampled 100K transitions, aligning with the Atari 100K benchmark. Although our approach significantly benefits from Efficien(Zero's sample efficiency, the presence of delay adds complexity to the learning process, requiring mildly more interactions 130K in our case. Success- fully tackling delays with such limited data is non-trivial task.
RoadRunner
RoadRunner
Qhert
Qhert
Hero
Hero
Asterix
Asterix
Name I
hame Game
Name histiame Game
TinePilot
TimePilot
Gopher
Gopher
StarGunner
StarGonner
WizardO/Wor
WizanOO/Wor
MsPacman
MsPacman
Assault
Assault
Alien
Alien
BankHeiis
BankHeist
Amidar
Amidar
(Ours)
(Ours)
Boxing
Oblivions-FF EZ
Boxing
Oblivions-EZ
Delayed DQN
Delayed DQN
500
2000
100000 25000
200 500
2000
10000 25000
Seores
Scares
(a)
(b)
Figure 3: Average score on 15 Atari games and delays M E (5, 15, 25} over 32 test episodes per trained seed. Delays appear from low to high values for each game. (a) Constant delay value; (b) Stochastic delay value within .0...... M).
To evaluate our theoretical findings, we subject DEZ to testing across 15 Atari games, each under both constant and stochastic delays. In either case, the delay value is revealed to the agent. We stress

---

Published as a conference paper at ICLR 2024
that the baseline scores consistent for the two types of delays that simulate. Indeed, constant delays, Delayed-Q (Derman et al. 202I) tends to achieve higher scores than the oblivious version of EfficientZero, while Delayed-Q sufters more from stochastic delays than EfficientZero. As explained next, DEZ consistently achieves higher scores on both types of delays. full summary of scores and standard deviations for algorithm and baseline methods is presented in Appx. C.4
Tabs. D aadd2 2
6.1 CONSTANT DELAYS
We first analyze the scores produced by DEZ for constant delays and refer Appx. C.1 for the convergence plots of all games tested.
Figure B[a) shows that method achieves the best average score in 39 of the 45 experiments. The oblivious version of EfficientZero confirms previously established theoretical findings (Derman al. 2021, Prop. 5.2): stationary policies alone are insufficient to achieve the optimal value. Given that Oblivious EfficientZero lacks adaptability and exclusively generates stationary policies, it is not surprising that struggles to learn effectively in most games.
Our second baseline reference is Delayed-Q (Derman et al., 2021). recognized as tate-of-the-ar algorithm for addressing constant delays Atari games. However, it should he noted that Delayed- Q is a -QN-based algorithm, and its original implementation entailed training with one million samples. Our observations reveal that within the constraints of the allotted number of samples, Delayed-Q struggles to achieve efficient learning. On the other hand, Delayed-Q benefits from its perfect forward model, provided by the environment itself. observe that in 21 out of 45 experiments, Delayed-Q Q achieves an average score that is at least 85% of our method's 's result, even from the initial training iterations.
Importance of the forward model. Despite the dependence of Delayed-Q the Atari envi- ronment as its forward model, this baseline exhibits significant vulnerabilities when faced with limited data. To address this challenge, ficientZero, allowing us to acquire state representations and dynamics through the utilization of its self-supervised rich reward signal, among other features. Our findings illustrate that when we ef- fectively learn a precise prediction model, delays become more manageable. However, it is worth noting that increased randomness in the environment can result in larger compounding errors in subsequent forward models.
hamesss the representation learning capabilities of Ef-
6.2 STOCHASTIC DELAYS
For a more realistic scenario, we also our method on stochastic delays. For each Atari game, we use three stochas- tic delay settings. For each value M E (5, 15, 25), we use the following formulation of the delay 2, at time t:
20
M
min(2 24 + M)
with probability 0.2, with probability 0.2,
Delay
2t>0
max 1,0)
otherwise.
Note that the delay is never reinitialized to M when the episode terminates. Instead, the delays remain the same for the beginning of the next episode. By doing that, we do not assume an initial delay value and cover broader range of ap- plications.
811
122
Episodes
Figure 4: Random walk behav- ior of the stochastic delay across multiple episodes. No initial de- lay value is set at the start of the episode. Here, the maximal delay is 15.
We opt to avoid the augmentation approach in the baselines due to its inherent complexity. Incorporating the pending ac- tion queue into the state space was deemed infeasible due to its exponential growth, even in simple environments such as Maze (Derman et al. 2021). In our scenario, the length of the pending queue ranges from to M in cases involving stochastic de- lays. Consequently, the size the augmented state space becomes |S] x AM As the value of M increases, the order of magnitude of this quantity becomes overwhelming.
8

---

Published as a conference paper at ICLR 2024
We report the average scores of DEZ and baselines for 15 Atari games in Figure b)), and refer to Appx. C.2 for the convergence plots. Similarly to the constant case, we observe an impressive achievement, even slightly better, highlighting the added resilience of our method to stochastic de- lays. In 42 of 45 experiments, our method prevails with the highest average score. DEZ is also trained incorporate very large delay values for evaluation in extreme scenarios. The performance in such cases is predominantly influenced by the specific characteristies of the environment. For example, in Asterix, we observe that DEZ struggles learn efficiently with delays of M 35 and M = 45. Contrarily, in Hero, our algorithm demonstrates comparable learning performance even with the largest delay value.
DISCUSSION
In this work, we formalized stochastic execution delay in MDPs without resorting to state augmen- tation. Although its analysis is more engaged, this setting leads to an intriguing insight: as in the constant delay case, we can restrict the policy search to the class of Markov policies and still reach optimal performance in the stochastic delay case. We introduced DFZ, a model-based approach that achieves state-of-the-art performance for delayed environments, thanks to an accurately learned world model. A natural extension of our approach would consider predicting the next state distribu- tion instead of point prediction $142 to train a more robust world model and mitigate uncertainty in more stochastic environments.
DEZ heavily relies on a learned world model to infer future states. Devising a model-free method that addresses delayed execution while avoiding embedding remains open question. DEZ also assumes delay values are observed in real-time, which enabled us to backpropagate the forward model the corresponding number of times. Ridding of this constraint would add another layer of difficulty because the decision time that generated each action would be ignored. For deterministic execution delay, we may estimate its value. For stochastic delays, we could adopt robust approach to roll out multiple realizations of delays and act according to a worst-case criterion.
Useful improvements may also be made to support continuous delays and remove drop and dupli- cation of actions. In such a case, we may plan and derive continuous actions. Another modeling assumption that we made was that the delay process independent of the MDP environment. Al- ternatively, one may study dependent delay processes, e.g., delay values that depend on the agent's s current state or decision rule. Such extension is particularly meaningful in autonomous driving where the agent state must be interpreted from pictures of various information complexities.
REPRODUCIBILITY
To further advance the cause of reproducibility in the field of Reinforcement Learning (RL), we are committed to transparency and rigor throughout our research process. We outline the steps taken to facilitate reproducibility: (1) Detailed Methodology: Our commitment transparency begins with description of our methodology. We provide clear explanations of the experimental setup, algorith- mie choices, and concepts introduced ensure that fellow researchers can replicate our work. (2) Formal proofs are presented in the appendix. (3) Open implementation: To encourage exploration and research on delay-related challenges in RL, we include the code as part of the supplementary material. We include a README file with instructions on how to run both training and evaluation. Our repository is a fork of EfficientZero (Ye et al., 2021) with the default parameters taken from the original paper. (4) Acknowledging Distributed Complexity: It is important to note that, while we strive for reproducibility, the inherent complexity of distributed architectures, such as EfficientZero, presents certain challenges. Controlling the order of execution through code can be intricate, and we acknowledge that achieving exact-result replication in these systems may pose difficulties. In sum- mary, our dedication to reproducibility is manifested through transparent methodologies, rigorous formal proofs, and an openly accessible implementation. Although we recognize the complexities of distributed systems, believe that our contributions provide valuable insight into delay-related issues in RL, inviting further collaboration within the research community.

---

Published as a conference paper at ICLR 2024
REFERENCES
Eitan Altman and Philippe Nain. Closed-loop control with delayed information. ACM sigmetrics performance evaluation review, 20,,),193-204, 1992.
Dimitri Bertsekas. Dynamic programming and optimal control: Volume I, volume 4, Athena scien- tific, 2012.
Yann Bouteiller, Simon Ramstedt, Giovanni Beltrame, Christopher Pal, and Jonathan Binas. Rein- forcement learning with random delays. In International conference on learning representations, 2020.
Esther Derman, Gal Dalal, and Shie Mannor, Acting in delayed environments with non-stationary markov policies. January 2021.
Gabriel Dulac-Amold, Daniel Mankowitz, and Todd Hester. Challenges of real-world reinforcemnnt learning. arXiv preprint arXiv: 12901, 2019.
Danijar Hafner, Jurgis Pasukonis, Jimmy Ba, and Timothy Lillicrap. Mastering diverse domains through world models. arXiv preprint arXiv:2301.041 2023.
Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blazej Osinski, Roy H Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, et al. Model-based reinforcement learning for atari. arXiv preprint arXiv: 003774 2019.
Armin Karamzade, Kyungmin Kim, Montek Kalsi, and Roy Fox. Reinforcement learning from delayed observations via world models. arXiv preprint arXiv:2403. 12309, 2024.
Konstantinos V Katsikopoulos and Sascha E Engelbrecht. Markov decision processes with delays and asynchronous cost collection. IEEE transactions on automatic control, 48(4):568-57) 2003.
A Rupam Mahmood, Dmytro Korenkevych, Brent J Komer, and James Bergstra. Setting up reinforcement learning task with a real-world robot. In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 4635 46400 IEEE, 2018.
Vincent Micheli, Eloi Alonso, and François Fleuret. Transformers are sample efficient world models. arXiv preprint arXiv:2209.005: 2022.
Ruth E Politi, Peter D Mills, Lisa Zubkoff, and Julia Neily. Delays in diagnosis, treatment, and surgery: Root causes, actions taken, and recommendations for healtheare improvement. Journal of Patient Safery, 187))e1061-e1166, 2022.
Martin L Puterman. Markov Decision Processes.: Discrete Stochastic Dynamic Programming. John Wiley Sons, 2014.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):604-699 2020.
Thomas J Walsh, Ali Nouri, Lihong Li, and Michael L Littman. Learning and planning in environ- ments with delayed feedback. Autonomouy Agents and Multi-Agent Systems, 18:83-105, 2009.
Weirui Ye, Shaohuai Liu, Thanard Kurutach, Pieter Abbeel, and Yang Gao. Mastering atari games with limited data. October 2021.
10

---

Published as a conference paper at ICLR 2024
APPENDIX
A A FORMULATION FOR STOCHASTIC DELAYS
A.1 PROOF OF THEOREM 4.1
Proof.
By definition of conditional probability, for all measurable sets -,, An E B()), we
have
PPT (A,l -z= A1) 1ett (An).
1p (N=
II
(3)
Applying Eq. 13 to n 21 + 1 on the following events:
A241 = {50 = {o}
A2 {20 20; 0g- aa)
A2 = [21-1 = =2 at-1 = a.-1)
A {5, =
Ag = {2 = =+
we obtain that
1at (50 -00 20 = z0, āg = 00, ... -0-11=1 = Qr-1, 8. = St, Es = 21)
p=5 = 80) II
pa (ž: 24, ā: 0:150
80, 2g = 20, 0g ag. ;8 8:)
t=0
Pd (3141 s 500 So, Zu = 20, āg 00
,4 = =2; 0: a.)
(& 24 [u
Sg. E0
2p, āy Cp. 2
1
at a.-1, 8t s:)
2 1 (50 so)
1ot (ž; = Zs 0. a.
50
50, 20
20, 0o = ao. ... 88 = st)
Pd (8141 8
10
80, 2g
20, āo ag.
,
2, 0
a. i (a+ 2t)
1-1
= (50 = so)
P (3 = 2, ā. 0.150 = so, 20 = 20, do ag. ... ,5 8t)
(=0
1dT (Bi+1 8 hh
(h; 1, 8;), = a:) pr
Tr (E+ = z+)
P 8o)
II
1st (2
24 a. 0.150 so, uo 20, وo ag.
,6, ((5tt)st
1-1
(50 so)
II
.st (ā; aith: h:))p (ā: 2u/50 so, 30 z0, مo ...
...,, ......
P(s
1-1
(30 = 3o)
II
1st (ā. = ahe =
k=0
=1(30)
II k=
La (ax) 1 ak)
II
क.. ((s4 ((2r)
1=tz

---

Published as a conference paper at ICLR 2024
where equality (1) comes from the fact that the delay distribution at 2 is independent of the state 8i+1 observed then. By Eq. (2)
nn (50- = so, 20 = 20, āg = ao,
d = ac-1, Stz 2s = 2t)
= (50 = 80)
II ((2))
2i), = ai) (ā; = as 10 = hss I ( ($i+1 = 81+1 = (h3-1, as- 11,
1=0
pa
(āx ax/hx = )P= (5a+1 = skt1l/x = 1, 8h, =k); 0z as)
k=
= =((s))
II
La ((
II l-t.
h-1
T.
i ((zm)
m==
where the first product is empty if and only if = 0. i.e. the decision taken time / 0 is immediately executed.
A.2 PROOF OF THEOREM 4.2
We first establish the following lemma, which will be used in the theorem's proof.
Lemma A.1. For all t and 2, 0,
pa 8 0r a', 8 8, a PT 8/)8:-1 8, 0, =a)
(4)
Proof. Since 2t 0 by assumption, the state variable šn is independent of āe, so that: (P; s' a. = a', 8 = 0t-1 a) P(s'ls, = Tp (3t s (8t-1 dz = a).
Theorem. Let π E II be a history dependent policy. For all so S, there exists a Markov policy n' MR that yields the same process distribution n,, i.e.
pr (k.. = 8, āg = aa80 = 80, 2 = = =P= (Br, = 8 āt = also 80, 2 = 2),
(5)
for all a E A, s' S.t 0, and 2 == (E)ee the whole delay process.
Proof. If M = 0, the result holds true by standard RL theory (Puterman 2014 5.5. Assume now that M 0, fix S and (z))EN- The variable exogenous, and shall consider the corresponding sequence of effective decision times (π.)EN- We construct Markov policy x' for these times only while for other times, T' can be anything else. Let thus T' )EEN with T {s} + Aa defined as
(s') = (it = al87, = 8,,80 =, =,8== == ifL2 AA S,EEA (a) otherwise,
(6)
Recall the definition of the time the SED-MDP performs switch and uses the agent's policy min 20, 21 +l..... M.....MM M-1+ 2M-1]- }. For the policy x' defined in Eq. (6), we prove the theorem by induction on t 2 t,, since for t 1z, the decision rule being applied is Ia, regardless of the policy.
For / = 12, by Thm. 4.1 we have:
P. (3.r. 8', 0t. = a, 50 = so)
TsT ('T = =s',0 0z. = alšu = su)
p7 (30 =so)
Σ
Pst (T( = =8,ū0 ar, a, a, at, -.. 0g = 0g. 80 = 80)
Pot (50 = 80)
-r.-1
Σ
II
la P(ses123)))))
81. 88g k=0
80. .i1g
12

---

Published as a conference paper at ICLR 2024
We observe that the expression does not depend on the preseribed policy, so it equals IPT (SrL. 8', ft. a 100 8o) and the induction base holds.
Assume that Eq. (5) holds up until n 1, with 2 1.2 Let denote t' n. we aim to prove that
IPA (5p = 5'150 = s) pa (5e = 5'150- = s).
(7)
Then, we can write
F 5v
5'150 = s)
Σ ("( 8', St St, â, 00|50 8)
a,EA
Σ
ps (5 āg = ue. 8t = st, 80 s)
RES,,
a.EA
Ps (ā: at [3t $1, 80 5) (5+ s2 = s)
P(s' st. PP (āz = a, |3 = $t, 3g = s)P (3: = -1 =s.
&EE.
G,EA
By Eq. 2 ae only depends state-action sequences up to T, Let's differentiate the value of
2 = 0, then T. = and by construction of I' we can write:
(ā+ = ae a0 = Se, 80 = 8) = PP (āe = a1/37. = S2, 80 = 5) = =p= (āt = a.137. = =8t, 80 = 8).
=s)=
(3x 5'050 5) Σ
P(s'(si, (āt ar15.. sc, 50 8)IP (5t st s5|50 s).
S,ES. a.EA
If 21 > 0, then Tr < and we can write: pxt (ā: 0r|8e. = St, 80 8) 1p (pr((rr
az 30 8)
1Tr(3p s'1su s) Σ
a 130 5)
(ăt
sy 50 s).
R.ESS
Ge EA
Since f 1. by the induction hypothesis we can rewrite
P" (āt = az 380 = 8) = Σ
Tptt (ā: = at, 8r. = =87,150 = 8)
ES
Ipr (āt at, 8r, 87, 150 8)
9,,
p
(āg- = a. 130 = 5)
1a (5t 5'130 = 3) Σ
P(s St, a. )I (ā, aj 150 =S)P (3. st s s).
S A.EAA
13

---

Published as a conference paper at ICLR 2024
In the two cases, now study the last term in the above equations, Pa; selāu). We have
P" (& 81/00 s)
Σ
(3 81, 84-1,
_8c, Se, 0s, ooz 180
4-11"rit EB EA
Σ
(² = 8e-1 8t-1, 1e-1 ae-1.".. ,8g = deg deg = deg 80 =))
41 1.0det 68
(8t-1 81-1, 01-1. ,8, = 5 0r, as 180
Σ
(T 81-1, ".- = =))
Σ
P(s)(t--11((11)
4-1""0t dt
"t-1"":;",E EA
p (8t-1 8t-1 lit-- 11-1 81-2, 01-2 0z-2. ,8, = 50,, = as. =)
[a di 1,3 81-2: 2:22; a1-2: 24-2:111-0 ,512 S1g 01g 180
lemn
P(ecloi i 1)P(ec a/s1 2: 2)
68 9t-11" 1l4
(at-1 14-1, -
24-2, ae-2: St. Sts. Reg aes s)
Σ
P(ai|si 1.01 P)P(e 1/8: 2,01 2)
pd (ū--1 01-1 1/221112222 8t-2: ut-2
St, 8eg des 0z 180 =
pa (5t 2 81 2, at St. Si2 Si.
01. 150
E
II P(o-)
4t-1 ft
"c 10m PE
II 121
pT P* at
1a ("r, = t1, las at.. 5) (ās, = as =0, =s)
Σ
II Plec-
B" (ā._; =n-;ldr- = era_s)
1-11" cs at- 4-11" 19 EA
1a ( = =8, Jās, 50 8)P" (Bs, = 180 s)
We continue and write
I-ix
1-1x-1
Σ
II P(4-
II
anl (cr (ore-)) (ac-s)
"t- Pe is at-jinm dey EA
pd (5r, m mty āe. = 50 s)F² (āz, = ar, 10 m
(3)
Σ
P( 10 II 100
II j-1
qn
(1eea)) ( (acc-s)
28
EA
(8,,, = dey des Otg, =) Σ
Rdia, ceres s(atz)
Es
14

---

Published as a conference paper at ICLR 2024
In (2) and (3) used equation not policy dependant:
We now analyze the last term implying and show that it is
pd [ = 81, lāc, or.
(8t, $1_lã0 s) 18o -e,-1, Ae,-1
Σ
(5t,
$1, 01 a1, 0o 50
1 dies
Σ
(re, eegi 8eg-11 Beg -1 81, 02,00 do no. do
(*o =
2i e16s
Oig Ane
1--1
(4)
Σ
u(+)
II (()
Σ
I 1
u(a)
S6x I1 - REEA
where (4) results from Th.
4.1
Thus, if decompose pa (se 800 8) according to the exact same derivation did for pa (3y = s'180 = 8), we obtain that at 1'' = n.:
PT (5v s su s) p (5v s/150 =).
(8)
As preceding step in the induction process, this results holds at Tv S t'
I (3 = 5' = s) = Fm (5 = s'130 = s).
(9)
As result, at 6' = we have
pp' (3rp s', āe al50 = 8)=Pr (ār alBT, = =6,550 = 8)1 (हTo = s 150 = 8)
(a) pr' (ār alšry s 50 3)P²T (5m, 5000
pr (āe al =| s 80 8)IPT 1BT, 80 = s)
Ps (δ., s', ăe also 8).
where (a) follows from Eq. (b) by construction of 7 (s))() in Eq. 6 Finally, assuming it is satisfied at = n 1, the induction step is proved for / = n, which ends The proof.
15

---

Published as a conference paper at ICLR 2024
B ALGORITHM
We briefty describe the EfficientZero algorithm from Ye et al. 2021) and highlight the places where novelties are introduced in DEZ. EfficientZero, there are several actors running in parallel:
The Self-play actor fetches the current networks of the model (representation, dynamics, value, policy prediction and reward networks: H. G, V, P, R). It samples episodes accord- ing to these networks, following the algorithm Although the algorithm relies episode sampling, the differences from the original version of EfficientZero, Ye et al. (2021) reside also in the episode post processing. After generating the trajectory, each episode is edited, associating each state 8, with the executed action at time / rather than the decided action at that time. This modification ensures that the replay buffer contains episode that is effec- tively free of delays, allowing the utilization of existing learning procedures for effective learning. In addition, for the learner's sake, the self-play actors store statisties and outputs of the consecutive MCTS searches to the replay buffer.
The CPU rollout workers (Ye et al. (202)) are responsible for preparing the batch contexts (selecting indexes of trajectories, and defining boundaries of valid episodes).
GPU batch workers (Ye et al. 2021) effectively place batches on the GPUs and trigger the
learner with an available batch signal.
The Learner itself updates weights of the different networks using the several costs func- tions: the innovative similarity cost (for efficient dynamics learning), the reward cost, the policy cost, and the value cost.
As previously highlighted, actor and the testing procedure. our approach does not necessitate changes to the architecture. It is adaptable and can be integrated into any model-based algorithm.
important note that, aside from modifications to the Self-Play
Technically, the challenges were to incorporate the parallel forward of the four environments for effectiveness; plan for the initial action queue based on the initial observation as described in S and to manipulate episodes according to the delay values in complex structure of obser- vations, actions, reward, and statisties of MCTS searches.
16

---

Published as a conference paper at ICLR 2024
Algorithm DEZ: acting in environments with stochastic delays. PQR stands for Pending Queue
Resolver (see Fig. I
while < STEPS do
H, V, < Ho, Go, Vo. Pa, R.o
Sample new episode (80; 20, 40.
ST, 2T, aT)
Initialize queues:
Default action queue: Ja- M a- a. Delay queue: M.. 2-1] , M].
t ++0
while episode not terminated do
Observe $t, 2t
Query from the delayed environment the estimated pending queue:
a1+2,-1 (ūt,...,(+2.-- 8e+1 g(st,ar)
PQR (0R(a-M.... M.,.......... 1t-1, zt- -t 1)
8r+2, gg -1, -1)
W (CTS($(+2.)
Te
Shift the action and delay queues and insert az and 2t-
t <- 1++1
end while
Post process the episode (so, 20, do. ......... ST, 27, aT) and compute effective decision times
Tos
TT Add (su, Tu, ao ........p.. Sy; Tr, ar) the Replay Buffer.
72 4 n +
end while
C EXPERIMENTS
C.I CONVERGENCE PLOTS FOR CONSTANT DELAY
Figure gives the learning curves of DEZ together with the baselines for constant delay.
17

---

Published as a conference paper at ICLR 2024
200d
Figure 5: Convergence plots for 15 Atari games on constant delays in (5, 15, 25}.
C.2 CONVERGENCE PLOTS FOR STOCHASTIC DELAY
Figure giiee the learning curves of DEZ together with the baselines for stochastic delay.
18

---

Published as a conference paper at ICLR 2024
Figure 6: Convergence plots for 15 Atari games on stochastic delays with maximal delay M e
(5. 15, 25) and probability 0.2.
C.3 DEZ ON LARGE DELAYS
Here, we add results for very large delays in Asterix and Hero Atari games. As expected, the scores decrease the delay increases, due the complexity and emor in planning.
19

---

Published as a conference paper at ICLR 2024
Scores on two Atari games: Comparison with longer delays
Asterix
Hero
10000
M=5
M=15
1OCO0
M=25
0000
Scores
19000
M=35
0000
M=45
5000
2000
2000
Steps
Steps
Figure 7: Scores on two Atari games with stochastic delays up to M 45. Left: Asterix. Right: Hero.
C.4 SUMMARY OF SCORES ON ATARI GAMES
We summarize the scores and standard deviations obtained for DEZ (ours) and baselines Oblivious EfficientZero of (Ye et al., 2021) and Delayed DQN of (Derman et al. 2021 on 15 Atari games. The following table shows scores on constant delays.
m = 5
m 15
= 25
Game
Obl. EZ
Delayed
Delayed EZ.
Obl. EZ
Delayed DQN
Delayed EZ
Obl. EZ
Delayed DQN
Delayed EZ
DQN
Alien
335.5
484.33
993.25
287.86
421.33
512.0
278.8
454.0
497.25
=24.88
473.67
1:311.5
1:30.57
+58.0
+109.75
4:29.0
1220.
115..75
Amidar
50.8 ::5.2
64.0 120.0
111.8
12.43
61.67
72.0 118.2
3.2 11.41.4
115.5
#:5.2
116.4
+2286
+-22.0
Assault
234.5
369.0
1056.5
208.6
371.0
674.75
179.75
389.5
636.6
=21.25
+91.0
+281.25
+33.2
193.67
#59.75
+20.0
107.5
+
Asterix
348.43
486.25
10758.2
244.4
304.75
1160.71
186.4
248.33
673.4
556.43
+242.75
+5809.0
125.4
16000
+447.86
115.4
#136.33
#314.8
BankHeist
13.25
17.0 +13.5
180.2
11.4 +222
13.67
35.6 117.4
12.5 +3.0
14.17
29.4
+14.6
=4.25
133.2
#12.67
=10.83
Boxing
4.5 #1.25
2.33 +9.33
2.0 +4.75
-5.2 +1.8
1.5 +5.5
-3.25 +4.25
-11.75
2.0 +8.0
-1,25 +5.0
+2.25
Gopher
373.5
294.67
1882.0
306.6
287.0
932.0
307.25
239.0
812.2
-43.0
+190.33
+998.75
+44.4
+196.5
+365.0
+:36.0
+157.0
+372.4
Hero
4867.6
948.67
11233.2
1949.4
717.0
9630.4
1364.5
843.5
5908.8
4497.4
11157.33
+ 1478..2
1156.0
11107.5
11874.4
1273.5
11224.5
11707.4
MsPacman
520.0
849.6
1091.4
386.0
665.2
934.5
367.5
616.67
716.2
-43.83
1293.6
1.38.8
140.2
1178.2
1360.5
135.0
-91.67
1377.6
NameThisGamee
1707.17
2171.0
5021.4
1725.4
2099.67
3926.17
1863.0
2083.0
3591.2
=151.67
+658.75
+1007.2
+149.0
+577.0
+697.17
+202.0
=568.25 25
+1033.4
Qbert
323.29
358.5
13085.5
214.2
343.0
3241.6
227.0
320.33
622.0
=51.99
111.5
+2510.5
+27.4
+52.67
+1009.6
+50.6
88.67
+285.6
RoadRunner
1540.29
816.0
18485.25
89.8 162.0
970.25
4636.0
106.0
1066.5
2642.2
-293.57
1912.33
14068.75
1535.5
1948.4
171.5
L5210
1846.2
StarGunner
631.0
992.0
1841.2
596.71
883.5
937.83
557.17
944.25
874.4
164.4
1:232333
1442.6
166.43
1211.5
1137.17
161.5
-135.0
+175.2
TimePilot
1876.71
2809.75
2048.5
2264.4
1981,25
2584.0
2659.0
2871.67
2615.4
=340.29
+1265.5
+ +1564.75
+432.6
+908.75
+1277.25
+323.5
=1090.0
+1595.0
WizardOrWor
434.25
545.25
1150.8
348.8
525.67
1066.0
368.25
608.33
845.4
=71.5
+312.5
+664.
+60.8
+226.67
+569.8
+60.75
3304.67
+472.4
Table 1: Summary of mean scores on 15 Atari games with constant execution delay M {5, 25) on 32 episodes for each of the four trained seeds.
The following table shows scores stochastic delays.
20

---

Published as a conference paper at ICLR 2024
Game
m
15
25
Obl.
Delayed DQN
Delayed EZ.
ObL.
Delayed
Delayed E.Z
Obl, EZ
Delayed
Delayed E7
DQN
DQN
Alien
348.43
366.0
796.6
318.0
333.0
820.33
257.71
324.5
607.8
=52.14 14
+231.67
+205.4
+29.71
#118.5
+325.67
#20.86
=100.5
+
Amidar
41.5 +6.17
37.0
220.25
23.4 +5.8
48.5 427.0
145.67
7.33 +2.83
40.0 +17.5
95.8 #:32.4
+21.67
+43.0
+30067
Assault
376.0
267.0
1068.25
293.0
242.5
1132.0
203.4
251.5
790.6
-20.14
+140.67
+229.0
+23.0
+110.5
+-286.33
+30.0
+98.5
+191.8
Asterix
507.3
268.33
6535.5
256.67
239.5
1225.0
233.17
234.5
636.0
=35.9
+148.0
14392.75
133.5
113.0
1934.33
116.33
168.55
+336.
BankHeist
15.0 +3.33
13.0
140.0
16.17
6.5 +7.5
91.67
14.0 #2.55
9.0 +T2.0
27.33
112.6
1.30.6
12.33
1.26.6
16.0
Boxing
-2.6 +4.0
33.0 +6.0
20.2 +9.0
4..33 #1.71
4.0 +9.0
2.5 +6.0
-5.5 #1.75
-3.0 +6.5
3.33 +6.33
Gopher
424.38
145.0
1855.4
364.33
198.0
1633.0
347.4
130.0
1378.25
335.62
1127.33
1828.4
167.5
168.0
1709.0
131.8
#18.5
1666.25
Hero
4813.88
492.0
11798.8
2466.67
669.5
11890.33
1887.83
619.0
8127.25
4475.75
1856.0
11399.6
1345.0
10006.0
11372.0
1303.17
-022..5
1:2681. .25
MsPacman
530.0
444.0
1443.6
452.4
439.0
1173.0
397.17
399.0
940.6
-64.62
1276.0
14498.4
155.0
1192.0
1612.33
166.17
-62.5
1455.8
NamsThisGame
1933.33
1673.0
5395.0
1991.0
1760.0
5029.33
1513.44
1761.0
5027.4
=127.33
+912.33
+1244.4
+160.0
+780.5
+1085.33
+243.0
-69..0
+1099.8
Qbert
548.8
208.67
3747.6
154.0
296.5
4121.67
176.75
303.0
1553.0
=207.0
+113.33
+2603.8
+26.0
+88.5
+1829.0
+30.5
=78.5
+1275.5
RoadRunner
1254.0
668.0
9978.6
876.4
227.0
12906.33
488.75
260.5
2173.0
1161.33
1649.5
1.2914.6
1166.8
+515.5
1.331.00
1113.62
+352.0
11103.0
StarGunner
700.2
378.5
19318
656.33
604.0
1235.33
666.14
621.5
939.33
-71.6
+:231.0
1:6074
+.5.55
+.32..5
1-249.67
+.5986
35660
1199.33
TimePilot
2304.75
1529.67
1425.6
1997.17
1905.25
2128.0
2405.5
2523.5
1931.33
=309.5
+972.67
+1347.8
+326.33
+1307.5 5
+1308.0
+379.83
= =1488.0
#1778.0
WizardO/Wor
541.8
288.5
1270.0
383.8
336.0
1175.0
409.5
294.5
1038.67
=125.8
#247.0
1985.4
153.2
#304.0
=9900.
159.67
2233.
#721.67
Table Summary mean scores on 15 Atari games with stochastic execution delay with maximal delay M E (5, 15, 25} on 32 episodes for each of the four trained seeds.
D COMPUTATIONAL RESSOURCES
The computational costs associated with training DFZ in environments with delays increase in pro- portion to the delay values. This escalation arises from the multiple applications of the forward network during inference.
EfficientZero's architectural design harnesses the efficiency C++/Cython for Monte Carlo Tree Search (MCTS) implementation, intelligently distributes computation across CPU and GPU threads, thereby enabling parallel processing. Our experimental setup included two RTX 2080 GPUs. In the context of DEZ, each training comprised 130,000 environment interactions and 150,000 training steps. We provide training duration statistics for the three delay configurations we em- ployed:
For M 5, the training duration exhibited fluctuations over period 20 hours. For M 15, the training duration exhibited fluctuations over a period of 22 hours. For M 25, the training duration exhibited fluctuations over a period of 25 hours.
The training duration of Oblivious EfficientZero is lightly shorter due the omission of multi-step forward processing. For any delay value we tested, the training duration exhibited fluctuations over a period of 20 hours.
21


Reviews:
[{"review_id": "1pfEmEmKqB", "reviewer": "Reviewer_yeMT", "summary": "This paper studies the delayed MDP problem, where stochastic delays are considered during the execution of actions. The authors introduce the concept of Stochastic Delayed Execution MDPs (SED-MDPs) as a solution to address random delays without relying on state augmentation. In particular, they show that optimizing within the set of Markov policies effectively reaches optimal performance.  Empirical validation across Atari games are performed under both constant and stochastic delay settings.", "questions": "Under stochastic execution-delay MDPs (SED-MDPs), if at a specific time step (especially at the beginning of the game), there is no action available due to the delay, how does the proposed method execute the policy?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Standard RL assumes immediate availability of information for decision-making, overlooking delays prevalent in various real-world applications.  Existing approaches resort to state augmentation,  which is inefficient in handling exponential computational complexity and dependence on delay values, hindering its scalability to random delays. To address this issue, the authors propose Delayed EfficientZero, a delayed variant of EfficientZero, which is a model-based algorithm that optimizes over the class of Markov policies. The proposed method is able to accurately infer future states from the action queue, and thus handles delayed execution while preserving the sample efficiency of EfficientZero.\n\nThe authors establish the insight of optimizing within the set of Markov policies offers a more efficient and scalable solution compared to history-dependent policies. They introduce a model-based algorithm, namely, Delayed EfficientZero, that builds upon EfficientZero. The proposed algorithm yields non-stationary Markov policies, maintaining efficiency and scalability without making assumptions about the delay distribution.\n\nDelayed feedback analysis is a rising topic in RL. Existing methods mainly focus on delays in states / trajectory / rewards. This work instead concerns delays in actions during policy execution, and this setting can be useful in practice.", "weaknesses": "1. This paper adopts the ED-MDP formulation of (Derman et al., 2021) that sidesteps state augmentation, and extend it to the random delay\ncase. This extension appears to be a direct application of the previous formulation, authors are expected to explain the technical challenges compared to the constant delay formulation, and be clear about their technical contribution in terms of this formulation.\n\n2. This paper mainly develops based on the ED-MDP formulation of (Derman et al., 2021), random delay formulation in (Bouteiller et al., 2020),  and EfficientZero (Ye et al., 2021). The technical novelty in terms of the algorithm appears to be limited. Authors are expected to highlight the technical challenges and novelties.\n\n3. While authors provide a thorough experimental study on 15 Atari benchmarks, they only consider small delays by setting $M = \\{5, 15, 25\\}$. It is desirable to see how the performance can be when delays are large.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "00KS4Ch07S", "reviewer": "Reviewer_eDQ2", "summary": "The paper focus on MDPs in which there is a stochastic delay in the execution of the action selected by an agent acting in the MDP. Stochastic exectuion delay can result in the agent executing actions in the wrong state as the environment changes in real-time. Prior work focuses in fixed-delay times. This work provides a framework for situations in which the delay time is stochastic.", "questions": "No questions.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Orignality:\"\" The approach introduced in the paper is a novel algorithm for a problem framed in a more realistic way than before.\n\n**Clarity:** The paper is relatively clear and easy to understand. Some minor tweaks could be useful (see later.)\n\n**Significance:** The approach proposed would be of interest to others working MDPs with stochastic delays.\n\n**Quality:** The algorithm designed seems reasonable. The theoretical analysis looks sound however I did not thoroughly go through the proofs. The experiments chosen made sense however there are weaknesses in the results (see later.)", "weaknesses": "- I may be misunderstanding the graphs, but it looks as if SD-EZ scores worse than the other algorithms in most of the games in the plots in Fig 3a and 3b. Also, there are no confidence intervals or significance testing of any kind.\n\n- The algorithmic description is slightly difficult to follow. Perhaps breaking down the data structures (lists, etc.) used into a list would help ease the process.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gw8xq7KQFW", "reviewer": "Reviewer_zW4Z", "summary": "In the real world, state information may not instantly be observed, actions may not instantly be applied, and reward feedback may not be immediate for various environmental reasons. The authors tackle this problem, called stochastic execution delay in MDPs, through the introduction of a new formalism, SED-MDPs. They prove that during policy optimization it is sufficient to restrict the search to the set of Markov policies and present a novel algorithm called Delayed EfficientZero, which shows improved performance over EfficientZero and Delayed-Q on Atari benchmarks.", "questions": "My low score is down to the problems with Figure 3, which is central to supporting the claim about improved performance over Atari. If the authors can confirm my suspicions and commit to fixing the figure in the rebuttal, or at least clarify the situation, I will strongly consider raising my score (after considering other reviews as well).", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The authors motivate the problem well. It's easy to understand why stochastic execution delay is an important problem in RL. The contributions are also strong. The extension of ED-MDPs into SED-MDPs seems useful, and Theorem 4.2 is a nice theoretical result that shows Delayed EfficientZero is a well-principled algorithm for them. The results seem promising, given that Figure 5 is correctly labeled and not Figure 3.", "weaknesses": "There are some clarity issues with the experiments, particularly in Figure 3. It seems mislabeled. Figure 5 in the appendix suggests blue should be SD-EZ, red delayed DQN, and white Oblivious-EZ. It also looks like delays appear from \"low to high\" rather than from \"high to low\" as suggested in the caption. It would also be nice for comparison's sake to standardize the figure so that the same game appears on a single row in both columns.\n\nSince SED-MDP is a new formalism, it may benefit the paper to include experiments in simpler domains. A central point of the paper seems to be constant vs. stochastic delays, but the experiments don't seem to show much of a difference between algorithms in the two environments for a given Atari game.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dkUes0GYLe", "reviewer": "Reviewer_Rzwe", "summary": "The paper introduces(?) an MDP variant with stochastic execution delay. For the problem considered the authors show that  the optimal policy lays in a class of Markov policies. A variant of an MCTS algorithm, EfficientZero, is proposed that deals with the stochastic delay in the execution. Empirical evaluation are performed on a set of modified Atari benchmarks with superior results against some baselines.", "questions": "The relation between the MDP variant considered here and the one discussed in the Bouteiller article should be made clear. I would prefer also some motivating discussion on the choice of dealing with the action delays. Personally, I would find more natural if the action delays would not be limited to discrete values, and being executed after the delay (in many physical systems, the evolution of the system is not restricted to discrete steps anyway, even if the decision are). This would avoid the drop and duplication of the actions. Also, we might not necessarily observe the realization of execution delay, unless we can reverse engineer it from a known transition model (when it is deterministic). \n\nI can see arguments for the considered variant as well. Since the `proper' way to incorporate stochastic action delays in the MDP is not well established, I would like to see some (more) motivating discussion on the choice, and not only how it is handled. \n\nWhile MuZero and (somewhat to lesser extent) EfficientZero are well known, it is still difficult to understand the new algorithm described only in terms of differences to EfficientZero. The algorithm should be described completely, while pointing out the relevant differences.\n\nThe experiments are fairly extensive, but there is the issue of lack of clear baselines when a new problem is proposed. Maybe adapting the Delay-Correcting Actor-Critic of Bouteiller (even if does not have an MCTS module)?\n\nMinor: the initial state distribution (\\mu) in the MDP tuple is not present in the SED-MDP definition. Is this an intentional omission? \n\nOverall, I feel that there is a valuable contribution in the paper, but the presentation issues are fairly significant, and make the evaluation of the contribution difficult.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The delayed MDP variant seems a relevant problem.\n\nThe theoretical insight for the considered variant is valuable, and the proposed algorithm extension seems reasonable.", "weaknesses": "It is not clear that this is a new MDP variant, or it is a particular version of the one with random delays considered in the Bouteiller article (cited in the paper) - with no observation delays. \n\nThe algorithm is described only in terms of differences to EfficientZero, which makes it hard to understand.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)