Title: SELF-IMITATION LEARNING VIA TRAJECTORY-CONDITIONED POLICY FOR HARD-EXPLORATION TASKS Anonymous

Abstract: Imitation learning from human-expert demonstrations has been shown to be greatly helpful for challenging reinforcement learning problems with sparse environment rewards. However, it is very difficult to achieve similar success without relying on expert demonstrations. Recent works on self-imitation learning showed that imitating the agent's own past good experience could indirectly drive exploration in some environments, but these methods often lead to sub-optimal and myopic behavior. To address this issue, we argue that exploration in diverse directions by imitating diverse trajectories, instead of focusing on limited good trajectories, is more desirable for the hard-exploration tasks. We propose a new method of learning a trajectory-conditioned policy to imitate diverse trajectories from the agent's own past experiences and show that such self-imitation helps avoid myopic behavior and increases the chance of finding a globally optimal solution for hard-exploration tasks, especially when there are misleading rewards. Our method significantly outperforms existing self-imitation learning and count-based exploration methods on various hard-exploration tasks with local optima. In particular, we report a state-of-the-art score of more than 20,000 points on Montezumas Revenge without using expert demonstrations or resetting to arbitrary states. 1 In many important application domains (e.g. the robotics domain), such handcrafted representation is available. Also, learning a good state representation itself is an important open question and extremely challenging especially for hard-exploration and sparse-reward environments, which is not the main focus of this work. Therefore, we assume the availability of the high-level representations as many previous works (Florensa et al., 

1. INTRODUCTION:

Hard-exploration tasks, particularly characterized by sparse environment rewards, are traditionally challenging in reinforcement learning (RL), because the agent must carefully balance the exploration and exploitation when taking a long sequence of actions to receive infrequent non-zero rewards. Demonstration data has been shown to be helpful for tackling hard-exploration problems (Subramanian et al., 2016) ; many existing methods (Hester et al., 2018; Pohlen et al., 2018; Aytar et al., 2018; Salimans & Chen, 2018) provide the guidance for exploration based on imitation learning of expert demonstrations and achieve strong performances on hard-exploration tasks. However, the reliance on human demonstrations largely limits the general applicability of such approaches. where the reward for getting an apple, getting the gold and taking a step in the rock is 1, 10, -0.05 respectively. The time limit for one episode is 45 steps. The agent's own past good trajectories with high total rewards are easily accessible (though imperfect) alternatives for the human-expert demonstrations. Recent works (Oh et al., 2018; Gangwani et al., 2018) verify that imitation learning from the agent's previous good trajectories could indirectly drive exploration in certain environments. However, imitation of good experiences within limited directions might hurt exploration in some cases. Specifically, in environments with misleading rewards which may trap the agent in local optima, simply imitating 'good' trajectories that would accumulate misleading positive rewards may guide the agent to a myopic behavior and hinder it from reaching a higher return in the longer term. Therefore, imitating diverse trajectories would be more desirable to help encourage exploration in diverse directions and avoid being distracted by the misleading rewards. For example, as illustrated in Figure 1 , the agent starts in the bottom left corner where it can easily collect apples near its initial location by random exploration and achieve a small positive reward. If the agent imitates the trajectories around the orange path, it would receive the nearby positive rewards quickly but it is unlikely to collect the gold within a given time limit. Therefore, in order to find the optimal path (purple), it is better to exploit the past experiences in diverse directions (gray paths), instead of focusing only on the trajectories with the myopic behavior. This paper investigates how imitation of diverse past trajectories leads a further exploration and helps avoid getting stuck at a sub-optimal behavior. Our main contributions are summarized as follows:

(1) We propose a novel architecture for a trajectory-conditioned policy that can imitate diverse demonstrations. (2) We show the importance of imitating diverse past experiences to indirectly drive exploration to different regions of the environment, by comparing to existing approaches on various sparse-reward reinforcement learning tasks with discrete and continuous action space. (3) We achieve a performance comparable with the state-of-the-art on hard-exploration Atari game of Montezuma's Revenge and Pitfall without using expert demonstrations or resetting to arbitrary states.

2. RELATED WORK:

Imitation Learning The goal of imitation learning is to train a policy to mimic a given demonstration. Many previous works achieve good results on hard-exploration Atari games by imitating human demonstrations. DQfD (Hester et al., 2018) combines the temporal difference updates in Q-learning with the supervised classification of the demonstrators' actions. Ape-X DQfD (Pohlen et al., 2018) extends DQfD with the transformed Bellman operator and temporal consistency loss to improve the efficiency of exploration. Aytar et al. (2018) learn embeddings from a variety of demonstrations videos and proposes the one-shot imitation learning reward, which inspires the design of reward in our method. All these successful attempts rely on the availability of human demonstrations. In contrast, our method treats the agent's past trajectories as demonstrations. Imitation learning is more difficult when the environment becomes more stochastic because the demonstrations could not account for all possible situations. Our method allows for some flexibility to follow the demonstrations in a soft-order and thus could perform well in the environment with a moderate degree of stochasticity. As discussed in Appendix C.1, we can easily extend our method to handle a more challenging scenario (e.g., where the location of objects could be random). Yet, imitation learning in extremely stochastic environments is still an open problem (Ghosh et al., 2017; Paine et al., 2019) . Self-Imitation Learning a good policy by imitating past experiences has been discussed where the agent is trained to imitate only the high-reward trajectories with the SIL (Oh et al., 2018) or GAIL objective (Gangwani et al., 2018) . In contrast, we store the past trajectories ending with diverse states in the buffer, because trajectories with low reward in the short term might lead to high reward in the long term, and thus following a diverse set of trajectories could be beneficial for discovering optimal solutions. Furthermore, our method focuses on explicit trajectory-level imitation while existing methods use sampled state-action pairs from the buffer to update the policy. Gangwani et al. (2018) proposed to learn multiple diverse policies in a SIL framework using the Stein Variational Policy Gradient. Empirically, their exploration can be limited by the number of policies learned simultaneously and the exploration performance of every single policy, as shown in Appendix F. Exploration Many exploration methods (Schmidhuber, 1991; Auer, 2002; Chentanez et al., 2005; Strehl & Littman, 2008) in RL tend to award a bonus to encourage an agent to visit novel states. Recently this idea was scaled up to large state spaces (Tang et al., 2017; Bellemare et al., 2016; Ostrovski et al., 2017; Burda et al., 2018) . We propose that instead of directly taking a quantification of novelty as an intrinsic reward, one can encourage exploration by rewarding the agent when it successfully imitates demonstrations that would lead to novel states and gain the advantages in exploitation, as discussed in Appendix I. Go-Explore (Ecoffet et al., 2019 ) also shows the benefit of exploration by returning to promising states. Our method can be viewed in general as an extension of Go-Explore, though we do not need to explicitly divide learning into two phases of exploration and robustification. Go-Explore relies on the assumption that the environment is resettable. Resetting to an arbitrary state is often infeasible in real environments and gives an unfair advantage. When using a perfect goal-conditioned policy instead of a direct 'reset' function, this variant of Go-Explore may not explore as efficiently as our method, as discussed in Appendix H. Previous works attempted reaching a goal state by learning a set of sub-policies (Liu et al., 2019) or a goal-conditioned policy in pixel observation space (Dong et al., 2019) . Gregor et al. (2016) ; Eysenbach et al. (2018) ; Pong et al. (2019) seek a diversity of exploration by maximizing the entropy of mixture skill policies or generated goal states. However, these methods do not show experimental results performing well on sparse-reward environments with a rich observation space like Atari games. Goal-Conditioned Policy Andrychowicz et al. (2017) ; Nair et al. (2017) ; Schaul et al. (2015a) ; Pathak et al. (2018) studied learning a goal-conditioned policy. Our trajectory-conditioned policy could be viewed as a goal-conditioned policy. Similarly to hindsight experience replay (Andrychowicz et al., 2017) , our approach samples goal states from past experiences. Compared to conditioning on a single final goal state, the state trajectory includes rich intermediate information leading the Algorithm 1 Diverse Self-Imitation Learning with Trajectory-Conditioned Policy Initialize parameter θ for the trajectory-conditioned policy π θ (at|e ≤t , ot, g) Initialize the trajectory buffer D ← ∅ # Store diverse past trajectories Initialize set of transitions in the current episode E ← ∅ # Store current episode trajectory Initialize set of on-policy samples F ← ∅ # Store data for on-policy PPO update Initialize demonstration trajectory g ← ∅ for each iteration i from 1 to I do for each step t do Observe st = {ot, et} and choose an action at ∼ π θ (at|e ≤t , ot, g) Execute action at in the environment to get rt, ot+1, et+1

Store transition E ← E ∪ {(ot, et, at, rt)} # Positive reward if agent follows demonstration g # No reward after agent completes g and then takes random exploration Determine r DTSIL t by comparing e ≤t+1 with g (Eq. 1) Store on-policy sample F ← F ∪ (ot, et, at, g, r DTSIL t ) end for if st+1 is terminal then

D ← UpdateBuffer(D, E) (Alg. 2) Clear current episode trajectory E ← ∅ g ← SampleDemo(D, i, I) (Alg. 3) end if θ ← θ -η∇ θ L RL #

Perform PPO update using on-policy samples (Eq. 2) Clear on-policy samples F ← ∅ θ ← θ -η∇ θ L SL # Perform supervised learning updates using samples from D for J times (Eq. 3) end for agent to follow a demonstration and reach the goal state even far away from the current state. Our method shares the same motivation as Duan et al. (2017) which uses an attention model over the demonstration but mainly focuses on the block stacking task. However, our architecture is simpler since it does not use an attention model over the current observation and our method is evaluated on various environments.

3. METHOD:

The main idea of our method is to maintain a buffer of diverse trajectories collected during training and to train a trajectory-conditioned policy by leveraging reinforcement learning and supervised learning to roughly follow demonstrations sampled from the trajectory buffer. The demonstration trajectories cover diverse possible directions in the environment. Therefore, the agent is encouraged to explore beyond various visited states in the environment and gradually push its exploration frontier further. In the meantime, we can train the policy to imitate the best trajectories collected to exploit the past good experiences. We put more weights on exploration in the early stage of training, and then increases the probability of imitating the best trajectories (i.e., exploitation) as training goes on. We name our method as Diverse Trajectory-conditioned Self-Imitation Learning (DTSIL).

3.1. BACKGROUND AND NOTATION:

In the standard reinforcement learning setting, at each time step t, an agent observes a state s t , selects an action a t ∈ A, and receives a reward r t when transitioning to a next state s t+1 ∈ S, where S is a set of all states and A is a set of all actions. The goal is to find a policy π θ (a|s) parameterized by θ that maximizes the expected return

E π θ [ T t=0 γ t r t ],

where γ ∈ (0, 1] is a discount factor. In our work, we assume a state s t includes the agent's observation o t (e.g., raw pixel image) and a high-level abstract state embedding e t (e.g., the agent's location in the abstract space). The embedding e t may be learnable from o ≤t (e.g., ADM (Choi et al., 2018) could localize the agent in Atari games), but in this work, we consider a setting where high-level embedding is provided as a part of s t 1 . A trajectory-conditioned policy π θ (a t |e ≤t , o t , g) (which we refer to as π θ (•|g) in shorthand notation) takes a sequence of state embeddings g = {e g

1 , e g 2 , • • • , e g |g| } as input for a demonstration, where |g| is the length of the trajectory g. A sequence of the agent's past state embeddings e ≤t = {e 1 , e 2 , • • • , e t } is provided to determine which part of the demonstration has been followed by the agent. Together with the current observation o t , it helps to determine the correct action a t to accurately imitate the demonstration. Our goal here is to find a set of optimal state embedding sequence(s) g * and the policy π * θ (•|g) to maximize the return:

g * , θ * arg max g,θ E π θ (•|g) [ T t=0 γ t r t ].

For robustness we may want to find multiple near-optimal embedding sequences with similar returns and a trajectoryconditioned policy for executing them. In our implementation, we train the trajectory-conditioned policy to imitate the best trajectories. Alternatively, an unconditional stochastic policy could also be trained to imitate the best trajectories, which may further improve generalization and robustness (see Appendix C.1 for more discussion and experiments).

3.2. ORGANIZING TRAJECTORY BUFFER:

We maintain a trajectory buffer D = {(e (1) , τ (1) , n (1) ), (e (2) , τ (2) , n (2) ), • • • } of diverse past trajectories. For each embedding-trajectory-count tuple (e (i) , τ (i) , n (i) ), τ (i) is the best trajectory ending with a state with the high-level representation e (i) , and n (i) is the number of times the cluster represented by this state embedding e (i) has been visited during training. To maintain a compact buffer, similar state embeddings within the tolerance threshold th can be clustered together, and the existing entry is replaced if an improved trajectory τ (i) ending with a near-identical state is found.

When given a new episode E = {(o 0 , e 0 , a 0 , r 0 ), • • • , (o T , e T , a T , r T )}, all of the state embeddings e t (1 ≤ t ≤ T ) in this episode E are considered as follows (similarly to Ecoffet et al. (2019) ), because the buffer should maintain all of the possible paths available for future exploration to avoid missing any possibility to find an optimal solution. If the Euclidean distance between e t and any state embedding e (i) in the buffer is larger than th (i.e e t does not belong to any existing cluster in the buffer), (e t , τ ≤t , 1) is directly pushed into the buffer, where τ ≤t = {(o 0 , e 0 , a 0 , r 0 ), • • • , (o t , e t , a t , r t )} is the agent's partial episode ending with e t . If there exists e (k) similar to e t (i.e., e (k) and e t belong to the same cluster within threshold th) and the partial episode τ ≤t is better (i.e., higher return or shorter trajectory) than the stored trajectory τ (k) , τ (k) is replaced by the current trajectory τ ≤t , and e (k) is replaced by e t to represent this cluster of state embeddings. The full algorithm in pseudo-code is described in Appendix A.1.

3.3. SAMPLING DEMONSTRATIONS:

When learning a trajectory-conditioned policy π, demonstration trajectories are sampled from the buffer D. We record the count n (i) of how many times the cluster represented by this state embedding e (i) is visited. In the exploration mode, we set the probability of sampling each trajectory as 1/

√:

n (i) . This is inspired by the count-based exploration bonus (Strehl & Littman, 2008; Bellemare et al., 2016) and the idea of rank-based prioritization (Schaul et al., 2015b; Ecoffet et al., 2019) : we prioritize a trajectory that ends with a less frequently visited state because this leads the agent to reach rarely visited regions in the state space and is more promising for discovering novel states.

On the other hand, in the imitation mode, we sample the best trajectories stored in the buffer for imitation learning. These trajectories are used to train the policy to converge to a high-reward behavior (Aytar et al., 2018; Ecoffet et al., 2019) . To balance between exploration and exploitation, we decrease the probability of taking the exploration mode and exploit the best experiences more as training goes on. The algorithm is described in Appendix A.2.

