pages=-, frame=true, pagecommand=

# Teacher-student curriculum learning for reinforcement learning

### Declaration of Originality

I hereby declare that the written work I have submitted entitled

Teacher-student curriculum learning for reinforcement learning

is original work which I alone have authored and which is written in my own
words.

Author

Yanick |  Schraner
---|---

Supervisor

Manfred |  Vogel
---|---

With the signature I declare that I have been informed regarding normal
academic citation rules. The citation conventions usual to the discipline in
question here have been respected.

Place and date |  |  Signature
---|---|---

###### Contents

  1. Abstract
  2. Acknowledgements
  3. Symbols
  4. 1 Introduction
    1. 1.1 Related Work
    2. 1.2 Previous Work
    3. 1.3 Problem Statement
  5. 2 Background
    1. 2.1 Reinforcement Learning
      1. 2.1.1 Finite Markov Decision Processes
      2. 2.1.2 Policy and Value Functions
      3. 2.1.3 Deep Reinforcement Learning
      4. 2.1.4 Policy Gradient Methods
      5. 2.1.5 Proximal Policy Optimization
      6. 2.1.6 Challenges of Deep Reinforcement Learning
    2. 2.2 Transfer Learning
      1. 2.2.1 Evaluation Metrics for Transfer Learning
    3. 2.3 Curriculum
    4. 2.4 Curriculum Learning
      1. 2.4.1 Curriculum Learning Categorization
      2. 2.4.2 Task sequencing
  6. 3 Methods
    1. 3.1 Curriculum Learning
      1. 3.1.1 Transfer Method
    2. 3.2 Teacher Curriculum Markov Decision Process
      1. 3.2.1 Teacher Observation
      2. 3.2.2 Reward Signal
      3. 3.2.3 Action
      4. 3.2.4 Network Architecture
    3. 3.3 Baselines
    4. 3.4 Evaluation Protocol
  7. 4 Experiments and Results
    1. 4.1 Grid World
      1. 4.1.1 Grid World Environments
      2. 4.1.2 State & Observations
      3. 4.1.3 Actions
      4. 4.1.4 Rewards
      5. 4.1.5 MDP Statement
    2. 4.2 Grid World Experiments
      1. 4.2.1 Experimental Setup
      2. 4.2.2 Results Overview
      3. 4.2.3 Transfer Method
      4. 4.2.4 Teacher Reward Signal
      5. 4.2.5 Choosing Alpha for Exponential Moving Average
      6. 4.2.6 Sample Efficiency
      7. 4.2.7 Generality of Agents
    3. 4.3 Google Football Environment
      1. 4.3.1 State & Observations
      2. 4.3.2 Actions
      3. 4.3.3 Rewards
      4. 4.3.4 Football Academy Scenarios
      5. 4.3.5 MDP Statement
    4. 4.4 Google Football Experiments
      1. 4.4.1 Experimental Setup
      2. 4.4.2 Results
  8. 5 Discussion
  9. 6 Conclusion
  10. References
  11. A Appendix
    1. A.1 Grid World CNN Architecture
    2. A.2 Grid World Student Hyperparameters
    3. A.3 Google Football Student Hyperparameters
    4. A.4 Teacher Hyperparameters
    5. A.5 MLP vs. LSTM Teacher Model

## Abstract

Reinforcement learning (rl) is a popular paradigm for sequential decision
making problems. The past decade’s advances in rl have led to breakthroughs in
many challenging domains such as video games, board games, robotics, and chip
design. The sample inefficiency of deep reinforcement learning methods is a
significant obstacle when applying rl to real-world problems. Transfer
learning has been applied to reinforcement learning such that the knowledge
gained in one task can be applied when training in a new task. Curriculum
learning is concerned with sequencing tasks or data samples such that
knowledge can be transferred between those tasks to learn a target task that
would otherwise be too difficult to solve. Designing a curriculum that
improves sample efficiency is a complex problem. In this thesis, we propose a
teacher-student curriculum learning setting where we simultaneously train a
teacher that selects tasks for the student while the student learns how to
solve the selected task. Our method is independent of human domain knowledge
and manual curriculum design. We evaluated our methods on two reinforcement
learning benchmarks: grid world and the challenging Google Football
environment. With our method, we can improve the sample efficiency and
generality of the student compared to tabula-rasa reinforcement learning.

## Acknowledgements

I want to thank everyone who supported me throughout this thesis. I am
thankful for the moral support, open door for my thoughts and concerns, and
advice during my thesis work.

Firstly, I would like to extend my special thanks to my advisor Prof. Dr.
Manfred Vogel, who supported me in my thesis and throughout my master’s
studies. I am thankful for his criticism, humor, and his guidance during this
time.

I would also like to thank Christian Scheller and Lukas Neukom for their
proofreading and valuable comments on this thesis.

## Symbols

### Symbols

The following list describes important notations used in this work.

$\mathbb{E}[X]$ | expectation of a random variable X
---|---
$\alpha,\beta$ | step-size parameters
$\gamma$ | discount-rate parameter
$s,s^{\prime}\in\mathcal{S}$ | states, $s^{\prime}$ is subsequent step of $s$
$a\in\mathcal{A}$ | an action
$r\in\mathcal{R}$ | a reward
$\mathcal{S}$ | set of all states
$\mathcal{A}(s)$ | set of all actions available in state $s$
$\mathcal{R}$ | set of all possible rewards, a finite subset of $\mathbb{R}$
$t$ | discrete time step
$T$ | final time step of an episode
$a_{t}$ | action at time $t$
$s_{t}$ | state at time $t$
$r_{t}$ | reward at time $t$
$\pi$ | policy
$\pi(s)$ | action taken in state $s$ under deterministic policy $\pi$
$\pi(a|s)$ | probability of taking action $a$ in state $s$ under stochastic policy $\pi$
$p(s^{\prime}|s,a)$ | probability of transition to state $s^{\prime}$, from state $s$ taking action $a$
$r(s,a)$ | expected immediate reward from state $s$ after action $a$
$V^{\pi}(s)$ | state-value function for policy $\pi$
$V^{*}(s)$ | optimal state-value function
$Q^{\pi}(s,a)$ | action-value function under policy $\pi$
$Q^{*}(s,a)$ | optimal action-value function
$\boldsymbol{\theta},\boldsymbol{\theta_{t}}$ | parameter vector of target policy
$\pi(a|s,\boldsymbol{\theta})$ | probability of taking action $a$ in state $s$ given parameter vector $\boldsymbol{\theta}$
$\pi_{\boldsymbol{\theta}}$ | policy corresponding to parameter $\boldsymbol{\theta}$
$\nabla\pi(a|s,\boldsymbol{\theta})$ | column vector of partial derivatives of $\pi(a|s,\boldsymbol{\theta})$ with respect to $\boldsymbol{\theta}$
$J(\boldsymbol{\theta})$ | performance measure for the policy $\pi_{\boldsymbol{\theta}}$
$\nabla J(\boldsymbol{\theta})$ | column vector of partial derivatives of $J(\boldsymbol{\theta})$ with respect to $\boldsymbol{\theta}$
$\mathcal{V}$ | Set of all task used in curriculum learning

### Acronyms and Abbreviations

ALP | Absolute learning progress section 3.2.1
---|---
EMA | Exponential moving average section 3.2.1
FS-EMA | Fast and slow exponential moving average section 3.2.1
LP | Learning progress section 3.2.1
PTR | Previous task reward section 3.2.1
RH | Reward history section 3.2.1
RL | Reinforcement Learning section 2.1
SMM | Super Mini Map section 4.3
MDP | Markov decision problem section 4.3.5
POMDP | Partially observable Markov decision problem
PPO | Proximity Policy Optimization section 2.1.5

## Chapter 1 Introduction

Reinforcement learning is based on the idea of learning through interaction
with an environment. Learning through interaction is a natural way to gain new
skills and a concept underlying nearly all theories of learning and
intelligence. Infants learn a lot about the cause and effect of their actions
by observing the results of their actions. We learn how to achieve specific
goals solely by observing the joy of actions leading to a pleasant state in
our environment (like grabbing our favorite toys) or getting harmed by other
actions (like touching a hot plate).

Reinforcement learning (RL) builds upon this idea of learning through
interaction. As supervised learning (SL) and unsupervised learning (UL),
reinforcement learning is a machine learning paradigm. Due to its generality,
researchers apply RL to a broad range of tasks. The ongoing rise of deep
learning enabled reinforcement learning on high-dimensional input and highly
complex environments. Successful applications are board games [Silver et al.,
2016, 2017, 2018], video games [Mnih et al., 2015, OpenAI et al., 2019a,
Vinyals et al., 2019] and robotics [OpenAI et al., 2019b].

The use of reinforcement learning in a practical setting is often not
realistic due to the sample inefficiency of RL. RL agents usually require a
large number of interactions with the environment to learn proper behavior.
For example, the training of OpenAI Five [OpenAI et al., 2019a] took two
months with 150 PFlops / day to surpass professional human-level performance.
Training Agent57 [Badia et al., 2020] for the Atari benchmark required 90
billion environment frames to reach human performance.

There are multiple ways to improve the sample efficiency of reinforcement
learning. Imitation learning methods make use of an existing expert
demonstration dataset to learn from expert priors. The simplest form of
imitation learning is behavior cloning, where a policy is learned in a
supervised learning fashion [Pomerleau, 1989]. This method suffers from the
distribution mismatch of the training data and the actual environment. A
slight divergence of trajectories present in the dataset during inference
leads to situations unknown to the trained policy. Ross et al. [2011] use a
human in the loop process to counter the distribution mismatch by continuously
labeling the data for those unknown situations. Another option is to use
reinforcement learning to fine-tune the initial policy [Scheller et al., 2020,
Vinyals et al., 2019]. A different popular strategy to make RL more sample
efficient is to exploit the hierarchical structure of the given problem
[Sutton et al., 1998, Dayan and Hinton, 1993, Sutton et al., 1999a]. One can
imagine training a sub-policy for every individual task and a general policy
that chooses one of those sub-policies. Another way to improve sample
efficiency is curriculum learning (CL), where the learning process is
structured so that new concepts are learned in a sequence and an agent can
leverage what he previously learned. Let us consider maths as an analogy: We
first have to learn basic arithmetic before we can do linear algebra. The idea
of using such a structured learning process to train artificial agents dates
back to Elman [1993] for grammar learning.

In this work, we build upon the idea of curriculum learning to improve the
sample efficiency of our RL approach. There are many ways to define a
curriculum. We will specify those in section 2.3. Our work focuses on how we
can automatically define such a curriculum during training by phrasing the
task sequencing problem as a meta Markov decision process. We present a novel
curriculum learning framework where no domain knowledge for the task
sequencing is required. This framework aims to increase the sample efficiency
as well as the asymptotic reward compared to vanilla reinforcement learning
and a set of heuristic-based baselines.

This work builds upon a previous project where we applied manually designed
curriculum learning on a football simulation. In this previous work, we were
able to increase the sample efficiency of our algorithm and the asymptotic
reward to 1 compared to vanilla reinforcement learning with a reward of -1.4
on the 11 vs. 11 hard environment. In section 1.2 we provide a brief
recapitulation of the previous work and its findings.

###  1.1 Related Work

Our work lies in the field of curriculum learning in reinforcement learning.
CL comprises three key elements: transfer learning, task sequencing, and task
generation. In this work, we focus on transfer learning and task sequencing.

##### Transfer learning

is a field in machine learning which studies how knowledge gained by solving a
source task can be transferred to a target problem such that the target task
can be solved faster. In reinforcement learning, transfer learning increases
the sample efficiency or the performance on the target task. Knowledge can be
transferred by selecting samples collected on a source task and use them as
input for batch reinforcement learning [Lazaric et al., 2008, Lazaric and
Restelli, 2011]. Options [Sutton et al., 1999b] or macro-actions can be
extracted on a source task and included in the action space of the target task
[Soni and Singh, 2006, Vezhnevets et al., 2016]. Models of the transition and
reward function of a source task can be transferred to allow a hybrid approach
of model-free and model-based RL on the target task [Fachantidis et al.,
2013]. The parameters of a learned policy or value function can also be used
to initialize the policy or value function in the target task [Fernández et
al., 2010, Taylor et al., 2007, Taylor and Stone, 2005].

Those methods make different assumptions about the source and target Markov
Decision Processes (MDP). The action or state space must be shared to allow
the initialization of a policy or value function. Alternatively, a task
mapping for states and actions of the source task to their equivalents of the
target task is needed in tabular reinforcement learning. For some methods, we
need access to a model of the source task, and not all methods allow the use
of multiple source tasks.

In our work, we focus on transfer learning through policy transfer and reward
shaping.

We refer to the surveys on transfer learning for reinforcement learning
provided by Taylor and Stone [2009], Lazaric [2012] for more insights.

##### Task sequencing

is concerned with how the tasks can be sequenced in order to provide a
curriculum. The sequencing of those tasks is crucial in CL. If the tasks at
the beginning of the sequence are too hard, then the agent may fail to learn
and is unable to solve the following tasks. The goal is to sequence the task
into a curriculum which allows the agent to learn with a higher sample
efficiency and final performance compared to an agent trained solely on the
target ask. A suitable task sequence depends on the set of tasks, the agent’s
characteristics, the target task, and is domain-specific.

To perform task sequencing, we must control the environment to a certain
degree to create different tasks. Depending on the level of control we have,
we can apply different task sequencing methods. In practice, the first
approach to task sequencing is made manually. We focus on how we can
automatically generate a task sequence for our curriculum. The simplest form
is a single task curriculum where we reorder recorded experience without
changing the MDP, referred to as sample sequencing. We collect this experience
into an experience buffer during agent-environment interactions. This idea has
its roots in supervised learning, where the training data is sampled in a
specific order to speed up the training process [Bengio et al., 2009]. One
example of sample sequencing in RL is Prioritized Experience Replay for DQN
and its follow-up work [Schaul et al., 2016, Andrychowicz et al., 2017, Ren et
al., 2018, Kim and Choi, 2018].

In multi-agent environments, we can create a curriculum by controlling the
interaction of agents in the same environment. This approach to task
sequencing is called co-learning. In its simplest form, one performs self-play
where an agent competes against or acts cooperatively with an older version of
itself. The agent to train and his counterpart gets progressively better on
the task and therefore creates an implicit curriculum. This setup has proven
to be successful in the well-known Go AI Alpha Go and its successors [Silver
et al., 2016, 2018]. In Vinyals et al. [2019] the idea of self-play was
extended to a league setting. The goal of this league setup is that the agent
faces increasingly stronger opponents and opponents trained to perform
specific strategies to exploit weaknesses and prevent mode collapse.

