Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper studies the problem of RL with action delay, or equivalently, non-Markov decision process.
Compared 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:
  (a) achieve the optimal policy in analysis for tabular MDPs
  (b) performs well in a series of computational experiments.

There are several things to like about this paper:
- The overall standard of exposition and discussion is strong, and it is easy to follow the paper.
- The paper takes on a clear issue in reinforcement learning, and comes to some equally clear recommendations and findings.
- The proposed solution method is reasonable, and appears to perform well in practice.
- The series of experiments are well thought through... with a clear progression from theory -> didactic examples -> deep RL.

However there are a few places where this paper falls short:
- 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.
- 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.
- 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.

Overall I think the paper is a reasonable contribution, I'm generally a fan of these simple/clear pieces of work.
However, 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?
If you can include that and discuss that well then I will upgrade to an accept.
review_title: Approximate an RNN policy in non-Markov observations

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

Pros:
1. The execution delay seems to be an important problem in practice. The motivation is convincing.
2. The theoretical study is fairly strong and insightful.
3. The experiments show that the proposed method promisingly works well.

Questions:
1. 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"?
2. 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$?
3. 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?
4. 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?
5. 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.

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

===Update===

After reading the authors' feedback and other reviews, I would keep my current rating.
review_title: well-motivated study

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

This 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).

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

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

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

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

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

=== Update ===
The 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.
review_title: A learning-based approach to solving MDPs with control or observation delays

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

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

*Clarity*
The paper is well-written in general. 

*Originality*
To my best knowledge, the results are new and the need for non-stationary policies is a novel highlight.

*Significance*
rather significant, execution delay is a common issue in practice and the paper lays foundations for analysis of MDPs with execution delay.

Pros
* Theoretical analysis of ED-MDPs that guides the presented algorithm
* Great results on Tabular Maze and Physical domain problems

Cons
* No analysis on how the stochasticity of environment affects the performance of Delayed-Q
* Atari results use the simulator to predict the future state
review_title: This paper is a solid study of the problem with lots of potential research directions for the future work

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)