Efficient Imitation under Misspecification
Authors: Nicolas Espinosa-Dice
Sanjiban Choudhury
Wen Sun
Gokul Swamy
Venue: ICLR 2025 Poster (2025)
Keywords: Inverse Reinforcement Learning
Imitation Learning
Distribution Shift
Policy Completeness
Primary area: reinforcement learning
TL;DR: We address interactive imitation learning in the misspecified setting and prove a structural condition under which our efficient imitation algorithm can avoid compounding errors.

Abstract: We consider the problem of imitation learning under misspecification: settings where the learner is fundamentally unable to replicate expert behavior everywhere. This is often true in practice due to differences in observation space and action space expressiveness (e.g. perceptual or morphological differences between robots and humans). Given the learner must make some mistakes in the misspecified setting, interaction with the environment is fundamentally required to figure out which mistakes are particularly costly and lead to compounding errors. However, given the computational cost and safety concerns inherent in interaction, we'd like to perform as little of it as possible while ensuring we've learned a strong policy. Accordingly, prior work has proposed a flavor of efficient inverse reinforcement learning algorithms that merely perform a computationally efficient local search procedure with strong guarantees in the realizable setting. We first prove that under a novel structural condition we term reward-agnostic policy completeness, these sorts of local-search based IRL algorithms are able to avoid compounding errors. We then consider the question of where we should perform local search in the first place, given the learner may not be able to "walk on a tightrope" as well as the expert in the misspecified setting. We prove that in the misspecified setting, it is beneficial to broaden the set of states on which local search is performed to include those reachable by good policies the learner can actually play. We then experimentally explore a variety of sources of misspecification and how offline data can be used to effectively broaden where we perform local search from.

