PaperlayerView exact revision on arXiv

Source-linked AI summary

Toward the Fundamental Limits of Imitation Learning

Nived Rajaraman, Lin F. Yang, Jiantao Jiao, Kannan Ramachandran

arXiv:2009.05990v1cs.LGcs.AImath.OCstat.ML

TL;DR

The paper asks what statistical limits imitation learning faces, since supervised-learning reductions can be loose for stochastic experts and may depend on the number of actions. The paper analyzes empirical risk minimization under log loss and develops a hybrid minimum-distance method that imitates observed expert actions and learns on remaining states. In the active setting, learner suboptimality is at least |S|H²/N up to universal constants, even for deterministic experts; known transitions yield a policy that breaks the H² error-compounding barrier.

  • Problem

    The paper asks what statistical limits imitation learning faces, since supervised-learning reductions can be loose for stochastic experts and may depend on the number of actions.

    Source: §1 · p. 3, §1.1 · p. 5

  • Method

    The paper analyzes empirical risk minimization under log loss and develops a hybrid minimum-distance method that imitates observed expert actions and learns on remaining states.

    Source: §1.1 · p. 6

  • Results

    In the active setting, learner suboptimality is at least |S|H²/N up to universal constants, even for deterministic experts; known transitions yield a policy that breaks the H² error-compounding barrier.

    Source: §1.1 · p. 4, §7 · p. 15

  • Takeaways & Limitations

    Behavior cloning is optimal in the no-interaction setting for deterministic experts, while known transitions permit better dependence on episode length.

    Source: §7 · p. 15

    The gap between known-transition upper and lower bounds remains open, as does how much finite interaction or non-tabular settings can improve the results.

    Source: §7 · p. 15

Abstract

from arXiv · show

Imitation learning (IL) aims to mimic the behavior of an expert policy in a sequential decision-making problem given only demonstrations. In this paper, we focus on understanding the minimax statistical limits of IL in episodic Markov Decision Processes (MDPs). We first consider the setting where the learner is provided a dataset of $N$ expert trajectories ahead of time, and cannot interact with the MDP. Here, we show that the policy which mimics the expert whenever possible is in expectation $\lesssim \frac{|\mathcal{S}| H^2 \log (N)}{N}$ suboptimal compared to the value of the expert, even when the expert follows an arbitrary stochastic policy. Here $\mathcal{S}$ is the state space, and $H$ is the length of the episode. Furthermore, we establish a suboptimality lower bound of $\gtrsim |\mathcal{S}| H^2 / N$ which applies even if the expert is constrained to be deterministic, or if the learner is allowed to actively query the expert at visited states while interacting with the MDP for $N$ episodes. To our knowledge, this is the first algorithm with suboptimality having no dependence on the number of actions, under no additional assumptions. We then propose a novel algorithm based on minimum-distance functionals in the setting where the transition model is given and the expert is deterministic. The algorithm is suboptimal by $\lesssim \min \{ H \sqrt{|\mathcal{S}| / N} ,\ |\mathcal{S}| H^{3/2} / N \}$, showing that knowledge of transition improves the minimax rate by at least a $\sqrt{H}$ factor.

1 Introduction

Imitation learning seeks policies that match experts from demonstrations without reward feedback, but the limits of supervised-learning reductions—especially for stochastic experts—remain unclear. The paper studies these limits in episodic tabular MDPs across no-interaction, active-query, and known-transition settings.

1 Introduction

  • Supervised-learning reductions can suffer from covariate shift and, for stochastic experts, action-count-dependent convergence under total variation; the paper asks what limits are inherent to imitation learning itself.The paper frames this question in tabular episodic MDPs with state space S, action space A, and episode length H.Source: §1 · p. 3, §1.1 · p. 5

1.1 Main results

  • Even with active expert queries and deterministic experts, some instance forces every learner to incur suboptimality at least |S|H^2/N.At states never visited during interaction, the learner lacks information about both expert actions and action-induced transitions.Source: §1.1 · p. 4
  • Behavior cloning has expected suboptimality at most |S|H^2/N for deterministic experts without interaction, and active expert queries do not improve worst-case minimax suboptimality.The proof bounds population 0-1 risk by |S|/N before applying the reduction to suboptimality.Source: §1.1 · p. 5
  • Mimic-Emp uses empirical risk minimization under log loss and has expected suboptimality independent of the number of actions, minimax optimal up to logarithmic factors for stochastic experts.For deterministic experts it also minimizes empirical 0-1 risk to zero.Source: §1.1 · p. 5
  • Mimic-MD combines exact expert imitation on states seen in demonstrations with a minimum-distance functional on remaining states, improving behavior cloning’s quadratic dependence on H.The method is presented for deterministic experts when transitions are known.Source: §1.1 · p. 6
  • In the known-transition setting, a universal lower bound of |S|H/N applies even when the expert is deterministic.The paper identifies closing the gap between this lower bound and the upper bound as an open question.Source: §1.1 · p. 7

