Efficient Imitation under Misspecification

Thank you for your review. We address the concerns raised.

1. Theoretical work and concerns

While I see some value of this theoretical work, I have a concern about how this paper is positioned which influence the score by a lot:

For a theory paper, I feel this result is not groundbreaking, in the sense that the bounds seems to be very standard. Perhaps the authors can clarify this and whether I am missing anything.

As detailed in the Introduction, the realizability assumption is quite strong and often untrue in robotics and self-driving applications due to the expert having privileged information over the expert (Kumar et al., 2021; 2022; Liang et al., 2024; Swamy et al., 2022b) or morphological differences between robots and humans (Zhang et al., 2024; He et al., 2024; Al-Hafez et al., 2023). However, prior work in efficient interactive imitation learning has not considered the misspecified setting (i.e. where the expert policy is not realizable by the learner’s policy class). It is an open question whether interactive imitation learning methods can efficiently avoid quadratically compounding errors.

We present the first bounds on efficient interactive imitation in the misspecified setting. While the bounds themselves are not necessarily tighter than prior work, the setting we consider is novel – and notably does not rely on the unrealistic realizability assumption. Prior work assumes that since $\pi_E \in \Pi$, then after enough optimization (i.e. policy search), the expert policy can be recovered. We conduct a more careful finite sample analysis and decompose the error into distinct components, including optimization error, misspecification error, and finite sample error. Additionally, we do not need a queryable expert like DAgger (Ross et al., 2011), nor global search like IRL (Ziebart et al., 2008).

Additionally, we prove how offline data can improve the sample efficiency in interactive imitation algorithms, without relying on strong assumptions about the offline data’s structure.

2. Empirical work and concerns

For a empirical paper,

1. I have trouble convincing myself why rolling-in with BC policy is a valid approach (assuming the BC policy was trained with the scarce data provided in the dataset), and
2. there can be more analysis on the experiments including analyzing the extent of misspecification and the potential gap on "trajectory length" the paper has raised.

To follow up on the previous point, I am curious how misspecification is validated in the experiments? Did the authors try running behavioral cloning on a large dataset and find that there is an inherit performance gap?

Response to (2): In our revised paper, we add a new experiment with far greater misspecification, under which we see a considerable gap between our method (GUITAR), and the interactive baselines (MM and FILTER) and offline baseline (BC). In our new setting, the expert solves the maze by traversing one way through the maze. The learner, however, is unable to take the actions necessary to follow the expert’s course through the maze. (We restrict the learner’s movement by adding additional blocks in the path of the expert.) Therefore, the learner must solve the maze through a different route through the maze. This experiment is performed with true resets.

Response to (1): We also consider the setting without access to true resets. (For example, in real robots, resetting the robot to an arbitrary state is often impossible.) We propose an efficient, alternative approach to performing true resets that effectively resets the learner to the BC policy’s distribution (i.e. by rolling in with the BC policy). This method also gives us an exact way to measure the quality of the reset distribution. We clarified this in the Experiments section.

Question on roll-in distributions

On page 10, lines 515-516: "When we improve the roll-in distribution by adding offline data, we see..." I am having trouble relating this result with Figure 2, can the paper please clarify this statement?

We added further discussion and clarification of reset distributions in Sections 4 and 6. In Figure 2, FILTER's reset distribution is $\text{BC}(\pi_E)$, while GUITAR's reset distribution is $\text{BC}(\pi_E + \pi_B)$. This is accomplished in FILTER and GUITAR by rolling in with the corresponding BC policy. In the Hopper environment in Figure 2, we observe a difference between the performance of $\text{BC}(\pi_E + \pi_B)$ and $\text{BC}(\pi_E)$, which indicates a difference in the quality of reset (i.e. roll-in) distributions between GUITAR and FILTER. Reflecting the trend in reset distribution quality, we observe a performance difference between GUITAR and FILTER. In contrast, in the Walker environment, $\text{BC}(\pi_E + \pi_B)$ and $\text{BC}(\pi_E)$ perform similarly, indicating a similar reset distribution quality. The trend is reflected in the similar performance between FILTER and GUITAR.

