Reinforcement Learning with Random Delays
Authors: Yann Bouteiller
Simon Ramstedt
Giovanni Beltrame
Christopher Pal
Jonathan Binas
Venue: ICLR 2021 Poster (2021)
Keywords: Reinforcement Learning
Deep Reinforcement Learning

Abstract: Action and observation delays commonly occur in many Reinforcement Learning applications, such as remote control scenarios. We study the anatomy of randomly delayed environments, and show that partially resampling trajectory fragments in hindsight allows for off-policy multi-step value estimation. We apply this principle to derive Delay-Correcting Actor-Critic (DCAC), an algorithm based on Soft Actor-Critic with significantly better performance in environments with delays. This is shown theoretically and also demonstrated practically on a delay-augmented version of the MuJoCo continuous control benchmark.

Published as a conference paper at ICLR 2021
REINFORCEMENT LEARNING WITH RANDOM DELAYS
Yann Bouteiller*
Simon Ramstedt"
Polytechnique Montreal
Mila, McGill University s simon ramst teanstedde tedt @gma com
yann.boutei petputtelllr@pppll
aelerrrlllll ymt ymtl..llcc caa
Giovanni Beltrame Polytechnique Montreal
Christopher Pal Mila, Polytechnique Montreal
Jonathan Binas Mila, University Montreal
ABSTRACT
Action and observation delays commonly oceur in many Reinforcement Learning applications, such as remote control scenarios. We study the anatomy of randomly delayed environments, and show that partially resampling trajectory fragments hindsight allows for off- off-policy multi-step value estimation. We apply this principle to derive Delay-Correcting Actor-Critic (DCAC), an algorithm based on Soft Actor- Critic with significantly better performance in environments with delays. This is shown theoretically and also demonstrated practically on delay-augmenter version the MuloCo continuous control benchmark.
INTRODUCTION
Agent
This article is concerned with the Reinforcement Learning (RL) scenario depicted in Figure which is commonly encountered in real-world applications (Mahmood et al., 2018; Fuchs et al., 2020; Hwangbo et al., 2017). Oftentimes, actions generated by the agent are not immediately applied in the environment, and observations do immediately reach the agent. Such environments have mainly been studied under the unrealistic assumption of constant delays (Nilsson et al., 1998; Ge et al., 2013; Mahmood et al., 2018). Here, prior work has proposed different planning algorithms which naively try to undelay the environment by simulating future observations (Walsh et al., 2008; Schuitema et al., 2010; Firoiu et al., 2018).
action delay
diverration dalloy
Undelayed
Delayed environment
We propose an off-policy, planning- free approach that enables low- bias and low-variance multi-step value estimation in environments with random delays. First, we study the anatomy of such environ- ments in order to exploit their structure, defining Random-Ded Delay Markov Decision Processes (RDMDP). Then, we show how to trans-
Figure delayed
environment can be decomposed into an undelayed environment and delayed communication dynamics.
form trajectory fragments collected under one policy into trajectory fragments distributed according another policy. We demonstrate this principle by deriving a novel off off-policy algorithm (DCAC) based on Soft Actor-Critic (SAC), and exhibiting greatly improved performance delayed environments. Along with this work we release our code, including a wrapper that conveniently augments any OpenAl gym environment with custom delays.
DELAYED ENVIRONMENTS
We frame the general setting of real- Reinforcement Learning in terms of an agent, random observation delays, random action delays, and undelayed environment. At the beginning of each time-step, the agent starts computing new action from the most recent available delayed observation. Meanwhile, a new observation sent and the most recent delayed action is applied in the undelayed environment. Real-valued delays are rounded to the next integer time-step.
"qqual contribution

---

