On the Value of Interaction and Function Approximation in Imitation Learning

Abstract:
We study the statistical guarantees for the Imitation Learning (IL) problem in episodic MDPs. [22] show an information theoretic lower bound that in the worst case, a learner which can even actively query the expert policy suffers from a suboptimality growing quadratically in the length of the horizon, H . We study imitation learning under the μ-recoverability assumption of [27] which assumes that the difference in the Q-value under the expert policy across different actions in a state do not deviate beyond μ from the maximum. We show that the reduction proposed by [25] is statistically optimal: the resulting algorithm upon interacting with the MDP for N episodes results in a suboptimality bound of Õ (μ|S|H/N) which we show is optimal up to log-factors. In contrast, we show that any algorithm which does not interact with the MDP and uses an offline dataset of N expert trajectories must incur suboptimality growing as & |S|H/N even under the μrecoverability assumption. This establishes a clear and provable separation of the minimax rates between the active setting and the no-interaction setting. We also study IL with linear function approximation. When the expert plays actions according to a linear classifier of known state-action features, we use the reduction to multi-class classification to show that with high probability, the suboptimality of behavior cloning is Õ(dH/N) given N rollouts from the optimal policy. This is optimal up to log-factors but can be improved to Õ(dH/N) if we have a linear expert with parameter-sharing across time steps. In contrast, when the MDP transition structure is known to the learner such as in the case of simulators, we demonstrate fundamental differences compared to the tabular setting in terms of the performance of an optimal algorithm, MIMIC-MD (Rajaraman et al. [22]) when extended to the function approximation setting. Here, we introduce a new problem called confidence set linear classification, that can be used to construct sample-efficient IL algorithms.

