Align-RUDDER: Learning From Few Demonstrations by Reward Redistribution
Authors: Vihang Prakash Patil
Markus Hofmarcher
Marius-Constantin Dinu
Matthias Dorfer
Patrick M Blies
Johannes Brandstetter
Jose Arjona-Medina
Sepp Hochreiter
Venue: ICLR 2022 Submitted (2022)
Keywords: RUDDER
reinforcement learning
reward redistribution
return decomposition
delayed reward
sparse reward
episodic reward
minecraft

Abstract: Reinforcement Learning algorithms require a large number of samples to solve complex tasks with sparse and delayed rewards. Complex tasks are often hierarchically composed of sub-tasks. Solving a sub-task increases the return expectation and leads to a step in the $Q$-function. RUDDER identifies these steps and then redistributes reward to them, thus immediately giving reward if sub-tasks are solved. Since the delay of rewards is reduced, learning is considerably sped up. However, for complex tasks, current exploration strategies struggle with discovering episodes with high rewards. Therefore, we assume that episodes with high rewards are given as demonstrations and do not have to be discovered by exploration. Unfortunately, the number of demonstrations is typically small and RUDDER's LSTM as a deep learning model does not learn well on these few training samples. Hence, we introduce Align-RUDDER, which is RUDDER with two major modifications. First, Align-RUDDER assumes that episodes with high rewards are given as demonstrations, replacing RUDDER’s safe exploration and lessons replay buffer. Second, we substitute RUDDER’s LSTM model by a profile model that is obtained from multiple sequence alignment of demonstrations. Profile models can be constructed from as few as two demonstrations. Align-RUDDER uses reward redistribution to speed up learning by reducing the delay of rewards. Align-RUDDER outperforms competitors on complex artificial tasks with delayed rewards and few demonstrations. On the MineCraft ObtainDiamond task, Align-RUDDER is able to mine a diamond, though not frequently. 

Under review as a conference paper at ICLR 2022
ALIGN-RUDDER: LEARNING FROM FEW DEMON- STRATIONS BY REWARD REDISTRIBUTION
Anonymous authors Paper under double-blind review
ABSTRACT
Reinforcement Learning algorithms require a large number of samples to solve complex tasks with sparse and delayed rewards. Complex tasks are often hierarchi- cally composed of sub-tasks. Solving sub-task increases the return expectation and leads to step in the Q-function. RUDDER identifies these steps and then redistributes reward to them, thus immediately giving reward if sub-tasks are solved. Since the delay of rewards is reduced, learning is considerably sped up. However, for complex tasks, current exploration strategies struggle with discovering episodes with high rewards. Therefore, we assume that episodes with high rewards are given as demonstrations and do not have to be discovered by exploration. Unfortunately, the number of demonstrations is typically small and RUDDER's L.STM deep learning model does not learn well on these few training samples. Hence, we in- troduce Bign-RUUDER, which is RUDDER with two major modifications. First, Align-RUDDER assumes that episodes with high rewards are given as demonstra- tions, replacing RUDDER's safe exploration and lessons replay buffer. Second, we substitute RUDDER's 's LSTM model by profile model that is obtained from multiple sequence alignment of demonstrations. Profile models can be constructed from as few as two demonstrations. Align-RUDDER uses reward redistribution to speed up learning by reducing the delay of rewards. competitors complex artificial tasks with delayed rewards and few demonstra- tions. On the MineCraft Obt i nD i amond task, Align-RUDDER is able to mine diamond, though not frequently.
outperforms
INTRODUCTION
Reinforcement learning algorithms struggle with learning complex tasks that have sparse and delayed rewards (Sutton & Barto, 2018; Rahmandad et al., 2009; Luoma et al., 2017). For delayed rewards, temporal difference (TD) suffers from vanishing information (Arjona-Medina al., 2019). On the other hand Monte Carlo (MC) has high variance since it must average over all possible futures (Arjona- Medina et al., 2019). Monte-Carlo Tree Search (MCTS), used for Go and chess, can handle delayed and rare rewards since it has a perfect environment model (Silver et al., 2016; 2017). RUDDER (Arjona-Medina et al., 2019; 2018) has been shown to excel in model-free learning of policies when only sparse and delayed rewards are given. RUDDER requires episodes with high rewards to store them in its lessons replay buffer for learning a reward redistribution model like an LSTM network. However, for complex tasks, current exploration strategies find episodes with high rewards only after an incommensurate long time. Humans and animals obtain high reward episodes by teachers, role models, or prototypes. Along this line, we assume that episodes with high rewards are given as demonstrations. Since generating demonstrations is often tedious for humans and cune-consuming for exploration strategies, typically, only a few demonstrations are available. However, RUDDER's LSTM (Hochreiter, 1991; Hochreiter & Schmidhuber, 1997a) as a deep learning method requires many examples for learning. Therefore, we introduce Align- RUDDER, which replaces RUDDER's LSTM with profile model obtained from multiple sequence alignment (MSA) of the demonstrations. Profile models are well known in bioinformatics. They are used to score new sequences according to their sequence similarity to the aligned sequences. Like RUDDER also Align- RUDDER performs reward redistribution using an alignment model-, which considerably speeds up learning even only few demonstrations are available.

---

Under review as a conference paper at ICLR 2022
Figure I: Basic insight into reward redistribution. Left panel, Row 1: An agent has to take key to unlock door. Both events increase the probability of receiving the treasure, which the agent always gets as delayed reward, when the door is unlocked at sequence end. Row 2: The Q-function approximation typically predicts the expected return at every state-action pair (red arrows). Row 3: However, the Q-function approximation requires only to predict the steps (red arrows). Right panel, Row I: The Q-function is the future expected return (blue curve). Green arrows indicate Q-function steps and the big red arrow the delayed reward at sequence end. Row 2 and 3: The redistributed rewards correspond steps in the (2-funciion (small red arrows). Row 4: After redistributing the reward, only the redistributed immediate reward remains (red arrows). Reward is no longer delayed.
Our main contributions are:
We suggest reinforcement algorithm that works well for sparse and delayed rewards, where standard exploration fails but few demonstrations with high rewards are available.
We adopt multiple sequence alignment from bioinformatics to construct reward redistribu- tion technique that works with few demonstrations.
We propose a method that uses alignment techniques and reward redistribution for identifying sub-goals and sub-tasks which in turn allow for hierarchical reinforcement learning.
REVIEW OF RUDDER
Basic insight: Q-functions for complex tasks are step functions. Complex tasks are typically composed of sub-tasks. Therefore the Q-function of an optimal policy resembles step function. The Q-function the expected future return and increases (i.e, makes a step) when a sub-task completed. Identifying large steps in the Q-function speeds learning since it allows (i) to increase the return by performing actions that cause the step and (ii) to sample episodes with a larger return for learning.
An approximation to the Q-function must predict the expected future return for every state-action pair. However, Q-function that resembles ttep-function is mostly constant. Therefore predictions are only necessary at the steps. We have to identify the relevant state-actions that cause the steps and then predict the size of the steps. An LSTM network (Hochreiter, 1991; Hochreiter & Schmidhuber, 1995; 1997a;b) can identify relevant state-actions that open the input gate to store the size the steps in the memory cells. Consequently, LSTM only updates its states and changes its return prediction when a new relevant state-action pair is observed. Therefore, both the change of the prediction and opening input gates indicate Q-function steps through LSTM network that predicts the return of an episode.
Reward Redistribution. We consider episodic Markov decision processes (MDPs), i.c., the reward is only given once at the end of the sequence. The Q Q-function is assumed to be step function, that is, the task can be decomposed into sub-tasks (see previous paragraph). Reward redistribution aims at giving the differences in the Q-function of an optimal policy as a new immediate reward. Since the Q-function an optimal policy is not known, we approximate it by predicting the expected return by LSTM network by an alignment model in this work. The differences in predictions determine the reward redistribution. The prediction model will first identify the largest steps in the Q-function as they decrease the prediction error most. Fortunately, just identifying the largest steps even with poor predictions speeds up learning considerably. See Figure for a description of the reward redistribution.
2

---

Under review as a conference paper at ICLR 2022
Mammon Chorkon Yeast E. col Amooba Archaron
PXTAU
PXVO
AGGANGANTI S TIKE
88
VSL
TECCAOO AULKAB
88
MARNNN
REA
VELPUPLORT PF
APP.
consersation
The function of a protein largely determined by its structure. The relevant regions of this structure are even conserved across organisms, as shown in the left panel. Similarly, solving task can often be decomposed into sub-tasks which are conserved across multiple demonstrations. As shown in the right panel where events are mapped to the letter code for amino acids. Sequence alignment makes those conserved regions visible and enables redistribution reward to important events.
Figure 2:
Learning methods based on reward redistribution. The redistributed reward serves as reward for subsequent learning method: (A) The Q-values can be directly estimated (Arjona-Medhe Medina et al., 2019), which is used in the experiments for the artificial tasks and BC pre-training for MineCraft. (B) Redistributed rewards can serve for learning with policy gradients like Proximal Policy Optimization (PPO) (Schulman et al., 2018), which is used in the MineCraft experiments. (C) Redistributed rewards can serve for temporal difference learning like Q-learning (Watkins, 1989).
LSTM models for reward redistribution. RUDDER uses an LSTM model for predicting the future return. The reward redistribution is the difference between two subsequent predictions. If state- action pair increases the prediction of the return, then it is immediately rewarded. Using state-action uub-sequences (s, a)o: (sg, ag:- St, 0z), the redistributed reward is R&+1 = g((s, a)o.)) g((s, 1),, where g is an LSTM model that predicts the return of the episode. The LSTM model learns at first to approximate the largest steps of the Q-function since they reduce the prediction error the most.
3 ALIGN-RUDDER: RUDDER WITH FEW DEMONSTRATIONS
In bioinformatics, sequence alignment identifies similarities between biological sequences to deter- mine their evolutionary relationship (Needleman & Wunsch, 1970; Smith & Waterman, 1981). The result of the alignment multiple sequences a profile model. The profile model is consensus sequence, frequency matrix, New sequences can be aligned to a profile model and receive an alignment score that indicates how well the new sequences agree the profile model.
Desition-Specifi Scoring Matrix (PSSM) (Stormo et al., 1982).
Aign-RUDDER uses such alignment techniques to align two or more high return demonstrations. For the alignment, assume that the demonstrations follow the same underlying strategy, therefore they are similar to each other analog to being evolutionary related. If the agent generates a state-action sequence (s, a (a)0a-11111 1, then this sequence aligned to the profile model y giving score g((s, a)o:t-1) The next action of the agent extends the state-action sequence by one state-action pair (st, az). The extended sequence (s, a)o.: is also aligned to the profile model g giving another score g((s, a)ox)) The redistributed reward Ri+1 is the difference of these scores: R++1 = ((s,, a) a)o:)) - g((s, a)o:-11 (see Eq. (1)). This difference indicates how much of the return is gained or lost by a adding another sequence element.
HUDDRR scores how close an agent follows an underlying strategy, which has been extracted by the profile model. Similar to the LSTM model, we identify the largest steps in the Q-function via relevant events determined by the profile model. Therefore, redistributing the reward by sequence alignment fits into the RUDDER framework with all its theoretical guarantees. RUDDER's 's theory for reward redistribution valid for LSTM, other recurrent networks, attention mechanisms, or sequence and profile models.
Advantages of alignment compared to LSTM. Learning an LSTM model is severely limited when very few demonstrations are available. First, LSTM is known to require a large number of samples to generalize to new sequences. In contrast, sequence alignment requires only two examples to generalize well as known from bioinformatics. Second, expert demonstrations have high rewards.
3

---

Under review as a conference paper at ICLR 2022
Defining Events
II) Scoring Matrix
III) Multiple Sequence Alignment
di
d1
d2
d2
d3
da
d4
d4
IV) PSSM and Profile
V) Reward Redistribution
Profile Model
(TT))
S(n-1)
Tt-1
RG+1 (S(Tr) S(T--1) C
Figure 3: The five steps of Align-RUDDER's reward redistribution. (I) Define events and turn demonstrations into sequences of events. Each block represent event to which the original state is mapped. (II) Construct scoring matrix using event probabilities from demonstrations for diagonal elements and setting off-diagonal to a constant value. (III) Perform an MSA of the demonstrations. (IV) Compute a PSSM. Events with highest column scores are indicated at the top row. (V) Redistribute reward the difference of scores of -euuenesss aligned to the profile.
Therefore random demonstrations with very low rewards have to be generated. LSTM does not generalize well when only these extreme reward cases be observed in the training In contrast, sequence alignment only uses examples that are closely related; that is, they belong to the same category (expert demonstrations).
Reward Redistribution by Sequence Alignment. The new reward redistribution approach consists of five steps, see Fig. 3: (I) Define events turn episodes of state-action sequences into sequences of events. (II) Determine an alignment scoring scheme, so that relevant events are aligned to each other. (III) Perform multiple sequence alignment (MSA) of the demonstrations. (IV) Compute the profile model like PSSM. (V) Redistribute the reward: Each sub-sequence of new episode is aligned to the profile. The redistributed reward R proportional the difference of scores S based on the PSSM given in step (IV), i.c. R&+1 S(T)) S(T--)).
In the following, the five steps of Align-RUDDER's reward redistribution are outlined. For the interested reader, each step is detailed in Sec. A.3 in the appendix. Finally, in Sec. A.7.3 in the appendix, we illustrate these five steps on the example Minecraft.
(I) Defining Events. Instead of states, consider differences of consecutive states to detect change caused by an important event like achieving sub-goal. An event is defined as a cluster of state differences. We similarity-bart based clustering like affinity propagation (AP) (Frey & Dueck, 2007). If states are only enumerated, we suggest to use the "successor representation" (Dayan, 1993) "successor features" (Barreto et al., 2017). We use the demonstrations combined with state-action sequences generated by random policy to construct the successor representation.
sequence of events is obtained from state-action sequence by mapping states its cluster identifier e (the event) and ignoring the actions. Alignment techniques from bioinformatics assume sequences composed of a few events, e.g. 20 events. If there are too many events, good fitting alignments cannot be distinguished from random alignments. This effect is known in bioinformatics as "Inconsistency of Maximum Parsimony" (Felsenstein, 1978).
(II) Determining the Alignment Scoring System. A scoring matrix with entries st,j determines the score for aligning event with j. A priori, we only know that relevant event should be aligned to itself but not to other events. Therefore, we set s; = 1/p; for i j and sij = a for i + j. Here, p; a hyper-parameter, which typically a
the relative frequency of event i the demonstrations. small negative number. This scoring scheme encourages alignment of rare events, for which pt is small. For more details see Appendix Sec. A.3.
(II) Multiple sequence alignment (MSA), An MSA algorithm maximizes the sum of all pairwise scores SMSA Eigiee El Sijjt, in alignment, where &i is the score alignment
4

---

Alignment vs LSTM in 1D key-chest environment. We use ID key-chest environment to show the effectiveness of sequence alignment in a low data regime compared to an LSTM model. The agent has to collect the key and then open the chest to get a positive reward at the last timestep. See Appendix Fig. A.9 for a schematic representation of the environment. As the key-events (important compute the key-event detection rate of Under review as a conference paper at ICLR 2022
column t for aligning the event position & in sequence i to the event at position ij in sequence j. L 2 T is the alignment length, since gaps make the alignment longer than the length of each sequence. We use ClustalW (Thompson et al., 1994) for MSA. MSA constructs guiding tree by agglomerative hierarchical clustering of pairwise alignments between all demonstrations. This guiding tree allows to identify multiple strategies. For more details Appendix Sec. A.3.
(IV) Position-Speeifie Scoring Matrix (PSSM) and MSA profile model. From the alignment, we construct profile model a) volumn-wise event probabilities and b) a PSSM (Stormo et al., 1982). The PSSM is column-wise scoring matrix to align new sequences to the profile model. More details are given in Appendix Sec. A.3.
(V) Reward Redistribution. The reward redistribution is based on the profile model. A sequence
EO.T (ex is event at position t) is aligned to the profile, which gives the score S(T) Ei $1, Here, $1,4, is the alignment score for event ét, at position in the alignment. Alignment gaps are columns to which no event was aligned, which have f = T + 1 with gap penalty #1,7+1 If T c0.t is the prefix sequence of r of length t + 1, then the reward redistribution R(+1 for 0 < t t Tis
T
Be+1 = -S((T)) - S(T--1) C = (((ssa)or) - 9(((s, a)oa-1), RT+2 Go
Σ t=
R (1)
where C' Edemo [Go] Edemo [T -(T)))( with S(T-1) = 0. The original return of
the sequence r is GD = Et= Re+1 and the expectation of the return over demonstrations is Edemo- The constant C' scales R&+1 to the range of Go. RT+2 is the correction of the redistributed reward (Arjona-Medina et al., 2019), with zero expectation for demonstrations: Edemo [RT+2] = O. Since
T Cout and e, = fst, ). we can set g((s, a)oa)) = S(n)C. We ensure strict return equivalence (Arjona-Medina et al., 2019) by Go = ET= Ret1 = Go- The redistributed reward depends only on the past: Re+1 = h((s, a)):).
Sub-tasks. The reward redistribution identifies sub-tasks as alignment positions with high redis- tributed rewards. These sub-tasks are indicated by high scores s in the PSSM Reward redistribution also determines the terminal states of sub-tasks since assigns rewards for solving the sub-tasks. However, reward redistribution and Align-RUDDER cannot guarantee that the redistributed reward is Markov. For redistributed Markov reward, options (Sutton et al., 1999), MAXQ (Dietterich, 2000), or recursive option composition (Silver & Ciosek, 2012) can be used.
Higher Order Markoy Reward Redistributions. Align-RUDDER may lead to higher-order Markov redistribution. Corollary in the appendix states that the optimality criterion from Theorem in Arjona- Medina et al. (2019) also holds for higher-order Markov reward redistributions. expected redistributed higher-order Markov reward is the difference of Q-values. In that case the redistribution is optimal, and there is no delayed reward. Furthermore, the optimal policies are the same for the original problem. This corollary is the motivation for redistributing the reward to the steps in the Q-function. In the Appendix, Corollary 2 states that under a condition, an optimal higher-order reward redistribution can be expressed as the difference of Q-values.
the
EXPERIMENTS
Align-RUDDER compared on three artificial tasks with sparse & delayed rewards and few demon- strations to Behavioral Cloning with Q-learning (BC+Q), Soft Q Imitation Learning (SQIL) (Reddy et al. 2020), RUDDER (LSTM). and Deep Q-learning from Demonstrations (DQ1D) (Hester et al., 2018). GAIL (Ho & Ermon, 2016) failed to solve the two artificial tasks, reported previously for similar tasks (Reddy et al., 2020). Then, we test Align-RUDDER on the complex MineCraft ObtainDi amond task with episodic rewards (Guss et al., 2019b). All experiments use finite time MDPs with y = 1 and episodic reward. More details are in Appendix Sec. A.6.
state-action pairs) in this environment are known,
5

---

Under review as a conference paper at ICLR 2022
events
/.
pinea
creling tehe
wooder pioune
stae prikase
Fnget
chneed
human demonstrations
>
algrment
7
>
7
A
>
>
7
>
reward redatribution
sub-goats
>
Figure 4: Example alignment and reward redistribution for demonstrations of immnddd.. Thresholding the redistributed reward identifies sub-goals.
a reward redistribution model. A key event is detected if the redistributed reward of an important state-action pair is larger than the average redistributed reward in the sequence. We train the reward redistribution models with 2, 5, and 10 training episodes and test on 1000 test episodes, averaged over ten trials. AUUDERR significantly outperforms LSTM (RUDDER) for detecting these key events in all cases, with an average key-event detection rate of 0.96 for sequence alignment vs. 0.46 for the LSTM models overall dataset sizes. See Appendix Fig. A.10 for the detailed results.
Artificial tasks (I) and (II). They are variations of the gridworld rooms example (Sutton et al., 1999), where cells are the MDP states. In our setting, the states do not have to be time-aware for ensuring stationary optimal policies, but the unobserved used-up time introduces random effect. The grid is divided into rooms. The agent's goal is to reach target from an initial state with the fewest steps. It has to cross different rooms, which are connected by doors, except for the first room, which is only connected to the second room by a teleportation portal. The portal is introduced to avoid BC initialization alone, solving the task. It enforces that going to the portal entry cells is learned when they are at positions not observed in demonstrations. At every location, the agent can move up, down, stochastic. An episode ends after T 200 time steps. Suppose
left, right. The state transitions the agent arrives at the target. In that case, it goes into an absorbing state where it stays until T 200 without receiving further rewards. The reward is only given at the end of the episode. Demonstrations are generated by an optimal policy with a 0.2 exploration rate.
The five steps of Aign-RUDDEER'S reward redistribution are: (1) Events are clusters of states obtained by Affinity Propagation using as similarity the successor representation based on demonstrations. (2) The scoring matrix is obtained according to (II), using e 0 and setting all off-diagonal values of the scoring matrix to -1. (3) ClustalW is used for the MSA of the demonstrations with zero gap penalties and no biological options. (4) The MSA supplies a profile model and a PSSM as in (IV). (5)
Sequences generated by the agent are mapped to sequences of events according to (I). The reward is redistributed via differences of profile alignment scores of consecutive sub-sequences according to Eq. (1) using the PSSM. The reward redistribution determines sub-tasks like doors portal arrival. The sub-tasks partition the ttbble into sub-tables that represent a sub-agent. However, we optimize single Q-table in these experiments. Defining sub-tasks has no effect on learning in the tabular case.
All compared methods learn a Q-table and use an e-greedy policy with e = 0.2. The Q-table is initialized since they
initialized by behavioral cloning (BC). The state-action pairs which not visited in the demonstrations get an initialization by drawing a sample from a normal distribution. Align-RUDDER learns the Q-table via RUDDER's 's Q-value estimation (learning method (A) from

---

Under review as a conference paper at ICLR 2022
100000
100000
Algx SETEER E-gh
73000
25000
Eagb:
50000
IM IA (2:75)
IUITEER (US755)
Dplindes to. optinal
17500
SigEL
Episodes S0% optimal
80000
FIgEL
15000
12500
10000
20000
7560
10000
2620
10
100
Demonstration the Foor Rocm-ss) Enviranmett
Demcestralis of the RightR-ooommt) Enviromment
Figure 5: Comparison of Align-RUDDER and other methods on Task (I) (left) and Task (II) (right) with respect to the number of episodes required for learning on different numbers of demonstrations. Results are the average over 100 trials. Align-RUDDER significantly outperforms all other methods.
Sec.2). For BC+Q, RUDDER (LSTM), SQIL, and DQfI Q-table is learned by Q-learning. Hyperparameters are selected via grid search using the same amount of time for each method. For different numbers of demonstrations, performance is measured by the number of episodes to achieve 80% of the average return of the demonstrations. A Wilcoxon rank-sum test determines the significance of performance differences between Align-RUDDER and the other methods.
Task (I) environment is 12x x 12 gridworld with four rooms. The target is in room #4, and the start is in room #1 with 20 portal entry locations. The state contains the portal entry for each episode. Fig. shows the number of episodes required for achieving 80% of the average reward of the demonstrations for different numbers of demonstrations. Results are averaged over 100 trials. Align-RUDDER significantly outperforms all other methods, for & 10 demonstrations (p-values < 100 10).
Task (II) is a 12x24 gridworld with eight rooms: target in room #8, and start in room #1 with 20 portal entry locations. Fig. 5 shows the results with settings as in Task (I). Align- RUDDER significantly outperforms all other methods, for & 10 demonstrations (p-values < 10-19), We also conduct ablation study to study performance of Align-RUDDER, while changing various parameters, like environment stochasticity (See Sec. A.6.4) and number of clusters (See Sec. A.6.5).
MineCraft. We further test RUihERRUDERR on MineCraft Obt i nDi amond task from the MineRL dataset (Guss et al., 2019b). We do not use intermediate rewards given by achieving sub- goals from the challenge, since Align-RUDDER is supposed discover such sub-goals automatically via reward redistribution. We only give a reward for mining the diamond. This requires resource gathering and tool building in hierarchical way. To the best of our knowledge, no pure learning method (sub-goals are also learned) has mined diamond yet (Scheller et al., 2020). The dataset contains demonstrations which are insufficient to directly learn a single policy (117 demonstrations, 67 mined a diamond).
Implementation: (1) A state consists of visual input and an inventory (inel. equip state). Both inputs are normalized to the same information, that is, the same number of components and the same variance. We cluster the differences of consecutive states -Meiina-eediaa et al., 2019). Very large clusters are removed, and small merged, giving 19 clusters corresponding to events, which are characterized by inventory changes. Finally, demonstrations are mapped to sequences of events. (2) The scoring matrix is computed according to (II). (3) The ten shortest demonstrations that obtained diamond are aligned by ClustalW with zero gap penalties and no biological options. (4) The multiple alignments gives profile model and PSSM. (5) The reward redistributed via differences of profile alignment scores of consecutive sub-sequences according to Eq. (1) using the PSSM. Based on the reward redistribution, we define sub-goals. Sub- Sub-goals are identified as profile model positions that obtain an average redistributed reward above a threshold for the demonstrations. Demonstration sub- sequences between sub- sub-goals are considered as demonstrations for the sub-tasks. New sub-sequences generated by the agent are aligned to the profile model to determine whether sub-goal is achieved. The redistributed reward between two sub-goals is given at the end of the sub-sequence, therefore, the sub-tasks also have episodic reward. Fig. 4 shows how sub-goals are identified. Sub-agents are pre- pre-trained on the demonstrations for the sub-tasks using BC, and further trained in the environment using Proximal Policy Optimization (PPO) (Schulman et al., 2018). BC pre-training corresponds to RÜDDER's 's Q-value estimation (learning method (A) from above), while PPO corresponds to RUDDER'S ' PPO training (learning method (B) from above).
7

---

