Title: PARTIAL SIMULATION FOR IMITATION LEARNING

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.

1. 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 to 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 a limited tool when it 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, as previously mentioned, BC follows a different success criterion that requires access to expert actions and is less in line with the true definition of success. But most importantly, BC discards two key ingredients of the problem: a) states order (i.e., it breaks trajectories), and b) partial knowledge about the transition kernel (ego car in the example above). In this paper we ask the following question:

Can we enjoy the benefits of 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 a given set of demonstrations into a Markov Decision Process (MDP), and we show that solving it 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 a 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 1 ). To understand the conditions when the use of eMDP is just, we derive a PAC result that bounds the error in the state-value 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 = {S, A, P, r, γ}, where S is a continuous state space endowed with a metric d S , A is the action space, P : S × A × S → R + is the transition probability induced by a transition kernel F : S × A → S, r : S × A → R is the reward function and γ ∈ [0, 1] is the discount factor. We also wish to define ρ 0 : S → R + as the initial state distribution. Our interest is in special MDPs where S can be factored as S = S r × S u , where S r refers to state components that are governed by a Responsive kernel F r : S ×A → S r . Put in words, S r represents element in the state space that we can simulate (ego car in the example above). On the other hand, S u represents the complement part of S, governed by an unknown kernel F u : S × A → S u (other road users in the example above). Therefore, it will be replaced by a synthetic kernel Fu : T → S that will be explained in Section 4. We also assume the existence of an expert policy π e : S × A → [0, 1] that is used to generate a set of state-only trajectories D = s i,0 e , ..., s i,T e n i=1 . To measure the distance between probability distributions we will use the Integral Probability Measure (IPM) formulation:

K p, q) = sup G S g(s)p(s)ds - S g(s)q(s)ds : g ∈ G (1)

The IPM formulation is attractive since it represents multiple distance measures that can be recovered under different choices of G. Eq. ( 1) becomes the famous kernel-distance. Although the analysis in Section 5 applies to a set of IPM measures, hereinafter we will set G = {g : ||g|| L ≤ 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 (M 1 , d 1 ), (M 2 , d 2 ). Let g : M 1 → M 2 be a function from M 1 to M 2 . The Lipschitz constant of g is given by:

||g|| L = sup d 2 (g(s 1 ), g(s 2 )) d 1 (s 1 , s 2 ) : s 1 , s 2 ∈ M 1 .

2.2. PROBLEM FORMULATION:

Let d t π , d t E denote the state distribution at time t, induced by the agent and the expert respectively. We wish to solve the following optimization problem:

EQUATION

However, we cannot calculate either of the distributions. While d t E can at least be estimated based on D, d t π cannot even be estimated because F r F. To solve this problem, we turn to use dt π , the distribution that is induced by F = { Fu , F r } and which can be estimated in the simulation. To justify the replacement of d t π by dt π we propose the following proposition: Proposition 2.1 (eMDP Optimal Solution). Let K(p, q) be an IPM measure over probability distributions p, q. Let d t π , dt π denote the t-step state distributions induced by F and F respectively. Then, if

∞ t=1 γ t K(d t π , d t E ) = 0 then dt π = d t π for all t ≥ 0.

Proof. See Appendix A.

Proposition 2.1 ensures that the optimal solution of eMDP coincides with the optimal solution of problem (2). However, it does not provide any guarantees when the optimum is not reached. In Section 5 we bound the errors between the eMDP and the original MDP for any π. Motivated to replace d t π with dt π in equation 2 we end up with a tractable optimization problem:

EQUATION

Denoting r t = -|g(s t )-g(s t e )|, it is easier to see that equation 3 takes the form of adversarial imitation learning (Ho & Ermon, 2016) , with g playing the role of the discriminator. It is also interesting to see that if d t π , d t E were to describe transition densities, then (3) would coincide with GAILfO's objective function. In the same way, if we had chosen G = {g : ||g|| L ≤ 1}, then (3) would have taken the form of Wasserstein GAN (Arjovsky et al., 2017) . However, solving (3) requires to address two optimization problems concurrently, which complicates the problem and leads to many instability issues associated with training GANs (Salimans et al., 2016) . Fortunately, we note a key feature in our setup that allows simplifying problem (3). At each step, eMDP exposes two states: the synthetic state {s t r , s t u } ∼ dt π and the reference state {s t r,e , s t u,e } ∼ d t E that share the same unresponsive component: s t u = s t u,e . Therefore, we know that to achieve the optimal solution of (3) we must have that s t r = s t r,e . This condition can be enforced explicitly without invoking a neural-network based classification network. For example, by restricting G to be a class of norm function. If this is the case, then using the help of Lemma 2.1 we can upper bound (3) in the following way:

EQUATION

Lemma 2.1 (Norm Function Inequality). Let g be a norm function. Then ∀x, y the following holds:

|g(x) -g(y)| ≤ |g(x -y)| Proof. See Appendix B.

To conclude, denoting r(s t r , s t r,e ) = -g(s t r -s t r,e ), where g(x) = ||x|| d S , we arrive at the final optimization problem of the eMDP model:

arg max π ∞ t=1 γ t E s t ∼d t π s t e ∼d t E

r(s t r , s t r,e ).

(5)

3. RELATED WORK:

Solving problem ( 5) is challenging. From one hand, the constraint that F r F prohibits using model-based (i.e., simulation-based) methods. On the other hand, the constraint on inaccessible expert actions prohibits the use of BC or 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 F, A, S: A fairly permissive simulation-based setup that violates our setup twice. First, for assuming access to 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 et 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 a loss function between expert and agent actions. GAIL (Ho & Ermon, 2016) and mGAIL (Baram et al., 2016) use ζ to train a discriminator to classify between fake 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-free 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 a state-to-action mapping. The strength of BC lies in its simplicity and is 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, andTai et al. ( 2016); Giusti et al. (2016) that learn a mapping between depth images to robot commands.

Methods requiring access to F, S: These are imitation algorithms that can train policies from state-only trajectories when full access to F is available. Torabi et al. (2018) follows GAIL's structure 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 a similar setup, however, there, the reward is modified to enhance stability using ideas of Preference-Based 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 to train a robot controller with zero-knowledge 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 to explicitly, it is always possible, yet presumptuous, to use the demonstrations to learn a model M of the environment, or at least parts of it. Depending on what MDP components are recovered, different approaches can be invoked as listed above. For example, a complete recovery of the underlying MDP, including the reward function r, also known as 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 demonstrations (Venkatraman et al., 2015) . Cascading prediction errors from forward-simulation with a 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 to typical states. In the same spirit, we propose to construct an MDP that allows recovering from "off-route" states, even with partial knowledge of the state dynamics. eMDP provides guidance that compares the responsive elements in the agent's trajectory (S r ) to the responsive elements in the original trajectory (S r,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 requirement that A = A E since eMDP ignores expert actions.

State Space S: We assume a decomposable state space S = {S r , S u }. S r , where we demand that S u ≡ S u,e . There is also a similar demand on the responsive part S r , however this can be relaxed provided that a suitable reward function is available (see below).

Reward Function r: The reward is derived directly from (5), and is defined over the metric of S:

r t = -||s t r -s t r,e || d S .

In Appendix C we demonstrate how additional shaping of r t is possible with the help of prior knowledge about the correct relations between s r and s u,e .

Discount Factor γ: The discount factor lies in the same range of [0, 1). We denote γ = 0 as the BC-regime of eMDP (see Section 6.1), and γ 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-expert, while at the RL-regime it encourages π to follow the "long-horizon-expert". Short-term experts can guide π to fix immediate 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 γ-annealing.

Transition Kernel F: Upon receiving an action, the new state is calculated in the following way:

• Simulating the transition of the responsive component:

s t+1 r = F r (s t , a t ).

• Reflecting the transition of the unresponsive component:

s t+1 u ≡ Fu (t) = s t+1

u,e . • Stitching s r , s u together to get the final state:

s t+1 = {s t+1 r , s t+1 u }.

That is, the responsive component is updated according to F r , while the unresponsive component is extracted as is from the next state in the demonstration.

Initial State Distribution ρ 0 : The initial state distribution is equivalent to the empirical state distribution of the demonstration set. I.e., initial states are sampled uniformly across time-steps and episodes in D:

s 0 = {s 0 r , s 0 u } = {s (i,t )

r,e , s (i,t )

u,e }, where i ∼ U[1, ...n] is the episode index and t ∼ U(1, ...T ) is the time index. For simplicity, hereinafter we omit the trajectory index i.

Absorbing Set B: The termination set is defined by the set of states that the agent reaches after T -t steps. I.e., the last step in the current demonstration: B = {s t |t = 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. However, 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 {s t r , s t r,e }. 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 a 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 at hand, and assuming that the transition kernel is a Lipschitz function (see Definition 5 in Asadi et al. ( 2018)), we are able to bound the divergence between the state distributions after a single step with high probability. Following right after, we relate the 1-step divergence to the one that compounds after n 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 i.i.d sample sets: {S r,i } m i=0 , {S r,e,i } m i=0 drawn randomly from P M (•|s, a) and P M(•|s, a) respectively, the empirical estimator of K is given by: The points we sample from the eMDP model are a function of a specific expert realization. Different realizations will lead to different estimations. In Appendix H we draw a PAC result on the convergence rate of the empirical estimator.

EQUATION

From 1-step Divergence to n-step Divergence In the following, we use the Lipschitz assumption on the transition function to bound the n-step error using the error that compounds after a single step2 .

Lemma 5.1. Let M, M be two MDPs with Lipschitz transition functions with constants L, L respectively. Let L = min{L, L}, and denote KP M, M = max

s∈D K P M (•|s), P M(•|s) + m,δ,c,ν,C0,C1 ,

then for all n ≥ 1 the following holds:

EQUATION

)

where P n G (•|µ) is the distribution induced by model G after n steps taken from distribution µ.

Proof. See Appendix K.

Approximation Error in the State-Value Function We are now ready to present the main result that relates the n-step divergence to the error in the value function. The following lemma is true for all s: Lemma 5.2. Let M, M be two MDPs with Lipschitz transition functions with constants L, L respectively such that L = min{L, L}, and Lipschitz reward functions with a constant L R . Then, ∀s, L ∈ [0, 1 γ )] and n ≥ 1, with probability at least 1 -2e -c the following holds:

|V M (s) -V M(s)| ≤ γL R KP M, M (1 -γ)(1 -γ L) (9)

Proof. See Appendix I.

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 on the maximal error between the eMDP and the demonstration set: KP M, M .

6. EMPIRICAL EVALUATION:

The evaluation was made between the BC baseline and a Policy Gradient (PG) algorithm (Schulman et al., 2017) 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 player1 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: F r = {player1}, Fu = {player2, ball}, and A consists of 5 vertical move commands in oppose to 3 movements used by the human experts.

Surround a two-player game where each player controls a growing "snake" comprised of the player's trajectory (Gam, 2019) . The player who first touches either snakes loses. We let two human players to compete. The goal of the agent we trained was to imitate human player 1 at the presence of human player 2. The eMDP model was constructed in the following way: F r = {player1's snake}, Fu = {player2's snake} and the action space consists of two turning commands.

Boxing a 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 1 at the presence of human player 2. The eMDP was constructed in the following configuration: F r = {boxer1}, Fu = {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 to imitate human player 1 at the presence of human player 2. The following eMDP model was created: F r = {player1}, Fu = {player2} and the action space consists of 4 move commands and a single hit command.

Assault-v0, Carnival-v0 a single-player shooter game (Brockman et al., 2016) 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-based imitation methods were impractical to use. We construct an eMDP model in the following way: F r = {player's shooter}, Fu = {enemy shooters} and the action space consists of seven movement commands and a single shoot command. The BC agent used the unmodified action space of the original game.

Breakout-v0 a single-player game (Brockman et 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 r = {racket}, Fu = {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 a 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 1 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 a single-step horizon, much like the BC solution that completely overlooks transitions. Lemma 6.1 shows that the optimal policy assigns action probabilities proportionally to r: Lemma 6.1. The solution of optimization problem 5 with entropy regularization at the BC-regime (γ = 0) is given by: π RL (a|s) = e r(s,a)/τ ã e r(s,ã)/τ .

Proof. See Appendix E. 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 a coherent training set (i.e., that ∀s i = s j : a i = a j ), although a similar result can be drawn in the general case. We also assume a uniform prior function on the hypothesis set of τ -regularized policies: Π τ = {π | ∀(a, s) ∈ A × S : π(a|s) ≥ τ }. Lemma 6.2 shows that the optimal solution of BC assigns minimal probability to each sub-optimal action and a probability of 1 -(|A| -1)τ to the ground-truth one. Lemma 6.2. Assume a set of policies Π τ with a uniform prior function and a coherent training set.

The solution of BC is given by:

EQUATION

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 a 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 r → ∅, S u → S), so is the level of synthetic augmentation. However, in this case the reward will be highly indicative of the task at hand because we fix a large portion of S. Overall, we identify a tension between the reliability of the model (measured in the reward), and its level of augmentation (See Appendix N for a further discussion about kernel extensiveness). An additional factor that affects the eMDP model but was not accounted for in our analysis is the level of interaction between F r and Fu . As future research, it would be interesting to suggest an improved model that can quantify the level of interaction and use it to reward policies that follow the expert while leading to low F r / Fu interaction.

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, we can design an auxiliary responsive termination signal by applying prior knowledge on the relations between S r and S u,e .

E THE OPTIMAL SOLUTION OF ENTROPY REGULARIZED RL AT THE BC REGIME:

Lemma E.1. The solution of optimization problem 5 at the bc-regime (γ = 0) is given by: π RL (a|s) = e r(s,a)/τ ã e r(s,ã)/τ (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, π) = a π(a|s) -log π(a|s) + γH(s , π) ,

which allows us to draw a similar recursive connection between the optimal value function V * (s) and the optimal policy: π RL (a|s) = e r(s,a)+γV * (s ) /τ e V * (s)/τ .

We use the fact that γ = 0 at the BC regime to get that: 

Define Π τ to be the set of policies with a τ lower bound on the allowed conditional probability:

Π τ = {π | ∀(a, s) ∈ A × S : π(a|s) ≥ τ }.

The prior function assigns zero-probability to functions outside of Π τ , and an even probability measure of 1 |Πτ | to each of its members. Therefore, we can limit the search to policies that reside in Π τ : . Since the prior assigns an even distribution to all members in the set, we can remove the first term and get that: 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:

EQUATION

G TRACTABLE COMPUTATION OF THE EMPIRICAL PROBABILITY DISTANCE ESTIMATOR:

Calculating the estimator in ( 6) requires to solve an optimization problem. Therefore, it is not straightforward to calculate. In the following, we present an easier form of the estimator as a solution to a linear program.

Lemma G.1. For all α ∈ [0, 1] the following function attains the supremum in 6: such that:

-d S ( Si , Sj ) ≤ a i -a j ≤ d S ( Si , Sj ), ∀i, j.

Proof. See Theoram 2.1 in Sriperumbudur et al. (2012) 

:

Informally, a Hilbert space is a RKHS if the evaluation functional Ls : g → g(s) is continuous at any g.

Lemma 5.1 applies to several IPM measures besides the Wasserstein metric. The composition lemmas we prove in Appendix J can be used in the Kantarovich-Rubinstein duality theorem to generalize the result to compositions over transition function with bounded TV, Dudley or Wasserstein norms.

Figures and Tables:

Figure 1: 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 at 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 we 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 is faintly visible next to the blue agent for visualisation purposes.

(i) represents the next-state empirical distribution under model G, c i = +1 when Si = S (i) r for i = 1, ...m and c i = -1 when Sm+i = S (i) r,e . This estimator is strongly consistent and converges to the population value as m → ∞ as the following proposition suggests: Proposition 5.1. Let (S, d S be a totally bounded metric space. Then as m → ∞: K P M (•|s, a), P M(•|s, a) -K P M (•|s, a), P M(•|s, a) | See Proposition 3.2 in Sriperumbudur et al. (2012).

Figure 2: Performance Comparison: results on 7 games. The x-axis represent the number of game frames and the y-axis Numbers represent the cumulative return from the eMDP model.

r(s,a)+γV * (s ) /τ e V * (s)/τ = e r(s,a)+γV * (s ) /τ e log ã e r(s,ã)+γV * (s ) /τ = e r(s,a)+γV * (s ) /τ ã e r(s,ã)+γV * (s ) /τ = e r(s,a)/τ ã e r(s,ã)/τ (12)F THE OPTIMAL SOLUTION OF ENTROPY REGULARIZED BEHAVIOR CLONING Lemma F.1. Assume a set of policies Π τ with a uniform prior function and a coherent training set. The solution of behavior cloning is given by:π bc (a|s) = 1 -(|A -1|)τ, if y(s) = a. τ, else(13)Proof. Entropy-regularized behavior cloning aims to solve the following maximum a posteriori optimization problem:π bc = arg max π P (π|D).(14)Using Bayes rule and the naive assumption we have that: arg max π P (π|D) = arg max π P (D|π)P (π) P (D) = arg max π P (π)Π (s,a)∈D P (s, a|π) = arg max π log P (π) + (s,a)∈D log π(a|s)

log function we end up with:π bc = arg max π∈Πτ (s,a)∈D π(a|s)

For example, choosing G = {g : ||g|| L ≤ 1}, where L is the Lipschitz constant of g (see Definition 2.1), reduces Eq. (1) to the popular Wasserstein metric. Setting G = {g : ||g|| H ≤ 1}, where H represents a Reproducing Kernel Hilbert Space (RKHS) 1 , and

Table content: <table/>

Peer review (iclr2020):
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. Overall, 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. One 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)?