Robust Imitation via Mirror Descent Inverse Reinforcement Learning
Authors: Dong-Sig Han
Hyunseo Kim
Hyundo Lee
JeHwan Ryu
Byoung-Tak Zhang
Venue: ICLR 2022 Submitted (2022)
Keywords: inverse reinforcement learning
reward learning
regularized markov decision processes
imitation learning

Abstract: Adversarial imitation learning techniques are based on modeling statistical divergences using agent and expert demonstration data. However, unbiased minimization of these divergences is not usually guaranteed due to the geometry of the underlying space. Furthermore, when the size of demonstrations is not sufficient, estimated reward functions from the discriminative signals become uncertain and fail to give informative feedback. Instead of formulating a global cost at once, we consider reward functions as an iterative sequence in a proximal method. In this paper, we show that rewards dervied by mirror descent  ensures minimization of a Bregman divergence in terms of a rigorous regret bound of $\mathcal{O}(1/T)$ for a particular condition of step sizes $\{\eta_t\}_{t=1}^T$. The resulting mirror descent adversarial inverse reinforcement learning (MD-AIRL) algorithm gradually advances a parameterized reward function in an associated reward space, and the sequence of such functions provides optimization targets for the policy space. We empirically validate our method in discrete and continuous benchmarks and show that MD-AIRL outperforms previous methods in various settings.

Under review as a conference paper at ICLR 2022
ROBUST IMITATION VIA MIRROR DESCENT INVERSE REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Adversarial imitation learning techniques based modeling statistical diver- gences using agent and expert demonstration data. However, unbiased minimiza- tion of these divergences not usually guaranteed due to the geometry of the underlying space. Furthermore, when the size of demonstrations is not sufficient, estimated reward functions from the discriminative signals become uncertain and fail to give informative feedback. Instead of formulating a global cost at once, we consider reward functions as an iterative sequence in a proximal method. In this paper, we show that rewards dervied by mirror descent ensures minimization of Bregman divergence in terms of a rigorous regret bound of (1/TT) for a particular condition of step sizes {n (=1 The resulting mirror descent adver- sarial inverse reinforcement learning (MD-AIRL) algorithm gradually advances a parameterized reward function in associated reward space, and the sequence of such functions provides optimization targets for the policy space. We empir- ically validate our method in discrete and continuous benchmarks and show that MD-AIRL outperforms previous methods in various settings.
INTRODUCTION
Inverse reinforcement learning (IRL) is an algorithm of learning ground rewards from demon- strations of an expert that acts optimally with respect to an unknown reward function. Traditional IRL approaches (Ng & Russell 2000 Abbeel & Ng. 2004 Ziebart et al. 2008) solve the imita- tion problem based on iterative algorithms, alternating between the reward estimation process and a reinforcement learning (RL) algorithm. Recent adversarial imitation learning (AII.) studies (Ho) & Ermon 2016; Fu et al. (017)) focus on formulating statistical divergence minimization with fine-tuned representation of the target expert probability distribution (Ghasemipour et al.) 2020).
One method approximate the distance between probability distributions is using Bregman diver- gences, a family of metric-like functions induced by a strongly convex function. Jeon et al. (2020) generalized the AIL framework to optimization problem with respect to a Bregman divergence between policy distributions where the method shares on the essence of regularized Markov deci- sion processes (Geist et al. 2019). Through the lens of differential geometries, this implies that policy distribution and reward function can be associated with geometric constraints specified by convex regularizer (Shimal 2007). Apparently, the limitation of regularized IRL studies naturally comes from a geometric property in which minimizing a Bregman divergence does not guarantee unbiased progression due to the constraints of the underlying space (Butnariu & Resmerita 2006).
The success of machine learning has been the key to learning such divergences with high preci- sion. When the demonstration size is sufficiently large, the discriminator approximation of AIL can model the entire expert policy distribution internally using nonlinear approximators such as neu- ral networks (Finn et al. 2016 Fu et al.] 2017). However, there are challenging tasks that require long action sequences to be solved. When states only be rarely visited by imitation learning agents, the uncertainty of estimated expert policy often substantially affects the discrimination qual- ity. Therefore, the development of robust IRL method that is tolerant to unreliable discriminative signals induced by imperfect demonstrations is necessary.
The reasonable question is how to learn with cost estimations that not precisely determined throughout the learning process. There have been considerable achievements in dealing with tempo- ral costs in the online learning domain (Fiat & Woeginger 1998 Hazan 2019). An online learning

---

