We present a simple and effective algorithm designed to address the covariate shift problem in imitation learning. It operates by training an ensemble of policies on the expert demonstration data, and using the variance of their predictions as a cost which is minimized with RL together with a supervised behavioral cloning cost. Unlike adversarial imitation methods, it uses a fixed reward function which is easy to optimize. We prove a regret bound for the algorithm in the tabular setting which is linear in the time horizon multiplied by a coefficient which we show to be low for certain problems in which behavioral cloning fails. We evaluate our algorithm empirically across multiple pixel-based Atari environments and continuous control tasks, and show that it matches or significantly outperforms behavioral cloning and generative adversarial imitation learning.
Summary of what the paper claims and contributes
---
This paper proposes a new interactive imitation learning algorithm to address the covariate shift problem in imitation learning. It explicitly seeks to avoid settings interactive expert feedback (e.g. DAgger). The method is straightforward: 1. First, learn an ensemble of policies via KL-based Behavior Cloning 2. Then, learn a new policy via a new objective that combines the original Behavior Cloning objective with a "disagreement" loss, formed by computing the expected variance of the ensemble evaluated on state-action trajectories under the new policy. The intuition for the method is that by learning an ensemble, it will have low variance on in-distribution demonstration data, and high variance on out-of-distribution other data; by encouraging the policy to seek regions of low variance, it should result in a policy that more closely matches the demonstrator's state visitation distribution than Behavior-Cloning alone. Analysis in the discrete finite case shows that the algorithm achieves regret linear in \kappa*T, where \kappa is an environment- and expert-dependent constant. The analysis is instantiated for a simple MDP, and experiments comparing their algorithm on this restricted environment provide some evidence that the bound is achievable in practice.
Further experiments on a variety of Atari environments and continuous-control tasks from OpenAI Gym also 1) demonstrates that their algorithm outperforms Behavior Cloning in these settings 2) usually approaches expert performance with a small number of demonstrations, and 3) also shows that the uncertainty cost improves over time, indicating the final policy learns to visit states where the ensemble agrees, and that while doing so, improves performance on the underlying task.
Evaluation
---
>Originality:
Are the tasks or methods new?
The method is new.
Is the work a novel combination of well-known techniques?
Yes.
Is it clear how this work differs from previous contributions?
Yes.
Is related work adequately cited?
There is some missing discussion of related works:
1. EnsembleDAgger (Menda 2018) also uses the variance of ensembles in Imitation Learning, but instead of using it to regularize on-policy learning, it uses it as an improved decision criterion by which to query an expert demonstrator.
2. Data as Demonstrator (Venkatraman 2015) uses on-policy learning to create "corrections" of time-series models (See their Fig 1), which is similar to this paper's intuition of seeking to push the learner back to places that are in-distribution of the expert demonstrations. That paper also achieves a linear regret bound under some assumptions.
>Quality:
Is the submission technically sound?
Mostly, although there are some issues:
1. Step 9 of the algorithm is ambiguous. What is the distribution of on-policy data that is fed into the cost? E.g. how many rollouts from the policy are collected?
2. Why is the clipped cost negative, as opposed to 0?
3. Why was a clipped cost used at all? This cost is different from that used in the theoretical analysis. Some justification and discussion is needed for why the new cost was used, and whether the analysis still applies when it's used.
4. Throughout most of the paper, p(\pi | \mathcal D) represents the model ensemble. However, no discussion was dedicated to what we should expect this distribution to look like in theory and in practice. It depends on how the ensemble is constructed / learned. A degenerate case would be if all models in the ensemble converged to the same local optima, in which case they would agree everywhere, nullifying the cost penalty. Discussion of what properties this distribution must satisfy is missing. It probably needs full support over the space of policies such that the optimal policy is nearly realizable (within \epsilon)?
5. \kappa is overloaded: A. it's used as a function B. it's used as the optimal value of that same function. Consider using different notation for one of the, e.g. \kappa^* for the optimum, or \gamma for the function. Furthermore, it might help to make \kappa's dependencies clearer, which would help illustrate its independence of T.
6. Example 1: the fact that the policy always starts at s_1 is missing from the description (at least, an equivalent assumption is made in Ross 2010)
7. Example 1: it's not clear that setting \mathcal U = \{s_1, s_2\} achieves the optimum of \kappa(\mathcal U). Discussion of this aspect is needed.
8. Example 1: The statement that the variance is equivalent to the variance of the uniform distribution seems to be a strong assumption about p(\pi | \mathcal D). This missing assumption is related to point 4. I mentioned above^
9. The paper is missing discussion for why the analysis would not immediately extend to continuous state and action spaces.
Are claims well supported by theoretical analysis or experimental results?
Yes, although the experimental results would be made stronger if related approaches were considered, e.g. Reddy 2019. Right now, there's just a single method of comparison -- BC.
Is this a complete piece of work or work in progress?
Seems complete.
Are the authors careful and honest about evaluating both the strengths and weaknesses of their work?
I believe so -- noting that BC ended up performing similar in environments where there is less drift was a good addition.
>Clarity:
Is the submission clearly written?
Yes.
Is it well organized?
Yes.
Does it adequately inform the reader?
Yes.
>Significance:
Are the results important?
Yes.
Are others (researchers or practitioners) likely to use the ideas or build on them?
Yes.
Does the submission address a difficult task in a better way than previous work?
Yes.
Does it advance the state of the art in a demonstrable way?
Yes.
Does it provide unique data, unique conclusions about existing data, or a unique theoretical or experimental approach?
Unique theoretical approach.
Additional feedback
---
Sec 3: "The threshold q defines a normal range of uncertainty based on the demonstration data, and values outside of this range incur a negative cost". The logic of this statement is confusing. 1. It's not clear what "outside" means from the sentence alone (i.e. it should be "above"). 2. A single value doesn't define a range (i.e. state the lower value is 0).
Sec 4.1: "high density" -> "high mass"
It would help to have a diagram of \mathcal U, \mathcal S - \mathcal U, \alpha, \beta, \kappa.
It would be clearer if set notation was used for the complement of \mathcal U, rather than \beta's definition of s\notin \mathcal U.
Example 1: citation should be Ross 2010, not Ross 2011.
Example 1 has different notation than in Ross 2010 (consider changing to match)
It's possible that copying a model from the ensemble and fine-tuning it with the loss would yield a faster Algorithm (1). Would this work? What do the training curves (i.e. like the plots in Fig 3b) look like in that case?
Why does the breakout DRIL agent outperform the expert?
Mention that Pinkser's inequality yields the KL bound on total variation.