# Wang-Sun Formula in $\overrightarrow{GL}(\mathbb{Z}/2k\mathbb{Z})$

Octavio A. Agustín-Aquino  Universidad Tecnológica de la Mixteca. Carretera a
Acatlima Km 2.5 s/n. Huajuapan de León, Oaxaca, México, C. P. 69000.
<EMAIL_ADDRESS>
(Date: 29 July 2022)

###### Abstract.

Wang and Sun proved a certain summatory formula involving derangements and
primitive roots of the unit. We study such a formula but for the particular
case of the set of affine derangements in
$\overrightarrow{GL}(\mathbb{Z}/2k\mathbb{Z})$ and its subset of involutive
affine derangements in particular; in this last case its value is relatively
simple and it is related to even unitary divisors of $k$.

###### Key words and phrases:

Derangements, involutions, affine general linear group, roots of unity

###### 2020 Mathematics Subject Classification:

11A07, 11A25, 05A19, 20B35

##  1\. Introduction

In [5], for $n>1$ an odd integer and $\zeta$ a $n$-th primitive root of unity,
Wang and Sun proved that

$\sum_{\pi\in
D(n-1)}\mathrm{sign}(\pi)\prod_{j=1}^{n-1}\frac{1+\zeta^{j-\pi(j)}}{1-\zeta^{j-\pi(j)}}=(-1)^{\frac{n-1}{2}}\frac{((n-2)!!)^{2}}{n}$

where $D(n-1)$ is the set of all derangements within $S_{n-1}$.

For the mathematical theory of counterpoint it is not the whole of $S_{n-1}$
as important as it is the general affine linear group

$\overrightarrow{GL}(\mathbb{Z}/2k\mathbb{Z}):=\\{e^{u}.v\\}_{u\in\mathbb{Z}/2k\mathbb{Z},v\in\mathbb{Z}/2k\mathbb{Z}^{\times}}.$

where an element $e^{u}.v\in\overrightarrow{GL}(\mathbb{Z}/2k\mathbb{Z})$ maps
$x\in\mathbb{Z}/2k\mathbb{Z}$ to

$e^{u}.v(x)=vx+u.$

We are interested not only in plain derangements but in particular in those
that are involutive, i.e., they are their own inverses. Affine involutive
derangements are called _quasipolarities_ , and its set within
$\overrightarrow{GL}(\mathbb{Z}/2k\mathbb{Z})$ will be denoted with $Q_{k}$.
They are important because they relate consonances ($K$) and dissonances ($D$)
in $2k$-tone equal temperaments; more precisely, if
$\mathbb{Z}/2k\mathbb{Z}=K\sqcup D$ and $q$ is a quasipolarity, then it is the
unique affine morphism such that $q(K)=D$ (see [3] for details).

The structure of the article is as follows: first we prove the sum for
quasipolarities in Section 2. Then we calculate using code in Maxima some
values of the sum for derangements in
$\overrightarrow{GL}(\mathbb{Z}/2k\mathbb{Z})$ in Section 3 and finally we
make some remarks in Section 4.

##  2\. The case of quasipolarities

Note first that all quasipolarities have the same sign as permutations, so we
can disregard it in the original Wang-Sun formula.

######  Theorem 1.

If $k$ is odd and $\zeta$ a $2k$-th primitive root of unity, then

$\sum_{\pi\in
Q_{k}}\prod_{j=0}^{n-1}\frac{1+\zeta^{j-\pi(j)}}{1-\zeta^{j-\pi(j)}}=0.$

###### Proof.

Whenever $j-\pi(j)=k$ then

$1+\zeta^{j-\pi(j)}=1+\zeta^{k}=1-1=0,$

thus it suffices to prove that this happens for any quasipolarity
$\pi=e^{u}.v\in Q_{k}$ for some $0\leq j\leq 2k-1$. From [1, Theorem 3.1], we
know that

(1) $u=\sigma(v)q+\frac{2k}{\tau(v)}$

where $\sigma(v)=\gcd(v-1,2k)$, $\tau(v)=\gcd(v+1,2k)$ and $q$ is any integer.
Now, we want to show that there is a $j$ such that

$j-\pi(j)=j-e^{u}.v(j)=(1-v)j-u\equiv k\pmod{2k},$

which is possible if, and only if, $\gcd(1-v,2k)\backslash(k+u)$. In other
words, if and only if $\sigma(v)\backslash(k+u)$. Using (1), this can be
rewritten as

$\sigma(v)\backslash\left(k+\sigma(v)q+\frac{2k}{\tau(v)}\right)$

for some integer $q$. Thus, if we can show that the congruence

$\sigma(v)x\equiv k-\frac{2k}{\tau(v)}\pmod{2k}$

has a solution for $x$, then we will be done. Indeed, $\sigma(v)=2I_{1}$ and
$\tau(v)=2I_{2}$ for some $I_{1},I_{2}$ odd and coprime divisors of $k$. The
linear Diophantine equation

$2x+2\left(\frac{k}{I_{1}}\right)y=\left(\frac{k}{I_{1}}-\frac{k}{I_{1}I_{2}}\right)$

has a solution since the GCD of the the coefficients on the left is $2$ and
the number on the right is even. Hence, if $(x,y)$ is a solution, then

$2I_{1}x+\frac{k}{I_{2}}-k=\sigma(v)x+\frac{2k}{\tau(v)}-k=2ky$

which shows that $x$ is the required solution. ∎

Table 1. Results of the evaluation of the sum $S$ of Theorem 1 for some values of $k$. $k$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$
---|---|---|---|---|---|---|---|---|---|---
$S$ | $0$ | $4$ | $0$ | $8$ | $0$ | $8$ | $0$ | $12$ | $0$ | $16$

While this result was relatively easy to conjecture considering a few values
of the sum for some $k$ (as they can be seen in Table 1), it is less easy to
make a guess for the sum when $k$ is even, but the following seems reasonable.

######  Conjecture 1.

If $\zeta$ is a $2k$-th primitive root of unity, then

$\sum_{\pi\in
Q_{k}}\prod_{j=0}^{n-1}\frac{1+\zeta^{j-\pi(j)}}{1-\zeta^{j-\pi(j)}}=\sum_{\pi\in
Q_{k}}\prod_{j=0}^{n-1}[j-\pi(j)\neq k].$

The search of the sequence $4,8,8,12$ in the Online Encyclopedia of Integer
Sequences (OEIS) [4] yields as first result A054785, which is the difference
of the sum of divisors of $2n$ and $n$. The values match up to $k=16$, but
they differ at $k=18$, where the former is $20$ and the later is $26$.
Nonetheless, the results from [2] lead us in the right direction. We need some
definitions first.

######  Definition 1.

A divisor $d$ of $n$ is said to be _unitary_ if $d\perp n/d$; we denote that
$d$ is a unitary divisor of $n$ with $d\,\backslash\\!\backslash n$. We have
the sum of unitary divisors function

$s_{1}^{*}(n)=\sum_{d\,\backslash\\!\backslash n}d.$

In [2] it is proved that

$|Q_{k}|=s_{1}^{*}(k).$

Now we can make Conjecture 1 more precise.

######  Theorem 2.

If $\zeta$ is a $2k$-th primitive root of unity, then

$\sum_{\pi\in
Q_{k}}\prod_{j=0}^{n-1}\frac{1+\zeta^{j-\pi(j)}}{1-\zeta^{j-\pi(j)}}=[2\backslash
k](|Q_{2k}|-|Q_{k}|)=[2\backslash k](s_{1}^{*}(2k)-s_{1}^{*}(k)).$

###### Proof.

We have already proved the case when $k$ is odd, so suppose $k$ is even. If
$\pi=e^{u}.v\in Q_{k}$ and $j-\pi(j)\nequiv k\pmod{2k}$ so the summand
associated to $\pi$ is not $0$, then we require the congruence

(2) $(v-1)j\equiv k-u\pmod{2k}$

to have no solutions for $j$; this happens if and only if
$\sigma(v)\medslash\\!\\!\\!\\!\\!\backslash(k-u)$. Again, because of [1,
Theorem 3.1], we have $\sigma(v)=\frac{4k}{\tau(v)}$ and
$u=\sigma(v)q+\frac{2k}{\tau(v)}$. Hence (2) has no solutions if and only if

(3)
$\sigma(v)\medslash\\!\\!\\!\\!\\!\backslash\left(\frac{\sigma(v)\tau(v)}{4}+\sigma(v)q+\frac{\sigma(v)}{2}\right).$

We know $\sigma(v)=2I_{1}$ and $\tau(v)=2I_{2}$ where $I_{1}\perp I_{2}$.
Moreover

$2k=\frac{\sigma(v)\tau(v)}{2}=\frac{4I_{1}I_{2}}{2}=2I_{1}I_{2}$

thus $I_{1}$ and $I_{2}$ are unitary divisors of $k$. By [2, Proposition 2.3],
we know that both $I_{1}$ and $I_{2}$ represent involutions of
$\mathbb{Z}/2k\mathbb{Z}$. If $I_{1}$ is odd, then $I_{2}>0$ is even and the
associated involution defines $\frac{2k}{\sigma(v)}=I_{2}$ quasipolarities. In
particular, $2I_{1}=\sigma(v)$ divides $k$. Furthermore, $\tau(v)$ is
divisible by $4$ and $\sigma(v)$ does not divide $\sigma(v)/2$, thus (3)
holds. Conversely, if (3) is true then $I_{2}$ has to be even for otherwise

$\frac{1}{2}\sigma(v)(2s+1)+\tfrac{1}{2}\sigma(v)=\sigma(v)(s+1)$

which contradicts (3).

For every $\pi=e^{u}.v$ with its linear part $v$ represented by an even
unitary divisor of $k$ and every $0\leq j\leq 2k-1$, we claim that there is an
$\ell$ such that $(j-\pi(j))-(\ell-\pi(\ell))\equiv k\pmod{2k}$, for this is
equivalent to

$(v-1)\ell\equiv k-(v-1)j\pmod{2k}.$

Since $\sigma(v)\backslash k$ and $\sigma(v)\backslash(1-v)$, it implies that
there exist a solution $\ell$. Therefore, for a summand indexed by $\pi$ such
that $j-\pi(j)\neq k$ for every $0\leq j\leq 2k-1$ and has a factor
$1+\zeta^{j-\pi(j)}$ in the denominator, it also has a factor

$1-\zeta^{\ell-\pi(\ell)}=1-\zeta^{j-\pi(j)+k}=1-\zeta^{j-\pi(j)}\zeta^{k}=1+\zeta^{j-\pi(j)}$

in the numerator, so all the factors cancel out and the summand equals $1$.

Thus we have to sum the number of even unitary divisors of $k$. This is
accomplished by $s_{1}^{*}(2k)-s_{1}^{*}(k)$ because

$\displaystyle s_{1}^{*}(2k)-s_{1}^{*}(k)$
$\displaystyle=\sum_{d\,\backslash\\!\backslash 2k,d\text{
even}}d+\sum_{d\,\backslash\\!\backslash 2k,d\text{
odd}}d-\sum_{d\,\backslash\\!\backslash k,d\text{
even}}d-\sum_{d\,\backslash\\!\backslash k,d\text{ odd}}d$
$\displaystyle=2\sum_{d\,\backslash\\!\backslash k,d\text{
even}}d+\sum_{d\,\backslash\\!\backslash k,d\text{
odd}}d-\sum_{d\,\backslash\\!\backslash k,d\text{
even}}d-\sum_{d\,\backslash\\!\backslash k,d\text{ odd}}d$
$\displaystyle=\sum_{d\,\backslash\\!\backslash k,d\text{ even}}d.\qed$

##  3\. The case of the derangements of the general affine group

Let us denote the derangements within
$\overrightarrow{GL}(\mathbb{Z}/2k\mathbb{Z})$ with $\Delta_{k}$. The
following code in Maxima calculates

$S=\sum_{\pi\in\Delta_{k}}\mathrm{sign}(\pi)\prod_{j=0}^{n-1}\frac{1+\zeta^{j-\pi(j)}}{1-\zeta^{j-\pi(j)}}$

