Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: 
This paper tackles an issue imitation learning approaches face. More specifically, policies learned in this manner can often fail when they encounter new states not seen in demonstrations. The paper proposes a method for learning value functions that are more conservative on unseen states, which encourages the learned policies to stay within the distribution of training states. Theoretical results are derived to provide some support for the approach. A practical algorithm is also presented and experiments on continuous control tasks display the effectiveness of the method, with particularly good results on imitation learning followed by reinforcement learning.

The proposed algorithm makes use of a natural intuition, that states visited by the expert probably have higher values, and the paper generally does a good job of supporting the approach through theory and experiments. Although the experiments seem sound, certain experimental details are not completely clear. The theory may also have some restrictive assumptions, limiting its significance.
Overall, I am divided about this paper. While this submission has the elements of a good paper and the presentation is great, certain concerns make me hesitant to recommend acceptance. I would be willing to increase my score if those points are addressed. 

Theory:
1) My main concern is the applicability of the theorem, due to Assumption 4.2. While the intuition is that there is an action that corrects the next state towards the demonstration states, the theoretical condition is more restrictive. In particular, the following part (paraphrasing): "there exists an action a_cx that is close to a^bar and that makes a correction towards U". This condition implies that there are correcting actions near any action a^bar, which sems unrealistic in most cases. For example, in a driving task, say s^bar is a state such that moving back to U require the vehicle to move to the left. Then, consider the action a^bar of steering towards the right (with some angle). There could be no action near a^bar that makes the vehicle turn left towards U. Note that this is not necessarily a pathological situation as described in the text.

2) Also concerning assumption 4.2, I do not see why s^bar' is included in the quantifier of the statement since it is not used afterwards; after "there exists an action..." no mention of s^bar' is made.

3) The projection function may not be well-defined if there are multiple states that are closest to the one being projected.

4) It could be said explicitly that the expert policy is assumed to be deterministic. Currently, this is not said outright.

Experiments:
1) It seems like VINS relies heavily on the assumption that the environment is deterministic to learn an effective model. Was VINS tried in stochastic environments? 

2) Data augmentation is used for VINS. This seems like an unfair advantage compared to the baseline competitors since sample efficiency is a key concern to reinforcement learning algorithms.  To make the comparisons fair, either it should be removed or the other algorithms should also receive additional data. How is the performance of VINS without this addition?

3) A description of how the hyperparameters were chosen and their final values would be needed for reproducibility. Also, a discussion of the importance of the hyperparameters and their sensitivity would be informative. For example, I was curious to know the value of \alpha in Algorithm 2 compared to the ranges the actions could take. 

4) I am not convinced that using Q functions would necessarily fail. On p.6, the paragraph "can we learn conservatively-extrapolated Q-function" gives some reasoning why this could fail, that we may not want to penalize unseen actions. This is in opposition to the BCQ algorithm [1], which explicitly tries to avoid unseen actions and still has good performance. Trying a variant with Q(s,a) could be worthwhile. 
I am not exactly sure if I understood Appendix A properly but, from my understanding, I do not think the argument made there necessarily invalidates using Q functions. It seems to apply mostly to deterministic expert policies and also Q(s,a) could still have reasonable values due to function approximation (even if the particular action 'a' is not seen in demonstrations). 

5) Which RL algorithms were used for the imitation learning + RL set of experiments?

6) For table 1, are the results also averaged over different sets of demonstrations? 

7) Are error bars one standard deviation or one standard error (divided by sqrt(n))?

8) For figure 3, using RL without imitation learning would serve as a good additional baseline 

9) Ablation study: Trying no negative sampling with a perfect model could isolate the effect of negative sampling. 

10) Ablation study: What is the no behavior cloning and perfect model experiment trying to show?

11) I think the name of the algorithm should be modified as "value iteration" refers to a specific dynamic programming algorithm for learning value functions, while the proposed algorithm does not resemble this at all. 

Minor comments and typos (no impact on score):
- Using the cross-entropy method as in QTOpt [2] could be used to pick actions in a more refined manner.
- There is a large amount of blank space on p.8
- p.3 "At the test time" -> "At test time"
- p.4 "entire states space" -> "entire state space", "burned to warm up them" -> "burned to warm them up"
- p.9  "option 2 by search the action uniformly."  -> "option 2 to search the actions uniformly"

[1] "Off-Policy Deep Reinforcement Learning without Exploration" by Fujimoto et al.
[2] "QT-Opt: Scalable Deep Reinforcement Learning for Vision-Based Robotic Manipulation" by Kalashnikov et al.

review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: This work presents the value iteration with negative sampling (VINS) algorithm, a method for accelerating reinforcement learning using expert demonstrations.  In addition to learning an expert policy through behavioral cloning, VINS learns an initial value function which is biased to assign smaller expected values to states not encountered during demonstrations.  This is done by augmenting the demonstration data with states that have been randomly perturbed, and penalizing the value targets for these states by a factor proportional to their Euclidean distance to the original state.  In addition to the policy and value function, VINS also learns a one-step dynamics model used to select actions against the learned value function.  As the value function learned in VINS is only defined with respect to the current state, action values are estimated by sampling future states using the learned model, and computing the value of these sampled states.

Empirical results on a set of robotic control tasks demonstrate that VINS requires significantly less interaction with the environment to learn a good policy than existing, state of the art approaches given the same set of demonstrations.  While the paper presents a novel and highly effective approach, there are some apparent limitations to the algorithms which should be highlighted, and there is room for improvement in the empirical evaluations.

It is unclear that VINS would generalize well beyond robotic control domains.  For one, its theoretical guarantees depend on the local reversibility of the dynamics, that is, for small deviations from the desired state, it is possible to return to that state in a single step.  This isn't too significant a restriction, as the ability to recover quickly from small mistakes would seem to be a necessary for any method to be able to provide similar guarantees about its behavior.  The bigger issue is the use of the Euclidean metric (or any fixed metric) in the definition of conservative extrapolation.  Basically, a state is said to be similar to the states observed during the demonstrations if it is close, under the Euclidean metric, to at least one demonstrated state.  This is a reasonable approach in robotic control tasks, where Euclidean distance is a good measure of how similar two configurations are to one another, but it would seem to be unsuitable for domains where the observation space consists of images or other high-dimensional representations.  In those cases, a useful notion of similarity would likely have to be learned from the data.  In such domains, one might imagine that the conservative value function would simply learn to distinguish between real observations, and those that have been perturbed by random noise, which would never be observed in the actual task.

While experimental results demonstrate a very significant advantage for VINS both in terms of sample complexity and final performance, results are presented for only two tasks, 'pick-and-place' and 'push', while VINS outperforms the alternatives on these tasks, it is worth noting that its initial performance (without additional environment interact) is not dramatically superior to pure behavioral cloning.  It would be helpful to see how well VINS compares against the alternatives for a much smaller number of demonstrations, say 5-20, a regime where we would expect initial performance to be poor.
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: This work tried to address the covariate shift problem in imitation learning, which is due to the mismatch between training and test state distribution and may cause compounding errors. 

The authors proposed the algorithm called value iteration with negative sampling (VINS) of which the main ideas can be summarized as follows. First, value iteration is used on expert trajectories with negative sampling. Specifically, the states that are randomly perturbed from expert’s states were used to enforce (4.1) and (4.2) in the submission (called *conservative extrapolation* requirements in the submission). By doing so, the state values outside the support of expert state visitation distribution become less than those inside the support. In the meantime, temporal-difference (TD) error was minimized to satisfy Bellman consistency among state values. The second main idea of this work is to use *self-correctable policy*, where the approximate dynamics and behavioral-cloning (BC) policy were used to select the action which is expected to give higher value at the successor states. 

To consolidate their ideas, the authors proved Theorem 4.4 showing that state visitation distribution of resultant policy is approximately close to that of an expert under a few assumptions. Empirically, they considered two experiments. In the first experiment, assuming that the environment simulation is not allowed, the performance of VINS was compared with that of BC over 5 tasks, and VINS achieved higher success rates. In the second experiment, assuming the simulation is allowed, VINS was compared with existing methods such as HER+BC, GAIL and Nair et al ‘18 and shown to be much more sample-efficient compared to the selected baselines. 

Although the theoretical and empirical contributions of this work are clear to me when the environment simulation is not allowed (as shown in the first experiment in Table 1), I think the second experiment, which allows the environment simulation (as shown in Figure 3), is misleading, and this is why I vote weak reject for this work. For instance, we can simply think about GAIL with BC initialization, but it seems to me that GAIL with random initialization was used in the second experiment (since authors mentioned GAIL in OpenAI baselines was used without hyperparameter tuning (https://github.com/openai/baselines/blob/master/baselines/gail/run_mujoco.py#L53)). In addition to it, there have been some recent works on the sample efficiency of imitation learning with environment simulation which are not included as baselines in this work:

[1] GMMIL (Kim and Park, 2018, “Imitation Learning via Kernel Mean Embedding”) - cost learning with maximum mean discrepancy minimization leads to sample-efficient training

[2] BGAIL (Jeon et al, 2019, “Bayesian Approach to Generative Adversarial Imitation Learning”) - Bayesian cost is helpful for sample-efficient imitation learning

[3] DAC (Kostrikov et al, 2019, “Discriminator-Actor-Critic: Addressing Sample Inefficiency and Reward Bias in Adversarial Imitation Learning”) - Solving reward bias in imitation learning with simulation and using off-policy RL algorithm to enhance the sample efficiency

[4] Sasaki et al, 2019, “Sample Efficient Imitation Learning for Continuous Control” - Bypassing cost learning and introducing off-policy RL to enhance the sample efficiency. 

Especially, off-policy imitation learning methods [3], [4] are shown to be extremely sample-efficient compared to GAIL. I think the authors should have compared the performance of VINS + RL with those baselines in the second experiment if they tried to emphasize the sample efficiency of VINS + RL. Otherwise, they should have focused more on the initialization effect of VINS and BC. For example, one can consider the convergence speed of GAIL to the expert performance when policies were initialized with either VINS or BC.
review_title: Official Blind Review #1

Meta-review: The paper introduces Value Iteration with Negative Sampling (VINS) algorithm as a method to accelerate RL using expert demonstrations. VINS learns an initial value function that has a smaller value at states not encounter during the demonstrations.

The reviewers raised several issues regarding the assumptions, theoretical results, and experiments. The method seems to be most natural for robotic control problems. Nonetheless, it seems that the rebuttal addressed most of the concerns, and two of the reviewers increased their scores accordingly. Since we have three Weak Accepts, I believe this paper can be accepted at the conference.
Decision: Accept (Poster)