3.4. LEARNING TRAJECTORY-CONDITIONED POLICY:

Imitation Reward Given a demonstration trajectory g = {e g 0 , e g 1 , • • • , e g |g| }, we provide reward signals for imitating g. At the beginning of an episode, the index u of the last visited state embedding in the demonstration is initialized as u = -1. At each step t, if the agent's new state s t+1 has an embedding e t+1 and it is the similar enough to any of the next ∆t state embeddings starting from the last visited state embedding e g u in the demonstration (i.e., e t+1 -e g u < th where u < u ≤ u+∆t), then it receives a positive imitation reward r im , and the index of the last visited state embedding in the demonstration is updated as u ← u . This encourages the agent to visit the state embeddings in the demonstration in a soft-order so that the agent could explore around the demonstration and the demonstration plays a role to guide the agent to the region of interest in the state embedding space. To summarize, the agent receives a reward r DTSIL t defined as 

EQUATION

)

Demonstration Trajectory g ⇠ D < l a t e x i t s h a 1 _ b a s e 6 4 = " 2 0 X v u Q o w m n / b 4 w Z L N Q N p O 6 y y M X w = " > A A A C u n i c b V F N b x M x E H W W r 1 K + 0 n L k Y h E h c Q j R b o t E D x w q w Y F j k U h b q Y m i s X e y s e K P x Z 4 F l t X + B 3 4 B V / h L / B u 8 a Q 4 0 y 0 i W n t + b 8 Y z n i V K r Q G n 6 Z 5 D c u n 3 n 7 r 2 9 + / s P H j 5 6 / G R 4 c H g e X O U l T q X T z l 8 K C K i V x S k p 0 n h Z e g Q j N F 6 I 9 b t O v / i C P i h n P 1 F d 4 t x A Y d V S S a B I L Y a H B Z 8 F Z f j M A K 0 k 6 O Z 9 u x i O 0 k m 6 C d 4 H 2 R

= " > A A A C q X i c b V F N b 9 N A E N 2 Y r 1 I + 2 s K R y 4 o I C Y k Q 2 Q W J H i t x 6 b F V S R v R R t F 4 P b F X 2 Q + z O 6 Z y L f 8 E p J 7 g t / F v u k 5 z o D E j r f T 2 v Z m d 2 X l p q a S n O P 4 7 i B 4 8 f P T 4 y d b T 7 W f P X 7 z c 2 d 1 7 d e Z t 5 Q R O h F X W T V P w q K T B C U l S O C 0 d g k 4 V n q f L r 5 1 + / h O d l 9 Z 8 o 7 r E m Y b c y I U U Q I E 6 L e Y 0 3 x 3 G 4 3 g V v A + S N R i y d R z P 9 w Y 3 l 5 k V l U Z D Q o H 3 F 0 l c 0 q w B R 1 I o b L c v K 4 8 l i C X k e B G g A Y 1 + 1 q x m b f m 7 w G R 8 Y V 0 4 h v i K / b e i A e 1 9 r d O Q q Y E K v 6 l 1 5 H 8 1 A U a g 2 u h O i 4 N Z I 0 1 Z E R p x 1 3 x R K U 6 W d 8 v g m X Q o S N U B g H A y z M 9 F A Q 4 E h Z X

O F G G n f B w K M U G i d B B I k X 1 i E o J n H K 1 q e t P r 1 G 5 4 X R 3 0 J l c a 6 g 0 G I p O I R I T X G R X d V F s 9 g f p u O 0 C 9 o H 2 Q Y M y S b O F g e D 2 1 l u e K l Q B y 7 B + 8 s s t W F e g w u C S 2 z 2 Z q V H C 3 w N B V 5 G q E G h n 9 f d v A 1 9 G 5 m c L o 2 L R w f a s f 9 W 1 K C 8 r x S L m Q r C y m 9 r L f l f j Y P m K L e 6 h + X x v B b a l g E 1 v 2 u + L C U N h

J i f k C z k j E 8 L J m v w k v 8 j v 5 E M y S W b J 1 V 1 q M t j U v C L 3 I i n + A r 0 C 2 R A = < / l a t e x i t > e0 < l a t e x i t s h a 1 _ b a s e 6 4 = " M F p P + x j f V 7 C W x G v c F 7 o e N i R o z c M = " > A A A C q X i c b V F N b x M x E H W W r 1 I + 2 s K R i 0 W E h E S I d g s S P V b i w r E V p I 1 o o 2 h 2 d r K x 4 i 9 s L 9 V 2 t T 8 B i R P 8 N v 4 N 3 j Q H m m U k S 8 / v z X j G 8 3 I r h Q 9 p + m e Q 3 L l 7 7 / 6 D n Y e 7 j x 4 / e b q 3 f / D s z J v K I U 3 Q S O O m O X i S Q t M k i C B p a h 2 B y i W d 5 6 u P n X 7 + n Z w X R n 8 J t a W Z g l K L h U A I k f p M 8 3 S + P 0 z H 6 T p 4 H 2 Q b M G S b O J k f D H 5 e F g Y r R T q g B O 8 v s t S G W Q M u C J T U 7 l 5 W n i z g C k q 6 i F C D I j 9 r 1 r O 2 / F V k C r 4 w L h 4 d + J r 9 t 6 I B 5 X 2 t 8 p i p I C z 9 t t a R / 9 U Q N J L c 6 h 4 W R 7 N G a F s F 0 n j T f F F J H g z v l s E L 4 Q i D r C M A d C L O z 3 E J D j D E l d 1 6 P Y j V d d t j 3 n 4 L j u K P 1 0 J H S J E 7 c H W j h C 4 U 2 F E n + 7 Y n + y V Y 8 u O S j K L g B P Y z w D l z 5 U c 8 j 9 1 K Z y p d x A u C x B F f m j y v R 9 w a L z o P h S 7 b 6 G G 2 7 V g f n B 2 O

s 3 f j w 9 P 3 w + O j j Z s 7 7 A V 7 y V 6 z j H 1 g x + w T O 2 E T h q x k P 9 g v 9 j t 5 k 5 w m 0 + T r T W o y 2 N Q 8 Z 7 c i w b 8 v G d c q < / l a t e x i t > e1 < l a t e x i t s h a 1 _ b a s e 6 4 = " 0 z c S n W S a I Z Z 2 k h 7 0 p A q k 1 + J 9 I 7 4 = " > A

A A C q X i c b V F N b x M x E H W W r 1 I + 2 s K R i 0 W E h E S I d g s S P V b i w r E V p I 1 o o 2 h 2 d r K x 4 i 9 s L 9 V 2 t T 8 B i R P 8 N v 4 N 3 j Q H m m U k S 8 / v z X j G 8 3 I r h Q 9 p + m e Q 3 L l 7 7 / 6 D n Y e 7 j x 4 / e b q 3 f / D s z J v K I U 3 Q S O O m O X i S Q t M k i C B p a h 2 B y i W d 5 6 u P n X 7 + n Z w X R n 8 J t a W Z g l K L h U A I k f p M 8 2 y + P 0 z H 6 T p 4 H 2 Q b M G S b O J k f D H 5 e F g Y r R T q g B O 8 v s t S G W Q M u C J T U 7 l 5 W n i z g C k q 6 i F C D I j 9 r 1 r O 2 / F V k C r 4 w L h 4 d + J r 9 t 6 I B 5 X 2 t 8 p i p I C z 9 t t a R / 9 U Q N J L c 6 h 4 W R 7 N G a F s F 0 n j T f F F J H g z v l s E L 4 Q i D r C M A d C L O z 3 E J D j D E l d 1 6 P Y j V d d t j 3 n 4 L j u K P 1 0 J H S J E 7 c H W j h C 4 U 2 F E n + 7 Y n + y V Y 8 u O S j K L g B P Y z w D l z 5 U c 8 j 9 1 K Z y p d x A u C x B F f m j y v R 9 w a L z o P h S 7 b 6 G G 2 7 V g f n B 2 O

s 3 f j w 9 P 3 w + O j j Z s 7 7 A V 7 y V 6 z j H 1 g x + w T O 2 E T h q x k P 9 g v 9 j t 5 k 5 w m 0 + T r T W o y 2 N Q 8 Z 7 c i w b 8 x X N c r < / l a t e x i t > et < l a t e x i t s h a 1 _ b a s e 6 4 = " h C K y 

M / k T + C p m y s N M b 3 6 h m b n X 4 a o = " > A A A C q X i c b V F N b x M x E H W W r 1 I + 2 s K R i 0 W E h E S I d g s S P V b i w r E V p I 1 o o 2 j W O 9 l Y 8 R f 2 L N V 2 t T 8 B i R P 8 N v 4 N 3 j Q H m m U k S 8 / v z X j G 8 3 K n Z K A 0 /

Y B Q 7 a J k / n B 4 O d l Y U W l 0 Z B Q E M J F l j q a N e B J C o X t 7 m U V 0 I F Y Q Y k X E R r Q G G b N e t a W v 4 p M w R f W x 2 O I r 9 l / K x r Q I d Q 6 j 5 k a a B m 2 t Y 7 8 r y b A C F R b 3 W l x N G u k c R W h E T f N F 5 X i

Y 3 Q z s n m c M + 2 Q g u B P k Z 8 g 0 V 8 = " > A A A C r n i c b V F N b x M x E H W W j 5 b y 1 c K R i 0 W E x C F E u w W p P V b i w r F I J I 3 U r K K x d 7 J r x V + 1 v a B l t f 8 B c Y U / x r / B m + Z A s 4 x k 6 f m 9 G c 9 4 H r N S + J C m f 0 b J v f s P H h 4 c P j p 6 / O T p s + f H J y / m 3 t S O 4 4 w b a d y C g U c p N M 6 C C B I X 1 i E o J v G K b T 7 2 + t V X d F 4 Y / S U 0 F n M F p R Z r w S F E a r E E a S t Y h d X x O J 2 m 2 6 B D k O 3 A m O z i c n U y + r E s D K 8 V 6 s A l e H + d p T b k L b g g u M T u a F l 7 t M A 3 U O J 1 h B o U + r z d D t z R N 5 E p 6 N q 4 e H S g W / b f i h a U 9 4 1 i M V N B q P y + 1 p P / 1 T h o j n K v e 1 i f 5 6 3 Q t g 6 o + W 3 z d S 1 p M L T f C C 2 E Q x 5 k E w F w J + L 8 l F f g g I e 4 t z u v B 7 H 5 3 g 2 Y d z f B Y f z x V u g J K Z g D 1 7 R K 6 E K B n f S y 7 w a y r 8 C i n 5 Z o F A Y n + D A D n D P f / I S y 2 K 1 0 p t Z F v H C Q f E I r w 1 g z o d Z 4 0 R s p d N l F D 7 N 9

x 4 Z g f j r N 3 k 9 P P 3 8 Y X 5 z v 3 D w k r 8 h r 8 p Z k 5 I x c k E / k k s w I J 5 L 8 J L / I 7 y R N 5 k m e r G 5 T k 9 G u 5 i W 5 E 0 n 1 F w 6 j 2 Z 0 = < / l a t e x i t > Attention Readout ct < l a t e x i t s h a 1 _ b a s e 6 4 = " E 8 L S H h q g 8 M s h a 1 _ b a s e 6 4 = " p I t X 1 d L e e g v b 2 d V e e + 9 N Q 9 5 + R 5 B 5 w r P 8 9 X H T j / / j j 5 I a 7 5 Q 7 c 2 y M 5 D a c o 2 e p h t O 9 Y H Z 4 f j 7 N 3 4 8 P T 9 8 P h o 4 + Y O e 8 F e s t c s 

L Y 3 B U k C b B Y j m 8 7 L T A = " > A A A C q X i c b V F N b x M x E H W W r 1 I + 2 s K R i 0 W E h E S I d g s S P V b i w r E V p I 1 o o 2 h 2 d r K x 4 i 9 s L 9 V 2 t T 8 B i R P 8 N v 4 N 3 j Q H m m U k S 8 / v z X j G 8 3 I r h Q 9 p + m e Q 3 L l 7 7 / 6 D n Y e 7 j x 4 / e b q 3 f / D s z J v K I U 3 Q S O O m O X i S Q t M k i C B p a h 2 B y i W d 5 6 u P n X 7 + n Z w X R n 8 J t a W Z g l K L h U A I k f q M 8 z D f H 6 b j d B 2 8 D 7 I N G L J N n M w P B j 8 v C 4 O V I h 1 Q g v c X W W r D r A E X B E p q d y 8 r T x Z w B S V d R K h B k Z 8 1 6 1 l b / i o y B V 8 Y F 4 8 O f M 3 + W 9 G A 8 r 5 W e c x U E J Z + W + v I / 2 o I G k l u d Q + L o 1 k j t K 0 C a b x p v q g k D 4 Z 3 y + C F c I R B 1 h E A O h H n 5 7 g E B x j i y m 6 9 H s T q u u 0 x b 7 8 F R / H H a 6 E j p M g d u L p R Q h c K 7 K i T f d u T / R I s + X F J R l F w A v s Z 4 J y 5 8 i O e x 2 6 l M 5 U u 4 g V B 4 o g v T Z 7 X I 2 6 N F 5 2 H Q p d t 9 D D b d q w P z g 7 H 2 b v x 4 e n 7 4 f H R x s 0 d 9 o K 9 Z K 9 Z x j 6 w Y / a J n b A J Q 1 a y H + w X + 5 2 8 S U 6 T a f L 1 J j U Z b G q e s 1 u R 4 F / E W 9 d s < / l a t e x i t > ot < l a t e x i t

Y f Y = " > A A A C q X i c b V F N b x M x E H W W r 1 I + 2 s K R i 0 W E h E S I d g s S P V b i w r E V p I 1 o o 2 j W O 9 l Y 8 R f 2 L N V 2 t T 8 B i R P 8 N v 4 N 3 j Q H m m U k S 8 / v z X j G 8 3 K n Z K A 0 / T N I 7 t y 9 d / / B z s P d R 4 + f P N 3 b P 3 h 2 F m z l B U 6 E V d Z P c w i o p M E J S V I 4 d

X C m o T R y I Q V Q p D 7 b O c 3 3 h + k 4 X Q f v g 2 w D h m w T J / O D w c / L w o p K o y G h I I S L L H U 0 a 8 C T F A r b 3 c s q o A O x g h I v I j S g M c y a 9 a w t f x W Z g i + s j 8 c Q X 7 P / V j S g Q 6 h 1 H j M 1 0 D J s a x 3 5 X 0 2 A E a i 2 u t P i a N Z I 4 y p C I 2 6 a L y r F y f J u G b y Q H g W p O g I Q X s b 5 u V i C B 0 F x Z b d e J 7 m 6 b n v M 2 2 / k M f 5 4 L X S E k r k H X z d a m k K D G 3 V y a H t y W I L D M C 7 R a i Q v R T 8 D v L d X Y c T z 2 K 3 0 t j J F v A h Q Y s S X N s / r E X