for the particular case of $k=4$.

    load("combinatorics");
    S:0;
    kk:4;
    zeta: exp(%pi*%i/kk);
    ZZ:[];
    L:[];
    for k1:0 thru (2*kk-1) do ZZ:append(ZZ,[k1]);
    for u:0 thru (2*kk-1) do
     (for v:1 thru (2*kk-1) step 2 do
      (if (gcd(v^2,2*kk)=1) then
       (
        M:mod(v*ZZ+u-ZZ,2*kk),
        if(not(product(M[l],l,1,2*kk)=0)) then
         L:append(L,[[u,v]])
       )
      )
     )$
    for k1:1 thru length(L) do
     (P: (-1)^perm_parity(mod(L[k1][2]*ZZ+L[k1][1],2*kk)+1),
      for k2:0 thru (2*kk-1) do
       P: trigrat(P*(1+zeta^(k2-mod(L[k1][2]*k2+L[k1][1],2*kk)))
       /(1-zeta^(k2-mod(L[k1][2]*k2+L[k1][1],2*kk)))),
      S:ratsimp(S+P)
     )$

As far as my computer’s memory and simplification capacity of Maxima allow, we
calculated $S$ for $k=3,\ldots,9$ _mutatis mutandis_. The results are
contained in Table 2. Except for the sign and the prime factors of $k$ in the
denominator, no other pattern is evident and searches in the OEIS do not point
yet in a meaningful direction.

Table 2. Results of the execution of the code. $k$ | $S$
---|---
$6$ | $1456/27$
$8$ | $-2300$
$10$ | $762256/5$
$12$ | $-10643506432/729$
$14$ | $13444304416/7$
$16$ | $-332995177452$
$18$ | $1450048309488389824/19683$

##  4\. Some final remarks

An interesting outcome of Theorem 1, from the musicological viewpoint, is that
for $2k$-tone equal temperaments with $k$ even, there is always a
quasipolarity such that a consonance and a dissonance are separated by a
_tritone_ (which always corresponds to $k$).

When $k$ is odd, the proof of Theorem 2 tells us that Wang-Sun sum counts
quasipolarities represented by even unitary divisors along the direction of
[2], so it suggest that we should explore more deeply the relationship between
the two concepts and its musicological implications.

For the Wang-Sun sum over all affine derangements we could not prove or
conjecture a general formula, and thus we stress the non-triviality of
studying it for derangements within subgroups.

## Acknowledgments

I deeply thank José Hernández Santiago at Universidad Autónoma de Guerrero for
his help completing the proof of Theorem 1.

## References

  * [1] O. A. Agustín-Aquino.  Antichains and counterpoint dichotomies.  Contributions to Discrete Mathematics, 7(2):97–104, 2012.
  * [2] O. A. Agustín-Aquino.  Prime injections and quasipolarities.  Le Matematiche, 69(1):159–168, 2014.
  * [3] O. A. Agustín-Aquino, J. Junod, and G. Mazzola.  Computational Counterpoint Worlds.  Springer, 2015.
  * [4] N. J. A. Sloane.  The On-Line Encyclopedia of Integer Sequences.  Published electronically at http://oeis.org, 2022.
  * [5] H. Wang and Z.-W. Sun.  Proof of a conjecture involving derangements and roots of unity, 2022\.  arXiv:2206.02589.


# I Know What You Would Like to Drink:
Benefits and Detriments of Sharing Personal Info
with a Bartender Robot