heading: 1 Introduction
text: In many practical sequential decision making problems it is difficult to manually design reward functions that capture the essence of carrying out the task “nicely”. Furthermore, many modern-day
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
reinforcement learning tasks operate in very large state and action spaces - with sparse reward feedback it is difficult to train good agents without additional feedback or supervision. This motivates the setting of Imitation Learning (IL) where the learner operates in a setting of unknown or unreliable rewards, but with an expert that provides demonstrations as to how to carry out the task in the desirable way. The work of [21] first showed that using expert demonstrations can significantly improve performance in autonomous driving applications. Imitation Learning approaches have found remarkable success in practice over the last decade since expert demonstrations are often available abundantly such as in game AI [13, 1], as well as more recently in autonomous-driving applications such as [5, 20]. In this paper, we study IL in the episodic Markov Decision Process (MDP) formalism. Notation: An MDPM = (S,A, P, ρ, r), where S is the state space, A is the action space P is the MDP transition, ρ is initial state distribution and r is the reward function. The value Jr(π) of a policy π is defined as the expected cumulative reward accumulated over an episode of length H , Jr(π) = Eπ[ ∑H t=1 rt(st, at)], where the notation Eπ[·] denotes expectation with respect to a random trajectory {(s1, a1), · · · , (sH , aH)} obtained by rolling out the policy π = (π1, · · · , πH), where the initial state s1 is sampled independently from an initial state distribution ρ(·). Here πt denotes the policy at time step t. In the IL setting, we assume that the underlying reward function is unknown and unobserved. The reward function r = {r1, · · · , rH} is assumed to be time-variant and pointwise bounded in [0, 1], and the transition function P = (P1, · · · , PH−1) of the MDP is also assumed to be time-variant. The simplest IL setting is the no-interaction setting [22]. Definition 1 (IL in the no-interaction setting). The learner is provided an offline dataset D of N trajectories (without rewards) drawn by independently rolling out an (unknown) expert policy π∗ through the MDP. The learner is not allowed to interact with the MDP.
The learner’s objective in IL is to construct a policy π̂ with small suboptimality, defined as the difference in the expert’s and learner’s values: Jr(π∗)− Jr(π̂). In this paper we restrict the expert policy to be deterministic and define π∗t (s) as the action played by the expert at time t at state s. An IL instance refers to the tuple (M, π∗).The Q-function of a policy π is defined as the expected rewardto-go, Qπt (s, a) = Eπ[ ∑H t′=t rt′(st′ , at′)|st = s, at = a], and fπt (s) is defined as the distribution over states induced at time t, by rolling out the policy π.
Since the expert policy is a collection of actions played at different states visited by the expert, a natural approach to IL is to use any classification algorithm to learn a mapping from states to actions as the learner’s policy. This supervised learning approach has proved to be quite popular in practice and is known as behavior cloning (BC). [25] study BC from a theoretical point of view, and bound the suboptimality of a policy in terms of the 0-1 loss of the resulting classifier. More recently, in the tabular setting, [22] show that BC is statistically optimal in the no-interaction setting, achieving expected suboptimality . |S|H 2
N . This H 2 dependence is known as error-compounding and is shown
to be necessary even if expert is optimal or the learner can actively query the expert. Definition 2 (IL in the active setting). In this setting, the learner is not provided a dataset of expert demonstrations up front. The learner can instead interact with the MDP for N episodes. While interacting, the learner can query an oracle to return the expert’s action π∗t (s) at the current state s.
It begs the question as to why approaches such as DAGGER ([25]) and AGGREVATE ([26]) which actively query the expert often perform better than BC in practice and to explain this gap, additional assumptions must be imposed. To this end, we look at the minimax lower bound of [22] in the no-interaction setting. The key idea of the lower bound is to include an absorbing “bad” state in the MDP which is never visited in the expert dataset and offers no reward. Any policy which visits this state is doomed to incur a large suboptimality - in the absence of full information, the learner is forced to visit this often. The lower bound instance is pathological in the sense that even if the expert itself visits the bad state, it is never able to “recover” and return to the remaining states. Indeed in practical situations such as driving a car, experts often can recover and collect a high reward even if a mistake is made locally. [25] introduce an assumption to this effect, which we refer to as µ-recoverability. Definition 3 (µ-recoverability). An IL instance is said to satisfy µ-recoverability if for each t ∈ [H] and s ∈ S, Ea∼π∗t (·|s) [ Qπ ∗ t (s, a) ] −Qπ∗t (s, a) ≤ µ for all actions a ∈ A. Informally, if the expert plays an “incorrect” action at any state s at a single time t and goes back to choosing the correct actions afterwards, the expected reward collected is less by at most µ.
Under the µ-recoverability assumption, [25] show that a learner which minimizes the 0-1 loss under the learner’s own state distribution to admits a suboptimality upper bound of µH . However, it is
a-priori unclear how small can be made as a function of the number of the size of expert dataset / number of MDP interactions, N in the no-interaction / active settings. This is a drawback of the reduction approach followed by [25, 27] since it cannot distinguish the power of learners in different interaction models. In this paper, we propose an policy in the active setting with expected 0-1 loss under the learner’s own state distribution bounded by |S|/N . This “completes” the reduction in a sense, and establishes suboptimality bounds for the active setting as an explicit function of the number of states |S|, interactions N and horizon H . Informal Theorem 1 (Formal version: Theorem 1 and 2). In the active setting, under the µ-recoverability assumption, there exists a learner π̂ which incurs expected suboptimality E [J(π∗)− J(π̂)] . µH|S|/N . Furthermore, if N ≥ |S|H , for any learner π̂ in the active setting, there exists an MDP such that the expected suboptimality E [J(π∗)− J(π̂)] & µH|S|/N .
The key challenge for a learner to minimize the 0-1 under its own state distribution is that the learner’s policy changes over the course of optimization. Note however that it is possible to compute an unbiased estimate of the 0-1 loss under the learner’s own state distribution by rolling out just a single trajectory. Thus the active sampling model plays a crucial role in this regard. idea is crucial towards constructing the learner policy discussed in Informal Theorem 1. Under the same µ-recoverability assumption, we next consider learners in the no-interaction setting. In contrast to the active setting, we show that error compounding is unavoidable for no-interaction learners.
Informal Theorem 2 (Formal version: Theorem 3). In the no-interaction setting, for any learner π̂ there exists an IL instance which satisfies µ-recoverability for µ ≥ 1 such that the expected suboptimality is E [J(π∗)− J(π̂)] & H2|S|/N .
This is the first result to establish a clear separation in the statistical minimax rate of the suboptimality incurred by learners in the no-interaction setting such as BC, and learners which can interact with the MDP, such as DAGGER [27] and AGGRAVATE [26].
A common theme of the previous bounds in the tabular setting is that the suboptimality necessarily scales linearly in the number of states. In practical RL settings, state and actions spaces are often continuous, and thus additional assumptions are required to carry out efficient learning. In this paper, we study IL with function approximation, in particular in the linear-expert setting.
Definition 4 (Linear-expert setting). In this setting, for each (s, a, t) tuple, the learner is provided a feature representation φt(s, a) ∈ Rd. For each t ∈ [H] there exists an unknown vector θ∗t ∈ Rd such that ∀s ∈ S, π∗t (s) = arg maxa∈A〈θ∗, φt(s, a)〉. As we discuss in Remark 1, the linear-expert setting generalizes several known settings such as when the expert is an optimal policy under the linear-Q∗ assumption as well as the tabular setting with an optimal expert. We first establish a bound on the expected suboptimality incurred by BC.
Informal Theorem 3 (Formal version: Theorem 4). Under the linear-expert setting, the policy π̂ returned by BC incurs suboptimality J(π∗)− J(π̂) . (d+log(1/δ))H
2 log(N) N with probability ≥ 1− δ.
The presence of this error-compounding is not so surprising because the tabular setting with an optimal expert is a special case of the linear-expert setting where [22] show that error compounding is unavoidable for no-interaction learners. In order to break this H2-dependence, we introduce a natural variant of the linear-expert setting known as linear-expert setting with parameter sharing.
Definition 5 (Linear-expert with parameter sharing). This setting is the same as the linear-expert setting (Definition 4), with the added constraint that for all t, θ∗t = θ ∗ is shared across time.
Our main contribution is to show that in the linear-expert setting with parameter sharing, IL can be reduced to sequence multi-class linear classification where we learn linear classifiers from SH → AH . The supervised learning reduction of [25] posits to learn separate classifiers from S → A or S × [H]→ A: this fails to account for the shared parameter θ∗ across time. While in both cases the resulting policy is an ERM classifier, the suboptimality grows quadratically in H using the supervised learning reduction. In contrast, using the multi-class classification algorithm of [8], we also provide an algorithm π̂ with suboptimality growing linearly in H .
Informal Theorem 4 (Formal version: Theorem 5). Under the linear-expert setting with parameter sharing, there exists a learner π̂ with suboptimality J(π∗) − J(π̂) . (d+log(1/δ))H log(N)N with probability ≥ 1− δ.
With the additional linearity assumption on the expert, the learner can potentially infer the expert’s action on states that are not observed in the dataset. However in the absence of transition information or the parameter sharing assumption, a learner cannot even distinguish between different actions at the remaining states, which is what leads to catastrophic error compounding. To remedy this issue, we borrow from the work of [22, 23] who study IL in the known-transition setting in tabular MDPs where the learner exactly knows the Markov transition kernel and the initial state distribution of the MDP. The motivation for this setting stems from autonomous driving applications where policies are often learned in a simulated environment prior to fine-tuning in the real world [9, 35] and in the simulator the rewards functions are still difficult to specify. In such settings, the state and action spaces are indeed unbounded, which makes it ideal to study through the frame of function approximation.
Definition 6 (IL in the known-transition setting). The learner is provided an dataset D of N trajectories (without rewards) drawn by independently rolling out the expert policy π∗ through the MDP. The learner also knows the MDP transition P and initial state distribution ρ exactly.
In the tabular setting, the known transition setting has an interesting landscape: it is known from [22] that the quadratic-H barrier can be broken - the authors propose the MIMIC-MD algorithm which achieves an expected suboptimality upper bound of |S|H3/2/N and this dependence on the horizon is optimal [23]. The key idea is that with access to the MDP transition structure, as long as the visited states are conditioned to be observed in the dataset (so the expert’s action is known), the learner can simulate artificial trajectories according to the expert’s policy to generate more training data.
While the approach of simulating artificial trajectories in MIMIC-MD achieves the minimax optimal bounds here, a natural question to ask is whether the approach is tailored to work only in the tabular setting. Indeed in the presence of continuous state spaces, the learner may observe but a measure-0 subset of the state-space in the expert dataset. In spite of this, to apply the approach of simulating artificial trajectories, the learner must be able to infer the expert’s actions on a large fraction of the state-space. To this end, in the known-transition setting, we propose a problem known as confidence set linear classification which extends multi-class linear classification and we prove that algorithms with small expected loss for confidence set linear classification can be used to construct policies with small suboptimality, using the approach of simulating artificial trajectories. At a high level, the objective of the learner is to not only otput a classifier, but also a set of inputs (confidence set) where the classifier certifiably outputs the correct label.
Definition 7 (Confidence set linear classification). Consider a classification problem on X with input distribution ρX , output space Y , with features φ : X × Y → Rd and a dataset D of N examples drawn i.i.d. as xi ∼ ρX and yi ∼ h∗(xi), where h∗ is an unknown linear multi-class classifier mapping x 7→ arg maxy∈Y 〈θ∗, φ(x, y)〉. Given the dataset D, a confidence set linear classifier returns a tuple (ĥ,X ) where ĥ is any classifier from X → Y and X ⊆ X is a measurable set of inputs (known as the confidence set) such that ∀x ∈ X , ĥ(x) = h∗(x). The learner’s objective is to minimize the expected loss E [1− ρX(X )].
Sample-efficient confidence set linear classification algorithms can be used to construct learners with small suboptimality. We prove such a reduction in the linear-expert setting with linear rewards: here, in addition to the linear-expert setting, for each t ∈ [H], the reward function rt(·, ·) is also constrained to be a linear function of the feature representations φt(·, ·). The linear reward setting was considered previously in the known transition setting in [3]. We formally define it in Definition 8.
Informal Theorem 5 (Formal version: Theorem 6). Consider any algorithm Alg for confidence set linear classification and define RN,d(ρX , Y, ψ) as the expected loss (Definition 7) incurred by Alg when (i) the input distribution is ρX , (ii) features are ψ : X × Y → Rd and (iii) the learner is provided a dataset of N samples (with labels from an unknown multi-class linear classifier). In the linear-expert setting with linear rewards, there exists a learner policy π̂ with expected suboptimality:
E [J(π∗)− J(π̂)] . H3/2 √ d
N
∑H t=1 RN,d(f π∗ t ,A, φt)
H (1)
Informal Theorem 5 shows that it suffices to find good algorithms for confidence set linear classification and bound Rd,N (ρX , Y, φ) to carry out sample efficient IL. However, even in the case of binary output space Y = {0, 1} and uniformly distributed features, the answer to this question is quite challenging and admits a non-standard rate.
Informal Theorem 6 (Formal version: Theorem 7). Consider an instance of confidence set linear classification where Y = {0, 1}, ρX = Unif(Sd−1) and φ(x, 0) = −φ(x, 1) = x/2 ∈ Rd. Then, for sufficiently large N ,
(i) For any algorithm d 3/2 N √ log(d) . Rd,N,A(ρX , Y, φ).
(ii) There exists an algorithm such that Rd,N,A(ρX , Y, φ) . d3/2 log(d)
N .
This result shows that the minimax risk for confidence set linear classification necessarily grows as & d3/2/N . This rate establishes a fundamental difference between function approximation and tabular settings. In the tabular setting, where the features for each state-action pair are orthogonal, the learner cannot conclude the labels at unobserved states. Thus, the minimax risk of confidence set linear classification corresponds to the expected probability mass on unobserved states, which is also known as the missing mass [18]. It is known from [22, Lemma A.20] that the expected missing mass is . |S|/N ≡ d/N under any distribution over states and binary action space. Informal Theorem 6 establishes a fundamental difference between the tabular setting and the linear-expert setting with linear rewards, in terms of the suboptimality guarantees achieved by the approach of simulating artificial trajectories.
While the upper bound in Informal Theorem 6 (ii) only applies in the special case of binary classification with uniformly distributed features, we conjecture that the minimax expected loss for confidence set linear classification is d 3/2
N . If this conjecture is true, then Informal Theorem 6 shows that there exists a learner π̂ in the known-transition setting with linear-expert and linear rewards such that the expected suboptimality is . H3/2d5/4/N . For sufficiently large H , this improves the Θ̃(dH2/N) of BC and achieves the optimal dependence on the horizon [23].