In co-learning and sample sequencing, the target MDP is not changed, and no
specific level of control over the environment is required. If control over
the environment is possible, one can change the target MDP by changing the
initial state distribution or the reward function to create a suitable task
sequence. One example of this approach is the reverse curriculum generation,
where a robot is learning to reach a goal from a set of starting positions
increasingly far from the goal [Florensa et al., 2017].

Foglino et al. [2019a] uses metaheuristic search methods such as beam search,
tabu search, genetic algorithms, or ant colony search in order to solve the
task sequencing problem. In their follow-up paper, they compare those
metaheuristic search methods to their Heuristic Task Sequencing for Cumulative
Return (HTS-CR) algorithm [Foglino et al., 2019b].

In our work, we treat the task sequencing as an MDP [Narvekar et al., 2017,
Matiisen et al., 2019, Narvekar and Stone, 2019] where we use reinforcement
learning in order to train a teacher agent to perform the task sequencing
online. In this setting, we formalize curriculum learning as an interaction of
two MDPs. The standard MDP modeling the learning agent interacting with the
environment is referred to as student MDP. A meta level MDP for the curriculum
agent to perform the task sequencing referred to teacher MDP.

At the time of writing, no MDP-based task sequencing method where both student
and teacher use neural network-based function approximators and where both are
trained using reinforcement learning is known to the author. Therefore the key
focus is to propose such a framework and analyze the efficiency of such an
approach.

##### Task generation

specifies how and when the source tasks for the curriculum are defined. The
quality of its source tasks heavily influences the quality of a curriculum.
The tasks can either be created beforehand or online during training. The goal
of task generation is to create a set of source tasks that allow a knowledge
transfer through them such that it is easier to solve the target task.

In Narvekar et al. [2016], a method for creating a set of source tasks by
specifying task descriptors, that are controlling the degrees of freedom of
the task, is introduced. Those task descriptors specify the environment like
the environment size, action set, opponent type, initial states, et cetera. In
Powerplay [Schmidhuber, 2013] a framework where new tasks are generated online
is introduced. The system searches for new source tasks such that the agent
becomes more and more general. A fixed computation budget is applied to force
the task generator to create new tasks that are only slightly more difficult
than the previous ones. Jiang et al. [2020] introduced the idea of prioritized
level replay. In reinforcement learning environments, there is usually a level
identifier. This could be a level index or a random seed. Usually, the level
to use is sampled uniformly. Which level is sampled can influence the
difficulty of the task as well as the environment dynamics. This diversity
among levels implies that different levels hold different learning potentials
for RL agents at any point in training. Prioritized level replay introduces a
new level sampling strategy to prioritize levels based on their learning
potential creating an implicit curriculum.

###  1.2 Previous Work

In previous work, we tried to reproduce the work of Kurach et al. [2019] on
the Google Research Football environment. We also implemented and evaluated
extensions to the Proximal Policy Optimization (PPO) algorithm such as Actor
with Variance Estimated Critic (AVEC) [Flet-Berliac et al., 2020].
Additionally, we carried out experiments with curriculum learning in the
Google football environment. Detailed information about this environment can
be found in section 4.3. We evaluated two manually defined curricula as well
as two automatically generated curricula, and a prioritized level replay
curriculum. We used the weights obtained by training on the source task as an
initialization for the policy on the target task as a transfer method.

The results of our previous work are summarized in table 1.1 for a comparison
in section 4.4.2. Scenarios curriculum and 11 vs 11 curriculum are both
manually defined curricula, the first one over both a set of football academy
tasks (see table 4.8) and the 11 vs 11 full game on difficulty easy, medium
and hard. The second curriculum only uses the 11 vs 11 full game environments.
The increasing curriculum consistently increases the game difficulty parameter
$\delta$ by $0.05$ starting from $0.01$ and finishing at $0.95$. A $\delta$
value of $0.95$ is equivalent to the 11 vs 11 hard environment. At the first
task change, we increase $\delta$ from $0.01$ to $0.05$ instead. The
difficulty is increased automatically after 100 training iterations. Smooth
increasing curriculum is similar to the increasing curriculum. Instead of
adapting the difficulty depending on training iterations, we increase the
difficulty as soon as the average return is greater than $0.9$. Additionally,
we increment $\delta$ by $0.001$, start with a value of $0.001$ and end with a
$\delta$ value of $0.95$.

Although four out of five curricula improve our results, only the smooth
increasing curriculum can outperform the baseline significantly. Using only
the 11 vs. 11 tasks includes too hard tasks at the early stages of learning.
The smooth increasing curriculum is superior over the increasing curriculum as
the task difficulty increases more evenly. Scenarios curriculum includes task
switches with significant changes in their initial state distribution and
observation space, making this type of curriculum worse than the increasing
ones.

Experiment | Return
---|---
PPO | -1.4
Best scenarios curriculum | -0.85
Best 11 vs 11 curriculum | -2.08
Best increasing curriculum | -0.48
Best smooth increasing curriculum | 1
Prioritized level replay | -1.05
Baseline | -1.39
Table 1.1: Comparison of our different curriculum learning approaches, the
average return over 100 episodes on the 11 vs 11 hard environment is reported.

###  1.3 Problem Statement

In this work, we are developing a teacher-student curriculum learning setup
focusing on online task sequencing and transfer learning. We manually do the
task generation and focus on the task sequencing problem formulated as a
curriculum MDP [Narvekar et al., 2017]. Both the teacher and student are
policy gradient reinforcement learning agents using neural networks as
function approximators and are trained with PPO. We aim to answer the
following research questions:

  * •

Is it possible to train both teacher and student with the curriculum MDP
(CMDP) setting from scratch such that the sample efficiency or average reward
on the target task increases compared to vanilla PPO on the target task?

  * •

What is a suitable reward function for our teacher agent to increase the
sample efficiency or average reward on the target task?

  * •

How can we define observations in the CMDP such that the sample efficiency or
average reward on the target task increases?

  * •

What is a suitable transfer method for the specified setting?

  * •

Are we able to improve the results of our previous work on the Google Research
Football environment with this curriculum learning framework?

## Chapter 2 Background

In this chapter, we introduce the core ideas and theoretical foundations used
in this work. We introduce the reinforcement learning paradigm focusing on
policy gradient methods and highlight some core ideas important in this work.
We introduce the proximal policy optimization (PPO) algorithm and additional
RL improvements used in this work. Parts of this chapter were written in our
previous work [Schraner, 2020] and added to this thesis for a coherent
document.

###  2.1 Reinforcement Learning

Reinforcement learning is a popular framework suited to solve sequential
decision-making processes. An agent learns how to act in an environment by
observing a numerical reward signal. The agent has to learn a policy to
predict an action based on the environment’s state, such that the cumulative
reward is maximized. At the early stages of learning, RL is very similar to
trial and error learning. By making progress, the learner usually continuously
observes new states of the environment and learns how to act in those new
states without forgetting about the correct behavior in the early stages. The
only indication wether a single or a series of actions leads to preferable
changes in the environment is the reward signal. After every action, the agent
receives a representation of the new environment state (observation) and a
reward signal. This signal can be either positive or negative, and it does not
tell the agent exactly which series of actions lead to that signal. The reward
can be delayed, for example, students receive a negative reward signal while
studying for their exams, but they receive a large positive reward signal
after successfully passing the exam. This way of learning makes RL a general
framework, as stated by the reward hypothesis:

> That all of what we mean by goals and purposes can be well thought of as the
> maximization of the expected value of the cumulative sum of a received
> scalar signal (called reward) [Sutton and Barto, 2018].

Biological systems inspire the use of a reward signal to learn: through
experiencing pleasure or pain, we know what actions are good in an immediate
sense.

In contrast to RL, supervised learning uses a training set of labeled
examples. With supervised learning, we are trying to capture the knowledge
represented in the training set. The use of a training set proved to be very
powerful to learn intelligent behavior, but it also makes supervised learning
hard for interactive problems. Often it is impractical or costly to obtain a
useful set of examples of the desired behavior that is both correct and
representative for all situations. There is an intersection of RL and
supervised learning called imitation learning. In imitation learning, the
agent receives an initial set of labeled demonstrations of actions in the
environment and uses it in a supervised fashion. The agent may be improved
further with standard reinforcement learning.

With unsupervised learning, one can find structure hidden in a large amount of
unlabeled data. There is no reward signal to maximize in unsupervised
learning, which differentiates it from RL.

####  2.1.1 Finite Markov Decision Processes

Markov decision processes (MDP) is a formalisation for sequential decision-
making processes. A Markov decision process is a 4-tuple
$(\mathcal{S},\mathcal{A},p,r)$, where

  * •

$\mathcal{S}$ is a set of states

  * •

$\mathcal{A}$ is a set of actions

  * •

$p(s^{\prime}|s,a)=P[s_{t+1}=s^{\prime}|s_{t}=s,a_{t}=a]$ is the probability
of transitioning from state $s$ to state $s^{\prime}$ when taking action $a$.

  * •

$r(s,a)=\mathbb{E}[r_{t+1}|s_{t}=s,a_{t}=a]$ is the expected reward received
by taking action $a$ in state $s$.

MDPs are an idealized form of the reinforcement learning problem and are used
to formulate mathematically precise theoretical statements [Sutton and Barto,
2018].

Figure 2.1: The agent-environment interaction in a Markov decision process
[Sutton and Barto, 2018].

The agent-environment interaction in a MDP is shown in fig. 2.1. The decision-
maker is called an agent. The agent interacts with the environment by
following a policy denoted by $\pi$. The policy maps from state $s$ to action
$a\in\mathcal{A}$ and can either be deterministic $\pi(s)=a$ or stochastic
$\pi(a|s)=P_{\pi}[a_{t}=a|s_{t}=s]$. Everything outside the agent is the
environment. Taking an action in the environment leads to a change in the
environment’s state. For example in the grid world environment, an action can
be moving forward, picking up a key, or opening a door. The environment
receives the action of the agent and returns a reward $r$ and a representation
of its new state $s\in\mathcal{S}$. If the entire state of the environment is
not observable, e.g., the agent has only a limited field of view, the agent
receives an observation $o\in\mathcal{O}$ instead of a state. The observation
only partially describes the environment’s state. The environment can be
deterministic or stochastic and may change itself without interactions from
the agent. Agent and environment are interacting in a sequence of discrete-
time steps $t$. $t$ starts from $0$ in the first time-step, and goes up to
$T$, with $T$ being the last time-step. At each time step, the agent receives
a representation of the environment state $s_{t}$ and a reward $r_{t}$ based
on which he selects and executes action $a_{t}$. This leads to a sequence of
interactions called trajectory:
$s_{0}a_{0}r_{1}s_{1}a_{1}r_{2}s_{2}a_{2}r_{3}\dots s_{t}a_{t}r_{t}$. A
trajectory has to be finite.

In a finite MDP, the sets of states, actions and rewards all have a finite
number of elements. The next state is only dependent on the preceding state-
action pair. Therefore we have a well defined discrete probability
distributions for the next state dependent only on the preceding state-action
pair [Sutton and Barto, 2018]:

$\text{P}[s_{t+1}|s_{t},a_{t}]=P[s_{t+1}|s_{1},a_{1},\dots,s_{t},a_{t}]$ (2.1)

This is called the Markov property. To fulfill the Markov property, the
probabilities given by $p$ can only depend on the preceding state and action
and completely characterize the dynamics of the environment. Therefore, a
single state must include information about every aspect of the past agent-
environment interactions that make a difference for the future.

####  2.1.2 Policy and Value Functions

In reinforcement learning, agents select their actions according to their
policy function. A policy has to be time-independent, the trajectory up to the
time step t does not influence the action probabilities. The policy $\pi(a|s)$
outputs a probability distribution over all possible actions given a state:

$\pi(a|s)=P[a_{t}=a|s_{t}=s]$ (2.2)

The objective of this policy is to maximize the cumulative future reward, also
called return $G_{t}$:

$G_{t}=r_{t+1}+\gamma
r_{t+2}+\gamma^{2}r_{t+3}+\cdots=\sum_{k=t}^{T-1}\gamma^{k}r_{t+k+1}$ (2.3)

The discount factor $\gamma\in[0,1]$ serves multiple purposes:

  * •

future rewards may have higher uncertainty

  * •

future rewards do not provide immediate benefits. In some cases, immediate
rewards are of more value, like in economics where we prefer the money now
over later as we could invest it in maximizing future earnings.

  * •

the discount factor provides mathematical convenience, as it solves problems
with infinite MDPs or loops in the state transition graph [Sutton and Barto,
2018]

The performance of a policy is measured by its state- and action-value
functions. Those value functions for the policy $\pi$ are the expectation of
what return the agent receives by following policy $\pi$ from state
$s\in\mathcal{S}$. This estimation is called state-value function $V(s)$ (how
good is it to be in a given state) or action-value function $Q(s,a)$ (how good
it is to perform a given action in a given state). The state-value function is
the expected return when following policy $\pi$ from state $s$:

$V^{\pi}(s)\doteq\mathbb{E}_{\pi}[G_{t}|s_{t}=s]$ (2.4)

The action-value function is the expected return when taking action $a$ in
state $s$ and then following policy $\pi$:

$Q^{\pi}(s,a)\doteq\mathbb{E}_{\pi}[G_{t}|s_{t}=s,a_{t}=a]$ (2.5)

A policy $\pi$ is considered better than another policy $\pi^{\prime}$ if for
all states $s\in\mathcal{S}$ the expected return is larger:

$V^{\pi}(s)>V^{\pi^{\prime}}(s),\forall s\in\mathcal{S}$ (2.6)

An optimal policy $\pi^{*}$ is a policy that is better or as good as any other
policy in any state:

$V^{\pi^{*}}(s)\geq V^{\pi}(s),\forall s\in\mathcal{S}\land\forall\pi\in\Pi$
(2.7)

where $\Pi$ is the set of all possible policies.

The optimal state-value function $V^{*}$ is the maximum expected return over
all policies when being in state s:

$V^{*}(s)=\text{max}_{\pi}V^{\pi}(s)$ (2.8)

The optimal action-value function $Q^{*}$ is the maximum expected return over
all policies when being in state s and taking action a:

$Q^{*}(s,a)=\text{max}_{\pi}Q^{\pi}(s,a)$ (2.9)

Therefore, the optimal policy $\pi^{*}$ can be obtained by acting greedily
according to the action that maximizes $Q^{*}(s,a)$:

$\pi^{*}(a_{t}|s_{t})=\begin{cases}1,&\text{if
}a_{t}=\text{argmax}_{a\in\mathcal{A}}Q^{*}(s_{t},a)\\\
0,&\text{otherwise}\end{cases}$