Under review as a conference paper at ICLR 2022
algorithm predicts sequence of parameters {wr C W that incurred by cost function (-) each iteration. The most ordinary approach in online learning is stochastic gradient descent (SGD): W+++1 w 77 V F (w,). SGD is desirable algorithu when the set W is the Euclidean geometry since it can provide unbiased progression for minimizing Fg (Raskutti & Mukherjee (013). How- ever, policies appear in manifolds of probability distributions; a gradient may not be the direction of the steepest descent in this case due to geometric constraints (Amari 1998 2016).
In this paper, we propose an iterative imitation learning framework that interprets the RL-IRL scheme similar to proximal optimization methods (Boyd et al.] 2004; [maaii 2016). We identify two issues in the AIL studies that have characteristics of unconstrained updates: (I) a divergence does not guarantee informative global directions to match the expert policy due to the geometry, and (2) a representation of divergence often cannot be accurately obtained due to insufficient data.
Our method is motivated by template of optimization algorithms specified by convex function, called mirror descent (MD: Nemirovsyy & Yudin 1983). For parameters sequences, cost functions, and step sizes, an MD update for strongly convex function Q is derived as vΩ(w++1) = ()(
V (ww)),
(1)
where V is a bijective transformation that links the primal space and the dual space of gradients. Different from these standard MD formulations, our methodology draws a sequence of functions on a space formulated by a regularized reward operator which is an alternative to the dual space. Consequently, the reward functions are projected optimization targets for the space of policies.
Our Contributions. We propose a novel IRI. algorithm which facilitates the agent in robustly imitating the expert. Our work is complementary to previous regularized studies; introduce a geometric perspective for optimizing rewards and derive solutions with theoretical guarantees.
NEW R1,
Instead of a monolithic estimation process of a global solution, we derive a sequence of reward functions that provides local optimization targets for the space of policies (Section (3).
We prove that rewards derived by an MD algorithm guarantee convergent divergence minimization performance along with rigorous regret bound (Section 4
We propose mirror descent adversarial inverse reinforcement learning (MD-AIRL)) a novel IRL.
algorithm that can be easily implemented on top of the standard AIL framework (Section We validate the outperforming performance of MD-AIRL on benchmarks with large discrete ac- tion spaces and continuous action spaces (Section 6)
2 PRELIMINARIES
Notation. For finite sets X and Y. we define Y set of functions from X Y. Ax (4 is set of (conditional) probabilities over X (conditioned on Y). For a function f E RSxA and a policy T E A., I and n" denote shorthand notation of f(s, -) and K (-|s),, respectively. A Markov decision process (MDP) is defined as a tuple P, with the state space S, the action space A, the transition kernel P E ASxA, the reward function S and the discount factor 7 E [0, 1). A Bregman divergence with respect to a convex function for a state s is defined as Dn((T"((**) = a(x*)= - (( (VI((*), (f(((*)), T² * We write 2(x))= = [[(x")) ")sss and similarly for VΩ.
Regularized RL & IRL. We consider the RL-IRL framework in regularized MDPs GGesst et al. 2019), where the policy is optimized along with causal convex regularizer. The objective is to find x which maximizes the expected discounted sum of rewards with a strongly convex regularizer Ω:
maximize Ja(T, r) = Ex Σ 1st (r(ss, a.) 2( (TT((1s))) TEAS
(2)
where the subscript on the expectation denotes samples generated from the MDP and policy
Consider the convex conjugate of gi- = V((mm): Ω2" (g)) max (7* : - R(m²). Differ- entiating both sides with respect to g the gradient of conjugate VΩ" maps de to the unique optimal policy Tg. Let 1I be a bounded, open set for A C II and R : + gSx be a reward operator which maps policy to a reward function. The output = R(Fx) is representation of the expert's s behavior; but finding such operator is an posed problem because every function 7 that makes the state-action value function Os is a valid solution of regularized IRL (Geist al. 2019). Recently, Jeon et al. (2020) proposed a tractable solution, which we refer to the function as the regularized reward function. We rewrite the previous notation by defining the regularized reward operator V..
2

---

Under review as a conference paper at ICLR 2022
Definition 1 (Regularized reward operators). Define the regularized reward operator Vn 1T +
4/r
(x a) = 52' ()) - (=", V2(T=)) + +
(3)
for (3) = v2((T)) = [
By using the operator in discriminative networks, Jeon et al. (2200) proposed regularized adversarial IRL (RAIRL) as a generalization of AIL in terms of minimizing a specific Bregman divergence.
Mirror Descent. Let be parameter from a class of functions F. Replacing the 1.2 proximity term of proximal gradient descent with the
set W and F3 W + R be convex cost function
Bregman divergence (Gutman & Peña 2018), the proximal form of the MD update is given as
ADDDY iw + oz a:DD(wwllu MD = argmin VF((u,"), w w W
(4)
wEW
where at := 1/m, denotes an inverse of the step size t/.. MD was developed as a generalization of SGD, where the local geometry is specified by Bregman divergence (Gunasckar al. 2020).
3 ITERATIVE RL-IRL AS A PROXIMAL OPTIMIZATION METHOD
We interpret the RL-IRL framework as variant of proximal optimization methods and consider two sequences [Te J and { that denote the learning policies and reward functions, respectively.
Associated reward function. An updated point in MD can be uniquely projected to the de- sired space (A in our case) using a Bregman projection operator P.. that locates iterative points to the feasible region, i.c. tc+1 (=( argmin [Dn [[ for Āe+1 II. To avoid these computations, we preemptively constrain a reward operator to satisfy the projection invariance with respect to regularized RL process of the associated state-action value function q: (V.' (4)) Vi2 (ÿ). According to Lemma 1 of Jeon al. 2020), regularized reward func- tion the can replace q. since the induced Bregman divergence allows the learning in a greedy manner. The projection invariance of the operator V,, can be shown by bijective relation with Vl" in the space of A by the following lemma.
FIX R3
Lemma 1 (Natural isomorphism). Let v E (a(A for (II) = { (s, = (s,a), AsE S, a A, ]E.I]. Then, VS is unique with respect to Lb and for every (D) TE A
Policy Space
Reward Space
The proof is in Appendix A Figure | illustrates that there is unique vi, for T.. hence the two func- tions are isomorphic objects. Note that the trans- formed (T.)) is different from the form V((T))) of the dual space that is used in classical MD algo- rithms. The transformation is shifted by vector 1c with a constant e = [((=f) - (xf. V[(==)) for each s. However, if the underlying space is AS the operator V12" reconstructs the original point for both V, and VΩ, since the distributivity of Ω Geist et al. 2019): holds (so V12" (3 + Ic) (y)( Conse- quently, we may omit the projection phase (the dotted angle Figure [ when the reward func- tion satisfies the constraint of (45)
A
V
Th or
Ut+1
V!
FIX R3
Figure 1: A schematic illustration. Suppose an update is constrained by divergence with re- spect to current n, (gray). MD is performed in the space defined by Un T++1 is recovered in the desired space A (solid curve) using VΩ*
(y+1c) Q (v) -
NEW R3
As result, we consider an updated reward function v/441 E (,, as projected target of MD, which can be associated by parameterization of AS, For instance, bijective mapping of s/+ can represent a softmax policy for a discrete space, or a Gaussian policy for a continuous space, using
FIX R3
NEW R3
its parameters. The subsequent RL process at t-th step becomes finding the next iteration Te+1 by
NEW R3
maximize Ja(T,, 1h+11 = Ey HEAR
D (T | |=++))
T++1 = VΩ (144)).
(5)
FIX R3
The equation shows that an arbitrary regularized RL algorithm with the regularizer ? forms a cu- mulative discounted sum of Bregman divergences, thus the mapping me-1 can be achieved.
3

---

Under review as a conference paper at ICLR 2022
#f
68141
Shannon entropy
Tsallis entropy
vp-1.0
Bregman div.
0
Tp-0.2
mEa
-2
-2
1=10
t=100
Stap
Step
Figure 2: The policy Ti minimizes an online cost Dp(-I(sss)) associated with a convex regularizer such as negative Shannon and Tsallis entropies. The left example shows that the number of updates of #t41 vary by the step sizes 1j of MD formulation. The plots on the right show that Dr (T (T vary by (averaged over 10 different trials). The solid red lines represent the baselines of Du (Ta,e Tee) Te)-
Online imitation learning. The necessity of online learning setup comes from observing that our RL-IRL processes do not retain the Vn (Tg), representation of TT., during training. Instead, consider a random process f J where the estimation тg. resides borhood of Te. estimated by separate estimation algorithm such as maximum likelihood methods. Substituting t/e to VeF,, in Ja (IT t/s) turns the RL objective into an online learning problem:
closed, convex neigh-
minimize F((T) = Jn(T, tRE,)) ) EE En 7d D'Dn( m #EA%
(6)
FIX
R3
For deeper understanding of our setup, we consider an example Figure 2 Assume that policies of the learning agent and the expert follow multivariate Gaussian distributions initially л ([[,, 0),,,) and Te = ([, 3] >i)) for [Sg] < 1. The policy स, is trained by cost function Da(- (T..) with the proximity constraint (e) where the Gaussian policy Ne. is also fitted using stochastic samples from T. at each iteration, starting from म.. лT We first observe that the step size constant affects the training speed in the early phase. Notably, the performance of certain cases exceeds the baselines Do ( by choosing the step size effectively low as 17 < This suggests that there is a clear advantage of the online imitation learning setup for unreliable Tg.t.
T
T
FE.t
Weid #e+2
b)
Figure 3: Illustrations of mirror descent imitation learning in the (a) f-th iteration and (b) (t + 1)- th iteration. Consider that (T 1 is random process and 7g,t and Net++ are sampled from neighborhood of Th with respect to norm. The MD step is taken in the interval of ny and Tg. Note that by decreasing the step size of updates, the region of 7T (blue) shrinks.
MD update rules. Plugging each divergence of the cumulative cost F, to the template of Equa- tion the optimization process for the subsequent 4/441 of the MD formulation is derived a
1et Vo (Te41): के
argmin V Dn(=i)
n =i)a + oj Dn(""
E'AA
V(((T) - ())
argmin DT || [ - (T [1=²)) au (a(
EEA
argmin ve Do D=((T") +(1 ne) Da(a (m
Me 1/o0, Vo S, (7)
T'EAA
estimated expert
learning agent
where the gradient of Dg is taken with respect to its first argument n². The objective of reward learning is analogous finding an interpolation each iteration where the point is controlled by the step size Th- Figure 3 shows that the region of ne (defined by norm) gradually decreases
NEW R3
Bregman divergences generally intractable to be computed, unless the policy is specific parametric model (e.g. exponential families). See the works of Nielsen Nock (20TT); Jeon al. (2020) and Appendix
4

---

Under review as a conference paper at ICLR 2022
when 7): M-+1- Note that solving the optimization of Fj requires interaction between and the dynamics of the given environment; thus, the RL process in Equation (5) plays the essential role of sequential learning by the value measures of the reward function.
4 ANALYSES ON STEP SIZES, CONVERGENCE, AND REGRETS
We define an online cost fe Te) which involves a policy and a trajectory as inputs. The trajectory 7, {&r { = is available at the 1-th step by executing the policy m. in the environment. An online cost function for reward 4/e,t = (Te,))))))) can be expressed as
Online IRL.
fe( E, {E Te(alsi) (8,, ()) - (1Ta(-1))))
(8)
FIX
R3
1=0
We refer the objective of the learning is to find unique fixed point T. E II that minimizes [T, 7)], where the expectation is taken over the entire steps (i.e. lim E, En....... [f 7.)). Taking (stepwise) gradient for each T--ss), is found by (I. when f - oc, hence (I( = lim (
NEW R3
The assumption of Me = n. allows the
particular situation when the estimation algorithm of Re.t actually convergent with - This
also allows general situations where the estimated expert policy is not stationary; the algorithm finds the unique point according to the expectation of gradient by scheduling the step size Tec.
Theoretical Analyses. We state two conditions of {n+ to guarantee convergence properties which is explained in the following analyses. Convergent sequence & divergent series;
lim Ttt t0000
and
Σ
t=1 T1 oc.
Divergent series & convergent series of squared terms: x and Σ Do.
Figure 4: A step size sequence example.
(10)
Under the satisfaction of both cases, a sequence that divergent its series (e.g. harmonic series E is suitable in Figure In arguments, a policy conditioned by state is in Banach space called the L space (R- (F-.I--Ip)) where I|-IIp denotes p-norm, where we assume 1 < p S for the convergence in the dual T," space (1/p + 1/1 = 1). The proofs are in Appendix
Theorem 1 (Stepsize considerations). Let Ω be strongly convex, VΩ be Lipschitz continuous, and the associated Bregman divergences are bounded. Assume infzeaş [[A((T,))) T)] > 0. Then
+co Erg...rr Ei= D m =0 and only if Eq. 9 is satisfied.
(a) If lim ne 0, then T E N, T, and > O exist S.I. E Ere,rr [fr(Tz, [x) 2 --n. t-+00
(b) If the step size takes the form n. - then Eng,,r [ r Da (T [m = ((IT))
Theorem 2 addresses the convergence of the algorithm in specific case when TT. can be achieved. Theorem (Convergence in optimal cases). Let be strongly convex, VΩ be Lipschitz continuous, and the associated Bregman divergences are bounded. Assume πι # Tg and inf inf TEAS (Tf T)] = Then, lim E. [ Tt)] 0 if and only if E T)t = oc. 1f =\t m, then there exist C1, (0, 1) such that e1 Ai S Ar S or AA where { denote a sequence of A. E, (PI(TTI((T)))
FIX
R3
Proposition D provides a sufficient condition for the almost certain convergence of an MD algorithm by imposing the stronger condition of step size in Equation (10). Proposition 1 (Convergence in general cases). Assume inf TEAS [[ T) If the step size sequence satisfies Eq. (10), then we have lim Ei- 7 DD ImT") = 0 almost surely.
Regrets. Define the regret at t-th iteration for sequence of cost functions (fe) as
R2 = E Ty) - inf x ( (,,
(11)
In the optimal case of inf = E[fe(T, T(] = 0, R, is bounded by O(1/T) since fe inherits the property of Bregman divergence so that the infimumm is achieved by 0 at Tg. By Proposition T
the updates regarding the policy converge when the step size sequence abides by Equation (IO) Therefore, even for the general case of inf infreag [[fe(T, r)] > O. Rr is bounded to O(ITT).
5

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Mirror Descent Adversarial Inverse Reinforcement Learning.
1: Input: an expert trajectory dataset (Tt) )(=1 a regularized reward function us E (4 an agent policy no, an estimate policy Ty. neural network b IR 01, R
2: for - 1 to do
3: 0t2 01 (t-
4: Collect rollout trajectories by using the agent policy Tg.
5:
Optimize via binary logistic regression for D, to classify Tj and T..
6:
Optimize Ty via binary logistic regression for D to classify Ti and 7r.
7: Optimize V with the MD objective in Equation 77) using at, T Tt. Te, and Ty.
8: Train Th via a regularized actor-critic method to maximize u a) with regularizer XL((-).
9: Output: Tg. V/
5 MIRROR DESCENT ADVERSARIAL INVERSE REINFORCEMENT LEARNING
In this section, parameters 0, é, and are presented representing agent policy, reward, and expert policy functions respectively parameterized with neural networks. On top of the standard All algo- rithm, we propose the MD-AIRL. method, learning with a dual discriminator architecture motivated by previous studies regarding multiple discriminators (Nguyen et al. 2017 Chongxuan al. 2017).
AIL methods have dealt divergences between joint densities of states and actions (Ghasemipour et al. 2020). To clearly distinguish matching overall state densities and imitating specific behavior, we aim to disentangle these concepts and propose two structured discriminators:
Da, (8, a) (log Th (als)/ ma]{s) + b(s) and Dz(s) - (b(s)),
where b S + R is neural network regarding states and (-) denotes the sigmoid function. discriminators Dj and Da., are trained with binary cross-entropy losses regarding trajectories:
The
maximize Emp [log (s, a)] + Ex, [log(1 (s,
(12)
maximize Eize [log Ds{s + Ex, [log(1 D,(s))].
(13)
Note that b and are not trained for learning Da,v. Let Pr E As denote normalized state visitation
distribution of æ, which is defined as (*(() = (1 - 7) FF [ TT{s = s3] where T(.) is an
indicator function. Since + a log (xx) + 3 log(1 (x)) attains its maximum at oxx) .+r
Goodfellow et al. 2014], optimality is achieved when ne = Tg and b(s) = log Pag (=)/p=
Let via denote the regularized reward function where the parameter o is trained using step size nh the agent policy Tp. and the estimation expert policy Tp:
minimize Eg n Da (T (11s)))))
(1 no (-(T)(((
(14)
where T. denotes the transformed policy vl(Us) and 5. denotes mini-batcher of states using the both agent and expert trajectories. The algorithm adjusts the term Te = 1/a, with a harmonic progression by linearly increasing oe by the range of (0n, 0. which is derived from analyses.
For a hyperparameter > > 0, the MD-AIRL reward function is defined by a linear combination: (3 a) = (
a) + b(s).
By using arbitrary regularized RL which uses AS2(-) as the regularization function, the reward learn- ing of vi regarding the agent ma is decomposed into the following two terms:
Eno (s, {((F((-(s)
= AlE [s, a) - ( (-1s)) DKL
= -EE, [ (-
s))] - (KL(Pno (lpx))
Minimizing the first term of FF,, Do (T(rr) (mm))) represents the online learning of MDD formulation. However, Ph that is trained on cannot cover the entire reachable states since the state visitation is heavily misaligned in challenging sequential decision problems. Therefore. we propose the second auxiliary term of generalized KL divergence (KL(PTo I| playing additional role of facilitat- ing the supports of state visitation densities to be matched properly. Algorithm T summarizes the entire procedure of MD-AIRL. See Appendix C for detailed implementation.

---

Under review as a conference paper at ICLR 2022
Table 1: Bregman divergences with ground-truth distribution with five different types of regulariza- tion. The numbers are multiplied by the dimension of action space (we report |A| D2 nr
TTg
LA|
10a
LA|
10a
[A|
10
Algorithm
RAIRL
MD-AIRI.
RAIRL
MD-AIRL.
RAIRL
MD-AIRL
Shannon
2.55 4: 1.59
2.28 1.20
140.3 = 87.5
125.3 + 61.8
5752.9 2986
5943.1 = 2967
Tsallis
0.21 0.13
0.11 0.04
0.55 0.133
0.24 0.03
4.95 + 2.3
4.21 0.16
exp
0.27 0.17
0.13 + 0.06
0.55 0.12
0.23 + 0.03
5.06 2.44
4.97 + 0.69
coe
0.05 0.04
0.02 1 0.01
0.03 + 0.02
0.01 + 0.01
0.21 0.62
0.05 + 0.05
0.25
3.46
0.75
7.59 1.02
SHANNON
TSALLI
EXP
COS
Bregman Div.
MD-AIRL RAIAL
NRL
MD-AIRE:
MD-NRL
16-2
MD AIL
1E:3
16-5
300K
Time Step
Time Step
Time Step
Time Step
Time Step
Figure 5: The average Bregman divergence measured on the log scale in multi-armed bandits the action size of |A| = 10 The shaded area represents 95% confidence interval for five runs.
6 EXPERIMENTAL RESULTS
For the RL algorithm, we implemented RAC Yang et al. 2019) method that is generalization
of SAC (Haarnoja al. 2018) in terms of the regularization choice. We considered the class of
separable regularizers s1
Ea-pl (p((a))) (1) Shannon entropy (f((x) = log(z)), (2) Tsallis by default), (3) exp regularizer (f(xx) = e e*), (4)
entropy Ty (p(2; g) = 9- - (29-1 1),
cos regularizer (f(x:) cos( (x)),, and (5) sin regularizer (f(x1) = - sin .²) We evaluated our approach on three topics (bandits, multiple goals, and MuloCo environments). The main compar- ative method was RAIRL with density- -bsed model (RAIRL-DBM) since this model shares the identical level of expressiveness as our method when the parameterization of A is specified.
6.1 LARGE-SCALL MULTI-ARMED BANDITS
We first considered multi-armed bandit problems, where the cardinality of action spaces is varied. Learning the optimal distribution of Te becomes challenging as |A] increases, because the frequency of each sample becomes sparse due to the curse of dimensionality (Bellman et al. 1957). For softmax
each experiment, a stateless expert distribution 7g was generated by the parameters distribution Fe (i) exp(a)//E, exp(x,) where the logits 2; were randomly initialized to uniform distribution. We set the action size to |A| 102 103 10 and restricted the sample size to 16.
Figure shows that the Bregman divergence was large for MD-AIRL the early training phase, because we chose the initial step size 7) to be greater than (01 = 0.5). MD-AIRL exceeded the discriminative performance of RAIRL after certain steps, while the progression of RAIRL mostly stopped at local minima. Table T shows that MD-AIRL achieved overall lower Bregman divergence on average when three different cardinalities and five regularizers were considered. MD-AIRL out- performed RAIRL in four cases by choosing effectively low step size at the 1/r to be less than (a,, = 2). These results match properties of MD algorithms and our convergence analyses. There- fore, argue that constrained update rule with appropriate step sizes necessary for robust reward acquisition and imitation for the situations when the total number of data samples is limited.
6.2 CONTINUOUS MULTI-GOAL ENVIRONMENT
We then considered an environment with two-dimensional continuous state space. In this ioronment, an agent is a point mass initialized at the origin, and the four goals are located in the four cardinal directions. To draw meaningful reward surface, considered multivariate Gaussian dis-

---

Under review as a conference paper at ICLR 2022
Shannon entropy
Tsallis entropy
esimattin
(a) Multi-Goal Environment
MD
Entropy
1,381
MD-AIRL
Stop 5K
Step 300K
Step 5K
Step 300K
(b) Goal Entropy
(c) Reward surfaces and trained policiesfr (state
(5, -1))
Figure 6: (a) The multi-gh multi-goal environment, MD-AIRL trajectories, and the ground-truth rewards
are shown. (b) The information entropies for the probabilities of achieving four goals. The x-
axis indicates the q value of the Tsallis entropy regularizers. The Shannon entropy regularizer considered by the case of g 1. (c) The top of each column shows regularized reward surfaces obtained by Ty. The middle and bottom show regularized rewards from T and the policy zg-
tribution policies with full covariance matrices. We parameterized covariance matrix of Gaussian policy using lower triangular matrix which is outcome of L.DI decomposition (see Appendix C
Figure 6 (a) shows trajectories generated by the trained agent. Figure 6 (b) shows that MD-AIRL achieved higher entropy for reaching the goals. (e shows reward surfaces with regularizers,
which was calculated by (s, a) + <p(TT((( (als)) for each point of a E A and 8 = (5, -1). During the training, the MD reward was similar to the estimated ground truth using adversarial training. However, the surface of MD-AIRL became flatter than the ground truth estimation when was sufficiently close to the expert behavior. As a result, we claim that drastic changes the target distribution, which are one of the typical characteristies of adversarial frameworks, are prevented. We argue that these characteristics mitigate overfitting caused by unreliable discriminatve signals.
Hopper
Walker2d
HalfCheetah
Ant
4000
5000
5000
4000
3000
4000
4000
MD-AIRI RAIRL
2000
3000
2000
3000
2000
1000
1000
random
1.1
1.5
1.1
1.1
1.1
1.5
4000
5000
5000
4000
Score
3000
2000
2000
4000
3000
2000
4000
3000
2000
3000
Bc
NAIRL
1000
1000
1000
1000
random
1.1
1.5
1.1
1.5
1.1
1.5
1.1
1.5
Figure 7: Average scores in MuJoCo benchmarks. The x-axis indicates the value of the Tsallis entropy regularizers. Shaded regions indicate 95% confidence intervals for four different runs. Top: 4 demonstrations. Bottom: 100 demonstrations.
6.3 CONTINUOUS CONTROL: MuJoCo
We validated MD-AIRL on MuJoCo continuous control tasks (Brockman et al. 2016). We as- sumed diagonal Gaussian policies for both learner's policy and expert policy πg. Instead of the tanh-squashed policy (Haarnoja et al. 2018). we used the hyperbolized environment assumption of RAIRL, which means that tanh is regarded
part of the environment.
For each tasks, we considered two different numbers of episodes collected by an expert policy. In Figure 7 the performance of MD--AIRI, RAIRL,, and behavior cloning (bc: Pomerleau 1991) al-
8

---

Under review as a conference paper at ICLR 2022
Hopper
Walker2d
HalfCheetah
Ant
5.2K
4.8K
Score
HD-AIRL
2K
export
0
500K Time Step
1M
0
500K
1M
0
DDK
1M
1M
2M
Time Step
Time Step
Time Step
Figure 8: Average scores during training with 4 demonstrations (Tsallis regularizer Ty with q 2).
gorithms are shown with the expert and random agent performance. In terms of sample efficiency, MD-AIRL outperformed RAIRL on Hopper- r-33, Wa 1 and Ant-v3. The performance gaps between MD-AIRL and RAIRL were more prominent in 4 episodes of expert demonstrations. The training curves in Figure 8 indicate that MD-AIRL showed lower variance than RAIRL espe- cially after early phase of training. It can be concluded that MD-AIRL inherits the sample efficiency of AIL algorithms in challenging RL tasks benchmarks. Additionally, the algorithm is highly stable with respect to limited sample sizes, which is in alignment with our theoretical analyses.
7 RELATED WORKS
Statistical manifolds. The Hessian of strongly convex function forms a metric tenser of a man- ifold called Hessian geometries (Shima 2007 Bregman divergences are similar these metrics, providing useful metric-like properties (Butnariu & Resmerita (206). Using the Bregman diver- gence allows to solve many optimization problems, generalizing traditional approaches such as least squres (Boyd et al. 2004 Urruyy & Lemaréchal 2004). Probability distributions can be considered as points in a geometric space. representative statistical manifold is the information
geometry induced by the Fisher-Rao metric (Amari 2016 Bauer et al. 2016 Nielsen 2020).
Regularized IRL. Energy-based policies (i.e. Boltzmann distributions) have been appeared in al.)
early IRL. researches (Ramachandran & Amir [0077] Neu & Szepesvári [0077: (Babeş-Vronen
2011]. Notably, MaxEnt IRL (Ziebart et al.) 2008 2010) is a representative IRL algorithm based on information theory. Other statistical entropies have also been applied to the imitation learning problem, such as the Tsallis entropy derived from Tsallis statistics (Lee et al., (2018). Compared to work allows more realistic situations where the expert policy cannot be precisely attained due to insufficient data, thanks to theoretical foundations originated from optimization studies.
RAIRL which also use various convex regularizers (Jeon et al. (2000),
NEW R1,
Mirror descent. MD is closely related to algorithms regarding non-Euclidean geometries with
discretization of steps such natural gradients (Amari) 1998, Raskutti & Mukherjee, 2015 Gu- nasekar et al. 2020). On the primal space, the infinitesimal limit of MD step corresponds to Riemannian gradient flow (Do Carmo 2016 Gunasekar et al., 2020). The online MD algorithms possess rigorous regret bounds (Srebro et al., [001]] Lei & Zhou 2020); thus they can be highly
efficient in terms of the number of evaluations until convergence.
DISCUSSION AND CONCLUSIONS
In this paper, we presented novel IRL framework. We provided an mirror descent solution on reward functions and corresponding theoretical arguments. We proposed MD-AIRL, practical adversarial IRL framework that can solve challenging imitation learning tasks. We verified that the proposed method has clear advantages over previous AlL. methods in terms of robustness. As the reward hypothesis grounded obtainining a robust representation of the expert policy using IRI., argued that current IRL studies lack robustness and theoretical guarantees for practical situations.
FIX
R3
Considering RL and its inverse problem with geometric perspectives is vital for achieving desired goals in realistic situations. Although our work covers various online imitation learning methods with MD, it does not include some other cases when the proximity term is of other statistical diver- gence families such f-divergence (Amari, 2016). Additionally, the boundedness and continuity assumptions on Bregman divergences in our analyses are usually justified, but outliers exist such as KI. divergences. More sophisticated analyses these general cases remain as future works.
NEW R3

---

Under review as a conference paper at ICLR 2022
REFERENCES
Pieter Abbeel and Andrew Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-first international conference on Machine learning, pp. ACM, 2004.
Sreangsu Acharyya, Arindam Banerjee, and Daniel Boley. Bregman divergences and triangle in- equality. In Proceedings of the 2013 SIAM International Conference on Data Mining, pp. 476- 484. SIAM, 2013.
Shun-ichi Amari. Natural gradient works efficiently in learning. Neural computation, 10(2):251- 276, 1998.
Shun-ichi Amari. Information geometry and its applications, volume 194. Springer, 2016.
Monica Vroman,, Vukosi Marivate, Kaushik Subramanian, and Michael Littman. Appren- ticeship learning about multiple intentions. In Proceedings of the 28th International Conference on International Conference Machine Learning, ICML' 11, pp. 897-904, Madison, WI, USA, 2011. Omnipress. ISBN 9781 7781450306199 95.
Martin Bauer, Martins Bruveris, and Peter W Michor. Uniqueness of the fisher-ras metric on the space of smooth densities. Bulletin of the London Mathematical Society, 48(3):499-506, 2016.
Amir Beck. First-order methods in optimization. SIAM, 2017.
Amir Beck and Marc Tehoulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):667-77,, 2003.
R. Bellman, Rand Corporation, and Karreman Mathematics Research Collection. Dynamic Programming. Rand Corporation research study. Princeton University Press, 1957. ISBN 9780691079516. (tLp:tp:: //books google.oooooooooooooooooooooo co bbbooks?ia-ve of o PAACCAAJ
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge uni- versity press, 2004.
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016.
Dan Butnariu and Elena Resmerita. Bregman distances, totally convex functions, and method for solving operator equations in banach spaces. In Abstract and Applied Analysis, volume 2006. Hindawi, 2006.
LI Chongxuan, Taufik Xu, Jun Zhu, and Bo Zhang Triple generative adversarial nets. In Advances in Neural Information Processing Systems, pp. 4088-4098, 2017.
Manfredo P Do Carmo. Differential geometry of curves and surfaces: revised and updated second edition. Courier Dover Publications, 2016.
Amos Fiat and Gerhard Woeginger. Online algorithms: The state of the art, volume 1442. Springer, 1998.
Chelsea Finn, Sergey Levine, and Pieter Abbeel. Guided cost learning; Deep inverse optimal control via policy optimization. In International Conference on Machine Learning, pp. 49-58, 2016.
Justin Fu, Katie Luo, and Sergey Levine. Learning robust rewards with adversarial inverse rein- forcement learning. arXiv preprint arXiv: /248, 2017.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized Markov decision processes. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2160-2169, Long Beach, California, USA, 09-15 Jun 2019. PMLR. URL http: //proceedings mlr. pwwsssppess//e.e. /
9 gwwsteeiil.... html
Seyed Kamyar Seyed Ghasemipour, Richard Zemel, and Shixiang Gu. A divergence minimization perspective on imitation learning methods. In Conference on Robot Learning, pp. 1259-1277. PMLR, 2020.
10

---

Under review as a conference paper at ICLR 2022
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farkey Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Infor- mation Processing Systems, pp. 2672-2680, 2014.
Suriya Gunasekar, Blake Woodworth, and Nathan Srebro. Mirrorless mirror descent: A more natural discretization of riemannian gradient flow. arXiv preprint arXiv:2004.01025, 2020.
David Gutman and Javier Peña. A unified framework for bregman proximal methods: subgra- dient, gradient, and accelerated gradient schemes. arXiv, pp. arXiv-1812, 2018.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International Confer- ence on Machine Learning, pp. 1856-1865 1865, 2018.
Elad Hazan. Introduction online convex optimization. arXiv preprint arXiv:1909.05207, 2019.
Jean-Baptiste Hiriart-Urnuty and Claude Lemaréchal. Fundamentals of convex analysis. Springer Science & Business Media, 2004.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in Neural Information Processing Systems, pp. 1565-4573 2016.
Wonseok Jeon, Chen- Yang Su, Paul Barde, Thang Doan, Derek Nowrouzezahrai, and Joelle Pineau. Regularized inverse reinforcement learning, 2020.
Ilya Kostrikov, Kumar Krishna Agrawal, Debidatta Dwibedi, Sergey Levine, and Jonathan Tomp- Addressing sample inefficiency and reward bias in adversarial
son. Discriminator-actor.coo imitation learning. arXiv preprint 1809.02200. 2018.
Kyungjae Lee, Sungjoon Choi, and Songhwai Oh. Maximum causal tsallis entropy imitation learn- ing. In Advances in Neural Information Processing Systems, pp. 4403-4413, 2018
Yunwen Lei and Ding-Xuan Zhou. Convergence of online mirror descent. Applied and Com- putational Harmonic Analysis, 48(1):343 - 373, 2020. ISSN 1063-5203. doi: https://doi.
00.0005.5.000... URL hattp://wwit www.eceeieeet.............. www. www.:/iieccc./eeeeoooeooeoa
atticiee/s1//10055311188333
Arkadii Semenovich Nemirovsky and David Borisovich Yudin. Problem Complexity and Method Ef-
ficiency in Optimizaation. A Wiley- Interseeenec publication. Wiley, 1983. ISBN 9780471 1004555.
URL httpttttttss/ooool
Gergely Neu and Csaba Szepesvári. Apprenticeship learning using inverse reinforcement learning the Twenty-Third Conference Uncertainty in Artificial
and gradient methods. In Proceedings the
Intelligence, pp. 295-302, 2007.
Andrew Y Ng and Stuart J Russell. Algorithms for inverse reinforcement learning. In Proceedings of the Seventeenth International Conference on Machine Learning, pp. 663-670, Morgan Kaufmann Publishers Inc., 2000.
Tu Nguyen, Trung Le, Hung Vu, and Dinh Phung. Dual discriminator generative adversarial nets. In I. Guyon, U. V. Luxburg. S. Bengio. H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran As- sociates, Inc., 2017. URL htttpsss:/ppcccedgg...o.t neurips... httpppp...c/ppper/////1eee eddeeicccoee17.cccd136223333 /aec2 -aaaaaeeccaaap---PP
Frank Nielsen. An elementary introduction to information geometry. Entropy, 22(10):1100, 2020.
Frank Nielsen and Richard Nock. On r\, 'enyi and tsallis entropies and divergences for exponential families. arXiv preprint arXiv: 105.3259, 2011.
Dean A Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neu- ral computation,
1991.
Deepak Ramachandran and Eyal Amir. Bayesian inverse reinforcement learning. In Proceedings of International Joint Conference Artificial Intelligence, pp. 2586-2591, 2007.

---

Under review as a conference paper at ICLR 2022
G. Raskutti and S. Mukherjee. The information geometry of mirror descent. IEEE Transactions Information Theory. 61(3):1451-1457, 2015. doi: 10.1199/1122115288888.
Walter Rudin. Real and Complex Analysis, 3rd Ed. McGraw-Hill, Inc., USA, 1987. ISBN 0070542341.
Hirohiko Shima. The geometry of Hessian structures. World Scientific, 2007.
Nati Srebro, Karthik Sridharan, and Ambuj Tewari. the universality of online mirror descent, In Advances in neural information processing systems, pp. 2645-2653 2011.
David Williams. Probability with martingales. Cambridge university press, 1991.
Wenhao Yang, Xiang Li, and Zhihua Zhang. regularized approach sparse optimal policy in reinforcement learning. In Advances in Neural Information Processing Systems, pp. 5938-5948, 2019.
Brian Ziebart, Andrew Maas, Andrew Bagnell, and Anind Dey. Maximum entropy inverse reinforcement learning. In Proceedings of AAAI08 Proceedings of the 23rd national conference on Artifical intelligence, volume 3, pp. 1433-1438, 2008
Brian D Ziebart, Andrew Bagnell, and Anind K Dey. Modeling interaction via the principle of maximum causal entropy. In Proceedings of the 27th International Conference International Conference on Machine Learning, pp. 1255-1262. Omnipress, 2010.
12

---

Under review as a conference paper at ICLR 2022
A PROOFS
We define the space of policy as an object A which is a vector space formed by a collection of
|8| elements of unit (I-A) si-siplex:s: A { [11e] +.... + dle Al i= 0g 1 and 0g 2 for i E AA }. We assume that each space of simplex is a subset of a specific Banach space called
L' space (R--, I|-II), where ||-|| is a p-norm on A. The dual space of L space for < < 00 is L
space I1-1),, where I|- is defined
q-norm (1pp + 1/9 1). We assume 1 < p S 2 for the convergence property in the dual L space. We start with following definitions.
Definition (Lipschitz constants). Given two metric spaces dx) and (Y, dy) where d denotes the metric set X and dy is the metric set Y, function f X Y is called Lipschitz continuous if there exists a real constant k 2 O such that, for all an and 222 in X,
(x(((x)) ( S dx x2).
(15)
In particular, a finction f is called Lipschitz continuous if there exists a constant such that, f S k 1|=1 -22l,, VI1,T2
(16)
where norms I1-I1 and Il- are endowed with each space X and Y respectively. For the smallest that substitutes L is called the Lipschitz constant and f called the L-Lipschitz continuous function.
Definition 3 (Discrete-time martingale). If stochastic process (Zib121 satisfies B[[Zn]] S oc and
1) ( Xn) [ S Zm; 2) E) 1 Xi,..., Xm] x=]=30 =7, 3) B) Z8[ XI,..., Xn) 2 Zao
then, the stochastic process (Zehez called a 1) submartingale, 2) martingale, and 3) super- martingale, respectively, with respect filtration (X1)121.
The following analyses and proof' follow the results appeared in previous literatures for general aspects (Nemirovsky Yudin 1983; Gunasekar et al. 2020 Srebro et al. [011 Lei & Zhou 2020) Beck & Teboulle, 2003; Raskutti & Mukherjee] 2015). Our analyses extend existing results to imitation learning, and they are also highly general to cover various online methods for sequential decision problems.
A.1 PROOF OF LEMMA I
Proof of Lemmal
The conjugate operator of 2l satisfies the following identity (Lemma I of Jeon
al. (2220)
max (5", vil 1((=))
ERRR
max (#t,, ((,(()(())))))) )) (x", (-'. V(((=))) + +(((T) - -(#*))
min 2(#*) - 2(TT)) (VV((*)), - >>)AA
#'ERd
= min Do(#*'(TT*)
EEER
for every state & E S. By the property of Bregman divergence, and the convexity of (=(*==((=*) with respect 7 (Geist et al. 2019 Acharyya et al., 2013), the optimal condition is obtained by
the unique maximizing argument 7 (--s8) (-1s). By taking gradient to both sides with respect to viz we yield π VΩ" (1'((>)) (v*).
If there is another ग + π that makes v4 = v.. this contradicts the property of unique maximizing arguments for conjugates. Therefore, V/ uniquely defined for each π and V12 (x)) A
We model the reward approximator regarding actions as & E (A = {sb (ss = vh (x a), Vs E S.a E A, n E A%). where th defined th (8,a) = St' a; )T) Ear (s(aa''))) + ((*(-ss)). Note that V. different from V((()). but it is shifted by the amount of -E,, -Eass)(-ls) [2' (''(s.'':)) a): + 2(T) for every element of th (s. Therefore, the operators V. and AΩ are link functions that form natural isomorphisms of functions.
13

---

Under review as a conference paper at ICLR 2022
A.2 PROOF OF THEOREM
We consider the unique fixed point of T. as the solution of infreas lime- [[f 7a). where the expectation indicates that we take consideration for all and ft. By equating derivatives to zero, we write (I( lim [F, We provide more general results than previous imitation learning, some of following statements include the case of inf rE25, (T r)] > 0, which means the estimates { )r do not converge to the fixed point of π., so limy+so || Tg.t >> 0. Thus, MD-AIRI. and other online MD algorithms allow realistic settings such as scarcity of data or imperfect demonstrations.
We first introduce a key relationship regarding cumulative gradients in our online MD setting.
Lemma 2. Let { (Te,)) and { be policy, estimate, and step size sequences, re- spectively. The subsequent policy W++1 in Equation (5) is obtained by an RL algorithm using the derivation of 4r41 Equation resulting to the following equation:
1-41(-1s)= = argmin Dn (
+ (1 DmF) E
(17)
*'EAA
We have for t E,,
Tr (Q[(T)) (((Ta))) VN(*)) VQ(T++1)
(18)
where we write VD(TT) [
Proof of Lemma
Since the optimization is convex with respect to each x², we equate the deriva-
tives to 0 at T++1
Te (V((TT)))) - VI(()))))) + (01mm))(v0) (V - = 0, V.
Finally, we derive Equation 18 as
The Th ((V((((()))
+ - (1- - v(((T))
V[((((+) - 7h V))( (1 [[( =0
V((m)) (((((+)))))+)))))) - (V)(m)) v)(
Therefore, the proof complete.
Lemma 2 indicates that the distances between dual maps are equivalent to n: (/lV V Therefore, if the step size decreases lim 1/t O, lim [/ (D( 0: thus, our argument in Section 3 is reasonable when Ω is strongly smooth.
Next, reintroduce the three-point identity as follows.
Lemma 3 (Three-point identity). Let Th. and ne be any policies with given state. We have the following identity:
(Vl(Ta) V(((T), Te mb)A = D - Da(T<l( + Da(TTolTTa)
Proof of Lemma
This can be derived using the definition of divergence as follows.
(T(TTelmm)) (a( + Dn(Fol(Ta))
M(me) (7())) (V](T)), Tee To)A -(((T)) + (((ma))))))))))))(()))) + (Vl(TTa); Tec Tala + - ((T.)) - (VI((Ta) To Tald
(VN(Ta) V(((T), Te -ome mols
Therefore, the proof is complete.
We now introduce basic identities regarding a Bregman divergence Lemmas and that are used to address progress of the algorithm.
Lemma 4. Let Th. and ne be any policies with given state. The following identity holds. Da( Da(Fell<a)) Da( + (Vi(FF)) V[((T)) Te ka)a-
(19)
14

---

Under review as a conference paper at ICLR 2022
Proof of Lemma 4 By Lemma
3 have
m (m(Tellma) - DD(moll=a) ( VS((T)); Te - -
Utilizing the identity of two Bregman divergences
Dn( D π) = (VQ(T) (
(20)
we separate Te Th into Ta and Th and write the rest of derivation as followings.
Da(Te]| (12(TTllT
-Do((To(TTa) + (Vi((T)) ([(T)) Ta -T)4 +(VD(T.)) VQ((T), To Tald
Eq
-D(TTalTT)) + (V)(TT)) V[(T)) - -o
Therefore, obtain the desired identity.
Lemma 5. Let To, and nee be any policies with given state. The following identity holds.
Da(TollTa) Da( (VI((=)) V[(TF)) -TTA4 + Do(Tollae).
(21)
Proof of Lemma
By Lemma 3 we have
Da(Tol - Da(Fol(Ta) = - + (V)(TT) V[((TT) -T))A
We separate Vl( (T(TT) into V(((T.) Vl((T.) and V[((T)) Vi((T)) and write the rest
of derivation as followings.
PI(Ta||Ta) (Te(Tellm
Tola + +(VS(TTT) VZ(TT)) ne TA)A -D2i(Tel + -V -
E4
-D( (T())) V[(T)), -TD)
Therefore, we obtain the desired identity.
We show the key arguments to prove Theorem D in the following lemma. Lemma 6. Assume inf [[fe(T R, r)] 0. Assume also that Q w-strongly convex and VQ is
L-Lipschitz continuous for 2 0 and I, 2 0. limimooo Th 7 Dn (n(" m
0 for
Te. then { J satisfies Equation holds with some constants n E N and 0.
Furthermore, if Q is strongly smooth, then Theorem (a)
Proof of Lemma 0 First, show the condition of lim;-+00 1 0. Assuming all states are reach-
able (Fu et al. 2017 Definition B.I), the condition lim; Er....rr [Σi 7 Do ( | ) 0,
NEW R3
implies lim, E,.... [|,
- ف.. []] = O, where ||-I] is a matrix norm induced by the p-norm on A.
Then, our aim is to show that the gradient of strong convex function for मe converges to V12 T3g as
lim E E t-+00
[[()))) v 0.
(22)
To prove this point, use the continuity of VΩ for any > 0, there exists some 0 < d such that [[V((T) - v((==)) whenever || Tel
When ||
Tel 8, upply the L-Lipschitz continuity assumption to find
||][(T)= V(((TT)) < L||T - -gll-
(23)
where 1| is a matrix norm induced by the g-norm. Combining Equation 22 and Equation we know that
23
E E
[)((T) - v(((T))] s L-
Er,...r [l]T L
Tz [].
(24)
However, lim, oc E
|Tee - Tell| = 0 ensures the existence of some n N such that for
t > there holds Er Ener [[/))(m.)) ([(T))) < 2e for some n.
|i Tell < e/L. Applying this inequality to Equation 24 we have
15

---

Under review as a conference paper at ICLR 2022
For temporal estimation, let denote the infimum of the expectation / = is ([) [))( > O. From 2 we have 7/ (V v((Fz,))) = (1) V Taking
the expectations on both sides of this equation yields
Th S T - [ [[( - v[(T=,))IL]] = E [[+ - v2((T++)
}bb]
Hence the convergence of the point (T)( is confirmed by taking the limit: lim 7tt = 0.
Next, show Σz= N xc. By the w-strong convexity by the L-Lipschitz continuity of Ω can find inequalities as
2L (T(()
(Vi(()) V2( x #)4 -|
+12
(25)
We note that Tc+1 Rg,al 1 |ITE eg so that there is a constant & that satisfies E[I TC-1 Te,t+1 [1] 2 E Te+1 - Te,t [I] +e. Therefore, taking expectations in Equation (21) (setting ma 7,,, Th = Te+1, and Te = m,), for lime-soo 1/2 = 0 and the strongly convex Q we can find
E [ (s,))1))
2 En DD (T(TT++)))) ||]+++1|[[]))))))())))) +'s
2 (1 - ) E. (I
+ Er.....e [Da(m441llg + e (Eq. 21
2 (1 am E T..... [ +-"
(26)
for some f and 0 < e' < e". The positive constant a 24/3 is derived by the inequalities in
Equation (25 We omit the conditioned states (superscripts) for simplicity of the derivation.
Since lim, on 7/2 0, we can also find constant N such that 1/. (3a)-1 for i 2 Applying the inequality - x > exp( 2xx) for x E (0, 1/3), we derive another inequality
E Da Te+1 (2, 2 exp(-2arp ) E. (ee(Te((=E.)))
V2 n
(27)
Applying this for L. T I,..., n yields
E Bn [De (T [T, N
II exp( 2am)
E Bry.n [Dea(T [e,m)
L(=++1
(28)
-2a Σ Tt
=xxp
t=++1
Using Equation (88 conclude E Enyyn P [e) O. Otherwise, we have
En..... Do((n ]e = E E DDe (T [[ =
according to Equation 27 which leads to E [[ITT [|] Erg [||TT]]
+ [| 0. This implies Wn āæ.. antialmost surely, leading to [ re)
0. This is contradiction to the previous assumption inf infzesg (T,,)) > 0. thus
E [Da(Tn+1 l| > 0. Let us suppose the ideal case that the estimation process
learns the exact in f - 0c. In order to satisfy the limit limy En....r [Da(TT [ = 0 we
see from Equation (88 that E 1) c0.
Now, we show that Theorem 1 (a) holds. Since Ω is w-strongly convex, so S2 is (w (w-")-sttrngly smooth with respect to I1-1k- Additionally, the L-LLppscitzz continuity of VΩ implies L-strong smoothness of Ωi thus, naturally. 52" is L-strongly convex.
Combining these, for Vt n, the condition 7). S (3a) induces
E E ( ( [+]] 2 (1 am En..., [[(
+ (2L) E
7441 [[[[ - V
and by Lemma we get
Eg E [Da(Te+1 [0]++1]] 2 (1 a37; ) F.n.... [
+ (2L) " T [[((T)) [1L
16

---

Under review as a conference paper at ICLR 2022
Using the
inequality, obtain lower bound of the last term
E [ V 2 ( [I ([
6
Thus, we obtain the final inequality as
E E [Po(==+1lle,t+))
(1 ane Bm [Da(Tel [g.+)] (2L) (2 222 n.
Applying this inequality from i = 7' 2 + 1 tot t = n 1, we obtain
E Engerri (D [e.
2 B (Ta(TTIl(TT,))
II (1 am) tma+1
+ (2L) -
Σ
II (1- amI)) k=t+1
t=n+1
12 18
Σ M/
II (1 amk).
(=n+1
kmt+1
By the Cauchy-Schward inequality and our bound
0 1 - aTk I 1 for k 2 we have
T
II (1 }
T
1/2
Σ (=++1
II (1 - amk) S
Σ
(1-am))
(T- n2
Th
T
kmt++1
1=++1
kmt+1
Hence
T
T II (n-))))
T
T
Σ
11
2 aT
(1 amk)
1=++1
k=t+1
(=1-1
k=1+1
T
T II (1 am7)
(1 -m)))
aT
-))
(=n-
k=t+1
T
T
(1 am))
II (1 -asss)
22(T
m))
t n-
k=H+1
k=t
T
amm))
(2
m)
(=n-1
k=t
am]++))²
(2
T n
Therefore, obtain the lower bound of
[1) 2 Mu (2L)
E En...r D P P
T - n
Since the Bregman divergence is bounded for all states, the sequence {yd (= [mm"")) will con- verge as + sc. Applying the monotone convergence theorem, we can interchange expectation and summation, which yields
E Eng...
7 (o( (- =
Σ E B oo ( DD(TTT (1s))
Σ
7 E
> n1 11 (2L -2 182
VT 2 n
- nl
This verifies Theorem (a) with the constant 1 (2T. (2Tm) -162
17

---

Under review as a conference paper at ICLR 2022
Last, show convergence unique fixed point of using the particular form of ny in Equa- tion (
Lemma 7. If {1t ii satisfies Eq. lim E E Ei= (= = 0. Furthermore, the step size takes the form T then E Br Di=0 Da +T
(1/T).
Proof of Lemmnl 7 According to Lemma 4 and the Bregman divergence of the conjugate Dar, the one step progress regarding TE, can be written as
Dn( (= (T) (VD(=)) (( n. m)) Dn(
17 (V2((T) (O(TT,)) n. m²) Da- (V((=)))))
where we omit given state. As w-strong convexity of Q implies the (w--)-ssroo smoothness of S2, we have
n [V[(TT)) (f, (29)
Dr- (V
[ V
2w
We bound [[( VΩ Ne.
by 2 V()(m))) - (1l >12 V((x.) (f( following
the work of Lei & Zhou 2020 obtain
Since VΩ is cocoercive with f. bye the Lipschitz continuity,
[Q((m))
Va( < L(VA(T.)) V.(TT), - nx)
thus
Da( (r(xx=|TTet)) DD (1 (VV((T)) - V2( - me)
(1 1c )m (T.( Vn(T)) m. m.) + n [I] (
(30)
By taking expectation, it follows that there exists n E N such that T S w for t 2 n holds
27
E,, (Ie s (T.(T.I1= The (T. 27/²"
(31)
where z is the constant = ~ { - (113.. Let { denote a sequence of A, =
E [D][T=[[=)]] Then we have
A S
1 (1-2)
T/t 2
Vt 2 n. A, + 2T
(32)
For constant h 0, claim that As, < h for some / n'. Assume that this is not true, and
find some t2 2 t such that A, >> ht vt 2 f2. Since lim Th = O, there are some t > t3 > to that 1p S 4h However, Equation (32) tells that for 2 t3.
A <
[1 (1-2)
Nt A 2n Atg
h
Σ T 0 k=t
(as t + oo).
This is contradiction, which verifies A, < h for t > n'. Since lim ne O, can find some T) that makes A, to be monotone decreasing. Then, we can conclude that the nonnegative sequence {A, converges by iteratively applying the upper bounds.
We now prove Theorem
4 (b) under the condition and the choice = t+1
the step size sequence.
The estimate becomes
1
2
162
A41 S
A
Vt n.
+
(t+ 1)2
It follows the recurrence relation as
1(1 + 1)A - (t 1)LA, 162, 11 2
Applying this relation iteratively, we obtain the general form of inequality.
(T - 1--17AA- S (n-11)n, 16:(T -n).
nn) VT 2
therefore we get the inequality as follows:
E Engrr [Da(T. [[ < (n- - 1)nE, .... [Da
16z
T 2 n.
(T -T'1)
T
By applying the monotone convergence theorem similar to Lemma
6 we conclude that
Enger Ei 7 Da(=. (1s))(((s))))==<<((())) (1/TT)
18

---

Under review as a conference paper at ICLR 2022
A.3 PROOF OF THEOREM 2
Necessity. We rewrite the inequality in Equation (26
B Da (T++1 [g,141)] (1 2w 1/ ) T. Do (Te mE,,
(33)
Since we assume that d converge from previous arguments, onsider the step size sequence 0 < S (2+x)TT for K > 0 and 2 where n E N. Denote constant 2+ log 2+ and apply the clementary inequality
FIX
R3
2
1 2 exp(-āx); VO < x S
8
From Equation 33 can be obtained that
I T [Da (Te (ore+1|/eeee [|= 2 exp(-2nl -2 -1 11p) " (D(TTllaaaa))
Applying this inequality iteratively for t- ....... T 1, then gives
T-1
E Br (I
exp( 22L6 '1))
t=n
T-1
exps
2ū Tw
Σ
n
Da(Tn
t=
From the assumption Tig lim Brg [
Ano we have [I
0. The convergence
then implies Σ 11: OC.
Sufticiency. Here we use the estimate
(32) derived in the proof of Lemma However, in the
optimal case, 2 _ (. r] so 32
takes the form (we can choose n by Equation 31
Ast1 S Ne A., E.
(34)
2
This implies that for any 0 < h, there must exist integer E N such that A, y for t t1. Otherwise, A, > 7 for every t 2 t2 with to 2 t,, which leads to a contradiction:
h
A+11 < A
mh -00 (as - oo).
k=
Equation (34) also tells us that the sequence {At of nonnegative numbers is monotone decreas- ing. Hence A, < h for every i tı, which proves the convergence of Ar
lim E, (D((T.ITTT))) 100
lim A₁ = 0. t-
We now prove the second point in Theorem 2 which is under the special choice of constant step size
sequence V/+ = mh It follows from Equation (33 that Ar (1 2 -m)) AT- A₁. Hence, Eq (34p translates to
A (1 A/:
A₁ by iteration starting from / = 1. This verifies the theorem with = = 2.m and = (1
from which we find Ar < (1 // m 11
A.4 PROOF OF PROPOSITION
The proof is based on Doob's forward convergence theorem.
Theorem 3 (Doob's forward convergence theorem). Let {Xi)ieN be a sequence of nonnegative random variables and let (Fehien be filtration with F, C Fi+1 for every i E N. Assume that E [F] & X, almost surely for every E N. Then the sequence {X,} converges to a nonnega- tive random variable X almost surely.
19

---

Under review as a conference paper at ICLR 2022
We follow the proof of Lemma and apply Eq. Equation 30 implies
330 Since (Th Te, Vl((TT)) v(((T)) 2 0,
Br, Da(T. [(+) < Do (T. + Th E VD(T)) VSR(TR;)))3] 14 22n. n
(35)
The condition Et=1 nh < enables us define stochastic process {X₂) by
1 B[IV[((T)) ( Σ m
X₁ Dr((T.1(<<+1)))
we know that F2 [x++1] & X for 2 n. Additionally, X, 2 0. Therefore, the stochastic process (X₂) t-=+121 is submartingale (equivalently, {-Xe)e-a+121 is supermartingale). Then the sequence {X converges to a nonnegative random variable Xx0 almost surely. According to Fatou's Lemma and the convergence lim E E[ 7 (..(T.((m)) 0 for any states a proved by Lemma 7
By (35
by Lemma 3
we obtain
NEW
E X
E
lim Σ
inf B 0. (1sss S ( inn
follows that the sequence of discounted sum (Eis DDO(T (1s+)]] CEN converges to almost surely.
B TSALLIS ENTROPY AND ASSOCIATED BREGMAN DIVERGENCE AMONG FULL COVARIANCE MULTIVARIATE GAUSSIAN DISTRIBUTIONS
In this section, we briefly reintroduce the tractable method derive Bregman divergences and reg- ularized reward functions proposed by Nielsen & Nock (20IT) and Jeon et al. (2020). Then, we identify specific paremeterization model Gaussian distributions with full covariance matrices.
The standard form of the exponential family is represented as
(x (x)) - F(0) + k(x))
(36)
The parameterization is as follows:
0
0
Σ
=
02
t(x)
I
xT
1 T ----5110 + In (n(2
F(0)
0 0z
0g
In| 111-000-1
z1
k(x)=
0,
where we can analytically recover the multivariate Gaussian distribution (Nielsen & Nock (xp((0, F(0) + k(x)}
2011
(37)
=exp T
ir xx
in
7"
1
4 Tx
In (n(2x) =u
(38)
2
(2m) 1/12
1
exp
y
2
1
-x
1 - 11 )
(39)
1
(27)4/2pyj1/2 exp
(x 11)
(x u)
(40)
For two distributions π and A with kxx) = 0, Nielsen & Nock 2011 proposed the function I I(.):
1 = {()) dr expp F(00 + 30) aF -FF(0)
20

---

Under review as a conference paper at ICLR 2022
where the detailed derivation is as follows:
/ {x)) dx
-B / (()) -BP(0)) dx
copp( =fopp + (0,t((x))))))))))(()))))))))(() (00 F(a0+ exp F(a0 + +00 - -F(0)) dr
exp F(a0 + 30) aF()) - |F(8)} / capp(a0 + 20,
30,0+ t(x)) F(at + }6)} dr
= =exp [((0+++ 30) (F))) - BF(0)}
B.1 TSALLIS ENTROPY OF FULL COVARIANCE GAUSSIAN DISTRIBUTIONS
For ((x;)) (- (1) 1), the Tsallis entropy can be written as
- (<))--1
(T) == - ExNTp((i: (Tx))
dx
q 9-1
1 [<(x)* dr
1
(1 (TT,T;q9000
q 9-1 1 exp (F(10) -FF(O))
q
exp(F((0))
g-1
If is multivariate Gaussian distribution, have
1 F(g0) = _ - 1 In(2
2 In
Since the covariance matrix is positive-definite, Cholesky decomposition can be applied, which sep- arates the matrix lower- and upper-triangle matrices. Likewise, we can apply LDL decomposition. Let us factorize the covariance 2 = L diag(o (of,... . L where L denotes unit lower triangular ..... matrix produced by LDL decomposition. Then we have
d g
F(g0) - (F) (1 v)
In
+
|n|
2(1
①)
d
d dlng
(1 1)
In 2T +
In
of
2
2(1
1=1
In 2m
lng
(1 9)
In
2(1 9)
i=1
B.2 TRACTABLE FORM OF d
For separable 22, Vi is written as (Jeon et al. 2020
(f== p(a]s)] Un (n = (s. a) Eo-x
where p(x) - x and accordingly f(x) xx((x). For the gradient of f(-), we have
k (1 (1-929-1) 9-1-
f((x)
k
(q - 92-- 9-1 (g - 1))
9k
(1 - - k
q 1
qpp(x) - k.
21

---

Under review as a conference paper at ICLR 2022
Taking the expectation yields Tsallis entropy follows.
Bx~x (x; + ((x)]
Ee [k qv((x) + p(x)] = (1 g1 g)T (TT + k.
For a multivariate Gaussian distribution х, the tractable form of Ee (- + p(x]] can be
derived by using that of Tsallis entropy 7 (TT) of x. Thus Var can be rewritten as
dh (3, a) (s) + (q 1)T, (TT) In the special case of q = 1 and k = 1, we have u (s, a) log (als).
B.3 BREGMAN DIVERGENCE WITH TSALLIS ENTROPY REGULARIZATION
We consider the following form of the Bregman divergence:
/ (<0)) ((())) (T<(x=)) dx (f (()))(((()))) w(+(x)) } dr
qu(x) h. and A 1, the above form is For (xx) - - -x (x) - (1 - -xg- (1-9---11)
equal
1 1 ()
(xx)
dx - (T( - (q - (*) +1
1
q
/ (())+(1)) dx - TT(T) - -(1 - (+) +
1
q
1-1
9
9
(()))(a)) dr (T) (g 1)Tg
Let us define two multivariate Gaussians as follows:
(x) N (2; p4 E), [MI, Ma]] E L diag(o ... ,.)
#(x) = (2 p. Σ), fi [A_.... , _Pal", E i diag 07. ... .
where L and L denote unit lower triangular matrix. We have
f ((())((0)>- dz = de 1) = exp (F(0)) F(0) - (q - 1))(
where
Σ
0
1
0
1
Σ x + (1 (1 + - 1)
00
0' =
0 +
(q
1)0
0%
and
d
1 T +
1
(n(22) = 1 (1)) 1
2T
F(0) z"
+ Iln
2
2
1=1
F(O) j
1 T 1 1
"
12(2 (1)
d
In 2m
+ In In
F(e + (q 1)0) = 1 (0)
2 In (0))
We can replace some difficult computations using LDL decomposition such as Σ-1
(I) and |Σ| Eim Ino..
22

---

Under review as a conference paper at ICLR 2022
C IMPLEMENTATION DETAILS
Unnormalized rewards of the IRL algorithm often mislead the agent to take unnecessary awareness of termination in knite-horizon MDPs (Kostrikov et al. 2018). To solve the issue IRL algorithms need to remove the difference between regarding steps depending on MDP's time. Doob's s optimal stopping theorem formally states that the expected value martingale at a stopping time equal to its initial expectation. Assume a martingale makes the entire procedure fair game on average, which means nothing can be gained by stopping the play.
Theorem (Doob's optimal stopping theorem). Let a process {X1]=1 be a martingale and t stopping time with respect to filtration {F() Assume that one the conditions holds:
(a) is almost surely bounded, i.e,, there exists a constant E N such that T S.
(b) T has finite expectation and the conditional expectations of the absolute value of the martingale increments almost surely bounded, more precisely, [[[T] < and there exists constant e such that EE] [ - Xxll Fi] S c almost surely on the event {T > t for all t 2 0.
(c) There exists a constant e such that [X Xmin(t,r3 I c almost surely for all t 2 0. Then X, is an almost surely well-defined random variable and E[X;] = x
Then xx is integrable and xx = E[Xo]
Doob's 's optimal stopping theorem states one of the necessary conditions of IRL reward of normaliz- ing the reward measures and making them as a martingale even for mnite-horizon benchmarks.
C.1 NETWORK ARCHITECTURES
For all networks, we use networks with 2-layer MLP with 100 hidden units, respectively. We con- sider the reward model with two separate neural networks (vos, b())) for the proposed reward func- tion for À > 0:
re (s. a) = (3, = ( b(s).
Motivated by RAIRL-DBM, we consider the reward models in Figure The model outputs reward for proximal updates trained by mirror descent and state-only discriminator network. Discriminating state visitation by b(-) is required because the reward function needs to consider every state (espe- cially the state that cannot be visited by my)) until DKL. (P=lltt) as O. Figure 9 (a) shows logits of the softmax distribution involved when calculating rewards when the action space is discrete. For continuous control (Figure 2 (b)), the architecture is similar, where the mean and covariance are used compute a reward for certain action.
(s,
(s(s, a)
b(s)
b(s)
To
To
Wel (8,
V/aa α)
softmax
linear
E (s)
linear
Mb. (s)
FC
FC
FC
FC
Figure 9: Schematic illustrations of MD-AIRL reward models for discrete (left) and continuous control (right)
C.2 MULTI-GOAL ENVIRONMENT
Let the 2D coordinate denote the position of point mass the environment. In the multi-goal environment, the agent is initially located according to the normal distribution (0, (0.1)21). The four goals are located at (6, 0). (-6, , 0). (0, 6), and (0, -6), where the agent move maximum of
23

---

Under review as a conference paper at ICLR 2022
1 unit per timestep for each coordinate. The ground-truth reward is given by the difference between
successive values of a Gaussian mixture depicted as Figure I0
Figure 10: Visualization of the multi-goal environment.
We used the full covariance Gaussian distribution in this experiment (as well as the conceptual ex- periment in Figure 2 Note that the covariance matrix positive-definite and symmetric. To achieve numerically stable computation, we applied LDL decomposition to covariance matrix involving unit lower- and upper-triangle matrices, and diagonal matrix. As a result, the policy network out- puts vector (p(s)T, ((s)),(()TT]) where the additional part ((s) denotes did-1) entries of unit lower triangular matrix. Denote [(s) unit lower triangular matrix from [(s). For example, the covariance matrix can be reconstructed by
2
E(s) =
Additionally, the action samples can calculated by
a (+) + (())(o()) ~~~ ~
Computing inverses, determinants and multiplications with unit triangular matrices and diagonal matrices can be efficiently performed by numerical libraries. Therefore, we can fully model the Bregman divergence and reward using neural networks provided in Appendix B
C.3 MuJoCo EXPERIMENTS
Instead of directly using squashed policies proposed in SAC (Haarnoja et al. 2018), we assume the application of tanh as part of the environment (known as hyperbolized environments of RAIRL (Jeon al. 2020)). Specifically, after action is sampled from the policies, we pass tanb(a/1.01) 1.01 to the environment. We additionally clip the hyperbolized actions to 1, the consider the standard
environment is not tolerant the excessive values of action. Therefore, diagonal Gaussian policy
T(-ss) N(nss), E(s)
where uus) denotes means (I)) [a(s)) and (ss) denotes standard variance [o (s), ( We soft-clip the standard deviation as (s) E [.00, 2] for the stability using tanh. Last, update the moving mean of intermediate values of regularized reward r(s, a) + (als)) and update the RI algorithm with mean-subtracted rewards. In addition to the analyses of (Fu al. 2017 Jeon al. (220)) regarding reward shaping and normalization, mean- zero rewards for training agents have the additional property of preventing termination awareness, as stated by the optimal stopping theorem (Theorem
24

---

Under review as a conference paper at ICLR 2022
C.4 HYPERPARAMETERS
Tables
and
show the hyperparameters of the conducted experiments.
Table 2: Hyperparameters for bandit environments.
Parameter
Value
Learning rate (policy)
1 10
Learning rate (reward)
1 10 -3
o1
0.5
OT
5
X
Discount factor (7)
0.0
Batch size
16
Steps per update
50
Total steps
300,000
Table 3: Hyperparameters for Mmiti-goal environment.
Parameter
Value
Learning rate (policy) Learning rate (reward)
5 10 -1
5 10
Replay size
10,000
QT
10
Discount factor (r)
0.5
Batch size
512
Steps per update
50
Total steps
300,000
Table 4: Hyperparameters for MuJoCo environments.
Parameter
Value
Learning rate (policy)
3 10-1
Learning rate (reward)
3 10-4
Replay size
1,000,000
On
1.0
of
20.0
0.01
Discount factor (7)
0.99
Batch size
256
Steps per update
5
Initial exploration
10,000
Total steps
1,000,000
25


Reviews:
[{"review_id": "ZRWmdUUMHj", "reviewer": "Reviewer_4kT4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper seems to have an incremental contribution to AIRL and it claims AIRL benefits from Mirror Descent updates. It is incremental in a sense that  MD has been studied extensively in optimization research. However, providing some intuitions on the benefits of MD in IL might be interesting for some researchers.\n\nStrength: \n- Provided convergence and regret bound\n- Better performance on experiments (slightly) \n\nThe derivations seem correct, but I did not check them thoroughly.\n\nWeakness:\n- The presentation of the paper needs improvement, especially on the connection of the previous works and the proposed method. \n- It is unclear how MD affects the resulted reward function (or the corresponding policy) for examples as opposed to SGD? \n- Experiments are not sufficient as authors compared the proposed method only with one other imitation learning method (RAIRL). \n\nDetailed Review: \n\n\nFrom the presentation it it not clear for me the significance of the contribution. More precisely: \n- It seems the step size greatly affects the convergence rate of the proposed method. So does this method require properly tuning the step-size for each problem? Is there experiments on the effect of step-size on the produced policy/reward function? \nHow the choice of SGD vs MD affects the reward function?\n- \"A gradient may not be the direction of the steepest descent in this case due to geometric constraints\" How to verify this claim in IL setting, faster convergence or superior reward function?  At convergence and without any prior knowledge on the optimal step size, can you claim that it is expected that MD will result in a higher quality reward function as opposed to other AIRL methods?  \n-Can you discuss more on how and why the choice of MD will resolve the two mentioned issued in AIRL? Can it be shown in the experiments? \n-Can you explain in details the claim \"We verified that the proposed method has clear advantages over previous AIL methods in terms of robustness\"? Is it verified through multi-armed bandit experiment? \n\n\n", "summary_of_the_paper": "This paper proposes an alternative optimization technique (Mirror Descent) for adversarial inverse reinforcement learning, claiming it will resolve some of the issues with previous methods. \n\n-The authors prove the convergence of the proposed optimization method and provide a regret bound. \n-They experimentally show the benefits of the proposed methods in discrete and continuous action spaces. \n\n", "summary_of_the_review": "Overall I think this is an interesting paper. However, my main concern is the accuracy of the claims and the presentation of the paper. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "RdJ7zsnoDR-", "reviewer": "Reviewer_fhXG", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n1. The proposed MD-AIRL are both theoretically and empirically justified. Theoretically, the reward derived by mirror decent algorithm ensures the minimization of Bregman divergence converges to local optima along with a rigorous regret bound. Empirically, the resulting MD-AIRL was evaluated with large discrete action spaces and continuous action spaces. \n2. It is good to see the dense theoretical analysis in the paper for introducing the MD-AIRL gradually. The MD can be implemented on top of existing adversarial imitation learning method. \n\nCons:\n1. This paper claims that the proposed Mirror Descent Inverse Reinforcement Learning is more robust than previous adversarial imitation learning method. However, in the experiments, there lacks evidence to support that claim. \n2. In Figure 8, the results show that the proposed MD-AIRL using Tsallis regularizer with p=2 is competitive or slightly better than RAIRL. How does the MD-AIRL perform with other choices of p and regularizer? \n3. RAIRL and MD-AIRL both use Tsallis regularizer, however, the relationship between the two methods has not been well discussed. \n\n", "summary_of_the_paper": "This paper presents a novel mirror-descent adversarial inverse reinforcement learning (MD-AIRL) algorithm. MD-AIRL considers the reward function as an iterative sequence in a proximal method. MD-AIRL has been introduced with dense theoretical analysis and validated with diverse experiments covering both discrete and continuous action spaces. ", "summary_of_the_review": "Despite its novelty and dense theoretical analysis, the empirical evaluation can be further improved to better support the robustness of MD-AIRL. I also hope to see more discussion between MD-AIRL and the related RAIRL in the rebuttal. I read through both authors' responses and other reviews and decided to recommend a marginal reject. I have thought the submission is interesting and has its own contribution in some extent, but it seems like there haven't been signficant improvement during the rebuttal period. The performance improvement is not significant and the written clarity is not ready to be acceoted by ICLR. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8VsiL9efcQK", "reviewer": "Reviewer_c6kk", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. The idea of using MD for reward updates is novel. A detailed theoretical guarantee on sufficiency and necessities on the choices of stepsizes are provided. \n\n2. The paper tends to develop MD-AIRL step by step, and also provides illustrative figures to help to understand. \n\nWeaknesses:\n\nMy complaints most come from the writing and illustration part. Please see the detailed comments as follows. \n\n1. Figure 1: what does the solid curve in policy/reward spaces mean? What about the dotted angles? The authors are encouraged to elaborate more on the illustration.\n\n2. “For instance, $\\psi_{t+1}$ can represent a softmax policy for a discrete space, ...”: is $\\psi_{t+1}$ a regularized reward function or a policy? I am assuming that it should be a reward function. \n\n3. Equation 5: It is a maximization problem of $\\pi$ but I cannot find $\\pi$ in the objective. Also, I am not clear how the form of $J_\\Omega(\\pi_t, \\psi_{t+1})$ is derived in equation 5, and how it is related to equation 2. The authors are encouraged to elaborate more to make it clear. \n\n4. Below equation 8: Is $\\pi_*$ a function of $t$? What do the authors mean by “the expectation is taken over the entire steps”? How is the optimality condition $E[...] = 0$ is derived? I am confused about the whole paragraph. \n\n5. Theorem 1: When will the assumptions on $\\Omega$ in theorem 1 be satisfied?  Are there any examples? I am thinking about KL but it does not satisfy the conditions here. Please correct me if I am wrong. \n\n6. Theorem 2: The last inequalities involve $s$. What is this $s$ here?\n\n7. Proof of Theorem 2: what is $n$ below equation 33? I am not sure about the relation between $f_t$ and $D_\\Omega$ throughout the proof. \n\n8. Proof of Lemma 6: The authors state \"Assuming all states are reachable\". Is this an assumption of the results? What if such a statement does not hold?\n\n\nMinor issues: \n\n1. Section 8: functinos -> functions\n\n2. Above Lemma 1: greed manner -> greedy manner\n\n3. Below Figure 1: a update -> an update\n\n4. Equation 7: gradient of $D_\\Omega$ is a bit misleading; the authors should mention that the gradient is taken w.r.t. the first argument. \n\n5. Equation 8: $\\Omega(\\pi(\\cdot | s_i))$ -> $\\Omega(\\pi_t(\\cdot | s_i))$\n", "summary_of_the_paper": "The paper proposes an algorithm MD-AIRL, where each iteration involves policy and reward updates, and an expert policy estimation. The algorithm is motivated by MD, especially the reward update is modeled as a projected update of an MD update. The sufficiency and necessities of the choices of stepsizes to guarantee convergence are theoretically justified. A practical algorithm with numerical experiments are also provided. ", "summary_of_the_review": "Overall I think the paper proposes a novel approach to IRL. But the most obvious drawback is that the paper is not clearly written, which has many significant issues leading readers to misunderstand/cannot understand the paper. I think the current revision is not sufficient to be published in ICLR, thus I recommend a marginal reject and tend to reject if there is no significant revision. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work introduces/applies the mirror descent optimization technique to adversarial inverse reinforcement learning (AIRL). As a result, the proposed algorithm (MD-AIRL) incrementally learns a parameterized reward function in an associated reward space. The two issues of standard adversarial imitation learning algorithms are 1) current "divergence"-based updates may not lead to updates that better match the expert (due to geometry) 2) "divergence"-based updates may suffer when only small number of demonstrations are provided. Thus the goal of this work is to (presumably)  to "robustify" the learning of reward function especially by addressing these issues. The proposed algorithm is evaluated on a bandits problem, a multi-goal toy example and standard mujoco benchmark.

**Strengths**
This work attempts to address the important problem of understanding and improving the updates of IRL algorithms
A theoretical analysis is provided

**Weaknesses**
The major concern is clarity of the manuscript. Even after updating clarity remains a concern
While a lot of experiments were performed, evaluation is not entirely convincing. One reason for this that it is hard to tie the results back to the original motivation/claims of this algorithm. As one reviewer notes "it's unclear how the new algorithm affects reward functions". Furthermore, reviewers find the experimental results not entirely convincing 

**Summary**
After rebuttal and revision, the clarity and experimental analysis remain a concern. My recommendation is that the authors are encouraged to take the reviewers feedback and improve the manuscript. In its current form it's not quite ready yet for publication.
Decision: Reject