Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: The submission proposes to extend reward redistribution methods from RL (RUDDER) to learning from demonstration. The principal contribution of the submission is a method for using low numbers of demonstrations. 
Essentially, the redistribution mechanism is adapted to switch from training neural networks to clustering and sequence alignment methods. The approach is shown to work well in toy tasks in multi-room navigation scenarios and a final sparse reward task from the MineRL competition.

The paper is clearly written and the introduction, reasoning behind the novel method are succinct and prior work and new contributions are clearly separated. The proposed method performs very well and the use of sequence alignment, scoring and clustering tools with prior background in bioinformatics is a good example for interdisciplinary work.

The experimental evaluation is limited with 2 toy tasks with low-dimensional observations (with relevant baselines) and a more complex high-dimensional task evaluating a strongly handcrafted adaptation of the proposed method (without strong baselines). Solving the sparse MineRL task is still impressive but it remains partially ambiguous which aspects of the now adapted algorithm and crafted event space contribute most. 

Regarding related work, there exists a considerable amount of work addressing one or few shot learning from demonstration. All with their own requirements which will partially render them inapplicable to the tasks but they could nonetheless be linked under related work for a more complete picture.

The main limitation of the paper is the experimental evaluation for previously mentioned reasons. There are a couple of ways to strengthen the part:
One could add stronger baselines for the MineRL task. There is a lot of introduced structure: small set of events, independent training for events and finally use of the consensus strategy for switching between individual policies. A possible baseline would be to use the manually chosen set of events, train policies for all possible events independently and train high-level controller to switch between these policies and solve the task. This baseline would use the same information about the event space and independent training, but would need to train more agents and also the high-level controller. In the current text, this is hinted at but not actually executed.
One could also add additional ablations on the performance in the MineRL task. Evaluation of the policies without PPO fine-tuning or performance during training would be helpful. Similarly, if accepted the additional space could be used to show success in the final task during training. An option would be to port figure A.7 to the main paper.


(Disclaimer: I have reviewed a previous submission of this work. My previous review was positive and had only few requests - most of which are addressed.)

review_title: Relevant interdisciplinary extension of prior work, good performance, slightly limited evaluation

final_score: rating: 7: Good paper, accept
review_content: This paper presents strong research and is very well written. The authors managed to put many technical details in a very limited space. The quality of writing is far above the average. I am very positive about this paper, but I also have a few concerns that don't allow me to give a very high score in my initial review.

Sub-tasks are an important element of the approach, but the authors did not even cite the most classical papers on hierarchical reinforcement learning. The two standard and well-known approaches are:

Dietterich, T.G., 2000. Hierarchical reinforcement learning with the MAXQ value function decomposition. Journal of artificial intelligence research, 13, pp.227-303.

Sutton, R.S., Precup, D. and Singh, S., 1999. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2), pp.181-211.

These papers are highly cited, and they were extended in various ways, and many researchers tried to learn the sub-tasks automatically - among other things. I have to say that I am quite shocked that the authors did not cite those two very classical references (or at least one of them). This paper should clearly state how the ideas presented here relate to the MaxQ algorithm, and the temporally extended actions (options) proposed by Sutton et al. The sub-tasks presented here clearly resemble Sutton's options. This relationship should be discussed. In particular, learning Sutton's options was not a trivial task in the past. The authors should explain why sub-task learning seems to be trivial in this paper. What is the main reason or the main assumption that allows for that? What are the main simplifying assumptions made in this paper that allow for easy sub-task learning?

Figure 1 is very informative. I would ask however what would happen if the agent lost the key? The blue line should go down I assume. It would be good to see what the RUDDER algorithm would do when negative things (like lost keys) happen.

Section 3 assumes that demonstrations can be aligned. This means that if the goal can be achieved using two alternative paths of similar quality, the methods proposed here cannot be applied. The authors should say a bit more about this limitation. Could it be mitigated? If not so, this limitation mustn't be hidden.

A related question: the environment can be highly stochastic. Assume that an agent takes action a, and ends up in one of the states s1, s1, or s2 with the same probability. Also, assume that the goal state can be reached from each of these 3 states, but one has to follow a different path from each of these states. That is, all the paths that go from s1, s2, and s3 to the goal state are disjoint. Would this algorithm cope with such a situation?

The following statement is unclear to me: "In our setting the states do not have to be time-aware for
ensuring an MDP but the unobserved used-up time introduces a random effect."

I am not certain about correctness of this "Demonstration sub-sequences between sub-goals are considered as demonstrations for the sub-tasks." The agent may pick the key up, but it can drop it a few time steps later, and then pick it up again. This would not be a useful demonstration for the sub-task I think. How does the algorithm deal with the goals that be done and undone many times?

There is potentially significant novelty in this well-written paper. I would prefer to give a stronger recommendation to accept it, but I am disappointed that references to the key literature on hierarchical reinforcement learning are missing.
review_title: RUDDER is an algorithm published in 2019 that tries to address challenges posed by delayed rewards in reinforcement learning. This paper extends RUDDER in several ways. It applies RUDDER to learning from a small number of demonstrations. It has to replace LSTM with profile models used in sequence matching in biology because the number of human demonstrations available for learning is small. The results on several domains are encouraging.

final_score: rating: 6: Marginally above acceptance threshold
review_content: [Summary]

Paper proposes to attack the challenging problem of RL with sparse feedback by leveraging a few demonstrations and learnable reward redistribution. The redistributed reward is computed by aligning the key events (a set of clustered symbols) to the demonstrations via PSSM-based seq matching. Experiments on two artificial tasks and a Minecraft task demonstrate that the presented method performs advantageously than two baselines (DQfD and BC+Q learning).

[Strength]

+) The authors motivate their central research problem well with a rich background ranging from the canonical RL context of credit assignment to the biological seq alignment, which helps enhances the rationale of the proposed method.

+) The paper is overall clear and well-written. The proposed approach is technically sound and I cannot find any issue.

+) Reused from the previous RUDDER paper though, the author provides a comprehensive theoretical analysis on how the proposed reward redistribution could not alter the optimality of the original problem, and how can these results adapt to the new configuration with demonstrations.

[Weakness]

Having said those above, indeed I feel this submission could be revised from several angles. Some of them are minor while others could be crucial to the acceptance in this round.

-) (major) The main claim of this paper is a "reward redistribution" strategy that utilizes expert demonstrations. Compared to RUDDER, the redistributed reward is computed by weighting the return with the differences between the trajectory similarities of two consecutive states. However, after reading the paper, I'm still not confident enough about the rationale of this practice. An even more critical point is that I really doubt the validity of redistributing the return by merely comparing it with the demonstration. Is it still reasonable to judge whether a specific time step is more important than the others when the trajectory of the learner may include events that do not happen in the demonstrations? Almost all the existing work is to use demonstrations for shaping the training either directly (as shaped rewards) or indirectly (as constraints) since the demonstrations may not cover the same state visitation of the learner's rollouts, and therefore, could be problematic to explain away how should the return be distributed. The authors are expected to clarify why their redistribution strategy is reasonable given the possible event set misalignment between expert and learner, and also why choosing the difference between similarity as the key metric of redist.

-) (minor) The authors provide a rich literature review of many seminal research works of combing imitation learning and reinforcement learning. However, only very few of them are compared in the experiments. Also, only two artificial tasks are evaluated for comparison. The authors are encouraged to add more baselines to their method list (e.g. POfD, THOR, etc) and scale up to standard benchmark (at least on the Minecraft domain).


[Suggestions&Questions]

(1) Clarify the rationale of redistributing the reward with the differences of similarity of two consecutive states.

(2) Is it still reasonable to redistribute the reward merely based on the demonstrations when novel states appear in the learner's trajectories?

(3) Add more baselines (at least POfD or its variants) and compared them on standard benchmarks, e.g. the Minecraft domain.

[Post-rebuttal]

I have read through all the other reviews and the rebuttal. Would like to thank the authors for their efforts in improving this submission. I do believe most of my concerns have been addressed. However, the concern on some possibly confusing technical details remains. The authors are expected to further revise their paper to make it more self-explained.
review_title: Review for paper "Align-RUDDER: Learning From Few Demonstrations by Reward Redistribution"

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary:
The paper presents a method that learns from few demonstrations by computing a reward function coming from an alignement score between agent trajectories and expert demonstrations. The alignement score is inspired by methods used in bioinformatics called profile models.

Comments:
I think the paper could be better organise and not focus so much on the RUDDER framework. You could simply look at this problem from the angle of training an RL agent to produce aligned trajectories with the trajectories given by the expert where the local reward at time t is given by the profile models: g((s,a)_{0:t}) - g((s,a)_{0:t-1}).  This reward simply represents how much I deviated or not from the expert trajectories between time t and time t-1. Therefore presenting the method as a trajectory-matching imitation learning method would be way simpler for the reader. Too much emphasis is given to RUDDER and the message of the paper is somehow diluted whereas the algorithm could be simply presented. Indeed almost one page is dedicated to present results on reward distribution whereas I would like, for instance, to have more information on how the events are computed and not be referred to a paper. Indeed understanding how events are computed is crucial because they define the intrinsic metric used to compute distances between trajectories. This has been for a long time the main problem of trajectory-matching methods compared to distribution matching method. Therefore it seems crucial to develop this point.
It seems also that the number of events should not be too large for the alignement method to work. It would be nice to have more information on that specific problem. In addition such alignement methods may have problems in stochastic environments unless the events are really well defined. Could the authors expand on this (deterministic vs stochastic environments)?
Finally I find that the experimental section could be more exhaustive qualitatively and quantitatively. More environments (more or less stochastic) are needed, showing an experiment that pushes the algorithm in terms of number of events to see how it behaves, having an experiment showing different type of events and how it impact the performance. In general, as a practitioner, I would like to have a better understanding of the method  and in particular its robustness that is why I am asking for those experiments.

Rating: I think the paper could be simplify by focusing on solving the problem of learning from demonstrations by minimising a distance between expert and agent trajectories with an alignment score. This can be framed as trajectory matching imitation learning. In addition, a more extended experimental section is needed to show the limits of the method. At the moment, it is not ready for publication.
review_title: Review for Align-Rudder

Meta-review: The reviewers appreciated that the paper was clear and well written. They also appreciated that the paper has been largely improved during the discussions. The results seem to support the claim and the experiments on Minecraft are convincing. 

Yet, the reviewers had some important concerns. First the focus on RUDDER seems too strong and the method doesn't seem to be that much related to RUDDER. Presenting the work as a trajectory matching method seems more appropriate. In addition, the authors support their choice of referring to RUDDER because it comes with theoretical guarantees. But RUDDER's guarantees come from the usage of a modified LSTM while Align-RUDDER doesn't use an LSTM. 

The hierarchical approach was also questioned as the way to switch between different sub-policies is not very well explained in the paper. Baselines wrt to the switching method could not be provided. Similarly, the structure of the Minecraft task seems to be used heavily to define the hierarchy and meta-planning, so more baselines (with less structured tasks) were requested. 

The method also suffers from scalability issues as the authors acknowledge that if the number of events grows, they would need to downsample the events so as to apply their method. 
Decision: Reject