Thank you for your review. We believe we have addressed your concerns, especially regarding lack of misspecification in experiments. We discuss the new experiment we considered below.

1. Assumptions about misspecification

the assumptions made in the paper for formalizing misspecification do not really fit the motivation introduced in the introduction. Here, misspecification is motivated by (i) "distinct perception" and (ii) "distinct action spaces" due to different morphology...

Our theory and algorithm can handle any source of misspecification, including both “distinct perception” and “distinct action spaces” highlighted above–we do not need a case-by-case analysis. (The approximate policy completeness structural condition works in both cases and is not reliant on fully observable information.) This is one of the strengths of our analysis. In terms of the second concern, we propose and validate one method for mimicking resets in the setting without access to resets (Section 6.2 of the revised paper). We address the third concern below.

2. Misspecification and DNNs

misspecification is mainly considered if the policy parametrization is not strong enough to take the optimal action in each state. However, as DNNs are very expressive representations, I am wondering how much this is really an issue in most setups...

We agree that DNNs are expressive representations, but this is not the issue we are highlighting. The misspecification arises because (1) the robot itself cannot perform the expert’s actions/behavior, irrespective of the policy parameterization, due to morphological differences between robots and/or humans (Zhang et al., 2024; He et al., 2024; Al-Hafez et al., 2023). Additionally, the misspecification issue arises because (2) the expert has access to privileged information. No DNN can read a text-heavy road sign if it isn’t in the state/observation.

3. Limited misspecification in experiments

The experiments are rather limited and do not show any application under "misspecification", which is the main contribution of the paper. For all experiments, the experts policy can be realized by the learned policy, so I do not fully see the point if studying misspecifation in this setup. While (i) might be hard to realize, the authors could have presented experiments where (ii) is the case (see above). This can be done in gridworlds as well as for continuous control...

The existing experiments considered misspecification by adding “trembling,” or some random action selection, for the learner, thus preventing the learner from exactly mimicking the expert policy. To address the critique that our experiments did not sufficiently consider the misspecified setting, we introduce a new experiment with far larger misspecification. In our new setting, the expert solves the maze by traversing one way through the maze. The learner, however, is unable to take the actions necessary to follow the expert’s course through the maze. (We restrict the learner’s movement by adding additional blocks in the path of the expert.) Therefore, the learner must solve the maze through a different route through the maze. This new experiment addresses the setting of strong misspecification that the reviewer has asked for. For the camera ready version, we will have more versions of similarly misspecified tasks.

4. Benefit of proposed method

The presented experiments also hardly show any benefit of the presented method. E.g. I can not see any benefit in Figure 2...

The new experiment setting shows a significant difference between our algorithm and the baselines and thus highlights the value of our method in hard exploration and strongly misspecified tasks. Additionally, there was a mistake in our previous revision’s legend for one of the experiments. We further clarified that the motivation behind Figure 2’s experiments was to show a trend, specifically how the reset distribution’s quality affects the speedup seen in the IRL algorithm. We elaborated on this in Section 6.

5. Mirror descent update

The negative entropy function is used in Online Mirror Descent (OMD) to project from the dual space to the primal space. We simplified the description of our GUITAR algorithm by highlighting that any no-regret algorithm will work; we simply choose Online Mirror Descent for its strong theoretical guarantees. We then present a more thorough discussion of OMD in Appendix D.

6. Approximate policy completeness

I was also unclear why in the case of approximate policy completeness, we have O(1) for the sample complexity error bounds. $O(1)$ is not the sample complexity of the error bounds. It is the complexity of the reward-agnostic policy completeness condition. We consider the structural condition of “approximate policy completeness,” which we define to be when $\epsilon_\Pi = O(1)$, meaning the reward-agnostic policy completeness term is not dependent on the horizon of the MDP.

Thank you for your review. We address the concerns raised below.

1. Ambiguity in language (sample vs computational efficiency)

Some of the language is unclear. In particular, the use of sample efficiency and computational efficiency seem to be used interchangeably, but sample efficiency is the more valuable metric. Is computational efficiency even the problem here, and not sample efficiency?

