Provable Benefits of Regularization: Fast Rates for Adversarial Imitation Learning

1 Introduction

• AIL uses a reward-based performance criterion because cumulative reward depends on state–action occupancy, linking expert–learner occupancy gaps to performance on tasks represented by the reward class.This differs from behavior cloning, which directly predicts expert actions.Source: §1 · p. 1
• Reward and entropy-based policy regularization appear in practical AIL methods, but their finite-sample benefits remain less understood.GAIL and LS-IQ are examples of methods incorporating these ingredients.Source: §1 · p. 2
• AIL's reward learner must estimate from both a reused finite expert dataset and learner trajectories whose distribution changes with the evolving policy.The policy learner also improves behavior using an estimated value function.Source: §1 · p. 2
• Dually Regularized AIL combines KL policy regularization with a quadratic reward penalty weighted by expert and learner occupancies.It alternates optimistic value-based policy learning with online mirror descent over a general convex reward class, reusing a fixed expert dataset and collecting one learner trajectory per episode.Source: §1 · p. 2
• The analysis yields Õ(1/ε) sample requirements in both expert demonstrations and online interactions, including for stochastic experts.The guarantee is for fixed positive regularization parameters and controlled function-class complexity.Source: §1 · p. 3
• Reward-side online mirror descent controls estimation error from expert data and stochastic learner feedback, while optimistic KL-regularized policy learning uses curvature to control planning uncertainty.The analysis combines these arguments to explain the fast finite-sample rates.Source: §1 · p. 3

2 Related Work

• GAIL links convex cost regularization to occupancy discrepancy, while IQ-Learn and LS-IQ retain reward-policy regularization structures.LS-IQ studies a squared reward penalty under expert–learner mixture occupancies; the paper notes that a quadratic penalty controls reward magnitude and supplies curvature, not necessarily input smoothness.Source: §2 · p. 3
• Prior AIL analyses cover online apprenticeship learning, unknown tabular dynamics, linear-mixture models, linear MDPs, and general function approximation.OPT-AIL uses a generalized eluder coefficient, while MB-AIL learns a transition model and gives second-order guarantees.Source: §2 · p. 3
• Table 1 compares sample complexity in expert trajectories and online episodes across related works, omitting horizon, reward-range, and structural-complexity factors.Its guarantees are high-probability except Mimic-Emp's expected gap; “General” experts may be stochastic.Source: Table 1 · p. 4
• The paper's regularized saddle-point criterion uses reward curvature for inverse-sample dependence without requiring deterministic experts or vanishing variance.The passage cautions that objectives and structural assumptions matter when comparing this result with prior work.Source: §2 · p. 4
• Prior stochastic-expert fast-rate results depend on setting: tabular expected-error bounds and entropy-regularized linear-reward IRL rates address objectives distinct from this paper's regularized objective.The paper frames its rate as complementary to ordinary-imitation lower bounds and notes that offline cloning rules out a universal claim that online interaction is necessary.Source: §2 · p. 4

3 Preliminaries

• The setup is an episodic MDP with state and action spaces, horizon H, transition dynamics, a fixed initial state, and stage-wise state–action occupancies induced by a policy.The expert supplies N independent trajectories; the learner interacts for K rounds and seeks a bounded stage-wise reward distinguishing expert and learner behavior.Source: §3 · p. 5
• The policy is regularized by KL divergence to a reference policy; choosing a uniform reference recovers entropy regularization up to an additive constant.The reference may alternatively be initialized from a policy pretrained via behavioral cloning.Source: §3 · p. 5
• The AIL objective compares learner and expert uniformly over the reward class and adds a quadratic reward regularizer weighted by expert occupancy.The formulation is a min-max optimization over policy and reward.Source: §3 · pp. 5–6
• The cumulative dual gap over K online episodes is the paper's regret measure.The cited definition follows the regularized AIL objective.Source: §3 · p. 6
• The analysis quantifies exploration complexity with generalized Eluder dimension and function-class size with covering numbers.The generalized Eluder dimension is described for bounded function classes over state–action pairs; covering numbers enter uniform concentration bounds.Source: §3 · p. 6

4 Dually Regularized Adversarial Imitation Learning

