Control in Stochastic Environment with Delays: A Model-based Reinforcement Learning Approach

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 04:54:01

Abstract: In this paper we are introducing a new reinforcement learning method for control problems in environments with delayed feedback. Specifically, our method employs stochastic planning, versus previous methods that used deterministic planning. This allows us to embed risk preference in the policy optimization problem. We show that this formulation can recover the optimal policy for problems with deterministic transitions. We contrast our policy with two prior methods from literature. We apply the methodology to simple tasks to understand its features. Then, we compare the performance of the methods in controlling multiple Atari games.

Main paper: 
 introduction: 
 To introduce robots into our every-day life, researchers have to transfer algorithms developed in simulated environments to real environments. Existing research such as (Mahmood et al. 2018; Ramstedt and Pal 2019) has shown that applying general Reinforcement Learning (RL) methods to realtime control systems, such as robotic arms and self-driving cars is a challenging problem. One reason is that RL methods assume that the optimal action is directly applied to the observed state of the system. However, in real applications, the action may in fact be applied to a different state of the system. This could be due to delays in transmission, or the randomness of the system transitions. For example, in Figure 1 , a real-world system is evolving while the optimal action is calculated, transmitted, etc. All these translate into time delays between the observed system state and the target state, the system state on which the action is applied. (Derman, Dalal, and Mannor 2020) show notable performance degradation of RL methods when introducing such delays in a control system. The performance further deteriorates in an environment with increased uncertainty in the next state transition.The system evolves from the observed state to the target state by executing a sequence of prior submitted actions whose effects have not been observed yet. Previous studies (Walsh et al. 2009; Firoiu, Ju, and Tenenbaum 2018; Derman, Dalal, and Mannor 2020) use the observed state and the sequence of actions to estimate the target state and to select optimal actions based on the estimated state. These methods have shown good performance in environments with deterministic or slightly random state transitions. However, real- world applications can contain high level of randomness in state transitions. For example, control schemes have to cope with uncertain road/weather conditions as well as delays in 45 transmission. In Figure 2 we illustrate a situation where we need to apply an action to the target state. Due to delays, the target state is unknown, only its probability distribution may be estimated. In this paper, we show that the aforementioned methods may not perform well in such environments where 50 state transitions are stochastic. We design a model-based RL method to control an agent in a stochastic environment with a known constant delay. Our method learns a probabilistic model of the environment to estimate multiple possible target states and their probabilities. The method evaluates the 55 consequences of each possible action taken.The main contribution of our work is a new control method, Stochastic Model Based Simulation (SMBS), for problems in environments with stochastic transitions which are observed with a constant delay. We illustrate how to train 60 the SMBS method in delayed environments. We show that the new control method recovers the optimal policy in delayed environments with deterministic transitions. In the experiments section, we illustrate the advantages of the proposed method over two baseline methods in multiple envi-65 ronments. We also demonstrate how the parameter of SMBS policy function can shape its risk preference.We consider an infinite time horizon control problem with a finite action space. General RL methods model the non- delayed environment as a Markov Decision Process (MDP) in (Sutton and Barto 2018 ). An MDP can be defined as (S, A, P, r, µ) where S is the state space, A is the action space, P (S t+1 = s | S t = s, A t = a) is the probability of transiting to next state s , given current state s and action a. The reward function r(s, a) : S × A → R, quantifies the immediate reward obtained by applying action a to current state s. Let µ denote the probability distribution of the initial state s 0 . Given a deterministic Markov control policy π : S → A, we can define the Q-function as the expectation of the discounted cumulative rewards for state s and action a:q π (s, a) = E ∞ k=0 γ k r(s k , a k ) | s 0 = s, a 0 = awhere a i = π(s i ) and s i ∼ P (• | s i-1 , a i-1 ) for i = 1, 2, . . .. (Sutton and Barto 2018) show the optimal action value function is defined as q * (s, a) = max π q π (s, a), and maximizing the function produces the optimal control policy π * (s) = arg max a q * (s, a).In MDPs, actions are assumed to be applied immediately to the current states. However, in real-world applications, the action is applied to a later state than the observed state because of system delays. Previous studies (Jeong and Kim 1991; White 1988; Loch and Singh 1998; Bander and White 1999 ) model control problems with delays as a special case of a Partially Observable Markov Decision Process (POMDP) due to the uncertainty of the target state. A natural solution for POMDP problems is to create another MDP with an augmented state space. Following this idea, (Katsikopoulos and Engelbrecht 2003) formulate the general Augmented MDP (AMDP) for problems with constant delays in observation and action. They show that observation delays and action delays are equivalent from the perspective of the controlling agent. In our work we use delay steps to indicate the sum of these two types of delay. We consider a control problem with d delay steps. Let M denote 90 the non-delayed MDP. The corresponding augmented MDP is M D (M, d) = (I, A, P , r , ω ) where I = S × A d , and r is defined as r (I t , a t ) = r(s t-d , a t-d ). Let q * denote the optimal Q-function for this AMDP.Although, (Katsikopoulos and Engelbrecht 2003) show that q * provides the optimal control for this delayed problem, (Walsh et al. 2009 ) state that solving this problem in practice is difficult since the size of state space I grows exponentially with the number of delay steps. This issue is even more significant in modern applications, as the state and action spaces are already large, even before state augmentation.Several recent studies use RL to find good control policies without solving the AMDP. We discuss these methods and their connections to our method in detail in the next section. We mention alternative approaches based on simto-real learning by (Tobin et al. 2017 ) and robust learning by (Pinto et al. 2017) to adapt models from simulations to real world robots. Our work focuses on solving delay problems using RL. The methodology we develop could complement a sim-to-real transfer but combining the ideas is beyond the scope of this work.The methods developed by (Derman, Dalal, and Mannor 2020; Walsh et al. 2009; Firoiu, Ju, and Tenenbaum 2018) can be classified as instances of deterministic planning. A deterministic planning strategy consists of two components: a model of the system dynamics, and a non-delayed policy function. This strategy obtains a single estimate of the target state. Then, based on this estimate, the non-delayed policy function selects an optimal action to be applied to the target state. (Walsh et al. 2009) state that this approach performs well in deterministic tasks. Note that a fundamental requirement is the single estimate of the target state. In stochastic environments, the estimator of the target state has a distribution which may have a large variance. As the action is chosen based on the estimator, this may lead to sub-optimal actions if the estimator is far from the actual state. Therefore, we must consider the effect of the action taken on multiple possible target states, rather than a single one.To expand the deterministic planning method for stochastic environments, we develop a stochastic model based simulation (SMBS) method. This method develops a strategy which consists of a probabilistic model of the system and a value-based non-delayed policy function. This policy function is generated by an optimal Q-function. We denote this non-delayed optimal Q-function with q * . The model of the system, denoted as µ(s, a), maps a given state/action pair to a probability measure on the state space S. Suppose the environment has d delay steps. We form an augmented state using the delayed observation and a sequence of actions,I t = (s t-d , a t-d , • • • , a t-1). Note that s t-d is the latest observation of the system state, and the effect of {a t-d , • • • , a t-1 } has not been observed yet. As shown in Figure 3 , we sample M estimates of the target states, {s(i) t } i=1,••• ,M using the one-step transition model µ(s | s, a).To be specific, for each path i, we let the initial state s (i) t-d = s t-d . Then, we recursively sample the estimates of the next states s(i) t-d+k+1 using µ(• | s (i) t-d+k , a t-d+k ) for k = 0, 1, • • • , d-1.Finally, we select the action using the following policy function150 a t = π 1 (I t ) = arg max a∈A QM (a) -α QM (a) , where QM (a) = 1 M M i=1 q * (s (i) t , a), QM (a) = 1 M -1 M i=1 (q * (s (i) t , a) -QM (a)) 2 .(1)The function QM (a) estimates the average state action value for action a. The risk of executing action a when the target state is unknown is measured using QM (a). Mathematically, QM (a) is the sample standard deviation of the Q-value of the target state. The hyper-parameter α controls the importance of QM (a).The policy function of SMBS (equation 1) uses the mean and standard deviation of the sampled Q-values. Intuitively, it will select optimal actions by maximizing the expected action value while minimizing the deviation of the Q-values 160 from their mean value. Algorithm 1 introduces the pseudocode used to implement the SMBS method.Algorithm 1: Stochastic Model Based Simulation Policy 1: Input: A trained Q-function q * , a trained system model µ, I t = (s t-d , a t-d , • • • , a t-for all s (i) t in D do 16: L ← q * (s (i) t , a); 17: end for 18: V[a] = mean(L) -α • std(L); 19: end for 20: return arg max a V[a].We present a training procedure for the SMBS method in delayed environments in Algorithm 2. In the sample collection step, the delayed action a t+d is selected using the 165 SMBS policy in 1. We record the transition sequence of the system and determine the actions corresponding to respective state transitions. This will produce the non-delayed Algorithm 2: Training the Q-function q and the system model µ for the SMBS method 1: Input: An interactive environment E.2: Output: a Q-function q and a model of the system dynamics µ. 3: Initialization: randomly initialize the parameter in q and µ, a data container C for transition samples. 4: /* Collecting Samples */ 5:I d = (s 0 , a 0 , • • • , a d-1 ) ← E 6: for t = d, d + 1, • • • , N do 7:a t ← SMBS(I t ; q, µ); 8: Update µ using Maximum Likelihood Method; 16: end for 17: return q, µ transitions (s t , a t , s t+1 , r t ) which are used to train q * and µ. Similar procedures are also used by (Schuitema et al. 2010; Derman, Dalal, and Mannor 2020) .s t-d+1 , r t-d ← E(a t ); 9: C ← (s t-d , a t-d , s t-d+1 ,The main difference SMBS and the planning policy in (Derman, Dalal, and Mannor 2020) is that the policy of (Derman, Dalal, and Mannor 2020) plans for the most likely next state. As a result, once trained the planned action path is always the same for the same input I t . This is why we term this planning method as deterministic. In contrast, SMBS (equation (1)) obtains multiple target state estimates by sampling trajectories using a probabilistic model of the system. The action is selected to maximize the average Q-value subject to the penalty term.Even though the SMBS method is designed to accommodate a stochastic environment, it also works in deterministic environments. In fact, the next result establishes that the SMBS method provides the optimal control. A proof of this theorem is provided in the supplementary material.Theorem 1. Assume a discrete-time MDP with an infinite time horizon. The Markovian movement is deterministic, i.e., for arbitrary (s, a) ∈ S × A, t ≥ 0, there exists an s ∈ S such that P (S t+1 = s | S t = s, A t = a) = 1 for all t = 0, 1, . . . Then, the policy function of the SMBS method (1) is equivalent to the following optimal policy:EQUATIONwhere q * denotes the optimal Q-function for the AMDP.When parameter α is set to 0, the SMBS method is reduced to a Monte-Carlo procedure that estimates E s [q * (s t , a) | I t ]. This conditional expectation is associated with the probability measure for s t , given I t . Thus, the policy (1) in the SMBS method approximates the following (3)When the problem has a small discrete state space, the model 200 of the system may be expressed using one-step transition matrices. In such cases, we compute the distribution of the target state using these transition matrices. Then, we calculate the expectations in (3) for all actions a ∈ A and select the action with the highest expected value. We note that 205 this procedure has been analyzed by (Agarwal and Aggarwal 2021) . Interestingly, although the two policy functions are similar, the two methods have been developed independently from different perspectives. When the problem has a large discrete state space or a continuous state space, the SMBS method models the system model using an artificial neural network (ANN). Thus, instead of learning transition matrices, the algorithm focuses on learning the parameters of the ANNs approximating the model. When the problem solved involves a complicated state space, this change avoids multiplications between large matrices which are computationally expensive and inefficient. Our method can solve complex tasks by incorporating parametrized Q-functions which are trained using well-known deep RL methods such as DQN in (Mnih et al. 2015) , DDQN in (Van Hasselt, Guez, and Silver 220 2016), Dueling DQN in (Wang et al. 2016) , etc. We also provide a probabilistic bound for the SMBS policy in (1) when α = 0. Theorem 2. Assume a discrete-time MDP with a positive reward function and a finite discrete action space A. For any a ∈ A and augmented state I t ∈ I, assume the random variable q * (s t , a) has mean Q(a) and variance Q(a) 2 . Then, for δ > 0, we haveP max a∈A QM (a) ≤ 1 |A| E [V * (s) | I t ] - δ √ M max a∈A Q(a) ≤ |A| δ 2The proof of this theorem is provided in the supplementary material.If the variance Q(a) 2 exists for any a ∈ A, its sample estimates converges to 0 when the sample size M goes to infinite. This implies that if we plan for sufficiently large amount of paths, the value of SMBS policy function is not worse than 1|A| E [V * (s) | I t ] with high probability.In order to understand how the SMBS method performs in delayed environment with different levels of randomness in transitions. We train and test the SMBS method with other baseline methods in multiple tasks. We choose the following baseline methods for comparison.1. AMDP in (Katsikopoulos and Engelbrecht 2003) , which forms an AMDP and directly solve the problem using Double DQN by (Van Hasselt, Guez, and Silver 2016). 2. Delayed-Q in (Derman, Dalal, and Mannor 2020) , which is, to the best of our knowledge, the latest deterministic planning method. This method follows the following policy π 2 (I t ) = arg max a∈A q * (ŝ t , a),where ŝt is obtained by a recursive propagation using a deterministic model of the system m(s, a) = arg max s P (S t+1 = s | S t = s, A t = a). That is,ŝt-d+1 = m(s t-d , a t-d ), ŝt-d+2 = m(ŝ t-d+1 , a t-d+1 ), • • • ŝt = m(ŝ t-1 , a t-1 ).We note that while the Delayed-Aware Trajectory Sampling (DATS) method in (Chen et al. 2020 ) may be used as a baseline comparison, it does require knowledge of the exact reward function. As the other three methods learn the reward function, we excluded DATS from our analysis.When comparing the SMBS with the baseline methods, we are trying to address the following questions:1. Does the SMBS method obtain better average rewards? 2. Is there less performance degradation of the SMBS method than the baseline methods when the number of delay steps increases and when randomness in the environment increases?with a 1-dimensional state space and a discrete action space with 4 actions. Figure 4a illustrates this environment. The task requires the agent to maneuver a car on a narrow road during a storm. The road is through a large swamp. The car can fall off the road and get stuck in the swamp on both 265 sides of the road. There are four actions possible representing 4 forces with different directions and magnitudes, i.e., steering to left/right aggressively/mildly. If the car runs into the swamp, an aggressive steering to the road has a higher chance to move the car back to the road than a mild steering.If the agent cannot return the car to the road immediately, the agent will receive a large penalty. The storm randomly pushes the car to the left or the right. The level of randomness is adjusted by a parameter r. A higher r increases the variability of transition. We test r = 0.05/0.1/0.15 in our experiments.Frozen Lake is a maze-like problem which is implemented in (Brockman et al. 2016) . Figure 4c illustrates the 4-by-4 Frozen Lake task. The goal is to reach the Goal State (G) starting from the Initial State (S). The agent goes back to the Initial State if at any time reaches a Hole state (in blue in Figure 4c ). This environment has a slippery parameter p (1/3 ≤ p ≤ 1) which controls the randomness of the transition. This parameter indicates the probability of moving to the intended target square. That is, if the agent chooses to go right, it will arrive to the state to its right with probability p. Otherwise, the agent may move to the two other adjacent states (up and down) with equal probabilities 1-p 2 . We denote r = 1-p 2 , we test r = 0.05/0.1/0.15 in our experiments.Cartpole is a classic benchmark task, and has been implemented in (Brockman et al. 2016) . The agent applies left-/right forces onto the cart to keep the pendulum balance. A normally distributed noise with zero mean is added to the force. The standard deviation of the noises is a parameter r = 0.1/0.2/0.3.Puddle World is another classical task mentioned in (Degris, White, and Sutton 2012) . The goal is to navigate to the goal state (1.0, 1.0) on a 2D world at the soonest without stepping in the high penalty zone (grey area in Fig- ure 4d ). The movement noise is controlled by a parameter r = 0.005/0.01/0.02.For each environment setting (level of randomness and number of delay steps), we train 5 models (with different random seeds attached to the clock) using each of the three methods. Each model is trained in the delayed environment with 10 5 steps. The policy with the highest average reward is recorded for evaluation. Each model is evaluated using the 10 4 steps. We report the average rewards by the top four models in the next section.The system dynamics model and the Q-function are trained using the dataset collected from the delayed environments. For the Stormy and Swampy Road and for the Frozen Lake environments we estimate the transition matrices using the observed frequency of transition. For the Puddle World and for the Cartpole environments we model system dynamics using Gaussian based probabilistic neural networks, which are often used for continuous control problems in (Duan et al. 2016; Mnih et al. 2016 ). The neural networks have two layers, each layer has 64 units. For the SMBS method, we plan 50 trajectories for each decision (M = 50). The small number of paths is chosen so that the algorithm converges in a reasonable amount of time. The α parameter controls the importance of the variability of the estimated future cumulative rewards. A large alpha produce policies that produce stable future rewards. However, these may not be optimal from the perspective of maximizing reward. After an extensive number of experiments, we choose α = 0.01 in our studies.The average rewards from three methods are reported in Figure 5 . Figure 5a shows SMBS and AMDP both perform better than Delayed-Q in all settings. SMBS outperforms AMDP when the environment has 20 steps of delay and the random factor r = 0.15. This result is not surprising as the task is simple and easy to solve. AMDP can produce the optimal strategy given sufficient amount of samples (10 5 steps). In Figure 5b , the bar plots indicate that SMBS has the overall best performance among three methods. The performance degradation is relatively smaller than the other methods. When the level of randomness is small (r = 0.1/0.15), AMDP and SMBS have better performance than Delayed-Q. When r = 0.2, the performance of AMDP significantly degrades, SMBS still outperforms the other two methods. Moreover, to understand how the SMBS method can outperform the Delayed-Q method in Stormy and Swampy Road task, we evaluate the both methods using the same system model and the same Q-function. Figure 6 shows a comparison of performance between SMBS and the Delayed-Q with a slight change of the estimated Q-function. The two Q-functions in Figure 6a and 6b are two non-optimal Q-functions that are consecutively recorded during training 355 (Q 1 is closer to the real Q-function than Q 2 ). Figure 6d displays the main difference between two Q-functions. When the state is close to 1, Q 1 indicates the action a 1 has a higher value than a 2 , while Q 2 indicates a 2 has higher value than a 1 . As a result, the policy of Delayed-Q method produces different actions when the estimated target state is close to 1. In contrast, the SMBS policy is less affected by small changes in the Q-function since it considers the expected Q-value.Atari Learning Environments (ALE) in (Bellemare et al. 2013 ) offers intricate environments for training and testing RL methods. (Mnih et al. 2015) has shown that RL agents can surpass human-level strategies using RL methods. With delayed observations, (Derman, Dalal, and Mannor 2020) shows the Delayed-Q method can outperform baseline methods such as AMDP and Obvious-Q method on ALE.We apply our method to ALE and compare it with the AMDP method and the Delayed-Q method. Across all experiments, additional randomness in movements is introduced by setting a 0.2 probability for sticky actions. Sticky actions simulate scenarios where the controller ignores the input action and repeats the prior action. We perform training and testing of the three methods across 7 Atari games when the number of delay steps equals to 5 and to 25. In each experiment setting, we train models with the three methods with the same amount of steps, and we load the bestperforming model for evaluation. In the SMBS method, we set the number of planning paths M as 20 to create a trade off between efficiency and accuracy. We set the risk preference parameter α as 0 because we would like to only maximize the expected reward.The evaluation results are reported in Figure 7 . It can be seen that the AMDP method performs worse than the other two methods in most of the games. The AMDP method also suffers from stronger performance degradation than the two other methods when the number of delay steps increases from 5 to 25. This is evident in Freeway and RoadRunner. The performance of Delayed-Q and SMBS is consistent when the number of delay steps increases. Their two To explore how different risk preferences impact the policy function in 1, we examine the policy function in Cliff, a classic control problem from (Sutton and Barto 2018) . In Cliff, the agent navigates a maze-like path from start to end (refer Figure 8 ) . The agent needs to avoid falling off the cliff during the movement. When the agent moves, the agent has a chance to slip towards the cliff. Due to delays in observations in this problem, the actual location of the agent is unclear when the action is chosen. Therefore, the agent faces the choice between a risky move to the right or a safer move upwards. We select this task to demonstrate the impact of the risk preference parameter because the risk involved in this problem is easy to understand. A more risk-averse agent would prefer moving away from the cliff due to the risk of falling.We construct the SMBS policy functions using the optimal Q-function and different risk preference parameters α.We then run these policy functions in the Cliff environment. Figure 8 presents the average path for different risk preference parameters. When the slippery parameter is small, the risk preference parameter has small impact on the policy functions and the resulting paths are very similar. However, when the slippery parameter is large, thus more randomness in movements, it can be seen that higher risk preference parameters lead to paths distant from the cliff edge. This demonstrates that policies with higher α values exhibit greater risk aversion. In Figure 9 we illustrate the SMBS method performance for varying α values in the Cliff environment. In a more deterministic setting (left graph with slippery chance 5%), we see little difference in the policy function performance regarless of the risk averse parameter α. In Figure 9 right increasing alpha produces less variable results which means that the policy becomes more and more conservative. This aligns with expectations, as a risk-averse agent tends to move farther from the cliff to reduce the risk of falling, consequently prolonging the time taken to reach the goal.In this study, we investigate control problems in stochastic environments with constant delayed feedback. We develop a new method (SMBS) designed to approximate optimal control for such problems. We show that the SMBS method 445 is optial when the system has deterministic movement. We compare the performance of the SMBS method, with two other baseline methods using 4 classical control environments and 7 Atari Learning Environments. We observe performance degradation as the number of delay steps increases 450 and as the level of randomness in transitions is increased. Our experiments show that the SMBS method outperforms AMDP in most experiments and is no less than the Delayed Q method in most Atari games. Further, the SMBS method is more robust to errors in estimation of the Q-function. We 455 also showcase the impact of the risk preference parameter in the SMBS policy function. This parameter may be used to further tune the agent behavior in response to perceived delays. 
 
 Appendix:  


Decision: The paper describes a method, called Stochastic Model-Based Simulation (SMBS), for decision-making in with delayed feedback. The key idea is to anticipate a different possible future states rather than relying on deterministic estimates.

The reviewers agreed on the value of the work despite some issues with the experiments and the scolarship. We recommend the authors to include the information provided in the rebuttal in the final version of the paper.

Reviews: review: strength_weakness: strength_weakness: - The paper must clarify the policy governing the evolution of the system during training of the delayed policy. The paper originally stated that the evolution of the system state was simulated based on actions from a non-delayed optimal policy, and calculates the delayed policy for controls based on the system evolving according to the optimal policy. If the system is already being controlled according to a non-delayed optimal policy, it is difficult to see why we would want to override that with a delayed control. However, careful examination of the pseudocode shows that the policy used to generate the action sequences are in fact the delayed policy being trained. 
- The paper's results could be better explained. AMDP is described as the full problem, whereas SMBS is a sampling approximation which deals with the intractability of uncertainty propagation. It is unusual that an approximate algorithm would yield better results, unless there were unreported limits on computation. The computation limits should be clarified and emphasised.
questions: questions: 1. Given that a non-delayed optimal policy exists, and the system is evolving according to the non-delayed optimal policy, what is the motivation for control using a delayed policy? 
2. What makes SMBS not a "deterministic" method? Is it simply that it is sampling at each point, and so there exists a distribution over the actual action taken? In that case, would SMBS be a deterministic method in the limit, as the number of samples approach infinity?
3. What were the parameters for running the experiments? Specifically, the experiments note that 5 models were trained for each method. How were the models trained? Were they trained until convergence, or up to a time limit? Why were the results reported for only the top 4 models for each method?

===
Post rebuttal
===
My main concerns were: 
- The motivation for finding a delayed control policy, given that the system is evolving already according to actions derived from q*, a "non-delayed optimal Q-function" lines 135-138. This is passed into Algorithm 1 (SMBS Policy) in Line 1, and used in Line 8 of Algorithm 1 to simulate forward. Reading Line 8 of Algorithm 1, the simulation samples state s_{t-d+j+1} from applying a_{t-d+j} at state s_{t-d+j}, with a_{t-d+j} presumably from q*. What is actually trained in Algorithm 2, and used as input into Algorithm 1 is a delayed policy. This should be clarified in the final text text.
- The text states in Line 176 that the authors "term this planning method [Delayed-Q] as deterministic". It was unclear how the proposed method contrasts. It was important to clarify that stochasticity comes from the sampling. 

Further minor errors:
- Algorithm 1, line 10: should be updating \mathcal{D} to be \mathcal{D}\cup \left\{s_t^{(i)}\right\}
- Algorithm 1, line 16: should be updating \mathcal{L} to be \mathcal{L}\cup q^*(\left\{s_t^{(i)}\right\},a)
strength_weakness: strength_weakness: Unfortunately, while the work is quite interesting I think there are some weaknesses that might need to be fixed.

W1. This is a minor comment but using \citet for in-line text citations would be better for listing ciations.

W2. It seems from the empirical evaluation, that this approach is not particularly well-suited to heavily outperform the closest baseline: Delayed-Q which also utilizes planning via single-outcome determinization.

For example, even as the total noise and delay steps increase, the overall performance in domains such as Frozen Lake and Puddle World and many of the Atari games remains quite similar and does not best showcase the merits of SMBS. Similarly, for RoadRunner in Atari, performance deteriorates for SMBS as "d" increases.

W3. Fig. 9 (right) is unclear. One would expect that as \alpha increases, the avg. reward goes significantly down but the mean rewards remain relatively the same even if the std. deviation decreases slightly.
questions: questions: I think that the work is interesting but the experiment design in the paper might be poor and might not be well-suited to showcase the strengths of SMBS well. One immediate improvement would be to use higher values of r to induce even more randomness.

Q1. Could you please comment on W2. Is there any intuition as to why the performance on Frozen Lake and Puddle world are quite close. For example, when r=0.05, as the delay steps increase SMBS starts outperforming Delayed-Q but surprisingly for r=0.1 and r=0.15 it is not so prominent. One would expect delayed-Q to start performing worse as d increases. An ablation of sensitivity to M is not provided and it would be useful to have such info. Similarly, please also provide an intuitition on why SMBS worsens in RoadRunner while Delayed-Q performance increases?

General comment here: I think Fig 8 and Fig 9 could be left to supplement and you could use the space to provide a better analysis on why these performance differences occur particularly as "d" increases since one would expect SMBS to shine in such cases with high values of "r".

Q2. Could you please comment on W3?

Q3. In line 8 of Alg. 1, why are you sampling from \mu? Since you have already computed the probability distribution you can always grow a tree of depth d making the approach independent of M as well. Is there a particular reason for sampling?

Post Rebuttal
===========
Thank you for clarifying my questions. I have raised my score to a weak-accept. If this paper were to get rejected, I'd encourage the authors to tighten the empirical evaluation that showcase the performance of SMBS over Delayed-Q better and resubmit. (Handling of continous environments is a strength and I hope that the authors are able to emphasize that as well). I wish the authors all the best.
strength_weakness: strength_weakness: 1. Complexity in Real-World Applications: The method shows promise in simpler grid-world simulations, but its scalability and computational feasibility in complex real-world tasks, such as robotic manipulation with vast state and action spaces, are not addressed. The proposed model's approach of selecting actions based on multiple trajectories from the current state might face tractability issues in long-horizon tasks, such as those in robotic manipulation. These tasks often involve a vast number of potential future states, making the computation of multiple trajectories computationally intensive. In such scenarios, the model's feasibility and efficiency could be significantly challenged. Could the authors provide a complexity analysis or comment on the potential computational limitations in more intricate scenarios?

2. Assumption of Constant Delay: The paper assumes a fixed delay, which simplifies the model but may not accurately reflect the variability found in real-world delays. Can the authors discuss the implications of this assumption and potential adaptations for variable delays?

3. Comparative Analysis with Related Work: The paper lacks a thorough comparison with relevant research in lookahead learning with delay, specifically papers by Han et al. (2022) and Lancewicki et al. (2023). How does the proposed method compare with these approaches, and why might these methods not be adaptable to the authors' framework?

Han, B., Ren, Z., Wu, Z., Zhou, Y. & Peng, J.. (2022). Off-Policy Reinforcement Learning with Delayed Rewards. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:8280-8303 Available from https://proceedings.mlr.press/v162/han22e.html.

Lancewicki, T., Rosenberg, A., & Sotnikov, D. (2023). Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedback. *ArXiv*. /abs/2305.07911 [Published at ICML 2023]

Rosenberg, A., Hallak, A., Mannor, S., Chechik, G., & Dalal, G. (2023, June). Planning and learning with adaptive lookahead. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 37, No. 8, pp. 9606-9613).
questions: questions: 1. Please comment on the time and space complexity of the proposed method and how well the method will scale for real-world robotic tasks such as manipulation and long-horizon problems.

2. Please comment on the papers I mentioned in the weakness section and explain how they differ from the proposed approach.