Thank you for highlighting this ambiguity in our language. We clarified our usage of computational and sample efficiency in the revised paper. Sample efficiency is the primary focus of our paper.

2. Advantage function is not defined

[omitted due to max character constraints]

We added a definition of the advantage function in Section 2.1.

3. Use of Bregman divergence and PSDP

While the core definitions for policy completeness error are more or less well defined the GUITAR method itself is not self-contained. It is not obvious what the Bregman divergence or PSDP methods are, and probably more importantly, why these are preferable to other methods. I assume it is because of their theoretical properties, but it is not straightforward to draw the connection between the properties given and those proven in the paper.

By using a general reduction to an expert-competitive response, our approach can work with any no regret update on the reward function (e.g. follow the regularized leader, online mirror descent, etc) and any expert-competitive response in the policy, which can be computed through any RL algorithm. We added clarification on this point in the paper to make it more understandable to the reader. We specifically select online mirror descent for the reward update and PSDP for the policy update due to their theoretical properties. We clarified this point in the revised paper. The PSDP procedure is outlined in Algorithm 3 in Appendix D, and we added greater explanation for both online mirror descent (including Bregman divergence) and PSDP in Appendix D.

4. Organization of the paper and connection to resets

The organization of the paper make is more challenging to follow, as the issue of resetting is not the central focus of the work yet intrudes in the middle. If resetting is a core component of the method, then the confusion lies in expressing the connection between resetting and the misspecification problem. Furthermore, this section does not address the original problem of resetting to unreachable states, since the behavior policy may also be unreachable.

We appreciate your feedback on the paper’s organization. We revised the structure of the paper, adding motivation and context for the issue of resets. In short, our paper considers efficient interactive imitation learning in the misspecified setting. Resets are a key method for improving efficiency in interactive imitation learning. However, the following remain open questions:

1. Can interactive imitation learning avoid quadratically compounding errors efficiently in the misspecified setting?
2. Given that resets are the key method of making interactive imitation learning methods efficient, what is the optimal reset distribution in the misspecified setting?

We then consider settings – both in theory and in practice – where resetting to the expert’s state distribution (as proposed by previous work for the realizable setting) is not the optimal reset distribution.

5. Empirical analysis and comparison to offline RL methods

The empirical analysis is quite limited. In particular, the performance on more generic tasks is not convincing for this method. In particular the FILTER baseline appears to match or exceed performance in all domains. In several domains, performance is comparable with BC as well. Furthermore, there is no comparison with non-resetting SOTA offline RL methods such as IQL or CQL. Finally, the number of environments for a straightforward, fundamental method is quite limited. In a domain such as this the expectation would be to cover a good portion of at least the deepmind control suite, especially the Franka Kitchen tasks.

In response to this comment, we introduce a new experiment with far larger misspecification. In our new setting, the expert solves the maze by traversing one way through the maze. The learner, however, is unable to take the actions necessary to follow the expert’s course through the maze. (We restrict the learner’s movement by adding additional blocks in the path of the expert.) Therefore, the learner must solve the maze through an entirely different route through the maze. Under such settings, we see a significant difference between our method (GUITAR) and the IRL baselines (MM and FILTER) and offline baselines (BC).

We did not compare to offline RL methods such as IQL and CQL because, as offline RL methods, they require known rewards. We consider the imitation setting where rewards are unknown, where offline RL algorithms do not work.

Thank you for your review. Below, we address the concerns raised, and have revised our paper accordingly.

1-2. Guitar algorithm design and implementation

The GUITAR algorithm, with its dependence on multiple reset distributions and dual optimization steps, may be challenging to implement and deploy in resource-constrained environments...

The algorithm's design is notably complex, involving a dual optimization loop with reset-based IRL, reward updates via mirror descent, and policy updates that mix offline and expert data resets. Could you please talk a little bit about the computational complexity of the method?

