Tree Search-Based Policy Optimization under Stochastic Execution Delay

Dear reviewer, thank you for your response. Please find our answers in the following.

W1: Is the legend in Figure 3 wrong? Good catch, the legend in Figure 3 was indeed wrong. Also, we added a table in the appendix, summarizing all the scores, including standard deviations for the four seeds.

W2: Can you make a each game appear in a single row in both columns? Thanks for the suggestion. We have now standardized the game to appear in the same rows in both columns for comparison’s sake.

W3: Do we expect a difference between constant and stochastic delays? We do not expect a significant difference in the score behavior between constant and stochastic delays. Since the delay process we used was not biased toward a single value, the effect of stochasticity in delays can be to ease the state prediction when delays become smaller. For both settings, the scores should decrease when the delay increases.

Dear reviewer, thank you for your response. Please find our answers in the following.

W1: What is the difference from the formulation of (Bouteiller et al., 2020)? In fact, there is a crucial difference between our work and (Bouteiller et al., 2020). The formulation in the latter included an augmentation of the state space with the action queue and delay values: X=S×A^K×N^2. This makes the decision process Markovian and therefore all standard results on non-delayed RL hold naturally at the expense of an exponentially larger new (embedded) state space. In our SED-MDP, however, the state space remains unembedded. We therefore devise the theoretical machinery needed to be able to prove that non-Markov policies are as beneficial as history-dependent policies, as long as they can be non-stationary.

Q1: What about continuous time delay and estimation of it without observing it? We appreciate the useful real-world direction. We agree and added this direction to the summary as relevant future work. We mentioned another approach when dealing with unobserved stochastic delays. Using a robust criterion with respect to multiple possible realizations of delays may lead to conservative policies, adapted to the delay complexity.

Q2: Can you add motivating examples to having stochastic delay? Sure. Perhaps the most prominent example of why delay can be stochastic is in real world systems that rely on transmission of data. Often, there is interference in transmission that can stem both from internal or external sources. Internal sources may be due to sensing HW that can be dependent on the temperature and pressure conditions. Whereas external sources can stem in the case of a robot or AV whose policy infers actions remotely (e.g., in the cloud). We added this motivation to the introduction.

Q4: Can you baselines such as DCAC? The Delay-Correcting Actor-Critic of Bouteiller et al., (2020) uses augmented state space, embedding the entire action queue, which we avoid by planning. Moreover, the DCAC algorithm does not support discrete action space and adapting Soft Actor Critic to these settings is a complex task as shown in (Zhou et al., 2022, Revising discrete soft actor-critic) that requires significant modifications of the model structure, deviating from DCAC. With such a support to discrete action space, one could have used, for comparison, an adapted version of Soft Actor Critic for delayed environments - a Delayed Actor Critic with planning - but we believe this extension doesn't naturally align with the context.

Dear reviewer, thank you for your response. Please find our answers in the following.

W1 Mistake in Figure 3 Good catch, the legend in Figure 3 was indeed wrong; we fixed it in the revised version. Also, we added a table in the appendix, summarizing all the scores, including standard deviations for the four seeds.

W2 Algorithmic description We added a description of the actors in the original EfficientZero model of Ye et al., (2021) along with a pseudo-code of the episode sampling procedure to Appendix B, to clarify the order of execution of the different components during episode collection.

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.

I acknowledge that I've read the author comments and am raising my score accordingly.