Alessandra Rossi*, Vito Giura**, Carmine Di Leva**, Silvia Rossi  University
of Naples Federico IINaplesItaly
*{alessandra.rossi<EMAIL_ADDRESS>**{vi.giura<EMAIL_ADDRESS>
###### Abstract.

This paper introduces benefits and detriments of a robot bartender that is
capable of adapting the interaction with human users according to their
preferences in drinks, music, and hobbies. We believe that a personalised
experience during a human-robot interaction increases the human user’s
engagement with the robot and that such information will be used by the robot
during the interaction. However, this implies that the users need to share
several personal information with the robot. In this paper, we introduce the
research topic and our approach to evaluate people’s perceptions and
consideration of their privacy with a robot. We present a within-subject study
in which participants interacted twice with a robot that firstly had not any
previous info about the users, and, then, having a knowledge of their
preferences. We observed that less than 60% of the participants were not
concerned about sharing personal information with the robot.

Personalised HRI, social robotics, multi-modal interaction, long-lasting
collaborations, privacy

##  1\. Introduction

Nowadays, service robots have been employed in different public environments,
such as restaurants, fairs, museums, and hospitals. An application context for
service robots that is particularly challenging is the bartending domain
(Petrick and Foster, 2013). A robot deployed in human populated environments
needs not only to be able to successfully complete a task, but also to show
socially intelligence to enhance its interaction with a robot (Salem et al.,
2013). Bartender robots need to manipulate objects, and actively engage
customers by personalising the interactions in order to make them more
pleasant and long-lasting.

Such robots need to acquire a wide range of information regarding their users
(e.g. personal details, preferred drinks, hobbies, habits) in order to adapt
their behaviours to the human users’ needs and preferences. This information
can be used to suggest preferred or new drinks and personalise the interaction
with music and topics to be verbally introduced while preparing them. However,
while privacy issues can be addressed by encrypting the data collected or when
possible reducing the amount of data stored (Basharat et al., 2012; Fung et
al., 2010), users remain very concerned of sharing such data (Vitale et al.,
2018; Syrdal et al., 2007). Moreover, since the data could be used to
personalise the interaction in a public space, this could produce a breach of
confidentiality. These might consequently affect negatively users’ interaction
with a robot. In this work, we present an exploratory study to investigate
whether people’s perception of privacy affects their willingness to sharing
personal information with a robot bartender.

##  2\. Approach

The focus of this study was to evaluate the impact of a personalised
interaction with a robot to build a long-term relationship between people and
a service robot. In particular, we were interested in the people’s perception
of privacy when sharing personal information with a robot.

The study was organised as a within-subject experimental design. We conducted
an online video study where each participant watched two different
interactions with the robot. The first time, the robot bases its interaction
with the participants without having any previous information of the user.
During the second interaction, the robot personalises the interaction
according to the information collected during the first interaction.

In the video, an actor used a magnetic card to register and, later, to be
recognised by the robot, and, finally, simulated the payment for a drink. The
actor interacted with a robotic arm using voice commands.

###  2.1. Procedure

Actors were given a magnetic card and asked to swipe it on a RFID reader.
During their first interaction with the robot, the actors were able to
register their personal information (i.e. name, age, gender), and preferences
(i.e. drinks, hobbies and music genre) using a computer to be used for
personalising the second interaction. Then, they were able to order a drink
from the robot by speech using an external microphone connected through
Bluetooth to the robot. The participant’s chosen drink is also stored in their
magnetic card to be used during the second interaction.

During the second interaction, actors were recognised swiping their magnetic
card, and the robot suggested preparing the last ordered drink for them while
playing a song from their favourite music genre. The robot also engaged
participants by talking with them about their favourite hobbies.

In both interactions, the graphical application on the computer was designed
to improve the interaction using colours that convey serenity and calm to the
user (O’Connor, 2011). We also decided to use a simple robotic arm with a
synthetic voice to be able to meet user expectations. While people are
becoming very familiar with virtual assistant AI technologies, such as Amazon
Alexa111Amazon Alexa https://www.amazon.com, their expectation of robot
capabilities have also raised. However, the absence of the robot’s ability to
sense and respond to the user’s actions and intentions had been a limiting
factor in the success of an HRI, it specifically affects people’s trust, in
the robot (Rossi et al., 2020). For this reason, we decided to use a simple
robotic arm that is able to speak to the user and prepare a drink.

At the end of each interaction, we asked participants to complete a short
questionnaire.

###  2.2. Measures

Participants were asked whether they had any previous experience of
interaction with robots. Moreover, we asked participants to confirm that they
were truly involved in the study by asking them which was the cocktail
suggested by the robot, and finally ordered by the actor.

At the end of each video, participants were asked to evaluate the usability,
the level of sympathy, security and intelligence of the robot. In particular,
we asked the participants to rate their perception of privacy by providing
personal information to the robot.

###  2.3. Participants

We recruited 78 participants (45 male, 33 female), aged between 17 and 59
years (avg. 25.7%, dev. std. 6.90%). Three participants failed the engagement
test, i.e. those who gave more than one wrong answer thus identified as not
paying very much attention to the study, which can be expected in an online
survey (Berinsky et al., 2011). We, therefore, decided to exclude them from
further analysis.

##  3\. Results

The majority of participants (74.4%) declared to have never had any experience
with a robot, while the remaining had some interactions with robots. These
participants also stated to have medium-high expectations of the robot’s
capabilities, expectations that were also confirmed for the 56% of
participants, and increased for the 40% of participants after the second
interaction.

We observed that 50.7% participants would have preferred to be served by a
robot with more human-like appearances, while only the 20% was content of the
proposed robot’s appearance. This might be due to the fact that a robot with
human-like physical features might be perceived to be more intelligent than
one without (Lohse et al., 2008; Rossi et al., 2018).

57.3% of participants rated to be comfortable providing sensible information
to the robot, the 25.3% were uncomfortable to share the personal information,
and the remaining were neither comfortable nor uncomfortable.

Finally, we observed that participants felt safe to interact with the robot
with average ratings 3.77 over a scale from 1 (very unsafe) to 5 (very safe).

##  4\. Future works / Conclusions

Our main research interest is focused on investigating how to deploy a service
robot that is able to engage users in a dynamic and unsupervised interaction.
In particular, we are interested in investigating how a long-term interactive
relationship can be established and preserved between human users and a
service robot personalising people’s experience and adapting the robot’s
behaviours to people’s needs and requests. The results presented in this study
will serve as preliminary study to further investigate people’s willingness to
share personal information with a robot to have a personalised experience with
a robot. We will also further investigate how the robot’s appearance affects
people’s perception of the robot and their willingness to share information.

##  5\. Acknowledgments

This work has been supported by Italian PON I&C 2014-2020 within the BRILLO
research project “Bartending Robot for Interactive Long Lasting Operations”,
no. F/190066/01-02/X44.

## References

  * (1)
  * Basharat et al. (2012) Iqra Basharat, F. Azam, and Abdul Wahab Muzaffar. 2012\.  Database Security and Encryption: A Survey Study.  _International Journal of Computer Applications_ 47 (2012), 28–34.
  * Berinsky et al. (2011) Adam Berinsky, Gregory Huber, and Gabriel Lenz. 2011\.  Using Mechanical Turk as a Subject Recruitment Tool for Experimental Research.  20 (11 2011).
  * Fung et al. (2010) Benjamin C. M. Fung, Ke Wang, Rui Chen, and Philip S. Yu. 2010\.  Privacy-Preserving Data Publishing: A Survey of Recent Developments.  _ACM Comput. Surv._ 42, 4 (2010).
  * Lohse et al. (2008) Manja Lohse, Frank Hegel, and Britta Wrede. 2008.  Domestic applications for social robots: an online survey on the influence of appearance and capabilities.
  * O’Connor (2011) Zena O’Connor. 2011\.  Colour psychology and colour therapy: Caveat emptor.  _Color Research & Application_ 36, 3 (2011), 229–234.  https://doi.org/10.1002/col.20597
  * Petrick and Foster (2013) Ronald P. A. Petrick and Mary Ellen Foster. 2013.  Planning for Social Interaction in a Robot Bartender Domain. In _Proceedings of the Twenty-Third International Conference on International Conference on Automated Planning and Scheduling_ (Rome, Italy) _(ICAPS’13)_. AAAI Press, 389–397.
  * Rossi et al. (2020) A. Rossi, K. Dautenhahn, K. Lee Koay, and M. L. Walters. 2020.  How Social Robots Influence People’s Trust in Critical Situations. In _2020 29th IEEE International Conference on Robot and Human Interactive Communication (RO-MAN)_. 1020–1025.  https://doi.org/10.1109/RO-MAN47096.2020.9223471
  * Rossi et al. (2018) Silvia Rossi, Mariacarla Staffa, and Anna Tamburro. 2018\.  Socially Assistive Robot for Providing Recommendations: Comparing a Humanoid Robot with a Mobile Application.  _International Journal of Social Robotics_ 10, 2 (2018), 265–278.  https://doi.org/10.1007/s12369-018-0469-4
  * Salem et al. (2013) Maha Salem, Friederike Eyssel, Katharina Rohlfing, Stefan Kopp, and Frank Joublin. 2013.  To Err is Human(-like): Effects of Robot Gesture on Perceived Anthropomorphism and Likability.  _International Journal of Social Robotics_ 5, 3 (01 Aug 2013), 313–323.
  * Syrdal et al. (2007) Dag Sverre Syrdal, Michael Walters, Nuno Otero, Kheng Koay, and Kerstin Dautenhahn. 2007.  ”He knows when you are sleeping” - Privacy and the personal robot companion.  (01 2007), 28–33.
  * Vitale et al. (2018) Jonathan Vitale, Meg Tonkin, Sarita Herse, Suman Ojha, Jesse Clark, Mary-Anne Williams, Xun Wang, and William Judge. 2018\.  Be More Transparent and Users Will Like You: A Robot Privacy and User Experience Design Experiment. In _Proceedings of the 2018 ACM/IEEE International Conference on Human-Robot Interaction_ _(HRI ’18)_. Association for Computing Machinery, New York, NY, USA, 379–387.


# Improving Generalization in Meta Reinforcement Learning using Learned
Objectives

Louis Kirsch, Sjoerd van Steenkiste, Jürgen Schmidhuber
The Swiss AI Lab IDSIA, USI, SUPSI
{louis, sjoerd<EMAIL_ADDRESS>

###### Abstract

Biological evolution has distilled the experiences of many learners into the
general learning algorithms of humans. Our novel meta reinforcement learning
algorithm _MetaGenRL_ is inspired by this process. _MetaGenRL_ distills the
experiences of many complex agents to meta-learn a low-complexity neural
objective function that decides how future individuals will learn. Unlike
recent meta-RL algorithms, _MetaGenRL_ can generalize to new environments that
are entirely different from those used for meta-training. In some cases, it
even outperforms human-engineered RL algorithms. _MetaGenRL_ uses off-policy
second-order gradients during meta-training that greatly increase its sample
efficiency.

##  1 Introduction

The process of evolution has equipped humans with incredibly general learning
algorithms. They enable us to solve a wide range of problems, even in the
absence of a large number of related prior experiences. The algorithms that
give rise to these capabilities are the result of _distilling_ the collective
experiences of many learners throughout the course of natural evolution. By
essentially _learning from learning experiences_ in this way, the resulting
knowledge can be compactly encoded in the genetic code of an individual to
give rise to the general learning capabilities that we observe today.

In contrast, Reinforcement Learning (RL) in artificial agents rarely proceeds
in this way. The learning rules that are used to train agents are the result
of years of human engineering and design, (e.g. Williams (1992); Wierstra et
al. (2008); Mnih et al. (2013); Lillicrap et al. (2016); Schulman et al.
(2015a)). Correspondingly, artificial agents are inherently limited by the
ability of the designer to incorporate the right inductive biases in order to
learn from previous experiences.

Several works have proposed an alternative framework based on _meta
reinforcement learning_ (Schmidhuber, 1994; Wang et al., 2016; Duan et al.,
2016; Finn et al., 2017; Houthooft et al., 2018; Clune, 2019). Meta-RL
distinguishes between learning to act in the environment (the reinforcement
learning problem) and learning to learn (the meta-learning problem). Hence,
learning itself is now a learning problem, which in principle allows one to
leverage prior learning experiences to meta-learn _general_ learning rules
that surpass human-engineered alternatives. However, while prior work found
that learning rules could be meta-learned that generalize to slightly
different environments or goals (Finn et al., 2017; Plappert et al., 2018;
Houthooft et al., 2018), generalization to _entirely different_ environments
remains an open problem.

In this paper we present _MetaGenRL_ 111Code is available at
http://louiskirsch.com/code/metagenrl, a novel meta reinforcement learning
algorithm that meta-learns learning rules that generalize to entirely
different environments. MetaGenRL is inspired by the process of natural
evolution as it distills the experiences of many agents into the parameters of
an objective function that decides how future individuals will learn. Similar
to Evolved Policy Gradients (EPG; Houthooft et al. (2018)), it meta-learns low
complexity neural objective functions that can be used to train complex agents
with many parameters. However, unlike EPG, it is able to meta-learn using
second-order gradients, which offers several advantages as we will
demonstrate.

We evaluate MetaGenRL on a variety of continuous control tasks and compare to
RL2 (Wang et al., 2016; Duan et al., 2016) and EPG in addition to several
human engineered learning algorithms. Compared to RL2 we find that MetaGenRL
does not overfit and is able to train randomly initialized agents using meta-
learned learning rules on _entirely different_ environments. Compared to EPG
we find that MetaGenRL is more sample efficient, and outperforms significantly
under a fixed budget of environment interactions. The results of an ablation
study and additional analysis provide further insight into the benefits of our
approach.

##  2 Preliminaries

##### Notation

We consider the standard MDP Reinforcement Learning setting defined by a tuple
$e=(S,A,P,\rho_{0},r,\gamma,T)$ consisting of states $S$, actions $A$, the
transition probability distribution $P:S\times A\times S\to\mathbb{R}_{+}$, an
initial state distribution $\rho_{0}:S\to\mathbb{R}_{+}$, the reward function
$r:S\times A\to[-R_{max},R_{max}]$, a discount factor $\gamma$, and the
episode length $T$. The objective for the probabilistic policy
$\pi_{\phi}:S\times A\to\mathbb{R}_{+}$ parameterized by $\phi$ is to maximize
the expected discounted return:

$\mathbb{E}_{\tau}[\sum_{t=0}^{T-1}\gamma^{t}r_{t}],\ \text{where}\
s_{0}\sim\rho_{0}(s_{0}),\ a_{t}\sim\pi_{\phi}(a_{t}|s_{t}),\ s_{t+1}\sim
P(s_{t+1}|s_{t},a_{t}),r_{t}=r(s_{t},a_{t}),$ (1)

with $\tau=(s_{0},a_{0},r_{0},s_{1},...,s_{T-1},a_{T-1},r_{T-1})$.

##### Human Engineered Gradient Estimators

A popular gradient-based approach to maximizing Equation 1 is REINFORCE
(Williams, 1992). It directly differentiates Equation 1 with respect to $\phi$
using the likelihood ratio trick to derive gradient estimates of the form:

$\nabla_{\phi}\mathbb{E}_{\tau}[L_{REINF}(\tau,\pi_{\phi})]:=\mathbb{E}_{\tau}[\nabla_{\phi}\sum_{t=0}^{T-1}\log\pi_{\phi}(a_{t}|s_{t})\cdot\sum_{t^{\prime}=t}^{T-1}\gamma^{t^{\prime}-t}r_{t^{\prime}})].$
(2)

Although this basic estimator is rarely used in practice, it has become a
building block for an entire class of policy-gradient algorithms of this form.
For example, a popular extension from Schulman et al. (2015b) combines
REINFORCE with a Generalized Advantage Estimate (GAE) to yield the following
policy gradient estimator:

$\nabla_{\phi}\mathbb{E}_{\tau}[L_{GAE}(\tau,\pi_{\phi},V)]:=\mathbb{E}_{\tau}[\nabla_{\phi}\sum_{t=0}^{T-1}\log\pi_{\phi}(a_{t}|s_{t})\cdot
A(\tau,V,t)].$ (3)

where $A(\tau,V,t)$ is the GAE and $V:S\to\mathbb{R}$ is a value function
estimate. Several recent other extensions include TRPO (Schulman et al.,
2015a), which discourages bad policy updates using trust regions and iterative
off-policy updates, or PPO (Schulman et al., 2017), which offers similar
benefits using only first order approximations.

##### Parametrized Objective Functions

In this work we note that many of these human engineered policy gradient
estimators can be viewed as specific implementations of a general objective
function $L$ that is differentiated with respect to the policy parameters:

$\nabla_{\phi}\mathbb{E}_{\tau}[L(\tau,\pi_{\phi},V)].$ (4)

Hence, it becomes natural to consider a generic parametrization of $L$ that,
for various choices of parameters $\alpha$, recovers some of these estimators.
In this paper, we will consider _neural objective functions_ where
$L_{\alpha}$ is implemented by a neural network. Our goal is then to optimize
the parameters $\alpha$ of this neural network in order to give rise to a new
learning algorithm that best maximizes Equation 1 on an entire class of
(different) environments.

##  3 Meta-Learning Neural Objectives

Figure 1: A schematic of _MetaGenRL_. On the left a population of agents
($i\in 1,\ldots,N$), where each member consist of a critic $Q^{(i)}_{\theta}$
and a policy $\pi^{(i)}_{\phi}$ that interact with a particular environment
$e^{(i)}$ and store collected data in a corresponding replay buffer $B^{(i)}$.
On the right a meta-learned neural objective function $L_{\alpha}$ that is
shared across the population. Learning (dotted arrows) proceeds as follows:
Each policy is updated by differentiating $L_{\alpha}$, while the critic is
updated using the usual TD-error (not shown). $L_{\alpha}$ is meta-learned by
computing second-order gradients that can be obtained by differentiating
through the critic.

In this work we propose _MetaGenRL_ , a novel meta reinforcement learning
algorithm that meta-learns neural objective functions of the form
$L_{\alpha}(\tau,\pi_{\phi},V)$. MetaGenRL makes use of value functions and
second-order gradients, which makes it more sample efficient compared to prior
work (Duan et al., 2016; Wang et al., 2016; Houthooft et al., 2018). More so,
as we will demonstrate, MetaGenRL meta-learns objective functions that
generalize to vastly different environments.

Our key insight is that a differentiable critic $Q_{\theta}:S\times
A\to\mathbb{R}$ can be used to measure the effect of locally changing the
objective function parameters $\alpha$ based on the quality of the
corresponding policy gradients. This enables a population of agents to use and
improve a single parameterized objective function $L_{\alpha}$ through
interacting with a set of (potentially different) environments. During
evaluation (meta-test time), the meta-learned objective function can then be
used to train a randomly initialized RL agent in a new environment.

###  3.1 From DDPG to Gradient-Based Meta-Learning of Neural Objectives

We will formally introduce MetaGenRL as an extension of the DDPG actor-critic
framework (Silver et al., 2014; Lillicrap et al., 2016). In DDPG, a
parameterized critic of the form $Q_{\theta}:S\times A\to\mathbb{R}$
transforms the non-differentiable RL reward maximization problem into a myopic
value maximization problem for any $s_{t}\in S$. This is done by alternating
between optimization of the critic $Q_{\theta}$ and the (here deterministic)
policy $\pi_{\phi}$. The critic is trained to minimize the TD-error by
following:

$\nabla_{\theta}\sum_{(s_{t},a_{t},r_{t},s_{t+1})}(Q_{\theta}(s_{t},a_{t})-y_{t})^{2},\
\text{where}\ y_{t}=r_{t}+\gamma\cdot
Q_{\theta}(s_{t+1},\pi_{\phi}(s_{t+1})),$ (5)

and the dependence of $y_{t}$ on the parameter vector $\theta$ is ignored. The
policy $\pi_{\phi}$ is improved to increase the expected return from arbitrary
states by following the gradient
$\nabla_{\phi}\sum_{s_{t}}Q_{\theta}(s_{t},\pi_{\phi}(s_{t}))$. Both gradients
can be computed entirely off-policy by sampling trajectories from a replay
buffer.

MetaGenRL builds on this idea of differentiating the critic $Q_{\theta}$ with
respect to the policy parameters. It incorporates a parameterized objective
function $L_{\alpha}$ that is used to improve the policy (i.e. by following
the gradient $\nabla_{\phi}L_{\alpha}$), which adds one extra level of
indirection: The critic $Q_{\theta}$ improves $L_{\alpha}$, while $L_{\alpha}$
improves the policy $\pi_{\phi}$. By first differentiating with respect to the
objective function parameters $\alpha$, and then with respect to the policy
parameters $\phi$, the critic can be used to measure the effect of updating
$\pi_{\phi}$ using $L_{\alpha}$ on the estimated return222In case of a
probabilistic policy $\pi_{\phi}(a_{t}|s_{t})$ the following becomes an
expectation under $\pi_{\phi}$ and a reparameterizable form is required
(Williams, 1988; Kingma & Welling, 2014; Rezende et al., 2014). Here we focus
on learning deterministic target policies.:

$\nabla_{\alpha}Q_{\theta}(s_{t},\pi_{\phi^{\prime}}(s_{t})),\ \text{where}\
\phi^{\prime}=\phi-\nabla_{\phi}L_{\alpha}(\tau,x(\phi),V).$ (6)

This constitutes a type of second order gradient
$\nabla_{\alpha}\nabla_{\phi}$ that can be used to meta-train $L_{\alpha}$ to
provide better updates to the policy parameters in the future. In practice we
will use batching to optimize Equation 6 over multiple trajectories $\tau$.

$p(e)$ a distribution of environments

$P\Leftarrow\\{(e_{1}\sim
p(e),\phi_{1},\theta_{1},B_{1}\leftarrow\varnothing),\ldots\\}$
$\triangleright$ Randomly initialize population of agents

Randomly initialize objective function $L_{\alpha}$

while $L_{\alpha}$ has not converged do

for $e,\phi,\theta,B\in P$ do $\triangleright$ For each agent $i$ in parallel

if extend replay buffer $B$ then

Extend $B$ using $\pi_{\phi}$ in $e$

Sample trajectories from $B$

Update critic $Q_{\theta}$ using TD-error

Update policy by following $\nabla_{\phi}L_{\alpha}$

Compute objective function gradient $\Delta_{i}$ for agent $i$ according to
Equation 6

Sum gradients $\sum_{i}\Delta_{i}$ to update $L_{\alpha}$

Algorithm 1 MetaGenRL: Meta-Training

Similarly to the policy-gradient estimators from Section 2, the objective
function $L_{\alpha}(\tau,x(\phi),V)$ receives as inputs an episode trajectory
$\tau=(s_{0:T-1},a_{0:T-1},r_{0:T-1})$, the value function estimates $V$, and
an auxiliary input $x(\phi)$ (previously $\pi_{\phi}$) that can be
differentiated with respect to the policy parameters. The latter is critical
to be able to differentiate with respect to $\phi$ and in the simplest case it
consists of the action as predicted by the policy. While Equation 6 is used
for meta-learning $L_{\alpha}$, the objective function $L_{\alpha}$ itself is
used for policy learning by following
$\nabla_{\phi}L_{\alpha}(\tau,x(\phi),V)$. See Figure 1 for an overview.
MetaGenRL consists of two phases: During meta-training, we alternate between
critic updates, objective function updates, and policy updates to meta-learn
an objective function $L_{\alpha}$ as described in Algorithm 1. During meta-
testing in Algorithm 2, we take the learned objective function $L_{\alpha}$
and keep it fixed while training a randomly initialized policy in a new
environment to assess its performance.

We note that the inputs to $L_{\alpha}$ are sampled from a replay buffer
rather than solely using on-policy data. If $L_{\alpha}$ were to represent a
REINFORCE-type objective then it would mean that differentiating $L_{\alpha}$
yields _biased_ policy gradient estimates. In our experiments we will find
that the gradients from $L_{\alpha}$ work much better in comparison to a
biased off-policy REINFORCE algorithm, and to an importance-sampled unbiased
REINFORCE algorithm, while also improving over the popular on-policy REINFORCE
and PPO algorithms.

###  3.2 Parametrizing the Objective Function

We will implement $L_{\alpha}$ using an LSTM (Gers et al., 2000; Hochreiter &
Schmidhuber, 1997) that iterates over $\tau$ in reverse order and depends on
the current policy action $\pi_{\phi}(s_{t})$ (see Figure 2). At every time-
step $L_{\alpha}$ receives the reward $r_{t}$, taken action $a_{t}$, predicted
action by the current policy $\pi_{\phi}(s_{t})$, the time $t$, and value
function estimates $V_{t},V_{t+1}$333The value estimates are derived from the
Q-function, i.e. $V_{t}=Q_{\theta}(s_{t},\pi_{\phi}(s_{t}))$, and are treated
as a constant input. Hence, the gradient $\nabla_{\phi}L_{\alpha}$ can not
flow backwards through $Q_{\theta}$, which ensures that $L_{\alpha}$ can not
naively learn to implement a DDPG-like objective function. . At each step the
LSTM outputs the objective value $l_{t}$, all of which are summed to yield a
single scalar output value that can be differentiated with respect to $\phi$.
In order to accommodate varying action dimensionalities across different
environments, both $\pi_{\phi}(s_{t})$ and $a_{t}$ are first convolved and
then averaged to obtain an action embedding that does not depend on the action
dimensionality. Additional details, including suggestions for more expressive
alternatives are available in Appendix B.

By presenting the trajectory in reverse order to the LSTM (and $L_{\alpha}$
correspondingly), it is able to assign credit to an action $a_{t}$ based on
its _future_ impact on the reward, similar to policy gradient estimators. More
so, as a general function approximator using these inputs, the LSTM is in
principle able to learn different variance and bias reduction techniques, akin
to advantage estimates, generalized advantage estimates, or importance
weights444We note that in practice it is is difficult to assess whether the
meta-learned object function incorporates bias / variance reduction
techniques, especially because MetaGenRL is unlikely to recover _known_
techniques.. Due to these properties, we expect the class of objective
functions that is supported to somewhat relate to a REINFORCE (Williams, 1992)
estimator that uses generalized advantage estimation (Schulman et al., 2015b).

A test environment $e$, and an

objective function $L_{\alpha}$

Randomly initialize $\pi_{\phi}$, $V_{\theta}$, $B\leftarrow\varnothing$

while $\pi_{\phi}$ has not converged do

if extend replay buffer $B$ then

Extend $B$ using $\pi_{\phi}$ in $e$

Sample trajectories from $B$

Update $V_{\theta}$ using TD-error

Update policy by following $\nabla_{\phi}L_{\alpha}$

Algorithm 2 MetaGenRL: Meta-Testing

Figure 2: An overview of $L_{\alpha}(\tau,x(\phi),V)$.

###  3.3 Generality and Efficiency of MetaGenRL

MetaGenRL offers a general framework for meta-learning objective functions
that can represent a wide range of learning algorithms. In particular, it is
only required that both $\pi_{\phi}$ and $L_{\alpha}$ can be differentiated
w.r.t. to the policy parameters $\phi$. In the present work, we use this
flexibility to leverage population-based meta-optimization, increase sample
efficiency through off-policy second-order gradients, and to improve the
generalization capabilities of meta-learned objective functions.

##### Population-Based

A general objective function should be applicable to a wide range of
environments and agent parameters. To this extent MetaGenRL is able to
leverage the collective experience of _multiple_ agents to perform meta-
learning by using a _single_ objective function $L_{\alpha}$ shared among a
population of agents that each act in their own (potentially different)
environment. Each agent locally computes Equation 6 over a batch of
trajectories, and the resulting gradients are combined to update $L_{\alpha}$.
Thus, the relevant learning experience of each individual agent is compressed
into the objective function that is available to the entire population at any
given time.

##### Sample Efficiency

An alternative to learning neural objective functions using a population of
agents is through evolution as in EPG (Houthooft et al., 2018). However, we
expect meta-learning using second-order gradients as in MetaGenRL to be much
more sample efficient. This is due to off-policy training of the objective
function $L_{\alpha}$ and its subsequent off-policy use to improve the policy.
Indeed, unlike in evolution there is no need to train multiple randomly
initialized agents in their entirety in order to evaluate the objective
function, thus speeding up credit assignment. Rather, at any point in time,
any information that is deemed useful for future environment interactions can
directly be incorporated into the objective function. Finally, using the
formulation in Equation 6 one can measure the effects of improving the policy
using $L_{\alpha}$ for _multiple_ steps by increasing the corresponding number
of gradient steps before applying $Q_{\theta}$, which we will explore in
Section 5.2.3.

##### Meta-Generalization

The focus of this work is to learn _general_ learning rules that during test-
time can be applied to vastly different environments. A strict separation
between the policy and the learning rule, the functional form of the latter,
and training across many environments all contribute to this. Regarding the
former, a clear separation between the policy and the learning rule as in
MetaGenRL is expected to be advantageous for two reasons. Firstly, it allows
us to specify the number of parameters of the learning rule independent of the
policy and critic parameters. For example, our implementation of $L_{\alpha}$
uses only $15K$ parameters for the objective function compared to $384K$
parameters for the policy and critic. Hence, we are able to only use a short
description length for the learning rule. A second advantage that is gained is
that the meta-learner is unable to directly change the policy and must,
therefore, learn to make use of the objective function. This makes it
difficult for the meta-learner to _overfit_ to the training environments.

##  4 Related work

Among the earliest pursuits in meta-learning are meta-hierarchies of genetic
algorithms (Schmidhuber, 1987) and learning update rules in supervised
learning (Bengio et al., 1990). While the former introduced a general
framework of entire meta-hierarchies, it relied on discrete non-differentiable
programs. The latter introduced local update rules that included free
parameters, which could be learned using gradients in a supervised setting.
Schmidhuber (1993) introduced a differentiable self-referential RNN that could
address and modify its own weights, albeit difficult to learn.

Hochreiter et al. (2001) introduced differentiable meta-learning using RNNs to
scale to larger problem instances. By giving an RNN access to its prediction
error, it could implement its own meta-learning algorithm, where the weights
are the meta-learned parameters, and the hidden states the subject of
learning. This was later extended to the RL setting (Wang et al., 2016; Duan
et al., 2016; Santoro et al., 2016; Mishra et al., 2018) (here refered to as
RL2). As we show empirically in our paper, meta-learning with RL2 does not
generalize well. It lacks a clear separation between policy and objective
function, which makes it easy to overfit on training environments. This is
exacerbated by the imbalance of $O(n^{2})$ meta-learned parameters to learn
$O(n)$ activations, unlike in MetaGenRL.

Many other recent meta-learning algorithms learn a policy parameter
initialization that is later fine-tuned using a fixed reinforcement learning
algorithm (Finn et al., 2017; Schulman et al., 2017; Grant et al., 2018; Yoon
et al., 2018). Different from MetaGenRL, these approaches use second order
gradients on the same policy parameter vector instead of using a separate
objective function. Albeit in principle general (Finn & Levine, 2018), the
mixing of policy and learning algorithm leads to a complicated way of
expressing general update rules. Similar to RL2, adaptation to related tasks
is possible, but generalization is difficult (Houthooft et al., 2018).

Objective functions have been learned prior to MetaGenRL. Houthooft et al.
(2018) evolve an objective function that is later used to train an agent.
Unlike MetaGenRL, this approach is extremely costly in terms of the number of
environment interactions required to evaluate and update the objective
function. Most recently, Bechtle et al. (2019) introduced learned loss
functions for reinforcement learning that also make use of second-order
gradients, but use a policy gradient estimator instead of a Q-function.
Similar to other work, their focus is only on narrow task distributions.
Learned objective functions have also been used for learning unsupervised
representations (Metz et al., 2019), DDPG-like meta-gradients for
hyperparameter search (Xu et al., 2018), and learning from human
demonstrations (Yu et al., 2018). Concurrent to our work, Alet et al. (2020)
uses techniques from architecture search to search for viable artificial
curiosity objectives that are composed of primitive objective functions.

Li & Malik (2016; 2017) and Andrychowicz et al. (2016) conduct meta-learning
by learning optimizers that update parameters $\phi$ by modulating the
gradient of some fixed objective function $L$:
$\Delta\phi=f_{\alpha}(\nabla_{\phi}L)$ where $\alpha$ is learned. They differ
from MetaGenRL in that they only modulate the gradient of a fixed objective
function $L$ instead of learning $L$ itself.

Another connection exists to meta-learned intrinsic reward functions
(Schmidhuber, 1991a; Dayan & Hinton, 1993; Wiering & Schmidhuber, 1996; Singh
et al., 2004; Niekum et al., 2011; Zheng et al., 2018; Jaderberg et al.,
2019). Choosing
$\nabla_{\phi}L_{\alpha}=\tilde{\nabla}_{\phi}\sum_{t=1}^{T}\bar{r}_{t}(\tau)$,
where $\bar{r}_{t}$ is a meta-learned reward and $\tilde{\nabla}_{\theta}$ is
a gradient estimator (such as a value based or policy gradient based
estimator) reveals that meta-learning objective functions includes meta-
learning the gradient estimatior $\tilde{\nabla}$ itself as long as it is
expressible by a gradient $\nabla_{\theta}$ on an objective $L_{\alpha}$. In
contrast, for intrinsic reward functions, the gradient estimator
$\tilde{\nabla}$ is normally fixed.

Finally, we note that positive transfer between different tasks (reward
functions) as well as environments (e.g. different Atari games) has been shown
previously in the context of transfer learning (Kistler et al., 1997;
Parisotto et al., 2015; Rusu et al., 2016; 2019; Nichol et al., 2018) and
meta-critic learning across tasks (Sung et al., 2017). In contrast to this
work, the approaches that have shown to be successful in this domain rely
entirely on human-engineered learning algorithms.

##  5 Experiments

Table 1: Mean return across multiple seeds (MetaGenRL: 6 meta-train $\times$ 2 meta-test seeds, RL2: 6 meta-train $\times$ 2 meta-test seeds, EPG: 3 meta-train $\times$ 2 meta-test seeds) obtained by training randomly initialized agents during meta-test time on previously seen environments (cyan) and on unseen environments (brown). Boldface highlights best meta-learned algorithm. Mean returns (6 seeds) of several human-engineered algorithms are also listed. Training \Testing |  | Cheetah | Hopper | Lunar
---|---|---|---|---
Cheetah & Hopper | MetaGenRL | 2185 | 2439 | 18
| EPG | -571 | 20 | -540
| RL2 | 5180 | 289 | -479
Lunar & Cheetah | MetaGenRL | 2552 | 2363 | 258
| EPG | -701 | 8 | -707
| RL2 | 2218 | 5 | 283
Lunar & Hopper & Walker & Ant | MetaGenRL (40 agents) | 3106 | 2869 | 201
Cheetah & Lunar & Walker & Ant |  | 3331 | 2452 | -71
Cheetah & Hopper & Walker & Ant |  | 2541 | 2345 | -148
| PPO | 1455 | 1894 | 187
| DDPG / TD3 | 8315 | 2718 | 288
| off-policy REINFORCE (GAE) | -88 | 1804 | 168
| on-policy REINFORCE (GAE) | 38 | 565 | 120

We investigate the learning and generalization capabilities of MetaGenRL on
several continuous control benchmarks including _HalfCheetah (Cheetah)_ and
_Hopper_ from MuJoCo (Todorov et al., 2012), and _LunarLanderContinuous
(Lunar)_ from OpenAI gym (Brockman et al., 2016). These environments differ
significantly in terms of the properties of the underlying system that is to
be controlled, and in terms of the dynamics that have to be learned to
complete the environment. Hence, by training meta-RL algorithms on one
environment and testing on other environments they provide a reasonable
measure of out-of-distribution generalization.

In our experiments, we will mainly compare to EPG and to RL2 to evaluate the
efficacy of our approach. We will also compare to several fixed model-free RL
algorithms to measure how well the algorithms meta-learned by MetaGenRL
compare to these handcrafted alternatives. Unless otherwise mentioned, we will
meta-train MetaGenRL using 20 agents that are distributed equally over the
indicated training environments555An ablation study in Section A.3 revealed
that a large number of agents is indeed required.. Meta-learning uses clipped
double-Q learning, delayed policy & objective updates, and target policy
smoothing from TD3 (Fujimoto et al., 2018). We will allow for $600K$
environment interactions per agent during meta-training and then meta-test the
objective function for $1M$ interactions. Further details are available in
Appendix B.

###  5.1 Comparison to Prior Work

##### Evaluating on previously seen environments

We meta-train MetaGenRL on _Lunar_ and compare its ability to train a randomly
initialized agent at test-time (i.e. using the learned objective function and
keeping it fixed) to DDPG, PPO, and on- and off-policy REINFORCE (both using
GAE) across multiple seeds. 3(a) shows that MetaGenRL markedly outperforms
both the REINFORCE baselines and PPO. Compared to DDPG, which finds the
optimal policy, MetaGenRL performs only slightly worse on average although the
presence of outliers increases its variance. In particular, we find that some
meta-test agents get ‘stuck’ for some time before reaching the optimal policy
(see Section A.2 for additional analysis). Indeed, when evaluating only the
best meta-learned objective function that was obtained during meta-training
(MetaGenRL (best objective func) in 3(a)) we are able to observe a strong
reduction in variance and even better performance.

We also report results (3(a)) when meta-training MetaGenRL on both _Lunar_ and
_Cheetah_ , and compare to EPG and RL2 that were meta-trained on these same
environments666In order to ensure a good baseline we allowed for a maximum of
$100M$ environment interactions for RL2 and $1B$ for EPG, which is more than
eight / eighty times the amount used by MetaGenRL. Regarding EPG, this did
require us to reduce the total number of seeds to 3 meta-train $\times$ 2
meta-test seeds.. For MetaGenRL we were able to obtain similar performance to
meta-training on only _Lunar_ in this case. In contrast, for EPG it can be
observed that even one billion environment interactions is insufficient to
find a good objective function (in 3(a) quickly dropping below -300). Finally,
we find that RL2 reaches the optimal policy after 100 million meta-training
iterations, and that its performance is unaffected by additional steps during
testing on _Lunar_. We note that RL2 does not separate the policy and the
learning rule and indeed in a similar ‘within distribution’ evaluation, RL2
was found successful (Wang et al., 2016; Duan et al., 2016).

(a) Previously seen _Lunar_ environment.

(b) Unseen _Hopper_ environment.

Figure 3: Comparing the test-time training behavior of the meta-learned
objective functions by MetaGenRL to other (meta) reinforcement learning
algorithms. We train randomly initialized agents on (a) environments that were
encountered during training, and (b) on significantly different environments
that were unseen. Training environments are denoted by $\dagger$ in the
legend. All runs are shown with mean and standard deviation computed over
multiple random seeds (MetaGenRL: 6 meta-train $\times$ 2 meta-test seeds,
RL2: 6 meta-train $\times$ 2 meta-test seeds, EPG: 3 meta-train $\times$ 2
meta-test seeds, and 6 seeds for all others).

Table 1 provides a similar comparison for two other environments. Here we find
that in general MetaGenRL is able to outperform the REINFORCE baselines and
PPO, and in most cases (except for _Cheetah_) performs similar to DDPG777We
emphasize that the neural objective function under consideration is unable to
implement DDPG and only uses a constant value estimate (i.e.
$\nabla_{\phi}V=0$ by using gradient stopping) during meta testing.. We also
find that MetaGenRL consistently outperforms EPG, and often RL2. For an
analysis of meta-training on more than two environments we refer to Appendix
A.

##### Generalization to vastly different environments

We evaluate the same objective functions learned by MetaGenRL, EPG and the
recurrent dynamics by RL2 on _Hopper_ , which is significantly different
compared to the meta-training environments. 3(b) shows that the learned
objective function by MetaGenRL continues to outperform both PPO and our
implementations of REINFORCE, while the best performing configuration is even
able to outperform DDPG.

When comparing to related meta-RL approaches, we find that MetaGenRL is
significantly better in this case. The performance of EPG remains poor, which
was expected given what was observed on previously seen environments. On the
other hand, we now find that the RL2 baseline fails completely (resulting in a
flat low-reward evaluation), suggesting that the learned learning rule that
was previously found to be successful is in fact entirely overfitted to the
environments that were seen during meta-training. We were able to observe
similar results when using different train and test environment splits as
reported in Table 1, and in Appendix A.

###  5.2 Analysis

####  5.2.1 Meta-Training Progression of Objective Functions

Previously we focused on test-time training randomly initialized agents using
an objective function that was meta-trained for a total of $600K$ steps
(corresponding to a total of $12M$ environment interactions across the entire
population). We will now investigate the quality of the objective functions
during meta-training.

Figure 4: Meta-training with 20 agents on _Cheetah_ and _Lunar_. We test the
objective function at five stages of meta-training by using it to train three
randomly initialized agents on _Hopper_.

Figure 4 displays the result of evaluating an objective function on _Hopper_
at different intervals during meta-training on _Cheetah_ and _Lunar_.
Initially ($28K$ steps) it can be seen that due to lack of meta-training there
is only a marginal improvement in the return obtained during test time.
However, after only meta-training for $86K$ steps we find (perhaps
surprisingly) that the meta-trained objective function is already able to make
consistent progress in optimizing a randomly initialized agent during test-
time. On the other hand, we observe large variances at test-time during this
phase of meta-training. Throughout the remaining stages of meta-training we
then observe an increase in convergence speed, more stable updates, and a
lower variance across seeds.

####  5.2.2 Ablation study

(a) Meta-training on _Lunar_ & _Cheetah_

(b) Meta-testing on _Cheetah_

Figure 5: We meta-train MetaGenRL using several alternative parametrizations
of $L_{\alpha}$ on a) _Lunar_ and _Cheetah_ , and b) present results of
testing on _Cheetah_. During meta-training a representative example of a
single agent population is shown with shaded regions denoting standard
deviation across the population. Meta-test results are reported as per usual
across 6 meta-train $\times$ 2 meta-test seeds.

