Partial Simulation for Imitation Learning
Authors: Nir Baram
Shie Mannor
Venue:  (2020)
Keywords: Reinforcement Learning
Imitation Learning
Behavior Cloning
Partial Simulation

Abstract: Model-based imitation learning methods require full knowledge of the transition kernel for policy evaluation. In this work, we introduce the Expert Induced Markov Decision Process (eMDP) model as a formulation of solving imitation problems using Reinforcement Learning (RL), when only partial knowledge about the transition kernel is available. The idea of eMDP is to replace the unknown transition kernel with a synthetic kernel that: a) simulate the transition of state components for which the transition kernel is known (s_r), and b) extract from demonstrations the state components for which the kernel is unknown (s_u). The next state is then stitched from the two components: s={s_r,s_u}. We describe in detail the recipe for building an eMDP and analyze the errors caused by its synthetic kernel. Our experiments include imitation tasks in multiplayer games, where the agent has to imitate one expert in the presence of other experts for whom we cannot provide a transition model. We show that combining a policy gradient algorithm with our model achieves superior performance compared to the simulation-free alternative.

Under review as a conference paper at ICLR 2020
PARTIAL SIMULATION FOR IMITATION LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
Model-based imitation learning methods require full knowledge of the transi- tion kernel for policy evaluation. In this work, we introduce the Expert Induced Markov Decision Process (eMDP) model as a formulation of solving imitation problems using Reinforcement Learning (RL), when only partial knowledge about the transition kernel is available. The idea of eMDP is to replace the unknown transition kernel with a synthetic kernel that: a) simulate the transition of state components for which the transition kernel is known (s,), and b) extract from demonstrations the state components for which the kernel unknown (8..). The next state is then stitched from the two components: in detail the recipe for building an eMDP and analyze the errors caused by its synthetic kernel. Our experiments include imitation tasks in multiplayer games, where the agent has to imitate one expert in the presence of other experts for whom we cannot provide transition model. We show that combining a policy gradient algorithm with our model achieves superior performance compared to the simulation-free alternative.
{8r; 8u). We describe
INTRODUCTION
Recent work on Imitation Learning (IL) offers a new approach to the problem. Torabi et al. (2018) and Baram Mannor 2018) suggest defining success if the agent and the expert influence the environment in the same way and not if they necessarily take the same actions. They remove the need label expert actions and allow to settle for examples that include nothing but state transitions. The objective function they define seeks to minimize the distance between the state-transition density functions induced by the agent and the expert. However, since the state-transition dynamics is usually complex and unknown, it can not be calculated explicitly and is instead estimated through sampling. For reasons such as cost, time and safety, the sampling occurs in simulation and not in the real plant. However, despite considerable advances in simulation technologies, it is still limited tool when comes to complex real-world problems. Therefore, the adoption of advanced IL methods is hindered.
Consider the self-driving car example. Given their intent, physical simulation of pedestrians and vehicles can be done with high accuracy. However, simulating the intent itself, i.e., the decision-making process of those entities, is challenging. In this example, simulating the transition of other road users is hard (requires intent and physical transformation), however, simulating the ego car that is controlled externally is feasible (requires physical transformation only). The unwelcome solution, in this case, is to resort to behavior cloning (BC) that do not require simulation at all (Pomerleau] 1991). However, that requires access to expert actions and less in line with the true definition of success. But most importantly, BC discards two key ingredients of the problem: states order (i.e., it breaks trajectories), and b) partial knowledge about the transition kernel (ego car in the example above). In this paper ask the following question:
previously mentioned, BC follows different success criterion
Can we enjoy the benefits contemporary imitation methods if we keep every trajectory intact, and maintain partial information on the transition kernel?
We answer this question affirmatively and introduce a new model called expert-induced Markov Decision Process (eMDP) that fulfill this wish. eMDP transforms given set of demonstrations into

---

Under review as a conference paper at ICLR 2020
(b)
(d)
Figure I: Illustration of the transition kernel in an eMDP. (a) two players are playing the game of Pong. We wish to imitate the left (blue) one the presence of the right (red) expert. The state is split into two components: (b) Responsive components that we can simulate, and (c) Unresponsive components that do not know how to simulate. (d) the eMDP model produces the next state by updating each component separately and then stitching them together. The unresponsive elements (gray) are extracted as is from the consecutive state in the demonstration. while the responsive element (blue player) is updated according to an external command. Notice that the original expert faintly visible next the blue agent for visualisation purposes.
a Markov Decision Process (MDP), and we show that solving amounts to solving an imitation problem that seeks to match the state densities at each step. The idea of eMDP is to replace the unknown transition kernel with synthetic kernel that: 1) simulate the transition of state components for which the transition kernel is known, and 2) extract from demonstrations the state components for which the kernel is unknown (see illustration in Figure D. To understand the conditions when the of eMDP is just, derive PAC result that bounds the error in the state- statevaluu function between the eMDP model and the genuine model that uses the original transition kernel. Finally, we show empirical results that stress the benefits of using eMDP when the transition kernel is partially available and model-based approaches are not applicable.
2
PRELIMINARIES
The following describes the mathematical formulation of MDPs and the assumptions we require to build an eMDP model. Following after, we outline the optimization problem solved by eMDP.
2.1 MATHEMATICAL FORMULATION
We assume an MDP defined as M = AS,A,P, rr 7), where S is a continuous state space endowed with metric ds. A is the action space, P S x A x S > R2 is the transition probability induced by a transition kernel JF S A + discount factor. We also wish to define Po : R4 the initial state distribution.
R is the reward function and y E [0, 1] is the
Our interest is in special MDPs where S can be factored as S S, x Su. where S, refers to state components that are governed by Responsive kernel F, S x A + S,. Put in words, S, represents element in the state space that we can simulate (ego car in the example above). On the other hand, S, represents the complement part of S. governed by unknown kernel Fu, S A S, (other road users in the example above). Therefore, it will be replaced by synthetic kernel F, T will be explained in Section We also assume the existence of an expert policy S x A + [0, that is used to generate set of state-only trajectories D = (s :...,
that
s...,'?."" sf."") i=1"
To measure the distance between probability distributions we will use the Integral Probability Mea- sure (IPM) formulation:
((p.g) = sup { ((s)p(s)ds - -(t)plo)dssooooooollloo (000)(o)dd) g
g e)
(1)
G
The IPM formulation is attractive since represents multiple distance measures that can be recov- ered under different choices of G. For example, choosing Lipschitz constant of (see Definition [2]), reduces Eq. [1) to the popular Wasserstein metric, Set- ting {g ||l|| S 1), where H represents a Reproducing Kernel Hilbert Space (RKHS and
{g ||ll|2 1}, where L is the
Informally, Hillert space RKHS the evaluation functional I. g + g(s) is continuous any g-
2

---

Under review as a conference paper at ICLR 2020
Eq. becomes the famous kernel-distane. Although the analysis in Section 5 applies to set of IPM measures, hereinafter we will set 9 = (g: [g 1 S 1 to invoke the Wasserstein metric, which was previously shown to be weak (Arjovsky et al. 2017).
Definition 2.1 (Lipschitz continuity). Define two metric spaces (Mi,di), (M2, d2). Let g Mi + M2 be function from Mi to M2. The Lipschitz constant of g is given by:
|| sup { d2(g(51), :81, 82 E M1).
82)
2.2 PROBLEM FORMULATION
Let d' d'g denote the state distribution at time I, induced by the agent and the expert respectively. We wish to solve the following optimization problem:
arg min
(K((d,
However, we cannot calculate either of the distributions. While d'g can at least be estimated based on D, d cannot even be estimated because F, F. To solve this problem, we turn to use d;, the distribution that is induced by F = Fr) and which can be estimated in the simulation. To justify the replacement of d², by d' we propose the following proposition:
Proposition 2.1 (eMDP Optimal Solution). Let K(p, q) be an IPM measure over probability distri- butions p, Let d',, d' denote the t-step state distributions induced by F and F respectively. Then, 7
if FE K(d" d'g) 0 then d² d' for all 2 O.
Proof. See Appendix A
Proposition ensures that the optimal solution of eMDP coincides with the optimal solution of problem However, it does not provide any guarantees when the optimum is not reached. In Section we bound the errors between the eMDP and the original MDP for any æ. Motivated to we end up with tractable optimization problem:
replace d with dz in equation 2
arg min Σ o X'Cdd,, d'aa) = arg min
sup gEG slnd! t-
lo(s') g(st)).
(3)
Denoting T = --1g( (g((g()) g( is casier that equation takes the form of adversarial imita- tion learning (Ho Ermon 2016), with playing the role the discriminator, It is also interesting see that if di,, d' objective function. In the same way, if we had chosen G {g igglz I 1}. then would have taken the form of Wasserstein GAN (Arjovsky al. 2017
to describe transition densities, then ( would coincide with GAILfO's
However, solving 33 requires to address two optimization problems concurrently, which compli- cates the problem and leads to many instability issues associated with training GANs (Salimans et al. 2016). Fortunately, we note key feature in our setup that allows simplifying problem (3). At each step, eMDP exposes two states: the synthetic state {st,, s ~ d' and the reference state (sf ( d'g that share the same unresponsive component: s = sf Therefore, we know that to achieve the optimal solution of we must have that 8y = =f This condition can be en- forced explicitly without invoking neural-network based classification network. For example, by restricting G to be a class of norm function. this is the case, then using the help of Lemma 2.1 we upper bound in the following way:
arg min
sup sup E (g((") g($2) gEg L
<
arg min
sup E gEg
lg(s" - -.))- (4)
g norm
aal <L-
Lemma 2.1 (Norm Function Inequality). Let g be norm function. Then Vx, y the following holds:
(g(x)) -(() 1a(2 v)1

---

Under review as a conference paper at ICLR 2020
Proof. See Appendix
To conclude, denoting r(s e. = -g(s + -,,,), where g(z) = ||xldds we arrive at the final
optimization problem the eMDP model:
arg max
r(8 a 87))
(5)
studd 4nndg
RELATED WORK
Solving problem (5) is challenging. From one hand, the constraint that F, F prohibits using model-based (i.c., simulation- ) methods. On the other hand, the constraint on inaccessible expert actions prohibits the of BC other simulation-free methods. This setup differs from previous imitation learning configurations that were introduced in the literature. As no method exactly fits problem
5).
we turn to review the ones that can operate under slight modifications.
Methods requiring access to A, S: fairly permissive simulation-based setup that violates our setup twice. First, for assuming access expert actions, and second, for assuming full access to F. Algorithms of this type execute a simulation step Ç ~ π followed by a policy improvement step. DAGGer (Ross al.) 2011), an online no-regret algorithm, queries the expert at the states of Ç to generate ground-truth actions. Policy improvement is carried out by minimizing loss function between expert and agent actions. GAIL (Ho Ermon 2016) and mGAIL (Baram et al. 2016) use Ç to train discriminator to classify between take and authentic trajectories. The discriminator's classification probability is used as a reward signal that the agent seeks to maximize.
Methods requiring access to A, S: Included in this group are simulation-Fir methods that assume access to expert actions. The most prominent approach of this class is BC that administers supervised learning tools to the problem. I.e., it tries to directly learn state-to-action mapping. The strength of BC lies in its simplicity and favorable when enough state-action pairs are available. When this is not true, BC will tend to suffer compounding errors. Extensions of BC include Bojarski et al. (2016) that learn a mapping from images to vehicle steering commands, and Tai et al. (2016); Giusti et al. (016)) that learn mapping between depth images robot commands.
Methods requiring access to F.S: These are imitation algorithms that can train policies from state-only trajectories when full access F is available. Torabi et al. (2018) follows GAIL's struc- ture but uses a discrimination rule that is based on the state-transition distribution and not on the state-action joint distribution. |Baram & Mannor (2018) describes similar setup, however, there, the reward is modified to enhance stability using ideas of Preference-Basee RL.
Methods requiring access to S: The most stringent approach in terms of prior knowledge is also the only approach that can operate under the configuration proposed here. One notable example is Time Contrastive Networks (TCN) (Sermanet et al. 2018) that proved able train a robot controller with zero-knowe knowllnoweedge of F. However, TCN also requires multiple views (cameras) of the agent to achieve good performance.
Methods requiring access to a recovered model M: Although not referred explicitly, it is al- ways possible, yet presumptuous, to use the demonstrations learn model M of the environment, what MDP components are recovered, different approaches can
or at least parts of it. Depending be invoked as listed above. For example, a complete recovery of the underlying MDP, including the reward function т, also known Inverse Reinforcement Learning (IRL) (Ng et al. 2000 Ziebart et al. 2008), allows administering any RL algorithm with no constraints what so ever.
4 THE eMDP MODEL.
The motivation of eMDP is borrowed from techniques for learning time-series models from demon- strations /Venkatraman et al., 2015). Cascading prediction errors from siwarddsimulation with learned model can result in predicting infeasible states. To solve this, the demonstrations are used to generate synthetic examples for the learner to ensure that prediction returns typical states. In
4

---

Under review as a conference paper at ICLR 2020
the same spirit, we propose construct MDP that allows recovering from "off-route" states, even with partial knowledge of the state dynamics. eMDP provides guidance that compares the re- sponsive elements in the agent's 's trajectory (S,) to the responsive elements in the original trajectory (Sr,e). In the following, we outline the elements of the eMDP model.
Action Space A: The action space of an eMDP can be defined arbitrarily and there is no require- ment that A = Ag since eMDP ignores expert actions.
State Space S: We assume a decomposable state space S {S,, S..). Sy, where we demand that Su = Su.e- There is also a similar demand on the responsive part S,: however this can be relaxed provided that a suitable reward function available (see below).
Reward Function The reward is derived directly from ( and is defined over the metric of S: Ys = - llel In Appendix C we demonstrate how additional shaping of r. is possible with the help of prior knowledge about the correct relations between 5y and Su,e-
Discount Factor 7/2 The discount factor lies in the same range of [o, 1). We denote = 0 as the BC-regime of eMDP (see Section 6.1], and y close to one as the RL--regime of the model. At the BC-regime, eMDP encourages to be greedy w.r.t the short-horizon-exper, while at the RL-rregime it encourages π to follow the bong-horizon-expert drifts that occur after short action sequences (easier). Long-term experts will help it to fix drifts that compound after long action sequences (harder). Therefore eMDP naturally supports y-annealing.
Short-term experts can guide π to fix immediate
Transition Kernel F: Upon receiving an action, the state is calculated in the following way:
Simulating the transition of the responsive component: sf+1 = Fr Fs a²).
Reflecting the transition of the unresponsive component: s = (1) Su.e
Stitching $r; Sy together to get the final state: g²+1
st+11 {
That is, the responsive component is updated according Fr, while the unresponsive component is extracted as is from the next state in the demonstration.
Initial State Distribution Pot The initial state distribution is equivalent to the empirical state dis- tribution of the demonstration set. Le., initial states sampled uniformly across time-steps and episodes in D: 8o = {s,, s0} = {sr.e Su.e ((.4"), where i ~ U[1,...n] is the episode index and t' U.....TT) is the time index. For simplicity, hereinafter we omit the trajectory index i.
(8.4")
Absorbing Set B: The termination set is defined by the set of states that the agent reaches after T t' steps. Le., the last step the current demonstration: B { T t'}. In Appendix D we demonstrate how an augmentation of B is possible using prior knowledge.
5 THEORETICAL JUSTIFICATION OF THE eMDP MODEL
Lemma 2.1 ensures that eMDP perfectly follows the original MDP at the optimum solution. How- ever, it tells us nothing otherwise. As long as the optimum is not met, eMDP induces an improper state-distribution which leads to an error. Denote the model governed by F as M, we are interested to compare the performance of the agent in M to the one in the true model M. The error we wish to calculate is the difference in the value function between the models, and in the following, we show how to derive it from samples of (sf, }. Due to space constraints, we deffer parts of the proof to the appendix and present here the highlights of the analysis.
Analysis Overview We rely on the IPM formulation introduced in Section 2 in the Wasserstein form. We desire to use the Wasserstein distance since it can metrize the weak topology of the state space. In this way, we can relate the error in a metric state space to continuous distance in the distribution space. We will show how to estimate the distance from samples, without requiring access to the true, unavailable model M. Since expert samples are scarce, it is also important to discuss the rate to which the empirical estimator converges to the real quantity, which we do so in Appendix H With the empirical estimator hand, and assuming that the transition kernel is Lipschitz function (see Definition in Asadi et al.] (2018)), we are able to bound the divergence between the state distributions after single step with high probability. Following right after,
5

---

Under review as a conference paper at ICLR 2020
relate the 1-step divergence to the that compounds after steps. All that is left is to use the n-steps divergence to bound the error in the value function.
Empirical Estimation of the Single Step Divergence Given two iid sample sets: [Sr,i)==, (Srees); drawn randomly from PM((-ss,) and (,)))) respectively, the empiri- cal estimator of K is given by:
Σ a.()
sup fet
where Fg( 8, a) 1 Σ 5gm represents the next-state empirical distribution under model g,
G = when 5; = 5 for m. and G; =1 when 8m+; S This estimator is strongly as the following proposition suggests:
consistent and converges the population value as
Proposition 5.1. Let (S, ds be totally bounded metric space. Then as m + oc:
- (ulss 00
Proof. See Proposition 3.2 in Sriperumbudur et al. (2012).
The points we sample from the eMDP model are a function of a specific expert realization. Dif- ferent realizations will lead to different estimations. In Appendix H we draw PAC result on the convergence rate of the empirical estimator.
From 1-step Divergence to n ststep Divergence In the following, we use the Lipschitz assumption on the transition function to bound the step using the error that compounds after a single S
Lemma 5.1. Let M, M be two MDPs with Lipschitz transition functions with constants L, L re- spectively. Let L = min L, L.. and denote Ke M. max K (P)( Em.bI..u.Cs,G..
then for all the following holds:
Kg
MM M
S205
(8)
i=0
where (-Ip)) the distribution induced by model after n steps taken from distribution μ..
Proof. See Appendix K
Approximation Error in the State- Value Function We are ready present the main result that relates the ntstep divergence to the error in the value function. The following lemma is true for all
Lemma 5.2. Let M,M be two MDPs with Lipschitz transition functions with constants L,, L re- spectively such that L = minfL, L, L}, and Lipschitz reward functions with constant LR. Then, Vs. E [0, f)) and n 2 1, with probability at least 1 - - the following holds:
LLRKe m.
[v((s) Vi((s) (1 7) LL)
Proof. See Appendix
Not surprisingly. Lemma 5.2 show us that the correctness of the eMDP model depends on the Lipschitz constant of the reward function (which we control) and the maximal error between the eMDP and the demonstration set: K2 PP
applies several IPM measures besides the Wasserstein metric. The composition lemmas prove in Appendix can be used in the Mnatarrvich-Rubinsstee duality theorem to generalize the result to compositions over transition function with bounded TV, Dudley Wasserstein
'Lemma 5.1

---

Under review as a conference paper at ICLR 2020
6 EMPIRICAL EVALUATION
The evaluation was made between the BC baseline and a Policy Gradient (PG) algorithm (Schulman et al.] (017) equipped with our eMDP model. Both agents used the same CNN-based policy (See Appendix L for details), and the same set of 10 demonstrations, each of a maximal length of 500 steps. In the following, we briefly describe the construction of the eMDP model for each experiment. Unless otherwise mentioned, both agents share the same action space.
Pong-v0 a two-player tennis-like game (Brockman et al. 2016). We record 2 human players. Our goal was to imitate playerl at the presence of human player2. We do not have full knowledge about the dynamics of the problem because human player2 can not be simulated. Therefore, we resort to use our eMDP model in the following way: J, = {player]}, Fr = {plaaer2, ball), and A consists of 5 vertical move commands in oppose to 3 movements used by the human experts.
Surround two-player game where each player controls a growing "snake" comprised of the player's trajectory (Gam (019). The player who first touches either snakes loses. We let two human players to compete. The goal of the agent we trained was imitate human player 1 the presence of human player 2. The eMDP model was constructed in the following way: F,, = {playerl's 's snake), F. {player2's 's snake) } and the action space consists of two turning commands.
Boxing two-player game that simulates a boxing match from a top view camera (Gam 2019)
We let two humans to compete. The goal of the agent we trained was to imitate human player at the presence of human player 2. The eMDP was constructed the following configuration: F, {boxerl), F. (boxer2), and A consists of 5 movement commands and two hit commands.
Tennis a two-player game simulating a tennis match (Brockman et al. 2016). We let two human players to compete. The goal of the agent we trained was imitate human player the presence of human player 2. The following eMDP model was created: J, = {player1], F, = {player2) and the action space consists of 4 move commands and a single hit command.
Assault-vO, Carnival-v0 single-player shooter game (Brockman et al., (016) where the player's character faces multiple enemy shooters. We trained an agent to imitate a human player while using a modified action space. Since we introduced modifications to the action space. we could no longer use the emulator of the game, and model- -ased imitation methods were impractical to use. We construct an eMDP model in the following way: F, {player's 's shooter), F. = {enemy shooters} and the action space consists of seven movement commands and single shoot command. The BC agent used the unmodified action space of the original game.
Breakout-v0 a single-playe playeerpperrreeee game (Brockman al., 2016) that do not require the construction of an eMDP model but is included here for its popularity. The eMDP was constructed in the following way: F, {racker), F. [ball, bricks} } and the action space consists of seven horizontal move command. The BC agent used the unmodified action space of the human player.
The performance of the PG agent and BC are brought in Figure 2 The graphs present the cumulative return of the eMDP model as function of the number of processed game frames. We note that this is an unfair comparison since the BC agent was trained to solve a different optimization problem, Therefore, we also provide video results for a visual comparison (see supplementary material).
6.1 QUALITATIVE EVALUATION
As shown in Figure 2 the PG agent clearly outperforms the BC baseline. In the following, we try to formalize the claim introduced in Section [ that the solution of BC (to induce the same actions) deviates from the native objective of the problem (to induce the same effects on the environment). To do so, we compare the optimal solution of BC and eMDP. For a fair and clear comparison, we conduct the comparison at the BC Regime of eMDP (:- = 0) to encourage greedy policies that take into account single-step horizon, much like the BC solution that completely overlooks transitions. Lemma 6. shows that the optimal policy assigns action probabilities proportionally r:
Lemma 6.1. The solution of optimization problem with entropy regularization the BC-regime (N 0) is given by: π RL. (als) = Σg e
c'om))
Proof. See Appendix E
7

---

Under review as a conference paper at ICLR 2020
0.1
0.4
BC
MC
5C
eNOP
044
0.3
-0.2
-0.4
0.2
-0.25
0.1
-0.00
-0.9
00.75
-10
Frames (msiios]
Framee (milkors)
Pames (m/lloo))
Pramnes (milloo))
(a) Pong
(b) Surround
(c) Boxing
(d) Tennis
DC
2.0
BC
WPED
WNIEP
1.0
2.0
0.0
1.0
0.0
0.5
-14
0.0
02
D4
5.5
0.5
1.0
0.0
0.4
0.4
0.5
1.0
[mil
(milllonss
(e) Assault
(1) Carnival
(g) Breakout
Figure 2: Performance Comparison: results on 7 games. The xa-axs represent the number of game frames and the y-axis Numbers represent the cumulative return from the eMDP model.
On the other hand, the BC solution will seek to find the mode of the posterior distribution defined by the training set and the prior function. For simplicity, we assume coherent training set (i.e., that Vs; = Sy uniform prior function on the hypothesis set of r-regularized policies: II, = { V(a, 8) E A S (als) 2 J.. Lemma 6.2 shows that the optimal solution of BC assigns minimal probability to each sub-optimal action and probability of 1 - (IAA) - 1)T to the ground -tuth one.
aj), although similar result can be drawn in the general case. We also assume
Lemma 6.2. Assume set of policies II, with uniform prior function and coherent training set. The solution of BC is given by:
11 (IA1 1)r,
f' = a. else
π (als)
(10)
5,
Proof. See Appendix F
We can see that the optimal solution of BC distributes the probability evenly across all non-optimal actions, regardless of what next state they induce. On the other hand, the optimal solution of eMDP assigns probabilities proportionally to their immediate reward which is directly related to the error in the state space which accounts for the deviation between the agent and the expert. Thus, while BC is oblivious to action outcomes, eMDP considers the dynamics of the problem.
7 CONCLUSIONS
We introduced the eMDP model as formulation of solving imitation problems using RL, without requiring full knowledge about the state dynamics. eMDP can augment a training set by simulating the components of the state space for which the transition model is known. However, the degree to which the synthetic augmentation is reliable highly depends on the extensiveness of the responsive kernel. For example, when the responsive kernel is minimal (S, - 0, S, - 5), so is the level of synthetic augmentation. However, this case the reward will be highly indicative of the task at hand because we fix large portion of S. Overall, we identify tension between the reliability of the model (measured in the reward), and its level of augmentation (See Appendix NN] for a further discussion about kernel extensiveness). An additional factor that affects the eMDP model but was not accounted for in our analysis the level of interaction between F, and Fg. As future research, would be interesting to suggest an improved model that can quantify the level of interaction and reward policies that follow the expert while leading to low F,,F,, interaction.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Top 10 lists: The top 10 multiplayer games on the atari 2600. httpp::/gaamefatteee gamepttt Com/ top10/ 20t0:6626------6 twe-ttee--ppp 10-1-0mmmm multiplayer games on- the ataai- 2600 2019. Accessed: 2019-09-10.
Martin Arjovsky, Soumith Chintala, and Léon Bottou.
Wasserstein gan.
arXiv preprint
arXiv:1701.07875. 2017.
Kavosh Asadi, Dipendra Misra, and Michael L. Littman. Lipschitz continuity in model-based rein- forcement learning. arXiv preprint wvXiv:180..0719,, 2018.
Nir Baram and Shie Mannor. Inspiration learning through preferences.
arXiv preprint
arXiv:1809.0580 2018.
Nir Baram, Oron Anschel, and Shie Mannor. Model-based adversarial imitation learning. arXiv preprint arXiv:1612.02179, 2016.
Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp, Prasoon Goyal, Lawrence Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, al. End end learning for self-driving cars. arXiv preprint
2016.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016.
Alessandro Giusti, Jérôme Guzzi, Dan C Cireşan, Fang-Lin He, Juan P Rodríguez, Flavio Fontana, Matthias Faessler, Christian Forster, Jürgen Schmidhuber, Gianni Di Caro, al. A machine learning approach to visual perception of forest trails for mobile robots. IEEE Robotics and Automation Letters, 1(2):661-66)) 2016.
Jonathan Ho and Stefano Ermon. 1644:0/60000377700 2016.
Generative adversarial imitation learning. arXiv preprint
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Bridging the gap between value and policy based reinforcement learning. Advances Neural Information Processing Systems, pp. 2775-2785, 2017.
Andrew Y Ng, Stuart J Russell, et al. Algorithms for inverse reinforcement learning. In Icml, pp. 663-670, 2000.
Dean A Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neu- ral Computation, 3(1):88-97, 1991.
Stéphane Ross, Geoffrey J Gordon, and Drew Bagnell. A reduction of imitation learning and struc- tured prediction to no-regret online learning. In AISTAYS, volume 1, pp. 6, 2011.
Tim Salimans, Ian Goodfellow, Wojeiech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training gans. In Advances in neural information processing systems, pp. 2234-2242. 2016.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1700:0000.77777 2017.
Pierre Sermanet, Corey Lynch, Yevgen Chebotar, Jasmine Hsu, Eric Jang, Stefan Schaal, Sergey Levine, and Google Brain. Lime-contrastive networks: Self-supervised learning from video. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 1134-1141. IEFE, 2018.
Bharath K Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, Gert RG Lanck- riet, et al. On the empirical estimation of integral probability metrics. Electronic Journal of Statisties, 6:1550-1599, 2012.

---

Under review as a conference paper at ICLR 2020
Lei Tai, Shaohua Li, and Ming Liu. A ddeep-netwer solution towards model-less obstacle avoidance. In 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 2759- 2764. IEEE, 2016.
Faraz Torabi, Garrett Warnell, and Peter Stone. Generative adversarial imitation from observation. arXiv preprint arXiv: 1xX.:1807.06658. 2018.
Arun Venkatraman, Martial Hebert, and Andrew Bagnell. Improving multi-step prediction of learned time series models. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
Brian Zicbart, Andrew Maas, Andrew Bagnell, and Anind K Dey. Maximum entropy inverse reinforcement learning. In AAAI, pp. 1433 1438, 2008
10

---

Under review as a conference paper at ICLR 2020
Appendix
A OPTIMAL SOLUTION OF THE eMDP MODEL
The following Lemma ensures that the optimal solution of the eMDP model coincides with the optimal solution of Eq 2
Lemma A.1 (eMDP Optimal Solution). Let K(p, q) an IPM measure over probability distri-
butions P.q. 9. Let d=,, d', denote the t-step state distributions induced by F, Fu} respectively, Then, if St=1 "',((" (ddd,,d,, d'E) = =0 then d² = d' for all 2 0
Proof. Let Fr, be the responsive and unresponsive kernels in the original MDP. Lee, Sr (f+1) (st, (t); (++1) Fu (st; at). Let Fet,, Fu be the responsive and unresponsive kemnlss in the eMDP model. Le., Sy [t+1) (1,, a.), su (f+1) = tildeFu (st az). The responsive kernels are equivalent by definition: F F. Regarding the unresponsive kernel, we write:
F(s,,)) ((t Fu,,,, (s)) (x( d.=TE
Therefore, we get an equivalence in the unresponsive transition kernels at the point where actions taken according the expert.
Using the kernel equivalence along with the fact that the initial state distribution is the same, d da, it can be easily shown in induction that the state distribution remains the same for every step
B NORM FUNCTION INEQUALITY
Lemma B.1 (Norm Function Inequality). Let f be norm function. Then Vx, y the following holds:
ff f(y) If(x -v)l
Proof. Using Minkowski's inequality have that:
f(x) fly x) 2 f(x + - f(v)
Which leads to:
fly - x) 2 { - f(x)
And in the same way, since f is symmetric we have that:
f()) f(x - f(xx)
Which leads to:
- = f(y - x) 5(w)
Combining the above we get that Vx, yf:
(f(x) f(x) < fly - x) = 1 - x))
C RESPONSIVE REWARD
Consider a self-driving imitation task where a policy car S, follows an expert car Sr.. S, is pe- nalized via the Metric-reward for deviating from Sr.e Tmetric ||S, - Spellds- However, prior knowledge tells us that S, should also maintain distance from other cars in the scene: S There- fore, extra cost terms between S, and Sa,a be added.

---

Under review as a conference paper at ICLR 2020
D RESPONSIVE TERMINATION
Re-consider the self-driving example. We know that an accident or even a "bump" with other cars should terminate the current episode. Therefore, signal by applying prior knowledge on the relations between S, and Su.e.
design auxiliary responsive termination
E THE OPTIMAL SOLUTION OF ENTROPY REGULARIZED RL AT THE BC REGIME
Lemma E.1. The solution of optimization problem at the be-regime (7 0) is given by:
et(s,a)/+
π RL (als) = Ea erlaaa/T
(11)
Proof. It was previously shown by Nachum et al. (2017) that the causal entropy term can be written in the following recursive way:
H(s,
Σ (als)) m(as) AH(' ())((()))]] m)]
which allows us to draw a similar recursive connection between the optimal value function V* (s) and the optimal policy:
π RL (als) = (((e)))))VV
eV"(0//T
We use the fact that 7 the BC regime to get that:
(1())))
(v)))=
(2)/T
en (116)))))()))))))
(12)
(((e))
e'(a,0)/7
Ea Eaerlaa17
F THE OPTIMAL SOLUTION OF ENTROPY REGULARIZED BEHAVIOR CLONING
Lemma F.1. Assume set of policies 11, with uniform prior function and coherent training set. The solution of behavior cloning is given by:
π bc (a|s) = { (IA - 1()T,
fu(()) = a.
(13)
else
Proof. Entropy-regularizee behavior cloning aims to solve the following maximum a posteriori op- timization problem:
be arg max (Dr
(14)
Using Bayes rule and the naive assumption have that:
arg max P(T|D) arg max P(D(T)P(T)
P(D)
(15)
arg max P(s. = arg max log P(T) +
p().
Σ
log (als)
(s.A)D
12

---

Under review as a conference paper at ICLR 2020
Define II, to be the set of policies with lower bound on the allowed conditional probability:
I ( V(a. s) A (a|s)) 7)
The prior function assigns zero- zero- err-pprobability to functions outside of 11,, and an even probability measure of - to each of its members. Therefore, we can limit the search to policies that reside in [T-]
arg max log P(T) + sell,
Σ
log (()s))
(e.a)ED
Since the prior assigns an even distribution to all members in the set, we can remove the first term and get that:
arg max alll,
Σ
log (als)
(s
Removing the log function we end up with:
π
br arg max
Σ
T(als)
xEII,
(s.a)ED
From here it easy to see that the policy that maximizes the expression above is the one that assigns the maximum allowed probability to the ground-truth action while evenly distributing the remaining weight among the other ones:
1 (1A4 11),,
yfs) = a. else
bc (a|s)
(16)
G TRACTABLE COMPUTATION OF THE EMPIRICAL PROBABILITY DISTANCE ESTIMATOR
Calculating the estimator in ( 6 requires to solve optimization problem. Therefore, it is not straightforward to calculate. In the following, we present an easier form the estimator as a solution to linear program.
Lemma G.I. For all [0, 1] the following function atlains the supremum
fa(s) min (a) + ds(s,
i=1...2m
(17)
+ (1 a)) max (aj ds(s, S:))
where {at ym solve the following linear program:
2m
max
C204
(18)
41....0.m
1=1
such that:
ds(S, 5,) s a; s (S. Vi,j-
Proof. See Theoram 2.1 in Sriperumbudur al. 2012
n
13

---

Under review as a conference paper at ICLR 2020
H CONVERGENCE RATE OF THE EMPIRICAL ESTIMATOR
The points we sample from the eMDP model are a function of the specific realization of expert demonstrations D. Different demonstration sets will lead to different estimations. In the following. we draw a PAC result on the convergence rate the empirical estimator.
Lemma H.1. Let F be the space of measurable functions such that |l S v, Var(n.a) s (P..) Yf F. Let Cu, C1 < co, > 0, 8 E (0.1). D (5,12m0 P P. Then Vs the following holds:
P(C((MM(()) (M)(1)s)
{(PM((1s) + ((m, < 2
where:
Cm,....Coo.. = 2(1+a)
2
2t1 1
(Cov
+
V m
1-
Acmax o22
(p:Ag}
(19)
4cv
2
1
+
3
8(1 - 5)
Proof. See Theorem 3.3 in Sriperumbudur et al. (2012)
eMDP VALUE FUNCTION ERROR
In the following. present the main result that relates the n-step divergence to the error in the value function. The following lemma is true for all st
Lemma I.1. Let M,M be two MDPs with Lipschitz transition functions with constants L., i. re- spectively such that L = min L, È),, and Lipschitz reward functions with constant LR. Then, Vs. L E [0, f) and 2 1, with probubility at least 1 - 2e the following holds:
LRR M.M
[V((s) - (vns)) (1 (1 (L)
(20)
Proof. (Following Theorem 2 in Asadi et al. (2018) Let 5, be Dirac delta function in then, for each state 8, the difference between the value function under M and M is given by:
Vm(s) V= >n 1 (s'15))) n=
LR where LR the Lipschitz constant of r(s). can be casily shown that [lfllz = With the definition of f(s) we can re-write the state value gap as:
Define the function f(s) = r(s)
Σn" f (Ps)(PP))))))) - P (s'
VM(s) (s) LR
n=0
Since f()) E F where FF (f Il S 1} we can bound the state value gap from above by taking the supremum over F:
2
VM((s) - (s) =R Σ
F(s))(P(((116)) - -P" (s)
7"
n=
/ ((6))(2(()11))) (s)1611)
L R
n=0
14

---

Under review as a conference paper at ICLR 2020
Following the definition of IPM in Eq equation Wasserstein distance between the state distribution induced after taking steps in M and M:
that the right hand side is exactly the
VM(s) - V LR n=0
Relying on Lemma
5.1
with probability of at least 1 1- 20 we can upper bound the n-step deviation
as follows:
n-1
LR y (K)()) PM((6))) S LB Σ 7" K
Σ L
M.M
Re Re-writing the right hand side get that:
L"
LR
Σ L' LRKE M.M
M.
1- L
n=0
1=0
n=0
And after re-arranging we can write that:
K M La
20
LRKg
Σ
7"
(7b)*
M
T,
T.
mm0
n=
Using on the fact that L E [0, )1 we know that the right hand side is finite:
Kr Krm. LA
K
P
Σn" 7"
[(TL)"
= I.
L
11 1-
1 1L7
n=0
n=0
Which can be written as:
K2
yI. R M.M.
M.M
M.,
-(1-))
In 1-
== I.
1 7/
1- (1 (1)))
(1 7) IL
Since K. equipped with F ( ||/ < 1) leads to the Wasserstein distance which is metric, it therefore symmetric. We can repeat the process, this time with VM((s) (s)(s), which concludes the proof.
J COMPOSITION LEMMAS
We wish to make our result general to several IPMs besides the Wasserstein metric. In the following present two helpful lemmas.
J.1 LIPSCHITZ COMPOSITION
The following lemma (Following Lemma in Asadi et al. (2018) shows that the composition of two Lipschitz functions is also Lipschitz constant:
Lemma J.1. Define metric spaces (M₃, (M2, d2), (Ma, d3). Define Lipschitz functions g :
Mi + M2 M2 M3, then h f o M1 + Ms is also Lipschitz with constant bounded above by ||gl|e|ifll
Proof.
da (s(((
|| sup
82(
M
de d=(c((1). ds((f
sup MM
(21)
di (81,822
de(g((1),
d2((((1)) 82)
sup ((((((())))((((()))) = |lgl
sup M1.
d.djeM, d2(0(()).g(()))
15

---

Under review as a conference paper at ICLR 2020
J.2 DUDLEY COMPOSITION
Recall that the Dudley metric can be extracted from the IPM formulation (Eq. 1 by setting
F= I1/IB/BBB 1)
where |lfl|o |ff + |l and || (u) E S). The following lemma states that the composition of two function with bounded BL norm has a bounded BL norm itself.
Lemma J.2. Define 3 metric spaces (M1, d1), (M2, d2), (Ma, da). Define functions g MM + M2. : M2 - My. Then h fog: M1 + M3 has bounded BL norm: |[k| I |19l|e/lflle +
Proof.
da(f (d(f(g(s))),f(((s))))
||
sup
di 52)
M
sup [f(g(s)))
s llg||a/1flle++
sup If(s')l
(22)
sEM
= -|g||a////|4 |l/
where the incquality given by Lemma J.1
J.3 TOTAL VARIATION COMPOSITION
Recall that the TV metric can be extracted from the IPM formulation (Eq. D by setting
F= Ilf S 1};
where || == sux( : x E S). The following lemma states that the composition of two functions with bounded TV norm has bounded TV norm itself:
Lemma J.3. Define 3 metric spaces (M1, d1). (M2, d2), (M,, dz). Define functions : M1 +
M2, M2 + M3. Then h fog M1 + M3 has a bounded TV norm: [|]] ll
Proof.
|/// sup If(o(s)) < sup If(s')) = llfll
(23)
M
s'EM2
K FROM 1 1-STEP DIVERGENCE TO STEP DIVERGENCE
We prove this lemma following the proof Theorem 1 in Asadi et al. (2018). We generalize the result several IPM measures using the composition lemmas we proved Appendix J
Lemma K.1. Let M, be two MDPs with Lipschitz transition functioos with constants L, L re- spectively, Let L = min L, L}. and denote Kp KPM.N thenfor all 2 the following holds:
max sED
(+(ls))) + emm.C.P.CC....p
n-1 _
((K(PM(WW) Ke
M.
22
(24)
1=0
where (-1p) is the state distribution induced by model G after steps taken from an initial distri- bution p..
Proof. The proof is done by induction.
Induction base: Using the definition of an IPM we can write that:
sup /
(PM(66(s) P (s)ddds
x(PM(H))
16

---

(+()) Under review as a conference paper at ICLR 2020
$f sup / (Pu(51)))) (( (((P))))-)/(())))))
We use the fact that fs = 1 to get:
= =K(PM(d(()) Pm(((s)) / (()))))))((()))))PP(((0
With probability at least 2 on the choice of D, the above can be bounded above by Re M. which concludes the proof of the base of the induction.
Induction step: Assume that the claim holds for 1, i...:
R 2
(P), (-1p)) S KP
Σ
L
Using the triangle inequality we write that:
(PP & ((PM)( Pu (M +
+ (())
=
(1PM PM + K
To upper bound the first term rely on the proof of the Kantarovich Rubiiisteennin duality theorem (See Asadi et al. (2018), page 3 13). It is easy to see that using our composition lemmas (See Ap- p) the result proved there be generalized in several ways: 1) A Dudley-metric composed on a transition model with a bounded BL. norm. 2) a TV-metric composed on a transition model with bounded TV norm. Therefore:
XC where || ll is the munsition-moder norm. E.g., É when reducing IPM to Wasserstein- metric to- gether with Lipschitz transition model as we shell assume for the rest of the proof:
((PM (1)) M Pa (-1))) s (())))
PM (-1w))
Finally:
K(PM(HW) < LXC(PT) (x) + Kr KP S Kr Kimmar Σ 1
L POLICY NETWORK ARCHITECTURE & TECHNICAL DETAILS
The CNN architecture used by all agents described in Table [ The state is a concatenation of last four frames, where each frame is 80 x 80 gray-level pixels. Although our method is agnostic to the action space, all environments we tested have discrete action spaces (not intentional). We used the Adam optimizer Kingma& & Ba (2014) across all experiments. We used linearly decaying learning rate with an initial coefficient of 7e All agents were trained on single workstation with a single GPU/CPU.
17

---

Under review as a conference paper at ICLR 2020
Layer Type
Size
Details
Activation
2D Convolution
32 filters
kernel size = 8, stride=4
Relu
2D Convolution
64 filters
kernel size = 4, stride=2
Relu
2D Convolution
64 filters
kernel size = 2, stride=1
Relu
Fully Connected
512
Relu
Fully Connected
|
Table 1: Policy Network Architecture
M FURTHER EXPERIMENTAL RESULTS
Videos results can be found in the following link: fol colders/ 1FSve01 JLNn 4bNoP 4bNoP Saw.oooPEEEELLLYYYI....... Note that the expert is overlaid in red for visualization purposes only.
com/ dr i ve/
N ON THE EFFECTS OF KERNEL EXTENSIVENESS
In the following, we discuss the effects of using an extensive kernel in the eMDP model, in the case of extensive knowledge about the transition kernel, vs the of using minimal kernel in the of minimal prior knowledge.
BC Limit: S, O,S. S With insufficient prior-knowledge about the world, the responsive kernel is minimal. In this case, partial simulation barely enriches the demonstration set D with new simulated states. However, in this case, the reward signal provided by PS-Env is highly indicative of the task at hand. This is true because we fix a large portion of the state space (S + S). Therefore, the hypothetical behavior of the expert in the observed state should align to high degree with the recorded behavior of the expert Sr,e upon which we define Tmetric-
the contrary, with extensive knowledge about the world, comprehensive responsive kernel can be designed. Partial simulation can enrich the training set with numerous new simulated states. Yet, the reward signal provided at this limit dubious: we fix small subset of the state (S,, 0), and behavior of the expert the observed state with respect to the recorded behavior Sy.e upon which reward the agent. To exemplify this problem, consider the extreme presence of any randomness, the simulated trajectory will completely diverge from the reference trajectory, thus ruling out the utility of Tmetric. The only case in which Tmetric maintains relevancy is completely deterministic environment.
Model-Based I Limit: - S,S. -
result we have fewer guarantees on the hypothetical
where S, S. At the
18


Reviews:
[{"review_id": "rkgvO5taFB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides a theoretical basis called expert-induced MDP (eMDP) for formulating imitation learning through RL when only partial information on the transition kernel is given. Examples include imitating one player in multiplayer games where the learner cannot explicitly have the transition kernel for other players. eMDP just uses the available part of transition kernel (e.g. the target player's state-action transitions) for learning, but substitute the next state from demonstrations 'as is' into the unavailable part. In this situation, using IPM (Wasserstein-like) divergence, it is easily guaranteed that eMDP is consistent with the optimal solution in the limit. However, this does not guarantee anything when the optimum is not reached. The paper's main contributions would be to provides error bounds (Lemma 5.2 in particular) for the convergence rate in terms of Lipschitz constants and the maximum error between eMDP and the demonstration set. This roughly means that when transition functions are continuous and smooth and the sample demonstration set well characterize the underlying MDPs, then eMDP is theoretically guaranteed to work well. If these factors (Lipschitz continuity and the max deviation of state distributions conditioned on the given demonstration set) are expected to be small, eMDP can nicely perform learning with partial knowledge. Some demonstrations confirm eMDP works when simple BC fails in multiplayer games.\n\nOverall, the paper is worth accepting. The proposed eMDP would be a technically simple solution, but providing a solid theoretical basis for that solution to these commonly seen situations of imitation learning with partial knowledge would be quite beneficial. The paper is well written with intuitive examples and nice overview summaries for the theoretically complicated parts. Though the implications of the experimental part are not clear, the paper fairly states this point and also provides a video for visual assessment with displaying ghost imitations. \n\nOne minor question: For the experimental part, BC baselines for multiplayer games just imitates the target player's behavior (player1), completely ignoring the states/actions of player2 (ignoring the states of bricks and balls for breakout-v0)? ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "r1xJuNzPYH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "* Paper summary.\nThe paper considers an IL problem where partial knowledge about the transition probability of the MDP is available. To use of this knowledge, the paper proposes an expert induced MDP (eMDP) model where the unknown part of transition probability is modeled as-is from demonstrations. Based on eMDP, the paper proposes a reward function based on an integral probability metric between a state distribution of expert demonstrations under the target MDP and a state distribution of the agent under the eMDP. Using this reward function, the paper proposes an IL method that maximizes this reward function by RL. The main theoretical result of the paper is that the error between value function of the target MDP and that of the eMDP can be upper-bounded. Empirical comparisons against behavior cloning on discrete control tasks show that the proposed method performs better. \n\n* Rating.  \nThe main contribution of the paper is the eMDP model, which enables utilizing prior knowledge about the target MDP for IL. While this idea is interesting, eMDP is too restrictive and its practical usefulness is unclear. Moreover, there are other issues that should be addressed such as clarity and experiments. I vote for weak rejection. \n\n* Major comments:\n- Limited practicality due to an assumption on the unresponsive transition kernel.\nIn eMDP, the unresponsive transition kernel is modeled from demonstrations by directive using the observed next states (in demonstrations) as a next state of the agent. This modeling implicitly assumes that the agent cannot influence the unresponsive part of the state space. This is too restrictive, since actions of the agent usually influence other parts of the state space such as opponents and objects. For instance, in pong, actions of the agent indeed influence trajectories of the ball. Due to this restrictive assumption, I think the practicality of eMDP is too limited.\n\nAlso, it is unclear what happens when the transition of unresponsive state space is stochastic. In this case, the unresponsive transitions of eMDP would be incorrect since eMDP assumes deterministic transitions as-is from demonstrations. Though I am not sure about this. \n\n- The equality in Eq. (3) should be an upper-bound. The IPM is defined by the absolute difference between summations (expectations), but the right-hand side of Eq. (3) is summations (expectations) of the absolute difference. These two are not equal, and the right-hand side should be an upper-bound. \n\n- The paper is difficult to follow. There are many skipping contents in the paper. Especially, in the description of eMDP and its solution, where the paper describes the optimal solution of eMDP (Section 2) before describing the eMDP model (Section 4). Also, it is unclear from my first reading pass what is the actual IL procedure. Including a pseudo-code would help. \n\n- The state-value function’s error bound ignores a policy. The proof utilizes the state distribution P(s’|s). However, this distribution should depend on a policy. It is unclear to me what is the policy function used in this error bound. Does this error-bound hold for any policy or only for the optimal policy? In the case that it only holds for the optimal policy, this result still does not provide useful guarantees when the optimal policy is not learned, similarly to the result in Proposition 2.1.\n\n- Empirical evaluation lacks strong baseline methods. The paper compares the proposed method against behavior cloning, which is known to perform poorly under limited data. The paper requires stronger baseline methods such as those mentioned in Section 3. Also, it is strange that the vertical axis in Figure 2 represents the reward function of eMDP, which is an artificial quantity in Eq. (5). The results should present the reward function of the target MDP, which is the ground-truth reward of the task.\n\n* Besides the major comments, I have few minor comments and questions:\n- Does the reward function in Eq. (5) correspond to the Wasserstein distance for any metric d_s? If it is not, then the value function’s error-bound for the Wasserstein distance is not applicable to this reward function. \n- What is the reward function r(s) in the value function’s error-bound that we can control the Lipschitz constant? We do not know the ground-truth reward r(s,a) so it cannot be controlled. The reward r(s,s’) of eMDP is given by the metric d_s of the state space so again we cannot control it. \n- What is the metric d_s used in the experiments? \n- How do you perform BC without expert actions in the experiments? \n- Confusing notations. E.g., the function r is used for r(s,a) (MDP’s reward), r(s, s’) (eMDP’s reward), and r(s) (reward in the error bound’s proof); these r’s have different meaning and should be denoted differently.\n- Typos. E.g., “Lemma 2.1” in Section 5 should be “Proposition 2.1”, “Lemma A.1” should be “Proposition 2.1”. \"tildeF\". etc.\n\n*** After authors' response.\nI read the other reviews and the response. My major concern was the impracticality of eMDP. While I can see that the eMDP model provides advantages over BC, I still think that it is impractical since it assumes the agent cannot influence the unresponsive part. Moreover, extracting next-unresponsive states as-is from demonstrations is problematic with stochastic transitions, since actual next-unresponsive states can be different from next-unresponsive states in demonstrations even when the sames state and actions are provided. Given that the major concern remains, I still vote for weak rejection. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SkeQKHjaYH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes an imitation learning algorithm that learns from state-only demonstrations and assumes partial knowledge of the transition dynamics. The demonstrated states are decomposed into \"responsive\" and \"unresponsive\" features. The imitation policy is trained in an environment where the responsive state features are simulated and controllable by the agent, and the unresponsive state features are replayed from the demonstrations. The agent is rewarded for tracking the responsive state features in the demonstrations.\n\nOverall, I was confused by this paper. Isn't it problematic that the imitation agent is trained in an environment where unresponsive state features from the demonstrations are replayed and not affected by the agent's actions? It would be nice to expand Section 4 to explain why it makes sense to reflect the unresponsive component in the transition kernel. It would also be helpful to include some of this information in Section 1.\n\nI am also confused by the method. What is the purpose of observing unresponsive features, if the reward function for the imitation agent is only defined in terms of the responsive features? Is it that the imitation policy is conditioned on the unresponsive features?\n\nThere are several important experimental details missing from Sections 4 and 6. What distance metric was used to define the reward function? For example, was it Euclidean distance in pixel space for the Atari games? The main experimental results in Figure 2 are difficult to interpret without knowing the how the reward function is defined in the eMDP. Could the authors either provide definitions of the reward functions of the eMDPs in the experiments, or measure performance of the imitation agents using more interpretable or standardized metrics (e.g., game score) for the chosen environments?\n\nIt is also concerning that the Google Drive links to code and supplementary materials aren't anonymized.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces the concept of an Expert Induced MDP (eMDP) to address imitation learning settings where environment dynamics are part known / part unknown. Based on the formulation a model-based imitation learning approach is derived and the authors obtain theoretical guarantees. Empirical validation focuses on comparison to behavior cloning. Reviewers raised concerns about the size of the contribution. For example, it is unclear to what degree the assumptions made here would hold in practical settings.
Decision: Reject