Imitation learning, followed by reinforcement learning algorithms, is a promising paradigm to solve complex control tasks sample-efficiently. However, learning from demonstrations often suffers from the covariate shift problem, which results in cascading errors of the learned policy. We introduce a notion of conservativelyextrapolated value functions, which provably lead to policies with self-correction. We design an algorithm Value Iteration with Negative Sampling (VINS) that practically learns such value functions with conservative extrapolation. We show that VINS can correct mistakes of the behavioral cloning policy on simulated robotics benchmark tasks. We also propose the algorithm of using VINS to initialize a reinforcement learning algorithm, which is shown to outperform prior works in sample efficiency.
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.