We conduct an ablation study of the neural objective function that was
described in Section 3.2. In particular, we assess the dependence of
$L_{\alpha}$ on the value estimates $V_{t}$,$V_{t+1}$ and on the time
component that could to some extent be learned. Other ablations, including
limiting access to the action chosen or to the received reward, are expected
to be disastrous for generalization to any other environment (or reward
function) and therefore not explored.

##### Dependence on $t$

We use a parameterized objective function of the form
$L_{\alpha}(a_{t},r_{t},V_{t},\pi_{\phi}(s_{t})|t\in 0,...,T-1)$ as in Figure
2 except that it does not receive information about the time-step $t$ at each
step. Although information about the current time-step is required in order to
learn (for example) a generalized advantage estimate (Schulman et al., 2015b),
the LSTM could in principle learn such time tracking on it own, and we expect
only minor effects on meta-training and during meta-testing. Indeed in 5(b) it
can be seen that the neural objective function performs well without access to
$t$, although it converges slower on _Cheetah_ during meta-training (5(a)).

##### Dependence on $V$

We use a parameterized objective function of the form
$L_{\alpha}(a_{t},r_{t},t,\pi_{\phi}(s_{t})|t\in 0,...,T-1)$ as in Figure 2
except that it does not receive any information about the value estimates at
time-step $t$. There exist reinforcement learning algorithms that work without
value function estimates (eg. Williams (1992); Schmidhuber & Zhao (1998)),
although in the absence of an alternative baseline these often have a large
variance. Similar results are observed for this ablation in 5(a) during meta-
training where a possibly large variance appears to affect meta-training.
Correspondingly during test-time (5(b)) we do not find any meaningful training
progress to take place. In contrast, we find that we can remove the dependence
on _one_ of the value function estimates, i.e. remove $V_{t+1}$ but keep
$V_{t}$, which during some runs even increases performance.

