On Efficient Online Imitation Learning via Classification
Authors: Yichen Li
Chicheng Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Imitation Learning
Online Learning
Reinforcement Learning Theory

Abstract: Imitation learning (IL) is a general learning paradigm for sequential decision-making problems. Interactive imitation learning, where learners can interactively query for expert annotations, has been shown to achieve provably superior sample efficiency guarantees compared with its offline counterpart or reinforcement learning. In this work, we study classification-based online imitation learning (abbrev. COIL) and the fundamental feasibility to design oracle-efficient regret-minimization algorithms in this setting, with a focus on the general non-realizable case. We make the following contributions: (1) we show that in the COIL problem, any proper online learning algorithm cannot guarantee a sublinear regret in general; (2) we propose Logger, an improper online learning algorithmic framework, that reduces COIL to online linear optimization, by utilizing a new definition of mixed policy class; (3) we design two oracle-efficient algorithms within the Logger framework that enjoy different sample and interaction round complexity tradeoffs, and show their improvements over behavior cloning; (4) we show that under standard complexity-theoretic assumptions, efficient dynamic regret minimization is infeasible in the Logger framework. 


On Efficient Online Imitation Learning via Classification
Yichen University of Arizona yichenl@arizona. edu
Chicheng Zhang University of Arizona chi chichengzocs arizona. edu
Abstract
Imitation learning (IL) is a general learning paradigm for tackling sequential decision-makin problems. Interactive imitation learning, where learners can in- teractively query for expert demonstrations, has been shown achieve provably superior sample efficiency guarantees compared with its offline counterpart reinforcement learning. In this work, we study classification-baat learning (abbrev. COIL. and the fundamental feasibility to design oracle-efficient regret-minimizztion algorithms this setting, with focus on the general non- realizable case. We make the following contributions: (1) show that in the COIL problem, any proper online learning algorithm cannot guarantee sublinear regret in general; (2) we propose LOGGER, an improper online learning algorithmic framework, that reduces COIL to online linear optimization, by utilizing a new def- inition of mixed policy class; (3) design two oracle-efficient algorithms within the LOGGER framework that enjoy different sample and interaction round com- plexity tradeoffs, and conduct sample analyses to show their improvements over naive behavior cloning; (4) we show that under the standard complexity- theoretic assumptions, efficient dynamic regret minimization is infeasible in the LOGGER framework. Our work puts classification- based online imitation learning, important IL setup, into a firmer foundation.
online imitation
Introduction
Imitation learning (IL), also known as learning from expert demonstrations [47 44), is a general paradigm for training intelligent behavior for sequential decision making tasks. IL has been success- fully deployed in many applications, such as autonomous driving [47 45), robot arm control [69], game playing [60], and sequence prediction [23] 8). It is now well-known that with the help of demonstrating expert, an IL agent can bypass the exploration challenges of reinforcement learning, achieving much lower sample requirement than reinforcement learning agents [63].
Two major paradigms have been studied in the literature: offline and interactive. In offline II. [ (4 [4] (3), the learner receives a set of expert demonstrations ahead of time; in contrast, in interactive 23 [66] 55 32), the learner has the ability to interactively query the expert for demonstrations on states its disposal, allowing expert feedback to be provided in targeted manner. In both settings, the goal of the learner is to output a policy f that competes with the expert's policy FF by consuming few resources (e.g. expert annotations) possible. Between these two, interactive IL known to be able to achieve superior policy performance than its offline counterpart under certain favorable assumptions the expert policy and the environment, in that learning agents can use interaction to address the compounding error challenge 54
Despite the recent progress in the fundamental limits of the interactive imitation learning in the realizable setting (63
50 49 the statistical and computational limits of the interactive imitation learning in the general nonrealizable setting remain open. One promising and influential algorithmic framework for studying and analyzing interactive IL the nonrealizable setting is DAGGER (Data
36th Conference on Ncural Information Processing Systems (NcurIPS 2022).

---

Aggregation) [56], whose key insight is to reduce interactive IL to regret minimization in online learning [59]. Specifically, constructs N-round online learning game, where at every round E [M]. the learner outputs some policy Th from a policy class B, and incurs loss (T):: the loss carefully constructed so that the learner's instantaneous loss (T, characterizes current policy nn's 's competitiveness compared to the expert л A representative example of (1) is the expected disagreement between π and T5 on the state occupancy distribution induced by Ta- used in the original DAGGER paper [56), which can be expressed as the expected zero-one loss of Online
ı on a distribution of classification examples we call such setting Classification-but Imitation Learning (abbrev. COIL). The DAGGER reduction framework has spurred an active line of L3 88 38] it enables conversions from stochastic online optimization algorithms with static dynamic regret guarantees to IL algorithms with different output policy suboptimality guarantees, allowing the research community to directly translate new results in online learning to those in II..
research on IL [c.g. 55 63
Perhaps surprisingly, from a fundamental perspective, rigorous design of efficient regret minimization algorithms for COIL has been largely overlooked by the prior literature. Specifically, many works assume a fixed parameterization of policies in B, and assume that F, (7) )'s are convex in x underlying parameters to allow for no-regret online convex optimization [e.g. 56 63 [5] Although natural, this viewpoint has some issues: (1) in DAGGER'S reduction, the learner uses sample approximations of (TT,, which are often discontinuous in x' underlying parameters (e.g. given policy (T)s)
sign( (0, s)) as a linear classifier, its zero-one loss on a state, (TTT()) * π (s)) is discontinuous in 8), making stochastic gradient-based methods inapplicable. Convex surrogate loss functions has been proposed as popular workaround [56], but it is well-known that in the nonrealizable setting, even for the special case of supervised learning, minimizing convex surrogate losses can result in very different models compared to minimizing the original zero-one classification losses 77: (2) it makes the usage of policy classes with complex parameterization (e.g. rule-based policies such decision trees) difficult, as convexity is hard to establish for such classes.
Overview of our results. In this paper, we bridge the mhove-mentioned gaps by studying the funda- mental feasibility of designing efficient regret minimization algorithms for COIL, putting the study of statistical and computational limits of interactive imitation learning in the general nonrealizable setting into firmer foundation. Our first result is that, analogous to Cover's impossibility result in online classification (20). in the COIL setting, any proper online learning algorithm (that outputs iN
sequence of policies { {Tn/n=1 from the original class B) cannot guarantee sublinear regret in general ( 3.1..
The above negative result motivates the design of improper learning algorithms for regret minimiza- tion. To this end, we propose to choose policies from mixed policy class lsg, and provide an algorithmic framework, LOGGER, that reduces COIL to online linear optimization. In a nutshell, LOGGER uses natural parameterization Ig that allows to express Fz (T)) as linear function of the underyling parameters of π E 1lg. We show that any online linear optimization algorithm with (high-probability) regret guarantees can be plugged into LOGGER to obtain algorithm for COIL with policy suboptimality guarantees 3.2).
Next, enabled by the LOGGER framework, we design computationally efficient algorithms for static regret minimization. Assuming access to an offline cost-sensitive classification (CSC) oracle O and a set of unlabeled separator examples for B [66] (24), we design LOGGER-M, sample and computationally efficient algorithm. With ( interaction rounds and 2 expert annotations, LOGGER-M -M enjoys a per-round static regret of d 4.1). Underlying LOGGER-M M is delicate utilization of the connection between Follow-the-Pertun thhe--PettubeddLLee Leader, two well-known online learning algorithm families, first observed by (2). Moreover, by exploiting the predictability of the COIL problem
and Follow-ther tet-thh-Reeee the-Reeularized-
[5T] [8 [7], we design an efficient algorithm LOGGER-ME that enjoys per-round static regret of c, with (1/cc) interaction rounds and O(1/e²) expert annotations O 4.2) Its reduced number of interaction rounds can enable a more practical deployment of IL agents, especially when interactive expert annotations come in batches with delays.
Finally, we study efficient dynamic regret minimization in the LOGGER framework 5 that this is unlikely to be feasible: under standard complexity-thene -theoretic assumption, no oracle- efficient algorithms can output policies in IIg with sublinear dynamic regret. Due to space constraints, we discuss key related works throughout the paper, and defer additional related works to Appendix
We show
2