Under review as a conference paper at ICLR 2022
Table I: Maximum item score of methods on the MineCraft task. "Auto": Sub-goals/sub-taske are found automatically. Demonstrations are used for hierarchical reinforcement learning ("HRL"). Methods: Soft-Actor Critic (SAC, Haarnoja et (2018)). DQfD, Meta Learning Shared Hierarchies (MLSH, Frans et al. (2018)), Rainbow (Hessel et al., 2017), PPO, and BC.
Method
Team Name
HRL/Auto
>
Align-RUDDER
Ours
V14
DQID
CDS
VIX
BC
MC RL
V1
CLEAR
I4DS
XIV
Options&PPO
CraftRL
v VIX
BC
UEFDRL
XIv
SAC
TD240
XIV
MLSH
LAIR
VIV
Rainbow
Elytra
XIV
PPO
karolisram
XIV
Our main agent can perform all actions but additionally can execute sub-agents and learns via the redistributed reward. The main agent corresponds and is treated like Manager module (Vezhnevets et al., 2017). The main agent is initialized by executing sub-agents according to the alignment but can deviate from this strategy. When sub-agent successfully completes its task, the main agent executes the next sub-agent according to the alignment. More details can be found in Appendix Sec. 1.7.1. Using only ten demonstrations, Align-RUDDER is able learn to mine diamond. A diamond is obtained in 0.1 % of the cases. With 0.5 success probability for each of the 31 extracted sub-tasks (skilled agents not random agents), the resulting success rate for mining the diamond would be 4.66 x 10 10_ Tab. 1 shows a comparison of methods on the MineCraft MineRL dataset by the maximum item score (Milani et al., 2020). Results are taken from (Milani et al., 2020), in particular from Figure 2, and completed by (Skrynnik et al., 2019; Kanervisto et al., 2020; Scheller et al., 2020). dign-RUDDER was not evaluated during the MineCraft MineRL challenge, but follows the timesteps limit (8 million) imposed by the challenge. Align-RUDDER did not receive the intermediate rewards provided by the challenge that hint at sub-tasks, thus tries to solve a more difficult task. Recently ForgER++ (Skrynnik et al., 2020) the cases. We do not include it in Table as it did not have any limitations on the number of timesteps. Also, ForgER++ generates sub-goals for MineCraft using heuristic, while Align-RUDDER uses redistributed reward to automatically obtain sub-goals.
able to mine diamond in 0.0667 % of
Analysis of MineCraft Agent Behaviour. For each agent and its sub-task, we estimate the success rate and its improvement during fine-tuning by averaging over return of multiple runs (see Fig. 6). For carlier sub-tasks, the agent has a relatively higher sub-task success rate. This also corresponds the agent having access to much more data for earlier sub-tasks. During learning from demonstrations, much less data available for training for later sub-tasks, as not all expert demonstrations achieve the later tasks. During online training using reinforcement learning, an agent has to successfully complete all earlier sub-tasks to generate trajectories for later sub-tasks. This is exponentially difficult. Lack of demonstrations and difficulty of the learned agent to generate data for later sub-tasks leads to degradation of the success rate in MineCraft.
RELATED WORK
Learning from demonstrations has been widely studied over the last 50 years (Billard et al., 2008), An example is imitation learning, which uses supervised techniques when the number of demonstrations is large enough (Michie et al., 1990; Pomerleau, 1991; Michie & Camacho, 1994; Schaal, 1996; Kakade & Langford, 2002). However, policies trained with imitation learning tend to drift away from demonstration trajectories due to a distribution shift (Ross & Bagnell, 2010). This effect can be mitigated (III et al., 2009; Ross & Bagnell, 2010; Ross al., 2011: 1; Judah et al., 2014; Sun et al., 2017;
8

---

Under review as a conference paper at ICLR 2022
1.00
frequency
0.10
exact consensus path human demonstrations
fine tuning
BC
0.01
0.00
consensus
P
Figure 6: Comparing the consensus frequencies between behavioral cloning (BC, orange), where fine-tuning starts, the fine-tuned model (blue), and human demonstrations (green). The plot is in symmetric log scale (symlog in matplotlib). See Appendix Fig. A.19 for mapping of letters to items.
2018). Many approaches demonstrations for initialization, e.g. of policy networks (Taylor et al., 2011; Silver et al., 2016), value function networks (Hester et al., 2017; 2018), both networks (Zhang & Ma, 2018; Nair et al., 2018), or an experience replay buffer (Hosu & Rebedea, 2016). Beyond initialization, demonstrations are used to define constraints (Kim et al., 2013), generate sub-goals (Bysenbach et al., 2019), enforce regularization (Reddy et al., 2020), guide exploration (Subramanian et al., 2016; Jing et al., 2019), or shape rewards (Judah et al., 2014; Brys et al., 2015; Suay et al., 2016). Demonstrations may serve for inverse reinforcement learning (Ng & Russell, 2000; Abbeel & Ng. 2004; Ho & Ermon, 2016), which aims at learning a (non-sparse) reward function that best explains the demonstrations. Learning reward functions requires large number of demonstrations (Syed & Schapire, 2007; Ziebart et al., 2008; Silva et al., 2019). Some approaches rely on few-shot or/and meta learning (Duan al., 2017; Finn et al., 2017; Zhou et al., 2020). However, few-shot and meta learning demand large set of auxiliary tasks prerecorded data. Concluding, most methods that learn from demonstrations rely on the availability of many demonstrations (Khardon, 1999; Lopes al., 2009), in particular, if using deep learning methods (Bengio & Lecun, 2007; I Lakshminarayanan et al., 2016). Some methods can learn on few demonstrations like Soft Q Imitation Learning (SQIL. (Reddy et al., 2020), Generative Adversarial Imitation Learning (GAIL) (Ho & Ermon, 2016), and Deep Q-learning from Demonstrations (DQID) (Hester et al., 2018).
6 DISCUSSION AND CONCLUSION
Discussion. Firstly, reward redistributions do not change the optimal policies (see Theorem 1 in Appendix). Thus, suboptimal reward redistributions due alignment errors or choosing events that are non-essential for reaching the goal might not speed up learning, but also do not change the optimal policies. Secondly, while Align-RUDDS the resulting performance depends on the quality of the alignment model. A low quality alignment model can arise from multiple factors, one of which is having large number (* 20) of distinct events. Clustering can be used to reduce the number of events, which could also lead to a low quality alignment model if too many relevant events are clustered together. While the optimal policy is not changed by poor demonstration alignment, the benefit of employing reward redistribution based on diminishes. Thirdly, the alignment could fail if the demonstrations have different underlying strategies i.e events common in the demonstrations. We assume that the demonstrations follow the same underlying strategy, therefore they are similar to each other and can be aligned. However, if no underlying strategy exists, then identifying those relevant events via alignment, which should receive high redistributed rewards, may fail. In this case, reward is given at sequence end, when the redistributed reward is corrected, which leads to an episodic reward without reducing the delay of the rewards and speeding up learning.
can speed up learning even in complex environments,
Conclusions. We have introduced Align-RUDDER solve highly complex tasks with delayed and sparse reward from few demonstrations. We have shown experimentally that RUDDER outperforms state of the art methods designed for learning from demonstrations in the regime of few demonstrations. On the MineCraft Obt a i amand task, Align-RUDDER is, to the best of our knowledge, the first pure learning method to mine a diamond.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
Impact on ML and related scientific fields. Our research has the potential to positively impact wide variety of fields life due to its general applicability. Most importantly, it has the potential reduce the cost for training and deploying agents in real world applications and therefore enable systems that have not been possible until now.
However, any development in machine learning be applied for good for bad. Our system can be used for medical applications where it can save life but it could be used for malevolent systems. It the society that decides how new technology is employed. However, we as scientist have to inform the society and the decision makers about our technologies. We have to show the limits of our technology, to give ideas of possible applications. to point out possible misuse or erroneous operation of our new technology.
Impact on society. big danger that users rely too much on our new approach and use it without reflecting on the outcomes. For example, in medical treatment decisions doctors may rely on the technical system and push are the responsibility toward the machine: "The machine suggested this treatment, therefore it is not my fault". Another example is self-driving cars where we see that drivers become more careless even if they are supposed to pay attention and keep the hands on the steering wheel. They trust too much in the technology, even if the technology does not justify this trust or is not mature.
Finally, our method can be deployed in companies for job automation. Therefore there is the danger that some people lose their jobs, particularly those whose work is to perform predictable and repetitive tasks. An often used example is the taxi driver who would lose their job because of self-driving cars. The same holds for many jobs in production industry where automation can replace jobs. However all industrialization led to loss of jobs but new jobs have been created.
Consequences of failures the method. Depending on the application area, a failure of this method might be of lesser concern, such as a failed execution of computer program. If our method is employed within a larger automation system, a failure can result in damages such as a car accident. However, this holds for almost all reinforcement learning methods, and usage and testing falls within the responsibility of the application area. We note that in this work, the method was only used in computer game environments.
Leveraging of biases the data and potential discrimination. Our proposed method relies on human demonstrations and thereby human decisions, which are usually strongly biased. As almost all machine learning methods trained on human-influenced data, our method could learn to use and exploit those biases and make similar decisions (Solaiman et al., 2019). Therefore, the responsible use of our method depends on a careful selection of the training data and awareness of the potential biases within those.
REPRODUCIBILITY STATEMENT
Code for experiments on the FourRooms and EightRooms environment is included as supplementary material. The README contains step-by-step instructions to set up environment and run the experiments. We have specified all the training details ex. hyperparameters and how they were chosen in the Appendix (See Section A.6). We trained 100 replicates for each datapoint of the first set of experiments and are shown in Fig. 5. Using the code in the supplementary material, it is quite easy to reproduce our results for these experiments.
We also include code for the experiments done for MineCraft in the supplementary materials. All the preprocessing steps, hyperparameters and other implementation details given in the Appendix (See Section A.7).
We also provide deeper overview of the RUDDER (Arjona-Medina al., 2019) theory in the Appendix (See Section A.2) as it is important for many design choices in Align-RUDDER.
Finally, video showcasing the MineCraft agent is also provided as supplementary material.
10

---

Under review as a conference paper at ICLR 2022
REFERENCES
Abbeel and A. Y. Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the Twenty-First International Conference on Machine Learning, pp. 1, 2004. ISBN 1581 138385,
F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. Lipman. Basic local alignment search tool.
J. Molec. Biol., 214:403-410, 1990.
S. F. Altschul, T. L. Madden, A. A. Schäffer, J. Zhang, Z. Zhang, W. Miller, and D. J. Lipman. Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Research, 25(17):3389-33
1997. doi: 10. 100.1/9////5.17333999
J. A. Arjona-Medina, M. Gillhofer, M. Widrich, T. Unterthiner, and S. Hochreiter. RUDDER: return decomposition for delayed rewards. ArXiv, 2018.
A. Arjona-Medina, M. Gillhofer, M. Widrich, T. Unterthiner, J. Brandstetter, and Hochre- iter. RUDDER: return decomposition for delayed rewards. In Advances in Neural Information Processing Systems 32, pp. 13566-1357,, 2019.
L. Bacon, Harb, and D. Precup. The option-critic architecture. In Proceedings of the Thirty-Fitt AAAI Conference Artificial Intelligence, pp. 1726-1734, AAAI Press, 2017. doi: 10.5555/ 399844...298491.
A. Bairoch and P. Bucher. PROSITE: recent developments. Nucleic acids research, 22(17):3583-9, 1994.
A. Barreto, W. Dabney, R. Munos, J. Hunt, Schaul, H. vanHasselt, and D. Silver. Successor features for transfer in reinforcement learning. In Advances in Neural Information Processing Systems 30, pp. 4055-4065, 2017. ArXiv 1606.05312.
Y. Bengio and Y. Lecun. Large-scale kernel machines, chapter Scaling learning algorithms towards AI. pp. 321-359. MIT Press, 2007.
A. Billard, S. Calinon, R. Dillmann, and S. Schaal. Robot programming by demonstration. In
B. Siciliano and O. Khatib (eds.), Springer Handbook of Robotics, pp. 1371-1394. Springer, 2008.
G. Brockman, Cheung, L. Pettersson, J. Schneider, Schulman, Tang, and Zaremba. Openai gym. ArXiv, 2016.
T. Brys, A. Harutyunyan, H. B. Suay, S. Chernova, M. E. Taylor, and A. Nowé. Reinforcement learning from demonstration through shaping. In Proc. of the 24th Int. Joint Conf. on Artificial Intelligence, (IJCAI'55) pp. 3352-3333333 3358, 2015.
K. Chao and L. Zhang. Sequence comparison: theory and methods. Springer, 2009. ISBN 9781 7781848003200.
J. A. Cock, T. Antao, J. T. Chang, B. A. Chapman, C. Cox, A. Dalke, I. Friedberg, T. Hamelryck, F. Kauff, B. Wilczynski. and M. J. L. de Hoon. Biopython: freely available Python tools for computational molecular biology and bioinformatics. Bioinformatics, 25(11):1422-1423, 03 2009, ISSN 1367-4803. doi: 10. 2..099//oonfommmtic//hp.....
G. Comanici and Precup. Optimal policy switching algorithms reinforcement learning. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), volume 2, pp. 709-714, 2010. doi: 10.1145/1838206, 1838300.
Corpet. Multiple sequence alignment with hierarchical clustering. Nucleic Acids Research, 16(22): 10881-10890, 1988.
C. Daniel, H. vanHoof, J. Peters, and G. Neumann. Probabilistic inference for determining options in reinforcement learning. Machine Learning, 104, 2016. doi: 10.1007/s10994-011 016-5580-x.
Dayan. Improving generalization for temporal difference learning: The successor representation. Neural Computation, 5(4):613-624 1993.
M. O. Dayhoff, Atlas of Protein Sequence and Structure, volume 3. Silver Spring, 1978.
11

---

Under review as a conference paper at ICLR 2022
T. G. Dietterich. Hierarchical reinforcement learning with the MAXQ value function decomposition. Journal of Artificial Intelligence Research, 13(1):227-303, 2000. doi: 10.5555/1622222.122266. arXiv 9905014.
Y. Duan, M. Andrychowicz, B. Stadie, J. Ho, J. Schneider, Sutskever, P. Abbeel, and W. Zaremba. One-shot imitation learning. In Advances in Neural Information Processing Systems 30, pp. 1087- 1098, 2017.
A. Ecoffet, J. Huizinga, J. Lehman, K. O. Stanley, and J. Clune. Go-Explore: A new approach for hard-exploration problems. arXiv, abs/1901. 10995, 2019.
R. C. Edgar. MUSCLE: multiple sequence alignment with high accuracy and high throughput. Nucleic Acids Research, 32($):1722-1797, 2004.
L. Espeholt, H. Soyer, R. Munos, K. Simonyan, Mnih, T. Ward, Y. Doron, V. Firoiu, T. Harley, Dunning, S. Legg, and K. Kavukcuoglu. IMPALA: Scalable distributed Deep-RL with importance weighted actor-learner architectures. In J. Dy and A. Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, 2018. ArXiv: 1802.01561.
B. Eysenbach, R. Salakhutdinov, and S. Levine. Search the replay buffer: Bridging planning and reinforcement learning. In Advances in Neural Information Processing Systems 32, pp. 15220-15231, 2019.
Felsenstein. Cases in which parsimony or compatibility methods will be positively misleading. Systematic Zoology, 27(4):401-410 1978. doi: 10.2307/2412923.
C. Finn, T. Yu, T. Zhang, P. Abbeel, and S. Levine. One-shot visual imitation learning via meta- learning. In 1st Annual Conference on Robot Learning (CoRL), volume 78 of Proceedings of Machine Learning Research, pp. 357-368. PMLR, 2017.
K. Frans, J. Ho, X. Chen, Abbeel, and Schulman. Meta learning shared hicrarchies. In International Conference Learning Representations, 2018. arXiv 1710.09767.
B. J. Frey and D. Dueck. Clustering by passing messages between data points. Science, 315(5814): 972-976, 2007. doi: 10. 10.1126/science. 113800..
O. Gotoh. An improved algorithm for matching biological sequences. Journal of Molecular Biology, 16203))705-708 1982.
W. H. Guss, C. Codel, K. Hofmann, B. Houghton, N. Kuno, S. Milani, S. P. Mohanty, D. P. Liebana, R. Salakhutdinov, N. Topin, M. Veloso, and Wang. The MineRI. competition on sample efficient reinforcement learning using human priors. arXiv, 2019a.
W. H. Guss, B. Houghton, N. Topin, P. Wang, C. Codel, M. Veloso, and Salakhutdinov. MineRL: A large-scale dataset of Minecraft demonstrations. In Proc. of the 28th Int. Joint Conf. on Artificial Intelligence (LJCAI') (9)), 2019b.
T. Haarnoja, A. Zhou, P. Abbeel, and Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In J. Dy and A. Krause (eds.), Proceedings of Machine Learning Research, volume 80, pp. 1861-1870. PMLR, 2018. arXiv 1801.0129
C. R. Harris, K. J. Millman, S. J. van der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, Taylor, Berg, N. Smith, R. Kern, M. Picus, Hoyer, M. H. van Kerkwijk, M. Brett, A. Haldane, J. F. del Río, M. Wiebe, P. Peterson, P. Gééaadd-archhan W. Weckesser, H. Abbasi, C. Gohlke, and E. Oliphant. Array programming with NumPy. Nature, 585(7825):357-362. September 2020. doi: 10.10388/411586-00- 2649-2.
K. Sheppard, T. Reddy,
Henikoff and G. Henikoff. Amino acid substitution matrices from protein blocks. Proceedings of the National Academy of Sciences of the United States of America, 89(22):10915-1099 1992.
M. Hessel, J. Modayil, H. van Hasselt, T. Schaul, G. Ostrovski, W. Dabney, D. Horgan, B. Piot, M. G. Azar, and D. Silver. Rainbow: Combining improvements in deep reinforcement learning. ArXiv, 2017.
12

---

Under review as a conference paper at ICLR 2022
T. Hester, M. Vecerík, O. Pietquin, M. Lanctot, T. Schaul, B. Piot, A. Sendonaris, G. Dulac-Amold, Osband, J. Agapiou, Z. Leibo, and A. Gruslys. Learning from demonstrations for real world reinforcement learning. ArXiv, 2017.
Hester, M. Vecerík, Pietquin, Lanctot, Schaul, B. Piot, D. Horgan, J. Quan, A. Sendonaris, I. Osband, G. Dulac-Amold, J. Agapiou, J. Z. Leibo, and A. Gruslys. Deep q-learnnng from demonstrations. In The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18). Association for the Advancement of Artificial Intelligence, 2018
D. Hirschberg. A linear space algorithm for computing maximal common subsequences. Commu- nications of the ACM, 18(6))341-343 1975. doi: 10. 145/360825.360886
Ho and S. Ermon. Generative adversarial imitation learning. Advances in Neural Information Processing Systems 29, pp. 4565-4573, 2016.
Hochreiter. Untersuchungen zu dynamischen neuronalen Netzen. Master's thesis, Technische Universität München, 1991.
Hochreiter and Schmidhuber. Long short-term memory. Technical Report FKI-207-95, Fakultät für Informatik, Technische Universität München, 1995.
S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural Comput., 98):1735--780. 1997a.
S. Hochreiter and J. Schmidhuber. LSTM can solve hard long time lag problems. In M. C. Mozer, M. I. Jordan, and T. Petsche (eds.), Advances in Neural Information Processing Systems 9, pp. 473-479, Cambridge, MA, 1997b. MIT Press.
M. Holzleitner, L. Gruber, J. A. Arjona-Medina, J. Brandstetter, and S. Hochreiter. Convergence proof for actor-critic methods applied to PPO and RUDDER. arXiv, 2020.
A. Hosu and T. Rebedea. Playing Atari games with deep reinforcement learning and human checkpoint replay. ArXiv, 2016.
D. Hunter. Matplotlib: A 2d graphics environment. Computing Science Engineering, 9(3): 90-95, 2007. doi: 10. 109/MCSE.2007.55
H. Daumé III, J. Langford, and D. Marcu. Search-based structured prediction, 2009.
M. Jing, X. Ma, W. Huang, F. Sun, C. Yang, B. Fang, and H. Liu. Reinforcement learning from imperfect demonstrations under soft expert guidance. ArXiv, abs/1911.07101 2019.
K. Judah, A. P. Fern, T. G. Dietterich, and P. Adepalli. Active imitation learning: Formal and practical reductions to i.i.d. learning. J. Mach. Learn. Res., 15(1):3925-394) 3963, 2014. ISSN 1532-4435.
Kakade and Langford. Approximately optimal approximate reinforcement learning. In 19th International Conference Machine Learning (ICML), pp. 267-274, 2002. 2002.
A. Kanervisto, J. Karttunen, and V. Hautamäki. Playing Minecraft with behavioural cloning. In J. Escalante and R. Hadsell (eds.), Proceedings of Machine Learning Research (PMLR), volume 123, pp. 56-66. PMLR, 2020.
S. Karlin and S. F. Altschul. Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes. Proceedings of the National Academy of Sciences of the United States of America, 8766):224--2268 1990. doi: 10.1073/pnas.88 6..224
S. Karlin, A. Dembo, and Kawabata. Statistical composition of high-scoring segments from molecular sequences. Ann. Statist., 18(2)5571-881, 1990. doi: 10. (0.1221/aoss 1176376616.
R. Khardon. Learning to take actions. Machine Learning. 35(1):57-90, 1999.
B. Kim, A. Farahmand, J. Pineau, and D. Precup. Learning from limited demonstrations. In Advances in Neural Information Processing Systems 26, 2013.
13

---

Under review as a conference paper at ICLR 2022
T. D. Kulkarni, K. Narasimhan, A. Saeedi, and Josh J. Tenenbaum. Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Gareett (eds.), Advances in Neural Information Processing Systems, volume 29, pp. 3675-3683. Curran Associates, Inc., 2016.
A. S. Lakshminarayanan, S. Ozair, and Y. Bengio. Reinforcement learning with few expert demon- strations. In NIPS Workshop on Deep Learning for Action and Interaction, 2016.
K. Y. Levy and N. Shimkin. Unified inter and intra options learning using policy gradient methods. In S. Sanner and M. Hutter (eds.), Recent Advances in Reinforcement Learning, pp. 153-164. Springer Berlin Heidelberg, 2012. doi: 10. 00.10000978---0 3--62---699-----
M. Lopes, F. S. Melo, and L., Montesano. Active learning for reward estimation in inverse rein- forcement learning. In European Conference on Machine Learning and Knowledge Discovery in Databases (ECML,PKDD), volume 5782 of Lecture Notes in Computer Science, pp. 46.
Springer, 2009.
J. Luoma, S. Ruutu, A. W. King, and H. Tikkanen. Time delays, competitive interdependence, and firm performance. Strategic Management Journal, 38(3):506-525, 2017. doi: 10.1002/smj.2512
M. Machado, C. Rosenbaum, X. Guo, M. Liu, G. Tesauro, and M. Campbell. Eigenoption discovery through the deep successor representation. arXiv, abs/1 1.. 11089, 2017.
D. J. Mankowitz, T. A. Mann, and S. Mannor. Adaptive skills adaptive partitions (ASAP). In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29, pp. 1588-1596. Curran Associates, Inc., 2016.
J. A. Mccammon and P. G. Wolynes. Highly specific protein sequence motifss for genome analysis. Computational Biomolecular Science, 95(May):5865-587) 1998.
D. Michie and R. Camacho. Building Symbolic Representations of Intuitive Real-Time Skills from Performance Data, pp. 385-418. Oxford University Press, Inc., USA, 1994. ISBN 01 0198538502.
D. Michie, M. Bain, and Hayes-Michie. Cognitive models from subcognitive skills, pp. 71- 99. Control, Robotics and Sensors. Institution of Engineering and Technology, 1990. doi: 10. 10.1049/PBCH044F_.c.
Milani, N. Topin, B. Houghton, W. H. Guss, S. P. Mohanty, K Nakata, O. Vinyals, and S. Kuno. Retrospective analysis of the 2019 MineRL competition on sample efficient reinforcement learning. arXiv, 00tp/2220000002,,,0 2020.
B. Morgenstern. DIALIGN: Multiple DNA and protein sequence alignment at BiBiServ. Nucleic Acids Research, 23:W33-6. 2004.
A. Nair, B. McGrew, M. Andrychowicz, W. Zaremba, and P. Abbeel. Overcoming exploration in reinforcement learning with demonstrations. In 2018 JEEE International Conference on Robotics and Automation, ICRA 2018, Brishane, Australia, May 21-25, 2018, pp. 6292-6299, IEEE, 2018.
B. Needleman and D. Wunsch. A general method applicable the search for similarities in the amino acid sequence of two proteins, Journal of Molecular Biology, 48(3):443-453, 1970.
A. Y. Ng and S. J. Russell. Algorithms for inverse reinforcement learning. In Proceedings of the Seventeenth International Conference on Machine Learning, pp. 663-670, 2000. ISBN 1558607072.
C. Notredame, D. G. Higgins, and J. Heringa. T-coffee: a novel method for fast and accurate multiple sequence alignment. Journal of Molecular Biology, 302(1): 2005-2220 2000.
A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf. E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang. J. Bai, and S. Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Be Bucc E. Fox, and R. Gameett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024-802 Curran Associates, Inc., 2019.
14