Our algorithm’s dual optimization loop is standard for inverse RL. The algorithm we propose is conceptually simpler than standard inverse RL: we replace the global search of RL with the local search of “staying on the expert’s path.” A key strength of our algorithm, GUITAR, is that it is easy to implement in practice. GUITAR can be implemented via a straightforward environment reset wrapper, thus retaining the level of computational complexity as the other IRL baselines (MM and FILTER), while improving on sample efficiency.

More generally, IRL algorithms are known to be more statistically efficient – with respect to expert data – than offline imitation algorithms (Swamy et al., 2021a). Our paper improves the sample efficiency – with respect to environment interactions – of IRL in the misspecified setting (Theorem 3.3). Our implementation of GUITAR does not impose any additional computation over the baseline IRL algorithms (Appendix G).

3. Analysis of different qualities and types of offline data

While the use of offline data is well-motivated, additional analysis of how different qualities and types of offline data affect performance could...

Thank you for this suggestion. We updated our paper based on this feedback. In our revision, we devote more discussion to the impact of reset distributions in the misspecified setting – both from theory and empirical perspectives – in a way that we feel will give the reader clearer takeaways on choosing reset distributions in the misspecified setting.

4. Description of PSDP

Could you include a brief description of PSDP...

We revised the section describing our algorithm. We emphasized that our method can work with any RL algorithm, including popular ones such as SAC, TRPO, and PPO. We specifically choose PSDP for its theoretical guarantees, and added greater discussion in Appendix D, and the full PSDP procedure is described in Algorithm 3.

5. Code

The authors' choice of not including the codes...

We agree that releasing code is an important part of the process, and we will release our code publicly with the release of the paper.

6. Experiment environments

The main results are only provided in three MuJoCo environments. However... compounding errors for offline IL algorithms... happen when the environment is stochastic...

We agree that one of the areas where BC fails is in stochastic environments. To incorporate greater stochasticity in the Mujoco environments, we add noise in the environment by randomly selecting an action with probability $p_{tremble}$. However, we wish to emphasize that a primary cause of BC's failure is misspecification (Ross et al., 2011), and the misspecified setting is the focus of our paper. In our revision, we added an experiment under which there is greater misspecification than simply the random action $p_{tremble}$. In our new setting, the expert solves the maze by traversing one way through the maze. The learner, however, is unable to take the actions necessary to follow the expert’s course through the maze. (We restrict the learner’s movement by adding additional blocks in the path of the expert.) Therefore, the learner must solve the maze through a different route through the maze. Under such settings, we see a significant difference between our method (GUITAR) and the IRL baselines (MM and FILTER) and offline baselines (BC).

7. AntMaze experiment in Appendix

What is happening in the AntMaze experiment provided in the Appendix...

We added further explanation and a key to Figure 4 in Appendix H. The figure is meant to demonstrate the state distribution of different components of the D4RL dataset, when parsed by short and long trajectories, showing where the ant is reset to, where it travels, and where the goals are in the dataset's episodes. The purpose of the associated experiment (Figure 5) is to empirically test the effectiveness of different reset distributions for ant maze. In other words, are there subsets of the expert’s data that are better to reset to than others? We find the answer is yes: resetting to “short” trajectories in the dataset is far more beneficial than resetting to longer trajectories, suggesting that resetting to states closer to the goal improves learning more than resetting to states farther from the goal.

Q functions depend on the MDP’s dynamics. It was shown in [2] that the learning Q function approach of $`IQ-Learn`$ breaks in settings with stochastic dynamics, suggesting that learning Q functions does not transfer as well as learning rewards.

One of the inverse RL baselines that we compared to, $`FILTER`$, was shown in [2] to outperform $`IQ-Learn`$ in MuJoCo experiments with added $p_{tremble}$. Our Figure 2 experiments were done on the same environments, where $`FILTER`$ outperformed $`IQ-Learn`$. Our method, $`GUITAR`$, matched or outperformed $`FILTER`$ in those environments.

[1] Garg, Divyansh, et al. "Iq-learn: Inverse soft-q learning for imitation." 2021.

[2] Ren, Juntao, et al. “Hybrid inverse reinforcement learning.” 2024.