• The algorithm alternates two phases each episode: optimistic value-based policy learning and an online mirror descent reward update using expert and learner data.It takes an expert dataset, reference policy, and function classes for action-value approximation and reward learning as inputs.Source: §4 · pp. 6–7
• Policy planning uses a regularized shaped reward, backward least-squares value estimation on collected transitions, and exploration bonuses from confidence bounds.The resulting optimistic action values enter a soft Bellman update and a closed-form policy update balancing value against KL deviation from the reference policy.Source: §4 · pp. 7–8
• Historical transitions support planning under changing rewards and policies because Bellman targets are recomputed without estimating the transition dynamics.On the stated confidence event, the clipped action-value estimates are optimistic and encourage exploration of uncertain state–action pairs.Source: §4 · p. 8
• The reward learner observes empirical loss from the current learner episode and the average over N expert trajectories, then updates the reward using online mirror descent.The analysis loss is distinguished from the empirical loss used to determine the reward update.Source: §4 · p. 8
• The reward update uses an adaptive proximal penalty aligned with the quadratic reward penalty, supporting a reward-class Eluder-dimension stability bound and a sharp reward-error bound.The stated design adds an extra multiplier to the penalty.Source: §4 · pp. 8–9

5 Theoretical Analysis

• The theorem assumes bounded bonus classes, finite covering numbers for reward, value, and bonus classes, and Bellman completeness for value estimation.The bonus class contains every bonus generated by the algorithm over possible data histories.Source: §5 · p. 9

N log 4HN R(1/N2)2

• The faster rates do not directly imply the same sample complexity for the unregularized objective, which must account for regularization bias and parameter dependence.Source: N log 4HN R(1/N2)2 · p. 10
• Matching the proximal penalty to empirical curvature bounds reward-update stability by generalized eluder dimension, while ρ reserves curvature for expert and learner sampling errors.Source: N log 4HN R(1/N2)2 · p. 11
• The regularized saddle-point gap is tilde-O(1/K + 1/N) for fixed regularization parameters and controlled function-class complexity.The guarantee concerns the regularized objective, not the unregularized imitation gap.Source: N log 4HN R(1/N2)2 · pp. 10–11
• ω allocates curvature between expert and learner occupancies; values near either endpoint weaken the corresponding error bound, while ω = 1/2 matches LS-IQ's equal-mixture regularizer (Al-Hafez et al., 2023).For any fixed ω in (0, 1), the regularized-gap rate is preserved under the stated conditions.Source: N log 4HN R(1/N2)2 · p. 11

• The regret decomposition isolates reward-learning error T1 from policy-planning error T2, allowing the proof to bound the two sources separately.Source: §6 · p. 11
• Curvature-matched online mirror descent retains loss curvature to control stability despite reward iterates depending on sequential learner feedback and a repeatedly reused expert dataset.The proximal penalty telescopes in a data-dependent seminorm while preserving comparator curvature.Source: §6 · pp. 11–12
• Uniform expert-data concentration permits each reward iterate to depend on the same demonstrations, and the resulting expert-reuse contribution averages to 1/N without deterministic experts or fresh demonstrations each episode.The cumulative expert-reuse contribution is O(KH/N).Source: §6 · p. 12
• Optimistic KL-regularized planning makes policy error quadratic in action-value estimation error, which is reduced to squared bonuses and controlled using generalized eluder dimension.The analysis transfers observed squared-bonus control to occupancy expectations.Source: §6 · p. 12
• Averaging the episode-wise bounds gives an O(1/K + 1/N) regularized saddle-point gap for fixed regularization parameters and controlled function-class complexity.Source: §6 · p. 13

7 Conclusion

• Reward regularization absorbs sampling error while controlling update stability, and policy regularization controls planner error, together contributing to faster AIL convergence.Source: §7 · p. 13

A Additional Related Works

• Prior regularized-RL guarantees do not directly address an adversarial reward learner that repeatedly reuses a finite expert sample; the analysis also uses generalized eluder dimension for reward stability and value estimation.Source: A Additional Related Works · p. 16

B Properties of KL-Regularized RL

• The appendix states that KL-regularized RL has a closed-form optimal policy and expresses a policy’s regularized value gap as expected cumulative KL divergence from that policy.Source: B Properties of KL-Regularized RL · p. 17

C Proof of Theorem 1

• The proof assumes finite expected KL costs for the expert and algorithm policies and does not assume independence between stages.Source: C Proof of Theorem 1 · p. 18

C.1 Main Proof of Theorem 1

• The regret decomposition separates reward-learning error T1 from policy-planning error T2, and their bounds combine to establish Theorem 1.Source: §C.1 · pp. 18, 20
• Retained quadratic curvature offsets proximal-penalty growth and variance terms, controlling stability and concentration for reward learning.Source: §C.1 · p. 19
• Choosing ρ = 1/2 balances the stability and sampling-error factors, while any fixed ρ in (0, 1) preserves the sample-budget dependence with constants depending on ρ.Source: §C.1 · p. 19
• Optimism and the KL-regularized performance-difference identity make policy-planning error quadratic in action-value estimation error, which exploration bonuses and generalized eluder dimension control.Source: §C.1 · p. 20

C.2.1 Technical Lemmas

• The reward-learning error is decomposed into stability and concentration terms, with the update controlling the former through reward-class sequential complexity.The technical lemmas bound stability and sampling error separately.Source: §C.2.1 · p. 21

• The proof first separates reward-learning error T1 into two terms using the reward-error decomposition.Source: §C.2.2 · p. 22
• Earlier stability and concentration lemmas bound the two terms, after which the proof sets ρ = 1/2 and absorbs the lower-order stability term into learner concentration.Source: §C.2.2 · p. 22
• These steps yield the stated reward-learning error bound up to universal numerical constants.Source: §C.2.2 · p. 22

C.2.3 Proofs of the Technical Lemmas

• For any fixed comparator r, the proof decomposes TC(r) into learner-sampling and expert-sampling errors and bounds their covering-based remainders separately.For the learner term, approximation at scale 1/K2 contributes at most 2H(1 + α(1 − ω))/K after summing over k and h. For the expert term, approximating both rewards within 1/N2 in sup norm changes reward polynomials by at most 8(1 + αω)/N2 for each h and k.Source: §C.2.3 · pp. 25–27

C.3.1 Technical Lemmas

• The auxiliary lemmas bound the covering numbers of the optimistic value classes through the regression and bonus classes.These bounds support the subsequent pointwise regression-error analysis.Source: §C.3.1 · p. 27
• Uniform regression-error control over the function classes supports the confidence event used to establish optimism.The argument covers data-dependent regression and continuation functions after establishing a uniform event.Source: §C.3.1 · p. 28
• With high probability, the action-value estimate is optimistic and its Bellman residual is bounded above by twice the bonus.The proof does not require the clipped residual to be nonnegative.Source: §C.3.1 · p. 28

C.3.2 Proof of Lemma 8

• A uniform regression confidence event and the optimism lemma provide the conditions for bounding policy-planning error.The proof intersects events with total probability at least 1 − δ/2 before applying the policy-planning bound.Source: §C.3.2 · p. 28

C.3.3 Proofs of the technical lemmas

• Uniform concentration covers data-dependent regression and continuation functions selected using the same historical transitions.The functions are selected only after the uniform event has been established.Source: §C.3.3 · p. 30
• The optimistic action-value estimate has Bellman residual at most twice the bonus, although clipping need not preserve residual nonnegativity.The backup can exceed Vmax, so the proof asserts an upper residual bound rather than nonnegativity.Source: §C.3.3 · p. 31
• The optimistic KL-regularized policy planning argument bounds policy error by combining optimism, the Bellman residual bound, and nonnegative KL divergence.The proof proceeds by backward induction from the terminal stage.Source: §C.3.3 · pp. 31–32

D Proof of Corollary 1

• Choosing counts so each online and expert contribution is at most ϵ/2 gives the corollary’s sufficient sample orders, including suppressed logarithmic factors.The counts must be sufficiently large universal multiples of the displayed expressions.Source: D Proof of Corollary 1 · p. 33
• Because the complexity terms depend on both K and N, the sufficient count inequalities must hold jointly; boundedness alone gives no small-complexity growth rate.An upper bound on counts alone does not establish sufficiency.Source: D Proof of Corollary 1 · p. 33