Standard old fashion approaches to find the optimal state-value function
$V^{*}$ or optimal action-value function $Q^{*}$ are Dynamic Programming,
Monte-Carlo Methods, or Temporal-Difference Learning. We will not cover those
methods in this report and continue with deep reinforcement learning and
policy gradient methods. See Sutton and Barto [2018] for an introduction of
those traditional methods.

####  2.1.3 Deep Reinforcement Learning

Tabular methods work well for problems with a small state and action space.
For such environments, it is easy to build a table with value or action-value
estimates and act according to this table. Those problems are not very
interesting and far away from real-world applications. With growing state or
action spaces, the memory and computation needs are growing exponentially,
with respect to the state or action space, for tabular methods. It is also not
feasible to visit every state to fill a table with value estimates. With
stochastic environments, the problem gets even worse, as we would have to
visit every state multiple times to calculate statistics. This raises the need
for state approximation to generalize between similar states. There are
numerous ways to approximate states, but the advances in deep learning made
neural networks the preferred option as a function approximator. The work of
Mnih et al. [2015] can be considered as the breakthrough of mixing deep
learning with reinforcement learning and allowing a single algorithm to learn
how to play Atari games. One challenge of deep learning with RL is that the
optimization problem is non-stationary because the agent encounters new states
in the environment during the ongoing learning progress.

####  2.1.4 Policy Gradient Methods

Instead of learning value functions and selecting actions based on those
functions, we can directly learn a parameterized policy that selects actions
without consulting a value function. This approach is called policy gradient
method. In policy gradient methods the policy $\pi_{\theta}$ is parametrized
with a parameter vector $\theta\in\mathbb{R}^{d}$. When using a neural network
as a function approximator for the optimal policy, the last layer of this
network is usually a softmax layer in case of discrete actions. The
probability distribution will be close to a uniform distribution in the early
learning stages, leading to natural exploration. If the optimal policy is
stochastic, then the softmax distribution will approximate the optimal
stochastic policy. If the optimal policy is deterministic, then softmax
distribution degenerates to a nearly deterministic policy. There is no need to
specify that beforehand. Another advantage of policy gradient methods is that
we directly optimize for what we care about, which is the optimal policy. It
may be simpler to learn the policy directly than to estimate the state or
state-action value.

Given a performance measure for $\pi_{\theta}$ in the form of a differentiable
objective function $J(\theta)$, we can perform gradient ascent to update the
pararameters $\theta$:

$\theta\leftarrow\theta+\alpha\nabla_{\theta}J(\theta)$ (2.10)

The learning rate is specified by $\alpha$ and needs to be tuned.

The objective of reinforcement learning is to maximize the expected sum of
total discounted rewards. Policy gradient methods take this as an objective
function to maximize:

$J(\theta)=\mathbb{E}_{\pi_{\theta}}[\sum_{t=0}^{T-1}\gamma^{t}r_{t}]$ (2.11)

The objective function in this form is usually not differentiable as it is
dependent on the stationary state distribution of the environment and thus can
not be used for gradient ascent. By the policy gradient theorem [Sutton and
Barto, 2018] we can rewrite $J(\theta)$ to a differentiable form:

$\nabla
J(\theta)=\mathbb{E}_{\pi_{\theta}}[\nabla_{\theta}\text{log}\pi_{\theta}(a_{t}|s_{t})Q_{\pi_{\theta}}(s_{t},a_{t})]$
(2.12)

Actor-critic methods are policy gradient methods that are also learning a
value function. This value function is used as a critic. The critic is used
for bootstrapping as in temporal-difference learning [Sutton and Barto, 2018].
Using one or more estimated values, in this case, an estimate for the action-
value, in the update step for the same kind of estimated value is called
bootstrapping. Actor-critic methods use a bootstrapped $n$-step return or
directly estimate the action-value function. The advantage of bootstrapping is
variance reduction of the estimates and allowing us to take updates on partial
episodes. However, it comes at the cost of a bias towards the learned critic
as it usually does not match the real action-value function.

In advantage actor-critic methods, the same critic used for bootstrapping is
also used as a baseline function. The baseline (estimated action-value) is
subtracted from the sampled $n$-step return resulting in a term called
advantage. The advantage tells the agent how much better or worse his policy
performs than currently estimated by the critic. The actor updates the policy
parameters $\theta$ for $\pi_{\theta}(a_{t}|s_{t})$, in the direction
suggested by the critic. If the observed return is less than the expected
return, we want to lower the probability of taking the given action;
otherwise, we want to assign that action a higher probability. Using a
baseline leads to further variance reduction and thus increases the
convergence speed.

####  2.1.5 Proximal Policy Optimization

Proximal policy optimization (PPO) is a policy gradient method for
reinforcement learning by Schulman et al. [2017]. Similar to trust region
policy optimization (TRPO) [Schulman et al., 2015] a constraint on the policy
update is added such that parameter updates do not change the policy too much.
This improves training stability as it prevents large policy updates. In TRPO
an objective function is maximized, while a constraint on the size of policy
updates is enforced. The Kullback–Leibler (KL) divergence of the old policy
$\pi_{\theta_{\text{old}}}$ and the policy after the updated $\pi_{\theta}$ is
used for such a constraint:

$\text{maximize}_{\theta}\mathbb{E}[\dfrac{\pi_{\theta}(a_{t}|s_{t})}{\pi_{\theta_{\text{old}}}(a_{t}|s_{t})}A_{t}(s_{t},a_{t})]$
(2.13) $\text{subject to
}\mathbb{E}[\text{KL}[\pi_{\theta_{\text{old}}}(\cdot|s_{t}),\pi_{\theta}(\cdot|s_{t})]]\leq\delta$
(2.14)

where $\theta_{\text{old}}$ is the vector of policy parameters before the
update, and $A$ is the advantage.

This constraint can be transformed to a penalty in order to solve an
unconstrained optimization problem:

$\text{maximize}_{\theta}\mathbb{E}[\dfrac{\pi_{\theta}(a_{t}|s_{t})}{\pi_{\theta_{\text{old}}}(a_{t}|s_{t})}A_{t}-\beta\text{KL}[\pi_{\theta_{\text{old}}}(\cdot|s_{t}),\pi_{\theta}(\cdot|s_{t})]]$
(2.15)

where $\beta$ is a scaling coefficient. In TRPO, the hard constraint is used
instead of a penalty because it is hard to choose a value of $\beta$ that
performs well. Especially on problems where the characteristics change
throughout learning, as is the case in RL.

PPO builds upon this idea of a trust region but implements a more
straightforward constraint. A clipped surrogate objective is used to archive
this simplification. The ratio between old an new policies is denoted by
$\phi(\theta)$:

$\phi(\theta)=\dfrac{\pi_{\theta}(a_{t}|s_{t})}{\pi_{\theta_{\text{old}}}(a_{t}|s_{t})}$
(2.16)

The TRPO objective is, therefore:

$J^{TRPO}(\theta)=\mathbb{E}[\phi(\theta)A_{t}(s_{t},a_{t})]$ (2.17)

PPO now imposes the constraint by forcing $\phi(\theta)$ to stay within a
trust region of $[1-\epsilon,1+\epsilon]$ where $\epsilon$ is a
hyperparameter. Simply clipping updates force the policy to stay in the trust
region:

$J^{\text{CLIP}}(\theta)=\mathbb{E}[\text{min}(\phi(\theta)A,clip(\phi(\theta),1-\epsilon,1+\epsilon)A)]$
(2.18)

Therefore if the objective value is not in the trust region, the clipped value
will be used.

When PPO is used in a network architecture with shared parameters for policy
(actor) and value (critic) functions, an additional entropy term (blue) is
introduced to encourage exploration. Furthermore, the error term on the value
estimation (red) is part of the PPO objective function.

$J^{\text{CLIP}}(\theta)=\mathbb{E}[J^{\text{CLIP}}(\theta)-{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}c_{1}(V_{\theta}(s_{t})-V_{\text{target}}(s_{t}))^{2}}+{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{2}H(s_{t},\pi_{\theta}(\cdot,s_{t}))}]$
(2.19)

where both $c_{1}$ and $c_{2}$ are scaling parameters for those losses which
need to be tuned.

PPO increases the sample efficiency of the RL algorithm empirically, and we
hence use it in this work. Hsu et al. [2020] has shown that in some cases, PPO
fails to converge to a bad local optimum:

  * •

Using standard PPO with a continuous action space, training becomes unstable
when rewards vanish outside the trust region. This can happen due to a bad
Gaussian policy update, where PPO fails to recover.

  * •

On high-dimensional discrete action spaces, clipping might converge to
suboptimal actions with standard softmax policy parametrization. This happens
when the policy sees only bad actions (reward 0) and suboptimal actions
without observing the optimal action. PPO then tends to increase the
probability of suboptimal actions and not exploring new actions.

  * •

PPO can converge to suboptimal actions if they are close to the
initialization.

####  2.1.6 Challenges of Deep Reinforcement Learning

There are a lot of unsolved challenges in deep reinforcement learning. The
most important two are the exploration vs. exploitation dilemma and the deadly
triad.

The exploration vs. exploitation dilemma also exists in the real world. We
might have our favorite ski resort, where we go skiing every year. However,
there are a lot of other ski resorts which we have not visited yet. It could
be that one of the new resorts would please us more than our current favorite.
If we do not try out different resorts, we may never find the optimal one, but
we risk skiing in a place with only easy slopes and bad restaurants if we try
out new ones. The best long-term strategy might involve short-term sacrifices
to find the optimal ski resort. The difficulty is to find the optimal ratio of
exploring new places vs. exploiting the current best one. This analogy can be
adapted to reinforcement learning. We have to explore new actions to learn
more about their effectiveness and maximize the expected return in the long
run by exploiting new better actions found by exploring. In stochastic tasks,
this dilemma is even worse because we have to explore the same action multiple
times due to the stochastic changes. According to Sutton and Barto [2018] this
problem remains unresolved and is specific to RL as it does not occur in
supervised or unsupervised learning.

The deadly triad is a definition by Sutton and Barto [2018]. It states that
instability and even divergence while optimizing arises whenever we combine
the following three elements:

  * •

Function approximation like neural networks. This element is needed to solve
problems with large state and action spaces.

  * •

Bootstrapping Using one or more estimated values in the update step for the
same kind of estimated value [Sutton and Barto, 2018]. Bootstrapping adds a
bias towards our start estimation, but the updates result in high variance for
long trajectories without bootstrapping. Without bootstrapping, we need more
samples before our estimate converges, leading to a loss in data efficiency
and a rise in computational cost.

  * •

Off-policy training We call our training off-policy when we update another
policy (target policy) than the one we followed to generate the training
trajectories. We need to train multiple value functions and policies in
parallel for some use-cases and are therefore off-policy. Many of the current
state-of-the-art RL algorithms are off-policy algorithms. Being off-policy is
also useful as it allows us to run a learned policy in parallel distributed on
hundreds of actors and having a centralized learner who uses the generated
trajectory to update a slightly off-policy policy.

All of the three elements are very useful, and one does not want to give them
up. In practice, many RL architectures successfully use all three elements of
the deadly triad, like DQN [Mnih et al., 2015]. In the example of DQN, they
use many tricks to cope with the instability and prevent the estimates from
divergence through training with experience replay and occasionally freeze the
target network.

###  2.2 Transfer Learning

In reinforcement learning, an agent usually starts with a random policy. The
agent then has to learn an optimal policy for the target task using no prior
knowledge. For challenging target tasks, for example, due to sparse reward
signals or poor state representations, the agent might learn very slowly or
entirely fails to learn at all.

Transfer learning is one area of research that tries to speed up the training
of RL agents by transferring knowledge from one or more source task MDPs to a
target task. Instead of learning to solve the target task tabula rasa, the
agent acquires knowledge on one or more source tasks. The knowledge can be
transferred in form of samples [Lazaric et al., 2008], options [Soni and
Singh, 2006], policies [Fernández et al., 2010], models [Fachantidis et al.,
2013] or value functions [Taylor and Stone, 2005]. In the case of policy and
value function transfer, the parameters of a policy or value function obtained
by training on one or multiple source tasks can be used to initialize the
policy or value function of the agent. Transferring the policy or value
function leads to a bias in the action selection towards the experience
acquired in the source task.

####  2.2.1 Evaluation Metrics for Transfer Learning

To quantify the benefits gained from transfer learning, we need meaningful
metrics. Typically we compare the learning curve on the target task for an
agent after transfer with a tabula rasa agent. We consider the following three
metrics:

  * •

Time to Threshold: The time to threshold computes how much faster an agent
with knowledge transfer reaches a reward threshold compared to a tabula rasa
agent. The time can be measured by CPU / GPU instructions, wall clock time,
episodes, or steps.

  * •

Jumpstart: This measurement quantifies the initial performance boost we gain
as a result of knowledge transfer.

  * •

Asymptotic Performance: The asymptotic performance compares the final
performance increase at the end of training.

When comparing tabula rasa agents to agents that use transfer learning, we
need to specify if we want to include the time spent learning the source tasks
in our metrics. We talk about weak transfer when we do not include the costs
of training in source tasks. If we consider the time spent in the source tasks
when calculation the metrics, we measure the strong transfer. In fig. 2.2 we
illustrate the three metrics once with a weak transfer and once with a strong
transfer. As the strong transfer includes costs for training in the source
task, the transfer curve starts with a delayed training time in fig. 2.2 (b).

(a) Weak transfer

(b) Strong transfer

Figure 2.2: Performance metrics for transfer learning using (a) weak transfer
and (b) strong transfer (figure by Narvekar et al. [2020]).

###  2.3 Curriculum

We define a curriculum as a concept that organizes past experiences and
schedules future experiences by training on tasks. Every task is modeled as a
Markov Decision Process.

In the following we use the curriculum definition of Narvekar et al. [2020]:

######  Definition 2.3.1 (Curriculum).

Let $\mathcal{T}$ be a set of tasks, where
$m_{i}=(\mathcal{S}_{i},\mathcal{A}_{i},p_{i},r_{i})$ is a task in
$\mathcal{T}$ and $i$ is the task identifier. Let $\mathcal{D}^{\mathcal{T}}$
be the set of all possible transition samples from tasks in $\mathcal{T}$:
$\mathcal{D}^{\mathcal{T}}=\\{(s,a,r,s^{\prime})|\exists
m_{i}\in\mathcal{T}\text{ s.t.
}s\in\mathcal{S}_{i},a\in\mathcal{A}_{i},s^{\prime}\sim
p_{i}(\cdot|s,a),r\leftarrow r_{i}(s,a,s^{\prime})\\}$. A curriculum
$C=(\mathcal{V},\mathcal{E},g,\mathcal{T})$ is a directed acyclic graph, where
$\mathcal{V}$ is the set of vertices,
$\mathcal{E}\subseteq\\{(x,y)|(x,y)\in\mathcal{V}\times\mathcal{V}\wedge x\neq
y\\}$ is the set of directed edges, and
$g:\mathcal{V}\rightarrow\mathcal{P}(\mathcal{D}^{\mathcal{T}})$ is a function
that associates vertices to subsets of samples in $\mathcal{D}^{\mathcal{T}}$,
where $\mathcal{P}(\mathcal{D}^{\mathcal{T}})$ is the power set of
$\mathcal{D}^{\mathcal{T}}$. A directed edge $(v_{j},v_{k})$ in $C$ indicates
that samples associated with $v_{j}\in\mathcal{V}$ should be trained on before
samples associated with $v_{k}\in\mathcal{V}$. All paths terminate on a single
sink node $v_{t}\in\mathcal{V}$.