Published as a conference paper at ICLR 2021
constant delays
random dclays
ageni starts
compuring action
older action
aaciium diday 0
1+1
undelay Meniann
is appllied
obs. delay w
resulting observation
We
agent receives
0
1
2
0
previoous obs.
5
IS repeated
2
2
2
2
1
Figure 3: Influence of actions on delayed observations in delayed environments.
For a given delayed observation St, the observation delay Wi refers the number of elapsed time-steps from when s, finishes being captured to when it starts being used to compute new action. The action delay 0₁ refers to the number of elapsed time-steps from when the last action influencing 8, starts being computed to one time-step before finishes being captured. We further refer to wi + ar as the total delay of 8t-
Relative frequency
As motivating illustration of real-world delayed setting, we have collected a dataset of communication delays between decision- making computer and flying robot over WiFi, summarized in Figure 2. In the presence of such delays, the naive approach is to simply the last received observation. In this case, any delay longer than one time-step violates the Markov assumption, since the last sent action becomes unobserved part of the current state of the environment. To overcome this issue, we define a Markov Decision Process that takes into account the communication dynamics.
40%
30%
10%
0%
20
40
60
Round trip time ms
Figure 2: Histogram of real-world WiFi delays.
2.1 RANDOM DELAY MARKOV DECISION PROCESSES
To ensure the Markov property delayed settings, it necessary to augment the delayed observation with at least the last K sent actions. K is the combined maximum possible observation and action delay. This is required as the oldest actions along with the delayed observation describe the current state of the undelayed environment, whereas the most recent actions are yet to be applied (see Appendix C). Using this augmentation suffices to ensure that the Markov property is met certain delayed environments. On the other hand, it is possible to do much better when the delays themselves are also part the state-space. First, this allows us to model self-correlated delays, e.g. discarding outdated actions and observations (see Appendix A. Second, this provides useful information to the model about how old an observation is and what actions have been applied next. Third, knowledge the total delay allows for efficient credit assignment and off off-policy partial trajectory resampling, as we show in this work.
Definition A Random Delay Markov Decision Process RDMDP(E. = A, augments Markov Decision Process E (S, A, p) with: (1) state-space X = S x AK x N², (2) action-space A,
(3) initial state distribution (i( ju(s, a. (u() 6(u - cu) 8lw cw) 5(a Ca):
(4) transition distribution ş( .u' w aa s.u.w. a)) -f fw- ('',.''''''''rraaaraaa.a (a...aaa (w' ( (u' ( lu
where E S is the delayed observation,
A is buffer of the last K sent actions, E N is the observation delay, and a N is the action delay as defined above. To avoid conflicting with the subscript notation, most recent and u[K] is the oldest action the buffer. We denote slices by ui = (uff...., 4bl) and u((:-s] (u(i),-.. -. u/K u -j]). We slightly override this notation and additionally define ujo]
index the action buffers' elements using square brackets. Here, un] is the
2

---

Published as a conference paper at ICLR 2021
The constants Cu E A and Cu: Ca N initialize u. ",w,a, a, since 5 is the Dirac delta distribution. The transition distribution itself is composed of three parts: (1) The observation delay distribution Pa modelling the evolution of observation delays. Note that this density function must represent discrete distribution (i.e. be a weighted sum of Dirac delta distributions). Furthermore, this process will repeat observations if there are
ones available. This means that the observation delay can maximally grow by one from one time-step to the next. (2) The transition distribution for the action buffer Pu (u' [u, a) = ō('' (a, u(1:-11)). (3) The distribution fa describing the evolution of observations, rewards and action delays (Definition 2).
Definition 2. For each change in observation delays distribution fa as
w') we define a variable step update
[a(s' aa u''rr'ss,,uaa (ss.s,, () a -f- aumaaa) (psss ,r -r---"1 "u, ,u(w A -'o')) Pa (a ||") (1)
The base case of the recursion is f=1(s','' a',r s.u.wa = 8(s' - 8) 8(a' - a) 8(r').
Here, P., is the action delay distribution which, similar to Pa. must be discrete. The transition distribution of the underlying, undelayed MDP is p. The r' r* term accumulates intermediate rewards in case observations are skipped or repeated (see Appendix A.4). Since the observation delay cannot increment by more than one, f-1 is used when w is increasing, whereas fo is used when there is no change in observation delay.
simple special case of the RDMDP is the constant observation and action delay case with p., (w'lw) = 8(w' )w) and pa (a'la) = 5(a' ca). Here, the RDMDP reduces to Constantly Delayed Markov Decision Process, described by Walsh et al. (2008). In this case, the action and observation delays o, w be removed from the state-space they don't carry information. Examples of RDMDP dynamics are visualized in Figure (see also Appendix C).
REINFORCEMENT LEARNING IN DELAYED ENVIRONMENTS
Delayed environments as described in Section 2 are specific types of MDP, with an augmented state- space and delayed dynamics. Therefore, using this augmented state,space, traditional algorithms such as Soft Actor-Critic (SAC) (Haarnoja et al., 20 (a)arroa et al., 2018b) will always work in randomly delayed settings. However, their performance will still deteriorate because of the more difficult credit assignment caused by delayed observations and rewards, on top of the exploration and generalization burdens of delayed environments. We now analyze how to compensate for the credit assignment difficulty by leveraging our knowledge about the delays' dynamics.
One solution is to perform on-policy multi-step rollouts on sub-trajectories that are longer than the considered delays. On the other hand, on-policy algorithms are known to be sample-inefficiett and therefore are not commonly used in real-world applications, where data collection is costly. This motivates the development of aff-policy algorithms able to reuse old samples, such as SAC.
Intuitively, in delayed environments, one should take advantage of the fact that actions only influence observations and rewards after a number of time-steps relative to the beginning of their computation (the total delay w + a). Since the delay information is part of the state-space, it can be leveraged track the action influence through time. However, applying conventional off-policy algorithms in delayed settings leads to the following issue: the trajectories used to perform the aforementioned multi-step backups have been sampled under an outdated policy, and therefore contain outdated action buffers. In this section, we propose method to tackle this issue by performing partial trajectory resampling. We make use of the fact that the delayed dynamics are known to simulate the effect they would have had under the current policy, effectively transforming off- off-policy sub-tran -obbtarjectores into on-po on-policy sub- sub-trajectories. This enables us derive a family of efficient off aff-policy algorithms for randomly delayed settings.
3.1 PARTIAL TRAJECTORY RESAMPLING IN DELAYED ENVIRONMENTS
One important observation implied by Figure 3 is that, given the delayed dynamics RDMDPS, some actions contained in the action buffer of an off-policy state did not influence the subsequent delayed
3

---

Published as a conference paper at ICLR 2021
(z
8g
0g
640
a
80
a_3
80
600
81
W1
40
a"'
#1
%
9g
82
02
W
4
d
82
02
W2
%
(2
42
a]
%
x(a))
Figure 4: Partial resampling of small sub-trajectory. The action buffer is recursively resampled
according to the current policy (rewards are not modified by and are omitted here).
observations and rewards for a number of time-steps. Therefore, an off-policy sub-trajectory is short enough, it is possible to recursively resample its action buffers with influence the return. We propose the following transformation of off-policy sub-trajectories:
Definition 3. The partial trajectory resampling operator recursively updates action buffers as follows
( (s. ri, - $1, u1, wi, 01 ri, Tn-1)
= (1
(2)
with trivial base oo (=t)
This operator recursively resamples the most recent actions of each action buffer in an input sub- trajectory Tus according provided in Figure 4 with n = 2 and an action buffer of two actions. When resampled actions delayed and would not affect the environment, they do "invalidate" the sub-trajectory. The resampled trajectories can then be considered on-policy.
policy и. Everything else stays unchanged. A visual example
Theorem 1. The partial trajectory resampling operator of (Def. 3) transforms off- trajectories into on- policy trajectories
- pf (1aa) (T. =
(3)
on the condition that none of the delayed observations depend on any of the resampled actions, i.e.
: + a 2
(4)
where indexes the trajectory - (si wi wf
ai ri ri...... Sh un wn ah, r from 1 n.
The condition in Equation can be understood visually with the help of Figure 3. In the constant delay example it is fulfilled until the third time-step. After that, the observations would have been influenced by the resampled actions (starting with ag).
3.2 MULTI-STEP OFF-POLICY VALUE ESTIMATION DELAYED ENVIRONMENTS
We have shown in Section 3.1 how it is possible to transform off-policy sub- trjjecaaetssoies into on- mololicc sub-trajectories in the presence of random delays. From this, we can derive a family of efficient off off-policy algorithms for the randomly delayed setting. For this matter, we make use of the classic on-policy Monte-Carlo n-step value estimator:
Definition 4. The n-step state-value estimator is defined as
on (av: 2(, ri 70n-1 T
1- 12 + + (o
(5)
where úp is state- value function approximator (e.g. neural network).
4

---

Published as a conference paper at ICLR 2021
Condition Theorem
72
0
1
left
left
left
(intial state)
%
left
1+12
22:12
-1
left
left
2+122
1+1<8 X
-2
left
left
loft
11
Definiion
0
1
laft
left
left
of (x 12)
<i."]
0
disbi
left
left
10
debi
Dghtt
Detintion
(2(2)) T3)
+
+-(6n(
right
)))
=;
Figure 5: Visual example in a ID-world with random delays (K = 3). The original trajectory has been sampled under the policy μ:: "always go left', The current policy is "always go right'.
Indeed, y-discounted RL, performing on-policy n-step rollouts to estimate the value function reduces the bias introduced by the function approximator by factor of
Lemma 1. The n-step value estimator has the following bias:
bias(On +)) "E ... airt mnn (1 (Dins(
A simple corollary of Lemma is that the on on-policy n-step value estimator is unbiased when the function approximator d unbiased. On the other hand, Theorem provides recipe for transforming tub-trajectories collected under old policies into actual on-policy sub-trajectories, From a given state an off-policy trajectory, this is done by applying o, to all the subsequent transitions until meet total delay (w: + a;) that is shorter than the length of the formed uub-trajectory. Consequently, the transformed sub-trajectory can be fed the on-policy n-step value estimator, where is the length of this sub-trajectory. This does only provide better value estimate than usual 1-step off ofo-policy estimators according to Lemma 1, but maximally compensates for the multi-step credit assignment difficulty introduced by random delays. Indeed, the length of the transformed sub-trajectory is then exactly the number of time-steps it took the first action of the sub-trajectory to have influence on subsequent delayed observations, minus time-step.
As opposed to other unbiased n-step off off-policy methods, such as importance sampling and Retrace (Munos et al., 2016), this method doesn't suffer from variance explosion. This is because the presence of delays allows us to transform ooo-cc sub-trajectories into on on-policy sub-trajectories, so that old samples don't need be weighted by the policy ratio.
Although we use a multi-step state-value estimator, the same principles can be applied to action-vall value estimation as well. In fact, the trajectory transformation described Definition enables efficient off-policy n-step value estimation in any value-based algorithm that would otherwise perform 1-step action-valus backups, such as DQN, DDPG or SAC. the next section, we illustrate this using SAC.
Figure summarizes the whole procedure in simple ID-world example. The maximum possible delay is K 3 here, and the agent can only go 'left' or 'right'. An initial augmented state xo is sampled from the replay memory, along with the 3 subsequent augmented states and rewards. The condition of Theorem 1 is satisfied for n < policy trajectory fragment is partially resampled, which yields the corresponding on- on-policy trajectory fragment -" = Tÿ. This on on-pol trajectory fragment can then be used to compute an unbiased n-step value estimate of the initial state 2o 2
follows that 7, T2 = (x1, x2). This off-
5

---

Published as a conference paper at ICLR 2021
4 DELAY-CORRECTING ACTOR-CRITIC
We have seen in Section how it is possible, in the delayed setting. to collect off aff-policy trajectories and still use on-policy multi-step estimators in an unbiased way, which allows us compensate for the more difficult credit assignment introduced by the presence of random delays. We now apply this method to derive CorrecCon EctorCCritie (DCAC), an improved version of Soft Actor-Critic (Haarnoja et al., 201 8a;b) for real-time randomly delayed settings.
4.1 VALUE APPROXIMATION
Like SAC, DCAC makes of the entropy-augmmented soft value function (Haarnoja al., 2018a):
Lemma 2, In a RDMDP (E,, Pa,, the soft value function is:
2o (z)) -Bo)) (ag)) (it (1)))
can be estimated by augmenting the reward function in Definition with an entropy reward:
The delayed on- on-policy n-step soft state-value estimator, i.e. the n-step state-value estimator with entropy augmented rewards under the current policy म, is
Definition 5.
g5oft (=g - +7 sooft (a0-:110--:111 (21:7"11)-B (m [logr(a
(8)
where igoft is state-value function approximator (e.g. neural network).
Given the off-policy trajectory transformation proposed in Section 3, Definition directly gives DCAC's value target. To recap, sample initial state 2o (= a5)) and subsequent trajectory Tn (= Z1, Pl.... In, rn) from a replay memory. The sampling procedure ensures that n is the greatest length that the sampled trajectory Tn does not contain any total delay w; 3 i. This trajectory was collected under an old policy μu, but we need a trajectory compatible with the current policy
1:oft in unbiased way. Therefore, we feed 7n the partial trajectory resampling operator defined in Definition 3. This produces an equivalent on-policy sub-trajectory 7n with respect the current policy æ according
Theorem while maximally taking advantage the bias reduction described by Lemma 1. This partially resampled on-policy sub-trajectory is fed as input to 35eft (xo: ), which yields the target used in DCAC's soft value loss:
Definition 6. The DCAC critic loss is
L (v)
DCAC
E (=DD Erg~ot (1 ((110377.)) ( (xvs(=o) - ب (xo: +
where Tp. Tn are start state and following trajectory, sampled from the replay memory, and satisfying the condition of Theorem 1.
4.2 POLICY IMPROVEMENT
In addition using the on-policy n-step value estimator as target for our parametric value estimator, we can also use it for policy improvement. As in SAC we use the reparameterization trick (Kingma & Welling, 2013) to obtain the policy gradient from the value estimator. However, since we use our trajectory transformation and multi-step value estimator, this involves backpropagation through time in the action buffer.
Definition 7. The DCAC actor loss is
L
DCAC T
(ro.TT)) Brt~a (1120:)))) [6 (zo: [[
(10)
where To. F, are start state and following trajectory, sampled from the replay memory, and satisfying the condition of Theorem

---

Published as a conference paper at ICLR 2021
Proposition 1. The DCAC actor loss less biased version of the SAC actor loss with
(L. E,, [n bias( [
(11)
assuming both are using similarly biased parametric value estimators to compute the loss, i.e. bias( bias(e (z)) (z))) = E Ea [bias( (000 (2, a)]]
(12)
EXPERIMENTAL RESULTS
To evaluate approach and make future work in this direction easy for the RL community, release as open-source, along with our code, a Gym wrapper that introduces custom multi-step delays in any classical turn-based Gym environment. In particular, this enables us to introduce random delays to the Gym MuJoCo continuous control suite (Brockman et al., 2016; Todorov et al.), which is otherwise turn-based.
Compared algorithms. A naive version of SAC would only use the unaugmented delayed ob- servations, which violates the Markov assumption in delayed settings as previously pointed out. Consequently, naive SAC exhibits near-random results in delayed environments. A few such experi- ments are provided in the Appendix for illustration (Figure 9).
In order to make fair comparison, all other experiments compare DCAC against SAC in the same RDMDP setting, i.e. all algorithms use the augmented observation space defined in Section 2.1. Since SAC is the algorithm we chose to improve for delayed scenarios, comparing DCAC against it in the same setting provides like-for-like comparison. We also found it interesting to compare against RTAC (Ramstedt & Pal, 2019). Indeed, DCAAC reduces to this algorithm in the special case where observation transmission is instantaneous (w=0) and action computation and transmission constantly takes one time-step (a=l). Whereas DCAC performs -eiablle-ength state-value backups with partial trajectory resampling as explained in Section 4, RTAC performs 1-step state-value backups, and SAC performs the usual 1-step aation-value backup described in its second version (Haamoja et al., 2018b). All hyperparameters and implementation details are provided in Section B of the Appendix.
For each experiment, we perform six with different seeds, and shade the 90% confidence intervals.
HalfCheetahh-v2
Walker2d-v2
6000
average return
5000
average age return
4000
2500
4000
2000
3000
3000
2000
2000
1000
500
0-
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.0
0.2
0.4
0.6
0.8
1.0
million steps
millian steps
million
steps
Hopper-v2
Humanoid-v2
Reacher-v2
overage return
3000
8000
average return
-8
2000
-32
-14
1000
2000
SAC
0-
-18
RTAC
2.0
million steps
millian steps
million steps
Figure 6: 2, (constant delays). With constant total delay of five time-steps, DCAC exhibits very strong advantage performance. tested algorithms use the same RDMDP augmented observations.
7

---

Published as a conference paper at ICLR 2021
Ant-v2
HalfCheetah-v2
Walker2d-v2
2000
2500
4000
everage return
1500
2000
average return
1500
1000
2000
1000
500
1000
0-
0.0
0.5
1.0
1.5
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
million steps
millian stops
million steps
Hopper-v2
Humanoid-v2
Reacher-v2
averoge return
5000
average return
-0
4000
-10
3000
-12
2000
SAC RTAC
1000
0-
0.0
3.5
0.6
million steps
million steps
million steps
Figure 7: a, w WiFi (random delays), DCAC clearly dominates the baselines. Ant became too difficult for all tested algorithms. HalfCheetah also became difficult and only DCAC escapes from local minima.
Constant delays. Our first batch of experiments features simple, constantly delayed scenarios. Figure displays the results of the most difficult of these experiments (i.e. where the delays are longest), while the others are provided in Section D.2 of the Appendix. The advantage of using DCAC is obvious in the presence of long constant delays. Note that DCAC reduces to the RTAC (Ramstedt Pal, 2019) algorithm when = 0 and a 1 and behaves as evolved form of RTAC in the presence of longer constant delays.
Real-world random delays. Our second batch of experiments features random delays of different magnitudes. The experiment we chose to present in Figure 7 is motivated by the fact that our approach designed for real-world applications. Importantly, it provides an example how to implement DCAC in practice (see Appendix A and B for more details). We sample the communication delays for actions and observations from our real- weal-world WiFi dataset, presented in Figure 2. When action observation communications supersede previous communications, only the most recently produced information is kept. In other words, when action received in the undelayed environment, its age is compared to the action that is currently being applied. Then, the one that the agent most recently started to produce is applied. Similarly, when the agent receives a new observation, only keeps the one that was most recently captured in the undelayed environment (see the right-hand side of Figure for a visual example). We discretize the communication delays by using a time-step of 20ms. Importantly, note that Figure 2 has been cropped to 60ms, but the actual dataset contains outliers that can go as far as 1s. However, long delays (longer than 80ms our example) are almost always superseded and discarded. Therefore, when such information is received, we clip the corresponding delay with no visible impact in performance: in practice, the maximum acceptable delays are design choices, and can be guided by existing probabilistic timing methods (Santinelli et al., 2017).
RELATED WORK
We trace our line of research back to Katsikopoulos & Engelbrecht (2003), who provided the first discussion about Delayed Markov Decision Processes. particular, they were interested in asynchronous rewards, which provides interesting insights in relation to Appendix A.4. Walsh et al. (2008) later re-introduced the notion of "Constantly Delayed Markov Decision Process". While recent advances in deep learning enable implementations of what the authors call an "augmented approach", this was considered intractable at the time because the size of the action buffer grows with the considered delay length. Instead, they studied the case where observations are retrieved with constant delay and developed a model-based algorithm to predict the current state of the environment. Similarly, Schuitema et al. (2010) developed "memory-less" approaches based SARSA and vanilla
8

---

Published as a conference paper at ICLR 2021
Q-learning, taking advantage of prior knowledge about the duration of a constant control delay. Hester & Stone (2013) adopted the action buffer-augmented approach to handle random delays, and relied a decision-tre algorithm to perform credit assignment implicitly. By comparison, approach relies on delay measurements to perform credit assignment explicitly. More recently, Firoiu al. (2018) introduced constant action delays video game train agents whose reaction time compares to humans. Similar to previous work, the authors used state-predictive model, but based on recurrent neural network architecture. Ramstedt & Pal (2019) formalized the framework of Real-Time Reinforcement Learning (RTRL) that we generalize here to all forms of real-time delays. Initially designed to cope with the fact that inference not instantaneous in real-world control, the RTRL setting is equivalent to constantly delayed MDP with 1 and = O. Finally, Xiao et al. (2020) adopted an alternative approach by considering the influence of the action selection time when action selection is performed within the duration of larger time-step. However, their framework only allows delays smaller than one time-step, whereas large time-steps are not compatible with feeh-fre control.
7 CONCLUSION AND FUTURE WORK
We proposed deep off-policy and planning-fire approach that explicitly tackles the credit assignment difficulty introduced by real-world random delays. This is done by taking advantage of delay measurements in order to generate actual on-policy sub-trajectories from off-policy samples. In addition, we provide a theoretical analysis that can easily be reused to derive a wide family of algorithms such DCAC, whereas previous work mostly dealt with finding approximate ways of modelling the state-space in constantly delayed environments. The action buffer is fundamentally required to define a Markovian state-space for RDMDPS but it is of course possible to observe this action buffer approximately, e.g. by compressing it in the hidden state of an RNN, which is complementary our work.
We have designed our approach with real-world applications in mind, and it is easily scalable to wide variety of scenarios. For practical implementation, see Section 5 and Sections and B of the Appendix. See also rtgym, small python helper that we use in future work to easily implement delayed environments the real world.
To the best of our knowledge, DCAC is the first deep actor-critic approach to exhibit such strong performance on both randomly and constantly delayed settings, as it makes use of the partially known dynamics of the environment to compensate for difficult credit assignment. We believe that our model can be further improved by making use of the fact that our critic estimates the state-value instead of the action-valus function. Indeed, in this setting, Ramstedt & Pal (2019) showed that it is possible to simplify the model by merging the actor and the critic networks using the PopArt output normalization (van Hasselt et al., 2016), which did not try yet and leave for future work.
Our approach handles and adapts to arbitrary choices of time-step duration, although in practice time-steps smaller than the upper bound of the inference time will require few tricks. We believe that this approach is close to time-step agnostic RL and will investigate this direction in future work.
ACKNOWLEDGMENTS
We thank Fierre-Yves Lajoie, Yoshua Bengio and our anonymous reviewers for their constructive feedback, which greatly helped improve the article. We also thank ElementAI and Compute Canada for providing the computational resources we used to run our experiments.

---

Published as a conference paper at ICLR 2021
REFERENCES
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint arXiv:1606.c 01540, 2016.
Vlad Firoiu, Tina Ju, and Joshua B. Tenenbaum. human speed: Deep reinforcement learning with action delay. CoRR, abs/18 00t/18800072285 10.072286, 2018.
Florian Fuchs, Yunlong Song, Elia Kaufmann, Davide Scaramuzza, and Peter Duerr. Super-human performance in gran turismo sport using deep reinforcement learning, 2020.
Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. arXiv preprini arXiv: 1882.094777 2018.
Yuan Ge, Qigong Chen, Ming Jiang, and Yiqing Huang. Modeling of random delays in networked control systems. Journal of Control Science and Engineering, 2013, 2013.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maxi- mum entropy deep reinforcement learning with a stochastic actor. arXiv preprint arXiv:1801.0122 2018a.
Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, et al. Soft actor-critic algorithms and applications. arXiv preprint arXiv: /8/2.05925 2018b.
Todd Hester and Peter Stone. Texplore: real-time sample- reinforcement learning for robots. Machine learning, 90(3):385 4298855------ 2013.
Jemin Hwangbo, Inkyu Sa, Roland Siegwart, and Marco Hutter. Control of quadrotor with reinforcement learning. IEEE Robotics and Automation Letters, 2(4):209--2033, 2017.
Konstantinos Katsikopoulos and Sascha E Engelbrecht. Markov decision processes with delays and asynchronous cost collection. IEEE transactions automatic control, 48(4):568 574, 2003.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980 2014.
Diederik P Kingma and Max Welling. arXiv: 2013.
Auto-encoding variational bayes.
arXiv preprint
A. Rupam Mahmood, Dmytro Korenkevych, Brent Komer, and James Bergstra. Setting up a reinforcement learning task with real-worlds robot, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.
Remi Munos, Tom Stepleton, Anna Harutyunyan, and Mare Bellemare. Safe and efficient off-policy reinforcement learning. In D. D. Lee, M. Sugiyama, U. V. Luxburg. I. Guyon, and R. Gamett (eds.), Advances Neural Information Processing Systems 29, pp. 1054-1062. Curran Associates, Inc., 2016.
Johan Nilsson, Bo Bernhardsson, and Bjöm Wittenmark. Stochastic analysis and control of real-time systems with random time delays. Automatica, 34(1):57-64, 1998.
Simon Ramstedt and Christopher Pal. Real-time reinforcement learning. In NeurIPS, 2019.
L. Santinelli, F. Guet, and J. Morio. Revising measurement-basee probabilistic timing analysis. In 2017 IEFE Real-Time and Embedded Technology and Applications Symposium (RTAS), pp- 199-208. 2017.
Erik Schuitema, Lucian Busoniu, Robert Babuska, and Pieter Jonker. Control delay in reinforcement learning for real-time dynamic systems: A memoryless approach. In International Conference on Intelligent Robots and Systems, 2010.
10

---

Published as a conference paper at ICLR 2021
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. in 2012 ieee. In RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double learning, arXiv preprint (rX.vv:509000400 2015.
Hado van Hasselt, Arthur Guez, Matteo Hessel, Volodymyr Mnih, and David Silver. Learning values across many orders of magnitude. In Advances in Neural Information Processing Systems, pp. 4287 4295, 2016.
Thomas J. Walsh, Ali Nouri, Lihong Li, and Michael L. Littman. Learning and planning in en- vironments with delayed feedback. Autonomous Agents and Multi-Agent Systems, 18:83-105, 2008.
Ted Xiao, Eric Jang. Dmitry Kalashnikov, Sergey Levine, Julian Ibarz, Karol Hausman, and Alexander Herzog. Thinking while moving: Deep reinforcement learning with concurrent control. In International Conference on Learning Representations, 2020.

---

Published as a conference paper at ICLR 2021
A PRACTICAL CONSIDERATIONS AND SCALABILITY
A. SELF-CORRELATED DELAYS
The separation between w and a allows auto-correlated conditional distributions on both delays. This is necessary to allow superseded actions and observations be discarded. In RDMDPS the agent keeps the delayed observation that was most recently captured in the undelayed environment. Ideally, it is also ensured by the undelayed environment that the applied action is the action that most recently started being computed by the agent. In practice, this can be ensured by augmenting the actions with timestamps corresponding
the beginning of their computation, and observations with timestamps corresponding to the end of their capture. Thus, the undelayed environment and the agent can keep track of the most recent received timestamp and discard outdated incoming information.
A.2 HOW TO MEASURE DELAYS
To measure the delays in practice, one possibility is to make use of the aforementioned timestamps. In addition to the augmentations described in A. one can augment each observation sent by the undelayed environment with the timestamp the action that was applied before the end of observation capture. When the agent receives an observation, this observation then contains two timestamps: one that directly corresponds to an action in the buffer (agent's 's clock), and one that corresponds to when the observation finished being captured (undelayed environment's 's clock). The identified action the buffer directly gives the total delay. If the agent and the undelayed environment have e.g. synchronized clocks, the current timestamp minus the timestamp corresponding observation capture gives the observation delay (and thus we can deduce the action delay).
A.3 SCALABILITY OF THE ACTION BUFFER
As seen in our WiFi experiment, the maximum delays are design choices in practice. The actual maximum delays can be prohibitively long (e.g. infinite when packets are lost) and would require long action buffer to be handled in the worst-case scenario. However, in random delays scenarios, long delays are likely to be superseded by shorter delays. Therefore, observations reaching the agent with total delay that exceeds the chosen K value should simply be discarded, and procedure implemented to handle the unlikely edge-case where more than such observations are received in a row. Also note that, although we used simple action buffer in this work, more clever representations are possible in the presence of long delays, e.g. run-length encoding.
A.4 DELAYED REWARDS
We have implicitly made a choice when defining the rewards for RDMDPS. Indeed, keep in mind that observations can be dropped (superseded) at the level of the agent. In such cases, we chose to accumulate the rewards corresponding to the lost transitions. When an observation gets repeated because no new observation is available, the corresponding reward is 0, and when a new observation arrives, the corresponding reward contains the sum of intermediate rewards in lost transitions.
In practice, this is ensured for example by making the assumption that the remote robot (i.e. the undelayed environment) can observe its own instantaneous reward. This allows the robot to compute its cumulative reward and send it to the agent along with the observation. The agent can then compute the difference between the last cumulative reward it received from the remote robot and the new one for each incoming observation (NB: outdated observations are discarded so the agent only sees cumulative rewards with time-increasing timestamps).
Alternatively, the practitioner can choose to repeat the delayed rewards along with the repeated delayed observations the level of the agent (this is what we to do in earlier versions of the paper). When a trick similar to the aforementioned cannot be implemented, this can be done instead, with impact on analysis. However, the reward signal will inherently have higher variance.
12

---

Published as a conference paper at ICLR 2021
A.5 LONG OBSERVATION CAPTURE
In practice, it often the case that observation capture is not instantaneous. In such situation, one should increase the size of the action buffer so that it always includes the actions for which it is unclear whether they have influenced the observation yet or not. Indeed, when observation capture is not instantaneous it is not possible to know which undelayed state(s) it describes. The length of the multi-step backup performed by DCAC doesn't t need to be adapted, because only cares about the first action that is known not have influenced the delayed observation.
A.6 COMBINED OBSERVATIONS
Equivalently, if observations are formed of several combined parts that were captured at different times, the action buffer must be long enough to always include the first action that has not influenced the oldest sub-observation yet (i.e. be as long as the maximum possible combined total delay).
B IMPLEMENTATION DETAILS
B. MORE INFORMATION INPUT TO THE MODEL
The action delay a identifies the action that was applied during the previous time-step. is needed define RDMDPS and thus is used by DCAC. However, practice we can include another piece of information top of a: the delay of the action that is going to be applied in the undelayed environment when the captured observation sent. We use this additional information as input of the model for all tested algorithms.
B.2 MODEL ARCHITECTURE
The model we use in our experiments is composed two separate multi-layer perceptrons (MLPs): critic network, and an actor network. Both MLPs are built with the same simple architecture of two hidden layers, 256 units each. The critic outputs a single value, whereas the actor outputs an action distribution with the dimension of the action-space, from which actions sampled with the reparameterization trick. This architecture is compatible with the second version SAC described in Haarnoja et al. (2018b). The only difference from the DCAC model is that the critic tracks q(x), and not v(x). Indeed, differently from usual actor-critic algorithms, the output of DCAC's critic approximates the state-value v(x) (instead of the action-value (xx)), it sufficient optimize the actor loss described in Definition 7. Weights and biases are initialized with the default Pytorch initializer. Both the actor and the critic are optimized by gradient descent with the Adam optimizer, on losses T,CCAC (T) (Equation 10) and 7, (,CAC()) (Equation 9), respectively. Classically, we use twin critic networks (Van Hasselt al., 2015; Fujimoto al., 2018) with target weight tracking (Mnih et al., 2015) to stabilize training.
B.3 HYPERPARAMETERS
Other than our neural network architecture, our implementations SAC, RTAC and DCAC all share the following hyperparameters:
13

---

Published as a conference paper at ICLR 2021
Table 1: Hyperparameters
Name
Value
Optimizer
Adam (Kingma & Ba, 2014)
Learning rate
0.0003
Discount factor (?)
0.99
Batch size
128
Target weights update coefficient (r)
0.005
Gradient steps environment steps
1
Reward scale
5.0
Entropy scale
1.0
Replay memory size
1000000
Number of samples before training starts
10000
Number of critics
2
NB: the target weights are updated according the following running average: 0 + r8 + (1 (1-r)0
C
VISUAL EXAMPLES
Constant delays
Random delays
Agent
Agent
Qt-5
04.-5
Q;-4
0/-3
01-11
Qx-2
(2)
(3)
w112)
(213)3
8t
(Dc-5)
Gr-2
(ax-1)
86-1
(oc-4)
(ac-s)
4;-3
(ac-a)
(or-2)
Undelayed environment
Undelayed
Example of Constantly Delayed MDP, with an action delay of three time-steps and an observation delay of two time-steps. Here, actions are indexed by the time at which they started heing produced. The augmented observation is composed of action buffer of the last five computed actions along with the delayed observation 8:-2. It will be used by the agent compute action a, Meanwhile. environment, action a--a is received and observation &t is captured. Right: Example of Random Delay MDP, with a < time-steps and w < 2 time-steps. Actions and observations may be superseded due to random delays, In such cases, only the most recently produced actions and observations are kept, the others are discarded (crossed out).
Figure 8: Left:
undelayed
14

---

Published as a conference paper at ICLR 2021
D ADDITIONAL EXPERIMENTS
D.1 IMPORTANCE OF THE AUGMENTED OBSERVATION SPACE
Ant-v2
HalfCheetah-v2
Walker2d-v2
average return
return
6000
average return
3000
4000
2000
2000
1000
SAC naive
0
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.9
1.0
0.0
0.2
0.4
1.0
mill lon steps
million steps
million steps
Figure 9: w 0, a 1: We illustrate the importance of the augmented observation space in delayed settings using our simplest task (constant 1-step action delay). Even with this small 1-step constant delay, the delayed observations are not Markov and a naive algorithm using only these observations (here: SAC naive) has near-random results. By comparison, an algorithm using the RDMDP augmented observations instead (here: SAC) is able to learn in delayed environments.
D.2 CONSTANT DELAYS
Ant-v2
HalfCheetah-v2
Walker2d-v2
10000
6000
average return
8000
average return
2000
3000
3000
4000
2000
1000
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.5
0.8
1.
steps
steps
steps
Hopper-v2
Humanoid-v2
Reacher-v2
average return
3000
5000
average return
-10
4000
2000
-30
1000
2000
-40
-50
0
0.2
mill lon steps
million stops
million stops
Figure 10: w 0, 1: This specific setting is equivalent to the RTRL setting (Ramstedt & Pal, 2019), in which DCAC reduces to the vanilla RTAC algorithm (without output normalization and merged networks). DCAC (RTAC) slightly outperforms SAC in this setting.
15

---

Published as a conference paper at ICLR 2021
Ant-v2
HallCheetah-v2
Walker2d-v2
5000
average return
return
average return
8000
3000
6000
3000
2000
4000
2030
2000
1030
0
0.0
1.0
0.6
0.0
1.0
million steps
million steps
million steps
Hopper-v2
Humanoid-v2
Reacher-v2
average return
return
5000
-7.5
-10.0
2000
4000
-12.5
1000
2000
-17.5
RTAC
0-
-20.0
0.0
1.0
1.5
2.0
0.5
1.0
1.5
2.0
2.5
3.0
5
million stops
million steps
million stops
1e-1
Figure 11:
a 2: In this more difficult setting (total constant delay of instead of 1), DCAC starts really showing its potential, clearly outperforming all other approaches.
D.3 RANDOM DELAYS
Ant-v2
HalfCheetah-v2
Walker2d-v2
2000
average return
1500
3000
average return
2000
1000
1000
0.00
0.25
0.50
0.75
1.00
125
1.50
0.0
0.2
0.4
0.6
0.8
1.0
1.2
0.00
0.25
0.50
0.75
1:00
1.25
150
millian
million stops
million steps
Hopper-v2
Humanoid-v2
Reacher-v2
average return
average return
4000
-10.0
average
3000
2000
-15.
SAC
1000
-17.
DCWC
-20.3
0.55
0.75
1.25
0.00
0.25
0.50
1.55
1:50
million steps
million steps
million steps
Figure 12: E 2), E [1;3] (uniformly sampled delays): This experiment is perhaps even more difficult than the WiFi experiment featured the main paper, because gives equal probability to all possible delays in the specified ranges (but delays are smaller here which makes it casier for RTAC, because these delays are closer to 1). All tested approaches fail on randomly delayed Ant. For other tasks, the advantage of DCAC is very clear over SAC.
16

---

Published as a conference paper at ICLR 2021
E DEFINITIONS
Definition 8. The n-step state-reward distribution for environment E = (S, 14, and a policy и is defined as
Pu+1 (s','' Tn (s) = Ba (')pss''''prrrsssss""s"" = / (T alsssa)t(als)dd (13)
Ta+11
with the base case pi (s) = and the first iterate ( r'1s) p(6', ())
Definition 9. A 1-step action-value estimator is defined
qn (s;a; s' (r/==r++> (=))=())))))))))))))))))))))))>) (0000 (sssa'' ,a')].
(14)
Part of this estimator is usually another parametric estimator qu (e.g. a neural network trained with stochastic gradient descent).
F OTHER MATHEMATICAL. RESULTS
F.1 LEMMA ON STEADY-STATE VALUE ESTIMATION BIAS
Lemma 3.
The expected bias of the n-step value estimator under the steady-state distribution (if it
exists)
Egspp bias ir (x)) E [bias (o(x))
(15)
Proof.
We remind ourselves that the steady state distribution observes
(rx)) = Exo-pI ( In, (n|20)]]
(16)
According to Lemma we then have
Exa-pg bias (xo, -) => E.... (aa (bias
(17)
=7 " [bias (o(r)).
(18)
F.2 LEMMA ON DIRAC DELTA PRODUCT DISTRIBUTION
Lemma 4. For p(u, v) = 6(u - c)q(u, v) if quu v) < oc for u = then (hhenpppuuuu v) = 8(u -cg((, v).
Proof. If c then p(u, v) 5(u - c))(c, v), otherwise p(u, v) 5(u ((qcc)q(c,v) v)
F.3
LEMMA FN
Lemma 5. The dynamics described by f depend neither the input action range of actions in the action buffer:
Sa (sf of rilzo, a fa (s), aj, rf ( ag)
with Zo So. No. wa. Cgg and z sū. ug wh. ag. given that wo, ap sū wp, ag and given
uolwō
8 a;
u Wا 8 + aj] for all 8 (A.A -
Proof. We prove by induction.
The base (w) w| -1) is trivial since it does not depend the inputs that differ.
17

---

Published as a conference paper at ICLR 2021
For the induction step have
[s 0i, 80s Nos wo, Old, aij
B, (-0.aat(11l..s.o..oooom atg .n. [p( - -F83, ulwo A + +a]) Po (ajla) (19)
Because of our condition on un and ug and the fact that win = wi this is equal to
R 8.8.P=ffaii (-
wa..ttt.aa [p(s], rf F|8, 1 - A ail) (aila)
We the induction hypothesis since the conditions so, uo w0, Onp still met when f
B fa 16 -3) (p(ss F|3, u5lun A + + Pa(ajlā)
fa af ri, 05)
(20)
F.4 LEMMA ON PARTIAL RESAMPLING
Lemma 6. Partially resampling trajectories collected under a policy μ according to o," transforms them into trajectories distributed according to
(T aas (x,0
with Zo 8o. No wo, dg and z sh. Mi wi, ag. the condition that so, wo, ag- s wij ag and on the condition that the actions the initial action buffers un and un that are applied in the following trajectory the same, i.e.
uolk: end] uolk: end] with h min(w[+1 + a -) for iE (0, 1}
and for the trajectory h, = (sj. un, wi, .i..... sn un wh, a.)).
Proof. We start with the induction base for n 0. The theorem is trivial in this case since have O-length trajectories () and (0(zo) o% [=: () p0 (0lz)) = 1.
For the induction step start with the left hand side of the lemma's main equation.
E, Npai (-z)) (0 Tn)
Bag~attlzn (z0) (E (moaaf) Bra-wpy (o m
(21)
with
pl 81, U1, 4i, 0.1,
8o. uo. wl, oo. an)) = fao-wy (81, on Ti So. Uns wo. coo a!") Pa (wi) (wo) pr (ui uuo a
Plugging that and solving the integral over un yields
Eog~u((lan (Burapp (wm) (B wi ("030.0..""0.00..0) ( (T pn 81, 81, (a", un
E B endee and (l
wi, onl Yi, Tu- .)I]]] (22)
Rolling out of by step and integrating out 81, w1, 01,77 yields
18

---

Published as a conference paper at ICLR 2021
E ofj (olaallooo (1)a)) 1aa-- (-lasi uoll: (: ai)) [Bag ~ -x(1)=)))))0))))))))))))))))))) - (ag 45ll -1j))
o (T |s| ui wi, afl: (wo (sî, of ; ri (u. uo. wa, ao, ab) Pa (wم (23)
Reordering terms and substituting 8o, wo, oz sú, wi, og yields
Pw (Wf (og ((( (1 (aï uill - -1])
Bag (ntg)u(-)mo)la Long -wi (si, aj, ri at)
E 1mph 1-Bii -a]::
(24)
We can substitute the / term according to Lemma 5 since the condition between zo and vū is met. More precisely the condition on up and ug is met because l I w A a = wi af After the substitution we have
(w (())))))))))))))))))))))))))))) ( [ō(ui (aā ugll 1))) fuj -wi aj. a5)
Bf ~u (mo)
T -n -لل::=-]) o (T ( Tn-1)ll (25)
We can substitute the induction hypothesis in the following form.
E, 1- ( (n = Ph-1(Th-11 1x;))
on the condition that
u1 [k: end] = uil [A: end]
with h = min(w[+2 + osf2 - i) for i {0, n 2
for the trajectory 7 (sž, uy wh, og. ..... t u w a.)) To check that this condition met observe that #1 (al uo -]) and substitute oi (aā "0[1 -1]) (made possible by Lemma 4) which means that
wolk - end end] = ug(k: 1 end] with A = min(wi42 ai+2 -) for ie {0, 2}
Substituting the induction hypothesis yields
~((l)))))))) (1)1)))))0000 -a uo[1 - -1)) Suy fog-e; ( a5) pā- 15-1(7h-1127) [=1)
(26)
which is
Eag -
11 1o 17 p( (aiirrila a5)1 = pT(T7
G
PROOFS OF THE RESULTS FROM THE MAIN PAPER
A
Theorem 1. The partial trajectory resampling operator of (Def. transforms off-policy trajectories into on-policy trajectories
19

---

Published as a conference paper at ICLR 2021
on the condition that none of the delayed observations depend any of the resampled actions, i.e.
wi + a
(4)
where indexes the trajectory T = (si |i ri...., Wh, r.)) from 1 to
Proof. The theorem is special condition in the lemma as we show next.
of Lemma 6 with 2o zz- This allows simplify the
Since uo ug we can allow all k 2 which is the minimum allowed index for u. Therefore must ensure 1 S. (wn + a;+1 z). Since the min must be larger than then all arguments must be larger than which means this equivalent
1 wh+ + +,411 -i for i {0, n - 1}.
This can be transformed into
w + a 2t for tE [1,n}
(27)
Lemma 1. The n-step value estimator has the following bias:
bias(On (zo, 1) n t opr
Proof.
bias 0n bias(On
(No. :) (o , vz (zo))
(28)
Er::r (rt 1 Eagaz( so) (0 + 700 (x;))
(29)
Erg-nt() Ir 1 - - -0 (x;))
(30)
:B [6 (af: vr (xf)]
(31)
(32)
B - (1 (+0(())) 0"' (x
(33)
"E r ~ (11m)) [bias( 0n (z.;,,,
(34)
B
Lemma 2. In RDMDP (E, Pa) the soft value function is:
sonl (xi)=Ba>r((e))) [Eng (15.a) +oy (ogT
(7)
Proof.
The soft value function for an environment (X, A, F. defined as
n0 (x²)==B F (1 soft (x).a) log (a|x;))
(35)
where
sonl ( a)
+ (,000((222)
(36)
If (X, A. = RDMDP E, Pw: Pa.) = (X, A, n. P) with E (S, A, this is
q soft
17 (ai))
(37)
and
(0ol(
Eg wt) Bn oo (x+)) log (a)=;))
(38)
n
20

---

Published as a conference paper at ICLR 2021
Proposition 1. The DCAC actor loss is less biased version of the SAC actor loss with
bias(L E, [h]] (
(11)
assuming both are using similarly biased parametric value estimators to compute the loss, i.e.
bias( (z)) = (a) @0 (z, a))]
(12)
Proof. Note that for simplicity, we also assume that the states the replay memory are distributed according to the steady-state distribution, i... D P This assumption could be avoided by making more complicated assumptions about the biases of the state-value and action-value estimators.
We now start with the bias of the DCAC loss with respect to unbiased SAC loss using the true action-value function,
bias(L
DCCAC L
(39)
where
T,DAAC Rg Begnon (112ur (1 (00s 7i)
(40)
Eng B,, E upt (-120) [0 (xo; TH)
Theorem
(41)
and
SAC UB =B (Baw x (a(3r)) - (roo a)]
(42)
= BRooD (v (2o)].
(43)
Substituting these we have
bias (CCAC)
- -Bzg En Enloon (zo:
(2o: Tna) - wooll (zo))
(44)
= EEzo D En collbbsss() (2 (Fo: -)!
(45)
Exxo D Enly"E R B. (1)() [bias( (1 (x,)))] -Bn[7"] Exa n (ias (x)))()))) (x))
Lemma 1
(46)
using pi, and Lemma
(47)
-En[?"] E Ea [bias( (x, a)]l
Equation 12
(48)
=Bn[>"] BEED |a (112) csooft (x. a) g (z, a)]
(49)
_E,[>"] (L L
(50)
-Enly"
[] bias(LEA))
(51)
21


Reviews:
[{"review_id": "yt2DVR4ijsE", "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": "Summary:\nThe paper introduces an algorithm for the case where actions have delayed effects in RL, and specifically in the case where the delay is random.  A resampling approach is applied to off policy buffered data in order to align it with the current policy and this approach is integrated into a SAC architecture, creating the new DCAC algorithm.  Empirical results in constant-delay and random-delay environments show the algorithm outperforming baselines.\n\nReview:\nThe strongest part of the paper are the empirical results, which clearly show the approach has merit over an augmented solution and an algorithm built for one step delays.  The approach is also strong because it deals with random delays which are not as well studied in the literature (though an older related work was missed there, see below).\n\nThe weakness of the paper is the lack of clarity in the description of the Algorithm itself and particularly in the crucial resampling operator in Definition 3, which is very unclear and makes the solution irreproducible with the current description.  In comparison to related work, the authors claim they are the first to deal with random delays but this is incorrect – Texplore (Hester and Stone) dealt with this situation and there is older work (cited below) that also addressed this problem.  In addition, an empirical comparison to Firoiu et al.’s approach, which is the state of the art in Deep RL for constant delayed observations is needed in the first set of experiments.\n\nDetailed Notes:\nThe heart of the paper is Section 3.1, which describes the overall algorithm, but unfortunately this section is very difficult to understand.  The confusion begins in the first paragraph of section 3.1 on the bottom of page 3.  The discussions of actions that do not affect observations is too high level and it is unclear what situation exactly the authors are referring to.  A concrete example, even in a simple domain, could make the author’s point clear – can you provide such an example?\n\nDefinition 3, the resampling operation, is the most important part of the paper, but it is unclear what is actually happening here.  Is sigma returning a probability of replacing one term with another, or is it a mapping?  What exactly is the delta term doing or is it a function?  And more conceptually, how does this replacement work if two policies don’t share actions at a state?  If the policy that generated in the data in the buffer is “always do action 1” and the new policy is “always do action 2”, resampling is impossible right?  The whole procedure should really be written as pseudocode to make the algorithm reproducible and analyzable. \n\nI found the motivation for the resampling also hard to follow.  Why is on-policy data even needed here?  SAC, as I understand it, is an off-policy algorithm so it should be able to handle off policy samples.  And the delayed observations are the result of the actual actions taken, independently of the policy that produced them.  So can’t one compute the estimated states from the stored actions and provide that data to SAC?  Why is resampling even needed?\n\nRelation to existing work:\nFiroiu et al.’s approach should appear in the empirical comparisons on constant-delayed MDPs.  That work is the state of the art on Deep RL with constant delays and while the new algorithm deals with random delays, since there is a constant-delay testbed described here, a comparison is warranted, especially because the overmatched baselines are similar between the current work and Firoiu et al.’s\n\nTwo references that were missed but seem highly relevant since they dealt with random delays:\nTEXPLORE: real-time sample-efficient reinforcement learning for robots (Hester and Stone) – builds a decision tree representation of delay effects to generalize and deal with non-constant delays.  This solution should be compared to in some way.\n“Markov decision processes with delays and asynchronous cost collection” by Katsikopoulos, & Engelbrecht (2003) was the first paper to study random (non-constant) delays in MDPs and should be correctly cited here as the seminal work.  \n\nFinally, the description of the prior work in the introduction as “proposing on-policy planning algorithms” does not make sense.  First, planning algorithms by their definition are off-policy since they create new policies.  Secondly, several of the approaches in the referenced works, including Walsh et al. use off-policy algorithms, so that characterization seems incorrect.\n\nMinor notes:\nPage 3 – ‘their performance will still deteriorate because of the more difficult credit assignment’ – that is only part of the problem.  The augmented space also causes significant exploration and generalization burdens.\nPage 3 - `One solution is to perform on-policy multi step rollouts’ – I don’t see this as a “solution”.  It will certainly generate helpful information, but simply doing rollouts is not an algorithm.  What do you do with them?  How do you combine them?  This is not a good point of comparison because it is not a full procedure.\nPage 5, second line – the formed the sub trajectory (fix one of ‘the’ instances)\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "KVBDzmNOdTe", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Post rebuttal: The updates clearly explain the resampling procedure of this paper, and strengthen the theoretical part of this paper. As a result, I'd like to change my rating to 6 and recommend an acceptance.\n\nAdditional thoughts emerged from the discussion with authors (which are irrelevant to the rating): I agree that experiments in the paper demonstrate the modified SAC algorithm has a significant improvement compared to baseline algorithms. And I believe that the paper could benefit from including some theoretical justifications to the loss function and data collection scheme (though I completely understand the difficulty of theoretically justify deep RL algorithm). For example:\n- Assuming all the loss functions can be optimized to optimal, will the policy converge to optimal or near-optimal solutions?\n- Assuming the value net can be optimized to optimal, how the resampling process change the gradient of policy net? In which case would the on-policy sample with truncated trajectory (i.e., the value function computed by Eq. (8) where the length of the trajectory is $n$) out-perform off-policy sample with full trajectory (i.e. SAC without resampling)? If I understand correctly, without resampling the error of the value net suffers from the amplification caused by distribution mismatch (which is potentially exponential?). And with resampling, would the error of value net come from the truncation?\n\nAdditional minor issues:\n- Definition 5: There is no base (i.e., $n=0$) in the recursive definition of $\\hat{v}_n^{soft}$.\n\n---------\nThe paper considers reinforcement learning with delays, motivated by real-world control problems. Novelty of the setting is that the delay is random and changing. Algorithm proposed by the paper uses importance sampling to create on-policy samples of augmented observations, and is empirically shown to out perform base line SAC algorithm.\n\nWhile the idea of the paper is clean, I found it a bit hard to follow the complicated notations and definitions without intuition explanation. I appreciate the effort of making the paper mathematically rigorous, but I believe that the paper could be more easy-to-follow and have a larger impact to the community if there were more explanations before/after each definition, especially when the math behind this paper is not super complicated.\n\nSome additional questions:\n1. What is the observation if the delay decrease by more than one? If I understand correctly, does Eq. (1) imply that the agent can only observe the last state? In other words, suppose there are some delay of the network such that there are no observations for 5 time steps, and after that all the network packages arrive at the same time. Will the agent discard the information of time steps 1, 2, 3 and 4?\n2. In order to have a Markovian transition, definition 1 requires $K$ being the maximum possible total delay. However, Theorem 1 assumes that total delays are longer than the trajectory. Does it imply that $w_i+\\alpha_i$ is a constant? Otherwise at least one of the assumptions can not be true.\n3. I couldn't follow the proof of Theorem 1 (and Lemma 6). In Definition 3, Eq. (2), what is $u_0^*$? For the induction in Lemma 6, what is the induction base? If I understand correctly (please correct me if I'm wrong), the operator $\\sigma_n^\\pi(\\tau_n^\\star\\mid x_0;\\tau_n)$ is similar to probability ratio in standard importance sampling method, and can only assign non-zero value to trajectories $\\tau_n^\\star$ such that $s_i^\\star=s_i,\\forall i$. If this is the case, I'm not convinced that Eq. (3) can hold. For example, there might be a sequence $\\tau_n^\\star$ such that $p_n^\\mu(\\tau_n\\mid x_0)=0$ for every $\\tau_n$ such that $s_i=s_i^\\star$. And policy $\\pi$ can reach such sequence (i.e., $\\pi_n^\\pi(\\tau_n^\\star\\mid x_0)>0$). Will it violate Eq. (3)?\n\nIn summary, I believe that the RL with delay setting is important and interesting. However, due to over-complicated notations and theorem statement, I'm not able to verify the soundness/correctness of the method. I can not recommend acceptance at this point, and I'm willing to discuss and change my score if my main concerns are answered.", "extra_scores": {}, "extra_text": {}}, {"review_id": "5-4qG7pGJ3z", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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 work tackles an existing phenomenon that is often ignored in real-world control problems -- stochastic-lengthed delays. While the motivation and examples are clear, I feel I'm completely baffled by the theory that follows. \n\nI find the definitions and, consequently, the results, extremely hard to follow. Namely, in Def. 1 — why is the state-space a product of $\\mathbb{R}^2$? Is this due to the action and observation delay values? If so, why are they continuous and not discrete (as mentioned in the paper)? \n\nThen, in the same definition, comes the most confusing equation regarding $f_\\Delta$. What exactly is it? How can it be part of a transition probability while according to Def. 2 it is an expectation? Also, what is $s^*$ there and why is $r’-r^*$ a relevant term? And most puzzling to me is the fact that $f_\\Delta$ itself is recursive. That is new and surprising but barely receives any attention in the text and gets me wondering what does that imply on the process and algorithms. \n\nSimilar to the confusing definitions, the text itself is very hard to comprehend as well. For example, one paragraph before Sec. 3.1 and the first one discuss an off-policy partial trajectory resampling method using very vague arguments, and the relation to what was presented up to that point in the paper is loose. Honestly, I read those two paragraphs a couple of times and couldn't understand them. Then, the following definition and theorem 1 that follow are as confusing to me as the text. At that point, I felt I could not follow the paper anymore. \n\nLastly, the experiments apparently exhibit good results, but I cannot say anything smarter on it. Since I couldn’t understand the analysis that preceded the algorithm, I cannot appreciate its qualities.\n\n\nAdditional comments:\n1. The literature review is very scarce. Two examples of prior art dealing directly with RL with stochastic delays are [1, 2]. Additional multiple recent citations using SOTA algorithms for constant delay are also missing.\n2. Often, unclear sentences are either not backed up by references (e.g., in Sec. 2.1, “it is also possible to do much better when the delays themselves are also part of the state-space”), or when the reader is referred to the appendix, but there, no compelling argument to the original claim is found (e.g. Sec. 2.1,  $r’-r^*$ explanation with reference to B.2). \n\n[1] Katsikopoulos, K. V., & Engelbrecht, S. E. (2003). Markov decision processes with delays and asynchronous cost collection. IEEE transactions on automatic control, 48(4), 568-574.\n\n[2] Campbell, J. S., Givigi, S. N., & Schwartz, H. M. (2016). Multiple model Q-learning for stochastic asynchronous rewards. Journal of Intelligent & Robotic Systems, 81(3-4), 407-422.", "extra_scores": {}, "extra_text": {}}, {"review_id": "-P1x-1S9_vg", "reviewer": "AnonReviewer3", "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": "This paper studies the effects of random action + observations in reinforcement learning, and proposed to use partial trajectory resampling to improve off-policy algorithms such as SAC. The proposed method performs strongly in multiple environments augmented with random delays, and beats baseline SAC and RSAC in both sample efficiency and final policy performance. \n\n\nPros:\n\n(1) The methodology is sound, and the performance gaps between the proposed method and baselines are significant, especially when the tasks become harder as delay increases. \n\n(2) The experiments are comprehensive and demonstrate the potential of this algorithm. \n\nCons:\n\n(1) The paper introduced a critical concept: partial trajectory resampling in Sect 3.1. I find that this section is generally not easy to read given the packed symbols. In addition to the equations, it would be better to add a figure illustrating the recursive sub-sampling process. \n\n(2) The paper only augmented SAC. However, in theory this paper should apply to other off policy learning algorithms such as TD3. It would be more comprehensive to try such studies. \n\n(3) Clearly the baseline SAC suffers in environments with large latencies and the learning is slow. In these scenarios I am interested in seeing an on-policy baseline such as PPO/TRPO, which generally seems to be more robust to state/action delays. \n\n\nConclusion:\nPlease address my concerns raised in the \"cons\" section.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the RL problems where actions and observations may be delayed randomly. The proposed solution is based on generating on-policy sub-trajectories from off-policy samples. The benefits of this approach over standard RL algorithms is clearly demonstrated on MuJoCO problems. The paper also provides theoretical guarantees. 
This paper is well-written overall and technically strong. The majority of the reviewers find that this paper would constitute a valuable contribution to the ICLR program. 
Decision: Accept (Poster)