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
arXiv:2607.29617v1 [cs.LG] 31 Jul 2026
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.
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 between BC and interactive IL disappears, making the precise role of interaction less clear than it once seemed. * Equal contribution.
1
Normalized return
Acrobot-v1
CartPole-v1
Pendulum-v1
LunarLander-v2
1
0.5
0
1 32
1 16
1 8
1 4
1
1 32
1 16
1 8
1
1 4
1 32
1 16
1 8
1 4
1
1 32
1 16
1 8
1 4
1
Learner/Expert hidden layer size ratio
OVI (Ours) (online, value-based)
DAgger
SPOIL
(offline, value-based)
(online, policy-based)
BC
(offline, policy-based)
Figure 1: OVI achieves higher return with smaller learner networks. Average normalized return (y-axis, 1 and 0 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), over 50 seeds and 10 expert trajectories for offline methods or 10 rounds of expert queries along learner trajectories for interactive methods. The expert network has width 64. We compare with offline and interactive policy-based methods (BC; Pomerleau, 1988; DAgger; Ross et al., 2011), and the offline value-based method SPOIL (Moulin et al., 2025a). When the learner network shrinks, OVI outperforms each of the following methods alone: (1) offline value-based and (2) interactive policy-based—thereby supporting the theory that predicts that representational 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 introduce OVI (Algorithm 1), the first algorithm that is statistically and computationally oracle-efficient under only QπE -realizability—a natural representational assumption requiring only that the learner can represent the expert’s value function—provided that the learner can interactively query the expert on-policy. OVI queries 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 complement this with a study on the representational advantages of Qπ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, OVI outperforms
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 at https://github.com/lviano/ovi. Interaction is necessary for value-based IL (Section 4). We prove that without conditions stronger than Qπ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., via BC or DAgger), 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 complementary perspective on the benefits of interaction in IL by showing that OVI can 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, OVI uses 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 tuple M = (X , A, H, P, r, ν0 ), where X is a (potentially large) finite state space, A is a finite action space with A ≥ 2 actions, H ∈ N is the horizon, P = (Ph : X × A → ∆(X ))H h=1 is the transition kernel, r = (rh : 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 distribution Pπ over trajectories (xh , ah , rh )H h=1 via the following interaction protocol: an initial state x1 ∼ ν0 is drawn, and then for each h = 1, . . . , H, we have ah ∼ πh (· | xh ), rh = rh (xh , ah ), and xh+1 ∼ Ph (· | xh , ah ). PH We denote by Eπ the corresponding expectation. The expected return of a policy π is given by J π = Eπ h=1 rh , and the value functions are defined for any state-action pair (x, a) by hP i hP i H H ′ ′ Vhπ (x) = Eπ and Qπh (x, a) = Eπ h′ =h rh xh = x h′ =h rh xh = x, ah = a . The value functions satisfy the Bellman equations π Qπh (x, a) = rh (x, a) + Ex′ ∼Ph (·|x,a) Vh+1 (x′ ) ,
Vhπ (x) = Ea∼πh (·|x) [Qπh (x, a)],
(1)
π where VH+1 = 0. We define the occupancy measures via dπh (x, a) = Pπ [xh = x, ah = a] and dπh (x) = Pπ [xh = x]. To disentangle the effects of reward scaling PH from the horizon H, we assume rewards are normalized such that for some Qmax > 0 and any feasible trajectory, h=1 rh ∈ [0, Qmax ] (Jiang and Agarwal, 2018; Wang et al.,P 2020; Zhang et al., 2021).1 For any policy π and function f : X × A → R, we sometimes use the notation f (x, π) = a π(a | x)f (x, a). 1 In general (the dense reward setting), Q
max can be as large as H, but in some settings (e.g., in LM reasoning tasks with binary outcome-level rewards) we can have Qmax = 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 MDP M, and the goal is to learn a policy that performs as well as πE , as measured by expected return. Formally, for error tolerance ε > 0 and 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 n H onE DE = xiE,h , aiE,h h=1 , where xiE,h , aiE,h ∼ dπhE , (3) i=1
where nE 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 (xh )H h=1 where xh ∼ dπh and might query expert actions at states along the trajectory, i.e., aE,h ∼ πE,h (· | xh ).
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 class Q ⊆ {(Qh : X × A → [0, Qmax ])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 class Q contains the expert’s value function, i.e., QπE ∈ Q. By contrast, policy-based methods, such as BC and DAgger, 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 class Q (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 the H = 1 (“contextual bandit”) setting, where Assumption 2.1 simplifies to realizability of the reward function, and Moulin et al. require closure-type assumptions on Q, i.e., that it can realize Qπ for any policy π generated by the learner.2 In Section 3.2, we further establish that mere reward realizability is insufficient for general environments when H > 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 as AggreVaTe (Ross and Bagnell, 2014; Sun et al., 2017), the learner interacts with the MDP and can observe the expert value QπE (xh , ah ), 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 expressive Q class.
4
3
Interaction Enables QπE -Realizable Value-Based Imitation
The main result of this section is OVI, the first provably efficient algorithm for value-based IL under QπE -realizability. In Section 3.1, we describe the algorithm and its guarantees. We then show in Section 3.2 that QπE -realizability can be weaker than policy realizability, while reward realizability alone is insufficient. Finally, in Section 3.3 we present empirical evidence that OVI outperforms 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), OVI treats 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
π
Ldh (πh , QπhE ),
h=1 H where, for any d = (dh ∈ ∆(X ))h=1 ,
Ldh (π, Q) :=
X
dh (x)
(πE,h (a | x) − π(a | x))Q(x, a) .
a∈A
x∈X
|
X
{z
(I)
}|
{z
(II)
}
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 over Qh := {Qh : ∃Q′ ∈ Q, Q′h = Qh } for every h on the right hand side. J πE − J π ≤
H X h=1
π
sup Ldh (πh , Qh ).
Qh ∈Qh
Accordingly, what remains is to find an approximate saddle point of the expected advantage function, i.e., a policy πout πout such that, for all h ∈ [H], supQh ∈Qh Ldh (πout,h , Qh ) ≲ ε/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 the Forward algorithm (Ross and Bagnell, 2010). To understand this design choice, we recall that k the approach employed by past work (Moulin et al., 2025a) is to compute a sequence (π k , Qk )K k=1 where π performs k online mirror ascent (Beck and Teboulle, 2003) and Q performs a best response to (an empirical estimate of) the loss function L. This technique does not seem to apply in the QπE -realizability setting, as the sequence π k is also dictating the current sampling distribution d under which the error is measured (see (I) above), preventing us from simultaneously forming an empirical estimate of L and controlling the error in (II) via online learning. This is addressed in OVI by learning πout one layer at a time (note the outer loop over h = 1, . . . , H in line 2 of Algorithm 1), as dπhout (x) only depends on (πout,1 , . . . , πout,h−1 ) and we can thus fix the sampling distribution for stage h before 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 for OVI is given in Algorithm 1. The main sample complexity guarantee is stated below. It establishes that OVI only requires a number of expert queries that scales with the statistical capacity of the value function class Q, as represented by its log-cardinality log|Q|. Theorem 3.1 (Sample complexity of OVI). Let Assumption 2.1 hold for a finite class Q. Then, for any ε, δ ∈ (0, 1), e 4 Q4max log(A) log(|Q|/δ)ε−4 ), η = (log(A)/(KQ2max ))1/2 , and K = OVI (Algorithm 1) with parameters nE = O(H 2 2 −2 O(H Qmax log(A)ε ), outputs a policy πout such that with probability at least 1 − δ, J πE − J πout ≤ ε after 5 4 H Qmax log(A) log(|Q|/δ) e expert queries. O ε4 Note that the total number of learner interactions with the environment obeys the same bound with an extra factor of H. Up to the usual polynomial factors in the horizon H, the suboptimality 1/ε, and the log failure probability log(δ −1 ), the main appealing feature of OVI is that its sample complexity is controlled by the statistical complexity of only the value function class Q, 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 nE . 2: for h = 1, . . . , H do 3: Create dataset at stage h: for i ∈ [nE ], sample xih ∼ dπhout , and query aiE,h ∼ πE,h (· | xih ). 4: 5: 6:
Initialize πh1 = Unif(A). for k = 1, . . . , K do PnE (Qh (xih , aiE,h ) − Qh (xih , πhk )). Set Qkh ∈ arg maxQh ∈Qh i=1
7:
Set πhk+1 (a | x) ∝ πhk (a | x)eηQh (x,a) , for any state-action pair (x, a). PK 1 k Create the output policy at layer h: πout,h = K k=1 πh .
k
8:
on the learner’s policy class. We show in Section 3.2 that, in many natural settings, a function class Q satisfying 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 as BC or DAgger. We note that the dependence on the problem horizon is larger than that obtained by policy-based methods such as BC or DAgger (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 e −2 ). covering numbers. The result also shows that, when Q is convex, the expert-query complexity improves to O(ε Computationally, OVI only requires access to a standard linear maximization oracle for the Q updates (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. e −4 ) Improved rates for nonconvex classes. The rate attained by OVI for nonconvex classes Q has a suboptimal O(ε −2 e dependence. This can be improved to an O(ε ) rate via a variant of OVI, named Q-OVI (Algorithm 3), where the roles of the value functions and the policies are reversed, i.e., the Q player 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 class Q, making the method computationally unattractive for large or continuous classes such as neural networks. It is an e −2 ) in a computationally efficient manner. Another advantage of Q-OVI is that interesting question to obtain a rate of O(ε it can be used to compute a stationary expert-matching policy (see Appendix H.3), whereas OVI learns 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 as BC, 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 which H = 1, and show that value-based IL can be strictly weaker than policy-based IL (note that when H = 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 class R3 satisfying |R| ≤ |Π|, simply by taking R = {r : ∃π ∈ Π, r(x, a) = 1{a ∈ supp(π(· | x))}}. By contrast, they show that the existence of a small realizable reward class R cannot 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, with H > 1). Given a finite class Π that realizes an optimal expert πE , we show in Appendix C.1 that it is possible to construct a class Q such that |Q| ≤ |Π| and Q realizes e πE which assigns maximal value to actions within the expert support, defined by Q e πE (x, a) = Qmax 1{a ∈ a function Q πE supp(πE (· | x))}. OVI still succeeds, even if we cannot guarantee that Q ∈ Q (see Appendix C.1.1). Conversely, as above, when given a small Q class satisfying Qπ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 relaxed QπE -realizability condition detailed in Appendix C.1.1. In the H > 1 setting, the closest comparable value-based IL work is the SPOIL algorithm of Moulin et al., which requires that Q can realize Qπ 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 class Q that 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 class Q 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 function Qπ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 class R ⊆ {(rh′ : X × A → [0, 1])H h=1 } satisfying the following expressivity condition. Assumption 3.2 (Reward realizability). The class R 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 algorithm Alg with a fixed interaction budget nE ∈ N⋆ is a (potentially randomized) procedure that, in each episode k ∈ [nE ], selects a policy π k based on the preceding k interaction history, rolls it out in the MDP to generate states xkh ∼ dπh for all h ∈ [H], and is allowed to query the expert for actions akE,h ∼ πE,h (· | xkh ) for all h ∈ [H], without observing rewards. After the nE 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 MDP M, we write JM for the return of a policy π, and πM for one of its optimal deterministic policies. Theorem 3.2 (Lower bound under reward realizability). For every X ≥ 1 and ε ∈ (0, 1/4], there exists a family F of MDPs with: i) stochastic initial states but deterministic rewards and transitions, ii) horizon H = 2, iii) state space size |X | = O(X), and iv) family size log(|F|) = O(X), such that for every M ∈ F, Assumption 3.2 is satisfied by the same singleton reward class R = {r⋆ }. Let Alg be 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 MDP M ∈ F, with corresponding expert πE = πM , such that Alg needs Ω Xε rounds of interactions to output a πE πout policy πout such that E[JM − JM ] ≤ ε.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 when H = 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 step h = 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 takes min{|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 view Qπ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 of Qπ 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 of Qπ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 in {2, 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 as BC and DAgger may therefore degrade relative to OVI. The code for these experiments is available at https://github.com/lviano/ovi. We evaluate OVI, SPOIL, BC, and DAgger across the above range of widths. We use 10 expert trajectories for the offline methods, 10 learner-trajectory labeling rounds for the interactive methods, and 50 seeds (see Appendix D for more experimental details). Figure 1 shows that when the learner also has 64 neurons per layer, BC and DAgger perform 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. SPOIL generally deteriorates faster than OVI, especially in CartPole-v1 and Acrobot-v1, consistent with the possibility that QπE -realizability is easier to satisfy in these experiments than the closure-type realizability conditions required by SPOIL. We use a stationary approximation to OVI in these experiments; see Algorithm 2 for pseudocode. Finally, we compare DAgger and OVI in a synthetic QπE -realizable MDP to highlight that, despite both IL algorithms being interactive, OVI implements a different imitation mechanism than DAgger. (Figure 2) DAgger vs. OVI: a different imitation mechanism. Although also an interactive IL method, DAgger is surprisingly suboptimal in this environment, which is an extended version of the simple Qπ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 , of OVI (solid red line) converges significantly faster than the suboptimality of DAgger (solid purple line). The advantage of OVI stems from the fact that it directly matches the expert’s return, while DAgger, 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 consideration because there are O(2|X | ) possible optimal policies from which the expert can choose. In comparison, OVI acts approximately6 greedily with respect to its learned QπE , which is sufficient to achieve the optimal return with significantly 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 expert, DTV (PπE , Pπout ), which decreases under DAgger (dashed purple line) but remains constant for OVI (dashed red line).
4
Interaction Is Necessary for QπE -Realizable Value-Based Imitation
In Section 3, we showed that interaction enables OVI to succeed under only Qπ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 algorithm Alg is a (potentially randomized) mapping from an expert dataset DE (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 exhibiting Qπ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 MDP M, we write JM 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 any X ∈ N⋆ and any ε ∈ (0, 18 ], there exists a family F of MDPs with: i) stochastic initial states but deterministic rewards and transitions, ii) horizon H = 2, iii) state space size |X | = O(X), and iv) family size log(|F|) = O(X), as well as a value function class Q with |Q| = 2 such ⋆ that for every M ∈ F, Assumption 2.1 is satisfied for expert policy πE = πM . Let Alg be any offline IL algorithm (Definition 4.1). Then, there exists an MDP M ∈ F such that Alg needs nE ≥ Ω( Xε ) trajectories sampled according to π⋆
⋆ πout Eq. (3) with expert policy πM , to output a policy πout such that E[JMM − JM ] ≤ ε.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 satisfying Qπ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. Representation Offline IL (Definition 4.1) Interactive IL (Definition 3.1)
Reward r
Value QπE
Policy πE
✗ (Theorem 3.2) ✗ (Theorem 3.2)
✗ (Theorem 4.1) ✓ (OVI; Theorem 3.1)
✓ (e.g., BC) ✓ (e.g., DAgger)
⋆
Table 1: Tractability of imitation learning (for H > 1) under different representational assumptions. ✓: A poly(log(|F |), H, ε−1 , log(δ −1 )) sample complexity is possible, where F is 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
1.0 0.8 OVI (Ours) DAgger Return suboptimality Total Variation suboptimality
0.6 0.4 0.2 0.0
0
1
2
5
10
20
50
100
200
500
Expert queries / iterations k
Figure 2: Comparison of reward suboptimality, J πE − J πout , and total variation distance, DTV (PπE , Pπout ) for OVI and DAgger in a synthetic environment satisfying Assumption 2.1 (illustrated in Figure 7). OVI matches 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 algorithm Alg (Definition 4.1) uses a value-induced (VI) policy class (for value function class Q) if it outputs policies of the form πout,h (a | x) ∝ f (wT (Q1:K h )(x, a)), for some parameter K ∈ N, sequence Q1:K ∈ QK , linear parameter w ∈ RK , 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 by OVI. See Appendix G for details. The following lower bound shows that, under Qπ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 family F of MDPs with: i) deterministic initial states, rewards, and transitions, ii) horizon H = 2, iii) state space size |X | = 3, and iv) family size |F| = 2, as well as a value function class Q with |Q| = 2 such that for every M ∈ F, Assumption 2.1 is satisfied for the expert ⋆ πE = πM . Moreover, for any algorithm Alg (Definition 4.1) with a VI policy class (Definition 4.2), for any nE ∈ N⋆ , there exists an MDP M ∈ F such that, given nE expert trajectories sampled from πE , Alg outputs policies πout such πE πout that E[JM − JM ] ≥ 14 .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 only Qπ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 as SPOIL (Appendix I). In particular, in Theorem I.1, we prove sample complexity guarantees for SPOIL under Qπ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 of OVI that mixes learner and expert trajectories succeeds whenever Q satisfies either QπE -realizability (Assumption 2.1) or the SPOIL-like closure condition, which requires Qπ ∈ Q for 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 how OVI can 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 verifiers 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 prompt x ∈ X , samples a response y ∈ Y via y ∼ π(· | x), where y = (y1 , . . . , yH−1 , yH ) is a sequence of H tokens, belonging to a token vocabulary denoted by Σ, generated autoregressively as yh ∼ π(· | x, y1 , . . . , yh−1 ), h = 1, . . . , H, and the last token yH is the final answer. This interaction defines a token-level MDP with horizon H, where states are the partial generations so far, xh = (x, y1:h−1 ) ∈ X × Σh−1 , the action is the next token yh ∈ Σ, and the next state is xh+1 = (x, y1:h ). The learner is given access to a dataset D = {(x, y)}, where the prompt x is 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 as r : X × Y → {0, 1} so 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 an H = 1 problem (i.e., a contextual bandit), where the prompt x is the context and the response y ∈ ΣH is an action. Under a reward (or outcome verifier) realizability assumption (Assumption 3.2), Joshi et al. (2026) estimate a reward rb from the demonstrations D using an exponential-weights-type procedure which, at each iteration, must solve arg maxy∈ΣH rb(x, y) to extract a response for a given prompt x.11 Their procedure presents two computational barriers. First, the reward optimization is over the full response space Y = Σ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 apply OVI directly to the token-level MDP generated by the interaction of the prompt distribution, the LM, and the outcome verifier r. At each step h, OVI learns 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 into H local search steps. Moreover, each stage of the problem is solved by OVI using 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 of OVI over 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 through OVI, an interactive value-based IL algorithm that is statistically and computationally efficient under Qπ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 an O(ε−2 ) rate for nonconvex classes Q with 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 whether OVI (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. URL https://icml.cc/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 Conference on Intelligent Robots and Systems, 2008. URL https://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. URL https://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. URL https://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://www.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. URL https://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:2603.20538, 2026. URL https://arxiv.org/abs/2603.20538.
arXiv preprint
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 reinforcement. 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. URL https:// 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. URL https://proceedings.neurips.cc/paper_files/paper/2019/ file/947018640bf36a2bb609d3557a285329-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. URL https: //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. URL https://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. URL https: //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. URL https://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. URL https://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. URL https: //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. URL https://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. URL https://proceedings.mlr.press/v70/ haarnoja17a.html. Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in Neural Information Processing Systems, 2016. URL https://proceedings.neurips.cc/paper_files/paper/2016/file/ cc7e2b878868cbae992d1fb743995d8f-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. URL https://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. URL https: //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. URL https://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. Discriminatoractor-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 International 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. URL https://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. URL https: //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 misspecification. Advances in Neural Information Processing Systems, 2026. URL https://papers.nips.cc/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. URL https://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://www.nature.com/articles/nature14236.
16
Antoine Moulin, Gergely Neu, and Luca Viano. Inverse Q-learning done right: Offline imitation learning in Qπ 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. URL https://proceedings. neurips.cc/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. URL https://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. URL https://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. URL https://proceedings.neurips.cc/paper/2022/ hash/b1efde53be364a73914f58805a001731-Abstract.html. Dean A. Pomerleau. Alvinn: An autonomous land vehicle in a neural network. In Advances in Neural Information Processing Systems, 1988. URL https://proceedings.neurips.cc/paper_files/paper/1988/file/ 812b4ba287f5ee0bc9d43bbf5bbe87fb-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. URL https://proceedings.neurips. cc/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 Information Processing Systems, 2021a. URL https://proceedings.neurips.cc/paper_files/paper/2021/hash/ 09dbc1177211571ef3e1ca961cc39363-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. URL https://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 reinforcement 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. URL https: //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. URL https://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. URL https://proceedings. mlr.press/v97/sun19b.html. Gokul Swamy, Sanjiban Choudhury, J Andrew Bagnell, and Steven Wu. Of moments and matching: A gametheoretic 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. URL https://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 Information Processing Systems, 2022b. URL https://proceedings.neurips.cc/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 Neural Information Processing Systems, 2007. URL https://papers.nips.cc/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. URL https://icml.cc/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. URL https://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. URL https://proceedings.neurips.cc/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. URL https://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. URL https://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 Information Processing Systems, 2023. URL https://proceedings.neurips.cc/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 neural information processing systems, 2022. URL https://proceedings.neurips.cc/paper/2022/hash/ 9d5609613524ecf4f15af0f7b31abca4-Abstract-Conference.html. Gellert Weisz, Philip Amortila, Barnabás Janzer, Yasin Abbasi-Yadkori, Nan Jiang, and Csaba Szepesvari. On queryefficient 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. URL https: //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. URL https://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. URL https://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. URL https://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. URL https://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 Reference
22
B Additional Related Work
23
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 Examples C.1 Constructing Q from Π Reduces Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27 27
πE
30
D Experiment Details
35
C.2 Q -Realizability Can Be Strictly Weaker Than πE -Realizability under Exogenous Noise . . . . . . .
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 Tools
I
38
E.1 Concentration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
E.2 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
E.3 Performance Difference Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
Proofs of Main Results
45
F Proofs from Section 3
45
F.1
Proof of Theorem 3.1 (Sample Complexity Guarantee for OVI) . . . . . . . . . . . . . . . . . . . . .
46
F.2
Proof of Theorem 3.2 (Reward Realizability Is Insufficient) . . . . . . . . . . . . . . . . . . . . . . .
49
G Proofs from Section 4 (QπE -Realizability Is Insufficient to Learn Offline)
II
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
Additional Results
58
H Q-OVI: An Inefficient Algorithm with Improved Statistical Guarantees
I
J
52
58
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
Breaking the Offline Lower Bound with Coverage
64
I.1
OVI with Arbitrary Sampling Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
64
I.2
Proof of Theorem I.1 (Offline IL with Coverage and Optimal Expert) . . . . . . . . . . . . . . . . . .
67
On the Benefits of Mixing Expert and Learner Trajectories
21
70
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. Notation
Meaning
First introduced
MDP and imitation-learning setting M = (X , A, H, P, r, ν0 ) π = (πh )H h=1 Pπ , Eπ , J π Vhπ , Qπh dπh (x), dπh (x, a) πE , πE,h πout , πout,h ε, δ DE , nE , xiE,h , aiE,h
Episodic MDP. State space X , action space A with A = |A|, horizon H, transition kernel P , reward function r, and initial-state law ν0 . Nonstationary Markov policy. πh : X → ∆(A) is a decision rule. Trajectory law, expectation, and expected return induced by policy π. State-value and state-action-value functions of policy π at stage h. State and state-action occupancy measures at stage h under π. Expert policy and its decision rule at stage h. Output policy returned by the learner and its decision rule at stage h. Target suboptimality and failure probability. Offline expert dataset, number of expert samples, and the i-th expert state-action sample at stage h.
Section 2 Section 2 Section 2 Section 2 Section 2 Section 2 Eq. (2) Eq. (2) Eq. (3)
Value classes and realizability Q, Qh Qmax Π e πE Q QΠQ -realizability
Sequence-level value-function class and its projection at stage h. Uniform upper bound used for state-action values in the analysis. Policy class used when stating policy realizability comparisons. Witness for relaxed QπE -realizability. Closure assumption requiring Qπ ∈ Q for learner-generated policies π ∈ ΠQ .
Assumption 2.1 Section 2 Assumption 3.1 Assumption C.1 Assumption J.1
Objectives, empirical estimates, and complexity Ldh (p, Q) Lπh Lbh (p, Q) ∆(π) Rπh (x) Nε (S, d), Cε (S, d) Nεmax (Q) ∥·∥∞,1 ρ ΠQ , ΠQ,h
Expected advantage objective at stage h against the expert action distribution, with states weighted by dh . π Shorthand for Ldh , used when the state distribution is induced by policy π. Empirical estimate of Lπhout (p, Q) built from queried expert actions. Uniform estimation error between Lbh and Lπhout for policy π. Stage-state regret of the π-player against the expert decision rule. Covering number of S under metric d, and a corresponding ε-cover. Largest covering number over Q, Nεmax (Q) := maxh Nε (Qh , ∥·∥∞ ). Sup-over-states, ℓ1 -over-actions metric for decision rules. Scaled product metric on value functions and decision rules. Policies generated by softmax combinations of functions in Q.
Section 3.1 and Lemma E.2 Appendix F Appendix F Lemma F.1 Lemma F.1 Definition E.1 Definition E.1 Eq. (5) Eq. (6) Lemma E.3
Algorithmic and appendix-specific notation K, η, πhk , Qkh Q1:K , LC, f ΠAlg , C∞ , C1 bd d = (dh )H h=1 , Lh , ∆d ℓbπhout ,k b πE whk , Rw h , Qh
Number of iterations, learning rate, and the policy/value iterates at stage h. Value functions, linear combination, and link function that defines a VI policy. Output-policy class and coverage coefficients used when offline learning is possible under expert coverage. Arbitrary state-sampling distributions and the corresponding empirical objective and estimation error. Sampled loss used by the Q-OVI exponential-weights update. Cover weights, their regret, and the closest covering element to QπhE in the Q-OVI analysis.
22
Algorithm 1 Definition 4.2 Assumptions I.1 and I.2 Algorithm 5 and Theorem I.2 Algorithm 3 Lemma H.1
Appendix 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 valuebased 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 under Qπ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) introduced AggreVaTe, 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-networkbased 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 to OVI is the moment-matching framework of Swamy et al. (2021), especially their “On-Q” template and the associated DAeQuIL algorithm. This framework also includes reward and “Off-Q” momentmatching templates, and analyzes imitation gaps through moment recoverability µ: matching action-value moments to precision ε yields a suboptimality bound of order µHε, improving on the classical H 2 error-propagation factor in BC-style analyses. Empirically, Swamy et al. (2021) show that DAeQuIL can outperform BC and DAgger in a forestnavigation 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-propagationstyle 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 under Qπ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 (ii) 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 dependence H 2 and √show that, for deterministic experts, access to the transition model can improve the horizon dependence by at least a H factor. 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
23
Appendix table of contents
occupancies, or expert states or features rather than through value feedback. Xu et al. (2023) removed the knowntransition 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, whereas OVI uses 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 class Q must realize Qπ 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 only Qπ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 that Qπ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 horizon H = 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 with H = 1, thereby obtaining faster rates when the expert is optimal. Because H = 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 that IQ-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 class Q by removing functions with “temporal” variations greater than one; this is guaranteed to reduce the complexity of Q while still providing realizability of QπE . In practice, this could be implemented by adding a regularization term to the OVI 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, BC fits the expert action distribution by supervised learning on expert trajectories, with early BC-style systems including ALVINN (Pomerleau, 1988, 1991).
24
Appendix table of contents
Interactive variants such as DAgger—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, offline BC can 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 amplification reappears in misspecified settings and that next-token or BC-style objectives face computational-statistical tradeoffs. They also propose robustified BC variants whose guarantees quantify the dependence on horizon and misspecification. Espinosa-Dice et al. (2025) introduce GUITAR, an efficient interactive IL algorithm under misspecification that uses a structural completeness condition and environment access initialized from states sampled from the expert occupancy measure, 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 as ALVINN (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. GAIL and 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 the IQ-Learn method of Garg et al. (2021) learns a single soft Q-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-Learn has 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, including SequenceMatch (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
25
Appendix table of contents
Table 3: Comparison with related algorithms, assumptions, and expert-interaction requirements. To state the guarantees of BC, we define a policy class Π such that πE ∈ Π. Joshi et al. (2026) study finite reward classes and one-step decision ′ 2 problems. Nεmax ′ (Q) denotes the largest covering number of the stagewise classes Qh in ∥·∥∞ with spacing ε = O(ε ). Pm 1 m k := We define the class ΠQ {π : ∃m ≤ K, ∀h, ∃Qh , . . . , Qh ∈ Qh , πh (· | x) = softmax(η k=1 Qh (x, ·))} for some K = poly(d, H, ε−1 ). QΠQ -realizability is the assumption that Qπ ∈ Q for any π ∈ ΠQ . Expert traj./queries (nE )
Algorithm
Representational assumptions
Comp. efficient
Interactive expert
LogLossBC (Foster et al., 2024)
πE -realizability
✓
✗
O
H 2 log|Π| ε2
MWAL (Syed and Schapire, 2007)
Reward linear in d features Known transitions
✓
✗
e O
H 2 log(d) ε2
MUWU (Joshi et al., 2026)
Reward realizability with class R Contextual bandits (H = 1)
✗
✗
e O
SPOIL (Moulin et al., 2025a)
QΠQ -realizability
✓
✗
e O
Q-OVI (Ours, Theorem H.1)
QπE -realizability
✗
✓
e O
OVI (Ours, Theorem F.1)
QπE -realizability
✓
✓
e O
SPOIL (Ours, Theorem I.1)
QπE -realizability Bounded C∞ , optimal πE
✓
✗
e O
Lower Bound (Ours, Theorem 4.1)
Linear QπE -realizability
−
✗
log(|R|) ε2
H 5 Q4 log(AN max (Q)) ε′
max
ε4
H 3 Q2 log N max (Q) ε′
max
ε2
H 5 Q4 log(AN max (Q)) ◦ ε′
max
ε4
C 4 H 5 Q4 log(AN max (Q)) ⋄ ∞
ε′
max
ε4
Ω |Xε |
△
◦ If Q is convex, the bound improves to O(H e 3 Q2 log(N max (Q))ε−2 ). max ε′ ⋄ If Q is convex, the bound improves to O(C e 2 H 3 Q2 log(N max (Q))ε−2 ). ∞ max ε′ △
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.
26
Appendix table of contents
C Value-Based Imitation Learning versus Policy-Based: Motivating Examples 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 class Q 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, Q can be easier to specify than Π when the expert behavior may depend on uncontrollable exogenous noise, while QπE does not: the reward and transition dynamics are unaffected by this noise, whereas the expert’s control policy is.
C.1
Constructing Q from Π Reduces Complexity
We first show that, given a policy class Π realizing an optimal expert policy πE , one can construct a function class Q that realizes QπE in a relaxed sense. We then show that OVI guarantees continue to hold under this relaxed realizability condition. These guarantees improve the representational-complexity term over those of BC, DAgger, and other policybased methods that aim to match the expert trajectory distribution in total variation: indeed, such methods incur a log|Π| dependence, while OVI pays a factor log|Q|, where Q is constructed from Π and has no larger cardinality, i.e., |Q| ≤ |Π|. Constructing Q from a policy class that realizes the expert. We preprocess Π by keeping only the action supports e π = (Q e π )H with Q e π : X × A → [0, Qmax ] be defined by induced by its policies. Specifically, for each π ∈ Π, let Q h h=1 h e πh (x, a) = Qmax 1{a∈supp(π (·|x))} , Q h for every (h, x, a) ∈ [H] × X × A. We then set n o eπ : π ∈ Π . Q(Π) = Q Since infinitely many stochastic policies in Π can share the same support, Π may be infinite even when Q(Π) is finite under the construction above. Exact QπE -realizability may fail. When the expert is (pointwise) optimal, πE is greedy with respect to QπE . The construction also includes the function corresponding to π = πE , e πE (x, a) = Qmax 1{a∈supp(π (·|x))} , Q E,h h e πE = QπE ; in general, QπE may not belong to with respect to which πE is greedy. However, this does not imply that Q e πE , QπE , and the expert’s action support Q. The key point is that OVI only needs the weaker relationship between Q πE formalized as relaxed Q -realizability in Assumption C.1. The support-indicator witness above satisfies this condition because it assigns Qmax to every expert-supported action and zero elsewhere, while QπE takes values in [0, Qmax ]. C.1.1
Guarantees for OVI under relaxed QπE -realizability
In this section, we present guarantees for OVI under a relaxed notion of QπE -realizability. At a high level, the condition asks Q to contain a surrogate for QπE that preserves the action comparisons used by OVI. We show that this condition is sufficient when the expert is statewise optimal, and that expert optimality is necessary. Assumption C.1 (Relaxed QπE -realizability). We say that Q satisfies relaxed QπE -realizability if there exists a sequence e πE = (Q e πE )H ∈ Q such that, for every (h, x) ∈ [H] × X , of functions Q h h=1 e πE (x, b), supp(πE,h (· | x)) ⊆ arg max Q h b∈A
and, for every (h, x, a) ∈ [H] × X × A, e πE (x, a) ≥ QπE (x, a), a ∈ supp(πE,h (· | x)) =⇒ Q h h πE πE e a∈ / supp(πE,h (· | x)) =⇒ Q (x, a) ≤ Q (x, a). h
27
h
Appendix table of contents
Under the relaxed Qπ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 Qkh ∈ Qh be computed as in Eq. (19). Define the π-regret at stage h and state x ∈ X as Rπh (x) =
K X
Qkh (x, ·), πE,h (· | x) − πhk (· | x) ,
k=1
PK 1
define the output policy as πout = K
k=1 π
k
, and, for any policy π, define the estimation error as
∆(π) = max sup Lbh (πh , Qh ) − Lπhout (πh , Qh ) . h∈[H] Qh ∈Qh
Then, it holds that J πE − J πout ≤
H
K
h=1 x∈X
k=1
1 X X πout 2H X dh (x)Rπh (x) + ∆ πk . K K
At this can establish the same complexity guarantee as OVI in the exactly realizable setting by bounding PKpoint, one 2H k with high probability, as in the proof of Theorem F.1. To conclude the section, we prove Lemma C.1. ∆(π ) k=1 K Proof of Lemma C.1. The proof follows the proof of Lemma F.1, except that we first compare QπhE with the relaxed e πE . For any policy π, we use the shorthand Lπ := Ldπ and we claim that, for every h ∈ [H], witness Q h h h e πE . Lπhout (πout,h , QπhE ) ≤ Lπhout πout,h , Q (4) h To prove this claim, fix h ∈ [H] and x ∈ X , write AEx,h := supp(πE,h (· | x)), and set δhx (a) := πE,h (a | x)−πout,h (a | x). By definition of Lπhout , X π X Lπhout (πout,h , QπhE ) = dhout (x) δhx (a)QπhE (x, a). x∈X
a∈A
Fix a state x. Since πE is statewise optimal, every action in AEx,h is greedy with respect to QπhE (x, ·), that is, AEx,h ⊆ arg maxb∈A QπhE (x, b). Thus, by definition of δhx , X
δhx (a)QπhE (x, a) =
X
δhx (a)QπhE (x, a)
a∈A / Ex,h
a∈AEx,h
a∈A
X
δhx (a)QπhE (x, a) +
X X πout,h (a | x)QπhE (x, a), = max QπhE (x, b) 1 − πout,h (a | x) − b∈A
a∈AEx,h
where we used that πE,h (a | x) = 0 for a ∈ / AEx,h , that
a∈A / Ex,h
E a∈AEx,h πE,h (a | x) = 1, and that all actions in Ax,h maximize e πE as follows QπhE (x, ·). By the relaxed realizability condition (Assumption C.1), we can replace QπhE with Q h
X
P
X X (a) e πE (x, b) 1 − e πE (x, a) δhx (a)QπhE (x, a) ≤ max Q πout,h (a | x) − πout,h (a | x)Q h h b∈A
a∈A (b)
=
a∈AEx,h
X
e πE (x, a) − δhx (a)Q h
a∈AEx,h (c) X
=
a∈A / Ex,h
X
e πE (x, a) πout,h (a | x)Q h
a∈A / Ex,h
e πE (x, a). δhx (a)Q h
a∈A
e πE is at least QπE , so maxb∈A Q e πE (x, b) ≥ maxb∈A QπE (x, b), that 1 − Step (a) uses that on the support AEx,h , Q h h h h P P πE E e π (a | x) = π (a | x) ≥ 0, and that outside the support A , Q (x, a) ≤ QπhE (x, a) holds, E E x,h a∈Ax,h out,h a∈A / x,h out,h h e πE (x, b) and so the inequality is reversed when multiplied by −πout,h (a | x). Step (b) uses AE ⊆ arg maxb∈A Q x,h
28
h
Appendix table of contents
x x / AEx,h . a∈AEx,h πE,h (a | x) = 1. Finally, (c) uses the definition of δh and the fact that δh (a) = −πout,h (a | x) for a ∈ Averaging the last display over x ∼ dπhout gives Eq. (4).
P
e πE ∈ Q and hence Q e πE ∈ Qh for each h ∈ [H], we can now upper bound the suboptimality as in Lemma F.1. Since Q h 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
Lπhout (πout,h , QπhE )
h=1
≤K
H X
e πE . Lπhout πout,h , Q h
h=1
Furthermore, by the definitions of the policy πout and the estimation error ∆, we have K(J πE − J πout ) ≤
H X K X
e πE Lπhout πhk , Q h
h=1 k=1
≤
H X K X
K X k e πE b Lh πh , Qh + H ∆ πk
h=1 k=1
≤
H X K X
k=1 K X Lbh πhk , Qkh + H ∆ πk k=1
h=1 k=1
≤
H X K X
K X Lπhout πhk , Qkh + 2H ∆ πk .
h=1 k=1
k=1
e πE ∈ Qh and Qk ∈ Qh . The second Here, the first and third inequalities use the definition of ∆(π k ), respectively with Q h h e πE ∈ Qh (Assumption C.1) and the fact that Qk is a best response to Lbh (π k , ·) over Qh . Finally, for inequality uses Q h h h each h ∈ [H], expanding Lπhout gives K X k=1
K X X π X πout Qkh (x, ·), πE,h (· | x) − πhk (· | x) = dhout (x)Rπh (x). Lπhout πhk , Qkh = dh (x) x∈X
x∈X
k=1
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 relaxed Qπ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 algorithm Alg outputting a VI policy (see Definition 4.2, even if allowed expert interaction, there exists a 2-action MDP M with a suboptimal expert policy and a class Q satisfying Assumption C.1 such that, πout πE even if Alg performs infinitely many expert queries, Eπout ∼Alg [JM − JM ] = Ω(H). Proof of Theorem C.1. Consider a class of environments {M1 , M2 } with action space A = {a1 , a2 } and a single absorbing state x, i.e., both actions from x transition back to x with probability 1. For i ∈ [2], let r(x, ai ) = 1 in Mi and r(x, a) = 0 for the other action a ̸= ai . In Mi , let the expert policy πE,i satisfy πE,i (ai | x) = 0.9 and e where Q e h (x, a) = H for all πE,i (a | x) = 0.1 for a ̸= ai . Assumption C.1 is satisfied by the singleton class Q = {Q}, (h, a) ∈ [H] × A. Indeed, for both πE,1 and πE,2 , the expert support is the full action space A. Under the additional value-derived output restriction that the learner can only output a policy obtained by applying a scalar link function to a e h assigns the same linear combination of functions in Q, the output policy is uniform over the action space because Q
29
Appendix table of contents
value to all actions, regardless of which environment the learner faces. Therefore, 2 π 1X π πout πout max Eπout ∼Alg JME,ii − JM ≥ Eπ ∼Alg JME,ii − JM = 0.9H − 0.5H = 0.4H. i i 2 i=1 out i∈[2]
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 than Qπ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 action 0 is 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 as BC and DAgger aim 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 as log|Π| (or a log-covering number). In contrast, our value-based guarantees depend on the complexity of a value-function class Q 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 ExBMDPs {Mb : b ∈ Bn } and deterministic, suboptimal experts {π b : b ∈ Bn } indexed by balanced Boolean decoders b : {0, 1}n → {0, 1}, where n is 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∈Bn ,π b ∈Π
log2 Nε (Π, dΠ ) ≥ 2n − n − 1 ,
where dΠ is the sup-total variation metric. By contrast, a two-dimensional class Q realizes the expert action-value b function QπMb for every b ∈ Bn , and log Nε (Q, ∥·∥∞ ) ≤ 2 log(3/ε) . Informally, the construction is as follows. We consider an instance where the endogenous state is a single bit s ∈ {0, 1}, and the expert’s endogenous policy simply plays action a = s among the actions A = {0, 1, 2}. However, the learner does not observe s directly. Instead, the learner observes a high-dimensional binary string w ∈ {0, 1}n , and recovering s from w requires computing a decoder b(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, the Q-function does not need this decoder. At the first layer, actions 0 and 1 are both safe and value-equivalent, while action 2 is unsafe. Hence QπE only needs to know the value-relevant distinction of {0, 1} vs. {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 return 1/2, while the policy that always chooses action 0 obtains 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−1 H H H H H−1 H H, (Sh )h=1 , (Ξh )h=1 , (Xh )h=1 , A, Thendo h=0 , (Thexo )h=0 , ghobs h=1 , (rh )h=1 ,
30
Appendix table of contents
where H is the horizon, and at each layer h, Sh is the endogenous state space, Ξh is the exogenous state space, Xh is the observation space, A is the action space, T0endo and T0exo are initial distributions, for h ∈ [H − 1] the map Thendo : Sh × A → ∆(Sh+1 ) is the endogenous transition kernel and Thexo : Ξh → ∆(Ξh+1 ) is the exogenous transition kernel, ghobs : Sh × Ξh → Xh is the observation map, and rh : Xh × A → [0, 1] is the reward function. The initial latent state is generated by s1 ∼ T0endo (· | ∅), ξ1 ∼ T0exo (· | ∅) independently, with the convention that S0 = Ξ0 = ∅. For h ∈ [H − 1], after taking action ah ∈ A, the latent state evolves according to sh+1 ∼ Thendo (· | sh , ah ), and ξh+1 ∼ Thexo (· | ξh ). Thus only the endogenous state is causally affected by the action; the exogenous state evolves independently of the action. The observation at layer h is generated by a deterministic emission map xh = ghobs (sh , ξh ) ∈ Xh . The model is decodable if for any h, there exists a decoder φ⋆h : Xh → Sh such that for any s ∈ Sh and ξ ∈ Ξh , φ⋆h (ghobs (s, ξ)) = s. Finally, the rewards are endogenous if there exist functions r̄h : Sh × A → [0, 1] such that rh (x, a) = r̄h (φ⋆h (x), a) for all h ∈ [H], x ∈ Xh , and a ∈ A. Because we work in a finite-horizon nonstationary MDP, policies and value functions are also indexed by the layer h. Thus a policy is a sequence π = (πh : Xh → ∆(A))H h=1 . In the construction below, we use separate observation spaces X1 and X2 . Equivalently, one can combine them into a single disjoint union X = X1 ⊔ X2 . Balanced decoders. For the construction below, we will consider the family of balanced Boolean functions as decoders, defined for any n ≥ 1 as n Bn = b : {0, 1} → {0, 1} : b−1 (0) = b−1 (1) = 2n−1 . 2n The number of balanced Boolean functions is |Bn | = 2n−1 . By unimodality of the binomial coefficient, and since the largest binomial coefficient is at least the average binomial coefficient, we have
2n
2n−1
n n 2n 2 1 X 2n 22 = maxn ≥ n = n . k 2 +1 k 2 +1 k∈[2 ] k=0
Therefore log2 |Bn | ≥ 2n − log2 (2n + 1) ≥ 2n − n − 1. C.2.2
The construction
Fix an integer n ≥ 1 and a decoder b ∈ Bn . Exogenous block MDP. We define an ExBMDP Mb with horizon H = 2 and action space A = {0, 1, 2}. Actions 0 and 1 are safe first-layer actions, while action 2 is unsafe. Let S = S1 ⊔ S2 be a layered endogenous state space with 7 states, where the first layer is S1 = {0, 1} and the second layer is S2 = G ∪ {B}, with G = {Gs,p : s ∈ {0, 1}, p ∈ {0, 1}}. The state Gs,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. n−1
Let the exogenous state space be time-homogeneous and given by Ξ1 = Ξ2 = {0, 1} . Since b is balanced, we have b−1 (0) = b−1 (1) = |Ξ1 | = 2n−1 . Therefore, for each s ∈ {0, 1}, we can fix an arbitrary bijection ηsb : Ξ1 → b−1 (s) that maps an (n − 1)-bit exogenous variable to an n-bit observation string. n
The observation spaces are X1 = {0, 1} and X2 = S2 × Ξ2 . The endogenous dynamics are defined as follows. The initial endogenous state is sampled uniformly at random, s1 ∼ Unif({0, 1}), and the transition from layer 1 to layer 2 is deterministic: ( Gs1 ,a1 , a1 ∈ {0, 1}, s2 = B, a1 = 2. Thus, the first action genuinely affects the endogenous state: actions 0 and 1 lead to different good branches, while action 2 leads to the bad state. This specifies a valid deterministic transition kernel from S1 × A to S2 .
31
Appendix table of contents
For the exogenous dynamics, the initial exogenous state is sampled independently of s1 , also uniformly at random, ξ1 ∼ Unif(Ξ1 ), and the exogenous process is persistent, i.e., ξ2 = ξ1 . Equivalently, T1exo (ξ ′ | ξ) = I{ξ ′ = ξ}. The exogenous transition is independent of the action. obs We define the observation map at stage 1 for any (s, ξ) ∈ S1 × Ξ1 as g1,b (s, ξ) = ηsb (ξ). Hence, conditional on s = 0, −1 the observed string is uniformly distributed over b (0), and conditional on s = 1, it is uniformly distributed over b−1 (1). Since s1 and ξ1 are both uniform, every observation w ∈ {0, 1}n is reachable and equally likely at layer 1: if b(w) = s, then P[x1 = w] = P[s1 = s]P[ηsb (ξ1 ) = w] = 21 · 2−(n−1) = 2−n . We can think of the observation map as hiding the endogenous state within an n-bit observation string via the mapping ηsb . The observation map at stage 2 is obs transparent: for any (y, ξ) ∈ S2 × Ξ2 , g2,b (y, ξ) = (y, ξ). n
Define the decoder φ⋆b by φ⋆1,b (w) = b(w) for any w ∈ {0, 1} , and φ⋆2,b (y, ξ) = y for any y ∈ S2 , ξ ∈ Ξ2 . Then, for obs every latent state (sh , ξh ), φ⋆h,b (gh,b (sh , ξh )) = sh . Indeed, at layer 1, we have obs φ⋆1,b g1,b (s, ξ) = φ⋆1,b ηsb (ξ) = b ηsb (ξ) = s, because ηsb (ξ) ∈ 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 observation x ∈ X1 and action a ∈ A, r1 (x, a) = 0. Atstage 2, for any observation (y, ξ) ∈ X2 and a ∈ A, we define r2 ((y, ξ), a) = I{y ∈ G} I{a = 0} + 21 I{a = 1} . Thus action 0 gives reward 1 and action 1 gives reward 1/2 in good secondlayer states, while all actions give reward 0 in the bad state B. The reward is endogenous: taking r̄1 ≡ 0 and r̄2 (y, a) = I{y ∈ G} I{a = 0} + 21 I{a = 1} gives rh (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 π̄1b (s) = s,
and π̄2b (y) = 1,
s ∈ {0, 1},
y ∈ S2 .
The corresponding observation-based expert policy π b : X → A is π1b (w) = b(w),
n
w ∈ {0, 1} ,
and
π2b (y, ξ) = 1,
y ∈ S2 , ξ ∈ Ξ 2 .
Thus π b is endogenous, since for any layer h and observation x ∈ Xh , πhb (x) = π̄hb (φ⋆h,b (x)). In endogenous coordinates, the expert is simple. In raw observation coordinates, the first-layer expert action is exactly the decoder b. b
π The expert always reaches a good state and then plays action 1, so JM = 1/2. By contrast, the policy that always b plays action 0 reaches a good state and receives reward 1, 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 class Q = {Qα,β : α, β ∈ [0, 1]}, where, for observations x ∈ X1 , (y, ξ) ∈ X2 , and action a ∈ A, the functions are defined as follows. α 1 α,β α,β and Q2 ((y, ξ), a) = β I{y ∈ G} I{a = 0} + I{a = 1} . Q1 (x, a) = I{a ∈ {0, 1}}, 2 2 Every function in Q is bounded by Qmax = 1. Importantly, the class Q does not depend on b. At layer 1, it does not distinguish the strings w ∈ {0, 1}n at all; it only distinguishes the safe actions 0, 1 from the unsafe action 2. For any function Q ∈ RX ×A , we will use the norm ∥Q∥∞ = maxh∈{1,2} maxx∈Xh maxa∈A |Qh (x, a)|. We start by showing that every expert in the family has the same Q-function, which is realizable by Q. b
b
Lemma C.2 (QπMb -realizability). For every b ∈ Bn , QπMb = Q1,1 ∈ Q. Proof of Lemma C.2. At layer 2, there is no future reward. Thus, for every (y, ξ) ∈ X2 and a ∈ A, b 1 QπMb ,2 ((y, ξ), a) = r2 ((y, ξ), a) = I{y ∈ G} I{a = 0} + I{a = 1} = Q1,1 2 ((y, ξ), a). 2 32
Appendix table of contents
At layer 1, the immediate reward is zero. Fix any observation w ∈ {0, 1}n . Its decoded endogenous state is s = φ⋆1,b (w) = b(w). If a ∈ {0, 1}, then the next endogenous state is Gs,a ∈ G. At layer 2, the expert plays action 1, b
receiving reward 1/2. Thus, for a ∈ {0, 1}, QπMb ,1 (w, a) = 1/2. If a = 2, then the next endogenous state is B. From b
B, every action receives reward 0, so QπMb ,1 (w, 2) = 0. Hence b
QπMb ,1 (w, a) =
1 I{a ∈ {0, 1}} = Q1,1 1 (w, a). 2
b
Combining the two layers gives QπMb = Q1,1 ∈ Q. We can then bound the covering number of the class Q 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 of [0, 1]2 inthe 1 any ε-grid ℓ∞ norm induces an ε-cover of Q. By Lemma E.5, such a grid has cardinality at most 2 ( ε + 1) . 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 metric dΠ . 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 class Q realizes the expert Q-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 max ∥πh − πh′ ∥∞,1 , 2 h∈{1,2}
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Π ) ≥ |Bn |. In particular, log2 Nε (Π, dΠ ) ≥ 2n − n − 1. If Π is finite, then also |Π| ≥ |Bn |. Proof of Lemma C.4. If b ̸= b′ are two different decoders in Bn , then there exists an observation w ∈ {0, 1}n such ′ ′ that b(w) ̸= b′ (w). As a result, π1b (w) = b(w) ̸= b′ (w) = π1b (w). Therefore, π b ̸= π b . Hence the map b 7→ π b is injective. Any finite policy class containing all experts {π b : b ∈ Bn } must therefore have cardinality at least |Bn |. ′
Moreover, if b ̸= b′ , then the deterministic policies π b and π b choose different actions at some observation w in stage 1. ′ Hence dΠ (π b , π b ) = 1. Thus {π b : b ∈ Bn } is a 1-packing under dΠ . A ball of radius ε < 1/2 cannot contain two distinct elements of this packing. Therefore every ε-cover of Π must contain at least |Bn | elements. Finally, the lower bound on the log-covering number follows from the lower bound on |Bn | shown in Appendix C.2.1.
33
Appendix 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 decoders b has exponential metric entropy, while (ii) a value-based guarantee under Qπ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 family {Mb : b ∈ Bn } defined in Appendix C.2.2 satisfies the following properties. 1. Uniform QπE -realizability. For every balanced decoder b ∈ Bn , the expert policy π b is deterministic and πb π endogenous in Mb . It is strictly suboptimal, with JM = 1/2 and supπ JM = 1. Moreover, the twob b dimensional class Q defined in Appendix C.2.3 realizes every expert action-value function in the family: for every b b ∈ Bn , QπMb = Q1,1 ∈ Q. In addition, for every ε ∈ (0, 1], 3 log Nε (Q, ∥·∥∞ ) ≤ 2 log . ε 2. Family-level policy lower bound. Let Π ⊂ ∆(A)X be any expert-agnostic policy class. If {π b : b ∈ Bn } ⊆ Π, then, for every ε ∈ (0, 1/2), log2 Nε (Π, dΠ ) ≥ 2n − n − 1. Proof of Theorem C.2. The validity of the ExBMDP construction and the fact that each π b is deterministic and endogeb nous follow from Appendix C.2.2. The return gap is also established in that section. The identity QπMb = Q1,1 ∈ Q for every b ∈ Bn follows from Lemma C.2. The covering-number bound for Q follows from Lemma C.3. The family-level policy lower bound follows from Lemma C.4. Why the policy needs the decoder but the Q-function does not. At layer 1, for any observation w, the expert’s action is π1b (w) = b(w). Thus exact behavioral cloning must recover the decoder b. However, the expert Q-function at the b b b same observation is QπMb ,1 (w, 0) = QπMb ,1 (w, 1) = 1/2, and QπMb ,1 (w, 2) = 0, which is independent of b(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 action 1 rather than action 0 at the second layer. This does not affect the tie-breaking mechanism at the first layer: actions 0 and 1 have the same expert Q-value, and recovering the exact expert policy still requires the decoder-dependent rule w 7→ b(w). Thus a simple Q-function can correspond to an enormous set of expert policies even when those experts are suboptimal. Making the expert’s first-layer action uniquely b optimal in this construction would force Qπ to encode the decoder, eliminating the present decoder-independent witness class. Why the exogenous structure matters. If the endogenous state s were observed directly, the expert would be the constant-complexity policy π̄1b (s) = s and π̄2b (y) = 1 on an endogenous state space of size 7. 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 = ηsb (ξ) ∈ {0, 1}n . Recovering the endogenous bit from the raw observation requires computing s = b(w). Thus the observation-based expert policy factors as π1b (w) = π̄1b (φ⋆1,b (w)) = b(w). Expert-policy realizability therefore requires b
representing the hard decoder. By contrast, Qπ is identical across decoders. This is why the same two-dimensional Q-class works uniformly for all decoders b, whereas any policy class that realizes all corresponding experts must be exponentially large.
34
Appendix 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 under QπE -realizability and no additional assumptions. As a representative offline algorithm that outputs a VI policy, we use SPOIL (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
Suboptimality
We start by investigating the performance of an offline VI-policies-based algorithm, such as SPOIL. 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 experiment 500 times, each time letting the adversary choose uniformly between the two environments M1 and M2 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 of M1 and M2 has suboptimality no smaller than the average. As Figure 3 shows, OVI reaches zero suboptimality, whereas SPOIL remains at the constant suboptimality predicted by our construction.
0.2 OVI (Ours) SPOIL Offline IL lower bound (0.25)
0.1
0.0 0
20
40
60
80
100
Number of expert queries τE
Figure 3: Experiment on the environment class used to prove Theorem 4.2.
D.2 Implementation 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 from dπhout 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 by OVI and compute an approximate saddle point by K iterations of the online learning algorithms. The resulting pseudocode is given in Algorithm 2. For the experiments, we set K = 50 while 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 via Soft DQN (Haarnoja et al., 2017) as in Moulin et al. (2025a). Moreover, we have observed that OVI’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 like CartPole-v1 and Acrobot-v1, we find that 10 trajectories collected offline (for SPOIL and BC) or online and then labeled by the expert (for OVI and DAgger) usually suffice to match the expert performance. In Figure 4, in more complicated environments such as LunarLander-v2 and Pendulum-v1, we increased the number of expert samples, but we did not find it necessary to increase the value of K. As baselines, we use DAgger (Ross et al., 2011), an interactive method requiring policy realizability. We also use standard BC (Pomerleau, 1991), an offline method requiring expert-policy realizability, and SPOIL (Moulin et al., 2025a), an offline method that does not require interactive expert access but assumes the stronger QΠ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 via DQN (Mnih et al., 2015) in Pendulum-v1 and PPO (Schulman et al., 2017) in CartPole-v1 and Acrobot-v1 and 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, BC and DAgger are expected to work well. Second, we considered smaller
35
Appendix table of contents
πE ∈ Π, Learner width = 64
Acrobot-v1
Pendulum-v1
CartPole-v1
LunarLander-v2
1
0 1 2 3
5
7
10
1 2 3
5
7
10
1 3 5 7
10
15
23
5
10
15
1 2 3
5
7
10
1 2 3
5
7
10
1 3 5 7
10
15
23
5
10
15
1 2 3
5
7
10
1 2 3
5
7
10
1 3 5 7
10
15
23
5
10
15
1 2 3
5
7
10
1 2 3
5
7
10
1 3 5 7
10
15
23
5
10
15
1 2 3
5
7
10
1 2 3
5
7 10 1 3 5 7 Number of trajectories
10
15
23
5
10
15
1
0.5
0
1 Learner width = 8
Normalized return
Learner width = 16
0.5
0.5
0
Learner width = 4
1
0.5
0
Learner width = 2
1
0.5
0
OVI (Ours) (online, value-based)
SPOIL
(offline, value-based)
DAgger (online, policy-based)
BC
(offline, policy-based)
Figure 4: Experiments in the Gymnasium library. 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 values {16, 8, 4, 2} neurons. The x-axis reports the number of expert trajectories for offline methods (BC and SPOIL) and the number of learner trajectories labeled with expert actions for DAgger and OVI. 36 Appendix table of contents
Algorithm 2 Stationary approximation of OVI for neural networks. 1: Initialize policy weights ψ0K and value network weights θ0K . 2: for ℓ = 1, . . . , nE do 3: Collect a state trajectory (xh,ℓ )H h=1 with the policy πψ K
ℓ−1
4: 5: 6: 7: 8: 9: 10:
# Warm-start initialization of policy and Q network parameters. K K θℓ1 = θℓ−1 , ψℓ1 = ψℓ−1 for k = 1, . . . , K − 1 do
# Update the policy weights.
Update ψℓk via SoftDQN (Haarnoja et al., 2017) using Qθℓk as the Q-network. # The argmax is approximated with several Adam iterations initialized at θℓk .
θℓk+1 ≊ arg maxθ∈Rd K . 12: Output the policy πψn 11:
.
Label the states with expert actions aEh,ℓ ∼ πE,h (· | xh,ℓ ) for each h ∈ [H].
Pℓ
s=1
PH
h=1
Qθ (xh,s , aEh,s ) − Qθ (xh,s , πψℓk ) .
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 like SPOIL and OVI to be more efficient as the expert–learner size gap increases. The aforementioned hypotheses are indeed confirmed by our experiments in CartPole-v1 and Acrobot-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 which OVI outperforms SPOIL. This suggests, therefore, that the network parametrization considered here is not powerful enough to represent the Q-functions of the policy sequence generated by the algorithm. An interesting additional observation is that in CartPole-v1 and Acrobot-v1, value-based methods clearly outperform policy-based ones. In contrast, in Pendulum-v1 and LunarLander-v2, the interactive methods, i.e., OVI and DAgger, 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. The Pendulum-v1 environment 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 that OVI outperforms the standard SPOIL, potentially because OVI imposes a weaker requirement on the representational power of the Q-class. The experts achieved the following average returns: 500 in CartPole-v1, −77.1 in Acrobot-v1, 270 in LunarLander-v2 and −176.6 in Pendulum-v1. The zero point on the y-axis is set to the following returns achieved by very suboptimal policies: −500 in Acrobot-v1, 8 in CartPole-v1, −1650.0 in Pendulum-v1 and −600 in LunarLander-v2. For each environment, we ran each IL algorithm 50 times with different random seeds from 0 to 49. 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 length T contributes ⌈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 the README file accompanying our code. For SPOIL and OVI, we approximate the policy update via Soft DQN learning over the Q-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.
37
Appendix table of contents
E
Technical Tools
E.1
Concentration
Lemma E.1 (Azuma–Hoeffding inequality; Boucheron et al., 2013, Section 1.1). Let X1 , . . . , Xn be a martingale difference sequence with respect to a filtration (Fi )ni=1 , i.e., E[Xi | Fi−1 ] = 0 and |Xi | ≤ M almost surely for all i ∈ [n]. Then, for any t > 0, " # n nt2 1X P Xi > t ≤ 2e− 2M 2 . n i=1 Equivalently, for any δ ∈ (0, 1), with probability at least 1 − δ, r n 1X 2 log(2/δ) Xi ≤ M . n i=1 n We recap the definition of covering numbers. Definition E.1 (Covering number). Let (M, d) be a metric space, S be a subset of M , and ϵ > 0. A set Cϵ (S, d) is an ϵ-covering of S if for any x ∈ S, there exists y ∈ Cϵ (S, d) such that d(x, y) ≤ ϵ. The covering number of S, Nϵ (S, d), is the minimum cardinality of any such covering of S. Moreover, we denote Cϵ (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 X ∥p − p′ ∥∞,1 := max |p(a | x) − p′ (a | x)|. (5) x∈X
a∈A
Given two functions Q, Q′ ∈ {f : X × A → [0, Qmax ]}, and two decision rules p, p′ ∈ ∆(A)X , define the scaled product metric ρ((Q, p), (Q′ , p′ )) := ∥Q − Q′ ∥∞ + Qmax ∥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 and Qh ⊆ {Qh : X × A → [0, Qmax ]} for every h ∈ [H]. For each h, let Fh−1 denote the history available before the samples for stage h are drawn. Let dh ∈ ∆(X ) be Fh−1 -measurable, and suppose that, conditionally on Fh−1 , xih ∼ dh , aiE,h ∼ πE,h · xih , i ∈ [nE ], are independent. For any p ∈ Πh and Qh ∈ Qh , define X Ldh (p, Qh ) := dh (x)⟨Qh (x, ·), πE,h (· | x) − p(· | x)⟩, x∈X nE 1 X Lbdh (p, Qh ) := Qh xih , aiE,h − Qh xih , p . nE i=1
Then, for any r > 0 and δ ∈ (0, 1), with probability at least 1 − δ, v u u 8 log 2 PH Nr (Qh × Πh , ρ)/δ t h=1 max sup sup Lbdh (p, Qh ) − Ldh (p, Qh ) ≤ 4r + Qmax . nE h∈[H] p∈Πh Qh ∈Qh If
(7)
PH
h=1 Nr (Qh × Π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
Nr (Qh × Πh , ρ) < ∞.
h=1
38
Appendix table of contents
Fix h and condition on Fh−1 . For a fixed pair (Qh , p) ∈ Qh × Πh , define Zi (Qh , p) = Qh xih , aiE,h − Qh xih , p − Ldh (p, Qh ). E Then (Zi (Qh , p))ni=1 is a conditionally independent mean-zero sequence and |Zi (Qh , p)| ≤ 2Qmax almost surely. By the Azuma–Hoeffding inequality (Lemma E.1), for every t > 0, h i nE t2 d d b . (8) P Lh (p, Qh ) − Lh (p, Qh ) ≥ t Fh−1 ≤ 2 exp − 2 8Qmax
For each h, choose a finite set Ch,r ⊆ Qh × Πh with cardinality Nr (Qh × Πh , ρ) such that every pair in Qh × Πh lies within distance r of some element of Ch,r under ρ. Applying Eq. (8) to all elements of these finite sets, then taking expectations and a union bound over h ∈ [H], gives an event of probability at least 1 − δ on which, for all h and all e h , pe) ∈ Ch,r , (Q v u u 8 log 2 PH Nr (Qh × Πh , ρ)/δ t h=1 e h − Ld pe, Q e h ≤ Qmax Lbdh pe, Q . (9) h nE e h , pe) ∈ Ch,r We work on this event and pass from the cover to the full class. Fix h, Qh ∈ Qh , and p ∈ Πh , and choose (Q such that eh Qh − Q + Qmax ∥p − pe∥∞,1 ≤ r. ∞
By the triangle inequality, nE nE X 1 X e h xi , ai e h xi , pe . eh ≤ 1 Qh xih , aiE,h − Q + Qh xih , p − Q Lbdh (p, Qh ) − Lbdh pe, Q h E,h h nE i=1 nE i=1
For every state x, e h (x, p) − Q e h (x, pe) e h (x, pe) ≤ Qh (x, p) − Q e h (x, p) + Q Qh (x, p) − Q eh ≤ Qh − Q
∞
+ Qmax ∥p − pe∥∞,1 .
Therefore, e h ≤ 2 Qh − Q eh Lbdh (p, Qh ) − Lbdh pe, Q
∞
+ Qmax ∥p − pe∥∞,1 ≤ 2r.
(10)
The same deterministic calculation, with empirical averages replaced by expectation under x ∼ dh and a ∼ πE,h (· | x), gives e h ≤ 2r. Ldh (p, Qh ) − Ldh pe, Q (11) Combining Eqs. (9) to (11) yields Eq. (7). Since h, p, and Qh 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 classes Qh ⊆ {Qh : X × A → [0, Qmax ]}, an integer K ≥ 0, and η > 0, define n P o j ΠQ := π : ∃m ∈ {0, . . . , K}, ∀h, ∃Q1h , . . . , Qm . h ∈ Qh , πh (a | x) = softmax η j Qh (x, ·) a
For each h, let ΠQ,h := {πh : π ∈ ΠQ }. When m = 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 every h ∈ [H] and every ε > 0, K X m Nε ΠQ,h , ∥·∥∞,1 ≤ 1 + Nε/(ηm) (Qh , ∥·∥∞ ) . (12) m=1
39
Appendix table of contents
Consequently, for the scaled product metric ρ in Eq. (6), for every r > 0, Nr (Qh × ΠQ,h , ρ) ≤
inf Nα (Qh , ∥·∥∞ ) 1 +
α∈(0,r)
K X
! m
N(r−α)/(Qmax ηm) (Qh , ∥·∥∞ )
.
(13)
m=1
In particular, the simpler bound r Nr (Qh × ΠQ,h , ρ) ≤ (K + 1)N 2 max{1,Q
K+1
max ηK}
(Qh , ∥·∥∞ )
(14)
also holds. Proof of Lemma E.3. Fix h and m ∈ {0, . . . , K}. If m = 0, the only decision rule represented with m functions is the uniform decision rule. Suppose now that m ≥ 1, and let Cs be an s-covering of Qh under ∥·∥∞ . Consider any j ej ej p ∈ ΠQ,h represented with this value of m by Q1h , . . . , Qm h ∈ Qh , and choose Qh ∈ Cs such that ∥Qh − Qh ∥∞ ≤ s for all j ∈ [m]. Define m X e j (x, ·). pe(· | x) = softmaxη Q h j=1
By 1-Lipschitz continuity of the softmax (Lemma E.8) and the triangle inequality, for every x ∈ X , ∥p(· | x) − pe(· | x)∥1 ≤ η
m X
ej Qjh − Q h
j=1
∞
≤ ηms,
e1 , . . . , Q e m in the last inequality. Taking s = ε/(ηm) gives a ε-covering for the where we used the definitions of Q h h decision rules represented with this value of m, of cardinality at most Nε/(ηm) (Qh , ∥·∥∞ )m . Taking the union over m = 0, . . . , K proves Eq. (12). For the product bound, fix α ∈ (0, r). Take an α-covering of Qh under ∥·∥∞ and an (r − α)/Qmax -covering of ΠQ,h under ∥·∥∞,1 . By definition of ρ, their Cartesian product is an r-covering of Qh × ΠQ,h under ρ. Applying Eq. (12) with ε = (r − α)/Qmax , and then taking the infimum over α, gives Eq. (13). To obtain Eq. (14), take α = r/2 in Eq. (13). If K = 0, the claim follows immediately. Suppose then that K ≥ 1. The radius r/(2 max{1, Qmax ηK}) is at most r/2 and at most r/(2Qmax ηm) for every 1 ≤ m ≤ K. Thus, by monotonicity of covering numbers, r Nr/2 (Qh , ∥·∥∞ ) ≤ N 2 max{1,Q
max ηK}
(Qh , ∥·∥∞ ),
N 2Qmaxr ηm (Qh , ∥·∥∞ )
m
r ≤ N 2 max{1,Q
K
max ηK}
(Qh , ∥·∥∞ ) .
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 each Qh is convex. Then, for every h ∈ [H] and every ε > 0, K X Nε ΠQ,h , ∥·∥∞,1 ≤ 1 + Nε/(ηm) (Qh , ∥·∥∞ ).
(15)
m=1
Consequently, for the scaled product metric ρ in Eq. (6), for every r > 0, Nr (Qh × ΠQ,h , ρ) ≤
inf Nα (Qh , ∥·∥∞ ) 1 +
α∈(0,r)
K X
! N(r−α)/(Qmax ηm) (Qh , ∥·∥∞ ) .
(16)
m=1
In particular, the simpler bound r Nr (Qh × ΠQ,h , ρ) ≤ (K + 1)N 2 max{1,Q
2
max ηK}
(Qh , ∥·∥∞ )
(17)
also holds. 40
Appendix table of contents
Proof of Lemma E.4. Fix h and m ∈ {0, . . . , K}. The case m = 0 again gives the uniform decision rule. Suppose that m ≥ 1, and let p ∈ ΠQ,h be represented with this value of m by Q1h , . . . , Qm h ∈ Qh . Define m
Qh =
1 X j Q . m j=1 h
By convexity, Qh ∈ Qh , and p(· | x) = softmax(ηmQh (x, ·)) for every x ∈ X . Let Cs be an s-covering of Qh under e h ∈ Cs such that ∥Qh − Q e h ∥∞ ≤ s, and define ∥·∥∞ , choose Q e h (x, ·) . pe(· | x) = softmax ηmQ e h , for every x ∈ X , By 1-Lipschitz continuity of the softmax (Lemma E.8) and the definition of Q eh ∥p(· | x) − pe(· | x)∥1 ≤ ηm Qh − Q
∞
≤ ηms.
Taking s = ε/(ηm) gives a ε-covering for the decision rules represented with this value of m, of cardinality at most Nε/(ηm) (Qh , ∥·∥∞ ). Taking the union over m = 0, . . . , K proves 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/2 in Eq. (16). If K = 0, the claim follows immediately. Suppose then that K ≥ 1. The radius r/(2 max{1, Qmax ηK}) is at most r/2 and at most r/(2Qmax ηm) for every 1 ≤ m ≤ K. Thus, by monotonicity of covering numbers, r Nr/2 (Qh , ∥·∥∞ ) ≤ N 2 max{1,Q
max ηK}
(Qh , ∥·∥∞ ),
r N 2Qmaxr ηm (Qh , ∥·∥∞ ) ≤ N 2 max{1,Q
max ηK}
(Qh , ∥·∥∞ ).
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). Let d ∈ N, R > 0, and let Bd∞ (R) denote the ℓ∞ ball of radius R in Rd . Then, for every ε > 0, d 2R Nε Bd∞ (R), ∥·∥∞ ≤ +1 . ε
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 set V , an arbitrary sequence of adaptively chosen loss vectors (ℓk )K k=1 such that ∥ℓk ∥∞ ≤ ℓmax , and let D : V × int(V ) → R be a Bregman divergence induced by a λ-strongly convex function in the ℓ1 norm. Then, for all u ∈ V , the sequence (xk )K k=1 generated for each k by 1 xk+1 = arg min ⟨ℓk , v⟩ + D(v, xk ) η v∈V for an initial x1 ∈ int(V ) and under the assumption that xk ∈ int(V ) for every k ∈ [K + 1] satisfies K X k=1
⟨ℓk , xk − u⟩ ≤
D(u, x1 ) ηKℓ2max + . η 2λ
Lemma E.7 (FTRL over the simplex). Let P ∆(A) be the simplex over a discrete action space A, and for any x ∈ ∆(A), define the Shannon entropy as H(x) = − a∈A x(a) log x(a). Consider the sequence (xk )K k=1 generated via FTRL using the potential −H(x) − minx′ ∈∆(A) (−H(x′ )) ψk (x) = . ηk 41
Appendix table of contents
That is, for a certain sequence of cost vectors ℓ1 , . . . , ℓK we have * k−1 + Pk−1 X e−ηk k′ =1 ℓk′ xk = arg min x, ℓk′ + ψk (x) = P . P −ηk k−1 ℓ ′ (a) k′ =1 k x∈∆(A) k′ =1 a∈A e Then, if ∥ℓk ∥∞ ≤ ℓmax and ηk =
q
log(A) ⋆ ℓ2max k , it holds that for any K ∈ N and any x ∈ ∆(A), K X
⟨ℓk , xk − x⋆ ⟩ ≤ 3
p ℓ2max log|A|K.
k=1
Proof of Lemma E.7. Let us define the function Fk (x) = −
K X
Pk−1
k′ =1 ⟨ℓk , x⟩ + ψk (x). Then, by definition, we have ′
⟨ℓk , x⋆ ⟩ = ψK+1 (x⋆ ) − FK+1 (x⋆ ) .
k=1
Adding and subtracting FK+1 (xK+1 ) and F1 (x1 ) and noticing that x1 minimizes F1 = ψ1 over the simplex, we obtain −
K X
⟨ℓk , x⋆ ⟩ = ψK+1 (x⋆ ) − FK+1 (x⋆ ) − FK+1 (xK+1 ) + FK+1 (xK+1 ) − min ψ1 (x) + F1 (x1 ). x∈∆(A)
k=1
Now, writing the difference F1 (x1 ) − FK+1 (xK+1 ) as a telescoping sum, we have −
K X
⟨ℓk , x⋆ ⟩ = ψK+1 (x⋆ ) − FK+1 (x⋆ ) +
K X
(Fk (xk ) − Fk+1 (xk+1 )) + FK+1 (xK+1 ) − min ψ1 (x) , x∈∆(A)
k=1
k=1
Finally, adding
PK
k=1 ⟨ℓk , xk ⟩ to both sides, we obtain
K X
⟨ℓk , xk − x⋆ ⟩ = ψK+1 (x⋆ ) − FK+1 (x⋆ ) +
k=1
K X
(Fk (xk ) − Fk+1 (xk+1 ) + ⟨ℓk , xk ⟩)
k=1
+ FK+1 (xK+1 ) − min ψ1 (x). x∈∆(A)
Using that ψk (x) ≥ 0 for all k and x ∈ ∆(A), and FK+1 (x⋆ ) ≥ FK+1 (xK+1 ) (by definition of xK+1 ), we obtain K X
⟨ℓk , xk − x⋆ ⟩ ≤ ψK+1 (x⋆ ) +
k=1
K X
(Fk (xk ) − Fk+1 (xk+1 ) + ⟨ℓk , xk ⟩).
k=1
At this point, note Fk (xk ) − Fk+1 (xk+1 ) + ⟨ℓk , xk ⟩ (a)
= Fk (xk ) + ⟨ℓk , xk ⟩ − (Fk+1 (xk+1 ) + ⟨ℓk , xk+1 ⟩) + ⟨ℓk , xk+1 ⟩
(b)
= Fk (xk ) + ⟨ℓk , xk ⟩ − (Fk (xk+1 ) + ⟨ℓk , xk+1 ⟩) + ⟨ℓk , xk+1 ⟩ + Fk (xk+1 ) − Fk+1 (xk+1 )
(c)
= Fk (xk ) + ⟨ℓk , xk ⟩ − (Fk (xk+1 ) + ⟨ℓk , xk+1 ⟩) + Fk+1 (xk+1 ) − ψk+1 (xk+1 ) + ψk (xk+1 ) − Fk+1 (xk+1 )
(d)
= Fk (xk ) + ⟨ℓk , xk ⟩ − (Fk (xk+1 ) + ⟨ℓk , xk+1 ⟩) − ψk+1 (xk+1 ) + ψk (xk+1 ) ,
where we (a) added and removed a term ⟨ℓk , xk+1 ⟩, (b) added and removed a term Fk (xk+1 ), (c) used the fact that ⟨ℓk , xk+1 ⟩ + Fk (xk+1 ) = Fk+1 (xk+1 ) − ψk+1 (xk+1 ) + ψk (xk+1 ) by definition of Fk , and (d) rearranged terms.
42
Appendix table of contents
For any x ∈ RA , we define ι∆(A) (x) = 0 if x ∈ ∆(A) and ι∆(A) (x) = ∞ otherwise. Then, since both xk+1 and xk are in ∆(A), it holds that Fk (xk ) − Fk+1 (xk+1 ) + ⟨ℓk , xk ⟩ = Fk (xk ) + ⟨ℓk , xk ⟩ + ι∆(A) (xk ) − Fk (xk+1 ) + ⟨ℓk , xk+1 ⟩ + ι∆(A) (xk+1 )
− ψk+1 (xk+1 ) + ψk (xk+1 ) . Since ψk is ηk−1 -strongly convex, the function Fk + ⟨ℓk , ·⟩ + ι∆(A) is also ηk−1 -strongly convex. Hence, writing ∂ for the subdifferential, for any subgradient gk ∈ {ℓk } + ∂(Fk + ι∆(A) )(xk ), we have Fk (xk ) + ⟨ℓk , xk ⟩ + ι∆(A) (xk ) − Fk (xk+1 ) + ⟨ℓk , xk+1 ⟩ + ι∆(A) (xk+1 ) 1 2 ≤ −⟨gk , xk+1 − xk ⟩ − ∥xk − xk+1 ∥1 . 2ηk Since xk = arg minx∈∆(A) (Fk + ι∆(A) )(x), we obtain that 0 ∈ ∂(Fk + ι∆(A) )(xk ), which implies that we can choose gk = ℓk . Plugging this back into the previous display, we obtain that Fk (xk ) − Fk+1 (xk+1 ) + ⟨ℓk , xk ⟩ 1 2 ≤ ⟨ℓk , xk − xk+1 ⟩ − ∥xk − xk+1 ∥1 − ψk+1 (xk+1 ) + ψk (xk+1 ) 2ηk (a) 1 2 ≤ ∥ℓk ∥∞ ∥xk − xk+1 ∥1 − ∥xk − xk+1 ∥1 − ψk+1 (xk+1 ) + ψk (xk+1 ) 2ηk (b) η k 2 ≤ ∥ℓk ∥∞ − ψk+1 (xk+1 ) + ψk (xk+1 ) 2 (c)
2
≤ ηk ∥ℓk ∥∞ , 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 , xk − x⋆ ⟩ ≤ ψK+1 (x⋆ ) +
k=1
K X
2
ηk ∥ℓk ∥∞ .
k=1
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) =
maxx∈∆(A) H(x) −H(x) − minx∈∆(A) (−H(x)) log(A) ≤ ≤ . ηK+1 ηK+1 ηK+1
Therefore, we obtain K X
K
⟨ℓk , xk − x⋆ ⟩ ≤
k=1
Then, choosing ηk = K X
q
log(A) X 2 + ηk ∥ℓk ∥∞ . ηK+1 k=1
log(A) 2 2 ℓ2max k and using the fact that ∥ℓk ∥∞ ≤ ℓmax , we obtain that
⋆
⟨ℓk , xk − x ⟩ ≤
p
ℓ2max log(A)(K + 1) +
K X k=1
k=1
p
r
p ℓ2max log(A) ≤ 3 ℓ2max log(A)K. k
Here, the last inequality follows by factoring out ℓ2max log(A) and using √ √ and K + 1 ≤ K + 1. This concludes the proof.
PK
k=1
√ RK 1 √1 ≤ 1 + √ dx = 2 K − 1, 1 x k
Lemma E.8 (Softmax Lipschitzness). For any finite action set A and any u, v ∈ RA , ∥softmax(u) − softmax(v)∥1 ≤ ∥u − v∥∞ . 43
Appendix 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 the 1-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 the 1-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 its 1-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 expresses 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, H X X
′
Jπ − Jπ =
dπh (x)
h=1 x∈X
X
′
(πh′ (a | x) − πh (a | x))Qπh (x, a).
(18)
a∈A
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 X ′ π′ Qπh (x, a) = rh (x, a) + Ph (x′ | x, a)Vh+1 (x′ ). x′ ∈X
Then, taking the expectation with respect to the state-action occupancy measure of the policy π, we have X X X X ′ π′ dπh (x, a)Qπh (x, a) = dπh (x, a)rh (x, a) + dπh (x, a) Ph (x′ | x, a)Vh+1 (x′ ). x,a
x,a
x,a
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′ Ph (x | x , a )dh (x , a ), observe that ! X X X X π ′ π′ ′ ′ π π′ dh (x, a) Ph (x | x, a)Vh+1 (x ) = Ph (x | x, a)dh (x, a) Vh+1 (x′ ) x′
x,a
x′
=
X
x,a π′ dπh+1 (x′ )Vh+1 (x′ ).
x′
This implies that D E D E D E D E ′ ′ ′ π′ − dπh , Vhπ . dπh , Qπh − dπh , Vhπ = ⟨dπh , rh ⟩ + dπh+1 , Vh+1 ′
π Then, summing over h ∈ [H] and recalling that VH+1 = 0 and that ν0 = dπ1 , we obtain that H D X
dπh , Qπh
′
E
H D E X D E ′ ′ ′ − dπh , Vhπ = ⟨dπh , rh ⟩ − ν0 , V1π = J π − J π .
h=1
h=1
Finally, rearranging, we have ′
Jπ − Jπ =
H D X
dπh , Qπh
′
E
D E ′ − dπh , Vhπ
h=1
=
H X X
! dπh (x)
X
h=1 x
=
H X X h=1 x
′ ′ πh (a | x)Qπh (x, a) − Vhπ (x)
a
dπh (x)
X
′
(πh (a | x) − πh′ (a | x))Qπh (x, a),
a ′
where we used dπh (x, a) = dπh (x)πh (a | x) and the definition of Vhπ . Multiplying by −1 concludes the proof.
44
Appendix 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, OVI reduces the suboptimality gap to a sequence of saddle-point problems involving the objective Ldh 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 denote Lπh = Ldh for convenience. When learning layer h, the previously computed decision rules πout,1 , . . . , πout,h−1 allow us to sample from dπhout . Thus, for each i ∈ [nE ], OVI independently samples xih ∼ dπhout and aiE,h ∼ πE,h · xih . For h = 1, we can sample from dπ1 out = ν0 . For subsequent stages h, we can sample from dπhout by rolling in with the previously computed policies πout,1 , . . . , πout,h−1 . Given these samples, for any decision rule p and function f ∈ RX ×A , we define the empirical estimate of Lπhout as nE 1 X Lbh (p, f ) = f xih , aiE,h − f xih , p . nE i=1
For the version of OVI analyzed in Theorem F.1, the empirical game is solved by having the Q-player best respond to Lbh (πhk , ·), while the π-player uses online mirror ascent (Beck and Teboulle, 2003) with negative entropy as a regularizer. Fixing a stage h, for each k, Qkh ∈ arg max Lbh πhk , Qh , and πhk+1 ∝ πhk ⊙ exp ηQkh , (19) Qh ∈Qh
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 the Q-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 nE . Lemma F.1. Let Assumption 2.1 hold. Let policies πh1 , . . . , πhK and functions Q1h , . . . , QK h ∈ Q be computed as in PK π k Eq. (19). We define the π-regret at stage h and state x as Rh (x) = k=1 ⟨Qh (x, ·), πE,h (· | x)−πhk (· | x)⟩. Furthermore, for any policy π, we define the estimation error as ∆(π) = maxh∈[H] supQh ∈Qh |Lbh (πh , Qh ) − Lπhout (πh , Qh )|, where PK 1 k πout,h = K k=1 πh . Then, J πE − J πout ≤
H
K
h=1 x∈X
k=1
1 X X πout 2H X dh (x)Rπh (x) + ∆ πk . K K
Proof of Lemma F.1. By the performancePdifference lemma (Lemma E.9) with π = πout and π ′ = πE , and by the H definition of Lπhout , we have J πE − J πout = h=1 Lπhout (πout,h , QπhE ). Since Lπhout (p, Q) is affine in the decision rule p P K 1 k and πout,h = K k=1 πh , this gives J
πE
−J
πout
=
H X
H
Lπhout (πout,h , QπhE ) =
h=1
K
1 X X πout k πE Lh πh , Qh . K h=1 k=1
45
Appendix table of contents
Then, we can upper bound the suboptimality as follows K(J πE − J πout ) =
X
X (a) X Lπhout πhk , QπhE ≤ Lbh πhk , QπhE + H ∆ πk
h,k (b) X
≤
h,k
k
X X (a) X πout k k Lbh πhk , Qkh + H ∆ πk ≤ Lh πh , Qh + 2H ∆ πk ,
h,k
k
h,k
k
where step (a) uses the definition of ∆(π k ) together with QπhE ∈ Qh in the first application and Qkh ∈ Qh in the second, and step (b) uses that Qkh is a best response to Lbh (πhk , ·) over Qh . Finally, by expanding the definition of Lπhout and exchanging the finite sums over k, x, and a, K X
Lπhout (πhk , Qkh ) =
k=1
X x∈X
dπhout (x)
K X
X
⟨Qkh (x, ·), πE,h (· | x) − πhk (· | x)⟩ =
dπhout (x)Rπh (x).
x∈X
k=1
This concludes the proof. Next, we use Lemma F.1 to derive a sample complexity guarantee for OVI. 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 ensure that Rπh (x) grows sublinearly in K for each stage h and state x ∈ 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 P iterate belongs to the policy class ΠQ := {π : ∃m ≤ K, ∀h, ∃Q1h , . . . , Qm ∈ Q , π (a | x) = softmax( Qk (x, ·))a } for some h h h Pk K h 1 −1 K = poly(H, log A, Qmax , ε ), and concentration uniformly over ΠQ × Q controls K k=1 ∆(π k ) with a sufficiently large number of expert queries nE . 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 of OVI). Let Assumption 2.1 hold for a finite class Q. Then, for any ε, δ ∈ (0, 1), e 4 Q4 log(A) log(|Q|/δ)ε−4 ), η = (log(A)/(KQ2 ))1/2 , and K = OVI (Algorithm 1) with parameters nE = O(H max max 2 2 −2 O(H Qmax log(A)ε ), outputs a policy πout such that with probability at least 1 − δ, J πE − J πout ≤ ε after 5 4 e H Qmax log(A) log(|Q|/δ) expert queries. O ε4 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 class Q. 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 of OVI is controlled by the largest ℓ∞ -covering number of e 3 Q2max log(Nrmax (Q)/δ)ε−2 ) for Qh over h ∈ [H], and that when Q is convex, the sample complexity improves to O(H ε 2 some rε = O(ε ). When the classes are infinite, the best responses in the Q-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 each Qh is compact and the empirical objective optimized by the Q-player is continuous on Qh . Theorem F.1 (Sample complexity of OVI). Let Assumption 2.1 hold. For every r > 0, let Nrmax (Q) be the largest ℓ∞ -covering number (see Definition E.1) of Qh over h ∈ [H], and choose rε = O(ε2 /(H 2 Qmax log A)). Then, for any ε, δ ∈ (0, 1), OVI (Algorithm 1) with parameters s ! 2 2 4 4 max H Q log(A) log N (Q)/δ log(A) H Qmax log(A) max r ε e η= ,K = O , and nE = O , KQ2max ε2 ε4 46
Appendix table of contents
outputs a policy πout such that, with probability at least 1 − δ, J πE − J πout ≤ ε after ! H 5 Q4max log(A) log Nrmax (Q)/δ ε e expert queries. O ε4 e 2 Q2max log(Nrmax (Q)/δ)ε−2 ), and the sample Moreover, when Q is convex, the same guarantee holds with nE = O(H ε 3 2 max −2 e complexity improves to O(H Qmax log(Nrε (Q)/δ)ε ). Proof of Theorem F.1. To prove the sample complexity guarantees of Algorithm 1, we start from the decomposition given in Lemma F.1. H K 1 X X πout 2H X dh (x)Rπh (x) + ∆ πk . J πE − J πout ≤ K K h=1 x∈X
k=1
We need to control the regret of the policy player Rπh , defined for any state x as Rπh (x) =
K X
Qkh (x, ·), πE,h (· | x) − πhk (· | x) ,
k=1 1 and we need to control the average estimation error K
PK
k=1 ∆(π
k
), where, for any policy π, we define
∆(π) = max sup Lbh (πh , Qh ) − Lπhout (πh , Qh ) . h∈[H] Qh ∈Qh
Controlling the regret Rπh . In order to control Rπh , we use online mirror ascent with negative-entropy regularizer, which corresponds to the following update rule for each stage h ∈ [H], iteration k ∈ [K], state x ∈ X and action a ∈ A, k πhk+1 (a | x) ∝ πhk (a | x)eηQh (x,a) . Fix h and x. Applying Lemma E.6 to the simplex with losses ℓk = −Qkh (x, ·) and comparator u = πE,h (· | x) gives Rπh (x) ≤
log|A| + ηKQ2max , η
where we used that the initial decision rule is uniform, so the negative-entropy Bregman divergence to any comparator is at most log|A|, and that each Qh ∈ Qh satisfies ∥Qh ∥∞ ≤ Qmax , as assumed in Assumption p 2.1. Plugging the value π of η from the statement of Theorem F.1, η = (log(A)/K)1/2 Q−1 , we get that R (x) ≤ 2 KQ2max log|A|. Since dπhout max h 2 2 −2 is a probability distribution for every h, setting K = 36H Qmax log(A)ε implies r H ε 1 X X πout H 2 Q2max log|A| π dh (x)Rh (x) ≤ 2 = . K K 3 h=1 x∈X
PK 1 k Controlling the estimation error. It remains to control the average estimation error K k=1 ∆(π ). To this end, π recall that, in Algorithm 1, we build the empirical estimator Lbh by sampling nE states from dhout . This sampling is possible because dπhout 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 ∈ [nE ], we sample xih ∼ dπhout and aiE,h ∼ πE,h · xih . For every k ∈ [K], the policy π k belongs to the class ΠQ ⊂ ∆(A)X defined below. n P o j ΠQ := π : ∃m ∈ {0, . . . , K}, ∀h, ∃Q1h , . . . , Qm Q (x, ·) . h ∈ Qh , πh (a | x) = softmax η j h a
For each h, write ΠQ,h := {πh : π ∈ ΠQ } for the corresponding class of decision rules. We upper bound the average estimation error by K
1 X ∆ π k ≤ sup ∆(π) ≤ max sup sup Lbh (p, Qh ) − Lπhout (p, Qh ) . K h∈[H] p∈ΠQ,h Qh ∈Qh π∈ΠQ k=1
47
Appendix table of contents
To control the upper bound, we verify that we can apply the concentration argument from Lemma E.2. Fix h, p ∈ ΠQ,h , and Qh ∈ Qh , and define Yi (Qh , p) := Qh xih , aiE,h − Qh xih , p − Lπhout (p, Qh ). E Conditionally on the history before the samples for stage h are drawn, dπhout is fixed and (Yi (Qh , p))ni=1 is a martingale X ×A i i i difference sequence. Moreover, since Qh ∈ [0, Qmax ] , both Qh (xh , aE,h ) and Qh (xh , p) belong to [0, Qmax ], while Lπhout (p, Qh ) belongs to [−Qmax , Qmax ]. Hence
|Yi (Qh , p)| ≤ 2Qmax
almost surely.
Applying Lemma E.2 with dh = dπhout and Πh = ΠQ,h therefore gives, for any radius r > 0, with probability at least 1 − δ, v u u 8 log 2 PH Nr (Qh × ΠQ,h , ρ) t h=1 δ sup ∆(π) ≤ 4r + Qmax . nE π∈ΠQ
(20)
Taking r = ε/(24H) and ! H 2X 288H 2 Q2max Nε/(24H) (Qh × ΠQ,h , ρ) log nE ≥ ε2 δ h=1
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 H
K
2H X 1 X X πout ∆ πk dh (x)Rπh (x) + K K h=1 x∈X k=1 v u r u 8 log 2 PH N t h=1 ε/(24H) (Qh × ΠQ,h , ρ) δ H 2 Q2max log|A| ε ≤2 + + 2HQmax K 3 nE ε ε ε ≤ + + , 3 3 3
J πE − J πout ≤
where the last line uses K = 36H 2 Q2max log(A)ε−2 and ! PH 2 h=1 Nε/(24H) (Qh × ΠQ,h , ρ) 288H 2 Q2max nE ≥ log . ε2 δ Next, we consider separately the convex and nonconvex cases for the classes Qh , and show that the sample complexity improves in the convex case. Convex case. Assume first that each Qh is convex. Fix h ∈ [H]. By Lemma E.4, more precisely by Eq. (17), for every radius r > 0, 2 r Nr (Qh × ΠQ,h , ρ) ≤ (K + 1)N 2 max{1,Q (Qh , ∥·∥∞ ) . ηK} max
If ε ≥ Qmax , reward normalization gives J πE − J πout ≤ Qmax ≤ ε, so the performance claim is immediate. We may therefore assume that ε < Qmax . For the parameter choice in the theorem, Qmax ηK =
p
K log|A| =
6HQmax log|A| . ε
Since H ≥ 1 and A ≥ 2, we then have Qmax ηK > 6H log 2 > 1. Hence max{1, Qmax ηK} = Qmax ηK in the remaining covering estimates. We now plug this stagewise bound into the estimation guarantee. With the radius r = ε/(24H) used in Eq. (20), the product bound above implies H X
2
Nε/(24H) (Qh × ΠQ,h , ρ) ≤ H(K + 1) max N 48HQεmax ηK (Qh , ∥·∥∞ ) . h∈[H]
h=1
48
Appendix table of contents
Combining the bound above with the sufficient condition on nE in the preceding paragraph, it is enough to take 2H(K + 1) 288H 2 Q2max 2 ε log nE ≥ max N (Q , ∥·∥ ) . h ∞ 48HQmax ηK ε2 δ h∈[H] Substituting the values of K and Qmax ηK, the following order of expert queries per stage suffices: !! H 1 + 36H 2 Q2max log|A|/ε2 H 2 Q2max 2 log (Qh , ∥·∥∞ ) max N nE = O ε2 ε2 δ h∈[H] 288H 2 Qmax log|A| 2 2 H Qmax 1 e =O log (Qh , ∥·∥∞ ) . max N ε2 ε2 δ h∈[H] 288H 2 Qmax log|A| Since the algorithm queries the expert at H stages, the total number of expert queries is 3 2 e H Qmax log 1 max N 2 (Q , ∥·∥ ) . HnE = O ε h ∞ ε2 δ h∈[H] 288H 2 Qmax log|A| Nonconvex classes. We now turn to the general case. Fix h ∈ [H]. By Lemma E.3, more precisely by Eq. (14), and since the case split above gives Qmax ηK > 1, for every radius r > 0, K+1
Nr (Qh × ΠQ,h , ρ) ≤ (K + 1)N 2Qmaxr ηK (Qh , ∥·∥∞ )
.
With the radius r = ε/(24H) used in Eq. (20), the product bound above implies H X
Nε/(24H) (Qh × ΠQ,h , ρ) ≤ H(K + 1) max N 48HQεmax ηK (Qh , ∥·∥∞ )
K+1
h∈[H]
h=1
.
Combining the bound above with the sufficient condition on nE in the preceding paragraph, it is enough to take 288H 2 Q2max 2H(K + 1) K+1 ε nE ≥ log max N (Q , ∥·∥ ) . h ∞ 48HQmax ηK ε2 δ h∈[H] Substituting the values of K and Qmax ηK, the following order of expert queries per stage suffices: !! H 1 + 36H 2 Q2max log|A|/ε2 H 2 Q2max 1+36H 2 Q2max log|A|/ε2 nE = O log max N (Qh , ∥·∥∞ ) ε2 ε2 δ h∈[H] 288H 2 Qmax log|A| 4 4 e H Qmax log|A| log 1 max N 2 (Q , ∥·∥ ) . =O ε h ∞ ε4 δ h∈[H] 288H 2 Qmax log|A| Since the algorithm queries the expert at H stages, the total number of expert queries is 5 4 e H Qmax log|A| log 1 max N HnE = O (Q , ∥·∥ ) . ε2 h ∞ ε4 δ h∈[H] 288H 2 Qmax log|A| This concludes the proof.
F.2
Proof of Theorem 3.2 (Reward Realizability Is Insufficient)
So far, we showed that, under Qπ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: when H = 1, QπE -realizability reduces to reward realizability, and Joshi et al. (2026) show that reward realizability 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. 49
Appendix table of contents
ν0 x0start = 1 − Xq
ν0 x1start = q
x0+
a = b0 = 0
x1+
a = b1
x0start
ν0 xistart = q a = bi
x1start a ̸= b0
xistart a ̸= b1
x0−
xi+
a ̸= bi
x1−
xi−
Figure 5: Instance from the family used in Theorem 3.2. Every MDP in the family uses the same reward, and the hidden bit bi ∈ {0, 1} selects which action reaches xi+ from xistart . It remains hidden unless xistart is observed during training. Theorem 3.2 (Lower bound under reward realizability). For every X ≥ 1 and ε ∈ (0, 1/4], there exists a family F of MDPs with: i) stochastic initial states but deterministic rewards and transitions, ii) horizon H = 2, iii) state space size |X | = O(X), and iv) family size log(|F|) = O(X), such that for every M ∈ F, Assumption 3.2 is satisfied by the same singleton reward class R = {r⋆ }. Let Alg be any interactive IL algorithm (Definition 3.1). Then, there exists ⋆ an MDP M ∈ F, with corresponding expert πE = πM , such that Alg needs Ω Xε rounds of interactions to output a πE πout 12 policy πout such that E[JM − JM ] ≤ ε. Comparison with Qπ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 vector b ∈ {0, 1}X , the common reward only identifies xi+ as rewarding and xi− as non-rewarding but it does not reveal which action from xistart reaches xi+ . By contrast, for each instance Mb , the expert value function πb
satisfies QME b ,1 (xistart , a) = 1{a = bi }. Thus QπE stores the information about which action to take at the starting state itself. Equivalently, a value class that QπE -realizes all MDPs in this family must contain one distinct function for each b ∈ {0, 1}X , so its complexity already scales with X. 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. Set q = 4ε/X, which satisfies q ≤ 1/X because ε ≤ 1/4. We first define the hard family H = HX,q . Let the action space be A = {0, 1}. For each i ∈ {0, . . . , X}, the state space contains a start state xistart and two terminal states xi+ and xi− . The initial distribution is ν0 x0start = 1 − Xq, and ν0 xistart = q for i ∈ [X]. For b = (b1 , . . . , bX ) ∈ {0, 1}X , set b0 = 0. In the MDP Mb , the first transition is deterministic and given by P1b xi+ xistart , a = 1{a = bi }, and P1b xi− xistart , a = 1{a ̸= bi }. All stage-two behavior is fixed independently of b. For concreteness, let the expert’s terminal action be 0, and take any fixed terminal transitions. The reward is common to all instances. For any index i and action a, r1⋆ (xistart , a) = 0,
r2⋆ (xi+ , a) = 1,
r2⋆ (xi− , a) = 0.
Thus the singleton class R = {r⋆ } realizes every instance in the family. Let the expert in Mb be the deterministic b policy πE,1 (xistart ) = bi , with the fixed terminal behavior described above. The expert reaches xi+ from every xistart , so πb
it is optimal and JME b = 1. The family is illustrated in Figure 5. For any policy π, starting from xistart yields terminal reward one if and only if the first action equals bi . Hence πb
π JME b − JM =1− b
X X
X X ν0 xistart π1 bi xistart = ν0 xistart π1 A \ {bi } xistart .
i=0
(21)
i=0
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.
50
Appendix table of contents
We lower bound the average suboptimality gap over a random instance. Let B = (B1 , . . . , BX ) ∼ Unif({0, 1}X ), and run Alg on MB . Let ξ be an independent random seed encoding all of the algorithm’s internal randomness, and let D denote the complete interaction transcript available to the learner after the fixed nE episodes. For each i ∈ [X], let Vi be the event that xistart appears as the initial state in one of the fixed nE interaction rounds. Although Bi is sampled uniformly initially, we later condition on the dataset used to choose πout . This conditioning can matter because D is generated in the MDP whose expert policy and transitions depend on Bi . If Vi occurs, then D contains a transition out of xistart . No matter whether an expert action is observed or not, the transition out of xistart reveals which action reaches xi+ . On Vic , however, D contains no observation from the i-th component of the construction: the state xistart can only appear as an initial state, and no transition from any other component reaches it. Thus, conditional on Vic , D may depend on the coordinates Bj for j ̸= i, but the conditional law of (D, ξ) does not depend on Bi . Since Bi is uniform and independent of Bj for j ̸= i, even after seeing the dataset and knowing Vic , we still have no information about Bi . Whenever P[Vic ] > 0, this gives P[Bi = 0 | D, Vic , ξ] = P[Bi = 1 | D, Vic , ξ] =
1 . 2
Conditional on D, Vic , and ξ, the output policy is fixed. We define pi := πout,1 (1 | xistart ). The quantity that appears in the suboptimality gap for the i-th component is πout,1 (A \ {Bi } | xistart ), which is the probability that the output policy chooses the wrong first action at xistart . If Bi = 0, action 1 is wrong, and this quantity equals pi . If Bi = 1, action 0 is wrong, and this quantity equals 1 − pi . When P[Vic ] > 0, averaging over D and ξ and multiplying by P[Vic ] gives the identity below; when P[Vic ] = 0, the identity is trivial. Hence 1 E πout,1 (A \ {Bi } | xistart )1{Vic } = P[Vic ]. (22) 2 Because nE is a fixed deterministic budget and the initial state in each interaction round is sampled independently from ν0 , the event Vic has probability P[Vic ] = (1 − q)nE . Combining Eqs. (21) and (22) with this identity and discarding the nonnegative contribution of x0start gives X h B i X Xq πE πout (1 − q)nE . E JMB − JMB ≥ qE πout,1 (A \ {Bi } | xistart )1{Vic } = 2 i=1
(23)
Since the left-hand side averages uniformly over B, there exists a fixed b ∈ {0, 1}X such that h b i Xq π πout (1 − q)nE . E JME b − JM ≥ b 2 If nE < X/(8ε), Bernoulli’s inequality gives (1 − q)nE = (1 −
4ε nE 4εnE 1 ) ≥1− > . X X 2
Therefore, Mb satisfies
h b i X 4ε 1 π πout E JME b − JM > · · = ε. b 2 X 2 Thus, achieving expected suboptimality at most ε on every instance requires nE ≥ X/(8ε). Since |X | = 3X + 3, the sample-complexity statement follows.
51
Appendix table of contents
Proofs from Section 4 (QπE -Realizability Is Insufficient to Learn Offline)
G
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 only Qπ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 algorithm Alg is said to be a value-based IL algorithm if the following conditions hold. 1. Alg receives an expert dataset DE and a state-action value function class Q. 2. For some K ∈ N ∪ {∞}, Alg chooses a sequence Q1 , Q2 , . . . , QK ∈ Q and coefficients (wk )K k=1 defining the PK linear combination LC((Qk )K ) = w Q . When K = ∞, this series must converge absolutely at every k=1 k=1 k k stage-state-action tuple. 3. Alg outputs the policy K πout (a | x) ∝ f LC (Qk )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 P K πout (a | x) = softmax η k=1 Qk (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 have H = 1, so we can omit the subscript h and consider a reward class R rather than a value function class Q. Their learner forms a P reward r(x, a) = r̃∈R w(r̃)r̃(x, a) using learned weights w ∈ ∆(R) and uses a predictor that is greedy with respect to r. Such a predictor is not a finite-temperature VI policy: for any finite η, choosing fη (z) = exp(ηz) gives the softmax VI policy πη (· | x) = softmax(ηr(x, ·)), which generally assigns positive mass to nongreedy actions. Under our standing assumptions that A is finite and r is 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 maxb∈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 as IQ-LEARN (Garg et al., 2021) and CSIL (Watson et al., 2023), are also value-based imitation algorithms. Indeed, these algorithms choose a single Q-function from the class Q and 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.1
Proof 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.
52
Appendix table of contents
Theorem 4.2 (Unidentifiability under VI policies). There exists a family F of MDPs with: i) deterministic initial states, rewards, and transitions, ii) horizon H = 2, iii) state space size |X | = 3, and iv) family size |F| = 2, as well as a value function class Q with |Q| = 2 such that for every M ∈ F, Assumption 2.1 is satisfied for the expert ⋆ πE = πM . Moreover, for any algorithm Alg (Definition 4.1) with a VI policy class (Definition 4.2), for any nE ∈ N⋆ , there exists an MDP M ∈ F such that, given nE expert trajectories sampled from πE , Alg outputs policies πout such πE πout that E[JM − JM ] ≥ 14 .13 Proof of Theorem 4.2. For clarity, we carry out the proof using centered rewards rh ∈ [−1, 0]. Adding 1 to 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 satisfies QπE -realizability with Qmax = 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 at xstart , and the proof treats the action distribution at x− as arbitrary. Hence the argument below applies unchanged. Formally, a1 ≡ + and a2 ≡ − are the two global actions; for every unspecified state-action-stage tuple, we assign zero centered reward and a transition to the absorbing state xend , whose features are zero. +
+
xend
xstart a1
−
x−
xend
xstart a2
−
x−
a2 , r = −1
(a) MDP M1 : Action a1 is optimal.
a1 , r = −1
(b) MDP M2 : Action a2 is optimal.
Figure 6: Family of hard tasks. Unless otherwise specified, the reward is 0. The blue path is the one taken by the deterministic expert. xend is an absorbing state. We consider the family of hard MDPs F = {M1 , M2 } depicted in Figure 6. We consider the following 2-dimensional features that satisfy the QπE -realizability assumption. • φ(xstart , +) = φ(xstart , −) = [0, 0]T , • φ(x− , a1 ) = [0, 1]T , • φ(x− , a2 ) = [1, 0]T . If the expert policy satisfies πE,1 (+ | xstart ) = 1 and πE,1 (a1 | x− ) = 1, then we have π
π
• QME,11 (xstart , +) = QME,11 (xstart , −) = 0, π
• QME,11 (x− , a1 ) = 0, π
• QME,11 (x− , a2 ) = −1. π
Thus, by choosing θ1 = [−1, 0], we can realize the expert action-value function as QME,11 (x, a) = φ(x, a)T θ1 for all (x, a) ∈ X × A. For the second MDP in F, M2 , the optimal expert policy satisfies πE,2 (+ | xstart ) = 1 and π πE,2 (a2 | x− ) = 1. Taking θ2 = [0, −1], we can similarly write QME,22 (x, a) = φ(x, a)T θ2 , so M2 is also QπE -realizable with the same features. Therefore, the two MDPs differ only in which action is good at x− : a1 in M1 and a2 in M2 . Fix any dataset size nE ∈ 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 = QME,11 , QME,22 , π
π
where QME,11 (x, a) = φ(x, a)T θ1 and QME,22 (x, a) = φ(x, a)T θ2 for all x, a. Notice that in both M1 and M2 , we have π π that QME,11 (xstart , a) = QME,22 (xstart , a) = 0 for all a ∈ {+, −}. 13 The expectation is over the training data and the internal randomness of Alg.
53
Appendix table of contents
Under this setting, no matter how Alg selects the sequence Q1 , . . . , QK , the output policy at the starting state is uniform: πout (· | xstart ) = Unif({+, −}). Indeed, every Q ∈ Q assigns the same value to the two actions + and − at xstart . Hence any well-defined linear combination LC(Q1:K ) also assigns the same scalar to the two start actions, including when K = ∞. Since f is 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 combination LC and function f in Definition 4.2 guarantees πout (+ | xstart ) = πout (− | xstart ) = 12 . Moreover, taking pointwise limits or averaging policies obtained from different choices of sequences in Q still gives a uniform policy. It follows that, with probability 1/2, the next state is x− . Suppose that the sequence Q1 , . . . , QK chosen by Alg induces probabilities πout (a1 | x− ) = p and πout (a2 | x− ) = 1 − p. The choice of Q1 , . . . , QK , and hence of p, cannot depend on whether the underlying MDP is M1 or M2 , because the expert dataset is identical in the two cases, even with infinite data. Therefore, the suboptimality at x− , averaged over the MDP class F, equals 1/2 as shown next. 2 2 1X 1 X πE,i π π QMi (x− , ai ) − QME,ii (x− , πout ) = −QME,ii (x− , πout ) 2 i=1 2 i=1
=
2 2 pX 1−pX (−rMi (x− , a1 )) + (−rMi (x− , a2 )) 2 i=1 2 i=1
p 1−p + 2 2 1 = . 2 =
Fix i ∈ {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 at xstart gives the following identity. Suppressing the stage index as above, the only state-occupancy terms that can contribute are dπ1 out (xstart ) = 1 and dπ2 out (x− ) = πout (− | xstart ) = 1/2. All terms at xend vanish because the expert Q-values there are zero. Therefore, X π π πout VME,ii (xstart ) − VM (xstart ) = |{z} 1 (πE,i (a | xstart ) − πout (a | xstart ))QME,ii (xstart , a) i π
d1 out (xstart ) a∈{+,−}
+
1 2 |{z}
π
π
X
(πE,i (a | x− ) − πout (a | x− ))QME,ii (x− , a)
a∈{a1 ,a2 }
d2 out (x− )
1 πE,i =0+ QMi (x− , ai ) − 2
X
π πout (a | x− )QME,ii (x− , a)
a∈{a1 ,a2 }
1 π π = QME,ii (x− , ai ) − QME,ii (x− , πout ) . 2 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∈{M1 ,M2 }
πout πE VM (xstart ) − VM (xstart ) ≥
2 1 X πE,i πout V (xstart ) − VM (xstart ) i 2 i=1 Mi 2
= =
1 X 1 πE,i π QMi (x− , ai ) − QME,ii (x− , πout ) 2 i=1 2 2 1 1 1 X πE,i π · QMi (x− , ai ) − QME,ii (x− , πout ) = . 2 2 i=1 4 {z } | =1/2 by the preceding display
The preceding display holds for every deterministic offline algorithm that outputs a VI policy under the uniform distribution over the two instances in F. Therefore, by Yao’s minimax principle (see, e.g., Bubeck et al., 2012), the 54
Appendix table of contents
same lower bound holds against possibly randomized algorithms: max
M∈{M1 ,M2 } π
πout ⋆ Eπout ∼Alg [VM (xstart ) − VM (xstart )] ≥
1 , 4
π
⋆ ⋆ where we used the equalities VME,1 = VM and VME,2 = VM , which follow by optimality of the experts. 1 2 1 2
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 in xstart 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 class Q realizing QπE has cardinality independent of |X |. Theorem 4.1 (Main lower bound for offline IL). For any X ∈ N⋆ and any ε ∈ (0, 18 ], there exists a family F of MDPs with: i) stochastic initial states but deterministic rewards and transitions, ii) horizon H = 2, iii) state space size |X | = O(X), and iv) family size log(|F|) = O(X), as well as a value function class Q with |Q| = 2 such ⋆ that for every M ∈ F, Assumption 2.1 is satisfied for expert policy πE = πM . Let Alg be any offline IL algorithm (Definition 4.1). Then, there exists an MDP M ∈ F such that Alg needs nE ≥ Ω( Xε ) trajectories sampled according to π⋆
⋆ πout Eq. (3) with expert policy πM , to output a policy πout such that E[JMM − JM ] ≤ ε.14
Proof of Theorem 4.1. As in the preceding proof of Theorem 4.2, we use centered rewards rh ∈ [−1, 0] for convenience. Applying the same shifts and conventions yields the required formal construction without affecting the argument. 2X+1 We consider a family F = Mext in which each of the 2X+1 extended MDPs has 3X + 3 states and is obtained j j=1 by considering X + 1 copies of the structure in Figure 6, with starting states labeled as xistart for i ∈ {0, . . . , X}. For any ε ≤ 81 , denote q = 8ε X and consider the following initial distribution ν0 x0start = 1 − Xq, and ν0 xistart = q for 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 xistart to xiend , without passing through xi− . • In mode −, instead the action − goes straight from xistart to xiend , without passing through xi− . Considering all possible combinations of modes for each copy except the first, i.e., for i = 1, . . . , X, we obtain 2X MDPs. Moreover, for each of these 2X 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 of 2X+1 MDPs. A visual representation of an extended MDP with parameters θ1 is given in Figure 7. The family of 2X+1 optimal expert policies is defined so that the expert policy in the copy with root state xistart in the MDP Mext takes the optimal action that does not pass through xi− . That is, the expert chooses action + if the ith copy j is in mode + in the MDP Mext and action − if the copy is in mode −. At each xi− , the expert takes an action that is j 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 MDP Mext by Q⋆Mext and the state j j
⋆ X+1 value function by VM ], we have that Q⋆Mext is affine in the features ext . At this point, note that for each j ∈ [2 j
φ(xistart , +) = φ(xistart , −) = [0, 0]T ,
j
φ(xi− , a1 ) = [0, 1]T ,
and
φ(xi− , a2 ) = [1, 0]T ,
with parameters either θ1 or θ2 . Denoting Qθ (x, a) = φ(x, a)T θ, the class Q = {Qθ1 , Qθ2 } satisfies QπE -realizability in Mext for every j ∈ [2X+1 ] and has cardinality independent of X. Formally, we have Q⋆Mext ∈ Q for any j ∈ [2X+1 ]. j j
0 X In each MDP, the expert from the root states x0start , . . . , xX start only takes the action that avoids the states x− , . . . , x− , so it does not reveal which action (between a1 and a2 ) 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.
55
Appendix table of contents
ν0 (x0start ) = 1 − Xq
ν0 (x1start ) = q
+
+
x0end
x0start
x0−
+
x1end
x1start
a1
−
ν0 (xistart ) = q
a1
−
x1−
a2 , r = −1
xiend
xistart a1
−
xi−
a2 , r = −1
a2 , r = −1
Figure 7: Representation of a MDP in the class F. The states highlighted in green appear in DE , so the learner can deterministically replay the expert action +. The red states are absent from DE . Thus, no expert guidance is available there, and the learner reaches xi− with probability at least 1/2 in some environment in F, where it plays an action that is suboptimal under one of the two reward parameter choices θ1 and θ2 . Here, q = 8ε/X, so ν0 assigns mass 1 − Xq to x0start and mass q to 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 nE = Ω(|X |ε−1 ). For the averaging argument, draw an environment M uniformly from F, 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 copy i, so action σi bypasses xi− , while Θ is the reward parameter shared by all copies and determines which action is optimal at each xi− . Let ξ be a random seed, independent of the environment and expert data, that encodes all of the learner’s internal randomness, and define T := (DE , ξ). Thus, T consists exactly of the expert dataset and the learner’s random seed. Fix i ∈ [X] and consider the event Ei := {xistart ∈ / DE }. On Ei , the dataset contains no observation from copy i, so it does not depend on σi . Moreover, it does not depend on Θ: the expert never visits any of the states x0− , . . . , xX − , 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, T is therefore independent of (σi , Θ) conditional on Ei , even though it may reveal the modes of other sampled copies. Consequently, conditional on any realization T = t and Ei , the variables σi and Θ remain independent and uniform, while the learner’s output policy may depend arbitrarily on t. Fix such a transcript t, write πout,t for the resulting output policy, and let pt := πout,t,1 (+ | xistart ) and ut := πout,t,2 (a1 | xi− ). Averaging over σi , the probability of reaching xi− is (1 − pt )/2 + pt /2 = 1/2. Independently, averaging over Θ, the suboptimality at xi− is (1 − ut )/2 + ut /2 = 1/2. Therefore, for every such t, ⋆ i 1 − pt pt 1 − ut ut 1 πout,t i E VM xstart − VM xstart T = t, Ei = + + = . 2 2 2 2 4 For each j, let Ej denote expectation under the transcript distribution in Mext and the learner’s internal randomness, j πout ⋆ i i and write ∆j,i := VM (x ) − V (x ). Since E depends only on the initial-state draws, it has probability ext i start start Mext j
j
(1 − q)nE in every environment. Averaging the preceding identity over T therefore yields the unconditional bound 1
X+1 2X
2X+1 j=1
Ej [∆j,i 1Ei ] ≥
1 n (1 − q) E . 4
Optimality implies ∆j,i ≥ 0 at every root state. Thus, dropping the i = 0 term and retaining only the terms on Ei , for any j ∈ [2X+1 ] we have X D E X ⋆ πout πout ⋆ i ν0 , VM = ν0 xistart VM xistart ext − V ext xstart − V Mext Mext j
j
j
j
i=0
≥
X X
ν0 xistart
⋆ πout i VMext xistart − VM ext xstart j
j
i=1
=
X X πout i i ⋆ q VM x ext xstart − V ext start M j
j
i=1 X X πout ⋆ i ≥ q VM xistart 1Ei . ext xstart − V Mext j
j
i=1
56
Appendix table of contents
Taking Ej in the preceding inequality, averaging over the environments, and applying the unconditional bound above gives hD Ei πout ⋆ max Ej ν0 , VM ext − V ext M j∈[2X+1 ]
j
≥
≥
X+1 2X
1
2X+1 j=1 X X i=1
1
j
hD Ej
πout ⋆ ν0 , VM ext − V Mext j
Ei
j
X+1 2X
q X+1 Ej [∆j,i 1Ei ] 2 j=1
X
≥
qX n (1 − q) E 4 i=1
=
X n q(1 − q) E . 4
3 nE E Then, if nE ≤ X/(32ε), Bernoulli’s inequality gives (1 − q)nE = (1 − 8ε ≥ 1 − 8εn X) X ≥ 4 . Therefore, πout ⋆ max E[⟨ν0 , VM − VM ⟩] ≥
M∈F
3ε X 8ε 3 · · = > ε, 4 X 4 2
Thus, recalling 3(X + 1) = |X |, achieving ε-suboptimality requires nE = Ω(|X |/ε) for any offline IL algorithm.
57
Appendix table of contents
Part II
Additional Results We collect here additional results omitted from the main text. We begin by completing Section 3 with a variant of OVI. In Appendix H, we show that reversing the order in which the players update in OVI yields an algorithm that is less computationally efficient, but provides statistical benefits for nonconvex Q classes 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 class Q realizes either QπE or the Q-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 OVI therefore applies to a strictly larger set of classes Q than 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 the Q-variables via a no-regret algorithm. The resulting method, Q-OVI, is computationally inefficient when Q is continuous because it requires discretizing Q, but it enjoys better statistical rates when Q is nonconvex. When the Q-player moves first, the policy player πhk can be chosen greedily with respect to Qkh . For each (k, h) ∈ [K] × [H], define xkh ∼ dπhout ,
akE,h ∼ πE,h · xkh ,
ℓbπhout ,k (Q) = Q xkh , πhk − Q xkh , akE,h .
To complete the design of Q-OVI, we use Lemma H.1 below and note that the sequence (Qkh )K k=1 can be chosen to minimize a regret with respect to losses ℓbπhout ,1 , . . . , ℓbπhout ,K . In the following, for any h ∈ [H], Cϵ (Qh ) denotes an ϵ-cover of Qh , and we abbreviate Nϵmax (Q) := maxh∈[H] Nϵ (Qh ). Then, for a weight distribution whk ∈ ∆(Cε/(4H) (Qh )) over a covering set Cε/(4H) (Qh ) of Qh , we define Qkh as the corresponding weighted average. For any state-action pair (x, a) ∈ X × A, X Qkh (x, a) = whk (Q)Q(x, a). Q∈Cε/(4H) (Qh )
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 sets Cε/(4H) (Qh ) ⊆ Qh for h ∈ [H]. 1 2: For any h ∈ [H] and Q ∈ Cε/(4H) (Qh ), set wh (Q) = 1/N P ε/(4H) (Qh ). 1 1 3: For any h ∈ [H] and (x, a) ∈ X × A, set Qh (x, a) = Q∈C (Q ) wh (Q)Q(x, a). ε/(4H)
h
1 4: For any h ∈ [H] and x ∈ X , set πh (· | x) ∈ arg maxp∈∆(A) p, Q1h (x, ·) . 5: for h = 1, . . . , H do 6: for k = 1, . . . , K do 7: Sample xkh ∼ dπhout , akE,h ∼ πE,h (· | xkh ). k
8: 9: 10: 11:
k
k
k
For any Q ∈ Cε/(4H) (Qh ), set whk+1 (Q) ∝ whk (Q)eη(Q(xh ,aE,h )−Q(xh ,πh )) . P k+1 For any (x, a) ∈ X × A, set Qk+1 (Q)Q(x, a). Q∈Cε/(4H) (Qh ) wh h (x, a) = For any x ∈ X , set πhk+1 (· | x) ∈ arg maxp∈∆(A) p, Qk+1 h (x, ·) . PK 1 k π (a | x) for any (x, a) ∈ X × A. Set πout,h (a | x) = K k=1 h
58
Appendix table of contents
Lemma H.1. Let Assumption 2.1 hold, and fix an accuracy parameter ε > 0. For each (k, h) ∈ [K] × [H], suppose that whk ∈ ∆(Cε/(4H) (Qh )) and that Qkh is the corresponding weighted average. For each h ∈ [H], define πhk (· | x) ∈ PK 1 k arg maxp∈∆(A) ⟨p, Qkh (x, ·)⟩, and set πout,h (a | x) = K k=1 πh (a | x) for any state-action pair (x, a) ∈ X × A. Let π π E E b ∈ Cε/(4H) (Qh ) be a closest element to Q for each h ∈ [H]. Then, with probability at least 1 − δ, we have Q h h J
πE
−J
πout
H ≤ max Rw + 8HQmax K h∈[H] h
r
2 log(2H/δ) ε + , K 2
where the regret of the sequence (whk )K k=1 is defined by K X X b πE . Rw whk (Q)ℓbπhout ,k (Q) − ℓbπhout ,k Q h = h k=1
Q∈Cε/(4H) (Qh )
Lemma H.1 says that, withqprobability at least 1 − δ, the performance gap J πE − J πout is upper bounded by H w K maxh∈[H] Rh + 8HQmax
2 log(2H/δ) + 2ε . K
k K Rw h can be easily controlled by updating (wh )k=1 via exponential weights. The resulting algorithm is in Algorithm 3. Therefore, using the decomposition in Lemma H.1 and showing √ that Rw = O( K) via a standard online learning bound for the regret of the exponential weights algorithm (see, e.g., h Cesa-Bianchi and Lugosi, 2006; Orabona, 2026), we obtain the following guarantees. max Theorem H.1. Let Assumption 2.1 hold. For any ε, δ ∈ (0, 1), recall that Nε/(4H) (Q) := maxh∈[H] Nε/(4H) (Qh ). Run Q-OVI (Algorithm 3) with s max max (Q)H/δ H 2 Q2max log Nε/(4H) log Nε/(4H) (Q) , , K = O η= KQ2max ε2
Then, the algorithm outputs a policy πout such that, with probability at least 1 − δ, we have J πE − J πout ≤ ε after max (Q)H/δ H 3 Q2max log Nε/(4H) O expert queries. ε2 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 implementation because it does not require discretizing the class Q. While we think that the linear case could be made efficient, this approach is clearly not scalable when Q corresponds to the class of weights for modern architectures. Q-OVI would learn a distribution over a set of exponentially many weight configurations. In contrast, OVI is compatible with the common practice of specifying a loss function and backpropagating through it. Comparison of the statistical complexity. When the class Q is convex, both algorithms achieve a rate of order O(ε−2 ). A rate difference emerges in the nonconvex case, where Algorithm 3 has a sample complexity of order O(ε−2 ), while Algorithm 1 has a suboptimal O(ε−4 ) rate. To summarize, Q-OVI (Algorithm 3) has better statistical properties but is computationally inefficient compared to OVI (Algorithm 1) because it requires discretizing the class Q.
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
Lπhout (πout,h , QπhE )
h=1
59
Appendix table of contents
H
=
K
1 X X πout k πE Lh πh , Qh K h=1 k=1
=
H K H K 1 X X πout k πE 1 X X πout k k Lh πh , Qh + Lh πh , Qh − Qkh . K K h=1 k=1
h=1 k=1
Since πhk (· | x) ∈ arg maxp∈∆(A) ⟨p, Qkh (x, ·)⟩, we have Lπhout (πhk , Qkh ) ≤ 0. Hence, H
J πE − J πout ≤
K
1 X X πout k πE Lh πh , Qh − Qkh . K h=1 k=1
b πE ∈ Cr (Qh ) be such that ∥Q b πE − QπE ∥∞ ≤ r for each h ∈ [H]. For any decision rule p and Let r > 0 and let Q h h h ′ functions Qh , Qh , X π |Lπhout (p, Qh − Q′h )| ≤ ∥Qh − Q′h ∥∞ dhout (x)∥πE,h (· | x) − p(· | x)∥1 ≤ 2∥Qh − Q′h ∥∞ . x∈X
b πE costs at most 2r for each pair (k, h), hence at most 2Hr after averaging over k and Thus, replacing QπhE by Q h b πE in the previous display gives summing over h. Replacing QπhE by Q h J
πE
−J
πout
H K 1 X X πout k b πE ≤ Lh πh , Qh − Qkh + 2Hr. K
(24)
h=1 k=1
For each (k, h) ∈ [K] × [H], define the sampled loss ℓbπhout ,k (Q) = Q xkh , πhk − Q xkh , akE,h ,
xkh ∼ dπhout ,
akE,h ∼ πE,h · xkh .
Then, h i b πE Fk−1,h = Lπout πhk , Q b πE − Qkh , E ℓbπhout ,k Qkh − ℓbhπout ,k Q h h h where Fk−1,h contains all randomness from previous layers and from the first k − 1 samples at layer h. Conditionally on Fk−1,h , the distribution dπhout is fixed because it only depends on the already computed policies πout,1 , . . . , πout,h−1 , and Qkh and πhk are also fixed because they are functions of the previous samples at layer h. Therefore, the increments b πE − Qk − ℓbπout ,k Qk − ℓbπout ,k Q b πE Mhk = Lπhout πhk , Q h h h h h h b πE belongs to the cover and Qk is a form a martingale difference sequence in k, for each fixed h ∈ [H]. Moreover, since Q h h b πE − Qk ∥∞ ≤ 2Qmax , convex combination of cover elements, both functions are bounded in sup-norm by Qmax . Thus, ∥Q h h b πE − Qk )| and |ℓbπout ,k (Qk ) − ℓbπout ,k (Q b πE )| are at most 2∥Q b πE − Qk ∥∞ ≤ 4Qmax . Hence and both |Lπhout (πhk , Q h h h h h h h h |Mhk | ≤ 8Qmax almost surely. By the Azuma-Hoeffding inequality and a union bound over h ∈ [H], with probability at least 1 − δ, for all h ∈ [H], r K 1 X k 2 log(2H/δ) Mh ≤ 8Qmax . K K k=1 P Summing over h ∈ [H] incurs an extra H factor in the upper bound. Finally, using Qkh = Q∈Cr (Qh ) whk (Q)Q and taking r = ε/(4H), we obtain from Eq. (24) r H X K X X 2 log(2H/δ) 1 πout ,k πout ,k b πE πE πout k b b J −J ≤ wh (Q)ℓh (Q) − ℓh Qh + 8HQmax + 2Hr K K h=1 k=1 Q∈Cr (Qh ) r H 1 X w 2 log(2H/δ) ε = Rh + 8HQmax + K K 2 h=1 r H 2 log(2H/δ) ε ≤ max Rw + , h + 8HQmax K h∈[H] K 2 which gives the stated form.
60
Appendix 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 r H 2 log(2H/δ) ε πE πout w ≤ J −J max Rh + 8HQmax + . K h∈[H] K 2 Thus, it remains to control the regret Rw h for each h ∈ [H]. The update in Algorithm 3 can be written for any Q ∈ Cε/(4H) (Qh ) as k k k k wk+1 (Q) ∝ wk (Q)eη(Q(xh ,aE,h )−Q(xh ,πh )) . h
h
Equivalently, this is exponential weights with sampled losses ℓbπhout ,k . Moreover, by the definition of the function class, max each Qh ∈ Qh satisfies ∥Qh ∥∞ ≤ Qmax , so |ℓbπhout ,k (Qh )| ≤ 2Qmax for all Qh ∈ Qh . If Nε/(4H) (Q) = 1, every π k E b for every h and stagewise cover is a singleton, so the prescribed learning rate is η = 0 but wh assigns unit mass to Q h k. Hence, Rw = 0 for all h, and the regret bound below holds directly without invoking Lemma E.6. We may therefore h max suppose that Nε/(4H) (Q) ≥ 2, so η > 0. For any stage with a singleton cover, the same zero-regret conclusion holds. Fix a stage h ∈ [H] with a non-singleton cover and apply Lemma E.6 to the simplex V = ∆(Cε/(4H) (Qh )) with loss vectors ℓk (Q) = ℓbhπout ,k (Q). The update above is mirror descent with the negative entropy regularizer, whose Bregman b πE ∈ Cε/(4H) (Qh ). Since w1 is uniform over the cover, divergence D is the KL divergence. We use as comparator Q h h 1 b πE . Thus, using the bounds ∥ℓk ∥∞ ≤ 2Qmax and D(eQbπE , wh ) ≤ log Nε/(4H) (Qh ), where eQbπE is the unit vector at Q h h h λ ≥ 1/2, Lemma E.6 gives log Nε/(4H) (Qh ) + 4ηKQ2max . Rw h ≤ η q max Using Rw log Nε/(4H) (Q)/(KQ2max ) in the preceding h = 0 for singleton stagewise covers and substituting η = bound for non-singleton covers, we obtain q max max Rw ≤ 5 KQ2max log Nε/(4H) (Q). h
h∈[H]
Combining the decomposition above with the regret bound gives s r max Q2max log Nε/(4H) (Q) 2 log(2H/δ) ε πE πout + 8HQmax + J −J ≤ 5H K K 2 v u u log N max (Q)2H/δ √ t ε/(4H) ε ≤ 5 + 8 2 HQmax + . K 2 Choosing K so that 2 2 max √ 2 H Qmax log Nε/(4H) (Q)2H/δ K ≥4 5+8 2 ε2 makes the first term in the display above at most ε/2, and therefore J πE − J πout ≤ ε with probability at least 1 − δ. Since Algorithm 3 makes one expert query for each pair (k, h) ∈ [K] × [H], the total number of expert queries is max HK = O H 3 Q2max log Nε/(4H) (Q)H/δ ε−2 .
H.3
Learning a Stationary Policy with Q-OVI
In this section, we show that Q-OVI can be used to learn a stationary policy that competes with the expert in the discounted infinite-horizon setting. We formalize the setting next. 61
Appendix table of contents
Infinite-horizon MDPs. We consider a discounted MDP M = (X , A, r, P, γ, ν0 ), where X and A are 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 (xh , ah )∞ h=0 by drawing x0 ∼ ν0 , ah ∼ π(· | xh ), and xh+1 ∼ P (· | xh , ah ) for all h ≥ 0. For any state-action pair (x, a) ∈ X × A, the discounted state-action value function is "∞ # X Qπγ (x, a) = Eπ γ h r(xh , ah ) x0 = x, a0 = a . h=0
For any function Q : X × A → R and policy π, we use Q(x, π) to denote Ea∼π(·|x) [Q(x, a)]. The discounted state occupancy measure of π is denoted by dπγ ∈ ∆(X ) and defined by dπγ (x) = (1 − γ)
∞ X
γ h Pπ [xh = x].
h=0
Finally, we denote the normalized expected return of π by "∞ # X π π h Jγ = (1 − γ)E γ r(xh , ah ) . h=0
Infinite-horizon Q-OVI and guarantees. For simplicity, we consider finite classes Q in 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 of Q-OVI. For simplicity, we assume direct access to samples from dπγ k . Under ordinary trajectory access, Algorithm 4 Infinite-horizon Q-OVI 1: input: Learning rate η, iterations K, finite class Q. 2: Set w1 (Q) = 1/|Q| for all Q ∈ Q. P 3: For any (x, a) ∈ X × A, set Q1 (x, a) = Q∈Q w1 (Q)Q(x, a). 4: For any x ∈ X , set π1 (· | x) ∈ arg maxp∈∆(A) ⟨p, Q1 (x, ·)⟩. 5: for k = 1, . . . , K do 6: Sample xk ∼ dπγ k , aEk ∼ πE (· | xk ). E
k ,ak )−Q(xk ,πk )) For any Q ∈ Q, set wk+1 (Q) ∝ wk (Q)eη(Q(x . P For any (x, a) ∈ X × A, set Qk+1 (x, a) = Q∈Q wk+1 (Q)Q(x, a). 9: For any x ∈ X , set πk+1 (· | x) ∈ arg maxp∈∆(A) ⟨p, Qk+1 (x, ·)⟩. 10: Draw I ∼ Unif([K]) and output πout = πI .
7: 8:
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. Assume Qπγ E ∈ Q, |Q| ≥ 2 and ∥Q∥∞ ≤ (1 − γ)−1 for all Q ∈ Q. For any ε ∈ (0, 1), run Algorithm 4 with ! r log|Q| log|Q| η = (1 − γ) , K=O . 2 K (1 − γ) ε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. K πE 1 X πE πout E Jγ − Jγπk . E Jγ − Jγ = K k=1
62
Appendix table of contents
For any fixed k ∈ [K], the performance difference lemma in discounted MDPs (Moulin et al., 2025a, Lemma 1) gives X JγπE − Jγπk = dπγ k (x) Qπγ E (x, ·), πE (· | x) − πk (· | x) x∈X
=
X
dπγ k (x)⟨Qk (x, ·), πE (· | x) − πk (· | x)⟩
x∈X
+
X
dπγ k (x) Qπγ E (x, ·) − Qk (x, ·), πE (· | x) − πk (· | x) .
x∈X
Because πk (· | x) is greedy with respect to Qk (x, ·), the first term is nonpositive. Therefore, X JγπE − Jγπk ≤ dπγ k (x) Qπγ E (x, ·) − Qk (x, ·), πE (· | x) − πk (· | x) . x∈X
Define the sampled gains xk ∼ dπγ k ,
gk (Q) = Q xk , aEk − Q(xk , πk ),
aEk ∼ πE (· | xk ).
Let Fk−1 be the history before drawing (xk , aEk ), that is, the σ-field generated by the previous samples (xj , aEj )j<k and any additional algorithmic randomness up to round k − 1. Although the distribution dπγ k changes with k, conditional on Fk−1 , the weight vector wk , and hence Qk , πk , and dπγ k , are fixed. The fresh sample is then drawn conditionally as xk ∼ dπγ k and aEk ∼ πE (· | xk ). Hence, X π E gk Qπγ E − gk (Qk ) Fk−1 = dγ k (x) Qπγ E (x, ·) − Qk (x, ·), πE (· | x) − πk (· | x) . x∈X
Taking expectations and summing over k gives "K # K X X πE E Jγ − Jγπk ≤ E gk Qπγ E − gk (Qk ) . k=1
Let w
⋆
k=1
= eQπγ E be the unit vector at Qπγ E . Since Qk (x, a) =
P
Q∈Q wk (Q)Q(x, a), the previous display becomes
K K X X X πE E Jγ − Jγπk ≤ E (w⋆ (Q) − wk (Q))gk (Q). k=1
k=1 Q∈Q
The exponential weights update is mirror descent over the simplex V = ∆(Q) with loss vectors ℓk (Q) = −gk (Q). The regularizer is negative entropy, whose Bregman divergence D is the KL divergence. We use the comparator w⋆ , and since w1 is uniform over Q, we have D(w⋆ , w1 ) ≤ 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 X
(w⋆ (Q) − wk (Q))gk (Q) ≤
k=1 Q∈Q
log|Q| 2ηK + 2. η (1 − γ)
p Assuming |Q| ≥ 2, we can set η = (1 − γ) log|Q|/K to obtain s πE log|Q| πout E Jγ − Jγ ≤3 2. K(1 − γ) 9 log|Q| Choosing K ≥ (1−γ) 2 ε2 makes the right-hand side at most ε.
63
Appendix 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 of OVI. Assumption I.1 (L∞ -coverage). Assume an algorithm Alg outputs 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πhE (x) ≤ C∞ . Assumption I.2 (L1 -coverage). Assume an algorithm Alg that outputs a VI policy πout in a class ΠAlg such that, for some finite constant C1 , H X 2 X (dπh (x)) ≤ C1 . sup dπhE (x) π∈ΠAlg h=1 x∈X
For both cases, we use the convention 0/0 = 0. We note that Assumption I.1 implies Assumption I.2 with C1 ≤ 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 algorithm SPOIL (Moulin et al., 2025a) satisfies Assumption I.1. For every radius r > 0, write Nrmax (Q) := maxh∈[H] Nr (Qh , ∥·∥∞ ), and choose a radius rε = O(ε2 ) small enough. Then, SPOIL returns an ε-optimal policy 4 e ∞ with probability at least 1 − δ using O(C H 5 Q4max log(A) log(Nrmax (Q)δ −1 )ε−4 ) precollected expert data. Moreover, ε 2 3 2 e if the class Q is convex the bound improves to O(C∞ H Qmax log(Nrmax (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 stage h may differ from dπhout . This result will be used several times below. Algorithm 5 OVI with arbitrary state sampling distribution d K+1
1: input: Sampling distributions d = {dh }H h=1 , learning-rate schedule {ηk }k=1 , iterations K, number of expert
queries per stage nE . 2: for h = 1, . . . , H do 3: Create the stage-h dataset: for i ∈ [nE ], sample xih ∼ dh and query aiE,h ∼ πE,h (· | xih ). 4: 5: 6: 7: 8:
Initialize πh1 = Unif(A). for k = 1, . . . , K do PnE Set Qkh ∈ arg maxQh ∈Qh i=1 (Qh (xih , aiE,h ) − Qh (xih , πhk )). Pk ′ Set πhk+1 (a | x) ∝ πh1 (a | x) exp(ηk+1 k′ =1 Qkh (x, a)). PK 1 k Set the output policy at stage h to πout,h (a | x) = K k=1 πh (a | x).
Theorem I.2 (Sample complexity for OVI with arbitrary sampling distributions). For each h ∈ [H], let Fh−1 denote the history available before the stage-h samples are drawn. Fix any sequence of state sampling distributions d = {dh }H h=1 , where each dh may be random but is Fh−1 -measurable, and run Algorithm 5 with K, nE ∈ N and the FTRL learningrate schedule s log A ηk = for every k ≥ 1. kQ2max E For each h ∈ [H], assume that, conditionally on Fh−1 , the pairs (xih , aiE,h )ni=1 are independent, with xih ∼ dh and i i max aE,h ∼ πE,h (· | xh ). For every radius r > 0, write Nr (Q) := maxh∈[H] Nr (Qh , ∥·∥∞ ). Let ε, δ ∈ (0, 1) and choose ′ a radius rε = O(ε2 ) small enough. Fix any comparator policy π ′ such that Qπh ∈ Qh for every h ∈ [H]. For the policy πout returned by Algorithm 5, we recall the definition X D ′ E ′ Ldh πout,h , Qπh = dh (x) Qπh (x, ·), πE,h (· | x) − πout,h (· | x) .
x∈X
64
Appendix table of contents
If Q is convex, then with probability at least 1 − δ, r s H 2 2 max 2 2 X ′ e H Qmax log A + H Qmax log Nrε (Q)/δ + ε. Ldh πout,h , Qπh ≤ O K nE h=1
If Q is not assumed to be convex, then with probability at least 1 − δ, r s H 2 Q2 log N max (Q)/δ 2 Q2 log A X KH ′ H max rε max e Ldh πout,h , Qπh ≤ O + + ε. K nE h=1
In particular, up to logarithmic factors, the convex bound is of order ε by taking K ≳ H 2 Q2max log(A)/ε2 and nE ≳ (Q)/δ)/ε2 H 2 Q2max log(Nrmax (Q)/δ)/ε2 . In the nonconvex case, the same choice of K and nE ≳ KH 2 Q2max log(Nrmax ε ε suffices. Proof of Theorem I.2. Recall the definitions of the empirical objective and the uniform estimation error Lbdh (πh , Qh ) := n−1 E
nE X
Qh xih , aiE,h − Qh xih , πh ,
i=1
∆d (π) := max sup Lbdh (πh , Qh ) − Ldh (πh , Qh ) . h∈[H] Qh ∈Qh
′
Fix h ∈ [H]. Since Qπh ∈ Qh , the first inequality below follows from the definition of ∆d (π k ). The second inequality follows from the empirical maximization property defining Qkh , and the last inequality uses the definition of ∆d (π k ) again, now with Qkh : K X
K K X X ′ ′ Lbdh πhk , Qπh + ∆d π k Ldh πhk , Qπh ≤
k=1
k=1
≤
K X
k=1
Lbdh πhk , Qkh +
k=1
≤
K X
K X
∆d π k
k=1 K X Ldh πhk , Qkh + 2 ∆d π k .
k=1
k=1
We now control the first term on the right-hand side using the FTRL regret bound. Fix x ∈ X and define the loss vectors ℓk,h,x (a) := −Qkh (x, a). Since πh1 is uniform, the update in Algorithm 5 implies that, for every k ≥ 1, P P exp ηk j<k Qjh (x, a) exp −ηk j<k ℓj,h,x (a) P =P . πhk (a | x) = P P j ′) ′) exp η Q (x, a exp −η ℓ (a ′ ′ k k a ∈A j<k h a ∈A j<k j,h,x K Thus, for this fixed h and x, the sequence (πhk (· | x))p k=1 is exactly the FTRL sequence of Lemma E.7 with comparator πE,h (· | x). Moreover, ∥ℓk,h,x ∥∞ ≤ Qmax and ηk = log A/(kQ2max ). Applying Lemma E.7 pointwise in x and then averaging over dh , for any K ∈ N, we obtain K X k=1
K X p X Ldh πhk , Qkh = dh (x) Qkh (x, ·), πE,h (· | x) − πhk (· | x) ≤ 3 Q2max K log A, x∈X
k=1
where the last inequality uses that dh 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.
65
Appendix table of contents
It remains to control the estimation error. Since the learning rate varies with k, define the policy class n o Pm j ΠQ := π : ∃m ∈ {0, . . . , K}, ∀h, ∃Q1h , . . . , Qm . h ∈ Qh , πh (a | x) = softmax ηm+1 j=1 Qh (x, ·) a
For each h, let ΠQ,h := {πh : π ∈ ΠQ }. The iterates generated by Algorithm 5 satisfy π k ∈ ΠQ for every k ∈ [K], by taking m = k − 1. E For every h, condition on Fh−1 . Then dh is fixed, and the pairs (xih , aiE,h )ni=1 are independent, with xih ∼ dh and i i aE,h ∼ πE,h (· | xh ). 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 − δ, v P u H u K X t 8 log 2 h=1 Nr (Qh × ΠQ,h , ρ)/δ . ∆d π k ≤ K sup ∆d (π) ≤ K 4r + Q max nE π∈ΠQ
k=1
′
1 Therefore, dividing by K and using Ldh (πout,h , Qπh ) = K H X
Ldh πout,h , Qπh
′
r ≤3
h=1
d k π′ k=1 Lh (πh , Qh ), we obtain
PK
v u u 8 log 2 PH Nr (Qh × ΠQ,h , ρ)/δ t h=1 H 2 Q2max log A + 8Hr + 2HQmax . K nE
Next, we bound the covering number of the product class. Choose r = ε/(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 by m functions, the factor ηm is replaced by ηm+1 m. Thus, they naturally lead to a covering number with radius ε . 16H max{1, Qmax max1≤m≤K mηm+1 } Increasing K by an absolute constant if necessary, we may assume K log A ≥ 1. Then the learning-rate schedule gives r p p log A Qmax max mηm+1 = K ≤ K log A, max 1, Qmax max mηm+1 ≤ K log A. 1≤m≤K 1≤m≤K K +1 Thus, for the parameter choices below, it is enough to use the smaller radius rε :=
ε , 16H K log A √
which only enlarges the covering number. After the choices of K below, this radius satisfies rε = O(ε2 ). Convex case. If Q is convex, then each projection Qh is convex. Hence, by Lemma E.4, for every h ∈ [H], 2
Nr (Qh × ΠQ,h , ρ) ≤ (K + 1)Nrε (Qh , ∥·∥∞ ) . Plugging this into the preceding estimation bound gives H X
Ldh πout,h , Qπh
h=1
′
r ≤3
v u u 8 log 2H(K + 1) N max (Q)2 /δ rε t H 2 Q2max log A + ε + 2HQmax . K nE
Thus, the convex bound becomes r s 2 Q2 log N max (Q)/δ 2 Q2 log A H H max rε max e O + + ε. K nE In particular, choosing 9H 2 Q2max log A K≥ , ε2
2 ! 2H(K + 1) Nrmax (Q) 32H 2 Q2max ε nE ≥ log ε2 δ 66
Appendix table of contents
makes the three terms in the previous display of order ε. Nonconvex case. For arbitrary, not necessarily convex, classes Q, Lemma E.3 instead gives, for every h ∈ [H], K+1
Nr (Qh × ΠQ,h , ρ) ≤ (K + 1)Nrε (Qh , ∥·∥∞ )
.
Therefore, H X
r
′ Ldh πout,h , Qπh ≤ 3
h=1
v u u 8 log 2H(K + 1) N max (Q)K+1 /δ 2 2 rε t H Qmax log A + ε + 2HQmax , K nE
or, equivalently, r e O
H 2 Q2max log A + K
s
KH 2 Q2max log Nrmax (Q)/δ ε + ε. nE
With the same choice of K as above, taking K+1 ! ! 2H(K + 1) Nrmax (Q) KH 2 Q2max log Nrmax (Q)/δ 32H 2 Q2max ε ε e nE ≥ log =O ε2 δ ε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 Assumption I.2 alone in terms of the L1 -coverage coefficient C1 , 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 that SPOIL (Moulin et al., 2025a) satisfies at least one of Assumptions I.1 and I.2. Run SPOIL (i.e., Algorithm 5 with d = dπE ) with the FTRL learning-rate schedule s log A ηk = for every k ≥ 1. kQ2max (1) (∞) For every radius r > 0, write Nrmax (Q) := maxh∈[H] Nr (Qh , ∥·∥∞ ). Choose radii rε = O(ε4 ) and rε = O(ε2 ) small enough. If Q is arbitrary, the C1 -dependent choice below guarantees J πE − J πout ≤ ε with probability at least 1 − δ under Assumption I.2, while the C∞ -dependent choice guarantees the same under Assumption I.1: 2 2 4 max 4 4 8 log(A) log N (Q)/δ C H Q (1) max 1 (1) rε e C1 H Qmax log A , e , K (1) = O nE = O ε4 ε8 2 2 2 4 C∞ H 4 Q4max log(A) log N max (∞) (Q)/δ C H Q log A (∞) rε ∞ max e e . K (∞) = O , nE = O ε2 ε4
If both coverage assumptions hold, choosing the better of the two branches gives total expert sample complexity 4 C14 H 5 Q8max log(A) log N max C∞ H 5 Q4max log(A) log N max (1) (Q)/δ (∞) (Q)/δ rε rε emin . HnE = O , ε8 ε4 If Q is convex, the same branch-wise guarantees hold under their respective coverage assumptions, with the same choices of K (1) and K (∞) , but with 2 C12 H 2 Q4max log N max H 2 Q2max log N max C∞ (1) (Q)/δ (∞) (Q)/δ (1) (∞) rε rε e e , . nE = O nE = O ε4 ε2 67
Appendix table of contents
If both coverage assumptions hold, choosing the better of the two branches gives total expert sample complexity 2 3 2 max C12 H 3 Q4max log N max (Q)/δ (Q)/δ C H Q log N (∞) (1) ∞ max rε rε emin . , HnE = O ε4 ε2 e notation in each branch hides logarithmic factors in H, Qmax , and the corresponding coverage coefficient. Here, the O Proof of Theorem I.3. Since the expert is optimal, πE is greedy with respect to QπE at every stage h and state x ∈ supp(dπhE ). Hence, for any policy π, stage h, and state x ∈ supp(dπhE ), ⟨QπhE (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 of C1 , and one under Assumption I.1, in terms of C∞ . When both assumptions hold, the guarantee takes the better of the two. Bounds scaling with C1 . Let
gh (x) := ⟨QπhE (x, ·), πE,h (· | x) − πout,h (· | x)⟩.
Finiteness of C1 implies that, for every h and x, dπhout (x) = 0 whenever dπhE (x) = 0, so the following change of measure is well defined. The expert value function satisfies QπhE (x, a) ∈ [0, Qmax ] for every h, x, a. Together with the nonnegativity above, this gives 0 ≤ gh (x) ≤ Qmax , and hence gh (x)2 ≤ Qmax gh (x) for every x ∈ supp(dπhE ). By the performance difference lemma (Lemma E.9), the Cauchy–Schwarz inequality, and Assumption I.2, we have J πE − J πout =
H X X
dπhout (x)gh (x)
h=1 x∈X
v v uH uH X uX X (dπout (x))2 uX 2 h t t ≤ dπhE (x)gh (x) πE dh (x) h=1 x∈X h=1 x∈X v u H X X u ≤ tC1 Qmax dπhE (x)gh (x). h=1 x∈X
The last summation is exactly the loss controlled by Theorem I.2 with d = dπE and π ′ = πE : H X X
dπhE (x)gh (x) =
h=1 x∈X
H X
LπhE (πout,h , QπhE ).
h=1
For nonconvex Q, applying Theorem I.2 with accuracy parameter ε0 and associated covering radius rε0 = O(ε20 ) gives, with probability at least 1 − δ, v r s u u 2 2 2 2 H Qmax log A KH Qmax u e J πE − J πout ≤ O + log Nrmax (Q)/δ + ε0 . tC1 Qmax ε0 K nE (1)
Taking ε0 = ε2 /(C1 Qmax ) and choosing rε ≤ rε0 , the monotonicity of covering numbers and the absorption of e yield logarithmic factors in H, Qmax , and C1 into O v u r max 2 u 2 4 2 2 4 4 KC1 H Qmax log N (1) (Q)/δ t rε e 4 C1 H Qmax log A + J πE − J πout ≤ O + ε . K nE
68
Appendix table of contents
Thus the C1 -tuned nonconvex choice in the theorem makes the right-hand side at most O(ε). If Q is convex, the second term in Theorem I.2 has no factor K. Repeating the same calculation gives v u r max 2 u 2 4 2 2 4 4 C1 H Qmax log N (1) (Q)/δ t rε e 4 C1 H Qmax log A + J πE − J πout ≤ O + ε , K nE (1)
which gives the improved convex choice of nE . Bounds scaling with C∞ . The C∞ argument gives a better dependence on 1/ε at the cost of replacing C1 by the stronger coverage coefficient C∞ . Since gh (x) ≥ 0, Assumption I.1 gives J πE − J πout =
H X X
dπhout (x)gh (x)
h=1 x∈X
≤
dπout (y) max max hπE y∈X h∈[H] dh (y)
≤ C∞
H X X
X H X
dπhE (x)|gh (x)|
h=1 x∈X
dπhE (x)gh (x) = C∞
h=1 x∈X
H X
LπhE (πout,h , QπhE ).
h=1 (∞)
Applying Theorem I.2 with d = dπE , π ′ = πE , and accuracy parameter ε0 = ε/C∞ , and choosing rε ≤ rε0 for the associated radius rε0 = O(ε20 ), the monotonicity of covering numbers gives for nonconvex Q that v u r max u 2 2 2 2 2 2 t KC∞ H Qmax log Nrε(∞) (Q)/δ e C∞ H Qmax log A + J πE − J πout ≤ O + ε . K nE (∞)
This is at most O(ε) for the C∞ -tuned nonconvex choice of K (∞) and nE in the theorem. If Q is convex, the same calculation with the convex version of Theorem I.2 gives v u r max u C 2 H 2 Q2 log N 2 2 2 (∞) (Q)/δ max t ∞ rε e C∞ H Qmax log A + J πE − J πout ≤ O + ε , K nE (∞)
which yields the stated convex choice of nE . Finally, SPOIL uses nE expert samples at each of the H stages, so the total number of precollected expert samples is HnE . Multiplying the branch-wise bounds on nE by H gives the two sample-complexity displays in the theorem.
69
Appendix 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 class Q satisfies either QπE -realizability or the QΠ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 the QΠ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). Fix K = poly(H, log A, Qmax , ε−1 ) and learning rates η1:K+1 ∈ RK+1 , and define n o m h Pmh h ΠQ := π : ∀h ∈ [H], ∃mh ≤ K, ∃ Qhj j=1 ⊂ Qh , πh (a | x) = softmax ηmh +1 j=1 Qj (x, ·) . a
ΠQ
The class Q satisfies Q
π
-realizability if Q ∈ Q for every π ∈ ΠQ .
For each stage h, write ΠQ,h := {πh : π ∈ ΠQ }. This notation is always understood with the same value of K and 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 of m shared 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 the Q-functions of many policies, whereas QπE -realizability only requires realizing the expert’s Q-function. Since the expert need not belong to ΠQ , QΠQ -realizability does not imply QπE -realizability. Nevertheless, the upper bound of Moulin et al. (2025a) implies that, under QΠ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 under QΠ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 each h ∈ [H], we sample states from a mixture of the expert occupancy dπhE and the learner occupancy dπhout . 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 dh = (1 − α)dπhout + αdπhE , for an appropriate choice of α ∈ [0, 1]. The mixture is the key adaptive device: the dπout component gives coverage of the learner states needed under QπE -realizability, while the dπE component keeps enough expert-state mass for the QΠQ argument. The change relative to Algorithm 5 is highlighted in orange. We have the following result. Algorithm 6 RAOVI: Representation-Adaptive OVI K+1
1: input: Mixture parameter α ∈ [0, 1], learning rates (ηk )k=1 , iterations K, dataset size per stage nE . 2: for h = 1, . . . , H do 3: Create the stage-h dataset: for i ∈ [nE ], sample
xih ∼ (1 − α)dπhout + αdπhE , 4: 5: 6: 7: 8:
aiE,h ∼ πE,h (· | xih ).
Initialize πh1 = Unif(A). for k = 1, . . . , K do PnE Set Qkh ∈ arg maxQh ∈Qh i=1 (Qh (xih , aiE,h ) − Qh (xih , πhk )). Pk ′ Set πhk+1 (a | x) ∝ πh1 (a | x) exp(ηk+1 k′ =1 Qkh (x, a)). P K 1 k Set πout,h (a | x) = K k=1 πh (a | x).
Theorem J.1. Let the expert policy πE be optimal, ε ∈ (0, min{1, 2HQmax }), and δ ∈ (0, 1). Run Algorithm 6 with s ε log A α=1− , ηk = for every k ≥ 1. 2HQmax kQ2max 70
Appendix 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 4 4 H Qmax log A e , K=O ε4
4 4 2 2 e H Qmax log 2H maxh∈[H] Nε /(8H Qmax ) (Qh × ΠQ,h , ρ)/δ nE = O 4 ε
! .
2. Under QΠQ -realizability (Assumption J.1), J πE − J πout ≤ ε is guaranteed by the choices 2 2 H Qmax log A e , K=O ε2
2 2 e H Qmax log 2H maxh∈[H] Nε/H (Qh × ΠQ,h , ρ)/δ nE = O ε2
! .
The total number of expert queries is at most H 2 nE . Thus, without knowing which condition holds, one can choose K and nE to be the componentwise maximum of the two displayed requirements, and the corresponding guarantee applies under either condition. We remark that the rates in the Qπ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 dh = αdπhE + (1 − α)dπhout . As in the previous cases, dh is measurable with respect to the history available before sampling at stage h, and E conditionally on this history, the pairs (xih , aiE,h )ni=1 are independent with xih ∼ dh and aiE,h ∼ πE,h (· | xih ), as required by Lemma E.2. Obtaining one labeled sample at stage h requires at most h expert queries, PHincluding the queries used to roll in under the expert. Summing over the nE samples at each stage gives at most nE h=1 h ≤ H 2 nE expert queries. Case 1: QπE -realizability. For every h ∈ [H] and x ∈ X , define gh (x) := ⟨QπhE (x, ·), πE,h (· | x) − πout,h (· | x)⟩. A one-step deviation argument using expert optimality gives gh (x) ≥ 0 for dπhE -almost every x. Therefore, the definition of dh and the performance difference lemma (Lemma E.9) give H X
Ex∼dh [gh (x)] = (1 − α)(J πE − J πout ) + α
h=1
H X
Ex∼dπhE [gh (x)]
h=1
≥ (1 − α)(J πE − J πout ). Consequently, H
J
πE
−J
πout
1 XX ≤ dh (x)⟨QπhE (x, ·), πE,h (· | x) − πout,h (· | x)⟩ 1−α h=1 x∈X H
1 X d Lh (πout,h , QπhE ) 1−α h=1 v P u r H u 2 2 t 8 log 2 h=1 Nr (Qh × ΠQ,h , ρ)/δ 1 3 H Qmax log A + 8Hr + 2HQmax , ≤ 1−α K nE =
where the last inequality holds with probability at least 1 − δ by rederiving the proof of Theorem I.2 with sampling distribution dh = αdπhE + (1 − α)dπhout and comparator π ′ = πE , stopping at the intermediate product-cover bound, for any r > 0. Taking r = ε2 /(8H 2 Qmax ) gives 8Hr = ε2 /(HQmax ) and covering radius ε2 /(8H 2 Qmax ) in the logarithm. With α = 1 − ε/(2HQmax ), the choices of K and nE in the QπE -realizable branch make the right-hand side at most O(ε). Case 2: QΠQ -realizability. The subtle point is that we should not apply the performance difference lemma directly with Qπout , because πout is a pointwise average of softmax policies and need not belong to ΠQ . Instead, we represent 71
Appendix table of contents
the trajectory distribution of πout as a mixture over stagewise hybrids of the iterates. Let I = (I1 , . . . , IH ) be sampled uniformly from [K]H , and define the hybrid policy π I by πhI = πhIh
for every h ∈ [H].
We now justify carefully why these hybrids are related to the averaged policy. Let τ = (x1 , a1 , . . . , xH , aH , xH+1 ) be a trajectory under policy πout . By the definition of πout , we have Pπout (τ ) = ν0 (x1 )
H Y
[πout,h (ah | xh )Ph (xh+1 | xh , ah )]
h=1
= ν0 (x1 )
H Y
"
! # K 1 X kh πh (ah | xh ) Ph (xh+1 | xh , ah ) K kh =1
h=1
H Y ih 1 ν (x ) πh (ah | xh )Ph (xh+1 | xh , ah ) 0 1 KH h=1 i1 ,...,iH ∈[K] h I i π = EI P (τ ) .
X
=
The third line is where we use that the coordinates I1 , . . . , IH 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 function F , and in particular for the cumulative reward F (τ ) = PH h=1 rh (xh , ah ), we can average over the finite trajectory space to obtain " # h I i X X I πout πout π E [F (τ )] = P (τ )F (τ ) = EI P (τ )F (τ ) = EI Eπ [F (τ )] . τ
τ
Taking F to be the cumulative reward gives h Ii J πout = EI J π . For every I, the hybrid policy π I belongs to ΠQ . Indeed, at each stage h, choose mh = Ih − 1, the functions I Q1h , . . . , QIhh −1 ∈ Qh (empty if Ih = 1), and ηIh = ηmh +1 . By Assumption J.1, we have Qπ ∈ Q, and hence I Qπh ∈ Qh for every h. Applying the performance difference lemma (Lemma E.9) to each hybrid policy gives "H # h i D I E XX I J πE − J πout = EI J πE − J π = EI dπhE (x) Qπh (x, ·), πE,h (· | x) − πhIh (· | x) . h=1 x∈X
Using dπhE = dh + (1 − α)(dπhE − dπhout ), the right-hand side is equal to T1 + T2 , where we define T1 := EI
"H XX
# D I E Ih π dh (x) Qh (x, ·), πE,h (· | x) − πh (· | x) ,
h=1 x∈X
T2 := (1 − α)EI
"H XX
(dπhE (x) − dπhout (x))
# D I E Ih π Qh (x, ·), πE,h (· | x) − πh (· | x) .
h=1 x∈X
We first control T1 . For a fixed stage h, write J ∈ [K]H−1 for the collection of indices at all stages except h. For k ∈ [K], let I h,k,J be the full index vector obtained by setting Ih = k and I−h = J, and define π Qk,J h := Qh
I h,k,J
.
For every h, k, J, we have Qk,J h ∈ Qh . Using the independence and uniformity of Ih , we can rewrite T1 as T1 =
H X h=1
h EIh ,I−h
Ldh
H K i 1 X X h d k k,J i Ih πI πh , Qh = EJ Lh πh , Qh . K h=1 k=1
72
Appendix table of contents
k We now compare each realized comparator Qk,J h to the empirical best response Qh before averaging over J. With a k slight abuse of notation, recall that π denotes the policy whose decision rule at stage h is πhk . Define the same uniform estimation error used in Theorem I.2 by
∆d (π) = max sup Lbdh (πh , Qh ) − Ldh (πh , Qh ) . h∈[H] Qh ∈Qh
For every fixed h, k, J, on this uniform-concentration event, bdh πhk , Qk,J + ∆d π k ≤ Lbdh πhk , Qkh + ∆d π k ≤ Ldh πhk , Qkh + 2∆d π k . Ldh πhk , Qk,J ≤ L h h The middle inequality is the empirical best-response property of Qkh , which we can use since Qk,J h is one feasible element of Qh by Assumption J.1. Averaging the last display over J, summing over h and k, and dividing by K, we obtain H
T1 ≤
K
K
h=1 k=1
k=1
1 X X d k k 2H X Lh πh , Qh + ∆d π k . K 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 X p X Ldh πhk , Qkh = Qkh (x, ·), πE,h (· | x) − πhk (· | x) ≤ 3 Q2max K log A. dh (x) x∈X
k=1
k=1
Since π k is in ΠQ , applying Lemma E.2 with Πh = ΠQ,h and radius r > 0 gives, on an event of probability at least 1−δ, v u u 8 log 2 PH Nr (Qh × ΠQ,h , ρ)/δ K X t h=1 ∆d π k ≤ 4Kr + KQmax . nE k=1
Combining the previous three displays, taking r = ε/H, and bounding the sum by the maximum gives s r 8 log 2H maxh Nε/H (Qh × ΠQ,h , ρ)/δ Q2max log A + 8ε + 2HQmax . T1 ≤ 3H K nE It remains to control T2 . Define, for each h, x, I, D I E ghI (x) := Qπh (x, ·), πE,h (· | x) − πhIh (· | x) . I
We have Qπh (x, a) ∈ [0, Qmax ] for every x, a, h, I. Therefore I
ghI (x) = Qπh (x, πE,h ) − Qπh
I
x, πhIh
≤ Qmax .
Using the triangle inequality and the previous inequality, we can bound the signed change-of-measure term explicitly: "H # X X |T2 | ≤ (1 − α)EI (dπhE (x) − dπhout (x))ghI (x) h=1 x∈X
≤ (1 − α)
H X
"
# X
EI
x∈X
h=1
≤ (1 − α)Qmax
|dπhE (x) − dπhout (x)| ghI (x)
H X
∥dπhE − dπhout ∥1
h=1
≤ 2(1 − α)HQmax . In the last line, we used that both dπhE and dπhout are probability distributions, so their ℓ1 distance is at most 2. With α = 1 − ε/(2HQmax ), the term T2 is at most ε. The QΠQ -realizable choices of K and nE make T1 at most O(ε), proving the second branch for the same averaged output policy πout .
73
Appendix table of contents