Y x / Y M f v E T t i E C V a y H + w X + 5 2 8 S U 6 T a f L 1 J j U Z b G q e s 1 u R i L / f l 9 d 4 < / l a t e x i t > FC Observation Conv ⇡(at | et, ot, g)

< l a t e x i t s h a 1 _ b a s e 6 4 = " U G e E 0 n 2 u 4 w 7 5 2 s w z 8 a a R h d 6 q r D I where f (•) is a monotonically increasing function (e.g., clipping (Mnih et al., 2015) ). Figure 2 illustrates the updates of u during an episode when the agent visits a state whose embedding is close to state embeddings in the demonstration g.

= " > A A A C x 3 i c b V F N b 9 N A E N 2 Y r 1 I + m s K R A y s i p C K Z y C l I 9 F i J C 9 y K R N p K d W S N 1 x N n l f 0 w u + N C s H z g w J 3 / w R V + D P + G d Z o D j R l p p b f v z e z s z M s r J T 0 l y Z 9 B d O P m r d t 3 d u 7 u 3 r v / 4 O H e c P / R q b e 1 E z g V V l l 3 n o N H J Q 1 O S Z L C 8 8 o h 6 F z h W b 5 8 2 + l n l + i 8 t O Y j r S q c a S i N n E s B F K h s + D S t 5 A F k x F M t C 4 5 Z k y r k 1 M b c Z h T z 8 k U 2 H C X j Z B 2 8 D y Y b M G K b O M n 2 B z / S w o p a o y G h w P u L S V L R r A F H U i h s d 9 P a Y w V i C S V e B G h A o 5 8 1 6 0 l a / j w w B Z 9 b F 4 4 h v m b / r W h A e 7 / S e c j U Q A u / r X X k f z U B R q D a 6 k 7 z o 1 k j T V U T G n H V f F 4 r T p Z 3 q + K F d C h I r Q I A 4 W T 4 P x c L c C A o L P T a 6 y S X X 9 s e 8 / I T O Q w T r 4 W O U D J 3 4 F a N l q b Q U M W d 7 N u e 7 B d Q o R + X a D W S k 6 K f A c 7 Z z z 7 m e e h W O l u b I l w E K B H z h c 3 z V c w r 6 2 X n s D R l G z y c b D v W B 6 e H 4 8 m r 8 e G H 1 6 P j o 4 2 b O + w J e 8 Y O 2 I S 9 Y c f s H T t h U y b Y d / a T / W K / o / e R j S 6 j L 1 e p 0 W B T 8 5 h d i + j b X 6 n f 4 c 0 = < / l a t e x i t > V (et, ot, g) < l a t e x i t s h a 1 _ b a s e 6 4 = " V 2 f 7 d B + E U w m F C V X v o a X b Y a 5 N f Y A = " > A A A C v H i c b V H b b t N A E N 2 Y W y m X p s A b L y s i p C K Z y C 5 I 9 A l V 4 o X H I p G 0 U h N Z 4 / X E W W U v Z n d c 5 F r + B z 6 B V / g j / o Z 1 m g e a M N J K Z 8 + Z 2 Z m d k 1 d K e k q S P 4 P o z t 1 7 9 x / s P d x / 9 P j J 0 4 P h 4 b O p t 7 U T O B F W W X e R g 0 c l D U 5 I k s K L y i H o X O F 5 v v r U 6 + d X 6 L y 0 5 i s 1 F c 4 1 l E Y u p A A K V D Z 8 M T 3 C r J 0 p 5 N T F 3 G Y U 8 / J N N h w l 4 2 Q d f B e k G z B i m z j L D g c / Z o U V t U Z D Q o H 3 l 2 l S 0 b w F R 1 I o 7 P Z n t c c K x A p K v A z Q g E Y / b 9 f j d / x 1 Y A q + s C 4 c Q 3 z N / l v R g v a + 0 X n I 1 E B L v 6 3 1 5 H 8 1 A U a g 2 u p O i 5 N 5 K 0 1 V E x p x 0 3 x R K 0 6 W 9 / v h h X Q o S D U B g H A y z M / F E h w I C l u 8 9 T r J 1 X W 3 w 7 z 9 R g 7 D j 9 d C T y i Z O 3 B N q 6 U p N F R x L / t u R / Z L q N C P S 7 Q a y U m x m w H O 2 e 8 + 5 n n o V j p b m y J c B C g R 8 6 X N 8 y b m l f W y t 1 W a s g s e p t u O 7 Y L p 8 T h 9 N z 7 + 8 n 5 0 e r J x c 4 + 9 Z K / Y E U v Z B 3 b K P r M z N m G C X b O f 7 B f 7 H X 2 M i m g V 6 Z v U a L C p e c 5 u R X T 1 F 8 5 F 3 X Y = < / l a t e x i t >

Policy Architecture For imitation learning with diverse demonstrations, we design a trajectoryconditioned policy π θ (a t |e ≤t , o t , g) that should imitate any given trajectory g. Inspired by neural machine translation methods (Sutskever et al., 2014; Bahdanau et al., 2014) , one can view the demonstration as the source sequence and view the incomplete trajectory of the agent's state representations as the target sequence. We apply a recurrent neural network (RNN) and an attention mechanism to the sequence data to predict actions that would make the agent follow the demonstration.

As illustrated in Figure 3 , RNN computes the hidden features h g i for each state embedding e g i (0 ≤ i ≤ |g|) in the demonstration and derives the hidden features h t for the agent's state representation e t . Then the attention weight α t is computed by comparing the current agent's hidden features h t with the demonstration's hidden features h g i (0 ≤ i ≤ |g|). The attention readout c t is computed as an attention-weighted summation of the demonstration's hidden features to capture the relevant information in the demonstration trajectory and to predict the action a t . The more details of policy architecture are described in Appendix B.

Reinforcement Learning Objective With the reward defined as r DTSIL t (Equation 1), the trajectoryconditioned policy π θ can be trained with a policy gradient algorithm (Sutton et al., 2000) :

L RL = E π θ [-log π θ (a t |e ≤t , o t , g) A t ],

where

EQUATION

where the expectation E π θ indicates the empirical average over a finite batch of on-policy samples and n denotes the number of rollout steps taken in each iteration. We use Proximal Policy Optimization (PPO) (Schulman et al., 2017) as an actor-critic policy gradient algorithm for our experiments.

Supervised Learning Objective To improve trajectory-conditioned imitation learning and to better leverage the past trajectories, we propose a supervised learning objective. We sample a trajectory

τ = {(o 0 , e 0 , a 0 , r 0 ), (o 1 , e 1 , a 1 , r 1 ) • • • } ∈ D, formulate the demonstration g = {e 0 , e 1 , • • • , e |g| }

and assume the agent's incomplete trajectory is the partial trajectory g ≤t = e ≤t = {e 0 , e 1 , • • • , e t } for any 1 ≤ t ≤ |g|. Then a t is the 'correct' action at step t for the agent to imitate the demonstration.

Our supervised learning objective is to maximize the log probability of taking such actions:

L SL = -log π θ (a t |e ≤t , o t , g), where g = {e 0 , e 1 , • • • , e |g| }.

(3)

4. EXPERIMENTS:

In the experiments, we aim to answer the following questions: (1) How well does the trajectoryconditioned policy imitate the diverse demonstration trajectories? (2) Does imitation of the past diverse experience enable the agent to further explore more diverse directions and guide the exploration to find the trajectory with a near-optimal total reward? (3) Can our proposed method aid in avoiding myopic behaviors and converge to near-optimal solutions? We compare our method with the following baselines: (1) PPO: Proximal Policy Optimization (Schulman et al., 2017) ; (2) PPO+EXP: PPO with reward f (r t ) + λ/ N (e t ), where λ/ N (e t ) is the count-based exploration bonus, N (e) is the number of times the cluster which the state representation e belongs to was visited during training and λ is the hyper-parameter controlling the weight of exploration term; (3) PPO+SIL: PPO with Self-Imitation Learning (Oh et al., 2018) . More details about the implementation can be found in the Appendix.

4.1. APPLE-GOLD DOMAIN:

The Apple-Gold domain (shown in Figure 1 ) is a simple grid-world environment with misleading rewards that can lead the agent to local optima. An observation consists of the agent's location (x t , y t ) and binary variables showing whether the agent has gotten the apple or the gold. A state is represented as the agent's location and the cumulative positive reward: e t = (x t , y t , t i=1 max(r i , 0)), indicating the location of the agent and the collected objects.

As shown in Figure 4a , PPO, PPO+SIL, and PPO+EXP agents are stuck with the sub-optimal policy of collecting the two apples. In Figure 4b , PPO+EXP agent could occasionally explore further and gather the gold with total reward 8.5. However, the agent does not replicate the good trajectory due to the negative reward along the optimal path and network forgetting about the good experiences. DTSIL marches forward on the right side of the maze and achieves the highest total reward 8.5 within the time limit. Figure 4c shows the number of different state embeddings found during training.

In Figure 4d , we show the average success ratio of the imitation during training. It is defined as follows: for a given demonstration g = {e g 0 , e g 1 , • • • , e g |g| }, let u be the index of the last visited state embedding in g when the agent's current episode terminates, then the success ratio of imitating g is u |g| (i.e., the portion of trajectory imitated). Ideally, we want the success ratio to be 1.0, which indicates that the trajectory-conditioned policy could successfully follow any given demonstration from the buffer. At 5M steps, the trajectories with the optimal total reward 8.5 are found, and our trajectory-conditioned policy eventually imitates them well with a success ratio around 1.0.

Figure 5 visualizes a learning process. PPO+SIL fails on this task because the agent quickly exploits good experiences of collecting the apples and the buffer is filled with the trajectories in the nearby region. On the contrary, DTSIL maintains a buffer of diverse trajectories which are used as demonstrations to guide the agent to explore different regions and discover an optimal behavior.

4.2. ATARI MONTEZUMA'S REVENGE AND PITFALL:

We evaluate our method on the hard-exploration game Montezuma's Revenge and Pitfall in the Arcade Learning Environment (ALE) (Bellemare et al., 2013; Machado et al., 2017) . The environment setting is the same as Mnih et al. (2015) . There is a random initial delay resulting in stochasticity in the environment. The observation is a frame of raw pixel images, and the state representation e t = (room t , x t , y t , t i=1 max(r i , 0)) consists of the agent's ground truth location (obtained from RAM) and the accumulated positive environment reward, which implicitly indicates the objects the agent has collected 2 . It is worth noting that even with the ground-truth location of the agent, on these two infamously difficult games, it is highly non-trivial to explore efficiently and avoid local optima without relying on expert demonstrations or being able to reset to arbitrary states. In addition to the agent's location information, many complicated elements such as moving entities, traps, and the agent's inventory are included in the state. Therefore, these Atari games with agent's location information are still much more challenging than the grid world environments. Empirically, as summarized in Table 1 , the previous SOTA baselines using the agent's ground truth location information even fails to achieve high scores.

Using the state representation e t , we introduce a variant 'DTSIL+EXP' that adds a count-based exploration bonus r + t = 1/ N (e t ) to Eq.1 for faster exploration 3 . As shown in Figure 6a and 6e, in the early stage, the average episode reward of DTSIL+EXP is worse than PPO+EXP because our policy is trained to imitate diverse demonstrations rather than directly maximize the environment reward. Contrary to PPO+EXP, DTSIL+EXP agent is not eager to myopically follow the high-reward path since the path with a relatively low score in the short term might lead to higher rewards in the long term. On Montezuma's Revenge, for example, with two keys in hand, PPO+EXP agent often opens a nearby door and loses the chance of opening the last two doors of the first level 4 . As training continues, DTSIL+EXP successfully discovers trajectories to pass the first level with a total reward of more than 20,000, as shown in Figure 6b . While gradually increasing the probability of imitating the best trajectories in the buffer by sampling them as demonstrations, the average episode reward 2 We can also use the number of keys as an element in the state embedding as in (Ecoffet et al., 2019) to reduce the size of the state embedding space and improve the performance, as shown in Appendix H.

3 Note that the existing exploration methods listed in Table 1 already take advantage of count-based exploration bonus (e.g., A2C+CoEX+RAM, SmartHash, DeepCS, and Abstract-HRL). Therefore, combination of DTSIL and the count-based exploration bonus does not introduce unfair advantages over other baselines. 4 Demo videos of the learned policies for both PPO+EXP and DTSIL+EXP are available at https:// sites.google.com/view/diverse-sil. In comparison to DTSIL+EXP, we could see the PPO+EXP agent does not explore enough to make best use of the tools (e.g. sword, key) collected in the game. A map of this level is shown in Figure 16 2019) assumes more high-level state information, including the agent's location, inventory and invetory history, etc. DTSIL, A2C+CoEX+RAM (Choi et al., 2018) , SmartHash (Tang et al., 2017) , and DeepCS (Stanton & Clune, 2018) only make use of agent's location information from RAM, while A2C+SIL (Oh et al., 2018) , PPO+CoEX (Choi et al., 2018) , and RND (Burda et al., 2018) do not use RAM information. The score is averaged over multiple runs, gathered from each paper. could increase to surpass 20,000 in Figure 6a . On Pitfall, the positive reward is much sparser and most of the actions yield small negative rewards that would discourage getting a high total reward in the long term. However, our method still stores the trajectories with negative rewards, encourages the agent to visit these novel regions and then discovers good paths with positive rewards as illustrated in Figure 6f . Therefore we are able to eventually reach average episode reward over 0 in Figure 6e , without expert demonstrations.

Table 1 compares our proposed method with previous works without using any expert demonstration or resetting to an arbitrary state, where our approach significantly outperforms the other approaches which make use of the same information from RAM about the agent's location. In the Appendix C.3, we present more experimental results on other interesting environments with discrete action space such as Deep Sea (Osband et al., 2019) .

4.3. MUJOCO:

We evaluate DTSIL on continuous control tasks. We adapt the maze environment introduced in (Duan et al., 2016) to construct a set of challenging tasks, which require the point mass agent to collect the key, open the door with the same color and finally reach the treasure to get a high score. One key cannot be re-used once it was used before to open a door with the same color, which makes the agent to be easily trapped. A visualization of these environments is shown in Figure 7 . The agent's initial location is randomly sampled from a Gaussian distribution as in standard MuJoco tasks (Brockman et al., 2016) . The observation is the agent's location and range sensor reading about nearby objects. The state representation is e t = (x t , y t ,

t i=1 r i ).

As shown in the first maze of Figure 7 , the agent can easily get the blue key near its initial location and open the blue door in the upper part. However, the optimal path is to bring the key to open the blue door in the bottom and obtain the treasure, reaching an episode reward of 9. In the second maze, the agent should bring the blue key and pick up the green key while avoiding opening the blue door in the upper part. Then, the green and blue key can open the two doors at the bottom of the maze, which results in the total reward of 12. The learning curves in Figure 7 show that PPO, PPO+EXP, and PPO+SIL may get stuck at a sub-optimal behavior, whereas our policy eventually converges to the behavior achieving the high episode reward.

