Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: 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. 


Pros:

(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. 

(2) The experiments are comprehensive and demonstrate the potential of this algorithm. 

Cons:

(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. 

(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. 

(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. 


Conclusion:
Please address my concerns raised in the "cons" section.

review_title: The paper improved Soft-Actor-Critic algorithm in more realistic environments with random action/state delays. 

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

Additional 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:
- Assuming all the loss functions can be optimized to optimal, will the policy converge to optimal or near-optimal solutions?
- 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?

Additional minor issues:
- Definition 5: There is no base (i.e., $n=0$) in the recursive definition of $\hat{v}_n^{soft}$.

---------
The 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.

While 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.

Some additional questions:
1. 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?
2. 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.
3. 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)?

In 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.
review_title: Interesting setting with straightforward solution

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:
The 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.

Review:
The 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).

The 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.

Detailed Notes:
The 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?

Definition 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. 

I 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?

Relation to existing work:
Firoiu 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

Two references that were missed but seem highly relevant since they dealt with random delays:
TEXPLORE: 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.
“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.  

Finally, 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.

Minor notes:
Page 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.
Page 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.
Page 5, second line – the formed the sub trajectory (fix one of ‘the’ instances)

review_title: good results but needs clearer algo description and some missing related work

final_score: rating: 3: Clear rejection
review_content: 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. 

I 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)? 

Then, 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. 

Similar 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. 

Lastly, 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.


Additional comments:
1. 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.
2. 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). 

[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.

[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.
review_title: Clear motivation but confusing contribution

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)