If the curriculum is created online, then the edges are added dynamically
during the agent’s training. If the curriculum is created offline, then the
graph is created beforehand.

One simplification to the curriculum definition is the single-task curriculum,
where all samples stem from a single task. In a single-task curriculum, we
rearrange the order in which we train on the experience samples as in
prioritized experience replay [Schaul et al., 2016].

######  Definition 2.3.2 (Single-task Curriculum).

A single-task curriculum is a curriculum $C$ where the cardinality of the set
of tasks considered for extraction samples $|\mathcal{T}|=1$, and consists of
only the target task $m_{t}$.

A second simplification of the curriculum definition is the task-level
curriculum. In the task-level curriculum, we define a directed acyclic graph
of intermediate tasks. The main challenge here is how to order the
intermediate tasks such that the agent can constantly learn to solve more
complex tasks while preventing catastrophic forgetting on already solved
tasks. The mapping function $g$ determines the set of samples
$\mathcal{D}^{\mathcal{T}}_{i}$ that are available at the next vertex. There
are multiple works on task-level curricula [Svetlik et al., 2017, Matiisen et
al., 2019].

######  Definition 2.3.3 (Task-level Curriculum).

For each task $m_{i}\in\mathcal{T}$, let $\mathcal{D}^{\mathcal{T}}_{i}$ be
the set of all samples associated with task
$m_{i}:\mathcal{D}^{\mathcal{T}}_{i}=\\{(s,a,r,s^{\prime})|s\in\mathcal{S}_{i},a\in\mathcal{A}_{i},s^{\prime}\sim
p_{i}(\cdot|s,a),r\leftarrow r_{i}(s,a,s^{\prime})\\}$. A task-level
curriculum is a curriculum $C=(\mathcal{V},\mathcal{E},g,\mathcal{T})$ where
each vertex is associated with samples from a single task in $\mathcal{T}$.
Thus, the mapping function g is defined as
$g:\mathcal{C}\rightarrow\\{\mathcal{D}^{\mathcal{T}}_{i}|m_{i}\in\mathcal{T}\\}$.

The simplest form of a curriculum is the sequence curriculum. In the sequence
curriculum, all nodes have an indegree and outdegree of at most 1. If combined
with the task-level curriculum, we end up with the task-level sequence
curriculum, which is an ordered list of tasks $[m_{1},m_{2},\dots m_{t}]$

######  Definition 2.3.4 (Sequence Curriculum).

A sequence curriculum is a curriculum $C$ where the indegree and outdegree of
each vertex $v$ in the graph $C$ is at most 1, and there is exactly one source
node and one sink node.

###  2.4 Curriculum Learning

In curriculum learning, we try to find the optimal order in which we feed
experience from different source tasks to the agent in order to maximize one
of the metrics defined in section 2.2.1. The intuition behind curriculum
learning is that through generalization over source tasks and knowledge
transfer through increasingly more complex tasks, we can increase the sample
efficiency or asymptotic performance of our training algorithms. There are
three key elements to curriculum learning:

  * •

Task Generation: In order to produce a beneficial curriculum, we need a good
set of source tasks. The tasks should provide an increasing difficulty. The
tasks have to be similar to the target task. Otherwise, we might end up with a
negative transfer, and using a curriculum over such tasks is hurtful for
solving the desired target task. Task generation is, therefore, an important
part of curriculum learning. In a task-level curriculum, the tasks are the
nodes of the curriculum graph. The task may be generated online during
training or pre-specified.

  * •

Sequencing: Sequencing is concerned with the ordering of the experience
samples. According to the graph definition in section 2.3, sequencing defines
the vertices in our curriculum graph. These vertices can either be defined
online during training or offline before training the agent. In section 2.4.2
we go into details of this aspect to curriculum learning.

  * •

Transfer Learning: In order to benefit from a curriculum of tasks, we need a
method to transfer knowledge through the curriculum. In section 2.2 we
explained multiple methods for transfer knowledge from one or more source
tasks to the target task. In curriculum learning, we repeatedly transfer
knowledge from task to task, whereas we have only one transfer step in
standard transfer learning.

We visualized the interaction between the three key elements in fig. 2.3.

Figure 2.3: We visualize the interaction between the three key elements of
curriculum learning. Task generation is concerned with generate a set of tasks
for the curriculum. Task sequencing selects a task out of the task set for the
agent. The agent use knowledge obtained by training on previously selected
task through transfer learning. After or during training on the new task, the
obtained knowledge is stored. The task generation and sequencing can be done
online and dependent on the student’s current performance or offline before
training.

When evaluating the curriculum, we use the same metrics as in section 2.2.1.
Those metrics have to be extended as we have to consider the costs of building
the curriculum. It is not clear how the work for the task sequencing or task
generation done by humans should be included into the strong transfer metrics.
In our work, we ignore those costs for the sake of simplicity.

####  2.4.1 Curriculum Learning Categorization

We can categorize a curriculum learning approach along six dimensions,
organized by attributes (in bold) and their respective values (in italics).
This categorization was introduced in Narvekar et al. [2020]:

  1. 1.

Intermediate task generation: target / automatic / domain experts / naive
users. The set of tasks can be either defined offline before training or
online during training. One can also specify a single task curriculum called
target where only the target task is used. The tasks can be specified by a
human, either a domain expert [Schraner, 2020] or a naive user with no special
domain knowledge. There are also methods to automatically generate tasks using
a set of rules or a generative process as in Wang et al. [2019].

  2. 2.

Curriculum representation: single / sequence / graph. The simplest way to
represent a curriculum is a single task curriculum, where we simply reorder
the recorded experience [Schaul et al., 2016, Andrychowicz et al., 2017]. When
using multiple tasks we can either represent the curriculum as a simple
sequence of tasks [Schraner, 2020] or as directed acyclic graph of tasks
[Svetlik et al., 2017]. In the task representation, we can allow many-to-one,
one-to-many, and many-to-many knowledge transfer.

  3. 3.

Transfer method: policies / value function / task model / partial policies /
shaping reward / other / no transfer. In section 2.2 we specified different
forms of knowledge transfer. The weights of policy [Scheller et al., 2020] or
value [Fernández et al., 2010, Taylor et al., 2007, Taylor and Stone, 2005]
functions can be transferred from task to task. One can learn task models
[Fachantidis et al., 2013] and transfer those from task to task, learn an
auxiliary reward function, or extract options [Sutton et al., 1999b] and
transfer those to the next task.

  4. 4.

Curriculum sequencer: automatic / domain experts / naive users. The curriculum
sequencing is concerned with the task switches during training. The switch can
happen automatic upon specific rules, through a teacher or other methods. In
section 2.4.2 we go into detail about this aspect of curriculum learning. We
can also sequence the task manually by domain experts or naive users.

  5. 5.

Curriculum adaptivity: static / adaptive. The adaptivity of a curriculum
specifies if the curriculum is completely defined before training or if it is
dynamically adapted online during training. A static curriculum is defined
before training, a adaptive curriculum is changed during training. Adaptive
curricula can use the learning progress to estimate, e.g., if a task is easy
or hard to learn at the current stage. Static curricula incorporate problem-
specific knowledge.

  6. 6.

Evaluation metric: time to threshold / asymptotic / jumpstart / total reward.
In section 2.2.1 we introduced metrics to quantify the benefits gained from
curriculum learning. When calculating those metrics, we have to decide if we
want to measure the weak or strong transfer.

####  2.4.2 Task sequencing

Task sequencing is concerned with how the tasks can be sequenced in order to
provide a curriculum. The tasks need to be sequenced in a way such that the
current task at hand is just hard enough to solve. It might also be of
interest to add an already learned task that the agent forgets about to allow
live long learning.

In section 1.1 we already introduced a few methods for task sequencing. In
this section, we detail two sequencing methods that use the teacher-student
setup with the MDP formulation.

Narvekar et al. [2017] formulates curriculum learning as the interaction of
two MDPs. A student MDP describes the currently selected task, and a teacher
MDP models the selection of the next task for the student. They denote the
teacher MDP as a fully observable MDP, where the state space is the set of
policies the learning agent can represent. The state is represented as the
parameters of the policy. The final states are defined as policies where the
return on the target task is higher than a specific threshold. The action
space is the set of tasks a student agent can train on. Taking an action
results in the student training on the selected task for a fixed number of
steps or until convergence. The transition function describes how the student
agents policy changes as a result of learning a task. The reward function is
defined as the time needed by the student agent to learn a policy that results
in a return surpassing a certain threshold on the target task (time to
threshold). The teacher wants to minimize this time to threshold. Therefore
the reward is encoded as the negative of the expected time needed to learn the
target task starting from a given policy. A recursive Monte-Carlo algorithm
optimizes the teacher agent, and the student is a tabular RL agent with tile
coding, trained with Sarsa($\lambda$) and a value function transfer. In their
follow-up paper, they investigated reward shaping as an additional transfer
method [Narvekar and Stone, 2019].

Matiisen et al. [2019] uses a similar approach, but the state is not fully
observable, making the MDP a partially observable Markov decision process
(POMDP). The state and action space of the teacher MDP are the same as in
Narvekar et al. [2017], but the teacher has no access to the internal
parameters of the student agent. The observation is the reward of the student
obtained on the currently selected task. The reward is the average reward of
the student evaluated on all tasks at the end of a teacher step. One could
also optimize for the reward of the target task, but initially, the student
might not archive a reward on the target task leaving the teacher without a
meaningful signal.

A comprehensive survey of task sequencing methods is provided by Narvekar et
al. [2020].

## Chapter 3 Methods

In this chapter, we describe the methods used in this thesis. We characterize
our curriculum learning approach along the six dimensions introduced in
section 2.4. Next, we detail our transfer method and the automated curriculum
sequencing approach. We propose multiple types of observations and reward
signals for our curriculum MDP. Finally, we describe our set of baselines and
the evaluation protocol.

###  3.1 Curriculum Learning

In this section, we characterize our curriculum learning approach. We use a
task-level sequence curriculum. A combination of the task-level curriculum
defined in Definition 2.3.3 and a sequence curriculum (see Definition 2.3.4).
Our curriculum learning has the following properties:

  1. 1.

Intermediate task generation: The tasks, represented as nodes in the
curriculum graph, are predefined before training. We use a subset of the tasks
provided by the grid world environment and the Google Research Football
environment. We initially selected the tasks and kept this selection fixed
throughout this thesis. The exact task selection is described in section 4.2.1
and section 4.4.1.

  2. 2.

Curriculum representation: We represent the curriculum as a task-level
sequence. We only allow one-to-one knowledge transfer between our source tasks
and the target task. A source task can be visited multiple times in the
sequence. Therefore the agent is allowed to retrain on already known tasks.

  3. 3.

Transfer method: We experiment with three transfer methods. First, we copy the
policy and value function weights from task to task to transfer the learned
policy and value function. Second, the learned value function, obtained by
training on the previous task, calculates an additional reward signal that we
added to the environment’s reward signal. Third, we experiment with a
combination of the first and second method. In section 3.1.1 we go into detail
about our knowledge transfer methods.

  4. 4.

Curriculum sequencer: In this work, we experiment with automated task
sequencers. We formulate the task sequencing problem as a curriculum Markov
Decision Process where we have full control over the student’s MDP. In section
3.2 we formalize the CMDP and explain our approach in detail.

  5. 5.

Curriculum adaptivity: We use an adaptive curriculum. The teacher performs
task sequencing online to select tasks with a suitable learning potential for
the current learning stage. Our set of source tasks is defined beforehand and
kept fix throughout training.

  6. 6.

Evaluation metric: We evaluate our agents using a weak transfer with the
asymptotic performance improvement. We compare our work against agents trained
in Schraner [2020], which uses manually defined curricula.

####  3.1.1 Transfer Method

We use two types of knowledge transfer methods: policy and value function
transfer and reward shaping. Our student agent starts with a random
initialized policy and value function. After training for a fixed amount of
steps at time-step $t$ on a task $m_{t}$, we switch to a new source task
$m_{t+1}$. The weights of the policy and value function obtained by training
on task $m_{t}$ are used to initialize the agent before training on task
$m_{t+1}$. Our student uses weight sharing for the policy and value function.
Therefore we copy all neural network weights from task to task.

We assume that both the policy and value function transfer from task to task
as the dynamics of the environment does not change in our set of tasks
$\mathcal{V}$. Therefore, a state with a true high value in one environment
$m_{i}\in\mathcal{V}$ has also a true high value in another environment
$m_{j}\in\mathcal{V}$. The same applies to our policy. The environments in our
set of source tasks differ in their initial state distribution, state space
and complexity. All tasks in $\mathcal{V}$ share the same set of actions
$\mathcal{A}$, environment dynamics function $p$ and reward function $r$.

It would also be possible to only transfer the weights of the shared embedding
together with either the policy head or the value head from task to task. Like
this, either the policy or the value are initialized randomly for each task.
The gradients for the policy and the value function flow through the same
model in our network architecture with weight sharing. If either the policy or
the value function is initialized randomly, this could lead to catastrophic
updates to the shared weights. Therefore, we transfer all the neural network
weights from task to task.

Additionally to the policy and value function transfer, we experiment with a
shaped reward signal. We use the value function $v_{m_{t}}$ obtained by
training on task $m_{t}$ as an additional reward signal when training on the
next task $m_{t+1}$. The reward $r_{i}$ at time-step $i$ is therefore
$r_{i}=r_{i}+v_{m_{t}}(s_{i})$ We expect that the value function can help to
overcome the spares reward signal provided by the environment. For the first
task $m_{1}$ in our curriculum, we do not add a shaped reward signal as we do
not have a value function at hand. Only the value function of the previous
task is added as a shaped reward. One could also use the average of the last
$n$ value functions as a shaped reward signal. We leave this experiment to
future work.

The two transfer methods described can be combined, leading to a transfer
method with policy and value function transfer and a shaped reward signal. We
also experiment with this combined transfer method.

###  3.2 Teacher Curriculum Markov Decision Process

