Interactive and Hybrid Imitation Learning: Provably Beating Behavior Cloning
Authors: Yichen Li
Chicheng Zhang
Venue: NeurIPS 2025 poster ()
Keywords: imitation learning
online learning
reinforcement learning
Primary area: reinforcement_learning
TL;DR: We reexamine the utility of interaction in imitation learning, and propose State-wise DAgger (Stagger) and its warm-started variant Warm-Stagger, that beats Behavior Cloning in terms of sample complexity.

Abstract: Imitation learning (IL) is a paradigm for learning sequential decision-making policies from experts, leveraging offline demonstrations, interactive annotations, or both. Recent advances show that when annotation cost is tallied per trajectory, Behavior Cloning (BC)—which relies solely on offline demonstrations—cannot be improved in general, leaving limited conditions for interactive methods such as DAgger to help. We revisit this conclusion and prove that when the annotation cost is measured per state, algorithms using interactive annotations can provably outperform BC. Specifically: (1) we show that Stagger, a one‑sample‑per‑round variant of DAgger, provably beats BC under low-recovery-cost settings; (2) we initiate the study of hybrid IL where the agent learns from offline demonstrations and interactive annotations. We propose Warm-Stagger whose learning guarantee is not much worse than using either data source alone. Furthermore, motivated by compounding error and cold‑start problem in imitation learning practice, we give an MDP example in which Warm-Stagger has significant better annotation cost; (3) experiments on MuJoCo continuous‑control tasks confirm that, with modest cost ratio between interactive and offline annotations, interactive and hybrid approaches consistently outperform BC. To the best of our knowledge, our work is the first to highlight the benefit of state‑wise interactive annotation and hybrid feedback in imitation learning.

Interactive and Hybrid Imitation Learning: Provably Beating Behavior Cloning
Yichen University of Arizona yichenl@arizona edu
Chicheng Zhang
University of Arizona chichengz@cs arizona.edu
Abstract
Imitation learning (IL) is paradigm for learning sequential decision-main making poli- cies from experts, leveraging offline demonstrations, interactive annotations, or both. Recent advances show that when annotation cost tallied per trajectory, Behavior Cloning (BC)-which relies solely on offline demonstrations-canne be improved in general, leaving limited conditions for interactive methods such as DAgger to help. We revisit this conclusion and prove that when the annotation cost is measured per state, algorithms using interactive annotations can provably outperform BC. Specifically: (I) we show that STAGGER, a one-sample-per-ronee variant of DAgger, provably beats BC under low-recovery-com settings; (2) we ini- tiate the study of hybrid IL where the agent learns from offline demonstrations and interactive annotations. We propose WARM-STAGGER STAGGER whose learning guarantee is not much worse than using either data source alone. Furthermore, motivated by compounding error and cold-start problem in imitation learning practice, we give an MDP example in which WARM-STTAGGER has significant better annotation cost; (3) experiments on MuloCo continuous-contry tasks confirm that, with mod- est cost ratio between interactive and offline annotations, interactive and hybrid approaches consistently outperform BC. To the best of our knowledge, our work is the first to highlight the benefit of state-wise interactive annotation and hybrid feedback in imitation learning.
Introduction
Imitation learning, also known learning from demonstrations, is widely-used approach for learning policies to make sequential decisions 45 6 5 In many applications, it offers a preferable alternative to reinforcement learning, it bypasses the need for carefully designed reward functions and avoids costly exploration
43 67).
Two prominent data collection regimes exist in imitation learning: offline and interactive. In offline imitation learning, expert demonstration data the format of trajectories is collected ahead of time, which is non-adaptive process that is easy to maintain. In contrast, in interactive imitation learning,
the learner is allowed to query the expert for annotations in an adaptive manner [51] 50 67 The
most basic and well-known approach for offline imitation learning is Behavior Cloning [49] [7].
which casts the policy learning problem as a supervised lcarning problem that learns to predict expert actions from states. Although simple and easy implement, offline imitation learning has the brak that the quality of the data can be limited 45). As result, the trained model can well suffer from compounding error, where imperfect imitation leads the learned policy enter unseen states, resulting in a compounding sequence of mistakes. In contrast, interactive imitation learning, the learner maintains learned policy over time, with the demonstrating experts providing corrective feedback on-policy, which enables targeted collection of demonstrations and improves sample efficiency.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Recent work [17], via a sharp analysis of Behavior Cloning, shows that the sample efficiency of Behavior Cloning cannot be improved in general when measuring using the number of trajectories annotated. Interactive methods like DAgger [49 can enjoy sample complexity benefits, but so far the benefits are only exhibited in limited examples, with the most general ones in the tabular setting [46 This leaves open the question:
Can interaction provide sample efficiency benefit for imitation learning under diverse settings, notably in the presence of function approximation?
In this paper, we make progress towards this question, with focus on the deterministically realizable setting (i.c. the expert policy π is deterministic and is in the leamnr'' policy class B3). Specifically, we make the following contributions:
1. Motivated by the costly nature of interactive labeling on entire trajectories 29 37,. we propose to measure the cost of annotation using the number of states annotated by the demonstrating expert. We propose a general state-wise interactive imitation learning al- gorithm, STAGGER, and show that as long as the expert can recover from mistakes low cost in the environment [51], it significantly improves over Behavior Cloning in terms of its number of state-wise demonstrations required.
2. Motivated by practical imitation learning applications where sets of offline demonstration data are readily available, we study hybrid imitation learning, where the learning agent can additionally query the demonstration expert interactively to improve its performance. We design a hybrid imitation learning algorithm, optimality guarantee not much worse than using either of the data sources alone.
and prove that its policy
3. Inspired by compounding error 445 and cold start problem [35] 42], we provide an MDP example, for which we show hybrid imitation learning can achieve strict sample complexity savings over using either source alone, and provide simulations that verify this claim.
4. We conduct experiments in MuJoCo continuous control tasks and show that if the cost of state-wisc interactive demonstration is not much higher than its offline counterpart, interactive algorithms can enjoy a better cost efficiency than Behavior Cloning. Under some cost regimes and some environments, hybrid imitation learning can outperform approaches that use either source alone.
2 Preliminaries
Basic notation. Define [n] := {l....,,] n.. Denote by ((X) the set of probability distributions over a set X. For u E A(x) and x E X, we denote by u(z) the z-th coordinate of u and e, the delta mass will also apply this shorthand to tuples, e.g. using (z, 1) to denote (I,, y.) We will frequently use the Hellinger distance to
on We use the shorthand T1:a to represent the sequence (z:),==
measure the difference between two distributions: D2, Q) = S((
dP
ddw, where IP and
Q share a dominating measure w.
episodic R, H), where S is the state space, A the action space, > A (S) denotes the transition dynamics, / E ASS) is the initial state distribution, P P x R A ([D, 1)) denotes the reward distribution, and H denotes episode length. | Given a stationary policy æ S > A(A), we use T-1s)) to denote the action distribution of a on state Rolling out policy in MDP M gives distribution over trajectories
Episodic Markov decision process and agent-environment interaction. A
MDP M is defined as tuple
(Sh, On oh, ) by first drawing the initial state $1 ~ p. and then iteratively taking actions ~ TT- sx), receiving rewards Th R(,,, an), and transitioning to the next state sh+1 ~ P(s), an) (except at step H). Let E= and Ix denote expectation and probability law for (8h, 4x rT) induced by and M. Given x, denote by d= (s) = 1. EM Ip (sh 5) its state visitation distribution. The expected return of policy π is detined J ((T) ET
Eit Th and the value functions of π are given by (s) = x E# PM 84 = s] and (s, a) = E. - / 8h. = 8, an = a) If for
11
Here we assume that the transition dynamics and reward functions are stationary. i.e., it does not depend on time step in the episode. To translate our results to the nonstationary transition dynamics and reward setting (to have fair comparison with [e.g.. [7[47] 47). augment the state with a step index, iec. define = (s. h).

---

policy step h, and state s, x(. s) is the delta-mass on an action, we also sometimes slightly abuse the notation and let π (s) denote that action.
Additional policy-related notations. Throughout, we assume the access to a class B of stationary policies of finite size B. A (MDP, Expert) pair (M, is said be ju-recoverable if for all E [H]. 8 E S and a E A, Q7 (s,a) - V/ (s) I μ. Additionally, we assume normalized return [77, where there exists some R > 0 such that for any trajectory ($), ah, rh) rolled out in M, Σh= E 10, R.. It always holds that f S R, while in many applications we expect μ to be much smaller [51] Section 2.2]. Throughout this paper, we make the assumption that our imitation learning problem is deterministically realizable:
Assumption 1 (Deterministic Realizability). The expert policy a is deterministic and is contained the learner's policy class B.
In our algorithm and analysis, frequently the following "convexification" of policy class B: Definition (Each-step mixing and each-step mixing policy class). For in (B)), define its each-step mixing policy ān as a stationary policy from S to ((A):
(u 3) == Σ u(()r((a s).
TEB
Define NT == (T E ABB) as B's each-step mixing policy class.
An each-step mixing policy F. 1Ig can be executed by drawing ग freshly-at-random each step h E [H] and taking action d₁ TT-(sh) (e.g. 33
Offline imitation learning and Behavior Cloning. In offline imitation learning, the agent is given collection of expert trajectories D [TI,..., TNuth J. where = (Si.A, (s.b 1/2 is the i-th (reward- free) trajectory, all of which are drawn iid from the trajectory distribution of expert policy E.
Behavior Cloning finds policy E B that minimizes its log loss expert's actions the states:
Notr
मे = argmin TEB
log T ((aihh (8.h))
A=1
Recent work of [17] establishes sharp bonizon-indeeendenn sample complexity bound of Behavior Cloning, which we recall here:
Theorem ((T7). Suppose Assumption 7 holds, then with probability 8, the policy returned by
BC â satisfies:
Rlog B Noff
- J(m - (+t) Sō
Interactive imitation learning protocol. In interactive IL, the learner has the ability query the demonstration expert interactively. A first way to model interaction with expert is through a trajectory-wise demonstration oracle ['ra 17 given state sequence (sk) return (ax) such that d₁ (sn. for all h. Subsequent works have considered modeling the interaction with
expert as interacting with a state-wise demonstration oracle [22 7 40 55 Statte given a state
8n and step return aş (s)). We consider the learner interacting with the environment and demonstration oracles using the following protocol:
For 1,2,
Select policy n' and roll it out in M, observing reward-free trajectory (8,,a),..., 8H, an).
Query the available oracle(s) to obtain expert annotations.
Goal: Return policy such that ( J(+) is small, with few number of queries to Traj or State.
In practice, we expect the cost of querying Tra) to be higher than that of collecting a single offline expert trajectory [29]. Since H queries State can simulate one query to Tiaii the cost of single State query should be at least E the cost of Trajj Consequently, we also expect one State query

---

Algorithm STAGGER: DAgger with State-wise annotation oracle
1: Input: MDP M, state- wise expert annotation oracle SSatte with query budget Nin,, stationary
state-wise
policy class B, online learning oracle A.
2: for n ,,...,,iin do
3: Query A and receive x²
4: Execute x" and sample s" d=". Query O for a"n = T (s").
5: Update with loss function
e" (T)) log TT(atm|sn)
(I)
6: end for
7: Output म., a first-step uniform mixture of Nint
to be more expensive than obtaining an additional offline (state, expert action) pair. We denote the ratio between these two costs as C, where C' 2 1 is an application-dependent constant.
3 State-wise Annotation in Interactive Imitation Learning
Recent work 11 refined analysis of Behavior Cloning (BC) casts doubt on the utility of interaction
in imitation learning: when measuring sample complexity in the number of trajectories annotated, BC is minimax optimal even among interactive algorithms [17] Corollary 2.1 and Theorem 2.2). Although benefits of interactive approaches have been shown specific examples, progresses so far have been sparse (7746),, with the most general results in the less-practical tabular setting [46). In this section, we reexamine this conclusion and show that interaction benefits imitation learning in fairly general sense in the general function approximation setting: when measuring sample complexity using the number of state-wise annotations, we design an interactive algorithm with sample complexity better than BC, long as the expert policy has a low recovering cost μ in the environment.
3.1 Interactive II. Enables Improved Sample Complexity with State-wise Annotations
Our algorithm STAGGER (short for State-wise DAgger), namely Algorithm I interacts with the demonstration expert using a state-wise annotation oracle Statee Similar to the original DAgger [51], it requires base policy class and reduces interactive imitation learning to no-regret online learning. At iteration it rolls out the current policy x² obtained from online learning oracle A. and samples state s" from d=t A classical example of A is the exponential weight algorithm that chooses policies from 1Ig (9) see also Proposition 41 in Appendix F). then queries State to get expert action t. and updates A with loss function t"(m (T) induced by this new example (Eq. (T)). The final policy क Niat is returned as uniform first-step mixture of the historical policies {nr In=l i.e., sample one n" uniformly at random and execute for the episode. In contrast to the DAgger variants analyzed
in [7 46] which trains a distinct policy at each step step-yielding H policies in total and employs trajectory-level annotations, our algorithm utilizes parameter sharing of the policy representation across all steps and uses state-wise annotations [
We show the following performance guarantee of Algorithm weight algorithm:
I with A instantiated as the exponential
Theorem 3. Suppose STAGGER is run with a state-wise expert annotation oracle State, an MDP M where (M, F) is p-recoverable, a policy class B such that deterministic realizability (Assumption / holds, and the online learning oracle A set as the exponential weight algorithm with decision space
obtaining a short segment of corrective demonstrations may be cheaper than querying Statt for each state therein. Thus, cost model may need refinements to match practical applications, which leave interesting future work. 'A one noe-ssamle-pee -eee-per-iie ver-iteaation version of Aggre Vate (50) has been analyzed in 2 Section 15.5). Our analysis follows similar structure and further takes direct advantage of the expert action feedback in DAgger and the deterministic realizability assumption to get refined sample complexity.
FFor practical settings such as human-in-the-loop learning with expert interventions 37 63

---

ngg. Then it returns ît such that, with probability at least 1 - 5,
J(x J(+) S pH log( (B) + 2 (bg(1/0)
Nint
Theorem 3 shows that STAGGER returns policy of suboptimality O ( log B) using Nint interactive
Noss
Wate-wise annotations from the expert. In comparison, with the cost of Nint state-wise annotations, one can obtain CNus H trajectory-wise annotations; [7'ss 's analysis shows that Behavior Cloning with
this number of trajectories from B returns a policy suboptimality O
RH log (recall Theorem 2
C.Nint
Thus, if C <<
R Algorithm has better cost-efficiency guarantee than Behavior Cloning.
We now sketch the proof of Theorem 3 estimation error as
In line with 17 we define the online, on-policy state-wise
OnEst
State
Σ
Band
[Di( [s), (.1s)))
The proof proceeds by bounding this error and translating it to the performance difference between स and ,². While our definition of estimation error is similar to [17] Appendix C.2]. their definition requires all H states per trajectory, while ours depends on the distribution over state sampled uniformly from the rollout of policy л" This enables each labeled state to serve as immediate online feedback, fully utilizing the adaptivity of online learning.
3.2 Experimental Comparison
We conduct a simple simulation study comparing the sample efficiency of log-loss Behavior
Cloning [17] and STAGGER in four MuJoCo 772 g continuous control tasks with H 1000
and pretrained deterministic MIP experts [52 53 Considering MuJoCo's low sensitivity to hori-
zon length [17), reveal expert states one by one along consecutive trajectories for BC to allow fine-grained state-wise sample complexity comparison, while STAGGER queries exactly one state per iteration by sampling from the latest policy's 's rollout and updating immediately with the expert's annotation. In STAGGER, we implement the online learning oracle A so that it outputs a policy that approximately minimizes the log loss. In addition log loss, we also include results with online learning oracle minimizing historical examples' total square loss in Appendix G.2, We defer other implementation details to Appendix G
Figure 1 shows the performance of the learned policy as a function of the number of state-wise annotations. When each interactive state-wise annotation has the same cost offline (state, expert action) pair (C = 1), STAGGER has superior and more stable performance than Behavior Cloning. For given target performance (e.g., near expert-level), STAGGER often requires significantly fewer state-wise annotations than BC-escccillyy on harder though the gains are less pronounced on easier ones like Ant and Hopper. To highlight sample efficiency, we plot STAGGER using only half the annotation budget of BC; despite this, it still matches or surpasses BC on several tasks, suggesting meaningful benefits from interaction when small (e.g.. C = 3 for Walker).
Hybrid Imitation Learning: Combining Offline Trajectory-wise and Interactive State-wise Annotations
Practical deployments of imitation learning systems often learn simultancously from offline and interactive feedback modalities 227 20): for example, in autonomous driving [78 4 79 the learner has access to some offline expert demonstrations start with, and also receives interactive expert demonstration feedback in trajectory segments for subsequent finetuning. Motivated by this practice, we formulate the following problem:
Hybrid Imitation Learning (HyIL); Problem Setup. The learner has access to two complementary sources of expert supervision:
Not offline expert trajectories Dof ( [Nor]]. sampled i.i.d. from rolling E in M:
A state-wise annotation oracle State that can be queried interactively up Nint times.
5

---

Ant
Hopper
Half Cheetah
Walker
Expected Retumn
2000
M
2000
xia ahe
Number of Expert Annotations
Number of Expert Arnotations
Number of Expert Anmotations
Number of Expart Annotations
Stagger
Behavior Cloning
Expert
Figure State-wise sample complexity comparison between Behavior Cloning and STAGGER. Shaded areas show STAGGER matches or exceeds BC with 50% fewer annotations, achieving better state-wise an- notation efficiency.
the 10th-90th percentile hootstrap confidence intervals [15] over 10 runs.
Algorithm WARM-STAGGER: Warm-start STAGGER with offline demonstrations
Input: MDP M, state-wise expert annotation oracle State stationary policy class B, online learning oracle A. offline expert dataset Do of size Notf online budget Nins
2: Initialize A with policy class Byc {TT B T(sh) ubs Ah E [H], ((s,a)11 Dont.
3: for = 1,..., Nint do
4: Query A and receive x"
5: Execute x" and sample s ddd Query State for am x (s")).
6:
Update with loss function:
(T) = log aaa+.n sn)
(2)
7: end for
8:
Output: n, first-step uniform mixture of {n² ,,,
Each offline (state, action) pair takes unit cost, and the cost of an interactive query is C 2 1. The total cost budget therefore Non + C Nin- The goal is to return policy & that minimizes its suboptimality relative the expert policy J(x²) (ft).
We ask: can we design Hyll. algorithm with provable sample efficiency guarantee? Furthermore, can its performance surpass pure BC and pure interactive II. with the same cost budget?
4.1 WARM-STAGGERS Algorithm and Analysis
We answer the above questions by proposing the WARM-STAGGER algorithm, namely Algorithm 2 It extends STAGGER to incorporate offline expert demonstrations, in that it constructs Bbe. restricted policy class that contains policies in B consistent with all offline expert demonstrations (line 2}. subsequently performs online log-loss optimization on B&e where the state s" obtained by rolling out x" the MDP M, and the action ah is annotated by the state-wise expert annotation oracle State, For analysis, introduce the following definitions.
state-action pairs collected online,
Definition (Non-stationary Markovian policies). non-stationary Markovian policy
(V1...., VH) ) is a collection H mappings. with each vn. in ((A)5, where upon rolling out at every step E [H], the agent takes action an by sampling from vi(( (s)).
Definition 5 (Step-wise completion of stationary policy class). For stationary policy class B C
A(A)S, define step-wise completion to class of nonstationary Markovian policies:
= (1...,,,,. VH) E B, for all h E [H]}
In words, each B uses a possibly distinct policy Th from B to take action at step h. By definition, B
B is at most B# An interesting special case is the con-parameter sharing 47 17,, where the set of possible states visited different steps are disjoint (see setting 49
also footnote for examples), and B are factorized, in the sense that parameters associated with the policies at different steps separate. In this case, we have that B B and thus B = B.

---

Theorem 6. If WARM-STAGGER is run with state-wise expert annotation oracle SStase an MDP M where (M, is p r-reooverable, policy class B such that deterministic realizability (Assumption [1 holds, and the online learning oracle A set the exponential weight algorithm with each-step mixing policies, then it returns such that, with probability at least 1 5,
Rlog(B/0))
μH (b0((B///0))
-( SO min
Nott
Nint
where we recall that B S S BH and Bic
BBel S B.
Theorem shows that WARM-STAGOR finds a policy with suboptimality guarantee not signficantly worse than BC or STAGGER: first, Behavior Cloning using the offline data has suboptimality
guarantee of O
[1/((//6) (cf. Theorem 2), and WARM-STAGGER guarantee is worse by at most
Nor
a factor of H; second, STAGGER without using offline data has a suboptimality of O (utt log (B/8)
Nim
(ef. Theorem 3). which is par with the second term of Eq. 8 We conjecture that the log B dependence may be sharpened to log B, and leave this as an interesting open question.
Remark 7. One may consider another baseline that naively switches between BC and STAGGER based on a comparison between their bounds; however, such a baseline needs to know R and μ ahead of time. practice, we expect WARM-STAGGRR to perform much better than this baseline, since seamlessly incorporates both sources of data, and its design does not rely theoretical bounds that may well be pessimistic.
4.2
On the Benefit of Hybrid Imitation Learning
Theorem i perhaps best viewed as fall-back guarantee for WARM-STAGGER its performance is not much worse than using either the feedback source alone. In this section, we demonstrate that the benefit of hybrid feedback modalities can go beyond this: we construct an MDP, in which hybrid imitation learning has a significantly better sample efficiency than both offline BC and interactive prove the following theorem:
STAGGER. Specifically,
Theorem 8. For large enough S, H, A, there exists an episodic MDP M with S states, A actions, and horizon H, and expert policy T such that:
With (SS) offline expert trajectories for BC, the learned policy is -sbboppunl:
With Ω (HHS)) interactive expert annotations for STAGGER, the learned policy is (HH)- suboptimal;
With Ô H) offline trajectories and 0(1) expert interactions, WARM-STAGGER learns policy â such that J(x) B..
Theorem suggests that when HS >> max C. and C > F. WARM-STAGGER achieves expert-level performance with significantly lower cost than two baselines. To see this, observe that WARM-STAGGER has a total cost of O(S + C), which much smaller than ((HS) by BC, and Q(HSC) by STAGGER.
The MDP construction and simulation results. We now sketch our construction of MDP M. M has an episode length H = (log((S)) and action space of size greater than 10H. For each state, one of the actions is taken by the expert; the rest are "wrong" actions. We illustrate MM's state space on the left of Figure 2 specifically, it consists of the following subsets:
Unrecoverable state B = {b): 3: a special absorbing state that is unrecoverable by any action (dead).
Expert ideal states E, where E No: this model for example, autonomous driving agent driving stably on the edge of a cliff (51]. where any incorrect action transitions the agent to the unrecoverable state (c.g.. car falling off the cliff). Taking the expert action keeps the agent in E with high probability (1 - B), and with a small probability B8, moves the agent to E' (e.g., a safe slope).
Expert recoverable states E': this models the agent driving outside the edge of the cliff in safe slope. When in E', taking the expert action allows the agent to return to uniformly
7

---

w.p.1 8
Policy Performance
State Coverage
E' State Coverage
2.
E
Expected Return
Coverage Rotte
Coverage Rote
W
2.4
32-
12.
Number of Expert Annotations
Number of Expert Annotations
Number of Export Annotations
Expert Action
Wrong Actions
Expert
Stagger
WS (200)
WS (800)
(3200)
Figure 2: MDP construction and simulation results of algorithms with rewards assigned only in E. We evaluate WARM-STAGGER STAGGER (WS) with 200, 800, 3200 offline (state, expert action) pairs. All methods are evaluated under equal total annotation cost with C' 1. With 800 offline (state, expert action) pairs, WS significantly improves the sample efficiency over the baselines and explores E' more effectively.
sampled state in E. Taking a wrong action from E' leads to reaching recoverable state b' (e.g., rest area).
Recoverable state B' = {b'}: Not knowing how to act in b' will result in the agent getting trapped in b' for the episode.
We now briefly justify each algorithm's 's learning performance as stated in Theorem 8 First, BC only observes expert actions in E and E', but never in b'. As a result, near-expert performance at test time requires high coverage over E'; otherwise, BC's trained policy will likely incur compounding errors and get trapped in b'. Second, STAGGER suffers from a cold-start problem: early policies fail to explore E efficiently, and incorrect actions cause transitions into b. Consequently, coverage E grows slowly, and the policy may still fail on unannotated states in E even with ((HS) queries. Lastly, WARM-STAGES interactions to visit b' and query the expert, avoiding costly exploration in E' while matching expert performance.
benefits from offline data that fully covers E, and uses small number of
We also conduct a simulation of the aforementioned three algorithms in a variant of the above MDP with No 200, Ni 1000, // 100, and 3 0.08, using another reward function that assigns a reward of 1 only when the agent visits the states in E. Here, we let the online learning oracle A optimize 0-1 I Ioss on the data seen so far, which is equivalent to minimizing log loss under class of deterministic policies and discrete actions. Figure 2 shows return and state coverage as functions of the number of expert annotations, averaged over 200 runs
We observe that: (1) BC exhibits slow improvement, b' remains unseen (and thus unannotated) throughout training, resulting in poor performance even with substantial coverage (e.g., 80%) over E': (2) STAGGER is sample-ineffiiiet due to slow exploration over states in E, consistent with the cold-start intuition; (3) WARM-STACE STAGGER (WS), when initialized with limited (e.g.. 200) offline (state, expert action) pairs, still needs to explore E first before can safely reach E' without failure; and (4) VARM-STAGGER with sufficient offline coverage
E (e.g., initialized with 3200 offline (state, expert action) pairs) directly benefits from exploring b' with immediate performance gain, and enables safe and even faster exploration than the expert in E'.
4.3 Hybrid IL on Continuous Control Benchmarks
Following our earlier MuJoCo-based comparison of Behavior Cloning and STAGGER, we now evaluate WARM-STAGGER (WS) on the same benchmarks. This experiment aims to answer: Does WS reduce total annotation cost compared to the baselines?
Based on the observation in Figure I we assign 400 total state-wise annotations for Hopper and Ant, and 1200 for HalfCheetah and Walker2D. For WARM-STAGGER, we allocate 1/8, 1/4, or 1/2 of the total annotations to offline data, with the remainder used for interactive queries. For fair comparison, all methods are evaluated under the same total annotation cost, with C 1 or C This makes the baselines stronger, they have full cost budget assigned to single source.
8

---

Hopper
Ant
Half Cheetah
Walker
Exprcted Return
130
180
30 16
30
30
16
x0 20
XE 200
30
Number of Expert Annotation
Number Expert Annotations
Number of Expert Annotations
Number of Expert Annotations
Expected Return
150
1300
238
Expert Annotation Costs (C
Expert Annotation Costs (C 2)
Export Annotation Costs 2)
Expert Annotation Costs (C
WS(100)
(5|/5]] wS]E0o) WS[200]
-S[150) -W]3000 W51600)
W50150) W5(300) W5(500)
Expert
Stagger
Behavior Cloning
Figure Sample and cost efficiency on MuJoCo tasks. The top row shows expected return vs. number of annotations (C 1); the bottom row shows performance in a cost-aware setting (C = 2). WARM-STAGGER (WS) initialized with 1/8, 1/4, or 1/2 of the total annotation budget as offline demonstrations. Specifically, WS(n) refers to WS with offline expert trajectory demonstrations of total length n. For good range of n's, WS(n) matches STAGGER in sample efficiency and outperforms the baselines when C 2.
In terms of the number of state-wise annotations (C' = 1), the results align with our theoretical findings: WS performs not significantly worse than BC STAGGER, regardless of the offline dataset size. WS still achieves performance competitive with STAGGER, and even outperforms it on Ant when 1. Furthermore, as shown by the purple curves, WS with appropriate offline sample size has preferable performance over 4 tasks when C = 2, highlighting its utility in cost-aware regimes. These results confirm that WARM-STAGGER reduces total annotation cost for moderate C.
Related Work
Imitation Learning with offline demonstrations, pioneered in autonomous driving [45], was solved by offline, state-wise supervised learning in early works [49 70 and named Behavior Cloning (BC). A recent analysis by [17] employs trajectory-wise Hellinger distance to tighten the dependence of BC the horizon at the trajectory level, although its sample complexity measured per state still grows quadratically with the horizon in the worst case. This shortcoming, often termed covariate shift compounding error [45). arises when the learned policy's imperfect imitation drives the learner to unseen states, resulting in a cascading sequence of mistakes. From a data collection perspective, this be mitigated by noise-injection approaches such 30
26
By leveraging additional
environment interactions, generative-adven advvessrralaaa IL methods two-player game, and aims to find policy that matches expert's state-action visitation distributions. This setting is also known as "apprenticeship learning using inverse reinforcement learning" in earlier works [ [69]. Quantitative comparisons with these methods are beyond our scope, as they rely on extensive interactions with the MDP and access to a class of discriminator functions, while we focus on understanding the utility of state-wise interactive annotations. This line of works also include recent work of (48), who introduce "Hybrid Inverse Reinforcement Learning", which leverages hybrid reinforcement learning [61] to accelerate inner loop of policy search; different from theirs, our "hybrid" setting focus on utilizing heterogeneous data modalities. Recent offline imitation learning approaches [T, 75 do not require MDP access but still require access to offline datasets possibly collected by non-expert policies, either with broad expert coverage or a large transition buffer. Our work assumes that interacting with the environment does not incur costs; we leave a detailed analysis that takes into account environment interaction cost as future work.
19
66
25
64
frame learning as a

---

Imitation Learning with interactive demonstrations, first proposed by 49) allows the expert to provide corrective feedback to the learner's action retroactively. Assuming low costs of expert recovery from mistakes (j-recoverability; recall Section 2. DAgger [5I], and following works [28 outperform traditional BC both theoretically and empirically. However, this efficiency demands substantial annotation effort [37. Although DAgger [51] and some subsequent
50 67
46
popularized the practice of annotating full trajectories, there has also been growing interest in state-wise annotations [40] 33 54 34), which appeared early as [49 22]. In fact, practical applications of DAgger often adopt partial trajectory annotation in expert-in-the- 731, where issues such inconsistencies caused by retroactive relabeling [29] can be mitigated. These methods often leverage human- or machine- gated expert interventions to ensure safety during data collection 78 38), provide more targeted feedback [39 13,, and enable learning on the fly [59]. The use of selective state-wiss tete-wise queries aligns with our goal of promoting interactive imitation learning with efficient supervision and provable sample efficiency. We regard our contribution as providing a starting point for understanding this increasingly popular paradigm of partial trajectory annotations.
works [67
46
68 17
loop 37 62 36 designs, seen in 77 27
20
Utilizing Offline Data for Interactive Learning. Many practical deployments of interactive learning systems do not start from tabula rasa; instead, prior knowledge of various forms is oftentimes available. For example, combining offline data and interactive feedback has recently gained much popularity in applications such training large language models to follow human instructions [16 44], and bandit machine translation [41]. Many recent theoretical works in reinforcement learning try to quamtify the computational and statistical benefit of combining offline and online feedback: for example, B2 show provable reduction of sample complexity using hybrid reinforcement learning, using novel notions of partial coverage; [6]] shows that under some structural assumptions the MDP, hybrid RL can bypass computational barriers in online RL (24]. Many works also quantify the benefit of utilizing additional offline data sources in the contextual bandit domain; for example, 442 58 76)
study warm-starting contextual bandit learning using offline bandit logged data or supervised learning examples. While some variants of DAgger (78] 20 also operate in a hybrid setting, our work focuses on fundamental formulation that explicitly accounts for the cost asymmetry between offline and interactive annotations [56).
Conclusion
We revisit imitation learning from the perspective of state-wise annotations. We show via the STAGGER algorithm that, interaction with the demonstrating expert, with its cost properly measured, can enable provable cost efficiency gains over Behavior Cloning. We also propose WARM-STAGGER that combines the benefits of offline data and interactive feedback. Our theoretical analysis shows that such a hybrid method can strictly outperform both pure offline and pure interactive baselines under realistic cost models. Empirical results our synthetic MDP support our theoretical findings, while MuJoCo experiments demonstrate the practical viability and competitive performance of our methods on continuous control tasks. In Appendix E we also show that a trajectory- annotation variant of DAgger can match the sample complexity of log-loss Behavior Cloning without recoverability assumptions, with additional experiments (Appendix G.3).
Limitations: Our design of imitation learning algorithm only aims at closing the gap between the performance of the expert and the trained policy; thus, the performance of our learned policy is bottlenecked by the expert's performance. In this respect, designing imitation learners that output policies surpassing expert performance is an important direction.
Our theory provide sample complexity guarantees for the discrete- action setting with deterministic and realizable expert. When such assumptions are relaxed, additional challenges arise [60]. In this respect, there remains a gap between our theoretical analysis and our MuJoCo experiment results. In future work, we are interested in conducting additional experiments on discrete-action control problems (e.g., Atari) as well as language model distillation tasks.
Acknowledgments: We thank the anonymous NeurIPS reviewers for their helpful feedback, which significantly improved the presentation of the paper. We thank Kianté Brantley for helpful discussions on state-wise annotations. We thank National Science Foundation IIS-2440266 (CAREER) for research support.
10

---

References
[1] Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-firas international conference on Machine learning. page 2004.
[2] Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seatile, Seattle, WA, USA, Tech. Rep, 32:96, 2019.
[3] Philip Amortila, Nan Jiang, Dhruv Madeka, and Dean P Foster. A few expert queries suffices for sample-efficient rl with resets and linear value approximation. Advances in Neural Information Processing Systems, 35:29637-29664 2022.
[4] Claudine Badue, Rânik Guidolini. Raphael Vivacqua Cameiro, Pedro Azevedo, Vinicius B Cardoso, Avelino Forechi, Luan Jesus, Rodrigo Berriel, Thiago M Paixao, Filipe Mutz, et al. Self-driving cars: A survey. Expert systems with applications, 165:1 13816, 2021.
[5] Mayank Bansal, Alex Krizhevsky, and Abhijit Ogale. Chauffeurnet: Learning drive by imitating the best and synthesizing the worst. arXiv preprint arXiv:/812.0300 2018.
[6] Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp. Prasoon Goyal, Lawrence D Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, et al. End to end learning for self-driving cars. arXiv preprint arXiv:1604.077 2016.
[7] Kiante Brantley, Wen Sun, and Mikael Henaff. Disagreementt-egulliiiee imitation learning. In International Conference Learning Representutions, 2019.
[8] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv:1606.00 1606.01540, 2016.
[9] Nicolo Basa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[10] Jonathan Chang, Masatoshi Uchara, Dhruv Sreenivas, Rahul Kidambi, and Wen Sun. Mitigating covariate shift in imitation learning via offline data with partial coverage. Advances in Neural Information Processing Systems, 34:965-9777 2021.
[11] Ching-An Cheng and Byron Boots. Convergence of value aggregation for imitation learning. In International Conference on Artificial Intelligence and Statistics, pages 1801-1809, PMLR, 2018.
[12] Ching-An Cheng, Xinyan Yan, Nathan Ratliff, and Byron Boots. Predictor-correctorr policy optimization. In International Conference on Machine Learning, pages 1151-1161. PMLR, 2019.
[13] Yuchen Cui, David Isele, Scott Niekum, and Kikuo Fujimura. Uncertainty aware data aggrega- tion for deep imitation learning. In 2019 International Conference on Robotics and Automation (ICRA), pages 761-767. IEEE, 2019.
[14] Hal Daumé, John Langford, and Daniel Marcu. Search-based structured prediction. Machine learning, 75(3):297-325, 2009.
2009.
[15] Thomas DiCiccio and Bradley Efron. Bootstrap confidence intervals. Statistical science, ((3))189-228) 1996.
[16] Hanze Dong, Wei Xiong, Bo Pang. Haoxiang Wang, Han Zhao, Yingbo Zhou, Nan Jiang, Doyen Sahoo, Caiming Xiong, and Tong Zhang. Rlhf workflow: From reward modeling to online rlhf. Transactions on Machine Learning Research.
[17] Dylan J Foster, Adam Block, and Dipendra Misra. behavior cloning all you need? under- standing horizon in imitation learning. arXiv preprint 100iv 2024.
[18] Dylan Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13488
11

---

[19] Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. Advances in neural information processing systems, 29, 2016.
[20] Ryan Hoque, Ashwin Balakrishna, Ellen Novoseller, Albert Wilcox, Daniel S Brown, and Ken Goldberg. Thriftydagger: Budget-aware novelty and risk gating for interactive imitation learning. arXiv preprint arXiv:2109.08855 08273, 2021.
[21] Pooria Joulani, Andras Gyorgy, and Csaba Szepesvári. Online learning under delayed feedback. In International conference on machine learning, pages 1453-1461. PMLR, 2013.
[22] Kshitij Judah, Alan Fern, Thomas Dietterich, and Prasad Tadepalli. Active imitation learning: Formal and practical reductions to iid learning. Journal of Machine Learning Research, 15(120):4105-444 2014.
[23] Sham M. Kakade and John Langford. Approximately optimal approximate reinforcement learning. In ICML, 2002.
[24] Daniel Kane, Sihan Liu, Shachar Lovett, and Gaurav Mahajan. Computationall gap in reinforcement learning. In Conference on Learning Theory, pages 1302-1302. PMLR, 2022.
[25] Liyiming Ke, Sanjiban Choudhury, Matt Barnes, Wen Sun, Gilwoo Lee, and Siddhartha Srini- vasa. Imitation learning f-divergence minimization. In International Workshop on the Algorithmic Foundations of Robotics, pages 313-329, Springer, 2020.
[26] Liyiming Ke, Jingqiang Wang. Tapomayukh Bhattacharjee, Byron Boots, and Siddhartha Srinivasa. Grasping with chopsticks: Combating covariate shift in model-free imitation learning for fine manipulation. In 2021 IEEE international conference on robotics and automation (ICRA), pages 6185-6191. IEEE, 2021
[27] Michael Kelly, Chelsea Sidrane, Katherine Dregs-Campbell, and Mykel J Kochenderfer. Hg- dagger: Interactive imitation learning with human experts. In 2019 International Conference Robotics and Automation (ICRA), pages 8077-8083. IEEE, 2019.
[28] Beomjoon Kim, Amir-massoud Farahmand, Joelle Pineau, and Doina Precup. Learning from limited demonstrations. Advances in Neural Information Processing Systems, 26, 2013.
[29] Michael Laskey, Caleb Chuck, Jonathan Lee, Jeffrey Mahler, Sanjay Krishnan, Kevin Jamieson, Anca Dragan, and Ken Goldberg. Comparing human-centric and robot-centric sampling for robot deep learning from demonstrations. In 2017 IEEE International Conference on Robotics and Automation (ICRA), pages 358-365. IEEE, 2017.
[30] Michael Laskey, Jonathan Lee, Roy Fox, Anca Dragan, and Ken Goldberg. Dart: Noise injection for robust imitation learning. In Conference on robot learning, pages 143-156. PMLR, 2017.
[31] Hoang Le, Nan Jiang, Alekh Agarwal, Miroslav Dudík, Yisong Yue, and Hal Daumé III. Hierarchical imitation and reinforcement learning. In International conference on machine learning, pages 2917-2926. PMLR, 2018.
[32] Gen Li, Wenhao Zhan, Jason D Lee, Yuejie Chi, and Yuxin Chen. Rewart-agnostic fine-tuning Provable statistical benefits of hybrid reinforcement learning. Advances in Neural Information Processing Systems, 36:55582-5561 2023.
[33] Yichen Li and Chicheng Zhang. On efficient online imitation learning via classification. Advances in Neural Information Processing Systems, 35:32383-32399 2022.
[34] Yichen Li and Chicheng Zhang. Agnostic interactive imitation learning: New theory and practical algorithms, 2023.
[35] Alexander Lin, Jeremy Wohlwend, Howard Chen, and Tao Lei. Autoregressive knowledge distillation through imitation learning. arXiv preprint 2rXiv:2009.07253. 2020.
[36] Huihan Liu, Soroush Nasiriany, Lance Zhang, Zhiyao Bao, and Yuke Zhu. Robot learning on the job: Human-in-the-logg autonomy and learning during deployment. The International Journal of Robotics Research, page 027836442441233901, 2022.
12

---

[37] Ajay Mandlekar, Danfei Xu, Roberto Savarese. Human-in-the tho-loop imitation learning using remote teleoperation. arXiv preprint arXiv:20/2.06733 2020.
Yuke Zhu, Li Fei-Fei, and Silvio
[38] Kunal Menda, Katherine Driggs-Campbell, and Mykel J Kochenderfer. Dropoutdagger: A bayesian approach to safe imitation learning. arXiv preprint
2017.
[39] Kunal Menda, Katherine Driggs-Campbell, and Mykel J Kochenderfer. Ensembledagger: A bayesian approach to safe imitation learning. In 2019 TEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 5041-5048 IEEE, 2019.
[40] Khanh Nguyen and Hal Daumé III. Active imitation learning from multiple non -enermteiiii teachers: Formulation, challenges, and algorithms. arXiv preprint arXiv:2006.07777, 2020.
[41] Khanh Nguyen, Hal Daumé III, and Jordan Boyd-Graber. Reinforcement learning for bandit neural machine translation with simulated human feedback. In Proceedings of the 2017 Conference Empirical Methods in Natural Language Processing, pages 1464-14744 2017.
[42] Bastian Oetomo, R Malinga Perera, Renata Parovica-Gajie, and Benjamin IP Rubinstein. Cutting to the chase with warm-start contextual bandits. Knowledge and Information Systems, 65()):3533-355,, 2023.
[43] Takayuki Osa, Joni Pajarinen, Gerhard Neumann, J Andrew Bagnell, Pieter Abbeel, Jan Peters, al. An algorithmic perspective on imitation learning. Foundations and Trends@ in Robotics, (112))11179, 2018.
[44] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730-27744, 2022.
[45] Dean A Pomerleau. Alvinn: An autonomous land vehicle in neural network. Advances in neural information processing systems, 1, 1988.
[46] Nived Rajaraman, Yanjun Han, Lin Yang. Jingbo Liu, Jiantao Jiao, and Kannan Ramchandran. On the value of interaction and function approximation imitation learning. Advances in Neural Information Processing Systems, 34, 2021.
[47] Nived Rajaraman, Lin Yang, Jiantao Jiao, and Kannan Ramchandran. Toward the fundamental limits of imitation learning. Advances in Neural Information Processing Systems, 2020.
[48] Juntao Ren, Gokul Swamy, Steven Wu, Drew Bagnell, and Sanjiban Choudhury. Hybrid inverse reinforcement learning. In International Conference on Machine Learning, pages 42428 42448. PMLR, 2024.
[49] Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 661-668. JMLR Workshop and Conference Proceedings, 2010.
[50] Stephane Ross and J Andrew Bagnell. Reinforcement and imitation learning via interactive no-regret learning. arXiv preprint arXiv:1406.. 5979, 2014.
[51] Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction no-regret online learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 627-635, 2011.
[52] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897. PMLR, 2015.
[53] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
13

---

[54] Ayush Sekhari, Karthik Sridharan, Wen Sun, and Runzhe Wu. Selective sampling and imitation learning via online regression, 2023.
[55] Ayush Sekhari, Karthik Sridharan, Wen Sun, and Runzhe Wu. Selective sampling and imitation learning via online regression. Advances in Neural Information Processing Systems, 36, 2024.
[56] Burr Settles, Mark Craven, and Lewis Friedland. Active learning with real annotation costs. In Proceedings of the NIPS workshop on cost-sensitive learning, volume 1. Vancouver, CA:, 2008.
[57] Shai Shalev-Shwart et al. Online learning and online convex optimization. Foundations and trends in Machine Learning, 4(2):177-194, 2011.
[58] Nihal Sharma, Soumya Basu, Karthikeyan Shanmugam, and Sanjay Shakkottai. Warm starting bandits with side information from confounded data. arXiv preprint arXiv:2002.08805, 2020.
[59] Lucy Xiaoyang Shi, Zheyuan Hu, Tony Z Zhao, Archit Sharma, Karl Pertsch, Jianlan Luo, Sergey Levine, and Chelsea Finn. Yell at your robot: Improving on-the-fly from language 2024.
corrections. arXiv preprint ar
[60] Max Simchowitz, Daniel Pfrommer, and Ali Jadbabaie. The pitfalls of imitation learning when actions are continuous. arXiv preprint arXiv:2503.0972) 2025.
[61] Yuda Song, Yifei Zhou, Ayush Sekhari, Drew Bagnell, Akshay Krishnamurthy, and Wen Sun. Hybrid rl: Using both offline and online data can make efficient. The Eleventh International Conference on Learning Representations.
[62] Jonathan Spencer, Sanjiban Choudhury, Matthew Barnes, Matthew Schmittle, Mung Chiang, Peter Ramadge, and Sidd Srinivasa. Expert intervention Icarning: An online framework for robot learning from explicit and implicit human feedback. Autonomous Robots, pages 1-15, 2022.
[63] Jonathan Spencer, Sanjiban Choudhury, Matthew Barnes, Matthew Schmittle, Mung Chiang, Peter Ramadge, and Siddhartha Srinivasa. Learning from interventions: Human-robot interac- tion as both explicit and implicit feedback. In 16th robotics: science and systems, RSS 2020.
MIT Press Journals, 2020.
[64] Jonathan Spencer, Sanjiban Choudhury, Arun Venkatraman, Brian Ziehart, and J Andrew Bagnell. Feedback in imitation learning: The three regimes of covariate shift. arXiv preprint (.Xiv:2/02.00272 2021.
[65] Wen Sun, Andrew Bagnell, and Byron Boots. Truncated horizon policy search: Combining reinforcement learning& & imitation learning. arXiv preprint 1rXiv:1805.112400 2018.
[66] Wen Sun, Anirudh Vemula, Byron Boots, and Drew Bagnell. Provably efficient imitation learning from observation alone. In International conference on machine learning, pages 6036-6045. PMLR, 2019.
[67] Wen Sun, Arun Venkatraman, Geoffrey J Gordon, Byron Boots, and J Andrew Bagnell. Deeply aggrevated: Differentiable imitation learning for sequential prediction. In International Confer- ence on Machine Learning. pages 3309-3318 PMLR, 2017.
[68] Gokul Swamy, Nived Rajaraman, Matt Peng. Sanjiban Choudhury, 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, 2022.
[69] Umar Syed and Robert E Schapire. A game-theoretic approach to apprenticeship learning. Advances in neural information processing systems, 20, 2007.
[70] Umar Syed and Robert E Schapire A reduction from apprenticeship learning to classification. Advances in neural information processing systems, 23, 2010.
[71] Kevin Tan, Wei Fan, and Yuting Wei. Hybrid reinforcement learning breaks sample size barriers in linear mdps. In The eighth- Annual Conference on Neural Information Processing Systems.
14

---

[72] Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based based control. In 2012 JEEE/RS/ international conference on intelligent robots and systems, pages 5026-5033. IEFE, 2012.
[73] Mitchell Torok, Mohammad Deghat, and Yang Song. Greedy-daggers student rollout efficient imitation learning algorithm. IEEE Robotics and Automation Letters, 2025.
[74] Yuanyu Wan, Wei-Wei Tu, and Lijun Zhang. Online strongly convex optimization with unknown delays. Machine Learning, 1 111(3):771-83, 2022.
[75] Siliang Zeng, Chenliang Li, Alfredo Garcia, and Mingyi Hong. When demonstrations meet generative world models: A maximum likelihood framework for offline inverse reinforcement learning, Advances in Neural Information Processing Systems, 36:65531-65565, 2023.
[76] Chicheng Zhang, Alekh Agarwal, Hal Daumé Iii, John Langford, and Sahand Negahban. Warm-starting contextual bandits: Robustly combining supervised and bandit feedback. In International Conference on Machine Learning, pages 7335-7344. PMLR, 2019.
[77] Jiakai Zhang and Kyunghyun Cho. Query-efficient imitation learning for end-to-end autonomous driving. arXiv preprint arXiv:1605.064400 2016.
[78] Jiakai Zhang and Kyunghyun Cho. Query-efficient imitation learning for end-to-end simulated driving. In Proceedings of the AAAI conference on artificial intelligence, volume 31, 2017.
[79] Zhouqiao Zhao, Xishun Liao, Amr Abdelraouf, Kyungtae Han, Rohit Gupta, Matthew Barth, and Guoyuan Wu. Real-time learning of driving gap preference for personalized adaptive cruise control. In 2023 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pages 4675 4682. IEEE, 2023.
[80] Brian D Ziebart, Andrew Bagnell, and Anind Dey. Modeling interaction via the principle of maximum causal entropy, 2010.
15

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] [NA]
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] pprovided proper justification is given (e.g., "error bars are not reported because would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification to claborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification; The abstract and introduction clearly state the paper's contributions proposinn STAGGER and WARM FARM-STAGGEL STAGGER, establishing their sample efficiency, and validating them empirically. These claims align with the paper's content and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
16

---

The paper discusses limitations such as the assumption of realizable and deterministic expert, and that environment interaction cost modeled. These are noted in the theoretical setup and discussed as directions for future work.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiscless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Fach theorem explicitly states its assumptions, such as realizability and recov- erability. Full, self-contained proofs are provided in the appendix, including intermediate lemmas and detailed derivations, to the best our knowledge.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
17

---

The paper includes all necessary details to reproduce the main experimental results, including model architecture, training hyperparameters, evaluation protocols, and data collection methods. Additional implementation details and results are provided in Appendix G
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The paper includes a link the appendix a public GitHub repository containing the code and instructions necessary to reproduce the main experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https //nips http:///wwppoeeeeee/e//////aaaaa
for more details.
18

---

The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
reproducible, they
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
The paper specifies training and evaluation protocols, including model ar- chitecture, learning rate, batch size, optimizer, number of updates, and trajectory length. Additional details and implermentation-specifi settings are provided in Appendix
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
The paper reports error bars using bootstrap confidence bounds, computed over 10 independent runs, and clearly states the methodology the caption of each relevant figure.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
19

---

For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Details on compute resources used for experiments, including GPU type, memory configuration, and experiment running time, are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: httpprip////rrps...e/ https///cccppcccetcccccccceeeeee
Answer: [Yes]
Justification: The research adheres the NeurIPS Code Ethics. involves standard simulation environments and pretrained MLP expert policy annotations, without the use of sensitive data, human subjects, or deployments with societal implications.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
The paper presents foundational theoretical work in imitation learning, aimed at improving sample efficiency through state-wise annotation and hybrid learning algorithms. To the best of our knowledge, the work poses no direct negative societal impact. Its potential applications, such as in robotics or autonomous systems, are mentioned to motivate the study, but the contributions themselves are purely algorithmic and theoretical.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinfornation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
20

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
The paper does not release pretrained models, large-scale datasets, or tools with high risk of misuse. The work is theoretical and algorithmic in nature, focusing sample efficiency in imitation learning, and thus does not raise direct concerns requiring safeguards.
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All external assets used in this work, including MuJoCo environments and pretrained experts, are properly cited (e.g.. 72 52)). MuJoCo is used under its standard academic license, and the pretrained models are referenced with proper attribution. No proprietary data or code was used without credit.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperssi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's 's creators.
21

---

13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We introduce new simulation scripts and code for our proposed algorithms (STAGGER and
which are documented and included via GitHub link in the appendix. Instructions for running experiments and reproducing results are also provided.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve any crowdsourcing or research with human subjects. All experiments conducted simulated environments.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve human subjects or participant- based studies; all experiments are performed in simulation, so IRB approval is not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
22

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: Large language models (LLMs) were only used for grammar checking and editing. They were not involved in the development or evaluation of the core methodology. and did not influence the scientific contributions of the work.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should not be described.
23

---

A Additional Related Work
First-step mixing and each-step mixing policies. The emergence of first-step mixing policies originated from technical considerations. In may interactive IL methods (5,50) the returned policy was not uniform first-step mixture but rather the best policy selected through validation. However, performing such validation in an interactive setting often requires additional expert annotations. Subsequent works [46 33 34 [7 circumvented the need for validation by employing uniform first- step mixture of policies across learning rounds, thereby directly translating online regret guarantees into performance differences. Our TRAGGER algorithm (Algorithm 3 in Appendix ( also employs first-step mixing policy at each iteration, and has state-wise sample complexity on par with behavior cloning.
On the other hand, each-step mixing between the learned policy across rounds and the expert policy has been prevalent strategy in interactive IL approaches [14 49 [T 50]. For each-step mixture policies, [33] was the first to explicitly distinguish this approach from first-step mixing. In other
works 46 17.. each-step mixing can be interpreted as learning H separate mixture policies, one for
each step within an episode.
Alternative algorithm designs and practical implementations, Though this work follows [17 and focuses on log loss, we believe our (1//N) rate is not exclusive to log loss. Despite requiring an additional supervision oracle, [31] suggests that trajectory-wise annotation complexity similar to Theorem (and Theorem 31 can be achieved using Halving [57] and 0-1 loss.
From an algorithmic perspective, we explored trajectory-wise annotation with first-step mixing (Algorithm in Appendix E and state-wise annotation with each-step mixing (Algorithm [ For trajectory- wise annotation with each-step mixing, naively learning a parameter-sharing policy may encounter batch-summed log loss, introducing an (undesirable) additional H factor the sample complexity [21 74). Analyzing state-wise annotation with first-step mixing remains an open question.
For practical implementations, it is worth noting that even with oracle-efficient implementations (e.g. 33 34 ) interactive IL. may require multiple supervised learning oracle calls per iteration. In contrast, offline IL requires only single oracle call to obtain the returned policy, which provides a clear computational advantage. We also note that real-world experts can suboptimal: in some applications it may be preferable to combine imitation and reinforcement learning signals (c.g..
[50 65 3).
information-theoeeee lower bounds for interactive imitation learning. A line of works 47
46 [7] provides lower bounds for the sample complexity of imitation learning under the realizable setting and considers j-recoverability. [46] is the first to demonstrate a gap between the lower bounds of offline IL and interactive IL in trajectory-wise annotation, focusing on the tabular and non- parameter-sharing setting. [17 establishes a Ω ( sample-complexity lower bound for trajectory- wise annotation the parameter-sharing setting.
We observe that the proof of [17 Theorem 2.2] also implicitly implies a 9 H) sample complexity lower bound for the state-wise annotation setting. Their proof relies on an MDP consisting only of self-absorbing states, where annotating a full trajectory gives the same amount of information as
annotating single state. In that MDP (which is 1-recoverable), Algorithm I achieves Ō H log (B) state-wise sample complexity, which does not contradict this lower bound. Nonetheless, obtaining lower bounds for state-wise sample complexity for general MDPs, policy classes, and general recoverability constants remains an open question.
B Proof for STAGGER
We first present two useful distance measures for pair of policies.
Definition 9 (Trajectory- wise Lı -i-iivergence.. For a pair of Markovian policies a and n², define their trajectory-wise Li -ivieergeece
H
T(an + dii)
A(Tr x')= = EBTES war (-101) (e (-len)
24

---

X(T a') ( is the expected total number of actions taken by n' that deviates from actions in trajectories induced by x. Note that X(-Il-) asymmetric, while the same concept applied in offline and
interactive II 49 51 with different guarantees for A(T || BF) and A( E π (see Lemma 39).
Definition 10 (Siate-wise Hellinger distance). For a pair of policies a and n', define their state-wise Hellinger distance as Bo-d" ( s), s))].
State-wise Hellinger distance represents the expected Hellinger distance between the action distri- bution of π and ní on s ~ d One notable feature here that the distance is evaluated between T. 8) and (- s). unrelated to the original action taken by by when visiting By Lemma 33 state-wise Hellinger distance with the expert policy is a constant factor equivalent to trajectory- wise L1 -iverrgeee in the deterministic realizable expert setting.
In the following lemma, we show that the performance difference between the policy á returned by STAGGER (Algorithm and the expert policy T can be bounded by the online state-wise Hellinger estimation error:
OnEst
State == Σ
Eanaa [DA(T"( 18), (+]))))
n=1
where (- s) and x x () denote the action distributions produced by the policies T" and np state
We ready to prove the state-wise annotation complexity of Algorithm T
Lemma 11. For any MDP M, deterministic expert n², and sequence of policies {TT" In= then ft, the first-step uniform mixture of { ,...,,"""".....,.,,,........., N satisfies:
J(TB) J(+)= S pH OnEst
N
Proof. By Lemma 39 under the assumption of recoverability, the performance difference between î and the expert bounded by
- J(t) s 1( 7)
where we recall the notation that
H
1
A(x || P E
Σ
I(an + x (sn))
Σ
E [ (: sh) - -+ P sn)l2
2 h=1
The proof follows by upper-bounding to show that for any stationary policy
Σ A(TT [) by H OnEst To this end, it suffices
1 H1
H Egnad [D]
BB (-|s))]
2 2
Σ
E [ s) - I
hm1
sn)) T.. sn))), we con- clude the proof by applying Lemma 38 with p = T(. sn.) and g = π F. s4), which gives
Observe that Eenar [D (T(- |s) s), s))] = Σ E= [D (T(
(1( sx), n (- sn)) マ || (h)) न 5- sh) 1|
Theorem 12 (Theorem Restated). If STAGGER (Algorithm 7 is run with a state-wise expert annotation oracle Stare MDP M where (M, is p-recoverable, policy class B such that deterministic realizability (Assumption [ holds, and the online learning oracle & set as the exponential weight algorithm,, then it returns it such that, with probability least 1 - 8,
OnEst Nims < log(B) 2 log(1/5),
State
and furthermore, the returned àt satisfies
J(#) F S pHl log(B) + 2 log (og(1/))
Nit
25

---

Proof. Recall the each-step mixing in Definition 1 since Tu is each-step mixing policy, we have that vh [H]. S. (a(ss) EESB u( (a)s)
The loss function each round that passed through online learning oracle A, evaluated T. llg. en (Ru), is of the form
1
et ( log
log
Tu Fa(ai (qn.)18a))
E ((T))(a"">)))))
which 1-exp-concave with respect to u. Thus, implementing using the exponential weights algorithm (Proposition 41 achieves:
Nint
Nint
1og(1/n"(a"" 18)))
Σ
log(1 (1/11" (*))) log( B) loog B)-
Then, Lemma 42 standard online-to-batch conversion argument with x" (8", hh),,,)) y² a".", " === where 0 (s", a", ")",,, implies that with probability at least
B and Ht (o"
9.
1 - 6,
Nint
OnEst State Nark
Σ E Egu [Di((=((1 (-)=",(s),,,)) s"))] < log(B) + 2log(1/6).
n=1
The second part of the theorem follows by applying Lemma
11
C Proof for WARM-STAGGER
In this section, analyze the guarantees of WARM-STAGGER under the realizable and deterministic expert assumption. We show that intermediate policies, as well the final returned mixture policy, induces distributions over trajectories that enjoy small Hellinger distance to the expert's 's trajectory distribution, due to their agreement on the offline dataset. Our analysis builds on generalization guarantees of the maximum likelihood estimator (MLE).
C.1 Preliminaries: First-step mixing and causally conditioned probabilities
Our main analysis leverages the fact that the each-step mixing policies T"'s maintained by MARM-STAGGER can be viewed as first-step mixtures of policies in B (recall Definition 5 this subsection is dedicated to prove this result (Lemma 16). We first recall the definition of first-step mixing of policies, adapted to our notations:
Definition 13 (First-step mixing, e.g. (69). Given a distribution over a set of (possibly nonsta- tionary) policies 11, denote T. the first-step mixing policy induced by u. when rolling out Tu. first sample policy æ ~ u, and follow ग for the entire episode.
Importantly, when the policies in II are all Markovian, T. may longer be Markovian policy: for example, the random draw of action does not only depend on the Markovian state 82 but also the random policy drawn, which in may correlate with di
To simplify the notations in our development below, following [80]. we define causally conditional probabilities, when the agent uses Markovian policies or their first-step mixing:
Definition 14. Given an MDP M, the causally conditional probability of state sequence 81:1 given action sequence 01:H-1, is defined as:
#-1
[-M ll (1---1)= = p(s)) II
P(s sh, ak).
Am
Given (first-step mixture) of Markovian policy, its causally conditional probability of state sequence a1.H given action sequence $1.8 defined as:
Note that notation different from every-step mixing policy notation Tu.
26

---

For Markovian policy T1.H <(a1 |l $1:H) == II TA (T(an (sh).
For first-step mixing of Markovian policies Tu. Tu(: $1:H) ExEB u u(z))((: $1.8).
Note that π T--[ss1:) and {=(+)[s1:H) are valid probability distributions (e.g.. Ear. a (1.:H) $1:B)
1), however, the use 'Il' highlights its distinction from standard conditioning. For example, when executing Markovian policy the conditional probability of the actions given the states
Pa (a1.H $1:H) I[ (a(l)s)) II P(s++1 Sh ah), which is clearly different from its causally conditional counterpart.
We have the following (perhaps folklore) lemma for causally conditional probability (e.g. [0
Lemma 15. For any Markovian policy n,
(P (1.H) = (p (1:H-1) T((.. $1.H),
(4)
and for any first- step mixing of Markovian policies Tu.
I ($1:H: 01.H) = (s1. (1:H-1) Tu(ai: ll $1:H).
(5)
Proof.
Eq. follows by noting that both sides are equal
H-1
p(s)) II
P(sN41
Sh
an)
II
Ta (an sn).
Am1
hm
Eq. (5) follows by noting that both sides are equal to
H-1 P(s h=1
H un va(an) sh)-
Σ ((())((s)) II
8h, an) II h=1
Lemma 16. If Fy is an each-step policy Ugg then there exists some first-step mixture of policies in B that equivalent Ras i.e., they induce the same distribution over all length- H trajectories.
Proof. Define y as a distribution over class B with p(v) = == u(va), for every Vi:H B. Consider the joint action distribution under Tu. which samples Th u independently for each step and executes ад ~ T.(- sn). The resulting causally conditional distribution over actions given state sequence $1:H is
[a( = II 1=1
Σ FA
u(TT) Ta(an ss)))
On the other hand, under the first-step mixture policy TH over B, full tuple v (VI,..., VH) is sampled once from μ. and actions are drawn an un sn). The resulting action distribution is
T (a.aa.H|ss.l
Σ En(v) DEB
II hml
(an sw).
Expanding the yields
A Am!
H II Am
Σ
sh)
Σ u(va) (n sh),
(2) (Pi.... EBN
by the distributive property and independence of the product.
Therefore, F.. (: (8:11) = ( (11:1)) and both policies induce the same trajectory distribu-
tion by Lemma 15
D
27

---

C.2 Proof of Theorem
Lemma 17. Let Buc == ( TISH E ::: : (T(3)) ane vh E [H], (s, a)1:H E +Dont be the set of policies in B that agree with the expert on the offline dataset of Nott iid expert trajectories. Assume the expert policy Th is deterministic and realizable. Then, with probability at least ô: for all π in Bbo
R Rlog( (B/5)
J(x - J(T) So
(6)
Not
Consequently, for all x computed WARM-STAGGER (Algorithm holds that:
Rlog(B/b)
- J(x") so
Noft
Proof. Eq. (6) is direct consequence of behavior cloning's guarantee applied to Markovian policy class B (17 Corollary 2.
Eq. 7 follows from Lemma 16 that Ipr is convex combination of P for r's in Bpc. as well as the fact that the expected return function J(x) is linear in the trajectory distribution IP*.
Theorem 18 (Theorem O restated). If Algorithm iis is run with deterministic expert policy BB an MDP M such that (M, Tt) is p-recoverable, a policy class such that deterministic realizability holds, and the online learning oracle A set the exponential weight algorithm, then it returns π such that, with probability at least 1 ô,
Rlog(B//8)
μH log log(Bbe//)
pHllg
J(T - J(+) 1(+)50 50 min
(8)
Noff
Non
Proof. We bound J(x=) J(t) ) by the two terms in the minimum expression on the right hand side of Eq. (8) respectively.
For the first term, we recall from Lemma 17 that with probability 1 6/2, for all policies ="'s.
J - ((T") < O
R (olo(B/)) Not
Since ( N En (TT", we have.
R Rlog(B/0)
J( J(+)
Noft
For the second term, note that by definition x F E Bbc. Thus, by applying Theorem that with probability at least 1 6/2, the returned satisfies
conclude
J( - ((T S (nH (uH log
(nH
Boc/d) log(Boe/D))
Nint
Together, we conclude proof by applying union bound.
D Proof for Theorem 8
We formally define the MDP M and the expert policy from Section 4.2 deterministic
where the expert policy nF
State Space S = E' B'UB', where:
E: ideal expert states, E No:
E': recoverable expert states, |E = N₁;
- B (b): absorbing failure state (unrecoverable);
'Our presentation of Theorem uses less general interpretation of that corollary, by restricting the policy class to be stationary.
28

---

B' = {b'}: recoverable reset state.
Action Space A: contains = |A] discrete actions. For each state a S, there a unique
action x (s) taken by the expert.
Episode length H.
Initial State Distribution p.
1
B for 8 E, p(s) (1+ B)N
((s) (1 + 8)No
for 8 E E..
Transition Dynamies:
E E:
* a = π (s): with probability 1 - 3, transitions to a uniformly random s' E E; with
probability 3, transitions to a uniformly random s' E';
+ (s): transitions b.
E':
* a F (s): transitions uniformly random s' E:
* x (s): transitions b'.
B (b): absorbing for all actions. Specifically, P(s' = bls b. 1.
E B' {b'}:
a π (b'): transitions to uniformly random s' E
* a + (b'): remains in b'.
Reward Function: For theoretical analysis, we consider the following reward function R₁:
{
if E EUE'
(1 a)
if b' and a = FF()s
otherwise
Specification of Parameters: In the following proofs, let max(50, & log(10No)).
10H, 3 N₁ max(500, 160
We also make the following assumption on the policies produced our learning algorithms (BC, STAGGER, and WARM-STAGGER) At any any stage of learning, denote the set of states that are annotated by the expert by Sannotated. Given the annotated (state, expert action) pairs, the learner calls some offline or online learning oracle A to obtain policy We require n behavior as follows:
T ( s), (G....,, 4))
8 Sanootated:
m( 1)
8 Sannotated
In other words, π follows the expert's action whenever such information is available; otherwise, takes an action uniformly at random.
Denote by di (s) IPT (sh, s) policy ITs state visitation distribution in M at step h. We next make a simple observation that by the construction M, the expert policy's state- visitation distribution in M is stationary over all steps:
Observation For MDP M, d, equals p. for all h E [H].
Proof. Recall the initial state distribution:
E, E E' otherwise.
No
p(s)
N1
0,
Under E, states b and are never reached. And the induced transition kernel on E U satisfies:
1-8
No E, s' E E, s se E, s' E', s E', s' E, otherwise.
P( Fs)) =
N
No
0,
29

---

For any fixed E E, using the kernel above,
1-3
8
Edd)P(o1d Similarly, for any fixed & E E'.
Σ
No + Σ
ps)).
No + 33
Ni(1 + B) No.
No + 33)
EEEB
S'E
B
B
E No(1+ +
N1 + B) = p(s).
N1
Thus, for any 8 EEUE',
p(s) = |s
Hence is stationary distribution for the Markov chain induced by rolloing out x in M. Since dy p and the dynamics ain-hhomggeneus, induction gives that vh [H] di p.
The following is the main theorem of this section; setting No = ((N)) (in which case both No and N1 are ((S) gives Theorem 8 our main paper.
Theorem 19 (Strengthening of Theorem 8). To achieve smaller than suboptimality compared to expert MDP M with probability 4:
Behavior Cloning (BC) using offline expert trajectories requires
Not ((NN)) with total annotation cost ()HN))
STAGGER that collects interactive state-wise annotations requires
Nint No) with total annotation cost (cCH
In contrast, WARM-STAGGER learns a policy that achieves expert performance with probability at least 1, using
No Noff - log( expert trajectories, and
Nin. 3 interactive annotations,
(9)
with total annotation cost Ô + C..
Proof. The proof is divided into three parts:
First, by Lemma 20 show that in M, Behavior Cloning requires ((HN) expert trajectories to achieve suboptimality H/2 with probability 3.
Next, in Lemma 24 show that STAGGER, which rolls out the learner policy and queries the expert
on only one state sampled uniformly from its learned policy's rollout, requires Nin. = 2(HN))
interactive annotations achieve suboptimality greater than H 22 with probability 2-
Finally, by Lemma 26 we demonstrate that O( No (N)) offline expert tarjectories and interactive annotations with probability 1.
achieves expert performance using
D.1 Lower Bound for Behavior Cloning
Throughout this subsection, denote by E' E'annotated the set of states in E' that are visited and annotated by the expert's 's Not offline trajectories. Lemma 20 (BC suboptimality lower bound). Consider the MDP M and the expert policy T. constructed as above. If Behavior Cloning uses
N1
Not
160
iid expert trajectories, then with probability at least 1, the suboptimality of its returned policy क is lower bounded by:
- 2
30

---

Proof. First, given policy म. we define a modified policy स that agrees with ğ everywhere except that it always take the expert's action on E. Note that if î ever takes wrong action at state in E, the trajectory deterministically falls into the absorbing bad state b, yielding even smaller return than f. Thus, ) 2 ). so suffices to prove the claimed lower bound for n, which we show for the remainder of this proof.
In the following, we show that an insufficient number of expert trajectories leads to small an ie., poor coverage on E". This, in turn, causes policy i to frequently fail to recover and get trapped in the absorbing bad state b', incurring a large suboptimality compared to the expert.
By Lemma 21
when Not is below the stated threshold, with probability 2'
E annotated
10
We henceforth condition on this happening. In this case, recall that our offine learning oracle is such that स takes actions uniformly random states E' E' aaanotttedd Suppose we roll out the policy सt in M; let r be the first step such that 8, E' (and T == H + + if no such step exists).
By Lemma 22
(r < H/5) 0.79, and Pr (8r & E annotaaedd | H/5) 2 0.9. M
M,
We henceforth condition on the event f S H/5, St Ennotaaedd } when rolling out म. Applying Lemma 23 we have, with probability at least 0.9, म takes a wrong action at s, and transitions to b and subsequently never takes the expert recovery action at b'. Therefore the trajectory remains in b' from step H/5 onward, yielding zero reward for at least 4Hl
5 steps.
Multiplying all factors, with probability greater than 1
2'
J(
(TT)
0.79 X
0.9
X
0.9
x
0.8H reward
2
unannotated s.
erross
which concludes the proof.
Lemma 21 (Bounded E' coverage). the number of expert trajectories satisfies:
Ni
Not I
160
then, with probability at least 1
N1
E aanotated
I
10
dr (s) (1 HN, for s E', where H-8- De- note X == E annotated to be the number of annotated states in E'. Consider Notf expert trajectories, each of length H, and let si,A be the state at step h of trajectory i. Fix any s E'. By a union bound over all steps and available offline expert trajectories,
Proof. Recall that by Observation
Nott (UU
Notr
Non H Σ
8NNof N₁
Pr(s E Fanotaaedd Pr
s))
Pr(sup =
(s)
(=1 1=1
Under the assumption Not S N261 this gives
Pr(s E E' annooaaed) S
20"
Let Z, be the indicator that state s appears in the expert trajectories, by linearity of expectation,
N1
Σ ETZ.
Pr(s E' annotated)
5
20
31

---

Applying Markov's inequality at threshold N1 /1/10,
N1
[[
N1 / 1 2
Pr
X
10
N1/
10
/1
Equivalently,
M
Pr
X <
10 2
Lemma 22 (First E' visit). For the MDP M, and any policy that agrees with a on E;
Pr M,
(3h E [H/5]. E E' 2 0.79
Proof.
Since π agrees with RB on E, (3h E [1/5), E') = Pr (3h E [M/5], E E M
M
suffices to consider the expert policy x B's visitation. By Observation distribution for nh satisfies that for all [H].
the state visitation
s' E E, s' E E, otherwise.
No(1+0)
N1
0,
The probability that no E' is visited in steps
1 1+ 3 (1 - -3)
(1 + B)( B)
1 3
8
1 f8
H
(10)
8 8
1 (H-8)2
64
<1.038 e 8 0.21,
where apply H-8- - " and H 2 50. Thus:
8
Pr (3h [H/5] St E E' > 1 0.2095 = 0.79 Mixh
Lemma 23 (Action Errors on Unannotated States). Consider MDP M with action space size A 2 10H.
Pr (vh E [ sh E (E' E E UB' Oh F π (Sh)) 2 0.9.
M,
Proof. Since for any state in (E") E UBB क selects the expert action with probability exactly 1, thus,
Pr (hh [M] 8h E (E' E annotated) U B' and az π (sn))
M,
Pr (sh (E' E
Eanotaatdd
UB' and an π (sn))
M,
H
H
<
Pr (an = x = 8h E (E'
E Eamootatra)
UU'
< < 0.1,
M
A
where we recall that > 10H in our construction. The lemma now follows by taking the complement of the probability above.
32

---

D.2 Lower Bound for STAGGER
Throughout the proof, denote by Eannotated the final set of states in E on which STAGGER have requested expert annotations.
Lemma 24 (STAGGER suboptimality lower bound). Consider the MDP from Section 4.2 with 8 H 2 50, A 2 10H, and ß n1-8- STAGGER collects no more than
HNO
Nint
12
interactive state-wise annotations, then, with probability least 2.2 the returned policy ft suffers suboptimality at least
H
J( - J(
Proof. By Lemma if STAGGER collects at most H.oo interactive state-wis wise annotations as above, 12
then with probability at least 5.4 Eannotsted] the number of distinct states in annotated is fewer than No/3. Consider a random rollout of ât and define the following events:
F1 == {s1 & Eaunotated
F2 = faı # (s1)).
We now lower bound their probabilities:
Pr(Fi) 2 3(1 + 3)
Pr(F2 Fi) 2 2 1
10H
Conditioned on the two events, the agent will get trapped at state b from step 2 on, and thus its conditional expected return satisfies
H
E&
Σ
Th
F1, F2
S 1.
Also, by the definition of the reward function R1,
[TT
H. Thus.
J( - ((a) - E+
H
Fh
h=1
2Pa F2) E&
H
Th
Fi, F2
h=1
2 H - 8 10H
H 2
(H
1
3 11
1011
where we use our setting H-B and apply H 2 50.
Lemma 25 (Bounded coverage under STAGGER). Suppose STAGGER collects at most
HNo
Nint
12
interactive annotations. Then,
E Emnnotated 2 No
1 2
Pr
Proof. In this proof, we say that state is annotated at iteration i, if it has been annotated by the expert before iteration i (excluding iteration i). Since each iteration of STAGGER samples one state uniformly from the current policy's rollout for annotation, denote the indicator of expert
33

---

annotating an unannotated state from E at iteration i as X; E {0, With this notation, we have the total number of annotated states by the end of iteration Nnt.
Nan
E aanottaeed
X
Let Fy be the sigma-algebra generated by all information seen by STAGGER up to iteration j. We now upper bound the expected value of X; conditioned on Fi-1 for each i.
Denote by Y, the number of unannotated states E visited by round i's rollout (by policy œ²). We claim that conditioned on Fi Y; is stochastically dominated by geometric distribution with parameter A-1, Indeed, whenever an unannotated state in E is encountered when rolling out n the A
probability that the agent takes wrong action is A if so, the agent gets absorbed to b immediately, and thus never sees any new unannotated states in this episode. In summary.
A
Y Fi-1] S E
Z Geometrri 1 |2| A
< 2.
A
Since the state sampled for expert annotation is uniformly at random from the trajectory, conditioned on Y, the probability that lands on a an unannotated state in most H Hence,
Y H
2
B|X, ---1= E E Yr, Fi
E
F - S
H
By linearity of expectation:
Nius
2 2
E annotated
E S
H
Applying Markov's inequality:
E[X]
6.
Pr Eannotatdd
2 No/3)
<
<
N
HNo
2
where the last inequality is by our assumption that Nin S
HNo 12
This completes the proof.
D.3
Upper Bound for WARM-STAGGER
Lemma 26 (Hybrid II. achieves expert performance under R1). Consider the MDP M and expert policy B as above, then, with probability least 1/2, WARM-STAGGER outputs policy that achieves expert performance using Noft =0 N log(No)) offline expert trajectories and Nin interactive annotations.
Proof. We divide the proof into four steps. Throughout, denote by Eannotated and E' anmotateed the subsets of E and E', respectively, that are annotated by the Noff offline expert demonstration trajectories.
First, we state a high probability event for the Not offline expert demonstration trajectories to provide annotations all states in E. Define event
F3 = (Eannotated = E}.
By Lemma 27 the choice
No
log (1.N.)
Noff (1 - H)
ensures that Pr(Fs) 2 0.9. On event F3, the learner takes the correct action on every state in E.
Next, we define the event under which only small fraction of E' is covered by the expert. With our setting of MDP parameters, the number of offline trajectories satisfies
No
4(H 8) 5(H - 16)
N
No of
log (1.No) < 5(1 33
No
No I No <
(1 - 3)H
160'
34

---

where in the first inequality we apply H 2 log(11)N)): in the second inequality, we apply H-16 <
H-8
when H 2 50; and we apply No
Ni. in the third inequality by the MDP setting. Thus, by I60
Lemma 21
Ni
E
E annotated
20
Applying Markov's inequality at threshold N. - gives
1
N1
N1
2N1
25
Pr
E Lanottated
>
2)
Pr
E
annotated
< 0.21.
4
500
121
Define event
N1
F4
E
Fannotated
Then Pr(Fa) 2 0.79.
Third, show that under events F3 and Fa, the interactive phase of WARM-STAGGNE gets b' annotated with probability greater than 0.4 in each of the first three rollouts, such that b' is annotated within three iterations with good probability.
First, we observe that by union bound,
Pr(Ps, P4) 2 Pr(F3) + Pr(F.) 0.69.
We henceforth condition on F3 F4 happening. By the definition of F3, the policies x" produced by acts optimally on all states in E.
Denote by E annotated the set of annotated states in after WARM-STAGGER'S iteration nı with annotated S E annotated + 1 for all n. Thus, by the
this notation, E
annotated = E auunotated- and [E
N1 definition of F4, for every n 0, 1, 2, unnotated S 4 2 + 2 = 4. In other words, at least 3 4 of
E
N1
the states in E' are unannotated for each of the first three iterations.
During the rollout of π", let be the first step such that 8, E E.. By Lemma 22 for every n E 3).
Pr (T
H/5) 2 0.79.
Since by the definition of M, 8, is drawn uniformly from E' conditioned on T S H/5,
Pr M,
(sy & E d.
annotated | S H/5) 2 0.75.
Therefore,
Pr (s, & E Mi
amnotated T T/H3) 2 0.79 0.75 2 0.59
(11)
With A 2 10H, by Lemma 23
Pr (vh E [M] Sh (E') E M
UU'
an + π =sn)) Z 0.9.
(12)
Thus, when the events in Egs. and 12 happen simultaneously (which happens with probability 2 0.59 + 0.9 1 2 0.49 by union bound), the trajectory rolled out by л" transitions b' step + 1 and stays there till the end of episode, accumulating no less than 0.8H b' states. Since WARM-STAGGER samples one state uniformly from each rollout for annotation, this gives 0.8
probability of b' being annotated with probability 2 0.49.
Denote by F., the sigma-algebra generated by observations up iteration of WARM-STAGGER. Our reasoning above implies that for all history F,-1 such that F3 n F4 happens, for all n E (1,2,3),
Pr(b' is annotated iteration n FF.1)) 0.49 0.8 0.39.
Define event
F6 == {b' is annotated within 3 iterations).
Hence
Pr(F: Ps, F)) 1- -1-0.39) 1 0.61 0.77.
35

---

Combining the three events, we have
Pr(Fs O F4 Fs) 2 Pr(Fs(F)) Pr(Fs| Ft) 2 0.69 x 0.77 > 0.5.
Finally, on F3 n P4 n Fs, states in and the reset state b' are annotated, under reward function R1, the learner receives reward 1 at any step if it is in E E' or it is in b' and takes the recovery action same as the expert. Since learned policy now behaves identical to xF on all states E and can successfully recover in B', its total return is the same as the expert, which concludes the proof. N
Lemma 27 (Coverage of states in E with Noft trajectories). Consider the MDP M. For Noff trajectories of length H rolled out by expert policy nh, all No states in E are annotated with probability 2 1 8 if:
No
No 8
Noff
log
(1 3)H
Proof. Recall that we denote by Eunnotated the set states in E visited and annotated by offline expert demonstrations. Fix any E E and concatenate all expert trajectories into single sequence {st)== of length 7 = Not. ordered from the first state of the first trajectory to the last state of the last trajectory. Let F, be the sigma-algebra generated by all states .1,...3 8t, and define the of initial indices
lo : [1, H 1, 2H
(Not 1)H1 +13.
For any t 1 E To 8141 is drawn from p, so
1 (1+ N)
Pr(s = Fi) p(s)
For + $ Lo. we have 8t E E BUE' and under =:
1 - 3
No 8t E
Pr(sc1=8| = =3(3))
No E'.
Therefore, in all cases,
1-
1 1 3
Pr(st-1 F() 2 No
Pr(s+11 F s 1
No
Let A == {8l * .,....81 $). Then
Pr(A(t1) < <(1- (1-
1-3 1--1-3 Pr(Ac),
No
Thus,
B (1-1-0)² S exp
(app--1--10 [1-
(1 3)H
Pr (s Eannotated) Pr(Ar)=
exp
No
No
No
By a union bound over all E,
(1
3)H
Pr(3s E E, & Eannotasod)
< No exp
No
which is most 8 whenever
No
No
NoR
log
3)
8
E Additional Guarantees for a Trajectory-wise DAgger Variant without Recoverability Assumption
In this section, we revisit and conduct refined analysis of another variant of DAgger with trajectory- wise annotations. We show that without the recoverability assumption, an interactive II. algorithm has sample complexity no worse than that of behavior cloning. This result complements [17 that analyzes a different version of wraeectory-wise DAgger, which they proved to have a worse sample complexity guarantee than behavior cloning.
36

---

E.1 Additional Notations and Useful Distance Measures
Recall that we have defined first-step mixing of policies in Section C.I We instantiate it to define mixture of policies in B, which induces a useful policy class below:
Definition 28 (First-step mixing of B). Define 1lg {Ta : E ( where policy nu is executed in an an episode of an MDP M by: draw π ~ u at the beginning of the episode, and execute policy throughout the episode.
In the following, we present another two useful distance measures for a pair of policies. Definition 29 (Trajectory- semi-mmeetiii define their trajectory-wise -em--mmmimttric as
17 For pair of Markovian policies and x',
p( n T = E Ba -a ((llaa))
[T (3h ab + t Hl
p(T x') I is the probability of any action taken by n deviating from actions in trajectories induced by o,, which symmetric [17]. A bound on p(T
x B) leads to straightforward performance difference
guarantee: J(T (T) < R. p π (Lemmaa 40).
Recall that we have defined causually conditional probabilities in Section C.1 introduce the following definition:
Built upon it, we
Definition 30 (Decoupled Hellinger distance). For a pair of Markovian policies π and n', define their decoupled Hellinger distance E [ x' (=[ss1:H)]]
Similarly, E" D (-1))11.); x (((111)1:1))) denotes the expected Hellinger distance between the causal distribution of actions T(: ((:1)).H) and n' r'(1))s1.H) on state sequence s visited by This allows decoupled analysis for state and action sequences, which useful for our analysis below.
E.2 Interactive IL Matches Offline IL on Trajectory-wise Annotation Sample Complexity
We present TRAGGER (AlgorithmB) B). another variant of DAgger that operates in the trajectory- wise sampling model, and provide its sample complexity bounds.
Algorithm 3 TRAGGER: DAgger with trajectory-wise annotation oracle
1: Input: MDP M, deterministic expert E, stationary policy class B, online learning oracle A with decision space llg.
2: for 1,...,N N do
3: Query & and receive x" E Ilg.
4: Roll n² and sample s"t following Ta
Query Trail for ai: x (s
5: Update A with loss function
('( = log
(13)
4. ( H
(T.HH)
6: end for
7: Output 4. the first-step uniform mixture of policies
{It
Algorithm uses first-step mixing policies T. Igg (recall Definition 28 nh" T.. obtained from online learning oracle A and samples full state sequence sT. Similar to Algorithm I Algorithm 3 also requires A to have decision space IIg (cf. II in Algorithm I It then requests expert's 's trajectory-wiss annotation ail and updates by 8" (ir) (Eq. (13). At the end of iteration N, the uniform first-step mixing of {
At round n, rolls out
1.W is returned, which is equivalent returning Tá. where u = N Σm= u². We provide the following performance guarantee of Algorithm
Theorem 31. If Algorithm B run with deterministic expert policy ET policy class B such that realizability holds, and the online learning oracle À. set as the exponential weight algorithm, then returns â such that, with probability at least 1 5,
J(T J(t) s 2R log(B) (B) 2 log(1/6) (1/6)
37

---

Theorem 31 shows that in the deterministic realizable setting, the interactive IL Algorithm has trajectory-wise sample complexity matching that of behavior cloning [T7] contrast, prior state-of- the-art analysis of interactive II. algorithms Appendix C.2] gives sample complexity results that are general worse than behavior cloning.
For the proof of Theorem 31 we introduce new notion called decoupled Hellinger estimation error:
OnEst Traj
E
[ (f (11ls..))))
Iraj decouples the dependence between the state sequence and the distribution of action sequence induced by the learner. Perhaps surprisingly, as we show below, is compatible with non-Markovian first-step mixing of policies, while still being well-behaved enough to be translated to a policy suboptimality guarantee, which could be of independent interest.
OnEst
E.3 Decoupling State and Action Sequences by Decoupled Hellinger Distance
In this section, we demonstrate that similar to D [PT, pa*
the decoupled Hellinger distance
E" [DH(T(-I[(1.))) x (-]ss_=))) also proportionally lower bounded by constant factor of p( B.. The following two lemmas show that such relationship holds for both Markovian policies and their first-step mixings.
Lemma 32. Let T be deterministic policy, and let be Markovian policy. Then have
1
p(
E"
[ (.
2
Lemma 33. Let F. be a deterministic policy, and let nu be a first-teep mixing of Markovian policies. Then we have
2 p(T, B) T.
The cornerstone of the above two lemmas is the following special case about first-step mixing of deterministic policies. Given MDP with finite state space size S and action space size A, denote the set of all deterministic, Markovian policies, as BDet BDet contains A deterministic policies, which can be indexed by tuple of actions
Lemma 34. Let F. be deterministic Markovian policy, and let be first- mixing of deterministic Markovian policies (i.e., elements of Dett) Then we have that
1
p n TTu
2
We now quickly conclude Lemmas 32 and 33 using Lemma back the proof of Lemma 34 the subsection after.
34 in the next subsection, then come
E.3.1 Proofs of Lemmas
32 and
33
We show the following simple claim: any Markovian policy л is equivalent to first-step mixing set of deterministic Markovian policies. This allows us to apply guarantees for mixtures of deterministic Markovian policies in Lemma 34 to conclude the proof.
Proof of Lemma 32
Claim 35. For a Markovian policy (M (TTI...., TH). there exists a first-step mixing of deterministic (.1181:11) policy Tu such that for any 81:11 E S 1. 1. = T=.-11 and 2. Tpx (p1.H) = pm= ($1:11)
improve over behavior cloning. we need μH maX log [B,] to be significantly smaller log [B] (where B, is the projection of onto step h). This may require the strong condition that < R/H < 1 in the more practical parameter-shane sharing settings (Bal) [B].
For I17 Appendix C.2J's sample complexity
38

---

Proof of Claim 35 To construct policy we will set the weight vector (over Det such that its weight on policy indexed by (ee,s)Ne(M).ss as;
u(v)
II II h= aES
(14)
can be easily verified that EvEBDa u(v) = 1.
We now verify the first item. By first-step mixing, rewrite Tu (u(01. $1.H
Ta(HH (8:11) Σ
u(v) II
(n(aalsn)
h=1
H
Σ
IIIII
Th 1 (s)
II I [a on]
(E))))E 1=1 sES
h=1
H
H
Σ
II
II
Th (1/
II
n ( (sp)
II h=1
[ahhe ap.
(oh (N) A=1 st8a
h=1
H II
Σ
II
Ta (ahh
II
(n(alss))
A=1 8788
h=1
H
= II mn(an(s)) = л (a1:1 $1.H). h=1
(15)
Since this holds for any action sequence 01:H E A" we derive the first part Claim 35 that (-11)11.H) Tu(-1|s1.11 The second item follows from the first item combined with Lemma 15
Proof of Lemma 33
By Claim 35| any Markovian policy can be viewed as a first-step mixing of
ASH deterministic policies from B Det thus, any first-step mixing of Markovian policies тa can also
be viewed as first-step mixing of A deterministic policies from BDet The proof again follows by applying Lemma
E.3.2 Proof of Lemma 34
To facilitate the proof of Lemma 34 we introduce the following additional notations:
Recall that Det is the set of all deterministic, Markovian policies. We will use v. to denote members BDet and (n(s)) (s) to denote the action takes at state at step h when is clear from the context.
Let 1 (s1:h) represent the subset of Det that agrees with nT on the state sequence 81ch-
Define F(u;v/;*B) = E. (" [V' (s which evaluates the probability
that 1/ disagrees with n. over the distribution of H-step state sequences induced by π.
Our key idea is to lower bound Ed [D] roles of the two appearances of n, using symmetric formulation via function F (as shown in (9 below).
(-1181:H1, x B (P
which reflects the asymmetric
Proof. Recall the first-step mixing policy in Definition
28
start by rewriting
39

---

P(Tu 1 =E [[ an # n (sn)]
= Σ
u(v) Σ
(H) (3h: an # (sn))
(16)
oe eDt
#1:11
Σ
p(v) ,))
vEBDet
which is a weighted combination of p(u || x²) for E Brtt
Next, we turn to analyzing (- (-1(s.1n)))) Since the deterministic expert induces delta mass distribution over actions, we apply the elementary fact about the Hellinger distance with delta mass distribution stated in Lemma 38 yielding:
1 2
Tu (-(1-11::1)) (-Ils.HH) l1
We recall that (s1.H) denotes the subset of Det that agrees with T on $1:H and define the total weight assigned by u on u(BB (s1.H)) = EveBm(eun)) u(v). Then,
2 nu (-1111.H) x (-11s1:1) ||1= 1 u(B ($1:H)),
which implies:
1- I-u(B"(s1.t)) (s).))) - (1111)))) -
(17)
Therefore, by taking expectation over 81:1 ~ Tp in Eq. (17)
Σ PTT (SLH) uu (s 1
((Ilo)))))
(18)
We now examine the expression
Σ (sin))) (BBB(((BB)))) $1.8
Since Tu a first-step mixing of policies in BDet with weight u. we have IPT (S1.H)
Evegon (..H.) This allows us to rewrite (+) using the definition of F(v; v', R as:
= Σ Σ
u(v)F" (51:H)
Σ u(v')I(P/ & (s1.))
#1WH DEB
W'EBDe
Σ
u(v)u(v))
1 (SI.)) (s.H))
DD Der
(19)
Σ
1
u(v)ulv)) (F(1;V/;TB) F(vr1/;BB)
2
where the first three equalities are by algebra and the definition of F(v; B). In the last equality, use the observation that
Σ
Σ (())u(/))F(/::u.z)))
M.V'EDD
By Lemma 36
stated below).
1
Σ u(v)u((') (p(v) BB plu || a))
2 2
Σ
u(v)p(v || xB) p( |l x.).
1
-2
MEBBet
40

---

Combining the above two inequalities with Eq (18) we conclude the proof by
~ π S T (-I1s())))):11)) (-1ls..)))]-
Lemma 36 (Symmetric Evaluation Lemma). Given deterministic Markovian policies v, v', and R the following holds:
(plv x1) pl x s F(V::
(20)
Proof. Recall that
(1u;//==)) + F(U:2;= = Σ( (F & (s + pp ($1:8) [I B (s.H)))
$1.22
Throughout the proof, we say that makes mistake at step h, if vn (sn) # (sA). Then, we can partition all state sequences $1:H E S into 4 subsets, N; indexed by i E (1,2.3.4)
1. X1 {$1:H v,v E (si:H)))
2. X2 {51.H 3h, s.t.v/ B (sLA), & (s1n)), v/ BB((sn-1));:
3. X3 (81:1 8.L.v... B (s1ah)) (81a)) E BB (F(
4. X4 = ($1:H Eh, s.t.v & (sLah,) (s E B (s1:hh v' (sthh-))))
In words, the four subsets divide state sequences into where: (1) both v agree with the x throughout, (2)&z(3) one of v, s/ makes its first mistake earlier than the other, and (4) v. v/ make their first mistake at the same time. It can now be easily seen that each $1.11 E S lies in exactly of such X, and
Xi U U U
To see this, consider ht the first time step h such that one of v and v' disagree with T If hr does exist, then $1:8 E X1. Otherwise, $1.H lies one of X2 Xx, Nn depending on whether and v/ makes mistakes at step AaT
By definition, subset X; denotes trajectories 8I:H where v. v/ (SL.H) meaning that
Σ (s"())))) [v/ & (s..)) + pa (SI.H) [M B (sLH)) 0. E1-
For the other 3 sets, i.e. X, for i (2,3,4) 4), we can further divide each set based on the time step where the first error occurs, formally:
x (SL. E B ( $ B (sin),) E (SLA-1))
X3 = (11. $ (F(S))), E (sun), B (sun-
(21)
x ( v B (s1.),,) & (B E (s1A-1)), E BB (81n-1))
By definition, each pair of subsets is disjoint and Uhew Xh X. for 2,3, 4. Note that determination of whether 81:H E X only depends on 815; therefore, 2nhh can be represented as X x SH - where
g = (81sh 81:H x.}.
Based on this observation, we have
Σ (*I.H)))=
Σ
P*(SI:)) = Σ P' (*r.))
$1.8 EX
SEG EA M BESSH-
SLAE&
Furthermore, since deterministic policies v,v, aB agrees with each other for all (S1n-11s1i E d....
41

---

h-1
Σ
('(sh:))= Σ p(s))
61:6 EI
BLAA
(22)
h
Σ p(s1)
II
Ph Sh. (hh
Σ
pe (s1n))
h==1
This implies that
Σ ((IHH)) EX
Σ p (sIH))
and therefore, summing over all E [M].
Σ (*(SH:)= = Σ p' (s1.H)
$1.2 EX;
81.2 EX;
Now, for X2, we have
Σ (S & (sL.H) + + ($I.H) & (B(HH)) $1 2
Σ I ((TH))
EX2
(23)
where we apply the fact that for all $1.8 E X2, v/ & (s1H)) and dropping the second term which nonnegative. Similarly, for As, have that
Σ (s.H)) (v/ & (s.H)) + Fp' ($1:H)I I & (s(H)))
Σ P ($I:H)=
Σ
Ip (s1:H))
SILA EX2
$1.8 Exa
$I. EX: (24)
Finally, for X4, we use the fact that for $1. E X4, v.v & (s and obtain
Σ (P"((I
[v' 1 (s1.)) + Pm (SI.H)I [ & (F(.)))))
(25)
Σ (IP" ($1:H) pd (s1:H))
Σ (s(.s.)).
$L.22 Ex4
Now, we combine Eqs.
23
25
and observe that
Σ (su.n)) +
Σ
Pa (s
Σ
(s..))
PP'
2
Σ
(P"(S1a9)) + pp/ (SL.)).
$1.27 2
R1:
$1.8 EXSURR
(26)
which implies
F(v; F(V::V; 2
Σ
(P" + IP" (s1.1)).
(27)
$1.4 K3U
42

---

Based on the definitions of X2, Az. As and p(- || -).
Σ
(F"(OL.))) p" (sLn))
Σ P (s..n)) (hh::h(s))) + (sh) or v/((s)) # (sh))
SLW AL ERGUAAUA
Σ
p (81:)) {3h: (on) + क (on) or (bn) + (
$1.
Σ
($1.)) (3h (sn) # (sn))
61.8
Σ
P (8 {3h: (on) + (
#1.81
=pl
क p(v |x)),
(28)
where $1.11 E 2S U X3 U X4 implies either // disagrees with x while the inequality relaxes the condition by splitting into separate contributions for and v'.
We conclude the proof by plugging 28 into 27
E,4 Proof of Theorem 31
We first demonstrate that the performance difference between expert and the the uniform first-step mixing of any Markovian policy sequence {x") n then show the trajectory- sessee wise sample complexity of Algorithm 3 in Theorem 31
is upper bounded by 2R OnEst Truj /N, and
Lemma 37. For any MDP M, deterministic expert n= and sequence of policies { each of which can be Markovian or a first-step mixing of Markovian policies, their first step uniform mixture policy it satisfies.
OnEst
Traj
- ( - 2R
N
Proof. By Lemma 33 for each n², which is a first-step mixing of Markovian policies:
1 p(TT" " || ,))
2
Then, by the definition of OnEst Traj
OnEst
Traj N
1
N
gx"
1 N
Σ
p(T" || xx = p( TT)
N
N
2N
2
where we apply the fact that á is a first-step uniform mixing of {Λr) 1 proof by applying Lemma 40
In=1- Finally, we conclude the
Proof of Theorem 31 The proof closely follows Proposition C.2 in [ which was tailored to another variant of DAgger. Different from that analysis, here we leverage the distribution of the state sequence $1.H instead of the per-step state distribution.
Observe that the log loss functions passed through online learning oracle A. (TT) is of the form
e" (T) = loog
n.* T
sT.H)
can be observed that (m,m))'s are 1-exp-concave in u E A(B). Therefore, setting A as the exponential weight algorithm (Proposition 41) ensures that the following bound holds almost surely:
N
N
1og(1/7" (a (T.)) <
log(1/n (a (8.)) + log(B) = log
==1
43

---

Now, Lemma
42
with x = $1 y" = a1HH = --II- and H = fo" fo" In'=1 where *.n H H. H ) implies that with probability at least - 6,
+.n
6"
(s7, ai
N
OnEst
Traj N
Σ
E
(+Is)))))))))))))) log(B) + loog(1/0)
n=1
The second part of the theorem follows by applying Lemma 37
Auxiliary Results
Lemma 38. Pf are two distributions over some discrete domain 2, and q is a delta mass on an
element Z. Then
2 -1 Di 51p- llı
Proof. Without loss of generality, assume that is a delta mass on zp. Therefore, |lp g/1 2(1 p(za),, and
(p.q)) = =(1 (1- 2 + (1 p 2(1 v p(20)).
Thus,
Dj (p. ②) | 41l
1
1
5 1].
1+ 2/(2))
Lemma 39 (Performance Difference Lemma + ((A), we have
123
49
For two Markovian policies and x.
H
( ((x) 1E
Σ
A (shy an)
where A,, (Sh, an) = Q (sh, an) - V (sa). Furthermore:
It holds that (recall Definition
[ - (( < H A( T).
Suppose B) is p-recoverable, then
((T) - ( R) S μ. A(T || TB)
Lemma 40 (Lemma D.2. of (77). For all (potentially stochastic) policies π and x', it holds that
J(m) J(T') R p(TT x').
Proposition 41 (Proposition 3.1 of (9). Suppose (e"()) is sequence of n-xxpcconcave func-
tions from (X)) to IR. For all x E X, define the weights w"-1(x) and probabilities w" (x) as follows:
wn
-- (2)= ales),
(²(x)
Exex w (x'))
where is the x-th standard basis vector in RRld Then, choosing u" (u" (x)) (exponential weights used with learning rate π1) satisfies:
N
log |X!
Σ
("(
min DEX
Σ (e)
"
Lemma 42 (Corollary of Lemma A.14 18 g+ such that for all [N]. yd x." H ~ g-(- xx)).
Under the realizbility assumption, where there exists
where H1 denotes all histories at the beginning of round n. Then, for any estimation algorithm N
that outputs {g In=1 online and any (0, 1), with probability at least 5,
1
Σ En D2 (0" 9. ()]
Σ
log
-log
+2 tog((0)11)
gr (yn xx))
g. (y" x²)
where E. = E[- H*).
44

---

G Experiment Details
We compare WARM-STAGGER with Behavior Cloning (BC) and STAGGER on continuous- tasks from OpenAI Gym MuJoCo [72 8 with episode length H 1000.
Infrastructure and Implementation. All experiments were conducted on a Linux work- station equipped with Intel Core i9 CPU (3.3GHz) and four NVIDIA GeForce RTX 2080 Tí GPUs. Our implementation builds on the publicly available DRIL repository 7 (httss//githu..com/// cttpattccooo/ccicctbiillll with modifications to support interactive learning- The continuous control environments used in our experiments are: "HalfCheetahhuulletEen v0". "AntBulletEnv-oO, "Walke2DBBulletnn--W0"
and "HopperBauleetEnvvoO""" include link to our implementation here: https: http:thhbbccmmlllyycceee19999999 Interactive- and -
We
Ceeratiiiin-Laainngee Srrovably-Beatiing otw.a//wnn..aaaoooooooooooaaaaaa Bww---eeaaoorooiiiiee
Environments and Expert Policies. We use four MuJoCo environments: Ant, Hopper, HalfCheetah, and Walker2D. The expert policy is a deterministic MLP pretrained via TRPO [2 53] with two hidden layers of size 64.
Model Architecture used by Learner. The learner uses the same MLP architecture as the expert. Following [17], we use a diagonal Gaussian policy:
ata s) - (fo(s), diag(o"))
where (o()) E Rdd the learned mean, and Rdd is a learnable log-standard deviation vector.
Each model is trained from random initialization using a batch size of 100, a learning rate of 10-3 and up 2000 passes over the dataset, with early stopping evaluated every 250 passes using 20% held-out validation set.
To evaluate the performance of BC against the number of states annotated, reveal expert state-action pairs sequentially along expert trajectories until the annotation budget is reached. For STAGGER, at each iteration, it rolls out the latest policy, samples state uniformly from the trajectory, queries it for the expert action, and updates immediately.
Learning Protocols.
For WARM-STAGGER, we begin with BC and switch to STAGGER after a predefined number of offline expert state-action pairs has been used, denoted as N. We set to be 100, 200, or 400 for easier tasks (e.g., Hopper, Ant) and 200, 400, 800 for harder tasks (e.g., HalfCheetah, Walker2D).
Cost Model and Evaluation. We assign a cost of to each offline state-action pair and a cost of C'= 1 or 2 to each interactive query. We run each method for 10 random seeds. For every 50 new state-action pairs collected, we evaluate the current policy by running 25 full-episode rollouts and reporting the average return.
Though the nonrealizable setting is beyond the scope of this work, expect that some variant of our algorithm can still give reasonable performance, provided that the policy class is expressive enough (so that the approximation error is nonzero but small). For example, (34) observed that with nonrealizable stochastic experts, DAgger variants outperform BC, and exhibit learning curves similar ours.
G.1 Additional Experiment Plots
We present extended experiment results with larger cost budgets. As shown in Figure 4 we allocate total annotation cost budget of 2000 for Hopper and Ant, and 4000 for HalfCheetah and Walker. This complements Figure in the main paper by showing the full training curves without zooming into the stage with small cost budget. The trends are consistent with our earlier observations: WARM-STAL -TRMGES achieves similar or better sample efficiency compared to STAGGER when C' = =1, and clearly outperforms both baselines under the cost-aware setting where C' 2.
G.2 Experiment with MSE Loss
We additionally evaluate our algorithms using mean squared error (MSE) as the loss function for optimization. All training settings remain identical to the main experiments with log loss, except that we use a learning rate of 2.5 x 10-1 As shown in Figure we observe qualitatively similar results to those under log loss shown in Figure consistent with prior observations [77, with perhaps more stable learning curves.
45

---

Hopper
Ant
Half Cheetah
Walker
2012
Expected Return
300
26
Numbee Expert Annotat
Number Expert Annotations
Number of Expert Annotations
Number Expert Annotations
Expected Return
2240
16
1330
1/
1350
150
180
308 150
303 1800
Expert Annctation Costs (C = 21
Expert Annotation Costs (C
Expert Annotation Costs (C
Expert Annotation Costs (C
(S5100) W55200)
W5(400)
(SS(100) W5(200) W5(400)
(W5200)
WS(400) W5(800)
W5(200) WS(400) WS(800)
Expert
Stagger
Behavior Cloning
Figure 4: Sample and cost efficiency on MuJoCo tasks. The top row shows expected return vs. number of annotations (C 1); the bottom row shows performance under cost-aware setting
(C 2). WARM-STAGGER (WS) is initialized with 1/20, 1/10, or 1/5 of the samples as offline demonstrations. It matches STAGGER in sample efficiency and outperforms the baselines when = 2, especially WS(1/5).
Hopper
Cheetah
Walker
350
Expected Return
8000
380
Numberr Expert Amotations
Number of Expert Annotations
Number Expert Annotations
Number Expert Annotations
Expected Return
300
300
120
200
200
40
600
180
Expert
Expert
Annotation
WS(50) WS[100) WS1200)
WS(50) WS(100) WS1200)
WS(125)
WS{250) WS(5500)
WS1125) W51250 WS(500)
Expert
Stagger
Behavior Cloning
Figure Performance comparison under MSE loss across MuJoCo tasks. Results show that WARM-STAGGER (WS) achieves comparable sample efficiency and performance to the log loss setting, with improved training stability. Each curve represents the average over 10 seeds.
G.3 Additional Experiments with TRAGGER
For completeness, we evaluate TRAGGER and its warm-start variant (WARM-TRAGGER, Algo- rithm 4. on continuous control tasks and the toy MDP as in Figure The key distinction between WARM- TRAGGER and WARM-STAGGEE lies in the annotation mode: the former employs trajectory- wise oracle feedback instead of state-wise annotation, leading to notably different behaviors, as shown in F
In particular, Ant and HalfCheetah, the state-wise cost efficiency (C = 1) of TRAGGER and WARM- WARM-TRAGGER TRAGGER is significantly worse than that of STAGGER due the cold-start problem: early
46

---

Algorithm 4 WARM-TRAGGER: Warm-start TRAGGER with offline demonstrations
1: Input: MDP M, trajectory-wise expert annotation oracle O' Stationary policy class B, online learning oracle A, offline expert dataset Don of size Non, interaction budget (in terms of number of states) Nit
2: Initialize A with policy class Bre { B: ((s) ab. wh [H).(ss, Dott)
3: for n = 1,..., Nint/ do
4: Query A and receive x²"
s.n 5: Execute x" and sample si. following pr Query Orai for dil x (s
6: Update with loss function
ETH (TT) = log
(29)
|
(8:11)
7: end for
8: Output: #, first-step uniform mixture of {nr ,..., N..
Hopper
Half Cheetah
Walker
Expected Return
Viee
110
vaar
1100
130
Number of Expert Annotations
Number Expert Annotations
Number Expert Annotations
Number of Expert Annotations
-TT1100) WT12001 - WTT400) WTT100) WT/200) WT1400
WTT200)
WT(400) WT1800)
WTT200 WT/400) WT10000
Stagger
Tragger
Behavior Cloning
Expert
Figure 6: Sample efficiency of algorithms on MuJoCo tasks, showing expected return vs. number of annotations (C' 1). WARM-TRAGGER (WT) is initialized with 1/20, 1/10, 1/5 of the total annotation budget as offline demonstrations. Specifically, WT(n) refers to WT with offline demonstrations of total length Although the performance of WT improves with demonstrations, both TRAGGER and WARM-TRAGGER remain inferior to STAGGER and, in many cases, even underperform Behavior Cloning, confirming the advantage of state-wise over trajectory- wise annotations.
offline
DAgger rollouts have poor state coverage but must still proceed until the end of each trajectory. In contrast, STAGGER samples only one state per trajectory, thereby better leveraging interaction to get timely feedback. For Hopper and Walker, however, TRAGGER and WARM-TRAL TRAGER achieve performance closer to STAGGER. These environments feature hard resets when the agent's state becomes unhealthy (unlikely in Ant and never HalfCheetah), which terminates (" ('truncate' has specific meaning of ending at prespecified step in openai gym) poor trajectories and consequently improve sample efficiency.
Overall, these observations suggest a natural middle ground between full-trajectory and single-state annotation manoatiio--namelyy batch queries (e.g., sampling 50 states per trajectory). as explored by 34 with comparable results.
head-to-head comparison between TRAGGER and STAGGER, as well between WARM- WARM-TRAGGER and WARM-STAGGER, is shown in Figure 7 highlighting the advantage of state-wise over trajectory- wise annotation.
However, this advantage does not hold in general: in the toy MDP in Figure 2 TRAGGER and WARM-TRAGGER achieve performance nearly identical to STAGGER and WARM-STAGGER, as shown in Figure
47

---

Hopper
Ant
Half Cheetah
Walker
Expected Return
1009
580
-300
3138 170 1HG 130
2010
38.
Stagger
Tragger
Stagger
Tragger
Stagger
Tragger
Stagger
Tragger
Expected
130
WS((100)
WT(100)
WS/100)
WT((100)
(V((200)
WTT200]
WS(200)
WT((20)
Expected Return
200
1000
1000
180
(S52000
WT[200]
WS52000)
WT(2200)
WS[400))
WT((400)
WS(400)
WT(400)
Experted
100 180
350
120 300
50
300
380
200 250
380
703
90. 1900
380
1800 300 400
W5(400)
-VT(400)
W5[400)
WT(400)
WS{800)
WT(800)
WS(800)
-WT/800)
Number Expert Annotations
Number Expert Annotations
Number Expert Annotations
Number Expert Annotations
Expert
Behavior Cloning
Figure 7: Head-to-head sample efficiency comparison between TRAGGER and STAGGER, and be- tween WARM-TRAGGR and WARM-STAGGER under equal (since we talking about comparison here) offline demonstration budgets. STAGGER and WARM-STAGGER consistently outperform TRAGGER and WARM-TRAGGER. The performance gap narrows the offline budget increases, effectively alleviating the cold-start problem suffered by TRAGGER.
48

---

wip. 8
Policy Performance
State Coverage
El State Coverage
Expected keturn
Coverage Rate
Coverage Rate
w.p.B.
0.6
0.9
04
0.-
de zB 1s 28h z2t Number Expert Annotations
Number of Expert Annotations
Number Expert Annotations
Expert Action
Wrong Actions
Expert
Tragger
WT (200)
WT (800)
WT (3200)
BC
Figure 8: Similar to Figure 2 we evaluate TRAGGER and WARM-TRAGGEI (WT) with 200, 800, 3200 offline (state, expert action) pairs in the toy MDP therein. All methods are evaluated under cqual total annotation cost with 1. With 800 offline (state, expert action) pairs, WT significantly improves the sample efficiency over the baselines and explores E' more effectively. The performance of TRAGGER and WARM-TRAGGER almost the same as STAGGER and WARM-STAGGR in Figure
49


Reviews:
[{"review_id": "1Xl3SbzE7n", "reviewer": "Reviewer_p7ue", "summary": "This paper investigates the benefits of state-based annotations for imitation learning. A new imitation algorithm with state-based annotation, STAGGER, is developed and settings with better cost-sample efficiency tradeoff than offline imitation (behavioral cloning) are analyzed. A hybrid method that initializes from offline imitation, called WARM-STAGGER, is also developed to outperform both purely offline and the base STAGGER algorithms. An MDP is constructed to demonstrate this. Experiments in MuJoCo also demonstrate the benefits of the approach.", "questions": "Q1. Are the theoretical bounds meaningful for the MuJoCo environment? In other words, can R and \\mu be provided/estimated for each environment (and the resulting ratios discussed)?\n\nQ2. How reliant do you anticipate the performance of your algorithms to be on the assumptions of the expert policy being realizable and deterministic?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "1. This paper makes an important contribution to imitation learning by establishing the theoretical benefits of interactive imitation learning.\n2. The paper is nicely organized and well written in motivating, defining, and supporting its main claims.  \n3. The description of related work makes the originality and significance of the paper's contributions clear.  \n4. Despite being heavily based in sample complexity theory, the developed algorithms are practical.\n5. The experiments effectively demonstrate the benefits of the developed approach.\n\nOverall, this is a solid paper with both theoretical and experimental contributions.", "was_revised": true, "final_justification": "This paper makes both theoretical and experimental contributions to the imitation learning literature, so I recommend acceptance.", "rebuttal": "We thank reviewer p7ue for the kind and supportive review. We are glad you found the work a solid contribution both theoretically and experimentally.\n\n\n**For Q1: On the Applicability of Theoretical Bounds to MuJoCo**\n\nWe agree that our theoretical analysis is limited to discrete MDPs and does not directly extend to continuous control. Our intention was to use MuJoCo experiments to illustrate practical viability \nof our state-wise annotation model and algorithms\nrather than to validate theoretical bounds. \n\nWe will revise related statements to: \n\"Empirical results on the synthetic MDP support our theoretical findings, \nwhile MuJoCo experiments demonstrate the practical viability and competitive performance of our state-wise annotation model and algorithms on continuous control tasks.\" \nto accurately reflect this distinction.\n\nThat said, we are currently conducting additional experiments on discrete-action environments (e.g., Atari) and language model distillation tasks, which more directly align with our theoretical framework. Results from these ongoing efforts will be included in the final or extended version of the paper.\n\nIn MuJoCo, \nthe exact values of $R$ and $\\mu$ may be hard to estimate due to the infinite size of the action space.\nThe value of $R$ can be estimated by the cumulative reward of the expert policy over multiple episodes, while $\\mu$ can be estimated by replacing a single expert action during a rollout and measuring the maximum performance degradation compared to the original expert. We will include these empirical estimates in the final version under the experimental details section.\n\n\n**For Q2: On Assumptions of Expert Being Realizable and Deterministic**\n\nTheoretically, realizable and deterministic expert assumptions enable our favorable $\\mathcal{O}(1/N)$-style policy suboptimality guarantees.\n\nUnder stochastic experts, \nwe haven't worked out the guarantees of interactive imitation learning yet; we expect that\nthe suboptimality guarantee includes a variance term that vanishes at a rate of $\\mathcal{O}(1/\\sqrt{N})$ due to the expert’s randomness (analogous to [1]).\n\nUnder nonrealizable experts, \nwe expect the suboptimality guarantee of output policy to have two parts: \n\n(1) approximation error measuring how well the policy class approximates the expert; \n\n(2) an optimization error term that typically degrades to $\\mathcal{O}(1/\\sqrt{N})$ in the agnostic setting (see [2]). Extending the theory to the nonrealizable and stochastic expert settings is an interesting direction for future work. \n\nEmpirically, we evaluate our algorithm with realizable stochastic expert. \nThough the nonrealizable setting is beyond the scope of this work, \nwe expect that some variant of our algorithm can still give reasonable performance, provided the policy class is expressive enough (so that the problem is not exactly realizable but still meaningful). \nFor example, [2] observed that with nonrealizable stochastic experts, DAgger variants outperform BC, and exhibit learning curves similar to our Figure 1.\n\n**Thank You!**\n\nWe appreciate the thoughtful questions and hope our clarifications address the concerns raised.\n\n[1] D. J. Foster, A. Block, and D. Misra. “Is behavior cloning all you need? Understanding horizon in imitation learning.” NeurIPS 2024.  \n\n[2] Y. Li and C. Zhang. “Agnostic Interactive Imitation Learning: New Theory and Practical Algorithms.” ICML 2024."}, {"review_id": "0ZP9R7t3kb", "reviewer": "Reviewer_rsrZ", "summary": "This paper explores theoretical underpinnings of when interactive imitation learning (i.e. variants of DAgger) can provably outperform vanilla behavior cloning (BC), and when a hybrid approach can provably beat both pure DAgger and BC, given the same budget of \"expert annotations\". To this end, the paper considers an amortized version of DAgger denoted STAgger, which instead of querying expert labels for each state along an on-policy rollout, simply draws a single sample from the on-policy averaged state visitation distribution. A guarantee for STAgger is established, showing that the performance upper bound can be smaller than that of BC as long as the expert is sufficiently recoverable and the relative cost of state-wise oracle queries is not too large. Given this result, a natural extension denoted Warm-STAgger is considered for hybrid settings, where an offline dataset is available in addition to online expert queries. Warm-STAgger sets the initial rollout policy is to an empirical risk minimizer over the offline dataset and performs STAgger on top. This algorithm is demonstrated to satisfy a bound no worse than either pure offline BC or pure online STAgger. Some lower bound constructions and numerical experiments are provided to demonstrate the benefits of online interaction.", "questions": "Please refer to Weaknesses above. My main questions can be summarized as:\n\nWhen can sparse corrections like in Warm-STAgger typically outperform both BC and a BC warm-started DAgger (as is typically done in practice)? In other words, in what regimes is Warm-STAgger actually expected to outperform both BC and (Warm-)DAgger, rather than \"falling back\" to the behavior of one or the other? When DAgger also gets a warm-start, when is expert annotation along the full-trajectory provably \"wasteful\" compared to state-wise annotation?\n\nClarifying these points will alleviate some of my hesitation about interpreting the results.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Overall, this paper introduces an interesting dimension to imitation learning. The paper is generally well-written. Thus, I am leaning toward acceptance. My main concerns with the paper are regarding the actual efficacy of the proposed algorithm, and the degree to which the theorems convincingly establish the uniform benefit of hybrid imitation learning.\n\n**Strengths**\n\nThe focus on reducing the number of online expert oracle queries is a perennially relevant one, and this paper achieves an interesting result that a reduced form of DAgger may actually perform on par or better to offline BC and DAgger, as indexed by the budget of expert queries. This has practical relevance when on-policy expert queries may be expensive compared to collecting expert policy rollouts.\n\n\n**Weaknesses**\n\nIn terms of theoretical soundness, Theorems 2 (BC), 3 (STAgger), 4 (Warm-STAgger) are technically comparing worst-case performance upper bounds. To be clear, the authors do not claim otherwise, but this technically renders claims of one method being generically better than another difficult to conclude. Theorem 6 partially closes the gap with instance constructions. However, it remains unclear when Warm-STAgger generically instance-wise dominates the performance of (ST,D)Agger or BC.\n\nIt is somewhat precarious to attribute the experimental results in continuous control as support for the theoretical bounds in this paper. In particular, it is known that imitation learning in control systems suffers unique problems that otherwise do not manifest in discrete-action settings [1, 2]. Notably, imitation learning in control systems can suffer from exponential-in-horizon compounding errors. This does not conflict with, e.g. the loglossBC bound, because such bounds assume policy estimation in losses such as indicator or log-loss, which are not feasible in continuous action spaces. I am not aware of analysis of DAgger in these settings, though I imagine for expert annotation along a exponentially unstable policy rollout likely yields exponentially low \"coverage\" around on-expert trajectories.\n\nMinor comments\n\n- Some inconsistent use of $\\ln$ versus $\\log$, e.g. line 108\n- Line 210: the equality should be an inequality\n- Should the loss used for fitting the BC policy $\\hat\\pi$ technically be the log-loss to instantiate Theorem 2? The set of empirical risk minimizers is the same for deterministic realizable experts, but it does matter with respect to which loss generalization is proven in order to yield the horizon-independent bound in Theorem 2.\n\n[1] Tu et al. \"On the Sample Complexity of Stability Constrained Imitation Learning\"\n\n[2] Simchowitz et al. \"The Pitfalls of Imitation Learning when Actions are Continuous\"", "was_revised": true, "final_justification": "I maintain my generally positive evaluation, and lean acceptance (4) on the paper. I still maintain concerns about: 1. general performance upper bounds instead of instance-wise guarantees, and 2. when sparse annotations can beat both BC and (Warm) DAgger rather than fall back to the better-performing bound of the two. These are probably non-trivial extensions of the work the authors have already presented, and therefore they do not significantly impact my positive evaluation.", "rebuttal": "We thank reviewer rsrZ for the thoughtful and constructive review. We appreciate your recognition of our theoretical contributions and your positive evaluation. Below we address specific concerns:\n\n\n**For W1: Worst-Case Bounds and Instance-Wise Comparisons**\n\nWe acknowledge the reviewer’s valid observation that Theorems 2–4 provide worst-case upper bounds, which do not imply generic instance-wise superiority. We are glad that Theorem 6 was seen as a meaningful step toward closing this gap, and we appreciate the reviewer’s recognition of our efforts to go beyond worst-case analysis.\n\n**For W2: Applicability of Continuous Control Experiments to Support Theoretical Bounds**\n\nIndeed, our theoretical guarantees apply only to discrete-action MDPs. The MuJoCo experiments are intended to empirically evaluate the practical effectiveness of the proposed algorithms, not to validate the theory. We will revise related statements to: \n\"Empirical results on the synthetic MDP support our theoretical findings, \nwhile MuJoCo experiments demonstrate the practical viability and competitive performance of our methods on continuous control tasks.\" \nto accurately reflect this distinction.\n\nWe agree that continuous imitation learning presents unique challenges such as exponential-in-horizon compounding errors, and that DAgger-style theoretical analysis in this setting remains largely open, which is an interesting direction. We will explicitly acknowledge this in the experiment section. \n\nOur analysis is based on log-loss, which reduces to the indicator loss under deterministic experts in discrete-action settings. While indicator losses are indeed incompatible with continuous action spaces, log-loss remains applicable. Our implementation employs log-loss for continuous control tasks (see Appendix G, Line 1454), consistent with the Walker2d-v4 experiment setting with logarithmic loss in Foster et al. (2024) [1]\n\n**For Minor Comments**\n\n1. Inconsistent use of ln vs. log. We will use log consistently in the final version. \n\n2. Line 210: equality vs. inequality. Though the equality is technically correct under $\\mathcal{O}(\\cdot)$, we will revise it to $\\leq$ for consistency in presentation.\n\n3. Loss used in Theorem 2. We will clarify that Theorem 2 establishes a new horizon-independent generalization bound under log-loss, distinct from standard 0-1 loss analyses in BC.\n\n**For Q: When Does Warm-Stagger Provably Outperform BC and Warm-DAgger?**\n\nWe appreciate the reviewer’s thoughtful question. To clarify, our work is motivated by the need to understand and formally analyze warm-start and non–full-trajectory annotation strategies in interactive imitation learning, despite their widespread use in practice (e.g., [3,4]).\n \n \nTo the best of our knowledge, we are the first to formally analyze hybrid imitation learning that combines warm-start with interactive annotation. Our analysis framework is also transferable and can be extended to analyze other DAgger-style algorithms initialized from offline data.\n\nWe are not exactly sure which version of the Warm-DAgger algorithm the reviewer is referring to; thus we present and discuss three possible interpretations below:\n\n(1) Naively changing Warm-Stagger (Algorithm 2) to query full trajectory-wise annotation at step 5.  \n\nThis variant warm-starts with offline data and, in each interaction round, executes an on-policy rollout and retroactively labels the entire trajectory. Let $M_{\\text{on}}$ be the number of such trajectories.\n\nFollowing similar analysis, the suboptimality is bounded by\n$\nJ(\\pi_E) - J(\\hat{\\pi}) \\leq \\mathcal{O}( \\min ( \\frac{R \\log B}{N_{\\text{off}}}, \\frac{\\mu H \\log B}{M_{\\text{on}}})),\n$\n\nwhich matches the Warm-Stagger bound but replaces $N_{\\text{on}}$ with $M_{\\text{on}}$, incurring an extra factor of $H$ when measuring the cost using the number of state-wise annotations. \n\n(2) Adding a warm-start procedure to the LogLossDAgger in [1] (see their Proposition 2.2 and Appendix C.2).  \n\nTheir guarantee under a deterministic expert is:\n\n$\nJ(\\pi^*) - J(\\hat{\\pi}) \\leq \\mu \\cdot \\sum_{h=1}^H \\frac{\\log(|\\Pi_h| H \\delta^{-1})}{n}.\n$\n\nTranslating into our notation, with a fixed policy class of size $B$ and $M_{\\text{on}}$ on-policy full-trajectory queries, this becomes:\n\n$\nJ(\\pi_E) - J(\\hat{\\pi}) \\leq \\mathcal{O}(\\frac{\\mu H \\log B}{M_{\\text{on}}} ).\n$\n\nFollowing similar analysis with a warm-start initialization, the suboptimality of warm-start LogLossDAgger is:\n\n$\nJ(\\pi_E) - J(\\hat{\\pi}) \\leq \\mathcal{O} ( \\min ( \\frac{R \\log B}{N_{\\text{off}}}, \\frac{\\mu H \\log B}{M_{\\text{on}}} )),\n$\n\nwhich also incurs an extra factor of $H$ in state-wise annotation cost.\n\n\n(3) Adding a warm-start procedure to our Algorithm 3, Tragger.  \n\nBy our Theorem 26 (which achieves a better guarantee than [1] and does not require recoverability), under a deterministic expert, Tragger satisfies:\n\n$\nJ(\\pi_E) - J(\\hat{\\pi}) \\leq \\mathcal{O} \\left( \\frac{R \\log B}{M_{\\text{on}}} \\right).\n$\n\nWith a warm-start initialization using $N_{\\text{off}}$ offline trajectories, the suboptimality becomes:\n\n$\nJ(\\pi_E) - J(\\hat{\\pi}) \\leq \\mathcal{O} (\\min (\\frac{R \\log B}{N_{\\text{off}}}, \\frac{R \\log B}{M_{\\text{on}}} )).\n$\n\nThis is, to our knowledge, the best known guarantee for warm-start DAgger under log-loss with offline initialization and trajectory-wise annotations. However, since $\\mu \\leq R$, this implies $\\mu H \\leq R H$, and therefore Warm-Stagger remains more sample-efficient under state-wise annotation.\n\nIn all, under our analysis, \ngiven a fixed target policy suboptimality\nWarm-Stagger achieves better state-wise annotation cost than all three warm-start DAgger variants we consider. Therefore, if the considered variants align with the reviewer’s intended formulation, our analysis shows that sparse corrections are provably more efficient.\n\nA final remark to intuitively understand when full-trajectory expert annotation becomes wasteful compared to sparse corrections: consider MDPs with self-absorbing states (as in the lower bounds of [1,5]). In such settings, annotating all $H$ identical states in a trajectory provides no more information than annotating a single state.\n\n**Thank You!**\n\nWe would be happy to include empirical comparisons of Warm-start DAgger variants (specifically, variants (1) and (3)) on MuJoCo benchmarks in the appendix, to further support our theoretical conclusions. If the above response addresses your concerns, we would sincerely appreciate a reconsideration of the score.\n\n[1] D. J. Foster, A. Block, and D. Misra. “Is behavior cloning all you need? Understanding horizon in imitation learning.” NeurIPS 2024.\n\n[3] M. Kelly, C. Sidrane, K. Driggs-Campbell, and M. J. Kochenderfer. “HG-DAgger: Interactive imitation learning with human experts.” ICRA 2019.\n\n[4] R. Hoque, A. Balakrishna, E. Novoseller, A. Wilcox, D. S. Brown, and K. Goldberg. “ThriftyDagger: Budget-aware novelty and risk gating for interactive imitation learning.” CoRL, 2022.\n\n[5] N. Rajaraman, Y. Han, L. Yang, J. Liu, J. Jiao, and K. Ramchandran. “On the value of interaction and function approximation in imitation learning.” NeurIPS 2021."}, {"review_id": "6eK9Tj3I7c", "reviewer": "Reviewer_yovM", "summary": "This paper proposes new interactive algorithms for imitation learning. Motivated by several recent theoretical findings surrounding behavior cloning, the authors look into whether low-cost interaction can benefit behavior cloning, including in the case of function approximation. Specifically, the authors focus on how to minimize the number of expert queries, such that expert performance is achieved or some theoretical gap can be proven to occur with high probability.\n\nSpecifically, the proposed algorithm, STAgger, executes a mixture policy at each step (effectively can query a different policy at each state it seems along the trajectory), obtaining a single sample and using it to update the set of likelihoods over a finite policy class, of which the expert is assumed to be in.\n\nExperiments across a few MuJoCo tasks show that STAgger outperforms behavior cloning in terms of sample efficiency.", "questions": "There are a few things I would like to clear up personally -- how many members of the policy class do you experiment with when you run these MuJoCo tasks? The task seems like you have a set of deterministic or Markovian policies, and you're effectively learning some sort of router/mixture of them that should in principle converge to a Dirac over the true expert. The appendix didn't give much in terms of the experimental paradigm, so I was wondering how many policies this allows for.\n\nTo scale this to resemble something close to what we may have in practice, how does this scale to a (finite) set, but which has a large number of policies? This is in effect something that is more realistic, where we would want to choose the expert from this set as quickly and with as little interaction with the oracle as possible. Maybe an ablation study can be done for that.", "limitations": "The authors do mention some limitations of their work, including expert realizability (strong assumption) and lack of modeling of the environment query cost. It is clear (from an IL practitioner's perspective) that one can only be as good as an expert on any IL task at optimum, so design choices around the expert and the data collection process before IL takes place should be carefully considered from a societal standpoint. Maybe these can be put together as an addition to the last section of the paper (e.g. a \"Limitations\" section).", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper is pretty theoretically sound -- the underlying theory is classical no-regret theory from the original DAgger paper for the most part, which is well-known. The experiments also show good results of the proposed method, which is pretty neat for imitation learning. As for the method, it is a pretty straightforward extension to DAgger in the case of having a finite set of policies -- you effectively want to reduce your space down through queries on the mixture distribution, and update the mixture to bias towards the (expert) labels given at each query.\n\nThere are no theoretical weaknesses in the paper (e.g. nothing is really wrong from the theory side), but from the perspective of significance, I'm not sure how much this has from a practical standpoint. There weren't many details given about the experimental setup (my big concern are posed in the Questions section), and it seems that with something like this (if the set of policies given to you is reasonably small), a simple baseline could just be to find the policy in the (known) class that does the best (e.g. some type of test-set logic here) on the expert dataset (although I may be misunderstanding this), in which no interactions are required. It seems that interactive IL is great for theory, but not great from a practical perspective, and I'm not sure how much theoretical contribution this brings for now.", "was_revised": true, "final_justification": "After the authors clarified some misconceptions I had about the paper, as well as reading what other reviewers had discussed, I will raise my score to 4.", "rebuttal": "We are glad that reviewer yovM found our work “theoretically sound” and appreciated that the “experiments also show good results.” Below we address specific concerns:\n\n**For W: Practical Significance and Baseline Design**\n\nWe appreciate the thoughtful question of the reviewer. Our work is motivated by the need to understand and formally analyze warm-start and non–full-trajectory annotation strategies in interactive imitation learning, despite their widespread use in practice (e.g., [3,4]). As noted by Reviewer 9Cf7, DAgger-style algorithms are fundamental to modern data pipelines for robotics (e.g., [6,7]).\n\nAs noted in Appendix G, we train a single parametric MLP using log-loss with empirical risk minimization (ERM), retraining the policy after each newly annotated state. Thus, in our experiments our method does not initialize a small set of predefined policies. We apologize for the confusion, and will clarify this more explicitly in the main experimental section.\n\nWe interpret the reviewer's suggestion of \"test set logic\" baseline as behavior cloning (BC), which we already benchmark. Please let us know if we misunderstood the suggestion.\n\n**For Q1 and Q2: Scalability of Policy Class and Experimental Setup**\n\nWe use a single parametric MLP policy in MuJoCo experiments, trained via log-loss with ERM. There is no predefined finite policy class or mixture of policies. In our synthetic MDP experiment, where the policy class scales combinatorially (e.g., $B = 100^{1200}$ in Figure 2), we simulate the effect of a randomized mixture by assigning random actions to previously unseen states.\n\n**For Limitation: Realizability Assumption, Environment Cost Modeling, and Expert Design**\n\nWe agree that we should be aware of the suboptimality of the expert in practical deployment of imitation learning; \nin some applications it may be preferable to combine imitation and reinforcement learning signals (e.g., [8]). \nWe will add this discussion in a \"limitation\" section the final version.\nModeling environment query cost is an interesting direction, which we intentionally omitted for clarity of presentation (see line 301), and aim to explore in future work.\n\n**Thank You!**\n\nIf the above clarifications address your concerns, we would greatly appreciate a reconsideration of the score.\n\n\n[3] M. Kelly, C. Sidrane, K. Driggs-Campbell, and M. J. Kochenderfer. “HG-DAgger: Interactive imitation learning with human experts.” ICRA 2019.\n\n[4] R. Hoque, A. Balakrishna, E. Novoseller, A. Wilcox, D. S. Brown, and K. Goldberg. “ThriftyDagger: Budget-aware novelty and risk gating for interactive imitation learning.” CoRL, 2022.\n\n[6] L. X. Shi et al. “Yell at your robot: Improving on-the-fly from language corrections.” RSS, 2024.\n\n[7] Y. Jiang, C. Wang, R. Zhang, J. Wu, and L. Fei-Fei. “TRANSIC: Sim-to-Real Policy Transfer by Learning from Online Correction.” CoRL, 2025.\n\n[8] S. Ross and J. A. Bagnell. “Reinforcement and imitation learning via interactive no-regret learning.” arXiv, 2014."}, {"review_id": "D0odStAXoM", "reviewer": "Reviewer_9Cf7", "summary": "The paper analyzes a DAGGER-style algorithm which has access to both expert data, as well as interaction with the environment with access to a state-labeling oracle. The paper demonstrates theoretically how having access to both sources of data can lead to algorithms with better sample complexity.", "questions": "- The experiments run are all in continuous state and time, while the loss and theory uses Hellinger distances and indicator functions. Considering that continuous imitation learning can be exponentially harder than its tabular MDP equivalent (\"The Pitfalls of Imitation Learning when Actions are Continuous,\" Simchowitz et al), would it make more sense to consider discrete/language style tasks instead of continuous control tasks?\n\n- The paper uses \"hybrid imitation learning\" to describe the problem setting, yet similar algorithms like \"vanilla\" DAGGER and DART are usually described as \"online\" or \"interactive\" imitation learning algorithms and have the same premises as the hybrid setting described in the paper--access to an expert oracle and further rollouts. It would be helpful for the authors to clarify what they view as \"offline\" vs \"hybrid\" vs \"online\" imitation learning. Perhaps \"interactive\" and \"non-interactive\" would be better terminology to avoid overloading with terminology from Reinforcement Learning?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n - The paper furthers our understanding of DAgger-style algorithms which are fundamental to modern data pipelines for robotics. \n - The presentation is excellent, with a clear and intuitive proof sketch for the core result. The main Theorem 6 and proof sketch provide a clear framework for how to think about the tradeoffs in interaction algorithms.\n\nWeakness:\n - The paper makes use of Hellinger/TV-style distances throughout and uses a very strong indicator-based loss. It is unclear if these results transfer to a continuous-control setting, which is the principal setting of the experiments and presumably downstream applications. In particular bounds for continuous settings by necessity require much stronger assumptions on the expert (c.f. \"The Pitfalls of Imitation Learning when the Action Space is Continous\", Simchowitz et. al.). I believe there is considerable value in studying the tabular MDP case, but that the general claims need to be narrowed to better reflect that this only applies to discrete MDPs.\n\n - The original DAgger paper considers probabilistic switching between the expert and the learned policy on data collection rollouts, whereas WARM-STAGGER/STAGGER appear to roll out the learned policy directly after collecting the initial data. Properly tuned probabilistic switching between $\\pi^E$ and $\\pi^n$ should prevent the \"warm start issues\" mentioned in Proof Sketch of Theorem 6 (see the \"beta\" parameter in the original DAgger Ross et. al. paper). Slow mixing DAgger should explore E with higher probability, and therefore I believe would have similar properties to the WARM-STAGGER algorithm presented in this work.", "was_revised": true, "final_justification": "I think this paper is a fine addition to the literature. It is limited to the discrete-action setting as it requires a TV-style loss, although there are tasks (such as language) where this is applicable. As the authors note in the paper the Theorem 4 shows performance matching at least the baselines is somewhat weak. However, the specific construction underlying Theorem 6, on which their method provably performs better than the baselines, is very clean and presents a nice picture for how to think about interactive methods.\n\nI overall retain my original score of a 5--as a theoretical work this is very nicely presented and thorough, although not groundbreaking (they analyze a longstanding, existing method) and the theory certainly has limitations.", "rebuttal": "We thank reviewer 9Cf7 for the thoughtful and detailed feedback. We appreciate your recognition of our theoretical framework, the clarity of Theorem 6, and the relevance of DAgger-style analysis to modern robotics. Below, we address your specific concerns. \n\n**For W1 and Q1: Applicability of Theoretical Results to Continuous Control**\n\nWe thank the reviewer for this insightful observation. We agree that our theoretical analysis is specific to discrete-action MDPs and does not directly extend to continuous control settings such as MuJoCo. Our intention was to use MuJoCo primarily to illustrate the practical viability of our state-wise annotation model and algorithms, rather than to validate our theoretical bounds. We agree that continuous imitation learning presents unique challenges such as exponential-in-horizon compounding errors, and that DAgger-style theoretical analysis in this setting remains largely open.\n\nWe will revise relevant statements to clarify this distinction:\n\n\"Empirical results on the synthetic MDP support our theoretical findings, while MuJoCo experiments demonstrate the practical viability and competitive performance of our state-wise annotation model and algorithms on continuous control tasks.\" \n\nThat said, we are currently conducting additional experiments on discrete-action environments (e.g., Atari) and language model distillation tasks, which more directly align with our theoretical framework. Results from these ongoing efforts will be included in the final or extended version of the paper.\n\n\n**For W2: Probabilistic Switching vs. Warm-Start**\n\nFor clarity of exposition, we analyze DAgger without stochastic mixing with the expert (as also done in [1]), since setting $\\beta = 0$ yields the best policy suboptimality guarantee in the original DAgger paper. \nWe agree that stochastic mixing with the expert is a useful practical heuristic. Meanwhile, Warm-Stagger\ncan also be viewed as a form of stochastic mixing with $\\beta = 1$ for the $N_{\\text{off}}$ offline trajectories and $\\beta = 0$ for interactive rounds. While properly tuned probabilistic switching may also mitigate warm-start issues in our MDP example, we adopt this hybrid IL formulation to enable a clean analysis. Extending our framework to incorporate stochastic mixing is an interesting direction for future work.\n\n\n**For Q2: Clarification of Terminology – \"Offline\",  \"Interactive\" , \"Hybrid\"**\n\nWe appreciate the reviewer’s suggestion. In this paper, we deliberately use the terms \"offline\", \"interactive\", and \"hybrid\", to distinguish between three supervision regimes. The term online only appears in the context of online learning as induced by our theoretical reduction, and we deliberately avoid using online imitation learning to prevent confusion. \n\n\n\n\n**Thank You!**\n\nWe hope the above clarifications address your concerns, and we sincerely thank you for your thoughtful and supportive feedback.\n\n\n[1] D. J. Foster, A. Block, and D. Misra. “Is behavior cloning all you need? Understanding horizon in imitation learning.” NeurIPS 2024."}]

Author rebuttal:

Meta-review: The paper studies imitation learning in the realizable, discrete-action case. It compares non-interactive IL (such as behavior cloning) to interactive IL (such as DAgger). The paper considers a cost model where we can ask the expert for annotations either for a single state, or for an entire trajectory (at a factor-C discount from the cost if we separately queried each state). So the learner can use four kinds of data: offline or online collection and state or trajectory queries.

Earlier work pointed out that, if we’re restricted to whole-trajectory queries and the realizable case, there’s no benefit to allowing interaction in the worst case. (This contrasts sharply with the non-realizable case, in which there can be a strong benefit to interaction: we need it to see how to recover from the inevitable errors in matching a non-realizable expert. It would be really great if the authors could emphasize more strongly this dependence on realizability, e.g., in the paragraph that starts at line 38.)

The paper asks whether removing the whole-trajectory restriction can improve data efficiency for interactive IL, while leaving the other choices above intact. It answers affirmatively: it presents new algorithms (Stagger and Warm-Stagger) that have better bounds on the amount of data needed. It also presents experiments (both in settings that match the theory and in settings “inspired by” the theory) that confirm that the new algorithms can be useful.

The reviewers agree that the paper is clear and that the analysis is sound. The question is well posed, and the answer is interesting. The reviewer/author discussion was helpful, the authors were responsive, and hopefully the discussion will improve the final version.
Decision: Accept (poster)