---

Under review as a conference paper at ICLR 2022
D. A. Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neural Comput. 3(1):88 97, 1991. ISSN 0899-7667.
M. L. Puterman. Markov Decision Processes. John Wiley & Sons, Inc., 2nd edition, 2005. ISBN 978-0-471-72782-88
H. Rahmandad, N. Repenning, and J. Sterman. Effects of feedback delay learning. System Dynamics Review, 25(4))309-338, 2009. doi: 10.1002/sdr.427.
R. Ramesh, M. Tomar, and B. Ravindran. Successor options: An option discovery framework for reinforcement learning. In Proc. of the 28th Int. Joint Conf. on Artificial Intelligence (IJCAI'19), 2019.
S. Reddy, A. D. Dragan, and S. Levine. SQIL: imitation learning via regularized behavioral cloning. In Eighth International Conference on Learning Representations (ICLR), 2020. arXiv 1905. 1008.
D. Rolnick, A. Abuja, Schwarz, P. Lillicrap. and G. Wayne. Experience replay for continual learning. In Advances in Neural Information Processing Systems 32, pp. 348-358, 2019.
S. Ross and D. Bagnell. Efficient reductions for imitation learning. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pp. 661-668, 2010.
S. Ross, G. Gordon, and D. Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pp. 627-635, 2011.
S. Schaal. Learning from demonstration. In Proceedings of the 9th International Conference on Neural Information Processing Systems (9))) pp. 1040-1046, Cambridge, MA, USA, 1996. MIT Press.
C. Scheller, Y. Schraner, and M. Vogel. Sample efficient reinforcement learning through learning from demonstrations in Minecraft. In H. Escalante and R. Hadsell (eds.), Proceedings of Machine Learning Research (PMLR), volume 123, pp. 67-76. PMLR, 2020.
J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. ArXiv, 2018.
Sievers, A. Wilm, D. Dineen, T. J. Gibson, K. Karplus, W. Li, R. Lopez, H. McWilliam, M. Rem- mert, J. Soding, J. D. Thompson, and D. G. Higgins. Fast, scalable generation of high-quality protein multiple sequence alignments using Clustal Omega. Molecular Systems Biology, 7(1): 539- 2014.
Jr. A. R. Silva, V. Grassi, and D. F. Wolf. Continuous deep maximum entropy inverse reinforcement learning using online POMDP. In 19th International Conference on Advanced Robotics (ICAR), pp. 382-387, IEEE, 2019.
D. Silver and Ciosek. Compositional planning using optimal option models. In Proceedings of the 29th International Conference on Machine Learning (ICML), volume 2, 2012. arXiv 1206.6473.
D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. P. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7777):484 489, 2016. doi: 10. 10.1088/nature6699
D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, I. Sifre, D. Ku- maran, Graepel, T. P. Lillicrap, K. Simonyan, and D. Hassabis. Mastering Chess and Shogi by self-play with a general reinforcement learning algorithm. ArXiv, 2017.
A. Skrynnik, A. Staroverov, E. Aitygulov, K. Aksenov, V. Davydov, and A. I. Panoy. Hierarchical deep genetwork with forgetting from imperfect demonstrations in Minecraft. arXiv, abss/1122 1912.08644 2019.
15

---

Under review as a conference paper at ICLR 2022
A. Skrynnik, A. Staroverov, E. Aitygulov, K. Aksenov, V. Davydov, and A. I. Panov. Forgetful experience replay in hierarchical reinforcement learning from demonstrations, 2020.
T. F. Smith and M. S. Waterman. Identification of common molecular subsequences. Journal of Molecular Biology, 147()):195-177, 1981.
I. Solaiman, M.Brundage, J. Clark, A. Askell, A. Herbert-Voss, J. Wu, A. Radford, and J. Wang.
Release strategies and the social impacts of language models. arXiv, abs/ (ete11108..00000 2019.
M. Stolle and D. Precup. Learning options in reinforcement learning. In Lecture Notes in Computer Science, volume 2371, pp. 2 212-223, 2002. doi: 10.100773-540-4562--8.
G. D. Stormo, T. D. Schneider, L. Gold, and A. Ehrenfeucht. Use of the 'Perceptron' algorithm to distinguish translational initiation sites in E. coli. Nucleic Acids Research, 10(9):2997-3011 1982.
H. B. Suay, T. Brys, M. E. Taylor, and S. Chernova. Learning from demonstration for shaping through inverse reinforcement learning. In Proceedings of the 2016 International Conference Autonomous Agents & Multiagent Systems, pp. 429-437, ACM, 2016.
K. Subramanian, C. L. Isbell, and A. L. Thomaz. Exploration from demonstration for interactive reinforcement learning. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, pp. 447 456,,,66222 2016.
W. Sun, Venkatraman, G. Gordon, B. Boots, and J. A. Bagnell, Deeply AggreVaTeDD Dif- ferentiable imitation learning for sequential prediction. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 3309-3316 PMLR, 2017.
W. Sun, J.A. Bagnell, and B. Boots. Truncated horizon policy search: Combining reinforcement learning & imitation learning. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018
R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 2 edition, 2018
R. S. Sutton, D. Precup, and S. P. Singh. Between MDPs and Semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112(1-2):181-111 1999.
U. Syed and E. Schapire. A game-theoretic approach to apprenticeship learning. Advances in Neural Information Processing Systems 20, 2007.
M. E. Taylor, H. B. Suay, and S. Chernova. Integrating reinforcement learning with human demonstra- tions of varying ability. In 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), Taipei, Taiwan, May 2-6, 2011, Volume 1-3, pp. 617-624, 2011.
D. Thompson, D. G. Higgins, and T. J. Gibson. CLUSTAL W: improving the sensitivity of pro- gressive multiple sequence alignment through sequence weighting, position-specifie gap penalties and weight matrix choice. Nucleic Acids Research, 22(22):4673-4660, 1994.
A. S. Vezhnevets, S. Osindero, T. Schaul, N. Heess, M. Jaderberg, D. Silver, and K. Kavukcuoglu. FeUdal networks for hierarchical reinforcement learning. arXiv, abs//1003.0161, 2017.
L. Wang and T. Jiang. On the Complexity of Multiple Sequence Alignment. Journal of Computational Biology, 144):337-348, 1994.
J. H. Watkins. Learning from Delayed Rewards. PhD thesis, King's College, 1989.
X. Zhang and H. Ma. Pretraining deep actor-critic reinforcement learning algorithms with expert
demonstrations. ArXiv, 0bs//880.11n 10459, 2018
A. Zhou, E. Jang, D. Kappler, A. Herzog, M. Khansari, P. Wohlhart, Y. Bai, M. Kalakrishnan, S. Levine, and C. Finn. Watch, try, learn: Meta-learning from demonstrations and rewards. In International Conference Learning Representations, 2020.
16

---

Under review as a conference paper at ICLR 2022
B. D. Ziebart, A. Maas, J. A. Bagnell, and A. K. Dey. Maximum entropy inverse reinforcement learning. In Proceedings of the 23rd National Conference on Artificial Intelligence Volume 3, AAAI'08, pp. 4433-1438. AAAI Press, 2008. ISBN 9781577353683.
X. Zuo. mazelab: A customizable framework create maze and gridworld environments. https: //github. com/ zuox zuoxingdong wwaeen/////aaaaaaeeee maze lb. 2018.
17

---

Under review as a conference paper at ICLR 2022
A
APPENDIX
CONTENTS OF THE APPENDIX
A.1 Introduction to the Appendix
20
A.2 Review Reward Redistribution
20
A.3
The Five Steps of Align-RUDDER' s Reward Redistribution
25
A.4
Sequence Alignment
27
A.5
Extended Related Work
28
A.6
Artificial Task Experiments
29
A.6.1
Hyperparameter Selection
29
A.6.2
Figures
29
A.6.3
Artificial Task p-values
30
A.6.4
Stochastic Environments
31
A.6.5
Changing number of Clusters
32
A.6.6
Key-Event Detection
A.7
Minecraft Experiments
A.7.1
MineCraft
A.7.2
Related Work and Steps Towards a General Agent
A.7.3
The Five Steps of Align- Demonstrated on Minecraft
36
A.7.4
Implementation our Algorithm for Minecraft
38
A.7.5
Policy and Value Network Architecture
39
A.7.6 Imitation Learning Sub-Task Agents
40
A.7.7 Reinforcement Learning on Sub-Tasi Task Agents
A.8 Reproducing the Artificial Task Results
A.9 Software Libraries
42
A.10 Compute
LIST OF FIGURES
A.2 Clusters formed in the FourRooms and EightRooms environment
29
A.3 Clusters formed in the FourRooms and EightRooms environment
30
A.4 Clusters formed in the FourRooms and EightRooms environment
30
A.5 FourRooms and EightRooms environments
31
A.6 Reward redistribution for the FourRooms and FightRooms environments.
18

---