Figure 6: We meta-train MetaGenRL on the _LunarLander_ and _HalfCheetah_
environments using one, three, and five inner gradient steps on $\phi$. Meta-
test results are reported across 3 meta-train $\times$ 2 meta-test seeds.

####  5.2.3 Multiple gradient steps

We analyze the effect of making _multiple_ gradient updates to the policy
using $L_{\alpha}$ before applying the critic to compute second-order
gradients with respect to the objective function parameters as in Equation 6.
While in previous experiments we have only considered applying a single
update, multiple gradient updates might better capture long term effects of
the objective function. At the same time, moving further away from the current
policy parameters could reduce the overall quality of the second-order
gradients. Indeed, in Figure 6 it can be observed that using 3 gradient steps
already slightly increases the variance during test-time training on _Hopper_
and _Cheetah_ after meta-training on _LunarLander_ and _Cheetah_. Similarly,
we find that further increasing the number of gradient steps to 5 harms
performance.

##  6 Conclusion

We have presented MetaGenRL, a novel off-policy gradient-based meta
reinforcement learning algorithm that leverages a population of DDPG-like
agents to meta-learn general objective functions. Unlike related methods the
meta-learned objective functions do not only generalize in narrow task
distributions but show similar performance on entirely different tasks while
markedly outperforming REINFORCE and PPO. We have argued that this generality
is due to MetaGenRL’s explicit separation of the policy and learning rule, the
functional form of the latter, and training across multiple agents and
environments. Furthermore, the use of second order gradients increases
MetaGenRL’s sample efficiency by several orders of magnitude compared to EPG
(Houthooft et al., 2018).

