Proximal Point Imitation Learning
Authors: Luca Viano
Angeliki Kamoutsi
Gergely Neu
Igor Krawczuk
Volkan Cevher
Venue: NeurIPS 2022 Accept (2022)
Keywords: imitation learning theory
learning from demonstrations
proximal point method

Abstract: This work develops new algorithms with rigorous efficiency guarantees for infinite horizon imitation learning (IL) with linear function approximation without restrictive coherence assumptions. We begin with the minimax formulation of the problem and then outline how to leverage classical tools from optimization, in particular, the proximal-point method (PPM) and dual smoothing, for online and offline IL, respectively. Thanks to PPM, we avoid nested policy evaluation and cost updates for online IL appearing in the prior literature. In particular, we do away with the conventional alternating updates by the optimization of a single convex and smooth objective over both cost and $Q$-functions. When solved inexactly, we relate the optimization errors to the suboptimality of the recovered policy. As an added bonus, by re-interpreting PPM as dual smoothing with the expert policy as a center point, we also obtain an offline IL algorithm enjoying theoretical guarantees in terms of required expert trajectories. Finally, we achieve convincing empirical performance for both linear and neural network function approximation.

Proximal Point Imitation Learning
Luca Viano LIONS, EPFL Lausanne, Switzerland luca. vianodepf1.ch ch
Angeliki Kamoutsi
ETH Zurich Zurich, Switzerland kamoutsaßethz.co ch
Gergely Neu
Igor Krawezuk LIONS, EPFL Lausanne, Switzerland
Volkan Cevher LIONS, EPFL
Universitat Pompeu Fabra Barcelona, Spain gergely.neu@gne neuggmiinummmai..com com
Lausanne, Switzerland volkan. celkkanncevherrppl.chh
igor. krawczuk@epfI.ch
Abstract
This work develops algorithms with rigorous efficiency guarantees for infi- nite horizon imitation learning (IL) with linear function approximation without restrictive coherence assumptions. We begin with the minimax formulation of the problem and then outline how to leverage classical tools from optimization, in particular, the proximal-point method (PPM) and dual smoothing, for online and offline IL, respectively. Thanks to PPM, we avoid nested policy evaluation and cost updates for online IL appearing the prior literature. In particular, we do away with the conventional alternating updates by the optimization of single convex and smooth objective over both cost and Q-functions. When solved inexactly, we relate the optimization errors to the suboptimality of the recovered policy. As an added bonus, by re-interpreting PPM as dual smoothing with the expert policy as a center point, we also obtain an offline IL algorithm enjoying theoretical guarantees in terms of required expert trajectories. Finally, we achieve convincing empirical performance for both linear and neural network function approximation.
Introduction
This work is concerned with the prototypical setting of imitation learning (IL) where
1. An expert provides demonstrations of state-action pairs in an environment. The expert could optimal or suboptimal with respect to an unknown cost/reward function.
2. The learner chooses distance measure between its policy be learned and the expert empirical distribution estimated from demonstrations.
3. The learner employs an algorithm, which additionally may or may not use interactions with the environment, minimize the chosen distance.
In IL, the central goal of the learner is to recover a policy competitive with expert with respect to the underlying unknown cost function. IL is important for several real world applications like driving [62], robotics [88]. and economics/inance [27] at the expense of following resources: (R 1) expert demonstrations, (R2) (optional) interactions with the environment where the expert collected the demonstrations, and (R3) computational resources for solving the problem template.
Interestingly, while there is amount of literature using optimization ideas the IL problem
template, i.c. Lagrangian duality [5] 38 59 63 64], resource guarantees are still widely missing since the optimization literature focuses on the resource (R3) where IL literature mainly focuses on
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the first two resources (R1) and (R2). Our work leverages deeper connections between optimization tools and IL by showing how classical optimization tools can be applied in a linear programming formulation of II. problem guaranteeing efficiency in all (R1), (R2), (R3).
This work aims at designing an algorithm enjoying both theoretical guarantees and convincing empirical performance. Our methodology is rooted in classical optimization tools and the LP approach MDPs. More precisely, the method uses the recently repopularized overpa- rameterization technique to obtain the Q-function as a Lagrangian multiplier [77 14] and solves the associated program using a PPM update with appropriately chosen Bregman divergences. This results to an actor-critic algorithm, with the key feature that the policy evaluation step involves optimization of a single concave and smooth objective over both cost and Q-functions. In this way, we avoid instability or poor convergence due to adversarial training [ST [22 77 [005]. and can also recover an explicit cost along with Q-function. We further account for potential optimization errors, presenting an error propagation analysis that leads to rigorous guarantees for both online and offline setting. For we provide explicit convergence rates and error bounds for the suboptimality of the learned policy, under mild assumptions, significantly weaker than those found in the literature until now. To our knowledge, such guarantees in this setting are provided for the first time. Finally, we demonstrate that our approach achieves convincing empirical performance for both linear and neural network function approximation.
Our contributions:
the context of linear MDPs [4 121 55 22
116
X4
Related Literature. The first algorithm addressing the imitation learning problem is behavioral it has low efficiency in terms of expert proposed to cast the problem as inverse reinforcement learning (RL.. IRI. improves the efficiency in terms of expert trajectories, at the cost of introducing the need of running reinforcement learning (RL) repetitively, which can be prohibitive in terms of environment samples (R2) and computation (R3). A successive line of work started with (112) highlights that repeated calls to an RL routine can be avoided. This work inspired generative adversarial imitation learning (GAIL) S1 and other follow-up works [38 [5
cloning 993. Due to the covariate shift problem 98
99),
trajectories (R 1). To address this issue, [100 87 4
95
111
85 123
68, 69
63, 64] that leveraged optimization tools like primal-dual algorithms but did not try to deepen the optimization connections to derive efficiency guarantees in terms of all (R (R3). Finally, recent line of work [40] [57 in IL bypasses the need of optimizing over cost functions and thus avoids instability due to adversarial training. Although these algorithms achieve impressive empirical performance in challenging high dimensional benchmark tasks, they are hampered by limited theoretical understanding. This is the fundamental difference from our work, which enjoys both favorable practical performance and strong theoretical guarantees.
Existing model-free IL theoretical papers with global convergence guarantees assume either a finite horizon episodic MDP setting [70], or tabular MDPs [055, or the infinite horizon case but with restrictive assumptions, such as linear quadratic regulator setting (2I), continuous kernelized nonlinear regulator 226 566, access generative model and coherence assumption on the choice of features [58] 14). bounded strong concentrability coefficients [122] or a linear transition law that can be completely specified by mimte-dimensional matrix 770. On the other hand, we provide convergence guarantees and error bounds for the context of linear MDPs 14 121 55 22 16 7 84] under mild feature excitation condition assumption. Despite being linear, the transition law can still have infinite degrees of freedom. To our knowledge, such guarantees in this setting are provided for the first time.
Our work applies the technique known as regularization in the online learning literature 6 103
and Bregman proximal-pon
or smoothing in optimization literature 197| 82) to the LP formulation
for MDPs 773 35| 36 17 48 49 33
34 102, 91, 92
T 65 30 79 115 67 13 31
55 [06]. From
this perspective, we can see Deep Inverse Q- Q-Learning [57] and IQ- Learn [40] that consider entropy
regularization in the objective as smoothing using uniform distribution as center point. In our case, center point the previous iteration of the algorithm (for the online case) or the expert
we instead (for the offline case).
From the technical point of view, the most important related works are the analysis of REPS/Q- REPS 190) [4. [9] and O-REPS [124] that first pointed out the connection between REPS and PPM. We build on their techniques with some important differences. In particular, while in the LP formulation of RL, PPM and mirror descent [[5] 47 are equivalent, recognizing that they are not equivalent in IL is critical for stronger empirical performance. As an independent interest, our techniques can be used to improve upon the best rate for REPS in the tabular setting [89] and to
2

---

extend the guarantees to linear MDPs. In order to discuss in more detail our research questions and situate them among prior related theoretical and practical works, we provide Appendix A an extended literature review.
2 Background
2.1 Markov Decision Processes
The RL environment and its underlying dynamics are typically abstracted as an MDP given by tuple (S,A, P. Vu. c, y, where S is the state space, is the action space, P: S'x A + As is the transition law, Vy E As is the initial state distribution, c E [o, |]|S|[Al is the cost, and ? E (0, 1) is the discount factor. For simplicity, we focus on problems where S and A are finite but too large to be enumerated. stationary Markov policy x: S - A interacts with the environment iteratively, starting with an initial state So ~ Vo. At round t, if the system is at state an action 0₂- ~ rT-(s=) is sampled and applied to the environment. Then a cost d(s, a) incurred, and the system transitions to the next state 8t+1 ~ P(-ls,a.. The goal of RL is to solve the optimal control problem PCe - ming Pc(T), where Pe( _ (1- (Vu, Ve) is the normalized total discounted expected cost of n
The state value function V
RISI of n, given cost c, defined by (s) - ET ( where Eg denotes the expectation with respect the trajectories gen- crated by x starting from 80 = s. The optimal value function V E R| is defined by (s) _ min, (s). The optimal state-action value function Q E R|SIIAI, given by (= a) & a(s.a) + ? E. (s')P a), is known to characterize optimal behaviors. Indeed Va is the unique solution to the Bellman optimality equation (s) = min, Qr(s, a). In addition, any deter- ministic policy ne (s) = arg min, (s(s, a) is known be optimal.
For every policy æ, we define the normalized state-action occupancy measure Ps E AS by Ma (s, a) (1 - 7) - 7 PP, [st s, O2 = a], where PT, [-] denotes the probability of an event when following starting from Su Vu- The occupancy measure can be interpreted as the discounted visitation frequency of state- state-action pairs. This allows us to write Pe(TT) = (Mx c).
2.2 Imitation Learning
Similarly to RL, the IL problem is posed in the MDP formalism, with the critical difference that the true cost Ciee is unknown. Instead, we have access to a finite set of truncated trajectories sampled i.i.d. by executing an expert policy Te in the environment. The goal is to learn a policy that performs better than Te with respect to the unknown Cuue- To this end, we adopt the apprenticeship learning formalism [4. 012 50 5 105). which carries the assumption that Cine belongs to class of cost functions C. We then seek an apprentice policy TA that outperforms the expert across C by solving the following optimization problem
5* - min de Tg).
where de(T, mE)
maxeec (Pe(T) (e()))) defines the C-distance between and Te [TT, 28 122 70). Then, TA satisfies the goal of IL, since it holds that Pe.. (TA) Pen. (TE) <
S 0. Intuitively, the cost class C distinguishes the expert from other policies. The maximization
in || assigns high total cost to non-expert policies and low total cost to me (51). while the
minimization aims to find the policy that matches the expert as close as possible with respect to de.
By writing de in its dual form de (M4 mmgg) A maxege ( ( e)): ). it can be interpreted as an integral probability metric [80 60) between the occupancy measures fh and M Depending on how C is chosen, de turns to a different metric of probability measures like the 1-Wasserstein distance 117 for C = Lip, (S x A), the total variation for C = (c ||<|| < 1}. or the maximum mean diserepancy for = {c |c| < 1}. where Lip, (S A) denotes the space of 1-Lipschitz functions on S x A, and ||- I denotes the norm of reproducing kernel Hilbert space H. [104).
In our theoretical analysis, we focus on linearly parameterized cost classes [111 112 51
105
of the form C A (c. 2 Em witb; w E W), where { C !SI-AI are fixed feature vectors, such that || < 1 for all i E [m]) and W is a convex constraint set for the cost weights w. This
3

---

assumption is not necessarily restrictive as usually in practice the true cost depends on just a few key properties, but the desirable weighting that specifies how different desiderata should be traded-off is unknown [. Moreover, the cost features can be complex nonlinear functions that can be obtained via unsupervised learning from raw state observations 20 29
&ml gives _ (Po, (TT)) ................................ Po... (TE)) E R" of policy Then, by choosing W to be the E2 unit ball BiTh _ {w E R ||w 12 S 13 4 we get a feature expec- lation matching objective (T, Tag) = l (TT) P (EE) (TE))l while for W being the probability sim- Tin 2 we have worst-case excess cost objective dc( Fag) [ (po. (T)
The matrix T - [
rise a feature expectation vector (FEV) Pa (TT)
plex A [m]]
Pe. (TT)
For clarity, we will replace by w in the notation of the quantities defined in Section 2.1
3 A Q-Convex-Analyli Viewpoint
Our methodology builds upon the convex-analytic approach to AL, first introduced by 112). with the key difference that we consider different convex formulation that introduces Q-functions as slack variables. This allows to design a practical scalable model-free algorithm with theoretical guarantees.
(B HTTH = (1 - v) μ 2 0} be the state-action polytope, where P is the vector form of P, i.e., P(s.a). & P(s'|s, a), and B is a binary matrix defined by B(a.a). - 1 if s s', and B(ssa),s' _ 0 otherwise. The linear constraints that define the set 3. also known as Bellman flow constraints, precisely characterize the set of state-action occupancy measures.
Let 3 A {ur E R |S|AA|
s'.
Proposition (94). We have that μ E 3 if and only if there exists unique stationary Markov policy T such that μ uz u E F then the policy TH (a)x)) _ ExeaM(raa") has occupancy measure p.
Using Proposition 1 and the dual form of the C-distance de (M, Mmg) = maxwew (n Te Cw). it follows that ④ is equivalent to the primal convex program 5* = min (de(p, (2 μ E 8). In particular for W = [m) and by using epigraphic transformation,
end up with an L.P
program 112). while for W = BTT we get a quadratic objective with linear constraints 44)
A slight variation of the above reasoning is to introduce mirror variable d and split the Bellman flow constraints in the definition of 3. We then get the primal convex program
min (de (1s, (m)) (1,, d) E M),. (p.d)
(Primal)
where the new polytope is given by 20 & {(r. d) BTd TTd= (1-7) p= d, d 2 0}. This overparameterizzatoon trick has been first introduced by Mehta and Meyn [76) and has been recently revisited by [14 84 67 & 77 7T). A salient feature of this equivalent formulation is that introduces Q-function as Lagrange multiplier to the equality constraint d = μu, and so lends itself to data-driven algorithms. To motivate further this new formulation, in Appendix C we shed light to its dual and provide an interpretation of the dual optimizers. In particular, when W BTT, we show that (V+
Quee.
Wine) is a dual optimizer.
Wine
For our theoretical analysis we focus on the linear MDP setting [55]. we assume that the transition law is linear in the feature mapping. We denote by Φ(s, a) the (s, a)-th row of 4b
Assumption 1 (Linear MDP). There exists a collection of m probability measures = (Wl, .ul...... Wm) on S, such that P(-|s, a) = (w-(-, o6ss, a)), for all (s, a). Moreover Φ(5, a) [mm] all (s, a).
Assumption D essentialy says that the transition matrix P has rank most m, and P = &M for some matrix M E [ It is worth noting that in the case of continuous MDPs, despite being linear, the transition law P(-|s, a) can still have infinite degrees of freedom. This is a substantial difference from the recent theoretical works on II. (70 [05) which consider either a linear quadratic regulator, or a transition law that can be completely specified by a dimensoameniional matrix such that the degrees of freedom are bounded.
Assumption | enables us to consider relaxation of (Primal). In partieular, we aggregate the constraints μ d by imposing & = T instead, and introduce a variable À = TT.. that À lies in the mn-dimensional simplex Am)] Then, we get the following convex program
- It follows
S = min max (A, w) - (pe cw) I (2, d) E M.ph
(Primal')
(A.d) weW

---

where Di -
{(A d
B 7MTA -1-1111000 Voo. X D'd. X E [m)] d E Asxa). for linear MDPs, the of occupancy measures & can be completely
As shown in 14 83 characterized by the set a (c.f., Proposition 2). While the number of constraints and variables in (Primal') p intractable for large scale MDPs, in the next paragraph, we show how this problem can be solved using proximal point scheme.
4 Proximal Point Imitation Learning
By using Lagrangian decomposition, we have that (Primal' equivalent to the following bilinear saddle-point problem
min max (y, AxAA b) XEX yEy
(SPP)
where A
(2m+ (0 (2m=|()(((++((11))) and b R(m+(S(+(S(A)) are appropriately defined (see Ap- pendix x - [A d A [wt, VT, TT, X [m) Asx and - W R!S! R
Since in practice we do not have access to the whole policy TE. but instead can observe a finite (1) (1)
of i.i.d. sample trajectories Dr {(=0)) dg ,x(") 00
(1) HH an ) TE, define the ,...,
(1)
vector b by replacing P* (TE) with its empirical counterpart Ps (TE) (by taking sample averages) in the definition of b. We then consider the empirical objective f(x) - maxyey (y, (x,Ax= + b and
apply PPM on the decision variable x. For the X-variable we use the relative entropy D(A & A(i) Ea X(3) log x(i))> while for the occupancy measure d
the conditional relative entropy
(dllad) & Es. (i, d(s.a) (8,,aloog log ma(als)
With this choice we can rewrite the PPM update
(ar(a)))"
A
+ 6 D(( + - (d(ld)), (2)
(A++1, = min max Y
(E VEY
where used primal feasibility replace λ with TTd the center point of the relative entropy. PPM is implicit, meaning that it requires the evaluation of the gradient at the next iterate X Such requirement makes it not implementable in general. However, in the following, describe proce- dure to apply proximal point to our specific fxx). The following Proposition summarizes the result. Proposition For a parameter 0 E IRT we define the logistic state-action value function Qo R|S||A| by Qa A +0,, and the k-step logistic state value function V R|ST by
V
A
log Emdi (als)e Qo((n.) ((l))))=o((xoo))
Moreover. we define the k-step reduced Bellman error function ow. E R by 8 - W 0. Then, the PPM update (Xi, d in 2 is given by
Xg(1) x ( d 1
(3)
maz (als) x od. (a|s)e (o2o((0)))
(4)
where (wi, 0%) the maximizer over W Rm of the k-step logistic policy evaluation objective
Ga(w, 0) log
c de (i)e 160.0(1) (1) + (1-7) vτ) - (px (T)) w)
(5)
Moreover, it holds that (w( 0 = -Xi. - (p+ ( w + oj
D
Hdd H(ddldde-1) If in addition Assumption holds, then di is valid occupancy measure, i.e.,
å E & and so di M
The proof of Proposition is broken down into sequence of lemmas and is presented in Appendix employs an analytical- g y X' given by
A
1 D(A TT + - H(dlldd),
1
g y xx)
A
mrg
A
6
+
d
dEAsAA
7
5

---

and a max- oracle h : X' + y given by h(x) _ arg maxyey (v, A)(y: (x) where we used Dn to compact the two divergences. By noting that the PPM update Equation (2) can be rewritten as x g( ( xx ); xx), its analytical computation is reduced to the characterization of the come from the analytical-oren
two aforementioned oracles. In particular, the updates (3)
while (5) is the objective of the max-oracle.
The choice of conditional entropy as Bregman divergence for the variable living in the probability simplex is standard in the optimization literature and is known to mitigate the effect of dimension. In particular, as noted in [85,, the classic REPS algorithm [90] can be seen as mirror descent with relative entropy regularization. On the other hand, the choice of conditional entropy as Bregman divergence for the d variable is less standard and has been popularized by Q-REPS [14). Such particular divergence leads to an actor-critic algorithu that comes with several merits. By Proposition 2 it is apparent that we get analytical softmin updates for the policy va rather than the occupancy measure d. Moreover, these softmin updates are expressed in terms of the logistic Q-function and do not involve the unknown transition matrix P. Consequently, we avoid the problematic occupancy measure approximation and the restrictive coherence assumption on the choice of features needed in [13 58) as well as the biased policy updates appearing in REPS 900 89]. addition, the newly introduced logistic policy evaluation objective (w, 0) has several desired properties. It is concave and smooth in (w, 0) and has bounded gradients. Therefore, it does not suffer from the pathologies of the squared Bellman error [78 and does not require heuristic gradient clipping techniques. Moreover, unlike (58) it allows a model-free frree implementation without the need for a generative model (see Section 4.1)
We stress the fact that the max oracle of our proximal point scheme performs the cost update and policy evaluation phases jointly. This is a rather novel feature of our algorithm that differs from the separate cost update and policy evaluation step used in recent theoretical imitation learning works 212 IOS, [70.. Our joint optimization over cost and Q-functions avoids instability due to adversarial training and can also recover an explicit cost along with the Q-function without requiring knowledge or additional interaction with the environment (see Section 5)
worth noting that application of primal-dual mirror descent to (SPP) does not have this favorable property. While in the standard MDP setting, proximal point and mirror descent coincide because of the linear objective, in imitation learning proximal point optimization makes difference. In Appendix KK] we include a more detailed discussion and numerical comparison between PPM and mirror descent updates.
4.1 Practical Implementation
Exact optimization of the logistic policy evaluation objective is infeasible in practical scenarios, due to unknown dynamics and limited computation power. In this section, we design a practical algorithm that uses only sample transitions by obtaining stochastic (albeit biased) gradient estimators.
Proposition gives rise to Proximal Point Imitation Learning (P'IL), a model-free actor-critic IRL algorithm described in Algorithm [ The key feature of p2 IL is that the policy evaluation step involves optimization of a single smooth and concave objective over both cost and state-action value function parameters. In this way, we avoid instability or poor convergence in optimization due to nested policy evaluation and cost updates, as well as the undesirable properties of the widely used squared Bellman error. In particular, the kth iteration of I'IL consists of the following two steps (i) (Critic Step) Computation of an approximate maximizer (Wk, 02) so arg max o G& (w, 0) of the concave logistic policy evaluation objective, by using a biased stochastic gradient ascent subroutine; (ii) (Actor Step) Soft-min policy update T (a(s) x Tals( e -aQa, (s.a) expressed in terms of the logistic -ffuncioon.
The domain θ in Algorithm is the l with appropriately chosen radius D to be specified later (see Proposition 3). Moreover, (x) A arg minyce |xy (resp. llw(w)) denotes the Euclidean projection of x (resp. w) onto θ (resp. W).
In order to estimate the gradients Ve GA (w, θ) and V GR (w, 0) we invoke the Biased Stochastic Gradient Estimator subroutine (BSGE) (Algorithm [ given in Appendix H By using the linear MDP Assumption [ and leveraging ridge regression and plug-in estimators, the proposed stochastic stochasti gradients can be computed via simple linear algebra with computational complexity poly(m, n()), independent of the size of the state space.

---

Algorithm 1 Proximal Point Imitation Learning: P²IL( Dr, K, K,
Input: Feature matrix h, expert demonstrations Dg. number of iterations K, step sizes v and a, number of SGD iterations T, SGD learning rates 3 {Be 1T= number-of-samples function
n IN + IN
Initialize лo uniform distribution over A Compute the empirical FEV Ps (TF) using expert demonstrations DF for = K do
// Critic-step (policy evaluation) Initialize 0x 0 and W4.0
Run Tk-1 and collect i.i.d. samples B3 ( 22-1 8 === (m)
(n) (8) M(T)
such that
(sk-1 k-1 M and ((n) P(-1s xk-1)
for t = . do
Compute biased stochastic gradient estimators
(Vw Ox,e), A VOGR(WE. Ok,)) = BSGB(KK WK.t, Ox,,,(()) n())
WA.++1 (ww(wx, + 3, (WW,,, Os.t))
Og.r41 = Ile (Ox, + B.Vo (Wa,,, Ok.z))
end for
(Wx, 0%) ( ΣT 1=1 Wk,t E Qk.s)
// Actor-step (policy update)
Policy update: Te(a(s) x 1 aaQa (x.a) end for
Output: Mixed policy Re of { (Tkkk]]
4.2 Theoretical Analysis
The first step in our theoretical analysis is to study the propagation of optimization errors made by the algorithm on the true policy evaluation objective. In particular at each iteration step k the ideal policy evaluation update (w3, 0%) and the ideal policy update गे given by (wi, 0%)
arg maxw,e e Gi w, 0), and = T -a(Qo -V, (s)) On the other hand, consider 0%) (WA, 0x) = Eg. the corre- sponding policy Tı given by mæ = (a]=(a -aQQ,, Va, (+)) and let d - MAT We denote by R the extracted mixed policy of { We are interested in upper-bounding the suboptimality gap de ( K, mE) of Algorithm I a function of Eg. To this end, we need the following assumption.
the realised policy evaluation update (Wx, 02) such that GR (w
Assumption 2. holds that Amin (L),, ((s, (s, a))(s,a)) )) 2 for all [K].
Assumption 2 states that every occupancy measure de induces a positive definite feature covariance matrix, and every policy Jy explores uniformly well in the feature space. This assumption is common in the RL theory literature [2] 46 37 66 It is also related to the condition of persistent excitation from the control literature 81
The following proposition ensures that max 6= G& (w, 0) = max exw (w, 0). There- fore, this constraint does not change the problem optimality, but will considerably accelerate the convergence of the algorithm by considering smaller domains.
Proposition 3. There exists a maximizer 0% such that |10] S
1+ & A D.
We can now state our error propagation theorem.
loog 2mm 5²
Theorem Let मe be the output of running Algorithm for K iterations, with mg 2
expert
trajectories length H 2 log( Let C'
2a + 1-
(V/8))) + 18a Then, with probability
at least 1 - 8, it holds that de (+ TE) D(A
4 d'))
do) Hid'l do) C C V + Ee En +
By Theorem T whenever the policy evaluation errors cks as well as the estimation error E can be kept small, Algorithm ouputs policy #K with small suboptimality gap Pem. (#K) Peme (TE).
7

---

Surppes
Sumpae Juo8)
(a) RiverSwim
(b) CartPole
(c) DoubleChain
(d) Gridworld
(e) Acrobot
Proximal Point
KQLearn
GAIL
Linear
Figure Online IL Experiments. We show the total returns the number of env steps.
Notably, there is no direct dependence on the size of the state space or the dimension the feature space. In the ideal case, where & 0 for all k, the convergence rate is ((1/K) K).. The provided error propagation analysis still holds with general function approximation, i.e., in the context of deep RI. Indeed, by choosing +- I, Assumption I is trivially satisfied and the 0 variable in the objective 9% is replaced by Q-uuctioo. In practice, the estimation error & can be made arbitrary small, by increasing the number of expert demonstrations zig. Moreover, the next theorem ensures that under Assumptions and the biased stochastic gradient ascent (BSGA) subroutine has sublinear convergence rate.
Theorem 2. Ler (Wk, 0k) be the output of the BSGA subroutine in Algorithm foo T iterations, with sample transitions, and learning rates B. = = (1 Then, G (wt w 01) (w 0x) S O max(m,1)mm. ), with probability BVT
(t)) 2 max (o
>fmDt ( log 6 .
Tm
mt
log Tm
(
Corollary (Resource guarantees). Choose yj = a and let K 2 ), T 2 (E-*). Then for 92 (KT) = (c sample transitions, 52 (5-2) expert trajectories and approximately solving 2 (c-)) concave maximization problems, we can ensure de(R, TE) S O(++e), with high probability.
Offline Setting, Finally, we notice that using & T " as the reference distribution for the relative entropy we can obtain an offline algorithm that does not require environment interactions. By reinterpreting smoothing [82] one step of proximal point, and using similar arguments as in the proof of Theorem I we can provide similar theoretical guarantees for the offline setting. The formal statement of the theoretical result well as the optimization of the empirical policy evaluation objective are presented in Appendix [] (see Theorems and 6).
Experiments
In this section, we demonstrate that our approach achieves convincing empirical performance in both online and offline IL settings on several environments The precise setting is detailed in Appendix L
implement our algorithm without any practical relaxation outperforming GAII. (51), AIRL 38) and IQ-L Lean 40 Results are given in Figure [] Good performance but inferior to IQ-Learn is observed also for continuous states environments (CartPole and Acrobot) where we used neural networks function
Online Setting. We first present results in various tabular environments where
approximation.
Offline Setting, Figures
2a
to
20 shows that our method competitive with the state-of-the-art
40 and AVRIL (25) that recently showed performances superior to We also tried our algorithm in the complex mangeebasee Pong task from the Atari suite. Figure 2d shows that the algorithm reaches the expert level after observing 2e5 expert samples. We did not find AVRIL competitive in this setting, and skip for brevity. In these settings, verified that the algorithmic performance is convincing even for costs parameterized by neural networks.
offline IL methods IQLearn
other methods like [54] 64].
Continuous control experiments. We attain the expert performance also in 2 MuJoCo environments: Ant, Chefthhe,,h, Hopper, and Walker (see Figures 2e to 2h The additional difficulty in implementing the algorithm in continuous control experiments is that the analytical form of the policy
'The code is available at the following link 1ttp:///hhhhbbccm/m//////1//11

---

improvement step is no longer computationally tractable because this would require to compute an integral over the continuous action space. Therefore, we approximated this update using the Soft Actor Critic (SAC) 44 algorithm. SAC requires environment samples making the algorithm online. The good empirical result opens the question of analyzing policy improvement errors as 41
Point
Doen Thaedooes
Ocen Sumdees 101
(a) Acrobot
(b) CartPole
(c) LunarLander
(d) Pong
Proxima Point
IQLcom
AIRL
500
100
2500
2000
100
2006
200
4000
100 1000
GAL
(c) HalfChcetah
(f) Ant
(g) Hopper
(h) Walker2d
Figure 2: Neural function approximation experiments. Figures 2a to 2c show the total returns vs the number of expert trajectories. Figures 2e to show the total returns vs the number env steps. Figure shows the total return vs the number of expert state-action pairs.
Recovered Costs. unique algorithmic feature of the proposed methodology is that we can explicitly recover a cost along with the Q-function without requiring adversarial training. In Figure 3 we visualize our recovered costs in simple 5x5 Gridworld. Most importantly, recovered costs induce nearly optimal policies w.r.t. the unknown true cost function. Compared to IQ-Learn 400, we do not require knowledge or further interaction with the environment. Therefore, the recovered cost functions show promising transfer capability to new dynamics.
verify that the
(a) Ctruc
(b)
CC
-c)-Va
(d)-Vox
Figure 3: Recovered Costs in Gridworld. Comparison between the true cost Ctrue and the cost Ск recovered by I'IL We notice that the optimal value functions V and V present the same pattern. Hence, the optimal policy with respect to сд is nearly optimal with respect to Ctrue-
Cost Transfer Setting. We experimented with transfer cost setting We consider two different Gridworld MDP environments, say M and M, with opposite action effects. This means that action Down corresponds to action Left in M and vice versa. Similarly, the effects of Up and Right are swapped between M and M. We denote by V M.Ctewe (resp. V M.Creme the value function of policy æ (resp. optimal value function) the MDP environment M with cost function Ctrue- Moreover, we denote by -Mre the optimal policy in the MDP environment M under cost function c. Figure (a) gives the corresponding optimal value function. Figure (b) presents the value function of the expert policy Te TM.cuu used target by P'IL Figure (d) shows the value function of the learned imitating policy मж from P'IL. Finally, Figure (b) depicts the value function of the optimal policy xt M.cx
Gridworld (Figure 4
for the environment endowed with the recovered cost function ex by

---

I'IL (with access to samples from M). We conclude that the policy "M,ex is optimal in M with cost Curue- By contrast, the expert policy Te = π "M.cs used as target by P'IL performs poorly and as consequence also the imitating policy オ does so. All in all, we notice that the recovered cost induces optimal policy for the new dynamics while the imitating policy fails. Albeit, cost transfer successful in this experiment we do not expect this fact to be true general because we do not. tackle the issue of cost shaping [87]
Hil
Hil
-V (a)
V Strec M M.rar
FMeex M.errue
(d) -V
M.rer
(c)
M.Crron
Figure 4: Cost Transfer Experiment in Gridworld. We compare the performance of several policies the new MDP environment M with cost function Cmme We notice that the recovered cost induces optimal policy for the new dynamics while the imitating policy fails.
6 Discussion and Outlook
In this work, we studied a Proximal Point Imitation Learning (P²IL) algorithm with both theoretical guarantees and convincing empirical performance. Our methodology is rooted in classical optimiza- tion tools and the LP approach to MDPs. The most significant merits of I'IL are the following: (i) It optimizes a convex and smooth logistic Bellman evaluation objective over both cost and Q-functions. In particular, it avoids instability due adversarial training and can also recover explicit cost along with Q function; (ii) In the context of linear MDPs, comes with efficient resource guarantees and error bounds for the suboptimality of the learned policy (Theorem 2 and Corollary []. In particular, given poly(1/& (1))), m) many samples, it recovers an e-optimal policy, with probability 1 8. Notably, the bound is independent of the size of the state-action space; (iii) Beyond the linear MDP setting, it can be implemented in a model-free manner, for both online and offline setups, with general function approximation without losing its theoretical specifications. This is justified by providing an error propagation analysis (Theorems) and 4. guarantecing that small optimization errors lead to high-quality output policy; (iv) It enjoys not only strong theoretical guarantees but also favorable empirical performance. At the same time, our newly introduced methods bring challenges and open questions. One interesting question whether one can accelerate the PPM updates and improve the convergence rate. Another direction for future work is to provide rigorous arguments for the near-optimality of the recovered cost function. On the practical side, we plan to conduct experiments in more challenging environments than MuJoCo and Atari. We hope our new techniques will be useful to future algorithm designers and lay the foundations for overcoming current limitations and challenges. In Appendix B we point out in detail few interesting future directions.
Acknowledgements
The authors would like thank the anonymous reviewer for their suggestions to improve the presentation and for motivating us to inspect the recovered cost function. This work has received funding from the Enterprise for Society Center (E4S), the European Research Council (ERC) under the European Union's is Horizon 2020 research and innovation programme grant agreement OCAL, No. 787845, the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement n 725594 time-data), the Swiss National Science Foundation (SNSF) under grant number 200021 1211__20011.. Gergely Neu was supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (Grant agreement No. 950180). Luca Viano acknowledges travel support from ELISE (GA no 951847).
10

---

References
[1] Y. Abbasii- Yadkori, L. Bartlett, and A. Malek. Linear programming for large-scale Markov decision problems. In International Conference Machine Learning (ICML), 2014.
[2] Y. Abbasi-Yadkori, Yadkori, P. Bartlett, K. Bhatia, N. Lazic, C. Szepesvari, and G. Weisz. Politex: Regret bounds for policy iteration using expert prediction. In International Conference on Machine Learning (ICML., 2019.
[3] Y. Abbasi- Abbasi-Yadkori, N. Lazic, C. Szepesvari, and G. Weisz. Exploration-enhaneed politex. arXiv: 1908. 10479, 2019.
[4] P. Abbeel and A. Y. Ng. Apprenticeship learning via inverse reinforcement learning. In International Conference on Machine Learning (ICML), 2004.
[5] P. Abbeel, D. Dolgov, A. Ng, and S. Thrun. Apprenticeship learning for motion planning with application to parking lot navigation. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2008
[6] J. D. Abernethy, E. Hazan, and A. Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In Annual Conference on Learning Theory (COLT), 2008.
[7] A. Agarwal, S. Kakade, A. Krishnamurthy, and W. Sun. Flambe: Structural complexity and representation learning of low rank MDPs. Advances in neural information processing systems (NeurIPS), 2020.
[8] A. Ayoub, Z. Jia, C. Szepesvari, M. Wang, and L. Yang. Model-based reinforcement learning with value- targett regression. In International Conference on Machine Learning (ICML), 2020.
[9] J. A. Bagnell and J. G. Schneider. Covariant policy search. In International Joint Conference on Artificial Intelligence (IJCAT), 2003.
[10] G. Banjac and J. Lygeros. A data-driven policy iteration scheme based on linear programming. In IEEE Conference on Decision and Control (CDC), 2019.
[11] P. Barde, J. Roy, W. Jeon, Pineau, C. Pal, and D. Nowrouzezahrai. Adversarial soft advantage fitting: Imitation learning without policy optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[12] A. G. Barto, R. S. Sutton, and C. W. Anderson. Neuronlike adaptive elements that can solve difficult learning control problems. IEEE transactions systems, man, and cybernetics, pages 834-846, 1983.
[13] J. Bas-Serrano and G. Neu. Faster saddle-point optimization for solving large-scale Markov decision processes. In Conference Learning for Dynamics and Control (L4DC), 2020.
[14] J. Bas-Serrano, S. Curi, A. Krause, and G. Neu. Logistic Q-learning. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
[15] A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 3173)1167-175, 2003.
[16] P. N. Beuchat, A. Georghiou, and J. Lygeros. Performance guarantees for model-based approximate dynamic programming in continuous spaces. IEEE Transactions on Automatic Control, 65(1):143-158 2020.
[17] V. S. Borkar. A convex analytic approach to Markov decision processes. Probability Theory and Related Fields, 78(4):583-60) 602, 1988.
[18] S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities: A nonasympootic theory of independence. Oxford university press, 2013.
[19] Brockman, V. Cheung, I.. Pettersson, Schneider, Schulman, J. Tang, and W. Zaremba. OpenAl Gym. arXiv:166..00 01540, 2016.

---

[20] D. S. Brown, R. Coleman, R. Srinivasan, and S. Niekum. Safe imitation learning via fast Bayesian reward inference from preferences. In International Conference on Machine Learning (ICML), 2020.
[21] Q. Cai, M. Hong, Y. Chen, and Z. Wang. On the global convergence of imitation learning: case for linear quadratic regulator. arXiv:1901.03674, 2019.
[22] Q. Cai, Z. Yang, C. Jin, and Z. Wang. Provably efficient exploration in policy optimization. In International Conference on Machine Learning (ICML), 2020.
[23] Y. Carmon, Y. Jin, A. Sidford, and K. Tian. Variance reduction for matrix games. In Advances in Neural Information Processing Systems (NeurlPS), 2019.
[24] N. Cesa-Bianchi and Lugosi. Prediction, learning, and games. Cambridge university press. 2006.
[25] A. J. Chan and M. van der Schaar. Scalable Bayesian inverse reinforcement learning. arXiv:2102.06483. 2021.
[26] J. Chang, M. Uchara, D. Sreenivas, R. Kidambi, and W. Sun. Mitigating covariate shift in imitation learning via offline data with partial coverage. Advances in Neural Information Processing Systems (NeuriPS), 2021.
[27] A. Charpentier, R. Elie, and C. Remlinger. Reinforcement learning in economics and finance. arXiv:20031004, 2020.
[28] M. Chen, Y. Wang, T. Liu, Z. Yang, X. Li, Z. Wang, and T. Zhao. On computation and generalization of generative adversarial imitation learning. International Conference on Learning Representations (ICLR), 2020.
[29] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton. A simple framework for contrastive learning visual representations. In International Conference on Machine Learning (ICML), 2020.
[30] Y. Chen, L. Li, and M. Wang. Scalable bilinear π learning using state and action features. In International Conference on Machine Learning (ICML), 2018
[31] C.-A. Cheng, R. T. des Combes, B. Boots, and G. Gordon. A reduction from reinforcement learning to no-regret online learning. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
[32] R. Dadashi, L. Hussenot, M. Geist, and O. Pietquin. Primal Wasserstein imitation learning. In International Conference on Learning Representations (ICLR), 2021.
[33] D. P. De Farias and B. Van Roy. The linear programming approach to approximate dynamic programming. Operations Research, 31(6):550-866 2003.
[34] D. P. De Farias and B. Van Roy. On constraint sampling in the linear programming approach to approximate dynamic programming. Mathematics of Operations Research, 29(3):462-47,, 2004.
[35] T. De Ghellinck and G. D. Eppen. Linear programming solutions for separable Markovian decision problems. Management Science, 13(5):371-394, 1967.
[36] E. V. Denardo. On linear programming in a Markov decision problem. Management Science, 16(5):281-28) 1970.
[37] Y. Duan, Z. Jia, and M. Wang. Minimax-optimal off-policy evaluation with linear function approximation. In International Conference on Machine Learning (ICML), 2020.
[38] J. Fu, K. Luo, and S. Levine. Learning robust rewards with adverserial inverse reinforcement learning. In International Conference on Learning Representations (ICLR), 2018.
[39] T. Furmston and Barber. Variational methods for reinforcement learning. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2010.
12

---

[40] D. Garg, S. Chakraborty, C. Cundy, J. Song, and S. Ermon. IQ-leam: Inverse soft- Q learning for imitation. Advances in Neural Information Processing Systems (NeuRIPS), 2021.
[41] M. Geist, B. Scherrer, and O. Pietquin. A Theory of Regularized Markov Decision Processes. International Conference on Machine Leurning (ICML), 2019.
[42] A. Geramifard, C. Dann, R. H. Klein, W. Dabney, and J. P. How. RLPy: A funetiiun based reinforcement learning framework for education and research. Journal of Machine Learning Research, 16(46):1573-1578 2015.
[43] I. Goodfellow, Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems (NeurIPS), 2014.
[44] T. Haarnoja, A. Zhou, P. Abbeel, and S. Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International Conference on Machine Learning (ICML), 2018.
[45] F. Hanzely, P. Richtarik, and L. Xiao. Accelerated bregman proximal gradient methods for relatively smooth convex optimization. Computational Optimization and Applications, 79(2): 405 440, 2021.
[46] Hao, T. Lattimore, C. Szepesvári, and M. Wang. Online sparse reinforcement learning. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
[47] E. Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3-4):157-325, 2016.
[48] O. Hernández-Lerma and B. Lasserre. Discrete-Time Markov Control Processes: Basic Optimality Criteria. Springer-Verie New York, 1996.
[49] O. Hermández-Lerma and J. B. Lasserre. Further Topics on Discrete- -emre Markov Control Processes. Springer-Verlag New York, 1999.
[50] J. Ho and S. Ermon. Generative adversarial imitation learning. In Advances in Neural Information Processing Systems (NeurIPS), 2016.
[51] J. Ho, J. K. Gupta, and S. Ermon. Model-free imitation learning with policy optimization. In International Conference on Machine Learning (ICML), 2016.
[52] S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2), 2021.
[53] D. Hsu, S. M. Kakade, and T. Zhang. Random design analysis of ridge regression. In Conference on Learning Theory (COLT), 2012. 2012.
[54] D. Jarrett, I. Bica, and M. van der Schaar. Strictly batch imitation learning by energy- based distribution matching. arXiv:2006. 14154, 2021.
[55] Y. Jin and A. Sidford. Efficiently solving MDPs with stochastic mirror descent. In International Conference on Machine Learning (ICML), 2020.
[56] S. Kakade, A. Krishnamurthy, K. Lowrey, M. Ohnishi, and W. Sun. Information theoretic regret bounds for online nonlinear control. Advances in Neural Information Processing Systems (NeurIPS), 2020.
[57] G. Kalweit, H. Maria, M. Werling, and J. Boedecker, Deep inverse Q-larning with constraints. Advances in Neural Information Processing Systems (NeurIPS), 2020.
[58] A. Kamoutsi, G. Banjac, and J. Lygeros. Efficient performance bounds for primal-dual reinforcement learning from demonstrations. In International Conference on Machine Learning (ICML), 2021.
13

---

[59] L. Ke, S. Choudhury, M. Barnes, W. Sun, G. Lee, and S. Srinivasa. Imitation learning as f-divergence minimization. In International Workshop on the Algorithmic Foundations of Robotics (WAFR), 2020.
[60] C. Kent, J. Li, J. Blanchet, and P. Glynn. Modified Frank Wolfe in probability space. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[61] D. Kingma and J. Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations (ICLR), 2015.
[62] W. B. Knox, A. Allievi, H. Banzhaf, F. Schmitt, and P. Stone. Reward (mis)design for autonomous driving, 2021.
[63] I. Kostrikov, K. K. Agrawal, D. Dwibedi, S. Levine, and Tompson. Discriminator-actt critic: Addressing sample inefficiency and reward bias in adversarial imitation learning. In International Conference on Learning Representations (ICLR), 2019.
[64] I. Kostrikov, O. Nachum, and J. Tompson. Imitation learning via off-policy distribution matching. In International Conference on Learning Representations (ICLR), 2020.
[65] C. Lakshminarayanan, S. Bhatnagar, and C. Szepesvári. A linearly relaxed approximate linear program for Markov decision processes. IEEE Transactions on Automatic Control, 63(4): 1185-1191, 2018.
[66] N. Lazic, D. Yin, M. Farajtabar, N. Levine, D. Gorur, C. Harris, and D. Schuurmans. maximum-entrop approach to off-policy evaluation in average-reward MDPs. Advances in Neural Information Processing Systems (NeurIPS), 2020.
[67] Lee and N. He. Stochastic primal-dual Q-learning algorithm for discounted MDPs. In American Control Conference (ACC), 2019.
[68] S. Levine, Z. Popović, and V. Koltun. Feature construction for inverse reinforcement learning. Advances in Neural Information Processing Systems (NeurIPS), 2010.
[69] S. Levine, Z. Popović, and V. Koltun. Nonlinear inverse reinforcement learning with Gaussian processes. In Advances in Neural Information Processing Systems (NeurIPS), 2011.
[70] Z. Liu, Y. Zhang, Z. Fu, Z. Yang, and Z. Wang. Learning from demonstration: Provably efficient adversarial policy imitation with lincar function approximation. In International Conference on Machine Learning (ICML), 2022.
[71] F. Lu, P. G. Mehta, S. P. Meyn, and G. Neu. Convex lelamnngg. In 2021 American Control Conference (ACC), pages 4749-4756, 2021. doi: 10.23919/ACC50511 1.2221..983244
[72] Y. Malitsky and M. K. Tam. A forward- baakwadd splitting method for monotone inclusions without cocoercivity. SIAM Journal Optimization, 30(2):145-1142,, 2020.
[73] A. Manne. Linear programming and sequential decisions. Management Science, 6(3):259-267, 1960.
[74] A. Martinelli, M. Gargiani, and J. Lygeros. Data-driven optimal control with a relaxed linear program. arXiv:2003.08721, 2020.
[75] McDiarmid. Concentration, pages 095- Springer Berlin Heidelberg, 1998.
[76] P. Mehta and Meyn. Q-learning and pontryagin's 's minimum principle. In IEEE Conference on Decision and Control (CDC), 2009.
[77] P. G. Mehta and S. P. Meyn. Convex Q-learning, Part 1: Deterministic optimal control. arXiv:2008.0355 2020.
[78] Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. Bellemare, A. Graves,
M. Riedmiller, A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, King, D. Kumaran, Wierstra, S. Legg, and Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):529-533 2015.
14

---

[79] P. Mohajjein Esfahani, T. Sutter, D. Kuhn, and J. Lygeros. From infinite to finite programs: explicit error bounds with applications approximate dynamic programming. SIAM Journal Optimization,
2018.
[80] A. Müller. Integral probability metrics and their generating classes of functions. Advances in Applied Probability, 29(2):429-443 1997.
[81] K. S. Narendra and A. M. Annaswamy. Persistent excitation in adaptive systems. International Journal of Control, 45(1):127-160, 1987.
[82] Y. Nesterov. Smooth minimization of nonsmooth functions. Math. Programming. 103:127-152, 2005.
[83] G. Neu and J. Olkhovskaya. Online learning in mdps with linear function approximation and bandit feedback. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[84] Neu and C. Pike-Burke. A unifying view of optimism in episodic reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[85] G. Neu and C. Szepesvári. Apprenticeship learning using inverse reinforcement learning and gradient methods. Conference on Uncertainty in Artificial Intelligence (UAT), 2007.
[86] G. Neu, A. Jonsson, and V. Gómez. A unified view of eetropy-regularizeed Markov decision processes. arXiv: N70.vv/7055.079900 2017.
[87] A. Y. Ng and S. Russell. Algorithms for inverse reinforcement learning. In International Conference on Machine Learning (ICML), 2000.
[88] T. Osa, J. Pajarinen, G. Neumann, J. Bagnell, P. Abbeel, and J. Peters. An algorithmic perspective on imitation learning. Foundations and Trends Robotics, 2018.
[89]
Pacchiano, Lee, P. Bartlett, and O. Nachum. Near optimal policy optimization via REPS. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[90] J. Peters, K. Mülling, and Y. Altun. Relative entropy policy search. In National Conference Artificial Intelligence (AAAI), 2010.
[91] M. Petrik and S. Zilberstein. Constraint relaxation in approximate linear programs. In International Conference on Machine Learning (ICML), pages 809-816 2009.
[92] M. Petrik, G. Taylor, R. Parr, and S. Zilberstein. Feature selection using regularization in approximate linear programs for Markov decision processes. In International Conference on International Conference on Machine Learning (ICML), 2010.
[93] D. Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neural Computation, 3(1):88 97, 1991.
[94] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley Sons, Inc., USA, 1st edition, 1994.
[95] N. D. Ratliff, J. A. Bagnell, and M. A. Zinkevich. Maximum margin planning. In International Conference on Machine Learning (ICML), 2006.
[96] S. Reddy, A. D. Dragan, and S. Levine. SQIL: imitation learning via regularized behavioral cloning, urXiv:/905: / 108, 2019.
[97] R. T. Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14(5):877-898, 1976.
[98] S. Ross and D. Bagnell. Efficient reductions for imitation learning. International Conference on Artificial Intelligence and Statistics (AISIATS), 2010.
[99] S. Ross, G. Gordon, and D. Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In International Conference on Artificial Intelligence and Statistics (AISTATS), 1.11.
15

---

[100] S. Russell. Learning agents for uncertain environments (extended abstract). In Annual Conference on Computational Learning Theory (COLT), 1998.
[101] J. Schulman, E. Wolski, Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv: 3xXiv/770.00647 2017.
[102] P. J. Schweitzer and A. Seidmann. Generalized polynomial approximations in Markovian decision processes. Journal of Mathematical Analysis and Applications, 110(2):568558) 1985.
[103) S. Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2012.
[104] S. Shaley-Shwartz and S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
[105] L. Shani, Zahavy, and S. Mannor. Online apprenticeship learning. arXiv:2102.06924, 2021.
[106] R. Shariff and C. Szepesvári. Efficient planning in large MDPs with weak linear function approximation. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[107] M. Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171-176, 1958.
[108] A. L. Strehl and M. L. Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences,
2008.
[109] T. Sutter, A. Kamoutsi, P. E. Esfahani, and J. Lygeros. Data-driven approximate dynamic programming: A linear programming approach. In IEEE Conference on Decision and Control (CDC), 2017.
[110] R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, second edition, 2018.
[111] Syed and R. E. Schapire. A game-theoretic approach to apprenticeship learning. In Advances in Neural Information Processing Systems (NeurIPS), 2007.
[112] U. Syed, M. Bowling, and R. Schapire. Apprenticeship learning using linear programming. In International Conference on Machine Learning (ICML), 2008.
[113] E. Todorov, Erez, and Y. Tassa. Mujoco: A physics engine for model- control. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 5026- 5033, 2012.
[114] N. Vieillard, T. Kozuno, B. Scherrer, O. Pietquin, R. Munos, and M. Geist. Leverage the average: an analysis of kl regularization in reinforcement learning. Advances in Neural Information Processing Systems, 33:12163- 12174, 2020.
[115] M. Wang. Randomized linear programming solves the Markov decision problem in nearly linear (sometimes sublinear) time. Mathematics of Operations Research, 45(2):517-546, 2020.
[116] R. Wang. S. S. Du, L. Yang, and R. R. Salakhutdinov. On reward reinforcement learning with linear function approximation. Advances in Neural Information Processing Systems (NeurIPS), 2020.
[117] H. Xiao, M. Herman, J. Wagner, S. Ziesche, J. Etesami, and T. H. Linh. Wasserstein adversarial imitation learning. arXiv: /0t6::/9000///1111 /3, 2019.
[118] T. Xu, Z. Li, and Y. Yu. Error bounds of imitating policies and environments. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[119] S. Yan and N. He. Bregman augmented lagrangian and its acceleration. arXiv preprint arXiv:2002.065 06315, 2020.
[120] I. Yang and K--C. Toh. Bregman proximal point algorithm revisited: a new inexact version and its variant. arXiv preprint 1rXiv:2105.10377 2021.
16

---

[121] L. Yang and M. Wang. Sample-optimal parametric Q-learning using linearly additive features. In International Conference on Machine Learning (ICML), 2019.
[122] Y. Zhang, Q. Cai, Yang, and Z. Wang. Generative adversarial imitation learning with neural network parameterization: global optimality and convergence rate. In International Conference on Machine Learning (ICML), 2020.
[123] D. Ziebart, Maas, J. Bagnell, and A. Dey. Maximum entropy inverse reinforcement learning. In National Conference on Artificial Intelligence (AAAI), 2008.
[124] A. Zimin and G. Neu. Online learning in episodic Markovian decision processes by relative entropy policy search, Advances in neural information processing systems (NeurIPS), 2013.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We reflect the contribution described in the introduction with the theoretical results in Section 4 Section 4.2
(b) Did you describe the limitations of your work? [Yes] We state the assumptions needed for the analysis in Sections 3 and 4.2
(c) Did you discuss any potential negative societal impacts of your work? [N/A] The work mainly theoretical, we not foresee potential negative impacts on the society.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We acknowledge habing read the review guidelines.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We state the assumptions needed for the analysis in Section 3 Section
(b) Did you include complete proofs of all theoretical results? [es] The main results
stated in Section 4.2 and the proofs are included as supplementary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] The code is included in the supplementary material.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] Training details are provided in the Appendix.
(c) Did you report error bars (e.g., with respect to the random seed after running ex- periments multiple times)? [Yes] We averaged multiple seeds whenever possible computationally. We ran single seed for the computational expensive Pong environ- ment.
(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)? [Yes] We specified the resource in the Supplementary material.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We cite 440 for using their codebase and their expert data.
(b) Did you mention the license of the assets? [Yes] We mention the license in the Supplementary.
(c) Did you include any new assets either the supplemental material or as URL? [Yes] We attach the code to the supplementary.
(d) Did you discuss whether and how consent
obtained from people whose data you's 're using/curating? [Yes] We discuss this in the supplemnetary material (e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] We do not use personal data.
5. If you used crowdsourcing conducted research with human subjects...
17

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] We did not involve human partecipants.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] We did not involve human partecipants.
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A] We did not involve human partecipants.
18


Reviews:
[{"review_id": "yUqOpWv1Oiw", "reviewer": "Reviewer_7mcb", "summary": "Based on the proximal point method, this paper propose a new algorithm to solve the minimax formulation of the imitation learning problem, which avoids the nested policy evaluation and cost updates. Based on the assumption of linearly parametrized cost classes, the paper further provides a theoretical analysis for the required number of expert transitions, trajectories and number of concave maximization problems to solve. Finally the paper provides an empirical study on several RL environments with both linear and non-linear function approximations.", "questions": "See \"Strengths And Weaknesses\" Section.", "limitations": "See \"Strengths And Weaknesses\" Section. No potential negative societal impact.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Stengths:\n- Detailed introduction to related work and background.\n- Good writing and presentation quality.\n- Solid math derivations.\n\nComments, Questions & Limitations:\n- The motivation / key challenge to solve in this paper is not clear to me. It seems the derivations based on proximal point method may lead to a new algorithm for imitation learning, but what are the unique advantages (especially in terms of practical applications) of the proposed approach and what are the limitations of previous works this work has solved?\n- I understand that the resulting algorithm avoids nested optimization / alternating updates. But this does not seem to be a unique feature of the proposed method and many previous IL methods also enjoy that property.\n- The theoretical analysis is for linear functions, which may be restrictive. Moreover, I do not see particular insights from the theoretical analysis. If the main take-away message is the estimation error can be made arbitrarily small by increasing the number of expert transitions or computational resources in general, that is not very exciting. Is the sample complexity bound state-of-the-art, and is the bounds meaningful in practice (for example $\\epsilon^{-5}$ sample transitions may be too large to be useful in practice)?\n- The policy update step $\\pi_k \\propto \\pi_{k-1} e^{- \\alpha Q_{\\theta_k}}$ seems to be something like density ratio correction of previous policy. Can you elaborate more on that part, and in particular the intuitions?\n- From figure 2, the final performance of PPM and IQLearn seems similar in most cases, but PPM is indeed more sample efficient than other methods.", "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": "U0dO87XcxJQ", "reviewer": "Reviewer_7EDZ", "summary": "The paper presents a novel method for imitation learning that is based on the LP formulation for MDPs. More precisely, the method uses the recently repopularized technique of splitting the occupancy measures to also obtain the Q-function as Lagrangian multiplier, and optimizes this program using a proximal point method with the regularizers used by Q-REPS. The resulting algorithm is similar to the state-of-art IQ-Learn algorithm and differs primarily by using a \"logistic Bellman evaluation\" objective for optimizing the Q-function (and jointly the reward function).\nThe paper provides a thorough theoretical analysis in the linear MDP setting (transition matrix and rewards are linear for given features), bounding the suboptimality depending on the evaluation/estimation errors (except for the policy improvements which are assumed optimal), and evaluates the methind in tabular settings, for offline imitation learning, and for continous control problems, where it performs overall better than IQ-Learn.", "questions": "1. Compared to IQ-Learn, the proposed method explicitly learns a reward function. Intuitively, I would expect the parametric form of the reward function to perform better than the implicit form (referring to the way IQ-Learn recovers it from Q and Value function). I was a bit suprised, that the paper does not discuss the use of the reward function, given that one of the main algorithmic properties is that an explicit reward function is learned along with Q function. Why? \n\n2. How are the gradients estimated in the deep learning setting?", "limitations": "The paper states the theoretical assumptions, but overall the limitations should be better discussed. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Originality\nImitation learning based on the LP formulation was already introduced in the classical work by Syed & Schapire (2007) (MWAL). However, the proposed algorithm, significantly deviates from MWAL, mainly by building on the recent advances by Bas-Serrano & Neu (2020) to derive a bi-linear saddle point problem that contains the Q-function as Lagrangian multiplier, and by orientating algorithmically on the state-of-art IQ-Learn algorithm by Garg et al. (2021). The resulting work is clearly novel, both algorithmically as well as theoretically.\n \n## Quality\nThe derivation of the algorithm is presented clearly and I checked the proofs up to proposition 3. That is, I did not check the proofs related to the \"biased stochastic gradient estimates\" and the theoretical bounds, which are quite involved and not in my field of expertise. However, I have no reason to believe that they are of worse quality compared to the rest of the work.\n\nThe empirical analysis is good by including tabular settings where the assumptions can be met, as well as continuous settings, where the practical competitiveness could be demonstrated. However, the latter could be improved by adding more experiments on different environments.\n\nIt would be very interesting to evaluate the learned reward function, by--after convergence--discarding the Q-function and policy, and learning a new policy from scratch from the learned reward function. Would the reward succeed in inducing a good policy? Would it even transfer better, compared to Q-function/policy with respect to changes in the dynamics?\n\n\n## Clarity\nI like the presentation of the paper a lot. There is a nice flow starting from the imitation learning objective Eq. 1 in the background section (Section 2) to the presentation of the saddle point problem and the PPM update equations in Section 4, which are the basis of the proposed algorithm. Only the discussion of the \"Q-convex\" dual (cf. Proposition 2) breaks the flow a bit. I wonder, why the authors chose to discuss the dual formulation at this place. The path \"(Primal) -> (Primal') -> (Dual')\" would seem more logically to me than \"(Primal) -> (Dual) -> (Primal')\".\n\nThe paper ends quite abruptly after briefly describing the experimental settings and results. I think the paper would be better structured by adding a conclusion for reflecting on the main insights (LP formulation can be used for competitive IL algorithm with nice properties such as joint reward-cost optimization and logistic Bellman errors) and for discussion the limitations of the current work (limited  evaluation in challenging environments).\n\nI also think that the gradient estimates (6), (7) could be presented better. Or actually, I wonder, if the equations of the gradients need to be shown in the main document at all. I briefly looked into the code (thanks for submitting it!) and it seems like the gradients a computed by backpropagating through a different objective than Eq. 5. Would it be possible to state the objective that is used computing the gradients and refer to the appendix for showing that these gradients are biased estimates of the gradients of (5)?\n\nThe projections in Algorithm 1, should be briefly discussed in the text.\n\nTo save some space for additional discussions, I would consider integrating section 5 in section 4 (only briefly stating the theoretical results / theorems) and maybe removing the discussion of the dual in section 3 (at the cost of slightly extending the introduction to Eq. 2 in Section 4).\n\n## Significance\nI found the paper very interesting both from a theoretical and practical perspective, and believe that also many other researchers in the field of imitation learning could be inspired by the work.\n\n## Minor\nLine 706: The most important merits of the primal-dual algorithm [...] I wouldn't use \"merits\" for describing bad properties.\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": "RA0eq_7IxH", "reviewer": "Reviewer_s345", "summary": "This paper proposed an imitation learning algorithm to handle both online and offline setting. First, an intractable convex problem is obtained by relaxing the primal problem. After that, the saddle point problem is derived by applying Lagrangian decomposition. Finally, the authors provided an practical algorithm based on the problem, named PPIQ-Learn. For the policy evaluation, PPIQ-Learn uses a convex and smooth objective over both cost and Q-value function. In addition, the theoretical analyses support the performance guarantee. Finally, the provided experiments show that the proposed algorithm outperforms baselines.", "questions": "I enjoyed reading this paper, but I seem to have missed the main contribution of this paper (especially, compared to the IQ-Learn). It would be very helpful to understand if the authors clarify the following questions.\n\n- I'm not sure why PPIQ-Learn shows better performance than IQ-learn. Would you explain the main contribution (or intuitive explanation) of PPIQ-Learn compared to IQ-Learn?\n- Is there any reason to choose D to measure the distance between $\\lambda$ and $\\lambda’$? In addition, why the authors use fixed $\\eta$ instead of optimizing $\\eta$?\n- The definition of $H$ is different from that of simple KL-divergence – sample $(s,a)$ from $d$ and measure the log-ratio between $\\pi_d$ and $\\pi_{d’}$ instead of the log-ratio between $d$ and $d’$. Is there any reason or justification?\n- Why authors use only 2 MuJoCo domains (Ant and HalfCheetah) out of 4 domains used in IQ-Learn?\n- I am curious about the feature matrix used in the actual experiments. Would you explain about the choice of feature matrix?\n- Is it difficult to simply combine PPM and IQ-Learn? If so, what is the problem? If not, what are the advantages of PPIQ-Learn over such simple combining?\n", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nTheoretical analyses support the performance of the proposed algorithm.\n\nThe proposed algorithm shows convincing empirical results.\n\nIt can be applied to both online and offline imitation learning problem\n\nWeakness:\n\nThe novelty of this work is not clear – IQ-Learn also uses a single convex objective to evaluate the policy and handles both online and offline setting.\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": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept