Dear reviewer, thank you for your response. Please find our answers in the following.
**W1 How is the extension technically challenging compared to the existing ED-MDP formulation of Derman et al., (2021)?**
While both our work and that of Derman et al., (2021) tackle RL under delayed execution, we present new theoretical and algorithmic contributions. We understand the reviewer is asking regarding the theoretical part, so we answer it here. Unlike the fixed delay case of Derman et al., (2021), in an SED-MDP, the decision time of an executed action at $t$ is *random*. As a result, for a given policy, the process distribution can be different depending on the realization of the delay process. This is not the case of constant delay, as the SED-MDP process distribution stays the same once the policy is given. Yet, in Thm. 4.2, we show that *even* when the delay values are generated from a random process, for any history-dependent policy, we can achieve the same process distribution under a Markov policy. The technicalities of the proof require introducing the notion of *effective decision time* at time $t$, i.e., the effective time at which an action executed at $t$ has been drawn. Thus, instead of having $a_t\sim \pi_{t-m}$ for a constant execution delay $m$, we now have $a_t\sim\pi_{\tau_t}$, where $\tau_t}$ is the effective decision time – the time at which the action performed at time $t$ was previously decided. In some sense, the resulting process becomes a stopped process in the random delay case.
**W2 Technical challenges and novelties in Delayed EfficientZero**
As opposed to the Delay-Correcting Actor-Critic of Bouteiller et al., (2020), we leverage a model-based approach, which is different from their solution: Bouteiller et al., (2020) work on an augmented state space, a continuous action space, and effectively small delay values compared to ours (observation and execution delays are smaller than 7 in any of their wifi delay sampler). The technicalities in our work also differ from Delay-Correcting Actor Critic as we describe here. We address our approach by leveraging the popular model-based approach of Ye et al., (2021), but this requires a significant effort to extend to the delayed setting. When delays exist in tree search-based algorithms, one has to perform these searches successively while keeping parallelism efficiency. We do so by implementing a parallelized MCTS search for predicted states, game trajectory manipulation, and matching stochastic delays after observation are obtained as described in Section 5 and in the added Appendix B.
**W3 Longer delay values**
Thank you for your suggestion. We added experiments per your request on two Atari domains with larger delay values of {35,45}. The learning curves for Asterix and Hero can be found in the following link:
https://ibb.co/q7npffz
We also added them to Appendix C.3 in the revised version and the result explanations at the end of section 6.
**Q1 What action to take when none is available?**
As standard in control theory or previous delayed RL works, delay values are upper bounded (by, say, $M$) even though they are random. Thus, we specify an initial queue of $M$ actions to execute if none is available from the agent’s policy. Otherwise, especially when $t>M$, an action drawn from the agent’s policy is always available, and we use the latest executable action. This implies that some actions are duplicated when the realized delay value increases.