5. CONCLUSION:

This paper proposes to learn diverse policies by imitating diverse trajectory-level demonstrations through count-based exploration over these trajectories. Imitation of diverse past trajectories can guide the agent to rarely visited states and encourages further exploration of novel states. We show that in a variety of environments with local optima, our method significantly improves self-imitation learning (SIL). It avoids prematurely converging to a myopic solution and learns a near-optimal behavior to achieve a high total reward.

B DETAILS OF NETWORK ARCHITECTURE AND TRAINING PROCESS:

In the trajectory-conditioned policy (Figure 3 ), we first embed the input state e t (or e g i ) with a fully-connected layer with 64 units. Next, a RNN with gated recurrent units (GRU) computes the feature h t (or h g i ) with 128 units. The attention weight α t is calculated based on the Bahdanau attention mechanism (Bahdanau et al., 2014) . The concatenation of the attention readout c t , the hidden feature of agent's current state h t , and convolutional features from the observation are used to predict π(a t |e ≤t , o t , g) with a linear layer.

For experiments on the Apple-Key domain, Toy Montezuma's Revenge, and Mujoco, the features from o t are not required for the policy. However, on the Atari games such as Montezuma's Revenge, it is necessary to take the raw observation o t as input into policy because the location information in e ≤t solely could not let the agent to take temporal context into account (e.g. avoiding moving skulls and passing laser gates). With the raw observation o t with shape 84 × 84 × 4 as input, three convolutional layers are used to encode o t and then the convolutional feature is flattened.

h g 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " I V 5 x 0 g x t j c X 9 7 W e A + E q 9 5 F E U Y w A = " > A A A C r X i c b V F N b x M x E H W 2 f J T y l c K R i 0 W E x C G E 3 Y J E j 5 W 4 c C w S a S o 1 a T T 2 T n a t + A v b C 9 q u 9 j + 0 V / h l / B u 8 a Q 4 0 y 0 i W n t + b 8 Y z n M S u F D 2 n 6 Z 5 D s 3 b v / 4 O H + o 4 P H T 5 4 + e z 4 8 f H H m T e U 4 T r m R x p 0 z 8 C i F x m k Q Q e K 5 d Q i K S Z y x 9 e d O n / 1 A 5 4 X R 3 0 J t c a G g 0 G I l O I R I z c r L p m i X 2 X I 4 S i f p J m g f Z F s w I t s 4 X R 4 O r u e 5 4 Z V C H b g E 7 y + y 1 I Z F A y 4 I L r E 9 m F c e L f A 1 F H g R o Q a F f t F s 5 m 3 p m 8 j k d G V c P D r Q D f t v R Q P K + 1 q x m K k g l H 5 X 6 8 j / a h w 0 R 7 n T P a y O F 4 3 Q t g q o + W 3 z V S V p M L R b C M 2 F Q x 5 k H Q F w J + L 8 l J f g g I e 4 t j u v B 7 G + a n v M u + / B Y f z x R u g I K Z g D V z d K 6 F y B H X e y b 3 u y L 8 G i n x R o F A Y n e D 8 D n D M / / Z i y 2 K 1 w p t J 5 v H C Q f E x L w 1 g 9 p t Z 4 0 f k o d H R x O M p 2 H e u D s 6 N J 9 m F y 9 P X j 6 O R 4 6 + Y + e U V e k 7 c k I 5 / I C f l C T s m U c L I m N + Q X + Z 2 8 T 6 b J P L m 8 T U 0 G 2 5 q X 5 E 4 k x V / F F 9 k T < / l a t e x i t > h g 0 < l a t e x i t s h a 1 _ b a s e 6 4 = " w T m 5 n C D f S / x N c f B E z K W + f r X U e t 4 = " > A A A C r X i c b V F N b x M x E H W 2 f J T y l c K R i 0 W E x C G E 3 Y J E j 5 W 4 c C w S a S o 1 a T T 2 T n a t + A v b C 9 q u 9 j + 0 V / h l / B u 8 a Q 4 0 y 0 i W n t + b 8 Y z n M S u F D 2 n 6 Z 5 D s 3 b v / 4 O H + o 4 P H T 5 4 + e z 4 8 f H H m T e U 4 T r m R x p 0 z 8 C i F x m k Q Q e K 5 d Q i K S Z y x 9 e d O n / 1 A 5 4 X R 3 0 J t c a G g 0 G I l O I R I z c r L p m i X 6 X I 4 S i f p J m g f Z F s w I t s 4 X R 4 O r u e 5 4 Z V C H b g E 7 y + y 1 I Z F A y 4 I L r E 9 m F c e L f A 1 F H g R o Q a F f t F s 5 m 3 p m 8 j k d G V c P D r Q D f t v R Q P K + 1 q x m K k g l H 5 X 6 8 j / a h w 0 R 7 n T P a y O F 4 3 Q t g q o + W 3 z V S V p M L R b C M 2 F Q x 5 k H Q F w J + L 8 l J f g g I e 4 t j u v B 7 G + a n v M u + / B Y f z x R u g I K Z g D V z d K 6 F y B H X e y b 3 u y L 8 G i n x R o F A Y n e D 8 D n D M / / Z i y 2 K 1 w p t J 5 v H C Q f E x L w 1 g 9 p t Z 4 0 f k o d H R x O M p 2 H e u D s 6 N J 9 m F y 9 P X j 6 O R 4 6 + Y + e U V e k 7 c k I 5 / I C f l C T s m U c L I m N + Q X + Z 2 8 T 6 b J P L m 8 T U 0 G 2 5 q X 5 E 4 k x V / C 1 N k S < / l a t e x i t > h g |g| < l a t e x i t s h a 1 _ b a s e 6 4 = " 0 I 7 w 7 K U C 7 5 / + c r U s o j M E 2 z U Q P + o = " > A A A C s X i c b V F N b x M x E H W 2 f J T y 0 R a O X C w i J A 4 h 2 m 2 R 6 L E S F 4 5 F I m 1 R G s L Y O 9 m 1 4 i 9 s L 2 j Z 7 n / o h S v 9 X f 0 3 e N M c a J a R L D 2 / N + M Z z 2 N W C h / S 9 G a Q b N 2 7 / + D h 9 q O d x 0 + e P t v d 2 3 9 + 6 k 3 l O E 6 4 k c a d M / A o h c Z J E E H i u X U I i k k 8 Y 8 s P n X 7 2 A 5 0 X R n 8 O t c W Z g k K L h e A Q I j U t v z Z F O 2 8 u i 8 t 2 v j d M x + k q a B 9 k a z A k 6 z i Z 7 w + u L n L D K 4 U 6 c A n e T 7 P U h l k D L g g u s d 2 5 q D x a 4 E s o c B q h B o V + 1 q x m b u n r y O R 0 Y V w 8 O t A V + 2 9 F A 8 r 7 W r G Y q S C U f l P r y P 9 q H D R H u d E 9 L I 5 m j d C 2 C q j 5 b f N F J W k w t F s K z Y V D H m Q d A X A n 4 v y U l + C A h 7 i 6 O 6 8 H s f z V 9 p i 3 3 4 P D + O O V 0 B F S M A e u b p T Q u Q I 7 6 m T f 9 m R f g k U / L t A o D E 7 w f g Y 4 Z 3 7 6 E W W x W + F M p f N 4 4 S D 5 i J a G s X p E r f G i 8 1 L o o v M w 2 3 S s D 0 4 P x t n h + O D T u + H x 0 d r N b f K S v C J v S E b e k 2 P y k Z y Q C e H E k N / k D 7 l O D p M v y b e E 3 a Y m g 3 X N C 3 I n k u V f R u X b Y Q = = < / l a t e x i t > ... < l a t e x i t s h a 1 _ b a s e 6 4 = " / p s 7 m 7 2 I R a k V + X z l F 0 M m Y P W J g H 8 = " > A A A C q X i c b V F N b 9 Q w E P W G r 1 I + 2 s K R i 8 U K C Y k l S g o S P V b i w r E V b L u i X V W T y W z W W n 9 h O 6 A Q 5 S c g c Y L f x r / B 2 e 6 B b h j J 0 v N 7 M 5 7 x v M J K 4 U O W / R k l t 2 7 f u X t v 5 / 7 u g 4 e P H u / t H z w 5 8 6 Z 2 S F M 0 0 r h Z A Z 6 k 0 D Q N I k i a W U e g C k n n x e p 9 r 5 9 / J e e F 0 Z 9 C Y 2 m u o N J i I R B C p D 6 m a X q 1 P 8 7 S b B 1 8 C P I N G L N N n F w d j H 5 e l g Z r R T q g B O 8 v 8 s y G e Q s u C J T U 7 V 7 W n i z g C i q 6 i F C D I j 9 v 1 7 N 2 / E V k S r 4 w L h 4 d + J r 9 t 6 I F 5 X 2 j i p i p I C z 9 t t a T / 9 U Q N J L c 6 h 4 W R / N W a F s H 0 n j d f F F L H g z v l 8 F L 4 Q i D b C I A d C L O z 3 E J D j D E l d 1 4 P Y j V 9 2 7 A v P 4 S H M U f r 4 W e k K J w 4 J p W C V 0 q s J N e 9 t 1 A 9 k u w 5 N O K j K L g B A 4 z w D n z z U 9 4 E b t V z t S 6 j B c E i R O + N E X R T L g 1 X v Q e C l 1 1 0 c N 8 2 7 E h O D t M 8 z f p 4 e n b 8 f H R x s 0 d 9 o w 9 Z y 9 Z z t 6 x Y / a B n b A p Q 1 a x H + w X + 5 2 8 S k 6 T W f L 5 O j U Z b W q e s h u R 4 F 8 + r d b A < / l a t e x i t > e g 0 < l a t e x i t s h a 1 _ b a s e 6 4 = " f x B D 3 y a f J 2 7 j L E z 3 r W m v y I e B I i U = " > A A A C q 3 i c b V F N b x M x E H W W j 5 b y 1 c K R i 0 W E x C G N d l s k e q z E h W M R p K 1 o Q j T r n W y s + A t 7 t m h Z 7 W + A I / w 0 / g 3 e N A e a Z S R L z + / N e M b z c q d k o D T 9 M 0 j u 3 L 1 3 f 2 f 3 w d 7 D R 4 + f P N 0 / e H Y e b O U F T o R V 1 l / m E F B J g x O S p P D S e Q S d K 7 z I V + 8 6 / e I a f Z D W f K L a 4 U x D a e R C C q B I T X C e f i n n + 8 N 0 n K 6 D 9 0 G 2 A U O 2 i b P 5 w e D n t L C i 0 m h I K A j h K k s d z R r w J I X C d m 9 a B X Q g V l D i V Y Q G N I Z Z s 5 6 2 5 a 8 i U / C F 9 f E Y 4 m v 2 3 4 o G d A i 1 z m O m B l q G b a 0 j / 6 s J M A L V V n d a n M w a a V x F a M R N 8 0 W l O F n e r Y M X 0 q M g V U c A w s s 4 P x d L 8 C A o L u 3 W 6 y R X 3 9 s e c / i V P M Y f r 4 W O U D L 3 4 O t G S 1 N o c K N O D m 1 P D k t w G M Y l W o 3 k p e h n g P f 2 W x j x P H Y r v a 1 M E S 8 C l B j x p c 3 z e s S d D b J z U Z q y j R 5 m 2 4 7 1 w f n R O D s e H 3 1 4 M z w 9 2 b i 5 y 1 6 w l + w 1 y 9 h b d s r e s z M 2 Y Y J J 9 o P 9 Y r + T w + R j 8 j m Z 3 q Q m g 0 3 N c 3 Y r E v w L O l z Y A w = = < / l a t e x i t > e g |g| < l a t e x i t s h a 1 _ b a s e 6 4 = " j 2 4 C P U + M P v t b y U n 1 x 2 b Z t m a + z O U = " > A A A C r 3 i c b V F N b x M x E H W W r 1 K + W j h y s Y i Q O I R o t 0 W i x 0 p c O B a J N E V t G m a 9 k 4 0 V f 2 H P g p b t / g c k r v D D + D d 4 0 x x o l p E s P b 8 3 4 x n P y 5 2 S g d L 0 z y C 5 d f v O 3 X s 7 9 3 c f P H z 0 + M n e / t P T Y C s v c C K s s v 4 s h 4 B K G p y Q J I V n z i P o X O E 0 X 7 3 r 9 O l X 9 E F a 8 5 F q h z M N p Z E L K Y A i 9 Q n n z V V 5 1 V 6 W 8 7 1 h O k 7 X w f s g 2 4 A h 2 8 T J f H / w 4 6 K w o t J o S C g I 4 T x L H c 0 a 8 C S F w n b 3 o g r o Q K y g x P M I D W g M s 2 Y 9 c c t f R q b g C + v j M c T X 7 L 8 V D e g Q a p 3 H T A 2 0 D N t a R / 5 X E 2 A E q q 3 u t D i a N d K 4 i t C I 6 + a L S n G y v F s J L 6 R H Q a q O A I S X c X 4 u l u B B U F z c j d d J r r 6 3 P e b 1 F / I Y f 7 w W O k L J 3 I O v G y 1 N o c G N O j m 0 P T k s w W E Y l 2 g 1 k p e i n w H e 2 2 9 h x P P Y r f S 2 M k W 8 C F B i x J c 2 z + s R d z b I z

k l p y j Z 6 m G 0 7 1 g e n B + P s c H z w 4 c 3 w + G j j 5 g 5 7 z l 6 w V y x j b 9 k x e 8 9 O 2 I Q J p t l P 9 o v 9 T r J k m l w m n 6 9 T k 8 G m 5 h m 7 E Y n 8 C 7 u c 2 l I = < / l a t e x i t > Demonstration Trajectory g ⇠ D < l a t e x i t s h a 1 _ b a s e 6 4 = " 2 0