2 Related Work

Related work spans fixed-demonstration learning, supervised-learning reductions, active interaction, and other approaches to imitation learning. The statistical limits of learning from state observations alone remain an open direction in the cited work.

2 Related Work

  • The classical imitation-learning literature studies learning from fixed expert demonstrations, while reduction-based work analyzes theoretical guarantees.The cited approaches include learning from demonstrations and reducing imitation learning to supervised learning.Source: §2 · p. 7
  • Active methods such as AggreVaTeD learn policies through interaction with both the environment and the expert; other work studies value functions, f-divergences, and representation learning.The cited representation-learning approach uses datasets from multiple agents to learn a common environment representation.Source: §2 · p. 7
  • The cited state-only observation approaches differ from this paper's focus on observable expert states and actions, and their statistical limits are left for future work.The passage names Nair et al. (2017), Torabi et al. (2018), Sun et al. (2019), and Arora et al. (2020) as examples.Source: §2 · p. 7

3 Preliminaries

The paper studies episodic imitation learning with hidden rewards, where expert demonstrations provide the learning signal. It considers learners with fixed demonstrations, known transitions, or active access to the MDP and expert.

3 Preliminaries

  • An episodic MDP has an initial-state distribution, state and action spaces, time-dependent transitions, and rewards accumulated over an episode of length H.The learner's value is expected cumulative reward, and suboptimality is the difference between expert and learner values.Source: §3 · p. 7
  • Rewards are unobserved during interaction, while demonstrations from the expert are available to learn a policy with comparable value.Interaction proceeds by choosing actions at visited states and receiving subsequent states from the MDP.Source: §3 · p. 8
  • The no-interaction setting gives N expert trajectories without further MDP access, whereas known-transition adds access to the transition functions and initial distribution.In the active setting, the learner interacts for N episodes and can query an oracle for the expert's action distribution at visited states.Source: §3 · p. 8

4 No-interaction setting

The no-interaction analysis covers deterministic and stochastic experts: behavior cloning generalizes through states absent from demonstrations, while the stochastic-expert reduction has a slow TV-risk rate. Mimic-Emp circumvents that reduction and achieves a 1/N suboptimality rate up to logarithmic factors.

4 No-interaction setting

  • Behavior cloning for a deterministic expert mimics expert actions on observed states, so its population 0-1 risk comes only from states absent at that time in the dataset.The expected unseen-state mass is bounded by |S|/N at each time; the reduction from population 0-1 risk to suboptimality then gives the expected guarantee.Source: §4 · pp. 8–9
  • For a deterministic expert, behavior cloning's expected population 0-1 risk is controlled by states not visited in the expert dataset.The theorem passage introduces the result, and its proof sketch attributes the risk to unseen states at each time step.Source: §4 · p. 9

4.1.1 Reduction of IL to supervised learning under TV distance

  • For stochastic experts, population TV risk at most ε implies suboptimality at most min{H, H^2 ε}, extending the supervised-learning reduction beyond deterministic experts.When the expert is deterministic, this TV-risk definition recovers the behavior-cloning reduction.Source: §4.1.1 · p. 10

4.1 Stochastic expert

  • The stochastic-expert section motivates bypassing TV-risk reduction because matching action distributions converges slowly, despite the reduction's suboptimality guarantee.The paper's alternative is Mimic-Emp, which uses the empirical expert policy where available and a uniform action distribution otherwise.Source: §4.1.1 · p. 10, §4.1.2 · pp. 10–11

4.1.1 Reduction of IL to supervised learning under TV distance

  • The stochastic-expert reduction is statistically costly: population TV risk converges at a rate ≳|A|/N even when |S|=1.In the same setting, the deterministic-expert population 0-1 risk converges at ≲1/N; the paper therefore describes the stochastic-expert reduction analysis as loose.Source: §4.1.1 · p. 10

