Acting in Delayed Environments with Non-Stationary Markov Policies
Authors: Esther Derman
Gal Dalal
Shie Mannor
Venue: ICLR 2021 Poster (2021)
Keywords: reinforcement learning
delay

Abstract: The standard Markov Decision Process (MDP) formulation hinges on the assumption that an action is executed immediately after it was chosen. However, assuming it is often unrealistic and can lead to catastrophic failures in applications such as robotic manipulation, cloud computing, and finance. We introduce a framework for learning and planning in MDPs where the decision-maker commits actions that are executed with a delay of $m$ steps. The brute-force state augmentation baseline where the state is concatenated to the last $m$ committed actions suffers from an exponential complexity in $m$, as we show for policy iteration. We then prove that with execution delay, deterministic Markov policies in the original state-space are sufficient for attaining maximal reward, but need to be non-stationary. As for stationary Markov policies, we show they are sub-optimal in general. Consequently, we devise a non-stationary Q-learning style model-based algorithm that solves delayed execution tasks without resorting to state-augmentation. Experiments on tabular, physical, and Atari domains reveal that it converges quickly to high performance even for substantial delays, while standard approaches that either ignore the delay or rely on state-augmentation struggle or fail due to divergence. The code is available at \url{https://github.com/galdl/rl_delay_basic.git}.

Published as a conference paper at ICLR 2021
ACTING IN DELAYED ENVIRONMENTS WITH NON-STATIONARY MARKOV POLICIES
Esther Derman"
Gal Dalal*
Technion
Nvidia Research
retherderran@ campus.
gdala obalal.n www.nniiiia...mm com
Shie Mannor
Nvidia Research & Technion
shießee wew.eeeetttcniion.cc.oo
ABSTRACT
The standard Markov Decision Process (MDP) formulation hinges on the assump- tion that action is executed immediately after it chosen. However, assuming it is often unrealistic and can lead to catastrophic failures in applications such as robotic manipulation, cloud computing, and finance. We introduce a framework for learning and planning in MDPs where the decision maker commits actions that are executed with a delay of m steps. The brute-force state augmentation baseline where the state is concatenated to the last committed actions suffers from an exponential complexity m, as we show for policy iteration. We then prove that with execution delay, deterministic Markov policies in the original state-space are sufficient for attaining maximal reward, but need to be non-stationary. As for stationary Markov policies, we show they are sub-optimal in general. Consequently, we devise a non-stationary Q-learning style model-based algorithm that solves delayed execution tasks without resorting to state-ad aate--aammetttionn.. Experiments tabular, physical, and Atari domains reveal that it converges quickly to high perfor- mance even for substantial delays, while standard approaches that either ignore the delay or rely on state-augmentatin struggle or fail due to divergence. The code is available https:: /ttpttgtttbb/bb/ con/ ga ddl/rl delay basic.git
INTRODUCTION
The body of work on reinforcement learning (RL) and planning problem setups has grown vast in recent decades. Examples for such distinctions are different objectives and constraints, assumptions on access to the model or logged trajectories, on-policy or off-policy paradigms, etc. (Puterman 2014). However, the study of delay in RL remains scarce. It is almost always assumed the action executed as soon as the agent chooses it. This assumption seldom holds in real-world applications (Dulac Arnold al., 2019). Latency in action execution can either stem from the increasing computational complexity of modern systems and related tasks, or the infrastructure itself. The wide range of such applications includes robotic manipulation, cloud computing, financial trading, sensor feedback in autonomous systems, and more. To elaborate, consider an autonomous vehicle required for immediate response a sudden hazard on the highway. Driving at high speed, it suffers from perception module latency when inferring the surrounding scene, as well as delay in actuation once decision has been made. While the latter phenomenon an instance of execution delay, the former corresponds to observation delay. These two types of delay are in fact equivalent and can thus be treated with the same tools (Katsikopoulos & Engelbrecht 2003).
Related works. The notion of delay is prominent in control theory with linear time- invariant systems (Bar-Ilan & Sulem 1995; Dugard Verriest 1998 Richard 2003 Fridman 2014 Bruder & Pham 2009). While the delayed control literature is vast, work intersects with mostly in motivation. In the above control theory formulations, the system evolves according to some known diffusion or stochastic differential equation. Differently, the discrete-time MDP framework does not require any structural assumption on the transition function or reward.
$ Equal contribution

---

Published as a conference paper at ICLR 2021
A few works consider delay in the reward signal rather than in observation execution. Delayed reward has been studied on multi-armed bandits for deterministic and stochastic latencies (Joulani at.l. 2013) and for the resulting arm credit assignment problem (Pike- Burke et al. 2017). In the MDP setting. Campbell et al. (2016) proposed a Q-learning variant for reward-delay that follows a Poisson distribution. Katsikopoulos & Engelbrecht (2003) considered three types of delay: observation, execution, and reward. [Chnn et al. (2020b) studied execution delay on multi-agent systems. The above works on MDPs employed state-augmentation with primary focus on empirical evaluation of the degradation introduced by the delay. In this augmentation method, all missing information is concatenated with the original state to overcome the partial observability induced by the delay. The main drawback of this embedding method is the exponential growth of the state-space with the delay value (Walsh et al. 2009 Chen et al. 2020a) and, in the case of (Chen et al. 2020b), an additional growth that is polynomial with the number of agents.
Walsh et al. (009) avoided auttmmttmmettioonn in MDPs with delayed feedback via a planning approach. By assuming the transition kernel to be close to deterministic, their model-based simulation (MBS) algorithm relies on a most-likely present state estimate. Since the Delayed-Q algorithm we devise here resembles to MBS in spirit, we highlight crucial differences between them: First, MBS is a conceptual algorithm that requires the state-space to be finite or discretized. This makes it highly sensitive to the state-space size, as shall demonstrate in Sec. Fig. ]( prohibiting it from running on domains like Atari. Differently, Delayed-Q works with the original, possibly continuous state-space. Second, MBS is an offline algorithm: it estimates a surrogate. non-delayed MDP from samples, and only then does it solve that MDP to obtain the optimal policy (Walsh et al. [Alg 2, 1. 16]. This is inapplicable to large continuous domains and is again contrast to Delayed-Q.
Recent studies considered a concurrent control setting where action sampling occurs simultaneously with state transition (Ramstedt & Pal 2019 Xiao et al. 2020). Both assumed a single action selection between two consecutive observations, thus reducing the problem to an MDP with execution delay of m 1. Chen et al. (020a) have generalized to an arbitrary number of actions between two observations. Hester & Stone (2013) addressed execution delay in the braking control of autonomous vehicles with relatively low delay of m & 3. All these works employ statetaugeentttion to preserve the Markov property of the process, whereas we are interested whether this restriction can be lifted. Additionally, they studied policy-gradien style value-based. algorithm. Likewise, Firoiu et al. (2018) proposed modified version of the policy- bosed IMPALA (Espeholt et al.] (2018) which is evaluated on a single video game with delay values of m 7. To the best of our knowledge, our work is the first tackle delayed variant of the popular Atari suite (Bellemare et al. 2013).
moolicy-basedi methods, while we introduce a Q-learning
Contributions. Revisiting RL with execution delay both in theory and practice, we introduce:
1. Analysis of delayed MDP quantifying the trade-off between stochasticity and delay.
2. The first tight upper and lower complexity bounds on policy iteration for action-augmented MDPs. We stress that this is also a contribution to general RL theory of non-delayed MDPs.
3. A new formalism of execution-delay MDPs that avoids action-embeddingg Using it, we prove that out of the larger set of heepory policies, restricting non-stationary deterministic Markov policies is sufficient for optimality in delayed MDPs. We also derive a Bellman-type recursion for delayed value function.
4. A model-based DQN-style algorithm that yields non-stationary Markov policies. Our algorithm outperforms the alternative standard and state-augmented DDQN in 39 of 42 experiments spanning over 3 environment categories and delay of up to m = 25.
PRELIMINARIES: NON-DELAYED STANDARD MDP
Here, we describe the standard non-delayed MDP setup. Later, in Sec. 5 we introduce its general- ization to the delayed case. We follow and extend notations from (Puterman] [Sec) 1. An infinite horizon discounted MDP is tuple (S, A, P. P.r,y, r,,.) where S and A are finite state and action spaces, P : S x A - As is a transition kernel, the reward r : S x A + is a bounded function, and 7 [0. 1) is discount factor. At time t, the agent is in 8; and draws action a according to decision rule d, that maps past information to a probability distribution gd. over the action set. Once a, is taken, the agent receives a reward r r(8t, 0t).
2

---

Published as a conference paper at ICLR 2021
A decision rule can be history-dependee (H) or Markovian (M), and randomized (R) or deterministic decision-rui is given by di H4 AA with h4 9d, (h,) (.) A Markovian decision-rule, on the other hand, maps states to actions, i.e., de S - AA with - (s) ). A policy := (de is sequence of decision rules whose type dictates that of the policy. It can be either Markovian deterministic (ITMD) or randomized (TTM),, if its decision rules do not depend on time, c., dN = d for all t O. This defines the smaller class of stationary policies; deterministic (IISD) and randomized (IISR). Note that stationary policies are inherently Markovian. Indeed, at time Since the policy is stationary, i. l.e., d, = d dt,, subsequent decision rules are also state-dependent, thus Markovian. This makes I the most general set and ITSD the most specific.
(D). Denote by H4 the set of possible histories up to time t. Then, a
deterministic (ITHD) or randomized (ITHR). It is stationary
O, d Ho AA is state-dependent because Ho S.
We denote probability model by P where the subscript O stands for the delay value m = 0. The related random variables are denoted by 5t E S, ā A and he E (S x A) x S. The value function
given policy x e II is defined as 0 (=(ss ET
7"r0" āz) šu
where the expectation
is taken with respect to (w.r..)) PT (.15g | = s). Let the optimal value function
(s) == max v"(s)
V
-Ell
Our goal is find policy x* that yields v** and it is known that focusing stationary deterministic policies π E IISD is sufficient for reaching the optimum in (Puterman 2014 6.2.10.J.
3 MDPs WITH DELAY: A DEGRADATION EXAMPLE
In an MDP with execution delay m, any action chosen at time is executed at ttt- + m. Therefore, at each step, the agent witnesses the current state and action being executed, but selects a new action that will be applied in a future state. We assume that m decided actions are already awaiting execution at = 0, so at any given time, the queue of pending actions is of constant length m. As we illustrate in the next example, having a delay generally comes at a price.
P
1 p
p
S0
$1
r
do 0
41 r
41
11=11
:
Example 3.1 (Two-state MDP). Consider the MDP in Fig. 7 It has two states and two actions: S= {80, $ A= The transition kernel is independent of the action: for all s' E S s.t. * s', ",s('''s,,, [0.5, 1]. The reward is positive for one of the two actions only:
p
{ag, a1}-
Figure 1: Degradation due to delay two-state MDP.
= P(s'(s) = where E
r(80, (0) a() = (1) r()1,00) =0
We inspect the return obtained from the commonly used set of stationary deterministic policies II As expected, the highest possible return is attained when m O, but monotonically decreases with the delay, m, and increases with the level of certainty, p. We analytically quantify this effect in the following and give a proof in Appx. A.I
Proposition 3.1. For delay m E N and p [0.5, 11, the optimal return of x* e ITSD is (2p-
2(1-7)
Remark 3.1. This result demonstrates clear tradeoff between stochasticity and delay. For 0.5 or m + o0, the return goes to its minimal value of (155((1 - 7). Contrarily, for - or m - 0, it goes its maximal value of 1/(1 ()).
THE AUGMENTATION APPROACH
In this section, consider sate-augmentation for solving MDPs with execution delay. We begin with defining an equivalent MDP with a larger state space that memorizes all missing information for an informed decision. Due the full observability, the resulting optimal augmented policy attains the optimal return in the original delayed MDP.
The exact terminology used by Katsikopoulos & Engelbrecht (003) is action delay, while in Bertsekas al. (1955) (Section 1.4] it is time lag. We prefer the term execution delay since the action is itself decided instantancously.
3

---

Published as a conference paper at ICLR 2021
Definition 4.1 (m-AMDP). Given MDP A, and m N. m-Augmented MDP (m- AMDP) is a tuple (X (m::A, A, F, g,7) such that Xm := S x A is the augmented state-space, A the original action-space. F is the transition matrix given in Appx. B.1 14 and g is the reward function given in Appx. B.
15
The pending action queue is concatenated to the original state to form an augmented state 2t : (st, a, ........ ; ") E Xm, where ag is the i-th pending action at time t. It means that in the following step, t + 1, action ar will be executed independently of the present action selection, the queue will shift to the right, and the newly selected action will be at the second coordinate. By construction, the m-AMDP is non-delayed; it directly accounts for execution delay through its state-representationn as opposed to our coming formulation Sec. [ We further define a stationary deterministic policy के E ITSD with corresponding decision rule d : Xm A and augmented value function (xx) := 1 - g' (8)
x] As in our goal is to solve
(x)) = maX (x), V/ E X'm.
We now analyze the classical Policy Iteration (PI) algorithm (Howard 1960) for m-augmented MDPs and provide finite-time analysis of its convergence. We refer to as mA-PI and provide its pseudo-code in Appx. B.2 We consider PI since it a canonical representative upon which many other algorithms are built. Admittedly, we did not find any other formal result quantifying the effect of augmentation on a planning or learning algorithm, other than PAC upper bound for R-max with e-optimal policies (Walsh et al. 2009p. proof for the next result is given in Appx. B.4
Theorem 4.1 (Lower Bound for mA-PI). The number of iterations required for mA-P Pl to converge in m-AMDP Mm is [( Xmm l) = 22 S || A I")
Thm. 4.1 does not take advantage of the special delay problem structure but rather is an application of our more general result to augmented MDPs (Appx B.4). As pointed out in Scherrer et al. (016)) the lower-bound complexity of Pl is considered an open problem, at least in the most general MDP formulation. Lower-bounds have been derived in specific cases only, such as deterministic MDPs
(Hansen & Zwick 2010). total reward criterion (Fearnley 2010) or high discount factor (Hollanders) ct al. 2012). Even though we did not intend to directly address this open question, our lower bound result seems to be a contribution on its own to the general theory of non-delayed MDPs.
Next, we show that the above lower bound is tight (up to factor of |A and logarithmic terms) and mA-PI is guaranteed converge after ([S)||A A proof is given in Appx. B.5
Theorem 4.2 (mA-PI Convergence). The mA-PI algorithm converges to the optimal value-policy pair (6+, ,**) in al most [S]|-A|m((4 (I:4) 1) log (1/1) log (1/1>)) iterations.
EXECUTION-DELAY MDP: A NEW FORMULATION
In this section, we introduce and study the stochastic process generated by an MDP with execution delay, without resorting to state-augmentation, In the ED-MDP we consider, the probability measure changes according to the delay value m. We assume that during the initial steps, actions sequentially executed according to a fixed queue à := (ā..... am-1) E AAT Unlike m-AMDPss the initial queue of pending actions here plays the role of an exogenous variable that is not embedded into the state-space. A policy т E I induces a probability measure IP; that is defined through a
m, decision rules do not depend on the history, while for t 3 m. they depend on the history up to f - m only. Let I be an initial state distribution and 5 a Dirac distribution. Using this and the notations from Sec. 2
set of equations which, for brevity, we defer to Appx. 1 16- [9]]
We note that for
we can explicitly write the probability of sample path. See proof in Appx. C.
Proposition 5.1. For policy π. := (do, d.....) E THHR, the probability of observing history he := (3o, 0o $1, a1 aa-11, 8t) is given by:
p (50 80, āo do, 51 81, ōi ai, _ a,-1, = st)
Sag ((w))((snc)))) (sk, an) I k-
[ Ude (d (ax) llse,
-u(s))
From Prop. 5. we deduce that, differently than the standard MDP setting where any Markov policy induces Markov process, the delayed process is not Markovian even for stationary policies (see
4

---

Published as a conference paper at ICLR 2021
Appx. 2 for formal proof). Next, show that for any distory-depender policy and starting state, there exists a Markov policy (not necessarily stationary) that generates the same process distribution. Consequently, despite execution delay, one can restrict attention to Markov policies without impairing performance.
Theorem 5.1. Let π II be history dependent policy. For all so S, there exists Markov policy n' E IIMR that yields the same process distribution as 9, ie.. po (8.m = s', = a0 = su) P. (3tmm = = alš0 so), V A, E S,t z m.
The proof is given in Appx. CR3 builds on the concept that for each history-dependent policy I1 one can choose sequence of Markov decision rules that reconstruct the same time- dependent action distribution in the process induced by π.
This result proves attainability of the optimum over II but not how can efficiently find an optimal policy. In Appx. C.5
we formally define the delayed value function um Holjmm-1: for policy and initial action distribution queue M40 1mmm1 (Mo,...., 11- In Thm. there, we show that satisfies a non-stationary Bellman-type recursion. Though the question of how to efficiently find an optimal non-stationary Markov policy remains generally open, we partially answer it by proving that a deterministic Markov policy is sufficient for the optimal delayed value function.
Theorem 5.2. For any action distribution queue (4D 1mmm1 (No.- (m-1) and 8g S
max ed 1. MEll
max U (.00-/mmm- mEll
Degradation due to stationarity. To complement the finding that a deterministic Markov policy can be optimal for any ED-MDP, we show that restricting stationary policies impairs performance in general. Thus, while in non-delayed MDPs it is enough to
Hatoryy- Deperdeent
Random
Determinisde (HD)
focus on the latter, in ED-MDP the restriction should be to the more general class of Markov policies.
Markow Random (MI1
Markor Deterninatic (MD)
Delayed num [Tha wark)
Proposition 5.2. There exists an m-ED-MMD for
which all stationary policies are sub-optimal.
This result follows from computing the optimal re- turn for stationary and non-stationary policies in the ED-MDP from Example 3.1 using simulation. We elaborate this further in Appx. C.4 There, we also confirm that our theoretical return from Prop. 3.1 matches closely with simulation. Lastly, a visualiza- tion of the results from this section is given in Fig.
Statonary
Bratonary
(SPy
Nonvslaaped optimum [Piterman, 1894]
Figure Optimality of policy types in ED- MDPs: Markovness is sufficient but non- stationarity is necessary.
A NEW ALGORITHM: DELAYED-Q
We now introduce an algorithm capable of successfully handling tasks with exccution delay by inferring the future m-step state before each decision.
Non-stationary Markov policy
Action queue
Algorithm Description. Fig. depicts the algorithm. As a first stage, to select an action az to be executed state St+m- we infer that future state 8t+m using the current state st and the queue of pending actions (ar-m..... 11-1). This is done by successively apply- ing an approximate forward model m times: 8c+1 f(st, at-m)...........)... ...,, 8c+m =
future
Forward model
6
Q-network
(Srom Ferm Oc, Scom+1)
Xm
Replay buffer
9:
Delayed
f(rtmm 11. More details on the for- ward models are given Sec. / The ap- proximate model here is simpler than other model-base based algorithms such as tree-search methods, because it does not require access the reward function. Also, only single trajectory is
environment
Figure 3: Delayed- algorithm diagram.
5

---

Published as a conference paper at ICLR 2021
sampled rather than exponentially many w.r.t. the horizon length. We do note this method benefits from the environment not being entirely stochastic (Walsh et all 2009). Still, as we show next, performs well even noisy environments. As a second stage, a policy at = =f)++m). The two stages of this procedure can be represented as a non-stationary Markov policy (st);), where the non-stationarity stems from the time-dependency of the action queue, and the Markov property from the policy being applied on and no prior history. Notably, the Q-function here does not take past actions as imput, contrarily to the augmentation approach in Sec. Il To better stress the non-stationarity, we note that applying the policy on the same state at different times can output different actions. Lastly, for training. we maintain a sample-buffer of length m which we use to shift action a, into the tuple (8 Tt+m, des 8t+m+1) prior to each insertion to the replay buffer. During the course of this work, we also experimented with a model-free variant. Instead of "un-delaying" the Q- Q-function with the forward-moder we defined delayed Q-function trained on sequences whose actions were shifted m steps forward. However, the obtained results were unsatisfactory, seemingly because the Q-function is unable to implicitly Iearn the m-step transition.
select action according to
Point-Estimate Approaches. For completeness, we mention alternatives to using a 'most-likely' state estimate, such as expected future state. To demonstrate why point-estimate prediction can be devastating, consider an MDP where = (x. t): position and time, respectively. Starting from 50 (0, (), progresses deterministically, while behaves like random walk with momentum; i.e., if x: > 0, then x + is more likely than x - 1, and vice versa. The process obviously diverges with time. Consider two actions: one is good when |z|| big, and the other when |a|] is small. For a large delay m, the PDF of the state is bi-modal and symmetric around (Z, m) and (-2. m) for some finite Z. But, a point estimate (c. g., ML MAP) would yield value of (0, m). In addition this example, we observe that in our Ex. 3.I any alternative to a 'most-likely' state estimate is worse: there, the optimal policy applies actions based on the most- most-likely likely state (see proof of Pr. while it is easy to see that any other policy weighing future state probabilities leads to lower reward.
EXPERIMENTS
We perform experiments in a wide range of domains: tab- ular, physical, and image-based Atari. All of them include stochasticity: In the maze we inject noise to actions; in the physical domains we perturb the masses each step; and Atari is stochastic by nature. We compare our algorithm with two baselines: Oblivious- 2 and Augmented- Q. Oblivious- Q is the standard Q-learning that ignores delay and assumes each decision to be immediately executed. Augmented-Q acts on the m-AMDPP introduced in Def. 4.1 We test all domains on delays m E {0,5, 5, 15, 25} with 5 seeds per each
# Traiming ep sefore reaching 0.5
Delayed-Q Augmented-0 Q
Delay value
run. All results are summarized in Fig. 10 and are provided
Figure Maze: Time complexity as a function of m
in more detail with std. in Appx. D.I
Table 2
Tabular Maze Domain. We begin with testing Delayed-Q
Maze domain (Brockman al. (tloMiiyyuzl wwwo/////mfmmmt. It is based on tabular Q-learning and enables us to study the merits of our method decoupled from the coming DDQN added complexities. Moreover, it conveys the exponential complexity of Augmented-Q. The forward-model we construct is naturally tabular as well: predicts a state s' according to the highest visitation frequency given (s, a). The objective in Maze is to find the shortest path from start position to a goal state in a randomly-generater N x N maze. Reaching the goal yields a reward of 1, and 11/10))2) per step otherwise. The maximal episode length is 10 steps, so the cumulative reward is in [-1, 1]. We also create a Noisy Maze environment that perturbs each action w.p. p [0, 0.5].
Convergence plots are given in Fig. Delayed-Q outperforms the rest for all delay values m, while Oblivious-Q Q fails in all runs for m > Since the augmented state-space grows exponentially with m. Augmented-Q converges more slowly as m increases. In fact, for m > 15 the simulation fails to run due to memory incapacity for the Q-table; this explains its absence in Figs. the exponential complexity growth of Augmented-Q and compare it with Delayed-Q, we trained both agents with increasing delay values, and reported the number of training episodes each one required before reaching cumulative reward of 0.5. Fig. ellearly demonstrates the exponential (resp. linear) dependence of Augmented-QQ (resp. Delayed- Q) in the delay value. The linear dependence of Delayed-Q in m is not surprising: Delayed- Q is algorithmically identical to Q-learning, except
3 10
To confirm

---

Published as a conference paper at ICLR 2021
for the m-step forward- moward calls and the replay buffer shift of samples. To further analyze its sensitivity to the state-space size, we ran tabular Delayed-Q on increasing maze sizes, for a fixed 5. As Fig. [(c) shows, the performance drops exponentially, suggesting high sensitivity to the state-space size and highlighting one shortcoming of MBS (Walsh et al. 2009) (see Sec.
0.1 0.2 0.3 0.4 0.5
0.8
0.5
Delay Value
0.4
0
900
0.0
200
0.0
Naise value
-0,5
100
-0.4
363
5X3
10KL0
100x300
NoiGe value
Maze sie
(a)
(b)
Figure 5: Delayed-Q (median 5 seeds): (a) Total reward after 5000 training episodes 10 10 Maze. Performance is sensitive to both delay value and stochasticity. (b) Noisy Cartpole. (c) Reward on varying Maze sizes. Abscissa is in log-scale, the return decreases exponentially with m.
Augmented-O Delayed-Q ckllisus
Delay
Maze
Delay
Delay
-22
-0.9
-84
-0.75
-1.2
-35
-1.25
-12
300
580
72:00
801
7200
5000
1293
7200
8:30
'28
120
252
631
1510
3003
1463
Augmented-Q
Delaped-Q
Steps
Delay
Sleps
Noisy CartPole
Delay
vilvisus-
350
122
300
132
20
300%
150
2009
2009
50%
200%
150% Steps
200
250
50%
100
1009
200
250
50%
100
190%
2009
250
AugmentediQ
Steps
Sceps
Delayed-O
Deley
McPacman
Deley
V
1750
1330
Rowerd
1830
800
6021
2001
400%
222
100
1001
500
Steps
Figure 6: Convergence plots for Maze, Noisy Cartpole and Atari MsPacman. Note that the scale of the y-axes (performance) may change from figure figure.
Physical Domains. Next, we test our approach on two continuous domains: CartPold and Acrobot. The CartPole task requires balancing a pole connected to a cart that actuates left or right. In Acrobot, one needs to swing up the lower of two links connected by joint above certain height. The agent receives reward of 1 if the pole stays above a certain angle in Cartpole, and in Acrobot it receives until reaches the goal. The episode length 500 steps in both tasks. We also create noisy versions of both tasks: At each step, normal additive noises are independently added to each physical component's s mass, with std of 0.1 of the nominal mass.
We extend the famous DDQN algorithm (Van Hasselt al. 2015) and compare to it. though method is general and can be seamlessly integrated into any Q-learning based algorithm. Our one-step forward-model is implemented with neural network (NN) of the same architecture as the Q-network. Namely, it consists of two hidden layers, each of width 24, with ReLu activations. The input of the
"Since Cartpole fails in ~ steps if the initial actions are random, we initialize the m--legthed action queue with optimal actions using pretrained non-delayed model. We wait for 2m steps hefore starting to append samples the replay buffer avoid unfair advantage due these actions.
7

---

Published as a conference paper at ICLR 2021
Maze
Noisy Cartpole
Noisy Acrobot
Augmented-O
500
Augmentes--g
Augmented-0
Delayed-Q
Delayed-O
100
Delayed-Q
Episodic reward
0.5
Oblivious-O
400
Oblivious-O
Obliviou--
200
300
0.0
300
200
-0.5
400
100
500
-1.0
20 Delay value
25
0
5
10
15
20
25
10 15
20
25
30
Delay value
Delay value
Figure 7: Performance as a function of the delay (from left to right): Maze, Noisy Cartpole, Noisy Acrobot. For Augmented-O Q Maze, m > 10 missing due to explosion of the state-space.
m 0
m 5
15
m 25
HakpCatpple
Cartpeee Curadative Reward
HalkyCarpppic Corsiativo Reward
NodayCariplls Ourulativ Reward
208
150
20C
100
Figure 9: Noisy Cartpole: Performance gap between true and trained forward model.
neward-moder NN is the concatenation of (s, a) and its output is s'. Training the forward -ooell NN is conducted together with the Q-network training with the same hyperparameters and sample batches; this makes the implementation easy and simple. For Augmented-Q, Q, a concatenation of the pending actions to the state is fed to the Q-network.
Fig. 6 depicts the performance of the three algorithms for different values of for Noisy Cartpole. As expected from a physical domain, ignoring delay gives catastrophic results even for m 5. Augmented-Q performs moderately up to m = 15, but fails for larger delays. Delayed-Q performs the
Trained with
Delay (mternncl
best for all m values, and performs well even on the challeng-
ing task of balancing a noisy pole with m = 25. We observe similar behavior in all Cartpole and Acrobot experiments,
as shown in Fig. TO Moreover, in Fig. 7 we demonstrate the relative robustness of Delayed-Q to different delay val- ues. All tested environments exhibit superior performance of Delayed-Q for wide range of delays. In Noisy Acrobot, Delayed-Q performs better for m 25 than the alternatives do for m = 2. Figs. ((a))(()) show a clear trade-off between noise and delay, as we also discuss in Rmk. 3.T For high delays, the agent is much more sensitive to an increase in stochasticity.
CCmmutrivee reward
Figure 8: Performance gap for Delayed-Q trained with a delay of m = 10.
To quantify the dependence of Delayed-Q on the model accuracy, compare the learned model to a perfect one, i.e., the environment itself. Fig. shows performance is impaired more as the delay increases and suggests better model can potentially improve reward by 20-30%. Further, we test the robustness of Delayed-Q to misspecified delay by training it with m 10 and evaluating on other delay values. Fig. shows the evaluation performance for m E [5, ... 15). demonstrates the robustness of our method varying performance in evaluation (for good or bad) does not stem from delay misspecification. Instead, the delay 'forgotten' after training, and Fig. g depicts the general effect of execution delay on performance. For shorter delay than the training one, i. e., < 10, performance even improves. The reason is that, first, during training, the Q-function is 'un-delayed' due to the replay buffer shift that relates the actions to the correct execution time. Second, the darwar-moder is trained based on single-step transitions and only during inference it queried m times. Thus, these two networks composing the agent are oblivious to the delay they were trained on.
8

---

Published as a conference paper at ICLR 2021
Delay
Delay 25
Noisy Maze
Maze
600
0.5 0.5
1.00
Nolsy Acrobot
Delayed-Q Augieented Obl vious-Q
Acrobot
Noisy Caripole
Cartpole
limePilot
NameeThisGame
Obert
StarGunner
Enduro
MsPacman
RoadRunner
Episodic Reward
Figure 10: Experiment summary: mean of episodic return for all domains. Delayed-Q outperforms the alternatives in 39 of 42 experiments. Due to negative reward, a positive translation of is applied for Maze and 500 for Acrobot. Atari x-axis is the gain relative to lowest result in each experiment.
Atari Domains. We run the last set of experiments on the Atari Learning Environment (Bellemare) al. 2013). We inspect 8 games from those that were successfully tackled with the original Q- network architecture and hyperparameters of DDQN (Van Hasselt et al. 2013). Since a learned forward-model for images conditioned on actions a hanging question in the research frontier, we leave it for future work and use the simulator itself for prediction. It is stochastic in nature and thus encompasses approximation error. For Augmented-Q Q, we concatenate the action queue the output of the CNN part of the Q-network; the extended vector is then fed into the subsequent fully-connected part it. We train all games for 1M steps. Fig. 5 shows convergence plots for MsPacman. Delayed-Q consistently better than Augmented-Q for all values, which is, in turn, better than Oblivious-Q. Although the gap between all three algorithms is small for m 5, it increases with m. For m = 25, the delay is too large for the augmentation to have positive effect compared Oblivious- Q, and they perform the same. This behavior is representative of all Atari games, as can be seen in Fig. 10 Lastly, compared Delayed-Q Q with fourth algorithm which uses RNN policy that is unaware of the delay value. The results are given in Appx. D.2, showing that a recurrent policy does not improve upon Augmented-Q Oblivious-Q. This result is surprising though: as stated in Thm. S.T. the history sequence St-m: f--m-1...
does not aid the policy any further than only using St-m-
DISCUSSION
In this work, we found that non non-stationary deterministic Markov policies optimal in delayed MDPs. Though more expressive, the standard state augmentation approach is intractable for all but the shortest delays, while the oblivious approach that ignores delay suffers from inferior performance. We derived a Q-learning based algorithm that generates a Markov policy by combining a transition forward model with Q-network. The forward-model produces simple future-state estimate. Incorporating probabilistic estimates and other improvements such as integration of image-based action-dependent (Kim al., 2020), are left for future research. Extensions of our work for real-world applications can be unknown or varying delay. In the first case, good prior for the delay value can often be used, e. g., for autonomous vehicles, as the latency statistics of the different hardware and software components are well studied (Zhao et al. 2019 Niu et al. 2019), while in production systems, they are almost constant (Toschi et al. 2019). Our algorithm is also readily extendable to the second case of varying delay. Differently from the augmentation approach, our 1-step forward-model decouples the algorithm from the delay used for training, as Fig. g depicts. Also, quantization of the delay is not essential long the forward model can operate with variable delay values. Finally, our framework can be extended to policy-gue gradient- based methods that are particularly useful for continuous control, where observation delay is inherent.
learned

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGEMENTS
The authors would like to thank Daniel J. Mankowitz and Timothy A. Mann for motivating this work.
REFERENCES
Avner Bar-Ilan and Agnès Sulem. Explicit solution of inventory problems with delivery lags. Mathematics of Operations Research, 20(3):709-720, 1995.
Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling, The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279 2013.
Dimitri P Bertsekas, Dimitri Bertsekas, Dimitri P Bertsekas, and Dimitri P Bertsekas. Dynamic programming and optimal control, volume 1. Athena scientific Belmont, MA, 1995.
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. OpenAl Gym. arXiv:1606.0154000 2016.
Benjamin Bruder and Huyên Pham. Impulse control problem on finite horizon with execution delay. Stochastic Processes and their Applications, 119(5):436-1440 2009.
Jeffrey Campbell, Sidney Givigi. and Howard M Schwartz. Multiple model q-learning for stochastic asynchronous rewards. Journal of Intelligent & Robotic Systems, 812444):407-222 2016.
Baiming Chen, Mengdi Xu, Liang Li, and Ding Zhao. Delay-aware model-based reinforcement learning for continuous control. arXiv preprint arXiv:2005. 054440, 2020a.
Baiming Chen, Mengdi Xu, Zuxin Liu, Liang Li, and Ding Zhao. Delay-aware multi-agent reinforce- ment learning. arXiv preprint arXiv:2005.088 05544,, 2020b.
Luc Dugard and Erik Verriest. Stability and control of time-delay systems, volume 228. Springer, 1998.
Gabriel Dulac-Arnold, Daniel Mankowitz, and Todd Hester. Challenges real-world reinforcement learning. arXiv preprint 1904. 2019.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Volodymir Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, Iain Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. arXiv preprint / 2018.
John Fearnley. Exponential lower bounds for policy iteration. In International Colloquium Automata, Languages, and Programming, pp. 551-562. Springer, 2010.
Vlad Firoiu, Tina Ju, and Josh Tenenbaum. At human speed: Deep reinforcement learning with action delay. arXiv preprint 1rXiv:1810.07286, 2018.
Emilia Fridman. Introduction to time-delay systems: Analysis and control. Springer, 2014.
Thomas Ducholm Hansen and Uri Zwick. Lower bounds for howard's algorithm for finding minimum mean-cost cycles. In International Symposium on Algorithms and Computation, pp. 415-426. Springer, 2010.
Todd Hester and Peter Stone. Texplore: real-time sample-efficient reinforcement learning for robots. Machine learning. 90(3):385-429, 2013.
Romain Hollanders, Jean-Charles Delvenne, and Raphaël M Jungers. iteration is exponential for discounted markov decision processes. In 20/2 IEEE 51 IEEE Conference on Decision and Control (CDC), pp. 5997-6002. IEEE, 2012.
The complexity of policy
Ronald A Howard. Dynamic programming and Markov processes. John Wiley, 1960.
10

---

Published as a conference paper at ICLR 2021
Pooria Joulani, Andras Gyorgy, and Csaba Szepesvári. Online learning under delayed feedback. In International Conference on Machine Learning, pp. 1453-1461, 2013.
Konstantinos V Katsikopoulos and Sascha E Engelbrecht. Markov decision processes with delays and asynchronous cost collection. IEEE Iransactions on automatic control, 48(4):568-574 2003,
Seung Wook Kim, Yuhao Zhou, Jonah Philion, Antonio Torralba, and Sanja Fidler. Learning to simulate dynamic environments with gamegan. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1231-12400 2020.
Wei Niu, Xiaolong Ma, Yanzhi Wang, and Bin Ren. 26ms inference time for resnet-50; Towards real-time execution of all dnns smartphone. arXiv preprint arXiv:1905.0057/ 2019.
Ciara Pike-Burke, Shipra Agrawal, Csaba Szepesvari, and Steffen Grünewälder. Bandits with delayed anonymous feedback. stat, 1050:20, 2017.
Martin L Puterman. Markov Decision Processes.: Discrete Stochastic Dynamic Programming. John Wiley Sons, 2014.
Simon Ramstedt and Chris Pal. Real-time reinforcement learning. In Advances in Neural Information Processing Systems, pp. 3073 3082, 2019.
Jean-Pierre Richard. Time-delay systems: overview of some recent advances and open problems. automatica, 39(10):1667-169, 2003.
Bruno Scherrer et al. Improved and generalized upper bounds on the complexity of policy iteration. Mathematics of Operations Research, 41(3):58--77, 2016.
Alessandro Toschi, Mustafa Sanic, Jingwen Leng, Quan Chen, Chunlin Wang, and Minyi Guo. Characterizing perception module performance and robustness in production-scale autonomous driving system. In IFIP International Conference on Network and Parallel Computing, pp. 235-247.
Springer, 2019.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning, arXiv preprint arXiv:1509.06460 2015.
Thomas J Walsh, Ali Nouri, Lihong Li, and Michael L Littman. Learning and planning in environ- ments with delayed feedback. Autonomous Agents and Multi-Agent Systems, 18(1):83, 2009.
Ted Xiao, Eric Jang, Dmitry Kalashnikov, Sergey Levine, Julian Ibarz, Karol Hausman, and Alexander Herzog. Thinking while moving: Deep reinforcement learning with concurrent control. arXiv preprint arXiv:2004.0600 06089, 2020.
Hengyu Zhao, Yubo Zhang, Pingfan Meng, Hui Shi, Li Erran Li, Tiancheng Lou, and Jishen Zhao. Towards safety-aware computing system design in autonomous vehicles. arXiv preprint arXiv: 2019.


Reviews:
[{"review_id": "blqFn7X2xs7", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper investigated the problem of learning agents when there are execution delays. The authors (i) used a two-state MDP example to show some equivalence between execution delay and stochasticity of transitions; (ii) analyzed the action aggregation method, which cumulated all the history and then made decisions. They show a classic Policy Iteration (PI) method with the aggregation, unfortunately, has its iteration complexity exponentially depending on the delay time $m > 0$; (iii) formulated the Execution-Delay (ED)-MDP and showed that there exists a non-stationary Markov policy which attains optimal value, while any stationary policies will have suboptimal performance; (iv) proposed a model-based Q-learning method, delayed-Q, which used the predicted future state-action sequence to make decisions; (v) did experiments on Maze, CartPole, Acrobot and Atari tasks to verify the proposed delayed-Q method.\n\nPros:\n1. The execution delay seems to be an important problem in practice. The motivation is convincing.\n2. The theoretical study is fairly strong and insightful.\n3. The experiments show that the proposed method promisingly works well.\n\nQuestions:\n1. The equivalence between execution delay and stochasticity of transitions is interesting. If we use usual assumptions (immediate action execution, and stochastic transitions), does this observation implies inherently there is still something equivalent to \"execution delay\"?\n2. The PI method is proved to have exponential dependence on $m$. Is the proposed delayed-Q learning method guaranteed to have much nicer dependence on $m$?\n3. The proposed delayed-Q is model-based (although as noted it does not need a model of transitions), any thought about how to adapt it into model-free settings?\n4. If the environment is stochastic, then the proposed method will be largely impacted since the next state will be much harder to estimate. Any reason or evidence for if / why this method is expected to perform well?\n5. Also, it seems the comparison is unfair in terms of model-based delayed-Q vs. model-free Augmented Q-learning. How much benefit does the delayed-Q gain from the learned model (or how sensitive the delayed-Q is w.r.t. the model error)? It would be great if there is some investigation over this issue.\n\nOverall, I found the problem is important, and the motivation is convincing. The theoretical study of the execution delay problem is systematic and solid. The proposed method is promising and verified by experiments. On the other hand, there are still a number of questions that need to be clarified, such as the theoretical guarantees of the proposed delayed-Q, and issues about its model-based nature.\n\n===Update===\n\nAfter reading the authors' feedback and other reviews, I would keep my current rating.", "extra_scores": {}, "extra_text": {}}, {"review_id": "_S861TdByi", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the problem of RL with action delay, or equivalently, non-Markov decision process.\nCompared to a naive strategy of state expansion (which appends a history of actions to the observation), the authors show that amending a policy to be nonstationary can:\n  (a) achieve the optimal policy in analysis for tabular MDPs\n  (b) performs well in a series of computational experiments.\n\nThere are several things to like about this paper:\n- The overall standard of exposition and discussion is strong, and it is easy to follow the paper.\n- The paper takes on a clear issue in reinforcement learning, and comes to some equally clear recommendations and findings.\n- The proposed solution method is reasonable, and appears to perform well in practice.\n- The series of experiments are well thought through... with a clear progression from theory -> didactic examples -> deep RL.\n\nHowever there are a few places where this paper falls short:\n- I find some of the characterisations quite \"toy\" overall... yes it is great that the agent can perform well in the setting where m=delay is known, but there is no discussion of the robustness/tradeoff when this is not the case. In a sense this agent is given priveleged information, and while it does better than the expanded state space approach, this is still a very stylized problem.\n- Related to the above, the obvious baseline would be some kind of RNN-policy, who is *not* informed of the action delay m. I would have thought this is a more practical general purpose approach, and should at least be considered and/or compared to.\n- The plots in Figure 4 could be improved in a few ways... add the labels for maze/cartpole/boxing next to the actual plots. Find a way to show the dropoff with performance not just for Cartpole but also maze/boxing.\n\nOverall I think the paper is a reasonable contribution, I'm generally a fan of these simple/clear pieces of work.\nHowever, I feel like the current paper is missing the \"elephant in the room\"... state of the art agents like R2D2 are *already* using recurrent policies... that surely has to be a reasonable baseline here?\nIf you can include that and discuss that well then I will upgrade to an accept.", "extra_scores": {}, "extra_text": {}}, {"review_id": "DfFPE_dTKsE", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents theoretical analysis of MDPs with execution delay together with an algorithm that achieves better performance on the task than the baselines. The main theoretical result highlights the need for non-stationary Markov policies that is different from standard MDPs that can be solved using stationary Markov policies.\n\n*Quality*\nThe authors conducted a solid theoretical study of MDPs with the execution delay. The presented claims showcase why the existing approach based on augmenting the state space is not feasible for large delays. The suggested algorithm is a based on a simple idea to estimate the state of MDP m steps in the future, but it seems to work quite well when the MDP is not too stochastic. Overall, this paper is a solid study of the problem with lots of potential research directions for the future work.\n\n*Clarity*\nThe paper is well-written in general. \n\n*Originality*\nTo my best knowledge, the results are new and the need for non-stationary policies is a novel highlight.\n\n*Significance*\nrather significant, execution delay is a common issue in practice and the paper lays foundations for analysis of MDPs with execution delay.\n\nPros\n* Theoretical analysis of ED-MDPs that guides the presented algorithm\n* Great results on Tabular Maze and Physical domain problems\n\nCons\n* No analysis on how the stochasticity of environment affects the performance of Delayed-Q\n* Atari results use the simulator to predict the future state", "extra_scores": {}, "extra_text": {}}, {"review_id": "AlPR4TZrPmE", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper reminds us of the problem of delayed interaction (in control or observation) with MDPs, provides two theoretical formulations of the problem, and then a deep RL-based approach. \n\nThis is an interesting problem that has not been much talked about in the recent literature as far as I know.  It seems plausible that it would come up in real situations although the paper only shows us artificially delayed versions of artificial problems.  The paper would be much stronger if it were to address some real applications (in which, for example, we could see whether the approximate predictive model works well enough).\n\nThe theoretical analysis of the augmentation approach seems reasonable (but I did not check the math).  However, since the m-AMDP is another MDP, could we not just use existing computation-time analysis of PI (or VI or LP-solving) applied to the m-AMDP?  Or, if this bound is smaller (because it's taking advantage of special structure in the mAMDP), that's cool, and it should be clearly pointed out.\n\nI wasn't quite clear on the contribution of the execution-delay MDP formulation.  It was interesting, but didn't seem to lead to any new algorithmic approaches (and in fact seems to present some substantial algorithmic challenges) and it isn't obvious to me what makes it better than the augmented formulation.   If it was intended to be a lead-in to Delayed-Q, then I didn't quite see the connection and it would be good to make it clearer.\n\nThe delayed-Q algorithm seems sensible.   I didn't understand the phrase \"this method relies on the environment not being entirely stochastic\".   Perhaps this is an allusion to the fact that it's using a determinized \"point\" prediction of the next state?  Although the paper makes it clear that this is an approximation, it would have been nice to have a concrete example of a kind of MDP where this is a particularly poor strategy (e.g., returning an \"average\" next state, which is actually impossible).\n\nAs I understand it, the delayed-Q method is relatively similar to MBS: more efficient (because it doesn't consider multiple state sequences), but potentially less accurate.\n\nIn summary, I would say the main algorithm is reasonable but perhaps not highly novel, and that the theoretical work in sections 4 and 5 does not seem to make a substantial contribution.  I think a promising direction would be to push toward some real application domains and let their demands drive the architectural and algorithmic improvements you need to address them.\n\n=== Update ===\nThe arguments in the rebuttal clarify some confusions I had and illuminate the contributions of the paper further.   I am now completely on the fence about acceptance, but will tip toward positive.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper analyzes MDPs with execution delays. Interesting theoretical results and experiments are provided, which show the benefits of the proposed algorithms. However, some issues are highlighted in the reviews, such as the lack of theoretical analysis of the proposed delayed Q-learning method, and the simplicity of the experiments. The latter is at least partially addressed by the authors in the rebuttal, and the new experiments should be incorporated in the final paper. 

Decision: Accept (Poster)