Published as a conference paper at ICLR 2025
EFFICIENT IMITATION UNDER MISSPECIHICATION
Nicolas Espinosa-Diee Sanjiban Choudhury, Wen Sun Department of Computer Science
Gokul Swamy Roboties Institute
Cornell University
Carnegie Mellon University gswamy cmu.edee
(ne229, sc2582, ws 25045558crre111.cc
ABSTRACT
We consider the problem of imitation learning under mixspecification: settings where the learner is fundamentally unable to replicate expert behavior every- where. This is often true in practice due to differences in observation space and action space expressiveness (e.g. perceptual or morphological differences between robots and humans). Given the learner must make some mistakes the misspec- ified setting, interaction with the environment is fundamentally required to fig- ure out which mistakes are particularly costly and lead to compounding errors. However, given the computational cost and safety concerns inherent in interac- tion, we' d like to perform as little it as possible while ensuring we've learned strong policy. Accordingly, prior work has proposed flavor of efficient in- verse reinforcement learning algorithms that merely perform a computationally efficient local search procedure with strong guarantees the realizable setting. We first prove that under a novel structural condition we term reward-agnostic policy completeness, these sorts local-search based IRL algorithms are able to avoid compounding errors. We then consider the question of where we should perform local search in the first place, given the learner may not be able to "walk tightrope" well the expert in the misspecified setting. We prove that in the misspecified setting, it beneficial to broaden the set of states on which local search is performed include those reachable by good policies the learner actually play. We then experimentally explore variety of sources misspecifi- cation and how offline data can be used to effectively broaden where we perform local search from.
INTRODUCTION
Interactive imitation learning (IL) is a powerful paradigm for learning to make sequences of de- cisions from expert demonstrating how to perform task. While offline imitation learning ap- proaches suffer from covariate shift between the training distribution (i.c. the expert's 's state distribu- tion) and the test distribution (i.e. the learner's state distribution)-ann the associated compounding of errors errors-intced intteractteev approaches allow the learner to observe states from the test distribution during training via performing rollouts, unlocking the ability to recover from mistakes (Ross al., 2011).
Broadly speaking, the difference between the expert's performance and the learned policy's 's perfor- mance can attributed to three forms of error:
1. Optimization error: The error resulting from imperfect search within policy class (e.g. due to the difficulty of finding a global minima on non-convex problems).
2. Finite sample error: The statistical error arising from limited expert demonstrations.
3. Misspecification ervor: The irreducible error resulting from the learner's policy class not containing the expert's policy.
Notably, misspecification eπrоr is function of both the expert policy and the learner's policy class; cannot be improved by a better algorithm or more computation. Much of the prior work in im- itation learning has focused the first two sources of error, while avoiding the misspecification
"Correspondence Nicolas Espinosa-Dice <ne229@comell.ddu>>

---

Published as a conference paper at ICLR 2025
error by imposing expert realizability: the assumption that the expert policy is within the learner's 's policy class (Kidambi et al., 2021; Swamy et al., 20:1a; 2022b; Xu et al., 2023; Swamy et al., 2023; Ren et al., 2024). In other words, expert realizabilitty is the assumption that the leamer can per- fectly imitate the expert's actions in all states: that more data and computation are all we need for optimality.
e
However, in practice, is often impossible to imitate the expert perfectly. For example, realizability can also be an inaccurate assumption due mismatch between learner and expert action spaces. In humanoid robotics, the morphological differences between robots and humans prevent perfect human-to-robon motion re-targeting (Zhang et al., 2024; He et al., 2024; Al-Hafez et al., 2023). More generally. physical robots face the problem of changing dynamics due to wear and tear, as well as manufacturing imperfections, that cause variations in link lengths and other physical properties over the course of their operation. Thus, even if demonstrations are collected via teleoperation of a robot of the same make and model, expert realizability doesn't 't necessarily hold.
In response, our paper considers the more general misspecified setting, where the learner is not nec- essarily capable of perfectly imitating the expert's behavior. We analyze how the misspecification error interrelates with the optimization and finite sample errors. More specifically, we ask:
Under what condition can interactive imitation learning in the misspecified setting avoid compounding errors while retaining computational efficiency?
The last two words of the preceding question are central to our study. By reducing the problem of imitation learning to reinforcement learning against a learned reward, interactive imitation learning approaches like inverse reinforcement learning (IRL; Ziebart et al. (2008); Ho & Ermon (2016)) face a similar global exploration problem to that of reinforcement learning in the worst case, needing to explore all paths through the state space to find one reward (e.g. a tree-structured problem with sparse rewards) (Kakade, 2003; Swamy et al., 2023). Thus, in order to focus the exploration on use- ful states, efficient imitation algorithms leverage the expert's state distribution. In particular, rather than resetting the learner to the true starting state distribution, the learner is instead reset to states from the expert's demonstrations, resulting in an exponential decrease in interaction complexity (Swamy et al., 2023). We refer to this family of reset-based techniques as efficient IRL.
At a high level, efficient IRL can be understood as replacing the hard problem of global exploration with local exploration problem over the reset distribution-in in this case, the expert states. In other words, the RI. subroutine can be thought of as optimizing a policy with a similar state visitation distribution to the expert. However, prior work in efficient IRL. makes the crucial assumption expert realizability (Swamy et al., 2023). In the realizable setting, the best policy in the learner's policy class is the expert policy, so the goal of local policy search is recover the expert policy, in which case it is natural to perform local policy optimization over the expert states.
However, in the misspecified setting, there may be no policies in the policy class that match the expert's 's state distribution, leading to two possible pitfalls of performing local policy search over expert states. First, while the learner may be able to optimize the policy at expert states (i.e. after being reset to them), the learner may not be able to reach the expert states. For example, even if learned humanoid control policy can complete a backflip from the halfway point, it might not be able to get to the halfway point in the first place. Second, even if the learner can approximately match the expert's one-step local action, it may be unable to follow-through with the rest of the expert's trajectory. For example, even if a manipulator is able to move peg close to hole, it may be unable to insert the peg as dexterously as a person can due to a lack of haptic feedback.
Given the practical importance and relatively limited theoretical study of the misspecified setting, our first contribution is condition that informs when IRL. with expert resets works in the misspeci- fied setting. At high level, our condition measures how well, with respect to the globally optimal solution, the learner must perform local optimization over the expert states. Critically, expert realiz- ability not required for our condition to be satisfied, allowing for meaningful misspecification.
Contribution 1. We define new structural condition for the misspecified setting, reward-agnostie approximate policy completeness, under which our efficient IRL algorithm with expert resets can avoid quadratically compounding errors.
2

---

Published as a conference paper at ICLR 2025
We then extend our analysis of efficient IRL to performing resets states beyond those seen in the expert demonstration. As mentioned above, if no policy in the learne''s 's policy class can reach an expert state follow-throuhh as the expert would, policy optimization at such state doesn't 't seem particularly useful. This of course begs the question of where we should reset the learner to if we want to speed up the policy search subroutine of inverse RL if we can't uniformly imitate the expert.
Informally speaking, the choice of reset distribution in a local search procedure specifies the set of policies we're searching over: those with similar visitation distributions to the reset distribution. In the misspecified setting, our goal is to compete with the optimal realizable policy-the optimal policy the learner can actually choose. Thus, a natural choice for reset distribution is one that covers the states this optimal realizable policy visits, guarantecing we' re doing as well as one could hope.
Unfortunately, we don't know a priori what this optimal realizable policy is we'd have already solved the misspecified imitation problem if we did. Intuitively though, one wants to broaden the support of the reset distribution to cover policies that aren't exactly the expert's. Practically speak- ing, we might get examples of such states by looking at offline data, such as robot play data (Lynch et al., 2020; Wang et al., 2023), suboptimal robot demonstrations (Brown et al., 2019; Chang et al., 2021; Yang et al., 2021; Hoang et al., 2024), or internet data (Chang et al., 2023; 2024), all of which are more likely to be realizable. We consider the question of how incorporating the offline data into the reset distribution affects IRL performance, and we show that the performance improvement depends on how well the new reset distribution covers the optimal realizable policy.
Contribution 2. We theoretically show that broadening the reset distribution be- yond the expert demonstrations so that it covers the state distribution of the opti- mal realizable policy, improves efficient IRL performance under misspecification.
Finally, we corroborate our theory by empirically investigating several potential sources of misspec- ification, showing that non-expert reset distributions are preferable under misspecification.
We explore several distinct forms of misspecification on con- tinuous control and locomotion tasks, demonstrating that offline data that better covers the optimal realizable policy improves efficient IRL's performance.
Contribution 3.
We begin by defining the problem and postpone a discussion of related work to Appendix A.
2 IMITATION LEARNING IN THE MISSPECIFIED SETTING
Notation. We consider a finite-horizon Markov Decision Process (MDP), M = (S, A, Ph, H. n) (Puterman, 2014). S and A are the state space and action space, respec- tively. P = {P is the time-dependent transition function, where PA : S x A + A(S) S A - [0, 1] is the ground-truth reward function, which is unknown, but we assume r" E R. where R is class of reward functions such that S: x A + [0, 1] for all E R. H is the horizon, and μ A(S) is the starting state distribution.
and A is the probability simplex.
Let II = { S + {(A)} be the class of stationary policies. We assume II and R are compact and convex. Let the class of non-stationary policies be defined by I1" {TH,- : S - {(A))/= A trajectory is given by E = {s), an, (h)) (=) where Sy. E ag A, and rh = f(h, an) for some f E R. The distribution over trajectories formed by policy is given by: as ~ T(. sh),
Th = (sh: 0n), and sh+1 ~ (- | (h, an), for h 1...., H. Let d d (s) = p [sh s spl
and dz, (s) 1/4 >h- H.
d (s).
Misspecified Imitation. As previous stated, much of the theoretical analysis in II relies on the impractical assumption of a realizable expert policy (i.c. one that lies within the learner's policy class II) (Kidambi et al., 2021; Swamy et al., 202 2022a; Xu et al., 2023; Ren et al., 2024). In contrast to prior work, we focus on the more realistic misspecified setting, where the expert policy TE is not necessarily in the policy class II. We consider a known sample of the expert policy's trajectories, where the dataset of state-action pairs sampled from the expert is DE = D, U D2 D...UUU Dr. where Dn {sp, a ~ d',%, and |DEl = N. Let ph be uniform distribution over the samples in Dr. and eg be uniform distribution over the samples in DE-
3

---

Published as a conference paper at ICLR 2025
Algorithm Reset-Based IRL (Dual, Swamy et al. (2023))
1: Input: Expert state-action distributions PE, policy class II, reward class R
2: Output: Trained policy π
3: for = to N do
4:
//No-regret step over rewards (e.g. FTRL)
5: Ti 6 arg m (T) (
6:
// "'Expert-cmppeiice
response by RL algorithm (e.g. PSDP, Alg. 3)
7: T; f- RI r. PE)
8: end for
9:
Return AN
Goal of IRL. We cast IRL as a Nash equilibrium computation (Syed & Schapire, 2007; Swamy al., 2021a), where Sion's minimax theorem guarantees the existence of an equilibrium under the standard assumptions of compactness and convexity of the policy and reward classes. The ultimate objective of IRL to learn a policy that matches expert performance. Because the ground-truth re- ward is unknown but belongs to the reward class (i.e. r* E R),, we aim to learn policy that performs well under any reward function in the reward class. For example, in problems like autonomous driv- ing, R might include functions that capture staying close to the center of lanes and obeying speed limits. This is equivalent to finding the best policy under the worst-case reward (i.e. the reward function that maximizes the performance difference between the expert and learner). Formally, find an equilibrium strategy for the game
min max J(TE,T) J(, #Ell PER
(I)
where r(
EgEn Et r(s), By the compact and convex assumptions on II and R,
Sion's minimax theorem guarantees that the Nash equilibrium exists.
IRL Taxonomy. IRL algorithms consist of two steps: a reward update and a policy update. In the reward update, discriminator is learned with the aim of differentiating the expert and learner trajectories- this is effectively trained as a classifier between the expert and learner trajectories. The policy is then optimized by RL algorithm, with reward labels from the discriminator. IRL algorithms can be classified into primal and dual variants (Swamy et al., 2021a), the latter of which in our paper. An example dual algorithm is shown in Algorithm 1. In dual IRL. algorithms, the discriminator is updated slowly via no-regret step (c.g. Line 5, Follow The Regularized Leader McMahan (2011)). and the policy is updated via using an RL subroutine with reward labels (Ratiff et al., 2006; 2009; Ziebart et al., 2008; Swamy et al., 2021a).
Reset Distribution. RL algorithms require reset distribution. Often, this is simply the MDP's starting state distribution, (Mnih, 2013; Schulman et al., 2015; 2017; Haarnoja et al., 2018). We differentiate between traditional IRL. and efficient IRL by their RL subroutine's 's reset distribution, P. In traditional IRI. algorithms, the reset distribution remains the true starting state distribution (i.e. p = ()). In efficient IRI. algorithms, the reset distribution is the expert's state distribution (i.e. p = pg). which changes the RL subroutine from best response step to expert-competitive response (Swamy et al., 2023; Ren et al., 2024), while still maintaining performance guarantees. Intuitively, efficient IRL can be understood as replacing the global search problem inherent in RL with a local search over states from the demonstrations, thereby providing a computational speedup.
2.1 IMITATION UNDER MISSPECIFICATION IS HARD
Our paper considers efficient IRL in the misspecified setting, which begs the following question:
Is efficient IRL even possible in the misspecified setting without any assumptions on I1?
We first consider statistical efficiency, which refers to the number of expert samples required to achieve strong performance guarantees, without any requirements on the computational efficiency required to do Observe that if statistically efficient imitation under misspecification is not pos- sible, this implics that computationally efficient imitation is also not possible. Thankfully, we now prove that statistically efficient imitation is possible under misspecification with novel algorithm.
4

---

Published as a conference paper at ICLR 2025
Statistically Efficient Imitation. We present Scheffé Tournament Imitation LEarning (STILE), statistically optimal algorithm in the misspecified setting. STILE assumes access to expert demon- strations (i.. Dx) and known transition dynamics STILE's objective is to select the policy π in the policy class whose induced state-action distribution (i.e. states and actions from d²) ))) is closest to the expert's empirical estimate (i.e. states and actions from Dg) for any bounded test function f. STILE's procedure is defined in Appendix E, and we present the sample complexity for the misspecified setting below.'
Theorem 2.1 (Sample Complexity of STILE under Misspecification). Assume 11 is finite, but WE $ II With probability at least - 6, STILE learns policy át such that:
3
(1- 1-
In( + In(1/8)
V V S
7 min ||d d= +0
(2)
N
As shown in Theorem 2.1, STILE achieves statistically efficient sample complexity that is linear in the horizon." However, a tournament algorithm requires comparing every pair of policies, which isn't feasible with policy classes like deep networks, making ST STILE computationally inefficient.
Computationally Efficient Imitation. While STILE achieves statistically optimal guarantee in the misspecified setting, we ultimately desire an algorithm that is also computationally feasible and can be implemented with standard policy classes used in deep reinforcement learning. To that end, we now consider computational efficiency, specifically focusing on interaction sample efficiency- the number of environment interactions needed to obtain strong performance. We consider an algo- rithm computationally efficient its interaction complexity is polynomial in the MDP horizon. We present lower bound showing that without any further assumptions, computationally efficient IRL. under misspecification is not possible - i.c. a clear "no" to the question we began this section with.
Theorem 2.2 (Lower Bound on Misspecified RL with Expert Feedback (Jia et al., 2024)). For any H N and C' E [. there exists policy class 11 with [1I| C, expert policy TE I1, and family of MDPs M with state space S of size O22 binary action space, and horizon such that any algorithm that returns 1/4-optimal policy must either use QiCC') queries to the expert oracle Own S A - R, which returns Q (s, a) (i.e. the Q value of expert policy n gg). or (2(C) queries generative model, which allows the learner query the transition and reward associated with a stale-action pair on any state."
From Theorem 2.2, we establish that polynomial sample complexity in the misspecified IRL. setting, where F & II. cannot be guaranteed. In other words, computationally efficient IRL is not possible in the setting where no structure is assumed on the MDP, even with access to a queryable expert policy like DAgger (Ross al., 2011). The results show that while statistically efficient IRL in the misspecified setting is possible, computationally efficient IRL isn't 'n't without assuming additional structure, raising the question of what assumptions suffice to design practical algorithms.
3 APPROXIMATE POLICY COMPLETE INVERSE REINFORCEMENT LEARNING
We answer the question from the preceding section through an extension of policy completeness- a condition used in the analysis of policy gradient RL algorithms and a corresponding efficient algorithm. We then show that, without exponential amount of computation, our algorithm avoids quadratically compounding errors under approximate policy completeness.
3.1 APPROXIMATE POLICY COMPLETENESS
At high-level, we aim to measure the flexibility of the policy class in the misspecified setting- more nuanced metric than the simple binary of whether the expert policy lies in the class. While the realizability condition is action level measure -t requires the learner be able to exactly match
We present the sample complexity for the TE E II case in Appendix E. 2 For convenience the analysis, we consider an infinite horizon MDP. 'The generative model strictly generalizes the online interaction model, which is limited to playing actions sequential states in trajectory.
5

---

Published as a conference paper at ICLR 2025
the expert's actions- poolicypllyyyyyl completeness is reward-sensitiv measure. Intuitively, the policy com- pleteness condition requires that the policy class contain a policy that can achieve comparable per- formance to the expert woliey-without necessarily matching the exact actions of the optimal (i.e. expert) policy. Importantly, the policy completeness condition of RI. algorithms depends on the MDP's reward function, which in the inverse reinforcement learning setting is unknown and is in- stead learned throughout training. In response, we introduce reward-agnostic policy completeness, the natural generalization of policy completeness extended to the imitation learning setting,
Definition 3.1 (Reward-Indexed Indexed Policy Completeness Error). Given the expert's 's state distribution PE, MDP M with policy class Il and reward class R, learned policy Tú and learned reward function rs, define the award-indexed policy completeness ervor of M to be
Ti.Ti TTI
ESNPE
max A7 A7 (8, a) aEA
max Es-pg E Bawr(()))) [AT (s, a)] E'Ell
(3)
We first present reward-indexed policy completeness error, which measures the policy class's ability to approximate the maximum possible advantage over the current policy. Intuitively, we can think of the second term as the learner's ' ability to improve the policy based on its policy class, since consider the maximum over policies in the learner's policy class. The first term measures the maximum possible improvement over the current policy by taking the maximum over all possible actions, including the actions not realizable by the policies in the learner's policy class. We drop the Pg notation when it is clear from context.
Because the learned policies and reward functions are not fixed throughout the algorithm (i.e. the policy and reward are updated each iteration), we consider the worst-case policy completeness error over all possible learned policies and reward functions in their respective classes. We define this worst-case policy completeness error as reward-agnsste policy completeness error below.
Definition 3.2 (Reward-A Rreward-Agnostie Agnostic Policy Completeness Error), Given some expert state distribu- tion Pg and MDP M with policy class and reward class R, define the reward-agnosee policy completeness error of M to be
PF 'T
: max
FEIL.ER ETI
T.T.PE
Note that 0 < Ti < E < H for any II, ri E R. Reward-agnostic policy completeness 'II
therefore a measure of the policy class's ability to approximate the maximum possible advan- tage, over the expert's state distribution, under any reward function in the reward class. We define the approximate policy completeness setting to be when ςn = 0(1). Next, we will show that approximate policy completeness is sufficient for efficient IRL to avoid compounding errors.
3.2 EFFICIENT IRL WITH APPROXIMATE POLICY COMPLETENESS
We begin by presenting our efficient, reset-based IRL algorithm. GUiding Tmteasers with Arbitrary Resets (GUITAR). The high-level structure of our algorithm follows the standard efficient IRL pro- cedure (Algorithm 1). The policy update reduces the global search problem of standard RL to local search by resetting the learner to some informative state distribution. The reward update is training a classifier between expert and learner trajectories. GUITAR is outlined Algorithm 2.
Policy Update. More specifically, GUI TAR employs Policy Search by Dynamic Programming (PSDP, Bagnell al. (2003)), shown in Algorithm 3, for its strong theoretical guarantees. prac- tice, any RL algorithm, such as Soft Actor Critic (SAC, Haarnoja et al. (2018)), can be used. Cru- cially, in the policy update step, GUITAR replaces with standard reset distribution of its RL solver- both in theory and practice-with the expert's 's state distribution or some offline data distribution.'
Reward Update. GUITAR employs a no-regret update to the reward function. In theory, Online Mirror Descent (OMD, Nemirovskij & Yudin (1983)) is used due to its strong theoretical guarantees (Beck & Teboulle, 2003; Srebro et al., 2011). In practice, any no-regret update can be used, such as online gradient descent (Zinkevich, 2003) (i.e. taking few gradient steps the most recent data).
'Ren et al. (2024) established a reduction from inverse RL to expert-competitive RL. By replacing the reset distribution of the RI. subroutine with expert states, the RI. step in efficient IRI. algorithms becomes an expert-competitive response, rather than best-response step like in traditional IRI..

---

Published as a conference paper at ICLR 2025
Algorithm 2 GUiding ImiTaters with Arbitrary Resets (GUITAR)
1: Input: Expert state-action distributions PE, mixture of expert and offline state-action distribu-
tions pmix, policy class II, reward class R
2: Output: Trained policy
3: Set Ro E II
4: for i = 1 to N do
5:
Let
[(n,r) ((s,))-p=(8s00) ((s,)=a27(8,a) ( // Loss function
(5)
6: Optimize
n= OMD(M .M. Reward's no-regret update
T4-1)
(6)
7: Optimize
T. PSDP(r Ts. P Pmix) Policy's expert-competitive response (7)
8: end for
9: Return n. with lowest validation error
3.3 IS LOCAL SEARCH SUFFICIENT IN THE MISSPECIFIED SETTING?
GUI TAR can intuitively understood as reducing the hard problem of global RL search (i.e. explo- ration) to a local search problem over some state distribution. For simplicity, we assume this is the expert's s state distribution this section.
high level, the local search problem can be understood follows: working backwards from the final timestep, the learner is reset to expert state and optimizes the policy (i.e. by selecting an action) to maximize the advantage over the current policy. Because the learner is reset expert states, the performance guarantee of this local search exclu- sively over the expert's s state distribution. At test time, the learned policy's induced state distribution may deviate from the expert's policy because it may not be able to take the actions required reach the expert state it saw during training. This is because of the policy class misspecification.
To answer the question of whether local search over expert states is sufficient in the misspecified set- ting, we leverage the approximate policy completeness condition. Approximate policy completeness condition measures how well the learner optimizes the policy in comparison the globally optimal solution. We prove that under the approximate policy completeness condition, local search is sufficient avoid quadratically compounding errors in the misspecified setting.
Theorem 3.3 (Sample Complexity of GUITAR). Consider the case of infinite expert data samples, such that PE = d Denote (Tr,1, 2,,,,..., T(. as the policy returned by e-approximate PSDP at iteration E [r]] of GUITAR Then,
In
R
V
<
He
PR
H
+
H
Misspecificution Eveor
Policy Optimization
Reward Regret
where H is the horizon, n. is the number of outer-loop iterations of the algorithm, and म is the trajectory-level average of the learned policies (i.e. n; each iteration i [n] of Algorithm 2).5
Misspecification Error. The first term is the bound is due misspecification. Unlike policy opti- mization error, the policy completeness error cannot be reduced with more environment interactions. Instead, it represents fixed error that is property of the MDP, the richness of the policy class, and the reward class. Prior work in efficient IRL ignored this error term by assuming expert realizabil- ity (Swamy et al., 2023). Notably, GUITAR's misspecification is linear in the horizon H. thus avoiding the compounding enrors that all offline algorithms like behavioral cloning suffer from.
Policy Optimization Error. The second term stems from the policy optimization error of the RL. subroutine. This error can be interpreted as representing a tradcoff between environment interactions
Forr clarity, we present GU I T'R''s sample complexity in the infinite expert sample regime (i.c., when have infinite samples from the expert policy, so ps d=A²) see Appendix H.2 for the finite sample analysis.

---

Published as a conference paper at ICLR 2025
(i.e. computation) and error. It can be mitigated be decreasing the accuracy parameter of the RL solver-PSID in this case. Set to c = H. the term is reduced to linear error in the horizon H. Crucially, our algorithm does not require global policy search. Because over the expert's state distribution for the RL. subroutine, the policy optimization error can be reduced without requiring computation that scales exponentially in the task horizon H.
algorithm uses PSDP
n Reward Regret. Finally, the last term, H H / stems from the regret of the Online Mirror
Descent update to the reward function. By the no-regret property and reward realizability, we can reduce this term (to zero) by running more outer-loop iterations of GUITAR.
To summarize, GUITARRvOiie compounding errors under APC without an exponential amount of computation, proving that local search is sufficient for efficient imitation under misspecification.
4 THE THEORY OF WHERE TO SEARCH UNDER MISSPECIFICATION
In the preceding section, GUITAR replaces the RL subroutine's reset distribution with the expert states, which can be intuitively understood as reducing the global search problem of RL to local search problem over the expert states. In other words. the reset distribution specifies where to perform local search. More formally, the RL solver, PSDP, learns a policy that competes against any policy covered by the reset distribution, so long as it is in the policy class (Bagnell et al., 2003). While in the preceding section we considered resetting to expert states, we might be unable to perfectly imitate the expert at all of these states due to misspecification. Roughly speaking, this can happen because the learner can't It reach the expert states in the first place (e.g. they are through a narrow corridor the learner doesn't 't have the precision to pass through) or because the learner can't complete the rest of the episode the way the expert would (e.g. the learer can reach the same high velocity as the expert but loses the ability to avoid obstacles effectively). This begs the question:
What reset distribution should we perform local search from in the misspecified setting?
Intuitively, if we view the reset distribution as speciftying the set of policies we compete against, we want to make sure our reset distribution covers the optimal realizable policy (i.e. the best choice the learner could actually make given restrictions on IT). More formally, we define
arg min max (TT,T) - J (TT,)) *Ell
rER
In words, x² is the optimal policy in the learner's policy class against the worst-case reward function. By construction, the learner can actually reach x *'s states and follow through the way n² would.
4.1 AUGMENTING THE RESET DISTRIBUTION WITH OFFLINE DATA
While resetting to x= 's state distribution seems promising for local policy search the learner would then capable of replicating r behavior-n* is unknown a priori. Intuitively, what we'd like to do is broaden the set of states we've seen in the demonstrations so that we cover the states x² visits during rollouts, rather than just covering the "tightrope" the expert walks on.
One potential source of this broader state distribution is offline data. In many practical applications, there is commonly an additional source of offline data, such as internet data (Chang et al., 2023; 2024), robot play data (Lynch al., 2020; Wang et al., 2023), suboptimal robot demonstrations (Brown et al., 2019; Chang et al., 2021; Yang et al., 2021; Hoang et al., 2024), often from a non- expert, realizable policy. Intuitively, we can think of the offline data as complementing the reset distribution of expert states with states that are reachable by the learner. In the next section, we will prove the condition under which resetting to this offline data benefits policy optimization.
More formally, we consider the general setting of having access to some offline dataset Dan {s,, a; J. where (s, a) ~ d and n is some realizable behavior policy that is not necessarily as a high-quality the expert Tg. Our approach for incorporating offline data into IRL is to augment the reset distribution of expert states with the offline data. This approach requires no change to the structure of GUI TAR, in theory or in practice. We simply set the RL solver's 's reset distribution to the mixture of offline and expert states, p = Pmix. where we define D Dmix = D U Dan and Pmix as the uniform distribution over Dmix. We weight the two distributions
N+M d N+ d
N
d
8

---

Published as a conference paper at ICLR 2025
while the reward update remains the same. The only modification to en is change in the state distribution, replacing the distribution over expert samples, PE. with the mixed distribution, Pmix-
(a) Block obstruction
(b) Time constraint
Figure 1: Maze construction under misspecification. The expert's 'ss trajectory shown in green, and the learner's trajectory is shown in orange. The green circle represents the goal position that returns the maximum possible reward, while the purple circle represents the goal position that returns the maximum realizable reward.
4.2
WHEN OFFLINE DATA BENEFICIAL. IRL.
We can now precisely characterize when using offline data for resets is beneficial for IRL.
Corollary 4.1 (Benefit of Offline Data). If
oo, incorporating offtine data into the
B
reset distribution improves the sample efficiency of GUITAR when
CHI + M
CH.RR N
Cв
T
Pais
+
Pais ETI
N
< Pnii
+ Pain
(10)
where N is the number of expert state-action pairs, M the number of offline state-action pairs,
CHI = In m R and CB
Corollary 4. presents sufficient condition for offline data improving GUITAR's sample efficiency the algorithm with resets strictly to expert data. We observe that the benefit of offline data depends on how well the offline data covers the optimal realizable policy, n², as well as the amount of expert and offline data. Intuitively, we can think of the coverage coefficient Cn as the "exchange rate," measuring how useful the offline data is in comparison to the optimal realizable policy. This can be thought of intuitively as requiring that if n= visits state, тB does too, but not necessarily with an equal visitation frequency. We pay in terms of performance based on the mismatch in frequency. When the offline data covers "* state distribution well, CB is small, so the offline data helps.
Corollary 4.1 suggests that the optimal offline data is one that covers the optimal realizable policy π²' which further implies that the optimal reset distribution for efficient IRL under misspeci- fication is that which best covers the covers the state distribution of x*. Practically, this means that when choosing what offline data and reset distribution to use, it may be more effective to use one from realizuble policy (e.g. large amount of sub-optimal demonstrations from a robot of the same morphology) than data from an unrealizable expert policy. In the next section, we continue investigating the question of the optimal reset distribution empirically.
THE PRACTICE WHERE TO SEARCH UNDER MISSPECIFIICTIIO
The results from Section 4 suggest that, in theory, the optimal reset distribution is that best covers the state distribution of the optimal realizable policy, π². In this section, we corroborate those theoretical findings with empirical results testing the effect of different reset distributions on IRL's performance in misspecified settings. In particular, we consider the case of misspecification due to unreachable expert states. Intuitively, the learner cannot reach these states, policy optimization at such states is at best waste of computation and can potentially induce suboptimal behavior at states the learner actually can reach."
"We present the complete finite sample analysis in Appendix H.
Due space limitations, we postpone analysis of other misspecified settings Appendix B.

---

Published as a conference paper at ICLR 2025
Aatmaze-Umaze-2 (Block Obstruction)
Antmaze-Umaze--2 (Time Constraint)
100
IQM [(x) ((r)
75
I0M of [(xe)
40-
MMN
50-
20
0-
0.00
0.50
TOUARO 150000 200000 250000
Env. Steps
X100
Env. Steps
50(m)]
FILTER, A 1.0
OUSTAR, a 1.0
(a) Block obstruction
(b) Time constraint
Figure 2: Unreachable expert states. The reset distribution dictates where the learner performs local policy optimization. By resetting the learner expert states, FILTER optimizes the expert's state distribution. However, the learner is unable to reach certain expert states, so intuitively, there no value for the learner in optimizing at those unreachable states. In contrast, all of the states in GUITAR's reset distribution are reachable by the learner and thus valuable for optimization. Fg is the unrealizable expert policy, and x* the optimal realizable policy. Standard errors are computed across 10 seeds for Experiment (a) and 5 seeds for Experiment (b).
Practical Motivation. When learning to perform a particularly agile maneuver like dunking a basketball (He et al., 2025), a humanoid robot might benefit from being reset close to the rim in simulation to learn the skill of placing the ball into the hoop. However, the robot might lack the actuation capabilities to vertically jump in the same manner person would, making these states unreachable. In such a setting, one would hope to learn an alternative strategy like a layup.
Algorithm and Baselines. For the experiments in this section, we compare our algorithm, GUTTAR, against two behavioral cloning baselines (Pomerleau, 1988) and two IRL baselines (Swamy et al., 2023; 2021a). One behavioral cloning baseline is trained exclusively on the expert data, BC g and the second is trained with both expert and offline data, BC(TE + TT), when offline data is available. We consider a traditional IRL algorithm, MM, and an efficient IRL algorithm, FILTER (Swamy et al., 2021a; 2023). We train all IRL algorithms with the same expert data and hyperparameters. The difference between MM, FILTER, and GUITAR can be summarized by the reset distribution they use. MM resets the learner to the true starting state (i.e. p = μ), while FILTER resets the learner to expert states (i.e. p = Pg). GUTTAR resets the learner to offline data (i.e. = PB). For more details on the setup and implementations used in this section's experiments, refer to Appendix I.
Experimental Setup. To empirically investigate this setting, we consider a variant the Antmaze Umaze task, where a quadruped ant learns to solve maze to reach goal position (Fu et al., 2020). We impose two types of constraints to create misspecification. In the first variation (Figure la), simulate unrealizable expert actions by placing barrier in the learner's maze that prevents it from following the path of the expert. Notably, the block forces the learner to find an entirely different route through the maze. In the second variation (Figure 1b), consider "time constraint" that prevents the learner from reaching the second half of the maze. In this setting, we have access expert data from an unrealizable expert policy, Tg. and offline data from the optimal realizable policy, .T.
Experimental Results. From Figure 2b, we see that focusing the reset distribution on the realizable policy x² speeds up learning, as shown by GUITAR's 's improvement over FILTER. Interestingly, when the extent of the misspecification increases, the improvement exhibited by GUITAR over the baselines does too, shown by Figure 2a. From Figure 2a, we observe that GUTTAR is the only interactive algorithm capable of solving the hard exploration problem the strongly misspecified setting, suggesting that the offline data-states from optimal realizable policy-is is better reset distribution than expert states in this task. This agrees with what our preceding theory would predict.
Fundamentally, the reset distribution dictates where the learner performs local policy optimization, so by resetting the learner to expert states, FILTER optimizes on the expert's state distribution. However, the learner is unable to reach certain expert states, intuitively, there is value for the leamner in optimizing at those unreachable states. In contrast, all of the states in GUITAR's reset distribution are reachable by the learner and thus valuable for optimization, improving performance.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
NED is supported by DARPA LANCER: LeArning Network CybERagents. SC is supported in part by Google Faculty Research Award, OpenAl SuperAlignment Grant, ONR Young Investigator Award, NSF RI #2312956, and NSF FRR#2327973. WS acknowledges funding from NSF IIS- #2154711, NSF CAREER #2339395, and DARPA LANCER: LeArning Network CybERagents. GKS was supported in part by an STTR grant. GKS thanks Drew Bagnell for several helpful dis- cussions, particularly around how recoverability interacts with our results.
REFERENCES
Alckh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 32, 2019.
Firas Al-Hafez, Guoping Zhao, Jan Peters, and Davide Tateo Locomujoco: A comprehensive imitation learning benchmark for locomotion. arXiv preprint arXiv:2311.02455 2023.
Philip Amortila, Nan Jiang, Dhruv Madeka, and Dean Foster. A few expert queries suffices for sample-efficient rl with resets and linear value approximation. Advances in Neural Information Processing Systems, 15:29637-296441 2022.
James Bagnell, Sham M Kakade, Jeff Schneider, and Andrew Ng. Policy search by dynamic pro- gramming. Advances in neural information processing systems, 16, 2003.
Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-775, 2003.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. Oper- ations Research, 2024.
Daniel Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Niekum. Extrapolating beyond sub- optimal demonstrations via inverse reinforcement learning from observations. In International conference on machine learning, pp. 783-792. PMLR, 2019.
Daniel Brown and Scott Niekum. Deep bayesian reward learning from preferences. arXiv preprint arXiv:1912.04422, 2019.
Jonathan Chang. Masatoshi Uehara, Dhruv Sreenivas, Rahul Kidambi, and Wen Sun. Mitigating covariate shift imitation learning via offline data with partial coverage. Advances in Neural Information Processing Systems, 34:965-979, 2021.
Jonathan D Chang, Kiante Brantley, Rajkumar Ramamurthy, Dipendra Misra, and Wen Sun. Learn- ing to generate better than your Ilm. arXiv preprint arXiv:2306. 1816, 2023.
Jonathan D Chang, Wenhao Zhan, Owen Oertell, Kianté Brantley, Dipendra Misra, Jason D Lee, and Wen Sun. Dataset reset policy optimization for rlhf. arXiv preprint arXiv:2404. 084995, 2024.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. arXiv preprint drXiv:1111.00141, 2017.
Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4rl: Datasets for deep data-driven reinforcement learning. arXiv preprint arXiv:2004.07219, 2020.
Scott Fujimoto and Shixiang Shane Gu. A minimalist approach to offline reinforcement learning. Advances in neural information processing systems, 34:20132-20155, 2021.
Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Im- proved training of wasserstein gans. Advances in neural information processing systems, 30, 2017.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International confer- on machine learning, pp. 1861-1870. PMLR, 2018.

---

Published as a conference paper at ICLR 2025
Tairan He, Zhengyi Luo, Xialin He, Wenli Xiao, Chong Zhang, Weinan Zhang, Kris Kitani, Changliu Liu, and Guanya Shi. Omnih2o: Universal and dexterous human-to numan-to-humest humanoid whole- body teleoperation and learning. arXiv preprint arXiv:2406.0888 2024.
Tairan He, Jiawei Gao, Wenli Xiao, Yuanhang Zhang. Wang. Jiashun Wang, Zhengyi Luo, Guanqi He, Nikhil Sobanbab, Chaoyi Pan, et al. Asap: Aligning simulation and real-world physics for learning agile humanoid whole-body skills. arXiv preprint arXiv:2502.01145 2025.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. Advances in neural information processing systems, 29, 2016.
Huy Hoang, Tien Mai, and Pradeep Varakantham. Springl: Sub-optimal demonstrations driven offline imitation learning. arXiv preprint 1rX1v:2402.13147, 2024.
Zeyu Jia, Gene Li, Alexander Rakhlin, Ayush Sekhari, and Nati Srebro. When is agnostic reinforce- ment learning statistically tractable? Advances in Neural Information Processing Systems, 36, 2024.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, pp. 267-274, 2002.
Sham Machandranath Kakade. On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom), 2003.
Rahul Kidambi, Jonathan Chang, and Wen Sun. Mobile: Model-based imitation learning from observation alone. Advances in Neural Information Processing Systems, 34:28598-288 -26111, 2021.
Corey Lynch, Mohi Khansari, Ted Xiao, Vikash Kumar, Jonathan Tompson, Sergey Levine, and Pierre Sermanet. Learning latent plans from play. In Conference on robot learning, pp. 1113- 1132. Pmlr, 2020.
Brendan McMahan. Follow-the- hallow-the-rguuaaizeed-leee and mirror descent: Equivalence theorems and 11 regularization. In Proceedings of the Fourteenth International Conference on Artificial Intelli- gence and Statistics, pp. 525-533. JMLR Workshop and Conference Proceedings, 2011.
V Mnih. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.56002 2013.
Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Riccardo Poiani, Gabriele Curti, Alberto Maria Metelli, and Marcello Restelli. Inverse reinforce- ment learning with sub-optimal experts. arXiv preprint arXiv:2401.03857 2024.
Dean A Pomerleau. Alvinn: An autonomous land vehicle in neural network. Advances in neural information processing systems, 1, 1988.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John
Wiley & Sons, 2014.
Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dor- mann. Stable-baselines:: Reliable reinforcement learning implementations. Journal of Machine Learning Research, 22(268):1-8 1-8, 2021.
Nived Rajaraman, Yanjun Han, Lin Yang, Jingbo Liu, Jiantao Jiao, and Kannan Ramchandran, On the value of interaction and function approximation in imitation learning. Advances in Neural Information Processing Systems, 34:1325-1333 2021.
Nathan D Ratliff, Andrew Bagnell, and Martin A Zinkevich. Maximum margin planning. In Proceedings of the 23rd international conference on Machine learning, pp. 729-736. 2006.
Nathan D Ratliff, David Silver, and Andrew Bagnell. Learning to search: Functional gradient
techniques for imitation learning. Autonomous Robots, 27:25-53, 2009.
12

---

Published as a conference paper at ICLR 2025
Juntao Ren, Gokul Swamy, Zhiwei Steven Wu, J Andrew Bagnell, and Sanjiban Choudhury. Hybrid inverse reinforcement learning. arXiv preprint M.Xiv:24422088455 2024.
Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 661-668. JMLR Workshop and Conference Proceedings, 2010.
Stephane Ross and Andrew Bagnell. Reinforcement and imitation learning via interactive no-regret learning. arXiv preprint
2014.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. reduction of imitation learning and struc- tured prediction to no-regret online learning. In Proceedings of the fourteenth international con- ference on artificial intelligence and statistics, pp. 627-635. JMLR Workshop and Conference Proceedings, 2011.
Silvia Sapora, Gokul Swamy, Chris Lu, Yee Whye Teh, and Jakob Nicolaus Foerster. Evil: Evolution strategies for generalisable imitation learning. arXiv preprint arXiv:2406. 2024.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning. pp. 1889-1897. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
Lior Shani, Tom Zahavy, and Shie Mannor. Online apprenticeship learning. In Proceedings of the AAAI conference on artificial intelligence, volume 36, pp. 8240-8248, 2022.
Yuda Song, Yifei Zhou, Ayush Sekhari, J Andrew Bagnell, Akshay Krishnamurthy, and Wen Sun. Hybrid rl: Using both offline and online data can make efficient. arXiv preprint arXiv:2210.06718, 2022.
Nati Srebro, Karthik Sridharan, and Ambuj Tewari.
On the universality of online mirror descent. Advances in neural information processing systems, 24, 2011.
Gokul Swamy, Sanjiban Choudbury, J Andrew Bagnell, and Steven Wu. Of moments and match- ing: A game-theoretic framework for closing the imitation gap. In International Conference on Machine Learning, pp. 10022-10032. PMLR, 2021a.
Gokul Swamy, Sanjiban Choudhury, Andrew Bagnell, and Zhiwei Steven Wu. A critique of strictly batch imitation learning. arXiv preprint arXiv:2110.0206. 2021b.
Gokul Swamy, Sanjiban Choudhury, Drew Bagnell, and Steven Wu. Causal imitation learning under temporally correlated noise. In International Conference on Machine Learning, pp. 20877-20890. PMLR, 2022a.
Gokul Swamy, Nived Rajaraman, Matt Peng, Sanjiban Choudhury, J Bagnell, Steven Wu, Jiantao Jiao, and Kannan Ramchandran. Minimax optimal online imitation learning via replay estimation. Advances in Neural Information Processing Systems, 35:7077-7088, 2022b.
Gokul Swamy, David Wu, Sanjiban Choudhury, Drew Bagnell, and Steven Wu. Inverse reinforce- ment learning without reinforcement learning. In International Conference on Machine Learning, pp. 33318. PMLR, 2023.
Umar Syed and Robert Schapire. A game-theoretic approach apprenticeship learning. Advances in neural information processing systems, 20, 2007.
Luca Viano, Stratis Skoulakis, and Volkan Cevher. Imitation learning in discounted linear mdps without exploration assumptions. arXiv preprint arXiv:2405.00188) 2024.
Chen Wang, Linxi Fan, Jiankai Sun, Ruohan Zhang. Li Fei-Fei, Danfei Xu, Yuke Zhu, and An- ima Anandkumar. Mimicplay: Long-horizon imitation learning by watching human play. arXiv preprint a arXiv:2302. 2023.
13

---

Published as a conference paper at ICLR 2025
Tian Xu, Ziniu Li, Yang Yu, and Zhi-Quan Luo. Provably efficient adversarial imitation learning with unknown transitions. Uncertainty in Artificial Intelligence, pp. 2367-2378, PMLR, 2023.
Mengjiao Yang, Sergey Levine, and Ofir Nachum, Trail: Near-optimal imitation learning with suboptimal data. arXiv preprint arXiv:2110.144 147777000, 2021.
Chong Zhang, Wenli Xiao, Tairan He, and Guanya Shi. Wococo: Learning whole-body humanoid control with sequential contacts. arXiv preprint 200v:22006.00005, 2024.
Brian D Ziebart, Andrew L Maas, J Andrew Bagnell, Anind K Dey, et al. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pp. 1433-1438. Chicago, IL, USA, 2008
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference machine learning (icml-03), pp. 928-936, 2003.
14

---

Published as a conference paper at ICLR 2025
A RELATED WORK
Reinforcement Learning. Prior work in reinforcement learning (RL) has examined leveraging ex- ploration distributions improve learning (Kakade & Langford, 2002; Bagnell al., 2003; Ross et al., 10 Song et al., 2022). Similar to Song et al. (2022), we consider access to offline data but differ by considering the imitation learning setting, while Song et al. (2022) considers the known- reward reinforcement learning setting. We adapt the Policy Search via Dynamic Programming (PSDP) algorithm of Bagnell antees in our analysis. We use Jia et al. (2024)'s lower bound on agnostic RI. with expert feedback to show why agnostic IRI. is hard.
al. (2003) as our RL solver and leverage its performance guar-
Prior analyses of policy gradient RL algorithms such PSDP (Bagnell et al., 2003), Conservative Policy Iteration (CPI, Kakade & Langford (2002)), and Trust Region Policy Optimization (TRPO, Schulman et al. (2015)) a policy completeness condition to establish performance guarantee with respect to the global-optimal policy (Agarwal et al., 2019; Bhandari & Russo, 2024). In other words, policy completeness used when comparing the learned policy to the optimal (i.e. best possi- ble) policy and not simply the best policy in the policy class. We generalize the policy completeness condition from the RL setting with known rewards to the imitation learning setting with unknown rewards, resulting in novel structural condition we term reward-agnoste policy completeness. Our paper also builds on work in statistically tractable agnostic RL (Jia et al., 2024).
Imitation Learning. Our work examines the issue of distribution shift and compounding errors in IRL, which was introduced by Ross & Bagnell (2010). Ross al. (2011)'s DAgger algorithm is capable of avoiding compounding errors but requires an interactive (i.e. queryable) expert and recoverability (Rajaraman et al., 2021; Swamy et al., 2021a), which we do not assume in our setting.
Our algorithm and results are not limited to the tabular and linear MDP settings, differentiating from prior work in efficient imitation learning (Xu al., 2023; Viano et al., 2024). Our work relates to Shani et al. (2022), who propose Mirror Descent- based no-regret algorithm for online apprenticeship learning. We similarly use mirror descent based update to our reward function, but differ from Shani et al. (2022)'s 's work by leveraging resets to expert and offline data to improve the interaction efficiency of our algorithm. Incorporating structured offline data has been proposed to learn reward functions in IRL (Brown et al., 2019; Brown & Nickum, 2019; Poiani et al., 2024), but rely on stronger assumptions about the structure of the offline data. In contrast, we do not use offline data in learning a reward function, instead using it to accelerate policy optimization via resets.
Inverse Reinforcement Learning. We build upon Swamy et al. (2023)'s technique of speeding up IRL by leveraging the expert's s state distribution for learner resets. Our paper introduces the follow- ing key improvements to Swamy et al. (2023)'s work. First, while Swamy et al. (2023) relies on the impractical assumption of expert realizability, Second, instead of ussuming access to infinite expert data like Swamy et al. (2023), we consider the finite sample regime and further demonstrate how incorporate offline data into IRL.
tackle the more general, misspecified setting.
15

---

Published as a conference paper at ICLR 2025
B ADDITIONAL EMPIRICAL RESULTS UNDER MISSPECIRICATION
B.1 MISSPECIFIED SETTING II: DIFFERENT DYNAMICS
Next, we consider the setting of misspecification due to a difference in dynamics between the expert demonstrations and the learner's ' environment (Sapora et al., 2024). This can make it difficult for the learner to throughhh"""" like the expert would, complementing the setting we investigated above.
Practical Motivation. In humanoid robotics, the morphological differences between robots and motion retargeting (Zhang et al., 2024; He al.. 2024;
humans prevent perfect human-to-row AI-Hafez et al., 2023). As result, the expert's 8s and learner's s dynamics may be different.
Experimental Setup. To empirically investigate this setting, we consider MuJoCo continuous con- trol tasks where the expert and learner have different morphology, implemented by changing the link lengths and joint ranges between the expert-which uses the default values-and the learner. Changing the link lengths and joint ranges thereby changes the dynamics between the expert and learner. In such a setting, it is impossible to reset the learner to expert states without deforming the rigid body of the robot, and thus we cannot implement F FILTER. For GUITAR, reset the learner to states from the optimal realizable policy, RT, which has the same morphology as the learner.
Experimental Results. Figure 3 shows a speedup in learning enabled by using resets states from a realizable policy, which GUI TAR employs. In contrast, it is impossible to reset the learner to ex- pert states, LLTER does, due to the different morphology between the expert and learner. The consistently poor performance of the BC policies across the varying misspecified settings highlights the challenge of using offline data for direct policy learning, the approach is sensitive dynam- ies shifts in the misspecified setting. In contrast, the approach of using offline data for resets in interactive algorithms demonstrates stronger overall performance across tasks considered.
Ant-v3, Puanbl: 0.01
Humanold-v3, Poesile 0.0
of ((m))
6000
T(m)
6000
2000
0.4
0.6 Steps
0.8
1.0
0.4
0.5
0.5
Ery.
x10
Erv.
Steps
x10*
BC(TT)
BO(TE TT))
NM
GUITAR, 1.0
Figure 3: Changing dynamics. By resetting to states from a realizable policy, GUITAR shows a speedup over traditional inverse RL methods problem where the misspecification is due to dynamics mismatch. Standard errors are computed across 5 seeds.
B.2 ARE n' STATES THE UNIQUE OPTIMAL RESET DISTRIBUTION?
We have shown theoretical and empirical results suggesting that the optimal reset distribution for efficient IRI. are states from the best realizable policy, x². In this section, consider the question of whether n² is the unique optimal reset distribution. While theory suggests that the reset distribution must cover the state distribution of n², we explore resetting to subsets of x* state distribution.
Practical Motivation. Compared to the relatively unconstrained motion through free space before picking up object, the contact phase of the manipulation interaction might be significantly more challenging for the learner to get correct. Even if x² is able to successfully pick up and then manip- ulate some object, we might not need to expend much compute performing local search at certain states where wider range of actions is sufficient to make progress on the task.
Experimental Setup. To empirically investigate this setting, we consider the D4RL Antmaze-La tasks, where the expert data comes from the D4RL dataset. For GUITAR, we
'We leave formalizing this notion which seems related to the density of "good enough" actions under the learner's advantage function interesting question for future work.
16

---

Published as a conference paper at ICLR 2025
isolate all short trajectories shoot) and all long trajectories (Drogg in the expert dataset. We com- pare GUITAR(Daton) and GUITAR GuInAR(Doon)) which reset to short and long trajectories respectively. For simplicity, we do not add any additional misspecification and consider the policy that generated Diun to be realizable and thus x².
observe that using the short-trajectory dataset as the reset distribution performs comparably to the full expert dataset, suggesting that full coverage of the expert's s state distribution is not necessary. However, as demonstrated by the long-trajectory dataset failing to solve the problem, there are also subsets of the expert's 's state distribution that adversely affect learning. Crucially, we observe a difference in the coverage of the reset distributions when visualized in Figure 5, with the short-trajectory dataset having more focused coverage (i.c. coverage closer goals). The results in Figure suggest that the state distribution of x is not the only optimal reset distribution and resetting to a subset of x state distribution can be equally efficient.
Experimental Results. In Figure
We leave a more nuanced theoretical exploration of what makes particular subsets of better to reset to than others as question for future work.
Antmaze- Antmazz--Diveree Diverso- Plemmlee 0.0
Antmazze-liag Play--22, Piummble 0.05
of
40
MAN
1OM of ((x))
40
20
0.0
0.2
0.4
D.6
0.8
1.0
0.0
0.2
D.4
0U.6
0.8
1.0
Env. Steps
x100
Ery.
Steps
x10'
BC
VEN (asaa)
GUTTAR Plongh
FTLTTER(Daa))
(DeurR 1.0
Figure 4: Resets to subsets of " state distribution. We consider whether it is necessary, as the theory suggests, reset distribution that covers a* state distribution. In this experiment, we reset to subsets of "s state distribution and compare their performance. The performance of TAI(DDatoon) matches the performance F FILTER( Diuu). showing that full coverage of x*'s state distribution is not necessary in practice. Standard eтrors are computed across 10 seeds. During evaluation, agents sample a random action with probability Premble.
17

---

Published as a conference paper at ICLR 2025
C DISCUSSION
In summary, we explore computationally efficient algorithms for imitation learning under misspeci- fication, the setting where the learner cannol perfectly mimic the expert. In the misspecified setting, we demonstrate both theoretically and empirically that the lack of expert realizability affects the optimal choice of the reset distribution for the inner policy search step, thereby addressing one of the core limitations of Swamy et al. (2023). Notably, our analysis inherits a limitation from Swamy al. (2023) and the work it builds on (Ross & Bagnell, 2014; Bagnell al., 2003): overlooks the fundamental ability of any policy to recover from mistakes. For example, on cliff-like problems, no policy can recover after single mistake, but approximate policy completeness doesn't capture this.
The notion of expert recoverability- how effectively the expert can correct an arbitrary learner mistake-often appears in the analysis queryable expert imitation learning algorithms like DAg- ger (Ross et al., 2011; Swamy al., 2021a). Prior work has highlighted that, even for IRL algo- rithms, expert recoverability fundamentally dictates the ease of policy search (Swamy et al., 2021a, Section 4.3). While notion of reward-are reward-agnostic policy completeness bears similarity to the variant of recoverability explored in Swamy et al. (2021a)-both impose bounds on advantages over pos- sible reward functions- our definition is fundamentally off-policy in terms of the state distributions of the outer expectations. This off-policy nature makes it challenging to connect approximate policy completeness to the notion of policy recovering from their own mistake. An interesting avenue for future work is to pursue more refined notion of recoverability that inherits the strengths of both.
Furthermore, in the misspecified setting, where the learner cannot perfectly imitate the expert, remains an open question whether the expert's ability to recover from a mistake is the appropriate measure of problem difficulty. Thus, a more refined fusion of the above two concepts that also accounts for misspecification would be particularly illuminating for both theory and practice.
18

---

Published as a conference paper at ICLR 2025
D MISSPECIHIED RL WITH EXPERT FEEDBACK
Theorem 2.2 establishes that polynomial sample complexity in the misspecified IRL. setting, where TE $ II, cannot be guaranteed. In other words, efficient IRL not possible with no structure assumed on the MDP, even with access to queryable expert policy like DAgger (Ross et al., 2011). Note that a generative model allows the learner query the transition and reward associated with a state-action pair on any state, in contrast to an online interaction model that can only play actions on sequential states trajectory. For more thorough discussion of their differences, see Kakade (2003).
More specifically, Theorem 2.2 presents lower bound on agnostic RL with expert feedback. assumes access to the true reward function and an expert oracle, Oxxp S x A - R, which returns @**(s, a) for a given state-action pair (s, a). The lower bound in Theorem 2.2 applies in the case where the expert oracle is replaced with weaker expert action oracle (i.e. (E())= S A) (Amortila et al., 2022; Jia et al., 2024). agnostic IRL, we consider the even weaker setting of having dataset of state-action pairs from the expert policy mg-
Notably, this lower bound focuses on computational efficiency. Statistically efficient imitation is possible, and present statistically optimal imitation learning algorithm for the misspecified setting in Appendix E.
19

---

Published as a conference paper at ICLR 2025
E STATISTICALLY OPTIMAL IMITATION UNDER MISSPECIHICATION
We begin with the following question: ignoring computation efficiency, what is the statistically optimal algorithm, with respect to the number of expert samples, for imitation learning in the mis- specified setting?
We present Scheffé Tournament Imitation LEarning (STILE), statistically optimal algorithm for the misspecified setting. For any two policies π and n', we denote by JT, the following witness function:
fx. == arg max
Esaadr (8, a) - E, sana [(8
(1I)
fillfll
S1
and the set of witness functions as
F= (fn 1 u E II, T *
(12)
Note that [F| < [T] STILE selects á using the following procedure:
N
Σ 166 16)
à E arg min #ell
max /EF
Es f(8, a)
(13)
N
where af) DE. Notably, running tournament algorithm requires comparing every pair of policies, which not feasible with policy classes like deep neural networks, making STILE impractical to implement.
We present the analysis in the infinite-horizon setting for convenience.
Theorem E.1 (Sample Complexity of STILE), Assume II is finite and πt" E II. With probability at least 1 8, STILE finds a policy
2 21n I) + In (1)
WE V
(14)
N
Proof. The proof relies on a uniform convergence argument over of which the size is [ First, note that for all policies II:
max (Eeand [8, - Es ((),a)) fEF
max f: f1lxs1
(Be,avd f(3, a) Exand (() (15)
= 1|dd E
(16)
where the
first equality
comes
the E [s, a))
from
fact
that
includes
arg maxf:1/1l ( (s,a)
Via Hoeffding's ' inequality and union bound over F, we get that with probability at least 1 - 5, for all F:
< <2 In F(/8)
(s) and f(s
(17)
Estat
(18)
Denote
f = arg max
fef Beards f(s,a) - Ex f(s.
(19)
and
N
== arg max E, Egandr f(s, JEF
Σ f(s,, oz).
(20)
N
20

---

Published as a conference paper at ICLR 2025
Hence, for ft, we have:
|| d 111 = ga a(),a) - -B
(21)
N
1
a f(s,a)
[s5 + Estat
(22)
N
1
I Eg f(s
f(s a,) + Estat
(23)
N
S a (8) - R
f(8, a) + s
(24)
aa
(25)
where we use the optimality of # in the third inequality.
Recall that V = Es do, a)/(a111111 7), so we have:
v V
1- (E ((s, (e,,ad'))(s
(26)
sup, s.a (s(s
1|tt - d
(27)
1 --7
2
<
1 Sua
(28)
This concludes the proof.
21

---

Published as a conference paper at ICLR 2025
E.1 PROOF OF THEOREM 2.1
Proof. We first define some terms below. Denote := arg min ||dT - d=
||1. Let us denote:
f arg max fEJ
E aa f( -B,, Bs (s,
(29)
f arg max JEF
E Es f(s,a)
1
Σ
f(8
a.)
(30)
N
i=1
f'
arg max JEF
E. aa [f(s,
1
Σ
[( at)
(31)
N
Starting with triangle inequality, we have:
|
d=
11
- 1dt
d
[111 +
d
-d
(32)
[[(
Egand [[s,aa] + +f d=¹ |1
E
sand
(33)
N
1 N +
= =E,
[f(s.a]]
1
f(ss,
Σ (()
N
N
i=1
Bgaand [[(s,a]] + +110tt
d= -d
(34)
< Eggaand [F(s.a)]
1 - Σ f(s). a.)
1
Σ
f(s,, a.)
-Beand [F(s,a)
N
[Eaandr - Eggands f(s, a) + +11E0
(35)
In([F1/5)
< Bgaand [f((
(si (7) (00)))(+)) +.1
+ ||tt
R ||
(36)
N 1=1
N
[n((FF//))
< Egandi [s) - Ee.andr (f' + +4
+ +2
- E
(37)
N
[In[FF/5) N
<3 d 1d
dt +4V
(38)
where the first inequality uses the definition of f. the second inequality uses the fact that A is the minimizer of max Fgg ((8,a) - 1/2 EEE ((8), We also use Hoeffding's inequality
where vf E
In (1F1/5)
E Bg (() Σ ((st $
(39)
N
with probability at least - 6.
22

---

Published as a conference paper at ICLR 2025
F FURTHER EXPLANATION OF GUITAR AND PSDP
Algorithm 3 Policy Search Via Dynamic Programming (Bagnell et al., 2003)
1: Input: Reward function r,, reset distribution p. and policy class II
2: Output: Trained policy π
3: for h H,
do
4: Optimize
Th + arg max Eeprpi Eas NTT (slos) r'ell
A7; A (sh: an.)
(40)
5: end for
1H 6: Return = {TAJE=1
Algorithm 4 GUiding Taters with Arbitrary Resets (GUITAR)
1: Input: Expert state-action distributions pg. mixture of expert and offline state-action distribu- tions Pmix, policy class II, reward class R
2: Output: Trained policy π
Set To E II
4: for = 1 to N do
5: Let
// Loss function
[(I,)) r) E(s.a)pp r(s,a) -(
(41)
6: Optimize
// No-regret reward update
arg max ( + + A rER
(42)
7:
Optimize
// Bxppetttcommetttiiee response with RL
T + PSDP(r rs. P Pmix)
(43)
8: end for
9: Return n; with lowest validation error
The full IRL procedure is outlined in Algorithm 4. It can be summarized as (I) a no-regret reward up- date using Online Mirror Descent, and (2) an expert-competitie policy update using Policy Search by Dynamic Programming (PSDP) as the RL solver, where the learner is reset to distribution in the RL subroutine.
Existing efficient IRL algorithms, such as MMDP (Swamy et al., 2023), reset the learner exclusively to expert states (i.e. the case where p = pF). GUITAR can seen as extending MMDP to general reset distribution in the misspecified setting. We will focus on expert resets in the misspecified setting first, and we then consider other reset distributions in Section
Policy Update. Following Ren et al. (2024)'s reduction of inverse RL to expert-competitive RL, we can use any RL algorithm to generate an expert-competitive response. We employ PSDP (Bag- nell al., 2003), shown in Algorithm 3, for its strong theoretical guarantees. In practice, any RL algorithm can be used, such as Soft Actor Critic (SAC, Haarnoja et al. (2018)).
Reward Update. We employ no-regret update the reward function. We employ Ouline Mirror Descent (Nemirovskij & Yudin, 1983; Beck & Teboulle, 2003; Srebro et al., 2011) for its strong theoretical guarantees, but in practice, any no-regret update can be used, such gradient descent.
More specifically, the reward function is updated through Online Mirror Descent, such that
T: f- arg max L( T4 (m,-1, + - ARAR r--1);
(44)
PER
23

---

Published as a conference paper at ICLR 2025
where An is the Bregman divergence with respect to the negative entropy function R. L(T, r) is the loss, defined by
r(T,r) = (((a))= ((s, a) - (o (88, 0),
(45)
with respect to the distribution of expert samples, PE-
24

---

Published as a conference paper at ICLR 2025
G PROOFS OF SECTION 3
G.1 PROOF OF THEOREM 3.3
Proof. We consider the imitation gap of the expert and the average of the learned policies ,,
H
H
V V
E EENEE
r (8. - Re h=1
[r(s,
(46)
1=1
A=1
-H-
(( (s, - r(s,
(47)
H 71
L(TerT")
(48)
< max N1 rER
((TTT))
(49)
i=1
< H max TER
(L(T),T) - L(TT,Tt) - ((TT.))))
(50)
L(m + H max
Σ (M ((T,
(51)
n. FER
Applying the regret bound of Online Mirror Descent (Theorem K.2), we have
In R Hy
v V² <
L( r:)
+
(52)
12
1
E (n
E
yo and (ihh, an))
H
H
k=1
h=1
In
R
+ H
(53)
In [R]
E s va
Eonn V.l.) + H. n
(54)
Ee Rn A (sh. (7h (x)) + H In R
(55)
n
n
Focusing on the interior summation, we have
H
H
B Bon (
(8h, an)
S
S max aed
A (Sh, a)
(56)
0=0
E
E max A (sh, a) -ff.A -1.b
(57)
asA
max sn (19) (sh, a) + eft.
(58)
E'e
h=
< H2 He
(59)
where the last line holds by PSDPP's performance guarantee (Bagnell al., 2003).
25

---

Published as a conference paper at ICLR 2025
Applying Equation 59 to Equation 55, we have
V V
E (ss A Pech (Sh; an)) + H
In R
(60)
71
In R ( Hefr H
(61)
n1
In R
S 11 + Hef + H
(62)
which completes the proof.
26

---

Published as a conference paper at ICLR 2025
H PROOFS OF SECTION 4
H.1 LEMMAS OF THEOREM H.5
Lemma H.1 (Reward Regret Bound). Recall that
((,,)) ((s.a))po (f
(63)
Suppose that we update the reward via the Online Mirror Descent algorithm. Since S r(s, a) S for all 8, a, then suPREl..ERR MT, r) S 1. Applying Theorem K.2 with B 1, the regret is given by
An sup
1
Σ ((
1 Σ ( n
(64)
PER n
In [
(65)
C1
(66)
where C 2m [R] and is the number of updates.
Lemma H.2 (Statistical Difference of Losses). With probability at least 1 - 5,
C
Ma, s((,r)
(67)
N'
where C. In 2|R] and N is the mumber of state-action pairs from the expert.
Proof. By definition of and f. for any π E II and r E R, we have
[(z,r) [(T,T)
B (er.a)afur(s.. B(saaaa
((eea) (s,,a) a) r(s,
(68)
(( er (s,
(69)
1
Σ
r(s))a))
(70)
(saa,)EDs
1
2
(71)
2N
8
C
(72)
N
where C = 4n I|R|, The fourth line holds by Hoeffding's inequality and union bound. Specifi- cally, we apply Corollary K. with e = 1, since all rewards are bounded by and 1. We take union bound over all reward functions in the reward class R. Note that the terms involving cancel out, so the union bound only applies to the reward function class R. Rearranging terms gives the desired bound.
Lemma H.3 (Advantage Bound). Suppose that 0 and reward function r; the input parame- ters to PSDP, and म. = (T] m....., T'H) is the output learned policy. Then, with probability at least 1 8,
Co N
Co +
Ex-AT max A ( (s. I min Pai + &ft aEA
Cp
&ef
(73)
M
H the horizon, N the number of expert state-action pairs, M the number of offline state-action pairs, and Co 21n [nll]
where CB
d
27

---

Published as a conference paper at ICLR 2025
Proof. Suppose that is the imput accuracy parameter to PSDP, and the advantages computed under reward function r,. PSDP is guaranteed to terminate and output a policy T = ...... ..... T such that
He 2 max Ees Phiss BaNT (-1) (11)) ($hx a) x'ell
(74)
for all h E [M] (Bagnell et al., 2003). Consequently, we have
He max Enr (1)
(75)
x'Ell
max pam Ban (s, a) +
Pnin 11.r.
-1,
Pais
(76)
x'Ell
Egreai
max A (s, a) =TT,r
Puis
(77)
aeA
By definition, 0 5- Paix S ElI, so for any x E R. x 11,r, 2 r C11
Hc 2 Eg-ppe max A A (s, a) Llix
(78)
aEA
Rearranging the terms gives us
E Pm
max 15t - He + en aEA
(79)
c1
(80)
where the last line holds by our assumption that 6 = O.
Case 1: Jettison Offline Data. We will first consider the case where offline data is useless, in which case we will focus on the expert data.
Note that max A AT (s,
for all E S and h E [H]. Applying the definition of pmix.
Ex--pmc max A (s, a) Eseps max A (s, a) + Esppp max A A as) aeA
(81)
aEA
acA
Consequently, we know that
2 E
Egspp max A (s) 0)
(82)
111
aed
N
max A (s),a)
(83)
N
aEA
sEDE
Because max A (s.a) 2 0 for all s E S and A. know A S ct for all 8; E DE. We apply Hoeffidingss s incquality (Corollary K.I) with e = (efrin (efra)² to bound the difference between ExNanE max As, a) and Exppe max ( a). We apply a union bound on the policy and reward function. As stated previously, max A (s, a) 2 0 for all E S. By Hoeffding's inequality, with probability 1 - ō, we have
E B E max A (s, a) - EEnpe max A (s, aEA
= E Bgnd max A (5 a) aeA
(84)
aEA
max A (si, a)
(85)
N
aEA
REDE
|
Sv
(Cf
In
(86)
2N
Co N
<en
<
(87)
Note that the cardinality of the set of advantage functions over all possible policies is upper bounded by the cardinalities of the policy and reward classes. Rearranging the terms and applying Equation 82 yields
where Co In |
Co N
E Badd max ( a) < Pnis aEA
11
+
1I
Pnis
(88)
28

---

Published as a conference paper at ICLR 2025
Case 2: Leverage Offline Data. Next, we consider the case where offline data is useful. specifically where there is good coverage of the expert data.
Next, we apply Hoeffding's inequality (Corollary K.1) to bound the difference between (s, Egsy A A a) and Ex-pang m AT. We apply a union bound on the policy and reward function. We use c eñ for a similar argument to the one used in Case As stated previously, A (s, a) 2 for all E S. By Hoeffding's inequality, with probability 1 - 6, we have
E Egoy max A a) - -Eg Egrpp max A (s. aEA
E Bgny max A (s a) aEA
(89)
acA
1
E
max A Ari (st,
N + M
#EE DEDN+M N+M
aeA
Pmin 2
1
In
11 R
(90)
2(N + +M)
8
Co
S
(91)
N +
M
Note that the cardinality of the set of advantage functions over all possible policies is upper bounded by the cardinalities of the policy and reward classes. Rearranging the terms and applying Equation 79 yields
where Co 2n
|
Co + M
E EaND max A (s, S Puix + f1 aEA
Puis
(92)
By linearity of expectation, and using the fact that S CB < co, we have
N
Ex max A (s,
E BondrE max A A a)
oEA
N + M
aEA
M
+
EE max A (s,a) aEA
(93)
N + M
N
B max TT (s, a)
N M
AEA
M
CB
E
E max A (s,a) aEd
(94)
N
+
M
N
CB
E
E max A ( a)
N + M
aEA
M
CB
EE Eend
max A (s,a)
(95)
N + M
aeA
< CR max A (8. aeA
(96)
Applying Equation 96 to Equation 92, we have
Eg-aTe max Art CBE max AT (5, aEA
(97)
Co
CB
Onis
+ f
Pui
(98)
N + M
Final Result. Using the bounds from Case I and Case 2, we have
Co
Exndre max A (s, min aeA
(99)
'll
V
N
Co
CB
Prix + cl V
(100)
N + M
29

---

Published as a conference paper at ICLR 2025
is the horizon, N is the number of expert state-action pairs, M is the number of offline state-action pairs, and CG 2 [R]
where Cg
Lemma H.4 (Loss Bound), Suppose that and reward function v; the input parameters to PSDP, and x; = (mi, ;T. is the outpua learned policy. Then, with probability at least 6,
Co N
Co N M
}
C N
L(Ti, ri) S min
Pui T
+
CB
6TTT
+
+ Pmix
+
(101)
where CB
H is the horizon, N is the number of expert state-action pairs, M is the
dy
number of offline state-action pairs, Co = 2 In [ and C = In 2|
Proof. By Lemma H.2, we have
C ((T,)r)) S ((T.)r))) V/-
(102)
C
((.a))afE (ri(s,a]] (c.a)aa [ri(s,a)]+
(103)
N
C
(V - Viti) + V
(104)
H
1
(sn Jad A (sh, an)
C
(105)
H
N
H
C
Bag rd
max A (sh,
+ N
(106)
H
aeA
C
HE max A (8, a)
(107)
H
where C = In 2|R| The second line holds by the definition of L(T,, r.), and the third line holds by the definition of the reward-indexed value function. The fourth line holds by the Performance Difference Lemma (PDL). Applying Lemma H.3, we have
Co
Co N
}
C VVVN
[(m,)r)) min
II
CB
+ +1
Paik
V
M
+
N'
(108)
where Cg
is the horizon, N is the number of expert state-action pairs, M is the
number of offline state-action pairs, Co 2 ln [ and C In 2|
30

---

Published as a conference paper at ICLR 2025
H.2 FINITE SAMPLE ANALYSIS OF ALGORITHM 2
Theorem H.5 (Sample Complexity of Algorithm 2). Suppose that PSDP's accuracy parameter set to ε = 0. Then, upon termination of Algorithm with probability at least 1 ô. we have
CHI.R
CH.
CR
In R
V V S H min
Dau + F1
Pau
CBB
61 + f V (
H
Statinical Fome
Resond Regeet
Mixpoecthaationn Eveor
(109)
where H is the horizon, N the number of expert state-action pairs, M the number of of- fline state-action pairs, n. is the number of reward updates, CH, = [
Cr = In and
1 1 CB E
x
Theorem H.5 upper bounds the sample complexity of Algorithm 2 in the offline data setting. The bound differs from Theorem 3.3 in the following ways. First, the policy optimization error term vanishes by the assumption that O. Importantly, the assumption of 0 is not necessary but rather convenient, as the > O case was presented in Theorem 3.3. Second, offline data is incor- porated into the reset distribution, resulting in a modified misspecification error. Finally, the finite expert sample regime is considered, resulting in statistical error of estimating the expert policy's state distribution d with the distribution over samples pE. We use this concentrability coefficient CB with respect to the expert policy for Theorem H.5 in order to obtain tight bound on the sample complexity.
Proof. We consider the imitation gap of the expert and the averaged learned policies, ,,,
H
Σr (sh, an) .mi))
V
V
EC
Σ
(sn (sn an)
r
Σ h=1
(110)
1=0
1==1
-
-B(ao)aa [r' (r((s,))]]
(111)
[(T
(112)
t=0
max FER
Σ L(T.,r)
(113)
n
where n is the number of updates to the reward function. The second line holds by definition of d" The third line holds by definition of L.. Applying the Statistical Difference of Losses (Lemma H.2), we have
((ss,)) + V/
C
V V <
H max TR
(114)
1=
H max ER
(( - i. rz) (mTT)))) +
C
(115)
N
where In || and M is the number of state-action pairs from the expert. Applying the Reward Regret Bound (Lemma H. H), we have
[(m,)))) +
C
+
H
(116)
N
n
where C1 2n /R). Applying the Loss Bound (Lemma H.4), we have
Co N
Co M
vTB Vス
H
min
El1
El1
V
CB
+
E11
+
C1
H
(117)
N
n
31

---

Published as a conference paper at ICLR 2025
which simplifies to
Co CB V N
Co V N
} + H V c N H
G
V v S H min
1I
Puix
fl
Pais
ftth +
fi
M
(118)
d
where Cg
H is the horizon, N is the number of expert state-action pairs, M is the number of offline state-action pairs, n is the number of reward updates, Co 2 [
d,
C
R| and C1 2n (R].
Proof Sketch of Corollary 4.1. The proof follows from Theorem H.5, and more specifically, Lemma H.3. The notable change is, instead of using the concentrability coefficient with the ex- pert policy, TE, we use a concentrability coefficient with respect to the optimal realizable policy, n², such that
d
O
(119)
Then, in Case 2 of Lemma H.3 (Equation 94), we perform the change of distribution from d to d= and then to d resulting an additional TV distance to bound the first distribution change. Notably, this factor is independent of our offline data, and because TV distance is positive, it can be added to both Case and Case 2, resulting in a tradeoff that depends solely on the offline data distribution's coverage of x='s state distribution, as well as the other standard terms (СπI number of expert samples, number of offline data samples, etc). We use the standard concentrability coefficient CB with respect the expert policy for Theorem H.5 in order to obtain tighter bound the sample complexity.
32

---

Published as a conference paper at ICLR 2025
1 IMPLEMENTATION DETAILS
We describe the implementation details in this section. We compare GUITAR against two behavioral cloning baselines (Pomerleau, 1988) and two IRL baselines (Swamy al., 2023). The first behav- ioral cloning baseline is trained exclusively on the expert data, BC(Tx). and the second is trained on the combination of expert and offline data, BC(TF + mh). when offline data available. We compare against two IRL algorithms: (1) Swamy et al. (2021a)'s moment-matching algorithm, MM, a traditional IRL algorithm with the -aasenn-hannon divergence replaced by an integral probability metric, and (2) Swamy et al. (2023)'s efficient IRL algorithm, FILTER, that exclusively leverages expert data for resets.
We train all IRL algorithms with the same expert data and hyperparameters: The difference between MM, FILTER, and GUITAR can be summarized by the reset distribution they use. MM resets the learner the true starting state (i.e. p ()), while FILTER resets the learner to expert states (i.e. PF). GUITAR resets the learner to offline data (i.e. = pn), when offiine data is available, and otherwise resets subset of the expert data. In other words, isolate the effects of the reset distribution by using the same underlying IRL algorithm but simply change the reset distribution used in the RL optimizer step. This makes GUITAR easy implement and easily adaptable to other IRL algorithms.
We adapt Ren al. (2024)'s codebase for our implementation and follow their implementation de- tails. We restate Ren et al. (2024)'s 's details here, with modifications where necessary. We apply Optimistic Adam (Daskalakis al., 2017) for policy and discriminator optimization. We also apply gradient penalties (Gulrajani et al., 2017) 7) on all algorithms to stabilize the discriminator train- ing. The policies, value functions, and discriminators are all 2-layer ReLu networks with a hidden size of 256. We sample 4 trajectories to use in the discriminator update at the end of each outer-loop iteration, and batch size of 4096. In all IRL variants (MM, FILTER, and GUITAR), we re-label the data with the current reward function during policy improvement, rather than keeping the labels that were set when the data was added to the replay buffer. Ren et al. (2024) empirically observed such re-labeling improve performance. We release forked version of Ren al. (2024)'s code: https: / mwcooinesseee espinosadice ce .itthu.......................... 1o/e se/ffficieet IRL/.
We calculate the inter-quartile (IQM) and standard errors across seeds for all experiments.
1.1
MuJoCo TASKS
1.1.1 SETTING WITHOUT GENERATIVE MODEL ACCESS
We detail below the specific implementations used in all MuJoCo experiments (Ant, Hopper, and Humanoid).
PARAMETER
VALUE
BUFFER SIZE
lE6
BATCH SIZE
256
7
0.98
T
0.02
TRAINING FREQ.
64
GRADIENT STEPS
64
LEARNING RATE
LIN, SCHED. 7.3E-4
POLICY ARCHITECTURE
256 x
STATE-DEPENDENT EXPLORATION
TRUE
TRAINING TIMESTEPS
1
Table 1: Hyperparameters for baselines using SAC.
Expert Data. To experiment under the conditions of limited expert data, we set the amount of expert data to be the lowest amount that still enabled the baseline IRL algorithms to learn. For Ant, this was 50 expert state-action pairs. For Humanoid, this was 100 expert state-action pairs. For Hopper, this was 600 expert state-action pairs.
33

---

Published as a conference paper at ICLR 2025
Joint
Default
Modified
Body Part
Default
Modified
Right hip_x
--55,,5 5
[00
Right thigh
0.06
0.09
(+50%)
Left hip x
[-25 5
10.30% 30
Right foot
0.075
0.1
(+33%)
Left knee
|- --600 2
100", 50%
Left lower arm
0.031
0.04
(+29%)
(a) Joint angle range differences
(b) Size parameter differences
Table 2: Comparison between default and modified Humanoid configurations.
Offline Data. We generate the offline data by rolling out the expert policy with probability Puremlee of sampling random action. a 0.25 for the Ant environment and Piremblc 0.05 for the Hopper and Humanoid environments.
Discriminator: For our discriminator, we start with learning rate 8e-4 and decay it linearly over outer-loop iterations. We update the discriminator every 10,000 actor steps.
Baselines. We train all behavioral cloning baselines for 300k steps for Ant, Hopper, and Hu- manoid. For MM and FILTER baselines, we follow the exact hyperparameters in Ren et al. (2024), with a notable modification to how resets are performed, discussed below. We use the Soft Actor Critic (Haarnoja al., 2018) implementation provided by Raffin al. (2021) with the hyperparam- eters Table 1.
Reset Substitute. We mimic resets by training BC policy on the reset distribution specified by each algorithm. MM does not employ resets. FILTER's 's reset distribution is the expert data. GUITAR' reset distribution a mixture of the expert and offline data. The BC roll-in logic follows Ren et al. (2024)'s reset logic. The probability of performing non-starting-state reset (i.e. an expert reset FILTER) is a. non-starting-stale reset is performed, we sample a random timestep between 0 and the horizon, and we roll out the BC policy in the environment for / steps.
GUITAR. GUITAR follows the same implementation and reset logic as FILTER, with the only change being the training data for the BC roll-in policy.
1.1.2 MISSPECIFEE SETTING II: DIFFERENT DYNAMICS
For these experiments, we use the same parameters in Section I.1.1, with the following changes.
Expert Data. We use the same expert policy in Section I.1.1. 1. However, we do not consider the finite expert sample regime, so we use 100,000 state-action pairs from the expert policy. Notably, this expert policy uses the default configuration (i.c. the default MJCF file, MuJoCo's XML file specifying the robot's morphology, including link lengths and joint ranges) we collect expert data by rolling out the policy with the default morphology.
Offline Data. We generate the offline data by training policy under a new configuration, specified below, otherwise following similar setup to training the expert policy. We collect 100,000 state- action pairs from the offline policy by rolling it out with the new morphology.
Baselines. We train all behavioral cloning basclines for 300k steps for Humanoid and Ant. For MM and FILTER baselines, we otherwise follow the exact hyperparameters in Ren et al. (2024), except for varying the robot's morphology. We use the Soft Actor Critie (Haarnoja al., 2018) implementation provided by Raffin et al. (2021) with the hyperparameters in Table 1.
MM resets the learner to the true starting state, so no changes are needed. FILTER resets the learner expert states. However, due to the difference in morphology between the expert and learner, it is not possible to reset the learner to expert states. Therefore, F FILTER cannot applied in this misspecified setting.
Resets.
34

---

Published as a conference paper at ICLR 2025
Joint All Hip joints
Default
Modified
[300 30
[-20,, 40 [409 60" 20%)
Front Ankles (1,4)
[30", 70
Back Ankles (2,3)
70" 30
(a) Joint angle range differences
Body Part
Default
Modified
Auxiliary segments
0.08
0.11
(+38%)
Leg segments
0.08
0.11
(+38%)
Ankle segments
0.08
0.11
(+38%)
(b) Geometry size differences
Table 3: Comparison between default and modified Ant configurations. All changes are applied consistently to all four legs.
GUITAR. GUITAR follows the same implementation as FILTER, with the notable change of its reset distribution. Unlike FILTER, GUITAR resets the learner to the offline data, and in contrast to resetting expert states, is possible in this case, since the offline behavior policy and the learner have the same morphology.
Learner. The learner, in both the training and evaluation environments, has modified morphol- ogy, as indicated by Table and for Humanoid and Ant, respectively.
1.2
D4RL TASKS
1.2.1 RESETTING TO SUBSETS OF S STATE DISTRIBUTION
For the two Antmaze-Large tasks, we use the data provided by Fu et al. (2020) as the expert demonstrations. We append goal information the observation for all algorithms following Ren et al. (2024); Swamy et al. (2023). For our policy optimizer in every algorithm, we build upon the TD3+BC implementation of Fujimoto Gu (2021) with the default hyperparameters.
Expert Data and Discriminator. We use the relevant D4RL dataset to learn the discriminator. For our discriminator, start with learning rate of Se - 3 and decay it linearly over outer-loop iterations. We update the discriminator every 5,000 actor steps.
Baselines. For behavioral cloning, we run the TD3+BC optimizer for 500,000 steps while zeroing the component of the actor update that depends on rewards. We use reset proportion of a 1.0. We provide all runs with the same expert data. All IRL algorithms are pretrained with 10,000 steps of behavioral cloning on the expert dataset.
Reset Distributions. We reset GUITAR to various reset distributions. We consider the expert dataset, short trajectories (of length less than 500) in the expert dataset, and long trajectories (of length greater than or equal to 500) in the expert dataset. We use each of these datasets as different reset distributions. For the D4RL tasks, we perform true state resets (i.e. reset the learner to states the reset distribution), rather than perform BC roll-ins as done in the MuloCo tasks. Notably, IRL with resets to the true starting state distribution (i.e. no selective reset distribution) has been well studied by prior work (Swamy et al., 2023; Ren et al., 2024) and observed to not solve the Antmaze-Larg tasks.
1.2.2 MISSPECIFIED SETTING I: UNREACHABLE EXPERT STATES BLOCK OBSTRUCTION
For the expert action misspecification experiments, we train an RL expert using TD3+BC. We ap- pend goal information to the observation for all algorithms following Ren et al. (2024); Swamy al. (2023). For our policy optimizer in every algorithm, we build upon the TD3+BC implementation of Fujimoto & Gu (2021) with the default hyperparameters.
35

---

Published as a conference paper at ICLR 2025
ArtmaarnD
2G
26
Figure 5: We plot the coverage of the D4RL Antmaze-Large expert data, including the full dataset, short trajectories (episodes shorter than 500 steps), and long trajectories (episodes 500 steps or longer).
Expert Data and Offline Data. We collect expert data by first training an RL expert using TD3+BC on the following maze map:
1
1
0
0
0
Mag ==
R
1
1
0
0
1
where is the starting state and G is the goal state. The expert policy is then rolled out for 100,000 state-action samples. We collect the offline data by training RL agent using TD3+BC on the following maze map:
1
17
1
1
0
0
M
1
R
1
0
0
0
1
1
and then rolling out the policy for 100,000 state-action samples. The differences between M and Maa are bolded.
Discriminator. We use the expert data to learn the discriminator. For our discriminator, we start with learning rate of 8e-3 and decay linearly over outer-loop iterations. We update the discrim- inator every 5,000 actor steps. We use 10 sample trajectories for the discriminator update. Since this a strongly misspecified setting, we only use the x-position of agent as the input to the discriminator for all IRL. algorithms. The explanation for this design choice is that the learner's and the expert's 's behaviors may differ how they solve the maze (i.c. the y-position). but the goal is to finish the maze in some way (i.e. dependent the z-position).
Baselines and Reset Distributions. For behavioral cloning, we run the TD3+BC optimizer for 500,000 steps while zeroing out the component of the actor update that depends rewards. We use a reset proportion of = 1.0. We provide all runs with the same expert data. Due to the strong misspecification in this task, do pretrain the IRL algorithms with behavioral cloning.
36

---

Published as a conference paper at ICLR 2025
MM is reset the true starting state, while FILTER is reset to the expert data. GUITAR is reset to the offline data (i.e. TB s data).
Misspecification. The learner is trained and evaluated the map M Notably, this difference ensures that the expert policy solves the maze via one path, and the learner must solve in a different path, where the only shared states collection, as well as the learner's s environment, we add a BackWal 1 Coalllll @ocoalleee Wrapper, which allows the expert achieve reward of 1.0 by solving the maze through the "top hallway," but due the block in the learner's s maze, the learner is only able to achieve reward of 0.9 by solving the maze through the "bottom hallway." The BackWallGoan fack#aalGolllaapperr required z-position solve the maze is 4.0.
be the start and goal states. For the expert and offline data
should be noted that this is not the typical Antmaze-Umale task, which can typically be solved by IRL. approaches. In this setting, we consider the strongly misspecified setting, where the expert policy solves the maze one way, but the learner must solve it differently due differences in the maze "test-time." The degree of exploration difficulty due to the misspecification is likely the reason for the poor performance of the baselines.
1.2.3 MISSPECIFIED SETTING I: UNREACHABLE EXPERT STATES TIME CONSTRAINT
Expert Data and Offline Data. We train an expert policy via RL to solve the Motmaze-Umazer task and roll out the policy in the default Umaze configuration to collect 100,000 state-action pairs. We use the same policy for the offline data, but we stop the roll-out once the "safety constraint" is reached (described below). This means that the offline data consists of only states from the "first hallway" in the maze.
Misspecification. To incorporate a "safety constraint," such that the learner is not able reach the "bottom halllway" the maze, we impose time constraint in the leamer'' environment, such that after "T=50" steps, the episode terminates.
Discriminator. We use the expert data to learn the discriminator. For our discriminator, we start with a learning of 8e 3 and decay it linearly over outer-loop iterations. We update the dis- criminator every 5,000 actor steps. We use 10 sample trajectories for the discriminator update. We use full agent's 's observation for the discriminator input.
Baselines and Reset Distributions. For behavioral cloning, we run the TD3+BC optimizer for 500,000 steps while zeroing out the component of the actor update that depends on rewards. We use reset proportion of = 1.0. We provide all runs with the same expert data. Due to the strong misspecification in this task, we do not pretrain the IRL algorithms with behavioral cloning.
MM is reset the true starting state, while FILTER reset to the expert data. GUITAR is reset to the offline data (i.e. Tg's s data).
37

---

Published as a conference paper at ICLR 2025
J SETTING WITHOUT GENERATIVE MODEL ACCESS
We consider two additional constraints common in real-world robotics applications: settings with finite expert data and environments without generative model access (i.e. where the robot cannot be reset to an arbitrary state), To ensure we train in the low-data regime, we used the minimum amount of expert data that allowed the baseline IRL algorithm (MM) to learn in each environment (notably, less than one full episode). The offline data was generated by rolling out the pretrained expert policy with a probability Piremble of sampling a random action. We mimic resets by rolling in with BC policy trained on the corresponding reset distribution. More specifically, F FILTER's reset distribution consists of the the expert states, so FILTER rolls in with BC( GUTTAR'S reset distribution is mixture of expert and offline states, GUI rolls in with BC(TE + Tb). MM continues to reset to the environment's true starting state.
Hopper-13, Plommle 0.01
Ant-v3,
Humamoid-r3, Piuubbi 0.01
10M [[+]
IQM [(z]
4000
2000
IQM
2000
0.0
0.2
0.4
0.5 Steps
03
1.0
0.2
0.44
10.6
0.8
1.0
0.0
0.2
0.4
066
08
100
X10
Ens: Steps
X10
Steps
x10*
[C(
(C( Tgg)
MM
FILTER, 0.5
GUITAR, 0.5
Figure 6: Environment without arbitrary reset access. Standard errors are computed across seeds. Expert data is partial trajectory (i.e. subset of one full trajectory).
Based on Theorem 4.1, the sample efficiency of IRL should improve as the reset distribution's coverage of the expert's state distribution improves. More formally, this is when
d CB
1,
(120)
p
where d is the expert's state distribution and p is the reset distribution. Since GUTTAR resets BC(*E + m)), the performance of BC( π&) is estimation of the GUITAR's reset distribution's coverage of the expert's 's state distribution, and correspondingly for FILTER's reset distribution and BC(TF). From Figure improves-as measured by the corresponding BC performance-so does the performance of the IRL algorithm. In the case where the BC performance poor (Humanoid-v3), there is no observable benefit to modified resets.
that the reset distribution's 's coverage of the expert's states
38

---

Published as a conference paper at ICLR 2025
K
USEFUL LEMMAS
Theorem K.1 (Hoeffding's Inequality). If Zi...., ZM are independent with P(a S 2, s b) and common mean μ, then, with probability at least 8,
Z 1l S
c
In
(121)
2M
where NJ E (b: az)²
Lemma K.2 (Online Mirror Descent Regret). Regret is defined as
An
inf E 21)
(f,
(122)
FEF
Given J = AFF) and (f, V.) Ep el((f' (Zt, ve)),, where SupvED V
1000 B, let R be any
2supec R(F)
1-strongly convex function. If we use the Mirror descent algorithm with 1J
then,
NB
2B2 suprer R(f)
An S
(123)
If R is the negative entropy function, then SuPrE R(f) < log |F
39


Reviews:
[{"review_id": "Ky4SJm7FcD", "reviewer": "Reviewer_5fqP", "summary": "Define misspecification as the expected difference in advantage between an expert policy (taking the optimal action at each state), and a state conditioned policy. Then define an IRL algorithm which searchers for reward using a loss defined by the expected difference in reward under the expert and policy distribution with a divergence constraint to prevent stepping too far, and updating the policy with PSDP. Then, resetting to offline data is analyzed as a complement to resetting to expert data.", "questions": "See Weaknesses", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This work introduces a novel metric for misspecification.\n\nThe work offers an interesting perspective on the relationship between IRL and Offline RL\n\nThe proposed algorithm shows empirical results that match some of the theoretical claims", "weaknesses": "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?\n\nThe notation for the advantage function is not formally defined in the work, which makes it slightly more difficult to parse.\n\nWhile 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. \n\nThe 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. \n\nThe 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 somain such as this the expectation would be to cover a good portion of at least the deepmind control suite, especially the Franka Kitchen tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LYBzai4vdU", "reviewer": "Reviewer_EKUW", "summary": "The paper titled addresses a significant challenge in imitation learning (IL) by considering the setting when the expert's policy may not be fully realizable within the learner's policy class. This misspecified setting reflects real-world scenarios where the learner's capabilities may differ from the expert's, such as in robotic applications. It introduces reward-agnostic policy completeness to handle compounding errors even with this misspecification and proposes the GUITAR algorithm, which combines expert and offline data for efficient resets. Theoretical analysis and experiments on continuous control tasks are provided.", "questions": "- What is happening in the AntMaze experiment provided in the Appendix? I don't get what the conclusion from that experiment is.\n\n- 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?\n\n- Could you include a brief description of PSDP in the main paper to make it more self-contained?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper is theoretically robust, providing a thorough analysis of error sources in IL—optimization, finite sample, and misspecification errors—and offering a formal lower bound that emphasizes the challenges of efficient IRL under misspecification.\n\n- By addressing both limited data and misspecification, the paper proposes practical improvements for settings where ideal conditions (perfect data, full realizability) are unattainable, a scenario commonly encountered in robotics and autonomous driving.", "weaknesses": "- While the use of offline data is well-motivated, additional analysis of how different qualities and types of offline data affect performance could strengthen the results and offer practical insights for selecting such data.\n\n- 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. Simplifications or guidelines on choosing reset distributions could make it more accessible.\n\n- The authors' choice of not including the codes during the review process make the claims less transparent.\n\n- The main results are only provided in three MuJoCo environments. However, as has been understood in literature, compounding errors for offline IL algorithms like BC happen when the environment is stochastic. But the MuJoCo environments are almost deterministic where BC seems to perform really well [1] with very limited data. I wonder why no stochastic environments are used for evaluation.\n\n[1] Li, Ziniu, et al. \"Rethinking ValueDice: Does it really improve performance?.\" arXiv preprint arXiv:2202.02468 (2022).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xRJsudjNVx", "reviewer": "Reviewer_qn2v", "summary": "The paper studies inverse reinforcement learning (IRL) under the misspecification setup, i.e., the experts policy is not realizable within the policy class used for learning the policy. The paper presents a theoretical analysis of this case and introduces the measure of Reward-Agnostic Policy Completeness Error to quantify the misspecification under the imitation learning / IRL setup. This measure is used to obtain sample complexity bounds under the misspecification assumptions. Moreover, the paper argues that existing IRL algorithms that do not consider the misspecification assumption, rely on the expert's distribution for resetting, which is now in the misspecication setup not ideal any more as the expert distribution might contain states from which the learned policy can not reach the goal. For this case, the paper studies using additional offline data for the resetting the environment and the theoretical conditions when this is beneficial. The paper also contains limited experimental evaluation of this algorithm.", "questions": "- Please clearly motivate in which setup of misspecification you oberate (different state observations or different actions)\n- Provide a better motivation of the experiments and how they show a benefit in the misspecification setup\n- Experiments with an actual misspecification between expert and learned policy (even if only gridworld) would really help the paper\n- I was unclear about the mirror descent update rule for the reward. What the entropy of the reward R here? Is the rewward stochastic such that we can compute entropies? More information here would be useful (even though that might be described in previous papers, its not general knowledge and should be described in the paper as well briefly for self-consistency) \n- I was also unclear why in the case of approximate policy completeness, we have O(1) for the sample complexity error bounds. Please provide more detail here. \n\nIn general I like the paper, but the experiments do not show any application where misspecifcation is an issue. This is the main motivation of the paper and hence this should also be part of the evaluation. Happy to raise my score if the authors can provide experimental insights there.\n\nPost-Rebuttal: The new experiment show now a clear application in misspecification. Raised my score to 6.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- the paper formalizes a so far less considered problem, policy misspecification. The paper also introduces new interesting quantities such as the reward agnostic  Policy Completeness Error\n- the theoretical analysis of the paper is very interesting and looks sound. \n- the idea of using offline for the reset distribution is interesting", "weaknesses": "- 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. I am unsure whether (i) is really covered by the given theory and algorithm as this would require to use the partial observable setup (for both, expert and policy) where the theory probably does not hold any more. At least implementing resets to offline states might be very hard in the partial observable setup. Concerning (ii), while this could be covered by the theory as far as I understand, the experiments do not cover such a setup at all. This should be clarified in the paper. \n- 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 (i.e. most DNN policies can reproduce the optimal policy, at least in the setups considered in the experiments of the paper).\n- 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 (i.e. the expert has other action limits then the behavior policy). Such experiments would be much better suited to illustrate the benefits of the approach.\n- The presented experiments also hardly show any benefit of the presented method. E.g. I can not see any benefit in Figure 2. Alsothe experiment of Figure 3 is not well motivated. In this experiment, if I have the expert data, I can directly use it for the reset, why should I use less (I.e. the \"short trajectories\")? Seems to give the same performance...", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CJWJambM69", "reviewer": "Reviewer_iMEE", "summary": "This paper considers the interactive imitation-learning setting where policy realizability is violated. The paper further considers the setting where the reset distribution is a mixture of expert and a suboptimal policy, a more practical setting than reset distribution induced by just the expert policy. Based on these assumptions, the paper provides theoretical results on when the former reset distribution is more beneficial. Finally, the paper conducts few experiments to validate the theoretical findings and also identify potential gaps for future analysis.", "questions": "- To follow up on the previous point, I am curious how misspecification is validated in the experiments? Did the authors try running behavioural cloning on a large dataset and find that there is an inherit performance gap?\n- 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?\n\t- Perhaps I am confused about whether the roll-in for `FILTER` is using $\\pi_E$ rather than $BC(\\pi_E)$?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written and describes the theoretical results intuitively.\n- The misspecification setting is definitely a setting where previous works did not consider.\n- This work puts in a good effort to bridge the theory and application gap with experiments which I appreciate a lot", "weaknesses": "- Small writing nitpicks:\n\t- Page 6, equation 10 (or Algorithm 2): Should $n$ be $N$ (or the other way around) for the reward regret?\n\t- Page 6, line 315: Perhaps there should be some statement indicating why we cannot be more aggressive on $\\epsilon$ (e.g. $\\epsilon = 1/H^2$) (or why it does not make sense for this to happen).\n- 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:\n\t- 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.\n\t- 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.\n- For experiments, an alternative to using $p_{tremble}$ is to have mixture like $\\alpha \\rho_E + (1 - \\alpha) \\mu$ which I believe can be a way more realistic setting than random actions during data collection.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)