4.1.2 Circumventing the reduction approach

  • Mimic-Emp achieves a 1/N expected-suboptimality rate up to logarithmic factors for stochastic experts, with guarantees optimal in their dependence on H.The coupling analysis bounds the chance of visiting an unobserved state by ≲|S|H log(N)/N; empirical action distributions across states are dependent through the dataset.Source: §4.1.2 · pp. 10–11

5 Known-transition setting

In the known-transition setting, Mimic-MD combines copying demonstrated expert actions with transition-model knowledge to handle states absent from demonstrations. Its guarantee relies on estimating how often a policy reaches such states, and the optimization can be solved approximately.

5 Known-transition setting

  • Mimic-MD matches the expert on demonstrated states and uses known transitions to choose behavior for states absent from the demonstrations.The learner splits the dataset into D1 and D2; D1 defines the states to mimic, while D2 supplies an empirical estimate used in the optimization.Source: §5 · p. 12
  • The learner can compute state-visitation probabilities for known policies, but not for the expert on states whose actions are unknown from D1.The algorithm uses the remaining trajectories in D2 to estimate the expert-related probability needed by the minimum-distance functional.Source: §5 · p. 12
  • Mimic-MD constrains its output to copy expert actions on demonstrated states, unlike conventional distribution matching, which may choose different actions there.The authors conjecture that conventional matching of states or state-action pairs does not achieve their rate because it lacks this constraint.Source: §5 · pp. 12–13
  • The optimization need not be exact: solving it to additive error ε still yields a suboptimality guarantee, and approximate transition functions are also addressed.The exact-optimization guarantee is recovered by taking ε = 0.Source: §5 · p. 13

6 Lower bounds

The lower bounds show that data limitations constrain imitation learning even with deterministic experts or active querying. In the known-transition setting, the construction gives a separate lower bound for any learner.

6 Lower bounds

  • In the no-interaction and active settings, a mistake can send the learner to an absorbing state, while the construction forces a mistake with probability at least on the order of |S|/N.The resulting loss is at least on the order of min{H, H^2ε} when the learner makes a mistake with probability ε.Source: §6 · p. 14
  • |S|H^2/N is the deterministic-expert lower-bound rate in the no-interaction setting, and the same lower bound applies when the learner can actively query the expert.Behavior cloning achieves the corresponding optimal expected suboptimality in the no-interaction setting for a deterministic expert.Source: §6 · p. 14
  • For a deterministic expert, behavior cloning is optimal in the no-interaction setting, and active querying does not improve its sample complexity.The paper also states that Mimic-Emp is optimal up to logarithmic factors in N in the no-interaction setting.Source: §6 · p. 14
  • The known-transition lower bound is min{H, |S|H/N} for some MDP with a deterministic expert, and it applies to any learner’s policy.The construction uses absorbing states: when the initial state is unobserved, the learner misses the only rewarding action there for the episode.Source: §6 · pp. 14–15

7 Conclusion

The conclusion summarizes guarantees for deterministic and stochastic experts and the known-transition setting. It also identifies unresolved gaps in the known-transition bounds and in extending the analysis beyond tabular settings.

7 Conclusion

  • For deterministic experts, behavior cloning is optimal without interaction; minimizing empirical log-loss is optimal up to logarithmic factors for stochastic experts.With known transitions, the paper proposes a policy that breaks the H^2 error-compounding barrier and matches a lower bound up to an H-factor.Source: §7 · p. 15
  • The known-transition upper and lower bounds still have a gap of at most a factor H, which the authors identify as an open question.The conclusion also asks how much finite interaction can improve on the no-interaction and exact-transition settings.Source: §7 · p. 15

A.1 No-interaction setting under deterministic expert policy

  • The deterministic-expert behavior-cloning guarantee is developed by bounding population 0-1 risk and applying a supervised-learning reduction.Source: §A.1 · p. 19

A.1.1 Analysis of expected suboptimality of behavior cloning

The appendix bounds behavior cloning’s risk through the probability mass of states missing from demonstrations, then uses that risk bound to obtain suboptimality guarantees. It also describes a missing-mass route to a high-probability result.

A.1.1 Analysis of expected suboptimality of behavior cloning

  • For a deterministic expert, behavior cloning’s population 0-1 risk comes from states not observed at the corresponding time in the expert dataset.The expected contribution is bounded on the order of |S|/N, after which a supervised-learning reduction gives an expected-suboptimality bound.Source: §A.1.1 · p. 19, Lemma A.1. E · p. 19