Under review as a conference paper at ICLR 2022
A.11 Step (I): Define events and map demonstrations into sequences of events. First, extract the sequence of states from human demonstrations, transform images into feature vectors using pre-trained network and transform them into sequence of consecutive state deltas (concatenating image feature vectors and inventory states). We cluster the resulting state deltas and remove clusters with large number of members and merge smaller clusters. In the case of demonstrations for the Obtain- Diamond task in Minecraft the resulting clusters correspond obtaining specific resources and items required to solve the task. Then we map the demonstrations to sequences of events.
36
A.12 Step (II): Construct scoring matrix using event probabilities from demonstrations for diagonal elements and setting off-diagonal the diagonal position are proportional to the inverse of the event frequencies. Thus, aligning rare events has higher score. Darker colors signify higher score values.
constant value. The scores in
36
A.13 Step (III) Perform multipe sequence alignment (MSA) of the demonstrations. The MSA algorithm maximizes the pairwise sum of scores all alignments. The score of an alignment at each position is given by the scoring matrix. As the off-diagonal entries are negative, the algorithm will always try to align an event to itself, while giving preference to events which give higher scores.
37
A.14 Step (IV) Compute position-speciffi scoring matrix (PSSM). This matrix can computed using the MSA (Step (III) and the scoring matrix (Step (II)). Every column entry is for a position from the MSA. The score at a position (column) and for an the frequency of that event that position in the MSA. For
event (row) depends example, the event in the last position is present in all the sequences, and thus gets high score the last position. But it is absent in the remaining position, and thus gets score of zero elsewhere.
37
A.15 Step (V) new sequence aligned step by step the profile model using the PSSM, resulting in an alignment score for each sub-sequence. The redistributed reward is then proportional to the difference of scores of subsequent alignments.
37
A.16 Conceptual overview of our MineRL agent
38
A.17 Conceptual architecture of ALigERRUDDER MineRL policy and value networks
39
A.18 Discretization and interpolation of camera angles
40
A.19 Mapping of clusters letters
40
A.20 Trajectory replay given by an exemplary consensus
19

---

Under review as a conference paper at ICLR 2022
A.1 INTRODUCTION TO THE APPENDIX
This is the appendix to the paper "Align-RUDDES" Learning from few Demonstrations by Reward Redistribution". The appendix aims at supporting the main document and provides more detailed information about the implementation of our method for different tasks. The content of this document summarized as follows:
Section A.3 describes the five steps of Align- RUDDER's ' reward redistribution in more detail. In particular, the scoring systems are described in more detail. Section A.4 provides brief overview of sequence alignment methods and the hyperparameters used in our experiments. Section A.6 provides figures and tables to support the results of the experiments in Artificial Tasks (I) and (II). Section A.7 explains in detail the experiments conducted in the Minecraft ObtainDiamond task.
A.2 REVIEW REWARD REDISTRIBUTION
Reward redistribution and return decomposition are concepts introduced in RUDDER but also apply to Align-RUDDER as a variant RUDDER. Reward redistribution based on return decomposition climinates or at least mitigates delays of rewards while preserving the same optimal policies. Align- Align-RUDDER is justified by the theory of return decomposition and reward redistribution when using multiple sequence alignment for constructing a reward redistribution model. In this section, review the concepts of return decomposition and reward redistribution.
Preliminaries. We consider finite MDP defined by the 5-tuple p (8. A, p.7) where the state space S and the action space A are sets of finite states s and actions a and R the set of bounded rewards For given time step the corresponding random variables
S., A, and Re+1. Furthermore, P has transition-reward distributions p(S++1 = 8', R1+1 = r S, = 8, A, = a), and discount factor y E (0, 1]. which we keep at y A Markov policy π (a 8) is a probability of an action given a state s. We consider MDPs with finite time horizon or with an absorbing state. The discounted return of a sequence of length T at time / is G. Tf 7 Re+E+I. As usual, the Q-function == for a given policy π is (s. a) = E, [G, S. = s, A, = a]. Ez s.a] is the expectation of I, where the random variable is sequence of states, actions, and rewards that is generated with transition reward distribution p. policy т,, and starting at (s, a). The goal is to find an optimal policy x² argmax, F,, [Go] maximizing the expected return at t 0. We assume that the states time-aware (time i can be extracted from each state) in order to assure stationary optimal policies. According to Proposition 4.4.3 in (Puterman, 2005), a deterministic optimal policy π exists.
Definitions. A sequence-Markor decision process (SDP) is defined as a decision process that has Markov transition probabilities but a reward probability that is not required to be Markov. Two SDPs P and P with different reward probabilities are return-equivalnnt if they have the same expected return at f = 0 for each policy x, and strictly eeturn-equivalent if they additionally have the same expected return for every episode. Since for every π the expected return at f 0 is the same, SDPs have the same optimal policies. A reward redistribution is procedure that for given sequence of a delayed reward SDP P_ redistributes the realization or expectation of its return Go along the sequence. This yields a new SDP P with A as random variable for the redistributed reward and the same optimal policies as P:
neturn-equivalle
Theorem (Arjona- Medina et al. (2019)). Both the SDP P with delayed reward R441 and the SDP P with redistributed reward Ret1 have the same optimal policies.
Proof. The proof can be found in (Arjona- et al., 2019).
The delay of rewards is captured by the expected future rewards s(m, t 1) at time (t 1). is
defined as k(m, t - 1) ;= Ex 1> =0 Re+1+7 7 s;-1, 11, that is, at time (t - 1) the expected sum of future rewards from R441 R4+1+m but not the immediate reward R. A reward redistribution which is equivalent to
is defined to be optimal, if <(T
1,1) = 0 for O & & T - TT
E, [R(+1] a:-1, St, ar] q" az)
Theorem 2 (Arjona-Medina et al. (2019)). We assume a delayed reward MDP P, with episodic reward. A new SDP P obtained by a second order Markov reward redistribution, which ensures that P is return-quuivalent to P. For specific n. the following two statements are equivalent:
20

---

Under review as a conference paper at ICLR 2022
(I) R(T -t -- 1,t) = 0, i.e. the reward redistribution is optimal, (II) Ex [Re+1] st-1; 1,-1, St, at] q"' (st, (s)) (8-- a1-1) An optimal reward redistribution fulfills for & t. S and & m E m(m,l 1 =0.
Proof. The proof can be found in (Arjona-Medina et al., 2019).
This theorem shows that an optimal reward redistribution relies on steps q" (&t, az) T (st-1, 0t-1) of the Q-function. Identifying the largest steps in the Q-function detects the largest rewards that have to be redistributed, which makes the largest progress towards obtaining an optimal reward redistribution.
Corollary 1 (Higher order Markov reward redistribution optimality conditions). We assume delayed reward MDP P. with episodic reward. A new SDP P is obtained by higher order Markov reward redistribution. The reward redistribution ensures that P is return-qquivalent to P. for specific
B [ 8t-1, 1,-1, S1, at] q (St, at) -T (1t-1, 00-11)
holds, then the higher order reward redistribution Re+1 is optimal, that is, k(T - 1,t) 1,t)=0. =0
Proof. The proof is just PART (II) of the proof of Theorem (Arjona-Medina et al., 2019). We repeat it here for completeness.
We assume that
Ex Re41
81-1, ac-1, St, ail = he = (=(( - -4- 0--)),,
(4)
where we abbreviate the expected Re-1 by h4:
Es [Re+1
st-1, -6-,, az] h,
(5)
The expectations Fyz 8t-1, 4-1] like Fxr
RT++ 8t-1, 0t-1 are expectations over all episodes
that contain the state-action pair (s--1, (8--1.0(1) at time 1- The expectations F,, [- 8 a1-1; 8t, 4z] like E,, [Rr+1 |t-1, a1-1, de are expectations over all episodes that contain the state-action pairs (s,-1, 11-1) time - 1 and (st, a.) time t. The Q-values are defined
("1, = Ex
Retb+1 | S2, = Ex RT+1 1 82, at)
(6)
(s), F
Re+++1
82,
which are expectations over all trajectories that contain (st; ae) time t. Since P is Markov, for g" only the suffix trajectories beginning at (st, az) enter the expectation.
The definition of k(m, t 1) for < E,, 1ETh R st-1, 1.. We have to proof x<T - t - 1,t) =
T and & m
< T was x(m,t 1)
First, we consider the original MDP P has episodic reward, have F(st-1, 0:-1) E Ri 8t-1,0-1 0 for 1 < 1 < T. Therefore, we obtain:
and 1 < t < T, therefore x(0,t 1) Ex [R++1 0t-1, Since
(" ac-1) = F(s1-1, + Σ E(ss as 01-1, (s6.
(8)
St.
Σ .c.
p(3e, ar a--1) (s),
21

---

Under review as a conference paper at ICLR 2022
Using this equation obtain for 1 & T:
x(0, t 1) Ex [R++1 91-1,00-11
Ex 19" (s) - q" (11111, a--1 81-1,
Σ p(st, 0t) 0--1, (s), qºt 0--1)
Re
07 (8t-1, as-1) Eolos,a 01-1, ( (8-11,
Se,
q"h (s a1-1)
9"' (s = 0.
Next, we consider the expectation of Σ Ru+1+ for 1 <t T and 1 & m & T - (for 0)
m
x(m, t 1- 1)
F
Ret1+7 8t-1, 04-1
(10)
m
Fix
(T (8r+1, 9"' (8-+1-1, 81-1 at-1
Ex
(T
(8e4m; (14m) 7 (St-1, ut-1 8t- 1,-1, 0t-1
Ex
E
Ro+1 814m, a1mm Σ
01-1
-=I++m
Em
Ex
Σ Ri+1
a=-1 18- 0--1
0--1,0111
T=t-1
Ex RT+1 91-1,
Ex RT+1 91-1,
0.
We used that Re+1 0 for < T. For the particualr cases and =
we have
< 1, 0.
(II)
That is exactly what we wanted to proof.
Corollary explicitly states that the optimality criterion ensures an optimal reward redistribution even if the reward redistribution is higher order Markov. For RUgD-RUDDER we may obtain a higher order Markov reward redistribution due to profile alignment the sub-sequences.
Corollary (Higher order Markov reward redistribution optimality representation). We assume delayed reward MDP P. with episodic reward and that a new SDP is obtained by higher order Markov reward redistribution. The reward redistribution ensures that P is strictly return-equivalen to P. We assume that the reward redistribuition is optimal, that is, R(T t 1,t) 0. If the condition
E
Σ
R4424
St, a1
Ex
Σ
Re+t+ So, ao. ..,, a4
(12)
holds, then
Ex [R441 8t-1, 11, az)
7"d (81,
9"d (st-1,
(13)
Proof.
By and large, the proof is PART (I) of the proof of Theorem 2 in (Arjona-Medinn et al., 2019).
We repeat it here for completeness.
22

---

Under review as a conference paper at ICLR 2022
We assume that the reward redistribution is optimal, that is,
K(T 1 1,6) 0.
(14)
We abbreviate the expected R4+1 by hy:
Ex Re+1 St-1, St, ail h4
(15)
In (Arjona-Medina et al., 2019) Lemma A4 is as follows.
Lemma 1. Two strictly return-quiivalent SDPs P and have the same expected return for each start state-action sub-sequence (8o, 0t), 0 & T:
F Go 80, ao....... St, 04
= E [Go 80, ao....... .ag.....8. St, at)
(16)
The assumptions of Lemma hold for for the delayed reward MDP P and the redistributed reward SDP P. since reward redistribution ensures strictly ceur-eqquialentt SDPs. Therefore for given state-action sub-sequence (so, Ap. St, a.), 0 & & T::
Ex Go so. ao. ,,, st
= E2 [Go 50, .o...., St, ar]
(17)
with Go = Ef= R1+1 and G. RT+1- The Markov property of the MDP P ensures that the future reward from + on is independent of the past sub-sequence 8g, ao. $1-1, a:-1i
T
R4117
St, at
E
Σ
Ret1+ Su, ag.... St. ag
(18)
According to Eq. (12), the future reward from + 2 on is independent of the past sub-sequence So. Go. ... St-1, O1-1;
E
R422+
st, = Ex
R442+7 Su, ag.... st, St,
(19)
-=0
23

---

Under review as a conference paper at ICLR 2022
Using these properties obtain
q- (5 0z) Ex
Re+1+r 8e, ar
(20)
T
Eg
R++1+T
80, ao...., Sc, at
-r=
E
R so, Cu,..., St, at
Ex
s0: a0 St, Ry+1
T==
E
Go
80, 00.
.0..............................
St.
E
Go
so. ao
82, ael
E,
Rr++ 180 00.
................................
T-
Ex
Re+24T 80, ao....,... St,
+
Σ hr
t-1
Eg
Re+2+7 St
+ Σ hr
<(T -
1,t) + Σ
hy
T=0
ht
7=0
We used the optimality condition
T-1-1 Σ
<(T -t 1,t) = Ex
R4224
8t, 0t
= 0.
(21)
follows that
Ex [e+1 8t-1, ac-1, Sr, ail = be = ( - x"t (8)-
(22)
This is exactly what we wanted to proof.
This corollary shows that optimal reward redistributions can be expressed as difference of Q-values Eq. (12) holds. Eg. (12) states that the past can be averaged out. However, there may exist optimal reward redistributions for which Eq. (12) does not hold.
If the reward redistribution is optimal, the Q-values of are given by (st, = q oe)
di (st) and therefore P. and P have the same advantage function:
Theorem (Arjona-Meding
al. (2019)). the reward redistribution optimal, then the Q-values of the SDP P are (8t, a1) = r(st, 0t) and
ddt (st, a4) = (st, a4) Eg.-1ar-1 [qTh (st-1, 0-11 |8]] (st, 16 (st)
(23)
The SDP P and the original MDP P have the same advantage function.
Proof. The proof can be found in (Arjona-Medina al., 2019).
24

---

Under review as a conference paper at ICLR 2022
Defining Events
II) Scoring Matrix
III) Multiple Sequence Alignment
di
d1
d2
d2
d3
da
d4
d4
IV) PSSM and Profile
V) Reward Redistribution
Profile Model
(TT))
Tt-1
S(n-1)
RG+1 (S(T)) S(T--1) C
The five steps of Align-RUDDER's reward redistribution. (I) shows several demon- strations, where each demonstration is composed of sequence of events. Events are defined as difference of state-actions or clusters thereof. Step (II) depicts a scoring matrix, which we construct using event probabilities from demonstrations. With demonstrations and the scoring matrix we then perform MSA in step (III). In step (IV) to construct the profile model and PSSM from the alignment. These are then used align new sequence the model in step (V), one timestep at a time. The differences in alignment score are then used to redistribute reward for this new sequence.
Figure A.1:
For an optimal reward redistribution only the expectation of the immediate reward r(st, a:) E,, [R++1] 8t, a,] must be estimated. This considerably simplifies learning.
Learning methods according to Arjona-Medina et al. (2019). The redistributed reward serves as reward for subsequent learning method, which can be Type A, B, and as deseribed Arjona- Medina et al. (2019). Type A methods estimate the Q-values. They can be estimated directly according to Eq. (23) assuming an optimal redistribution (Type variant i). Q-values can be corrected for non-optimal reward redistribution by additionally estimating λ (Type A variant ii). Q-value estimation can use eligibility traces (Type A variant iii). Type B methods use the redistributed rewards for policy gradients like Proximal Policy Optimization (PPO) Schulman et al. (2018). Type C methods use TD learning like Q-learning Watkins (1989), where immediate and future reward must be drawn together as typically done. For all these learning methods, demonstrations can be used for initialization (e.g. experience replay buffer) or pre-training (e.g. policy network with behavioral cloning). Recently, the convergence of RUDDER learning methods has been proven under commonly used assumptions (Holzleitner et al., 2020).
Non-optimal reward redistribution and Hlgh-RUDDER. According Theorem non-optimal reward redistributions do not change the optimal policies. The value x(T - - 1. t) measures the remaining delayed reward. The smaller ς is, the faster the learning process. For Monte Carlo (MC) estimates, smaller к reduces the variance of the future rewards, and, therefore the variance of the estimation. For temporal difference (TD) estimates, smaller reduces the amount of information that has to flow back. Align- RUDDER dramatically reduces the amount of delayed rewards by identifying key events via multiple sequence alignment, to which reward is redistributed. For an episodic MDP, a reward that is redistributed to time É reduces all <(m, 7) with t < T by the expectation of the reward. Therefore, in most cases Align-RUDDER makes k-values much smaller.
A.3 THE FIVE STEPS OF ALIGN-RUDDER'S REWARD REDISTRIBUTION
The new reward redistribution approach consists of five steps, see Fig. A.1: (1) Define events to turn episodes of state-action sequences into sequences of events. (II) Determine an alignment scoring scheme, so that relevant events are aligned to each other. (III) Perform multiple sequence alignment (MSA) of the demonstrations. (IV) Compute the profile model and the PSSM. (V) Redistribute the reward: Each sub-sen sequence т of new episode is aligned to the profile. The redistributed reward R,+1 is proportional to the difference of scores S based on the PSSM given in step (IV), i..
R441 S(n)) S(Tr-1).
25

---

Under review as a conference paper at ICLR 2022
(I) Defining Events. Alignment techniques assume that sequences consist of few symbols, e.g- about 20 symbols, the events. It is crucial to keep the number of events small in order to increase the difference between random alignment and an alignment of demonstrations. If there many events, then two demonstrations might have few events that can be matched, which cannot be well distinguished from random alignments. This effect is known in bioinformatics "Inconsistency of Maximum Parsimony" (Felsenstein, 1978). The events can be the original state-action pairs, clusters thereof, or other representations of state-action pairs, e.g. indicating changes of inventory, health, energy, skills etc. In general, we define events as cluster of states or statenactions. A sequence of events obtained from a state-action sequence by substituting states or state acte-actiins by their cluster identifier. In order to cluster states, a similarity measure between them is required. We suggest to use the "successor representation" (Dayan, 1993) of the states, which gives similarity matrix based on how connected two states are given policy. Successor representation have been used before (Machado et al., 2017; Ramesh ct al., 2019) to obtain important events, for option learning. For computing the successor representation, we use the demonstrations combined with state-action sequences generated by a random policy. For high dimensional state spaces "successor features" (Barreto et al., 2017) can be used. We use Aimilarity-based clustering methods like affinity propagation (AP) (Frey & Dueck, 2007). For AP the similarity matrix does not have to be symmetric and the number of clusters need not be known. State action pairs (s, a) are mapped events e.
(II) Determining the Alignment Scoring System. Alignment algorithms distinguish similar sequences from dissimilar sequences using& scoring system. A scoring matrix $ has entries &t, that give the score for aligning event i with j. The MSA score SMSA of multiple sequence alignment is the sum of all pairwise scores: SMSA = ES.,,ee -
where Fi,t means that event wi,e is at position / for sequence т; ei...r in the alignment, analog for zz,t and the sequence Tj Cj.0:T, and L the alignment length. Note that T. 2 T and Ni, # Ci, since gaps are present in the alignment. In the alignment, events should have the same probability of being aligned as they would have if we know the strategy and align demonstrations accordingly. The theory of high scoring segments gives a scoring scheme with these alignment probabilities (Karlin & Altschul, 1990; Karlin et al., 1990; Altschul et al., 1990). Event is observed with probability p; in the demonstrations, therefore a random alignment aligns event with j with probability p.Py. An alignment algorithm maximizes the MSA score SMSA and, thereby, aligns events and j with probability Qi for demonstrations. High values of 4if means that the MSA often aligns events and j in the demonstrations using the scoring matrix $ with entries j.-- According to Theorem 2 and Equation [3] in Karlin & Altschul ( (1990), asymptotically with the sequence length, we have s = In(ge// ( ))pp where X is the unique positive root of nnn Ei=1,j=1 PiP, exp())s.,) = 1 (Equation [4] in Karlin & Altschul (1990)).
We can now choose a desired probability Qij and then compute the scoring matrix $ with entries sij. High values of qı should indicate relevant events for the strategy. A priori, we only know that a relevant event should be aligned to itself, while we do not know which events are relevant. Therefore we set q3j to large values for every = j and to low values for * j. Coneretely, we set q₁ p; e for i =j j and 4i = c/(n 1) for i * j. where n is the number of different possible events. Events with smaller p; receive a higher score s,,, when aligned to themselves since this self-match less often observed when randomly matching events (p.P, is the probability of a random self-match). Any prior knowledge about events should be incorporated into Gij.
(II) Multiple sequence alignment (MSA). MSA first produces pairwise alignments between all demonstrations. Then, a guiding tree (agglomerative hicrarchical clustering) is produced via hierarchical clustering sequences, according to their pairwise alignment scores. Demonstrations which follow the same strategy appear in the same cluster in the guiding tree. Each cluster is aligned separately via MSA to address different strategies. However, if there is not a cluster of demonstrations, then the alignment will fail. MSA methods like ClustalW (Thompson et al., 1994) or MUSCLE (Edgar, 2004) can be used.
(IV) Position-Specific Scoring Matrix (PSSM) and Profile. From the final alignment, we construct a) an MSA profile (column-wise event frequencies ys.)) and b) PSSM (Stormo al., 1982) which is used for aligning new sequences to the profile of the MSA. To compute the PSSM (column- wise wise scores s s,,)). we apply Theorem 2 and Equation [3] in Karlin& & Altschul ( (1990). Event is observed with probability pa in the data. For each position i in the alignment, we compute qi,,, which indicates The PSSM is s,,, in(4.t/p.) //////////// where X; the single (Equation [1] in Karlin & Altschul (1990)). If we
the frequency of event at position t.
unique positive root of Di Pi exp(\st.))
26

---

Under review as a conference paper at ICLR 2022
align sequence that follows the underlying strategy (a new demonstration) to the profile model, we would see that event is aligned to position t in the profile with probability qr,c-
(V) Reward Redistribution. The reward redistribution is based on the profile model. A sequence
T eo.7 (eg is event at position é) is aligned to the profile, which gives the score S(7) - E S2,,t- Here, $1.e is the alignment score for event and v2 is the event of T at position / in the alignment. L the profile length, where L 2 T and 24 A et. because of gaps in the alignment. T. = Co. the prefix sequence of r of length + 1, then the reward redistribution R for 0 & t T'is
T Ro+1- = (S(T)) S(Tr-1)) g((s, a)o.)) - a((ssa))=-1)) RT+2 = Go
Σ
Re+1.
t=0
(24)
where C' Edemo
Go] / Edemo En S(T,) S(--1) and Go Et=o Ret1 is the original
return of the sequence and S(Tr-1) = 0. Edamo is the expectation over demonstrations, and C scales R&+1 to the range of Gg. RT+2 is the correction of the redistributed reward (Arjona-Medina et al., 2019), with zero expectation for demonstrations: Edemo [r+2] = Since Tı = Eoxt and set g((s, a()a) S(r:)C. We ensure strict return equivalence, since Go- Ei=0 Re+1 = Go. The redistributed reward depends only on the past, that is, R&+1 l(((,, a)):)). For computational efficiency, the alignment of T can be extended to one for like exact matches are extended to high-scoring sequence pairs with the BLAST algorithm (Altschul et al., 1990; 1997).
e, = f(( a.),
Sub-tasks. The reward redistribution identifies sub-tasks, which are alignment positions with high redistributed reward. also determines the terminal states and automatically assigns reward for solving the sub-tasks. However, reward redistribution and Align- RUDDER cannot guarantee that the reward is Markov. For redistributed reward that is Markov, the option framework (Sutton et al., 1999), the MAXQ framework (Dietterich, 2000), recursive composition of option models (Silver & Ciosek, 2012) can be used as subsequent approaches to hierarchical reinforcement learning.
A.4 SEQUENCE ALIGNMENT
In bioinformatics, sequence alignment identifies regions of significant similarity among different biological sequences to establish evolutionary relationships between those sequences. In 1970, Needleman and Wunsch proposed a global alignment method based on dynamic programming (Needleman & Wunsch, 1970). This approach ensures the best possible alignment given substitution matrix, such as PAM (Dayhoff, 1978) or BLOSUM(Henikoff & Henikoff, 1992), and other parameters to penalize gaps in the alignment. The method of Needlemann and Wunsch is of (mm) complexity both in memory and time, which could be prohibitive in long sequences like genomes. An optimization of this method by Hirschberg (1975), reduces memory O(m + n), but still requires (mm) time.
Later, Smith and Waterman developed a local alignment method for sequences (Smith & Waterman, 1981). It is variation of Needleman and Wunseh's method, keeping the substitution matrix and the gap-scoring scheme but setting cells in the similarity matrix with negative scores to zero The complexity for this algorithm is of Mn) Osamu Gotoh published an optimization of this method, running in (mm) runtime (Gotoh, 1982).
The main difference between both methods is the following:
The global alignment method by Needleman and Wunsch aligns the sequences fixing the first and the last position both sequences. It attempts to align every symbol in the sequence, allowing some gaps, but the main purpose is to get a global alignment. This is especially useful when the two sequences are highly similar. For instance:
ATCCGATCGACCGGCTTAAATACCCC CGAGCATC APAGCATC-ACTTICT-- CAT.CCCAACTTTTTAAAAAACCTTTTTEEET GATCGACCTTAG
As an alternative to global methods, the local method of Smith and Waterman aligns the sequences with higher degree of freedom, allowing the alignment to start end with gaps.
27

---

Under review as a conference paper at ICLR 2022
This is extremely useful when the two sequences substantially dissimilar in general but suspected of having a highly related sub region.
ATC A-C----Bn -CC-=-CAAACACCCTTTC-TCCACCCCCCTO
A.4.0.1 Multiple Sequence Alignment algorithms. The sequence alignment algorithms by Needleman and Wunsch and Smith and Waterman are limited to aligning two sequences. The approaches for generalizing these algorithms to multiple sequences can be classified into four cate- gories:
Exact methods (Wang & Jiang, 1994).
Progressive methods: ClustalW (Thompson et al., 1994), Clustal Omega (Sievers et al., 2014), T-Coffee (Notredame et al., 2000).
Iterative and search algorithms: DIALIGN (Morgenstern, 2004), MultiAlign (Corpet, 1988).
Local methods: eMOTIF (Mccammon & Wolynes, 1998), PROSITE (Bairoch & Bucher,
1994).
For more details, visit Sequence Comparison: Theory and methods (Chao & Zhang, 2009).
our experiments, we use ClustalW from Biopython (Cock et al., 2009) with the following parame- ters:
clustalw2 -ALIGN -CLDSTERLNGGUUGGAAAA -NEGATIVE
-- T-INFILE= -OUTFILF=
PPMMTTTIX= -PWGAPOPEN=0 -PWGAPEXT=0
MATRIX= -GAPOPEN-O -GAPEXT-O -CASE-UPPER
" NOPGAP -NOHGAP -MAXDIV-0 -ENDGAPS -NOVGAP "
"-NEWTREE= (outputtree) -TYPE-PROTEIN -OUTPUT=GDE
where the PMMATRIX and MATRIX are computed according to step (II) in Sec. 3 of the main paper.
A.5 EXTENDED RELATED WORK
Align-RU Rign-RUDDER allows to identify goals and sub-tasks, therefore is related to hierarchical reinforcement learning (HRL) approaches like the option framework (Sutton et al., 1999), the MAXQ framework (Dietterich, 2000), or the recursive composition of option models (Silver Ciosek, 2012). However, these methods do not address the problem of finding good options, good sub-goals, or good sub-tasks. Methods to learn good options have been proposed. Frequently observed states in solutions are chosen as targets (Stolle Precup, 2002). Gradient-based approaches improving the termination function for options (Comanici & Precup, 2010; Mankowitz et al., 2016). Policy gradient optimized a unified policy consisting of intra-option policies, option termination conditions, and an option selection policy (Levy & Shimkin, 2012). Parametrized options are learned by treating the termination functions as hidden variables and using expectation maximization (Daniel et al., 2016). Intrinsic rewards are used to learn the policies within options, and extrinsic rewards to learn the policy over options (Kulkarni et al., 2016). Options have been jointly learned with an associated policy using the policy gradient theorem for options (Bacon et al., 2017). A slow time-scale manager module learns sub-goals that are achieved by fast time-scale worker (Vezhnevets et al., 2017).
Next, relate RUDDER imitation learning and trajectory matching. Imitation learning aims at learning a behavior close to the data generating policy by matching the trajectories of single demonstrations. In contrast, RRiDDRRUDDER does not try match single trajectories but identifies relevant events that are shared among successful demonstrations. In complex tasks like MineCraft trajectory matching fails, since large state spaces do not allow to match one of the few demonstrations, However, relevant events can still be matched as they appear in most demonstrations, therefore RUDDR excels such complex tasks.
28

---

Under review as a conference paper at ICLR 2022
A.6 ARTIFICIAL TASK EXPERIMENTS
This section provides additional information that supports the results reported in the main paper for Artificial Tasks (I) and (II).
A.6.1 HYPERPARAMETER SELECTION
For (BC)+Q-Leaninn and Align- RUDDER, performed a grid search to select the learning rate from the following values [0.1, 0.05, 0.01]. We used 20 different seeds for each value and each number of demonstrations and then selected the setting with the highest success for all number of demonstrations. The final learning rate for (BC)+Q-Learning and DQfD 0.01 and for Align- RUDDER it is 0.1.
For DQfD, we set the experience buffer size to 30, 000 and the number of experiences sampled at every timestep 10. The DQfD loss weights are set 0.01, 0.01 and 1.0 for the Q-learning loss term, n-step loss term and the expert loss respectively during pre-training. During online learning, we change the loss terms 1.0, 1.0 and 0.01 for the Q-learning loss term, n-step loss term and the expert loss term. This was necessary to enable faster learning for DQfD. The expert action margin is 0.8.
For successor representation, we use learning rate of 0.1 and gamma of 0.99. We update the successor table multiple times using the same transition (state, action, next state) from the demonstration.
For affinity propagation, we use a damping factor 0.5 and set the maximum number of iterations to 1000. Furthermore, if we obtain more than 15 clusters, then we combine clusters based on the similarity of the cluster centers.
A.6.2 FIGURES
Figure A.5 shows sample trajectories in the FourRooms and EightRooms environment, with the initial and target positions marked in red and green respectively. Figure A.2 shows the clusters after performing clustering with Affinity Propagation using the successor representation with 25 demonstrations and an environment with 1% stochasticity on the transitions. Different colors indicate different clusters. Figures A.3 and A.4 show clusters for different environment settings. Figure A.3 shows clusters when using 10 demonstrations and for Figure A.4 environments with 5% stochastictiy on transitions was used. Figure A.6 shows the reward redistribution for the given example trajectories in the FourRooms and EightRooms environments.
Figure A.2: Examples of clusters formed in the FourRooms (left) and EightRooms (right) environment with 1% stochasticity on the transitions after performing clustering with Affinity Propagation using successor representation with demonstrations. Different colors represent different clusters.
29

---

Under review as a conference paper at ICLR 2022
Figure A.3: Examples of clusters formed the FourRooms (left) and FightRooms (right) environment with 1% stochasticity the transitions after performing clustering with Affinity Propagation using the successor representation with 10 demonstrations. Different colors represent different clusters.
Figure A.4: Examples of clusters formed the FourRooms (left) and FightRooms (right) environment with 5% stochasticity the transitions after performing clustering with Affinity Propagation using the successor representation with 25 demonstrations. Diffcrent colors represent different clusters.
A.6.3 ARTIFCIAL TASK P-VALUES
Tables A.I and A.2 show the p-values obtained by performing Mann-Whitney-U test between Aign-RUDDER and BC+Q-Learning and DQfD respectively.
2
5
10
50
100
Align RUDDER vs. BC+Q-Leam
8.8e-31
2.8e-30
1.1e-09
3.5e-01
1.6e-01
Align-RUDDER vs. SQIL
3.6e-39
5.2e-39
3.1e-37
8.6e-36
1.9e-36
Align-RUDDER DQMD
2.7e-29
4.3e-30
1.3e-32
1.0e+00
1.0e+00
Aligo-RUDDER vs. RUDDER (LSTM)
1.9e-31
1.9e-27
3.7e-20
1.7e-15
7.3e-01
Table A.l: p-values for Artificial Task (D), FourRooms, obtained by performing Mann- Whitney-U U test.
30

---

Under review as a conference paper at ICLR 2022
Figure A.5: Exemplary trajectories in the FourRooms (left) and EightRooms (right) environments.
Initial position is indicated in red, the portal between the first and second room in yellow and the goal in green.
Figure A.6: Reward redistribution for the above trajectories the FourRooms (left) and EightRooms (right) environments.
A.6.4 STOCHASTIC ENVIRONMENTS
Figure A.7 shows results for the FourRooms environment with different levels of stochasticity (5%, 10%, 15%, 25% and 40%) on the transitions. Figure A.8 shows results for the EightRooms environment with different levels of stochasticity (5% and 10%) on the transitions.
2
5
10
50
100
Align RUDDER vs. BC+Q-Lean
4.5e-20
1.3e-34
4.9e-25
3.7e-01
6.1e-01
Align-RUDDER vs. SQIL
1.8e-37
2.8e-39
1.9e-36
1.7e-35
1.9e-37
Align-RUDDER vs. DQMD
1.2e-08
8.9e-20
5.6e-31
1.0e+00
1.0e+00
Aligo-RUDDER vs. RUDDER (LSTM)
1.2e-29
1.3e-34
3.9e-31
8.7e-22
1.0e-18
Table A.2: p-values for Artificial Task (II), EightRooms, obtained by performing Mann-Wii Honn-Whiteey-U test.
31

---

Under review as a conference paper at ICLR 2022
101000
Alga KITCOR
10:0000
Alga SETERR
23000
Eagb
25000
E-g
DUITEER (USTMM)
17500
SigEL
17500
FIgEL
15000
15000
12500
12500
10000
10000
7560
7500
Splindes to
2620
Eptinde
2000
10
Demonstratone the Foor Roomeel Environmett
Demonstration the Four Roum--22 Favironment
100000
100030
13000
50000
25000
BC + queerai
Digo
5X000
75900
BC - Quesses
ram
Epiindds to 3276 apeliall
17500
17500
13500
13500
10000
10000
1000
5000
Epiendes
50
100
10
50
100
Demonstration the 3
Demonstration the Fommoome-d
Alg-SCTCGR
25000
540.0
Eigit
BUTDER (ESTAO
17500
RIGIT
13000
12800
Eptocdes 8025
10000
7500
Demonstation the Fiou R ciniinammet
Figure A.7: Comparison of Align- RUgD-R and other methods on Task (I) (FourRooms) with increasing levels of stochasticity (from top left to bottom: 5%, 10%, 15%, 25% and 40%). Results are the average over 50 trials.
300000
75000
BC Quienrie
Alg-RCBOOR
75000
BC Queeeess
60000
DQD
50000
DQD
20000
Episcdes 80F% optinal
20000
20000
20000
Ejiocdes 807%
10000
10000
10
50
100
2
10
50
100
Demoustcations of the EightHooous-vi Enviromennt
Demonstrations of the Hightioooms x2 Envizonmentt
Figure A.8: Comparison of Align-RUDDER and other methods on Task (II) (EightRooms) with increasing levels of stochasticity (from top left to bottom: 5%, 10%). Results are the average over 50 trials.
A.6.5 CHANGING NUMBER OF CLUSTERS
We use Affinity Propagation for clustering, and do not set the number of clusters. Although, set the max number of clusters allowed. If Affinity propagation results in more clusters, they are combined and reduced to the maximum clusters allowed. This is necessary due the limitations of the underlying alignment library we are using. For the experiments on FourRooms and EightRooms in the main paper, fix the max number of clusters to 15.
We conduct an experimental study on how changing the max number clusters changes the perfor- mance of Align-RUDDER on the FourRooms environment. The results are in table A.3.
32

---

Under review as a conference paper at ICLR 2022
Max. # of Clusters
2
10
50
100
2
5782.1
2378
7624
18
14
5
4462.1
1277
7892
19
14
8
985
1417
1372
19
14
10
985
1417
1372
19
14
12
985
1417
1372
19
14
15
985
1417
1372
19
Table A.3: Results for different numbers of clusters for the FourRooms artificial task are shown in the table. It shows the number episodes required to reach 80% optimal return, using demonstrations given in column headers. These results averaged over 10 seeds. For the results report in the paper we set the maximum number of clusters to 15, the results show that even when reducing the number of clusters 8, results stay similar. We only worse performance for when only allowing 2 or 5 clusters.
k
S
C
Figure A.9: The agent has collect the key and then open the chest, get a positive reward the last timestep. The environment episode runs for fixed 32 timesteps.
A.6.6 KEY-EVENT DETECTION
ID key-chest environment. We use ID key-chest environment to show the effectiveness of sequence aligmment low data regime compared an LSTM model. The agent has to collect the key and then open the chest, to get a positive reward at the last timestep. See Appendix Fig. A.9 for schematic representation of the environment. As the key-events (important state-action pairs) this environment are known we can compute the key-event detection rate of reward redistribution model. key event detected if the redistributed reward of an important state-action pair is larger than the average redistributed reward in the sequence. We train the reward redistribution models with 2, and 10 training episodes and test on 1000 test episodes, averaged over trials. Align-RUDDER significantly outperforms LSTM (RUDDER) for detecting these key events in all cases, with an average key-event detection rate of 0.96 for sequence alignment vs. 0.46 for the LSTM models over all dataset sizes. See Appendix Fig. A.10 for the detailed results.
33

---

Under review as a conference paper at ICLR 2022
1.0
Detection
0.7
0.6
0.5
0.4
Align- RUDDER RUDDER (LSTM)
0.0
Number Demonstrations
Figure 1010: We use Align- and RUDDER to detect key events for Key-Chest environment, where we already know which state-action pairs important for return. A key event is detected if the redistributed reward at an important state-action is larger than the average redistributed reward in the sequence. We LSTM (RUDDER) for detecting these key events.
1000 test episodes and average over 10 trials. Align-RUDDER outperforms
A.7 MINECRAFT EXPERIMENTS
In this section explain in detail the implementation of Align-RUDDER for solving the task ObtainDiamond.
A.7.1 MINECRAFT
We show that our approach can be applied complex tasks by evaluating on the MineRL Minecraft dataset (Guss et al., 2019b). This dataset provides large collection of demonstrations from human players solving six different tasks in sandbox game MineCraft. addition to the human demonstrations the MineRL dataset also provides OpenAI-Gym wrapper for MineCraft. The dataset includes demonstrations for the following tasks:
navigating target location following a compass.
collecting wood by chopping trees,
obtaining item by collecting resources and crafting, and
free play "survival" where the player is free to choose his own goal.
The demonstrations include the video showing the players' view (without user interface). the players' inventory at every time step and the actions performed by the player. We focus the third task of obtaining a target item, namely a diamond. This task very challenging as it is necessary to obtain several different resources and tools and has been the focus of challenge (Guss et 2019a) at NeurIPS' 19. By the end of this challenge no entry was able to obtain the diamond.
We show that method is well suited for solving the task of obtaining the diamond, which can be decomposed into sub-tasks by reward redistribution after aligning successful demonstrations.
A.7.2 RELATED WORK AND STEPS TOWARDS GENERAL AGENT
In the following, we review two approaches Skrynnik et (2019); Scheller al. (2020) where more details are available and compare them with our approach.
Skrynnik et al. (2019) address the problem with TD based hierarchical Deep Q-Network (DQN) and by utilizing the hierarchical structure of expert trajectories by extracting sequences of meta-actions and sub-goals. This approach allowed them to achieve the 1st place in the official NeurlPS' 19 approaches have in
MineRL challenge (Skrynnik et al., 2019). In terms of pre-processing, common that both rely on frame skipping and action space discretization. However, they reduce the action space to ten distinct joint environment actions (e.g. move camera & attack) and treat inventory actions separately by executing a sequence of semantic actions. We aim taking a next step towards more general agent by introducing action space preserving the agent's full freedom of action in
34

---

Under review as a conference paper at ICLR 2022
the environment (more details are provided below). This allows us avoid the distinction between item (environment) and semantic (inventory) agents and to train identically structured agents in the same fashion regardless of facing a mining, crafting, placing smelting sub-task. Skrynnik et al. (2019) extract a sub-task chain by separately examining each expert trajectory and by considering the time of appearance of items in the inventory in chronological order. For agent training their approach follows heuristic where they distinguish between collecting the item log and all remaining items. The log-agent is trained by starting with the TreeChop expert trajectories and then gradually injecting trajectories collected from interactions with the environment into the DQN's replay buffer. For the remaining items they rely on the expert data of learning. Given our proposed sequence alignment and reward redistribution methodology we are able to avoid this shift in training paradigm and to leverage all available training data (ObtainDiamond, PbtainIronPickat and TreeChop) at the same time. In short, we collect all expert trajectories in one pool, perform sequence alignment yielding a common diamond consensus along with the corresponding reward redistribution and the respective sub-task sequences. Given this restructuring of the problem into local sub-problent with redistributed reward all sub-task agents are then trained in the same fashion (e.g. imitation learning followed by RL-based fine- fine-tuning). Reward redistribution guarantees that the optimal policies are preserved (Arjona-Medina et al., 2019).
and imitation
Scheller et al. (2020) achieved the 3rd place on the official leader board following different line of research and addressed the problem with a single end-to-end off-policy IMPALA (Espeholt et al., 2018) actor-critic agent, again utilizing experience replay to incorporate the expert data (Scheller et al., 2020). To prevent catastrophic forgetting of the behavior for later, less frequent sub-tasks they introduce value clipping and apply CLEAR (Rolnick al., 2019) both, policy and value networks. Treating the entire problem as a whole is already the main distinguishable feature compared to our method. To deal with long trajectories they rely on a trainable special form of frame skipping where the agent also has to predict how many frames to skip in each situation. This helps to reduce the effective length (step count) of the respective expert trajectories. In contrast to the approach of (Scheller et al., 2020) rely constant frame skip irrespective of the states and actions we facing. Finally, there are also several common features including:
1. a supervised BC pre-training stage prior to RL fine-tuning, 2. separate networks for policy and value function,
3. independent action heads on top of sub-sequence LSTM,
4. presenting the inventory state in certain form to the agent and
5. applying a dalue-function-bur -uroo-- prior to RL fine-tuning fine-tuning.
35

---

Under review as a conference paper at ICLR 2022
A.7.3 THE FIVE STEPS OF LIGN-RUDDERR DEMONSTRATED ON MINECRAFT
In this subsection, we give an example of the five steps of Align-RUDDER using demonstrations from the MineRL ObtainDiamond task. Figures A.11 to A.15 illustrate these steps.
planks
Clustering
FOR OFF
A
mapped demonstiaiion
pop
Figure A.II: Step (I): Define events and map demonstrations into sequences of events. First, we extract the sequence of states from human demonstrations, transform images into feature vectors using a pre-trained network and transform them into a sequence of consecutive state deltas (concatenating image feature vectors and inventory states). We cluster the resulting state deltas and remove clusters with a large number of members and merge smaller clusters. In the case of demonstrations for the task in Minecraft the resulting clusters correspond to obtaining specifie resources and items required to solve the task. Then we map the demonstrations to sequences of events.
event frequencies
10,000
15,000
8,000
>
500
4,000
400
Scoring Metrix
70
7
350
250
150
75
Figure A.12: Step (II): Construct scoring matrix using event probabilities from demonstrations for diagonal elements and setting off-diagonal to constant value. The scores in the diagonal position are proportional to the inverse the event frequencies. Thus, aligning rare events has higher score. Darker colors signify higher score values.
36

---

Under review as a conference paper at ICLR 2022
human demronttratoon
0009
/ >
/
/
/
/
aigreest
71 T
2 $
A
Figure A.13: Step (III) Perform multipe sequence alignment (MSA) of the demonstrations. The MSA algorithm maximizes the pairwise sum of scores of all alignments. The score of an alignment at each position is given by the scoring matrix. As the off-diagonal entries are negative, the algorithm will always try to align an event to itself, while giving preference to events which give higher scores.
Figure A.14: Step (IV) Compute a position-specingg scoring matrix (PSSM). This matrix can be computed using the MSA (Step (III) and the scoring matrix (Step (II).. Every column entry is for position from the MSA. The score at a position (column) and for an event (row) depends on the frequency of that event at that position in the MSA. For example, the event in the last position is present in all the sequences, and thus gets high score at the last position. But it is absent in the remaining position, and thus gets a score of zero elsewhere
ConsenNus
align NEW Soquenos
21
Figure A.15: Step (V) A new sequence is aligned step by step the profile model using the PSSM, resulting in an alignment score for each sub-sequence. The redistributed reward is then proportional to the difference of scores of subsequent alignments.
37

---

Under review as a conference paper at ICLR 2022
Agent
Sequence Algoment Reward Redlstmbutton
Erajectory Replay Resetting
Computation
Profile (PSSM)
Consensus Sequence (Strategy)
Trajectory Replay
Sub-task
Reploy Actions
Algmment
Hine Tune Task
(Emaronment & Reward Specificotion)
(Il & Iily Multiple Sequence Alignment
Pre-training
Fine-tunnng
Sequences of Events
Redistribution and Sequence Extraction
Pre-troined Weights
RL Fine Tuning
Expert Trajettories
(i) Event Sequence Extraction
Trajectories
Supervised Pre-training (BC)
Fine turie Sub-tosk Weights
Figure A.16: Conceptual overview of our MineRL agent.
A.7.4 IMPLEMENTATION OF OUR ALGORITHM FOR MINECRAFT
The architecture of the training pipeline incorporates three learning stages:
sequence alignment and reward redistribution
learning from demonstrations via behavioral cloning (pre-training) and
model fine-tuning with reinforcement learning.
Figure A. shows a conceptual overview of all components.
Sequence alignment and reward redistribution. First, we extract the sequence of states from human demonstrations, transform images into feature vectors using standard pre-trained network and transform them into a sequence of consecutive state deltas (concatenating image feature vectors and inventory states). A pre-trained network can be model trained for image classification or an auto-encoder model trained on images. In our case, we used an auto-encoder model trained on the MineRL obtain dataset. We cluster the resulting state deltas and remove clusters with large number of members and merged smaller clusters. This results in 19 events and we map the demonstrations to sequences of events. These events correspond to inventory changes. For each human demonstration we get a sequence of events which we map to letters from the amino acid code, resulting in sequence of letters. In Fig. A.19 we show all events with their assigned letter encoding that we defined for the Minecraft environment.
We then calculate scoring matrix according to step (II) in Sec. 3 in the main document. Then, we perform multiple sequence alignment to align sequences of events of the top N demonstrations, where shorter demonstrations we denote as the consensus. In order to redistribute the reward, we use the PSSM model and assign the respective reward. Reward redistribution allows the sub-goal definition i.e. positions where the reward redistribution is larger than a threshold or positions where the reward redistribution has certain value. In our implementation sub-goals are obtained by applying threshold the reward redistribution. The main agent is initialized by executing sub-agents according to the alignment. Figure shows how sub-goals are identified using reward redistribution.
ranked higher. This results in sequence of common events which
Learning from demonstrations via behavioral cloning. We extract demonstrations for each individual sub-task the form of sub-sequences taken from all demonstrations. For each sub-task we train an individual sub-agent via behavioral cloning.
Model fine-tuning with reinforcement learning. We fine-tune the agent in the environment using PPO (Schulman et al., 2018). During fine-tuning with PPO, an agent receives reward if it manages to reach its sub-goal.
38

---

Under review as a conference paper at ICLR 2022
Convolutional Block (Conv BN RRLUU)
LSTM
Value Head
R
Network Input
Inventory
independent Action Hends
Binary
(- Bernoulls)
48
Camera
- R
(- Multi Cateo-cat)))
Equip
(- Categorical)
48 piee!
Convolutional Block (Comv BN RelU)
LSTM
Place
R²
(- Categorical)
Cokr-encoded equpped Iem
Craft
+ R
(- Categorical)
Nearby
(- Categorical)
Nearty Smelt
R (- Categorical)
Figure A.17: Conceptual architecture of our MineRL policy and value networks.
To evaluate the performance of an agent for its current sub-goal, we average the return over multiple roul- This gives us good estimate of the success rate and if trained models have improved during fine tuning or not. In Fig. 6, we plot the overall success rate of all models evaluated sequentially from start to end.
In order to shorten the training time of our agent, we use trajectory replay and state resetting, similar to the idea proposed in (Ecoffet et al., 2019), allowing us to train sub-task agents in parallel. This is not necessary for the behavioral cloning stage, since here can independently train agents according to the extracted sub-goals. However, fine-tuning a sub-task agent with reinforcement learning requires agents for all previous sub-tasks. To fine-tune agents for all sub-tasks, record successful experiences (states, actions, rewards) for earlier goals and use them to reset the environment where subsequent agent can start its training. In Fig. A.20, illustrate trajectory replay given by an exemplary consensus.
A.7.5 POLICY AND VALUE NETWORK ARCHITECTURE
Figure A.17 shows conceptual overview of the policy and value networks used in our MineRL experiments. The networks are structured as two separate convolutional encoders with an LSTM layer before the respective output layer, without sharing any model parameters.
The input to the model is the sequence of the 32 most recent frames, which are pre- reepproesssed in the following way: first, we add the currently equipped item as a color-coded border around each RGB frame. Next, the frames are augmented with an inventory status bar representing all 18 available inventory items (each inventory item is drawn as an item-square consisting of 3 x pixels to the frame). Depending
the item count the respective square is drawn with a linearly interpolated gray-scale ranging from white (no item at all) to black (item count >> 95). The count of 95 is the 75-quantile of the total amount of collected cobblestones and dirt derived from the inventory of all expert trajectories. Intuitively, this count should be related to the current depth (level) where an agent currently is or at least has been throughout the episode. In the last pre-processing step the frames are resized from 64 x 64 to 48 x 48 pixels and divided by 255 resulting in an input value range between zero and one.
The first network stage consists of four batch-normalized convolution layers with ReLU activation functions. The layers are structured as follows: Conv-Layer-1 (16 feature maps, kernel size stride 2, zero padding 1), Conv-Layer-2 (32 feature maps, kernel size 4, stride 2, zero padding 1), Conv-Layer-3 (64 feature maps, kernel size 3, stride 2), and Conv-Layer-d (32 feature maps, kernel size 3, stride 2). The flattened latent representation (E 32222288 of the convolution stage is further processed with an LSTM layer with 256 units. Given this recurrent representation we only keep the last time step (e.g. the prediction for the most recent frame).
The value head is a single linear layer without non-linearity predicting the state-value for the most recent state. For action prediction, two types of output heads used depending on the underlying action distribution. The binary action head represents the actions attack, back, forwardd jump, left, right, sneak and sprint which can be executed concurrently and therefore modeled based
39

---

Under review as a conference paper at ICLR 2022
1.00
Probabiiity
0.75
0.50
0.25
Discretization Bins
True Camera Angle
0.00
30
-20
110
10
20
30
Camera Angle
Figure A.18: Discretization and interpolation of camera angles.
[dir]
[tron ond]
(cratting table]
pickaxe)
(log]
(iron ingot)
(Jumaca)
W (iro
[stone]
ppaanks]
[wooden axc]
Bron pickaxe]
[oobblestone]
V [stlak]
[wooden pickawe]
(diamond ore]
[coo]]
[arch]
[stone axo)
Figure A.19: Mapping of clusters to letters.
Bernoulli distribution. Since only one item can be equipped, placed, or crafted at a time these actions are modeled with a categorical distribution. The equip head selects from none, air, wooden-axe, wooden-pickaxe stone-axe, stone- iron-axe and iron-pickaxe. The place head selects from none, dirt, stone, cobblestone, crafting-tablee furle, furnace and torch. The craft head selects from none, torch, stick, planks and crafting-table Items which have to be crafted nearby are none, wooden-axe wooden-pin pickexx, stone-axe, stone-pickaxe, iron-axe, iron-pickaxe and furnace. Finally, items which smelted nearby none, iron-ingon inn-t and coal. For predicting the camera angles (up/down well as left/right) we introduce a custom action space outlined in Figure 1.18. This space discretizes the possible camera angles into 11 distinct bins for both orientations leading the 22 output neurons of the camera action head. Each bin holds the probability for sampling the corresponding angle as a camera action, since in most of the cases the true camera angle lies in between two such bins. We share the bin selection probability by linear interpolation with respect to the distance of the neighboring bin centers to true camera angle. This way we are able to train the model with standard categorical cross-entropy during behavioral cloning and sample actions from this categorical distribution during exploration and agent deployment.
A.7.6 IMITATION LEARNING OF SUB-TASK AGENTS
Given the sub-sequences of expert data separated by task and the network architectures described above we perform imitation learning via behavioral cloning (BC) on the expert demonstrations. All sub-task policy networks are trained with cross-entropy loss on the respective action distributions using stochastic gradient decent with a learning rate of 0.01 and momentum of 0.9. Mini-batches of size 256 are sampled uniformly from the set of sub-task sequences. As we have the MineRL simulator available during training evaluate the performance of the model by deploying in the environment every 10 training epochs. Once training over 300 epochs is complete
are able include all sub-sequences in the training set and
select the model checkpoint based the total count of collected target items over 12 evaluation trials per checkpoint. Due to presence of only successful sequences, the separate value network is not pre-trained with BC.
40

---

Under review as a conference paper at ICLR 2022
roplay until
replay until L
Agent
Figure A.20: Trajectory replay given by an exemplary consensus. The agent can execute training or evaluation processes of various sub-tasks by randomly sampling and replaying previously recorded trajectories on environment reset. Each letter defines task. L (log), P (planks), V (stick), L (crafting table) and N (wooden pickaxe).
7-
MEAN LOG
0.6
Moan Log
0.4
0.2
3-
0.0
0
50
100
150 Epoch
200
250
300
30
Learning
Figure A.21: Average number of logs collected during training: left: Behavioral Cloning, Right: PPO Training
A.7.7 REINFORCEMENT LEARNING ON SUB-TASK AGENTS
After the pretraining of the Sub- Task agents, we further fine tume the agents using PPO in the MineRL environment. The reward is the redistributed reward given by Align-RUDDER. The value function initialized burn-in stage prior to policy improvement where the agent interacts with environment for 50k timesteps and only updates the value function. Finally, both policy and the value function are trained jointly for all sub-tasks. All agents are trained between 50k timesteps and 500k timesteps. We evaluate each agent periodically during training and in the end select the best performing agent per sub-task. A.21 A.25 present evaluation curves of some sub-task agents during learning from demonstrations using behavioral cloning and learning online using PPO.
A.8 REPRODUCING THE ARTIFICIAL TASK RESULTS
The code reproduce the results and figures of both artificial tasks is provided supplementary material. The README contains step-by-step instructions to set up an environment and run the exper- iments. By default, instead of using 100 seeds per experiment only 10 used in the demonstration code.
Finally, video showcasing the MineCraft agent is also provided supplementary material.
41

---

Under review as a conference paper at ICLR 2022
Mamm Aome WM
NEAN, PLANKS
0.92
0.6
0.4
-0.04
6.2
50
100
150
200
M
[poch
0.0
50
100
150
200
Epech IPPO Learnin!
Figure A.22: Average number of planks crafted during training: left: Behavioral Cloning, Right: PPO Training
Crafting-Table
MCMN CRAITING_ TAOLE
0.02
0.8
0.00
0.6
-0.02
0.4
-0.04
0.2
0.0
25
75
1.00
125
150
175
Epoch IPPO Learning!
Figure A.23: Average number of table crafted during training: left: Behavioral Cloning, Right: PPO Training
ranert Litniialonn..
Cobblestone
25
COBBLEST BEBLESTONE
Noun Cobilastone
MW
2-
10-
0.00007
0
10
15
20
Epoch
Epoch IPPO Learning
Figure A.24: Average number of stone collected during training: left: Behavioral Cloning, Right: PPO Training
A.9 SOFTWARE LIBRARIES
We are thankful towards the developers of Mazelab Zuo (2018), PyTorch Paszke et al. (2019), OpenAI Gym Brockman al. (2016), Numpy Harris et al. (2020), Matplotlib Hunter (2007) and Minecraft Guss et al. (2019b).
A.10 COMPUTE
Artificial task (I) and (II) experiments were performed using CPU only as GPU speed-up was negligible. The final results for all methods were created internal CPU cluster with 128 CPU
42

---

Under review as a conference paper at ICLR 2022
0.08
Miiner, yonur rinert y0
3.5
MEAN IRON ORE
0.06
2.0
v
0.04
2.0
0.02
1.5
0.00
1.0
50
250
300
20
30
40
50
Epoch
Epoch IPPO Learning
Figure A,25: Average number of iron-ore collected during training: left: Behavioral Cloning, Right: PPO Training
cores with measured wall-clock time of 10,360 hours. The majority of compute is spent on baseline methods.
For minecraft, during development 6 to 8 nodes each with 4 GPUs of an internal GPU cluster were used for roughly six months of GPU compute time (Nvidia Titan V and 2080 TI).
The compute required for training the final agent was well within the challenge parameters (4 days on a single node with one GPU).
43


Reviews:
[{"review_id": "meFhKin1ns6", "reviewer": "Reviewer_YcqX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## **Paper Strengths**\n\n**Motivation**: The authors make very clear the motivation. Improving RUDDER, a reward redistribution method, so that it can work on tasks in which demonstrations of high-reward trajectories are given because the task is too hard for exploration alone. \n\n**Method Novelty:** Applying a sequence alignment mechanism seems relevant and a novel contribution, also leading to good empirical results.  \n\n**Experiment Results:** Align-RUDDER seems to have great performance improvements over RUDDER, especially with a very limited number of demonstrations. The compared baselines also seem to be relevant, demonstrating Align-RUDDER's good performance. Furthermore, the MineCraft diamond mining demonstrates impressive performance gains. The authors also perform hypothesis testing, further validating the results of their experiments.\n\n**Supplementary Material:** The authors provide a detailed set of background knowledge for RUDDER, sequence alignment, and extra figures/examples in the appendix. Furthermore, the supplementary video was nice and informative.\n\n \n\n## **Paper Weaknesses**\n\n**Grammatical Issues:** A few grammatical issues throughout, it doesn't detract too much but occasionally causes a hiccup in the flow when reading, so please fix these.\n\n**Method Clarity**: \n\n- The paper figures do not explain the method too well. Figure 2 is a decent figure, but the caption does not really explain the right half, nor does it draw any parallel between the two parts of the figures. I think this figure should be simplified, labelled, and used to better show how the reward redistribution using conservation score mechanism works in the biological sequence alignment case, and in the reward redistribution case. Figure 3 is nice, but it should have some text explaining things better in the caption. As the actual explanation for how the method + alignment strategy works is very complicated, these figures are critical for showing it clearly at a higher level.\n- Furthermore, there should be some more intuition presented earlier about *why* sequence alignment is easier than RUDDER's LSTM.\n- In Section 3, \"Reward Redistribution by Sequence Alignment,\" to someone unfamiliar with biological alignment techniques, you should explain why alignment will intuitively help first, before diving into details.\n- In fact, in general, I think at least to me the amount of detail given to the alignment explanation should be redistributed for a conference like ICLR. The authors should rewrite the method section to have far fewer details (except those explicitly needed) about the alignment algorithm itself, this should all be in the appendix. Instead, the entire reward redistribution scheme should be used to explain both intuitively and in detail how this 1) encourages alignment of similar trajectories in terms of states and actions, 2) better alignment scores  result in a better reward redistribution scheme, and 3) is far easier to learn with few demonstrations than RUDDER's LSTM. Of course, some details should be kept but in general I think there is too much detail placed in the nitty-gritty of *how* alignment is done in the main paper.\n\n**Experiments:** To me, the experimental setup seems valid. But along the same lines as what was stated above, there should be a bit more analysis in the main text about *why* Align-RUDDER performs the way it does in comparison to the other methods.\n\n## **Questions**\n\n- Appendix page 33: \"We...transform images into feature vectors using a standard pre-trained network,\" what standard pre-trained network was used?\n\n## Minor Issues\n\n- Contribution 2 and 4 in the intro are saying basically the same thing\n- \"Sub-tasks\" in page 5, is this meant to have a new line before and be bolded instead?\n- Page 7, describing the hierarchical setup, \"more details can be found in the appendix,\" please link an appendix section for easier referencing here\n- The reference to learning methods should be a clickable link back to that subsection describing the learning method (i had forgotten the learning methods by the time I reached page 6 where it's mentioned in the experiments)\n", "summary_of_the_paper": "This paper presents an improvement over RUDDER to allow for RUDDER-style reward redistribution when given limited sets of demonstrations by using a biological sequence alignment model.\n", "summary_of_the_review": "In summary, I think this paper presents strong results, and is a valid technical contribution, but the main reason I am currently voting for reject is that it needs some rewriting to address my clarity concerns. I am willing to adjust my score if the authors can improve on this.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "eqMaJWZqM40", "reviewer": "Reviewer_bJpP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n+ The empirical evaluation is well laid out and the experiments are described with necessary details. The authors perform careful evaluation on multiple (synthetic) environments to build intuition for and motivate the changes in the training algorithm.\n\nWeakness:\n+ The paper writing could be improved to better explain the prior work and segregating the core contributions of the work (e.g reward redistribution builds on RUDDER). \n+ The experiments are restricted to navigation based grid-world style environments. It would be useful to have more comparison on other benchmark tasks like locomotion.", "summary_of_the_paper": "The paper considers the challenge of improving sample efficiency of RUDDER-style algorithms in sparse MDPs. Building on prior work by Arjona-Medina et al [1], the authors incorporate demonstrations of optimal trajectories from an expert in the training pipeline. Additionally, to improve the sample efficiency and stability, the authors replace LSTM-model of RUDDER with an alignment based profile model. \n\nThe approach is evaluated on two synthetic grid-world based environments and a MineCraft based environment. On both benchmarks the proposed algorithm works better than baseline RUDDER. ", "summary_of_the_review": "The authors consider the challenge of improving sample efficient HRL in sparse environments. They identify several drawbacks in RUDDER and propose effective modifications to the learning algorithm to improve performance. While the experiments are promising they are restricted to navigation style experiments, it would be useful to have comparison to more imitation learning based baselines with diversity in learning environments.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "X62QZIhSKeX", "reviewer": "Reviewer_mK3T", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n- Simple, effective and general technique for identifying subgoals with few expert demonstrations sharing a common strategy\n\n- Large gains over RUDDER and sota imitation learning methods on 2 gridworld tasks\n\n- The only technique that was able to mine a diamond in the minecraft challenge with automatically learned subgoals (infrequently)\n\nCurrent Limitations:\n\n- As shown in figure 6, the success rate of Align-RUDDER is high, but then degrades rapidly in the last quarter of the minecraft task. An analysis of what elements of Align-RUDDER contributed to that degradation would be highly instructive in understanding the current limitations of the approach, and future research directions.\n\n- Align-RUDDER's \"five steps\" are described completely enough, but I feel that the presentation needs to be further improved for those not already familiar with profile models (many). Expanding figure 3 and better connecting the description with it would improve the paper substantially.\n\n- The assumption of a single underling strategy in Align-RUDDER seems like a significant limitation. A clustering step to identify multi-strategy profiles will be required in many situations. How common such situations are and how they would be detected and mitigated with e.g. with multi-strategy profiles is not adequately discussed.\n- Figure 1, which describes the basic intuitions behind the RUDDER approach, distributes all of the reward to earlier subtasks, leaving none for the end-goal, which seems like an issue...\n\nPost-rebuttal comments:\n\nThank you to the authors for their response. I have looked at the other reviews and re-read parts of the updated paper, and I tend to agree with the more critical reviews wrt the following: \n\n1) The explanation of RUDDER is still not complete or detailed enough to appreciate Align-RUDDER's relative strengths (and weaknesses), and thus the contributions of the paper. \n\n2) The explanation of Align-RUDDER needs significant work wrt both the layering and quality of explanation, it is just not clear enough. Read the first sentence in (V) of section 3, does it make sense? There are many more examples of poorly crafted sentences. Perhaps more significantly, it just doesn't come together to explain the technique clearly. In my opinion it still needs to be completely revised.\n\n3) In addition, following up on my concern with figure 1, I also take issue with the \"Q-functions are step-functions statement\", and the characterization around figure 1 that RUDDER makes all EFRs zero... These are not the correct characterizations. RUDDER is representing the EFR with a (sparse) set of reward advantage events through reward redistribution, and as such, the details around RUDDER become very important--perhaps with better \"event detection\" regularization, the LSTM approach is far more effective than the Align approach, which is constructed in a somewhat ad-hoc manner with a diverse set of tools. \n\nBased on these considerations, the paper is still in need of substantial revision, and I have lowered my score.", "summary_of_the_paper": "The authors propose Align-RUDDER, which aligns given task demonstrations (sharing a common strategy) using a profile model, to identify common events as subgoals and redistibute reward to realize more efficient and effective RL. Align-RUDDER replaces RUDDER's replay buffer with task demonstrations and RUDDER's LSTM with a simpler profile model to maximally leverage high reward but scarce demonstrations in tasks characterized by sparse and delayed reward signals, which are notoriously difficult to explore effectively.", "summary_of_the_review": "A solid approach to the difficult and important problem of learning from scarce expert demonstrations. An analysis of the success rate degradation in the last part of the minecraft task, and an improved explanation of Align-RUDDER's \"five steps\" would strengthen the paper significantly.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IS0IUU7saP", "reviewer": "Reviewer_nk2L", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "While the results in Minecraft are presented as impressive, the paper contains several shortcomings from the strict scientific point of view. The key question - is the new method working better than the original RUDDER and why? - is poorly addressed. The comparison is made only on two different GridWorld problems, and it is unclear whether the benefit is from the new reward redistribution technique or division to subtasks. An ablation study and experiments on different domains, perhaps those used in the original RUDDER paper, are required to find the answer.\n\nMoreover, some key concepts of the paper are poorly explained. Section \"Defining Events\" does not explain how the clustering is exactly done. A function \"f(s, a)\" remain undefined. I don't agree to the authors' claim that \"Q-function of an optimal policy resembles a step function\" and \"is mostly constant\". Presentation of the paper can be improved: It is not clear why the biological sequences in Fig. 2 left is included. Fig. 6 include letters on x-axis without any explanation about their meaning. Grammar and typography can be improved.\n", "summary_of_the_paper": "The paper uses Sequence Alignment technique to redistribute rewards, to a similar effect as with LSTM in RUDDER. The hierarchical agent is trained with behavioral cloning and fine-tuned with RL (tabular in Rooms environment / PPO in MineRL). Tasks are automatically divided into subtasks and specialized agents used for the subtasks. The main contributions seem to be: a) introduction of the Sequence Alignment technique which works well with few expert demonstrations; b) experimental demonstration in Rooms / MineRL.", "summary_of_the_review": "Given all the drawbacks, the paper is not ready for publication. I would recommend the authors to focus more on the in-depth comparison with Rudder, save some space by moving the figures regarding Minecraft to the appendix, rewrite the key concepts in more depth, verify the key assumptions and demonstrate WHY the new method is better.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: ## A Brief Summary
This paper proposes two critical modifications to the original RUDDER algorithm:
1. Proposes the Align-RUDDER method that assumes that the episodes with high rewards can be used as demonstrations.
2. Uses a profile model from the Multiple sequence alignment approach to align the demonstrations and redistribute the rewards according to how frequently events in the demos are shared across different demonstrators. MSA is being used as a profile model instead of LSTM.

The paper uses successor features to represent state-action pairs, which is then used to compute the similarity matrix used for MSA afterward. 
The paper shows promising results in the Minecraft environment (ObtainDiamond task,) as well as synthetic grid-world environments. 

## Reviewer bJbP
*Strengths:* 
- Empirical evaluation is well-done.
*Weaknesses:*
- The writing requires more work.
- Limited experiments: Mostly on toy-grid world/navigation environments, it is not clear if the results will generalize to the control problems.

## Reviewer mK3T
*Strengths:* 
- Simple and effective technique for identifying sub-goals.
- Large improvements over original RUDDER.
- Impressive results on Minecraft.
*Weaknesses:*
- More through ablations on the importance of different elements of Align-RUDDER.
- Presentation and writing need more improvements.
- Assumption of a single underlying successful strategy is an important limitation.
- Figure 1 is problematic and confusing because of the way it explains the RUDDER algorithm. 

## Reviewer nk2L
*Strengths:* 
- Impressive results on Minecraft.
*Weaknesses:*
- Poor justification and motivation.
- RUDDER vs Align-RUDDER comparisons are only done on two grid-world environments.
- More ablations are required to justify the approach.
- Writing requires more work, some important concepts require more clarity. Some undefined concepts...
- Incorrect claims such as:
> Q-function of an optimal policy resembles a step function

## Reviewer YcqX
*Strengths:* 
- Strong motivation.
- MSA for demos is novel.
- Strong experimental results.
*Weaknesses:* 
- Several grammatical errors.
- The method is not explained well in the paper, the writing needs more work to improve the clarity.
- Lack of sufficient analysis and ablations on the Align-RUDDER approach.

## Key Takeaways and Thoughts
Overall, the result provided in this paper in the Minecraft environment is impressive. The motivation for the Align-RUDDER is clear for me. I like the paper; in particular, the application of the MSA for the alignments across the demos is novel. However, as all the reviewers of this paper agreed that the paper is unclear, especially the method description requires more work. The paper needs to present more ablations and analysis to justify which components of Align-RUDDER algorithm are essential. I agree with both insights, the authors have made improvements in the paper to improve the exposition of the algorithms, but still, the paper feels a bit rushed. I would recommend the authors reconsider the paper's current structure and improve the writing further, especially the description of the method can be further improved. I would recommend that the authors fix those essential issues with the paper and the other comments reviewers made in a future resubmission.
Decision: Reject