In future work, we aim to further improve the learning capabilities of the
meta-learned objective functions, including better leveraging knowledge from
prior experiences. Indeed, in our current implementation, the objective
function is unable to observe the environment or the hidden state of the
(recurrent) policy. These extensions are especially interesting as they may
allow more complicated curiosity-based (Schmidhuber, 1991b; 1990; Houthooft et
al., 2016; Pathak et al., 2017) or model-based (Schmidhuber, 1990; Weber et
al., 2017; Ha & Schmidhuber, 2018) algorithms to be learned. To this extent,
it will be important to develop introspection methods that analyze the learned
objective function and to scale MetaGenRL to make use of many more
environments and agents.

## Acknowledgements

We thank Paulo Rauber, Imanol Schlag, and the anonymous reviewers for their
feedback. This work was supported by the ERC Advanced Grant (no: 742870) and
computational resources by the Swiss National Supercomputing Centre (CSCS,
project: s978). We also thank NVIDIA Corporation for donating a DGX-1 as part
of the Pioneers of AI Research Award and to IBM for donating a Minsky machine.

## References

  * Alet et al. (2020) Ferran Alet, Martin F Schneider, Tomas Lozano-Perez, and Leslie Pack Kaelbling.  Meta-learning curiosity algorithms.  In _International Conference on Learning Representations_ , 2020.
  * Andrychowicz et al. (2016) Marcin Andrychowicz, Misha Denil, Sergio Gómez Colmenarejo, Matthew W. Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando De Freitas.  Learning to learn by gradient descent by gradient descent.  In _Advances in Neural Information Processing Systems_ , pp. 3988–3996, 6 2016.
  * Ba et al. (2016) Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton.  Layer Normalization.  _arXiv preprint arXiv:1607.06450_ , 2016.
  * Bechtle et al. (2019) Sarah Bechtle, Artem Molchanov, Yevgen Chebotar, Edward Grefenstette, Ludovic Righetti, Gaurav Sukhatme, and Franziska Meier.  Meta-learning via learned loss.  _arXiv preprint arXiv:1906.05374_ , 2019.
  * Bengio et al. (1990) Yoshua Bengio, Samy Bengio, and Jocelyn Cloutier.  _Learning a synaptic learning rule_.  Université de Montréal, 1990.
  * Brockman et al. (2016) Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba.  OpenAI Gym.  _arXiv preprint arXiv:1606.01540_ , 2016.
  * Clune (2019) Jeff Clune.  AI-GAs: AI-generating algorithms, an alternate paradigm for producing general artificial intelligence.  _arXiv preprint arXiv:1905.10985_ , 2019.
  * Dayan & Hinton (1993) P Dayan and G Hinton.  Feudal Reinforcement Learning.  In D S Lippman, J E Moody, and D S Touretzky (eds.), _Advances in Neural Information Processing Systems (NIPS) 5_ , pp. 271–278. Morgan Kaufmann, 1993.
  * Duan et al. (2016) Yan Duan, John Schulman, Xi Chen, Peter L. Bartlett, Ilya Sutskever, and Pieter Abbeel.  RL^2: Fast Reinforcement Learning via Slow Reinforcement Learning.  _arXiv preprint arXiv:1611.02779_ , 2016.
  * Finn & Levine (2018) Chelsea Finn and Sergey Levine.  Meta-Learning and Universality: Deep Representations and Gradient Descent can Approximate any Learning Algorithm.  In _International Conference on Learning Representations_ , 2018.
  * Finn et al. (2017) Chelsea Finn, Pieter Abbeel, and Sergey Levine.  Model-agnostic meta-learning for fast adaptation of deep networks.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pp. 1126–1135, 2017.
  * Fujimoto et al. (2018) Scott Fujimoto, Herke van Hoof, and David Meger.  Addressing function approximation error in actor-critic methods.  _Proceedings of Machine Learning Research_ , 80:1587–1596, 2018.
  * Gers et al. (2000) Felix A Gers, Jürgen Schmidhuber, and Fred Cummins.  Learning to Forget: Continual Prediction with LSTM.  _Neural Computation_ , 12(10):2451–2471, 2000\.
  * Grant et al. (2018) Erin Grant, Chelsea Finn, Sergey Levine, Trevor Darrell, and Thomas Griffiths.  Recasting Gradient-Based Meta-Learning as Hierarchical Bayes.  In _International Conference on Learning Representations_ , 2018.
  * Ha & Schmidhuber (2018) David Ha and Jürgen Schmidhuber.  Recurrent world models facilitate policy evolution.  In _Advances in Neural Information Processing Systems_ , pp. 2450–2462, 2018.
  * Hochreiter & Schmidhuber (1997) S Hochreiter and J Schmidhuber.  Long Short-Term Memory.  _Neural Computation_ , 9(8):1735–1780, 1997.
  * Hochreiter et al. (2001) Sepp Hochreiter, A. Steven Younger, and Peter R. Conwell.  Learning to learn using gradient descent.  In _International Conference on Artificial Neural Networks_ , 2001\.
  * Houthooft et al. (2016) Rein Houthooft, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel.  VIME: Variational Information Maximizing Exploration.  In _Advances in Neural Information Processing Systems_ , pp. 1109–1117, 2016.
  * Houthooft et al. (2018) Rein Houthooft, Richard Y. Chen, Phillip Isola, Bradly C. Stadie, Filip Wolski, Jonathan Ho, and Pieter Abbeel.  Evolved Policy Gradients.  In _Advances in Neural Information Processing Systems_ , pp. 5400–5409, 2018.
  * Jaderberg et al. (2019) Max Jaderberg, Wojciech M Czarnecki, Iain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castañeda, Charles Beattie, Neil C Rabinowitz, Ari S Morcos, Avraham Ruderman, Nicolas Sonnerat, Tim Green, Louise Deason, Joel Z Leibo, David Silver, Demis Hassabis, Koray Kavukcuoglu, and Thore Graepel.  Human-level performance in 3D multiplayer games with population-based reinforcement learning.  _Science (New York, N.Y.)_ , 364(6443):859–865, 5 2019.
  * Kingma & Ba (2015) Diederik P Kingma and Jimmy Ba.  Adam: A Method for Stochastic Optimization.  In _International Conference on Learning Representations_ , 2015.
  * Kingma & Welling (2014) Diederik P Kingma and Max Welling.  Auto-Encoding Variational Bayes.  In _International Conference on Learning Representations_ , 12 2014\.
  * Kistler et al. (1997) Werner M Kistler, Wulfram Gerstner, and J Leo van Hemmen.  Reduction of the Hodgkin-Huxley equations to a single-variable threshold model.  _Neural Computation_ , 9(5):1015–1045, 1997.
  * Li & Malik (2016) Ke Li and Jitendra Malik.  Learning to Optimize.  _arXiv preprint arXiv:1606.01885_ , 2016.
  * Li & Malik (2017) Ke Li and Jitendra Malik.  Learning to Optimize Neural Nets.  _arXiv preprint arXiv:1703.00441_ , 2017.
  * Liang et al. (2018) Eric Liang, Richard Liaw, Philipp Moritz, Robert Nishihara, Roy Fox, Ken Goldberg, Joseph E Gonzalez, Michael I Jordan, and Ion Stoica.  Rllib: Abstractions for distributed reinforcement learning.  In _International Conference on Machine Learning_ , pp. 3053–3062, 2018.
  * Lillicrap et al. (2016) Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra.  Continuous control with deep reinforcement learning.  In _International Conference on Learning Representations_ , 2016.
  * Metz et al. (2019) Luke Metz, Niru Maheswaranathan, Brian Cheung, and Jascha Sohl-Dickstein.  Learning Unsupervised Learning Rules.  In _International Conference on Learning Representations_ , 3 2019\.
  * Mishra et al. (2018) Nikhil Mishra, Mostafa Rohaninejad, and Xi UC Chen Pieter Abbeel Berkeley.  A Simple Neural Attentive Meta-Learner.  In _International Conference on Learning Representations_ , 2018.
  * Mnih et al. (2013) Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller.  Playing Atari with Deep Reinforcement Learning.  _arXiv preprint arXiv:1312.5602_ , 2013.
  * Nichol et al. (2018) Alex Nichol, Vicki Pfau, Christopher Hesse, Oleg Klimov, and John Schulman Openai.  Gotta Learn Fast: A New Benchmark for Generalization in RL.  _arXiv preprint arXiv:1804.03720_ , 2018.
  * Niekum et al. (2011) Scott Niekum, Lee Spector, and Andrew Barto.  Evolution of reward functions for reinforcement learning.  In _Proceedings of the 13th annual conference companion on Genetic and evolutionary computation_ , pp. 177–178, 2011.
  * Parisotto et al. (2015) Emilio Parisotto, Jimmy Lei Ba, and Ruslan Salakhutdinov.  Actor-Mimic: Deep Multitask and Transfer Reinforcement Learning.  _arXiv preprint arXiv:1511.06342_ , 2015.
  * Pathak et al. (2017) Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell.  Curiosity-driven exploration by self-supervised prediction.  In _34th International Conference on Machine Learning, ICML 2017_ , volume 6, pp. 4261–4270, 2017.  ISBN 9781510855144.  doi: 10.1109/CVPRW.2017.70.
  * Plappert et al. (2018) Matthias Plappert, Marcin Andrychowicz, Alex Ray, Bob McGrew, Bowen Baker, Glenn Powell, Jonas Schneider, Josh Tobin, Maciek Chociej, Peter Welinder, and others.  Multi-goal reinforcement learning: Challenging robotics environments and request for research.  _arXiv preprint arXiv:1802.09464_ , 2018.
  * Rezende et al. (2014) Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra.  Stochastic Backpropagation and Approximate Inference in Deep Generative Models.  In _International Conference on Machine Learning_ , pp. 1278–1286, 2014.  ISBN 9781634393973.  doi: 10.1051/0004-6361/201527329.
  * Rusu et al. (2016) Andrei A. Rusu, Sergio Gomez Colmenarejo, Caglar Gulcehre, Guillaume Desjardins, James Kirkpatrick, Razvan Pascanu, Volodymyr Mnih, Koray Kavukcuoglu, and Raia Hadsell.  Policy Distillation.  In _International Conference on Learning Representations_ , 2016.
  * Rusu et al. (2019) Andrei A. Rusu, Dushyant Rao, Jakub Sygnowski, Oriol Vinyals, Razvan Pascanu, Simon Osindero, and Raia Hadsell.  Meta-Learning with Latent Embedding Optimization.  In _International Conference on Learning Representations_ , 7 2019\.
  * Santoro et al. (2016) Adam Santoro, Sergey Bartunov, Matthew Botvinick, Daan Wierstra, and Timothy Lillicrap.  Meta-Learning with Memory-Augmented Neural Networks.  In _International conference on machine learning_ , pp. 1842–1850, 2016.
  * Schmidhuber (1991a) J Schmidhuber.  Learning to Generate Sub-Goals for Action Sequences.  In T Kohonen, K Mäkisara, O Simula, and J Kangas (eds.), _Artificial Neural Networks_ , pp. 967–972. Elsevier Science Publishers B.V., North-Holland, 1991a.
  * Schmidhuber (1994) J Schmidhuber.  On learning how to learn learning strategies.  Technical Report FKI-198-94, Fakultät für Informatik, Technische Universität München, 1994.
  * Schmidhuber & Zhao (1998) J Schmidhuber and J Zhao.  Direct policy search and uncertain policy evaluation.  Technical Report IDSIA-50-98, IDSIA, Lugano, Switzerland, 1998.
  * Schmidhuber (1987) Jürgen Schmidhuber.  Evolutionary principles in self-referential learning. Diploma thesis, Institut für Informatik, Technische Universität München, 1987.
  * Schmidhuber (1990) Jürgen Schmidhuber.  Making the world differentiable: On Using Fully Recurrent Self-Supervised Neural Networks for Dynamic Reinforcement Learning and Planning in Non-Stationary Environments.  Technical Report FKI-126-90 (revised), Institut für Informatik, Technische Universität München, 11 1990.
  * Schmidhuber (1991b) Jürgen Schmidhuber.  A Possibility for Implementing Curiosity and Boredom in Model-Building Neural Controllers.  In J A Meyer and S W Wilson (eds.), _Proc. of the International Conference on Simulation of Adaptive Behavior: From Animals to Animats_ , pp. 222–227. MIT Press/Bradford Books, 1991b.
  * Schmidhuber (1993) Jürgen Schmidhuber.  A self-referential weight matrix.  In _Proceedings of the International Conference on Artificial Neural Networks, Amsterdam_ , pp. 446–451. Springer, 1993.
  * Schulman et al. (2015a) John Schulman, Sergey Levine, Philipp Moritz, Michael I. Jordan, and Pieter Abbeel.  Trust Region Policy Optimization.  In _International conference on machine learning_ , pp. 1889–1897, 2015a.  doi: 10.1063/1.4927398.
  * Schulman et al. (2015b) John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel.  High-Dimensional Continuous Control Using Generalized Advantage Estimation.  _arXiv preprint arXiv:1506.02438_ , 2015b.
  * Schulman et al. (2017) John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal Policy Optimization Algorithms.  _arXiv preprint arXiv:1707.06347_ , 2017.
  * Silver et al. (2014) David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller.  Deterministic policy gradient algorithms.  In _31st International Conference on Machine Learning, ICML 2014_ , volume 1, pp. 605–619, 1 2014.  ISBN 9781634393973.
  * Singh et al. (2004) Satinder Singh, Satinder Singh, A.G. Barto, A.G. Barto, Nuttapong Chentanez, and Nuttapong Chentanez.  Intrinsically motivated reinforcement learning.  _18th Annual Conference on Neural Information Processing Systems (NIPS)_ , 17:1281–1288, 2004.  ISSN 1943-0604.  doi: 10.1109/TAMD.2010.2051031.
  * Sung et al. (2017) Flood Sung, Li Zhang, Tao Xiang, Timothy Hospedales, and Yongxin Yang.  Learning to learn: Meta-critic networks for sample efficient learning.  _arXiv preprint arXiv:1706.09529_ , 2017.
  * Todorov et al. (2012) Emanuel Todorov, Tom Erez, and Yuval Tassa.  Mujoco: A physics engine for model-based control.  In _2012 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pp. 5026–5033. IEEE, 2012.
  * Wang et al. (2016) Jane X Wang, Zeb Kurth-Nelson, Dhruva Tirumala, Hubert Soyer, Joel Z Leibo, Remi Munos, Charles Blundell, Dharshan Kumaran, and Matt Botvinick.  Learning to reinforcement learn.  _arXiv preprint arXiv:1611.05763_ , 2016.
  * Weber et al. (2017) Théophane Weber, Sébastien Racanière, David P. Reichert, Lars Buesing, Arthur Guez, Danilo Jimenez Rezende, Adria Puigdomènech Badia, Oriol Vinyals, Nicolas Heess, Yujia Li, Razvan Pascanu, Peter Battaglia, David Silver, and Daan Wierstra.  Imagination-Augmented Agents for Deep Reinforcement Learning.  In _Advances in neural information processing systems_ , pp. 5690–5701, 2017.
  * Wiering & Schmidhuber (1996) M Wiering and J Schmidhuber.  HQ-Learning: Discovering Markovian Subgoals for Non-Markovian Reinforcement Learning.  Technical Report IDSIA-95-96, IDSIA, 1996.
  * Wierstra et al. (2008) Daan Wierstra, Tom Schaul, Jan Peters, and Jürgen Schmidhuber.  Natural Evolution Strategies.  In _2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence)_ , pp. 3381–3387, 2008.
  * Williams (1988) R J Williams.  On the Use of Backpropagation in Associative Reinforcement Learning.  In _IEEE International Conference on Neural Networks, San Diego_ , volume 2, pp. 263–270, 1988.
  * Williams (1992) Ronald J Williams.  Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning.  _Machine Learning_ , 8:229–256, 1992.
  * Xu et al. (2018) Zhongwen Xu, Hado Van Hasselt, and David Silver.  Meta-gradient reinforcement learning.  In _Advances in Neural Information Processing Systems_ , volume 2018-Decem, pp. 2396–2407, 5 2018.
  * Yoon et al. (2018) Jaesik Yoon, Taesup Kim, Ousmane Dia, Sungwoong Kim, Yoshua Bengio, and Sungjin Ahn.  Bayesian Model-Agnostic Meta-Learning.  In _Advances in Neural Information Processing Systems_ , pp. 7332–7342, 2018.
  * Yu et al. (2018) Tianhe Yu, Chelsea Finn, Annie Xie, Sudeep Dasari, Tianhao Zhang, Pieter Abbeel, and Sergey Levine.  One-shot imitation from observing humans via domain-adaptive meta-learning.  _International Conference on Learning Representations, Workshop Track_ , 2018.
  * Zheng et al. (2018) Zeyu Zheng, Junhyuk Oh, and Satinder Singh.  On learning intrinsic rewards for policy gradient methods.  In _Advances in Neural Information Processing Systems_ , pp. 4644–4654, 2018.

##  Appendix A Additional Results

###  A.1 All Training and Test Regimes

In the main text, we have shown several combinations of meta-training, and
testing environments. We will now show results for all combinations, including
the respective human engineered baselines.

(a) Within distribution generalization.

(b) Out of distribution generalization.

Figure 7: Comparing the test-time training behavior of the meta-learned
objective functions by MetaGenRL to other (meta) reinforcement learning
algorithms on _Hopper_. We consider within distribution testing (a), and out
of distribution testing (b) by varying the meta-training environments (denoted
by $\dagger$) for the meta-RL approaches. All runs are shown with mean and
standard deviation computed over multiple random seeds (MetaGenRL: 6 meta-
train $\times$ 2 meta-test seeds, RL2: 6 meta-train $\times$ 2 meta-test
seeds, EPG: 3 meta-train $\times$ 2 meta-test seeds, and 6 seeds for all
others).

##### Hopper

On _Hopper_ (Figure 7) we find that MetaGenRL works well, both in terms of
generalization to previously seen environments, and to unseen environments.
The PPO, REINFORCE, RL2, and EPG baselines are outperformed significantly.
Regarding RL2 we observe that it is only able to obtain reward when _Hopper_
was included during meta-training, although its performance is generally poor.
Regarding EPG, we observe some learning progress during meta-testing on
_Hopper_ after meta-training on _Cheetah_ and _Hopper_ (7(a)), although it
drops back down quickly as test-time training proceeds. In contrast, when
meta-testing on _Hopper_ after meta-training on _Cheetah_ and _Lunar_ (7(b))
no test-time training progress is observed at all.

(a) Within distribution generalization.

(b) Out of distribution generalization.

Figure 8: Comparing the test-time training behavior of the meta-learned
objective functions by MetaGenRL to other (meta) reinforcement learning
algorithms on _Cheetah_. We consider within distribution testing (a), and out
of distribution testing (b) by varying the meta-training environments (denoted
by $\dagger$) for the meta-RL approaches. All runs are shown with mean and
standard deviation computed over multiple random seeds (MetaGenRL: 6 meta-
train $\times$ 2 meta-test seeds, RL2: 6 meta-train $\times$ 2 meta-test
seeds, EPG: 3 meta-train $\times$ 2 meta-test seeds, and 6 seeds for all
others).

##### Cheetah

Similar results are observed in Figure 8 for _Cheetah_ , where MetaGenRL
outperforms PPO and REINFORCE significantly. On the other hand, it can be seen
that DDPG notably outperforms MetaGenRL on this environment. It will be
interesting to further study these differences in the future to improve the
expressibility of our approach. Regarding RL2 and EPG only within distribution
generalization results are available due to _Cheetah_ having larger
observations and / or action spaces compared to _Hopper_ and _Lunar_. We
observe that RL2 performs similar to our earlier findings on _Hopper_ but
significantly improves in terms of within-distribution generalization (likely
due to greater overfitting, as was consistently observed for other splits).
EPG shows initially more promise on within distribution generalization (8(a)),
but ends up like before.

(a) Within distribution generalization.

(b) Out of distribution generalization.

Figure 9: Comparing the test-time training behavior of the meta-learned
objective functions by MetaGenRL to other (meta) reinforcement learning
algorithms on _Lunar_. We consider within distribution testing (a), and out of
distribution testing (b) by varying the meta-training environments (denoted by
$\dagger$) for the meta-RL approaches. All runs are shown with mean and
standard deviation computed over multiple random seeds (MetaGenRL: 6 meta-
train $\times$ 2 meta-test seeds, RL2: 6 meta-train $\times$ 2 meta-test
seeds, EPG: 3 meta-train $\times$ 2 meta-test seeds, and 6 seeds for all
others).

##### Lunar

On _Lunar_ (Figure 9) we find that MetaGenRL is only marginally better
compared to the REINFORCE and PPO baselines in terms of within distribution
generalization and worse in terms of out of distribution generalization.
Analyzing this result reveals that although many of the runs train rather
well, some get stuck during the early stages of training without or only
delayed recovering. These outliers lead to a seemingly very large variance for
MetaGenRL in 9(b). We will provide a more detailed analysis of this result in
Section A.2. If we focus on the best performing objective function then we
observe competitive performance to DDPG (9(a)). Nonetheless, we notice that
the objective function trained on _Hopper_ generalizes worse to _Lunar_ ,
despite our earlier result that objective functions trained on _Lunar_ do in
fact generalize well to _Hopper_. MetaGenRL is still able to outperform both
RL2 and EPG in terms of out of distribution generalization. We do note that
EPG is able to meta-learn objective functions that are able to improve to some
extent during test time.

Table 2: Agent mean return across multiple seeds (MetaGenRL: 6 meta-train $\times$ 2 meta-test seeds, and 6 seeds for all others) for meta-test training on previously seen environments (cyan) and on unseen (different) environments (brown) compared to human engineered baselines. | Training (below) / Test (right) | Cheetah | Hopper | Lunar
---|---|---|---|---
MetaGenRL (20 agents) | Cheetah & Hopper | 2185 | 2433 | 18
| Cheetah & Lunar | 2551 | 2363 | 258
| Hopper & Lunar | 4160 | 2966 | 146
| Hopper | 3646 | 2937 | -62
| Lunar | 4366 | 2717 | 244
MetaGenRL (40 agents) | Lunar & Hopper & Walker & Ant | 3106 | 2869 | 201
| Cheetah & Lunar & Walker & Ant | 3331 | 2452 | -71
| Cheetah & Hopper & Walker & Ant | 2541 | 2345 | -148
PPO | - | 1455 | 1894 | 187
DDPG / TD3 | - | 8315 | 2718 | 288
off-policy REINFORCE (GAE) | - | -88 | 1804 | 168
on-policy REINFORCE (GAE) | - | 38 | 565 | 120

##### Comparing final scores

An overview of the final scores that were obtained for MetaGenRL in comparison
to the human engineered baselines is shown in Table 2. It can be seen that
MetaGenRL outperforms PPO and off-/on-policy REINFORCE in most configurations
while DDPG with TD3 tricks remains stronger on two of the three environments.
Note that DDPG is currently not among the representable algorithms by
MetaGenRL.

###  A.2 Stability of Learned Objective Functions

Figure 10: Meta-training with 20 agents on _LunarLander_. We meta-test the
objective function at different stages in training on the same environment.

In the results presented in Figure 9 on _Lunar_ we observed a seemingly large
variance for MetaGenRL that was due to outliers. Indeed, when analyzing the
individual runs meta-trained on _Lunar_ and tested on _Lunar_ we found that
that one of the runs converged to a local optimum early on during training and
was unable to recover from this afterwards. On the other hand, we also
observed that runs can be ‘stuck’ for a long time to then make very fast
learning progress. It suggests that the objective function may sometimes
experience difficulties in providing meaningful updates to the policy
parameters during the early stages of training.

We have further analyzed this issue by evaluating one of the objective
functions at several intervals throughout meta-training in Figure 10. From the
meta-training curve (bottom) it can be seen that meta-training in _Lunar_
converges very early. This means that from then on, updates to the objective
function will be based on mostly converged policies. As the test-time plots
show, these additional updates appear to negatively affect test-time
performance. We hypothesize that the objective function essentially ‘forgets’
about the early stages of training a randomly initialized agent, by only
incorporating information about good performing agents. A possible solution to
this problem would be to keep older policies in the meta-training agent
population or use early stopping.

Finally, if we exclude four random seeds (of 12), we indeed find a significant
reduction in the variance (and increase in the mean) of the results observed
for MetaGenRL (see Figure 11).

Figure 11: The left plot shows all 12 random seeds on the meta-test
environment _Lunar_ while the right has the 4 worst random seeds removed. The
variance is now reduced significantly.

###  A.3 Ablation of Agent Population Size and Unique Environments

In our experiments we have used a population of 20 agents during meta-training
to ensure diversity in the conditions under which the objective function needs
to optimize. The size of this population is a crucial parameter for a stable
meta-optimization. Indeed, in Figure 12 it can be seen that meta-training
becomes increasingly unstable as the number of agents in the population
decreases.

Using a similar argument, one would expect to gain from increasing the number
of distinct environments (or agents) during meta-training. In order to verify
this, we have evaluated two additional settings: Meta-training on _Cheetah &
Lunar & Walker & Ant_ with 20 and 40 agents respectively. Figure 13 shows the
result of meta-testing on _Hopper_ for these experiments (also see the final
results reported for 40 agents in Table 2). Unexpectedly, we find that
increasing the number of distinct environments does not yield a significant
improvement and, in fact, sometimes even decrease performance. One possibility
is that this is due to the simple form of the objective function under
consideration, which has no access to the environment observations to
efficiently distinguish between them. Another possibility is that MetaGenRL’s
hyperparameters require additional tuning in order to be compatible with these
setups.

Figure 12: Stable meta-training requires a large population size of at least
20 agents. Meta-training performance is shown for a single run with the mean
and standard deviation across the agent population.

Figure 13: Meta-training on _Cheetah_ , _Lunar_ , _Walker_ , and _Ant_ with 20
or 40 agents; meta-testing on the out-of-distribution _Hopper_ environment. We
compare to previous MetaGenRL configurations.

##  Appendix B Experiment Details

In the following we describe all experimental details regarding the
architectures used, meta-training, hyperparameters, and baselines. The code to
reproduce our experiments is available at
http://louiskirsch.com/code/metagenrl.

###  B.1 Neural Objective Function Architecture

##### Neural Architecture

In this work we use an LSTM to implement the objective function (Figure 2).
The LSTM runs backwards in time over the state, action, and reward tuples that
were encountered during the trajectory $\tau$ under consideration. At each
step $t$ the LSTM receives as input the reward $r_{t}$, value estimates of the
current and previous state $V_{t},V_{t+1}$, the current timestep $t$ and
finally the action that was taken at the current timestep $a_{t}$ in addition
to the action as determined by the current policy $\pi_{\phi}(s_{t})$. The
actions are first processed by one dimensional convolutional layers striding
over the action dimension followed by a reduction to the mean. This allows for
different action sizes between environments. Let
$A^{(B)}\in\mathbb{R}^{1\times D}$ be the action from the replay buffer,
$A^{(\pi)}\in\mathbb{R}^{1\times D}$ be the action predicted by the policy,
and $W\in\mathbb{R}^{2\times N}$ a learnable matrix corresponding to $N$
outgoing units, then the actions are transformed by

$\frac{1}{D}\sum_{i=1}^{D}([A^{(B)},A^{(\pi)}]^{T}W)_{i},$ (7)

where $[a,b]$ is a concatenation of $a$ and $b$ along the first axis. This
corresponds to a convolution with kernel size 1 and stride 1. Further
transformations with non-linearities can be added after applying $W$, if
necessary. We found it helpful (but not strictly necessary) to use ReLU
activations for half of the units and square activations for the other half.

At each time-step the LSTM outputs a scalar value $l_{t}$ (bounded between
$-\eta$ and $\eta$ using a scaled tanh activation), which are summed to obtain
the value of the neural objective function. Differentiating this value with
respect to the policy parameters $\phi$ then yields gradients that can be used
to improve $\pi_{\phi}$. We only allow gradients to flow backwards through
$\pi_{\phi}(s_{t})$ to $\phi$. This implementation is closely related to the
functional form of a REINFORCE (Williams, 1992) estimator using the
generalized advantage estimation (Schulman et al., 2015b).

All feed-forward networks (critic and policy) use ReLU activations and layer
normalization (Ba et al., 2016). The LSTM uses tanh activations for cell and
hidden state transformations, sigmoid activations for the gates. The input
time $t$ is normalized between $0$ at the beginning of the episode and $1$ at
the final transition. Any other hyper-parameters can be seen in Table 4.

##### Extensibility

The expressability of the objective function can be further increased through
several means. One possibility is to add the entire sequence of state
observations $o_{1:T}$ to its inputs, or by introducing a bi-directional LSTM.
Secondly, additional information about the policy (such as the hidden state of
a recurrent policy) can be provided to $L$. Although not explored in this
work, this would in principle allow one to learn an objective that encourages
certain representations to emerge, e.g. a predictive representation about
future observations, akin to a world model (Schmidhuber, 1990; Ha &
Schmidhuber, 2018; Weber et al., 2017). In turn, these could create pressure
to adapt the policy’s actions to explore unknown dynamics in the environment
(Schmidhuber, 1991b; 1990; Houthooft et al., 2016; Pathak et al., 2017).

###  B.2 Meta-Training

##### Annealing with DDPG

At the beginning of meta-training (learning $L_{\alpha}$), the objective
function is randomly initialized and thus does not make sensible updates to
the policies. This can lead to irreversibly breaking the policies early during
training. Our current implementation circumvents this issue by linearly
annealing $\nabla_{\phi}L_{\alpha}$ the first 10k timesteps ($\sim 2\%$ of all
timesteps) with DDPG $\nabla_{\phi}Q_{\theta}(s_{t},\pi_{\phi}(s_{t}))$.
Preliminary experiments suggested that an exponential learning rate schedule
on the gradient of $\nabla_{\phi}L_{\alpha}$ for the first 10k steps can
replace the annealing with DDPG. The learning rate anneals exponentially
between a learning rate of zero and 1e-3. However, in some rare cases this may
still lead to unsuccessful training runs, and thus we have omitted this
approach from the present work.

##### Standard training

During training, the critic is updated twice as many times as the policy and
objective function, similar to TD3 (Fujimoto et al., 2018). One gradient
update with data sampled from the replay buffer is applied for every timestep
collected from the environment. The gradient with respect to $\phi$ in
Equation 6 is combined with $\phi$ using a fixed learning rate in the standard
way, all other parameter updates use Adam (Kingma & Ba, 2015) with the default
parameters. Any other hyper-parameters can be seen in Table 4 and Table 4.

##### Using additional gradient steps

In our experiments (Section 5.2.3) we analyzed the effect of applying
_multiple_ gradient updates to the policy using $L_{\alpha}$ before applying
the critic to compute second-order gradients with respect to the objective
function parameters. For two updates, this gives

$\displaystyle\begin{split}\nabla_{\alpha}Q_{\theta}(s_{t},\pi_{\phi^{\dagger}}(s_{t}))&\textrm{
with
}\phi^{\dagger}=\phi^{\prime}-\nabla_{\phi^{\prime}}L_{\alpha}(\tau_{1},x(\phi^{\prime}),V)\\\
&\textrm{ and
}\phi^{\prime}=\phi-\nabla_{\phi}L_{\alpha}(\tau_{2},x(\phi),V)\end{split}$
(8)

and can be extended to more than two correspondingly. Additionally, we use
disjoint mini batches of data $\tau$: $\tau_{1},\tau_{2}$. When updating the
policy using $\nabla_{\phi}L_{\alpha}$ we continue to use only a single
gradient step.

###  B.3 Baselines

##### RL2

The implementation for RL2 mimics the paper by Duan et al. (Duan et al.,
2016). However, we were unable to achieve good results with TRPO (Schulman et
al., 2015a) on the MuJoCo environments and thus used PPO (Schulman et al.,
2017) instead. The PPO hyperparameters and implementation are taken from rllib
(Liang et al., 2018). Our implementation uses an LSTM with 64 units and does
not reset the state of the LSTM for two episodes in sequence. Resetting after
additional episodes were given did not improve training results. Different
action and observation dimensionalities across environments were handled by
using an environment wrapper that pads both with zeros appropriately.

##### EPG

We use the official EPG code base https://github.com/openai/EPG from the
original paper (Houthooft et al., 2018). The hyperparameters are taken from
the paper, $V=64$ noise vectors, an update frequency of $M=64$, and $128$
updates for every inner loop, resulting in an inner loop length of $8196$
steps. During meta-test training, we run with the same update frequency for a
total of 1 million steps.

##### PPO & On-Policy REINFORCE with GAE

We use the tuned implementations from
https://spinningup.openai.com/en/latest/spinningup/bench.html which include a
GAE (Schulman et al., 2015b) baseline.

##### Off-Policy Reinforce with GAE

The implementation is equivalent to MetaGenRL except that the objective
function is fixed to be the REINFORCE estimator with a GAE (Schulman et al.,
2015b) baseline. Thus, experience is sampled from a replay buffer. We have
also experimented with an importance weighted unbiased estimator but this
resulted in poor performance.

##### DDPG

Our implementation is based on
https://spinningup.openai.com/en/latest/spinningup/bench.html and uses the
same TD3 tricks (Fujimoto et al., 2018) and hyperparameters (where applicable)
that MetaGenRL uses.

Table 3: Architecture hyperparameters Parameter | Value
---|---
Critic number of layers | 3
Critic number of units | 350
Policy number of layers | 3
Policy number of units | 350
Objective function LSTM units | 32
Objective function action conv layers | 3
Objective function action conv filters | 32
Error bound $\eta$ | 1000

Table 4: Training hyperparameters Parameter | Value
---|---
Truncated episode length | 20
Global norm gradient clipping | 1.0
Critic learning rate $\lambda_{1}$ | 1e-3
Policy learning rate $\lambda_{2}$ | 1e-3
Second order learning rate $\lambda_{3}$ | 1e-3
Obj. func. learning rate $\lambda_{4}$ | 1e-3
Critic noise | 0.2
Critic noise clip | 0.5
Target network update speed | 0.005
Discount factor | 0.99
Batch size | 100
Random exploration timesteps | 10000
Policy gaussian noise std | 0.1
Timesteps per agent | 1M