In this section, we formulate the sequencing problem as a Markov Decision
Process. In this formulation, we define curriculum learning as an interaction
between two types of MDPs. The first MDP is the standard RL MDP modeling the
student interacting with a task. The second one is a higher level meta-MDP
called curriculum MDP (CMDP). We use the CMDP to model a teacher selecting
tasks for the student. The CMDP is a 4-tuple $(\mathcal{S},\mathcal{A},p,r)$,
where $\mathcal{S}$ is the set of all possible states equal to all possible
policies the student can represent. The action space $\mathcal{A}$ is the set
of tasks the teacher can assign to the student. Taking an action in the CMDP
equals to an entire training cycle on the selected task in the student MDP for
a fixed amount of steps. The environment’s dynamics function $p$ models the
transition from one student policy to the next student policy after taking an
action in the CMDP. The dynamics function is unknown. The reward for the CMDP
is defined by the reward function $r$. In section 3.2.2 we detail two reward
signals used in this research.

The interaction between the CMDP and the student MDP is shown in fig. 3.1. The
teacher selects a task, and the student trains for n steps on the selected
task. After the student training step, we evaluate the student on a set of
evaluation tasks and feed the evaluation result to the CMDP. In our research
the set of evaluation tasks $\mathcal{V}_{\text{eval}}$ is equal to the
learning tasks $\mathcal{V}_{\text{learn}}$.

Figure 3.1: Teacher-student interaction for task sequencing.

Now that we have defined the sequencing problem as a CMDP, we can use
reinforcement learning to find an optimal policy. We are using PPO to learn a
teacher policy while training the student at the same time. With this
approach, we have to deal with noise from the student training when performing
suboptimal task switches, especially at the beginning of our training
procedure. The teacher has to learn how to perform task sequencing while the
student has to learn how to solve the selected environment. Both are acting
randomly, which may lead to the teacher selecting too tricky tasks, and the
student has a hard time learning from that task.

####  3.2.1 Teacher Observation

We experiment with different types of observations for our teacher agent. The
state of the CMDP is the current policy of the student agent. We are using a
neural network to approximate the optimal student policy $\pi_{s}^{*}$.
Therefore the student weights $\theta_{s}$ are the state of the CMDP, and they
fulfill the Markov property. It is unclear how we should feed this state
representation into our teacher agent. We could flatten the weights
$\theta_{s}$ to a feature vector, but this would leave us with an enormous
input vector. In our case, we have roughly $400^{\prime}000$ weights in our
student network. Using such a large input vector is not feasible due to memory
limits. Additionally, we assume that such a feature vector is not easy to
interpret for our teacher agent. It is hard to relate $\theta_{s}$ to the
student’s performance and the optimal next task to select.

We use principal component analysis (PCA) [F.R.S., 1901] to find a reduced
representation for $\theta_{s}$. We build a training set containing student
weights at different training stages and then fit PCA to this dataset. This
dataset is obtained by saving the weights of the student network for different
tasks at different learning stages. At the end of each student training
iteration, we do dimensionality reduction to the first n principal components
and use this reduced representation as an input for our teacher.

There are other ways to get a reduced representation for $\theta_{s}$ like
model distillation or auto-encoders, each with its downsides. We leave the
question for an optimal way to bring $\theta_{s}$ into a meaningful
representation to future work. In this work, we refer to this observation type
as pca input (PCA).

In our work we also experiment with partial observable curriculum MDPs. We
work with six different types of manual defined observation types: reward
history (RH), previous task reward (PTR), learning progress (LP), absolute
learning progress (ALP), exponential moving average (EMA), and fast and slow
exponential moving average (FS-EMA).

##### Reward History

: Instead of using the students weights $\theta_{s}$ we try to represent the
learning potential per task. We can use a tuple of the student’s average
reward, obtained in the evaluation cycle at the end of a CMDP step, on each
task together with the time-step when this task was last sampled:

$\text{RH}=\\{(\overline{r^{m}_{\text{eval}}},t^{m}_{\text{last
sampled}})|m\in\mathcal{V}\\}$ (3.1)

Where $\overline{r^{m}_{\text{eval}}}$ is the average reward on all evaluation
episodes for task $m$ and $t^{m}_{\text{last sampled}}$ is the CMDP time-step
when task $m$ last has been sampled. If the task $m$ never has been sampled
$t^{m}_{\text{last sampled}}$ equals to 0.

##### Previous Task Reward

: Instead of using the average rewards of all tasks, we can input the last
selected task, one-hot encoded, together with the average reward on that task,
obtained in the evaluation cycle at the end of a CMDP step.

##### Learning Progress

: The learning progress is defined as the difference between the average
reward, obtained in the evaluation cycle at the end of a CMDP step, of the
current and the previous time step per task:

$\text{LP}=\\{(\overline{r^{m}_{t}}-\overline{r^{m}_{t-1}})|m\in\mathcal{V}\\}$
(3.2)

Where $\overline{r^{m}_{t}}$ is the average reward on the task $m$ at time-
step $t$ and $\overline{r^{m}_{t-1}}$ is the average reward on task $m$ at the
previous time-step $t-1$.

##### Absolute Learning Progress

: ALP is simply the absolute value of LP:

$\text{ALP}=\\{(|\overline{r^{m}_{t}}-\overline{r^{m}_{t-1}}|)|m\in\mathcal{V}\\}$
(3.3)

The intuition behind using the absolute value is that a task at the stage of
forgetting, resulting in a negative LP, should be treated similarly to a task
with a steep learning curve. This learning progress representation is inspired
by Portelas et al. [2019].

##### Exponential Moving Average

: We can interpret the history of evaluation rewards after every CMDP cycle as
a time-series. We use an exponential moving average over the history of
rewards to estimate the next reward. Depending on the $\alpha\in[0,1]$ value
used to calculate the EMA we assign more weight on recent samples than on old
ones. The exponential moving average over a vector $\mathbf{x}$ is defined as:

$\text{ema}(\mathbf{x}_{t})=\begin{cases}\alpha*\mathbf{x}_{t}+(1-\alpha)ema(\mathbf{x}_{t-1}),&t>1\\\
x_{1},&t=1\end{cases}$ (3.4)

Where $\text{ema}(\mathbf{x}_{t})$ is the value of the EMA at any time period
$t$ and $\mathbf{x}_{t}$ is the value at a time period $t$. Therefore the EMA
input is:

$\text{EMA}=\\{[ema(\mathbf{x}^{m}_{t})]|m\in\mathcal{V}\\}$ (3.5)

$\mathbf{x}^{m}$ is the history of the average reward, obtained in the
evaluation cycle at the end of a CMDP step, for task $m$ at all CMDP time-
steps. The last time step is denoted as $t$.

##### Fast and Slow Exponential Moving Average

: Kanitscheider et al. [2021] introduce a smoothed EMA version, where they
calculate a fast and a slow EMA with a high $\alpha$ and a low $\alpha$
respectively. The fast and slow EMA is then defined as the difference between
the two EMAs:

$\text{FS-
EMA}=\\{[ema_{\text{fast}}(\mathbf{x}^{m}_{t})-ema_{\text{slow}}(\mathbf{x}^{m}_{t})]|m\in\mathcal{V}\\}$
(3.6)

In our work, we wanted to test if this method is superior to a normal EMA with
a tuned $\alpha$ value.

####  3.2.2 Reward Signal

In reinforcement learning, a meaningful reward signal is crucial for success.
We need to define a reward signal for our CMDP that encodes our intention and
is rich enough for the teacher agent to learn fast. The goal of the teacher
agent is to perform task sequencing such that the asymptotic reward on the
target task increases. Therefore we can use the student’s average reward on
the target task after a CMDP step as a reward signal. We call this reward
signal target task reward. Typically, the target task is hard to solve.
Therefore the reward at the beginning of training is usually 0. This reward
signal is not meaningful for the teacher as it does not tell if the student is
making progress in easier environments or if the student is completely lost.
Such a sparse reward signal leads to less sample efficiency and as samples in
the CMDP are extremely costly, we want our teacher to learn fast.

We assume that the source tasks in $\mathcal{V}$ are related to the target
task. Therefore, if our student achieves a reward on the source tasks, this is
a step towards solving the target task. If this is true, then we can overcome
the sparse reward signal by defining a new reward signal source task reward:

$r_{\text{teacher}}=\sum_{m\in\mathcal{V}}\overline{r_{m}}$ (3.7)

Where $\overline{r_{m}}$ is the average reward on task $m$ obtained in the
evaluation cycle at the end of a CMDP step.

####  3.2.3 Action

The action space in the CMDP contains all tasks in $\mathcal{V}$. Taking an
action equals to selecting a task $m\in\mathcal{V}$, changing the student’s
environment to the selected task, and then train the student for a predefined
amount of steps. After the training, the student is evaluated on all tasks in
$\mathcal{V}$ and the evaluation results are passed to the CMDP agent. The
evaluation is carried out according to the section 3.4.

In our experiment, we train the student for $100^{\prime}000$ steps. One could
also train the student until convergence, surpassing a threshold, or make the
number of steps part of the teacher’s action space. It is unclear when the
student will converge, which could lead to very compute-intensive CMDP steps,
and if the agent can surpass the threshold, which could lead to an infinite
CMDP step. Therefore, we do not consider these two approaches. We want to keep
the teacher’s action space as simple as possible. Therefore we leaf
integrating the number of student training steps into the action space for
future work.

####  3.2.4 Network Architecture

We keep the teacher network architecture simple. We use a multilayer
perceptron (MLP) with three hidden layers with 64, 128, and 64 nodes,
respectively, and a ReLU [Agarap, 2018] activation function. We make use of
weight sharing as we do it for our student agent. The policy and value
function are represented as individual heads on top of the MLP feature
embedding.

We also experiment with LSTMs [Hochreiter and Schmidhuber, 1997] in order to
provide the teacher a memory. In this setting, we use the same MLP for the
feature embedding and then feed the feature vector into an LSTM with a hidden
state of 128. The hidden state is then used as an input for the policy and
value function heads.

Due to computation limits, we were not able to tune the network architecture.
Another network architecture likely yields better results.

###  3.3 Baselines

We compare our teacher task sequencing approach against four baselines:
uniform, LP sampling, window and thompson sampling. The last two are
introduced in Matiisen et al. [2019].

##### Uniform

: This is the simplest baseline. We select the next task by uniformly sampling
them.

##### LP sampling

: In this baseline, we select the task with the highest learning progress as
defined in eq. 3.2. If two or more tasks have the same LP, we sampling one of
those tasks uniformly.

##### Thompson sampling

: Similar to LP sampling we sample the next task according to a learning
progress metric. In the Thompson sampling baseline, we sample the task with
the highest average reward after the last CMDP step.

##### Window

: In the window algorithm, we approximate the learning progress with linear
regression. We store the history of average evaluation rewards. At each CMDP
step, we fit a linear regression to the reward history. The regression
coefficient per task is used to estimate the steepness of the learning curve.
The task with the steepest learning curve is selected.

###  3.4 Evaluation Protocol

The goal of the teacher task is to improve the asymptotic performance. We
evaluate our approach using a weak transfer to allow comparison with the
results on the Google Research Football environment from our previous work
[Schraner, 2020]. The asymptotic performance is defined as the increase in the
average reward at the end of training.

Additionally, we evaluate how well the trained student agent generalizes
across the environments. The agent is trained overall environments, and it is
interesting how well the agent performs on those environments. To measure the
generality, we calculate the total average return, which is the sum of all
average returns for all tasks in $\mathcal{V}$, and the percentage of
environments solved. We declare an environment as solved when the average
return is greater than zero.

After every CMDP step, we evaluate the student on every task in $\mathcal{V}$
for 100 episodes.

## Chapter 4 Experiments and Results

In this chapter we describe the experiments used to evaluate our methods. We
begin with an introduction of the environments used, the experimental setup
and then provide results of our baselines and teacher student experiments. In
depth experiments are carried out on a grid world environment, the most
promising settings are then evaluated on the Google Research Football
environment. In the following chapters, we use the terms task and environment
interchangeably. In our case, the environment is equal to the task to solve,
e.g., there is only a single task per environment. The description of the
Google Research Football environment is taken from our previous work
[Schraner, 2020].

###  4.1 Grid World

Grid world is a simple, lightweight, and fast environment for reinforcement
learning. In a Grid world environment, the agent must reach a target
destination by navigating through a maze. The difficulty of the environment
ranges from very simple empty grids to complex mazes where the agent has to
find keys in a specific order to unlock the target destination. We use the
minimalistic grid world (MiniGrid) implementation by Chevalier-Boisvert et al.
[2018].

In MiniGrid, the world is an NxN grid of tiles. Each tile in the grid world
contains zero or one object, and each object has an associated discrete color
and type. The object types are wall, floor, door, key, ball, and goal. Doors
have a state open, closed, or locked and behave according to this state. To
open a locked door, the agent has to carry a key matching the door’s color.
The agent can pick up and carry exactly one object (e.g., ball or key).

The simplicity of the grid world environment allows fast iteration and testing
of multiple ideas. Training a student agent in the CMDP setting in the grid
world environment takes around 18 hours. Training a teacher in the proposed
CMDP setting is computationally expensive as we have to train a student agent.
The set of environments with their different levels of complexity is helpful
for the curriculum learning setting.

Depending on the selected environment, the maximum number of steps changes. An
epoch in the simplest environment, Empty-5x5, ends after 100 steps, the most
difficult environment, KeyCorridor-S6R3, terminates after 1080 steps.

####  4.1.1 Grid World Environments

We describe the MiniGrid environments in table 4.1 and illustrate them in fig.
4.1. In a grid world environment, the agent has to navigate through a maze and
solve some puzzles to reach the green goal square. In the KeyCorridor
environment, the agent has to pick up a hidden ball behind a locked door. To
unlock that door, the agent must find the matching key, which is hidden in
another room. The agent has to explore the environment and move through open
doors to find the hidden key. The bottom row of fig. 4.1 displays two
different KeyCorridor environments.

Name |  Description
---|---
Empty-[X]x[X] |  This environment is an empty room. Upon reaching the green goal square, the student receives a sparse reward. The agent is starting in a random position. The value of X defines the grid size. We use a 5 by 5, 6 by 6, 8 by 8, and 16 by 16 grid.
FourRooms |  The agent must navigate in a maze of four rooms. Four gaps in the walls connect the rooms. To obtain a reward, the agent must reach the green goal square. Both the agent and the goal square are placed randomly in any of the four rooms.
DoorKey-[X]x[X] |  The agent must pick up a key in order to unlock a door and then reach the green goal square. Due to the sparse reward signal, this environment is difficult to solve. The door, wall, agent and green goal square are placed randomly. The value of X defines the grid size. We use a 5 by 5, 6 by 6, 8 by 8, and 16 by 16 grid.
MultiRoom-N[X]-S[Y] |  The environment has a series of connected rooms with doors that must be opened in order to get to the next room. The final green goal square is located in the last room. The rooms are all created randomly. This environment is challenging to solve using RL alone. The value of X defines the number of rooms and X the room size. We use N2-S4, N4-S5, and N6-S10 for our experiments.
KeyCorridor-S[X]R[Y] |  The agent has to pick up an object which is behind a locked door. The key is hidden in another room, and the agent has to explore the environment to find it. The key, ball, and agent are placed randomly. Due to the exploration required this is a challenging environment. The value of X defines the room size and Y number of rows (see fig. 4.1). We use an S3R1, S3R2, S3R3, S4R3, S5R3, S6R3 grid.
Table 4.1: Description of the MiniGrid environments used in this thesis. All
environments impose a penalty for the number of steps taken until reaching the
target.

Figure 4.1: Visualization of a subset of the MiniGrid environments used in
this work. The environment names from top left to bottom right: Empty-6x6,
FourRooms, DoorKey-16x16, MultiRoom-N4S5, KeyCorridor-S3R2, KeyCorridor-S3R3,
and KeyCorridor-S6R3.

####  4.1.2 State & Observations

MiniGrid supports a variety of observation types. In our work, we use a fully
observable view of the environment. This view has a dimension of
$\text{N}\times\text{N}\times 3$, where N is the dimension of the grid world.
These values are not pixels, the last channel is encoding the tile at the
$(\text{X},\text{Y})$ location. The tile encoding is a three-dimensional
tuple: (OBJECT_INDEX, COLOR_INDEX, STATE). Only doors and agents have a state
value other than 0. The door state 0 represents an open, 1 a closed, and 2 a
locked door. The agents’ state indicates the direction of the agent.

We are transferring the policy and value function weights from environment to
environment. Therefore the input dimension must stay the same for every
environment. We apply padding to have a $25\times 25$ grid world independent
of the selected environment. As padding values, we use $(1,0,0)$, which is
equivalent to a wall.

####  4.1.3 Actions

The action space in MiniGrid consists of six actions: Turn left, turn right,
move forward, pickup, drop and toggle (open door, interact with objects).

####  4.1.4 Rewards

The agent receives a reward of 1 for reaching the goal square and 0 otherwise.
A penalty for the number of steps required to reach the target location is
imposed. If the agent takes more steps to reach the target, the reward
decreases. The grid world reward upon success is calculated according to this
equation:

$r=1-0.9*(\text{step\\_count}/\text{max\\_steps})$ (4.1)

Where step_count is equal to the number of steps taken to reach the goal
square and max_steps is the maximum number of steps allowed per episode. In
fig. 4.2 we ilustrated the reward calculation for two different trajectories
in the DoorKey-8x8 environment.

Figure 4.2: A blue line illustrates the agent’s trajectory in the DoorKey-8x8
environment. The maximum number of steps in the DoorKey-8x8 environment is
640. If the agent takes the direct path, he takes 18 steps until he reaches
the green goal square. Therefore the agents reward is $1-0.9*(18/640)=0.9747$.
The agent on the right takes 28 steps, leaving him with a reward of
$1-0.9*(28/640)=0.9606$.

####  4.1.5 MDP Statement

Depending on the type of observation used, the grid world environment does not
fulfill the Markov property. Some observation types only provide a limited
field of view. To ease the problem, we only use a fully observable input for
all of our student agents. Each observation at every time step fully describes
the environment’s state space, and the following environment state is entirely
dependent on the current state.

###  4.2 Grid World Experiments

####  4.2.1 Experimental Setup

In this section, we detail the experimental setup applied to all our grid
world experiments.

##### Network architecture

Our student agent uses a fully connected network with ReLU activation
functions and separate policy and value function heads. The network
architecture is depicted in fig. 4.3.

Figure 4.3: Student neural network architecture for the MiniGrid environments.
The input is a $25\times 25\times 3$ fully observable representation of the
environments state. After every fully connected layer we use a ReLU activation
function. The policy head uses a softmax activation function for the action
probability distribution. The value head does not use an activation function.

We also evaluated a CNN network architecture. In the section A.1 we provide
details about the CNN architecture. The $25\times 25\times 3$ grid world
observation has location-dependent features. Therefore by intuition we expect
that CNN models work better than MLP models. Flattening the observation into a
vector makes it harder to discover patterns and generalize over the state
space. As we can see in fig. 4.4, using a CNN network architecture instead of
the MLP architecture improves results on harder environments. MLP models are
less noisy than CNN models, especially in the case of DoorKey experiments. We
value stability over best possible results in our thesis because reward
changes in our CMDP setting also lead to a lot of noise, therefore we use MLP
models for the rest of our experiments.

Figure 4.4: Comparison of the average return over 100 episodes at the end of
training between MLP and CNN models. The agent is trained with PPO for 10
million steps on a single environment.

##### No Curriculum Experiments

For all MiniGrid environments, we trained an agent with PPO for 10 million
steps and evaluated the agent for 100 episodes at the end of training. We used
these experiments to tune hyperparameters as well as the network architecture.
In section A.2 we report the hyperparameters. Additionally, we used the
results to select a subset of the MiniGrid environments for our curriculum
learning experiments. We removed the group of MiniGrid environments where our
trained agents failed in solving the environment. In the case of KeyCorridor
and MultiRoom, training an agent for the simplest version of those
environments succeeded. Therefore we kept all KeyCorridor and MultiRoom
environments in our task set $\mathcal{V}$. All experiments were repeated
three times under different random seeds. In our results, we report maximum
and standard deviations.

##### Curriculum learning

For both the baseline and the CMDP experiments, we perform $1^{\prime}000$
teacher steps, where for each teacher step, the student is trained for
$10^{\prime}000$ steps in the selected environment. Therefore, the student
agent is trained for 10 million steps in total. After each teacher step, the
student is evaluated for 100 episodes in each task in $\mathcal{V}$. We fixed
those number of steps to have the same training steps as we used in our no
curriculum learning experiments. We had to balance the number of teacher
updates and the number of student updates per CMDP step. Using fewer teacher
steps might not be sufficient for the teacher to learn how to perform task
sequencing but would allow our student more time to converge in the selected
environment. Using more teacher steps is beneficial for the teacher, but on
the other hand, the student has less time to learn the selected task. This
would provide the teacher with a noisy reward signal. We selected the teacher
and student steps because they seem reasonable. In future work, the influence
of those values should be evaluated.

The network architecture for the teacher agent is described in section 3.2.4.
We evaluated the MLP and LSTM network architecture in section A.5. The MLP
architecture is superior to the LSTM architecture. The hyperparameters for the
baselines as well as the CMDP teachers are described in section A.2 and
section A.4.

All experiments were repeated three times under different random seeds. In our
results, we report maximum and standard deviations.

####  4.2.2 Results Overview

Table 4.2 shows the best agent’s performance on each MiniGrid environment used
in this thesis. For each environment, we report the average return of 100
evaluation episodes. The total mean return is defined as the sum over all
average returns. The percentage of environments solved is defined as the
number of environments with an average reward greater than zero divided by all
environments. Overall, using no curriculum results in a higher average return
on 8 out of the 19 tested tasks. In contrast, curriculum learning agents
outperform standard RL agents in more complex tasks such as Empty-16x16,
DoorKey16x16, and KeyCorridor-S6R3. Comparing the best CMDP agent to the best
baseline agents we see, the CMDP agent outperforms the baselines regarding the
total mean return and percentage of solved environments.

Environment / Metric None Uniform LP Thompson Window CMDP Total mean return -
1.75 2.71 2.83 2.27 4.44 % environments solved 50% 44% 39% 50% 33% 55%
Empty-5x5 0.96 0.83 0.75 0.57 0.37 0.93 Empty-6x6 0.97 0.51 0.83 0.51 0.32 0.9
Empty-8x8 0.96 0.0 0.0 0.62 0.0 0.93 Empty-16x16 0.0 0.0 0.93 0.92 0.67 0.82
FourRooms 0.17 0.07 0.09 0.09 0.0 0.09 DoorKey-5x5 0.96 0.17 0.02 0.02 0.0
0.13 DoorKey-6x6 0.94 0.04 0.0 0.04 0.81 0.13 DoorKey-8x8 0.29 0.07 0.0 0.05
0.0 0.14 DoorKey-16x16 0.0 0.03 0.04 0.0 0.07 0.17 MultiRoom-N2-S4 0.14 0.02
0.04 0.02 0.03 0.15 MultiRoom-N4-S5 0.0 0.0 0.0 0.0 0.0 0.0 MultiRoom-N6-S10
0.0 0.0 0.0 0.0 0.0 0.0 KeyCorridor-S3R1 0.07 0.0 0.0 0.0 0.0 0.05
KeyCorridor-S3R2 0.0 0.0 0.0 0.0 0.0 0.0 KeyCorridor-S3R3 0.0 0.0 0.0 0.0 0.0
0.0 KeyCorridor-S4R3 0.0 0.0 0.0 0.0 0.0 0.0 KeyCorridor-S5R3 0.0 0.0 0.0 0.0
0.0 0.0 KeyCorridor-S6R3 0.0 0.0 0.0 0.0 0.0 0.01

Table 4.2: Highest average return over 100 episodes for each teacher type at
the end of 1000 teacher steps. The None results are the average return over
100 episodes obtained when training only the environment of that row.

In the curriculum learning approach, the agent spends less training time in a
single environment than with no curriculum. In easy environments, using no
curriculum learning and training on a single task yields better results than
the curriculum learning experiments. Training for 10 Million steps in a single
environment is better than learning in a curriculum without specifically
targeting those easy environments. In the CMDP setting using the source task
reward, the teacher is encouraged to maximize the student’s average return
over all environments and not a single environment, as is the case when using
no curriculum.

The following sections evaluate different teacher reward signals, transfer
methods, observation types, hyperparameters as well as the sample efficiency
and generality of trained agents.

####  4.2.3 Transfer Method

In this section, we evaluate the effect of the transfer methods introduced in
section 3.1.1. We evaluate policy transfer, reward shaping transfer, and both
transfers combined. All teacher agents use the source task reward, as defined
in section 3.2.2. The results for all seven teacher observation types are
reported in table 4.3 and the four baselines in table 4.4.

Figure 4.5 shows the learning curves of the reinforcement learning agents. All
agents with policy transfer surpass agents with reward shaping or the combined
knowledge transfer. The learning curve is noisy in policy transfer due to the
environment changes, but the performance is steadily increasing. The
performance of agents with policy transfer did not converge after 1000 teacher
steps. For both reward transfer and the combined transfer, the performance
converged during the first 50 to 100 CMDP steps and failed to improve from
then on. The agent’s performance with reward transfer scatters around a total
mean return of 1 during the whole training.

Figure 4.5: Learning curves for different teacher observations and transfer
methods. After each teacher step the sum of the students average return over
100 episodes for each environment in $\mathcal{V}$ is plotted. We plot the
learning curve with the highest total reward at the end of training for every
configuration.

Approximating the entire student state space by encoding the students’ weights
with PCA as described in section 3.2.1 fails. The results of the experiments
with PCA observation space are very similar to the uniform baseline results.
We, therefore, discard this method for the rest of our experiments.

The best results are obtained using the PTR, EMA, and LP observations with a
policy transfer. Using the fast-slow EMA as described in section 3.2.1 is not
superior to standard EMA. In section 4.2.5 we evaluate the best $\alpha$ value
for the EMA observation. Using the reward history (RH) is significantly worse
than the other observation types when using policy transfer. RH resulted in
the highest total mean return when using reward transfer but suffers from a
high standard deviation. In general, the results with policy transfer are more
stable compared to the results with reward transfer.

Environment / Metric RH PTR LP ALP EMA FS-EMA PCA Policy Total mean return
$2.34\pm 0.24$ $\mathbf{4.44\pm 0.33}$ $4.17\pm 0.33$ $3.35\pm 0.33$ $4.35\pm
0.42$ $3.72\pm 0.22$ $1.64\pm 0.24$ % environments solved 55% 55% 55% 55% 55%
61% 44% Empty-16x16 $0.58\pm 0.27$ $0.07\pm 0.03$ $0.9\pm 0.27$ $0.08\pm 0.03$
$0.82\pm 0.34$ $\mathbf{0.91\pm 0.38}$ $0.0\pm 0.0$ FourRooms $0.11\pm 0.03$
$\mathbf{0.13\pm 0.03}$ $0.11\pm 0.02$ $0.1\pm 0.04$ $0.08\pm 0.01$ $0.06\pm
0.03$ $0.08\pm 0.02$ DoorKey-16x16 $0.05\pm 0.01$ $0.04\pm 0.02$ $0.07\pm
0.03$ $0.13\pm 0.05$ $\mathbf{0.17\pm 0.06}$ $0.06\pm 0.03$ $0.03\pm 0.01$
MultiRoom-N2-S4 $0.1\pm 0.02$ $0.06\pm 0.02$ $0.09\pm 0.01$ $0.06\pm 0.03$
$\mathbf{0.15\pm 0.05}$ $0.09\pm 0.04$ $0.0\pm 0.0$ KeyCorridor-S3R3 $0.0\pm
0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm
0.0$ Reward Total mean return $\mathbf{1.38\pm 0.85}$ $0.68\pm 0.3$ $1.01\pm
0.32$ $1.11\pm 0.63$ $0.95\pm 0.1$ $1.22\pm 0.58$ $0.63\pm 0.21$ %
environments solved 50% 44% 61% 50% 11% 50% 34% Empty-16x16 $\mathbf{0.56\pm
0.28}$ $0.0\pm 0.0$ $0.46\pm 0.23$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$
$0.0\pm 0.0$ FourRooms $0.04\pm 0.002$ $0.03\pm 0.01$ $\mathbf{0.05\pm 0.03}$
$0.03\pm 0.01$ $0.0\pm 0.0$ $0.03\pm 0.01$ $0.0\pm 0.0$ DoorKey-16x16 $0.0\pm
0.0$ $0.0\pm 0.0$ $\mathbf{0.03\pm 0.01}$ $0.02\pm 0.01$ $0.0\pm 0.0$ $0.0\pm
0.0$ $0.0\pm 0.0$ MultiRoom-N2-S4 $0.0\pm 0.0$ $0.0\pm 0.0$ $\mathbf{0.06\pm
0.03}$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.02\pm 0.001$ $0.0\pm 0.0$ KeyCorridor-S3R3
$0.003\pm 0.001$ $0.003\pm 0.002$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$
$\mathbf{0.004\pm 0.001}$ $0.0\pm 0.0$ Both Total mean return $0.0\pm 0.0$
$\mathbf{0.47\pm 0.24}$ $0.0\pm 0.0$ $0.32\pm 0.16$ $0.0\pm 0.0$ $0.0\pm 0.0$
$0.0\pm 0.0$ % environments solved 0% 17% 0% 17% 0% 0% 0% Empty-16x16 $0.0\pm
0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm
0.0$ FourRooms $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $\mathbf{0.02\pm 0.01}$
$0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ DoorKey-16x16 $0.0\pm 0.0$ $0.0\pm 0.0$
$0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$
MultiRoom-N2-S4 $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm
0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ KeyCorridor-S3R3 $0.0\pm 0.0$ $0.0\pm 0.0$
$0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$

Table 4.3: We compare the different knowledge transfer methods for each
teacher observation type. Each configuration is run with three different
random seeds. The maximum return over 100 episodes at the end of 1’000 teacher
steps is reported. Additionally, we provide the standard deviation between the
three runs.

Agents with the combined knowledge transfer are failing to learn at all. In
fig. 4.5 we see that the average return drops from around 0.7 to 0 during the
first ten teacher steps and fails to recover from there. We visualized the
synthetic reward signal added by the reward transfer in fig. 4.6 for the
Empty-8x8 and Empty-16x16 environment. Each square in the image equals a
square in the grid world environment. The black squares are wall objects, and
the element in the bottom right is the green goal square. High state values
estimated by the value function obtained in experiments with only reward
transfer (images on the left) are scattered randomly around the grid. The
estimated state value is between 0.12 and 0.16. In the value function with a
combined knowledge transfer, the state values are almost identical for all
states and have an estimated value of 10 Million. We believe that the agent
starts to optimize and estimate its previous value function and this leads to
an ever increasing value estimate. This extremely high additional reward
overshadows the actual reward signal of the environment, making it impossible
for the agent to learn how to solve the environment successfully.

Figure 4.6: We visualize the added reward, when using reward transfer (left
column) and combined transfer (right column). For every state in the Empty-8x8
(top row) and Empty-16x16 (bottom row) grid world environment we plot the
added reward. A light color encodes a high added reward, black equals to zero
added reward. Dark tiles at the end of the grid are walls, the black tile in
the bottom right corner is the green goal square.

In fig. 4.7 we plot the teacher’s sampling probability distribution over the
teacher timesteps next to the teacher’s learning curve. During the first 100
episodes, the teacher samples tasks similar to a uniform distribution. The
teacher favors the family of Empty grid world environments during the first
200 episodes. From then on, the teacher selects more challenging environments
such as KeyCorridor and DoorKey environments. After roughly 400 teacher steps,
the sample distribution does not show the noisy changes in the sample
probabilities as at the beginning of the training. We interpret this as the
teacher getting more confident in performing task sequencing. The teacher’s
learning curve is noisy but steadily increasing. There are some drastic drops
in performance, probably due to selecting too challenging environments. The
student always manages to recover after those harmful teacher actions.

Figure 4.7: We visualize the sample probability distribution and learning
curve of one teacher agent over its training time. The colors in the legends
are ordered upside down to the order in the plot.

Table 4.4 shows the same properties as described above. The Thompson sampling
experiment with reward transfer is interesting. This is the only experiment
where the knowledge transfer with a reward signal surpassed agents with a
policy transfer. Therefore, this approach to transfer learning is feasible but
very noisy, which is also indicated by the high standard deviation for the
Thompson sampling experiments with reward transfer. While uniformly sampling
environments is a strong baseline, it still shows the worst performance across
the baselines. In general, sampling environments with the highest learning
progress estimate yields the strongest baseline results.

Environment / Metric Uniform LP Thompson Window Policy Total mean return
$1.75\pm 0.24$ $\mathbf{2.71\pm 0.33}$ $1.94\pm 0.21$ $2.28\pm 0.32$ %
environments solved 44% 39% 22% 34% Empty-16x16 $0.0\pm 0.0$ $\mathbf{0.92\pm
0.23}$ $0.0\pm 0.0$ $0.67\pm 0.14$ FourRooms $0.07\pm 0.02$ $\mathbf{0.09\pm
0.02}$ $0.0\pm 0.0$ $0.0\pm 0.0$ DoorKey-16x16 $0.03\pm 0.01$ $0.04\pm 0.01$
$0.0\pm 0.1$ $\mathbf{0.07\pm 0.03}$ MultiRoom-N2-S4 $0.02\pm 0.01$
$\mathbf{0.04\pm 0.01}$ $0.03\pm 0.01$ $0.03\pm 0.01$ KeyCorridor-S3R3 $0.0\pm
0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ Reward Total mean return $0.8\pm
0.34$ $0.51\pm 0.23$ $\mathbf{2.83\pm 1.1}$ $0.45\pm 0.12$ % environments
solved 44% 11% 50% 22% Empty-16x16 $0.0\pm 0.0$ $0.0\pm 0.0$ $\mathbf{0.92\pm
0.36}$ $0.0\pm 0.0$ FourRooms $0.03\pm 0.01$ $0.0\pm 0.0$ $\mathbf{0.09\pm
0.05}$ $0.0\pm 0.0$ DoorKey-16x16 $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$
$0.0\pm 0.0$ MultiRoom-N2-S4 $\mathbf{0.06\pm 0.02}$ $0.0\pm 0.0$ $0.02\pm
0.01$ $0.0\pm 0.0$ KeyCorridor-S3R3 $\mathbf{0.01\pm 0.01}$ $0.0\pm 0.0$
$0.0\pm 0.0$ $0.0\pm 0.0$ Both Total mean return $0.47\pm 0.21$ $0.0\pm 0.0$
$0.0\pm 0.0$ $\mathbf{0.52\pm 0.22}$ % environments solved 17% 0% 0% 17%
Empty-16x16 $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ FourRooms
$\mathbf{0.05\pm 0.01}$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.02\pm 0.01$ DoorKey-16x16
$0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ MultiRoom-N2-S4 $0.0\pm
0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ KeyCorridor-S3R3 $0.0\pm 0.0$
$0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$

Table 4.4: We compare the different knowledge transfer methods for each
baseline. Each configuration is run with three different random seeds. The
maximum the average students return of 100 episodes at the end of 1’000
teacher steps is reported. Additionally, we provide the standard deviation
between the three runs.

####  4.2.4 Teacher Reward Signal

In this section we evaluate the source task reward and the target reward. Both
reward signals are defined in section 3.2.2. We use the KeyCorridor-S3R3
environment as the target task. The agents use a policy knowledge transfer
between tasks. In table 4.5 we report experiments for both reward signals with
six observation types.

For all observation types, the reported results are better when using the
source task reward except for the RH experiments. The reported total mean
return has a lower standard deviation over three different random seeds when
using the source task reward instead of the target reward.

Environment / Metric RH PTR LP ALP EMA FS-EMA Total Eval. Reward Total mean
return $2.34\pm 0.24$ $\mathbf{4.44\pm 0.33}$ $4.17\pm 0.33$ $3.35\pm 0.33$
$4.35\pm 0.42$ $3.72\pm 0.22$ % environments solved 55% 55% 55% 55% 55% 61%
Empty-16x16 $0.58\pm 0.27$ $0.07\pm 0.03$ $0.9\pm 0.27$ $0.08\pm 0.03$
$0.82\pm 0.34$ $\mathbf{0.91\pm 0.38}$ FourRooms $0.11\pm 0.03$
$\mathbf{0.13\pm 0.03}$ $0.11\pm 0.02$ $0.1\pm 0.04$ $0.08\pm 0.01$ $0.06\pm
0.03$ DoorKey-16x16 $0.05\pm 0.01$ $0.04\pm 0.02$ $0.07\pm 0.03$ $0.13\pm
0.05$ $\mathbf{0.17\pm 0.06}$ $0.06\pm 0.03$ MultiRoom-N2-S4 $0.1\pm 0.02$
$0.06\pm 0.02$ $0.09\pm 0.01$ $0.06\pm 0.03$ $\mathbf{0.15\pm 0.05}$ $0.09\pm
0.04$ KeyCorridor-S3R3 $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$
$0.0\pm 0.0$ $0.0\pm 0.0$ Target Reward Total mean return $\mathbf{3.6\pm
0.49}$ $\mathbf{3.6\pm 0.36}$ $3.38\pm 0.62$ $2.35\pm 0.66$ $3.41\pm 0.51$
$3.38\pm 0.42$ % environments solved 55% 55% 55% 55% 55% 61% Empty-16x16
$0.58\pm 0.27$ $0.07\pm 0.03$ $0.24\pm 0.08$ $0.5\pm 0.1$ $\mathbf{0.72\pm
0.21}$ $0.63\pm 0.08$ FourRooms $0.11\pm 0.03$ $\mathbf{0.13\pm 0.03}$
$0.11\pm 0.04$ $0.1\pm 0.04$ $0.05\pm 0.01$ $0.06\pm 0.02$ DoorKey-16x16
$0.05\pm 0.004$ $0.02\pm 0.01$ $0.0\pm 0.0$ $0.08\pm 0.02$ $\mathbf{0.09\pm
0.03}$ $0.04\pm 0.01$ MultiRoom-N2-S4 $0.07\pm 0.01$ $\mathbf{0.11\pm 0.04}$
$0.01\pm 0.003$ $0.06\pm 0.03$ $0.02\pm 0.01$ $0.02\pm 0.01$ KeyCorridor-S3R3
$0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.0\pm 0.0$

Table 4.5: We compare the different teacher reward signals for each teacher
observation type. Each configuration is run with three different random seeds.
The maximum return over 100 episodes at the end of 1’000 teacher steps is
reported. Additionally, we provide the standard deviation between the three
runs.

In fig. 4.8 we plot the target reward signal along the steps in the CMDP. The
reward signal for the EMA, FS-EMA, LP, and ALP experiments are very close to
zero during training, therefore not providing the teacher agent with a helpful
signal. For RH and PTR, the reward for the first 200 teacher steps scatters
around 0.01 and 0.8 and then degenerates to the same reward signal as for the
other observation types. Surprisingly, this reward signal provided enough
information to the teacher to better perform task sequencing than the
baselines.

The target reward pushes the teacher agent towards solving the
KeyCorridor-S3R3 environment, but at the end of training the agent fails to
solve this environment with both reward signals. With both approaches, we did
not manage to solve the challenging KeyCorridor-S3R3 environment.

Figure 4.8: Visualization of the target reward signal for each teacher
observation type over the teachers training cycle.

####  4.2.5 Choosing Alpha for Exponential Moving Average

In this section, we optimize the $\alpha$ value for the exponential moving
average. An $\alpha$ value close to one favors current values over old values
in a time series. We experimented with $\alpha\in[0.1,0.3,0.5,0.7,0.9]$ and
reported the results in table 4.6. The teacher agents use a policy transfer
and the source task reward.

By looking at the results in table 4.6 it is hard to settle for an $\alpha$
value. While an $\alpha$ of 0.5 or 0.9 have the highest total mean returns,
the results for challenging environments are the best when selecting an alpha
value of 0.3. The experiments with a value of 0.7 and 0.9 suffer from a high
standard deviation in the reported total mean return.

Environment / Metric 0.1 0.3 0.5 0.7 0.9 Total mean return $3.49\pm 0.43$
$3.01\pm 0.39$ $\mathbf{4.35\pm 0.42}$ $3.89\pm 0.58$ $4.23\pm 0.95$ %
environments solved 50% 61% 55% 55% 61% Empty-16x16 $0.32\pm 0.06$ $0.58\pm
0.27$ $0.82\pm 0.34$ $\mathbf{0.97\pm 0.4}$ $0.94\pm 0.28$ FourRooms $0.08\pm
0.01$ $\mathbf{0.13\pm 0.03}$ $0.08\pm 0.01$ $0.09\pm 0.04$ $0.06\pm 0.01$
DoorKey-16x16 $0.0\pm 0.0$ $\mathbf{0.05\pm 0.02}$ $0.17\pm 0.06$ $0.0\pm 0.0$
$0.02\pm 0.01$ MultiRoom-N2-S4 $0.15\pm 0.06$ $0.08\pm 0.03$ $0.15\pm 0.05$
$0.13\pm 0.02$ $\mathbf{0.29\pm 0.12}$ KeyCorridor-S3R3 $0.0\pm 0.0$
$\mathbf{0.01\pm 0.004}$ $0.0\pm 0.0$ $0.0\pm 0.0$ $0.004\pm 0.002$

Table 4.6: We compare the different $\alpha$ values for the EMA observation
type. Each configuration is run with three different random seeds. The maximum
return of 100 episodes at the end of 1’000 teacher steps is reported.
Additionally, we provide the standard deviation between the three runs.

In fig. 4.9 we plot the average learning curve over three different random
seeds for all $\alpha$ values. An $\alpha$ value of 0.1 yields the worst
results. The learning curve of a value with 0.3 is below higher $\alpha$
values but surpassed most of the other experiments in the last 20 CMDP steps.
The learning curves for an $\alpha$ value of 0.5, 0.7, and 0.9 follow each
other closely. Our experiments do not allow us to select a clear winner.
Because of the highest total mean return combined with a relatively small
standard deviation, we propose to use an $alpha$ value of 0.5.

Figure 4.9: The average learning curve of three runs with three different
random seeds for each $\alpha$ value.

####  4.2.6 Sample Efficiency

In this section, we analyze the sample efficiency of an agent when trained in
the teacher-student setting compared to trained directly on the target task.
Learning curves compare the agent’s experience with their performance. We use
the teacher step on the x-axis to measure the experience. One teacher step
equals 10’000 steps in an environment. The performance is measured by the
average return on 100 evaluation episodes during the training. In fig. 4.10 we
plot three learning curves, one for each of the following environments:
Empty-16x16, DoorKey16x16, and FourRooms. The sample efficiency of an agent
can be measured as the area under the curve with transfer minus the area under
the curve without transfer. We do the evaluation manually by looking at the
curves.

In the Empty16x16 environment, the sample efficiency of the agents with
curriculum learning is negative for the first 400 teacher steps. After 400
teacher steps, the agent trained directly in the Empty16x16 environment
suffers from a catastrophic update and fails to recover from then on. It seems
like the agent got stuck in a bad local optimum. This is probably due to a bad
choice in the hyperparameters. We note that agents trained directly on the
Empty16x16 environment with three random seeds showed the same behavior.

In the DoorKey16x16 environment, all curriculum learning agents have a
positive sample efficiency. The learning curve is very noisy due to the
training in different environments. Although we notice an improvement in the
sample efficiency, the agent’s performance is not monotonically increasing and
dropping to the same performance level as when trained directly in the
DoorKey16x16 environment. One could perform early stopping when crossing a
reward threshold to solve this issue, but defining such a threshold is not
straightforward.

There is no improvement in the sample efficiency in the FourRooms environment.
Curriculum learning with the PTR teacher shows the best results with a slight
improvement in sample efficiency during some learning stages.

Figure 4.10: We visualize the learning curves of our agent when trained in the
teacher-student setup and directly on the target task for the Empty-16x16,
DoorKey16x16, and FourRooms environment. We use a teacher with policy
transfer, source task reward signal, and the six partially observable inputs.
The learning curve of the agent trained directly on the task is labeled with
”None”.

####  4.2.7 Generality of Agents

We compare the generality of agents trained with curriculum learning with
agents trained in a single environment. To measure the generality, we evaluate
the agent at the end of training on five different random seeds for 100
episodes on each environment in the task-set $\mathcal{V}$. After the
evaluation, we calculate the total mean return and the percentage of
environments solved with five random seeds and report the median of both
measurements in table 4.7.

Agents trained with curriculum learning are more general than agents trained
in a single environment. With every teacher, we could solve more environments
than training in one environment. The agent trained solely in Empty-6x6 scored
a total mean return of 3.25. Most of the obtained reward is received in the
easy Empty environment family. Some environments are especially useful to
generalize to other environments. The FourRooms and MultiRoom-N2-S4
environment solve a high percentage of environments.

Environment trained on | Total mean return | % environments solved
---|---|---
Empty-5x5 | 2.1 | 33%
Empty-6x6 | 3.25 | 28%
Empty-8x8 | 0.32 | 22%
Empty-16x16 | 0.02 | 6%
FourRooms | 2.41 | 56%
DoorKey-5x5 | 1.89 | 28%
DoorKey-6x6 | 2.58 | 39%
DoorKey-8x8 | 1.0 | 44%
DoorKey-16x16 | 0.6 | 39%
MultiRoom-N2-S4 | 1.48 | 56%
MultiRoom-N4-S5 | 0.66 | 39%
MultiRoom-N6-S10 | 0.99 | 33%
KeyCorridor-S3R1 | 0.47 | 28%
KeyCorridor-S3R2 | 0.53 | 28%
KeyCorridor-S3R3 | 0.32 | 22%
KeyCorridor-S4R3 | 0.21 | 11%
KeyCorridor-S5R3 | 0.11 | 11%
KeyCorridor-S6R3 | 0.72 | 28%
Curriculum RH | 2.64 | 56%
Curriculum PTR | 4.14 | 61%
Curriculum LP | 3.9 | 61%
Curriculum ALP | 3.06 | 67%
Curriculum EMA | 3.93 | 61%
Curriculum FS-EMA | 3.59 | 61%
Table 4.7: We report the median measurements obtained by evaluating each agent
with five random seed for 100 episodes on every environment in $\mathcal{V}$.

###  4.3 Google Football Environment

Google Research Football environment [Kurach et al., 2019] is a novel 3D RL
environment to provide a highly optimized, stochastic, and open-source
simulation. The environment provides single-agent RL, where the agent controls
all players of his team, and multi-agent RL, where a separate agent controls
each player. It is also possible to research the effect of self-play, where
the agent plays against different versions of itself. The environment provides
a comprehensive set of progressively more demanding and diverse scenarios with
the Football Academy. These scenarios enable us to analyze our algorithm on a
range of tasks requiring different levels of abstractions and different
tactics.

The engine implements a full 11 vs. 11 football game with the standard rules
including goal kicks, corner kicks, yellow and red cards, offsides, handballs,
and penalty kicks as shown in fig. 4.11. This full 11 vs. 11 football game,
consisting of 3000 frames, is called Football Benchmark.

Players have different characteristics like speed or accuracy, but both teams
have the same set of players. Further, players are getting tired over time,
which influences their behavior and skills.

Figure 4.11: The Google Football Engine is a football simulation which
supports the major football rules like kickoffs (top left), goals (top right),
fouls, cards (bottom left), corner and penalty kicks (bottom right), and
offside. [Kurach et al., 2019]

####  4.3.1 State & Observations

There are three ways to represent the environment state at the current time
step to the reinforcement learning agent (called observation).

pixel. The representation is a 1280 x 720 x 3 tensor corresponding to the
rendered screen. The scoreboard and a mini-map at the bottom of the image are
present in this representation. The mini-map tells the location of the ball
and the players of both teams.

Super Mini Map (SMM). The SMM is a 72 x 96 x 4 tensor encoding information
about both teams, the ball, and the currently active player. The encoding is
binary and indicates whether there is a player or the ball at the given
coordination or not.

Floats. This representation uses a 115-dimensional vector to capture the game
state, player coordinates, ball coordinates, possession, and the active
player.

####  4.3.2 Actions

The agent can execute one of 20 actions per time step. The currently active
player executes all of those actions, except the keeper rush action. The
active player moves by selecting one of eight dedicated moving actions. There
are four different ways to kick the ball (short pass, high pass, long pass,
shot). The move, sprint, and dribble actions are sticky and have to be ended
explicitly by their respective stop action. Finally, there are sliding and do-
nothing actions.

####  4.3.3 Rewards

The environment provides two different reward functions to choose from. It is
also possible to define custom reward functions to look into reward shaping.
In this work, we used the out-of-the-box reward functions.

SCORING rewards the agent when scoring a goal with a +1 reward and a -1 reward
when conceding one. This reward signal is sparse and can lead to no signal
during the early stages of learning where the agent does not know how to
overcome the opponent’s defense.

CHECKPOINT is an additional shaped reward designed to overcome the sparsity of
the SCORING reward signal. Once per episode, the agent receives a +0.1 reward
for getting closer to the opponent’s goal measured by the Euclidean distance.
The opponent’s field is divided into ten checkpoint regions, and the agent
receives the +0.1 reward once for every region. The agent also receives all
non-collected checkpoint rewards when scoring to avoid penalizing agents that
do not go through all the checkpoints before scoring.

####  4.3.4 Football Academy Scenarios

In addition to the full 11 vs. 11 football game, the environment allows agents
to train on a set of 11 progressively more complex scenarios. This set of
tasks is called Football Academy where it is possible to define custom
scenarios to train agents for a particular situation. In table 4.8 the
available scenarios are described.

Name |  Description
---|---
Empty Goal Close |  Our player starts inside the box with the ball and needs to score against an empty goal.
Empty Goal |  Our player starts in the middle of the field with the ball and needs to score against an empty goal.
Run to Score |  Our player starts in the middle of the field with the ball and needs to score against an empty goal. Five opponent players chase ours from behind.
Pass and Shoot with Keeper |  Two of our players try to score from the edge of the box. One is on the side with the ball and next to a defender. The other is at the center, unmarked and facing the opponent keeper.
Run, Pass and Shoot with Keeper |  Two of our players try to score from the edge of the box. One is on the side with the ball and unmarked. The other is at the center, next to a defender, and facing the opponent keeper.
Easy Counter-Attack |  4 versus 1 counter-attack with keeper; all the remaining players of both teams run back towards the ball.
Hard Counter-Attack |  4 versus 2 counter-attack with keeper; all the remaining players of both teams run back towards the ball.
11 versus 11 with Lazy Opponents |  Full 11 versus 11 game, where the opponents cannot move but intercept the ball if it is close enough to them. Our center-back defender has the ball at first. The maximum duration of the episode is 3000 frames instead of 400 frames.
11 versus 11 easy |  Full 11 versus 11 game, with a duration of 3000 frames per episode. The game starts with a kick-off, the team starting with the kick-off is assigned randomly. The agent receives a reward of -1 when receiving a goal and a reward of +1 when scoring one. The opponents difficulty is set to easy.
11 versus 11 medium |  Same as 11 versus 11 easy, but the opponents difficulty is set to medium.
11 versus 11 hard |  Same as 11 versus 11 easy, but the opponents difficulty is set to hard.
Table 4.8: Description of the Google Football environments taken directly from
Kurach et al. [2019]. All scenarios end after 400 frames, or if the ball is
lost, a team scores or the game stops (e.g., if the ball leaves the pitch or a
free kick is awarded).

####  4.3.5 MDP Statement

##### The Google research Football

environment does not fulfill the Markov property if we only consider the pixel
input at time step $t$ as observation $o_{t}$. We do not know in which
direction the ball or the players are moving from a single observation. It is
possible to have two identical observations, but in one observation, the ball
moves to the left of the pitch, and in the other, it moves to the right. The
direction and the velocity of the ball can not be inferred based on a single
image. The agent only partially observes its environment’s state, making it a
partially observable Markov decision process (POMDP).

There are a few possibilities to overcome this issue:

  * •

We can use another state representation than pixels. This representation would
have to encode the direction and velocity of the ball and the players.

  * •

We can use a long short-term memory (LSTM) [Hochreiter and Schmidhuber, 1997]
inside the agents function approximator. The observation $o_{t}$ together with
the hidden state of the LSTM $h_{t}$ are enough to overcome the uncertainty
about the current state $s_{t}$ of the environment.

  * •

We can use the last $k$ observations to approximate the true state $s_{t}$.
This is the solution proposed by Mnih et al. [2015].

In our work, we used the last four observations stacked on top of each other,
illustrated in fig. 4.12, as input to approximate the true Markov state.

Figure 4.12: To approximate the Markov property we use a frame stack of the
last 4 frames as an input for our neural networks.

###  4.4 Google Football Experiments

####  4.4.1 Experimental Setup

The experimental setup for the Google Football environment is similar to the
grid world environment. As in grid world, we train the teacher agent for
$1^{\prime}000$ steps, and for each teacher step, we train the student agent
for $10^{\prime}000$ steps in the selected environment. The student agent is
therefore trained for 10 million steps in total. After each step, we evaluate
the student on all environments in $\mathcal{V}$ for 100 episodes. In our
previous work [Schraner, 2020], we train the student agent for 50 million
steps. Due to a limit in computational resources, we limit the training in
this thesis to 10 million student steps and only one random seed per
experiment. Executing one experiment with the described amount of steps takes
around five days. We fixed the knowledge transfer to policy transfer and used
the source task reward signal. The hyperparameters are reported in section
A.3. We use all Google Football environments listed in table 4.8. The student
agent receives the SCORING reward signal.

##### Network architecture

The network architecture for the teacher agent is described in section 3.2.4.
The student’s network architecture is the same as in our previous work
[Schraner, 2020] and depicted in fig. 4.13.

Figure 4.13: CNN network architecture with the stacked Super Mini Map
observation as input. The one-hot encoded previous action $a_{t-1}$ is used as
an additional input. The policy and value function are two heads sharing the
network torso.

Actor-critic algorithms can share the network torso and represent the policy
and value function as individual heads. This allows weight sharing between the
two function approximators. Sharing weights can improve the training time and
forces the shared part to be more general. This may prevent over-fitting. As
we share network weights, we get different gradients from different loss
functions. In our work, we made use of sharing weights.

Each network uses the SMM observation, with a shape of $72\times 96\times 4$.
The football field has a dimension of $72\times 96$, and there is a separate
channel for each team, the ball, and the currently active player. To
approximate the Markov property, we use a frame stack of the last four frames,
as shown in fig. 4.12.

####  4.4.2 Results

We transfer the best CMDP teacher settings from the MiniGrid environment to
the Google Research Football environment. The four baseline methods and our
results in our previous work are used to compare the results in table 4.9. We
report the average return of 100 episodes per environment after training on
one random seed. Therefore the results should be interpreted with care.

The LP and Thompson baseline are by far the worst. In the case of Thompson
sampling, only one out of eleven environments were solved. The LP teacher
fails for the 11 vs. 11 full game. Sampling environments uniformly works well
on easy environments but fails for more challenging ones such as the counter-
attack and 11 vs. 11 environments. The window baseline is the strongest of all
baselines. With our proposed teacher-student setting we surpass our baselines
on all environments. The LP based teacher had the best results on empty goal
close, empty goal and run to score, but the improvement over the other
experiments is marginal.

Compared to the results in our previous work [Schraner, 2020] reported in
table 4.10 we do not match the results. Training optimized PPO for 50 million
steps leads to a return of -1.4 in the 11 vs. 11 hard environment. The highest
score we obtained in this environment was -1.45 with the window baseline and
LP teacher. Using a manually defined curriculum, we archive a return between
-2.08 and 1, depending on the curriculum.

Environment / Metric Uniform LP Thompson Window RH PTR LP ALP EMA FS-EMA Total
mean return -3.26 -11.62 -2.67 -0.81 -0.3 -0.28 -0.5 1.84 -1.36 -1.51 %
environments solved 45% 27% 9% 55% 55% 64% 45% 45% 45% 45% Empty Goal Close
0.99 1 -0.05 1 0.96 0.98 1 0.94 0.79 1 Empty Goal 0.84 1 0.64 0.93 0.85 0.67
0.98 0.93 0.6 0.76 Run to Score 0.88 0.98 0.0 0.76 0.95 0.7 0.05 0.98 0.67
0.91 Pass and Shoot with Keeper 0.12 0.0 -0.02 0.0 0.33 0.03 0.0 0.51 0.0
-0.07 Run, Pass and Shoot with Keeper 0.02 0.0 0.0 0.0 -0.11 -0.02 0.0 0.05
0.0 -0.17 Easy Counter-Attack 0.0 -0.02 0.0 0.23 0.33 0.17 0.0 0.0 0.02 0.0
Hard Counter-Attack 0.0 0.0 0.0 0.22 0.18 0.05 0.03 0.0 -0.05 0.02 11 vs. 11
lazy 0.0 -0.1 0.0 0.05 0.0 0.02 0.16 0.0 0.12 0.08 11 vs. 11 easy -1.55 -3.8
-0.55 -0.53 -0.42 0.0 0.0 -0.23 -0.85 -0.55 11 vs. 11 medium -1.98 -5.28 -1.48
-1.23 -1.75 -1.2 -1.08 -0.65 -1.58 -1.78 11 vs. 11 hard -2.63 -4.98 -1.5 -1.45
-1.88 -1.85 -1.45 -1.7 -1.9 -1.7

Table 4.9: Google football results obtained on one random seed after training
for 1’000 CMDP steps, equal to 10 million student steps. The average return
over 100 episodes is reported. We use policy transfer between the source tasks
and the source task reward signal.

Using the ALP, RH, PTR, and LP observation types leads to the best results.
Whereas using ALP gives the highest total average and PTR the highest number
of solved environments. The EMA-based teachers fall behind, probably due to a
not-tuned $\alpha$ value for the Google Football environments.

Experiment | Return
---|---
PPO | -1.4
Best scenarios curriculum | -0.85
Best 11 vs 11 curriculum | -2.08
Best increasing curriculum | -0.48
Best smooth increasing curriculum | 1
Prioritized level replay | -1.05