A.1.2 High probability bounds for behavior cloning

  • The high-probability analysis treats the risk contribution as missing mass under the time-averaged expert state distribution and applies concentration bounds for missing mass.The appendix states that this yields a high-probability bound on the learner’s suboptimality.Source: §A.1.2 · pp. 19–20

A.2 No-interaction setting when the expert policy is stochastic

  • The stochastic-expert subsection drops the deterministic-policy assumption and considers a general stochastic expert policy.Source: §A.2 · p. 20

A.2.1 Analyzing expected suboptimality of Mimic-Emp

The proof analyzes Mimic-Emp by comparing it with first-visit policies, then treats known-transition guarantees and lower-bound arguments. For Mimic-Emp, the analysis bounds the chance of reaching a state where the learner and an oracle policy differ.

A.2.1 Analyzing expected suboptimality of Mimic-Emp

  • The expected suboptimality analysis compares Mimic-Emp with a first-visit policy and an oracle version that uses expert actions at unseen states.The first-visit policy has the same expected value as Mimic-Emp; the oracle policy has the expert’s expected value, and disagreement matters on trajectories that visit unobserved states.Source: §A.2.1 · p. 21
  • In Lemma A.8, the expected probability of event E under πorc−first is upper bounded by |S|H ln(N)/N, and this bound completes the proof.Source: §A.2.1 · p. 23

A.3 Known-transition setting under deterministic expert policy

  • Mimic-MD’s proof bounds expected suboptimality by analyzing convergence of empirical estimates to their population quantities.The analysis splits into a fixed-dataset convergence bound and an expectation bound for the resulting dataset-dependent quantity.Source: §A.3 · pp. 24–25

A.4 Proof of lower bounds

  • The lower-bound proof section introduces arguments for no-interaction, active, and known-transition settings.The supplied passage identifies the scope of the proof section but does not state its bound.Source: §A.4 · p. 25

A.4.1 Active and no-interaction settings

The proof constructs MDPs with a deterministic expert whose correct actions yield reward while mistakes lead to a zero-reward bad state. In both active and no-interaction settings, the argument links unseen states to a lower bound on learner suboptimality.

A.4.1 Active and no-interaction settings

  • In the active setting, the learner may query the expert at visited states, but learns causally from its interaction history.The proof treats the no-interaction setting as a special case of active learning.Source: §A.4.1 · p. 25
  • The lower-bound construction samples a deterministic expert policy uniformly and makes the expert’s action at each non-b state the only rewarding action.The expert receives value H on its constructed MDP; any other action transitions to the absorbing bad state.Source: §A.4.1 · p. 26
  • The construction yields expected suboptimality at least on the order of min{H, |S|H^2/N} for active and no-interaction learning.A learner encounters states unseen in the expert data with probability at least on the order of |S|/N; a mistake leads to the bad state, which absorbs the learner without reward.Source: §A.4.1 · pp. 26–27

A.4.2 Known-transition setting

The known-transition lower-bound construction uses absorbing states and a shared transition model, so transition knowledge does not resolve uncertainty about the expert’s actions at unobserved states. The proof connects this uncertainty to missing initial-state mass.

A.4.2 Known-transition setting

  • The known-transition construction gives a lower bound of order |S|H/N on some learner’s expected suboptimality.Each state is absorbing, and at unobserved states the learner cannot reliably guess the expert’s rewarding action; the expected missing initial-state mass is at least on the order of |S|/N.Source: §A.4.2 · pp. 29–30

B.1.1 Proof of Lemma A.1

  • For N independent expert trajectories, a state’s probability of remaining unseen at time τ is (1 − Prπ∗[sτ = s])^N.The proof uses this unseen-state probability when analyzing missing mass.Source: §B.1.1 · p. 31

B.1.2 Proof of Theorem A.2

  • The proof invokes a concentration result for missing mass to establish a bound on deviations of unseen probability mass.The supplied passages identify the concentration theorem and state that its proof is completed, but do not give the bound’s full expression.Source: §B.1.2 · pp. 31–32

B.1.3 Proof of Lemma A.3

  • At each time τ, the weighted mass of states absent from the expert dataset is the missing mass of the state distribution induced by the expert.The proof applies the missing-mass concentration inequality to this quantity.Source: §B.1.3 · p. 32

B.2 Reduction of IL to supervised learning under TV distance (Lemma 4.3)

  • The TV-distance reduction proof compares policies that switch from expert to learner behavior at successive times.It uses bounded rewards and the dual representation of total variation distance to bound the change in expected reward.Source: §B.2 · p. 33

B.3.1 Proof of Lemma A.4

The proof shows that Mimic-Emp and a randomized policy extracting actions from the dataset have equal expected value. The accompanying oracle-policy proof evaluates trajectories under its fixed action table.

B.3.1 Proof of Lemma A.4

  • Mimic-Emp and Xunif have the same expected value, with Xunif extracting randomness from actions observed at visited states.At unvisited states, Xunif uses the uniform action distribution; at visited states, it samples from the empirical actions in the dataset.Source: §B.3.1 · p. 34
  • Conditioned on the preceding trajectory prefixes, actions observed at a visited state are independent draws from the expert’s policy.The proof uses this property to compare the empirical-action sampling of Xunif with the first-visit policy.Source: §B.3.1 · pp. 34–35

B.3.2 Proof of Lemma A.6

  • The oracle-policy proof fixes the expert table, computes trajectory probabilities, then sums rewards over trajectories.The passage describes the proof calculation but does not state its resulting value.Source: §B.3.2 · p. 36

B.3.3 Proof of Lemma A.8

These proof sections bound failures from states absent in the expert dataset and use those bounds to establish guarantees for imitation and active-learning settings. They also use sample splitting and concentration to control estimates.

B.3.3 Proof of Lemma A.8

  • The probability of an unvisited state at time t is bounded using the probability that expert trajectories missed it, yielding a log(N)/N term.The proof uses a union bound over states and times and the inequality min{x, (1 − x)^N} ≤ log N.Source: §B.3.3 · pp. 36–37

B.4.1 Proof of Lemma A.9

  • On trajectories that visit only dataset-observed states, the learner’s mimicking policy and the expert induce the same expectations.The proof conditions on the event that all visited states were observed in the dataset.Source: §B.4.1 · p. 37

B.4.2 Proof of Lemma A.10

  • The expert policy is feasible for the optimization problem, so an ε-approximate solution is compared against the expert through the objective.The proof then applies a triangle inequality to bound the discrepancy.Source: §B.4.2 · p. 38

B.4.3 Proof of Lemma A.11

  • Sample splitting makes the second dataset independent of the first conditional on the first, and the resulting quadratic deviation is bounded by ≲ 1 ∧ |S|H/|D1|.With |D1| = |D2| = N/2, this completes the stated proof bound.Source: §B.4.3 · pp. 38–39

B.4.4 Proof of Lemma A.12

  • A sub-Gaussian concentration bound is applied state by state and time by time, then combined by union bounds.The passages describe concentration conditional on D1 and a final union bound over two events.Source: §B.4.4 · pp. 40–41

B.5.1 Proof of Lemma A.14

  • For a deterministic expert, a policy disagreeing at a dataset-observed state has zero likelihood, while actions at unobserved states remain unconstrained by the data.The proof uses the uniform action distribution on unobserved states.Source: §B.5.1 · p. 41

B.5.2 Proof of Lemma A.15

  • In the lower-bound construction, reaching the absorbing state b ends reward collection, and reaching it requires an action other than the expert’s.The initial distribution assigns no mass to b.Source: §B.5.2 · pp. 41–42

B.5.3 Proof of Lemma A.16

These proof sections analyze failure in the lower-bound construction and derive related properties of deterministic policies and unseen states. They use the construction’s absorbing state and the initial-state distribution to establish the stated bounds.

B.5.3 Proof of Lemma A.16

  • The auxiliary bound γ ≳ |S|/N is combined with the recurrence argument to prove Lemma A.16.The initial distribution has no mass on b, so ρ(St(D) ∪ {b}) equals ρ(St(D) \ {b}).Source: §B.5.3 · pp. 42–43

B.6.1 Proof of Lemma A.18

  • For a deterministic expert, disagreement at a dataset-observed state gives a policy zero likelihood, while actions at unobserved states are uniform over A.The proof derives the result by the same argument as Lemma A.14.Source: §B.6.1 · p. 44

B.6.2 Proof of Lemma A.19

  • In the construction, each state is absorbing and reward is 1 exactly when the learner plays the expert’s action at that state.Conditioned on a state being unobserved, the expert’s action is uniformly sampled from A.Source: §B.6.2 · p. 44

B.6.3 Proof of Lemma A.20

  • Under the uniform prior over deterministic expert policies, the dataset retains initial states drawn from ρ, and the proof lower-bounds using |S| − 1 states.The proof substitutes this lower bound into the theorem’s bound.Source: §B.6.3 · p. 45
Loading 2009.05990v1…