X v u Q o w m n / b 4 w Z L N Q N p O 6 y y M X w = " > A A A C u n i c b V F N b x M x E H W W r 1 K + 0 n L k Y h E h c Q j R b o t E D x w q w Y F j k U h b q Y m i s X e y s e K P x Z 4 F l t X + B 3 4 B V / h L / B u 8 a Q 4 0 y 0 i W n t + b 8 Y z n i V K r Q G n 6 Z 5 D c u n 3 n 7 r 2 9 + / s P H j 5 6 / G R 4 c H g e X O U l T q X T z l 8 K C K i V x S k p 0 n h Z e g Q j N F 6 I 9 b t O v / i C P i h n P 1 F d 4 t x A Y d V S S a B I L Y a H B Z 8 F Z f j M A K 0 k 6 O Z 9 u x i O 0 k m 6 C d 4 H 2 R a M 2 D b O F g e D H 7 P c y c q g J a k h h K s s L W n e g C c l N b b 7 s y p g C X I N B V 5 F a M F g m D e b 4 V v + I j I 5 X z o f j y W + Y f + t a M C E U B s R M 7 s Z w 6 7 W k f / V J F i J e q c 7 L U / m j b J l R W j l d f N l p T k 5 3 m 2 H 5 8 q j J F 1 H A N K r O D + X K / A g K e 7 w x u u k 1 t / b H v P q M 3 m M P 9 4 I H a G V 8 O D r x i i b G y j H n R z a n h x W U G K Y F O g M k l e y n w H e u 6 9 h z E X s V n h X 2 T x e o m F y z F d O i H r M S x d U Z 6 q y R e d h t u t Y H 5 w f T b L j y d H H 1 6 P T k 6 2 b e + w Z e 8 5 e s o y 9 Y a f s A z t j U y b Z N / a T / W K / k 7 e J S F S y v k 5 N B t u a p + x G J P Q X Q e T d u w = = < / l a t e x i t > ... < l a t e x i t s h a 1 _ b a s e 6 4 = " / p s 7 m 7 2 I R a k V + X z l F 0 M m Y P W J g H 8 = " > A A A C q X i c b V F N b 9 Q w E P W G r 1 I + 2 s K R i 8 U K C Y k l S g o S P V b i w r E V b L u i X V W T y W z W W n 9 h O 6 A Q 5 S c g c Y L f x r / B 2 e 6 B b h j J 0 v N 7 M 5 7 x v M J K 4 U O W / R k l t 2 7 f u X t v 5 / 7 u g 4 e P H u / t H z w 5 8 6 Z 2 S F M 0 0 r h Z A Z 6 k 0 D Q N I k i a W U e g C k n n x e p 9 r 5 9 / J e e F 0 Z 9 C Y 2 m u o N J i I R B C p D 6 m a X q 1 P 8 7 S b B 1 8 C P I N G L N N n F w d j H 5 e l g Z r R T q g B O 8 v 8 s y G e Q s u C J T U 7 V 7 W n i z g C i q 6 i F C D I j 9 v 1 7 N 2 / E V k S r 4 w L h 4 d + J r 9 t 6 I F 5 X 2 j i p i p I C z 9 t t a T / 9 U Q N J L c 6 h 4 W R / N W a F s H 0 n j d f F F L H g z v l 8 F L 4 Q i D b C I A d C L O z 3 E J D j D E l d 1 4 P Y j V 9 2 7 A v P 4 S H M U f r 4 W e k K J w 4 J p W C V 0 q s J N e 9 t 1 A 9 k u w 5 N O K j K L g B A 4 z w D n z z U 9 4 E b t V z t S 6 j B c E i R O + N E X R T L g 1 X v Q e C l 1 1 0 c N 8 2 7 E h O D t M 8 z f p 4 e n b 8 f H R x s 0 d 9 o w 9 Z y 9 Z z t 6 x Y / a B n b A p Q 1 a x H + w X + 5 2 8 S k 6 T W f L 5 O j U Z b W q e s h u R 4 F 8 + r d b A < / l a t e x i t > h 0 < l a t e x i t s h a 1 _ b a s e 6 4 = " a v t N / 9 P O Z O L H m x 9 B n g / A E J 4 G I P c = " > A A A C q X i c b V F N b 9 N A E N 2 Y r 1 I + 2 s K R y 4 o I C Y k Q 2 Q W J H i t x 6 b F V S R v R R t F 4 P L F X 2 Q + z u 6 Z y L f 8 E p J 7 g t / F v u k 5 z o D E j r f T 2 v Z m d 2 X l p K Y X z c f x 3 E D 1 4 + O j x k 6 2 n 2 8 + e v 3 i 5 s 7 v 3 6 s y Z y i J N 0 E h j p y k 4 k k L T x A s v a V p a A p V K O k + X X z v 9 / C d Z J 4 z + 5 u u S Z g p y L R Y C w Q f q t J j H 8 9 1 h P I 5 X w f s g W Y M h W 8 f x f G 9 w c 5 k Z r B R p j x K c u 0 j i 0 s 8 a s F 6 g p H b 7 s n J U A i 4 h p 4 s A N S h y s 2 Y 1 a 8 v f B S b j C 2 P D 0 Z 6 v 2 H 8 r G l D O 1 S o N m Q p 8 4 T a 1 j v y v h q C R 5 E Z 3 v z i Y N U K X l S e N d 8 0 X l e T e 8 G 4 Z P B O W 0 M s 6 A E A r w v w c C 7 C A P q z s 3 u t e L K / b H v P x h 7 c U f r w S O k K K 1 I K t G y V 0 p q A c d b J r e 7 I r o C Q 3 z s k o 8 l Z g P w O s N V d u x N P Q L b e m 0 l m 4 I E g c 8 c K k a T 3 i p X G i 8 1 D o v A 0 e J p u O 9 c H Z / j j 5 N N 4 / + T w 8 P F i 7 u c X e s L f s P U v Y F 3 b I j t g x m z B k O f v F f r M / 0 Y f o J J p G 3 + 9 S o 8 G 6 5 j W 7 F x H e A j X o 1 y 0 = < / l a t e x i t > h 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " Y 2 7 6 h o M x S P i X P Z 1 b A T c S 6 7 5 o y P E = " > A A A C q X i c b V F N b 9 N A E N 2 Y r 1 I + 2 s K R y 4 o I C Y k Q 2 Q W J H i t x 6 b F V S R v R R t F 4 P L F X 2 Q + z u 6 Z y L f 8 E p J 7 g t / F v u k 5 z o D E j r f T 2 v Z m d 2 X l p K Y X z c f x 3 E D 1 4 + O j x k 6 2 n 2 8 + e v 3 i 5 s 7 v 3 6 s y Z y i J N 0 E h j p y k 4 k k L T x A s v a V p a A p V K O k + X X z v 9 / C d Z J 4 z + 5 u u S Z g p y L R Y C w Q f q t J g n 8 9 1 h P I 5 X w f s g W Y M h W 8 f x f G 9 w c 5 k Z r B R p j x K c u 0 j i 0 s 8 a s F 6 g p H b 7 s n J U A i 4 h p 4 s A N S h y s 2 Y 1 a 8 v f B S b j C 2 P D 0 Z 6 v 2 H 8 r G l D O 1 S o N m Q p 8 4 T a 1 j v y v h q C R 5 E Z 3 v z i Y N U K X l S e N d 8 0 X l e T e 8 G 4 Z P B O W 0 M s 6 A E A r w v w c C 7 C A P q z s 3 u t e L K / b H v P x h 7 c U f r w S O k K K 1 I K t G y V 0 p q A c d b J r e 7 I r o C Q 3 z s k o 8 l Z g P w O s N V d u x N P Q L b e m 0 l m 4 I E g c 8 c K k a T 3 i p X G i 8 1 D o v A 0 e J p u O 9 c H Z / j j 5 N N 4 / + T w 8 P F i 7 u c X e s L f s P U v Y F 3 b I j t g x m z B k O f v F f r M / 0 Y f o J J p G 3 + 9 S o 8 G 6 5 j W 7 F x H e A j g r 1 y 4 = < / l a t e x i t > h t < l a t e x i t s h a 1 _ b a s e 6 4 = " B e u V o 7 9 k S 0 e L z M o 8 5 X Q 5 j 3 1 w B g 4 = " > A A A C q X i c b V F N b 9 N A E N 2 Y r 1 I + 2 s K R y 4 o I C Y k Q 2 Q W J H i t x 6 b F V S R v R R t F 4 P b F X 2 Q + z O 6 Z y L f 8 E p J 7 g t / F v u k 5 z o D E j r f T 2 v Z m d 2 X l p q a S n O P 4 7 i B 4 8 f P T 4 y d b T 7 W f P X 7 z c 2 d 1 7 d e Z t 5 Q R O h F X W T V P w q K T B C U l S O C 0 d g k 4 V n q f L r 5 1 + / h O d l 9 Z 8 o 7 r E m Y b c y I U U Q I E 6 L e Y 0 3 x 3 G 4 3 g V v A + S N R i y d R z P 9 w Y 3 l 5 k V l U Z D Q o H 3 F 0 l c 0 q w B R 1 I o b L c v K 4 8 l i C X k e B G g A Y 1 + 1 q x m b f m 7 w G R 8 Y V 0 4 h v i K / b e i A e 1 9 r d O Q q Y E K v 6 l 1 5 H 8 1 A U a g 2 u h O i 4 N Z I 0 1 Z E R p x 1 3 x R K U 6 W d 8 v g m X Q o S N U B g H A y z M 9 F A Q 4 E h Z X d e 5 3 k 8 r r t M R 9 / k M P w 4 5 X Q E U q m D l z d a G k y D e W o k 3 3 b k 3 0 B J f p x j l Y j O S n 6 G e C c v f I j n o Z u u b O V y c J F g B I j X t g 0 r U e 8 t F 5 2 H k q T t 8 H D Z N O x P j j b H y e f x v s n n 4 e H B 2 s 3 t 9 g b 9 p a 9 Z w n 7 w g 7 Z E T t m E y Z Y z n 6 x 3 + x P 9 C E 6 i a b R 9 7 v U a L C u e c 3 u R S R u A c + 0 1 3 E = < / l a t e x i t > e g 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " l J w 7 u E 4 A i + b J h y A + 7 B x J A f B 3 l 8 E = " > A A A C r X i c b V F N b x M x E H W W j 5 b y 1 Z Y j F 4 s I i U M I u w W J H i v 1 w r F I p K n U p N H Y O 9 l Y 8 R e 2 t 2 i 7 2 v 9 Q r v D L + D d 4 t z n Q L C N Z e n 5 v x j O e x 6 w U P q T p n 0 H y 4 O G j x z u 7 T / a e P n v + 4 u X + w e G 5 N 6 X j O O F G G n f B w K M U G i d B B I k X 1 i E o J n H K 1 q e t P r 1 G 5 4 X R 3 0 J l c a 6 g 0 G I p O I R I T X G R X d V F s 9 g f p u O 0 C 9 o H 2 Q Y M y S b O F g e D 2 1 l u e K l Q B y 7 B + 8 s s t W F e g w u C S 2 z 2 Z q V H C 3 w N B V 5 G q E G h n 9 f d v A 1 9 G 5 m c L o 2 L R w f a s f 9 W 1 K C 8 r x S L m Q r C y m 9 r L f l f j Y P m K L e 6 h + X x v B b a l g E 1 v 2 u + L C U N h r Y L o b l w y I O s I g D u R J y f 8 h U 4 4 C G u 7 d 7 r Q a x v m h 7 z / n t w G H / c C S 0 h B X P g q l o J n S u w o 1 b 2 T U / 2 K 7 D o x w U a h c E J 3 s 8 A 5 8 w P P 6 I s d i u c K X U e L x w k H 9 G V Y a w a U W u 8 a H 0 U u v M w 2 3 a s D 8 6 P x t n H 8 d H X T 8 O T 4 4 2 b u + Q 1 e U P e k Y x 8 J i f k C z k j E 8 L J m v w k v 8 j v 5 E M y S W b J 1 V 1 q M t j U v C L 3 I i n + A r 0 C 2 R A = < / l a t e x i t > e 0 < l a t e x i t s h a 1 _ b a s e 6 4 = " M F p P + x j f V 7 C W x G v c F 7 o e N i R o z c M = " > A A A C q X i c b V F N b x M x E H W W r 1 I + 2 s K R i 0 W E h E S I d g s S P V b i w r E V p I 1 o o 2 h 2 d r K x 4 i 9 s L 9 V 2 t T 8 B i R P 8 N v 4 N 3 j Q H m m U k S 8 / v z X j G 8 3 I r h Q 9 p + m e Q 3 L l 7 7 / 6 D n Y e 7 j x 4 / e b q 3 f / D s z J v K I U 3 Q S O O m O X i S Q t M k i C B p a h 2 B y i W d 5 6 u P n X 7 + n Z w X R n 8 J t a W Z g l K L h U A I k f p M 8 3 S + P 0 z H 6 T p 4 H 2 Q b M G S b O J k f D H 5 e F g Y r R T q g B O 8 v s t S G W Q M u C J T U 7 l 5 W n i z g C k q 6 i F C D I j 9 r 1 r O 2 / F V k C r 4 w L h 4 d + J r 9 t 6 I B 5 X 2 t 8 p i p I C z 9 t t a R / 9 U Q N J L c 6 h 4 W R 7 N G a F s F 0 n j T f F F J H g z v l s E L 4 Q i D r C M A d C L O z 3 E J D j D E l d 1 6 P Y j V d d t j 3 n 4 L j u K P 1 0 J H S J E 7 c H W j h C 4 U 2 F E n + 7 Y n + y V Y 8 u O S j K L g B P Y z w D l z 5 U c 8 j 9 1 K Z y p d x A u C x B F f m j y v R 9 w a L z o P h S 7 b 6 G G 2 7 V g f n B 2 O s 3 f j w 9 P 3 w + O j j Z s 7 7 A V 7 y V 6 z j H 1 g x + w T O 2 E T h q x k P 9 g v 9 j t 5 k 5 w m 0 + T r T W o y 2 N Q 8 Z 7 c i w b 8 v G d c q < / l a t e x i t > e 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " 0 z c S n W S a I Z Z 2 k h 7 0 p A q k 1 + J 9 I 7 4 = " > A A A C q X i c b V F N b x M x E H W W r 1 I + 2 s K R i 0 W E h E S I d g s S P V b i w r E V p I 1 o o 2 h 2 d r K x 4 i 9 s L 9 V 2 t T 8 B i R P 8 N v 4 N 3 j Q H m m U k S 8 / v z X j G 8 3 I r h Q 9 p + m e Q 3 L l 7 7 / 6 D n Y e 7 j x 4 / e b q 3 f / D s z J v K I U 3 Q S O O m O X i S Q t M k i C B p a h 2 B y i W d 5 6 u P n X 7 + n Z w X R n 8 J t a W Z g l K L h U A I k f p M 8 2 y + P 0 z H 6 T p 4 H 2 Q b M G S b O J k f D H 5 e F g Y r R T q g B O 8 v s t S G W Q M u C J T U 7 l 5 W n i z g C k q 6 i F C D I j 9 r 1 r O 2 / F V k C r 4 w L h 4 d + J r 9 t 6 I B 5 X 2 t 8 p i p I C z 9 t t a R / 9 U Q N J L c 6 h 4 W R 7 N G a F s F 0 n j T f F F J H g z v l s E L 4 Q i D r C M A d C L O z 3 E J D j D E l d 1 6 P Y j V d d t j 3 n 4 L j u K P 1 0 J H S J E 7 c H W j h C 4 U 2 F E n + 7 Y n + y V Y 8 u O S j K L g B P Y z w D l z 5 U c 8 j 9 1 K Z y p d x A u C x B F f m j y v R 9 w a L z o P h S 7 b 6 G G 2 7 V g f n B 2 O s 3 f j w 9 P 3 w + O j j Z s 7 7 A V 7 y V 6 z j H 1 g x + w T O 2 E T h q x k P 9 g v 9 j t 5 k 5 w m 0 + T r T W o y 2 N Q 8 Z 7 c i w b 8 x X N c r < / l a t e x i t > e t < l a t e x i t s h a 1 _ b a s e 6 4 = " h C K y M / k T + C p m y s N M b 3 6 h m b n X 4 a o = " > A A A C q X i c b V F N b x M x E H W W r 1 I + 2 s K R i 0 W E h E S I d g s S P V b i w r E V p I 1 o o 2 j W O 9 l Y 8 R f 2 L N V 2 t T 8 B i R P 8 N v 4 N 3 j Q H m m U k S 8 / v z X j G 8 3 K n Z K A 0 / T N I 7 t y 9 d / / B z s P d R 4 + f P N 3 b P 3 h 2 F m z l B U 6 E V d Z P c w i o p M E J S V I 4 d R 5 B 5 w r P 8 9 X H T j / / j j 5 I a 7 5 Q 7 X C m o T R y I Q V Q p D 7 j n O b 7 w 3 S c r o P 3 Q b Y B Q 7 a J k / n B 4 O d l Y U W l 0 Z B Q E M J F l j q a N e B J C o X t 7 m U V 0 I F Y Q Y k X E R r Q G G b N e t a W v 4 p M w R f W x 2 O I r 9 l / K x r Q I d Q 6 j 5 k a a B m 2 t Y 7 8 r y b A C F R b 3 W l x N G u k c R W h E T f N F 5 X i Z H m 3 D F 5 I j 4 J U H Q E I L + P 8 X C z B g 6 C 4 s l u v k 1 x d t z 3 m 7 T f y G H + 8 F j p C y d y D r x s t T a H B j T o 5 t D 0 5 L M F h G J d o N Z K X o p 8 B 3 t u r M O J 5 7 F Z 6 W 5 k i X g Q o M e J L m + f 1 i D s b Z O e h N G U b P c y 2 H e u D s 8 N x 9 m 5 8 e P p + e H y 0 c X O H v W A v 2 W u W s Q / s m H 1 i J 2 z C B C v Z D / a L / U 7 e J K f J N P l 6 k 5 o M N j X P 2 a 1 I x F / I 5 d d u < / l a t e x i t > Agent's Trajectory ↵ t < l a t e x i t s h a 1 _ b a s e 6 4 = " f d 7 k Y 3 Q z s n m c M + 2 Q g u B P k Z 8 g 0 V 8 = " > A A A C r n i c b V F N b x M x E H W W j 5 b y 1 c K R i 0 W E x C F E u w W p P V b i w r F I J I 3 U r K K x d 7 J r x V + 1 v a B l t f 8 B c Y U / x r / B m + Z A s 4 x k 6 f m 9 G c 9 4 H r N S + J C m f 0 b J v f s P H h 4 c P j p 6 / O T p s + f H J y / m 3 t S O 4 4 w b a d y C g U c p N M 6 C C B I X 1 i E o J v G K b T 7 2 + t V X d F 4 Y / S U 0 F n M F p R Z r w S F E a r E E a S t Y h d X x O J 2 m 2 6 B D k O 3 A m O z i c n U y + r E s D K 8 V 6 s A l e H + d p T b k L b g g u M T u a F l 7 t M A 3 U O J 1 h B o U + r z d D t z R N 5 E p 6 N q 4 e H S g W / b f i h a U 9 4 1 i M V N B q P y + 1 p P / 1 T h o j n K v e 1 i f 5 6 3 Q t g 6 o + W 3 z d S 1 p M L T f C C 2 E Q x 5 k E w F w J + L 8 l F f g g I e 4 t z u v B 7 H 5 3 g 2 Y d z f B Y f z x V u g J K Z g D 1 7 R K 6 E K B n f S y 7 w a y r 8 C i n 5 Z o F A Y n + D A D n D P f / I S y 2 K 1 0 p t Z F v H C Q f E I r w 1 g z o d Z 4 0 R s p d N l F D 7 N 9 x 4 Z g f j r N 3 k 9 P P 3 8 Y X 5 z v 3 D w k r 8 h r 8 p Z k 5 I x c k E / k k s w I J 5 L 8 J L / I 7 y R N 5 k m e r G 5 T k 9 G u 5 i W 5 E 0 n 1 F w 6 j 2 Z 0 = < / l a t e x i t > Attention Readout c t < l a t e x i t s h a 1 _ b a s e 6 4 = " E 8 L S H h q g 8 M L Y 3 B U k C b B Y j m 8 7 L T A = " > A A A C q X i c b V F N b x M x E H W W r 1 I + 2 s K R i 0 W E h E S I d g s S P V b i w r E V p I 1 o o 2 h 2 d r K x 4 i 9 s L 9 V 2 t T 8 B i R P 8 N v 4 N 3 j Q H m m U k S 8 / v z X j G 8 3 I r h Q 9 p + m e Q 3 L l 7 7 / 6 D n Y e 7 j x 4 / e b q 3 f / D s z J v K I U 3 Q S O O m O X i S Q t M k i C B p a h 2 B y i W d 5 6 u P n X 7 + n Z w X R n 8 J t a W Z g l K L h U A I k f q M 8 z D f H 6 b j d B 2 8 D 7 I N G L J N n M w P B j 8 v C 4 O V I h 1 Q g v c X W W r D r A E X B E p q d y 8 r T x Z w B S V d R K h B k Z 8 1 6 1 l b / i o y B V 8 Y F 4 8 O f M 3 + W 9 G A 8 r 5 W e c x U E J Z + W + v I / 2 o I G k l u d Q + L o 1 k j t K 0 C a b x p v q g k D 4 Z 3 y + C F c I R B 1 h E A O h H n 5 7 g E B x j i y m 6 9 H s T q u u 0 x b 7 8 F R / H H a 6 E j p M g d u L p R Q h c K 7 K i T f d u T / R I s + X F J R l F w A v s Z 4 J y 5 8 i O e x 2 6 l M 5 U u 4 g V B 4 o g v T Z 7 X I 2 6 N F 5 2 H Q p d t 9 D D b d q w P z g 7 H 2 b v x 4 e n 7 4 f H R x s 0 d 9 o K 9 Z K 9 Z x j 6 w Y / a J n b A J Q 1 a y H + w X + 5 2 8 S U 6 T a f L 1 J j U Z b G q e s 1 u R 4 F / E W 9 d s < / l a t e x i t > o t < l a t e x i t s h a 1 _ b a s e 6 4 = " p I t X 1 d L e e g v b 2 d V e e + 9 N Q 9 5 + Y f Y = " > A A A C q X i c b V F N b x M x E H W W r 1 I + 2 s K R i 0 W E h E S I d g s S P V b i w r E V p I 1 o o 2 j W O 9 l Y 8 R f 2 L N V 2 t T 8 B i R P 8 N v 4 N 3 j Q H m m U k S 8 / v z X j G 8 3 K n Z K A 0 / T N I 7 t y 9 d / / B z s P d R 4 + f P N 3 b P 3 h 2 F m z l B U 6 E V d Z P c w i o p M E J S V I 4 d R 5 B 5 w r P 8 9 X H T j / / j j 5 I a 7 5 Q 7 X C m o T R y I Q V Q p D 7 b O c 3 3 h + k 4 X Q f v g 2 w D h m w T J / O D w c / L w o p K o y G h I I S L L H U 0 a 8 C T F A r b 3 c s q o A O x g h I v I j S g M c y a 9 a w t f x W Z g i + s j 8 c Q X 7 P / V j S g Q 6 h 1 H j M 1 0 D J s a x 3 5 X 0 2 A E a i 2 u t P i a N Z I 4 y p C I 2 6 a L y r F y f J u G b y Q H g W p O g I Q X s b 5 u V i C B 0 F x Z b d e J 7 m 6 b n v M 2 2 / k M f 5 4 L X S E k r k H X z d a m k K D G 3 V y a H t y W I L D M C 7 R a i Q v R T 8 D v L d X Y c T z 2 K 3 0 t j J F v A h Q Y s S X N s / r E X c 2 y M 5 D a c o 2 e p h t O 9 Y H Z 4 f j 7 N 3 4 8 P T 9 8 P h o 4 + Y O e 8 F e s t c s Y x / Y M f v E T t i E C V a y H + w X + 5 2 8 S U 6 T a f L 1 J j U Z b G q e s 1 u R i L / f l 9 d 4 < / l a t e x i t > FC Observation Conv ⇡(a t | e t , o t , g)