heading: 1.1 Related Work
text: There is a long line of history studying the IL problem, [2, 34, 24, 37, 25, 10, 11, 19, 14]. A number of algorithms target the H2 error compounding issue, [12, 15, 17, 4, 36]. [25, 27, 4] study IL in the reduction framework, where they reduce the IL problem to a supervised learning problem and study the how the supervised learning error translates to the IL error. DAGGER [27], AGGREVATE [26], and AGGREVATED [30] learn policies by actively interacting with the environment and the expert during training. Going beyond the tabular setting, [3, 33] study IL in the presence of linear function approximation. [31] study IL in a setting where expert actions are not observed in the dataset. [6, 16] analyze DAGGER and dynamic regret under some regularity conditions, in comparison with the static regret reductions of [27], [7] propose a policy learning method called LOKI based on bootstrapping policy gradient methods using IL. [32] establish that many proposed algorithms for imitation learning indeed carry out some form of matching of distributions or features (namely, “moment matching” as studied in the paper). Our proposed algorithm for the linear-expert setting also lies in this framework.

heading: 2 IL with µ-recoverability
text: As defined in Definition 3, the µ-recoverability assumption captures the ability of an expert to recover and collect a high reward at a state even upon locally deviating from its action distribution at states. The reduction in [27, Theorem 2] shows that under µ-recoverability, a learner policy π̂ which minimizes the 0-1 loss with respect to the expert’s policy under the learner’s own state distribution,
L(f π̂, π̂, π∗) , 1 H ∑H t=1 Es∼f π̂t (·) [ Ea∼π̂t(·|s) [1(a 6= π ∗ t (s)] ] . (2)
to be less than , incurs suboptimality upper bounded by µH . However, in the active setting, it is a-priori unclear how small can be made as a function of the number of times the learner interacts with the MDP, N . We address this question in the following theorem. Theorem 1. In the active setting it is possible to construct a learner policy π̂ such that E [ L(f π̂, π̂, π∗) ] . |S|/N . Furthermore, under µ-recoverability, J(π∗)− E[J(π̂)] . µ|S|H/N .
Following the no-regret reduction of [27], it suffices for the learner to find a sequence of policies π̂1, · · · , π̂T such that the online-learning regret,
1
N ∑N i=1 L(f π̂ i , π̂i, π∗)−min π 1 N ∑N i=1 L(f π̂ i , π, π∗) . |S| N . (3)
Then, the mixture policy 1N ∑N i=1 π̂ i satisfies L ( f π̂, π̂, π∗ ) . |S|N . Note that in eq. (3), the ora-
cle loss minπ 1N ∑N i=1 L(f π̂ i
, π, π∗) is in fact 0, achieved by π = π∗. Suppose for each i, the learner rolls out a single trajectory according to π̂i. Denoting the empirical state-visitation distribution f̂π i = (f̂ π̂ i
1 , · · · , f̂ π̂ i H ), observe that, 1 N ∑N i=1 L(f̂ π̂ i
, π̂i, π∗) is an unbiased estimate of 1 N ∑N i=1 L(f π̂ i
, π̂i, π∗) if π̂i is a measurable function the first i− 1 rolled out trajectories (according to π̂1, · · · , π̂i−1). Thus, it suffices for the learner to find a sequence of policies π̂1, · · · , π̂T which minimize the empirical online-learning regret: 1N ∑N i=1 L(f̂ π̂ i , π̂i, π∗)−minπ 1N ∑N i=1 L(f̂ π̂ i , π, π∗) to be . |S|N . As we discuss in more detail in the Appendix, it is possible to construct a sequence of policies π̂1, · · · , π̂N using entropy-regularized mirror descent [29] which minimizes the empirical online-learning regret to be . |S|/N . The resulting policy π̂ = 1N ∑N i=1 π̂
i minimizes the expected 0-1 loss under its own state distribution to be . |S|/N in expectation. The guarantee on the expected suboptimality of this policy directly follows from [27, Theorem 2] under µ-recoverability.
This suboptimality guarantee is optimal for any learner in the active setting. The lower bound instance essentially follows from that of [22] for the active tabular setting where if N ≥ |S|H , the expected suboptimality incurred is & |S|H 2
N . By scaling each reward by a factor of µ/H , the same family of IL instances now satisfies µ-recoverability and results in the lower bound for active learners.
Theorem 2. In the active setting, if N ≥ |S|H , every learner π̂ incurs expected suboptimality E[J(π∗)− J(π̂)] & min{µ, µ|S|H/N}.
Now, under the same µ-recoverability assumption, we study learners in the no-interaction setting. We prove a lower bound that in the worst case, error compounding is unavoidable for such learners.
Theorem 3. For |S| ≥ 3 and |A| ≥ H , for any learner π̂, in the no-interaction setting, there exists an IL instance which satisfies µ-recoverability for µ ≥ 1 such that the expected suboptimality incurred by the learner is lower bounded, E [J(π∗)− J(π̂(D))] & min { H, |S|H2/N } .
The lower bound we consider is a modification of the lower bound of [22] where the MDP is constructed to have a “bad” state in the MDP never visited by the expert. We modify the instance to add a single “recovery” action at the bad state; the instance now satisfies µ-recoverability for any µ ≥ 1. If the number of actions are large |A| ≥ H , any no-interaction learner still fails to identify the recovery action with constant probability. In essence this reduces the instance to the lower bound of [22] and any no-interaction learner incurs an expected suboptimality & min{H, |S|H2/N}. The classical reduction formulations of [25, 27] prove upper bounds for IL based on minimizing a certain surrogate objective. However the statistical rate of minimizing different surrogate objectives as a function of the number of interactions (active setting) / size of the expert dataset (no-interaction setting) is unclear. As we show here, with µ-recoverability, the surrogate objective of 0-1 loss under the learner’s policy can be minimized to |S|/N in the active setting, but this is impossible in the no-interaction setting. Going beyond the reduction formulation, we thus distinguish between the statistical power of learners under different interaction models.

heading: 3 Linear function approximation in the no-interaction setting
text: In this section, we go beyond the tabular setting and study IL in the presence of function approximation. In practical settings, state and action spaces are often continuous or unbounded and carrying out efficient IL requires imposing additional assumptions. In this section we study the linear-expert setting (Definition 4) where S and A may be unbounded, but the learner is provided a set of feature representations of state-actions, and the expert policy is constrained to be realizable by a unknown linear (in the feature representations) classifier. The linear-expert setting generalizes several known settings as we discuss in the following remark.
Remark 1. The linear-expert setting (Definition 4) generalizes the linear-Q∗ setting with an optimal expert. Under this assumption, the optimal expert policy plays actions according to π∗t (s) = arg maxa∈AQ ∗ t (s, a) = arg maxa∈A〈θ∗t , φt(s, a)〉 for an unknown θ∗t ∈ Rd. Thus the expert policy is realizable by a linear multi-class classifier. Since the tabular setting is a special case of the linear-Q∗ setting with d = |S||A|, with features for each t chosen as the standard basis vectors in Rd, the linear-expert setting with d = |S||A| generalizes the tabular setting with an optimal expert.
In the tabular setting, it is known that the expected suboptimality of behavior cloning isO ( |S|H2/N ) in the worst case which is minimax optimal [22]. We first establish an upper bounds on the suboptimality incurred by BC in the linear-expert setting. Theorem 4. For t = 1, · · · , H , denote (D)t as a collection of N state-action pairs visited at time t across trajectories in D. Consider a learner policy which trains a policy π̂ using BC as follows: for each t = 1, · · · , H , the learner trains a linear multi-class classifier ĥt : S → A on the dataset (D)t using the algorithm of [8] and plays the policy π̂t(s) = ĥt(s). Then, in the linear-expert setting, with probability 1− δ, the suboptimality of π̂ is upper bounded by J(π∗)− J(π̂) . H
2(d+log(1/δ)) log(N) N .
This result is in fact a special case of Theorem 5 where we prove guarantees in the linear-expert setting with parameter sharing, where the expert plays according to the same linear classifier shared across the episode. In Remark 2, we show that the linear-expert setting with parameter sharing with dimension dH generalizes the linear-expert setting with dimension d. Remark 2. Linear-expert setting with dimension d is a special case of the linear-expert setting with parameter sharing, with dimension dH . Define θ∗ = (θ∗1 , · · · , θ∗H) ∈ RdH and φ′t(s, a) = (0d, · · · , φt(s, a), · · · , 0d) ∈ RdH where φt(s, a) is embedded in the coordinates td+ 1 to (t+ 1)d. Then, π∗t (s) = arg maxa∈A〈θ∗t , φt(s, a)〉 = arg maxa∈A〈θ∗, φ′t(s, a)〉, satisfying Definition 5.

heading: 3.1 Linear-expert with parameter sharing: Reducing IL to sequence classification
text: In this section, we demonstrate a reduction of IL to sequence multi-class linear classification from SH → AH , in contrast to BC which learns a classifier from S → A. First note that the expert’s policy can be thought of as a classifier from SH → AH : for each input sequence of states (s1, s2, · · · , sH) the expert “classifier” outputs the sequence of actions (π∗1(s1), π ∗ 2(s2), · · · , π∗H(sH)). The learner obtains N i.i.d. trajectories from the expert which are examples in the classification training dataset, and the objective is to predict actions for each new trajectory from the expert. Define Θ as the set of linear multi-class classifiers for sequences, of the form
SH 3 (s1, · · · , sH) 7→ arg max a1,··· ,aH∈A
〈 θ, ∑H
t=1 φt(st, at)
〉 ∈ AH . (4)
for θ ∈ Rd. Note that under the linear-expert assumption with parameter sharing, the expert’s policy can be identified as a classifier in the family described above. At each state s, the expert plays the action according to arg maxa∈A〈θ∗, φt(s, a)〉 at time t. Summing over any sequence of states s1, · · · , sH , the expert’s policy therefore satisfies (π∗1(s1), · · · , π∗H(sH)) = arg maxa1,··· ,aH 〈θ ∗, ∑H t=1 φt(st, at)〉.
Note that classifiers of the form eq. (4) indeed correspond to meaningful (Markovian) policies which drawn actions at from a policy which is a function of only the current state st. Indeed the map in eq. (4) is separable as ∑H t=1 arg maxat∈A〈θ, φt(st, at)〉 where we carry out the optimization for each variable a1, · · · , aH separately. By contradiction, the action played by the classifier at any state st at time t must be arg maxat∈A〈θ, φt(st, at)〉 which is Markovian. Finally, we prove a bound on the suboptimality of the policy induced by θ̂ by the expected 0-1 loss of θ̂. The intuition is that in any trajectory where the learner’s actions exactly match the expert’s actions, no suboptimality is incurred. In contrast, in any trajectory where the learner plays an action different from the expert at some time, the suboptimality incurred is ≤ H . Lemma 1. Consider any linear multi-class classifier θ̂ : SH → AH (in eq. (4)) with expected 0-1 loss, Eπ∗ [1(θ̂(s1, · · · , sH) 6= (a1, · · · , aH))] ≤ γ. Then, the policy π̂ corresponding to the linear classifier θ̂, satisfies J(π∗)− J(π̂) ≤ Hγ. Remark 3. The linear dependence on the horizon can be interpreted in a different way: with parameter sharing, the learner can aggregate information across time steps in an episode to learn a single linear classifier with improved guarantees. The amount of training data the learner has access to is effectively larger by a factor of H since each trajectory provides H samples of data for learning a single classifier common across time. The reduction analysis of [25] shows a suboptimality gap of H2 for learners with expected 0-1 loss under the expert state distribution upper bounded by . If data can be aggregated across time to learn a single parameter, the expected 0-1 loss can be brought down by a factor of H , showing that it is possible to achieve a suboptimality bound with linear dependence on the length of the horizon.
[8] provide a compression based algorithm for linear multi-class classification in the realizable setting. Indeed, invoking [8, Theorem 5], it is possible to learn a linear classifier θ̂ ∈ Θ such that the expected 0-1 loss of the classifier is upper bounded by (d+log(1/δ)) log(N)N given N expert trajectories. In conjunction with Lemma 1 this results in an upper bound on the suboptimality of the resulting policy.
Theorem 5. Consider a learner π̂ which trains a classifier θ̂ from the family in eq. (4) on the expert dataset using the compression based learner of [8], and at each time t and state s, π̂t(s) = arg maxa∈A〈θ̂, φt(s, a)〉. Under the linear-expert assumption with parameter sharing, with probability ≥ 1− δ, the suboptimality of the learner’s policy satisfies J(π∗)− J(π̂) . H(d+log(1/δ)) log(N)N .

heading: 4 Linear function approximation under known-transition assumption
text: The framework of [23] shows that IL under the known-transition setting can be reduced to the problem of uniform expert value estimation: the problem of estimating the value of the expert policy under all reward functions. The authors show that given a uniform expert value estimator J̃r(π∗), which with probability 1− δ (over the expert dataset and external randomness) for all reward functions r, satisfies |Jr(π∗)− J̃r(π∗)| ≤ , then the policy π̂ output by the following optimization problem,
π̂ ← arg min π max r J̃r(π)− Jr(π) (OPT)
incurs suboptimality J(π∗)− J(π̂) ≤ 2 with the same probability 1− δ. [23] also show that this objective is a convex program and can be efficiently solved approximately in the tabular setting.
In this context, to execute the approach of simulating artificial trajectories, observe that a learner can construct a good estimate of the expert’s value under some reward function r by decomposing it as the sum of two parts:
J1r (π ∗) = Eπ∗ [∑H t=1 rt(st, at)1(E) ] , and J2r (π ∗) = Eπ∗ [∑H t=1 rt(st, at)1(Ec) ] . (5)
where E is the event that the all the states (s1, · · · , sH) visited in the trajectory are observed in the expert dataset. The first term, J1r , can be estimated to an arbitrary level of accuracy for any reward function r by rolling out many artificial trajectories using π∗, known at all states observed in the dataset. The remaining term, J2r can be tackled using a simple empirical estimate, as explained below. The event Ec guarantees that states in a trajectory are visited are observed in the dataset D (where the expert’s policy is known). Therefore, by holding out some trajectories in the dataset, the learner may carry out an empirical estimate of J2r (π
∗) using these trajectories. The error in uniform value estimation precisely stems from the error incurred by the empirical estimate, which is shown to be O(|S|H3/2/N) in [22], translating to the suboptimality of the policy π̂ in (OPT). It is a natural question to ask whether this approach of simulating artificial trajectories can be applied when state and action spaces may be unbounded. To effectively use such an approach, the learner should be able to infer the expert’s action at a large fraction of states in spite of observing the expert’s actions only on a measure-0 subset of states. We show a that if the learner is able to identify the expert’s policy on a known large measure of states (under the expert’s state distribution), then the approach of simulating artificial trajectories can be employed to give a policy with small suboptimality. We establish such a reduction under the linear-expert setting with an additional assumption on the linearity of rewards which we introduce below. The linear reward setting was first introduced in [3] in the known-transition and discounted setting. Here, imposing the linear reward assumption enables the learner to construct linear estimates of the expert value function, which is otherwise not possible. Definition 8 (Linear reward assumption). DefineRlin as the family of reward functions which take the form of an unknown linear function of the known feature representation of states. Namely Rlin = {{rt(s, a) = 〈ωt, φt(s, a)〉 : t ∈ [H], s ∈ S, a ∈ A} : ∀t ∈ [H], ωt ∈ Rd, ‖ωt‖∞ ≤ 1}. The features are assumed to satisfy ‖φt(s, a)‖1 ≤ 1. The linear reward assumption assumes the true reward function of the MDP belongs toRlin. We propose an extension of MIMIC-MD to the linear-expert setting with linear rewards. The algorithm is based on identifying a set of states X1, · · · ,XH on which the expert’s policy is exactly known. The learner then constructs a uniform expert value estimator by simulating artificial trajectories using the expert policy conditioned on visiting only these states and uses an empirical estimate of the reward on the remaining states. The final policy is output using the minmax optimization problem in (OPT). A formal description is provided in Algorithm 1.
Algorithm 1 MIMIC-MD under linear-expert and linear rewards assumption 1: Input: A dataset D of N expert policy rollouts; MDP transition P ; feature representations {φt(s, a) : t ∈ [H], s ∈ S, a ∈ A}; confidence set linear classification algorithm Alg.
2: Pick a uniformly random permutation of the trajectories of D and assign the first N/2 as D0 and the remaining trajectories as D1. 3: For t = 1, · · · , H: define (ĥt,Xt(D0)) as the output of Alg((D0)t) . (D0)t are state-action pairs at time t across trajectories in D0. . ĥt is a classifier from S → A and can be identified as a policy. . Xt(D0) captures a set of states on which expert’s action is certifiably known. 4: Define event ED0 = {∀t ∈ [H], st ∈ Xt(D0)}: all states in a trajectory belong to {Xt(D0)}Ht=1. 5: Define the expert value estimator,
J̃r(π ∗) = Eπ∗ [∑H t=1 rt(st, at)1(ED0) ] + Etr∼Unif(D1) [∑H t=1 rt(st, at)1 ( EcD0 )] (6)
. The estimator is measurable: the first term can be estimated by rolling out many trajectories using the policy (ĥ1, · · · , ĥt), equal to (π∗1 , · · · , π∗H) under the measurable event ED0 6: Output: Return π̂ ← arg minπ maxr∈Rlin J̃r(π∗)− Jr(π). .Rlin is defined in Definition 8
Theorem 6. The expected suboptimality of the policy π̂ returned by Algorithm 1 under the linearexpert setting with linear rewards can be upper bounded by,
E [J(π∗)− J(π̂)] . H3/2 √ d
N
∑H t=1 E [Prπ∗ (st 6∈ Xt(D0))]
H (7)
Note that for each t = 1, · · · , H , the probability Prπ∗ (st 6∈ Xt(D0)) is the loss (as defined in Definition 7) of the confidence set linear classifier Alg((D0)t) in Algorithm 1.
As a consequence of Theorem 6, it suffices to upper bound the loss of the confidence set linear classification algorithm Alg. However, it is quite a challenging problem to compute the minimax risk for confidence set linear classification. Below, we discuss the case of binary classification.

heading: 4.1 Confidence set linear classification with binary outputs
text: In this section, we study confidence set linear classification when the output space Y = {0, 1} is binary. Denote the dataset D provided to the learner as {(x1, y1), · · · , (xn, yn)} where yi = 0 if 〈θ∗, φ(x, 0)〉 ≥ 〈θ∗, φ(x, 1)〉 and 1 otherwise for some unknown θ∗ ∈ Rd. For each sample xi observed in the dataset, the learner can conclude that 〈θ∗, φ(xi, 0)〉 − 〈θ∗, φ(xi, 1)〉 is non-negative if yi = 0 and is non-positive if yi = 1. In other words, for each xi, the learner can conclude that 〈θ∗, φ(x, y) − φ(x, 1 − y)〉 ≥ 0. Incorporating the information from all samples in the dataset, the learner can localize θ∗ to a cone Θ = { θ ∈ Rd : ∀(x, y) ∈ D, 〈θ, φ(x, y)− φ(x, 1− y)〉 ≥ 0 } . This cone captures the maximum amount of information the learner can discern about θ∗. Indeed, every linear classifier θ ∈ Θ correctly classifies every sample x observed in the dataset as the correct label 0 or 1 observed in the dataset. Given the cone Θ which captures the uncertainty in θ∗, one can construct a set of inputs C such that each classifier θ ∈ Θ is consistent with their labelling of inputs in C. We prove that largest such C can be directly constructed from the datasetD as C = K∪−K, where K is the conical hull of the set of points (φ(xi, 0)− φ(xi, 1)) (−1)yi for i = 1, · · · , n (Figure 1). Lemma 2. The set C ⊆ X as defined above satisfies the following two properties:
(i) For each x ∈ C, sign(〈θ, φ(x, 0)− φ(x, 1)〉) = sign(〈θ∗, φ(x, 0)− φ(x, 1)〉). (ii) For any x 6∈ C, any classifier ĥ, there exists θ ∈ Θ s.t. ĥ(x) 6= I(〈θ, φ(x, 0)−φ(x, 1)〉 < 0).
Therefore, the learner can guarantee that the label was correctly predicted for any x ∈ C. More importantly, Lemma 2 (ii) shows that for any classifier ĥ, C is indeed the largest set of inputs for which the learner can guarantee to correctly predict the same output as the true classifier θ∗. Thus, in the case of A = {0, 1}, E [ρX(Cc)] is the minimum expected loss of confidence set linear classification.
Next, we study the special case where the input space X is the unit sphere Sd−1, the distribution over inputs ρX is uniform over X , and the feature φ(x, 0) = −φ(x, 1) = x/2 ∈ Rd. Then
ρX(C) = 2ρX(K) is the same as probability that a randomly sampled point on the surface of a hemisphere lies in the conical hull of n points sampled uniformly on the surface of the hemisphere. Theorem 7. Recall that ρX is the uniform distribution over Sd−1. Then, for sufficiently large N ,
d3/2 N √ log(d) . E [ρX(Cc)] . d3/2 log(d) N . (8)
The proof of this result is fairly involved and we defer it to the Appendix. The key approach is to represent K in its dual representation and computing the probability in the dual space. The proof uses the Poissonization trick and a delicate covering argument to argue concentration in the absence of Lipschitzness. Tabular IL corresponds to the confidence set linear classification with orthogonal features. In particular, 〈θ, φ(x, 0)− φ(x, 1)〉 is known exactly for each x, and for each unobserved x nothing can be said about sign(〈θ, φ(x, 0)− φ(x, 1)〉). There, the minimax risk translates to the expected probability mass on unobserved inputs - the missing mass [18] which is in expectation . d/N [22], which is tight over the worst-case choice of distribution on inputs, ρX . The Ω̃(d3/2/N) rate in thus Theorem 7 establishes differences between the tabular setting and the linear-expert setting with linear rewards in the context of the approach of simulating artificial trajectories.

heading: 5 Conclusion
text: We study IL in the presence of µ-recoverability and under linear function approximation. In the former case, we establish a separation in the minimax expected suboptimality of learners in the no-interaction and active settings. We show upper bounds for BC under the linear expert setting and show that this quadratic dependence on H can be broken in the presence of parameter sharing. Finally, we study the known transition setting, and introduce a problem known as confidence set linear classification which extends the approach of simulating artificial trajectories to the function approximation setting.

heading: 6 Acknowledgments and Disclosure of Funding
text: Nived Rajaraman and Jiantao Jiao were partially supported by NSF Grants IIS-1901252, and CCF1909499. Part of the work was done while Lin F. Yang was visiting the Simons Institute for the Theory of Computing at UC Berkeley (the Theory of Reinforcement Learning Program). Jingbo Liu was partially supported by the starting grant from the Department of Statistics, University of Illinois. Kannan Ramchandran was supported in part by the Army Research Office (ARO) under fund 62448.

Review summaries:
The paper examines statistical guarantees of imitation learning under various regimes -- interactive setting, non-interactive setting, and non-interactive setting with known dynamics. It further looks at the linear setting and derives bounds for non-interactive settings with/without known dynamics. The main contributions are: 1. Interactive: To show that “reduction-based” online algorithms (DAGGER / AGGREVATE, DAEQUIL) have matching upper and lower bounds 2. Non-interactive: All such algorithms have O(H^2) bounds 3. Non-interactive + Linear + Parameter sharing: Recover O(H) bound 4. Non-interactive + Known dynamics + Linear: Introduces a new algorithm, confidence set linear classification, that achieves O(H^3/2)  

They study imitation learning in several variations, in particular with interaction (i.e., the expert can be queried during training) and without. And under some interesting additional assumptions, such as mu-recoverability (i.e., if the imitator visits suboptimal states, this has small impact of the overall value, by being able to go back to optimal easily).  They provide several theoretical results,  - negative ones -- i.e., lower bounds on the suboptimality that can be achieved in terms of difference of imitator versus optimal expert value incurred -- as well as  - positive ones -- algorithms that achieve linear instead of quadratic suboptimality, in particular their main contribution thm4. This works by reduction to supervised learning paradigm sample bounds.  As a means to this, they also have a little taxonomy on versions of IL.  One thing that's hard to judge for me is novelty. I feel this is novel, but I'm not sure how much overlap there is with DAgger and all the subsequent work in this direction, not an expert on this.

This paper investigates statistical guarantees for imitiation learning (IL) under the $\mu$-recoverability assumption of [27]. The authors prove  bounds on the sub-optimality of any algorithm which does not interact with the MDP and uses an offline dataset. Under linear function approximation, the authors prove bounds on the suboptimality of behaviour cloning.