Source-linked AI summary
Of Moments and Matching: A Game-Theoretic Framework for Closing the Imitation Gap
Gokul Swamy, Sanjiban Choudhury, J. Andrew Bagnell, Zhiwei Steven Wu
TL;DR
Imitation learning must match expert performance without access to the unknown reward, and existing approaches use different divergence or moment-matching objectives. The paper classifies reward and Q-value moment matching, analyzes adversarial games and their performance bounds, and introduces moment recoverability to characterize error compounding. Reward matching has an O(ϵT) bound while off-policy Q matching has an O(ϵT^2) bound; empirically, AdRIL outperforms GAIL across tested environments and avoids SQIL’s catastrophic collapse there.
Problem
Imitation learning must match expert performance without access to the unknown reward, and existing approaches use different divergence or moment-matching objectives.
Source: §1 · p. 1Method
The paper classifies reward and Q-value moment matching, analyzes adversarial games and their performance bounds, and introduces moment recoverability to characterize error compounding.
Source: §1 · p. 2, §3.2 · p. 3Results
Reward matching has an O(ϵT) bound while off-policy Q matching has an O(ϵT^2) bound; empirically, AdRIL outperforms GAIL across tested environments and avoids SQIL’s catastrophic collapse there.
Source: §4.2 · p. 4, §4.3 · p. 5, §7 · p. 8Takeaways & Limitations
Recoverability depends on both the moments matched and the expert: LOOP is 1-recoverable, whereas CLIFF is not H-recoverable for any H<T if the expert never ends up in sx.
Source: §4.5 · p. 6The stated bounds rely on assumptions about the policy and function classes, including convexity and compactness; the main setup also defines recoverability relative to a specified expert Q-function class.
Source: §3.2 · p. 3, §4 · p. 4
Abstract
from arXiv · showhide
We provide a unifying view of a large family of previous imitation learning algorithms through the lens of moment matching. At its core, our classification scheme is based on whether the learner attempts to match (1) reward or (2) action-value moments of the expert's behavior, with each option leading to differing algorithmic approaches. By considering adversarially chosen divergences between learner and expert behavior, we are able to derive bounds on policy performance that apply for all algorithms in each of these classes, the first to our knowledge. We also introduce the notion of moment recoverability, implicit in many previous analyses of imitation learning, which allows us to cleanly delineate how well each algorithmic family is able to mitigate compounding errors. We derive three novel algorithm templates (AdVIL, AdRIL, and DAeQuIL) with strong guarantees, simple implementation, and competitive empirical performance.
1. Introduction
The paper frames imitation learning as matching learner and expert behavior under an unknown reward, and organizes algorithms by the moments they match. It develops bounds and moment recoverability to distinguish these approaches and introduces three algorithm templates.
1. Introduction
- Moment matching can preserve expert performance when the matched basis-function class includes the unknown objective, and its expectations support uncertainty-aware regularization.The paper presents this as a way to estimate moments from demonstrator samples and quantify uncertainty.Source: §1 · p. 1
- The framework classifies methods by matching on-policy reward, off-policy Q-value, or on-policy Q-value moments, each with different environment and expert requirements.The figure notes that off-policy Q methods can have quadratically compounding errors, while on-policy Q methods can yield strong policies in recoverable MDPs.Source: §1 · p. 1, Figure 1 · p. 1
- Reward moments capture differences in induced state visitation as well as action conditionals, making them harder to match but associated with stronger guarantees than Q-moment matching.Source: §1 · p. 2
- The paper introduces moment recoverability to characterize when compounding errors are likely, then derives AdVIL, AdRIL, and DAeQuIL with performance guarantees.The authors describe the practical performance and error-compounding guarantees of these algorithms as differing substantially.Source: §1 · p. 2
2. Related Work
Related work spans imitation learning applications, interactive methods for addressing compounding errors, and adversarial approaches. This paper connects functional gradients and integral probability metrics to derive algorithms that differ from prior methods in how they update discriminators and handle estimation.
Related Work
- Interactive expert feedback on learner-generated states can teach recovery from mistakes, while adversarial imitation learning frames policy learning as a game against a discriminator.Prior adversarial methods include GAIL and related approaches.Source: §2 · p. 2
- AdRIL and AdVIL optimize a value-directed integral probability metric, with AdRIL using functional-gradient discriminator updates and a linear objective in the discriminator.The paper contrasts this with the Donsker–Varadhan KL bound, whose exponentiated discriminator expectation is difficult to estimate from few samples.Source: §2 · p. 2
- AdVIL avoids ValueDICE’s exponential-expectation estimation difficulty, while AdRIL adaptively updates its discriminator unlike SQIL’s fixed discriminator.The paper relates DAeQuIL to extending DAgger to adversarial losses.Source: §2 · p. 2
3. Moment Matching Imitation Learning
The section defines imitation learning around closing the performance gap to an expert despite an unknown reward, then compares moment-matching choices and formulates them as games. The taxonomy distinguishes the information and interaction each choice requires.
3.1. Problem Definition
- The learner seeks to close the imitation gap, but must use expert demonstrations because the reward function is unknown.Perfectly matching all moments of expert performance would close the gap regardless of the unknown reward.Source: §3.1 · p. 3
3.2. Moment Taxonomy
- The taxonomy separates per-timestep reward moments from over-the-horizon Q-value moments and defines H-recoverability for an expert policy and its Q-function class.H bounds the expert's possible advantage under that class and intuitively indicates how many steps recovery from an arbitrary mistake takes.Source: §3.2 · p. 3
- Reward matching requires learner on-policy rollouts, off-policy Q matching can use expert trajectories alone, and on-policy Q matching needs learner rollouts plus an interactive expert.The off-policy Q-function class can be more complex because it must capture MDP dynamics and choices of any policy.Source: §3.2 · p. 3
3.3. Moment Matching Games
- Each moment-matching variant is a learner–discriminator minimax game, with the learner minimizing and the discriminator maximizing a payoff determined by the chosen moment class.The policy class contains the expert, giving the minimax value zero for the three games.Source: §3.3 · p. 4
4. From Approximate Equilibria to Bounded Regret
The section bounds imitation gaps for reward, off-Q, and on-Q moment matching using approximate-equilibrium solutions, then relates on-Q guarantees and compounding errors to recoverability. LOOP and CLIFF illustrate how errors affect learner behavior over a horizon.
4.1. Example MDPs
- LOOP lets the learner enter an unseen state and keep making errors; in CLIFF, one mistake can trap it in an absorbing state.LOOP is 1-recoverable for an expert that always moves toward s1; CLIFF is not H-recoverable for any H < T when the expert never reaches sx.Source: §4.1 · p. 4, Figure 2 · p. 4, §4.5 · p. 6
4.2. Reward Moment Performance Bounds
- Reward matching has a tight O(ϵT) worst-case imitation-gap rate, and its game-level bounds cover continuous spaces and algorithms including GAIL and SQIL.The upper bound applies across MDPs, while a lower bound establishes the worst-case rate.Source: §4.2 · pp. 4–5
4.3. Off-Q Moment Performance Bounds
- Off-Q matching has O(ϵT^2) upper and Ω(ϵT^2) lower bounds on the imitation gap.The upper bound holds for all MDPs under the stated function-class condition; the lower bound holds for an example MDP.Source: §4.3 · p. 5
4.4. On-Q Moment Performance Bounds
- On-Q matching has an O(ϵHT) upper bound for H-recoverable expert–moment pairs, while a lower bound of Ω(ϵT) holds for some MDP.The upper bound requires FQE to span F; the lower bound is existential.Source: §4.4 · p. 5
4.5. Recoverability in Imitation Learning
- Recoverability depends on both the expert and moment class: O(1) recoverability gives reward-like O(ϵT) behavior, while O(T) recoverability gives off-Q-like O(ϵT^2) behavior.For a non-H-recoverable pair, statewise classification error κ can yield an Ω(κT^2) imitation gap, even with interactive expert feedback.Source: §4.5 · p. 6
5. Finding Equilibria: Idealized Algorithms
The paper gives reduction-based procedures for finding approximate equilibria in moment-matching imitation games, using no-regret updates and best responses. With the required oracles, the procedures provide efficient equilibrium strategies that also certify policy performance.
5. Finding Equilibria: Idealized Algorithms
- The framework uses an outer no-regret strategy and an inner modified best response; causally conditioned policies make the games bilinear and strongly dual.The paper considers finite-state problems with a complete policy class.Source: §5 · p. 6, §5.2 · p. 6
5.2. Theoretical Guarantees
- The primal approach runs no-regret updates on policies and maximizes over discriminators; the dual runs no-regret updates on discriminators and computes entropy-regularized policy best responses.Entropy regularization helps recover a single policy-player equilibrium strategy.Source: §5.2 · pp. 6–7
- With no-regret and maximization oracles, all three imitation games yield a δ-approximate equilibrium strategy in poly(1/δ,T,ln|S|,ln|A|) outer iterations.The result applies using the specified oracles in either the primal or dual approach.Source: §5.2 · p. 7
- Setting δ = ϵ and combining equilibrium guarantees with the moment-matching bounds makes the computed equilibria certificates of policy performance.The authors conclude that this framework can efficiently close the imitation gap.Source: §5.2 · p. 7
6. Practical Moment Matching Algorithms
The paper turns moment-matching theory into three practical IPM-based algorithms: AdVIL matches off-Q moments, AdRIL reward moments, and DAeQuIL on-Q moments.
6.1. AdVIL: Adversarial Value-moment Imitation Learning
- AdVIL minimizes an IPM objective that drives down the learner’s extra cost over the expert, treating the negative discriminator as a value function.The algorithm uses a higher learning rate for the discriminator than for the policy, making it a primal algorithm.Source: §6.1 · p. 7
6.2. AdRIL: Adversarial Reward-moment Imitation Learning
- AdRIL uses RKHS functional-gradient discriminator updates and maximum-entropy reinforcement learning for policy best responses to match reward moments.With an indicator kernel and no repeated states, its objective is equivalent to maximizing reward at expert datapoints.Source: §6.2 · pp. 7–8
6.3. DAeQuIL: DAgger-esque Qu-moment Imitation Learning
- DAeQuIL extends DAgger to moment space with adversarial per-round losses and Follow the Regularized Leader, optimizing over a history of learner state distributions.It is technically not solving the on-Q game directly, but the authors say it retains strong performance guarantees.Source: §6.3 · p. 8
7. Experiments
Across continuous-control benchmarks and a toy UAV navigation task, the proposed methods match or exceed relevant baselines, with different advantages across algorithms.
7. Experiments
- AdVIL matches ValueDICE and behavioral cloning across most tasks, AdRIL beats GAIL across all tested environments, and DAeQuIL significantly outperforms DAgger on toy UAV navigation.Figure 4 contrasts DAgger’s mean-action crash with DAeQuIL’s successful forest navigation.Source: §7 · p. 8, Figure 4 · p. 8
- On HalfCheetah, AdRIL recovers a strong policy with far less data than behavioral cloning, while behavioral cloning reaches the optimal policy with enough data on both environments.The authors interpret the behavioral-cloning results as indicating little covariate shift on those environments.Source: §7 · p. 8
- AdVIL reliably reaches a policy quality comparable to ValueDICE using an order of magnitude less compute.Source: §7 · p. 8
8. Discussion
The discussion organizes imitation learning around reward, off-Q, and on-Q moment matching, then explains their guarantee–optimization trade-offs and the role of recoverability.
8.1. A Unifying View of Moment Matching IL
- The taxonomy distinguishes reward, off-Q, and on-Q approaches; the discussion notes comparatively less work on off-Q and on-Q dual algorithms.The table marks IPM-based algorithms in bold.Source: §8.1 · p. 9, Table 3 · p. 9
8.2. The Hidden Cost of Reward Moment Matching
- Reward moment matching has tighter performance bounds but can require exponentially harder optimization than Q-matching approaches.In a tree-structured problem, reward matching searches over O(|A|^T) trajectories, while the Q-matching choices total O(|A|T).Source: §8.2 · p. 9
8.3. Takeaways
- Reward matching requires an accurate simulator or real-world interaction, while off-Q matching can use collected data but incurs an O(εT^2) imitation gap.Source: §8.3 · p. 9
- Moment recoverability characterizes compounding-error behavior: O(T)-recoverable problems can admit unavoidable O(T^2) error, whereas O(1)-recoverability lets on-policy algorithms prevent compounding.The authors also characterize AdVIL, AdRIL, and DAeQuIL as addressing distinct imitation-learning difficulties, with AdRIL described as simple to implement and strong in theory and practice.Source: §8.3 · p. 9
Supplementary Material
A constructed MDP shows quadratic compounding of errors in an O(T)-recoverable setting.
A.1. Proof of Lemma 7
- With O(T)-recoverability, taking a2 in s1 with probability ε yields an Ω(εT^2) performance loss, despite only one action being available in s2.Source: §A.1 · p. 12
A.2. Proof of Entropy Regularization Lemma
The appendix establishes how entropy regularization and no-regret procedures yield approximate equilibrium policies, then derives off-Q and reward-moment algorithm objectives. The derivations use different sampling and optimization routes for AdVIL and AdRIL.
A.2. Proof of Entropy Regularization Lemma
- The regularized objective is strongly convex in the policy representation because negative entropy is strongly convex.Source: §A.2 · p. 12
- Entropy regularization yields an approximate equilibrium strategy for the original game, with error depending on regularization and game parameters.The proof bounds the strategy pair using αT(ln |A| + ln |S|).Source: §A.2 · pp. 12–13
A.3. Proof of Theorem 1
- No-regret learning finds a δ-approximate equilibrium in polynomially many iterations, but requires a no-regret algorithm over Π, challenging for reward moment matching.Source: §A.3 · p. 13
B.1. AdVIL Derivation
- AdVIL substitutes the learner’s expected Bellman operator into its objective, which telescopes into an off-policy expression estimated from expert trajectories.The resulting objective avoids estimating the expectation of an exponentiated discriminator.Source: §B.1 · p. 14
B.2. AdRIL Derivation
- AdRIL computes functional gradients from learner rollouts and fixed expert demonstrations, then aggregates them into the policy’s cost function.The kernel can be an indicator in discrete spaces or relaxed to a Gaussian in continuous spaces.Source: §B.2 · p. 14
B.3. DAeQuIL Derivations
DAeQuIL uses Follow The Regularized Leader losses, with a fixed visitation distribution that avoids repeatedly resampling trajectories. The appendix also describes experimental setup and reports that AdVIL converges faster than ValueDICE, while warning that prolonged training can collapse performance.
B.3. DAeQuIL Derivations
- DAeQuIL’s losses use the learner’s state-action visitation distribution, avoiding the need to resample trajectories after every gradient step.The proper on-Q game would make the state distribution depend on the policy passed to the loss.Source: §B.3 · p. 14
- Without realizability, DAeQuIL requires a policy that matches expert moments within ε on every visitation distribution generated by a policy in Π.Using the proper on-Q loss instead requires a stronger condition and a more computationally expensive optimization procedure.Source: §B.3 · p. 15
C.1. Expert
- The experiments train experts using PPO and SAC, primarily with previously tuned hyperparameters.Source: §C.1 · p. 15
C.2. Baselines
- Behavioral cloning solves all considered tasks with 25 trajectories and 100k gradient-descent steps, while other approaches can perform better with less data.Source: Table 6 · p. 15
C.3. Our Algorithms
- For AdRIL, balanced sampling can stabilize updates on some environments but significantly hamper performance on others; standard sampling is the recommended default.The experiments compare balanced and unbalanced sampling on Ant.Source: §C.3 · p. 16, Figure 7 · p. 16
- AdVIL converges in 50k steps on HalfCheetah and 100k steps on Ant, versus 500k steps for ValueDICE on both, but longer training can collapse policy performance.Loss fluctuations after a steady decrease can flag collapse without environment access.Source: §C.3 · p. 16
D. On-Q Experiments
The on-Q experiments find that DAeQuIL can match DAgger when behavioral cloning nearly solves a task, and outperform it when selected moments capture the task objective. The appendices bound a mixed reward-and-value moment class and describe trade-offs in combining those moments.
D. On-Q Experiments
- On rocket landing, DAeQuIL performs around as well as DAgger, with both quickly learning expert-equivalent policies when behavioral cloning nearly solves the task.Source: D. On-Q Experiments · pp. 16–17, Figure 8 · p. 17
- DAeQuIL progresses farther into the forest than DAgger, whose behavioral-cloning-style conditional-mean actions can send the drone into trees.The learner uses an imminent-crash indicator and heading difference as moments; the reported learning curves show DAeQuIL outperforming DAgger.Source: D. On-Q Experiments · p. 17, Figure 9 · p. 17
E.1. A Fourth Moment Class: Mixed-Moment Value
- Mixed reward-and-value moments give an O(εT^2) upper bound and an Ω(εT) lower bound on the imitation gap under the stated function-class conditions.The upper bound applies when either the scaled learner-Q and value classes or the scaled expert-Q and value classes span the reward class.Source: §E.1 · p. 18
- The mixed-moment bounds appear to offer no policy-performance gain, but value-based methods may be needed when action labels are unavailable.Source: §E.1 · p. 18
E.2. Combining Reward and Value Moments
- Combining reward and Q moments offers a bias/variance trade-off; reward-moment matching may be simpler for sparse rewards but adds nonstationary policies.A backward dynamic-programming procedure for the on-Q expansion is not possible because it requires policy trajectories from previous timesteps.Source: §E.2 · pp. 18–19