< l a t e x i t s h a 1 _ b a s e 6 4 = " U G e E 0 n 2 u 4 w 7 5 2 s w z 8 a a R h d 6 q r D I V (e t , o t , g) During training, our algorithm begins with an empty buffer D. We initialize the demonstration as a list of zero vectors. With such an input demonstration, the agent performs random exploration to collect trajectories to fill the buffer D. In practice, the sampled demonstration trajectory g = {e g 0 , e g 1 , • • • , e g |g| } could be lengthy. We present a part of the demonstration as the input into the policy, similarly to translating a paragraph sentence by sentence. Specifically, we first input {e g 0 , e g 1 , • • • , e g m } (m ≤ |g|) into the policy. When the index of the agent's last visited state embedding in the demonstration u belongs to {m -∆t, • • • , m}, we think that the agent has accomplished this part of the demonstration, and switch to the next part {e g u , e g u+1 , • • • , e g u+m }. We repeat this process until the last part of the demonstration. If the last part {e g u , e g u+1 , • • • , e g |g| } is less than m + 1 steps long, we pad the sequence with zero vectors.

= " > A A A C x 3 i c b V F N b 9 N A E N 2 Y r 1 I + m s K R A y s i p C K Z y C l I 9 F i J C 9 y K R N p K d W S N 1 x N n l f 0 w u + N C s H z g w J 3 / w R V + D P + G d Z o D j R l p p b f v z e z s z M s r J T 0 l y Z 9 B d O P m r d t 3 d u 7 u 3 r v / 4 O H e c P / R q b e 1 E z g V V l l 3 n o N H J Q 1 O S Z L C 8 8 o h 6 F z h W b 5 8 2 + l n l + i 8 t O Y j r S q c a S i N n E s B F K h s + D S t 5 A F k x F M t C 4 5 Z k y r k 1 M b c Z h T z 8 k U 2 H C X j Z B 2 8 D y Y b M G K b O M n 2 B z / S w o p a o y G h w P u L S V L R r A F H U i h s d 9 P a Y w V i C S V e B G h A o 5 8 1 6 0 l a / j w w B Z 9 b F 4 4 h v m b / r W h A e 7 / S e c j U Q A u / r X X k f z U B R q D a 6 k 7 z o 1 k j T V U T G n H V f F 4 r T p Z 3 q + K F d C h I r Q I A 4 W T 4 P x c L c C A o L P T a 6 y S X X 9 s e 8 / I T O Q w T r 4 W O U D J 3 4 F a N l q b Q U M W d 7 N u e 7 B d Q o R + X a D W S k 6 K f A c 7 Z z z 7 m e e h W O l u b I l w E K B H z h c 3 z V c w r 6 2 X n s D R l G z y c b D v W B 6

< l a t e x i t s h a 1 _ b a s e 6 4 = " V 2 f 7 d B + E U w m F C V X v o a X b Y a 5 N f Y A = " > A A A C v H i c b V H b b t N A E N 2 Y W y m X p s A b L y s i p C K Z y C 5 I 9 A l V 4 o X H I p G 0 U h N Z 4 / X E W W U v Z n d c 5 F r + B z 6 B V / g j / o Z 1 m g e a M N J K Z 8 + Z 2 Z m d k 1 d K e k q S P 4 P o z t 1 7 9 x / s P d x / 9 P j J 0 4 P h 4 b O p t 7 U T O B F W W X e R g 0 c l D U 5 I k s K L y i H o X O F 5 v v r U 6 + d X 6 L y 0 5 i s 1 F c 4 1 l E Y u p A A K V D Z 8 M T 3 C r J 0 p 5 N T F 3 G Y U 8 / J N N h w l 4 2 Q d f B e k G z B i m z j L D g c / Z o U V t U Z D Q o H 3 l 2 l S 0 b w F R 1 I o 7 P Z n t c c K x A p K v A z Q g E Y / b 9 f j d / x 1 Y A q + s C 4 c Q 3 z N / l v R g v a + 0 X n I 1 E B L v 6 3 1 5 H 8 1 A U a g 2 u p O i 5 N 5 K 0 1 V E x p x 0 3 x R K 0 6 W 9 / v h h X Q o S D U B g H A y z M / F E h w I C l u 8 9 T r J 1 X W 3 w 7 z 9 R g 7 D j 9 d C T y i Z O 3 B N q 6 U p N F R x L / t u R / Z L q N C P S 7 Q a y U m x m w H O 2 e 8 + 5 n n o V j p b m y J c B C g R 8 6 X N 8 y b m l f W y t 1 W a s g s e p t u O 7 Y L p 8 T h 9 N z 7 + 8 n 5 0 e r J x c 4 + 9 Z K / Y E U v Z B 3 b K P r M z N m G C X b O f 7 B f 7 H X 2 M i m g V 6 Z v U a L C p e c 5 u R X T 1 F 8 5 F 3 X Y = < / l a t e x i t >

A reward function f (r t ) = r t is used on the Apple-Gold, Deep Sea and MuJoco domain, and f (r t ) = 2 • clip(r t , 0, 1) on other environments. r im = 0.1 is the reward to encourage imitation. More details about hyperparameters and the environments can be found in the Appendix D.

C ADDITIONAL EXPERIMENTS C.1 GENERALIZATION AND ROBUSTNESS IN STOCHASTIC ENVIRONMENTS:

We evaluate our method on environments with different levels of stochasticity. For Apple-Gold domain, in the environments with random initial location of the agent (Figure 9 ), or with sticky action (Figure 10 ), our DTSIL still outperforms the baselines and achieves near-optimal total episode reward. In a more challenging scenario when the location of the objects can be random, previous works using expert demonstrations (e.g. Aytar et al. (2018) ) would also struggle. Our method can be easily extended to handle this difficulty by ditilling the behavior of good trajectories we collected to train an unconditional policy robust to the stochasticity. For example, on the Apple-Gold domain with pixel observation (Figure 11 ), the location of the gold could be random in the upper middle part of the maze. We first explore for a sufficiently large number of timesteps (e.g. 10M timesteps) with the trajectory-conditioned policy to collect good trajectories and then train an unconditional policy by distilling the behavior, as shown in Figure 11 , to always collect the gold. We could see DTSIL with unconditional policy training is able to generalize in the stochastic environment. 

C.2 EXPERIMENTS ON TOY MONTEZUMAREVENGE:

We evaluate our method on a more challenging domain, Toy Montezuma's Revenge (Roderick et al., 2018) , which requires a more sophisticated strategy to explore the environment. As shown in Figure 12 , there are 24 rooms similar to the layout of the first level of Atari Montezuma's Revenge, with a discrete grid for each room. The agent should navigate the labyrinth to locate the keys, unlock the doors and reach the goal (the treasure room). The observation is represented by the agent's location and cumulative episode reward. The state representation e t = (room t , x t , y t , t i=1 r i ) is the same as the observation.

The learning curve of the averaged episode reward in Figure 13 shows that PPO, PPO+SIL, and PPO+EXP could not learn a policy to reach the goal. The PPO+EXP agent occasionally finds a trajectory with the total reward of 11,200 reaching the treasure room, but fails to exploit this experience. On the other hand, our method learns a good behavior of not only reaching the goal room, but also collecting all of the keys to achieve an optimal total reward of 11,600.

Figure 12 : Map of Toy Montezuma's Revenge, where we show the agent (gray), key(blue), door(green), and treasure (yellow) as squares. The rewards are 100, 300, and 10000, respectively. An optimal path with the highest total reward of 11,600 is shown as a red line. 

C.3 EXPERIMENTS ON DEEP SEA:

As introduced in Osband et al. ( 2019), the deep sea problem is implemented as an N × N grid with a one-hot encoding for state. The agent begins each episode in the top left corner of the grid and descends one row per timestep. Each episode terminates after N steps, when the agent reaches the bottom row. In each state there is a random but fixed mapping between actions A = {0, 1} and the transitions 'left' and 'right'. At each timestep there is a small cost r = -0.01/N of moving right, and r = 0 for moving left. However, should the agent transition right at every timestep of the episode it will be rewarded with an additional reward of +1. This presents a particularly challenging exploration problem for two reasons. First, following the 'gradient' of small intermediate rewards leads the agent away from the optimal policy. Second, a policy that explores with actions uniformly at random has probability 2 -N of reaching the rewarding state in any episode.

We compare DTSIL and baselines on deep sea environments with 10 × 10 grid and and 30 × 30 grid.

The state embedding we use here is exactly the observation. The result is shown in Figure 14 . On the first environment, it is easy for all of the methods to converge to the optimal behavior. The second one is much more challenging to find the optimal trajectory maximizing total reward. Therefore, PPO and PPO+SIL fails at such environment due to the hard exploration. PPO+EXP could not always explore to find the good behavior and exploit it efficiently within 12M timesteps. DTSIL successfully discovers the right way and imitate to converge to the optimal behavior. 

D HYPERPARAMETERS:

The hyper-parameters for our proposed method used in each experiment are listed in Table 2 . On Mujoco environment, RL loss alone worked well so we did not include SL loss for behavior cloning.

On the other environments when action prediction in behavior cloning is poor, we set a large J for quickly learning to imitate demonstrations. When action prediction is accurate enough, we de-emphasize behavior cloning to enhance exploration around the demonstration. ∆t influences how flexibly the demonstration should be followed. In our experiment, we have ∆t < m due to the limit of the length m of the input demonstration part. When the demonstration is longer and harder to follow, we would want larger ∆t to generously provide imitation reward (More detailed ablation study of the hyper-parameter ∆ t is in Appendix J). On Atari games, there are much more different trajectories stored in the buffer, so we sample top-100 trajectories as demonstration for imitation of best experiences. On the other environments, the total number of trajectories is much smaller, so we only take top-10 or top-1. 

E ENVIRONMENT SETTING:

For each experiment we conducted, we list the detailed environment setting in Table 3 . There is stochasticity in the environments of Apple-Gold domain, Toy MontezumaRevenge, Atari, and Mujoco.

On Atari games, we use setting of the random initial delay introduced in (Mnih et al., 2015) . On Mujoco domain, the agent's initial location is randomly sampled from a Gaussian distribution, as in standard MuJoco tasks in OpenAI Gym (Brockman et al., 2016) . 

F COMPARISON WITH LEARNING DIVERSE POLICIES BY SVPG:

While the code for the Stein variational policy gradient (SVPG) in Gangwani et al. (2018) has not yet been released, we replicate the method in Gangwani et al. (2018) to learn diverse policies. Their experiments focus on continuous control tasks with relatively simple observation spaces with limited local optimal branches in the state space. We learn 8 diverse policies in parallel following their method on our Apple-Gold domain with discrete action space. Figure 15 shows a visualization of the learning progress: the 8 policies learn to cover different regions of the environment. The method explores better than PPO+SIL, but the exploration of each individual agent is not strong enough to find the optimal path to achieve the highest episode reward. 

H STUDY OF EXPLORATION EFFICIENCY:

To evaluate the efficiency of exploration, we compare our method with the "exploration phase" in the Go-Explore algorithm (Ecoffet et al., 2019) . The idea behind Go-Explore is to reset the agent to any interesting state sampled from the buffer of state embeddings, and then explore further using random actions. To study the exploration efficiency of our method, we modify the Go-Explore code such that we could not reset to any arbitrary states in the environment. Similarly to (Ecoffet et al., 2019) , we use the state representation (level t , room t , x t , y t , k t ) where k t is the number of keys the agent holds and (x t , y t ) is in a 9 × 9 grid division of the frame, and the sampling weight 1 √ n (i) to sample goal states from the buffer (It is worth noting that the state representation and goal-state sampling function recommended in Go-Explore paper is more complicated than this setting).

In the Go-Explore method without using the direct 'reset' function and with a perfect goal-conditioned policy to visit any state sampled from the buffer, the agent could precisely advance to the goal state by following the stored trajectory. The total steps taken in the environment are counted by summing the number of steps taken to follow the stored trajectories and the number of steps taken to explore. In Figure 18 , we show the average number of rooms found and the number of different state representations found during training. Even if we assume that there is a perfect goal-conditioned policy in Go-Explore to guide the agent to follow the stored trajectory exactly and visit the goal state, the learning curves demonstrate that our method is more efficient for exploring diverse state representations and consequently visits several rooms. This is because our method uses the countbased exploration bonus to encourages the exploration around and beyond the stored trajectories and the imitation reward allows the agent to follow the demonstrations in a soft-order. In addition, we notice that, comparing with the state embedding (room t , x t , y t , t i=1 r i ), the state embedding (level t , room t , x t , y t , k t ) makes the size of embedding space smaller so that the exploration could be more efficient. Such state representation conflates similar states while not conflating states that are meaningfully different. Therefore, our method could reach a higher average score around 29,817. Here, the baseline PPO+Exp is essentially the CoEX method introduced in Choi et al. (2018) with state embedding extracted from RAM, therefore DTSIL performs better than PPO+CoEX+RAM no matter the state embedding is (room t , x t , y t , t i=1 r i ) or (level t , room t , x t , y t , k t ).

I STUDY OF ADVANTAGE IN EXPLOITATION:

We compared our method DTSIL with PPO+EXP in the main text. PPO+EXP encourages exploration to novel states by providing auxiliary rewards to the agent, while our method rewards the agent when it successfully follow the demonstrations which leads to novel states. In order to understand more about the difference between these two mechanism, we propose a variant of our method denoted as "DTSIL-combine". In this variant, we do not separate the exploration mode and imitation mode. However, we always sample the top-K best trajectories with highest total reward ). We investigate the different performance of these two methods on the Apple-Gold domain. With λ = 10 which is the best hyper-parameter we found after searching λ = 5, 10, 20, 50 for PPO+EXP on Apple-Gold domain, in Figure 19c we could notice both PPO+EXP agent and DTSILcombine agent have 3 out of 5 runs finding the optimal trajectory with episode rewards 8.5 and the other 2 runs get stuck at the sub-optimal behavior. However, in Figure 19b , DTSIL-combine is better at optimizing the objective

|τ | t=0 f (r t ) + 10 √ N (et)

averaging over the agent's recent episodes and therefore it achieves higher environment environment reward as training goes on. As shown in Figure 19a , DTSIL-combine agent reproduce the good trajectories to collect the gold in 3 out of 5 runs while PPO+EXP agent is trapped at the behavior collecting the apples. The main reason might be that DTSIL-combine agent never forgets the good experience of collecting gold, and always select such good trajectories as demonstrations to guide the agent, while PPO+EXP might forget the good trajectories occasionally found or fails to exploit them before the exploration bonus vanishes. The importance of exploitation of the good experience to help the agent reproduce high-reward trajectories is also discussed in Oh et al. (2018) .

J ABLATION STUDY OF HYPER-PARAMETER ∆t:

We study the effect of the hyper-parameter ∆t in the various environments. At each step, we provide m = 10 (considering the computational burden, we selected the value of m as 10 for all experiments) steps of state embeddings from the demonstration trajectory as input into the trajectory-conditioned policy. Then we evaluate whether the agent has visited any of the next ∆t state embeddings from the lastly visited state embedding in the demonstration. It worth to note that the last visited state embedding must be included in the part of policy input. Thus, we should only compare the agent's current state embedding with the state embeddings in the demonstration segment provided into the policy for imitation reward. Therefore, the proper value of ∆t should be less than m = 10 and we consider ∆t = 2, 4, 8.

On the simple environments such as Apple-Gold and Deep Sea, we could see in Figure 20a and 20b the different values of ∆t do not influence the performance a lot.

As shown in Figure 20c and 20d, on more challenging environments where the demonstration trajectory is longer and it's harder to learn to imitate the demonstration, it's better to set a larger value of ∆t and we can provide imitation reward to the agent and encourage the imitation learning more generously. In general, allowing the agent some flexibility of imitation by setting ∆t close to m works well.

In summary, ∆t = 8 is a proper value for all of our primary experiment environments. 

K STUDY OF THE STOCHASTICITY IN THE ENVIRONMENT:

As listed in Table 3 , we consider stochastic environments for all the primary experiments, including the Apple-Gold domain, Montezuma's Revenge, Pitfall, and Mujoco maze. We set the initial state of the agent to be random. On the Apple-Gold domain, the agent takes 3 random steps in the left bottom part of the maze before the episode starts. On Montezuma's Revenge, the mechanism of random initial no-ops is one of the standard ways to introduce stochasticity in the environment (Machado et al., 2017) , as in previous work (Mnih et al., 2015) .

To show the difficulty in policy learning introduced by the stochastic environments, we tried to memorize and repeat the action sequence in the demonstration trajectory and check whether the agent could successfully visit the state of interest by following the demonstration. In Figure 21c and 22c , it is clear that the success ratio in imitation is much lower than DTSIL, because the agent could not successfully follow the demonstration by just repeating the action sequence step by step. Especially on Montezuma's Revenge, with random initial no-ops, the state of the enemy and electricity beam when the agent starts moving is randomized. Thus it could not successfully avoid death by just repeating the stored action sequence.

Obviously, when the environment is completely deterministic, repeating the action sequence could perfectly guide the agent to the state of interest. However, with the stochasticity of the random initial state, just memorizing the action sequence is sufficient to make the agent revisit novel regions. Thus, the agent could not revisit the novel regions as efficiently as DTSIL to discover better trajectories and converge to a better total episode reward, as shown in Figure 21a , 21b,22a, 22b . 

L RANDOM EXPLORATION WITH EPSILON-GREEDY POLICY:

In this section, we investigate an additional baseline method, random exploration with epsilon-greedy policy, which is a traditional exploration method in reinforcement learning problems. We consider combining epsilon-greedy policy with PPO or DQN framework and run experiments on Apple-Gold, Deep Sea, and Montezuma's Revenge. Our implementation is based on OpenAI baselines (Dhariwal et al., 2017) .

As shown in Figure 23 , 24, 25, we searched different values of the hyper-parameters for the scheduling of the epsilon, though the performance is not better than DTSIL. Especially, random exploration performs poorly on Montezuma's Revenge. The average score is less than 100, which is consistent with the experimental results from previous works (Mnih et al., 2015; Schulman et al., 2017) . 

:



Figures and Tables:

Figure 1: Map of Apple-Gold domain,where the reward for getting an apple, getting the gold and taking a step in the rock is 1, 10, -0.05 respectively. The time limit for one episode is 45 steps.

a M 2 D b O F g e D H 7 P c y c q g J a k h h K s s L W n e g C c l N b b 7 s y p g C X I N B V 5 F a M F g m D e b 4 V v + I j I 5 X z o f j y W + Y f + t a M C E U B s R M 7 s Z w 6 7 W k f / V J F i J e q c 7 L U / m j b J l R W j l d f N l p T k 5 3 m 2 H 5 8 q j J F 1 H A N K r O D + X K / A g K e 7 w x u u k 1 t / b H v P q M 3 m M P 9 4 I H a G V 8 O D r x i i b G y j H n R z a n h x W U G K Y F O g M k l e y n w H e u 6 9 h z E X s V n h X 2 T x e o m F y z F d O i H r M S x d U Z 6 q y R e d h t u t Y H 5 w f T b L j y d H H 1 6 P T k 6 2 b e + w Z e 8 5 e s o y 9 Y a f s A z t j U y b Z N / a T / W K / k 7 e J S F S y v k 5 N B t u a p + x G J P Q X Q e T d u w = = < / l a t e x i t > Agent's Trajectory

Figure 2: An example showing the updates of u, given ∆t = 4. At each step t, we check the state embedding et+1 to find similar state embedding e g u satisfying et+1 ≈ e g u (i.e. et+1e g u < th) and to determine the reward according to Equation 1. After completing the demonstration, the agent performs random exploration with reward 0 (e5 ∼ e7).

ht < l a t e x i t s h a 1 _ b a s e 6 4 = " B e u V o 7 9 k S 0 e L z M o 8 5 X Q 5 j 3 1 w B g 4

d e 5 3 k 8 r r t M R 9 / k M P w 4 5 X Q E U q m D l z d a G k y D e W o k 3 3 b k 3 0 B J f p x j l Y j O S n 6 G e C c v f I j n o Z u u b O V y c J F g B I j X t g 0 r U e 8 t F 5 2 H k q T t 8 H D Z N O x P j j b H y e f x v s n n 4 e H B 2 s 3 t 9 g b 9 p a 9 Z w n 7 w g 7 Z E T t m E y Z Y z n 6 x 3 + x P 9 C E 6 i a b R 9 7 v U a L C u e c 3 u R S R u A c + 0 1 3 E = < / l a t e x i t > e g 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " l J w 7 u E 4 A i + b J h y A + 7 B x J A f B 3 l 8 E = " > A A A C r X i c b V F N b x M x E H W W j 5 b y 1 Z Y j F 4 s I i U M I u w W J H i v 1 w r F I p K n U p N H Y O 9 l Y 8 R e 2 t 2 i 7 2 v 9 Q r v D L + D d 4 t z n Q L C N Z e n 5 v x j O e x 6 w U P q T p n 0 H y 4 O G j x z u 7 T / a e P n v + 4 u X + w e G 5 N 6 X j O