---

2 Preliminaries
Basic definitions. Define [n] := {l....,n) n). Define indicator function I(-) such that (()) = 1 if condition E is true, and = 0 otherwise. We use A(W) to denote the set of probability distributions over a finite set W, and use Onehot(w, w. W) E A(W) to denote the delta mass on w E W. For a finite W, we will oftentimes treat u E IR [ (c.g. u E A(W)) as [W] -dimensioona vector; for w. E W. denote by u[w] the w-th coordinate of u. We abuse the notation of {-} to denote multisets.
Episodic MDPs, We study imitation learning in episodic Markov decision processes (MDPs). An episodic MDP M is a tuple (S, A, H, c, p. P), where S is finite state space (that can be exponentially large), A is finite action set, H E N+ is the episode length, C: S x A + [o, 1] is the cost function, and p E A (SS) is the initial state distribution. Also, P= {P:} = denotes M's transition dynamics, with : x A - (SS) being the transition probability step f. Throughout,
S and A to denote |S] and |A,, respectively. Without loss of generality, we assume that M is layered, where S can be partitioned into H disjoint sets { the initial distribution p is supported on St, and transition distribution Pr(- s, a) is supported on S for all é, a. For state E S, define (s) as the step such that s St.
A learning agent interacts with .M for one episode using the following protocol: for every step t E [H]: it observes state St E St, takes action a E A, incurs cost c(s;, at), and transitions to next state 8,11 ~ P.(. St, az) except for the last step when it stops. Given a stationary policy S ((A), use r(-(s) to denote the action distribution of π on s. Denote by E, and Pr the expectation and probability over executing (i.e. rolling out) policy π in M. Given policy
n, its state oceupancy distribution at step is defined as d' (-) == (st = .); its average state
occupancy distribution is denoted as d, == मे E'= dz. Let (TT) == E, [(
c(st, at)
H Egrdd Eawa(-1a) [c(s denote the expected cumulative cost of i over an episode. For policy n, we denote its value function V=(s) == E E St=sep((s) c(st; 8, π and action-value function
Σ# Step((())+ c(sE, a.) 8, 8,a, π in words, they are the expected costs of rolling out ग starting from and (s, a). respectively. For policy π,, define its advantage function as An a) == (s, a) - (s). which measures the expected performance difference by one step deviation of by taking action a state s. Also, we define the recoverability constant as the ability of π to recover from deviation when rolled out in M:
Q=(s, a) == c(s, + E
Definition 1 (I-recoverabilityy. A (MDP, policy) pair (M, is said to be p-recoverable, if E S. E A. Ar a) S p.
Interactive IL. We study interactive imitation learning 223 54 where the learner has access to stationary deterministic demonstrating expert R and would like to learn policy with low ex- pected cost. Throughout, we assume that (M, B) is ju-recoverable, for some < H that can possibly be < H. At each interaction round, the learner interacts with M for a few episodes. obtaining trajectories of the form T = ($1, $2, $2, .H. aн) and queries the expert for feed- back on some of the states. Specifically, given a state s, the feedback given by the expert of the form (Ce(s, a))aEA E R-A. Two notable examples are: (1) direct expert annotation (56), i.e. given state s, expert provides demonstration N (s)) and we use to construct an A-dimensional feedback (SE(s, a) )aEA = (μ I(a * π (s)))) (2) estimates of value functions based on experts' rollout (55), i.e. (CF(s,u))GEA = -A* (s,a))oEA := (A, (s,,)))aeA
Throughout, we assume (=(s,a) a) satisfies Vs E S,a E A. A. (z,))) S ()(s,a) S : I(a 7 (s)); this satisfied by the two examples above. For stationary policy स, define its imitation loss as: [TT) := Rgnd, Ee [CE(s,a) a)]. By the performance difference lemma (34 (see Lemma 55 in Appendix H) J(T) - [[= I H L(T), implying that if æ has small imitation loss, it will have expected cost competitive with = In light of this connection, in interactive IL, the learner would like obtain policy म with low L(f). Subject to this, throughout the paper, we consider optimizing two measures of data efficiency:
'The u-recoverabilityy definition here is slightly different from the original ones in [56 in that also requires that Ar (8,a) a) 2 -Mz we can drop this assumption with a slightly worse sample complexity analysis. Sttrctly speaking, in Aggre Vate and its variants (55] 63). the learner requests expert rollout to obtain unbiased estimators of A a): sample complexity analysis can also be adapted this setting.
3

---

Protocol Classificatiinn-assed Online Imitation Learning (COIL)
for ,,.... .N do
Learner outputs policy Tn. Loss function F,, (TT == Eydda, (--x((19)) [SE((s, a)].
Learner draws samples from D obtain information about loss Fu, via interacting with M and querying the expert for annotation ÇE.
end for
Goal of learner: minimize En (T.))) = -E L(TT).
Sample complexity: the total number of expert annotations ÇE requested. A smaller sample complexity reduces the total cost of expert annotations (which often takes human effort). Interaction round complexity: total number of adaptive interaction rounds. A small number of interaction rounds enables more parallelized annotations within an interaction round, and mitigates issues of annotation delay [72 68].
The DAGGER reduction framework for interactive IL. The DAGGER framework reduces mini- mizing (TT) no-regret online learning [66 551 It constructs N-round online learning game, where at every round n E [N], the learner outputs some policy Tæ, which induces a loss function (x E gg Ba- s) [Sass,, a)). Its key insight is that, by the definition of { minimiz- ing the online learning cumulative loss Σ (T.().)) is equivalent to minimizing the cumulative imitation losses of n. 's. i.. 1 L(TT,)) Research efforts in online learning [5 43 have mainly
focused on the design of algorithms that can output {T,, Y with static regret SRega (B) or dynamic regret DRog (B) against some benchmark policy class B, formally:
N
N
SRegN (B) = Σ Fa( min
(T(TT),
DRegN (B) = Σ
E (T(TT) - min Fx (a(TT)
- xEB
(1)
Assuming that the learner chooses policies (π₂) N from another stationary policy class Bo (which may or may not be B3, the following proposition shows that static and dynamic regret guarantees in the induced online learning game can be converted to policy suboptimality guarantees:
Proposition 2 (e.g. [5]). For any N E N+ and online learner that oulputs { E BB, define Bias(B, Bo, N) := max min E Ba-x(-le) [T(a + n =s)),, where dx == N ENN de..
sEB
Then, choosing it uniformly at random from { W has guarantee:
{ {I. Bias(B, N) + E|SRegx 1 Bias(B, Bo. 1)
E[DRegy (B)
E [(A) J(x5)] < H H-min
N
N
In the above proposition, BBas(B, Bo, .N takes the worst-case mixture of state occupancy distributions {do., J induced by N policies from Bi, and measures the expected disagreement between T and its best approximating policy in B. Informally, it measures the "approximation error" of benchmark class B: it is always nonnegative, and in the special case of я F E B (which we call the realizable case), Bias [3, By N) O. Proposition 2 gives
ways obtain competitive imitation policy: (1) choose (B, Bb) with a small Bias B, Bo. .)) and achieve a low static regret; (2) choose (B, Bn) with small Bias(B, Bo. 1) and achieve low dynamic regret. Although achieving low dynamic regret can be significantly more challenging than achieving low static regret, minimizing dynamic regret has the advantage that its approximation error term Bias(B, Bo, 1) smaller than the static regret formulation's 's counterpart BBas(B, N). Classification- Online Imitation Learning (COIL). As consider finite action space A, policy æ can be equivalently viewed as a (possibly randomized) multiclass classifier. cost- sensitive classification (CSC) example is defined to be pair (z, where E S is its feature part, and č E is its cost part. Under the DAGGER reduction framework, the loss at iteration n, Fg (T) Ey-de, Ea [SE a)] can be viewed as the expected cost of policy æ on DE distribution cost-sensitive examples T.. (formally, E, [a(h(s))], where sample (s, a) is drawn from DE by first rolling out and drawing dn, and query the expert to obtain

---

(Se(s, a))GEA as its associated č. The learner can obtain a finite-sample approximation to (T) by interacting with M and the expert draw samples from D.F. We will focus on designing efficient regret-minimizing algorithms in the COIL setting; see Protocol T for a summary.
In addition data efficiency, we also consider the design of imitation learning algorithms with computational efficiency guarantees. To this end. following a sequence of empirically and theoretically successful works on oracle-efficient learning [66] 25 5 211. we assume access to the benchmark policy class B, a collection of B stationary and deterministic policies h: S + A, via the following computational oracle:
Definition 3 (CSC oracle). A CSC oracle O for policy class B3 is such that: given any input multiset
of cost-sensitivv examples D = {(111 G1 .),.... (IK, [K)] E (S BAAK K it outputs the policy in B that has the smallest empirical cost, formally,
O(D) == argmin (( [T((z))],
KEB
where we slightly abuse the notation and and use D to also denote the uniform distribution over it.
We measure an algorithm's computational efficiency by its number of calls to oracle O.
3 LOGGER: reducing COIL to online linear optimization
In this section, we introduce our main algorithmic framework, LOGGER (an abbreviation for Linear 1Oss uGGrEgation) for designing regret-minimizing algorithms in the COIL setting. Section [3.] motivates our approach by showing that natural proper learning- -earning-based approaches fail to achieve sublinear regret in general: Section 3.2 introduces our approach of performing improper learning using a carefully-defined mixture policy class, via reduction to online linear optimization.
3.1 Can we achieve sublinear regret using proper learning?
natural idea for minimizing regret is proper learning: at round n, the learner chooses some policy Tn (possibly at random) from B, B, our benchmark policy class, using some online learning algorithm, based on the information collected the first n 1 rounds; the learner then collects information on Fa via rollouts of л. and expert annotations, and continue to the next iteration.
While this approach has demonstrated sharp online regret guarantees in classical online cost-sensitive classification settings [40 227. perhaps subtly, we show in the following theorem that, this approach insufficient to guarantee sublinear regret in the COIL setting.
Theorem 4. Suppose the expert's 's feedback Çε(s, a) is of the form I(a + ( or A a) Then, for any H 2 3, there exists an MDP M of episode length H, a deterministic expert policy x B benchmark policy class B, such that for any learner that sequentially (and possibly at random) generates sequence of policies {nT, F E BN, its static regret satisfies SReg ((N).
The proof of the theorem can be found at Appendix D.I Its key insight is that, distinct from the classical online CSC setting, in COIL. the loss at round n. F.. depends on the policy chosen at that round nR. making standard regret minimization results in online classification 40 27 inapplicable. In more detail, we construct a fixed MDP that "act adversarially" to policies B, such that any
H-1 Tn E B has Fx(TT) 2 H whereas m EN Fx(T) S 2. Our theorem is similar in spirit to Cover's impossibility result in online classification 20). which shows that adversary that adapts to the randomness of the learner at each round can force the learner to suffer linear regret.
3.2 A new hypothesis class and the LOGGER algorithmic framework
To sidestep the impossibility result in Theorem 4 we apply the "convexification by randomization" technique in online convex optimization 599 by improper learning on a mixed policy class, defined below.
Definition 5 (Mixed policy class), Given policy class B, define its induced mixed policy class
11g = Tu T-((1))= = Σ
u[h] h(-1s) : u A(B)
heB
5

---

Algorithm 2 LOGGER: reducing COIL to online linear optimization
1: Input: MDP M, Expert feedback (E. sample size per iteration K, Online linear optimization algorithm OLOA with decision set ((B).
2: for 1,2...... NN do
3: Choose Uh f- OLOA (1 which induces policy Tu := Te,
4: Draw K examples D = (8, iid from DE,- via interaction with M and expert ÇE-
5: Dr induces [B(.E) Banl()))) [[(a]]) NEB
an unbiased estimator of ((un).
6: end for
We slightly abuse notation and use h(. 6) E A(A) to denote the delta mass on h(s) E A
At a cursory glance, choosing policy from 11g seems equivalent to choosing some policy at random from B, which also falls into the failure mode of proper learning (Theorem 4 We remark that this not true: rolling out a policy from Tu E I is equivalent to drawing new policies in an i.i.d. fashion from B at every step of the episode instead. As we will see next, the usage of Ig enables the design of COIL algorithms with sublinear regret.
Our key observation is that with the learner outputting policies from the mixed policy class Tsg online regret minimization in IL becomes an online linear optimization problem. Recall that in online IL, the loss at round Fn (T) = Egadd, (a--)(-1s) [SE(s,a) a)]. By choosing Tn Nu, 1Ig and Tu Ig for Un (B),, (TT be viewed as linear function of u:
(T.) = Σ ulh Bande, Baw)(ll)) [CE((s, a)] (0(un); u)
where ((v) = (Bonden Bawtet-ls) [SE(s,
We have
hEB
N
N
N
N Σ Fx(TT))
N min Σ FT(
(A(ua),un) = Σ FA(TT))
min (EA(B)
(0(un),
min WEA(B) ==1
FEB n=1
==1
and therefore, minimzing the static regret SRegN (B) equivalent to minimizing the static regret in
the online linear optimization problem with losses { uu (0(un), u)
This motivates LOGGER (Algorithm 2). our main algorithmic framework. Given input an online linear optimization algorithm OLOA and sample size K, LOGGER outputs policy sequence {TT J. Specifically, at round n, LOGGER calls OLOA to perform online linear optimization with respect linear losses {u + (gt, u) M and obtains u, E AB)), which corresponds a policy n, E Iīg (line 3 here for every i, 9; is unbiased estimator of ((u)). It then rolls out тr in M for K times to obtain K samples iid from dr,, queries the expert on each sample 8 to obtain (CE(s, a)) as its associated č and constructs dataset D, {(s )) (line 4p. Finally LOGGER computes the empirical (line
loss of policies on Dn, i.e. In = [E...,,, E.r.D,,Eaaaa Ba [ī(a)] hEB
Comparison to prior works. 16 considers a general online convex optimization formulation for online IL, dubbed "continuous online learning"; our loss function (0(u), can be viewed as an instantiation of the loss function fa(.) therein. However, their regret minimization results assume that (-) is strongly convex, which do not cover our COIL setting where f-) is linear.
Define LReg := E (gn; un) min Σ (gn, u) OLOA's 's static regret with respect (gns .) 1- We have the following proposition that links LReg, to SReg (B), the static regret of ( (Tn) Jnz in the online IL problem.
Proposition 6. For any 5 E (0, 1). if LOGGER such that with probability at least - 8/3, LReg & Reg(N), N). Then, with probability at least 1 8,
some OLOA that outputs {u, n= A(B)
its output policies { satisfy SReg (B) & Reg(N) (N) +
NI/(B/))
K
63 Theorem 5.3] proposes to perform no no-regret learning using another definition of nonstationary mixed policy class. We identify technical issue with this approach, and defer detailed discussion Appendix D.2

---

Proposition shows that Algorithm 2 is regret-preservvee reduction from online IL to online linear optimization over (B)). B-dimensional probability simplex. The latter is well-known as the "prediction with expert advice" problem [27] (abbrev. expert problem), where algorithms with different guarantees abound, such as Follow the Regularized Leader (FTRL), Hedge [27] and its adaptive and optimistic variants (e.g. [1, Section 1]. many of which have optimal worst-case regret
bounds Reg(N) = O (VN (N(((B) Instantiating Algorithm with OLOA set as these algorithms,
obtain family of online IL algorithms with expected regret of order O(vN).
Although satisfying from statistical efficiency perspective, such online IL. algorithms suffers from computational inefficiency: they require explicit calculation of In and maintenance of Un which are B-dimensional (dense) vectors whose entries need to be updated separately. For instance, when Hedge is chosen as OLOA, (n] xc exp(-nE==1 9n [h])) for all E B, which naively requires O(B) time per round to maintain. To address this computational efficiency issue, in the next section, we exploit the cost-sensitive classification nature of the COIL problem to design sublinear-regret algorithms that use implicit representations of 9n 's, i.e. D, 's, that enjoy oracle-efficiency guarantees.
4 Efficient algorithms with static regret guarantees
Using the LOGGER framework, in this section, we propose two oracle-efficient COIL algorithms that have sublinear static regret guarantees against policy class B, in Subsections 4.1 and respectively.
4.1 LOGGER-M: an efficient algorithm with O(VN) static regret
The LOGGER reduction framework calls for a computationally and statistically efficient OLOA, which, if devised, yields an computationally and statistically efficient online imitation learner. How- ever, when viewed as a general adversarial online learning problem, computational hardness re- sults [29] suggest that, even with access to classification oracle O, prohibitive ((vB) B) time complexity necessary for sublinear regret. Therefore, in subsequent sections, we adopt an assump- tion on B in (66), which, to the best of our knowledge, is the state-of-the-art weakest assumption that allows the design of oracle-efficient online CSC algorithms in the adversarial setting:
Assumption 1 (Small separator set). There exists set X C S (called the separator set) such that, for every pair of distinct policies h, h' E B, 3x E X, such that h(z) * h'()). Denote by X (
Technical challenges. Even under the small separator set assumption, the design of low-regret oracle-efficient algorithms for imitation learning still remains nontrivial. A naive application of existing oracle-efficient online CSC algorithms, such as Contextual Follow the Perturbed Leader (CFTPL) [66] 24], still falls into the failure mode of proper learning (Theorem 4 in Section [3II). where an ((N) regret lower bound is unavoidable in the worst case. This is in sharp contrast to the classical online CSC setting, where CFTPL enjoys O(vN) regret [66] 24). To recap, at round n. CFTPL first constructs a random set of "hallucinated" cost-sensitive examples Z based on the separator set X: it subsequently calls the CSC oracle O on the union of Z and the accumulated dataset ==1 D; to obtain policy T. E B. CFTPL achieves computational efficiency by operating on D, s, an implicit representation of 9n," 's, the linear losses of the underlying OLO problem.
Our approach. The above difficulty motivates the need of new algorithmic approach for efficient dlssification--asel online II.. In view of Section 3.2 observation that FTRL approaches enjoy sublinear regret, we ask the question: is it possible to perform FTRL in an oracle-efficient manner? positive answer will simultancously address the computational and statistical challenges of COIL.
We answer this question in the affirmative, by utilizing a connection between FTRL and FTPL first observed in 2 an in-expectation version of FTPL can be viewed as an FTRL algorithm. Using this observation, we design Algorithm 3, namely Mixed CFTPL (abbrev. MFTPL,, which mimics FTRL by approximating the in- in-expectation version of CFTPL in an oracle-efficient manner. Similar to CFTPL, MFTPL keeps 9n implicitly in D,, and calls the CSC oracle. Different from CFTPL, MFTPL runs the oracle-call step in CFTPL for T times and outputs the uniform mixture of the T policies. We refer to 7 as Algorithm 3 sparsification parameter, due to the algorithm's 's resemblance to Maurey's sparsification [46).
7

---

Algorithm 3 MFTPL: an oracle-efficient approximation of FTRL
1: Input: Linear losses {g)) )=1 represented by datasets {D:) n-1 each of size K (s.t. gi[M] ((,,)),, [T{(())] for all h B), separator set X, learning rate 1) sparsification parameter T. do ~ (( AA) iid for each X.
2: for j --1,,,
3: Draw
4: Define Zj (x, / (as) x x
5: Compute Un.j & Onehot (O(UU)
6: end for
7: return Uy, + Un.j.
Specifically, at each iteration j E [T], MFTPL first draws (Ln,(a)) ~ NO, IA) iid for each x in the separator set X, where LA is the identity matrix of dimension A (line It then constructs x} that contains each within 17 Ezzj as associated ē where K accounts for the adjustment dataset size and 17 accounts for FTRL's learning rate (line 4). It then calls the oracle O with datasets U D; accumulated so far, together with perturbation examples Zj obtain an empirical cost minimizer E B. This is represented by a one-hot vector Un E A(B) that has weight on the h-th coordinate and 0 elsewhere (line 55. Finally, after T iterations, MFTPL returns the mean value Un = Σ}= Un.j (line 7. MFTPL guarantees that:
perturbation set of cost-sensitive examples Zj = {{(z K (x.g)
the separator set and K
Lemma 7. There exists some strongly convex function R A(B) + IR, such that the following holds. Suppose MFTPL receives datasets (D:) separator X, learning n, sparsification parameter T. Then, 4ō E (0,1), with probability at least - 5, MFTPL. makes T calls to the cost-sensitive oracle O, and outputs Un (BB such that
2A (In(S) In(3))
vs S, Tua (-1s) Tuz (-1s)]1 1
T
with uc, = argmin (n n- gr. ui, + R(u)).
Therefore, by setting T = ((AAA((S)))) the policy n. induced by the MFTPL's output un closely mimics Tag a policy induced by the FTRL output ur The mild In(-) dependence on S makes the lemma useful in large-state-space settings. Specifically, naive attempt to show Lemma 7 is to establish the || l| closeness un and ue, given that un ~ Multinomiall(T, ut)) This unavoidably carries an impractical concentration factor of O (BBT)), as the bound requires T to be ((B) to be non-vacuous. We circumvent this challenge by directly showing the closeness of the action distributions uu., and Tuz for all states. We defer the full version of the lemma, including an explicit form of R, to Appendix E.I
Lemma 8. For any 8 (0, 1). MFTPL, if called for N rounds, with inpul learning rale 1 In(B)) and sparsification parameter T N N1((2N9/8) outputs sequence {u,) I== such
NVNA
that with probability at least
LRegy So (IVINA (x* 7
Composing LOGGER with MFTPL, we obtain efficient online IL algorithm, LOGGER-M. Its regret guarantees immediately follow from combining Lemma with with Proposition 6
Theorem 9. For any E (0, 1), LOGGER-M, with = 1 and MFTPL setting its parameters as in Lemma 8 is such that: (1) with probability at least 8, its output { satisfies: SReg < O (p/NAlm(1/0)() it calls the CSC oracle O for (n(6N8/6) times.
(n(B)))) (2) it queries N annotations from the expert; (3)
/x* ln()

---

4.2 LOGGER-ME: an efficient algorithm with O (1) static regret
Although LOGGER-M M is oracle-efficient, it is unclear whether its O(vN) regret guarantee is optimal. As a lower regret can translate to lower sample and interaction round complexity guarantees, desirable to design algorithms with regret as low as possible.
that, online IL is a predictable online learning problem [19 [1], and is thus not completely adversarial. This opens up possibilities to bypass the ((vN) worst-case regret barrier. Specifically, in the LOGGER framework, the coefficient of the linear loss round n. (u,,), depends continuously on uni more concretely. we can show:
key observation from prior works [e.g. 15 16 38
Lemma 10. For u, E (B), [0(u)) - 0(v)ll S uHl [max||Tu--ss - T (-|=)]I S nH a|lI.
This property and its variants, termed distributional continuity, has been utilized in many online IL algorithms to achieve sharper regret guarantees. These works additionally exploit the strong convexity on the loss functions F2 15 16 38), or use some external predictive model that can predict F., (TT) well [8 I7I. Unfortunately, in our COIL setting, neither is the loss function (T.) = (f(u)). u) strongly convex in the policy parameter u, nor do we have access to an external predictive model, rendering these approaches inapplicable.
We get around these challenges and design an oracle-efficient algorithm, namely MFTPL--RG (where EG stands for extra-gran straa-gradient,, with ((1) regret for the online linear optimization problem, which, when composed with the LOGGER framework, yiclds the LOGGER-ME MEE algorithm with ((1) regret in the COIL setting. MFTPL-EG is largely inspired by the predictor-corrector framework for policy optimization [17 and extragradient methods in smooth optimization 42 33;; ; its details can be found in Appendix E.2 Its key insight is that, although we do not have predictive model for (u,,). can use an extra round of interaction with .M and expert annotations to obtain a good estimate of it. Based on this, we derive online linear optimization regret guarantee of MFTPL-EG, deferred to Appendix F.2 This immediately implies the following guarantee of LOGGER-ME:
Theorem 11. For any 5 E 10, LOGGER-ME, with K and MFTPL-EG's parameters set appropriately, is such that: (I) with probability at least 6, its output { satisfies:
(B) S O(UHA/X3 Bn): (2) queries O
annotations from the expert: HPAXX*1n(BB
N2 In(NB/8))
(3) it calls the CSC oracle O for O
N In(N5/5) [HAX*II(B)
times.
Discussion and comparison. We now compare the guarantees of LOGGER-M, LOGGER-ME, and the baseline of behavior cloning, where the learner simply draws iid examples from DE and perform empirical risk minimization over B to learn a policy म. All algorithms' output policy suboptimality guarantees have the following decomposition:
J(+) - [(x))] s ApproxErr + EstimEEr,
(2)
where ApproxErr measures the approximation error of the policy class B to the expert policy F and EstimErr is an estimation error term that vanishes with the number of expert annotation examples and iterations increasing. By Proposition 2 for LOGGER-M M and LOGGER-ME, their ApproxErr terms are both μH Bias(B, Ilg, .N. For their EstimErr H (B) we use Theorems and to calculate the minimum total numbers of interaction rounds [(e). expert annotations A(e., and oracle calls C'(e). so that EstimErr is at most with probability least 6. As presented in Table I] LOGGER-ME has the same sample complexity order as LOGGER-M M, but has a much lower interaction round complexity (μH22 /c vs. p. H22 /(2).
On the other hand, by standard ERM analysis [58] and conversion from supervised learning to imitation learning guarantees (655) 34)), behavior cloning B using K samples outputs a policy t, such that Equation (2) holds with ApproxErr = H² Bias(B, B, {m 1). and EstimeEr
H²2 221n(22//5 //)/K (see Appendix E.3 for detailed derivation), where Bias(B, {m²), 1)
minges Eand_n [I(h(s) * ~ (s))]. We also summarize behavior cloning's 's performance guarantees in Table [ Compared with the two interactive IL algorithms above, behavior cloning requires only one interaction round and one call to the oracle O, however its ApproxErr has larger coefficient on the optimal classificatiin loss (H2 vs. HH),, and needs more expert annotations (H /e2 vs. H2 /22
to achieve approximation error smaller than with probability at least 1 - 6.

---

Algorithm
ApproxErr
I(e)
A(c)
C(c)
LOGGER-M
μH Bias(B, [B, Ds, N)
LOGGER-ME
μ Bias(B, Tıs N)
Ó uH
Ó
Ō Ö(E
Behavior cloning
2 Bias(B, { 1)
1
Table 1: A comparison between algorithms and the behavior cloning baseline, in terms of approximation error, and numbers of interaction rounds [(c), expert annotations A(c), oracle calls C(e) needed for estimation error to be at most with probability - 8. Here O(-) hides dependences on In(uH/e), X, A, In(),, (B)),, In(u), ln(1/6). See Appendix E.3 for the full version of the table.
Computational hardness of sublinear dynamic regret guarantees
Finally, we study dynamic regret minimization for COIL in the LOGGER framework. Although in the abstract continuous online learning setup. dynamic regret minimization has recently been shown to be computationally hard (16), given the peculiar linear loss structure of the LOGGER framework, the computational tractability of dynamic regret minimization within this framework still remains open.
We fill this gap by showing that, under a standard complexity -heoreeiic assumption (that PPAD- complete problems do not admit randomized polynomial-tne algorithms), there do not exist polynomial- algorithms that achieve sublinear dynamic regret in COIL. Specifically, we have:
Theorem 12. Fix > if there exist COIL algorithm such that for any M and expert n it interacts with M, CSC oracle O, expert feedback (E( a) A (s, a), and outputs sequence of { E Hg s.l. with probability at least 1/2,,
DReg (B) S (pooy(SS, A, B) -NT->,
in poly (No A,A,B) time, then all problems in PPAD are solvable randomized polynomial time.
The key insight behind our proof of Theorem 12 is that, achieving a sublinear dynamic regret in the COIL setup is at least hard as finding approximate Nash equilibrium in a two-player general-sum game, a well-known PPAD-compled problem [33. To establish a reduction from a two-player general-sum game to COIL problem, carefully construct tree-structured MDP whose "leaf states" consist of two major groups: one group has costs encoding the two players' payoffs, and the other group has large constant cost, ensuring that any policy in Hg with small dynamic regret encodes near-optimal strategies of both players. We refer the readers to Appendix F for details.
Conclusion
In this work, investigate the fundamental statistical and computational limits of classification- based online imitation learning (COIL). On the positive side, we propose the LOGGER framework that enables the design of oracle and regret efficient COIL algorithms with different sample and interaction round complexity tradeoffs, outperforming the behavior cloning baseline. On the negative side, we establish impossibility results for sublinear statie regret using proper learning in the COIL setting. We also show the computational hardness of sublinear dynamic regret guarantees in the LOGGER framework.
Looking forward, it would be interesting to investigate the optimality of our sample complexity and interaction round complexity guarantees; also speculate that it is possible to relax the small separator set assumption on B by utilizing very recent results on smoothed online learning [T] 28). Finally, we also interested in empirically evaluating algorithms.
Acknowledgments and Disclosure of Funding. We thank the anonymous reviewers for their constructive comments. We thank Kwang-Sung Jun, Ryn Gray, Jason Pacheco, and members of the University of Arizona machine learning reading group for helpful discussions. We thank Wen Sun for helpful communications regarding
(63 Theorem 5.3] and pointing us to an updated version 6 Section 15.5]. We thank Weijing Wang for helping with illustrative figures. This work is supported by startup funding by the University of Arizona.
10

---

References
[1] Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-first international conference Machine learning, page 1, 2004.
[2] Jacob Abernethy, Chansoo Lee, Abhinav Sinha, and Ambuj Tewari. Online linear optimization via smoothing. In Conference Learning Theory, pages 807-823. PMLR, 2014.
[3] Jacob D Abernethy, Young Hun Jung, Chansoo Lee, Audra McMillan, and Ambuj Tewari. Online learning via the differential privacy lens. Advances in Neural Information Processing Systems, 32, 2019.
[4] Jacob D Abernethy, Chansoo Lee, and Ambuj Tewari. Fighting bandits with a new kind of smoothness. Advances in Neural Information Processing Systems, 28, 2015.
[5] Alckh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. International Conference on Machine Learning, pages 1638-1646 PMLR, 2014.
[6] Alekh Agarwal, Nan Jiang, Sham M. Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms, 2020.
[7] Shai Ben-David, David Loker, Nathan Srebro, and Karthik Sridharan. Minimizing the misclas- sification error rate using a surrogate convex loss. In ICML, 2012.
[8] Samy Bengio, Oriol Vinyals, Navdeep Jaitly, and Noam Shazeer. Scheduled sampling for sequence prediction with recurrent neural networks. Advances in neural information processing systems, 28, 2015.
[9] Dimitri Bertsekas. Stochastic optimization problems with nondifferentiable cost functionals. Journal of Optimization Theory and Applications, 12(2):218-231, 1973.
[10] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Opera- tions research, 1225:11227, 2015.
[11] Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy as statistical learning. arXiv preprint arXiv:2202.04660, 2022..
[12] Stephen Boyd, Stephen Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[13] Xi Chen and Xiaotie Deng. Settling the complexity of two-player nash equilibrium. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS' '06), pages 261-272. IEEE, 2006.
[14] Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player nash equilibria. Journal the ACM (JACM), 5663) 2009.
[15] Ching-An Cheng and Byron Boots. Convergence of value aggregation for imitation learning. In International Conference Artificial Intelligence and Statistics, pages 1801-1809. PMLR, 2018.
[16] Ching-An An Cheng, Jonathan Lee, Ken Goldberg, and Byron Boots. Online learning with continuous variations: Dynamic regret and reductions. International Conference on Artificial PMLR, 2020.
Intelligence and Statistics, pages
(17) Ching-An Cheng, Xinyan Yan, Nathan Ratliff, and Byron Boots. Predictor-correetor policy optimization. In International Conference Machine Learning, pages 1151-1161. PMLR. 2019.
[18] Ching-An Cheng, Xinyan Yan, Evangelos Theodorou, and Byron Boots. Accelerating imitation learning with predictive models. The 22nd International Conference on Artificial Intelligence and Statistics, pages 3 3187-3196 PMLR, 2019.

---

[19] Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Conference on Learning Theory, pages G.I. Workshop and Conference Proceedings. 2012.
[20]
Thomas M Cover. Behavior of sequential predictors of binary sequences. Technical report, STANFORD UNIV CALIF STANFORD ELECTRONICS LABS, 1966.
[21] Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. On oracle-efficient pac rl with rich observations. Advances in neural information processing systems, 31, 2018.
[22] Constantinos Daskalakis, Paul W Goldberg, and Christos Papadimitriou. The complexity of computing nash equilibrium. SIAM Journal on Computing, 39(1):195-22) 2009.
[23] Hal Daumé, John Langford, and Daniel Marcu. Search- structured prediction. Machine learning, 75(3):297-325, 2009.
[24] Miroslav Dudík, Nika Haghtalab, Haipeng Luo, Robert Schapire, Vasilis Syrgkanis, and Jennifer Wortman Vaughan. Oracle-efficient online learning and auction design. Journal of the ACM (JACM), 67(5):1-57, 2020.
[25] Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang. Efficient optimal learning for contextual bandits. In Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, pages 169-178, 2011.
[26] Francisco Facchinei and Jong-Shi Pang. Finite-dimensional variational inequalities and com- plementarity problems. Springer Science & Business Media, 2007.
[27] Yoav Freund and Robert E Schapire. A decision-theoretie generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1): 19-139, 1997.
[28] Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang. Oracle-effccient online learning for beyond worst-case adversaries. arXiv preprint arXiv:2202.085599 2022.
[29] Elad Hazan and Tomer Koren. The computational power of optimization in online learning. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 221-141,77 2016.
[30] Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. Advances in neural information processing systems, 29, 2016.
[31] Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online optimization: Competing with dynamic comparators. In Artificial Intelligence and Statistics, pages 398-406. PMLR, 2015.
[32] Kshitij Judah, Alan Fern, Thomas Dietterich, and Prasad Tadepalli. Active imitation learning: Formal and practical reductions to iid learning. Journal of Machine Learning Research, 15(120):4155-414 2014.
[33] Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
[34] Sham M. Kakade and John Langford. Approximately optimal approximate reinforcement learning. In ICML, 2002.
[35] Sham M Kakade, Shai Shalev-Shwartz, and Ambuj Tewari. Regularization techniques for learning with matrices. The Journal of Machine Learning Research, 13(1):1865-180 2012.
[36] Liyiming Ke, Sanjiban Choudhury, Matt Barnes, Wen Sun, Gilwoo Lee, and Siddhartha Srini- vasa. Imitation learning as f-divergence minimization. In International Workshop on the Algorithmic Foundations of Robotics, pages 313-329, Springer, 2020.
[37] Hoang Le, Andrew Kang, Yisong Yue, and Peter Carr. Smooth imitation learning for online sequence prediction. International Conference on Machine Learning, pages 680-688, PMLR, 2016.
12

---

[38] Jonathan N Lee, Michael Laskey, Ajay Kumar Tanwani, Anil Aswani, and Ken Goldberg. Dynamic regret convergence analysis and an adaptive regularization algorithm for on-policy robot imitation learning. The International Journal of Robotics Research, 10:100111:12841111111 2021.
[39] Carlton E Lemke and Joseph Howson, Jr. Equilibrium points of bimatrix games. Journal of the Society for industrial and Applied Mathematics, 12(2):413-43, 1964.
[40] Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm. Information and computation, 108(2)2122-06) 1994.
[41] Brendan McMahan. A survey of algorithms and analysis for adaptive online learning. The Journal of Machine Learning Research, 18(1)3117-3116, 2017.
[42] Arkadi Nemirovski. Prox-method with rate of convergence o (1/t) for variational inequali- ties with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251, 2004.
[43] Francesco Orabona. A modern introduction to online learning, arXiv preprint arXiv: 2019.
[44] Takayuki Osa, Joni Pajarinen, Gerhard Neumann, J Andrew Bagnell, Pieter Abbeel, Jan Peters, et al. An algorithmic perspective on imitation learning. Foundations and Trends in Robotics, 7(1-2):1-179, 2018.
[45] Yunpeng Pan, Ching-An Cheng, Kamil Saigol, Keuntaek Lee, Xinyan Yan, Evangelos Theodorou, and Byron Boots. Imitation learning for agile autonomous driving. The International Journal of Robotics Research, 39(2-3):286-302 2020.
[46] Gilles Pisier. Remarques sur un résultat non publié de b. maurey. Séminaire d'Analyse fonctionnelle (dit" Maurey-Schwartz") pages 1-12, 1981.
[47] Dean A Pomerleau. Alvinn: An autonomous land vehicle in neural network. Advances in neural information processing systems, 1, 1988.
[48] Jian Qian, Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric. Concentration inequalities for multinoulli random variables. arXiv preprint arXiv:2001. /555, 2020.
[49] Nived Rajaraman, Yanjun Han, Lin Yang. Jingbo Liu, Jiantao Jiao, and Kannan Ramchandran. On the value of interaction and function approximation imitation learning. Advances in Neural Information Processing Systems, 34, 2021.
[50] Nived Rajaraman, Lin Yang, Jiantao Jiao, and Kannan Ramchandran. Toward the fundamental limits of imitation learning. Advances in Neural Information Processing Systems, 33:2914-2924, 2020.
[51] Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pages 993-1019, PMLR, 2013.
[52] Alexander Rakhlin and Karthik Sridharan. Bistro: An efficient relaxation-basee method for contextual bandits. In International Conference on Machine Learning, pages 1977-1985.
PMLR, 2016.
[53] Tyrrell Rockafellar. Convex analysis, volume 18. Princeton university press, 1970.
[54] Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference artificial intelligence and statistics, pages 661-668. JMLR Workshop and Conference Proceedings, 2010.
[55] Stephane Ross and J Andrew Bagnell. Reinforcement and imitation learning via interactive no-regret learning. arXiv preprint 1rXiv:1406.59999 2014.
[56] Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth international conference artificial intelligence and statistics, pages 627-635, 2011.
13

---

[57] S. SSaale--hwaatte Online Learning: Theory, Algorithms, and Applications. Hebrew University, 2007.
[58] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[59] Shai Chalev-Shwarde al. Online learning and online convex optimization. Foundations and trends in Machine Learning, 4(2):107-194, 2011.
[60] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mas- tering the game of go with deep neural networks and tree search. nature, 529(7587):444-889 2016.
[61] Jacob Steinhardt and Perey Liang- Adaptivity and optimism: An improved exponentiated gradient algorithm. In International Conference on Machine Learning, pages 1559-1601. PMIR, 2014.
[62] Wen Sun, Anirudh Vemula, Byron Boots, and Drew Bagnell. Provably efficient imitation learning from observation alone. In International conference machine learning, pages 6036-6045. PMLR, 2019.
[63] Wen Sun, Arun Venkatraman, Geoffrey J Gordon, Byron Boots, and J Andrew Bagnell. Deeply aggrevated: Differentiable imitation learning for sequential prediction. In International Confer- ence on Machine Learning, pages 3309-3318. PMLR, 2017.
[64] Umar Syed and Robert E Schapire. A game-theoretic approach to apprenticeship learning. Advances neural information processing systems, 20, 2007.
[65] Umar Syed and Robert E Schapire. A reduction from apprenticeship learning to classification. Advances in neural information processing systems, 23, 2010.
[66] Vasilis Syrgkanis, Akshay Krishnamurthy, and Robert Schapire. Efficient algorithms for adversarial contextual learning. In International Conference on Machine Learning, pages PMLR, 2016.
[67] Vasilis Syrgkanis, Haipeng Luo, Akshay Krishnamurthy, and Robert E. Schapire. Improved regret bounds for oracle-based adversarial contextual bandits. Advances in Neural Information Processing Systems, 29, 2016.
[68] Tianhao Wang, Si Chen, and Ruoxi Jia. One-round active learning. arXiv preprint arXiv:2104.1 / 1843, 2021.
[69] Ziyu Wang, Josh S Merel, Scott E Reed, Nando de Freitas, Gregory Wayne, and Nicolas Heess. Robust imitation of diverse behaviors. Advances in Neural Information Processing Systems, 30, 2017.
[70] Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. Inequalities for the 11 deviation of the empirical distribution. HewlettPaccard Labs, Tech. Rep, 2003.
[71] Tian Xu, Ziniu Li, and Yang Yu. Error bounds of imitating policies and environments. Advances in Neural Information Processing Systems, 33:15737-15749, 2020.
[72] Liu Yang and Jaime Carbonell. Buy-in-bulk active learning. Advances in neural information processing systems, 26, 2013.
[73] Constantin Zalinescu. Convex analysis in general vector spaces. World scientific, 2002.
[74] Brian D Ziebart, Andrew L Maas, J Andrew Bagnell, Anind K Dey, et al. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pages 1433-1438. Chicago, IL, USA, 2008.
14

---

Checklist
1. For all authors...
(a) Do the main claims made the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See Section 3.1 Section
3.2 Section
4 and Section
(b) Did you describe the limitations of your work? Yes]] See Section and Section
2
Section
3.2 Definition |
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
2. If you are including theoretical results...
(a) Did you state the full assumptions of all theoretical results? [Yes] See Section 2
Section[.22 Definition [
(b) Did you include complete proofs of all theoretical results? [Yes] Please refer to Appendix for detailed proofs.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URLY? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect to the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you 're
using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board
(IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "iM-SYwCB_8", "reviewer": "Reviewer_yqpJ", "summary": "This paper investigates the fundamental feasibility and statistical limits of designing oracle-efficient regret minimization algorithms in the setting of classification-based online imitation learning. Specifically, the paper shows that any proper algorithm is unlikely to achieve a sublinear regret (similar to the Cover's impossibility theory). Inspired by this observation, the paper propose an improper online learning framework that is equivalent to online linear optimization with the help of a mixed policy class. This framework allows us to design oracle0efficient algorithms with different sample/interaction round complexities.", "questions": "I note that theorem 4 is based on the assumption that the expert's feedback is of the form $\\zeta_E(s,a) = A^E(s,a)$. How does this choice affect the results and can we use other choices like direct expert annotation (zero-one loss, which seems more practical or easier to obtain in practice)?", "limitations": "Limitations and potential negative societal impact of their work have been properly discussed.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The paper is a solid theoretical work that studies the fundamental limitations of classification-based online imitation learning and propose a new algorithmic framework to bypass the fundamental challenges.\n- Good presentation quality with nice discussions about the connection and differences to previous works.\n\nWeaknesses\n- I do not find any technical issues. It would be very helpful if there are some experimental results (at least on some toy settings) to demonstrate the practical value as well as to make the key insights easier to understand.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "gPvj4XzlZQs", "reviewer": "Reviewer_vCUw", "summary": "The authors provide (1) an impossibility result for obtaining sublinear regret in general online learning settings, (2) present an online linear optimization algorithm (LOGGER) which uses policy mixtures to improve sample / complexity interaction guarantees over behavioral cloning algorithms, and (3) they show that achieving sublinear dynamic regret is still impossible in the LOGGER framework.\n\n\n\n", "questions": "## Abstract \n1. Please fix the spacing in the abstract. \n\n## Background\n1. The assumption about labeling of the expert examples seems unrealistic. In most settings checking if something is an expert action requires the same effort as just providing the binary value provided in your framework (unless you are using human in the loop RL for language tasks possibly). It makes sense why this is a much more difficult form of feedback to optimize with, but making the distinction between this and more common assumptions should be included. \n2. Theorem 4 seems similar to impossibility results from the reinforcement learning theory literature. This impossibility result is also somewhat confusing considering your previous result which uses effectively they same type of feedback, with what amounts to less information (e.g. binary feedback telling you if you were wrong, versus feedback telling you if you explicitly how much worse you were then the expert). Can you clarify intuitively why your result makes sense. \n5. Can you clarify the statement made in line 206 \"equivalent to drawing a freshly new policy ...\", are you sampling without replacement from the set B? If so does this not enforce additional requirements on the policy class not included in your list of assumptions?\n6. Proposition 6 seems strictly worse then the results presented in [1]\n7. Does the assumption regarding mu recoverability implicitly impose constraints on the space of MDPs that are not likely to be realistic in practice.\n \n## Efficient algorithms with static regret guarantees\n1. Text error on line 261 \n \n## Potentially relevant citations\n[1] https://arxiv.org/abs/2007.02520\n\n[2] https://arxiv.org/abs/1809.02864\n\n[3] https://arxiv.org/abs/2006.06835", "limitations": "The most important limitation of this work, is that it proposes a framework which creates a trade off between sample efficiency and oracle query efficiency, but provides no experimentation of such an algorithm. If the multiple variants of LOGGER are not possible to implement in practice, this should be stated explicitly. If they are, a simple toy experiment would be useful to illistrate to the reader how such an algorithm function, and whether or not there are any hidden constants in the bound or the algorithm definition which make it intractable in practice. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n1. The authors combined analysis which composes sample complexity and interaction round complexity is extremely interesting, and to my knowledge novel in the area of online imitation learning.\n2. The list of assumptions required in proving the results given by the authors is clear and precise. \n3. The use of \"separator sets\" by the authors seemingly opens up a couple fun algorithmic questions that can take advantage of existing research from support vector machines and active sets. \n4. Proposition 2 creates an interesting link between exploration in online imitation learning and recent results in over-parameterization in online convex optimization~[1,2].\n\n## Weaknesses \n2. Proposition 6 seems like a restatement of one of the theorems in [1], or perhaps a special case. \n3. The assumption regarding mu recoverability seems to implicitly impose some constraints on the space of MDPs that are not likely to be realistic in practice. \n5. All analysis are completed in a a discrete finite state-action Markov decision process, making the utility of such analysis unlikely to be directly applicable to practical applications and studies.\n6. No experimentation or code is included with the work, making it difficult to determine if the algorithms proposed are actually possible to implement.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cWkSL-FiYLt", "reviewer": "Reviewer_7TV7", "summary": "This paper studies the fundamental problems of classification-based online imitation learning. A framework called COIL is developed, and several contributions are achieved. First, like Cover's impossibility result, this paper shows there exists a hard instance, such that any proper online learning algorithm must suffer a sublinear regret. Second, an algorithmic framework called COIL is developed, which reduces COIL to online linear optimization. Third, two algorithms, LOGGER-M and LOGGER-ME, are proposed with provably efficient sample and interaction round complexities. This paper argues that these algorithms can be better than BC. Finally, this paper discusses why efficient dynamic regret minimization is inapplicable in the LOGGER framework.\n\n\n====\n\nAfter discussion, the authors have addressed my concerns. I am glad to see that this paper makes a remarkable step in the non-realizable cases. I believe such results could help us better apply imitation learning algorithms in practice. Accordingly, I raise my score from 5 to 7.", "questions": "- Can the authors help explain the computation benefits of LOGGER-M and LOGGER-ME?\n\nIn Section 3.2, this paper argues that regret-minimization algorithms like Hedge has a computation issue, i.e., O(B) complexity. I believe this is not a big issue. Furthermore, I do not find the discussion about the computation efficiency of LOGGER-M and LOGGER-ME in Section 4. I hope the authors can help explain this point. \n\n- What are new messages compared with the prior work [2]?\n\nI find this paper lacks a discussion with the prior work [2], in which it is shown that (with realizability assumption), an online IL algorithm can solve the COIL studied in this paper. Furthermore, a separation between the online and offline settings is established to help the readers understand the fundamental limit. I wonder whether there are new messages in this paper. \n\n- Is the theoretical guarantee for BC tight?\n\n[1] proved that the expert annotation complexity for BC should be $\\widetilde{O}(H^2 S/\\epsilon^2)$, if there is no approximation error. I believe this result is true even though there is an approximation error. The analysis in the appendix may be loose. For the approximation error of BC, due to the $\\mu$-recoverability assumption, I guess the tight dependence should be $\\mu H$ rather than $H^2$.  \n\n--- \n\n\n[2] Rajaraman, Nived, et al. \"On the Value of Interaction and Function Approximation in Imitation Learning.\" *Advances in Neural Information Processing Systems* 34 (2021): 1325-1336.", "limitations": "This paper studies classification-based online imitation learning (COIL). By the powerful techniques from the online optimization literature, new theoretical results are obtained in the context of imitation learning. Some theoretical results can corroborate some discussions in [3]. Though this paper has fruitful results, I am worried about the implications of these results. \n\nWhat are new messages? (compared with the old paper like DAGGER and the new paper [2]) How can the theoretical results of this paper guide practice? This question is related to the remark in the conclusion part. What kind of experiments do you want to conduct to empirically evaluate algorithms?\n\nThis paper is well written. A minor issue is a claim in the introduction (Line 30 and 31). In general, interactive IL can not be better than its offline counterpart; see [1]. Only under suitable assumptions, interactive IL can have superior performance; see [2]. A side message is that for tasks similar to the lower bound in [1], online algorithms cannot help. This message is important for practitioners. Please consider clarifying this misleading claim.\n\nI am willing to recommend accepting this paper if the above concerns can be well-addressed. \n\n---\n\n[3] Spencer, Jonathan, et al. \"Feedback in imitation learning: The three regimes of covariate shift.\" *arXiv preprint arXiv:2102.02872* (2021).", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n- Several new theoretical contributions to the online imitation learning field. Like Cover's impossibility result, Theorem 4 shows that without reachability or randomization, it is impossible to achieve a sublinear regret.\n- By considering mixed policy classes, new algorithms LOGGER-M and LOGGER-ME are developed. \n\n**Weakness** \n\n- Motivation is weak. This paper claims that the prior frameworks like DAgger have two issues: 1) applying rule-based policies is hard; 2) optimization of such policies is tricky (because of the convex realization). These issues depend on specific applications. It seems that they are not fundamental issues.\n- The BC's guarantee is weaker, and the improvements over BC are questionable. The direct reduction of BC to supervised learning yields a loose bound, as shown in [1]. The expert annotation complexity of BC should be \\widetilde{O}(H^2/\\epsilon) rather than \\widetilde{O}(H^4/\\epsilon^2). \n\n---\n\n[1] Rajaraman, Nived, et al. \"Toward the fundamental limits of imitation learning.\" *Advances in Neural Information Processing Systems* 33 (2020): 2914-2924.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Elw2ts8titl", "reviewer": "Reviewer_cDuK", "summary": "This paper studies the problem of classification-based online imitation learning, and shows a negative result that any proper learning fails to achieve sublinear regret.\nThe main contributions include:\n  - Theoretical guarantee for drawbacks of proper online learning\n  - An improper online learning algorithmic framework\n  - Efficient algorithms to deal with computational hardness\n", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strengths\n  - The paper proves that proper learning fails to achieve sublinear regret in COIL setting.\n  - The paper proposes a clear convex combination to construct mixed policy class so that online regret minimization in IL becomes an online linear optimization problem.\n  - The paper proposes Theorem 13 to show that all problems in PPAD are solvable in randomized polynomial time under some specific circumstances in COIL setting.\n\n- Weaknesses\n  - [12] already gives a general online convex optimization formulation for online IL, so it seems that linear optimization is covered.\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept