Paper deep dive
When Does On-Policy Interaction Help? Representational Tradeoffs in Value-Based Imitation Learning
Luca Viano, Antoine Moulin, Audrey Huang, Volkan Cevher, Philip Amortila, Dylan J. Foster
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 96%
Last extracted: 8/3/2026, 3:12:57 AM
Summary
The paper introduces OVI, an interactive on-policy imitation learning algorithm that leverages value function estimation to relax representational demands. The authors demonstrate that expert interaction allows the learner to succeed by realizing only the expert's value function (Q_pi_E-realizability), rather than the stricter policy realizability required by methods like Behavior Cloning. OVI is shown to be statistically and computationally efficient, outperforming offline and interactive policy-based methods, particularly when the learner's network is less expressive than the expert's. Theoretical results prove that interaction is necessary for value-based IL, as offline methods scale with expert policy complexity without stronger assumptions.
Entities (8)
Relation Signals (8)
OVI → isa → Interactive On-Policy Imitation Learning Algorithm
confidence 98% · Concretely, we introduce OVI, an interactive on-policy IL algorithm
OVI → relieson → Q_pi_E-realizability
confidence 97% · OVI is statistically efficient whenever the learner can represent the expert's value function
Expert Interaction → enables → Q_pi_E-realizability
confidence 96% · Our main finding is that expert interaction relaxes the representational demands on the learner: one only needs a model capable of realizing the expert's value function
OVI → outperforms → Behavior Cloning
confidence 95% · OVI outperforms offline policy-based (BC)
OVI → outperforms → DAgger
confidence 95% · OVI outperforms ... interactive policy-based (DAgger)
Behavior Cloning → suffersfrom → compounding errors
confidence 95% · Standard approaches such as Behavior Cloning (BC) are known to suffer from compounding errors
Offline IL → requiresstrongerassumptionsthan → Q_pi_E-realizability
confidence 94% · without stronger assumptions beyond expert-value realizability alone, any offline IL algorithm must scale with the complexity of the expert policy class
OVI → outperforms → SPOIL
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Imitation learning (IL)---training an agent to replicate expert behavior from demonstrations---underpins applications from robotics to language model training. Standard approaches such as Behavior Cloning (BC) are known to suffer from compounding errors and performance plateaus, particularly when the learner cannot perfectly represent the expert's policy (as is typical, e.g., in distillation). Two interventions are widely understood empirically to improve performance: querying the expert interactively along the learner's own trajectories, and using value function estimation en route to generating a policy rather than directly fitting the expert's full action distribution. We investigate the nature of these improvements and their potentially surprising interplay. Our main finding is that expert interaction relaxes the representational demands on the learner: one only needs a model capable of realizing the expert's value function, bypassing the (often stricter) requirement of realizing the expert's policy itself. Concretely, we introduce OVI, an interactive on-policy IL algorithm that is statistically efficient whenever the learner can represent the expert's value function and computationally efficient given access to a linear maximization oracle. We complement this with a negative result showing that interaction is necessary. Namely, without stronger assumptions beyond expert-value realizability alone, any offline IL algorithm must scale with the complexity of the expert policy class. Our findings bear out empirically. OVI outperforms offline policy-based (BC), interactive policy-based (DAgger), and offline value-based IL methods, with the largest gains when the learner network is substantially less expressive than the expert's.
Tags
Links
- Source: https://arxiv.org/abs/2607.29617v1
- Canonical: https://arxiv.org/abs/2607.29617v1
Trouble viewing inline? Open PDF directly →
Full Text
243,634 characters extracted from source content.
Expand or collapse full text
When Does On-Policy Interaction Help? Representational Tradeoffs in Value-Based Imitation Learning Luca Viano * luca.viano@epfl.ch Antoine Moulin * antoine.moulin@upf.edu Audrey Huang audreyh5@illinois.edu Volkan Cevher volkan.cevher@epfl.ch Philip Amortila p.amortila@berkeley.edu Dylan J. Foster dylanfoster@microsoft.com Abstract Imitation learning (IL)—training an agent to replicate expert behavior from demonstrations—underpins applica- tions from robotics to language model training. Standard approaches such as Behavior Cloning (BC) are known to suffer from compounding errors and performance plateaus, particularly when the learner cannot perfectly represent the expert’s policy (as is typical, e.g., in distillation). Two interventions are widely understood empirically to improve performance: querying the expert interactively along the learner’s own trajectories, and using value function estimation en route to generating a policy rather than directly fitting the expert’s full action distribution. We investigate the nature of these improvements and their potentially surprising interplay. Our main finding is that expert interaction relaxes the representational demands on the learner: one only needs a model capable of realizing the expert’s value function, bypassing the (often stricter) requirement of realizing the expert’s policy itself. Concretely, we introduceOVI, an interactive on-policy IL algorithm that is statistically efficient whenever the learner can represent the expert’s value function and computationally efficient given access to a linear maximization oracle. We complement this with a negative result showing that interaction is necessary. Namely, without stronger assumptions beyond expert-value realizability alone, any offline IL algorithm must scale with the complexity of the expert policy class. Our findings bear out empirically.OVIoutperforms offline policy-based (BC), interactive policy-based (DAgger), and offline value-based IL methods, with the largest gains when the learner network is substantially less expressive than the expert’s. 1 Introduction Training a model to replicate the behavior of a more capable expert—a process known as imitation learning (IL)—has become a central paradigm in modern AI. In language modeling, distillation trains a smaller language model (LM) to reproduce the outputs of a larger one (Agarwal et al., 2024; Lu and Thinking Machines Lab, 2025); in robotics and autonomous navigation, agents learn complex manipulation skills directly from expert demonstrations (Osa et al., 2018; Pomerleau, 1988). Predominant approaches such as Behavior Cloning (BC, Pomerleau, 1991) often suffer from slow convergence, training instability, and performance plateaus even given ample offline expert data (de Haan et al., 2019; Block et al., 2024; Laskey et al., 2017; Hu et al., 2025; Spencer et al., 2021). These shortcomings are commonly attributed to two interrelated phenomena: error propagation along the horizon (Ross and Bagnell, 2010; Ross et al., 2011), and the inability of the learner to faithfully capture the expert’s policy (Espinosa-Dice et al., 2025; Rohatgi et al., 2025). Two interventions are commonly observed empirically to mitigate each of these problems in turn. The first intervention is that of on-policy interaction, i.e., the act of querying the expert along the learner’s own trajectories. Interactive (or on-policy) IL is understood to avoid error amplification by learning to correct mistakes on-policy. This benefit has classically been formalized through improved horizon dependence (Ross et al., 2011; Rajaraman et al., 2021a). However, recent work by Foster et al. (2024) establishes that when the learner can accurately represent the expert policy, the apparent gap betweenBCand interactive IL disappears, making the precise role of interaction less clear than it once seemed. * Equal contribution. 1 arXiv:2607.29617v1 [cs.LG] 31 Jul 2026 1 32 1 16 1 8 1 4 1 0 0.5 1 Normalized return Acrobot-v1 1 32 1 16 1 8 1 4 1 CartPole-v1 1 32 1 16 1 8 1 4 1 Pendulum-v1 1 32 1 16 1 8 1 4 1 LunarLander-v2 Learner/Expert hidden layer size ratio OVI (Ours) (online, value-based) SPOIL (offline, value-based) DAgger (online, policy-based) BC (offline, policy-based) Figure 1:OVIachieves higher return with smaller learner networks. Average normalized return (y-axis,1and0 correspond to the expert’s and to a bad policy’s returns, respectively) as a function of the learner-to-expert network-width ratio (x-axis), over50seeds and10expert trajectories for offline methods or10rounds of expert queries along learner trajectories for interactive methods. The expert network has width64. We compare with offline and interactive policy-based methods (BC; Pomerleau, 1988;DAgger; Ross et al., 2011), and the offline value-based methodSPOIL (Moulin et al., 2025a). When the learner network shrinks,OVIoutperforms each of the following methods alone: (1) offline value-based and (2) interactive policy-based—thereby supporting the theory that predicts that represen- tational gains can emerge only from expert interaction and value-based design jointly. See Section 3.3 for more details. A second, parallel intervention is value-based IL, where an estimated value or reward function is used to assist policy learning (Garg et al., 2021; Swamy et al., 2021, 2022a), subsuming most inverse reinforcement learning (IRL) and apprenticeship learning methods (Abbeel and Ng, 2004; Syed and Schapire, 2007; Ho and Ermon, 2016). Rather than fitting the expert’s full distribution over actions, including potentially arbitrary or exogenous choices with equal value, value-based IL seeks to recover only enough information to match the expert’s return. This raises the hope that a value-based learner can succeed with a weaker representational burden, e.g., needing only to represent the expected value of each action even when representing the expert policy itself is too demanding. While previous works have sought to develop a theoretical understanding of value-based IL (Abbeel and Ng, 2004; Syed and Schapire, 2007; Joshi et al., 2026; Moulin et al., 2025a), existing methods either do not address the sequential setting or require structural assumptions on the environment; as a result, our understanding of the benefits of value-based IL remains incomplete. In this work, we investigate the mechanisms through which value functions and interaction help in IL. Our results reveal a potentially surprising interplay: interaction relaxes representational demands on the learner. Leveraging on-policy imitation, one only needs a model capable of realizing the expert’s value function, bypassing the (often stricter) requirement of realizing the expert’s policy itself. Furthermore, this is not possible in offline IL. Our contributions are detailed below. Interaction permits efficient value-based IL (Section 3). We introduceOVI(Algorithm 1), the first algorithm that is statistically and computationally oracle-efficient under onlyQ π E -realizability—a natural representational assumption re- quiring only that the learner can represent the expert’s value function—provided that the learner can interactively query the expert on-policy.OVIqueries the expert along the learner’s own trajectories and leverages a saddle-point formulation of IL to identify a useful value function, building on prior work (Moulin et al., 2025a; Swamy et al., 2021). We comple- ment this with a study on the representational advantages ofQ π E -realizability (Section 3.2): we show in several natural problem classes that representing the expert’s value function can be significantly easier than representing its policy, and furthermore that the weaker assumption of reward realizability is in general insufficient for (offline or interactive) IL. Interactive value-based IL empirically enables learning with fewer parameters (Section 3.3). We validate these findings empirically in Gymnasium (Towers et al., 2025); see Figure 1. Consistent with our theory,OVIoutperforms 2 both interactive policy-based methods (DAgger; Ross et al., 2011) and offline value-based methods (SPOIL; Moulin et al., 2025a), especially as the learner’s network shrinks relative to the expert’s—a regime in which policy realizability is likely to be increasingly violated. The code for these experiments is available athttps://github.com/lviano/ovi. Interaction is necessary for value-based IL (Section 4). We prove that without conditions stronger thanQ π E - realizability, all offline IL algorithms given only an offline dataset of expert trajectories necessarily scale with the number of states in the environment or the complexity of the expert policy class (Theorem 4.1). We further establish that an important subclass of value-based learners (including popular empirical algorithms) can fail to compete with the expert policy in the offline setting even in the limit of infinite data (Theorem 4.2). Intuitively, the hardness arises because, unlike in traditional policy-based IL (e.g., viaBCorDAgger), value-based learners match the expert’s return without matching its state visitation distribution (cf. Figure 2); our results indicate that this can be drastically more efficient under interaction but fails to overcome well-studied distribution shift challenges (Ross et al., 2011; Rajaraman et al., 2020; Foster et al., 2024) present in offline IL. Computational-representational tradeoffs in chain-of-thought learning (Section 5). Lastly, we provide a comple- mentary perspective on the benefits of interaction in IL by showing thatOVIcan achieve an exponential computational improvement over existing reward-based approaches (Joshi et al., 2026) when specialized to chain-of-thought learning. Prior theoretical approaches for value-based IL in chain-of-thought learning extract an imitating policy from a learned outcome reward function, but require intractable exponential-weights-type updates and response-level sampling. We show that, leveraging interaction and value function realizability,OVIuses value functions to decompose the search over complete responses into a series of tractable token-level policy updates. This gives new theoretical understanding and motivation for the successful use of on-policy updates (Agarwal et al., 2024; Gu et al., 2024; Yang et al., 2025) and process reward models (Lightman et al., 2024; Uesato et al., 2023) in LM training. When does interaction help in IL? Going beyond the classical understanding of improved horizon dependence, our results reveal additional (and perhaps stronger) representational benefits of interaction. Taken together, they provide a comprehensive picture of the interplay between interaction and representation in value-based IL. 2 Problem Setting: Value-Based Imitation Learning We first provide general definitions of Markov decision processes (MDPs) and the general IL problem, and then formally describe our problem setting of value-based imitation learning. 2.1 Imitation Learning Episodic MDPs. An episodic MDP is defined as a tupleM = (X,A,H,P,r,ν 0 ), whereXis a (potentially large) finite state space,Ais a finite action space withA≥ 2actions,H ∈ Nis the horizon,P = (P h : X ×A→ ∆(X )) H h=1 is the transition kernel,r = (r h : X ×A→ [0, 1]) H h=1 is the reward function, andν 0 ∈ ∆(X )is the initial state distribution. A nonstationary Markov policy (henceforth simply policy) is a sequence of decision rulesπ = (π h : X → ∆(A)) H h=1 , it induces a distributionP π over trajectories(x h ,a h ,r h ) H h=1 via the following interaction protocol: an initial statex 1 ∼ ν 0 is drawn, and then for eachh = 1,...,H, we havea h ∼ π h (·|x h ),r h = r h (x h ,a h ), andx h+1 ∼ P h (·|x h ,a h ). We denote byE π the corresponding expectation. The expected return of a policyπis given byJ π = E π P H h=1 r h , and the value functions are defined for any state-action pair (x,a) by V π h (x) = E π h P H h ′ =h r h ′ x h = x i and Q π h (x,a) = E π h P H h ′ =h r h ′ x h = x,a h = a i . The value functions satisfy the Bellman equations Q π h (x,a) = r h (x,a) + E x ′ ∼P h (·|x,a) V π h+1 (x ′ ) , V π h (x) = E a∼π h (·|x) [Q π h (x,a)],(1) whereV π H+1 = 0. We define the occupancy measures viad π h (x,a) = P π [x h = x,a h = a]andd π h (x) = P π [x h = x]. To disentangle the effects of reward scaling from the horizonH, we assume rewards are normalized such that for some Q max > 0and any feasible trajectory, P H h=1 r h ∈ [0,Q max ](Jiang and Agarwal, 2018; Wang et al., 2020; Zhang et al., 2021). 1 For any policyπand functionf : X ×A→ R, we sometimes use the notationf (x,π) = P a π(a|x)f (x,a). 1 In general (the dense reward setting),Q max can be as large asH, but in some settings (e.g., in LM reasoning tasks with binary outcome-level rewards) we can have Q max =O(1) (the sparse reward setting). 3 Offline and interactive imitation learning. In the imitation learning setting that we consider, there is an unknown expert policyπ E and an unknown MDPM, and the goal is to learn a policy that performs as well asπ E , as measured by expected return. Formally, for error toleranceε > 0and failure probabilityδ > 0, the learner’s objective is to output a policy π out such that, with probability at least 1− δ, J π E − J π out ≤ ε.(2) Central to our paper is the distinction between offline and interactive imitation learning. In offline IL, the learner is given a dataset of pre-collected independent expert trajectories D E = n x i E,h ,a i E,h H h=1 o n E i=1 ,where x i E,h ,a i E,h ∼ d π E h ,(3) where n E is the number of samples. The learner cannot interact with the MDP or the expert further. In contrast, in interactive IL the learner can query the expertπ E for actions while rolling out in the unknown MDP M—importantly, without observing the rewards. For the purpose of our paper, we formalize on-policy interaction as follows: in each round of interaction, the learner selects a policyπto generate a state trajectory(x h ) H h=1 where x h ∼ d π h and might query expert actions at states along the trajectory, i.e., a E,h ∼ π E,h (·|x h ). 2.2 Value-Based Imitation Learning Our focus is on value-based imitation learning, by which we mean methods that derive policies from learned value or reward functions. Classical policy-based methods (e.g.,BC,DAgger) aim to imitate the full conditional action distribution of the expertπ E and to match its performance as a consequence. By contrast, value-based learners aim to recover only enough information to match the expert’s return, which may be a simpler task whenever there is redundancy in the expert’s trajectory distribution (Example 3.1) or relevant structure in the dynamics that can be exploited (Example 3.2). In particular, our goal is to develop value-based IL algorithms that succeed with only realizability of the expert’s value function, a natural representational assumption for value-based IL. Stated in learning-theoretic terms, the learner has access to a value function classQ⊆(Q h : X ×A→ [0,Q max ]) H h=1 that can be used to recover a good policy, and we assume only the following on its expressivity. Assumption 2.1 (Q π E -realizability). The classQ contains the expert’s value function, i.e., Q π E ∈Q. By contrast, policy-based methods, such asBCandDAgger, commonly require policy realizability assumptions (Foster et al., 2024), which render them inapplicable in this setting. In Section 3.2, we highlight several natural settings in which representing the expert’s value function is drastically less stringent than realizing the expert’s policy. Accordingly, in Section 3.1 we will develop algorithms for interactive IL whose statistical rates depend only on the statistical capacity of the value function classQ (e.g., log(|Q|) for finite function classes) and not the policy class used by the learner. Value-based realizability assumptions comparable to Assumption 2.1 have been analyzed in previous works, although they further required assumptions about the dynamics of the MDP. In particular, Joshi et al. only consider theH = 1 (“contextual bandit”) setting, where Assumption 2.1 simplifies to realizability of the reward function, and Moulin et al. require closure-type assumptions onQ, i.e., that it can realizeQ π for any policyπgenerated by the learner. 2 In Section 3.2, we further establish that mere reward realizability is insufficient for general environments whenH > 1 (Theorem 3.2), indicating that Q π E -realizability is a natural minimal assumption for value-based IL. Comparing interactive value-based IL to related settings. Finally, we clarify the differences between our value-based IL setting and related IL settings considered in the literature. All of the settings mentioned below allow the learner to roll out in the MDP, but use protocols for interacting with the expert that differ from ours. In inverse RL, the learner interacts with the MDP or with known MDP dynamics, but does not query the expert interactively (Abbeel and Ng, 2004; Syed and Schapire, 2007; Ziebart et al., 2008). In value-feedback algorithms such asAggreVaTe(Ross and Bagnell, 2014; Sun et al., 2017), the learner interacts with the MDP and can observe the expert valueQ π E (x h ,a h ), whereas it is unclear how to directly estimate these values in our setting given that the learner does not observe rewards. Lastly, in a setting we call RL with expert advice, the learner both interacts with the MDP and queries the expert (or a reference policy that covers it well) interactively, but additionally observes rewards in the MDP (Amortila et al., 2022; Tiapkin et al., 2024; Foster et al., 2025). See Appendix B for a comprehensive discussion of related work. 2 Such “completeness” assumptions implicitly place restrictions on the dynamics (Chen and Jiang, 2019; Foster et al., 2022; Jiang and Xie, 2025), and by contrast with Assumption 2.1 cannot be satisfied by simply taking a more expressiveQ class. 4 3 Interaction Enables Q π E -Realizable Value-Based Imitation The main result of this section isOVI, the first provably efficient algorithm for value-based IL underQ π E -realizability. In Section 3.1, we describe the algorithm and its guarantees. We then show in Section 3.2 thatQ π E -realizability can be weaker than policy realizability, while reward realizability alone is insufficient. Finally, in Section 3.3 we present empirical evidence thatOVIoutperforms both policy-based methods (DAgger; Ross et al., 2011) and offline value-based methods (SPOIL; Moulin et al., 2025a) in regimes where policy realizability is likely to be violated. 3.1 OVI: Value-Based Imitation Learning With Only Q π E -Realizability Algorithm design. Following an approach suggested by the “On-Q” moment matching template (Swamy et al., 2021), OVItreats the problem of minimizing the suboptimality gap in Eq. (2) as a min-max game between aπ-player and a Q-player. The starting point is the performance difference lemma (Howard, 1960; Kakade and Langford, 2002): J π E − J π = H X h=1 L d π h (π h ,Q π E h ), where, for any d = (d h ∈ ∆(X )) H h=1 , L d h (π,Q) := X x∈X d h (x) | z (I) X a∈A (π E,h (a|x)− π(a|x))Q(x,a) |z (I) . This form is not enough yet to derive an algorithm because Q π E is unknown. However, assuming Q π E ∈Q, we bound the suboptimality by taking the supremum overQ h : =Q h :∃Q ′ ∈Q,Q ′ h = Q h for every h on the right hand side. J π E − J π ≤ H X h=1 sup Q h ∈Q h L d π h (π h ,Q h ). Accordingly, what remains is to find an approximate saddle point of the expected advantage function, i.e., a policyπ out such that, for all h∈ [H], sup Q h ∈Q h L d π out h (π out,h ,Q h )≲ ε/H . Algorithmically, the main point of departure from prior value-based IL algorithms is the layer-wise learning of a good policy, in the vein of theForwardalgorithm (Ross and Bagnell, 2010). To understand this design choice, we recall that the approach employed by past work (Moulin et al., 2025a) is to compute a sequence(π k ,Q k ) K k=1 whereπ k performs online mirror ascent (Beck and Teboulle, 2003) andQ k performs a best response to (an empirical estimate of) the loss functionL. This technique does not seem to apply in theQ π E -realizability setting, as the sequenceπ k is also dictating the current sampling distributiondunder which the error is measured (see(I)above), preventing us from simultaneously forming an empirical estimate ofLand controlling the error in(I)via online learning. This is addressed inOVIby learningπ out one layer at a time (note the outer loop overh = 1,...,Hin line 2 of Algorithm 1), asd π out h (x)only depends on(π out,1 ,...,π out,h−1 )and we can thus fix the sampling distribution for stagehbefore optimizing forπ out,h . We view this algorithm as a principled algorithmic realization of the “On-Q” moment matching template introduced by Swamy et al. (2021). The pseudocode forOVIis given in Algorithm 1. The main sample complexity guarantee is stated below. It establishes thatOVIonly requires a number of expert queries that scales with the statistical capacity of the value function classQ, as represented by its log-cardinality log|Q|. Theorem 3.1 (Sample complexity ofOVI). Let Assumption 2.1 hold for a finite classQ. Then, for anyε,δ ∈ (0, 1), OVI(Algorithm 1) with parametersn E = e O(H 4 Q 4 max log(A) log(|Q|/δ)ε −4 ),η = (log(A)/(KQ 2 max )) 1/2 , andK = O(H 2 Q 2 max log(A)ε −2 ), outputs a policy π out such that with probability at least 1− δ, J π E − J π out ≤ ε after e O H 5 Q 4 max log(A) log(|Q|/δ) ε 4 expert queries. Note that the total number of learner interactions with the environment obeys the same bound with an extra factor ofH. Up to the usual polynomial factors in the horizonH, the suboptimality1/ε, and the log failure probabilitylog(δ −1 ), the main appealing feature ofOVIis that its sample complexity is controlled by the statistical complexity of only the value function classQ, through its log-cardinality. In particular, the guarantee imposes no statistical assumption 5 Algorithm 1 OVI: On-Policy Value-Based Imitation Learning 1: input: Learning rate η, iterations K, expert queries per stage n E . 2: for h = 1,...,H do 3:Create dataset at stage h: for i∈ [n E ], sample x i h ∼ d π out h , and query a i E,h ∼ π E,h (·|x i h ). 4:Initialize π 1 h = Unif(A). 5:for k = 1,...,K do 6:Set Q k h ∈ arg max Q h ∈Q h P n E i=1 (Q h (x i h ,a i E,h )− Q h (x i h ,π k h )). 7:Set π k+1 h (a|x)∝ π k h (a|x)e ηQ k h (x,a) , for any state-action pair (x,a). 8:Create the output policy at layer h: π out,h = 1 K P K k=1 π k h . on the learner’s policy class. We show in Section 3.2 that, in many natural settings, a function classQsatisfying Q π E -realizability can be drastically smaller than a policy classΠsatisfyingπ E -realizability, while it is the latter that governs the sample complexity of policy-based methods such asBCorDAgger. We note that the dependence on the problem horizon is larger than that obtained by policy-based methods such asBCorDAgger(Foster et al., 2024); it is an interesting question whether this can be improved further or if this is fundamental to value-based IL. Theorem 3.1 is a special case of Theorem F.1, which extends this guarantee to infinite value function classes via covering numbers. The result also shows that, whenQ is convex, the expert-query complexity improves to e O(ε −2 ). Computationally,OVIonly requires access to a standard linear maximization oracle for theQupdates (Line 6 in Algorithm 1) and standard softmax policy updates for theπplayer (Line 7 in Algorithm 1). One drawback is that the layer-wise updates learn a potentially nonstationary policy and introduce computation and memory requirements that scale linearly with the horizon. However, in our experiments (Section 3.3), we find that a stationary approximation of OVI performs well. We refer to Appendix D for details. Improved rates for nonconvex classes. The rate attained byOVIfor nonconvex classesQhas a suboptimal e O(ε −4 ) dependence. This can be improved to an e O(ε −2 )rate via a variant ofOVI, namedQ-OVI(Algorithm 3), where the roles of the value functions and the policies are reversed, i.e., theQplayer performs online learning and theπplayer performs a best response (Theorem H.1). While statistically more efficient, this relies on explicitly discretizing the value-function classQ, making the method computationally unattractive for large or continuous classes such as neural networks. It is an interesting question to obtain a rate of e O(ε −2 ) in a computationally efficient manner. Another advantage ofQ-OVIis that it can be used to compute a stationary expert-matching policy (see Appendix H.3), whereasOVIlearns a nonstationary policy. Whether a computationally efficient value-based IL algorithm can compute such a stationary policy remains open. 3.2 Representational Advantages of Q π E -Realizability OVI requires only access to a value-function class that realizes the expert’s value function,Q π E . In this section, we show that, in many natural settings,Q π E -realizability is substantially weaker than the assumptions used by prior policy- and value-based approaches. We also establish that reward realizability alone is insufficient. 3.2.1 Value realizability can be weaker than policy realizability Classical IL algorithms, such asBC,DAgger, and their derivatives, are policy-based: they operate by directly fitting the expert’s entire conditional distribution of actions, and the performance of these algorithms classically relies on a policy realizability assumption (Foster et al., 2024). Assumption 3.1 (Policy realizability). The policy class Π contains the expert policy, i.e., π E ∈ Π. This assumption is natural if the goal is to reproduce the expert’s trajectory distribution in a reward-free manner. But the objective in IL is weaker: to match the expert’s return. For this objective, it may be unnecessary and wasteful to attempt to fit the specific details of the expert distribution (e.g., how it breaks ties among equally good actions, or how it responds to features that are irrelevant for value). The examples below formalize this intuition. Joshi et al. (2026) consider the special case of our setting in whichH = 1, and show that value-based IL can be strictly weaker than policy-based IL (note that whenH = 1,Q π E -realizability reduces to reward realizability). In particular, they 6 show that when the expert is optimal and realized by the policy classΠ, the class can be used to construct a realizable reward-function classR 3 satisfying|R|≤|Π|, simply by takingR =r :∃π ∈ Π,r(x,a) = 1a∈ supp(π(·|x)). By contrast, they show that the existence of a small realizable reward classRcannot be used to construct a small realizable policy class Π under which BC will succeed. 4 Our first example extends this to the multi-step setting. Example 3.1 (Learning to answer from correct demonstrations, withH > 1). Given a finite classΠthat realizes an optimal expertπ E , we show in Appendix C.1 that it is possible to construct a classQsuch that|Q|≤|Π|andQrealizes a function e Q π E which assigns maximal value to actions within the expert support, defined by e Q π E (x,a) = Q max 1a∈ supp(π E (·|x)) .OVIstill succeeds, even if we cannot guarantee thatQ π E ∈Q(see Appendix C.1.1). Conversely, as above, when given a smallQclass satisfyingQ π E -realizability, the learner cannot construct a small policy classΠ satisfying π E ∈ Π. We come back to this example in Section 5.◁ We note that this reduction is enabled by the relaxedQ π E -realizability condition detailed in Appendix C.1.1. In the H > 1setting, the closest comparable value-based IL work is theSPOILalgorithm of Moulin et al., which requires that Qcan realizeQ π for all policiesπgenerated by the learner. In that setting, it is highly unclear whether there exists a similar reduction from a small policy classΠto a small function classQthat satisfies this closure-type condition. Thus, under prior value expressivity conditions, value-based IL may not be representationally weaker than policy-based IL. Our second example shows that, even with suboptimal experts, the same separation can arise from structure in the dynamics, as the value function may ignore high-dimensional information needed to reproduce the expert’s exact actions. Example 3.2 (Structure in the dynamics). In Appendix C.2, we study an Exogenous Block MDP (Efroni et al., 2022; Mhammedi et al., 2024; Amortila et al., 2024b), where the dynamics and reward depend only on low-dimensional endogenous state components, while the observations contain high-dimensional exogenous noise. We construct a family of MDPs and expert policies and show that any expert-agnostic policy classΠsatisfying Assumption 3.1 must be exponentially large. In contrast, the same two-dimensional classQ satisfies Assumption 2.1 for the entire family. ◁ Although the two assumptions need not be comparable in general, we expect value realizability to be weaker than policy realizability in a wide range of analogous settings. This is empirically supported by our experiments in Section 3.3. 3.2.2 Reward realizability is insufficient The expert’s value functionQ π E encodes information about the expert policyπ E , the reward function, and the transitions of the MDP via the Bellman equations (Eq. (1)). A natural question is whether the assumption can be weakened to reward realizability alone while retaining efficient learning. Specifically, assume that the learner has access to a reward function classR⊆(r ′ h : X ×A→ [0, 1]) H h=1 satisfying the following expressivity condition. Assumption 3.2 (Reward realizability). The classR contains the MDP’s reward function, i.e., r ∈R. The following result shows that mere reward realizability is insufficient for efficient IL. Our lower bound is established against the class of interactive IL algorithms defined below, formalizing the interaction protocol described in Section 2.1. Definition 3.1 (Interactive IL algorithm). An interactive IL algorithmAlgwith a fixed interaction budgetn E ∈ N ⋆ is a (potentially randomized) procedure that, in each episodek ∈ [n E ], selects a policyπ k based on the preceding interaction history, rolls it out in the MDP to generate statesx k h ∼ d π k h for allh∈ [H], and is allowed to query the expert for actionsa k E,h ∼ π E,h (·|x k h )for allh∈ [H], without observing rewards. After then E episodes, it maps the resulting interaction history to a nonstationary policy (π out,h : X → ∆(A)) H h=1 . Our negative result for this setting establishes a lower bound on the rounds of interactions used by any algorithm following the protocol defined in Definition 3.1. Given an MDPM, we writeJ π M for the return of a policyπ, andπ ⋆ M for one of its optimal deterministic policies. Theorem 3.2 (Lower bound under reward realizability). For everyX ≥ 1andε∈ (0, 1/4], there exists a familyFof MDPs with: i) stochastic initial states but deterministic rewards and transitions, i) horizonH = 2, i) state space size |X| = O(X), and iv) family sizelog(|F|) = O(X), such that for everyM ∈ F, Assumption 3.2 is satisfied by the same singleton reward classR = r ⋆ . LetAlgbe any interactive IL algorithm (Definition 3.1). Then, there exists 3 Up to a reward shaping term that does not alter the optimal policy. 4 While the learner knows that policies in Π must be supported on reward-maximizing actions, the set of such policies is prohibitively large. 7 an MDPM∈F, with corresponding expertπ E = π ⋆ M , such thatAlgneedsΩ X ε rounds of interactions to output a policy π out such that E[J π E M − J π out M ]≤ ε. 5 We recall that the results of Joshi et al. (2026) establish that reward realizability is sufficient in the offline setting when H = 1. By sharp contrast, our lower bound establishes that this is insufficient even whenH = 2, and even with interaction. As a simple corollary of Theorem 3.2, either the number of environment interactions or the number of expert queries must beΩ(min|X|, log(|F|)/ε), and thus it is not possible to be polynomial in the relevant problem parameters (log(|R|),H,ε −1 , log(δ −1 )) for both resources simultaneously. Our results provide some worst-case impossibility results for the “reward” moment matching template of Swamy et al. (2021). In general, to avoid the “tabular” rateΩ(|X|), we expect that algorithms for this setting must estimate functionals of the dynamics, and thus additional structural conditions on the environment or additional representational ability, e.g. of the dynamics (Liu et al., 2022; Kidambi et al., 2021; Viano et al., 2024; Moulin et al., 2025b) or temporal differences of candidate Q functions (Garg et al., 2021), may be needed. We leave this as an interesting direction for future work. Intuitively, the source of hardness leading to Theorem 3.2 is that, even though the reward provides information on which states are rewarding, it does not provide information on which actions lead to those states. Consequently, the learner cannot use the reward information to learn how to act at steph = 1, and must resort to either using an expert query and cloning the received action or applying a learner’s action in the environment and using the observed next state to learn the dynamics. Overall this takesmin|X|, log(|F|)/εsamples. By contrast, Theorem 3.1 shows that this transition-dependent information is encoded in Q π E and can be exploited by OVI. All in all, we viewQ π E -realizability as a minimal representational assumption for efficient learning: it is more informative than reward realizability alone, which is insufficient, but less demanding than other assumptions (e.g., policy realizability, realizability ofQ π for infinitely-many policiesπ, or realizability of rewards and transitions) discussed in this paper and prior work. We next provide empirical evidence that the minimality ofQ π E -realizability translates to more effective IL when using learners with limited expressivity. 3.3 Experiments We test whether the representational benefits suggested by Section 3.2 translate into practical performance when the learner has limited capacity. In each of four Gymnasium environments (Towers et al., 2025), the expert is an RL-trained policy represented by a network with two hidden layers of 64 neurons each, while the learners use the same depth but have widths in2, 4, 8, 16, 32, 64. We use network width as a proxy for representational capacity: as the learner’s network becomes smaller relative to that of the expert, representing the expert’s action distribution should become increasingly difficult, and policy-based methods such asBCandDAggermay therefore degrade relative toOVI. The code for these experiments is available at https://github.com/lviano/ovi. We evaluateOVI,SPOIL,BC, andDAggeracross the above range of widths. We use10expert trajectories for the offline methods,10learner-trajectory labeling rounds for the interactive methods, and50seeds (see Appendix D for more experimental details). Figure 1 shows that when the learner also has64neurons per layer,BCandDAggerperform well in all four environments. Their performance degrades, however, as the learner network shrinks. In contrast,OVI dominates across all learner sizes and attains good performance even at the smallest width.SPOILgenerally deteriorates faster thanOVI, especially inCartPole-v1andAcrobot-v1, consistent with the possibility thatQ π E -realizability is easier to satisfy in these experiments than the closure-type realizability conditions required bySPOIL. We use a stationary approximation to OVI in these experiments; see Algorithm 2 for pseudocode. Finally, we compareDAggerandOVIin a syntheticQ π E -realizable MDP to highlight that, despite both IL algorithms being interactive, OVI implements a different imitation mechanism than DAgger. (Figure 2)DAggervs.OVI: a different imitation mechanism. Although also an interactive IL method,DAggeris surprisingly suboptimal in this environment, which is an extended version of the simpleQ π E -realizable instance used in Theorem 4.2 (defined for Theorem 4.1 and illustrated in Figure 7). As displayed in Figure 2, the reward suboptimality, i.e.,J π E −J π out , ofOVI(solid red line) converges significantly faster than the suboptimality ofDAgger(solid purple line). The advantage ofOVIstems from the fact that it directly matches the expert’s return, whileDAgger, being a policy-based 5 The expectation is over all randomness in the protocol, including the trajectories sampled from the MDP, the actions sampled from the expert policy, and the internal randomness of Alg. 8 method, attempts to match the expert’s actions almost everywhere, which is a harder problem in the MDP under consid- eration because there areO(2 |X| )possible optimal policies from which the expert can choose. In comparison,OVIacts approximately 6 greedily with respect to its learnedQ π E , which is sufficient to achieve the optimal return with signifi- cantly fewer samples but at the cost of potentially learning a policy different from the expert’s. To illustrate the difference between the learning mechanisms of these two algorithms, we plot in Figure 2 their trajectory-level TV distance to the ex- pert,D TV (P π E ,P π out ), which decreases underDAgger(dashed purple line) but remains constant forOVI(dashed red line). 4 Interaction Is Necessary for Q π E -Realizable Value-Based Imitation In Section 3, we showed that interaction enablesOVIto succeed under onlyQ π E -realizability, a weaker representational requirement than those imposed by comparable algorithms. Here, we prove that interaction is in fact necessary: under Q π E -realizability alone, no offline IL method can learn efficiently. We formally define an offline IL algorithm below. Definition 4.1 (Offline IL Algorithm). An offline IL algorithmAlgis a (potentially randomized) mapping from an expert datasetD E (sampled according to Eq. (3)) to a nonstationary policy (π out,h : X → ∆(A)) H h=1 . Our main negative result (Theorem 4.1), stated formally below, establishes that there exists a large family of MDPs (and corresponding optimal expert policies) with a small value function class exhibitingQ π E -realizability for each MDP in the class, but for which the sample complexity of any offline IL algorithm must scale with either the size of the state space or the number of MDPs in the class. For the statement below, we recall that, for an MDPM, we writeJ π M for the return of a policy π, and π ⋆ M for one of its optimal deterministic policies. Theorem 4.1 (Main lower bound for offline IL). For anyX ∈ N ⋆ and anyε ∈ (0, 1 8 ], there exists a familyFof MDPs with: i) stochastic initial states but deterministic rewards and transitions, i) horizonH = 2, i) state space size|X| = O(X), and iv) family sizelog(|F|) = O(X), as well as a value function classQwith|Q| = 2such that for everyM ∈ F, Assumption 2.1 is satisfied for expert policyπ E = π ⋆ M . LetAlgbe any offline IL algorithm (Definition 4.1). Then, there exists an MDPM∈Fsuch thatAlgneedsn E ≥ Ω( X ε )trajectories sampled according to Eq. (3) with expert policy π ⋆ M , to output a policy π out such that E[J π ⋆ M M − J π out M ]≤ ε. 7 In other words, any offline imitation learner needs at leastΩ(min|X|, log(|F|)/ε)samples to obtain a near-optimal policy, even when there exists a small value function class satisfyingQ π E -realizability for every MDP in the problem class. 8 We note that similar “tabular” lower bound rates have appeared for offline IL (Rajaraman et al., 2020, 2021b; Foster et al., 2024), though with a focus on establishing the optimal dependence on horizon. By comparison, our lower bound shows that the worst-case offline IL rate continues to depend on the number of states even when there exists a small value function class for the problem class, and even for H = 2. In Table 1, we summarize various representational assumptions considered in this work and whether they are statistically tractable or intractable in the offline or interactive IL settings. RepresentationReward rValue Q π E Policy π E Offline IL (Definition 4.1)✗ (Theorem 3.2)✗ (Theorem 4.1)✓ (e.g., BC) Interactive IL (Definition 3.1)✗ (Theorem 3.2)✓ ⋆ (OVI; Theorem 3.1)✓ (e.g., DAgger) Table 1: Tractability of imitation learning (forH > 1) under different representational assumptions.✓: A poly(log(|F|),H,ε −1 , log(δ −1 ))sample complexity is possible, whereFis a given finite reward/value/policy class satisfying realizability (Assumptions 3.2, 2.1, and 3.1, respectively).✗: Said polynomial sample complexity is not possible. ⋆ : incurs additional log(A) dependence. 6 The OVI iterates become more and more greedy with respect to Q π E as K increases. 7 The expectation is over the training data and the internal randomness of Alg. 8 By contrast, OVI succeeds on the MDPs defined in the proof of Theorem 4.1 with one expert query outside the support of its state distribution. 9 0125102050100200500 Expert queries / iterationsk 0.0 0.2 0.4 0.6 0.8 1.0 OVI(Ours) DAgger Return suboptimality Total Variation suboptimality Figure 2: Comparison of reward suboptimality,J π E − J π out , and total variation distance,D TV (P π E ,P π out )forOVIand DAggerin a synthetic environment satisfying Assumption 2.1 (illustrated in Figure 7).OVImatches expert return (see solid lines) without matching the expert trajectory distribution (see dashed lines). Next, we show a stronger negative result for any algorithm which only uses value-induced policies, defined below. Definition 4.2 (Value-induced policy class). An offline IL algorithmAlg(Definition 4.1) uses a value-induced (VI) policy class (for value function classQ) if it outputs policies of the formπ out,h (a|x)∝ f (w T (Q 1:K h )(x,a)), for some parameter K ∈ N, sequence Q 1:K ∈Q K , linear parameter w ∈ R K , and function f : R→ R + . The VI policy class encompasses the policies used by a broad class of algorithms that extract policies from value functions by applying activation functions (e.g., softmax, ReLU, greedy) to linear combinations of value functions from Q. 9 In particular, it includes the implicit policy classes used by prior theoretical and empirical value-based IL methods (Moulin et al., 2025a; Joshi et al., 2026; Garg et al., 2021; Watson et al., 2023) as well as byOVI. See Appendix G for details. The following lower bound shows that, underQ π E -realizability alone, offline learners with VI policy classes fail to compete with the expert’s performance, even in the limit of infinite data. Theorem 4.2 (Unidentifiability under VI policies). There exists a familyFof MDPs with: i) deterministic initial states, rewards, and transitions, i) horizonH = 2, i) state space size|X| = 3, and iv) family size|F| = 2, as well as a value function classQwith|Q| = 2such that for everyM∈F, Assumption 2.1 is satisfied for the expert π E = π ⋆ M . Moreover, for any algorithmAlg(Definition 4.1) with a VI policy class (Definition 4.2), for anyn E ∈ N ⋆ , there exists an MDPM∈Fsuch that, givenn E expert trajectories sampled fromπ E ,Algoutputs policiesπ out such that E[J π E M − J π out M ]≥ 1 4 . 10 The intuition for Theorem 4.2 is that the value-induced policies must randomize uniformly among actions with equally high value, even though the expert itself may only play a subset of those actions. In the construction of Theorem 4.2 (illustrated in Figure 6), this implies that the learner’s output policy goes out of distribution with constant probability, thus incurring a constant error rate for all dataset sizes. We expect that unidentifiability continues to hold under broader definitions of the VI policy class which assign probabilities to actions based on their value profiles (Sun et al., 2019a). Our lower bounds in this section (Theorem 4.1 and Theorem 4.2) show that interaction is necessary in general for learning with onlyQ π E -realizability. We conclude this section by briefly discussing how the interaction and representational requirements can be relaxed in certain settings. Coverage circumvents the offline lower bound. If the expert induces a distribution over the state space with sufficient coverage, then distribution shift no longer causes issues for offline algorithms that output a VI policy such asSPOIL(Ap- pendix I). In particular, in Theorem I.1, we prove sample complexity guarantees forSPOILunderQ π E -realizability, expert optimality and a standard coverage condition (Munos, 2003; Antos et al., 2008; Chen and Jiang, 2019; Xie et al., 2023; Amortila et al., 2024c; Jiang and Xie, 2025). However, we do not consider this an easy assumption to satisfy in practice. Representational benefits of mixing expert and learner rollouts. Finally, we show that additional representational benefits can arise when the dataset includes trajectories from both the learner and the expert, with the expert being 9 We note that greedy policies are only included as pointwise limits of other VI policies, as shown in Appendix G. 10 The expectation is over the training data and the internal randomness of Alg. 10 queried at all such states (a technique commonly used in LM distillation; Agarwal et al., 2024; Li et al., 2026a). We show that a variant ofOVIthat mixes learner and expert trajectories succeeds wheneverQsatisfies eitherQ π E -realizability (Assumption 2.1) or theSPOIL-like closure condition, which requiresQ π ∈ Qfor every policyπgenerated by the learner, without knowing in advance which condition holds (Theorem J.1). 5 Chain-of-Thought Learning: Computational-Representational Tradeoffs The preceding sections showed that interaction relaxes the representational requirements for the learner. Here, we show howOVIcan be instantiated in the setting of LM reasoning to achieve exponential improvements in computational efficiency over existing approaches (Joshi et al., 2026), provided that the expert’s value can be realized, thereby providing a complementary perspective on the value of interaction in IL. Reasoning tasks such as mathematics and code generation have become a central focus of modern LM research (Wei et al., 2022; Li et al., 2022). In these domains, objective evaluators (such as unit and integration tests for coding and formal ver- ifiers for math) are often available and can be used as a “ground truth” reward function. To solve these problems, LMs are trained to generate a sequence of tokens, called a chain of thought (CoT), before outputting the final answer. To acquire CoT reasoning, LMs can be trained via IL, commonly via next-token prediction (Ouyang et al., 2022; Cobbe et al., 2021) on expert reasoning traces consisting of a prompt, the expert’s complete chain-of-thought, and the correct final answer. CoT learning (Malach, 2024; Joshi et al., 2025) has been formalized as follows. The LM is modeled as an autoregressive policy that, given a promptx ∈ X, samples a responsey ∈ Yviay ∼ π(·|x), wherey = (y 1 ,...,y H−1 ,y H ) is a sequence ofHtokens, belonging to a token vocabulary denoted byΣ, generated autoregressively asy h ∼ π(·|x,y 1 ,...,y h−1 ),h = 1,...,H, and the last tokeny H is the final answer. This interaction defines a token-level MDP with horizonH, where states are the partial generations so far,x h = (x,y 1:h−1 )∈X × Σ h−1 , the action is the next tokeny h ∈ Σ, and the next state isx h+1 = (x,y 1:h ). The learner is given access to a datasetD =(x,y), where the promptxis sampled from a given prompt distribution, and the response is generated by the expert,y ∼ π E (·|x). The reward function is a binary outcome verifier defined asr : X ×Y →0, 1so that the expected return of a policy, J π = E π [r(x,y)], is equivalent to its answer accuracy. The goal of IL then translates to the problem of producing a policy π out whose final-answer accuracy competes with the expert’s. Non-interactive reward-based IL is intractable computationally. A natural simplification to CoT learning, exploiting that the dynamics are deterministic and known, is to treat the CoT problem as anH = 1problem (i.e., a contextual bandit), where the promptxis the context and the responsey ∈ Σ H is an action. Under a reward (or outcome verifier) realizability assumption (Assumption 3.2), Joshi et al. (2026) estimate a rewardbrfrom the demonstrationsDusing an exponential-weights-type procedure which, at each iteration, must solvearg max y∈Σ H br(x,y)to extract a response for a given promptx. 11 Their procedure presents two computational barriers. First, the reward optimization is over the full response spaceY = Σ H , which is computationally intractable for long horizons. Second, performing exponential weight updates over the reward class is infeasible as it requires enumerating over the reward class. Computational benefits of value-based interactive IL. To exploit the inherently sequential nature of CoT learning, we can applyOVIdirectly to the token-level MDP generated by the interaction of the prompt distribution, the LM, and the outcome verifierr. At each steph,OVIlearns a value function that naturally induces a softmax token sampling distribution (Line 7 of Algorithm 1). This decomposes the previously intractable search over the response spaceΣ H intoHlocal search steps. Moreover, each stage of the problem is solved byOVIusing simple linear maximization oracles for the value function search (Line 6 of Algorithm 1) and softmax updates for the policy (Line 7 of Algorithm 1), which can be implemented at scale. Indeed, our approach suggests a loss function for the value network which can be minimized via backpropagation coupled with modern optimizers. It is worth noting that the computational benefits ofOVIover sequence-level methods like Joshi et al. (2026) come at the cost of a stronger representational requirement (realizing the expert’s value function for each step rather than simply the reward of the final answer) as well as interactive query access to the expert. Both of these additional assumptions have been widely shown to improve performance; the first can naturally be interpreted as requiring an architecture capable of expressing a process verifier (or process reward model; Lightman et al., 2024; Uesato et al., 2023), as opposed to simply an outcome verifier, and the second corresponds to the setting of on-policy distillation (Agarwal et al., 2024; Gu 11 We note that our reward-based lower bound Theorem 3.2 does not apply in CoT learning since the dynamics in the token-level MDP are known. 11 et al., 2024; Yang et al., 2025) which has been widely employed in language modeling. Our results therefore provide a novel theoretical justification for the use of process reward models and on-policy interaction in LM training. Whether these gains translate to practical value-based IL algorithms for language models is a very interesting empirical question. 6 Conclusion What is the value of interaction in IL? In this work, we investigated the mechanisms through which interaction and value function estimation help in IL, revealing a perhaps surprising interplay: interaction relaxes the representational demands on the learner, allowing it to succeed while realizing only the expert’s value function, as opposed to the expert’s full policy or the value functions of all learner-generated policies. We formalized this throughOVI, an interactive value-based IL algorithm that is statistically and computationally efficient underQ π E -realizability alone, and a complementary lower bound establishing that interaction is necessary for IL under this minimal assumption. Specializing to chain-of-thought reasoning, we further showed that these representational benefits can translate into exponential computational gains over non-interactive approaches (Joshi et al., 2026). These findings suggest that the benefits of interaction in IL extend well beyond the classical understanding of improved horizon dependence. Several interesting future directions remain open. On the technical side, it would first be valuable to obtain anO(ε −2 ) rate for nonconvex classesQwith a computationally efficient algorithm. Second, while underπ E -realizability nearly horizon-free bounds are possible (Foster et al., 2024), whether the same is achievable for value-based IL is an interesting open question. Finally, it would be interesting to study value-based IL in the presence of value function misspecification; we expect that the relevant forms of misspecification differ from their counterparts in value-based RL (Chen and Jiang, 2019; Du et al., 2020; Amortila et al., 2023, 2024a; Maran and Szepesvári, 2026). On the empirical side, it would be valuable to understand whetherOVI(or value-based IL methods more broadly) can be effective in language model distillation, where expert policy realizability is unlikely to hold. 12 Acknowledgments We thank Gergely Neu for interesting discussions about this project. LV was supported by the Swiss Data Science Center under fellowship number P22_03. AM received funding from the European Research Council (ERC), under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 950180). PA gratefully acknowledges the support of DARPA through award No. HR00112520022. Part of this research was performed while AM and AH were visiting the Institute for Mathematical and Statistical Innovation (IMSI), which is supported by the National Science Foundation (Grant No. DMS-2425650). References Pieter Abbeel and Andrew Y. Ng. Apprenticeship learning via inverse reinforcement learning. In International Conference on Machine Learning, 2004. URLhttps://icml.c/Conferences/2004/proceedings/papers/ 335.pdf. Pieter Abbeel, Dmitri Dolgov, Andrew Y. Ng, and Sebastian Thrun.Apprenticeship learning for motion planning with application to parking lot navigation.In IEEE/RSJ International Con- ference on Intelligent Robots and Systems, 2008.URLhttps://ai.stanford.edu/~ang/papers/ iros08-ApprenticeshipLearningParkingLotNavigation.pdf. Rishabh Agarwal, Nino Vieillard, Yongchao Zhou, Piotr Stanczyk, Sabela Ramos Garea, Matthieu Geist, and Olivier Bachem. On-policy distillation of language models: Learning from self-generated mistakes. In The twelfth international conference on learning representations, 2024. URL https://arxiv.org/abs/2306.13649. Philip Amortila, Nan Jiang, Dhruv Madeka, and Dean Foster. A few expert queries suffices for sample-efficient RL with resets and linear value approximation. In Advances in Neural Information Processing Systems, 2022. URL https://openreview.net/forum?id=d19Dsqtw421. Philip Amortila, Nan Jiang, and Csaba Szepesvári. The optimal approximation factors in misspecified off-policy value function estimation. In International Conference on Machine Learning, 2023. URLhttps://proceedings.mlr. press/v202/amortila23a.html. Philip Amortila, Tongyi Cao, and Akshay Krishnamurthy. Mitigating covariate shift in misspecified regression with applications to reinforcement learning. In The Thirty Seventh Annual Conference on Learning Theory, 2024a. URL https://arxiv.org/abs/2401.12216. Philip Amortila, Dylan J Foster, Nan Jiang, Akshay Krishnamurthy, and Zakaria Mhammedi. Reinforcement learning under latent dynamics: Toward statistical and algorithmic modularity. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024b. URL https://openreview.net/forum?id=qf2uZAdy1N. Philip Amortila, Dylan J Foster, and Akshay Krishnamurthy. Scalable online exploration via coverability. In Forty-first International Conference on Machine Learning, 2024c. URL https://arxiv.org/abs/2403.06571. András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning, 2008. URLhttps://link.springer. com/article/10.1007/s10994-007-5038-2. Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 2003. URL https://w.tau.ac.il/~becka/3.pdf. Adam Block, Dylan J Foster, Akshay Krishnamurthy, Max Simchowitz, and Cyril Zhang. Butterfly effects of SGD noise: Error amplification in behavior cloning and autoregression. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=CgPs04l9TO. Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013. 13 Abdeslam Boularias, Jens Kober, and Jan Peters. Relative entropy inverse reinforcement learning. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, 2011. URLhttps://proceedings. mlr.press/v15/boularias11a.html. Sébastien Bubeck, Nicolo Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends® in Machine Learning, 2012. URL https://arxiv.org/abs/1204.5721. Locke Cai, Max Ryabinin, and Ivan Provilkov. Escaping the verifier: Learning to reason via demonstrations. In International Conference on Machine Learning, 2026. URL https://openreview.net/forum?id=pS1khvoxHT. Haoqun Cao and Tengyang Xie.Understanding behavior cloning with action quantization.arXiv preprint arXiv:2603.20538, 2026. URL https://arxiv.org/abs/2603.20538. Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006. Jinglin Chen and Nan Jiang. Information-theoretic considerations in batch reinforcement learning. In 36th International Conference on Machine Learning, 2019. URL https://proceedings.mlr.press/v97/chen19e.html. Ching-An Cheng, Xinyan Yan, Nolan Wagener, and Byron Boots. Fast policy learning through imitation and reinforce- ment. arXiv preprint arXiv:1805.10413, 2018. URL https://arxiv.org/abs/1805.10413. Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021. URL https://arxiv.org/abs/2110.14168. Chris Cundy and Stefano Ermon. Sequencematch: Imitation learning for autoregressive sequence modelling with backtracking. In The Twelfth International Conference on Learning Representations, 2024. URLhttps:// openreview.net/forum?id=FJWT0692hw. Robert Dadashi, Léonard Hussenot, Damien Vincent, Sertan Girgin, Anton Raichuk, Matthieu Geist, and Olivier Pietquin. Continuous control with action quantization from demonstrations. In 39th International Conference on Machine Learning, 2022. URL https://proceedings.mlr.press/v162/dadashi22a.html. Pim de Haan, Dinesh Jayaraman, and Sergey Levine. Causal confusion in imitation learning. In Advances in Neural Information Processing Systems, 2019. URLhttps://proceedings.neurips.c/paper_files/paper/2019/ file/947018640bf36a2b609d3557a285329-Paper.pdf. Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. Is a good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Representations, 2020. URLhttps: //arxiv.org/pdf/1910.03016. Yonathan Efroni, Dylan J Foster, Dipendra Misra, Akshay Krishnamurthy, and John Langford. Sample-efficient reinforcement learning in the presence of exogenous information. In Proceedings of Thirty Fifth Conference on Learning Theory, 2022. URL https://proceedings.mlr.press/v178/efroni22a.html. Nicolas Espinosa-Dice, Sanjiban Choudhury, Wen Sun, and Gokul Swamy. Efficient imitation under misspecification. In International Conference on Representation Learning, 2025. URLhttps://openreview.net/forum?id= fn36V5qsCw. Chelsea Finn, Sergey Levine, and Pieter Abbeel. Guided cost learning: Deep inverse optimal control via policy optimization. In Proceedings of The 33rd International Conference on Machine Learning, 2016. URLhttps: //proceedings.mlr.press/v48/finn16.html. Dylan J Foster, Akshay Krishnamurthy, David Simchi-Levi, and Yunzong Xu. Offline reinforcement learning: Fundamental barriers for value function approximation.In Conference on Learning Theory, 2022.URL https://arxiv.org/abs/2111.10919. Dylan J Foster, Adam Block, and Dipendra Misra. Is behavior cloning all you need? understanding horizon in imitation learning. In Annual Conference on Neural Information Processing Systems, 2024. URLhttps://openreview.net/ forum?id=8KPyJm4gt5. 14 Dylan J Foster, Zakaria Mhammedi, and Dhruv Rohatgi. Is a good foundation necessary for efficient reinforcement learning? the computational role of the base model in exploration. In Proceedings of Thirty Eighth Conference on Learning Theory, 2025. URL https://proceedings.mlr.press/v291/foster25a.html. Justin Fu, Katie Luo, and Sergey Levine. Learning robust rewards with adverserial inverse reinforcement learning. In International Conference on Learning Representations, 2018. URLhttps://openreview.net/forum?id= rkHywl-A-. Divyansh Garg, Shuvam Chakraborty, Chris Cundy, Jiaming Song, Matthieu Geist, and Stefano Ermon. IQ-learn: Inverse soft-Q learning for imitation. In Advances in Neural Information Processing Systems, 2021. URLhttps: //arxiv.org/abs/2106.12142. Note: Read arXiv version for correct version and complete author list. Yuxian Gu, Li Dong, Furu Wei, and Minlie Huang. MiniLLM: Knowledge distillation of large language models. In International Conference on Learning Representations, 2024. URLhttps://openreview.net/forum?id= 5h0qf7IBZZ. Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. In International Conference on Machine Learning, 2017. URLhttps://proceedings.mlr.press/v70/ haarnoja17a.html. Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in Neural Informa- tion Processing Systems, 2016. URLhttps://proceedings.neurips.c/paper_files/paper/2016/file/ c7e2b878868cbae992d1fb743995d8f-Paper.pdf. Jonathan Ho, Jayesh Gupta, and Stefano Ermon. Model-free imitation learning with policy optimization. In Proceedings of The 33rd International Conference on Machine Learning, 2016. URLhttps://proceedings.mlr.press/v48/ ho16.html. Ronald A Howard. Dynamic programming and Markov processes. John Wiley, 1960. Zheyuan Hu, Robyn Wu, Naveen Enock, Jasmine Jia ni Li, Riya Kadakia, Zackory Erickson, and Aviral Kumar. Rac: Robot learning for long-horizon tasks by scaling recovery and correction. In Workshop on Making Sense of Data in Robotics: Composition, Curation, and Interpretability at Scale at CoRL 2025, 2025. URLhttps: //openreview.net/forum?id=y8wskVS7BV. Chen Jia. Adversarial moment-matching distillation of large language models. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum?id=0VeSCjRDBy. Nan Jiang and Alekh Agarwal. Open problem: The dependence of sample complexity lower bounds on planning horizon. In Conference On Learning Theory, 2018. URL https://proceedings.mlr.press/v75/jiang18a.html. Nan Jiang and Tengyang Xie. Offline reinforcement learning in large state spaces: Algorithms and guarantees. Statistical Science, 2025. URL https://arxiv.org/abs/2510.04088. Nirmit Joshi, Gal Vardi, Adam Block, Surbhi Goel, Zhiyuan Li, Theodor Misiakiewicz, and Nathan Srebro. A theory of learning with autoregressive chain of thought. In Proceedings of Thirty Eighth Conference on Learning Theory, 2025. URL https://arxiv.org/abs/2503.07932. Nirmit Joshi, Gene Li, Siddharth Bhandari, Shiva Kasiviswanathan, Cong Ma, and Nathan Srebro. Learning to answer from correct demonstrations. In The Fourteenth International Conference on Learning Representations, 2026. URL https://openreview.net/forum?id=69fIHgLjyH. Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In International Conference on Machine Learning, 2002. URLhttps://homes.cs.washington.edu/~sham/papers/rl/aoarl. pdf. Rahul Kidambi, Jonathan Chang, and Wen Sun. Mobile: Model-based imitation learning from observation alone. In Advances in Neural Information Processing Systems, 2021. URL https://arxiv.org/abs/2102.10769. 15 Ilya Kostrikov, Kumar Krishna Agrawal, Debidatta Dwibedi, Sergey Levine, and Jonathan Tompson. Discriminator- actor-critic: Addressing sample inefficiency and reward bias in adversarial imitation learning. In International Conference on Learning Representations, 2019. URL https://openreview.net/forum?id=Hk4fpoA5Km. Ilya Kostrikov, Ofir Nachum, and Jonathan Tompson. Imitation learning via off-policy distribution matching. In Interna- tional Conference on Learning Representations, 2020. URL https://openreview.net/forum?id=Hyg-JC4FDr. Michael Laskey, Jonathan Lee, Roy Fox, Anca Dragan, and Ken Goldberg. Dart: Noise injection for robust imitation learning. In Proceedings of the 1st Annual Conference on Robot Learning, 2017. URLhttps://proceedings.mlr. press/v78/laskey17a.html. Changhao Li, Rushi Qiang, Jiawei Huang, Chenxiao Gao, Chao Zhang, Niao He, and Bo Dai. Revisiting dagger in the era of llm-agents. arXiv preprint arXiv:2605.12913, 2026a. URL https://arxiv.org/abs/2605.12913. Jiaxiang Li, Siliang Zeng, Hoi To Wai, Chenliang Li, Alfredo Garcia, and Mingyi Hong. Getting more juice out of the SFT data: Reward learning from human demonstration improves SFT for LLM alignment. In Annual Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum?id=orxQccN8Fm. Shangzhe Li, Dongruo Zhou, and Weitong Zhang. Near-optimal second-order guarantees for model-based adversarial imitation learning. In The Fourteenth International Conference on Learning Representations, 2026b. URLhttps: //openreview.net/forum?id=PD8wnZOV1J. Yichen Li and Chicheng Zhang. On efficient online imitation learning via classification. In Advances in Neural Information Processing Systems, 2022. URL https://openreview.net/forum?id=h2imPVlCCyN. Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. Competition-level code generation with alphacode. Science, 2022. URL https://arxiv.org/pdf/2203.07814. Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let’s verify step by step. In The twelfth international conference on learning representations, 2024. URL https://openreview.net/forum?id=v8L0pN6EOi. Sihan Liu, Gaurav Mahajan, Daniel Kane, Shachar Lovett, Gellért Weisz, and Csaba Szepesvári. Exponential hardness of reinforcement learning with linear function approximation. In The Thirty Sixth Annual Conference on Learning Theory, 2023. URL https://proceedings.mlr.press/v195/liu23b.html. Zhihan Liu, Yufeng Zhang, Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. Learning from demonstration: Provably efficient adversarial policy imitation with linear function approximation. In International Conference on Machine Learning, 2022. URL https://proceedings.mlr.press/v162/liu22u.html. Kevin Lu and Thinking Machines Lab. On-policy distillation. Thinking Machines Lab: Connectionism, 2025. URL https://thinkingmachines.ai/blog/on-policy-distillation. Eran Malach. Auto-regressive next-token predictors are universal learners. In Forty-first International Conference on Machine Learning, 2024. URL https://arxiv.org/abs/2309.06979. Davide Maran and Csaba Szepesvári. Beyond least squares: Uniform approximation and the hidden cost of misspec- ification. Advances in Neural Information Processing Systems, 2026. URLhttps://papers.nips.c/paper_ files/paper/2025/file/f5ecc67e8b2f4941137bcbde901ac6be-Paper-Conference.pdf. Zakaria Mhammedi, Dylan J Foster, and Alexander Rakhlin. The power of resets in online reinforcement learning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URLhttps://openreview. net/forum?id=7sACcaOmGi. Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 2015. URL https://w.nature.com/articles/nature14236. 16 Antoine Moulin, Gergely Neu, and Luca Viano. Inverse Q-learning done right: Offline imitation learning inQ π - realizable MDPs. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025a. URL https://openreview.net/forum?id=tvEE9KQcLi. Antoine Moulin, Gergely Neu, and Luca Viano.Optimistically optimistic exploration for provably efficient infinite-horizon reinforcement and imitation learning.In Conference on Learning Theory, 2025b.URL https://proceedings.mlr.press/v291/moulin25a.html. Rémi Munos. Error bounds for approximate policy iteration. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, pages 560–567, 2003. Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. In Advances in Neural Information Processing Systems, 2019. URLhttps://proceedings. neurips.c/paper_files/paper/2019/file/cf9a242b70f45317ffd281241fa66502-Paper.pdf. Andrew Y. Ng and Stuart J. Russell. Algorithms for inverse reinforcement learning. In International Conference on Machine Learning, 2000. URL https://ai.stanford.edu/~ang/papers/icml00-irl.pdf. Francesco Orabona. A modern introduction to online learning, 2026. URLhttps://arxiv.org/abs/1912.13213v10. Takayuki Osa, Joni Pajarinen, Gerhard Neumann, J Andrew Bagnell, Pieter Abbeel, and Jan Peters. An algorithmic perspective on imitation learning. Foundations and Trends® in Robotics, 2018. URLhttps://arxiv.org/abs/ 1811.06711. 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, 2022. URLhttps://proceedings.neurips.c/paper/2022/ hash/b1efde53be364a73914f58805a001731-Abstract.html. Dean A. Pomerleau. Alvinn: An autonomous land vehicle in a neural network. In Advances in Neural Infor- mation Processing Systems, 1988. URLhttps://proceedings.neurips.c/paper_files/paper/1988/file/ 812b4ba287f5e0bc9d43bbf5bbe87fb-Paper.pdf. Dean A. Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neural Computation, 1991. URL https://ieeexplore.ieee.org/document/6796843. Nived Rajaraman, Lin Yang, Jiantao Jiao, and Kannan Ramchandran. Toward the fundamental limits of imitation learning. In Advances in Neural Information Processing Systems, 2020. URLhttps://proceedings.neurips. c/paper_files/paper/2020/hash/1e7875cf32d306989d80c14308f3a099-Abstract.html. Nived Rajaraman, Yanjun Han, Lin Yang, Jingbo Liu, Jiantao Jiao, and Kannan Ramchandran.On the value of interaction and function approximation in imitation learning.In Advances in Neural Informa- tion Processing Systems, 2021a. URLhttps://proceedings.neurips.c/paper_files/paper/2021/hash/ 09dbc1177211571ef3e1ca961c39363-Abstract.html. Nived Rajaraman, Yanjun Han, Lin F. Yang, Kannan Ramchandran, and Jiantao Jiao. Provably breaking the quadratic error compounding barrier in imitation learning, optimally, 2021b. URL https://arxiv.org/abs/2102.12948. N. D. Ratliff, J. A. Bagnell, and M. A. Zinkevich. Maximum margin planning. In International Conference on Machine Learning, 2006. URL https://dl.acm.org/doi/10.1145/1143844.1143936. Siddharth Reddy, Anca D. Dragan, and Sergey Levine. SQIL: imitation learning via regularized behavioral cloning. arXiv:1905.11108, 2019. URL https://arxiv.org/abs/1905.11108. Dhruv Rohatgi, Adam Block, Audrey Huang, Akshay Krishnamurthy, and Dylan J. Foster. Computational-statistical tradeoffs at the next-token prediction barrier: Autoregressive and imitation learning under misspecification. In Conference on Learning Theory, 2025. URL https://proceedings.mlr.press/v291/rohatgi25a.html. Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In International Conference on Artificial Intelligence and Statistics, 2010. URL https://proceedings.mlr.press/v9/ross10a.html. 17 Stephane Ross and J Andrew Bagnell. Reinforcement and imitation learning via interactive no-regret learning. arXiv preprint arXiv:1406.5979, 2014. URL https://arxiv.org/abs/1406.5979. Stephane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, 2011. URL https://proceedings.mlr.press/v15/ross11a.html. Stuart Russell. Learning agents for uncertain environments (extended abstract). In Annual Conference on Computational Learning Theory, 1998. URL https://dl.acm.org/doi/pdf/10.1145/279943.279964. John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In Proceedings of the 32nd International Conference on Machine Learning, 2015. URLhttps://proceedings. mlr.press/v37/schulman15.html. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv:1707.06347, 2017. URL https://arxiv.org/abs/1707.06347. Lior Shani, Tom Zahavy, and Shie Mannor. Online apprenticeship learning. In AAAI Conference, 2022. URL https://ojs.aaai.org/index.php/AAAI/article/view/20798. Harshit Sikchi, Qinqing Zheng, Amy Zhang, and Scott Niekum. Dual RL: Unification and new methods for reinforce- ment and imitation learning. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=xt9Bu66rqv. Jonathan Spencer, Sanjiban Choudhury, Arun Venkatraman, Brian Ziebart, and J Andrew Bagnell. Feedback in imitation learning: The three regimes of covariate shift. arXiv preprint arXiv:2102.02872, 2021. URLhttps: //arxiv.org/abs/2102.02872. Ved Sriraman, Peihan Liu, Daniel Hsu, and Adam Block. Behavior cloning is not all you need: The optimality of on-policy distillation for noisy expert feedback, 2026. URL https://arxiv.org/abs/2606.30923. Hao Sun and Mihaela van der Schaar. Inverse reinforcement learning meets large language model post-training: Basics, advances, and opportunities. arXiv preprint arXiv:2507.13158, 2025. URLhttps://arxiv.org/abs/2507.13158. Wen Sun, Arun Venkatraman, Geoffrey J. Gordon, Byron Boots, and J. Andrew Bagnell. Deeply AggreVaTeD: Differentiable imitation learning for sequential prediction. In Proceedings of the 34th International Conference on Machine Learning, 2017. URL https://proceedings.mlr.press/v70/sun17d.html. Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, 2019a. URL https://arxiv.org/abs/1811.08540. Wen Sun, Anirudh Vemula, Byron Boots, and Drew Bagnell. Provably efficient imitation learning from observation alone. In Proceedings of the 36th International Conference on Machine Learning, 2019b. URLhttps://proceedings. mlr.press/v97/sun19b.html. Gokul Swamy, Sanjiban Choudhury, J Andrew Bagnell, and Steven Wu. Of moments and matching: A game- theoretic framework for closing the imitation gap. In International Conference on Machine Learning, 2021. URL https://proceedings.mlr.press/v139/swamy21a.html. Gokul Swamy, Sanjiban Choudhury, Drew Bagnell, and Steven Wu. Sequence model imitation learning with unobserved contexts. In Advances in Neural Information Processing Systems, 2022a. URLhttps://openreview.net/forum? id=3nbKUphLBg5. Gokul Swamy, Nived Rajaraman, Matt Peng, Sanjiban Choudhury, J Bagnell, Steven Z Wu, Jiantao Jiao, and Kannan Ramchandran. Minimax optimal online imitation learning via replay estimation. In Advances in Neural Infor- mation Processing Systems, 2022b. URLhttps://proceedings.neurips.c/paper_files/paper/2022/hash/ 2e809adc337594e0fee330a64acbb982-Abstract-Conference.html. 18 Umar Syed and Robert E. Schapire. A game-theoretic approach to apprenticeship learning. In Advances in Neu- ral Information Processing Systems, 2007. URLhttps://papers.nips.c/paper_files/paper/2007/hash/ ca3ec598002d2e7662e2ef4bdd58278b-Abstract.html. Umar Syed, Michael Bowling, and Robert E. Schapire. Apprenticeship learning using linear programming. In International Conference on Machine Learning, 2008. URLhttps://icml.c/Conferences/2008/papers/645. pdf. Daniil Tiapkin, Denis Belomestny, Daniele Calandriello, Eric Moulines, Alexey Naumov, Pierre Perrault, Michal Valko, and Pierre Menard. Demonstration-regularized RL. In The Twelfth International Conference on Learning Representations, 2024. URL https://arxiv.org/abs/2310.17303. Faraz Torabi, Garrett Warnell, and Peter Stone. Behavioral cloning from observation. In International Joint Conference on Artificial Intelligence,, 2018. URL https://arxiv.org/abs/1805.01954. Faraz Torabi, Garrett Warnell, and Peter Stone. Recent advances in imitation learning from observation. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence,, 2019. URLhttps://arxiv.org/ abs/1905.13566. Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U. Balis, Gianluca De Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Markus Krimmel, Arjun KG, Rodrigo Perez-Vicente, et al. Gymnasium: A standard interface for rl environments, 2025. URL https://arxiv.org/abs/2407.17032. Jonathan Uesato, Nate Kushman, Ramana Kumar, H. Francis Song, Noah Yamamoto Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. Solving math word problems with process-based and outcome-based feedback, 2023. URL https://openreview.net/forum?id=MND1kmmNy0O. Roman Vershynin. High-dimensional probability: An introduction with applications in data science. Cambridge university press, 2018. Luca Viano, Angeliki Kamoutsi, Gergely Neu, Igor Krawczuk, and Volkan Cevher. Proximal point imitation learning. In Advances in Neural Information Processing Systems, 2022. URLhttps://proceedings.neurips.c/paper_ files/paper/2022/hash/9988f2c8e07c1f98af7ba9ca31ccae0b-Abstract-Conference.html. Luca Viano, Stratis Skoulakis, and Volkan Cevher. Imitation learning in discounted linear MDPs without exploration assumptions. In International Conference on Machine Learning, 2024. URLhttps://openreview.net/forum? id=DChQpB4AJy. Stefano Viel, Luca Viano, and Volkan Cevher. IL-SOAR : Imitation learning with soft optimistic actor critic. In Forty-second International Conference on Machine Learning, 2025. URLhttps://openreview.net/forum?id= NNr8DHb0L7. Ruosong Wang, Simon S Du, Lin Yang, and Sham Kakade. Is long horizon rl more difficult than short horizon rl? Advances in Neural Information Processing Systems, 2020. URL https://arxiv.org/abs/2005.00527. Joe Watson, Sandy Huang, and Nicolas Heess. Coherent soft imitation learning. In Advances in Neural Infor- mation Processing Systems, 2023. URLhttps://proceedings.neurips.c/paper_files/paper/2023/file/ 2f0435cffef91068ced08d7c7d8e643e-Paper-Conference.pdf. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al.Chain-of-thought prompting elicits reasoning in large language models.Advances in neu- ral information processing systems, 2022.URLhttps://proceedings.neurips.c/paper/2022/hash/ 9d5609613524ecf4f15af0f7b31abca4-Abstract-Conference.html. Gellert Weisz, Philip Amortila, Barnabás Janzer, Yasin Abbasi-Yadkori, Nan Jiang, and Csaba Szepesvari. On query- efficient planning in mdps under linear realizability of the optimal state-value function. In Proceedings of Thirty Fourth Conference on Learning Theory, 2021. URL https://proceedings.mlr.press/v134/weisz21a.html. 19 Runzhe Wu, Yiding Chen, Gokul Swamy, Kianté Brantley, and Wen Sun. Diffusing states and matching scores: A new framework for imitation learning. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=kWRKNDU6uN. Markus Wulfmeier, Peter Ondruska, and Ingmar Posner. Maximum entropy deep inverse reinforcement learning. arXiv preprint arXiv:1507.04888, 2015. URL https://arxiv.org/abs/1507.04888. Markus Wulfmeier, Michael Bloesch, Nino Vieillard, Arun Ahuja, Jorg Bornschein, Sandy Huang, Artem Sokolov, Matt Barnes, Guillaume Desjardins, Alex Bewley, et al. Imitating language via scalable inverse reinforcement learning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URLhttps: //openreview.net/forum?id=5d2eScRiRC. Tengyang Xie, Dylan J Foster, Yu Bai, Nan Jiang, and Sham M Kakade. The role of coverage in online reinforcement learning. In The Eleventh International Conference on Learning Representations, 2023. URLhttps://arxiv.org/ abs/2210.04157. Tian Xu, Ziniu Li, Yang Yu, and Zhi-Quan Luo. Provably efficient adversarial imitation learning with unknown transitions. In Conference on Uncertainty in Artificial Intelligence, 2023. URLhttps://proceedings.mlr.press/ v216/xu23c.html. Tian Xu, Zhilong Zhang, Ruishuo Chen, Yihao Sun, and Yang Yu. Provably and practically efficient adversarial imitation learning with general function approximation. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum?id=7YdafFbhxL. Tian Xu, Chenyang Wang, Xiaochen Zhai, Ziniu Li, Yi-Chen Li, and Yang Yu. Non-adversarial imitation learning provably free of compounding errors: The value flow mechanism. In Forty-third International Conference on Machine Learning, 2026. URL https://openreview.net/forum?id=1UUJrgYr20. An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, et al. Qwen3 technical report. arXiv preprint arXiv:2505.09388, 2025. URLhttps://arxiv.org/abs/2505.09388. Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, 2021. URLhttps://proceedings. mlr.press/v134/zhang21b. B. D. Ziebart, A. Maas, J. A. Bagnell, and A. K. Dey. Maximum entropy inverse reinforcement learning. In National Conference on Artificial Intelligence, 2008. 20 Contents of Appendix A Notation Reference22 B Additional Related Work23 B.1 Theoretical Guarantees for Imitation Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23 B.2 Empirical Value-Based Imitation Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25 C Value-Based Imitation Learning versus Policy-Based: Motivating Examples27 C.1 ConstructingQ from Π Reduces Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27 C.2 Q π E -Realizability Can Be Strictly Weaker Than π E -Realizability under Exogenous Noise . . . . . . .30 D Experiment Details35 D.1 Experiments on the Lower Bound Instance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .35 D.2 Implementation with Neural Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .35 D.3 Additional Details and Comments on the Gym Experiments . . . . . . . . . . . . . . . . . . . . . . .35 E Technical Tools38 E.1 Concentration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38 E.2 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41 E.3 Performance Difference Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .44 I Proofs of Main Results45 F Proofs from Section 345 F.1Proof of Theorem 3.1 (Sample Complexity Guarantee for OVI) . . . . . . . . . . . . . . . . . . . . .46 F.2Proof of Theorem 3.2 (Reward Realizability Is Insufficient) . . . . . . . . . . . . . . . . . . . . . . .49 G Proofs from Section 4 (Q π E -Realizability Is Insufficient to Learn Offline)52 G.1 Proof of Theorem 4.2 (Lower Bound Against Offline Algorithms that Output VI Policies) . . . . . . .52 G.2 Proof of Theorem 4.1 (Lower Bound Against Any Offline IL Algorithm) . . . . . . . . . . . . . . . .55 I Additional Results58 H Q-OVI: An Inefficient Algorithm with Improved Statistical Guarantees58 H.1 Proof of Lemma H.1 (Suboptimality Gap Decomposition for Q-OVI) . . . . . . . . . . . . . . . . . .59 H.2 Proof of Theorem H.1 (Sample Complexity Guarantee for Q-OVI) . . . . . . . . . . . . . . . . . . .61 H.3 Learning a Stationary Policy with Q-OVI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .61 IBreaking the Offline Lower Bound with Coverage64 I.1 OVI with Arbitrary Sampling Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .64 I.2Proof of Theorem I.1 (Offline IL with Coverage and Optimal Expert) . . . . . . . . . . . . . . . . . .67 J On the Benefits of Mixing Expert and Learner Trajectories70 21 A Notation Reference The following table collects notation used throughout the paper. It is meant as a quick reference: the middle column gives only a short description, while the final column points to where the notation is first introduced or used substantively. Table 2: Notation reference. NotationMeaningFirst introduced MDP and imitation-learning setting M = (X,A,H,P,r,ν 0 )Episodic MDP. State spaceX , action spaceA with A =|A|, horizon H , transition kernel P , reward function r, and initial-state law ν 0 . Section 2 π = (π h ) H h=1 Nonstationary Markov policy. π h : X → ∆(A) is a decision rule.Section 2 P π , E π , J π Trajectory law, expectation, and expected return induced by policy π.Section 2 V π h , Q π h State-value and state-action-value functions of policy π at stage h.Section 2 d π h (x), d π h (x,a)State and state-action occupancy measures at stage h under π.Section 2 π E , π E,h Expert policy and its decision rule at stage h.Section 2 π out , π out,h Output policy returned by the learner and its decision rule at stage h.Eq. (2) ε, δTarget suboptimality and failure probability.Eq. (2) D E , n E , x i E,h , a i E,h Offline expert dataset, number of expert samples, and the i-th expert state-action sample at stage h. Eq. (3) Value classes and realizability Q, Q h Sequence-level value-function class and its projection at stage h.Assumption 2.1 Q max Uniform upper bound used for state-action values in the analysis.Section 2 ΠPolicy class used when stating policy realizability comparisons.Assumption 3.1 e Q π E Witness for relaxed Q π E -realizability.Assumption C.1 Q Π Q -realizability Closure assumption requiringQ π ∈Qfor learner-generated policiesπ ∈ Π Q .Assumption J.1 Objectives, empirical estimates, and complexity L d h (p,Q)Expected advantage objective at stage h against the expert action distribution, with states weighted by d h . Section 3.1 and Lemma E.2 L π h Shorthand forL d π h , used when the state distribution is induced by policy π.Appendix F b L h (p,Q)Empirical estimate ofL π out h (p,Q) built from queried expert actions.Appendix F ∆(π)Uniform estimation error between b L h andL π out h for policy π.Lemma F.1 R π h (x)Stage-state regret of the π-player against the expert decision rule.Lemma F.1 N ε (S, d), C ε (S, d)Covering number of S under metric d, and a corresponding ε-cover.Definition E.1 N max ε (Q)Largest covering number overQ,N max ε (Q) : = max h N ε (Q h ,∥·∥ ∞ ).Definition E.1 ∥·∥ ∞,1 Sup-over-states, ℓ 1 -over-actions metric for decision rules.Eq. (5) ρScaled product metric on value functions and decision rules.Eq. (6) Π Q , Π Q,h Policies generated by softmax combinations of functions inQ.Lemma E.3 Algorithmic and appendix-specific notation K, η, π k h , Q k h Number of iterations, learning rate, and the policy/value iterates at stage h.Algorithm 1 Q 1:K , LC, f Value functions, linear combination, and link function that defines a VI policy.Definition 4.2 Π Alg , C ∞ , C 1 Output-policy class and coverage coefficients used when offline learning is possible under expert coverage. Assumptions I.1 and I.2 d = (d h ) H h=1 , b L d h , ∆ d Arbitrary state-sampling distributions and the corresponding empirical objective and estimation error. Algorithm 5 and Theorem I.2 b ℓ π out ,k h Sampled loss used by the Q-OVI exponential-weights update.Algorithm 3 w k h , R w h , b Q π E h Cover weights, their regret, and the closest covering element to Q π E h in the Q-OVI analysis. Lemma H.1 22Appendix table of contents B Additional Related Work We provide an overview of closely related work. In Appendix B.1, we discuss theoretical results available for value- based IL methods, and in Appendix B.2 we cover value-based IL algorithms that focus on empirical performance. We use “value-based IL” broadly to include reward-learning, inverse reinforcement learning, apprenticeship learning, moment matching, and Q-function-based methods, since all use learned reward/value information to derive a policy rather than directly fitting the expert action distribution. B.1 Theoretical Guarantees for Imitation Learning As mentioned in the main text, our work aims to establish expert-sample complexity bounds when expert policy realizability need not hold. While we are the first to study this problem underQ π E -realizability alone, prior work has examined several alternative assumptions that we discuss below. After behavior cloning was proposed in the seminal work of Pomerleau (1988, 1991), a parallel line of work formalized inverse reinforcement learning (IRL; Russell, 1998; Ng and Russell, 2000), whose goal is to infer a reward function that explains the expert’s behavior, typically among many rewards for which the expert is optimal. Closely related work on apprenticeship learning (Abbeel and Ng, 2004; Abbeel et al., 2008; Syed and Schapire, 2007; Syed et al., 2008; Ziebart et al., 2008) uses this reward-based perspective to learn a policy that matches the expert’s performance. Ross and Bagnell (2014) introducedAggreVaTe, an interactive no-regret reduction that augments expert action queries with value information. That is, when the learner visits a state-action pair(x,a),Q π E (x,a)is observed. This oracle is referred to as value feedback and is stronger than our setting, where the learner can query expert actions but does not observe rewards or expert values. Their framework also yields practical algorithms compatible with neural-network- based function approximation; see Sun et al. (2017); Cheng et al. (2018). Value-based feedback, together with access to an interactive expert, is known to allow for better horizon dependence in error propagation (Ross and Bagnell, 2014; Sun et al., 2017), which can lead to representational benefits in policy-based IL (Foster et al., 2024). The closest conceptual predecessor toOVIis the moment-matching framework of Swamy et al. (2021), especially their “On-Q” template and the associatedDAeQuILalgorithm. This framework also includes reward and “Off-Q” moment- matching templates, and analyzes imitation gaps through moment recoverabilityμ: matching action-value moments to precisionεyields a suboptimality bound of orderμHε, improving on the classicalH 2 error-propagation factor in BC-style analyses. Empirically, Swamy et al. (2021) show thatDAeQuILcan outperformBCandDAggerin a forest- navigation task, which they attribute to the mode-seeking behavior induced by action-value moment matching. However, despite the better error-propagation properties of interactive algorithms, Foster et al. (2024) showed that no interactive algorithm can uniformly improve upon an offline one across all possible policy classes. Therefore, the error-propagation- style analysis does not seem sufficient to capture the benefits of interaction. Our contribution is complementary: we instantiate the “On-Q” perspective with a computationally oracle-efficient algorithm, provide a sample-complexity analysis underQ π E -realizability, and show that this representational assumption alone is insufficient in the offline setting. Next, we review value-based IL further, distinguishing (i) offline algorithms that operate on a fixed dataset of expert demonstrations from (i) variants that can additionally access the environment and collect trajectories without observing rewards. Then, we discuss the main policy-based IL methods, followed by influential empirical work on value-based IL. Value-based imitation learning with online MDP access or known dynamics. It is useful to distinguish three closely related access models. First, classical apprenticeship-learning and IRL methods (Abbeel and Ng, 2004; Syed and Schapire, 2007) assumed knowledge of a linear reward class containing the true unknown reward, as well as perfect knowledge of the MDP dynamics. In tabular problems with unknown dynamics, Syed and Schapire (2007) instead estimated the transition kernel only on state-action pairs frequently visited by the expert and sent all other transitions to a pessimistic dead state. They showed that this restricted model suffices to retain a guarantee, at the cost of a slightly worse sample-complexity bound. Also in the tabular setting, Rajaraman et al. (2020) characterize worst-case offline imitation rates with quadratic horizon dependenceH 2 and show that, for deterministic experts, access to the transition model can improve the horizon dependence by at least a √ Hfactor. Rajaraman et al. (2021b) later proved a matching lower bound in that setting. A second line of work assumes reward-free online access to the MDP: the learner may roll out policies in the environment, but it does not observe the reward and typically obtains expert information through precollected demonstrations, expert 23Appendix table of contents occupancies, or expert states or features rather than through value feedback. Xu et al. (2023) removed the known- transition assumption discussed above in tabular adversarial IL and proposed a method achieving the minimax optimal expert-sample complexity by combining expert demonstrations with reward-free environment interaction. Shani et al. (2022) presented an approach based on alternating updates between sequences of rewards and policies. Viano et al. (2022) develop minimax/proximal-point methods for infinite-horizon IL in MDPs with linear, unknown rewards and dynamics under a strong exploratory assumption on the learner’s policies, which was later removed by Viano et al. (2024). Moulin et al. (2025b) further develop optimistic exploration tools for infinite-horizon linear MDPs and apply them to IL. In state- or feature-matching variants, such methods can sometimes use expert states or features rather than expert actions, connecting them to imitation from observation alone (Sun et al., 2019b; Torabi et al., 2018, 2019; Kidambi et al., 2021; Viel et al., 2025). Beyond linear function approximation, Xu et al. (2024) extended the guarantees to the setting in which general function approximation is required to approximate the reward and the dynamics of the environment. Finally, recent work also studies instance-dependent and second-order guarantees (i.e., bounds that scale with the variance of the expert and learner value functions): Wu et al. (2025) give first- and second-order bounds in a score-matching framework, while Li et al. (2026b) prove near-optimal second-order guarantees for model-based adversarial IL. Finally, another related but distinct line gives the learner online reward observations in addition to expert information, making the problem closer to RL with expert advice than to reward-free IL. For example, Tiapkin et al. (2024) studied the setting in which an offline record of state-action pairs collected from an optimal expert can be used to initialize the learner policy in RL. They show that in tabular and linear MDPs, this can achieve better sample complexity than RL without expert data. On the representation side, Amortila et al. (2022) study RL with “one-step” resets, access to an interactive optimal expert, and a class that realizes the optimal state-value function. They provide a computationally efficient algorithm to approximate the optimal policy, showing that expert advice can make otherwise difficult value-realizable settings tractable. This contrasts with planning or RL under value-function realizability alone, where query or computational barriers are known in related settings (Weisz et al., 2021; Liu et al., 2023). These works are complementary to our setting: they exploit reward observations, known dynamics, reward-free environment interaction without learner-state expert action queries, or expert advice for RL, whereasOVIuses only reward-free MDP rollouts together with expert action queries on learner-visited states. Value-based imitation learning with logged expert data. The closest offline counterpart to our setting is Moulin et al. (2025a). Their algorithm,SPOIL, shows that expert-policy realizability can be avoided in offline IL by imposing a closure-type value realizability assumption: the classQmust realizeQ π for every policyπin the implicit policy class Π Q that the algorithm may optimize over or output. This assumption is qualitatively different from, and substantially stronger than, requiring onlyQ π E ∈Q , since it asks the value class to be closed under many learner-generated policies rather than only to contain the expert’s value function. This distinction is important for interpreting our offline lower bound: the lower bound shows thatQ π E -realizability alone is insufficient for offline value-based IL in general, while the offline guarantees of SPOIL rely on additional closure structure that is absent from our main setting. A different logged-data setting was studied by Joshi et al. (2026), who model learning from correct demonstrations as offline IL in a contextual bandit, equivalently an MDP with horizonH = 1. They assume that the correctness, or reward, model belongs to a finite class, rather than assuming expert-policy realizability, and they design statistically efficient algorithms from offline demonstrations alone. Moreover, they improve the algorithm of Syed and Schapire (2007) when instantiated withH = 1, thereby obtaining faster rates when the expert is optimal. BecauseH = 1, there is no sequential distribution shift and no nontrivial transition dynamics to learn or exploit. A recent value-based IL method also investigates how value structure can mitigate compounding errors. Xu et al. (2026) show thatIQ-Learn-style objectives can reduce to behavior cloning and still suffer compounding errors, and they introduce Bellman constraints as a mechanism for propagating value information from demonstrated states to states not covered by the demonstrations. In our setting, a variant of this idea could be used to filter a given realizable classQby removing functions with “temporal” variations greater than one; this is guaranteed to reduce the complexity ofQwhile still providing realizability ofQ π E . In practice, this could be implemented by adding a regularization term to theOVI objective that penalizes large temporal variations. Policy-based imitation learning. Historically, the most common paradigm for tackling IL is to maximize the likelihood of the observed expert actions over a given policy class. In its offline form,BCfits the expert action distribution by supervised learning on expert trajectories, with earlyBC-style systems includingALVINN(Pomerleau, 1988, 1991). 24Appendix table of contents Interactive variants such asDAgger—very popular in practice—and related no-regret reductions instead collect expert labels on states visited by the learner, thereby addressing the covariate shift that appears when an offline cloned policy is deployed on its own trajectory distribution (Ross and Bagnell, 2010; Ross et al., 2011). Theoretical guarantees are typically expressed in terms of the complexity of a policy classΠthat contains the expert policyπ E (see, for example, Rajaraman et al., 2021a; Swamy et al., 2022b). Li and Zhang (2022) study this classification-based online IL viewpoint more generally, including nonrealizable settings. More recently, Foster et al. (2024) refined the classical picture by showing that, under suitable policy realizability and log-loss learnability assumptions, offlineBCcan have much better horizon dependence than suggested by the standard compounding-error analysis. Follow-up work investigates what happens when the expert policy is not exactly realizable by the learner’s policy class. Rohatgi et al. (2025) analyze autoregressive learning and IL under policy misspecification, showing that error amplifica- tion reappears in misspecified settings and that next-token orBC-style objectives face computational-statistical tradeoffs. They also propose robustifiedBCvariants whose guarantees quantify the dependence on horizon and misspecification. Espinosa-Dice et al. (2025) introduceGUITAR, an efficient interactive IL algorithm under misspecification that uses a structural completeness condition and environment access initialized from states sampled from the expert occupancy mea- sure, with guarantees controlled by an advantage-class notion of misspecification rather than by statistical divergences. Most recently, Sriraman et al. (2026) studied a setting in which expert samples may be corrupted: with some probability, the action shown to the learner is drawn from a different policy rather than the expert’s. They show that any offline policy-based IL algorithm suffers exponential sample complexity, whereas their interactive algorithm,NAIL, avoids this exponential blow-up by additionally querying the expert. To conclude our review of the theoretical literature in IL, we report a comparison of our results with the bounds obtained and the representational conditions required by other algorithms in Table 3. B.2 Empirical Value-Based Imitation Learning Although early empirical IL successes include behavior-cloning systems such asALVINN(Pomerleau, 1988, 1991), empirical value-based IL largely grew out of IRL and apprenticeship learning. Early reward-learning methods include maximum-margin planning and maximum-entropy or relative-entropy IRL (Ratliff et al., 2006; Ziebart et al., 2008; Boularias et al., 2011). These methods learn a reward or cost function that explains the expert’s behavior and then derive a policy by planning or policy optimization under the learned objective. Deep variants, such as guided cost learning and maximum-entropy deep IRL, replace linear rewards with neural cost or reward functions (Finn et al., 2016; Wulfmeier et al., 2015). However, these methods typically inherit the “RL-in-the-loop” structure of Ziebart et al. (2008), requiring repeated planning or policy-optimization steps under a changing learned reward, which can be expensive in high-dimensional environments. Other methods replace explicit planning with adversarial or occupancy-matching objectives. Ho et al. (2016) developed model-free apprenticeship-learning methods using policy-gradient optimization, while Ho and Ermon (2016) introduced generative adversarial IL (GAIL), which alternates between training a discriminator/cost signal and updating the policy, using Trust Region Policy Optimization (TRPO; Schulman et al., 2015) in the original implementation.GAILand related adversarial IL methods inspired follow-up work on learned rewards, discriminator-actor-critic methods, off-policy distribution matching, and stationary-distribution correction (Fu et al., 2018; Kostrikov et al., 2019, 2020; Nachum et al., 2019). These methods can be effective, but adversarial IL is often sample-hungry and can be difficult to stabilize because the policy optimizer must continually adapt to a nonstationary learned reward or discriminator. More recent non-adversarial value- and Q-based methods aim to avoid some of this instability. For example,SQIL converts demonstrations into a sparse-reward RL problem (Reddy et al., 2019), while theIQ-Learnmethod of Garg et al. (2021) learns a single softQ-function that implicitly represents both the reward and the policy. Such methods are closely aligned with the broad class of value-based IL algorithms considered in our lower bound: they extract a policy by applying a softmax, greedy, or related activation to a learned value function.IQ-Learnhas been evaluated in simulated robotics tasks (Garg et al., 2021); related Q-learning, IRL, and moment-matching ideas have also been adapted to autoregressive sequence modeling and LM distillation, includingSequenceMatch(Cundy and Ermon, 2024), scalable inverse soft-Q learning for language imitation (Wulfmeier et al., 2024), and adversarial moment-matching distillation (Jia, 2024). Demonstration-based reward-learning and IRL-style approaches have also been applied to LM supervised fine-tuning (SFT) and reasoning without preference labels or verifiers (Li et al., 2024; Cai et al., 2026). We 25Appendix table of contents Table 3: Comparison with related algorithms, assumptions, and expert-interaction requirements. To state the guarantees ofBC, we define a policy classΠsuch thatπ E ∈ Π. Joshi et al. (2026) study finite reward classes and one-step decision problems.N max ε ′ (Q) denotes the largest covering number of the stagewise classesQ h in∥·∥ ∞ with spacingε ′ =O(ε 2 ). We define the classΠ Q : =π :∃m≤ K,∀h,∃Q 1 h ,...,Q m h ∈Q h ,π h (·|x) = softmax(η P m k=1 Q k h (x,·))for some K = poly(d,H,ε −1 ). Q Π Q -realizability is the assumption that Q π ∈Q for any π ∈ Π Q . AlgorithmRepresentational assumptionsComp. efficientInteractive expertExpert traj./queries (n E ) LogLossBC π E -realizability✓✗ O H 2 log|Π| ε 2 (Foster et al., 2024) MWALReward linear in d features ✓✗ e O H 2 log(d) ε 2 (Syed and Schapire, 2007)Known transitions MUWUReward realizability with classR ✗ e O log(|R|) ε 2 (Joshi et al., 2026)Contextual bandits (H = 1) SPOIL Q Π Q -realizability ✓✗ e O H 5 Q 4 max log(AN max ε ′ (Q)) ε 4 (Moulin et al., 2025a) Q-OVI Q π E -realizability✗✓ e O H 3 Q 2 max logN max ε ′ (Q) ε 2 (Ours, Theorem H.1) OVI Q π E -realizability✓ e O H 5 Q 4 max log(AN max ε ′ (Q)) ε 4 ◦ (Ours, Theorem F.1) SPOILQ π E -realizability ✓✗ e O C 4 ∞ H 5 Q 4 max log(AN max ε ′ (Q)) ε 4 ⋄ (Ours, Theorem I.1)Bounded C ∞ , optimal π E Lower Bound Linear Q π E -realizability−✗ Ω |X| ε △ (Ours, Theorem 4.1) ◦ IfQ is convex, the bound improves to e O(H 3 Q 2 max log(N max ε ′ (Q))ε −2 ). ⋄ IfQ is convex, the bound improves to e O(C 2 ∞ H 3 Q 2 max log(N max ε ′ (Q))ε −2 ). △ The lower bound holds even if the expert is deterministic and the learner is allowed to replay the expert actions at the states logged in the dataset. refer to Sun and van der Schaar (2025) for a broader overview of IRL and IL in LM post-training, and to Sikchi et al. (2024) for a unifying perspective on practical dual RL and IL methods. Policy-based imitation learning for language model fine-tuning. Policy-based,DAgger-like on-policy distillation methods have also been applied to LM fine-tuning. Agarwal et al. (2024) train student models on their own generated outputs using teacher feedback, and Lu and Thinking Machines Lab (2025) explicitly frames on-policy distillation as querying or evaluating a teacher on states visited by the student. These methods provide a policy-based analogue of the interactive protocols studied in this paper. Their strong empirical performance motivates the broader use of interaction in distillation, but our results suggest a complementary hypothesis: when the student is much less expressive than the teacher, interactive value-based distillation may be especially useful because it can target value-equivalent behavior rather than the teacher’s full action distribution. The Gym experiments in Figure 1 provide preliminary evidence for this. Testing the same mechanism in LM distillation remains an important empirical direction. 26Appendix table of contents CValue-Based Imitation Learning versus Policy-Based: Motivating Exam- ples In this section, we argue that Q π E -realizability can be weaker than π E -realizability in two important cases. 1. In Appendix C.1, we show that when the expert is optimal, any class Π that realizes the expert policy π E can be preprocessed into a classQ with|Q|≤|Π| that realizes Q π E in a relaxed sense. 2. In Appendix C.2, we give an example where the environment makes the state-action value functions of the constructed expert policies simple, regardless of how complex the policy class is. In particular,Qcan be easier to specify thanΠwhen the expert behavior may depend on uncontrollable exogenous noise, whileQ π E does not: the reward and transition dynamics are unaffected by this noise, whereas the expert’s control policy is. C.1 ConstructingQ fromΠ Reduces Complexity We first show that, given a policy classΠrealizing an optimal expert policyπ E , one can construct a function classQ that realizesQ π E in a relaxed sense. We then show thatOVIguarantees continue to hold under this relaxed realizability condition. These guarantees improve the representational-complexity term over those ofBC,DAgger, and other policy- based methods that aim to match the expert trajectory distribution in total variation: indeed, such methods incur alog|Π| dependence, whileOVIpays a factorlog|Q|, whereQis constructed fromΠand has no larger cardinality, i.e.,|Q|≤|Π|. ConstructingQfrom a policy class that realizes the expert. We preprocessΠby keeping only the action supports induced by its policies. Specifically, for each π ∈ Π, let e Q π = ( e Q π h ) H h=1 with e Q π h : X ×A→ [0,Q max ] be defined by e Q π h (x,a) = Q max 1 a∈supp(π h (·|x)) , for every (h,x,a)∈ [H]×X ×A. We then set Q(Π) = n e Q π : π ∈ Π o . Since infinitely many stochastic policies in Π can share the same support, Π may be infinite even whenQ(Π) is finite under the construction above. ExactQ π E -realizability may fail. When the expert is (pointwise) optimal,π E is greedy with respect toQ π E . The construction also includes the function corresponding to π = π E , e Q π E h (x,a) = Q max 1 a∈supp(π E,h (·|x)) , with respect to whichπ E is greedy. However, this does not imply that e Q π E = Q π E ; in general,Q π E may not belong to Q. The key point is thatOVIonly needs the weaker relationship between e Q π E ,Q π E , and the expert’s action support formalized as relaxedQ π E -realizability in Assumption C.1. The support-indicator witness above satisfies this condition because it assigns Q max to every expert-supported action and zero elsewhere, while Q π E takes values in [0,Q max ]. C.1.1 Guarantees for OVI under relaxed Q π E -realizability In this section, we present guarantees forOVIunder a relaxed notion ofQ π E -realizability. At a high level, the condition asksQto contain a surrogate forQ π E that preserves the action comparisons used byOVI. We show that this condition is sufficient when the expert is statewise optimal, and that expert optimality is necessary. Assumption C.1 (RelaxedQ π E -realizability). We say thatQsatisfies relaxedQ π E -realizability if there exists a sequence of functions e Q π E = ( e Q π E h ) H h=1 ∈Q such that, for every (h,x)∈ [H]×X , supp(π E,h (·|x))⊆ arg max b∈A e Q π E h (x,b), and, for every (h,x,a)∈ [H]×X ×A, a∈ supp(π E,h (·|x)) =⇒ e Q π E h (x,a)≥ Q π E h (x,a), a /∈ supp(π E,h (·|x)) =⇒ e Q π E h (x,a)≤ Q π E h (x,a). 27Appendix table of contents Under the relaxedQ π E -realizability assumption above, we can prove the same decomposition as in Lemma F.1 for the perfectly realizable case, i.e., Q π E ∈Q. Lemma C.1. Let Assumption C.1 hold, and assume that the expert policyπ E is statewise optimal. Let policies π 1 ,...,π K and functions Q k h ∈Q h be computed as in Eq. (19). Define the π-regret at stage h and state x∈X as R π h (x) = K X k=1 Q k h (x,·),π E,h (·|x)− π k h (·|x) , define the output policy as π out = 1 K P K k=1 π k , and, for any policy π, define the estimation error as ∆(π) = max h∈[H] sup Q h ∈Q h b L h (π h ,Q h )−L π out h (π h ,Q h ) . Then, it holds that J π E − J π out ≤ 1 K H X h=1 X x∈X d π out h (x)R π h (x) + 2H K K X k=1 ∆ π k . At this point, one can establish the same complexity guarantee asOVIin the exactly realizable setting by bounding 2H K P K k=1 ∆(π k ) with high probability, as in the proof of Theorem F.1. To conclude the section, we prove Lemma C.1. Proof of Lemma C.1. The proof follows the proof of Lemma F.1, except that we first compareQ π E h with the relaxed witness e Q π E h . For any policy π, we use the shorthandL π h :=L d π h and we claim that, for every h∈ [H], L π out h (π out,h ,Q π E h )≤L π out h π out,h , e Q π E h .(4) To prove this claim, fixh∈ [H]andx∈X, writeA E x,h : = supp(π E,h (·|x)), and setδ x h (a) : = π E,h (a|x)−π out,h (a|x). By definition ofL π out h , L π out h (π out,h ,Q π E h ) = X x∈X d π out h (x) X a∈A δ x h (a)Q π E h (x,a). Fix a statex. Sinceπ E is statewise optimal, every action inA E x,h is greedy with respect toQ π E h (x,·), that is,A E x,h ⊆ arg max b∈A Q π E h (x,b). Thus, by definition of δ x h , X a∈A δ x h (a)Q π E h (x,a) = X a∈A E x,h δ x h (a)Q π E h (x,a) + X a/∈A E x,h δ x h (a)Q π E h (x,a) = max b∈A Q π E h (x,b) 1− X a∈A E x,h π out,h (a|x) − X a/∈A E x,h π out,h (a|x)Q π E h (x,a), where we used thatπ E,h (a|x) = 0fora /∈A E x,h , that P a∈A E x,h π E,h (a|x) = 1, and that all actions inA E x,h maximize Q π E h (x,·). By the relaxed realizability condition (Assumption C.1), we can replace Q π E h with e Q π E h as follows X a∈A δ x h (a)Q π E h (x,a) (a) ≤ max b∈A e Q π E h (x,b) 1− X a∈A E x,h π out,h (a|x) − X a/∈A E x,h π out,h (a|x) e Q π E h (x,a) (b) = X a∈A E x,h δ x h (a) e Q π E h (x,a)− X a/∈A E x,h π out,h (a|x) e Q π E h (x,a) (c) = X a∈A δ x h (a) e Q π E h (x,a). Step (a) uses that on the supportA E x,h , e Q π E h is at leastQ π E h , somax b∈A e Q π E h (x,b) ≥ max b∈A Q π E h (x,b) , that1− P a∈A E x,h π out,h (a|x) = P a/∈A E x,h π out,h (a|x)≥ 0, and that outside the supportA E x,h , e Q π E h (x,a)≤ Q π E h (x,a)holds, so the inequality is reversed when multiplied by−π out,h (a|x). Step (b) usesA E x,h ⊆ arg max b∈A e Q π E h (x,b)and 28Appendix table of contents P a∈A E x,h π E,h (a|x) = 1. Finally, (c) uses the definition ofδ x h and the fact thatδ x h (a) =−π out,h (a|x)fora /∈A E x,h . Averaging the last display over x∼ d π out h gives Eq. (4). Since e Q π E ∈Qand hence e Q π E h ∈Q h for eachh∈ [H], we can now upper bound the suboptimality as in Lemma F.1. By the performance difference lemma (Lemma E.9), and the inequality we just proved (Eq. (4)), we have K(J π E − J π out ) = K H X h=1 L π out h (π out,h ,Q π E h ) ≤ K H X h=1 L π out h π out,h , e Q π E h . Furthermore, by the definitions of the policy π out and the estimation error ∆, we have K(J π E − J π out )≤ H X h=1 K X k=1 L π out h π k h , e Q π E h ≤ H X h=1 K X k=1 b L h π k h , e Q π E h + H K X k=1 ∆ π k ≤ H X h=1 K X k=1 b L h π k h ,Q k h + H K X k=1 ∆ π k ≤ H X h=1 K X k=1 L π out h π k h ,Q k h + 2H K X k=1 ∆ π k . Here, the first and third inequalities use the definition of∆(π k ), respectively with e Q π E h ∈Q h andQ k h ∈Q h . The second inequality uses e Q π E h ∈Q h (Assumption C.1) and the fact thatQ k h is a best response to b L h (π k h ,·)overQ h . Finally, for each h∈ [H], expandingL π out h gives K X k=1 L π out h π k h ,Q k h = X x∈X d π out h (x) K X k=1 Q k h (x,·),π E,h (·|x)− π k h (·|x) = X x∈X d π out h (x)R π h (x). Dividing by K concludes the proof. C.1.2 Expert optimality is necessary for learning under relaxed Q π E -realizability We conclude by showing that expert optimality is necessary. The failure mode for algorithms that output a VI policy under relaxedQ π E -realizability with a suboptimal expert is that the relaxed condition forces the algorithm to treat all actions in the expert support equally. For stochastic suboptimal experts, this can increase the probability of actions rarely played by the expert. Theorem C.1. For any algorithmAlgoutputting a VI policy (see Definition 4.2, even if allowed expert interaction, there exists a2-action MDPMwith a suboptimal expert policy and a classQsatisfying Assumption C.1 such that, even if Alg performs infinitely many expert queries, E π out ∼Alg [J π E M − J π out M ] = Ω(H). Proof of Theorem C.1. Consider a class of environmentsM 1 ,M 2 with action spaceA =a 1 ,a 2 and a single absorbing statex, i.e., both actions fromxtransition back toxwith probability1. Fori ∈ [2], letr(x,a i ) = 1in M i andr(x,a) = 0for the other actiona ̸= a i . InM i , let the expert policyπ E,i satisfyπ E,i (a i |x) = 0.9and π E,i (a|x) = 0.1fora̸= a i . Assumption C.1 is satisfied by the singleton classQ = e Q, where e Q h (x,a) = H for all (h,a) ∈ [H]×A. Indeed, for bothπ E,1 andπ E,2 , the expert support is the full action spaceA. Under the additional value-derived output restriction that the learner can only output a policy obtained by applying a scalar link function to a linear combination of functions inQ, the output policy is uniform over the action space because e Q h assigns the same 29Appendix table of contents value to all actions, regardless of which environment the learner faces. Therefore, max i∈[2] E π out ∼Alg J π E,i M i − J π out M i ≥ 1 2 2 X i=1 E π out ∼Alg J π E,i M i − J π out M i = 0.9H − 0.5H = 0.4H. This concludes the proof. C.2 Q π E -Realizability Can Be Strictly Weaker Thanπ E -Realizability under Exogenous Noise In this section, we give an example in which expert-policy realizability is more demanding thanQ π E -realizability. The example is an exogenous block MDP (ExBMDP), a standard rich-observation model in which the endogenous control problem is low-dimensional, but the observation-based expert policy must decode a high-dimensional observation. A typical example is a robot with high-dimensional camera observations that contain the (small) endogenous state and a background that evolves independently of the robot’s actions (e.g., a television). We formalize the setting below, and the results are stated and proved in subsequent subsections. One limitation of this example is that a single policy that always chooses action0is optimal in every MDP in the family, so the construction concerns exact representational complexity rather than control hardness. We view this as acceptable because the purpose of the construction is to show that exact expert-policy realizability can be much more demanding than Q π E -realizability. The motivation is directly tied to the complexity terms that appear in sample-complexity guarantees. Policy-based methods such asBCandDAggeraim to imitate the expert’s action distribution. Under an expert-policy realizability assumption, their guarantees typically depend on the complexity of a policy classΠsatisfyingπ E ∈ Π, through a term such aslog|Π|(or a log-covering number). In contrast, our value-based guarantees depend on the complexity of a value-function classQ satisfying Q π E ∈Q, through a term such as log|Q|. The construction below shows that these two quantities can be exponentially different. We construct a family of ExBMDPsM b : b∈B n and deterministic, suboptimal expertsπ b : b∈B n indexed by balanced Boolean decoders b : 0, 1 n →0, 1, wherenis the number of bits in the observation space at stage 1. Any expert-agnostic policy class that contains all experts in the family must have exponentially large metric entropy: for every ε∈ (0, 1/2), inf Π:∀b∈B n ,π b ∈Π log 2 N ε (Π,d Π )≥ 2 n − n− 1, whered Π is the sup-total variation metric. By contrast, a two-dimensional classQrealizes the expert action-value function Q π b M b for every b∈B n , and logN ε (Q,∥·∥ ∞ )≤ 2 log(3/ε). Informally, the construction is as follows. We consider an instance where the endogenous state is a single bits∈0, 1, and the expert’s endogenous policy simply plays actiona = samong the actionsA =0, 1, 2. However, the learner does not observesdirectly. Instead, the learner observes a high-dimensional binary stringw ∈0, 1 n , and recovering sfromwrequires computing a decoderb(w). Thus, an observation-based policy that exactly imitates the expert must computeπ E,1 (w) = b(w), and the complexity of a policy class realizing the expert must scale with the complexity of the decoder. On the other hand, theQ-function does not need this decoder. At the first layer, actions0and1are both safe and value-equivalent, while action 2 is unsafe. Hence Q π E only needs to know the value-relevant distinction of0, 1vs.2. The hard decoder determines only the expert’s tie-breaking between the two safe actions, which is what creates this separation. Every expert obtains return1/2, while the policy that always chooses action0obtains the optimal return 1. Thus the separation holds even though every expert is strictly suboptimal. C.2.1 Preliminaries Exogenous block MDPs. A finite-horizon exogenous block MDP (ExBMDP) consists of a tuple H, (S h ) H h=1 , (Ξ h ) H h=1 , (X h ) H h=1 ,A, T endo h H−1 h=0 , (T exo h ) H−1 h=0 , g obs h H h=1 , (r h ) H h=1 , 30Appendix table of contents whereHis the horizon, and at each layerh,S h is the endogenous state space,Ξ h is the exogenous state space,X h is the observation space,Ais the action space,T endo 0 andT exo 0 are initial distributions, forh ∈ [H − 1]the map T endo h : S h ×A→ ∆(S h+1 ) is the endogenous transition kernel andT exo h : Ξ h → ∆(Ξ h+1 ) is the exogenous transition kernel, g obs h : S h × Ξ h →X h is the observation map, and r h : X h ×A→ [0, 1] is the reward function. The initial latent state is generated bys 1 ∼ T endo 0 (·|∅),ξ 1 ∼ T exo 0 (·|∅)independently, with the convention thatS 0 = Ξ 0 =∅. Forh∈ [H − 1], after taking actiona h ∈A, the latent state evolves according tos h+1 ∼ T endo h (·|s h ,a h ) , andξ h+1 ∼ T exo h (·|ξ h ) . Thus only the endogenous state is causally affected by the action; the exogenous state evolves independently of the action. The observation at layerhis generated by a deterministic emission mapx h = g obs h (s h ,ξ h ) ∈ X h . The model is decodable if for anyh, there exists a decoderφ ⋆ h : X h →S h such that for anys∈S h andξ ∈ Ξ h ,φ ⋆ h (g obs h (s,ξ)) = s . Finally, the rewards are endogenous if there exist functions ̄r h : S h ×A→ [0, 1]such thatr h (x,a) = ̄r h (φ ⋆ h (x),a)for all h∈ [H], x∈X h , and a∈A. Because we work in a finite-horizon nonstationary MDP, policies and value functions are also indexed by the layerh. Thus a policy is a sequenceπ = (π h : X h → ∆(A)) H h=1 . In the construction below, we use separate observation spaces X 1 andX 2 . Equivalently, one can combine them into a single disjoint unionX =X 1 ⊔X 2 . Balanced decoders. For the construction below, we will consider the family of balanced Boolean functions as decoders, defined for any n≥ 1 as B n = b : 0, 1 n →0, 1 : b −1 (0) = b −1 (1) = 2 n−1 . The number of balanced Boolean functions is|B n | = 2 n 2 n−1 . By unimodality of the binomial coefficient, and since the largest binomial coefficient is at least the average binomial coefficient, we have 2 n 2 n−1 = max k∈[2 n ] 2 n k ≥ 1 2 n + 1 2 n X k=0 2 n k = 2 2 n 2 n + 1 . Therefore log 2 |B n |≥ 2 n − log 2 (2 n + 1)≥ 2 n − n− 1. C.2.2 The construction Fix an integer n≥ 1 and a decoder b∈B n . Exogenous block MDP. We define an ExBMDPM b with horizonH = 2and action spaceA =0, 1, 2. Actions0 and 1 are safe first-layer actions, while action 2 is unsafe. LetS = S 1 ⊔S 2 be a layered endogenous state space with7states, where the first layer isS 1 = 0, 1and the second layer isS 2 =G∪B, withG =G s,p : s∈0, 1, p∈0, 1. The stateG s,p is a good state reached from first-layer endogenous state s after taking safe action p. The state B is a bad state reached after taking action 2. Let the exogenous state space be time-homogeneous and given byΞ 1 = Ξ 2 =0, 1 n−1 . Sincebis balanced, we have b −1 (0) = b −1 (1) =|Ξ 1 | = 2 n−1 . Therefore, for eachs∈0, 1, we can fix an arbitrary bijectionη b s : Ξ 1 → b −1 (s) that maps an (n− 1)-bit exogenous variable to an n-bit observation string. The observation spaces areX 1 =0, 1 n andX 2 =S 2 × Ξ 2 . The endogenous dynamics are defined as follows. The initial endogenous state is sampled uniformly at random, s 1 ∼ Unif(0, 1), and the transition from layer 1 to layer 2 is deterministic: s 2 = ( G s 1 ,a 1 , a 1 ∈0, 1, B, a 1 = 2. Thus, the first action genuinely affects the endogenous state: actions0and1lead to different good branches, while action 2 leads to the bad state. This specifies a valid deterministic transition kernel fromS 1 ×A toS 2 . 31Appendix table of contents For the exogenous dynamics, the initial exogenous state is sampled independently ofs 1 , also uniformly at random, ξ 1 ∼ Unif(Ξ 1 ), and the exogenous process is persistent, i.e.,ξ 2 = ξ 1 . Equivalently,T exo 1 (ξ ′ |ξ) = Iξ ′ = ξ. The exogenous transition is independent of the action. We define the observation map at stage1for any(s,ξ)∈S 1 × Ξ 1 asg obs 1,b (s,ξ) = η b s (ξ). Hence, conditional ons = 0, the observed string is uniformly distributed overb −1 (0), and conditional ons = 1, it is uniformly distributed over b −1 (1). Sinces 1 andξ 1 are both uniform, every observationw ∈0, 1 n is reachable and equally likely at layer1: if b(w) = s, thenP[x 1 = w] = P[s 1 = s]P[η b s (ξ 1 ) = w] = 1 2 · 2 −(n−1) = 2 −n . We can think of the observation map as hiding the endogenous state within ann-bit observation string via the mappingη b s . The observation map at stage2is transparent: for any (y,ξ)∈S 2 × Ξ 2 , g obs 2,b (y,ξ) = (y,ξ). Define the decoderφ ⋆ b byφ ⋆ 1,b (w) = b(w)for anyw ∈0, 1 n , andφ ⋆ 2,b (y,ξ) = yfor anyy ∈S 2 , ξ ∈ Ξ 2 . Then, for every latent state (s h ,ξ h ), φ ⋆ h,b (g obs h,b (s h ,ξ h )) = s h . Indeed, at layer 1, we have φ ⋆ 1,b g obs 1,b (s,ξ) = φ ⋆ 1,b η b s (ξ) = b η b s (ξ) = s, because η b s (ξ)∈ b −1 (s). At layer 2, the claim follows from the transparent observation map. Finally, we define the reward function. At stage 1, the reward is zero everywhere: for any observationx ∈ X 1 and actiona ∈ A,r 1 (x,a) = 0. At stage2, for any observation(y,ξ) ∈ X 2 anda ∈ A, we definer 2 ((y,ξ),a) = Iy ∈G Ia = 0 + 1 2 Ia = 1 . Thus action0gives reward1and action1gives reward1/2in good second- layer states, while all actions give reward0in the bad stateB. The reward is endogenous: taking ̄r 1 ≡ 0and ̄r 2 (y,a) = Iy ∈G Ia = 0 + 1 2 Ia = 1 givesr h (x,a) = ̄r h (φ ⋆ h,b (x),a)for both layers. Together with the decoder identity above and the action-independent exogenous transition, this defines a valid decodable ExBMDP with endogenous rewards. Expert policy. Define the endogenous expert policy ̄π b : S →A by ̄π b 1 (s) = s, s∈0, 1,and ̄π b 2 (y) = 1, y ∈S 2 . The corresponding observation-based expert policy π b : X →A is π b 1 (w) = b(w), w ∈0, 1 n ,and π b 2 (y,ξ) = 1, y ∈S 2 , ξ ∈ Ξ 2 . Thusπ b is endogenous, since for any layerhand observationx ∈ X h ,π b h (x) = ̄π b h (φ ⋆ h,b (x)). In endogenous coordinates, the expert is simple. In raw observation coordinates, the first-layer expert action is exactly the decoder b. The expert always reaches a good state and then plays action1, soJ π b M b = 1/2. By contrast, the policy that always plays action0reaches a good state and receives reward1, which is the maximum possible return. Hence every expert is strictly suboptimal with suboptimality gap 1/2. C.2.3 A two-dimensional class realizes the expert Q-function Consider the two-parameter time-indexed function classQ =Q α,β : α,β ∈ [0, 1], where, for observationsx∈X 1 , (y,ξ)∈X 2 , and action a∈A, the functions are defined as follows. Q α,β 1 (x,a) = α 2 Ia∈0, 1,and Q α,β 2 ((y,ξ),a) = β Iy ∈G Ia = 0 + 1 2 Ia = 1 . Every function inQis bounded byQ max = 1. Importantly, the classQdoes not depend onb. At layer1, it does not distinguish the stringsw ∈0, 1 n at all; it only distinguishes the safe actions0, 1from the unsafe action2. For any functionQ∈ R X×A , we will use the norm∥Q∥ ∞ = max h∈1,2 max x∈X h max a∈A |Q h (x,a)|. We start by showing that every expert in the family has the same Q-function, which is realizable byQ. Lemma C.2 (Q π b M b -realizability). For every b∈B n , Q π b M b = Q 1,1 ∈Q. Proof of Lemma C.2. At layer 2, there is no future reward. Thus, for every (y,ξ)∈X 2 and a∈A, Q π b M b ,2 ((y,ξ),a) = r 2 ((y,ξ),a) = Iy ∈G Ia = 0 + 1 2 Ia = 1 = Q 1,1 2 ((y,ξ),a). 32Appendix table of contents At layer1, the immediate reward is zero. Fix any observationw ∈ 0, 1 n . Its decoded endogenous state is s = φ ⋆ 1,b (w) = b(w). Ifa∈0, 1, then the next endogenous state isG s,a ∈G. At layer2, the expert plays action1, receiving reward1/2. Thus, fora∈0, 1,Q π b M b ,1 (w,a) = 1/2. Ifa = 2, then the next endogenous state isB. From B, every action receives reward 0, so Q π b M b ,1 (w, 2) = 0. Hence Q π b M b ,1 (w,a) = 1 2 Ia∈0, 1 = Q 1,1 1 (w,a). Combining the two layers gives Q π b M b = Q 1,1 ∈Q. We can then bound the covering number of the classQ with the following lemma. Lemma C.3 (Covering number of the Q-class). For every ε∈ (0, 1],N ε (Q,∥·∥ ∞ )≤ ( 3 ε ) 2 . Proof of Lemma C.3. For any α,β,α ′ ,β ′ ∈ [0, 1], Q α,β − Q α ′ ,β ′ ∞ ≤ max|α− α ′ |,|β− β ′ |. Thus anyε-grid of[0, 1] 2 in theℓ ∞ norm induces anε-cover ofQ. By Lemma E.5, such a grid has cardinality at most ( 1 ε + 1) 2 . For ε∈ (0, 1], 1 ε + 1≤ 3 ε . This proves the claim. C.2.4 Policy realizability requires an exponentially large class We show that any policy classΠthat contains all experts in the family must have an exponentially large covering number under the sup-total-variation metricd Π . In particular, ifΠis finite, then it must have exponentially large cardinality. This shows that a policy realizability assumption is much stronger than a value-function realizability assumption, since the same two-dimensional classQrealizes the expertQ-function for every expert in the family, while any single policy class realizing all experts must have exponential complexity. For any policies π, π ′ , define the sup-total-variation metric d Π (π,π ′ ) = 1 2 max h∈1,2 ∥π h − π ′ h ∥ ∞,1 , where∥·∥ ∞,1 is defined in Eq. (5). For deterministic policies, this distance equals 1 whenever the two policies choose different actions at some layer and observation. Let Π n = π b : b∈B n be the natural expert-agnostic policy class containing all possible experts in the hard-decoder family. We have the following result. Lemma C.4 (Family-level policy lower bound). LetΠ ⊂ ∆(A) X be any policy class. IfΠ n ⊆ Π, then, for every ε∈ (0, 1/2),N ε (Π,d Π )≥|B n |. In particular, log 2 N ε (Π,d Π )≥ 2 n − n− 1. If Π is finite, then also|Π|≥|B n |. Proof of Lemma C.4. Ifb̸= b ′ are two different decoders inB n , then there exists an observationw ∈0, 1 n such thatb(w) ̸= b ′ (w). As a result,π b 1 (w) = b(w) ̸= b ′ (w) = π b ′ 1 (w) . Therefore,π b ̸= π b ′ . Hence the mapb 7→ π b is injective. Any finite policy class containing all expertsπ b : b∈B n must therefore have cardinality at least|B n |. Moreover, ifb̸= b ′ , then the deterministic policiesπ b andπ b ′ choose different actions at some observationwin stage1. Henced Π (π b ,π b ′ ) = 1. Thusπ b : b ∈ B n is a1-packing underd Π . A ball of radiusε < 1/2cannot contain two distinct elements of this packing. Therefore every ε-cover of Π must contain at least|B n | elements. Finally, the lower bound on the log-covering number follows from the lower bound on|B n | shown in Appendix C.2.1. 33Appendix table of contents C.2.5 Separation theorem We now summarize the separation. The result compares the complexity terms that enter policy-based and value-based guarantees. It shows that on the hard-decoder family, (i) any expert-agnostic class satisfying expert-policy realizability uniformly over all decodersbhas exponential metric entropy, while (i) a value-based guarantee underQ π E -realizability depends on the complexity of a two-dimensional class realizing the expert action-value function. Theorem C.2 (Hard-decoder ExBMDP separation). The ExBMDP familyM b : b∈B n defined in Appendix C.2.2 satisfies the following properties. 1.UniformQ π E -realizability. For every balanced decoderb ∈ B n , the expert policyπ b is deterministic and endogenous inM b . It is strictly suboptimal, withJ π b M b = 1/2andsup π J π M b = 1. Moreover, the two- dimensional classQdefined in Appendix C.2.3 realizes every expert action-value function in the family: for every b∈B n , Q π b M b = Q 1,1 ∈Q. In addition, for every ε∈ (0, 1], logN ε (Q,∥·∥ ∞ )≤ 2 log 3 ε . 2.Family-level policy lower bound. LetΠ⊂ ∆(A) X be any expert-agnostic policy class. Ifπ b : b∈B n ⊆ Π , then, for every ε∈ (0, 1/2), log 2 N ε (Π,d Π )≥ 2 n − n− 1. Proof of Theorem C.2. The validity of the ExBMDP construction and the fact that eachπ b is deterministic and endoge- nous follow from Appendix C.2.2. The return gap is also established in that section. The identityQ π b M b = Q 1,1 ∈Qfor everyb∈B n follows from Lemma C.2. The covering-number bound forQfollows from Lemma C.3. The family-level policy lower bound follows from Lemma C.4. Why the policy needs the decoder but theQ-function does not. At layer1, for any observationw, the expert’s action isπ b 1 (w) = b(w) . Thus exact behavioral cloning must recover the decoderb. However, the expertQ-function at the same observation isQ π b M b ,1 (w, 0) = Q π b M b ,1 (w, 1) = 1/2, andQ π b M b ,1 (w, 2) = 0, which is independent ofb(w). The decoder determines which safe action the expert chooses, but both safe actions have the same value. This is why it is easier to represent the expert’s Q-function than to represent the expert’s policy. Here the expert is strictly suboptimal because it chooses action1rather than action0at the second layer. This does not affect the tie-breaking mechanism at the first layer: actions0and1have the same expertQ-value, and recovering the exact expert policy still requires the decoder-dependent rulew 7→ b(w). Thus a simpleQ-function can correspond to an enormous set of expert policies even when those experts are suboptimal. Making the expert’s first-layer action uniquely optimal in this construction would forceQ π b to encode the decoder, eliminating the present decoder-independent witness class. Why the exogenous structure matters. If the endogenous stateswere observed directly, the expert would be the constant-complexity policy ̄π b 1 (s) = s and ̄π b 2 (y) = 1 on an endogenous state space of size7. The controlled dynamics and rewards are also simple in endogenous coordinates. The complexity appears only because the observation map hides the endogenous bit inside exogenous variation, w = η b s (ξ)∈0, 1 n . Recovering the endogenous bit from the raw observation requires computings = b(w). Thus the observation-based expert policy factors asπ b 1 (w) = ̄π b 1 (φ ⋆ 1,b (w)) = b(w) . Expert-policy realizability therefore requires representing the hard decoder. By contrast,Q π b is identical across decoders. This is why the same two-dimensional Q-class works uniformly for all decodersb, whereas any policy class that realizes all corresponding experts must be exponentially large. 34Appendix table of contents D Experiment Details This section includes additional experimental results and details on the experiments presented in the main text. To start with, we include some experiments in the instance we use for our lower bound to showcase the failure of offline value-based IL underQ π E -realizability and no additional assumptions. As a representative offline algorithm that outputs a VI policy, we useSPOIL(Moulin et al., 2025a). These results are described in Appendix D.1. Next, in Appendix D.2 we provide additional details and comments about the Gymnasium experiments. D.1 Experiments on the Lower Bound Instance 020406080100 Number of expert queriesτ E 0.0 0.1 0.2 Suboptimality OVI(Ours) SPOIL Offline IL lower bound (0.25) Figure 3: Experiment on the environment class used to prove Theorem 4.2. We start by investigating the performance of an offline VI-policies-based algorithm, such asSPOIL. Our negative result in Theorem 4.2 predicts a constant suboptimality in at least one environment. To observe this prediction in practice, we repeat the experiment500times, each time letting the adversary choose uniformly between the two environmentsM 1 andM 2 in the hard family used in the proof of Theorem 4.2. We report their average suboptimality in Figure 3, which is a lower bound on the worst-case suboptimality. Indeed, at least one ofM 1 and M 2 has suboptimality no smaller than the average. As Figure 3 shows,OVIreaches zero suboptimality, whereas SPOILremains at the constant suboptimality predicted by our construction. D.2Implementation with Neural Networks For the Gymnasium experiments, we consider a stationary approximation of Algorithm 1. At the beginning of each epoch, we label one trajectory collected with the learner policy output by the previous epoch,π ℓ , rather than fromd π out h as our theory for finite horizon would prescribe. We label such trajectories with expert actions. At this point, we compute the empirical approximation of the objective used byOVI and compute an approximate saddle point byKiterations of the online learning algorithms. The resulting pseudocode is given in Algorithm 2. For the experiments, we setK = 50while we vary the maximum number of queries along the learner trajectories as shown in Figure 4. The exponential weights update for the policy is approximated viaSoft DQN (Haarnoja et al., 2017) as in Moulin et al. (2025a). Moreover, we have observed thatOVI’s performance improves when the state dataset is formed by aggregating both expert and learner trajectories. Such data mixing is common in on-policy distillation (Agarwal et al., 2024) and we prove that it extends the representational benefits of interaction; see Appendix J. In the easiest environments likeCartPole-v1andAcrobot-v1, we find that 10 trajectories collected offline (forSPOIL andBC) or online and then labeled by the expert (forOVIandDAgger) usually suffice to match the expert performance. In Figure 4, in more complicated environments such asLunarLander-v2andPendulum-v1, we increased the number of expert samples, but we did not find it necessary to increase the value of K. As baselines, we useDAgger(Ross et al., 2011), an interactive method requiring policy realizability. We also use standardBC(Pomerleau, 1991), an offline method requiring expert-policy realizability, andSPOIL(Moulin et al., 2025a), an offline method that does not require interactive expert access but assumes the strongerQ Π Q -realizability condition, namely, Q π ∈Q for every π ∈ Π Q . D.3 Additional Details and Comments on the Gym Experiments We ran the above algorithms in some Gymnasium environments and report the results next. In particular, we first trained an expert network with 2 hidden layers with 64 neurons each viaDQN(Mnih et al., 2015) inPendulum-v1andPPO (Schulman et al., 2017) inCartPole-v1andAcrobot-v1and then considered the following two settings. First, we considered a learner parameterized via exactly the same architecture (2 hidden layers with 64 neurons). In this case, expert realizability clearly holds. Therefore,BCandDAggerare expected to work well. Second, we considered smaller 35Appendix table of contents 1235710 0 0.5 1 π E ∈ Π , Learner width = 64 Acrobot-v1 1235710 CartPole-v1 13571015 Pendulum-v1 2351015 LunarLander-v2 1235710 0 0.5 1 Learner width = 16 1235710135710152351015 1235710 0 0.5 1 Learner width = 8 1235710135710152351015 1235710 0 0.5 1 Learner width = 4 1235710135710152351015 1235710 0 0.5 1 Learner width = 2 1235710135710152351015 Normalized return Number of trajectories OVI (Ours) (online, value-based) SPOIL (offline, value-based) DAgger (online, policy-based) BC (offline, policy-based) Figure 4: Experiments in theGymnasiumlibrary. The top row reports the setting in which the expert and learner have the same network architecture. In the second and subsequent rows, the learner’s network width decreases, taking the values16, 8, 4, 2neurons. Thex-axis reports the number of expert trajectories for offline methods (BCandSPOIL) and the number of learner trajectories labeled with expert actions for DAgger and OVI. 36Appendix table of contents Algorithm 2 Stationary approximation of OVI for neural networks. 1: Initialize policy weights ψ K 0 and value network weights θ K 0 . 2: for ℓ = 1,...,n E do 3:Collect a state trajectory (x h,ℓ ) H h=1 with the policy π ψ K ℓ−1 . 4:Label the states with expert actions a E h,ℓ ∼ π E,h (·|x h,ℓ ) for each h∈ [H]. 5: # Warm-start initialization of policy and Q network parameters. 6: θ 1 ℓ = θ K ℓ−1 , ψ 1 ℓ = ψ K ℓ−1 7:for k = 1,...,K− 1 do 8: # Update the policy weights. 9:Update ψ k ℓ via SoftDQN (Haarnoja et al., 2017) using Q θ k ℓ as the Q-network. 10: # The argmax is approximated with several Adam iterations initialized at θ k ℓ . 11: θ k+1 ℓ ≊ arg max θ∈R d P ℓ s=1 P H h=1 Q θ (x h,s ,a E h,s )− Q θ (x h,s ,π ψ k ℓ ) . 12: Output the policy π ψ K n E . learner networks (2 hidden layers with 16, 8, 4, or 2 neurons per layer). Expert realizability is a poorly motivated assumption in this second case, and we therefore expected methods likeSPOILandOVIto be more efficient as the expert–learner size gap increases. The aforementioned hypotheses are indeed confirmed by our experiments inCartPole-v1andAcrobot-v1. When expert realizability holds (top row of Figure 4), we see that all four methods are essentially equivalent and all eventually manage to match the performance of the expert policy. By contrast, when the learner network becomes smaller, we see that the methods that avoid the expert-realizability assumption achieve better performance. Moreover, the benefits of interaction become evident for the largest size gap we tested (in the last row of Figure 4) in whichOVI outperformsSPOIL. This suggests, therefore, that the network parametrization considered here is not powerful enough to represent theQ-functions of the policy sequence generated by the algorithm. An interesting additional observation is that inCartPole-v1andAcrobot-v1, value-based methods clearly outperform policy-based ones. In contrast, in Pendulum-v1andLunarLander-v2, the interactive methods, i.e.,OVIandDAgger, are the best ones. Therefore, for some environments it seems that interaction is key for performance, while in others value-based representation is more important. We think that such instance-dependent phenomena raise interesting open questions. ThePendulum-v1environment naturally comes with continuous actions, but we adapted it to our setting via action discretization, a technique used in practice (Dadashi et al., 2022) and recently analyzed by Cao and Xie (2026). Notably, in this case, we notice thatOVIoutperforms the standardSPOIL, potentially becauseOVIimposes a weaker requirement on the representational power of theQ-class. The experts achieved the following average returns:500inCartPole-v1, −77.1inAcrobot-v1,270inLunarLander-v2and−176.6inPendulum-v1. The zero point on they-axis is set to the following returns achieved by very suboptimal policies:−500inAcrobot-v1,8inCartPole-v1,−1650.0in Pendulum-v1and−600inLunarLander-v2. For each environment, we ran each IL algorithm50times with different random seeds from0to49. As is common practice in Gymnasium environments (Garg et al., 2021), we subsampled the expert trajectories for offline methods and retained expert-action labels along learner trajectories only at a fixed frequency for interactive methods. For sample accounting, each retained label counts as one expert sample for offline methods and one expert query for interactive methods. Thus, a trajectory of lengthTcontributes⌈T/f⌉samples or queries at subsampling frequency f . For all algorithms, we tuned their hyperparameters to optimize the performance with no expert–learner gap and then kept the same hyperparameters for the experiments with smaller learner network sizes. The detailed list of hyperparameters is in theREADMEfile accompanying our code. ForSPOILandOVI, we approximate the policy update viaSoft DQNlearning over theQ-values, not from rewards, but with the loss motivated by our theoretical analysis. The experiments can be run on CPUs. We ran them on a personal laptop. Note, however, that running all the experiments can take several hours. 37Appendix table of contents E Technical Tools E.1 Concentration Lemma E.1 (Azuma–Hoeffding inequality; Boucheron et al., 2013, Section 1.1). LetX 1 ,...,X n be a martingale difference sequence with respect to a filtration(F i ) n i=1 , i.e.,E[X i |F i−1 ] = 0and|X i | ≤ Malmost surely for all i∈ [n]. Then, for any t > 0, P " 1 n n X i=1 X i > t # ≤ 2e − nt 2 2M 2 . Equivalently, for any δ ∈ (0, 1), with probability at least 1− δ, 1 n n X i=1 X i ≤ M r 2 log(2/δ) n . We recap the definition of covering numbers. Definition E.1 (Covering number). Let(M, d)be a metric space,Sbe a subset ofM, andε > 0. A setC ε (S, d)is an ε-covering ofSif for anyx∈ S, there existsy ∈C ε (S, d)such thatd(x,y)≤ ε. The covering number ofS,N ε (S, d), is the minimum cardinality of any such covering of S. Moreover, we denoteC ε (S) : =C ε (S,∥·∥ ∞ ). We state the finite-horizon concentration lemma that will be used for the uniform covering argument. For decision rules p,p ′ : X → ∆(A), define the policy metric ∥p− p ′ ∥ ∞,1 : = max x∈X X a∈A |p(a|x)− p ′ (a|x)|.(5) Given two functionsQ,Q ′ ∈ f : X ×A → [0,Q max ], and two decision rulesp,p ′ ∈ ∆(A) X , define the scaled product metric ρ((Q,p), (Q ′ ,p ′ )) : =∥Q− Q ′ ∥ ∞ + Q max ∥p− p ′ ∥ ∞,1 .(6) Lemma E.2 (Finite-horizon uniform concentration; analogue of Moulin et al., 2025a, Lemma 5). Fix nonempty deterministic classesΠ h ⊆ ∆(A) X andQ h ⊆ Q h : X ×A → [0,Q max ]for everyh ∈ [H]. For eachh, letF h−1 denote the history available before the samples for stagehare drawn. Letd h ∈ ∆(X )beF h−1 -measurable, and suppose that, conditionally onF h−1 , x i h ∼ d h , a i E,h ∼ π E,h · x i h , i∈ [n E ], are independent. For any p∈ Π h and Q h ∈Q h , define L d h (p,Q h ) : = X x∈X d h (x)⟨Q h (x,·),π E,h (·|x)− p(·|x)⟩, b L d h (p,Q h ) : = 1 n E n E X i=1 Q h x i h ,a i E,h − Q h x i h ,p . Then, for any r > 0 and δ ∈ (0, 1), with probability at least 1− δ, max h∈[H] sup p∈Π h sup Q h ∈Q h b L d h (p,Q h )−L d h (p,Q h ) ≤ 4r + Q max v u u t 8 log 2 P H h=1 N r (Q h × Π h ,ρ)/δ n E .(7) If P H h=1 N r (Q h × Π h ,ρ) =∞, the bound is interpreted as vacuous. Proof of Lemma E.2. The result is vacuous when the total covering number is infinite. Thus, assume that H X h=1 N r (Q h × Π h ,ρ) <∞. 38Appendix table of contents Fix h and condition onF h−1 . For a fixed pair (Q h ,p)∈Q h × Π h , define Z i (Q h ,p) = Q h x i h ,a i E,h − Q h x i h ,p −L d h (p,Q h ). Then(Z i (Q h ,p)) n E i=1 is a conditionally independent mean-zero sequence and|Z i (Q h ,p)|≤ 2Q max almost surely. By the Azuma–Hoeffding inequality (Lemma E.1), for every t > 0, P h b L d h (p,Q h )−L d h (p,Q h ) ≥ t F h−1 i ≤ 2 exp − n E t 2 8Q 2 max .(8) For eachh, choose a finite setC h,r ⊆Q h × Π h with cardinalityN r (Q h × Π h ,ρ)such that every pair inQ h × Π h lies within distancerof some element ofC h,r underρ. Applying Eq. (8) to all elements of these finite sets, then taking expectations and a union bound overh∈ [H], gives an event of probability at least1− δon which, for allhand all ( e Q h ,ep)∈C h,r , b L d h ep, e Q h −L d h ep, e Q h ≤ Q max v u u t 8 log 2 P H h=1 N r (Q h × Π h ,ρ)/δ n E .(9) We work on this event and pass from the cover to the full class. Fixh,Q h ∈Q h , andp∈ Π h , and choose( e Q h ,ep)∈C h,r such that Q h − e Q h ∞ + Q max ∥p− ep∥ ∞,1 ≤ r. By the triangle inequality, b L d h (p,Q h )− b L d h ep, e Q h ≤ 1 n E n E X i=1 Q h x i h ,a i E,h − e Q h x i h ,a i E,h + 1 n E n E X i=1 Q h x i h ,p − e Q h x i h ,ep . For every state x, Q h (x,p)− e Q h (x,ep) ≤ Q h (x,p)− e Q h (x,p) + e Q h (x,p)− e Q h (x,ep) ≤ Q h − e Q h ∞ + Q max ∥p− ep∥ ∞,1 . Therefore, b L d h (p,Q h )− b L d h ep, e Q h ≤ 2 Q h − e Q h ∞ + Q max ∥p− ep∥ ∞,1 ≤ 2r.(10) The same deterministic calculation, with empirical averages replaced by expectation underx∼ d h anda∼ π E,h (·|x), gives L d h (p,Q h )−L d h ep, e Q h ≤ 2r.(11) Combining Eqs. (9) to (11) yields Eq. (7). Since h, p, and Q h were arbitrary, the proof is complete. For later use, we also record the covering bounds for the decision-rule classes induced by exponentiated-gradient updates. For function classesQ h ⊆Q h : X ×A→ [0,Q max ], an integer K ≥ 0, and η > 0, define Π Q : = n π :∃m∈0,...,K,∀h,∃Q 1 h ,...,Q m h ∈Q h , π h (a|x) = softmax η P j Q j h (x,·) a o . For eachh, letΠ Q,h : =π h : π ∈ Π Q . Whenm = 0, the empty sum is the zero vector, so the corresponding decision rule is uniform. Lemma E.3 (Nonconvex product covering; analogue of Moulin et al., 2025a, Lemma 7). For everyh∈ [H]and every ε > 0, N ε Π Q,h ,∥·∥ ∞,1 ≤ 1 + K X m=1 N ε/(ηm) (Q h ,∥·∥ ∞ ) m .(12) 39Appendix table of contents Consequently, for the scaled product metric ρ in Eq. (6), for every r > 0, N r (Q h × Π Q,h ,ρ)≤ inf α∈(0,r) N α (Q h ,∥·∥ ∞ ) 1 + K X m=1 N (r−α)/(Q max ηm) (Q h ,∥·∥ ∞ ) m ! .(13) In particular, the simpler bound N r (Q h × Π Q,h ,ρ)≤ (K + 1)N r 2 max1,Q max ηK (Q h ,∥·∥ ∞ ) K+1 (14) also holds. Proof of Lemma E.3. Fixhandm ∈ 0,...,K. Ifm = 0, the only decision rule represented withmfunctions is the uniform decision rule. Suppose now thatm≥ 1, and letC s be ans-covering ofQ h under∥·∥ ∞ . Consider any p∈ Π Q,h represented with this value ofmbyQ 1 h ,...,Q m h ∈Q h , and choose e Q j h ∈C s such that∥Q j h − e Q j h ∥ ∞ ≤ s for all j ∈ [m]. Define ep(·|x) = softmax η m X j=1 e Q j h (x,·) . By 1-Lipschitz continuity of the softmax (Lemma E.8) and the triangle inequality, for every x∈X , ∥p(·|x)− ep(·|x)∥ 1 ≤ η m X j=1 Q j h − e Q j h ∞ ≤ ηms, where we used the definitions of e Q 1 h ,..., e Q m h in the last inequality. Takings = ε/(ηm)gives aε-covering for the decision rules represented with this value ofm, of cardinality at mostN ε/(ηm) (Q h ,∥·∥ ∞ ) m . Taking the union over m = 0,...,K proves Eq. (12). For the product bound, fixα∈ (0,r). Take anα-covering ofQ h under∥·∥ ∞ and an(r− α)/Q max -covering ofΠ Q,h under∥·∥ ∞,1 . By definition ofρ, their Cartesian product is anr-covering ofQ h × Π Q,h underρ. Applying Eq. (12) with ε = (r− α)/Q max , and then taking the infimum over α, gives Eq. (13). To obtain Eq. (14), takeα = r/2in Eq. (13). IfK = 0, the claim follows immediately. Suppose then thatK ≥ 1. The radiusr/(2 max1,Q max ηK)is at mostr/2and at mostr/(2Q max ηm)for every1≤ m≤ K. Thus, by monotonicity of covering numbers, N r/2 (Q h ,∥·∥ ∞ )≤N r 2 max1,Q max ηK (Q h ,∥·∥ ∞ ), N r 2Q max ηm (Q h ,∥·∥ ∞ ) m ≤N r 2 max1,Q max ηK (Q h ,∥·∥ ∞ ) K . Since covering numbers of nonempty classes are at least one, Eq. (14) follows. Lemma E.4 (Convex product covering; analogue of Moulin et al., 2025a, Lemma 8). Assume that eachQ h is convex. Then, for every h∈ [H] and every ε > 0, N ε Π Q,h ,∥·∥ ∞,1 ≤ 1 + K X m=1 N ε/(ηm) (Q h ,∥·∥ ∞ ).(15) Consequently, for the scaled product metric ρ in Eq. (6), for every r > 0, N r (Q h × Π Q,h ,ρ)≤ inf α∈(0,r) N α (Q h ,∥·∥ ∞ ) 1 + K X m=1 N (r−α)/(Q max ηm) (Q h ,∥·∥ ∞ ) ! .(16) In particular, the simpler bound N r (Q h × Π Q,h ,ρ)≤ (K + 1)N r 2 max1,Q max ηK (Q h ,∥·∥ ∞ ) 2 (17) also holds. 40Appendix table of contents Proof of Lemma E.4. Fixhandm∈0,...,K. The casem = 0again gives the uniform decision rule. Suppose that m≥ 1, and let p∈ Π Q,h be represented with this value of m by Q 1 h ,...,Q m h ∈Q h . Define Q h = 1 m m X j=1 Q j h . By convexity,Q h ∈Q h , andp(·|x) = softmax(ηmQ h (x,·))for everyx∈X. LetC s be ans-covering ofQ h under ∥·∥ ∞ , choose e Q h ∈C s such that∥Q h − e Q h ∥ ∞ ≤ s, and define ep(·|x) = softmax ηm e Q h (x,·) . By 1-Lipschitz continuity of the softmax (Lemma E.8) and the definition of e Q h , for every x∈X , ∥p(·|x)− ep(·|x)∥ 1 ≤ ηm Q h − e Q h ∞ ≤ ηms. Takings = ε/(ηm)gives aε-covering for the decision rules represented with this value ofm, of cardinality at most N ε/(ηm) (Q h ,∥·∥ ∞ ). Taking the union overm = 0,...,Kproves Eq. (15). The product bound follows from the same Cartesian-product argument used in the proof of Lemma E.3. To obtain Eq. (17), takeα = r/2in Eq. (16). IfK = 0, the claim follows immediately. Suppose then thatK ≥ 1. The radiusr/(2 max1,Q max ηK)is at mostr/2and at mostr/(2Q max ηm)for every1≤ m≤ K. Thus, by monotonicity of covering numbers, N r/2 (Q h ,∥·∥ ∞ )≤N r 2 max1,Q max ηK (Q h ,∥·∥ ∞ ), N r 2Q max ηm (Q h ,∥·∥ ∞ )≤N r 2 max1,Q max ηK (Q h ,∥·∥ ∞ ). Since covering numbers of nonempty classes are at least one, Eq. (17) follows. We also recall the following standard bound. Lemma E.5 (Covering number of anℓ ∞ ball; Vershynin, 2018, Section 4.2). Letd∈ N,R > 0, and letB d ∞ (R) denote the ℓ ∞ ball of radius R in R d . Then, for every ε > 0, N ε B d ∞ (R),∥·∥ ∞ ≤ 2R ε + 1 d . E.2 Optimization We will need the following regret bounds for mirror descent and follow-the-regularized-leader (FTRL), which are standard in the literature. We report them here for completeness. Lemma E.6 (Simplified version of Orabona, 2026, Theorem 6.11). Let us consider a non-empty closed convex setV, an arbitrary sequence of adaptively chosen loss vectors(ℓ k ) K k=1 such that∥ℓ k ∥ ∞ ≤ ℓ max , and letD : V × int(V )→ R be a Bregman divergence induced by aλ-strongly convex function in theℓ 1 norm. Then, for allu∈ V, the sequence (x k ) K k=1 generated for each k by x k+1 = arg min v∈V ⟨ℓ k ,v⟩ + 1 η D(v,x k ) for an initial x 1 ∈ int(V ) and under the assumption that x k ∈ int(V ) for every k ∈ [K + 1] satisfies K X k=1 ⟨ℓ k ,x k − u⟩≤ D(u,x 1 ) η + ηKℓ 2 max 2λ . Lemma E.7 (FTRL over the simplex). Let∆(A)be the simplex over a discrete action spaceA, and for anyx∈ ∆(A), define the Shannon entropy asH(x) =− P a∈A x(a) logx(a). Consider the sequence(x k ) K k=1 generated via FTRL using the potential ψ k (x) = −H(x)− min x ′ ∈∆(A) (−H(x ′ )) η k . 41Appendix table of contents That is, for a certain sequence of cost vectors ℓ 1 ,...,ℓ K we have x k = arg min x∈∆(A) * x, k−1 X k ′ =1 ℓ k ′ + + ψ k (x) = e −η k P k−1 k ′ =1 ℓ k ′ P a∈A e −η k P k−1 k ′ =1 ℓ k ′ (a) . Then, if∥ℓ k ∥ ∞ ≤ ℓ max and η k = q log(A) ℓ 2 max k , it holds that for any K ∈ N and any x ⋆ ∈ ∆(A), K X k=1 ⟨ℓ k ,x k − x ⋆ ⟩≤ 3 p ℓ 2 max log|A|K. Proof of Lemma E.7. Let us define the function F k (x) = P k−1 k ′ =1 ⟨ℓ k ′ ,x⟩ + ψ k (x). Then, by definition, we have − K X k=1 ⟨ℓ k ,x ⋆ ⟩ = ψ K+1 (x ⋆ )− F K+1 (x ⋆ ). Adding and subtractingF K+1 (x K+1 )andF 1 (x 1 )and noticing thatx 1 minimizesF 1 = ψ 1 over the simplex, we obtain − K X k=1 ⟨ℓ k ,x ⋆ ⟩ = ψ K+1 (x ⋆ )− F K+1 (x ⋆ )− F K+1 (x K+1 ) + F K+1 (x K+1 )− min x∈∆(A) ψ 1 (x) + F 1 (x 1 ). Now, writing the difference F 1 (x 1 )− F K+1 (x K+1 ) as a telescoping sum, we have − K X k=1 ⟨ℓ k ,x ⋆ ⟩ = ψ K+1 (x ⋆ )− F K+1 (x ⋆ ) + K X k=1 (F k (x k )− F k+1 (x k+1 )) + F K+1 (x K+1 )− min x∈∆(A) ψ 1 (x), Finally, adding P K k=1 ⟨ℓ k ,x k ⟩ to both sides, we obtain K X k=1 ⟨ℓ k ,x k − x ⋆ ⟩ = ψ K+1 (x ⋆ )− F K+1 (x ⋆ ) + K X k=1 (F k (x k )− F k+1 (x k+1 ) +⟨ℓ k ,x k ⟩) + F K+1 (x K+1 )− min x∈∆(A) ψ 1 (x). Using that ψ k (x)≥ 0 for all k and x∈ ∆(A), and F K+1 (x ⋆ )≥ F K+1 (x K+1 ) (by definition of x K+1 ), we obtain K X k=1 ⟨ℓ k ,x k − x ⋆ ⟩≤ ψ K+1 (x ⋆ ) + K X k=1 (F k (x k )− F k+1 (x k+1 ) +⟨ℓ k ,x k ⟩). At this point, note F k (x k )− F k+1 (x k+1 ) +⟨ℓ k ,x k ⟩ (a) = F k (x k ) +⟨ℓ k ,x k ⟩− (F k+1 (x k+1 ) +⟨ℓ k ,x k+1 ⟩) +⟨ℓ k ,x k+1 ⟩ (b) = F k (x k ) +⟨ℓ k ,x k ⟩− (F k (x k+1 ) +⟨ℓ k ,x k+1 ⟩) +⟨ℓ k ,x k+1 ⟩ + F k (x k+1 )− F k+1 (x k+1 ) (c) = F k (x k ) +⟨ℓ k ,x k ⟩− (F k (x k+1 ) +⟨ℓ k ,x k+1 ⟩) + F k+1 (x k+1 )− ψ k+1 (x k+1 ) + ψ k (x k+1 )− F k+1 (x k+1 ) (d) = F k (x k ) +⟨ℓ k ,x k ⟩− (F k (x k+1 ) +⟨ℓ k ,x k+1 ⟩)− ψ k+1 (x k+1 ) + ψ k (x k+1 ), where we (a) added and removed a term⟨ℓ k ,x k+1 ⟩, (b) added and removed a termF k (x k+1 ), (c) used the fact that ⟨ℓ k ,x k+1 ⟩ + F k (x k+1 ) = F k+1 (x k+1 )− ψ k+1 (x k+1 ) + ψ k (x k+1 ) by definition of F k , and (d) rearranged terms. 42Appendix table of contents For anyx∈ R A , we defineι ∆(A) (x) = 0ifx∈ ∆(A)andι ∆(A) (x) =∞otherwise. Then, since bothx k+1 andx k are in ∆(A), it holds that F k (x k )− F k+1 (x k+1 ) +⟨ℓ k ,x k ⟩ = F k (x k ) +⟨ℓ k ,x k ⟩ + ι ∆(A) (x k )− F k (x k+1 ) +⟨ℓ k ,x k+1 ⟩ + ι ∆(A) (x k+1 ) − ψ k+1 (x k+1 ) + ψ k (x k+1 ). Since ψ k is η −1 k -strongly convex, the function F k +⟨ℓ k ,·⟩ + ι ∆(A) is also η −1 k -strongly convex. Hence, writing ∂ for the subdifferential, for any subgradient g k ∈ℓ k + ∂(F k + ι ∆(A) )(x k ), we have F k (x k ) +⟨ℓ k ,x k ⟩ + ι ∆(A) (x k )− F k (x k+1 ) +⟨ℓ k ,x k+1 ⟩ + ι ∆(A) (x k+1 ) ≤−⟨g k ,x k+1 − x k ⟩− 1 2η k ∥x k − x k+1 ∥ 2 1 . Sincex k = arg min x∈∆(A) (F k +ι ∆(A) )(x), we obtain that0∈ ∂(F k +ι ∆(A) )(x k ), which implies that we can choose g k = ℓ k . Plugging this back into the previous display, we obtain that F k (x k )− F k+1 (x k+1 ) +⟨ℓ k ,x k ⟩ ≤⟨ℓ k ,x k − x k+1 ⟩− 1 2η k ∥x k − x k+1 ∥ 2 1 − ψ k+1 (x k+1 ) + ψ k (x k+1 ) (a) ≤ ∥ℓ k ∥ ∞ ∥x k − x k+1 ∥ 1 − 1 2η k ∥x k − x k+1 ∥ 2 1 − ψ k+1 (x k+1 ) + ψ k (x k+1 ) (b) ≤ η k 2 ∥ℓ k ∥ 2 ∞ − ψ k+1 (x k+1 ) + ψ k (x k+1 ) (c) ≤ η k ∥ℓ k ∥ 2 ∞ , where we also used (a) Hölder’s inequality, (b) Young’s inequality, and (c) the fact that the potential is nondecreasing. Therefore, the regret bound becomes K X k=1 ⟨ℓ k ,x k − x ⋆ ⟩≤ ψ K+1 (x ⋆ ) + K X k=1 η k ∥ℓ k ∥ 2 ∞ . By definition of the potential ψ K+1 and the facts that−H(x)≤ 0 and H(x)≤ log(A) for all x∈ ∆(A), we obtain ψ K+1 (x) = −H(x)− min x∈∆(A) (−H(x)) η K+1 ≤ max x∈∆(A) H(x) η K+1 ≤ log(A) η K+1 . Therefore, we obtain K X k=1 ⟨ℓ k ,x k − x ⋆ ⟩≤ log(A) η K+1 + K X k=1 η k ∥ℓ k ∥ 2 ∞ . Then, choosing η k = q log(A) ℓ 2 max k and using the fact that∥ℓ k ∥ 2 ∞ ≤ ℓ 2 max , we obtain that K X k=1 ⟨ℓ k ,x k − x ⋆ ⟩≤ p ℓ 2 max log(A)(K + 1) + K X k=1 r ℓ 2 max log(A) k ≤ 3 p ℓ 2 max log(A)K. Here, the last inequality follows by factoring out p ℓ 2 max log(A) and using P K k=1 1 √ k ≤ 1 + R K 1 1 √ x dx = 2 √ K− 1, and √ K + 1≤ √ K + 1. This concludes the proof. Lemma E.8 (Softmax Lipschitzness). For any finite action setA and any u,v ∈ R A , ∥softmax(u)− softmax(v)∥ 1 ≤∥u− v∥ ∞ . 43Appendix table of contents Proof of Lemma E.8. Since the gradient of the log-sum-exp function is the softmax function, the desired inequality is exactly the1-smoothness of log-sum-exp with respect to theℓ ∞ norm, whose dual norm isℓ 1 . By Orabona (2026, Theorem 6.26), this smoothness follows from the1-strong convexity of the convex conjugate of log-sum-exp with respect to the dualℓ 1 norm. This conjugate is the negative entropy on the simplex, and its1-strong convexity in theℓ 1 norm follows from Orabona (2026, Lemma 6.33). E.3 Performance Difference Lemma We use the following version of the performance difference lemma (Howard, 1960; Kakade and Langford, 2002): it ex- presses the performance gap between two policies as a sum of advantages of one policy under the occupancy of the other. Lemma E.9 (Performance difference lemma). Let π and π ′ be arbitrary policies. Then, J π ′ − J π = H X h=1 X x∈X d π h (x) X a∈A (π ′ h (a|x)− π h (a|x))Q π ′ h (x,a).(18) Proof of Lemma E.9. By considering the Bellman equations for the policyπ ′ , for any state-action pair(x,a)and any h∈ [H] we have that Q π ′ h (x,a) = r h (x,a) + X x ′ ∈X P h (x ′ |x,a)V π ′ h+1 (x ′ ). Then, taking the expectation with respect to the state-action occupancy measure of the policy π, we have X x,a d π h (x,a)Q π ′ h (x,a) = X x,a d π h (x,a)r h (x,a) + X x,a d π h (x,a) X x ′ P h (x ′ |x,a)V π ′ h+1 (x ′ ). Then, by swapping the sums and using the flow conditions satisfied by the occupancy measure ofπ, i.e.,d π h+1 (x) = P x ′ ,a ′ P h (x|x ′ ,a ′ )d π h (x ′ ,a ′ ), observe that X x,a d π h (x,a) X x ′ P h (x ′ |x,a)V π ′ h+1 (x ′ ) = X x ′ X x,a P h (x ′ |x,a)d π h (x,a) ! V π ′ h+1 (x ′ ) = X x ′ d π h+1 (x ′ )V π ′ h+1 (x ′ ). This implies that D d π h ,Q π ′ h E − D d π h ,V π ′ h E =⟨d π h ,r h ⟩ + D d π h+1 ,V π ′ h+1 E − D d π h ,V π ′ h E . Then, summing over h∈ [H] and recalling that V π ′ H+1 = 0 and that ν 0 = d π 1 , we obtain that H X h=1 D d π h ,Q π ′ h E − D d π h ,V π ′ h E = H X h=1 ⟨d π h ,r h ⟩− D ν 0 ,V π ′ 1 E = J π − J π ′ . Finally, rearranging, we have J π − J π ′ = H X h=1 D d π h ,Q π ′ h E − D d π h ,V π ′ h E = H X h=1 X x d π h (x) X a π h (a|x)Q π ′ h (x,a)− V π ′ h (x) ! = H X h=1 X x d π h (x) X a (π h (a|x)− π ′ h (a|x))Q π ′ h (x,a), where we used d π h (x,a) = d π h (x)π h (a|x) and the definition of V π ′ h . Multiplying by−1 concludes the proof. 44Appendix table of contents Part I Proofs of Main Results In this section, we include the proofs omitted from the main text. Appendix E provides technical results in concentration and optimization that will be used to prove the sample complexity guarantees of Algorithm 1 in Appendix F, and to prove the lower bound in Appendix G. F Proofs from Section 3 As discussed in Section 3.1,OVIreduces the suboptimality gap to a sequence of saddle-point problems involving the objectiveL d h and learns the output policy in a layer-wise manner. We recall here only the additional notation needed for the proofs. For any (partial) policyπ = (π 1 ,...,π h−1 ), we denoteL π h =L d π h for convenience. When learning layerh, the previously computed decision rulesπ out,1 ,...,π out,h−1 allow us to sample fromd π out h . Thus, for eachi∈ [n E ],OVI independently samples x i h ∼ d π out h and a i E,h ∼ π E,h · x i h . Forh = 1, we can sample fromd π out 1 = ν 0 . For subsequent stagesh, we can sample fromd π out h by rolling in with the previously computed policiesπ out,1 ,...,π out,h−1 . Given these samples, for any decision rulepand function f ∈ R X×A , we define the empirical estimate ofL π out h as b L h (p,f ) = 1 n E n E X i=1 f x i h ,a i E,h − f x i h ,p . For the version ofOVIanalyzed in Theorem F.1, the empirical game is solved by having theQ-player best respond to b L h (π k h ,·), while theπ-player uses online mirror ascent (Beck and Teboulle, 2003) with negative entropy as a regularizer. Fixing a stage h, for each k, Q k h ∈ arg max Q h ∈Q h b L h π k h ,Q h ,and π k+1 h ∝ π k h ⊙ exp ηQ k h ,(19) where η > 0 is the learning-rate parameter and⊙ denotes the element-wise product. Having recalled the algorithm structure, we can now move towards proving our main result: interaction enables computationally and statistically efficient value-based imitation learning algorithms such as our OVI. Before proving Theorem F.1, we derive Lemma F.1, which motivates theπ-player update that will be used in the proof of Theorem F.1. It shows that if theQ-player best responds to theπ-player, then the suboptimality gap can be bounded by the regret of theπ-player plus an estimation error term that can be controlled with a large enough number of expert queries n E . Lemma F.1. Let Assumption 2.1 hold. Let policiesπ 1 h ,...,π K h and functionsQ 1 h ,...,Q K h ∈ Qbe computed as in Eq. (19). We define theπ-regret at stagehand statexasR π h (x) = P K k=1 ⟨Q k h (x,·),π E,h (·|x)−π k h (·|x)⟩ . Furthermore, for any policyπ, we define the estimation error as∆(π) = max h∈[H] sup Q h ∈Q h | b L h (π h ,Q h )−L π out h (π h ,Q h )|, where π out,h = 1 K P K k=1 π k h . Then, J π E − J π out ≤ 1 K H X h=1 X x∈X d π out h (x)R π h (x) + 2H K K X k=1 ∆ π k . Proof of Lemma F.1. By the performance difference lemma (Lemma E.9) withπ = π out andπ ′ = π E , and by the definition ofL π out h , we haveJ π E − J π out = P H h=1 L π out h (π out,h ,Q π E h ) . SinceL π out h (p,Q)is affine in the decision rulep and π out,h = 1 K P K k=1 π k h , this gives J π E − J π out = H X h=1 L π out h (π out,h ,Q π E h ) = 1 K H X h=1 K X k=1 L π out h π k h ,Q π E h . 45Appendix table of contents Then, we can upper bound the suboptimality as follows K(J π E − J π out ) = X h,k L π out h π k h ,Q π E h (a) ≤ X h,k b L h π k h ,Q π E h + H X k ∆ π k (b) ≤ X h,k b L h π k h ,Q k h + H X k ∆ π k (a) ≤ X h,k L π out h π k h ,Q k h + 2H X k ∆ π k , where step (a) uses the definition of∆(π k )together withQ π E h ∈Q h in the first application andQ k h ∈Q h in the second, and step (b) uses thatQ k h is a best response to b L h (π k h ,·)overQ h . Finally, by expanding the definition ofL π out h and exchanging the finite sums over k, x, and a, K X k=1 L π out h (π k h ,Q k h ) = X x∈X d π out h (x) K X k=1 ⟨Q k h (x,·),π E,h (·|x)− π k h (·|x)⟩ = X x∈X d π out h (x)R π h (x). This concludes the proof. Next, we use Lemma F.1 to derive a sample complexity guarantee forOVI. At a high level, the proof intuition is to notice that Lemma F.1 reduces the control of the suboptimality gap to two terms: the average regret of the policy player and the average estimation error of the empirical saddle-point objective. Thus, it suffices to en- sure thatR π h (x)grows sublinearly inKfor each stagehand statex ∈ X, which is achieved by the no-regret update in Algorithm 1. The estimation error term is controlled by a uniform concentration argument over the Q-class and over the policies that can be played by our algorithm. In particular, each iterate belongs to the pol- icy classΠ Q : = π : ∃m ≤ K,∀h,∃Q 1 h ,...,Q m h ∈ Q h , π h (a|x) = softmax( P k Q k h (x,·)) a for some K = poly(H, logA,Q max ,ε −1 ), and concentration uniformly overΠ Q ×Qcontrols 1 K P K k=1 ∆(π k ) with a suf- ficiently large number of expert queries n E . We make the proof formal in the next subsection. F.1 Proof of Theorem 3.1 (Sample Complexity Guarantee for OVI) In this section, we present the proof of our main upper bound. Theorem 3.1 (Sample complexity ofOVI). Let Assumption 2.1 hold for a finite classQ. Then, for anyε,δ ∈ (0, 1), OVI(Algorithm 1) with parametersn E = e O(H 4 Q 4 max log(A) log(|Q|/δ)ε −4 ),η = (log(A)/(KQ 2 max )) 1/2 , andK = O(H 2 Q 2 max log(A)ε −2 ), outputs a policy π out such that with probability at least 1− δ, J π E − J π out ≤ ε after e O H 5 Q 4 max log(A) log(|Q|/δ) ε 4 expert queries. Proof of Theorem 3.1. The proof is a direct consequence of Theorem F.1 below, where the covering number argument simplifies to a union bound over the function classQ. Below, we present our general result that extends the sample complexity analysis to more general function classes. In particular, Theorem F.1 shows that the sample complexity ofOVIis controlled by the largestℓ ∞ -covering number of Q h overh∈ [H], and that whenQis convex, the sample complexity improves to e O(H 3 Q 2 max log(N max r ε (Q)/δ)ε −2 ) for somer ε =O(ε 2 ). When the classes are infinite, the best responses in theQ-player update need not exist automatically. Throughout this result, we consider classes for which the maximizers in Algorithm 1 are well defined. This holds, for instance, when eachQ h is compact and the empirical objective optimized by the Q-player is continuous onQ h . Theorem F.1 (Sample complexity ofOVI). Let Assumption 2.1 hold. For everyr > 0, letN max r (Q)be the largest ℓ ∞ -covering number (see Definition E.1) ofQ h overh∈ [H], and chooser ε =O(ε 2 /(H 2 Q max logA)). Then, for any ε,δ ∈ (0, 1), OVI (Algorithm 1) with parameters η = s log(A) KQ 2 max ,K =O H 2 Q 2 max log(A) ε 2 ,and n E = e O H 4 Q 4 max log(A) log N max r ε (Q)/δ ε 4 ! , 46Appendix table of contents outputs a policy π out such that, with probability at least 1− δ, J π E − J π out ≤ ε after e O H 5 Q 4 max log(A) log N max r ε (Q)/δ ε 4 ! expert queries. Moreover, whenQis convex, the same guarantee holds withn E = e O(H 2 Q 2 max log(N max r ε (Q)/δ)ε −2 ), and the sample complexity improves to e O(H 3 Q 2 max log(N max r ε (Q)/δ)ε −2 ). Proof of Theorem F.1. To prove the sample complexity guarantees of Algorithm 1, we start from the decomposition given in Lemma F.1. J π E − J π out ≤ 1 K H X h=1 X x∈X d π out h (x)R π h (x) + 2H K K X k=1 ∆ π k . We need to control the regret of the policy player R π h , defined for any state x as R π h (x) = K X k=1 Q k h (x,·),π E,h (·|x)− π k h (·|x) , and we need to control the average estimation error 1 K P K k=1 ∆(π k ), where, for any policy π, we define ∆(π) = max h∈[H] sup Q h ∈Q h b L h (π h ,Q h )−L π out h (π h ,Q h ) . Controlling the regretR π h . In order to controlR π h , we use online mirror ascent with negative-entropy regularizer, which corresponds to the following update rule for each stageh ∈ [H], iterationk ∈ [K], statex ∈ Xand action a∈A, π k+1 h (a|x)∝ π k h (a|x)e ηQ k h (x,a) . Fix h and x. Applying Lemma E.6 to the simplex with losses ℓ k =−Q k h (x,·) and comparator u = π E,h (·|x) gives R π h (x)≤ log|A| η + ηKQ 2 max , where we used that the initial decision rule is uniform, so the negative-entropy Bregman divergence to any comparator is at mostlog|A|, and that eachQ h ∈Q h satisfies∥Q h ∥ ∞ ≤ Q max , as assumed in Assumption 2.1. Plugging the value ofηfrom the statement of Theorem F.1,η = (log(A)/K) 1/2 Q −1 max , we get thatR π h (x)≤ 2 p KQ 2 max log|A|. Sinced π out h is a probability distribution for every h, setting K = 36H 2 Q 2 max log(A)ε −2 implies 1 K H X h=1 X x∈X d π out h (x)R π h (x)≤ 2 r H 2 Q 2 max log|A| K = ε 3 . Controlling the estimation error. It remains to control the average estimation error 1 K P K k=1 ∆(π k ). To this end, recall that, in Algorithm 1, we build the empirical estimator b L h by samplingn E states fromd π out h . This sampling is possible becaused π out h depends only onπ out,1 ,...,π out,h−1 , which have already been computed. We then query the expert for an action at each sampled state. For each i∈ [n E ], we sample x i h ∼ d π out h and a i E,h ∼ π E,h · x i h . For every k ∈ [K], the policy π k belongs to the class Π Q ⊂ ∆(A) X defined below. Π Q : = n π :∃m∈0,...,K,∀h,∃Q 1 h ,...,Q m h ∈Q h , π h (a|x) = softmax η P j Q j h (x,·) a o . For eachh, writeΠ Q,h : =π h : π ∈ Π Q for the corresponding class of decision rules. We upper bound the average estimation error by 1 K K X k=1 ∆ π k ≤ sup π∈Π Q ∆(π)≤ max h∈[H] sup p∈Π Q,h sup Q h ∈Q h b L h (p,Q h )−L π out h (p,Q h ) . 47Appendix table of contents To control the upper bound, we verify that we can apply the concentration argument from Lemma E.2. Fixh,p∈ Π Q,h , and Q h ∈Q h , and define Y i (Q h ,p) : = Q h x i h ,a i E,h − Q h x i h ,p −L π out h (p,Q h ). Conditionally on the history before the samples for stagehare drawn,d π out h is fixed and(Y i (Q h ,p)) n E i=1 is a martingale difference sequence. Moreover, sinceQ h ∈ [0,Q max ] X×A , bothQ h (x i h ,a i E,h )andQ h (x i h ,p)belong to[0,Q max ], while L π out h (p,Q h ) belongs to [−Q max ,Q max ]. Hence |Y i (Q h ,p)|≤ 2Q max almost surely. Applying Lemma E.2 withd h = d π out h andΠ h = Π Q,h therefore gives, for any radiusr > 0, with probability at least 1− δ, sup π∈Π Q ∆(π)≤ 4r + Q max v u u t 8 log 2 δ P H h=1 N r (Q h × Π Q,h ,ρ) n E .(20) Taking r = ε/(24H) and n E ≥ 288H 2 Q 2 max ε 2 log 2 δ H X h=1 N ε/(24H) (Q h × Π Q,h ,ρ) ! yields H sup π∈Π Q ∆(π)≤ ε 3 with probability at least 1− δ. Putting everything together. Plugging the two previous bounds in the decomposition shown in Lemma F.1, and using r = ε/(24H) in Eq. (20), with probability at least 1− δ, we have J π E − J π out ≤ 1 K H X h=1 X x∈X d π out h (x)R π h (x) + 2H K K X k=1 ∆ π k ≤ 2 r H 2 Q 2 max log|A| K + ε 3 + 2HQ max v u u t 8 log 2 δ P H h=1 N ε/(24H) (Q h × Π Q,h ,ρ) n E ≤ ε 3 + ε 3 + ε 3 , where the last line uses K = 36H 2 Q 2 max log(A)ε −2 and n E ≥ 288H 2 Q 2 max ε 2 log 2 P H h=1 N ε/(24H) (Q h × Π Q,h ,ρ) δ ! . Next, we consider separately the convex and nonconvex cases for the classesQ h , and show that the sample complexity improves in the convex case. Convex case. Assume first that eachQ h is convex. Fixh∈ [H]. By Lemma E.4, more precisely by Eq. (17), for every radius r > 0, N r (Q h × Π Q,h ,ρ)≤ (K + 1)N r 2 max1,Q max ηK (Q h ,∥·∥ ∞ ) 2 . Ifε ≥ Q max , reward normalization givesJ π E − J π out ≤ Q max ≤ ε, so the performance claim is immediate. We may therefore assume that ε < Q max . For the parameter choice in the theorem, Q max ηK = p K log|A| = 6HQ max log|A| ε . SinceH ≥ 1andA≥ 2, we then haveQ max ηK > 6H log 2 > 1. Hencemax1,Q max ηK = Q max ηKin the remaining covering estimates. We now plug this stagewise bound into the estimation guarantee. With the radiusr = ε/(24H) used in Eq. (20), the product bound above implies H X h=1 N ε/(24H) (Q h × Π Q,h ,ρ)≤ H(K + 1) max h∈[H] N ε 48HQ max ηK (Q h ,∥·∥ ∞ ) 2 . 48Appendix table of contents Combining the bound above with the sufficient condition on n E in the preceding paragraph, it is enough to take n E ≥ 288H 2 Q 2 max ε 2 log 2H(K + 1) δ max h∈[H] N ε 48HQ max ηK (Q h ,∥·∥ ∞ ) 2 . Substituting the values of K and Q max ηK, the following order of expert queries per stage suffices: n E =O H 2 Q 2 max ε 2 log H 1 + 36H 2 Q 2 max log|A|/ε 2 δ max h∈[H] N ε 2 288H 2 Q max log|A| (Q h ,∥·∥ ∞ ) 2 !! = e O H 2 Q 2 max ε 2 log 1 δ max h∈[H] N ε 2 288H 2 Q max log|A| (Q h ,∥·∥ ∞ ) . Since the algorithm queries the expert at H stages, the total number of expert queries is Hn E = e O H 3 Q 2 max ε 2 log 1 δ max h∈[H] N ε 2 288H 2 Q max log|A| (Q h ,∥·∥ ∞ ) . Nonconvex classes. We now turn to the general case. Fixh∈ [H]. By Lemma E.3, more precisely by Eq. (14), and since the case split above gives Q max ηK > 1, for every radius r > 0, N r (Q h × Π Q,h ,ρ)≤ (K + 1)N r 2Q max ηK (Q h ,∥·∥ ∞ ) K+1 . With the radius r = ε/(24H) used in Eq. (20), the product bound above implies H X h=1 N ε/(24H) (Q h × Π Q,h ,ρ)≤ H(K + 1) max h∈[H] N ε 48HQ max ηK (Q h ,∥·∥ ∞ ) K+1 . Combining the bound above with the sufficient condition on n E in the preceding paragraph, it is enough to take n E ≥ 288H 2 Q 2 max ε 2 log 2H(K + 1) δ max h∈[H] N ε 48HQ max ηK (Q h ,∥·∥ ∞ ) K+1 . Substituting the values of K and Q max ηK, the following order of expert queries per stage suffices: n E =O H 2 Q 2 max ε 2 log H 1 + 36H 2 Q 2 max log|A|/ε 2 δ max h∈[H] N ε 2 288H 2 Q max log|A| (Q h ,∥·∥ ∞ ) 1+36H 2 Q 2 max log|A|/ε 2 !! = e O H 4 Q 4 max log|A| ε 4 log 1 δ max h∈[H] N ε 2 288H 2 Q max log|A| (Q h ,∥·∥ ∞ ) . Since the algorithm queries the expert at H stages, the total number of expert queries is Hn E = e O H 5 Q 4 max log|A| ε 4 log 1 δ max h∈[H] N ε 2 288H 2 Q max log|A| (Q h ,∥·∥ ∞ ) . This concludes the proof. F.2 Proof of Theorem 3.2 (Reward Realizability Is Insufficient) So far, we showed that, underQ π E -realizability, interactive IL is possible but offline IL is not without additional coverage. It is natural to ask whether one can weaken the representation requirement even further. A tempting candidate is reward realizability: whenH = 1,Q π E -realizability reduces to reward realizability, and Joshi et al. (2026) show that reward real- izability is enough for statistical learnability in contextual bandits, although their algorithm is computationally inefficient. The theorem below shows that, in general MDPs, reward realizability alone cannot yield a representation-dependent guarantee even with interaction: the reward class is a singleton, but the learner still needs coverage of the rare decision states. This motivates the stronger assumption used in the main text,Q π E -realizability, which stores additional information about the transitions that a reward function alone does not provide. 49Appendix table of contents x 0 start x 0 + x 0 − ν 0 x 0 start = 1− Xq a = b 0 = 0 a̸= b 0 x 1 start x 1 + x 1 − ν 0 x 1 start = q a = b 1 a̸= b 1 x i start x i + x i − ν 0 x i start = q a = b i a̸= b i Figure 5: Instance from the family used in Theorem 3.2. Every MDP in the family uses the same reward, and the hidden bitb i ∈0, 1selects which action reachesx i + fromx i start . It remains hidden unlessx i start is observed during training. Theorem 3.2 (Lower bound under reward realizability). For everyX ≥ 1andε∈ (0, 1/4], there exists a familyFof MDPs with: i) stochastic initial states but deterministic rewards and transitions, i) horizonH = 2, i) state space size |X| = O(X), and iv) family sizelog(|F|) = O(X), such that for everyM ∈ F, Assumption 3.2 is satisfied by the same singleton reward classR = r ⋆ . LetAlgbe any interactive IL algorithm (Definition 3.1). Then, there exists an MDPM∈F, with corresponding expertπ E = π ⋆ M , such thatAlgneedsΩ X ε rounds of interactions to output a policy π out such that E[J π E M − J π out M ]≤ ε. 12 Comparison withQ π E -realizability. This lower bound is specific to reward realizability and should not be read as a contradiction to the guarantees under Assumption 2.1. In the construction below, where each MDP is characterized by a bit vectorb ∈ 0, 1 X , the common reward only identifiesx i + as rewarding andx i − as non-rewarding but it does not reveal which action fromx i start reachesx i + . By contrast, for each instanceM b , the expert value function satisfiesQ π b E M b ,1 (x i start ,a) = 1a = b i . ThusQ π E stores the information about which action to take at the starting state itself. Equivalently, a value class thatQ π E -realizes all MDPs in this family must contain one distinct function for eachb ∈ 0, 1 X , so its complexity already scales withX. Reward realizability avoids this complexity entirely by using a singleton class, but then the learner receives no representation of the control information needed at unobserved states. Proof of Theorem 3.2. Setq = 4ε/X, which satisfiesq ≤ 1/Xbecauseε ≤ 1/4. We first define the hard family H =H X,q . Let the action space beA =0, 1. For eachi∈0,...,X, the state space contains a start statex i start and two terminal states x i + and x i − . The initial distribution is ν 0 x 0 start = 1− Xq,and ν 0 x i start = qfor i∈ [X]. For b = (b 1 ,...,b X )∈0, 1 X , set b 0 = 0. In the MDPM b , the first transition is deterministic and given by P b 1 x i + x i start ,a = 1a = b i ,and P b 1 x i − x i start ,a = 1a̸= b i . All stage-two behavior is fixed independently ofb. For concreteness, let the expert’s terminal action be0, and take any fixed terminal transitions. The reward is common to all instances. For any index i and action a, r ⋆ 1 (x i start ,a) = 0, r ⋆ 2 (x i + ,a) = 1, r ⋆ 2 (x i − ,a) = 0. Thus the singleton classR = r ⋆ realizes every instance in the family. Let the expert inM b be the deterministic policyπ b E,1 (x i start ) = b i , with the fixed terminal behavior described above. The expert reachesx i + from everyx i start , so it is optimal and J π b E M b = 1. The family is illustrated in Figure 5. For any policy π, starting from x i start yields terminal reward one if and only if the first action equals b i . Hence J π b E M b − J π M b = 1− X X i=0 ν 0 x i start π 1 b i x i start = X X i=0 ν 0 x i start π 1 A\b i x i start .(21) 12 The expectation is over all randomness in the protocol, including the trajectories sampled from the MDP, the actions sampled from the expert policy, and the internal randomness of Alg. 50Appendix table of contents We lower bound the average suboptimality gap over a random instance. LetB = (B 1 ,...,B X )∼ Unif(0, 1 X ), and runAlgonM B . Letξbe an independent random seed encoding all of the algorithm’s internal randomness, and letD denote the complete interaction transcript available to the learner after the fixedn E episodes. For eachi∈ [X], letV i be the event that x i start appears as the initial state in one of the fixed n E interaction rounds. AlthoughB i is sampled uniformly initially, we later condition on the dataset used to chooseπ out . This conditioning can matter becauseDis generated in the MDP whose expert policy and transitions depend onB i . IfV i occurs, then Dcontains a transition out ofx i start . No matter whether an expert action is observed or not, the transition out of x i start reveals which action reachesx i + . OnV c i , however,Dcontains no observation from thei-th component of the construction: the statex i start can only appear as an initial state, and no transition from any other component reaches it. Thus, conditional onV c i ,Dmay depend on the coordinatesB j forj ̸= i, but the conditional law of(D,ξ)does not depend onB i . SinceB i is uniform and independent ofB j forj ̸= i, even after seeing the dataset and knowingV c i , we still have no information about B i . Whenever P[V c i ] > 0, this gives P[B i = 0|D,V c i ,ξ] = P[B i = 1|D,V c i ,ξ] = 1 2 . Conditional onD,V c i , andξ, the output policy is fixed. We definep i : = π out,1 (1|x i start ). The quantity that appears in the suboptimality gap for thei-th component isπ out,1 (A\B i |x i start ) , which is the probability that the output policy chooses the wrong first action atx i start . IfB i = 0, action1is wrong, and this quantity equalsp i . IfB i = 1, action0is wrong, and this quantity equals 1− p i . WhenP[V c i ] > 0, averaging overDandξand multiplying byP[V c i ]gives the identity below; whenP[V c i ] = 0, the identity is trivial. Hence E π out,1 (A\B i |x i start )1V c i = 1 2 P[V c i ].(22) Becausen E is a fixed deterministic budget and the initial state in each interaction round is sampled independently from ν 0 , the event V c i has probability P[V c i ] = (1− q) n E . Combining Eqs. (21) and (22) with this identity and discarding the nonnegative contribution of x 0 start gives E h J π B E M B − J π out M B i ≥ X X i=1 qE π out,1 (A\B i |x i start )1V c i = Xq 2 (1− q) n E .(23) Since the left-hand side averages uniformly over B, there exists a fixed b∈0, 1 X such that E h J π b E M b − J π out M b i ≥ Xq 2 (1− q) n E . If n E < X/(8ε), Bernoulli’s inequality gives (1− q) n E = (1− 4ε X ) n E ≥ 1− 4εn E X > 1 2 . Therefore,M b satisfies E h J π b E M b − J π out M b i > X 2 · 4ε X · 1 2 = ε. Thus, achieving expected suboptimality at mostεon every instance requiresn E ≥ X/(8ε). Since|X| = 3X + 3, the sample-complexity statement follows. 51Appendix table of contents G Proofs from Section 4 (Q π E -Realizability Is Insufficient to Learn Offline) Here, we show that an offline precollected expert dataset is insufficient for efficient IL (without paying for the expert policy hypothesis class) in MDPs where onlyQ π E is realizable. Our lower bound holds against all IL algorithms that output a value-induced policy, as defined in Definition 4.2. We recall the definition of such algorithms next. Offline Value-Based Imitation Learning Algorithms. An algorithmAlgis said to be a value-based IL algorithm if the following conditions hold. 1. Alg receives an expert datasetD E and a state-action value function classQ. 2.For someK ∈ N∪∞,Algchooses a sequenceQ 1 ,Q 2 ,...,Q K ∈Qand coefficients(w k ) K k=1 defining the linear combinationLC((Q k ) K k=1 ) = P K k=1 w k Q k . WhenK =∞, this series must converge absolutely at every stage-state-action tuple. 3. Alg outputs the policy π out (a|x)∝ f LC (Q k ) K k=1 (x,a) , for any state-action pair(x,a), with the requirement that the normalizing denominator is strictly positive and finite at every stage-state pair. The pointwise-limit convention in Definition 4.2 also includes valid pointwise limits of policies of this form. Next, we show that the class of algorithms that output a VI policy is general. It includes, for instance,SPOIL(Moulin et al., 2025a), while the pointwise-limit convention also represents greedy policies under suitable conditions. SPOIL uses VI policies. Choosing f (·) = exp(·) and taking LC to be the sum multiplied by a scalar η ≥ 0 gives π out (a|x) = softmax η P K k=1 Q k (x,·) a , which captures the output strategy of SPOIL and Algorithm 1. Greedy policies as limits of VI policies. In the contextual-bandit setting of Joshi et al. (2026), we haveH = 1, so we can omit the subscripthand consider a reward classRrather than a value function classQ. Their learner forms a rewardr(x,a) = P ̃r∈R w( ̃r) ̃r(x,a) using learned weightsw ∈ ∆(R)and uses a predictor that is greedy with respect tor. Such a predictor is not a finite-temperature VI policy: for any finiteη, choosingf η (z) = exp(ηz)gives the softmax VI policyπ η (·|x) = softmax(ηr(x,·)), which generally assigns positive mass to nongreedy actions. Under our standing assumptions thatAis finite andris finite-valued, however, the softmax normalizer is strictly positive and finite, and these policies converge pointwise as η →∞. lim η→∞ π η (a|x) = 1 a∈arg max b∈A r(x,b) |arg max b∈A r(x,b)| . Consequently, a uniformly tie-broken greedy policy belongs to the VI class through its pointwise-limit convention. A deterministic greedy policy does as well when the maximizing action is unique. Other tie-breaking rules are covered only if they can be realized by an admissible sequence of VI scores. This gives a limiting connection to the roundwise greedy extraction step of Joshi et al. (2026); it does not assert that their final mixed output policy is itself a VI policy. Algorithms used in practice output VI policies. Beyond prior work in IL theory (Moulin et al., 2025b), algorithms used in practice in IL, such asIQ-LEARN(Garg et al., 2021) andCSIL(Watson et al., 2023), are also value-based imitation algorithms. Indeed, these algorithms choose a singleQ-function from the classQand outputπ out = softmax(αQ(x,a)) . This is recovered by the definition of algorithms outputting VI policies, choosingαto be the weight of the linear combination and taking f (·) = exp(·). G.1Proof of Theorem 4.2 (Lower Bound Against Offline Algorithms that Output VI Policies) We prove Theorem 4.2, which shows nonidentifiability within the class of algorithms outputting VI policies: even with infinite offline data, no such algorithm can guarantee error below 1/4. 52Appendix table of contents Theorem 4.2 (Unidentifiability under VI policies). There exists a familyFof MDPs with: i) deterministic initial states, rewards, and transitions, i) horizonH = 2, i) state space size|X| = 3, and iv) family size|F| = 2, as well as a value function classQwith|Q| = 2such that for everyM∈F, Assumption 2.1 is satisfied for the expert π E = π ⋆ M . Moreover, for any algorithmAlg(Definition 4.1) with a VI policy class (Definition 4.2), for anyn E ∈ N ⋆ , there exists an MDPM∈Fsuch that, givenn E expert trajectories sampled fromπ E ,Algoutputs policiesπ out such that E[J π E M − J π out M ]≥ 1 4 . 13 Proof of Theorem 4.2. For clarity, we carry out the proof using centered rewardsr h ∈ [−1, 0]. Adding1to every reward yields an equivalent MDP with rewards in[0, 1]. This shift preserves optimal policies, suboptimality gaps, and all action comparisons. Shifting the value class accordingly yields a class of the same cardinality that lies in[0, 2] and satisfiesQ π E -realizability withQ max = 2. Although an arbitrary link function need not be translation invariant, every function in the shifted class still assigns equal values to the two actions atx start , and the proof treats the action distribution atx − as arbitrary. Hence the argument below applies unchanged. Formally,a 1 ≡ +anda 2 ≡−are the two global actions; for every unspecified state-action-stage tuple, we assign zero centered reward and a transition to the absorbing state x end , whose features are zero. x start x − x end + − a 1 a 2 , r =−1 (a) MDPM 1 : Action a 1 is optimal. x start x − x end + − a 2 a 1 , r =−1 (b) MDPM 2 : Action a 2 is optimal. Figure 6: Family of hard tasks. Unless otherwise specified, the reward is0. The blue path is the one taken by the deterministic expert. x end is an absorbing state. We consider the family of hard MDPsF =M 1 ,M 2 depicted in Figure 6. We consider the following2-dimensional features that satisfy the Q π E -realizability assumption. • φ(x start , +) = φ(x start ,−) = [0, 0] T , • φ(x − ,a 1 ) = [0, 1] T , • φ(x − ,a 2 ) = [1, 0] T . If the expert policy satisfies π E,1 (+|x start ) = 1 and π E,1 (a 1 |x − ) = 1, then we have • Q π E,1 M 1 (x start , +) = Q π E,1 M 1 (x start ,−) = 0, • Q π E,1 M 1 (x − ,a 1 ) = 0, • Q π E,1 M 1 (x − ,a 2 ) =−1. Thus, by choosingθ 1 = [−1, 0], we can realize the expert action-value function asQ π E,1 M 1 (x,a) = φ(x,a) T θ 1 for all(x,a) ∈ X ×A. For the second MDP inF,M 2 , the optimal expert policy satisfiesπ E,2 (+|x start ) = 1and π E,2 (a 2 |x − ) = 1. Takingθ 2 = [0,−1], we can similarly writeQ π E,2 M 2 (x,a) = φ(x,a) T θ 2 , soM 2 is alsoQ π E -realizable with the same features. Therefore, the two MDPs differ only in which action is good at x − : a 1 inM 1 and a 2 inM 2 . Fix any dataset sizen E ∈ N ⋆ . We now start proving our result. For the moment, we consider the case of deterministic value-based offline IL algorithms that choose a sequence of state-action value functions without randomization. Moreover, we consider the class Q = Q π E,1 M 1 ,Q π E,2 M 2 , whereQ π E,1 M 1 (x,a) = φ(x,a) T θ 1 andQ π E,2 M 2 (x,a) = φ(x,a) T θ 2 for allx,a. Notice that in bothM 1 andM 2 , we have that Q π E,1 M 1 (x start ,a) = Q π E,2 M 2 (x start ,a) = 0 for all a∈+,−. 13 The expectation is over the training data and the internal randomness of Alg. 53Appendix table of contents Under this setting, no matter howAlgselects the sequenceQ 1 ,...,Q K , the output policy at the starting state is uniform: π out (·|x start ) = Unif(+,−). Indeed, everyQ ∈ Qassigns the same value to the two actions+and−atx start . Hence any well-defined linear combinationLC(Q 1:K )also assigns the same scalar to the two start actions, including whenK =∞. Sincefis a function and the normalizing denominator is positive by definition of a valid output policy, the two numerator terms are equal and nonzero. Therefore, the policyπ out induced by any linear combinationLCand functionfin Definition 4.2 guaranteesπ out (+|x start ) = π out (−|x start ) = 1 2 . Moreover, taking pointwise limits or averaging policies obtained from different choices of sequences inQ still gives a uniform policy. It follows that, with probability1/2, the next state isx − . Suppose that the sequenceQ 1 ,...,Q K chosen byAlg induces probabilitiesπ out (a 1 |x − ) = pandπ out (a 2 |x − ) = 1− p. The choice ofQ 1 ,...,Q K , and hence ofp, cannot depend on whether the underlying MDP isM 1 orM 2 , because the expert dataset is identical in the two cases, even with infinite data. Therefore, the suboptimality at x − , averaged over the MDP classF , equals 1/2 as shown next. 1 2 2 X i=1 Q π E,i M i (x − ,a i )− Q π E,i M i (x − ,π out ) = 1 2 2 X i=1 −Q π E,i M i (x − ,π out ) = p 2 2 X i=1 (−r M i (x − ,a 1 )) + 1− p 2 2 X i=1 (−r M i (x − ,a 2 )) = p 2 + 1− p 2 = 1 2 . Fixi ∈ 1, 2. Applying the performance difference lemma (Lemma E.9) withπ = π out andπ ′ = π E,i to the MDP whose initial distribution is a point mass atx start gives the following identity. Suppressing the stage index as above, the only state-occupancy terms that can contribute ared π out 1 (x start ) = 1andd π out 2 (x − ) = π out (−|x start ) = 1/2. All terms at x end vanish because the expert Q-values there are zero. Therefore, V π E,i M i (x start )− V π out M i (x start ) =1 |z d π out 1 (x start ) X a∈+,− (π E,i (a|x start )− π out (a|x start ))Q π E,i M i (x start ,a) + 1 2 |z d π out 2 (x − ) X a∈a 1 ,a 2 (π E,i (a|x − )− π out (a|x − ))Q π E,i M i (x − ,a) = 0 + 1 2 Q π E,i M i (x − ,a i )− X a∈a 1 ,a 2 π out (a|x − )Q π E,i M i (x − ,a) = 1 2 Q π E,i M i (x − ,a i )− Q π E,i M i (x − ,π out ) . Separately, the worst-case suboptimality gap is at least the average of the two suboptimality gaps over the two instances, so combining the two derivations above gives max M∈M 1 ,M 2 V π E M (x start )− V π out M (x start )≥ 1 2 2 X i=1 V π E,i M i (x start )− V π out M i (x start ) = 1 2 2 X i=1 1 2 Q π E,i M i (x − ,a i )− Q π E,i M i (x − ,π out ) = 1 2 · 1 2 2 X i=1 Q π E,i M i (x − ,a i )− Q π E,i M i (x − ,π out ) | z =1/2 by the preceding display = 1 4 . The preceding display holds for every deterministic offline algorithm that outputs a VI policy under the uniform distribution over the two instances inF. Therefore, by Yao’s minimax principle (see, e.g., Bubeck et al., 2012), the 54Appendix table of contents same lower bound holds against possibly randomized algorithms: max M∈M 1 ,M 2 E π out ∼Alg [V ⋆ M (x start )− V π out M (x start )]≥ 1 4 , where we used the equalities V π E,1 M 1 = V ⋆ M 1 and V π E,2 M 2 = V ⋆ M 2 , which follow by optimality of the experts. G.2 Proof of Theorem 4.1 (Lower Bound Against Any Offline IL Algorithm) In the above construction, we could learn by memorizing one expert action inx start and playing it at deployment time. However, we can build a harder extended MDP by repeating the hard instance from Figure 6 several times, as shown in Figure 7. This lets us derive an information-theoretic lower bound against any offline IL algorithm. For algorithms outside the class of algorithms that output a VI policy, the problem is no longer nonidentifiable. However, the required dataset size scales linearly with the number of states, while the classQrealizingQ π E has cardinality independent of|X|. Theorem 4.1 (Main lower bound for offline IL). For anyX ∈ N ⋆ and anyε ∈ (0, 1 8 ], there exists a familyFof MDPs with: i) stochastic initial states but deterministic rewards and transitions, i) horizonH = 2, i) state space size|X| = O(X), and iv) family sizelog(|F|) = O(X), as well as a value function classQwith|Q| = 2such that for everyM ∈ F, Assumption 2.1 is satisfied for expert policyπ E = π ⋆ M . LetAlgbe any offline IL algorithm (Definition 4.1). Then, there exists an MDPM∈Fsuch thatAlgneedsn E ≥ Ω( X ε ) trajectories sampled according to Eq. (3) with expert policy π ⋆ M , to output a policy π out such that E[J π ⋆ M M − J π out M ]≤ ε. 14 Proof of Theorem 4.1. As in the preceding proof of Theorem 4.2, we use centered rewardsr h ∈ [−1, 0]for convenience. Applying the same shifts and conventions yields the required formal construction without affecting the argument. We consider a familyF = M ext j 2 X+1 j=1 in which each of the2 X+1 extended MDPs has3X + 3states and is obtained by consideringX + 1copies of the structure in Figure 6, with starting states labeled asx i start fori∈0,...,X. For any ε≤ 1 8 , denote q = 8ε X and consider the following initial distribution ν 0 x 0 start = 1− Xq,and ν 0 x i start = qfor all i̸= 0. To construct the MDP family, we consider that each of the X copies indexed by i̸= 0 can be in two modes: • In mode +, we consider that the action + goes straight from x i start to x i end , without passing through x i − . • In mode−, instead the action− goes straight from x i start to x i end , without passing through x i − . Considering all possible combinations of modes for each copy except the first, i.e., fori = 1,...,X, we obtain2 X MDPs. Moreover, for each of these2 X transition configurations, we can choose, as in the proof of Theorem 4.2, the reward parameters to beθ 1 = [−1, 0]orθ 2 = [0,−1]. Therefore, we obtain a family of2 X+1 MDPs. A visual representation of an extended MDP with parameters θ 1 is given in Figure 7. The family of2 X+1 optimal expert policies is defined so that the expert policy in the copy with root statex i start in the MDPM ext j takes the optimal action that does not pass throughx i − . That is, the expert chooses action+if thei th copy is in mode+in the MDPM ext j and action−if the copy is in mode−. At eachx i − , the expert takes an action that is optimal for the chosen reward parameter, while at every absorbing state all expert policies take the same fixed action. Since all the experts are optimal, we denote the expert action-value function in the MDPM ext j byQ ⋆ M ext j and the state value function by V ⋆ M ext j . At this point, note that for each j ∈ [2 X+1 ], we have that Q ⋆ M ext j is affine in the features φ(x i start , +) = φ(x i start ,−) = [0, 0] T , φ(x i − ,a 1 ) = [0, 1] T ,and φ(x i − ,a 2 ) = [1, 0] T , with parameters eitherθ 1 orθ 2 . DenotingQ θ (x,a) = φ(x,a) T θ, the classQ =Q θ 1 ,Q θ 2 satisfiesQ π E -realizability in M ext j for everyj ∈ [2 X+1 ]and has cardinality independent ofX. Formally, we haveQ ⋆ M ext j ∈Qfor anyj ∈ [2 X+1 ]. In each MDP, the expert from the root statesx 0 start ,...,x X start only takes the action that avoids the statesx 0 − ,...,x X − , so it does not reveal which action (betweena 1 anda 2 ) is optimal in those states and the learner cannot determine whether the reward parameter vector is θ 1 or θ 2 . 14 The expectation is over the training data and the internal randomness of Alg. 55Appendix table of contents x 0 start x 0 − x 0 end ν 0 (x 0 start ) = 1− Xq + − a 1 a 2 , r =−1 x 1 start x 1 − x 1 end ν 0 (x 1 start ) = q + − a 1 a 2 , r =−1 x i start x i − x i end ν 0 (x i start ) = q + − a 1 a 2 , r =−1 Figure 7: Representation of a MDP in the classF. The states highlighted in green appear inD E , so the learner can deter- ministically replay the expert action+. The red states are absent fromD E . Thus, no expert guidance is available there, and the learner reachesx i − with probability at least 1 /2in some environment inF, where it plays an action that is subop- timal under one of the two reward parameter choicesθ 1 andθ 2 . Here,q = 8ε/X, soν 0 assigns mass1− Xqtox 0 start and massqto every other root state. This initial distribution follows the lower-bound construction for tabular offline IL from Rajaraman et al. (2020) and ensures that the expected suboptimality can be below ε only if n E = Ω(|X|ε −1 ). For the averaging argument, draw an environmentMuniformly fromF, equivalently by drawing its modesσ 1 ,...,σ X independently and uniformly from+,−and its reward parameterΘindependently and uniformly fromθ 1 ,θ 2 . Here,σ i specifies the mode of copyi, so actionσ i bypassesx i − , whileΘis the reward parameter shared by all copies and determines which action is optimal at eachx i − . Letξbe a random seed, independent of the environment and expert data, that encodes all of the learner’s internal randomness, and defineT : = (D E ,ξ). Thus,Tconsists exactly of the expert dataset and the learner’s random seed. Fixi ∈ [X]and consider the eventE i : = x i start /∈ D E . On E i , the dataset contains no observation from copyi, so it does not depend onσ i . Moreover, it does not depend on Θ: the expert never visits any of the statesx 0 − ,...,x X − , rewards are unobserved, and all expert policies take the same fixed action at the absorbing states. Sinceξis independent of the environment and expert data,Tis therefore independent of(σ i , Θ)conditional onE i , even though it may reveal the modes of other sampled copies. Consequently, conditional on any realizationT = tandE i , the variablesσ i andΘremain independent and uniform, while the learner’s output policy may depend arbitrarily ont. Fix such a transcriptt, writeπ out,t for the resulting output policy, and letp t : = π out,t,1 (+|x i start ) andu t : = π out,t,2 (a 1 |x i − ) . Averaging overσ i , the probability of reachingx i − is (1− p t )/2 + p t /2 = 1/2. Independently, averaging overΘ, the suboptimality atx i − is(1− u t )/2 + u t /2 = 1/2. Therefore, for every such t, E V ⋆ M x i start − V π out,t M x i start T = t,E i = 1− p t 2 + p t 2 1− u t 2 + u t 2 = 1 4 . For eachj, letE j denote expectation under the transcript distribution inM ext j and the learner’s internal randomness, and write∆ j,i : = V ⋆ M ext j (x i start )− V π out M ext j (x i start ) . SinceE i depends only on the initial-state draws, it has probability (1− q) n E in every environment. Averaging the preceding identity overT therefore yields the unconditional bound 1 2 X+1 2 X+1 X j=1 E j [∆ j,i 1 E i ]≥ 1 4 (1− q) n E . Optimality implies∆ j,i ≥ 0at every root state. Thus, dropping thei = 0term and retaining only the terms onE i , for any j ∈ [2 X+1 ] we have D ν 0 ,V ⋆ M ext j − V π out M ext j E = X X i=0 ν 0 x i start V ⋆ M ext j x i start − V π out M ext j x i start ≥ X X i=1 ν 0 x i start V ⋆ M ext j x i start − V π out M ext j x i start = X X i=1 q V ⋆ M ext j x i start − V π out M ext j x i start ≥ X X i=1 q V ⋆ M ext j x i start − V π out M ext j x i start 1 E i . 56Appendix table of contents TakingE j in the preceding inequality, averaging over the environments, and applying the unconditional bound above gives max j∈[2 X+1 ] E j hD ν 0 ,V ⋆ M ext j − V π out M ext j Ei ≥ 1 2 X+1 2 X+1 X j=1 E j hD ν 0 ,V ⋆ M ext j − V π out M ext j Ei ≥ X X i=1 q 1 2 X+1 2 X+1 X j=1 E j [∆ j,i 1 E i ] ≥ q 4 X X i=1 (1− q) n E = X 4 q(1− q) n E . Then, if n E ≤ X/(32ε), Bernoulli’s inequality gives (1− q) n E = (1− 8ε X ) n E ≥ 1− 8εn E X ≥ 3 4 . Therefore, max M∈F E[⟨ν 0 ,V ⋆ M − V π out M ⟩]≥ X 4 · 8ε X · 3 4 = 3ε 2 > ε, Thus, recalling 3(X + 1) =|X|, achieving ε-suboptimality requires n E = Ω( |X| /ε) for any offline IL algorithm. 57Appendix table of contents Part I Additional Results We collect here additional results omitted from the main text. We begin by completing Section 3 with a variant ofOVI. In Appendix H, we show that reversing the order in which the players update inOVIyields an algorithm that is less computationally efficient, but provides statistical benefits for nonconvexQclasses and allows us to learn a stationary solution in discounted MDPs. In addition to the lower bound from Section 4, we show in Appendix I that it is possible to learn offline if one assumes the (optimal) expert covers the learner’s distribution. Moreover, in Appendix J, we show that interaction enables efficient learning even when the classQrealizes eitherQ π E or theQ-value of any policy that the algorithm might produce, without the learner knowing which case holds. The key algorithmic idea is to sample states from a mixture of the expert and learner occupancy measures, a technique proven successful in the context of language models (Agarwal et al., 2024; Li et al., 2026a). This adaptive variant of OVItherefore applies to a strictly larger set of classesQthan that covered by the offline algorithm of Moulin et al. (2025a), revealing a previously unknown benefit of interaction. H Q-OVI: An Inefficient Algorithm with Improved Statistical Guarantees In this section, we present an alternative algorithmic scheme that first updates theQ-variables via a no-regret algorithm. The resulting method,Q-OVI, is computationally inefficient whenQis continuous because it requires discretizingQ, but it enjoys better statistical rates whenQis nonconvex. When theQ-player moves first, the policy playerπ k h can be chosen greedily with respect to Q k h . For each (k,h)∈ [K]× [H], define x k h ∼ d π out h , a k E,h ∼ π E,h · x k h , b ℓ π out ,k h (Q) = Q x k h ,π k h − Q x k h ,a k E,h . To complete the design ofQ-OVI, we use Lemma H.1 below and note that the sequence(Q k h ) K k=1 can be chosen to minimize a regret with respect to losses b ℓ π out ,1 h ,..., b ℓ π out ,K h . In the following, for anyh∈ [H],C ε (Q h )denotes anε-cover ofQ h , and we abbreviateN max ε (Q) : = max h∈[H] N ε (Q h ) . Then, for a weight distributionw k h ∈ ∆(C ε/(4H) (Q h ))over a covering setC ε/(4H) (Q h )ofQ h , we defineQ k h as the corresponding weighted average. For any state-action pair (x,a)∈X ×A, Q k h (x,a) = X Q∈C ε/(4H) (Q h ) w k h (Q)Q(x,a). The next lemma specifies how to choose the weights. Algorithm 3 Q-OVI: Q-First On-Policy Value-Based Imitation Learning 1: input: Learning rate η, iterations K, finite covering setsC ε/(4H) (Q h )⊆Q h for h∈ [H]. 2: For any h∈ [H] and Q∈C ε/(4H) (Q h ), set w 1 h (Q) = 1/N ε/(4H) (Q h ). 3: For any h∈ [H] and (x,a)∈X ×A, set Q 1 h (x,a) = P Q∈C ε/(4H) (Q h ) w 1 h (Q)Q(x,a). 4: For any h∈ [H] and x∈X , set π 1 h (·|x)∈ arg max p∈∆(A) p,Q 1 h (x,·) . 5: for h = 1,...,H do 6:for k = 1,...,K do 7:Sample x k h ∼ d π out h , a k E,h ∼ π E,h (·|x k h ). 8:For any Q∈C ε/(4H) (Q h ), set w k+1 h (Q)∝ w k h (Q)e η(Q(x k h ,a k E,h )−Q(x k h ,π k h )) . 9:For any (x,a)∈X ×A, set Q k+1 h (x,a) = P Q∈C ε/(4H) (Q h ) w k+1 h (Q)Q(x,a). 10:For any x∈X , set π k+1 h (·|x)∈ arg max p∈∆(A) p,Q k+1 h (x,·) . 11:Set π out,h (a|x) = 1 K P K k=1 π k h (a|x) for any (x,a)∈X ×A. 58Appendix table of contents Lemma H.1. Let Assumption 2.1 hold, and fix an accuracy parameterε > 0. For each(k,h)∈ [K]× [H], suppose thatw k h ∈ ∆(C ε/(4H) (Q h ))and thatQ k h is the corresponding weighted average. For eachh∈ [H], defineπ k h (·|x)∈ arg max p∈∆(A) ⟨p,Q k h (x,·)⟩, and setπ out,h (a|x) = 1 K P K k=1 π k h (a|x)for any state-action pair(x,a)∈X ×A. Let b Q π E h ∈C ε/(4H) (Q h ) be a closest element to Q π E h for each h∈ [H]. Then, with probability at least 1− δ, we have J π E − J π out ≤ H K max h∈[H] R w h + 8HQ max r 2 log(2H/δ) K + ε 2 , where the regret of the sequence (w k h ) K k=1 is defined by R w h = K X k=1 X Q∈C ε/(4H) (Q h ) w k h (Q) b ℓ π out ,k h (Q)− b ℓ π out ,k h b Q π E h . Lemma H.1 says that, with probability at least1 − δ, the performance gapJ π E − J π out is upper bounded by H K max h∈[H] R w h + 8HQ max q 2 log(2H/δ) K + ε 2 .R w h can be easily controlled by updating(w k h ) K k=1 via exponential weights. The resulting algorithm is in Algorithm 3. Therefore, using the decomposition in Lemma H.1 and showing thatR w h =O( √ K)via a standard online learning bound for the regret of the exponential weights algorithm (see, e.g., Cesa-Bianchi and Lugosi, 2006; Orabona, 2026), we obtain the following guarantees. Theorem H.1. Let Assumption 2.1 hold. For anyε,δ ∈ (0, 1), recall thatN max ε/(4H) (Q) : = max h∈[H] N ε/(4H) (Q h ). Run Q-OVI (Algorithm 3) with η = s logN max ε/(4H) (Q) KQ 2 max , K =O H 2 Q 2 max log N max ε/(4H) (Q)H/δ ε 2 , Then, the algorithm outputs a policy π out such that, with probability at least 1− δ, we have J π E − J π out ≤ ε after O H 3 Q 2 max log N max ε/(4H) (Q)H/δ ε 2 expert queries. Despite having strong statistical guarantees, Algorithm 3 is not computationally attractive when the class is large or continuous because the construction of the covering set is cumbersome. We compare Q-OVI and OVI below. Comparison of the computational complexity. As mentioned, Algorithm 1 is better suited for a practical implementa- tion because it does not require discretizing the classQ. While we think that the linear case could be made efficient, this approach is clearly not scalable whenQcorresponds to the class of weights for modern architectures.Q-OVIwould learn a distribution over a set of exponentially many weight configurations. In contrast,OVIis compatible with the common practice of specifying a loss function and backpropagating through it. Comparison of the statistical complexity. When the classQis convex, both algorithms achieve a rate of orderO(ε −2 ). A rate difference emerges in the nonconvex case, where Algorithm 3 has a sample complexity of orderO(ε −2 ), while Algorithm 1 has a suboptimalO(ε −4 ) rate. To summarize,Q-OVI(Algorithm 3) has better statistical properties but is computationally inefficient compared toOVI (Algorithm 1) because it requires discretizing the classQ. H.1 Proof of Lemma H.1 (Suboptimality Gap Decomposition for Q-OVI) Proof of Lemma H.1. By the performance difference lemma (Lemma E.9) and by the definition of π out,h , we have J π E − J π out = H X h=1 L π out h (π out,h ,Q π E h ) 59Appendix table of contents = 1 K H X h=1 K X k=1 L π out h π k h ,Q π E h = 1 K H X h=1 K X k=1 L π out h π k h ,Q k h + 1 K H X h=1 K X k=1 L π out h π k h ,Q π E h − Q k h . Since π k h (·|x)∈ arg max p∈∆(A) ⟨p,Q k h (x,·)⟩, we haveL π out h (π k h ,Q k h )≤ 0. Hence, J π E − J π out ≤ 1 K H X h=1 K X k=1 L π out h π k h ,Q π E h − Q k h . Letr > 0and let b Q π E h ∈ C r (Q h )be such that∥ b Q π E h − Q π E h ∥ ∞ ≤ rfor eachh ∈ [H]. For any decision rulepand functions Q h ,Q ′ h , |L π out h (p,Q h − Q ′ h )|≤∥Q h − Q ′ h ∥ ∞ X x∈X d π out h (x)∥π E,h (·|x)− p(·|x)∥ 1 ≤ 2∥Q h − Q ′ h ∥ ∞ . Thus, replacingQ π E h by b Q π E h costs at most2rfor each pair(k,h), hence at most2Hrafter averaging overkand summing over h. Replacing Q π E h by b Q π E h in the previous display gives J π E − J π out ≤ 1 K H X h=1 K X k=1 L π out h π k h , b Q π E h − Q k h + 2Hr.(24) For each (k,h)∈ [K]× [H], define the sampled loss b ℓ π out ,k h (Q) = Q x k h ,π k h − Q x k h ,a k E,h , x k h ∼ d π out h , a k E,h ∼ π E,h · x k h . Then, E h b ℓ π out ,k h Q k h − b ℓ π out ,k h b Q π E h F k−1,h i =L π out h π k h , b Q π E h − Q k h , whereF k−1,h contains all randomness from previous layers and from the firstk− 1samples at layerh. Conditionally onF k−1,h , the distributiond π out h is fixed because it only depends on the already computed policiesπ out,1 ,...,π out,h−1 , andQ k h andπ k h are also fixed because they are functions of the previous samples at layerh. Therefore, the increments M k h =L π out h π k h , b Q π E h − Q k h − b ℓ π out ,k h Q k h − b ℓ π out ,k h b Q π E h form a martingale difference sequence ink, for each fixedh∈ [H]. Moreover, since b Q π E h belongs to the cover andQ k h is a convex combination of cover elements, both functions are bounded in sup-norm byQ max . Thus,∥ b Q π E h −Q k h ∥ ∞ ≤ 2Q max , and both|L π out h (π k h , b Q π E h − Q k h )| and| b ℓ π out ,k h (Q k h ) − b ℓ π out ,k h ( b Q π E h )| are at most2∥ b Q π E h − Q k h ∥ ∞ ≤ 4Q max . Hence |M k h |≤ 8Q max almost surely. By the Azuma-Hoeffding inequality and a union bound overh∈ [H], with probability at least 1− δ, for all h∈ [H], 1 K K X k=1 M k h ≤ 8Q max r 2 log(2H/δ) K . Summing overh∈ [H]incurs an extraHfactor in the upper bound. Finally, usingQ k h = P Q∈C r (Q h ) w k h (Q)Qand taking r = ε/(4H), we obtain from Eq. (24) J π E − J π out ≤ 1 K H X h=1 K X k=1 X Q∈C r (Q h ) w k h (Q) b ℓ π out ,k h (Q)− b ℓ π out ,k h b Q π E h + 8HQ max r 2 log(2H/δ) K + 2Hr = 1 K H X h=1 R w h + 8HQ max r 2 log(2H/δ) K + ε 2 ≤ H K max h∈[H] R w h + 8HQ max r 2 log(2H/δ) K + ε 2 , which gives the stated form. 60Appendix table of contents H.2 Proof of Theorem H.1 (Sample Complexity Guarantee for Q-OVI) Proof of Theorem H.1. From the decomposition proven in Lemma H.1, with probability at least 1− δ, we have J π E − J π out ≤ H K max h∈[H] R w h + 8HQ max r 2 log(2H/δ) K + ε 2 . Thus, it remains to control the regretR w h for eachh ∈ [H]. The update in Algorithm 3 can be written for any Q∈C ε/(4H) (Q h ) as w k+1 h (Q)∝ w k h (Q)e η ( Q ( x k h ,a k E,h ) −Q ( x k h ,π k h )) . Equivalently, this is exponential weights with sampled losses b ℓ π out ,k h . Moreover, by the definition of the function class, eachQ h ∈ Q h satisfies∥Q h ∥ ∞ ≤ Q max , so| b ℓ π out ,k h (Q h )| ≤ 2Q max for allQ h ∈ Q h . IfN max ε/(4H) (Q) = 1 , every stagewise cover is a singleton, so the prescribed learning rate isη = 0butw k h assigns unit mass to b Q π E h for everyhand k. Hence,R w h = 0for allh, and the regret bound below holds directly without invoking Lemma E.6. We may therefore suppose thatN max ε/(4H) (Q)≥ 2, soη > 0. For any stage with a singleton cover, the same zero-regret conclusion holds. Fix a stageh∈ [H]with a non-singleton cover and apply Lemma E.6 to the simplexV = ∆(C ε/(4H) (Q h ))with loss vectorsℓ k (Q) = b ℓ π out ,k h (Q). The update above is mirror descent with the negative entropy regularizer, whose Bregman divergenceDis the KL divergence. We use as comparator b Q π E h ∈C ε/(4H) (Q h ) . Sincew 1 h is uniform over the cover, D(e b Q π E h ,w 1 h )≤ logN ε/(4H) (Q h ) , wheree b Q π E h is the unit vector at b Q π E h . Thus, using the bounds∥ℓ k ∥ ∞ ≤ 2Q max and λ≥ 1/2, Lemma E.6 gives R w h ≤ logN ε/(4H) (Q h ) η + 4ηKQ 2 max . UsingR w h = 0for singleton stagewise covers and substitutingη = q logN max ε/(4H) (Q)/(KQ 2 max )in the preceding bound for non-singleton covers, we obtain max h∈[H] R w h ≤ 5 q KQ 2 max logN max ε/(4H) (Q). Combining the decomposition above with the regret bound gives J π E − J π out ≤ 5H s Q 2 max logN max ε/(4H) (Q) K + 8HQ max r 2 log(2H/δ) K + ε 2 ≤ 5 + 8 √ 2 HQ max v u u t log N max ε/(4H) (Q)2H/δ K + ε 2 . Choosing K so that K ≥ 4 5 + 8 √ 2 2 H 2 Q 2 max log N max ε/(4H) (Q)2H/δ ε 2 makes the first term in the display above at mostε/2, and thereforeJ π E − J π out ≤ εwith probability at least1− δ. Since Algorithm 3 makes one expert query for each pair (k,h)∈ [K]× [H], the total number of expert queries is HK =O H 3 Q 2 max log N max ε/(4H) (Q)H/δ ε −2 . H.3 Learning a Stationary Policy with Q-OVI In this section, we show thatQ-OVIcan be used to learn a stationary policy that competes with the expert in the discounted infinite-horizon setting. We formalize the setting next. 61Appendix table of contents Infinite-horizon MDPs. We consider a discounted MDPM = (X,A,r,P,γ,ν 0 ), whereXandAare finite state and action spaces,r : X ×A → [0, 1]is the reward function,P : X ×A → ∆(X )is the transition kernel,γ ∈ [0, 1)is the discount factor, andν 0 ∈ ∆(X )is the initial distribution. A policy is a mappingπ : X → ∆(A). Rolling outπ generates a trajectory(x h ,a h ) ∞ h=0 by drawingx 0 ∼ ν 0 ,a h ∼ π(·|x h ), andx h+1 ∼ P (·|x h ,a h )for allh≥ 0. For any state-action pair (x,a)∈X ×A, the discounted state-action value function is Q π γ (x,a) = E π " ∞ X h=0 γ h r(x h ,a h ) x 0 = x,a 0 = a # . For any functionQ : X ×A → Rand policyπ, we useQ(x,π)to denoteE a∼π(·|x) [Q(x,a)]. The discounted state occupancy measure of π is denoted by d π γ ∈ ∆(X ) and defined by d π γ (x) = (1− γ) ∞ X h=0 γ h P π [x h = x]. Finally, we denote the normalized expected return of π by J π γ = (1− γ)E π " ∞ X h=0 γ h r(x h ,a h ) # . Infinite-horizonQ-OVIand guarantees. For simplicity, we consider finite classesQin this section. The result can be extended to infinite classes via covering numbers, as in the finite-horizon case. We study the following infinite-horizon version ofQ-OVI. For simplicity, we assume direct access to samples fromd π k γ . Under ordinary trajectory access, Algorithm 4 Infinite-horizon Q-OVI 1: input: Learning rate η, iterations K, finite classQ. 2: Set w 1 (Q) = 1/|Q| for all Q∈Q. 3: For any (x,a)∈X ×A, set Q 1 (x,a) = P Q∈Q w 1 (Q)Q(x,a). 4: For any x∈X , set π 1 (·|x)∈ arg max p∈∆(A) ⟨p,Q 1 (x,·)⟩. 5: for k = 1,...,K do 6:Sample x k ∼ d π k γ , a E k ∼ π E (·|x k ). 7:For any Q∈Q, set w k+1 (Q)∝ w k (Q)e η(Q(x k ,a E k )−Q(x k ,π k )) . 8:For any (x,a)∈X ×A, set Q k+1 (x,a) = P Q∈Q w k+1 (Q)Q(x,a). 9:For any x∈X , set π k+1 (·|x)∈ arg max p∈∆(A) ⟨p,Q k+1 (x,·)⟩. 10: Draw I ∼ Unif([K]) and output π out = π I . each sample can instead be generated by a geometric rollout, yielding expected environment-interaction complexity O(K/(1− γ)), an additional factor of 1/(1− γ). The algorithm still makes one expert query per round. The resulting guarantee is as follows. Theorem H.2. AssumeQ π E γ ∈Q,|Q|≥ 2and∥Q∥ ∞ ≤ (1−γ) −1 for allQ∈Q. For anyε∈ (0, 1), run Algorithm 4 with η = (1− γ) r log|Q| K , K =O log|Q| (1− γ) 2 ε 2 ! . Then, the algorithm outputs a policy π out such that E J π E γ − J π out γ ≤ ε. Proof of Theorem H.2. Since π out = π I with I ∼ Unif([K]), it is enough to control the average gap. E J π E γ − J π out γ = 1 K K X k=1 E J π E γ − J π k γ . 62Appendix table of contents For any fixedk ∈ [K], the performance difference lemma in discounted MDPs (Moulin et al., 2025a, Lemma 1) gives J π E γ − J π k γ = X x∈X d π k γ (x) Q π E γ (x,·),π E (·|x)− π k (·|x) = X x∈X d π k γ (x)⟨Q k (x,·),π E (·|x)− π k (·|x)⟩ + X x∈X d π k γ (x) Q π E γ (x,·)− Q k (x,·),π E (·|x)− π k (·|x) . Because π k (·|x) is greedy with respect to Q k (x,·), the first term is nonpositive. Therefore, J π E γ − J π k γ ≤ X x∈X d π k γ (x) Q π E γ (x,·)− Q k (x,·),π E (·|x)− π k (·|x) . Define the sampled gains g k (Q) = Q x k ,a E k − Q(x k ,π k ), x k ∼ d π k γ , a E k ∼ π E (·|x k ). LetF k−1 be the history before drawing(x k ,a E k ) , that is, theσ-field generated by the previous samples(x j ,a E j ) j<k and any additional algorithmic randomness up to roundk− 1. Although the distributiond π k γ changes withk, conditional onF k−1 , the weight vectorw k , and henceQ k ,π k , andd π k γ , are fixed. The fresh sample is then drawn conditionally as x k ∼ d π k γ and a E k ∼ π E (·|x k ). Hence, E g k Q π E γ − g k (Q k ) F k−1 = X x∈X d π k γ (x) Q π E γ (x,·)− Q k (x,·),π E (·|x)− π k (·|x) . Taking expectations and summing over k gives K X k=1 E J π E γ − J π k γ ≤ E " K X k=1 g k Q π E γ − g k (Q k ) # . Let w ⋆ = e Q π E γ be the unit vector at Q π E γ . Since Q k (x,a) = P Q∈Q w k (Q)Q(x,a), the previous display becomes K X k=1 E J π E γ − J π k γ ≤ E K X k=1 X Q∈Q (w ⋆ (Q)− w k (Q))g k (Q) . The exponential weights update is mirror descent over the simplexV = ∆(Q)with loss vectorsℓ k (Q) =−g k (Q). The regularizer is negative entropy, whose Bregman divergenceDis the KL divergence. We use the comparatorw ⋆ , and sincew 1 is uniform overQ, we haveD(w ⋆ ,w 1 )≤ log|Q|. Moreover,∥ℓ k ∥ ∞ ≤ 2(1− γ) −1 , and the negative entropy is 1-strongly convex in the ℓ 1 -norm. Thus, Lemma E.6 yields, pathwise, K X k=1 X Q∈Q (w ⋆ (Q)− w k (Q))g k (Q)≤ log|Q| η + 2ηK (1− γ) 2 . Assuming|Q|≥ 2, we can set η = (1− γ) p log|Q|/K to obtain E J π E γ − J π out γ ≤ 3 s log|Q| K(1− γ) 2 . Choosing K ≥ 9 log|Q| (1−γ) 2 ε 2 makes the right-hand side at most ε. 63Appendix table of contents I Breaking the Offline Lower Bound with Coverage This section shows that the offline lower bound does not apply when the expert is sufficiently exploratory, as measured by a coverage coefficient introduced in Assumptions I.1 and I.2 below. We prove this through a generalized analysis ofOVI. Assumption I.1 (L ∞ -coverage). Assume an algorithmAlgoutputs a VI policyπ out in a classΠ Alg such that, for some finite constant C ∞ , any stage h, and any state x, sup π∈Π Alg d π h (x)/d π E h (x)≤ C ∞ . Assumption I.2 (L 1 -coverage). Assume an algorithmAlgthat outputs a VI policyπ out in a classΠ Alg such that, for some finite constant C 1 , sup π∈Π Alg H X h=1 X x∈X (d π h (x)) 2 d π E h (x) ≤ C 1 . For both cases, we use the convention0/0 = 0. We note that Assumption I.1 implies Assumption I.2 withC 1 ≤ HC ∞ , but we keep the two assumptions separate because Theorem I.3 tracks both dependencies. Under this setting our main theorem reads as follows. Theorem I.1. Letε,δ ∈ (0, 1)and Assumption 2.1 hold. Assume the expert policyπ E is optimal and that the algorithmSPOIL(Moulin et al., 2025a) satisfies Assumption I.1. For every radiusr > 0, writeN max r (Q) : = max h∈[H] N r (Q h ,∥·∥ ∞ ) , and choose a radiusr ε = O(ε 2 )small enough. Then,SPOILreturns anε-optimal policy with probability at least1− δusing e O(C 4 ∞ H 5 Q 4 max log(A) log(N max r ε (Q)δ −1 )ε −4 )precollected expert data. Moreover, if the classQ is convex the bound improves to e O(C 2 ∞ H 3 Q 2 max log(N max r ε (Q)δ −1 )ε −2 ). Theorem I.1 follows from the stronger Theorem I.3 proven below, which also gives a bound under Assumption I.2. I.1 OVI with Arbitrary Sampling Distributions We first prove a generalization of Algorithm 1 in which the state sampling distribution at stagehmay differ fromd π out h . This result will be used several times below. Algorithm 5 OVI with arbitrary state sampling distribution d 1:input: Sampling distributionsd = d h H h=1 , learning-rate scheduleη k K+1 k=1 , iterationsK, number of expert queries per stage n E . 2: for h = 1,...,H do 3:Create the stage-h dataset: for i∈ [n E ], sample x i h ∼ d h and query a i E,h ∼ π E,h (·|x i h ). 4:Initialize π 1 h = Unif(A). 5:for k = 1,...,K do 6:Set Q k h ∈ arg max Q h ∈Q h P n E i=1 (Q h (x i h ,a i E,h )− Q h (x i h ,π k h )). 7:Set π k+1 h (a|x)∝ π 1 h (a|x) exp(η k+1 P k k ′ =1 Q k ′ h (x,a)). 8:Set the output policy at stage h to π out,h (a|x) = 1 K P K k=1 π k h (a|x). Theorem I.2 (Sample complexity forOVIwith arbitrary sampling distributions). For eachh∈ [H], letF h−1 denote the history available before the stage-hsamples are drawn. Fix any sequence of state sampling distributionsd =d h H h=1 , where each d h may be random but isF h−1 -measurable, and run Algorithm 5 with K,n E ∈ N and the FTRL learning- rate schedule η k = s logA kQ 2 max for every k ≥ 1. For eachh ∈ [H], assume that, conditionally onF h−1 , the pairs(x i h ,a i E,h ) n E i=1 are independent, withx i h ∼ d h and a i E,h ∼ π E,h (·|x i h ). For every radiusr > 0, writeN max r (Q) : = max h∈[H] N r (Q h ,∥·∥ ∞ ). Letε,δ ∈ (0, 1)and choose a radiusr ε = O(ε 2 )small enough. Fix any comparator policyπ ′ such thatQ π ′ h ∈ Q h for everyh ∈ [H]. For the policy π out returned by Algorithm 5, we recall the definition L d h π out,h ,Q π ′ h = X x∈X d h (x) D Q π ′ h (x,·),π E,h (·|x)− π out,h (·|x) E . 64Appendix table of contents IfQ is convex, then with probability at least 1− δ, H X h=1 L d h π out,h ,Q π ′ h ≤ e O r H 2 Q 2 max logA K + s H 2 Q 2 max log N max r ε (Q)/δ n E + ε . IfQ is not assumed to be convex, then with probability at least 1− δ, H X h=1 L d h π out,h ,Q π ′ h ≤ e O r H 2 Q 2 max logA K + s KH 2 Q 2 max log N max r ε (Q)/δ n E + ε . In particular, up to logarithmic factors, the convex bound is of orderεby takingK≳ H 2 Q 2 max log(A)/ε 2 andn E ≳ H 2 Q 2 max log(N max r ε (Q)/δ)/ε 2 . In the nonconvex case, the same choice ofKandn E ≳ KH 2 Q 2 max log(N max r ε (Q)/δ)/ε 2 suffices. Proof of Theorem I.2. Recall the definitions of the empirical objective and the uniform estimation error b L d h (π h ,Q h ) : = n −1 E n E X i=1 Q h x i h ,a i E,h − Q h x i h ,π h , ∆ d (π) : = max h∈[H] sup Q h ∈Q h b L d h (π h ,Q h )−L d h (π h ,Q h ) . Fixh∈ [H]. SinceQ π ′ h ∈Q h , the first inequality below follows from the definition of∆ d (π k ). The second inequality follows from the empirical maximization property definingQ k h , and the last inequality uses the definition of∆ d (π k ) again, now with Q k h : K X k=1 L d h π k h ,Q π ′ h ≤ K X k=1 b L d h π k h ,Q π ′ h + K X k=1 ∆ d π k ≤ K X k=1 b L d h π k h ,Q k h + K X k=1 ∆ d π k ≤ K X k=1 L d h π k h ,Q k h + 2 K X k=1 ∆ d π k . We now control the first term on the right-hand side using the FTRL regret bound. Fixx∈Xand define the loss vectors ℓ k,h,x (a) : =−Q k h (x,a). Since π 1 h is uniform, the update in Algorithm 5 implies that, for every k ≥ 1, π k h (a|x) = exp η k P j<k Q j h (x,a) P a ′ ∈A exp η k P j<k Q j h (x,a ′ ) = exp −η k P j<k ℓ j,h,x (a) P a ′ ∈A exp −η k P j<k ℓ j,h,x (a ′ ) . Thus, for this fixedhandx, the sequence(π k h (·|x)) K k=1 is exactly the FTRL sequence of Lemma E.7 with comparator π E,h (·|x). Moreover,∥ℓ k,h,x ∥ ∞ ≤ Q max andη k = p logA/(kQ 2 max ) . Applying Lemma E.7 pointwise inxand then averaging over d h , for any K ∈ N, we obtain K X k=1 L d h π k h ,Q k h = X x∈X d h (x) K X k=1 Q k h (x,·),π E,h (·|x)− π k h (·|x) ≤ 3 p Q 2 max K logA, where the last inequality uses thatd h is a probability distribution. Compared with the proof of Theorem F.1, note that we use FTRL rather than online mirror descent. 15 15 This change gives anytime bounds that hold for every K, which is needed because we invoke Theorem I.2 with different values of K. 65Appendix table of contents It remains to control the estimation error. Since the learning rate varies with k, define the policy class Π Q : = n π :∃m∈0,...,K,∀h,∃Q 1 h ,...,Q m h ∈Q h , π h (a|x) = softmax η m+1 P m j=1 Q j h (x,·) a o . For eachh, letΠ Q,h : =π h : π ∈ Π Q . The iterates generated by Algorithm 5 satisfyπ k ∈ Π Q for everyk ∈ [K], by taking m = k− 1. For everyh, condition onF h−1 . Thend h is fixed, and the pairs(x i h ,a i E,h ) n E i=1 are independent, withx i h ∼ d h and a i E,h ∼ π E,h (·|x i h ). Applying the uniform concentration bound in Lemma E.2 withΠ h = Π Q,h gives that, for any radius r > 0, with probability at least 1− δ, K X k=1 ∆ d π k ≤ K sup π∈Π Q ∆ d (π)≤ K 4r + Q max v u u t 8 log 2 P H h=1 N r (Q h × Π Q,h ,ρ)/δ n E . Therefore, dividing by K and usingL d h (π out,h ,Q π ′ h ) = 1 K P K k=1 L d h (π k h ,Q π ′ h ), we obtain H X h=1 L d h π out,h ,Q π ′ h ≤ 3 r H 2 Q 2 max logA K + 8Hr + 2HQ max v u u t 8 log 2 P H h=1 N r (Q h × Π Q,h ,ρ)/δ n E . Next, we bound the covering number of the product class. Chooser = ε/(8H). The product-cover lemmas in Lemma E.4 and Lemma E.3 are stated for a fixed learning rateη, but their proofs apply almost verbatim to the present class. For policies represented bymfunctions, the factorηmis replaced byη m+1 m. Thus, they naturally lead to a covering number with radius ε 16H max1,Q max max 1≤m≤K mη m+1 . IncreasingKby an absolute constant if necessary, we may assumeK logA≥ 1. Then the learning-rate schedule gives Q max max 1≤m≤K mη m+1 = K r logA K + 1 ≤ p K logA,max 1,Q max max 1≤m≤K mη m+1 ≤ p K logA. Thus, for the parameter choices below, it is enough to use the smaller radius r ε : = ε 16H √ K logA , which only enlarges the covering number. After the choices of K below, this radius satisfies r ε =O(ε 2 ). Convex case. IfQ is convex, then each projectionQ h is convex. Hence, by Lemma E.4, for every h∈ [H], N r (Q h × Π Q,h ,ρ)≤ (K + 1)N r ε (Q h ,∥·∥ ∞ ) 2 . Plugging this into the preceding estimation bound gives H X h=1 L d h π out,h ,Q π ′ h ≤ 3 r H 2 Q 2 max logA K + ε + 2HQ max v u u t 8 log 2H(K + 1) N max r ε (Q) 2 /δ n E . Thus, the convex bound becomes e O r H 2 Q 2 max logA K + s H 2 Q 2 max log N max r ε (Q)/δ n E + ε . In particular, choosing K ≥ 9H 2 Q 2 max logA ε 2 , n E ≥ 32H 2 Q 2 max ε 2 log 2H(K + 1) N max r ε (Q) 2 δ ! 66Appendix table of contents makes the three terms in the previous display of order ε. Nonconvex case. For arbitrary, not necessarily convex, classesQ, Lemma E.3 instead gives, for every h∈ [H], N r (Q h × Π Q,h ,ρ)≤ (K + 1)N r ε (Q h ,∥·∥ ∞ ) K+1 . Therefore, H X h=1 L d h π out,h ,Q π ′ h ≤ 3 r H 2 Q 2 max logA K + ε + 2HQ max v u u t 8 log 2H(K + 1) N max r ε (Q) K+1 /δ n E , or, equivalently, e O r H 2 Q 2 max logA K + s KH 2 Q 2 max log N max r ε (Q)/δ n E + ε . With the same choice of K as above, taking n E ≥ 32H 2 Q 2 max ε 2 log 2H(K + 1) N max r ε (Q) K+1 δ ! = e O KH 2 Q 2 max log N max r ε (Q)/δ ε 2 ! makes the three terms of the nonconvex bound of order ε. This concludes the proof. I.2 Proof of Theorem I.1 (Offline IL with Coverage and Optimal Expert) We prove Theorem I.1 through the stronger Theorem I.3. The sharper statement also gives a guarantee under Assump- tion I.2 alone in terms of the L 1 -coverage coefficient C 1 , which can be much smaller than HC ∞ . Theorem I.3. Letε,δ ∈ (0, 1). Let Assumption 2.1 hold. Assume the expert policyπ E is optimal and thatSPOIL (Moulin et al., 2025a) satisfies at least one of Assumptions I.1 and I.2. RunSPOIL(i.e., Algorithm 5 withd = d π E ) with the FTRL learning-rate schedule η k = s logA kQ 2 max for every k ≥ 1. For every radiusr > 0, writeN max r (Q) : = max h∈[H] N r (Q h ,∥·∥ ∞ ). Choose radiir (1) ε =O(ε 4 ) andr (∞) ε =O(ε 2 ) small enough. IfQis arbitrary, theC 1 -dependent choice below guaranteesJ π E − J π out ≤ εwith probability at least 1− δ under Assumption I.2, while the C ∞ -dependent choice guarantees the same under Assumption I.1: K (1) = e O C 2 1 H 2 Q 4 max logA ε 4 ,n (1) E = e O C 4 1 H 4 Q 8 max log(A) log N max r (1) ε (Q)/δ ε 8 , K (∞) = e O C 2 ∞ H 2 Q 2 max logA ε 2 ,n (∞) E = e O C 4 ∞ H 4 Q 4 max log(A) log N max r (∞) ε (Q)/δ ε 4 . If both coverage assumptions hold, choosing the better of the two branches gives total expert sample complexity Hn E = e O min C 4 1 H 5 Q 8 max log(A) log N max r (1) ε (Q)/δ ε 8 , C 4 ∞ H 5 Q 4 max log(A) log N max r (∞) ε (Q)/δ ε 4 . IfQis convex, the same branch-wise guarantees hold under their respective coverage assumptions, with the same choices of K (1) and K (∞) , but with n (1) E = e O C 2 1 H 2 Q 4 max log N max r (1) ε (Q)/δ ε 4 ,n (∞) E = e O C 2 ∞ H 2 Q 2 max log N max r (∞) ε (Q)/δ ε 2 . 67Appendix table of contents If both coverage assumptions hold, choosing the better of the two branches gives total expert sample complexity Hn E = e O min C 2 1 H 3 Q 4 max log N max r (1) ε (Q)/δ ε 4 , C 2 ∞ H 3 Q 2 max log N max r (∞) ε (Q)/δ ε 2 . Here, the e Onotation in each branch hides logarithmic factors inH,Q max , and the corresponding coverage coefficient. Proof of Theorem I.3. Since the expert is optimal,π E is greedy with respect toQ π E at every stagehand state x∈ supp(d π E h ). Hence, for any policy π, stage h, and state x∈ supp(d π E h ), ⟨Q π E h (x,·),π E,h (·|x)− π h (·|x)⟩≥ 0. This nonnegativity is the only point at which expert optimality is used. It lets us remove absolute values in the change-of-measure arguments below. We prove two independent bounds: one under Assumption I.2, in terms ofC 1 , and one under Assumption I.1, in terms ofC ∞ . When both assumptions hold, the guarantee takes the better of the two. Bounds scaling with C 1 . Let g h (x) : =⟨Q π E h (x,·),π E,h (·|x)− π out,h (·|x)⟩. Finiteness ofC 1 implies that, for everyhandx,d π out h (x) = 0wheneverd π E h (x) = 0, so the following change of measure is well defined. The expert value function satisfiesQ π E h (x,a)∈ [0,Q max ]for everyh,x,a. Together with the nonnegativity above, this gives0≤ g h (x)≤ Q max , and henceg h (x) 2 ≤ Q max g h (x)for everyx∈ supp(d π E h ). By the performance difference lemma (Lemma E.9), the Cauchy–Schwarz inequality, and Assumption I.2, we have J π E − J π out = H X h=1 X x∈X d π out h (x)g h (x) ≤ v u u t H X h=1 X x∈X (d π out h (x)) 2 d π E h (x) v u u t H X h=1 X x∈X d π E h (x)g h (x) 2 ≤ v u u t C 1 Q max H X h=1 X x∈X d π E h (x)g h (x). The last summation is exactly the loss controlled by Theorem I.2 with d = d π E and π ′ = π E : H X h=1 X x∈X d π E h (x)g h (x) = H X h=1 L π E h (π out,h ,Q π E h ). For nonconvexQ, applying Theorem I.2 with accuracy parameterε 0 and associated covering radiusr ε 0 =O(ε 2 0 ) gives, with probability at least 1− δ, J π E − J π out ≤ e O v u u u t C 1 Q max r H 2 Q 2 max logA K + s KH 2 Q 2 max n E log N max r ε 0 (Q)/δ + ε 0 . Takingε 0 = ε 2 /(C 1 Q max )and choosingr (1) ε ≤ r ε 0 , the monotonicity of covering numbers and the absorption of logarithmic factors in H , Q max , and C 1 into e O yield J π E − J π out ≤ e O 4 r C 2 1 H 2 Q 4 max logA K + 4 v u u t KC 2 1 H 2 Q 4 max log N max r (1) ε (Q)/δ n E + ε . 68Appendix table of contents Thus theC 1 -tuned nonconvex choice in the theorem makes the right-hand side at mostO(ε). IfQis convex, the second term in Theorem I.2 has no factor K. Repeating the same calculation gives J π E − J π out ≤ e O 4 r C 2 1 H 2 Q 4 max logA K + 4 v u u t C 2 1 H 2 Q 4 max log N max r (1) ε (Q)/δ n E + ε , which gives the improved convex choice of n (1) E . Bounds scaling withC ∞ . TheC ∞ argument gives a better dependence on1/εat the cost of replacingC 1 by the stronger coverage coefficient C ∞ . Since g h (x)≥ 0, Assumption I.1 gives J π E − J π out = H X h=1 X x∈X d π out h (x)g h (x) ≤ max y∈X max h∈[H] d π out h (y) d π E h (y) H X h=1 X x∈X d π E h (x)|g h (x)| ≤ C ∞ H X h=1 X x∈X d π E h (x)g h (x) = C ∞ H X h=1 L π E h (π out,h ,Q π E h ). Applying Theorem I.2 withd = d π E ,π ′ = π E , and accuracy parameterε 0 = ε/C ∞ , and choosingr (∞) ε ≤ r ε 0 for the associated radius r ε 0 =O(ε 2 0 ), the monotonicity of covering numbers gives for nonconvexQ that J π E − J π out ≤ e O r C 2 ∞ H 2 Q 2 max logA K + v u u t KC 2 ∞ H 2 Q 2 max log N max r (∞) ε (Q)/δ n E + ε . This is at mostO(ε)for theC ∞ -tuned nonconvex choice ofK (∞) andn (∞) E in the theorem. IfQis convex, the same calculation with the convex version of Theorem I.2 gives J π E − J π out ≤ e O r C 2 ∞ H 2 Q 2 max logA K + v u u t C 2 ∞ H 2 Q 2 max log N max r (∞) ε (Q)/δ n E + ε , which yields the stated convex choice ofn (∞) E . Finally,SPOILusesn E expert samples at each of theHstages, so the total number of precollected expert samples isHn E . Multiplying the branch-wise bounds onn E byHgives the two sample-complexity displays in the theorem. 69Appendix table of contents J On the Benefits of Mixing Expert and Learner Trajectories In this section, we analyze the popular technique of mixing expert and learner data to create the empirical objective in LM distillation (Agarwal et al., 2024; Li et al., 2026a) and show that it leads to representational benefits. We develop an algorithm that is statistically efficient when the classQsatisfies eitherQ π E -realizability or theQ Π Q -realizability condition introduced by Moulin et al. (2025a), without knowing a priori which representational condition holds. To obtain the anytime regret bounds needed in this section, we use a slightly different version of theQ Π Q -realizability condition. Compared with Moulin et al. (2025a), our version uses FTRL rather than OMD and allows the softmax weights to depend on a fixed learning-rate schedule η 1:K+1 . Assumption J.1 (Q Π Q -realizability). FixK = poly(H, logA,Q max ,ε −1 )and learning ratesη 1:K+1 ∈ R K+1 , and define Π Q : = n π :∀h∈ [H],∃m h ≤ K,∃ Q h j m h j=1 ⊂Q h , π h (a|x) = softmax η m h +1 P m h j=1 Q h j (x,·) a o . The classQ satisfies Q Π Q -realizability if Q π ∈Q for every π ∈ Π Q . For each stageh, writeΠ Q,h : =π h : π ∈ Π Q . This notation is always understood with the same value ofKand the same learning-rate scheduleη 1:K+1 as the algorithm under consideration. This is a slightly broader policy class than the version with a single common value ofmshared by all stages. We use it because the hybrid policies in the proof may take different stages from different FTRL rounds, so the number of accumulated Q-functions can depend on h. This assumption requires realizing theQ-functions of many policies, whereasQ π E -realizability only requires realizing the expert’sQ-function. Since the expert need not belong toΠ Q ,Q Π Q -realizability does not implyQ π E -realizability. Nevertheless, the upper bound of Moulin et al. (2025a) implies that, underQ Π Q -realizability, there exists a policy in Π Q that is ε-optimal with respect to π E . As shown by Moulin et al. (2025a), offline IL is possible underQ Π Q -realizability, and therefore interactive IL is possible as well. However, Algorithms 1 and 3 do not directly use this condition. We instead modify the state-sampling rule in Algorithm 1: for eachh∈ [H], we sample states from a mixture of the expert occupancyd π E h and the learner occupancyd π out h . Sampling from the former is possible in the interactive setting by rolling in with actions queried from the expert. Thus, Algorithm 6 is an instance of Algorithm 5 with sampling distribution d h = (1− α)d π out h + αd π E h , for an appropriate choice ofα∈ [0, 1]. The mixture is the key adaptive device: thed π out component gives coverage of the learner states needed underQ π E -realizability, while thed π E component keeps enough expert-state mass for theQ Π Q argument. The change relative to Algorithm 5 is highlighted in orange. We have the following result. Algorithm 6 RAOVI: Representation-Adaptive OVI 1: input: Mixture parameter α∈ [0, 1], learning rates (η k ) K+1 k=1 , iterations K, dataset size per stage n E . 2: for h = 1,...,H do 3:Create the stage-h dataset: for i∈ [n E ], sample x i h ∼ (1− α)d π out h + αd π E h , a i E,h ∼ π E,h (·|x i h ). 4:Initialize π 1 h = Unif(A). 5:for k = 1,...,K do 6:Set Q k h ∈ arg max Q h ∈Q h P n E i=1 (Q h (x i h ,a i E,h )− Q h (x i h ,π k h )). 7:Set π k+1 h (a|x)∝ π 1 h (a|x) exp(η k+1 P k k ′ =1 Q k ′ h (x,a)). 8:Set π out,h (a|x) = 1 K P K k=1 π k h (a|x). Theorem J.1. Let the expert policy π E be optimal, ε∈ (0, min1, 2HQ max ), and δ ∈ (0, 1). Run Algorithm 6 with α = 1− ε 2HQ max , η k = s logA kQ 2 max for every k ≥ 1. 70Appendix table of contents Then, with probability at least 1− δ, each of the following guarantees holds under the corresponding condition. 1. Under Q π E -realizability (Assumption 2.1), J π E − J π out ≤ ε is guaranteed by the choices K = e O H 4 Q 4 max logA ε 4 , n E = e O H 4 Q 4 max log 2H max h∈[H] N ε 2 /(8H 2 Q max ) (Q h × Π Q,h ,ρ)/δ ε 4 ! . 2. Under Q Π Q -realizability (Assumption J.1), J π E − J π out ≤ ε is guaranteed by the choices K = e O H 2 Q 2 max logA ε 2 , n E = e O H 2 Q 2 max log 2H max h∈[H] N ε/H (Q h × Π Q,h ,ρ)/δ ε 2 ! . The total number of expert queries is at mostH 2 n E . Thus, without knowing which condition holds, one can chooseK andn E to be the componentwise maximum of the two displayed requirements, and the corresponding guarantee applies under either condition. We remark that the rates in theQ π E -realizable case are not optimal. It is an interesting open question whether they can be improved while maintaining the faster rates in the Q Π Q -realizable case. Proof of Theorem J.1. We analyze each case separately. Throughout, let d h = αd π E h + (1− α)d π out h . As in the previous cases,d h is measurable with respect to the history available before sampling at stageh, and conditionally on this history, the pairs(x i h ,a i E,h ) n E i=1 are independent withx i h ∼ d h anda i E,h ∼ π E,h (·|x i h ), as required by Lemma E.2. Obtaining one labeled sample at stagehrequires at mosthexpert queries, including the queries used to roll in under the expert. Summing over then E samples at each stage gives at mostn E P H h=1 h≤ H 2 n E expert queries. Case 1:Q π E -realizability. For everyh ∈ [H]andx ∈ X, defineg h (x) : = ⟨Q π E h (x,·),π E,h (·|x)− π out,h (·|x)⟩. A one-step deviation argument using expert optimality givesg h (x)≥ 0ford π E h -almost everyx. Therefore, the definition of d h and the performance difference lemma (Lemma E.9) give H X h=1 E x∼d h [g h (x)] = (1− α)(J π E − J π out ) + α H X h=1 E x∼d π E h [g h (x)] ≥ (1− α)(J π E − J π out ). Consequently, J π E − J π out ≤ 1 1− α H X h=1 X x∈X d h (x)⟨Q π E h (x,·),π E,h (·|x)− π out,h (·|x)⟩ = 1 1− α H X h=1 L d h (π out,h ,Q π E h ) ≤ 1 1− α 3 r H 2 Q 2 max logA K + 8Hr + 2HQ max v u u t 8 log 2 P H h=1 N r (Q h × Π Q,h ,ρ)/δ n E , where the last inequality holds with probability at least1− δby rederiving the proof of Theorem I.2 with sampling distributiond h = αd π E h + (1− α)d π out h and comparatorπ ′ = π E , stopping at the intermediate product-cover bound, for anyr > 0. Takingr = ε 2 /(8H 2 Q max )gives8Hr = ε 2 /(HQ max )and covering radiusε 2 /(8H 2 Q max )in the logarithm. Withα = 1−ε/(2HQ max ), the choices ofKandn E in theQ π E -realizable branch make the right-hand side at mostO(ε). Case 2:Q Π Q -realizability. The subtle point is that we should not apply the performance difference lemma directly withQ π out , becauseπ out is a pointwise average of softmax policies and need not belong toΠ Q . Instead, we represent 71Appendix table of contents the trajectory distribution ofπ out as a mixture over stagewise hybrids of the iterates. LetI = (I 1 ,...,I H )be sampled uniformly from [K] H , and define the hybrid policy π I by π I h = π I h h for every h∈ [H]. We now justify carefully why these hybrids are related to the averaged policy. Letτ = (x 1 ,a 1 ,...,x H ,a H ,x H+1 ) be a trajectory under policy π out . By the definition of π out , we have P π out (τ ) = ν 0 (x 1 ) H Y h=1 [π out,h (a h |x h )P h (x h+1 |x h ,a h )] = ν 0 (x 1 ) H Y h=1 " 1 K K X k h =1 π k h h (a h |x h ) ! P h (x h+1 |x h ,a h ) # = 1 K H X i 1 ,...,i H ∈[K] ν 0 (x 1 ) H Y h=1 π i h h (a h |x h )P h (x h+1 |x h ,a h ) = E I h P π I (τ ) i . The third line is where we use that the coordinatesI 1 ,...,I H are sampled independently. If one sampled a single common index for all stages, the resulting average of products would not generally equal the product of averages definingπ out . Therefore, for any trajectory-level functionF, and in particular for the cumulative rewardF (τ ) = P H h=1 r h (x h ,a h ), we can average over the finite trajectory space to obtain E π out [F (τ )] = X τ P π out (τ )F (τ ) = E I " X τ P π I (τ )F (τ ) # = E I h E π I [F (τ )] i . Taking F to be the cumulative reward gives J π out = E I h J π I i . For everyI, the hybrid policyπ I belongs toΠ Q . Indeed, at each stageh, choosem h = I h − 1, the functions Q 1 h ,...,Q I h −1 h ∈ Q h (empty ifI h = 1), andη I h = η m h +1 . By Assumption J.1, we haveQ π I ∈ Q, and hence Q π I h ∈Q h for every h. Applying the performance difference lemma (Lemma E.9) to each hybrid policy gives J π E − J π out = E I h J π E − J π I i = E I " H X h=1 X x∈X d π E h (x) D Q π I h (x,·),π E,h (·|x)− π I h h (·|x) E # . Using d π E h = d h + (1− α)(d π E h − d π out h ), the right-hand side is equal to T 1 + T 2 , where we define T 1 : = E I " H X h=1 X x∈X d h (x) D Q π I h (x,·),π E,h (·|x)− π I h h (·|x) E # , T 2 : = (1− α)E I " H X h=1 X x∈X (d π E h (x)− d π out h (x)) D Q π I h (x,·),π E,h (·|x)− π I h h (·|x) E # . We first controlT 1 . For a fixed stageh, writeJ ∈ [K] H−1 for the collection of indices at all stages excepth. For k ∈ [K], let I h,k,J be the full index vector obtained by setting I h = k and I −h = J , and define Q k,J h : = Q π I h,k,J h . For every h,k,J , we have Q k,J h ∈Q h . Using the independence and uniformity of I h , we can rewrite T 1 as T 1 = H X h=1 E I h ,I −h h L d h π I h h ,Q π I h i = 1 K H X h=1 K X k=1 E J h L d h π k h ,Q k,J h i . 72Appendix table of contents We now compare each realized comparatorQ k,J h to the empirical best responseQ k h before averaging overJ. With a slight abuse of notation, recall thatπ k denotes the policy whose decision rule at stagehisπ k h . Define the same uniform estimation error used in Theorem I.2 by ∆ d (π) = max h∈[H] sup Q h ∈Q h b L d h (π h ,Q h )−L d h (π h ,Q h ) . For every fixed h,k,J , on this uniform-concentration event, L d h π k h ,Q k,J h ≤ b L d h π k h ,Q k,J h + ∆ d π k ≤ b L d h π k h ,Q k h + ∆ d π k ≤L d h π k h ,Q k h + 2∆ d π k . The middle inequality is the empirical best-response property ofQ k h , which we can use sinceQ k,J h is one feasible element ofQ h by Assumption J.1. Averaging the last display over J , summing over h and k, and dividing by K, we obtain T 1 ≤ 1 K H X h=1 K X k=1 L d h π k h ,Q k h + 2H K K X k=1 ∆ d π k . The first term is controlled by the FTRL regret bound stage by stage (Lemma E.7). Indeed, for each fixed h, K X k=1 L d h π k h ,Q k h = X x∈X d h (x) K X k=1 Q k h (x,·),π E,h (·|x)− π k h (·|x) ≤ 3 p Q 2 max K logA. Sinceπ k is inΠ Q , applying Lemma E.2 withΠ h = Π Q,h and radiusr > 0gives, on an event of probability at least1−δ, K X k=1 ∆ d π k ≤ 4Kr + KQ max v u u t 8 log 2 P H h=1 N r (Q h × Π Q,h ,ρ)/δ n E . Combining the previous three displays, taking r = ε/H , and bounding the sum by the maximum gives T 1 ≤ 3H r Q 2 max logA K + 8ε + 2HQ max s 8 log 2H max h N ε/H (Q h × Π Q,h ,ρ)/δ n E . It remains to control T 2 . Define, for each h,x,I , g I h (x) : = D Q π I h (x,·),π E,h (·|x)− π I h h (·|x) E . We have Q π I h (x,a)∈ [0,Q max ] for every x,a,h,I . Therefore g I h (x) = Q π I h (x,π E,h )− Q π I h x,π I h h ≤ Q max . Using the triangle inequality and the previous inequality, we can bound the signed change-of-measure term explicitly: |T 2 |≤ (1− α)E I " H X h=1 X x∈X (d π E h (x)− d π out h (x))g I h (x) # ≤ (1− α) H X h=1 E I " X x∈X |d π E h (x)− d π out h (x)| g I h (x) # ≤ (1− α)Q max H X h=1 ∥d π E h − d π out h ∥ 1 ≤ 2(1− α)HQ max . In the last line, we used that bothd π E h andd π out h are probability distributions, so theirℓ 1 distance is at most2. With α = 1− ε/(2HQ max ), the termT 2 is at mostε. TheQ Π Q -realizable choices ofKandn E makeT 1 at mostO(ε), proving the second branch for the same averaged output policy π out . 73Appendix table of contents