r Y L o b l w y I O s I g D u R J y f 8 h U 4 4 C G u 7 d 7 r Q a x v m h 7 z / n t w G H / c C S 0 h B X P g q l o J n S u w o 1 b 2 T U / 2 K 7 D o x w U a h c E J 3 s 8 A 5 8 w P P 6 I s d i u c K X U e L x w k H 9 G V Y a w a U W u 8 a H 0 U u v M w 2 3 a s D 8 6 P x t n H 8 d H X T 8 O T 4 4 2 b u + Q 1 e U P e k Y x 8

T N I 7 t y 9 d / / B z s P d R 4 + f P N 3 b P 3 h 2 F m z l B U 6 E V d Z P c w i o p M E J S V I 4 d R 5 B 5 w r P 8 9 X H T j / / j j 5 I a 7 5 Q 7 X C m o T R y I Q V Q p D 7 j n O b 7 w 3 S c r o P 3 Q b

Z H m 3 D F 5 I j 4 J U H Q E I L + P 8 X C z B g 6 C 4 s l u v k 1 x d t z 3 m 7 T f y G H + 8 F j p C y d y D r x s t T a H B j T o 5 t D 0 5 L M F h G J d o N Z K X o p 8 B 3 t u r M O J 5 7 F Z 6 W 5 k i X g Q o M e J L m + f 1 i D s b Z O e h N G U b P c y 2 H e u D s 8 N x 9 m 5 8 e P p + e H y 0 c X O H v W A v 2 W u W s Q / s m H 1 i J 2 z C B C v Z D / a L / U 7 e J K f J N P l 6 k 5 o M N j X P 2 a 1 I x F / I 5 d d u < / l a t e x i t > Agent's Trajectory ↵t < l a t e x i t s h a 1 _ b a s e 6 4 = " f d 7 k

Figure 3: Architecture of the trajectoryconditioned policy (see Appendix B).

Figure 4: Learning curves on Apple-Gold domain averaged over 5 runs, where the curves in dark colors are average over 5 curves in light colors. The x-axis and y-axis correspond to the number of steps and statistics about the performance, respectively. The average reward and average imitation success ratio are the mean values over 40 recent episodes.

Figure6: Learning curves of the average episode reward, the best episode reward, and the number of different rooms found on Montezuma's Revenge and Pitfall, averaged over 3 runs. On Montezuma's Revenge, DT-SIL+EXP discovers around 40 rooms on average while PPO+EXP never finds a path to pass through all 24 rooms at the first level and then proceed to the next level.

Figure7: The reward for getting the key, opening the door, and collecting the treasure (yellow block) is 1, 2, and 6 respectively. The learning curve of the episode reward is averaged over 3 independent runs.

e H 4 8 m r 8 e G H 1 6 P j o 4 2 b O + w J e 8 Y O 2 I S 9 Y c f s H T t h U y b Y d / a T / W K / o / e R j S 6 j L 1 e p 0 W B T 8 5 h d i + j b X 6 n f 4 c 0 = < / l a t e x i t >

Figure8: Architecture of the trajectory-conditioned policy (Repeating Figure3).

Figure9: Learning curves on Apple-Gold domain with random initial location of the agent in the lower left corner, where the curves in dark colors are average over 5 curves in light colors. The x-axis and y-axis correspond to the number of steps and statistics about the performance, respectively. The average reward and average imitation success ratio are the mean values over 40 recent episodes.

Figure11: Learning curves on Apple-Gold domain with stochastic location of the gold in the upper middle part of the maze, where the curves in dark colors are average over 5 curves in light colors. The x-axis and y-axis correspond to the number of steps and statistics about the performance, respectively. The average reward and average imitation success ratio are the mean values over 40 recent episodes.

Figure 13: Learning curves on Toy Montezuma's Revenge averaged over 5 runs.

Figure14: Experiment on Deep Sea. The learning curves shows the average episode reward, best episode reward, the number of found state representations, and the average success ratio of imitating the demonstrations in order. The curves are averaged over 5 independent runs.

Figure 15: Visualization of the trajectories stored in the buffer for PPO+SIL, SVPG diverse Gangwani et al.(2018)  and our method as training continues. In the second row, we show the trajectories for a total of 8 policies learned simultaneously with the SVPG method proposed inGangwani et al. (2018), where each color corresponds to the trajectories collected by each policy.

Figure 16: Map of Atari Montezuma's Revenge at the first level with 24 rooms. On Montezuma's Revenge, there are multiple levels and each level consists of 24 rooms. At the first level, it is challenging to bring two keys to open the two doors in room 17 behind the treasure in room 15, where the agent can pass to the next level.

Figure 17: Learning curves of the number of rooms and the number of different state representations found on Atari Montezuma's Revenge, averaged over 5 runs. The curves in dark colors are the average of the 5 curves in light colors. During training, the state representation used is (levelt, roomt, xt, yt, kt).

while this variant indirectly optimizes such objective by imitating the best trajectories with highest value of

Figure 19: Learning curves averaged over 5 runs. The curves in dark colors are the average of the 5 curves in light colors.

Figure 20: Learning curves averaged over at least 3 independent runs. The curves in dark colors are the average of the curves in light colors.

Curves of the average success ratio in imitation over the recent 40 episodes

Figure 21: Learning curves averaged over 5 independent runs. The curves in dark colors are the average of the curves in light colors. The Apple-Gold domain is with random initial state of the agent.

Figure 22: Learning curves averaged over 3 independent runs. The curves in dark colors are the average of the curves in light colors. The Montezuma's Revenge is with random initial delay of the agent.

.95 PPO epsilon=1 decay=0.99 PPO epsilon=0.5 decay=0.95 PPO epsilon=0.5 decay=0.99 (a) With PPO framework, the value of is scheduled in a exponential way (i.e. ← × decay). . The value of starts from epsilon as annotated in the legends and decreases until 0.

With PPO framework, the value of is scheduled in a linear way (i.e. ← decrement). The value of starts from epsilon as annotated in the legends and decreases until 0.

Figure 23: Learning curves of the average episode rewards over the recent 40 episodes. On the Apple-Gold domain, DTSIL reaches episode reward of 8.5 as shown in Section 4.1 while the random exploration with epsilon-greedy policy gets stuck at the episode reward of 2.

With PPO framework, the value of is scheduled in a exponential way (i.e. ← × decay). The value of starts from epas annotated in the legends and decreases until 0.

With PPO framework, the value of is scheduled in a linear way (i.e. ← decrement). The value of starts from epsilon as annotated in the legends and decreases until 0.

Figure 24: Learning curves of the average episode rewards over the recent 40 episodes. On the Deap Sea environment with N = 30, DTSIL reaches episode reward of 1 as shown in Appendix C.3 while the random exploration with epsilon-greedy policy gets stuck at the negative episode reward.

in Appendix. Comparison with the state-of-the-art results on Montezuma's Revenge and Pitfall. Abstract-HRL Liu et al. (

Table content: <table><tr><td>Method</td><td colspan="8">DTSIL A2C+CoEX+RAM SmartHash DeepCS Abstract-HRL A2C+SIL PPO+CoEX RND</td></tr><tr><td colspan="2">MontezumaRevenge 20,187</td><td>6,600</td><td>5,661</td><td>3,500</td><td>11,000</td><td>2,500</td><td>11,618</td><td>10,070</td></tr><tr><td>Pitfall</td><td>6,546</td><td>-</td><td>-</td><td>-186</td><td>10,000</td><td>-</td><td>-</td><td>-3</td></tr></table>

Hyper-parameters on various environments for our experiments.

Table content: <table><tr><td>Environment</td><td>Apple-Gold</td><td>Toy MontezumaRevenge</td><td>Atari</td><td>Deep Sea</td><td>Mujoco</td></tr><tr><td>Learning Rate η</td><td>2.5e-4</td><td>2.5e-4</td><td>2.5e-4</td><td>2.5e-4</td><td>1e-4</td></tr><tr><td>∆t</td><td>2</td><td>4</td><td>8</td><td>2</td><td>8</td></tr><tr><td>Length of demonstration input part m</td><td>10</td><td>10</td><td>10</td><td>10</td><td>10</td></tr><tr><td>Number of supervised learning updates J</td><td>10 decreases to 1 accuracy ≥ 0.75 when action prediction</td><td>10 decreases to 1 accuracy ≥ 0.75 when action prediction</td><td>10 decreases to 1 accuracy ≥ 0.75 when action prediction</td><td>10 decreases to 1 accuracy ≥ 0.75 when action prediction</td><td>0</td></tr><tr><td>Threshold th for state embedding</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>Top-K trajectories imitation</td><td>1</td><td>10</td><td>100</td><td>1</td><td>10</td></tr><tr><td>Weight of exploration λ in PPO+EXP</td><td>10 (best one among 5, 10, 20, 50)</td><td>1 (best one among 0.5, 1, 2,4)</td><td>1 (best one among 0.5, 1, 2,4)</td><td>0.2 (best one among 0.1, 0.2, 0.5, 1)</td><td>1 (best one among 0.5, 1, 2, 4)</td></tr><tr><td>Discounting factor γ</td><td>0.99</td><td>0.99</td><td>0.99</td><td>0.99</td><td>0.99</td></tr></table>

The setting on various environments for our experiments.

Table content: <table><tr><td>Environment</td><td>Apple-Gold</td><td>Toy MontezumaRevenge</td><td>Atari</td><td>Deep Sea</td><td>Mujoco</td></tr><tr><td>Observation</td><td>agent's location (x, y) in 17x13 grid and binary variables indicating whether apple or gold is collected</td><td>agent's location (room, x, y) in 24x11x11 grid and accumulated reward</td><td>stacked most recent 4 gray observations with shape 84x84x4</td><td>one-hot encoding of state in 10x10 or 30x30 grid</td><td>agent's location (x,y) in 22x22 space and range sensor reading about nearby objects</td></tr><tr><td/><td/><td/><td>( roomt, xt, yt,</td><td/><td/></tr><tr><td>State Representation</td><td colspan="2">(xt, yt, t i=1 max(ri, 0)) (roomt, xt, yt, t i=1 ri)</td><td>t i=1 max(ri, 0)) where (xt, yt) in</td><td colspan="2">same as observation (xt, yt, t i=1 ri)</td></tr><tr><td/><td/><td/><td>9 × 9 grid</td><td/><td/></tr><tr><td>Action</td><td>5 discrete actions: up, down, left, right, noop</td><td>5 discrete actions: up, down, left, right, noop</td><td>18 discrete actions: noop, fire, left, • • •</td><td>2 discrete actions: left, right</td><td>(dx, dy) in continuous action space</td></tr><tr><td/><td/><td/><td/><td>0 if going left</td><td/></tr><tr><td>Reward</td><td>rock -0.05 gold +10 apple +1</td><td>key +100 door +300 treasure +10000</td><td>mostly zero, sparse positive rewards when collecting objects</td><td>-0.01 10 or -0.01 30 if going right 1 at the last step if</td><td>key +1 door +2 treasure +6</td></tr><tr><td/><td/><td/><td/><td>always going right</td><td/></tr><tr><td>Time limit</td><td>45 steps</td><td>1000 steps</td><td>4500 steps</td><td>10 or 30 steps</td><td>1000 steps</td></tr><tr><td/><td/><td/><td>{MontezumaRevenge,</td><td/><td/></tr><tr><td/><td>deterministic or</td><td/><td>Pitfall}-</td><td/><td/></tr><tr><td/><td>take 3 random</td><td>take 5 random</td><td>NoFrameskip-v4;</td><td/><td>take random normal</td></tr><tr><td>Stochasticity</td><td>steps before the</td><td>steps before the</td><td>take a random number</td><td>deterministic</td><td>noise from the</td></tr><tr><td/><td>episode starts</td><td>episode starts</td><td>between 0 and 30</td><td/><td>agent's initial position</td></tr><tr><td/><td>or sticky action</td><td/><td>of noop actions</td><td/><td/></tr><tr><td/><td/><td/><td>before the episode starts</td><td/><td/></tr></table>

Learning curves of the average reward, the best episode reward, the number of rooms, the number of different state representations found on Atari Montezuma's Revenge, averaged over 5 runs. The curves in dark colors are the average of the 5 curves in light colors. During training, the state representation used is (levelt, roomt, xt, yt, kt).

Table content: <table><tr><td/><td colspan="2">Montezuma's Revenge</td><td/><td>Montezuma's Revenge</td><td/><td/><td>Montezuma's Revenge</td><td/><td>Montezuma's Revenge</td></tr><tr><td>Average Reward</td><td>10000 20000 30000</td><td>PPO+Exp DTSIL+Exp</td><td>Best Reward</td><td>50000 100000 150000</td><td>Number of Found Room</td><td>10 20 30 40</td><td>Number of Found State</td><td>1000 2000 3000 4000</td><td>PPO+Exp DTSIL+Exp</td></tr><tr><td/><td>0</td><td/><td/><td>0</td><td/><td>0</td><td/><td>0</td><td/></tr><tr><td/><td colspan="2">0M 160M 320M 480M 640M 800M</td><td/><td>0M 160M 320M 480M 640M 800M</td><td/><td>0M</td><td>160M 320M 480M 640M 800M</td><td>0M</td><td>160M 320M 480M 640M 800M</td></tr><tr><td/><td/><td>Steps</td><td/><td>Steps</td><td/><td/><td>Steps</td><td/><td>Steps</td></tr><tr><td colspan="2">Figure 18:</td><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2020):
The authors identify and address the problem of sub-optimal and myopic behaviors of self-imitation learning in environments with sparse rewards. The authors propose DTSIL to learn a trajectory-conditioned policy to imitate diverse trajectories from the agent’s own past experience. Unlike other self-imitation learning methods, the proposed method not only leverages sub-trajectories with high rewards, but lower-reward trajectories to encourage agent exploration diversity. The authors claim the proposed method to be more likely to find a global optimal solution. Overall, this paper is well-written with comprehensive experimental results. The proposed trajectory-conditioned policy sounds, since rewarded trajectory carries significant information of the goal in the exploration problem. Extensive experimental results demonstrated the effectiveness of the proposed DTSIL. However, I have a few concerns below, that prevent me from giving a direct acceptance. 1. The proposed DTSIL changes the original MDP with sparse reward to an MDP with denser reward, which allows the training process to explore more in the “space” closer to the collected high reward trajectories. Such “exploration” sounds promising. However, it would be nice to compare it with traditional reinforcement learning (e.g., with epsilon-greedy policy for random exploration)? 2. In appendix D, the authors discussed what the parameter delta_t controls, however, it is unclear how delta_t should be chosen in implementation. The authors did not explain how delta_t was selected in their experiments. Choosing the right delta_t may be hard, but it would be nice to introduce what “heuristics” the authors used and suggest to readers.