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
cs.LG, cs.AI, stat.ML
2026-08-01
OVI matches the expert whenever the learner can represent the value function. A matching lower bound forces any offline method to scale with the state space, so interaction is necessary.
Imitation learning trains an agent to copy expert behavior. The simplest version, behavior cloning (BC), fits the expert's per-step action distribution from demonstrations, but when the learner cannot represent the expert's policy exactly, errors compound across time steps and performance plateaus. This is routine in distillation, where a small student cannot fit the large teacher's full action distribution.
Two fixes are widely accepted in practice. One is on-policy interaction (DAgger and its kin): the learner queries the expert along its own trajectories. The other is value-based learning: estimate a value function and derive a policy from it rather than fitting the expert's full action distribution. This paper asks why both help, and whether they enable each other.
The headline result: on-policy interaction relaxes what the learner must represent. Matching the expert's return only requires the learner to realize the expert's value function Q^piE, whereas policy-based methods need the stricter assumption that the learner can represent the expert policy itself. In distillation the former is often far easier to satisfy.
OVI (On-Policy Value-Based Imitation) operationalizes this. Using the performance difference lemma, it writes the gap to the expert's return as a min-max game between a policy player and a Q player. The crucial design choice is layer-wise learning: the policy player optimizes one time step at a time, because the state distribution at step h depends only on the already-fixed earlier steps, so the sampling distribution can be pinned down before optimizing that layer. Computationally OVI needs only a linear maximization oracle for the Q updates.
A single tractability table captures the conclusion:
| Realizability | Offline IL | Interactive IL |
| Reward | intractable | intractable |
| Value Q^piE | intractable | tractable (OVI) |
| Policy piE | tractable (BC) | tractable (DAgger) |
Value realizability is tractable only when interaction is allowed. Theorem 3.1 gives OVI a sample complexity of about Otilde(H^5 Q^4 log|Q| / eps^4) expert queries under Q^piE-realizability, with no assumption on the learner's policy class; if the value class is convex the rate improves to Otilde(eps^-2).
Theorem 4.1 supplies the matching lower bound: even with a value class of just two functions and a two-step horizon, any offline algorithm needs at least Omega(min{|X|, log|F|} / eps) expert trajectories, scaling with the state space. Under the same weak assumption, offline learning is simply impossible.
Experiments run on four Gymnasium environments (Acrobot, CartPole, Pendulum, LunarLander). The expert is a two-layer network with 64 neurons per layer; learners keep the depth but shrink the width from 2 to 64, across 50 seeds. At width 64 BC and DAgger do fine, but degrade as the network shrinks, while OVI leads at every size and learns well even at the smallest width. In a synthetic Q^piE-realizable MDP, OVI's reward suboptimality converges much faster than DAgger's, and it matches the expert's return without matching its trajectory distribution (its trajectory TV distance to the expert stays nonzero). The reason: this environment has about 2^|X| optimal policies, so acting greedily with respect to a learned value function suffices, while DAgger insists on matching the expert's actions everywhere, which is harder.
For anyone doing distillation, the practical signal is concrete: when the student is much smaller than the teacher, value-based on-policy distillation may beat policy-based on-policy distillation. Theoretically the paper pins down what interaction buys, which is representational slack, dropping the requirement from policy to value. The authors are upfront that language-model distillation is the most relevant test and remains untried, but the mechanism is directly portable.
OVI's dependence on the horizon H is worse than policy-based methods (BC, DAgger); whether this is fundamental stays open. For nonconvex value classes the rate is only Otilde(eps^-4); a variant, Q-OVI, reaches Otilde(eps^-2) but requires discretizing the value class, which is computationally unattractive for continuous classes like neural networks. OVI learns a nonstationary policy with memory and compute linear in H; a stationary approximation works empirically but lacks a guarantee. Experiments are confined to small Gym tasks; the LM distillation setting most worth testing is untouched.