On the Value of Interaction and Function Approximation in Imitation Learning
Authors: Nived Rajaraman
Yanjun Han
Lin Yang
Jingbo Liu
Jiantao Jiao
Kannan Ramchandran
Venue: NeurIPS 2021 Poster (2021)
Keywords: Reinforcement Learning
Imitation Learning
Minimax rates

Abstract: We study the statistical guarantees for the Imitation Learning (IL) problem in episodic MDPs.
Rajaraman et al. (2020) 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 $\mu$-recoverability assumption of Ross et al. (2011) which assumes that the difference in the $Q$-value under the expert policy across different actions in a state do not deviate beyond $\mu$ from the maximum. We show that the reduction proposed by Ross et al. (2010) is statistically optimal: the resulting algorithm upon interacting with the MDP for $N$ episodes results in a suboptimality bound of $\widetilde{\mathcal{O}} \left( \mu |\mathcal{S}| H / N \right)$ 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 $\gtrsim |\mathcal{S}| H^2/N$ even under the $\mu$-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  $\widetilde{O}(dH^2/N)$ given $N$ rollouts from the optimal policy. This is optimal up to log-factors but can be improved to $\widetilde{O}(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. (2020)) 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.

On the Value of Interaction and Function Approximation in Imitation Learning
Nived Rajaraman University of California, Berkeley waw...raaaaaaaabbbrllloooo edu
Yanjun Han University of California, Berkeley yjhan@berkeley. edu
Lin Yang
Jingbo Liu
University of California, Los Angeles linyang@ee. edu
University of Illinois, Jrbana-Champaigg jingbol@illinois. edu
Jiantao Jiao
Kannan Ramchandran University of California, Berkeley kannanr@eecs berkeley. edu
University of California, Berkeley j siantao@eess berkeley.en edd
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, 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 p-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 j 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 suboptimality bound of Ô (p|SH H//) 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 offline dataset of N expert trajectories must incur suboptimality growing as Z |S| /N even under the μ-- recoverability assumption. This establishes clear and provable separation of the minimax rates between the active setting and the no-interaction setting. We also study with linear function approximation. When the expert plays actions according to a linear classifier of known state-action features, we use the reduction multi-clan classification show that with high probability, the suboptimality behavior cloning is (dHH2 /) given rollouts from the optimal policy. This is optimal up to log-factors but can be improved to Odd 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 the tabular setting in terms the performance of an optimal algorithm, MIMIC-MD 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 II. algorithms.
Introduction
In many practical sequential decision making problems 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 (NcurIPS 2021).

---

reinforcement learning tasks operate in very large state and action spaces with sparse reward feedback is difficult to train good agents without additional feedback or supervision. This motivates the setting of Imitation Learning (II.) 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, IJ. as well as more recently in autonomous-drivigg applications such as [5, 20]. In this paper,
study IL in the episodic Markov Decision Process (MDP) formalism.
Notation: An MDP M = (S, A, P. p, r), where S is the state space, A is the action space P is the MDP transition, P is initial state distribution and is the reward function. The value Je Jz( of a policy π is defined as the expected cumulative reward accumulated over an episode of length H, Jr((T)) = 12 1= Tr(s), )t),, where the notation E, [-] denotes expectation with respect to random trajectory {(1)
(SH. aH)} obtained by rolling out the policy πT (ITI,-.. TH),, where the initial state $1 is sampled independently from an initial state distribution p(-). Here ne denotes the policy at time step f. In the IL. setting, we assume that the underlying reward function is unknown and unobserved. The reward function bounded in [0. 1], and the transition function P = (PI.... PH-1) ) of the MDP is also assumed to be time-variant The simplest IL setting is the no-interaction setting [22].
fri,- ,TH is assumed to be time-varian and pointwise
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 xt 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 is and learner's 's values: Jx(xx) (.)... In this paper we restrict the expert policy to be deterministic and define nī (s) as the action played by the expert at time t at state s. An IL instance refers to the tuple (M, x² ).The Q-function of policy is defined as the expected reward- to-go, QF (s, a) = Ex, -"=_re re (sy, ay [ss s, = a). and ff (s) is defined as the distribution over states induced at time ł, by rolling out the policy π.
Since the expert policy is collection of actions played at different states visited by the expert, natural approach to IL is to use any classification algorithm to learn a mapping from states to actions as the leamer's '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 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 x | This 112 dependence is known as error-compoudding and is shown to be necessary even if expert is optimal or the learner can actively query the expert.
N
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 's action कद (s) at the current state s.
It begs the question as to why approaches such as DAGGER ([25)) and AGGRE VATE ([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 j-recoverabillity
Definition 3 (p-recoverabilitty. An II. instance is said to satisfy p-recoverability for each l E [H] and s E S, (a [Q (s,a)] - -Qi (s, a) S p for all actions E A. Informally, if the expert plays an "incorrect" action at any state at a single time and goes back choosing the correct actions afterwards, the expected reward collected is less by at most p.
Under the p-recoverability assumption, [25] show that a learner which minimizes the 0-1 loss under the learner's 's own state distribution to admits a suboptimality upper bound of pHle. However, it is
2

---

a-prioni unclear how small e can be made as 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 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 and 2). In the active setting, under the u-recoverability assumption, there exists a learner ß which incurs expected suboptinality E [ - [R)] S. JHHSS Furthermore, i 2 |S] H. for any learner î in the active setting, there exists an MDP such that the expected suboptimality E [T [()] 2 JH|S.
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 crucial role in this regard. idea is crucial towards constructing the learner policy discussed in Informal Theorem 1. Under the same j-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 u-recoverability for p Z succ that the expected suboptimality is E [](²) - J [ Z H²|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 we study IL with function approximation, in particular in the linear-expert setting.
required to earry out efficient learning. In this paper,
Definition 4 dinear-expert setting). In this setting, for each (s, a, f) tuple, the learner is provided feature representation (s a) E Rd. For each t E [H] there exists an unknown vector 07 E such that Vs E S, x (s) = arg max,c.A (s)
As we discuss in Remark 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 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(T") ((x) (d+log(1/8)))7 log(N) with probability 2 1 - 8.
N
The presence of this cnoor-compuunding is not 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 H² -e-eedenneece,, we introduce 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 i, 0ī 0* 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 S" + " The supervised learning reduction of [25] posits to Iearn separate classifiers from A or S x [H] + A: this fails to account for the shared parameter 0* 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 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(x²) - ( S (d+ 1/8)) H log NN) with probability > 1 - 8.
N
3

---

With the additional linearity assumption on the expert, the learner can potentially infer the expert's 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 what leads to catastrophic emror compounding. To remedy this issue, we borrow from the work of [22, 23] who study IL in the known-transitin 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 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 x* through the MDP. The learner also knows the MDP transition P' and initial state distribution p 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 be observed in the dataset (so the expert's 's action is known), the learner can simulate artificial trajectories according to the expert's '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 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 nnown-transitio 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 (Confidence set linear elassification). Consider a classification problem on X with input distribution PX, outpul space Y, with feutures Φb X x Y + IR and dataset 'D of N examples drawn i..dd as Ts ~ px and ys ~ h-" (2,). where h is an unknown linear multi-class classifier mapping x + arg maxyey (10%,((a v)). Given the dataset D, a confidence set linear classifier returns tuple (h, X) where h is any classifier from X + Y and X S X is a measurable set of inputs (known as the confidence set) such that Vx E X. M(x) h² (x). The learner's objective is to minimize the expected loss E [1 - px (2))
Sample-efficient confidence set linear classification algorithms can be used to construct learners with small suboptimality. We prove such reduction in the linear-expert setting with linear rewards: here, in addition to the linear-expert setting, for each t E [H] the reward function re(:.-) is also constrained to be linear function of the feature representations dx(-.)). 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,a(px, v)) as the expected loss (Definition 7) incurred by Alg when (i) the input distribution is px, (ii) features are th X y Rd and (iū) 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 learner policy with expected suboptimality:
d D" N
RN A,, 0t) H
E
H8P2
Informal Theorem 5 shows that it suffices to find good algorithms for confidence set linear classi- fication and bound R. N (px, 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), Px Unif( 1) and Φ(x, 0) = 6(x, 1) = x/2 I. Then, for sufficientll large N,
(i) For any algorithm N /oggl)
S Ra,, 0).
(ii) There exists an algorithm such that Ra,N.A(xx. Y, 0) S / log(d)
This result shows that the minimax risk for confidence set linear classification necessarily grows as 2 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 S SI/N = d/N under any distribution over states and binary action space. Informal Theorem 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 classifica- tion with uniformly distributed features, we conjecture that the minimax expected loss for confidence
set linear classification is 2a/2 N. If this conjecture is true, then Informal Theorem 6 shows that there exists a learner fे in the known-transition setting with linear-expert and linear rewards such that the expected suboptimality is S //3/2/55/1// /N. For sufficiently large H, this improves the ((d ( of BC and achieves the optimal dependence on the horizon [23].
1.1 Related Work
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 H² 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 eтror translates to the IL error. DAGGER [27], AGGREVATE [26], and RGGREVATED [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 II. 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 the paper). Our proposed algorithm for the einear-expert setting also lies in this framework.
2 IL with ju-recoverability
As defined in Definition 3. the μ-recoverabillity assumption captures the ability of an expert to recover and collect a high reward at state even upon locally deviating from its action distribution at states. The reduction in [27, Theorem 2] shows that under y-recoverability, a learner policy स which minimizes the 0-1 loss with respect to the expert's policy under the learner's own state distribution,
c(F "))))))))
1
Σ"
H
E Ea [Eani(()) [1 + mT
H
1=
to be less than e, incurs suboptimality upper bounded by plle. 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 construct learner policy Ω such that E [A(S", r"] S |S//N. Furthermore, under p-recoverability, J(T") [ S//SH/N
Following the no-regret reduction of [27], suffices for the learner to find a sequence of policies #1 .....,, ST such that the miline-learnigg regret,
π. min N Σn L( प. ;T, S
S N
(3)
5

---

Then, the mixture policy N D Et satisfies L [( ((") x IS N. Note that in eq. (3), the ora- cle loss min, N -i= L(f n, x² is in fact O, achieved by क = =x Suppose for each i, the learner rolls out a single trajectory according to म'. Denoting the empirical state-visitation dis- JH observe that, N Σ L(f" 5t πT" is an unbiased estimate of N ii L(S" A = of is a measurable function the first - rolled out trajectories (according to ; Thus, it suffices for the learner to find sequence of policies 72, ,".... 5" which min- imize the empirical online-learning regret: N E L( ,², n²) min, N E== C(f" , I x") [S]
1
tribution for' (fi
(Ri)
E N
to be x N As we discuss in more detail in the Appendix, is possible to construct a sequence of policies 7., ,.,... ... -N using entropy-regularrzzed mirror descent [29] which minimizes the empirical lelinne regret to be & |S|/N. The resulting policy मे N == 0-1 loss under its own state distribution to be S |S|/N in expectation. The guarantee on the expected suboptimality of this policy directly follows from [27, Theorem 2] under j-recoverability.
N मt' minimizes the expected
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 2 |SH,, the expected
suboptimality incurred is 2 N |S By scaling each reward by a factor of μ H. the same family IL instances now satisfies jurecoverability and results in the lower bound for active learners.
Theorem 2. In the active setting. if N 2 |S| every learner incurs expected suboptimality [[J(T") - [(R) 2 min H|S J /.
Now, under the same j-recoverabilityy assumption, we study learners in the no-interaction setting. We prove a lower bound that the worst case, error compounding is unavoidable for such learners.
Theorem 3. For |S| 2 3 and |A| > H. for any learner T, in the no-interaction setting, there exists an IL instance which satisfies p-recoverabiiltyy for p. > 1 such that the expected suboptimality incurred by the learner is lower bounded, E [J(xx)) J ((+(D)) Z min {H, |S /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 the MDP never visited by the expert. We modify the instance to add single "recovery" action at the bad state; the instance now satisfies y-recoverability for any 1 2 1. the number of actions are large |A| 2 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 Z min H, S|H1//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 function of the number of interactions (active setting) / size of the expert dataset (no-interaction setting) is unclear. As we show here, with j-reeoverabillity 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.
Linear function approximation in the no-interaction setting
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 action, and the expert policy constrained be realizable by a unknown linear (in the feature representations) classifier. The linear-expert setting generalizes several known settings as we discuss 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 म (s) arg max A Qi (s, a) arg max és a)) for an unknown 87 E Rd. Thus the expert policy is realizable by a linear multi-clat claas classifier. Since the tabular setting is a special case of the linear-Q" setting with d = |S]| with features for each t chosen the standard basis vectors in Rd, the linear-expert setting with d = |S||AA| generalizes the tabular setting with optimal expert.

---

In the tabular setting, it is known that the expected suboptimality of behavior cloning is O (IS) in the worst case which minimax optimal [22]. We first establish an upper bounds on the subopti- mality incurred by BC in the linear-expert setting.
HN))
Theorem 4. For = 1. .... H, denote (D), 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 he S + A on the dataset (D), using the algorithm of [8] and plays the policy (s)ss) = (s)... Then, in the linear-expent setting, with probability 1 5, the suboptimality of is upper bounded by - x [[[d+ 1166 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-exper setting with parameter sharing with dimension dH generalizes the linear-expert setting with dimension d.
Remark 2. Lineur-expert setting with dimension d is special case of the linear-expert setting
with parameter sharing. with dimension dH. Define 8* = =(f (f ,88) E wall and (i(s, a) = (05: ....... (e((5, a)...................... 09) E TR.H where Φr(8,0) a) is embedded the coordinates td td+11 1 to (t + 1)d. Then, m3 (s) = arg aa (0i, (1(5, a)) = arg m (0", (0",, a.), satisfying Definition 5.
3.1 Linear-expert with parameter sharing: Reducing IL to sequence classification
In this section, we demonstrate a reduction of II. to sequence multi-class linear classification from SH + +,A in contrast to BC which learns a classifier from S + A. First note that the expert's 's policy can be thought of as a classifier from S - A"; for each input sequence of states (51, 82, .H)) the expert "classifier" outputs the sequence of actions (Tī (s1), = (s2)...... i 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 Q the set of linear multi- class classifiers for sequences, of the form
,,,""",H)) SH 3 (81, ... 8H) + arg max
(1) (0, ( .ar.
E AAA
(4)
for I Rd. Note that under the linear-expert assumption with parameter sharing, the ex- pert's policy can be identified as a classifier in the family described above. At each state 8, the expert plays the action according to arg max (8", óe(s, a)} at time t. Summing over any sequence of states 81, 8H, the expert's policy therefore satisfies (r((s1),..,,TT(((s)))))
arg a .a (0', Σ (st,, a:)).
Note that classifiers of the form eq. (4) indeed correspond to meaningful (Markovian) policies which drawn actions Oe from policy which is function of only the current state st. Indeed the map in eq. (4) is separable as Σ'= arg max,,e. (0, (r(st,,))) where we carry out the optimization for each variable a1, s, at time t must be arg m (0, (st,a,)) which is Markovian. Finally, we prove 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 '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.
ag separately. By contradiction, the action played by the classifier at any state
Lemma 1. Consider any linear multi-class classifier θ: SH + AH (in eq. (4)) with expected 0-1 loss, E,r (1((1)) .HH) # (a1. .ax))) sn Then, the policy से corresponding to the linear - classifier 0, satisfies J(m")- J(T) < H--
Remark 3. The linear dependence on the horizon can be interpreted in 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 H²e for learners with expected 0-1 loss under the expert state distribution upper bounded by If data can be aggregated ucross time to learn a single parameter, the expected 0-1 loss can be brought down by a factor of H, showing that is possible to achieve a suboptimality bound with linear dependence the length of the horizon.
7

---

[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 linear classifier 0 E & such that the expected 0-1 loss of the classifier is upper bounded by [d+log(]/8 (51) log(N) given N expert trajectories. In conjunction with Lemma 1 this results in an upper bound on the suboptimality of the resulting policy.
N
Theorem 5. Consider a learner ā which trains classifier 0 from the family in eq. (4) the expert dataset using the compression based learner of [8], and at each time t and state 8, (e(s)= = arg max (0, (e(s, a)). Under the linear-experl assumption with parameter sharing, with probabil- ity 2 8, the suboptimality of the learner's policy satisfies J(x²) ((=")-J(3) J( x H(d+log(1/ (8)) log(N)
Linear function approximation under known-transition assumption
The framework of [23] shows that IL under the known-transition setting can be reduced 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 Jr(xx), ") which with probability 1 (over the expert dataset and external randomness) for all reward functions r, satisfies [==(=*) - -r(( S e, then the policy मे output by the following optimization problem, (OPT)
मे f arg arg min max (T) (T(
incurs suboptimality J(T²) ( < 2e with the same probability 1 1 8. [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 by decomposing it as the sum of two parts:
H f=(=²) = E.. Σ _ re(Se, re(()) (E)) ) and F²(TT) = Ex- [>' ri ax)1(E))
(5) where E is the event that the all the states ($1,..., $H) visited in the trajectory are observed in the expert dataset. The first term, Jph can be estimated to an arbitrary level of accuracy for any reward function r by rolling out many artificial trajectories using n², known at all states observed in the dataset. The remaining term, J2 can be tackled using a simple empirical estimate, explained below. The event E 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 J²(TT) 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(SS) ((55)/3// /N) in [22], translating the suboptimality of the policy स in (OPT).
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 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 s actions only on measure-0 subset of states. We show a that if the learner is able to identify the expert's 's policy on a known large measure of states (under the expert's s state distribution), then the approach of simulating artificial trajectories can be employed to give 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] and discounted setting. Here, imposing the linear reward assumption enables
in the the learner to construct linear estimates of the expert value function, which is otherwise not possible.
Definition 8 (Linear reward assumption). Define Rinn as the family of reward functions which take the form of an unknown linear function of the known feature representation of states. Namely Rim = (rre(, a) (we, de a)) :1 E [H, E S, a E A} VL E [H], Wt E IR ||walll S 1}. The features are assumed to satisfy [ (s,aa)ll S 1. The linear reward assumption assumes the true reward function of the MDP belongs to Run.
We propose an extension of MIMIC-MDD to the linear- enpert- setting with linear rewards. The algorithm is based on identifying set of states X2. : Xx on which the expert's '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 output using the minmax optimization problem in (OPT). A formal description is provided in Algorithm I.
8

---

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
(ōr(s, [H. E S, a E A); confidence set linear classification algorithm Alg.
2: Pick uniformly random permutation of the trajectories of D and assign the first N/2 as Do and the remaining trajectories as D,.
3:
For L= 1, ... H: define (he, (Do)) as the output of Alg((
Do): are state-action pairs time across trajectories in Dp.
h2 is a classifier from S - A and can be identified as a policy.
X2 (D)) captures set of states on which expert's s action is certifiably known.
4: Define event &D = (4l E [H], 8, E (Do)): all states in trajectory belong to {2
5: Define the expert value estimator,
Hf Σn (e) + (nr-Ui)((D))
Hf Σn rr((t, (s)1 (EB.)
J+(mT) Exx
(6)
The estimator is measurable: the first term can be estimated by rolling out many trajectories using the policy (ha,... hh)) equal to (mi,,.. ; ,HH under the measurable event ED,
6: Output: Return t arg min, maxreRm. Je(TT) - JT(T). > Riin is defined in Definition
Theorem 6.
The expected suboptinality of the policy गे returned by Algorithm I under the linear- expert setting with linear rewards can be upper bounded by,
d
H E (Pra- (sc & Xe(Do) E
H
Note that for each I. = 11,..., H, the probability Pra- (st & (D)) is the loss (as defined in Definition 7) of the confidence set linear classifier Alg((Do)s 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 challenging problem to compute the minimax risk for confidence set linear classification. Below, we discuss the case of binary classification.
4.1 Confidence set linear classification with binary outputs
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 (1)1 ... (Ii, Un)] where yi if (0", ((r, 0)) (0", 6xx,, 1)) and 1 otherwise for some unknown 0* Rdd. For each sample i. observed in the dataset, the learner can conclude that (0" d(x;, 0)) - (8", ((2;, 1)) is non-negative In other words, for each 24 the learner
conclude that 10", (0x y) - Φ(x, 1 y)) 2 0. Incorporating the information from all samples in the dataset, the learner can localize 6" to a cone θ {o E Rd V(z, y) E D, (0, Φ( y) Φ(x, 1-))) 2 0}. This cone captures the maximum amount of information the learner
if y4 and is non-positive if y;
discern about 0". Indeed, every linear classifier f e θ correctly classifies every sample x observed in the dataset as the correct label O or 1 observed in the dataset. Given the cone @ which captures the uncertainty in 0" one can construct set of inputs C such that each classifier 0 E θ is consistent with their labelling of inputs in C. We prove that largest such C can be directly constructed from the dataset D as C K. -XC, where K. is the conical hull of the set of points (Ø(x,, 0) o(2,, 1)) (-1)%k for i 1,... (Figure 1), Lemma 2. The set C C X as defined above satisfies the following two properties:
(i) For each & E C, sign( (0, (xx, 0) o(x 1))) sign( (0", ((x, 0) (xx
(ii) For any & C, any classifier h, there exists 0 θ s.I. h((x)) +
p(x ( 1)) 0).
Therefore, the learner can guarantee that the label was correctly predicted for any x E 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 correctly predict the same output the true classifier 0* Thus, in the case of A = (0, 1}. E [xx (C") is the minimum expected loss of confidence set linear classification.
Next, we study the special case where the input space X the unit sphere $d-1, the distribution over inputs px is uniform over X, and the feature ő(z, 0) -6(2, 1) = z/2 e Rd. Then

---

6
V
V
AC
-K
Figure {-1, NN is the set of points observed in the dataset. For each x ga-1, y 11))(((((, 6(z, 1)). The gray region, IC is the conical hull of {V MaNt.
(C) 2px (KC) is the same probability that a randomly sampled point on the surface of hemisphere lies in the conical hull of n points sampled uniformly on the surface of the hemisphere.
Theorem Recall that Px the uniform distribution over Sd-1, Then, for sufficiently large N,
1/2
d/22
S Epx((())
(8)
N /lg((d))
N
The proof of this result is fairly involved and we defer it to the Appendix. The key approach is to represent IC in its dual representation and computing the probability in the dual space. The proof uses the Poissonization trick and delicate covering argument to argue concentration in the absence of Lipschitzness. Tabular corresponds to the confidence set linear classification with orthogonal features. In particular, (0, 6(x, 0) o(x, 1)} is known exactly for each and for each unobserved x nothing can be said about sign (0, o(x 0) - (xx 1))). There, the minimax risk translates to the expected probability mass unobserved inputs the missing mass [18] which is in expectation inputs, Px- The (dd3/2 /N)
S d/N [22], which is tight 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.
the worst-case choice of distribution
5 Conclusion
We study IL in the presence of j-recoverabillty 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, study the known transition setting, and introduce problem known confidence set linear classification which extends the approach of simulating artificial trajectories to the function approximation setting.
6 Acknowledgments and Disclosure of Funding
Nived Rajaraman and Jiantao Jiao partially supported by NSF Grants 1901220, and CCF- 1909499. 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.
10

---

References
[1] Grandmaster level in StarCraft II using multi multi-agent reinforcement learning. Nature, 575(7782)3350-
354, 2019. ISSN 1476-4687. doi: 10. 1038//445566-019-111 1724-z. URL, http:p:://do.oor////// 1038/
141586-019-1724--
[2] Pieter Abbeel and Andrew Y. Ng. Apprenticehhip learning via inverse reinforcement learning. In Proceedings of the Twenty-Fire International Conference on Machine Learning, ICML '04, page 1, New York, NY, USA, 2004, Association for Computing Machinery. ISBN 1581138385. doi: 10.1 10.1145/1015330.
1015430. URL https: //dp::///o..../ org/ 10. 1ee1111111110000 101533010000 1015330.101110000. 1015430.
[3] Pieter Abheel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In Procedd- ings of the twenty-first international conference on Machine learning, page 1, 2004.
[4] Kiante Brantley, Wen Sun, and Mikael Henaff. Disagreement-regulliiieee imitation learning. In Interna- tional Conference on Learning Representations, 2020. URL htttp::///ottt http://///ppeeeeeeeeeeeeeee wwt.eviwwweeeeeeeeeeeeeeeeeeeeee net/forummid=
rkgbYyHtwB.
[5] Jianyu Chen, Bodi Yuan, and Masayoshi Tomizuka. Deep imitation learning for autonomous driving in generic urhan scenarios with enhanced safety. CoRR, abs/1193.000640 2019. abs/1903. 00640.
org/
[6] Ching-An Cheng and Byron Boots. Convergence of value aggregation for imitation learning, 2018.
[7] Ching-An An Cheng, Xinyan Yan, Nolan Wagener, and Byron Boots. Fast policy learning through imitation and reinforcement, 2018.
[8] Amit Daniely and S. Shalev-Shwartz. Optimal learners for multiclass problems. In COLT, 2014.
[9] Alexey Dosovitskiy, German Ros, Felipe Codevilla, Antonio Lopez, and Vladlen Koltun. CARLA: An open urban driving simulator. In Sergey Levine, Vincent Vanhoucke, and Ken Goldberg, editors, Proceedings of the Ist Annual Conference on Robot Learning, volume 78 of Proceedings of Machine mlr prrss/ss//
Learning Research, pages 1-16. PMLR, 13-15 Nov 2017. URL http::/ppoceediiee v78 v/8/dosovitskiyl11 htm...
html.
[10] Chelsea Finn, Sergey Levine, and Picter Abbeel. Guided cost learning: Deep inverse optimal control via policy optimization. In International conference on machine learning, pages 49-58, 2016.
[11] Justin Fu, Katie Luo, and Sergey Levine. Learning robust rewards with adversarial inverse reinforcement learning. arXiv preprint arXiv: 1710. 1248, 2017.
[12] Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in neural information processing systems, pages 3565-4573. 2016.
[13] Borja Ibarz, Jan Leike, Tobias Pohlen, Geoffrey Irving, Shane Legg, and Dario Amodei. Reward leam- ing from human preferences and demonstrations in atari. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 801 1-0233 Curran Associates, Inc., 2018. URL http: /ttpp//aapppaaaeeee/eeeeeeeaee.t paaapers.ipps. cttpppprccccp//////ppppppppeeeee 6025-reward- learning- from human preferences-- and www.dddntnnniiin.nm. in-atrri -pdf.
[14] Liyiming Ke, Matt Barnes, Wen Sun, Gilwoo Lee, Sanjiban Choudhury, and Siddhartha Srinivasa. Imitation learning f-divergence minimization. arXiv preprint arXiv: /2888, 2019.
[15] Michael Laskey, Jonathan Lee, Roy Fox, Anca Dragan, and Ken Goldberg. Dart: Noise injection for robust imitation learning. In Conference on robot learning, pages 143-156. PMLR, 2017.
[16] Jonathan N Lee. Michael Laskey, Ajay Kumar Tanwani, Anil Aswani, and Ken Goldberg. A dynamic regret analysis and adaptive regularization algorithm for on-policy robot imitation learning. In International Workshop on the Algorithmic Foundations of Robotics, pages 212-227. Springer, 2018.
[17] Yuping Luo, Huazhe Xu, and Tengyu Ma. Learning self-correetable policies and value functions from demonstrations with negative sampling. In International Conference Learning Representations, 2020. URL //tttpss://pprreeeeee eeweereieee.e net/ form/ wwwddikeefffee... f6NKvS.
[18] David Mcallester, Luis Ortiz, Ralf Herbrich, and Thore Graepel. Concentration inequalities for the missing mass and for histogram rule error. In Journal of Machine Learning Research, pages 895-911. 2003.
[19] Yunpeng Pan, Ching-An Cheng, Kamil Saigol, Keuntack Lee, Xinyan Yan, Evangelos Theodorou, and Byron Boots. Agile autonomous driving using end-to-end deep imitation learning. arXiv preprint arXiv: 170..07174 2017.
[20] Yunpeng Pan, Ching-An An Cheng. Kamil Saigol, Keuntaek Lee, Xinyan Yan, Evangelos A Theodorou, and Byron Boots. Imitation learning for agile autonomous driving. The International Journal of Robotics Research, 39(2-))286-3000 2020. 0278364919880273.
doi: 10.1 00.1177/0273364499880077 URL https://doo org/10. 1177/

---

[21] Dean A. Pomerleau. Alvinn: An autonomous land vehicle in a neural network. In D. S. Touretzky, editor, Advances in Neural Information Processing Systems 1. pages 305-313. 95-alvinn- an a---auuoooouus--- land
URL http://papers nips. cc/pperr/ land-vehicle- vehicle- aata--nuual--ttttoe
1989.
[22] Nived Rajaraman, Lin F. Yang. Jiantao Jiao, and Kannan Ramachandran. Toward the fundamental limits of imitation learning. Advances Neural Information Processing Systems, 2020.
[23] Nived Rajaraman, Yanjun Han, Lin F. Yang, Kannan Ramchandran, and Jiantao Jiao. Provably breaking the quadratic error compounding barrier in imitation learning, optimally, 2021.
[24] Nathan D Ratliff, J Andrew Bagnell, and Martin A Zinkevich. Maximum margin planning. In Proceedings of the 23rd international conference on Machine learning, pages 729-736, 2006.
[25] Stephane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Yee Whye Teh and Mike Titterington, editors, Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine I learning Research, pages 661-668, Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010. PMLR. URL http:::/ppcceeeingg.. mlr wwwppeeeseeeeeeeeee https/////rrsss// html.
[26]
Stéphane Ross and J. Andrew Bagnell. Reinforcement and imitation learning via interactive no-regret learning. ArXiv, abs/1406.5997 2014.
[27] Stéphane Ross. Geoffrey Gordon, and Drew Bagnell, reduction of imitation learning and structured prediction to no-regret online learning. Geoffrey Gordon, David B. Dunson, and Miroslav Dudík, editors, AISTATS, volume 15 of JMLR Proceedings, pages 627-635. JMLR.org, 2011. URL http:
//dblp.ume ani-trier... de/db/ /bwjj/urreee journals/jjaaa jmlr/jmlrp1s html @ttm##RossCB11.
[28] Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 4(2):107-194, 2012. ISSN 1935-8237. doi: 10. 10.1561/220000001.. URL http:
/ /xx doi.oii.ooooo www.doooo.....ooooooo wtt..oor//....11220000000
[29] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algoritiuns. Cambridge University Press, USA, 2014. ISBN 1107057132.
[30] Wen Sun, Arun Venkatraman, Geoffrey J Gordon, Byron Boots, and J Andrew Bagnell. Deeply aggrevated: Differentiable imitation learning for sequential prediction. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 3309-3318. JMLR. org, 2017.
[31] Wen Sun, Anirudh Vemula, Byron Boots, and Drew Bagnell. Provably efficient imitation learning from observation alone. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings the 36th International Conference on Machine Learning, volume 97 Proceedings of Machine Learning Research, pages 6036-6606600006 6045, Long Beach, California, USA, 09 15 Jun 2019. PMLR. URL htttp://ppoceedingg mlr. www.eeeeeeeeeee vv7 sunn9b..... html.
the
[32] Gokul Swamy, Sanjiban Choudhury, Andrew Bagnell, and Steven Wu. Of moments and matching: A game-theoretic framework for closing the imitation gap. Marina Mcila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Muchine Learning Research, pages 10022-10032. PMLR, 18-24 Jul 2021. URL https://tppett //ppcc/e/ccoc........mm
mlr. preas/ preas/v139/ vv39// v139/swamy222 wwwswwaaslll html.
[33] Umar Syed and Robert E Schapire. A game-the approach to apprenticeship learning. In J. C. Platt. D. Koller, Y. Singer, and S. T. Roweis, editors, Advances in Neural Information Processing Sys- tems 20, pages 1456. Curran Associates, Inc., 2008. URL http://papers. mips. cc/ cc/paper/ 3293 a-----gaaan -a---ame--e thwoottii- approocchpppppcc----acccc taaeeaachhht--ppppee totaapppentiieesiiieeeeeeeeeeeee 1eailp-eeaannnnn.... pdf.
[34] Umar Syed, Michael Bowling, and Robert E Schapire. Apprenticeship learning using lincar programming. In Proceedings of the 25th international conference on Machine learning, pages
2008.
[35] Yurong You, Xinlei Pan, Ziyan Wang, and Cewu Lu. Virtual to real reinforcement learning for autonomous driving. CoRR, abs// 704.03952, 2017. URL http: : htt////axvvvv.e org/ wwg/abs/////aaeetooooo..o htsp//bb/1704./.. 017./404444..22...
[36] Yufeng Zhang, Qi Cai, Zhuoran Yang. and Zhaoran Wang. Generative adversarial imitation learning with neural networks: Global optimality and convergence rate. arXiv preprint arXiv:2003.037009 2020.
[37] Brian D Ziebart, Andrew L Maas, J Andrew Bagnell, and Anind K Dey. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pages 1433-1438. Chicago, IL, USA, 2008
12


Reviews:
[{"review_id": "vF02vGnnRCF", "reviewer": "Reviewer_A7G7", "summary": "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).\n\nThey provide several theoretical results, \n- 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 \n- 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.\n\nAs a means to this, they also have a little taxonomy on versions of IL.\n\nOne 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall this is an interesting paper, addressing common IL settings, providing non-trivial theoretical contributions. \n\nThe reduction-based approach to thm4 looks powerful (though reduction, I guess, are not new for this but originate from DAgger etc.). \n\nThe little IL taxonomy (Def1, 2, ...) is interesting in itself.\n\nSome of the proofs look non-trivial.\n\nQuality-wise, I have not checked details, but the theorems and proofs seem to be stated with care.\n\nStyle of writing is OK-good.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Small limitations include:\n- I'm surprised that one of the most common settings -- no interaction, but being able to sample from the dynamics -- is not discussed. However, I guess Def6 is a close enough approximation to this for the sake of this paper.\n- How limiting is the linear expert setting? Linear would be pretty limiting, but I guess it's only linear in the features which would be quite general again.\n- There are no experiments but that's OK given there is enough conceptual and theoretical contribution.\n- I have not read the full paper. Some writing may be premature -- e.g. l98 \"regard. idea is crucial\" -- but this seems neglectable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "ff-nKEh6V-c", "reviewer": "Reviewer_wRYy", "summary": " The authors study statistical guarantees for the Imitation Learning problem, for many settings: considering or not the possibility of interacting with the environment, using the \\mu-recoverability assumption, and assuming linear function approximation. Furthermore, they introduce a new setting, called confidence set linear classification.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Originality: \nThe main novelty consists in the analysis proposed by the authors, which allows to determine theoretical properties, improving some pre-existent results. Moreover, they introduce and study a new setting.\n\n## Quality:\nThe applied methodology seems to be sound, and the work is complete, analysing a spectrum of interesting cases.\n\n## Clarity: \nWhile the paper is clearly well written, the structure of the whole work can be improved. The authors tried to summarize in the introduction the main results provided, by means of informal theorems and definitions. I would suggest to keep a more traditional informal introduction, in which formulas and statement are few, and the main ideas are explained by words. Consequently, I would suggest to add a preliminaries section, where both the notation part and the definition could fit more.\n\n## Significance:\nThe work offers important statistical guarantees for different settings, advancing the state of the art. The obtained results are likely to be useful for other researchers to build on them.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No potential negative impact is present.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "R2aLoRDf13R", "reviewer": "Reviewer_VnQb", "summary": "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:\n1. Interactive: To show that “reduction-based” online algorithms (DAGGER / AGGREVATE, DAEQUIL) have matching upper and lower bounds\n2. Non-interactive: All such algorithms have O(H^2) bounds\n3. Non-interactive + Linear + Parameter sharing: Recover O(H) bound\n4. Non-interactive + Known dynamics + Linear: Introduces a new algorithm, confidence set linear classification, that achieves O(H^3/2) \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper addresses an important, yet under examined, problem -- what is the best one can expect from any imitation learning algorithm under various settings? The contributions in examining the linear setting are particularly important, one hopes functional analysis (RKHS) soon follows. \n\nI very much enjoyed reading the paper. It made central ideas accessible to the reader. I much appreciated the effort put in the introduction to give the reader a broad view of the key results. \n\nThe two main strengths of the paper are:\n1. Technically sound [4/5]: While some of the proofs get a bit hairy, there is adequate hand-holding and it is clear that the authors wield technical theorems in an adept manner\n2. Significance of claims (if true) [4/5]: In particular, the linear analysis potentially paves the way for a full RKHS analysis and that would be truly consequential. \n\nHowever, there are two main shortcomings that keep the paper from being a strong addition to the body of imitation learning knowledge: \n1. Contented contributions [2/5]: There appears to be contributions that are either incorrect or misinterpreted, and others that are previously established and refined here. Clarifying / removing these would sharpen the contributions this paper has to offer.\n2. Clarity of exposition [3/5]: For practitioners in IL (which is still a large majority), this paper is hard to read and glean insights from. Insights are often lost in the paper and a concern is that the consequences of the theory presented in this paper may be lost on its readers. \\\n\nI will now expand on the two shortcomings\n\n## Contented contributions\nBefore going into individual contributions, I would like to flag that there is a recent paper that appear to make a subset of the claims presented here that the authors do not cite:\n\nSwamy et al. “Of Moments and Matching: A Game-Theoretic Framework for Closing the Imitation Gap” (ICML 2021) https://arxiv.org/abs/2103.03236 \n\nFor instance, Swamy et al. also have a notion of \\mu-recoverability (Def 3) and express bounds as a function of \\mu. Hence, for overlapping claims (some of which I will attempt to call out), it would be useful to clarify the differences between them. I will henceforth refer to this paper as Swamy et al.\n\n1. Interactive setting (matching upper and lower bounds) [Informal Theorem 1, Formal theorem 2,3]: \nThe upper bound is similar in form to Swamy et al. (as well as Dagger), i.e. \\mu H \\epsilon, where \\epsilon is the per-step loss (I would imagine that would be of the order of |S| / N). The lower bound appears to be sharper than Swamy et al. (H \\epsilon), and perhaps this is worth calling out.\n\nThe devices used in the upper bound proof also follow from reduction of imitation learning to online learning (learner provides a policy, receives a loss). Hence, it is unclear what this theorem adds to what is already established.\n\n2. Non-interactive setting (Informal Theorem 1, Formal Theorem 2) The O(H^2) is a well known result and the proof uses an MDP very similar to the one used in “Efficient Reductions for Imitaiton Learning”  (http://proceedings.mlr.press/v9/ross10a/ross10aSupple.pdf), notably Figure 1. \n\n3.  L.105, the authors mention “this is the first result to establish a clear separation in statistical minimax rate of suboptimality..”. This claim is not substantiated, and at the very least requires a clear comparison to Swamy et al. which does not make such a claim but conveys results of the same kind. \n\n4. Non-interactive setting + Linear + Parameter sharing (Informal Theorem 4, Formal Theorem 5): The claim that parameter sharing results in a reduction from O(H^2) to O(H) appears to be incorrect. Notably in Lemma 1, \\gamma can be very high which would make the bound in Lemma 1 H\\gamma ~= H, i.e. trivial. \n \nTaking a step back, it’s totally common to share parameters in behavior cloning (i.e. have the same weights for all timestep). The update in (4) would add up the errors over timestep and be exactly the supervised learning loss. \\gamma can be high, and in fact be masking a H term, i.e. gamma = H \\epsilon. \n\n5. Non-interactive + Linear + Known dynamics (Informal Theorem 5, Formal Theorem 6) \n\nSwamy et al. show that in this setting it is possible to get O(H \\epsilon) though one needs a “planner” (ala MaxEnt IRL Ziebart et al.) to search over the sequence of actions. I was surprised to see no such discussion in this theorem although Mimic-MD clearly requires such a planner in step 6. Moreover, while O(H^3/2) seems to be a clear improvement over BC, O(H), it’s still not the same order as the bound O(H). Clarifying the significance of this result w.r.t to Swamy et al. would be useful. \n\n6. Informal theorem 6 (formal theorem 7): This indeed appears to be the novel contribution. I struggled to follow the proof entirely but trust that the authors got it correct. \n\n\n## Clarity of exposition\nI’ll go over the paper chronologically and identify areas where the writing was unclear / there were typos.\n\nSection 1: Introduction\n\n* Should have been at most 2 pages. There was no need to have so many definitions up front. Certainly no need to even talk about linear results. Instead, I would have structured it to talk about the 3 regimes of IL, talk about the key results in each regime and have forward pointers to theorem in the paper. There is no need to state things twice. \n* I would massively compress Def 4 onwards till the end. The only thing interesting there is the O(H) from parameter sharing and O(H^3/2) for known dynamics. \n* I would keep the parts that  convey insight (L.59-66, L.73-79,L.155-165).\n* L86. - 90: Unclear why reduction based approach fails to distinguish between power of learners. The authors claim they circumvent reduction based guarantees, but they don’t in their proofs (reduce it to FTRL). \n* L.131: Classic supervised learning in IL does indeed use multi-class classification algorithm (for discrete actions > 2). \n\nSection 2/3\n\n* Move the definition here\n* Theorem 1: Explicitly mention realizability assumption here. \n* Theorem 3: Probably want the figure from appendix to be moved up here. \n* L307: should be \\theta^* without the _t subscript\n* L310-313: Unclear what is meant by separable and Markovian here. The point is unclear as well. \n* L316: The reader is still left trying to understand why, by mere rephrasing of the problem, the bound goes from O(H^2) to O(H). It feels like a smoke and mirror trick. The intuition is that to get such a reduction, surely we are paying elsewhere for added complexity (reasoning in the space of trajectories). That needs to be made clearer.\n\nSection 4\n\n\nL333: OPT: \\tilde(J)_r(\\pi^*)\nAlso one needs to explain how to solve OPT in practice and that it is hard.\n\nAlso, what if the reward function is only a function of state and not state action. Does this entire section fall apart? (Presumably no, but unclear)\n\nEq (5) explain E^c. \nL340: Simple empirical estimate -- unclear from what distribution. Please explain mathematically\n\nAlg 1, Line 6. \\tilde(J)_r(\\pi^*)\n\nAppendix:\nL565 tr_i should be \\pi_i\n\nL604: Wrong theorem (state the active setting)\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "48"}, "extra_text": {}}, {"review_id": "6ONE0KUu69d", "reviewer": "Reviewer_AQx2", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall I found this paper to be quite good, for which I am recommending an accept.\n\nI really appreciated the informal theorems presented before the real theorems, as they help in the clarity of the paper.\n\nI think the proofs in the Appendix could be clarified and extended to make it easier for more readers to follow, as currently it seems to be written for an audience that is already quite familiar with that type of theoretical work.\n\nMore details below.\n\n## Questions / Comments\n1.  What exactly does \"0-1 loss\" mean in line 84?\n1. In line 92, why does $\\hat{\\pi}$ denote the learner, if the policy is continuously changing? Relatedly, in line 93 does $J(\\hat{\\pi})$ represent the policy at convergence? Same question on line 103. The phrasing used in informal theorem 3 seems better for this.\n1. Does the negative result of informal theorem 2 not hold for $\\mu < 1$? Why not?\n1.  The term \"statistical minimax rate\" is used quite a lot in the paper but never explicitly defined. It would be good to define for clarity.\n1.   In line 149, \"it is known from [22] that...\", is this also under the assumption of deterministic transitions, like in the current paper?\n1.  In line 168, if $h^{*}$ is defined as an $\\arg\\max$, shouldn't you use \"$=$\" instead of \"$\\sim$\"?\n1.  Please define $\\mathbb{S}^{d-1}$ in line 188.\n1.  In line 193, the term $d^{3/2} / N$ seems to suggest that there is a tradeoff between expressivity (large $d$) and vacuosity of bound (small $d$), since $d \\ll |\\mathcal{S}|$ likely incurs larger $\\mathfrak{R}$. Is this the case?\n1.  In line 230, shouldn't it be $\\hat{\\pi}^1,\\cdots,\\hat{\\pi}^T$?\n1.  In line 237, isn't the second term of the _empirical online-learning regret_ just zero?\n1.  The statement in line 245: \"By scaling each reward...\" seems a little strange. Presumably $\\mu$ has relevance under the assumption that the rewards are in $[0, 1]$ (as stated in the introduction). But just scaling the rewards, while not changing optimal policies, _does_ change the meaning and tightness of suboptimality bounds (e.g. I can make the bounds arbitrarily small by scaling the rewards). I guess this is for the lower bound, so it's ok? On this note, is $\\mu$-recoverability necessary just so you satisfy the the existing theorem's requirements (from [22])?\n1.  In Theorem 3, it seems the lower bound would be of more use if it depended on $|\\mathcal{A}|$ instead of $H$.\n1.  In line 322, I think you need to add \"with probability $1-\\delta$\" to the end of the sentence.\n1. In Section 4 you should specify from the beginning that you are considering the case when $P$ is known (this is only revealed once you reach the Algorithm).\n1.  In Algorithm 1, it would help clarify things if you highlight with a different color what is different from the original MIMIC-MD.\n1. In equation (8), what is $-\\mathcal{K}$?\n1.  In line 564 of the Appendix, it says \"samples the policy $tr_i$\", do you mean policy or trajectory?\n1.  In line 565 it says \"rolling out $tr_i$, should this be $\\pi_i$?\n1.  In line 568, what does it mean to be rolled out and conditioned on $\\hat{\\pi}^i$?\n\n\n## Minor comments\n1.  What do you mean by \"nicely\" in line 29?\n1.  What do you mean by \"game AI\" in line 37?\n1.  Throughout the paper the authors use numbered citations as nouns (e.g. \"[25] study BC from a theoretical...\"). You should use something like \"Ross & Bagnell [25] study BC from a theoretical...\". This is especially problematic when you start sentences/paragraphs like this, as you do in line 320.\n1.  In line 81, in the expectation subscript, use $a'$ (instead of $a$) to avoid confusion, as $a$ already has a different meaning.\n1.  Line 87, the sentence \"the size of expert dataset / number of MDP interactions, N in the no-interaction / active settings.\" reads weirdly, consider rephrasing.\n1.  Line 89, should be \"propose **a** policy\".\n1.  In line 98 a sentence starts improperly (\"idea is crucial...\")\n1.  In line 130 please state what ERM stands for.\n1.  Line 146, should read \"provied **a** dataset $D$\".\n1.  Line 164, should be \"output\" instead of \"otput\".\n1.  Section 1.1 (Related work) seems out of place where it is, as it interrupts the narrative flow. Consider putting at the end of the paper.\n1. Line 235, should be \"a measurable function **of** the first\".\n1.  Line 282 should be \"upper bound\" (singular, not plural).\n1.  Line 311, what do you mean by \"By contradiction\"?\n1.  In the paper use \\restatable so that the theorem statements are reprinted in the Appendix.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a good paper that studies the statistical properties of imitation learning under various regimes, e.g., interactive, and several non-interactive settings. The reviewers found the paper technically sound and the results significant.

The shortcomings of the papers are:
- Not citing and comparing with a recent paper by Swamy et al., ICML, 2021. Some of the results of these two papers are comparable.
I believe this omission in the initial submission is acceptable, given the recency of the paper and that its arXiv version was uploaded on 4 March 2021, relatively close to the NeurIPS deadline. That being said, I encourage the authors to provide a detailed comparison with that work.
- The exposition can be improved, for example, how the Introduction is presented.
Please consult the reviews for concrete suggestions.

Overall, I believe this paper should be accepted.
Decision: Accept (Poster)