summaries: This paper presents RAPID, an exploration algorithm for procedurally generated environments. The paper introduces an exploration scores composed of a local and global score. The local score is computed per-episode, it is the fraction of distinct states visited during an episode, the global score keeps track of the exploratory effort of the agent over the whole training procedure.

summaries: This paper presents an exploration method for procedurally-generated environments, RAPID, which imitates the past episodes that have a good exploration behavior. First, authors introduce exploration scores, local score for per-episode view of the exploration behavior, and global score for long-term and historical view of exploration. The authors use the weighted sum of these two exploration scores and extrinsic reward as a final episodic exploration score. They rank the state-action pairs based on episodic exploration score and train the agent to imitate behaviors with high score. In experiments, they show the results by comparing state-of-the-art algorithms in several procedurally-generated environments.

summaries: This paper tackles the problem of improving exploration in deep RL for procedurally-generated environments, where state-of-the-art exploration techniques typically fail. In the proposed approach, called RAPID, each agent-generated episode is evaluated with respect to its local exploration score (for the given episode), global exploration score (across all previous episodes), and extrinsic reward obtained. Episodes with high scores are stored in a replay buffer, and a policy is trained via behavioral cloning on batches of state-action pairs from this buffer. This policy is also used to produce the agent-generated episodes.

abstractText: Exploration under sparse reward is a long-standing challenge of model-free reinforcement learning. The state-of-the-art methods address this challenge by introducing intrinsic rewards to encourage exploration in novel states or uncertain environment dynamics. Unfortunately, methods based on intrinsic rewards often fall short in procedurally-generated environments, where a different environment is generated in each episode so that the agent is not likely to visit the same state more than once. Motivated by how humans distinguish good exploration behaviors by looking into the entire episode, we introduce RAPID, a simple yet effective episode-level exploration method for procedurally-generated environments. RAPID regards each episode as a whole and gives an episodic exploration score from both per-episode and long-term views. Those highly scored episodes are treated as good exploration behaviors and are stored in a small ranking buffer. The agent then imitates the episodes in the buffer to reproduce the past good exploration behaviors. We demonstrate our method on several procedurally-generated MiniGrid environments, a first-person-view 3D Maze navigation task from MiniWorld, and several sparse MuJoCo tasks. The results show that RAPID significantly outperforms the state-of-the-art intrinsic reward strategies in terms of sample efficiency and final performance. The code is available at https://github.com/daochenzha/rapid.

authors:
Pieter Abbeel
Andrew Y Ng

title: Apprenticeship learning via inverse reinforcement learning

venue: In Proceedings of the twenty-first international conference on Machine learning,

authors:
Marcin Andrychowicz
Filip Wolski
Alex Ray
Jonas Schneider
Rachel Fong
Peter Welinder
Bob McGrew
Josh Tobin
OpenAI Pieter Abbeel
Wojciech Zaremba

title: Hindsight experience replay

venue: In Advances in Neural Information Processing Systems,

authors:
Adrià Puigdomènech Badia
Pablo Sprechmann
Alex Vitvitskyi
Daniel Guo
Bilal Piot
Steven Kapturowski
Olivier Tieleman
Martin Arjovsky
Alexander Pritzel
Andrew Bolt

title: Never give up: Learning directed exploration strategies

venue: In International Conference on Learning Representations,

authors:
Marc Bellemare
Sriram Srinivasan
Georg Ostrovski
Tom Schaul
David Saxton
Remi Munos

title: Unifying count-based exploration and intrinsic motivation

authors:
Charles Blundell
Benigno Uria
Alexander Pritzel
Yazhe Li
Avraham Ruderman
Joel Z Leibo
Jack Rae
Daan Wierstra
Demis Hassabis

title: Model-free episodic control

venue: arXiv preprint arXiv:1606.04460,

authors:
Yuri Burda
Harri Edwards
Deepak Pathak
Amos Storkey
Trevor Darrell
Alexei A Efros

title: Large-scale study of curiosity-driven learning

authors:
Yuri Burda
Harrison Edwards
Amos Storkey
Oleg Klimov

title: Exploration by random network distillation

authors:
Andres Campero
Roberta Raileanu
Heinrich Küttler
Joshua B Tenenbaum
Tim Rocktäschel
Edward Grefenstette

title: Learning with amigo: Adversarially motivated intrinsic goals

venue: arXiv preprint arXiv:2006.12122,

title: gym-miniworld environment for openai gym

authors:
Maxime Chevalier-Boisvert
Lucas Willems
Suman Pal

title: Minimalistic gridworld environment for openai gym

venue: GitHub repository,

authors:
Jongwook Choi
Yijie Guo
Marcin Moczulski
Junhyuk Oh
Neal Wu
Mohammad Norouzi
Honglak Lee

title: Contingency-aware exploration in reinforcement learning

authors:
Karl Cobbe
Christopher Hesse
Jacob Hilton
John Schulman

title: Leveraging procedural generation to benchmark reinforcement learning

venue: arXiv preprint arXiv:1912.01588,

authors:
Marc-Alexandre Côté
Ákos Kádár
Xingdi Yuan
Ben Kybartas
Tavian Barnes
Emery Fine
James Moore
Matthew Hausknecht
Layla El Asri
Mahmoud Adada

title: Textworld: A learning environment for text-based games

venue: In Workshop on Computer Games,

authors:
Yali Du
Lei Han
Meng Fang
Ji Liu
Tianhong Dai
Dacheng Tao

title: Liir: Learning individual intrinsic reward in multi-agent reinforcement learning

authors:
Yan Duan
Xi Chen
Rein Houthooft
John Schulman
Pieter Abbeel

title: Benchmarking deep reinforcement learning for continuous control

venue: In International Conference on Machine Learning,

authors:
William Fedus
Prajit Ramachandran
Rishabh Agarwal
Yoshua Bengio
Hugo Larochelle
Mark Rowland
Will Dabney

title: Revisiting fundamentals of experience replay

authors:
Tanmay Gangwani
Qiang Liu
Jian Peng

title: Learning self-imitating diverse policies

authors:
Xiaoxiao Guo
Satinder Singh
Richard Lewis
Honglak Lee

title: Deep learning for reward design to improve monte carlo tree search in atari games

venue: In International Joint Conference on Artificial Intelligence,

authors:
Yijie Guo
Junhyuk Oh
Satinder Singh
Honglak Lee

title: Generative adversarial self-imitation learning

venue: arXiv preprint arXiv:1812.00950,

authors:
Yijie Guo
Jongwook Choi
Marcin Moczulski
Samy Bengio
Mohammad Norouzi
Honglak Lee

title: Efficient exploration with self-imitation learning via trajectory-conditioned policy

authors:
Peter Henderson
Riashat Islam
Philip Bachman
Joelle Pineau
Doina Precup
David Meger

title: Deep reinforcement learning that matters

venue: In AAAI Conference on Artificial Intelligence,

authors:
Matteo Hessel
Joseph Modayil
Hado Van Hasselt
Tom Schaul
Georg Ostrovski
Will Dabney
Dan Horgan
Bilal Piot
Mohammad Azar
David Silver

title: Rainbow: Combining improvements in deep reinforcement learning

authors:
Todd Hester
Matej Vecerik
Olivier Pietquin
Marc Lanctot
Tom Schaul
Bilal Piot
Dan Horgan
John Quan
Andrew Sendonaris
Gabriel Dulac-Arnold

title: Deep q-learning from demonstrations

authors:
Jonathan Ho
Stefano Ermon

title: Generative adversarial imitation learning

venue: In Advances in neural information processing systems,

authors:
Heinrich Küttler
Nantas Nardelli
Alexander H Miller
Roberta Raileanu
Marco Selvatici
Edward Grefenstette
Tim Rocktäschel

title: The nethack learning environment

venue: arXiv preprint arXiv:2006.13760,

authors:
Kwei-Herng Lai
Daochen Zha
Yuening Li
Xia Hu

title: Dual policy distillation

authors:
Timothy P Lillicrap
Jonathan J Hunt
Alexander Pritzel
Nicolas Heess
Tom Erez
Yuval Tassa
David Silver
Daan Wierstra

title: Continuous control with deep reinforcement learning

venue: arXiv preprint arXiv:1509.02971,

title: Self-improving reactive agents based on reinforcement learning, planning and teaching

venue: Machine learning,

title: Reinforcement learning for robots using neural networks

venue: Technical report, CarnegieMellon Univ Pittsburgh PA School of Computer Science,

authors:
Xiao-Yang Liu
Hongyang Yang
Qian Chen
Runjia Zhang
Liuqing Yang
Bowen Xiao
Christina Dan Wang

title: Finrl: A deep reinforcement learning library for automated stock trading in quantitative finance

authors:
Marlos C Machado
Marc G Bellemare
Michael Bowling

title: Count-based exploration with the successor representation

venue: arXiv preprint arXiv:1807.11622,

authors:
Jarryd Martin
S Suraj Narayanan
Tom Everitt
Marcus Hutter

title: Count-based exploration in feature space for reinforcement learning

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Andrei A Rusu
Joel Veness
Marc G Bellemare
Alex Graves
Martin Riedmiller
Andreas K Fidjeland
Georg Ostrovski

title: Human-level control through deep reinforcement learning

authors:
Volodymyr Mnih
Adria Puigdomenech Badia
Mehdi Mirza
Alex Graves
Timothy Lillicrap
Tim Harley
David Silver
Koray Kavukcuoglu

title: Asynchronous methods for deep reinforcement learning

authors:
Alex Nichol
Vicki Pfau
Christopher Hesse
Oleg Klimov
John Schulman

title: Gotta learn fast: A new benchmark for generalization in rl

venue: arXiv preprint arXiv:1804.03720,

authors:
Guido Novati
Petros Koumoutsakos

title: Remember and forget for experience replay

authors:
Junhyuk Oh
Yijie Guo
Satinder Singh
Honglak Lee

title: Self-imitation learning

authors:
Ian Osband
Benjamin Van Roy
Daniel J Russo
Zheng Wen

title: Deep exploration via randomized value functions

venue: Journal of Machine Learning Research,

authors:
Georg Ostrovski
Marc G Bellemare
Aäron Oord
Rémi Munos

title: Count-based exploration with neural density models

authors:
Pierre-Yves Oudeyer
Frederic Kaplan

title: What is intrinsic motivation? a typology of computational approaches

venue: Frontiers in neurorobotics,

authors:
Deepak Pathak
Pulkit Agrawal
Alexei A Efros
Trevor Darrell

title: Curiosity-driven exploration by self-supervised prediction

venue: In IEEE Conference on Computer Vision and Pattern Recognition Workshops,

authors:
Alexander Pritzel
Benigno Uria
Sriram Srinivasan
Adria Puigdomenech
Oriol Vinyals
Demis Hassabis
Daan Wierstra
Charles Blundell

title: Neural episodic control

authors:
Roberta Raileanu
Tim Rocktäschel

title: Ride: Rewarding impact-driven exploration for procedurally-generated environments

authors:
Aravind Rajeswaran
Kendall Lowrey
Emanuel V Todorov
Sham M Kakade

title: Towards generalization and simplicity in continuous control

authors:
Martin Riedmiller
Roland Hafner
Thomas Lampe
Michael Neunert
Jonas Degrave
Tom Wiele
Vlad Mnih
Nicolas Heess
Jost Tobias Springenberg

title: Learning by playing solving sparse reward tasks from scratch

authors:
Nikolay Savinov
Anton Raichuk
Damien Vincent
Raphael Marinier
Marc Pollefeys
Timothy Lillicrap
Sylvain Gelly

title: Episodic curiosity through reachability

title: A possibility for implementing curiosity and boredom in model-building neural controllers. In International conference on simulation of adaptive behavior: From animals

venue: animats,

authors:
John Schulman
Filip Wolski
Prafulla Dhariwal
Alec Radford
Oleg Klimov

title: Proximal policy optimization algorithms

venue: arXiv preprint arXiv:1707.06347,

authors:
David Silver
Aja Huang
Chris J Maddison
Arthur Guez
Laurent Sifre
George Van Den Driessche
Julian Schrittwieser
Ioannis Antonoglou
Veda Panneershelvam
Marc Lanctot

title: Mastering the game of go with deep neural networks and tree

venue: search. nature,

authors:
Rupesh Kumar Srivastava
Pranav Shyam
Filipe Mutz
Wojciech Jaśkowski
Jürgen Schmidhuber

title: Training agents using upside-down reinforcement learning

authors:
Bradly C Stadie
Sergey Levine
Pieter Abbeel

title: Incentivizing exploration in reinforcement learning with deep predictive models

venue: arXiv preprint arXiv:1507.00814,

authors:
Alexander L Strehl
Michael L Littman

title: An analysis of model-based interval estimation for markov decision processes

venue: Journal of Computer and System Sciences,

authors:
Sainbayar Sukhbaatar
Zeming Lin
Ilya Kostrikov
Gabriel Synnaeve
Arthur Szlam
Rob Fergus

title: Intrinsic motivation and automatic curricula via asymmetric self-play

authors:
Haoran Tang
Rein Houthooft
Davis Foote
Adam Stooke
OpenAI Xi Chen
Yan Duan
John Schulman
Filip DeTurck
Pieter Abbeel

title: exploration: A study of count-based exploration for deep reinforcement learning

authors:
Emanuel Todorov
Tom Erez
Yuval Tassa

title: Mujoco: A physics engine for model-based control

venue: In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems,

authors:
Tianbing Xu
Qiang Liu
Liang Zhao
Jian Peng

title: Learning to explore with meta-policy gradient

authors:
Daochen Zha
Kwei-Herng Lai
Yuanpu Cao
Songyi Huang
Ruzhe Wei
Junyu Guo
Xia Hu

title: Rlcard: A toolkit for reinforcement learning in card games

venue: arXiv preprint arXiv:1910.04376,

authors:
Daochen Zha
Kwei-Herng Lai
Kaixiong Zhou
Xia Hu

title: Experience replay optimization

authors:
Amy Zhang
Nicolas Ballas
Joelle Pineau

title: A dissection of overfitting and generalization in continuous reinforcement learning

venue: arXiv preprint arXiv:1806.07937,

authors:
Chiyuan Zhang
Oriol Vinyals
Remi Munos
Samy Bengio

title: A study on overfitting in deep reinforcement learning

venue: arXiv preprint arXiv:1804.06893,

authors:
Shangtong Zhang
Richard S Sutton

title: A deeper look at experience replay

venue: NIPS Deep Reinforcement Learning Symposium,

authors:
Zeyu Zheng
Junhyuk Oh
Satinder Singh

title: On learning intrinsic rewards for policy gradient methods

heading: 1 INTRODUCTION

text:
Deep reinforcement learning (RL) is widely applied in various domains (Mnih et al., 2015; Silver et al., 2016; Mnih et al., 2016; Lillicrap et al., 2015; Andrychowicz et al., 2017; Zha et al., 2019a; Liu et al., 2020). However, RL algorithms often require tremendous number of samples to achieve reasonable performance (Hessel et al., 2018). This sample efficiency issue becomes more pronounced in sparse reward environments, where the agent may take an extremely long time before bumping into a reward signal (Riedmiller et al., 2018). Thus, how to efficiently explore the environment under sparse reward remains an open challenge (Osband et al., 2019).
To address the above challenge, many exploration methods have been investigated and demonstrated to be effective on hard-exploration environments. One of the most popular techniques is to use intrinsic rewards to encourage exploration (Schmidhuber, 1991; Oudeyer & Kaplan, 2009; Guo et al., 2016; Zheng et al., 2018; Du et al., 2019). The key idea is to give intrinsic bonus based on uncertainty, e.g., assigning higher rewards to novel states (Ostrovski et al., 2017), or using the prediction error of a dynamic model as the intrinsic reward (Pathak et al., 2017). While many intrinsic reward methods have demonstrated superior performance on hard-exploration environments, such as Montezuma’s Revenge (Burda et al., 2018b) and Pitfall! (Badia et al., 2019), most of the previous studies use the same singleton environment for training and testing, i.e., the agent aims to solve the same environment in each episode. However, recent studies show that the agent trained in this way is susceptible to overfitting and may fail to generalize to even a slightly different environment (Rajeswaran et al., 2017; Zhang et al., 2018a). To deal with this issue, a few procedually-generated environments
are designed to test the generalization of RL, such as (Beattie et al., 2016; Chevalier-Boisvert et al., 2018; Nichol et al., 2018; Côté et al., 2018; Cobbe et al., 2019; Küttler et al., 2020), in which the agent aims to solve the same task, but a different environment is generated in each episode.
Unfortunately, encouraging exploration in procedually-generated environments is a very challenging task. Many intrinsic reward methods, such as count-based exploration and curiosity-driven exploration, often fall short in procedually-generated environments (Raileanu & Rocktäschel, 2020; Campero et al., 2020). Figure 1a shows a motivating example of why count-based exploration is less effective in procedually-generated environments. We consider a 1D grid-world, where the agent (red) needs to explore the environment to reach the goal within 7 timesteps, that is, the agent needs to move right in all the steps. While count-based exploration assigns reasonable intrinsic rewards in singleton setting, it may generate misleading intrinsic rewards in procedually-generated setting because visiting a novel state does not necessarily mean a good exploration behavior. This issue becomes more pronounced in more challenging procedually-generated environments, where the agent is not likely to visit the same state more than once. To tackle the above challenge, this work studies how to reward good exploration behaviors that can generalize to different environments.
When a human judges how well an agent explores the environment, she often views the agent from the episode-level instead of the state-level. For instance, one can easily tell whether an agent has explored a maze well by looking into the coverage rate of the current episode, even if the current environment is different from the previous ones. In Figure 1b, we can confidently tell that the episode in the right-hand-side is a good exploration behavior because the agent achieves 0.875 coverage rate. Similarly, we can safely conclude that the episode in the left-hand-side does not explore the environment well due to its low coverage rate. Motivated by this, we hypothesize that episode-level exploration score could be a more general criterion to distinguish good exploration behaviors than state-level intrinsic rewards in procedually-generated setting.
To verify our hypothesis, we propose exploration via Ranking the Episodes (RAPID). Specifically, we identify good exploration behaviors by assigning episodic exploration scores to past episodes. To efficiently learn the past good exploration behaviors, we use a ranking buffer to store the highlyscored episodes. The agent then learns to reproduce the past good exploration behaviors with imitation learning. We demonstrate that RAPID significantly outperforms the state-of-the-art intrinsic reward methods on several procedually-generated benchmarks. Moreover, we present extensive ablations and analysis for RAPID, showing that RAPID can well explore the environment even without extrinsic rewards and could be generally applied in tasks with continuous state/action spaces.

heading: 2 EXPLORATION VIA RANKING THE EPISODES

text:
An overview of RAPID is shown in Figure 2. The key idea is to assign episodic exploration scores to past episodes and store those highly-scored episodes into a small buffer. The agent then treats the episodes in the buffer as demonstrations and learns to reproduce these episodes with imitation learning. RAPID encourages the agent to explore the environment by reproducing the past good
exploration behaviors. This section introduces how we define the episodic exploration score for procedurally-generated environments and how the proposed method can be combined with state-ofthe-art reinforcement learning agents.

heading: 2.1 EPISODIC EXPLORATION SCORE

text:
Each episode is scored from both local and global perspectives. The local score is a per-episode view of the exploration behavior, which measures how well the current episode itself explores the environment. The global score provides a long-term and historical view of exploration, i.e., whether the current episode has explored the regions that are not well explored in the past. Additionally, we consider extrinsic reward, which is the episodic reward received from the environment. It is an external criterion of exploration since a high extrinsic reward often suggests good exploration in sparse environments. The overall episodic exploration score is obtained by the weighted sum of the above three scores. We expect that these scores can model different aspects of exploration behaviors and they are complementary in procedurally-generated environments.
Local Score. The intuition of the local exploration bonus is that the agent is expected to visit as many distinct states as possible in one episode. In our preliminary experiments on MiniGrid, we observe that many poor exploration episodes repeatedly visit the same state. As a result, the agent may get stuck in a well-known region but never reach out to unexplored regions. From a local view, we can quantify this exploration behavior based on the diversity of the visited states. Specifically, we define the local exploration score as
Slocal = Ndistinct Ntotal , (1)
where Ntotal is the total number of states in the episode, and Ndistinct is the number of distinct states in the episode. Intuitively, optimizing the local score will encourage the agent to reach out to the unexplored regions in the current episode. In an ideal case, the episodes that never visit the same state twice will receive a local bonus of 1. There could be various ways to extend the above definition to continuous state space. In this work, we empirically define the local score in continuous state space as the mean standard deviation of all the states in the episode:
Slocal =
∑l i=1 std(si)
l , (2)
where l is the dimension of the state, and std(si) is the standard deviation along the i-dimension of the states in the episode. Intuitively, this score encourages the episodes that visit diverse states.
Global Score. The global score is designed to model long-term exploration behavior. While a different environment will be generated in each episode in the procedurally-generated setting, the environments in different episodes usually share some common characteristics. For example, in the
Algorithm 1 Exploration via Ranking the Episodes (RAPID) 1: Input: Training steps S, buffer size D, RL rollout steps T 2: Initialize the policy πθ, replay buffer D 3: for iteration = 1, 2, ... until convergence do 4: Execute πθ for T timesteps 5: Update πθ with RL objective (also update value functions if any) 6: for each generated episode τ do 7: Compute episodic exploration score Sτ based on Eq. (4) 8: Give score Sτ to all the state-action pairs in τ and store them to the buffer 9: Rank the state-action pairs in D based on their exploration scores 10: if D.length > D then 11: Discard the state-action pairs with low scores so that D.length = D 12: end if 13: for step = 1, 2, .., S do 14: Sample a batch from D and train πθ using the data in D with behavior cloning 15: end for 16: end for 17: end for
MiniGrid MultiRoom environment (Figure 3a), although a different maze will be generated in a new episode, the basic building blocks (e.g., walls, doors, etc.), the number of rooms, and the size of each room will be similar. From a global view, the agent should explore the regions that are not well explored in the past. Motivated by count-based exploration, we define the global score as
Sglobal = 1
Ntotal ∑ s 1√ N(s) , (3)
where N(s) is the state count of s throughout the training process, that is, the global score is the mean count-based intrinsic reward of all the states in the episode.
Episodic Exploration Score. Suppose Sext is the total extrinsic reward of an episode received from the environment . The episodic exploration score is obtained by the weighted sum of the extrinsic reward Sext, the local score Slocal, and the global score Sglobal:
S = w0Sext + w1Slocal + w2Sglobal, (4) where w0, w1 and w2 are hyperparameters. We speculate that the three scores are complementary and the optimal w0, w1 and w2 could vary in different environments. For example, a higher w1 will give a higher weight to the per-episode view of exploration behavior. A higher w2 will focus more on whether the current episode has explored the past unexplored regions. Nevertheless, we find that a single set of w0, w1 and w2 works well across many tasks.
Comparison with Prior Work. Several papers have studied episode-level feedback to improve the sample efficiency of RL. To the best of our knowledge, the existing work mainly focuses on learning a meta-policy based on episodic rewards (Xu et al., 2018; Zha et al., 2019b), or imitating the episodes with high episodic rewards (Guo et al., 2018; Srivastava et al., 2019). However, in very sparse environments, it is not likely to receive a non-zero reward without exploration. These methods are not suitable for very sparse environments since episodic rewards could be always zero. In this work, we propose local and global episodic scores to quantify the exploration behaviors and encourage the agent to visit distinct states from per-episode and long-term views.

heading: 2.2 REPRODUCING PAST GOOD EXPLORATION BEHAVIORS WITH IMITATION LEARNING

text:
A straightforward idea is to treat the episodic exploration score as a reward signal and assign it to the last timestamp of the episode. In this way, the agent can be updated with any reinforcement learning objective. However, this strategy is not very effective with three potential limitations. First, the reward remains sparse so that the reinforcement learning agents may not be able to effectively exploit the reward signals. Second, the intrinsic exploration bonus may introduce bias in the objective. While the local score and global score may encourage exploration at the beginning stage, they are
not true objectives and may degrade the final performance. Third, it only uses a good episode once. In fact, many past good episodes can be exploited many times to improve sample efficiency.
To overcome the above limitations, we propose to use a small ranking buffer to store past good state-action pairs and then use imitation objective to enhance exploration. Specifically, we assign the same episodic exploration score to all the state-action pairs in an episode and rank all the stateaction pairs based on scores. In addition to the original RL objective, we employ behavior cloning, the simplest form of imitation learning, to encourage the agent to reproduce the state-action pairs in the buffer. This simple ranking buffer can effectively exploit the past good experiences since a good state-action pair could be sampled more than once. The procedure is summarized in Algorithm 1. A possible variant is to keep the entire episodes in the buffer. We have tried this idea and do not observe a clear difference between this variant and Algorithm 1 (see Appendix H for more discussions).

heading: 3 EXPERIMENTS

text: The experiments are designed to answer the following research questions: RQ1: how is RAPID compared with the state-of-the-art intrinsic reward methods on benchmark procedurally-generated environments (Section 3.2)? RQ2: how will RAPID perform if removing one of the scores (i.e., the local score, the global score, and the extrinsic reward) or the buffer (Section 3.3)? RQ3: how will the hyperparameters impact the performance of RAPID (Section 3.3)? RQ4: can RAPID explore the environment without extrinsic reward (Section 3.3)? RQ5: how will RAPID perform with larger and more challenging grid-world (Section 3.3)? RQ6: can RAPID generalize to 3D navigation task and continuous state/action space, such as MuJoCo (Section 3.4)?

heading: 3.1 ENVIRONMENTS AND BASELINES

text:
Figure 3 shows the rendering of procedurally-generated environments used in this work. Following the previous studies of exploration in procedurally-generated environments (Raileanu & Rocktäschel, 2020; Campero et al., 2020), we mainly focus on MiniGrid environments (ChevalierBoisvert et al., 2018), which provide procedurally-generated grid-worlds. We consider two types of hard exploration tasks: MultiRoom-NX-SY, where X and Y indicate the number of rooms and the room size, respectively, and KeyCorridor-SX-RY, where X and Y indicate the room size and the number of rows, respectively. A large X or Y suggests a larger environment, which will be more difficult to explore. The agent has a partial view of the environment and needs to navigate the green block or the red ball under sparse rewards. These tasks are challenging because the agent needs to explore many rooms in order to receive a reward signal so that standard RL algorithms will typically fail. To test whether RAPID can generalize to continuous state space, we consider MiniWorld Maze (Chevalier-Boisvert, 2018), whose observation space is 60 × 80 images. Similarly, the agent in MiniWorld Maze has a 3D partial view of the environment and needs to navigate the red box. The maze is procedurally-generated, i.e., a different maze will be generated in each episode. We further study RAPID in continuous state and action spaces on sparse MuJoCo tasks (Todorov et al., 2012; Brockman et al., 2016). More details of the above environments are described in Appendx B.
While exploration has been extensively studied in the literature, very few methods are designed for procedurally-generated environments. To better understand the performance of RAPID, we consider the baselines in the following categories. Traditional Methods: we consider several popular methods designed for singleton environments, including count-based exploration (COUNT) (Bellemare et al., 2016), Random Network Distillation Exploration (RANDOM) (Burda et al., 2018b),
.
and curiosity-driven exploration (CURIOSITY) (Pathak et al., 2017). Methods for ProcedurallyGenerated Environments: we consider two state-of-the-art exploration methods, including ImpactDriven Exploration (RIDE) (Raileanu & Rocktäschel, 2020), and exploration with Adversarially Motivated Intrinsic Goals (AMIGO) (Campero et al., 2020). Self-Imitation Methods: self-imitation learning (SIL) (Oh et al., 2018) also exploits past good experiences to encourage exploration. We further include PPO (Schulman et al., 2017) as a reinforcement learning baseline. All the algorithms are run the same number timesteps for a fair comparison. More details are provided in Appendix A.

heading: 3.2 MINIGRID RESULTS

text: To study RQ1, we plot the learning curves of RAPID and the baselines on MiniGrid benchmarks in Figure 4. We can make three observations. First, RAPID performs significantly better than the state-of-the-art methods designed for singleton or procedurally-generated environments in terms of sample efficiency and final performance. For example, on MultiRoom-N7-S8, RAPID is at least 10 times more sample efficient than RIDE. On KeyCorridor-S4-R3, RAPID is the only algorithm that successfully navigates the goal within 20 million timesteps. Second, the traditional intrinsic reward methods perform well on easy procedurally-generated environments but perform poorly on hardexploration tasks. For example, COUNT performs as well as RAPID on KeyCorridor-S3-R2 but fails on more challenging tasks, such as MultiRoom-N7-S8. This suggests that traditional methods may fall short in challenging procedurally-generated environments, which is consistent with the results in previous work (Raileanu & Rocktäschel, 2020). Third, RAPID outperforms SIL across all the tasks. Recall that both RAPID and SIL learn to reproduce past good experiences. While SIL reproduces experiences with high rewards, RAPID additionally considers local and global exploration scores. This verifies the effectiveness of the episodic exploration scores.

heading: 3.3 ABLATIONS AND ANALYSIS

text:
To study RQ2, we perform ablation studies on RAPID. Specifically, we remove one of the local score, the global score, and the extrinsic reward, and compare each ablation with RAPID. Besides, we consider a variant that directly uses the episodic exploration score as the reward signal without buffer. To demonstrate the effectiveness of the ranking, we further include a baseline that uses the replay buffer without ranking. Table 1 shows the results. We observe that the local score contributes the most to the performance. While most existing exploration methods reward exploration globally, the global score could be not aware of generalization, which may explain the unsatisfactory performance of COUNT and CURIOSITY. While the global score seems to play a relatively small role as compared to local score in most MiniGrid environments, it plays an important role in KeyCorridorS4-R3. A possible reason is that the local score is a too weak signal in KeyCorridor-S4-R3, and the global score may help alleviate this issue since it provides some historical information. We also observe that the agent fails in almost all the tasks without buffer or ranking. This suggests that the ranking buffer is an effective way to exploit past good exploration behaviors.
To study RQ3, we plot the learning curves with different training steps S and buffer size D in Figure 5a and 5b. We observe that larger number of training steps usually leads to faster learning speed at the beginning stage but may result in sub-optimal performance. For the buffer size, we observe that a large buffer will lead to slow learning speed with more stable performance. We speculate that there is a trade-off between learning speed and the final performance. In our experiments, we set training steps S to be 5 and buffer size D to be 10000, respectively, across all the tasks.
To investigate RQ4, we remove extrinsic rewards and show the learning curves of RAPID and the baselines in Figure 5c with the corresponding local exploration scores in Figure 5d. We make two interesting observations. First, without extrinsic rewards, RAPID can deliver reasonable performance. For example, on MultiRoom-N12-S10, RAPID achieves nearly 0.5 average return with pure exploration, compared with around 0.6 if using extrinsic rewards. We look into the episodes generated by RAPID with pure exploration and observe that, in most cases, the agent is able to reach the goal but struggles to find the optimal path to the goal. This is expected because the extrinsic reward is obtained by whether the agent can reach the goal subtracting some penalties of the timesteps spent. The extrinsic reward can encourage the agent to choose the shortest path to reach the goal. For other baselines, we observe that only RIDE and AMIGO can occasionally reach the goal. Second, we observe that some baselines, such as RIDE, are indirectly maximizing the local exploration scores. For example, we observe that the local exploration score increases for RIDE on MultiRoom-N12S10. However, the local score of RAPID drops after about 10 million timesteps. This suggests the episode-level score may better align with good exploration behaviors. A possible explanation for the superiority of RAPID is that it is designed to directly optimize episodic exploration score.
To answer RQ5, we focus on MultiRoom-NX-SY and ambitiously vary X and Y to make the environments more challenging. Specifically, we fix Y to be 4 and vary X in the left-hand-side of Figure 6, and fix X to be 4 and vary Y in the middle of Figure 6. Compared with RIDE, our RAPID delivers stronger performance on more challenging mini-worlds.

heading: 3.4 MINIWORLD MAZE AND SPARSE MUJOCO RESULTS

text: For RQ6, the learning curves on 3D Maze are shown in the right-hand-side of Figure 6. RAPID performs significantly better than the baselines. We also conduct experiments on a subset of sparse MuJoCo tasks (Figure 7). The results show that RAPID improves over PPO and SIL. Interestingly, RAPID achieves more than 200 average return on Swimmer, which surpasses some previous results reported on the dense reward counterpart (Duan et al., 2016; Henderson et al., 2018; Lai et al., 2020). Note that the MuJoCo environments are singleton. We use these environments solely to test whether RAPID can deal with continuous state/action spaces. We have also tried adapting Swimmer to be procedurally-generated and observe similar results (Appendix I)

heading: 4 RELATED WORK

text:
Count-Based and Curiosity-Driven Exploration. These two classes of intrinsic motivations are the most popular and proven to be effective in the literature. Count-based exploration encourages the agent to visit the novel states, which is first studied in tabular setting (Strehl & Littman, 2008) and has been recently extended to more complex state space (Bellemare et al., 2016; Ostrovski et al., 2017; Tang et al., 2017; Martin et al., 2017; Machado et al., 2018; Osband et al., 2019). Curiositydriven exploration learns the environment dynamics to encourage exploration (Stadie et al., 2015; Pathak et al., 2017; Sukhbaatar et al., 2018; Burda et al., 2018a). However, these methods are designed for singleton environments and often struggle to generalize to procedurally-generated environments (Raileanu & Rocktäschel, 2020).
Exploration for Procedurally-Generated Environments. Several recent studies have discussed the generalization of reinforcement learning (Rajeswaran et al., 2017; Zhang et al., 2018a;b; Choi et al., 2018) and designed procedurally-generated environments to test the generalization of reinforcement learning (Beattie et al., 2016; Nichol et al., 2018; Küttler et al., 2020). More recent papers show that traditional exploration methods fall short in procedurally-generated environments and address this issue with new exploration methods (Raileanu & Rocktäschel, 2020; Campero et al., 2020). This work studies a new perspective of exploration bonus in episode-level and achieves significantly better performance than the previous methods on procedurally-generated benchmarks.
Experience Replay Buffer and Self-Imitation Learning. Experience replay mechanism is widely used and is initially designed to stabilize deep reinforcement learning (Lin, 1992; 1993; Mnih et al., 2015; Zhang & Sutton, 2017; Zha et al., 2019b; Fedus et al., 2020). Self-Imitation Learning extends the experience replay buffer and uses it to store past good experiences (Oh et al., 2018; Guo et al., 2018; 2019; Gangwani et al., 2018). However, Self-Imitation only exploits highly rewarded experiences and thus is not suitable for very sparse environments. Our work incorporates local and global scores to encourage past good exploration behaviors in sparse procedurally-generated environments.
Episodic Memory. Inspired by the episodic memory of the animals, some studies propose to use episodic memory to enhance sample efficiency (Blundell et al., 2016; Pritzel et al., 2017). The key idea is to memorize and replay the good episodic experiences. More recently, episodic mem-
ory is used to generate intrinsic rewards to guide exploration (Savinov et al., 2018). Never Give Up (NGU) (Badia et al., 2019) further considers local and global novelties in the intrinsic rewards. Our work differs from NGU in that we approach the sample efficiency from a different angle by treating each episode as a whole and using a ranking mechanism to select good experiences. Thus, good experiences can be exploited multiple times to improve sample efficiency.

heading: 5 LIMITATIONS AND DISCUSSIONS

text:
RAPID is designed to study our hypothesis that imitating episode-level good exploration behaviors can encourage exploration in procedurally-generated environments. In the presented algorithm, we have made some simple choices. In order to make RAPID more competitive to the state-of-the-art methods in more complicated environments, in this section, we highlight some limitations of RAPID and the potential research directions.
First, in our work, the local and global scores are mainly calculated on low-dimensional state space. We have not yet tested the scores on more complex procedurally-generated environments, such as ProcGen benchmark (Cobbe et al., 2019), TextWorld (Côté et al., 2018), and NetHack Learning Environment (Küttler et al., 2020), some of which require high-dimensional image inputs. In this context, count-based scores may not be well-suited. Learning the state embedding (Raileanu & Rocktäschel, 2020) and pseudo-counts (Bellemare et al., 2016; Ostrovski et al., 2017) could be the potential ways to address this issue. Moreover, high extrinsic rewards may not necessarily mean good exploration behaviors in these environments. The applicability of RAPID in these environments needs future research efforts.
Second, the ranking buffer greedily selects the highly-reward state-action pairs, which is the key to boosting the performance. However, with this greedy strategy, some highly-ranked state-action pairs may never be forgotten even if they are out-of-date, which may introduce bias. As shown in Figure 5b, a larger buffer size will lead to more stable performance but will sacrifice the sample efficiency. In more complicated environments, selecting the proper buffer size could be non-trivial. Some forgetting mechanism (Novati & Koumoutsakos, 2019) and meta-learning strategies (Zha et al., 2019b) could be the potential directions to better manage the buffer.
Third, in our implementation, we employ behavior cloning, the simplest form of imitation learning, to train the policy. In recent years, many more advanced imitation learning methods have been proposed (Ho & Ermon, 2016; Hester et al., 2017). In particular, the idea of inverse reinforcement learning (Abbeel & Ng, 2004) is to learn reward functions based on the demonstrations. An interesting future direction is to study whether we can derive intrinsic rewards based on the experiences in the buffer via inverse reinforcement learning. Specifically, is there a connection between RAPID and intrinsic rewards from the view of inverse reinforcement learning? Can RAPID be combined with intrinsic rewards to improve the performance? We hope that RAPID can facilitate future research to understand these questions.

heading: 6 CONCLUSIONS AND FUTURE WORK

text: This work studies how we can reward good exploration behaviors in procedurally-generated environments. We hypothesize that episode-level exploration score could be a more general criterion to distinguish good exploration behaviors. To verify our hypothesis, we design RAPID, a practical algorithm that learns to reproduce past good exploration behaviors with a ranking buffer. Experiments on benchmark hard-exploration procedurally-generated environments show that RAPID significantly outperforms state-of-the-art intrinsic reward methods in terms of sample efficiency and final performance. Further analysis shows that RAPID has robust performance across different configurations, even without extrinsic rewards. Moreover, experiments on a 3D navigation task and a subset of sparse MuJoCo tasks show that RAPID could generalize to continuous state/action spaces, showing the promise in rewarding good episode-level exploration behaviors to encourage exploration. In the future, we will extend our idea and test it in more challenging procedurally-generated environments. We will also explore the possibility of combining the episode-level exploration bonus with intrinsic rewards. Last, we will try other imitation learning techniques beyond behavior cloning.

heading: A HYPERPARAMETERS AND NEURAL NETWORK ARCHITECTURE

text:
For the proposed RAPID, the common hyperparameters are summarized in Table 2. RAPID is based on the PPO implementation from OpenAI baselines1. The nstep is 128 for all MiniGrid environments and MuJoCo environments, and 512 for MiniWorld-Maze-S5. For MuJoCo environments, we report the results with only imitation loss since we find that the policy loss of PPO will harm the performance in the episodic reward setting. The learning rate is 10−4 for all MiniGrid environments and MiniWorld-Maze-S5, and 5× 10−4 for MuJoCo environments. Since MiniWorld-Maze-S5 and MuJoCo environments have continuous state space, we set w2 = 0. In practice, in MiniWorldMaze-S5, we observe that counting the states will usually lead to memory error because it is not likely to encounter the same state again in MiniWorld-Maze-S5 (COUNT is excluded in comparison due to memory issues). Note that it is possible to use pseudo-counts (Bellemare et al., 2016; Ostrovski et al., 2017), which we will study in our future work. For MiniGrid-KeyCorridorS2R3-v0, MiniGrid-KeyCorridorS3R3-v0 and MiniWorld-Maze-S5, the update frequency of imitation learning is linearly annealed to 0 throughout the training process. For other environments, the imitation learning is performed after each episode. We keep all other hyperparameters of PPO as default and use the default CNN architecture provided in OpenAI baselines for MiniWorld-Maze-S5 and MLP with 64-64 for other environments. The PPO also uses the same hyperparameters. We summarize the state space of each environment and how the local and global scores are computed in Table 3.
For RANDOM, we implement the two networks with 64-64 MLP. For CURIOSITY and RIDE, we use 64-64 MLP for state embedding model, forward dynamics model and inverse dynamics model, respectively. However, with extensive hyperparameters search, we are not able to reproduce the RIDE results in MiniGrid environments even with the exactly same neural architecture and hyperparameters as suggested in (Raileanu & Rocktäschel, 2020). Thus, we use the authors’ implementation2 (Raileanu & Rocktäschel, 2020), which is well-tuned on MiniGrid tasks. Our reported result
1https://github.com/openai/baselines 2https://github.com/facebookresearch/impact-driven-exploration
is on par with that reported in (Raileanu & Rocktäschel, 2020). For SIL and AMIGO, we use the implementations from the authors34 with the recommended hyperparameters.
For the methods based on intrinsic rewards, i.e., RIDE,, AMIGO CURIOSITY, RANDOM, and COUNT, we search intrinsic reward coefficient from {0.1, 0.05, 0.01, 0.005, 0.001, 0.0005, 0.0001}. For RIDE, the intrinsic reward coefficient is 0.1 for MiniGrid-KeyCorridorS2R3-v0, MiniGridKeyCorridorS3R3-v0, MiniGrid-KeyCorridorS4R3-v0, MiniGrid-MultiRoom-N10S4-v0, MiniGrid-MultiRoom-N7S4-v0 and MiniWorld-Maze-S5, and 0.5 for MiniGrid-MultiRoomN7S8-v0, MiniGrid-MultiRoom-N10S10-v0 and MiniGrid-MultiRoom-N12S10-v0. For AMIGO and CURIOSITY, the intrinsic reward coefficient is 0.1 for all the environments. For COUNT, the intrinsic reward coefficient is 0.005 for all the environments. For RANDOM, the intrinsic reward coefficient is 0.001 for all the environemnts. We also tune the entropy coefficient of RIDE from {0.001, 0.0005}, as suggested by the original paper. The entropy coefficient is 0.0005 for MiniGrid-KeyCorridorS2R3-v0, MiniGrid-KeyCorridorS3R3-v0, MiniGrid-KeyCorridorS4R3-v0, MiniGrid-MultiRoom-N10S4-v0, MiniGrid-MultiRoom-N7S4-v0 and MiniWorld-Maze-S5, and 0.001 for MiniGrid-MultiRoom-N7S8-v0, MiniGrid-MultiRoom-N10S10-v0 and MiniGridMultiRoom-N12S10-v0.
The w0, w1, and w2 are selected as follows. We first run RAPID on MiniGrid-MultiRoom-N7S8v0. We choose this environment because it is not too hard nor too easy, so we expect that it is representative among all the considered MiniGrid environments. We fix w0 to be 1, and select w1 and w2 from {10−4, 10−3, 10−2, 10−1, 100, 101, 102, 103, 104}, that is, there are 9 × 9 = 81 combinations. Note that we can fix w0 because only the relative ranking matters in the ranking buffer. The selected w1 and w2 are then directly used in other environments without tuning. We further conduct a sensitivity analysis on MiniGrid-MultiRoom-N7S8-v0 in Figure 8. We observe that RAPID has good performance in a very wide range of hyperparameter choices.

heading: B ENVIRONMENTS

text:
B.1 MINIGRID ENVIRONMENTS
MiniGrid5 is a suite of light-weighted and fast gridworld environments with OpenAI gym interfaces. The environments are partially observable with a grid size of N ×N . Each tile in the gird can have at most one object, that is, 0 or 1 object. The possible objects are wall, floor, lava, door, key, ball, box and goal. Each object will have an associated color. The agent can pick up at most one object (ball or key). To open a locked door, the agent must use a key. Most of the environments in
3https://github.com/junhyukoh/self-imitation-learning 4https://github.com/facebookresearch/adversarially-motivated-intrinsic-goals 5https://github.com/maximecb/gym-minigrid
MiniGrid are procedurally-generated, i.e. a different grid will be sampled in each episode. Figure 9 shows the grids in four different episodes. The procedurally-generated nature makes training RL challenging because the RL agents need to learn the skills that can generalize to different grids. The environments can be easily modified so that we can create different levels of the environments. For example, we can modify the number of rooms and the size of each room to create hard-exploration or easy-exploration environments. The flexibility of MiniGrid environments enables us to conduct systematic comparison of algorithms under different difficulties.
The original observations of MiniGrid are dictionaries, which consist of a image field providing a partially observable view of the environment, and a mission field describing the goal with texts. In our experiments, we use ImgObsWrapper which only keeps the image field. The environment uses a compact encoding with 3 input values per visible grid cell. Note that the cells behind the wall or unopened doors are invisible.
The possible actions in MiniGrid are (1) turn left, (2) turn right, (3) move forward, (4) pick up an object, (5) drop the carried object, (6) open doors/interact with objects, and (7) done. The agent will remain in the same state if the action is not legal. For example, if there is no object in front of the agent, the agent will remain in the same state when performing action (4) pick up an object.
We focus on MultiRoom-NX-SY and KeyCorridor-SX-RY, where X and Y are hyperparameters specifying the number of rooms or the room sizes in the environments. With larger X and Y, the environments will become more difficult to solve due to the sparse rewards. Figure 10 shows the environments (with different difficulties) in this work. In MultiRoom-NX-SY, the agent needs to navigate the green tile in the last room. If the agent successfully navigates the goal, the agent will receive a reward of 1 subtracting some penalties of the timesteps spent. In KeyCorridor-SX-RY, the agent needs to pick up the key, use the key to open the locked door, and pick up the ball. Similarly, the agent will receive a reward of 1 subtracting some penalties of the timesteps spent if it picks up the ball. Both environments are extremely difficult to solve using RL alone due to the sparse rewards.
B.2 MINIWORLD MAZE ENVIRONMENT
MiniWorld6 is a minimalistic 3D interior environment simulator. Similar to Minigrid, we can easily create environments with different levels. We focus on MiniWorld-Maze, where the agent is asked to navigate the goal through a procedurally-generated maze. The agent has a first-person partially observable view of the environment. This environment is extremely difficult to solve due to sparse reward, long-horizon, and the procedurally-generated nature of the environments.
6https://github.com/maximecb/gym-miniworld
In this work, we focus on MiniWorld-Maze-S5, a variant of the MiniWorld Maze environment with 5×5 tiles. Figure 11 shows the top view of the mazes in four different episodes. In each episode, the agent and the goal are initialized in the top-left and bottom-right corners of the map, respectively. In this way, we ensure that the agent and the goal are far away enough so that the agent can not easily see the goal without exploration. A random maze will be generated in each episode. There are three possible actions: (1) move forward, (2) turn left, and (3) turn right. The agent will move 0.4× tile length if moving forward, where tile length is the length of one side of a tile. The agent will rotate 22.5 degrees if turning right/left. The time budget of each episode is 600. The agent will not receive any positive reward if it can not navigate the goal under the time budget.
B.3 SPARSE MUJOCO ENVIRONMENTS
Mujoco is a physical engine for continuous control (Todorov et al., 2012). Figure 12 shows the rendering of the four MuJoCo tasks used in our work. The original MuJoCo environments use dense rewards, i.e., a well-defined reward is given in each timestep. However, in many scenarios, well-defined dense rewards may be not available. We consider a variant of MuJoCo task using only episodic reward. Specifically, the original rewards are accumulated and only an episodic reward is given in the final timestep. The agent will receive a 0 reward in all the other timesteps. This sparse setting makes the tasks much more challenging to solve. Contemporary RL algorithms will usually suffer from the sparse rewards and deliver unsatisfactory performance. We aim to use these sparse variants to study whether our RAPID can effectively capture the sparse rewards.

heading: C ABLATIONS

text: Figure 13 shows the learning curves of RAPID against different ablations. Without local scores, we observe significant performance drop on challenging environments in terms of sample efficiency and final performance, i.e., on MultiRoom-N7-S8, MultiRoom-N10-S10, MultiRoom-N12-S10, KeyCorridor-S3-R3, and KeyCorridor-S4-R3. This suggests that the proposed local score plays an important role in encouraging exploration. We also observe that without buffer, the agent fails to learn a good policy. Naively using the proposed scores as intrinsic reward will harm the performance. Using the extrinsic reward and the global score to rank the episodes also contribute in the challenging environments, such as KeyCorridor-S4-R3. Therefore, the three proposed scoring methods may be complementary and play different roles in different environments.

heading: D FULL ANALYSIS RESULTS

text:
D.1 IMPACT OF THE NUMBER OF UPDATE STEPS
D.2 IMPACT OF BUFFER SIZE
D.3 PURE EXPLORATION ON MINIGRID
D.4 LOCAL EXPLORATION SCORE OF PURE EXPLORATION ON MINIGRID

heading: F LEARNING CURVES WITH LARGE ROOMS

heading: E LEARNING CURVES WITH MORE ROOMS

heading: G ABLATION AND ANALYSIS OF MINIWORLD-MAZE

heading: H COMPARISON WITH STORING ENTIRE EPISODES IN THE BUFFER

text: A variant of RAPID is to keep the entire episodes in the buffer instead of state-action pairs. The intuition of keeping the whole episode is that it is possible that a particular state-action pair may only be good in terms of exploration, in the context of the rest of the agent’s trajectory in that episode. To test this variant, we force the buffer to keep the entire episode by allowing the episode at the end of the buffer to exceed the buffer size. For example, given that the buffer size is 5000, if the length of the end episode is 160 and the number of state-action pairs in the buffer is 5120, we do not cut off the end episode and exceptionally allow the buffer to store 5120 state-action pairs. In this way, we ensure that the entire episodes are kept in the buffer. We run this experiment on MiniGrid-MultiRoom-N7-S8-v0 (Figure 25). We do not observe a clear difference in the learning curves.

heading: I RESULTS ON PROCEDURALLY-GENERATED SWIMMER

text: The standard MuJoCo environments are singleton. Here, we modify the Swimmer-v2 environment to make it procedurally-generated. Specifically, we make the environment in each episode different by modifying the XML configuration file of MuJoCo engine in every new episode. We consider two environmental properties, i.e., density and viscosity. Density is used to simulate lift and drag forces, which scale quadratically with velocity. Viscosity is used to simulate viscous forces, which scale linearly with velocity. In the standard Swimmer-v2 environment, the density and the viscosity are fixed to 4000 and 0.1, respectively. In the first experiment, we uniformly sample the density in [2000, 4000] in each new episode to make it procedurally-generated, denoted as Density-Swimmer. Similarly, in the second environment, we uniformly sample the velocity in [0.1, 0.5], denoted as Velocity-Swimmer. These two variants make RL training more challenging since the agent needs to learn a policy that can generalize to different densities and velocities. Similarly, we accumulate the rewards to the final timestep of an episode to make the environments sparse. Both environments are provided in our code for reproducibility. The results are reported in Figure 26. We observe that all methods learn slower on these two variants. For example, RAPID only achieves around 190 return in Density-Swimmer, while RAPID achieves more than 200 return in Swimmer. Similarly, SIL reaches around 100 return after around 5×106 timesteps in Density-Swimmer, while it achieves around 100 return after around 3 × 106 timesteps in Swimmer. Nevertheless, RAPID can discover very good policies even in these challenging procedurally-generated settings.

heading: J DISCUSSIONS OF ANNEALING

text: In our experiments, we find that annealing the updating step to 0 sometimes helps improve the sample efficiency. However, in some environments, annealing will have a negative effect on the final performance. To show the effect of annealing, we plot learning curves with or without annealing on MiniGrid-KeyCorridorS3R2-v0 and MiniGrid-MultiRoom-N12-S10-v0 in Figure 27. We observe that annealing can help in KeyCorridor-S3-R2. The possible explanation is that, after the agent navigates the goal, it has access to the reward signal. the PPO objective is sufficient to train a good policy with the extrinsic rewards. The imitation loss may harm the performance since it could be better to perform exploitation rather than exploration at this stage. However, in MultiRoom-N12S10, annealing will harm the performance. In particular, the performance drops significantly in the final stage when the updating frequency of imitation loss approaches zero. The possible reason is that MultiRoom-N12-S10 needs very deep exploration to find the goal. Even though the PPO agent can navigate the goal, it may easily suffer from insufficient exploration when it encounters a new environment. As a result, the agent needs to keep exploring the environment in order to generalize. Introducing imitation loss will ensure that the agent keeps exploring the environments.

title: PROCEDURALLY-GENERATED ENVIRONMENTS


summaries: This paper focuses on improving zero-shot classification by reducing the bias of the classifier towards seen classes. The bias occurs since the embedding is trained with visual examples from the seen classes, while using only the attribute information from unseen classes for testing. Authors propose an isometric propagation network that build a graph in both visual and semantic space, performs some steps of propagation, and then uses the updated prototypes for training a classifier. They use attention to construct the graph and also use attention to regularize the graph edges between the two spaces to be isometric. Authors also propose to use an episodic training method to improve learning.

summaries: In this paper Zero Shot Classification is studied using prototypes. Each class is represented with a visual and semantic prototype, and at test time compared to a visual example + prototype for a(n unseen) test class. The most similar test class is chosen. In this work a novel method is proposed to construct the prototypes, which are trained in an episode learning setting. On various benchmarks the proposed method performs better than existing method for the generalized zero-shot classification task (seen + unseen) test classes.

summaries: The authors propose a novel computational pipeline to tackle a well-known problem in zero-shot learning: although multiple visual instances are available for the classes and categories to be recognized, one and only one semantic embedding is available to describe the classes/categories while using side information like attributes or relevant textual information. To cope with that problem, authors learn visual and semantic prototypes which are then adopted to perform gradient descent over a graph in which the topological relationship among similar/dissimilar classes are preserved. In the experimental validation, the proposed method shows its superiority among a number of prior methods in zero-shot learning, including discriminative and generative methods.

abstractText: Zero-shot learning (ZSL) aims to classify images of an unseen class only based on a few attributes describing that class but no access to any training sample. A popular strategy is to learn a mapping between the semantic space of class attributes and the visual space of images based on the seen classes and their data. Thus, an unseen class image can be ideally mapped to its corresponding class attributes. The key challenge is how to align the representations in the two spaces. For most ZSL settings, the attributes for each seen/unseen class are only represented by a vector while the seen-class data provide much more information. Thus, the imbalanced supervision from the semantic and the visual space can make the learned mapping easily overfitting to the seen classes. To resolve this problem, we propose Isometric Propagation Network (IPN), which learns to strengthen the relation between classes within each space and align the class dependency in the two spaces. Specifically, IPN learns to propagate the class representations on an auto-generated graph within each space. In contrast to only aligning the resulted static representation, we regularize the two dynamic propagation procedures to be isometric in terms of the two graphs’ edge weights per step by minimizing a consistency loss between them. IPN achieves state-of-the-art performance on three popular ZSL benchmarks. To evaluate the generalization capability of IPN, we further build two larger benchmarks with more diverse unseen classes, and demonstrate the advantages of IPN on them.

authors:
Zeynep Akata
Florent Perronnin
Zaid Harchaoui
Cordelia Schmid

title: Label-embedding for image classification

authors:
Zeynep Akata
Scott Reed
Daniel Walter
Honglak Lee
Bernt Schiele

title: Evaluation of output embeddings for fine-grained image classification

venue: In CVPR,

authors:
Yannick Le Cacheux
Herve Le Borgne
Michel Crucianu

title: Modeling inter and intra-class relations in the triplet loss for zero-shot learning

authors:
Soravit Changpinyo
Wei-Lun Chao
Boqing Gong
Fei Sha

title: Synthesized classifiers for zeroshot learning

authors:
Soravit Changpinyo
Wei-Lun Chao
Fei Sha

title: Predicting visual exemplars of unseen classes for zero-shot learning

venue: In ICCV,

authors:
Haoang Chi
Feng Liu
Wenjing Yang
Long Lan
Tongliang Liu
Gang Niu
Bo Han

title: Meta discovery: Learning to discover novel classes given very limited data, 2021

authors:
Kaize Ding
Jianling Wang
Jundong Li
Kai Shu
Chenghao Liu
Huan Liu

title: Graph prototypical networks for few-shot learning on attributed networks

venue: In Proceedings of the 29th ACM International Conference on Information & Knowledge Management,

authors:
Kaize Ding
Qinghai Zhou
Hanghang Tong
huan Liu

title: Few-shot network anomaly detection via cross-network meta-learning

venue: In Proceedings of The Web Conference

authors:
Xuanyi Dong
Yi Yang

title: Searching for a robust neural architecture in four gpu hours

authors:
Xuanyi Dong
Lu Liu
Katarzyna Musial
Bogdan Gabrys

title: NATS-Bench: Benchmarking nas algorithms for architecture topology and size

authors:
Hehe Fan
Ping Liu
Mingliang Xu
Yi Yang

title: Unsupervised visual representation learning via dual-level progressive similar instance selection. TCYB, 2021

authors:
Ali Farhadi
Ian Endres
Derek Hoiem
David Forsyth

title: Describing objects by their attributes

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

venue: In ICML,

authors:
Andrea Frome
Greg S Corrado
Jon Shlens
Samy Bengio
Jeff Dean
Tomas Mikolov

title: Devise: A deep visual-semantic embedding model

venue: NeurIPS,

authors:
Ian Goodfellow
Jean Pouget-Abadie
Mehdi Mirza
Bing Xu
David Warde-Farley
Sherjil Ozair
Aaron Courville
Yoshua Bengio

title: Generative adversarial nets

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

authors:
He Huang
Changhu Wang
Philip S Yu
Chang-Dong Wang

title: Generative dual adversarial network for generalized zero-shot learning

authors:
Huajie Jiang
Ruiping Wang
Shiguang Shan
Xilin Chen

title: Learning class prototypes via structure alignment for zero-shot recognition

venue: In ECCV,

authors:
Michael Kampffmeyer
Yinbo Chen
Xiaodan Liang
Hao Wang
Yujia Zhang
Eric P Xing

title: Rethinking knowledge graph propagation for zero-shot learning

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: In ICLR,

authors:
Elyor Kodirov
Tao Xiang
Shaogang Gong

title: Semantic autoencoder for zero-shot learning

authors:
Christoph H Lampert
Hannes Nickisch
Stefan Harmeling

title: Attribute-based classification for zero-shot visual object categorization

authors:
Hugo Larochelle
Dumitru Erhan
Yoshua Bengio

title: Zero-data learning of new tasks

venue: In IJCAI,

authors:
Jingjing Li
Mengmeng Jin
Ke Lu
Zhengming Ding
Lei Zhu
Zi Huang

title: Leveraging the invariant side of generative zero-shot learning

authors:
Kai Li
Martin Renqiang Min
Yun Fu

title: Rethinking zero-shot learning: A conditional visual classification perspective

authors:
Yanan Li
Donghui Wang
Huanhang Hu
Yuetan Lin
Yueting Zhuang

title: Zero-shot recognition using dual visual-semantic mapping paths

authors:
Feng Liu
Wenkai Xu
Jie Lu
Guangquan Zhang
Arthur Gretton
Danica J. Sutherland

title: Learning deep kernels for non-parametric two-sample tests

authors:
Lu Liu
Tianyi Zhou
Guodong Long
Jing Jiang
Lina Yao
Chengqi Zhang

title: Prototype propagation networks (PPN) for weakly-supervised few-shot learning on category graph

authors:
Lu Liu
Tianyi Zhou
Guodong Long
Jing Jiang
Chengqi Zhang

title: Learning to propagate for graph meta-learning

venue: In NeurIPS,

authors:
Shichen Liu
Mingsheng Long
Jianmin Wang
Michael I Jordan

title: Generalized zero-shot learning with deep calibration network

authors:
Yang Liu
Jishun Guo
Deng Cai
Xiaofei He

title: Attribute attention for semantic disambiguation in zero-shot learning

authors:
Yang Liu
Deyan Xie
Quanxue Gao
Jungong Han
Shujian Wang
Xinbo Gao

title: Graph and autoencoder based feature extraction for zero-shot learning

authors:
Yixin Liu
Shirui Pan
Ming Jin
Chuan Zhou
Feng Xia
Philip S. Yu

title: Graph self-supervised learning: A survey, 2021

authors:
Laurens van der Maaten
Geoffrey Hinton

title: Visualizing data using t-SNE

authors:
Mohammad Norouzi
Tomas Mikolov
Samy Bengio
Yoram Singer
Jonathon Shlens
Andrea Frome
Greg S Corrado
Jeffrey Dean

title: Zero-shot learning by convex combination of semantic embeddings

authors:
Jeffrey Pennington
Richard Socher
Christopher Manning

title: Glove: Global vectors for word representation

venue: In EMNLP,

authors:
Sachin Ravi
Hugo Larochelle

title: Optimization as a model for few-shot learning

authors:
Mengye Ren
Eleni Triantafillou
Sachin Ravi
Jake Snell
Kevin Swersky
Joshua B Tenenbaum
Hugo Larochelle
Richard S Zemel

title: Meta-learning for semi-supervised few-shot classification

authors:
Bernardino Romera-Paredes
Philip Torr

title: An embarrassingly simple approach to zero-shot learning

authors:
Adam Santoro
Sergey Bartunov
Matthew Botvinick
Daan Wierstra
Timothy Lillicrap

title: Metalearning with memory-augmented neural networks

authors:
Mert Bulent Sariyildiz
Ramazan Gokberk Cinbis

title: Gradient matching generative networks for zero-shot learning

authors:
Jake Snell
Kevin Swersky
Richard Zemel

title: Prototypical networks for few-shot learning

authors:
Richard Socher
Milind Ganjoo
Christopher D Manning
Andrew Ng

title: Zero-shot learning through cross-modal transfer

authors:
Robyn Speer
Joshua Chin
Catherine Havasi

title: Conceptnet 5.5: An open multilingual graph of general knowledge

venue: arXiv preprint arXiv:1612.03975,

authors:
Flood Sung
Yongxin Yang
Li Zhang
Tao Xiang
Philip HS Torr
Timothy M Hospedales

title: Learning to compare: Relation network for few-shot learning

authors:
Bin Tong
Chao Wang
Martin Klinkigt
Yoshiyuki Kobayashi
Yuuichi Nonaka

title: Hierarchical disentanglement of discriminative latent features for zero-shot learning

authors:
Xiaolong Wang
Yufei Ye
Abhinav Gupta

title: Zero-shot recognition via semantic embeddings and knowledge graphs

authors:
Peter Welinder
Steve Branson
Takeshi Mita
Catherine Wah
Florian Schroff
Serge Belongie
Pietro Perona

title: Caltech-ucsd birds 200

venue: Technical report, California Institute of Technology,

authors:
Yongqin Xian
Christoph H Lampert
Bernt Schiele
Zeynep Akata

title: Zero-shot learning-a comprehensive evaluation of the good, the bad and the ugly

authors:
Yongqin Xian
Saurabh Sharma
Bernt Schiele
Zeynep Akata

title: f-vaegan-d2: A feature generating framework for any-shot learning

authors:
Guo-Sen Xie
Li Liu
Xiaobo Jin
Fan Zhu
Zheng Zhang
Jie Qin
Yazhou Yao
Ling Shao

title: Attentive region embedding network for zero-shot learning

authors:
Guo-Sen Xie
Li Liu
Fan Zhu
Fang Zhao
Zheng Zhang
Yazhou Yao
Jie Qin
Ling Shao

title: Region graph embedding network for zero-shot learning

authors:
Fei Zhang
Guangming Shi

title: Co-representation network for generalized zero-shot learning

authors:
Li Zhang
Tao Xiang
Shaogang Gong

title: Learning a deep embedding model for zero-shot learning

authors:
Pengkai Zhu
Hanxiao Wang
Venkatesh Saligrama

title: Generalized zero-shot recognition based on visually semantic embedding

authors:
Yizhe Zhu
Jianwen Xie
Zhiqiang Tang
Xi Peng
Ahmed Elgammal

title: Semantic-guided multiattention localization for zero-shot learning

heading: 1 INTRODUCTION

text:
One primary challenge on the track from artificial intelligence to human-level intelligence is to improve the generalization capability of machine learning models to unseen problems. While most supervised learning methods focus on generalization to unseen data from training task/classes, zeroshot learning (ZSL) (Larochelle et al., 2008; Lampert et al., 2014; Xian et al., 2019a) has a more ambitious goal targeting the generalization to new tasks and unseen classes. In the context of image classification, given images from some training classes, ZSL aims to classify new images from unseen classes with zero training image available. Without training data, it is impossible to directly learn a mapping from the input space to the unseen classes. Hence, recent works introduced learning to map between the semantic space and visual space (Zhu et al., 2019a; Li et al., 2017; Jiang et al., 2018) so that the query image representation and the class representation can be mapped to a shared space for comparison.
However, learning to align the representation usually leads to overfitting on seen classes (Liu et al., 2018). One of the reasons is that in most zero-shot learning settings, the number of images per class is hundreds while the semantic information provided for one class is only limited to one vector. Thus, the mapping function is easily overfitting to the seen classes when trained using the small set of attributes. The learned model typically has imbalanced performance on samples from the seen classes and unseen classes, i.e., strong when predicting samples from the seen classes but struggles in the prediction for samples in the unseen classes.
In this paper, we propose “Isometric Propagation Network (IPN)” which learns to dynamically interact between the visual space and the semantic space. Within each space, IPN uses an attention module to generate a category graph, and then perform multiple steps of propagation on the graph.
In every step, the distribution of the attention scores generated in each space are regularized to be isometric so that implicitly aligns the relationships between classes in two spaces. Due to different motifs of the generated graphs, the regularizer for the isometry between the two distributions are provided with sufficient training supervisions and can potentially generalize better on unseen classes. To get more diverse graph motifs, we also apply episodic training which samples different subset of classes as the nodes for every training episode rather than the whole set of seen classes all the time.
To evaluate IPN, we compared it with several state-of-the-art ZSL methods on three popular ZSL benchmarks, i.e., AWA2 (Xian et al., 2019a), CUB (Welinder et al., 2010) and aPY (Farhadi et al., 2009). To test the generalization ability on more diverse unseen classes rather than similar classes to the seen classes, e.g., all animals for AWA2 and all birds for CUB, we also evaluate IPN on two new large-scale datasets extracted from tieredImageNet (Ren et al., 2018), i.e., tieredImageNet-Mixed and tieredImageNet-Segregated. IPN consistently achieves state-of-the-art performance in terms of the harmonic mean of the accuracy on unseen and seen classes. We show the ablation study of each component in our model and visualize the final learned representation in each space in Figure 1. It shows the class representations in each space learned by IPN are evenly distributed and connected smoothly between the seen and unseen classes. The two spaces can also reflect each other.

heading: 2 RELATED WORKS

text:
Most ZSL methods can be categorized as either discriminative or generative. Discriminative methods generate the classifiers for unseen classes from its attributes by learning a mapping from a input image’s visual features to the associated class’s attributes on training data of seen classes (Frome et al., 2013; Akata et al., 2015a;b; Romera-Paredes & Torr, 2015; Kodirov et al., 2017; Socher et al., 2013; Cacheux et al., 2019; Li et al., 2019b), or by relating similar classes according to their shared properties, e.g., semantic features (Norouzi et al., 2013; Chi et al., 2021) or phantom classes (Changpinyo et al., 2016), etc. In contrast, generative methods employ the recently popular image generation models (Goodfellow et al., 2014) to synthesize images of unseen classes, which reduces ZSL to supervised learning (Huang et al., 2019) but usually increases the training cost and model complexity. In addition, the study of unsupervised learning (Fan et al., 2021; Liu et al., 2021), meta learning (Santoro et al., 2016; Liu et al., 2019b;a; Ding et al., 2020; 2021), or architecture design (Dong et al., 2021; Dong & Yang, 2019) can also be used improve the representation ability of visual or semantic features.
Alignment between two spaces in ZSL Frome et al. (2013); Socher et al. (2013); Zhang et al. (2017) proposed to transform representations either to the visual space or the semantic space for distance for comparison. Li et al. (2017) introduces how to optimize the semantic space so that the two spaces can be better aligned. Jiang et al. (2018); Liu et al. (2020) tries to map the class representations from two spaces to another common space. Comparatively, our IPN does not align two spaces by feature transformation but by regularizing the isometry of the intermediate output from two propagation model.
Graph in ZSL Graph structures have already been explored for their benefits to some discriminative ZSL models, e.g., Wang et al. (2018); Kampffmeyer et al. (2019) learn to generate the weights of a fully-connected classifier for a given class based on its semantic features computed on a pre-
defined semantic graph using a graph convolutional networks (GCN). They require (1) a pre-trained CNN whose last fully-connected layer provides the ground truth of the classifiers ZSL aims to generate; and (2) an existing knowledge graph as the input of GCN. By contrast, our method learns to automatically generate the graph and the class prototypes composing the support set of a distancebased classifier. Hence, our method does not require a pre-trained CNN to provide a ground truth for the classifier. In addition, we train a modified graph attention network (GAN) (rather than a GCN) to generate the prototypes, so it learns both the class adjacency and edges by itself and can provide more accurate modeling of class dependency in scenarios when no knowledge graph is provided. Tong et al. (2019) and Xie et al. (2020) also leverage the idea of graph to transform the feature extracted from the CNN while our graph serves as the paths for propagation. It requires an off-the-shelf graph generated by ConceptNet (Speer et al., 2016), while IPN applies prototype propagation and learns to construct the graph in an end-to-end manner.
Attention in ZSL The attention module has been applied for zero-shot learning for localization. Liu et al. (2019c) introduces localization on the semantic information and Xie et al. (2019) proposes localization on the visual feature. Zhu et al. (2019b) further extends it to multi-localization guided by semantic. Different from them, our attention serves as generating the weights for propagation.
Our episodic training strategy is inspired by the meta-learning method from (Santoro et al., 2016). Similar methods have been broadly studied in meta-learning and few-shot learning approaches (Finn et al., 2017; Snell et al., 2017; Sung et al., 2018) but rarely studied for ZSL in previous works. In this paper, we show that training ZSL model as a meta-learner can improve the generalization performance and mitigate overfitting.

heading: 3 PROBLEM SETTING

text: We consider the following setting of ZSL. The training set is composed of data-label pairs (x, y), where x ∈ X is a sample from class y, and y must be one of the seen classes in Yseen. During the test stage, given a test sample x of class y , the ZSL model achieved in training is expected to produce the correct prediction of y. In order to relate the unseen classes in test to the seen classes in training, we are also given the semantic embedding sy of each class y ∈ Yseen ∪ Yunseen. We further assume that seen and unseen classes are disjoint, i.e., Yseen∩Yunseen = ∅. The test samples come from both Yseen and Yunseen in generalized zero-shot learning.

heading: 4 ISOMETRIC PROPAGATION NETWORK

text:
In this paper, we bridge the two spaces via class prototypes in both the semantic and visual spaces, i.e., a semantic prototype P sy and a visual prototype P v y for each class y. In order to generate high-quality prototypes, we develop a learnable scheme called “Isometric Propagation Network
(IPN)” to iteratively refine the prototypes by propagating them on a graph of classes so each prototype is dynamically determined by the samples and attributes of its related classes.
In this section, we will first introduce the architecture of IPN. An illustration of IPN is given in Figure 2. Then, we will elaborate the episodic training strategy, in which a consistency loss is minimized for isometric alignment between the two spaces.

heading: 4.1 PROTOTYPE INITIALIZATION

text:
Given a task T defined on a subset of classes YT with training data DT , IPN first initializes the semantic and visual prototype for each class y ∈ YT . The semantic prototype of class y is transformed from its attributes sy . Specifically, we have drawn on the expert modules from (Zhang & Shi, 2019) to initialize the semantic prototypes P sy [0]. In previous works (Snell et al., 2017; Santoro et al., 2016), the visual prototype of a class is usually computed by averaging the features of images from the class. In IPN, for each seen class y ∈ YT ∩ Yseen, we initialize its visual prototype P vy [0] by
P vy [0] = W |DTy | ∑
(xi,yi)∈DTy
fcnn(xi), D T y , {(xi, yi) ∈ DT : yi = y}, (1)
where fcnn(·) is a backbone convolutional neural nets (CNN) extracting features from raw images, and W is a linear transformation aiming to change the dimension of the visual prototype to be the same as semantic prototypes. We argue that W is necessary because (1) the visual feature produced by the CNN is usually in high dimension, and reducing its dimension can save significant computations during propagation; (2) keeping the dimensions of the visual and semantic prototypes the same can avoid the dominance of either of them in the model.
During test, we initialize the visual prototype of each unseen class y ∈ YT∩Yunseen as the weighted sum of its K-nearest classes from Yseen in the semantic space1, i.e.,
P vy [0] = W · ∑ z∈Ny as(P sy [0],P s z [0]) · P vz , (2)
where W is the same transformation from Eq. (1), and Ny is the set of the top-K (K is a hyperparameter) seen classes2 with the largest similarities cs(P sy [0],P s z [0]) to class y in semantic space.

heading: 4.2 CATEGORY GRAPH GENERATION

text:
Although the propagation needs to be conducted on a category graph, IPN does not rely on any given graph structure as many previous works (Kampffmeyer et al., 2019; Wang et al., 2018) so it has less limitations when applied to more general scenarios. In IPN, we inference the category graph of YT by applying thresholding to the attention scores between the initialized prototypes. In the visual space, the set of edges is defined by
ET,v = { (y, z) : y, z ∈ YT , cv(P vy [0],P vz [0]) ≥ } , (3)
where is the threshold. Thereby, the category graph is generated as GT,v = (YT , ET,v). Similarly, in the semantic space, we generate another graph GT,s = (YT , ET,s).

heading: 4.3 ISOMETRIC PROPAGATION

text:
Given the initialized prototypes and generated category graphs in the two spaces, we apply the following prototype propagation in each space for τ steps in order to refine the prototype of each class. In the visual space, each propagation step updates
P vy [t+ 1] = ∑
z:(y,z)∈ET,v av(P vy [t],P v z [t]) · P vz [t], (4)
1This only happens in the test since we do not use any information of unseen classes during training. 2Here the notation Ny needs a little overloading since it denotes the set of neighbor classes of y elsewhere
in the paper.
In the semantic space, we apply similar propagation steps over classes on graph GT,s by using the attention module associated with as(·, ·). Intuitively, the attention module computes the similarity between the two prototypes. In the visual space, given the prototypes P vy and P v z for class y and z, the attention module first computes the following cosine similarity:
cv(P vy ,P v z ) = 〈hv(P vy ), hv(P vz )〉 ‖hv(P vy )‖2 · ‖hv(P vz )‖2 , (5)
where hv(·) is a learnable transformation and ‖ · ‖2 represents the `2 norm. For a class y on a category graph, we can use the attention module to aggregate messages from its neighbor classes Ny . In this case, we need to further normalize the similarities of y to each z ∈ Ny as follows.
av(P vy ,P v z ) =
exp[γcv(P vy ,P v z )]∑
z∈Ny exp[γc v(P vy ,P v z )]
, (6)
where γ is a temperature parameter controlling the smoothness of the normalization. In the semantic space, we have similar definitions of hs(·), cs(·, ·) and as(·, ·). In the following, we will use P vy [t] and P sy [t] to represent the visual and semantic prototype of class y at the t
th step of propagation. We will use | · | to represent the size of a set and ReLU(·) , max{·, 0}. After τ steps of propagation, we concatenate the prototypes achieved in the two spaces for each class to form the final prototypes:
Py = [P v y [τ ],P s y [τ ]], ∀ y ∈ YT . (7)
The formulation of as(·, ·) and cs(·, ·) follows the same way as av(·, ·) and cv(·, ·). To be simple, we don’t rewrite the formulations here.

heading: 4.4 CLASSIFIER GENERATED FROM PROTOTYPES

text:
Given the final prototypes and a query/test image x, we apply a fully-connected layer to predict the similarity between x and each class’s prototype. For each class y ∈ YT , it computes
f(x,Py) = wReLU(W (1)x+W (2)Py + b (1)) + b, (8)
Intuitively, the above classifier can be interpreted as a distance classifier with distance metric f(·, ·). When applied to a query image x, the predicted class is the most probable class, i.e., ŷ = argmaxy∈YT Pr(y|x;P ), where Pr denotes the probability.

heading: 4.5 TRAINING STRATEGIES

text:
Episodic training on subgraphs. In each episode, we sample a subset of training classes YT ⊆ Yseen, and then build a training (or support) set DTtrain and a validation (or query) set DTvalid from the training samples of YT . They are two disjoint sets of samples from the same subset of training classes. We only use DTtrain to generate the prototypes P by the aforementioned procedures, and then apply backpropagation to minimize the loss of DTvalid. This equals to an empirical risk minimization, i.e.,
min ∑
YT∼Yseen ∑ (x,y)∼DTvalid − log Pr(y|x;P ), (9)
This follows the same idea of meta-learning Ravi & Larochelle (2016): it aims to minimize the validation loss instead of the training loss and thus can further improve generalization and restrain overfitting. Moreover, since we train the IPN model on multiple random tasks T and optimize the propagation scheme over different subgraphs (each generated for a random subset of classes), the generalization capability of IPN to unseen classes and new tasks can be substantially enhanced by this meta-training strategy. Moreover, it effectively reduces the propagation costs since computing the attention needs O(|YT |2) operations. In addition, as shown in the experiments, episodic training is effective in mitigating the problem of data imbalance and overfitting to seen classes, which harasses many ZSL methods.
Consistency loss for alignment of visual and semantic space. In ZSL, the interaction and alignment between different spaces can provide substantial information about class dependency and is critical to the generation of accurate class prototypes. In IPN, we apply prototype propagation in two separate spaces on their own category graphs by using two untied attention modules. In order to keep the propagation in the two spaces consistent, we add an extra consistency loss to the training objective in Eq. (9). It computes the KL-divergence between two distributions defined in the two spaces for each class y ∈ YT at every propagation step t:
DKL(p v y[t]||psy[t]) = − ∑ z∈YT pvy[t]z · log psy[t]z pvy[t]z , (10)
where
pvy[t]z , exp[cv(P vy [t],P v z [t])]∑
z∈YT exp[c v(P vy [t],P v z [t])]
, (11)
psy[t]z , exp[cs(P sy [t],P s z [t])]∑
z∈YT exp[c s(P sy [t],P s z [t])]
. (12)
The consistency loss enforces the two attention modules in the two spaces to generate the same attention scores over classes, even when the prototypes and attention module’s parameter are different in the two spaces. In this way, they share similar class dependency over the propagation steps. So the generated dual prototypes are well aligned and can provide complementary information when generating the classifier. The final optimization we used to train IPN becomes:
min ∑
YT∼Yseen  ∑ (x,y)∼DTvalid − log Pr(y|x;P ) + λ τ∑ t=1 ∑ y∈YT DKL(p v y[t]||psy[t])  , (13) where λ is weight for the consistency loss, and P , pvy[t], and p s y[t] are computed only based on DTtrain, the training (or support) set of task-T for classes in YT .

heading: 5 EXPERIMENTS

text: We evaluate IPN and compare it with several state-of-the-art ZSL models in both ZSL setting (where the test set is only composed of unseen classes) and generalized ZSL setting (where the test set is composed of both seen and unseen classes). We report three standard ZSL evaluation metrics, and provide ablation study of several variants of IPN in the generalized ZSL setting. The visualization of the learned class representation is shown in Figure 1.

heading: 5.1 DATASETS AND EVALUATION CRITERIA

text:
Small and Medium benchmarks. Our evaluation includes experiments on three standard benchmark datasets widely used in previous works, i.e., AWA2 (Xian et al., 2019a), CUB (Welinder et al., 2010) and aPY (Farhadi et al., 2009). The former two are extracted from ImageNet-1K, where AWA2 contains 50 animals classes and CUB contains 200 bird species. aPY includes 32 classes. Detailed statistics of them can be found in Table 1.
Two new large-scale benchmarks. The three benchmark datasets above might be too small for modern DNN models since the training may suffers from large variance and end-to-end training usually fails. Previous ZSL methods therefore fine-tune a pre-trained CNN to achieve satisfactory performance on these datasets, which is costly and less practical. Given these issues, we proposed two new large-scale datasets extracted from tieredImageNet (Ren et al., 2018), i.e., tieredImageNetSegregated and tieredImageNet-Mixed, whose statistics are given in Table 1. Comparing to the three benchmarks, they are over 10× larger, and training a ResNet101 (He et al., 2016) from scratch on their training sets can achieve a validation accuracy of 65%, indicating that end-to-end training without fine-tuning is possible. These two benchmarks differ in that the “Mixed” version allows a seen class and an unseen class to belong to the same super category, while the “Segregated” version does not. The class attributes are the word embeddings of the class names provided by GloVe (Pennington et al., 2014). We removed the classes that do not have embeddings in GloVe.
Following the most popular setting of ZSL (Xian et al., 2019a), we report the per-class accuracy and harmonic mean of the accuracy on seen and unseen classes.

heading: 5.2 IMPLEMENTATION AND HYPERPARAMETER DETAILS

text:
For a fair comparison, we follow the setting in (Xian et al., 2019a) and use a pre-trained ResNet101 (He et al., 2016) to extract 2048-dimensional image features without fine-tuning. For the three standard benchmarks, the model is pre-trained on ImageNet-1K. For the two new datasets, it is pre-trained on the training set used to train ZSL models.
All hyperparameters were chosen on the validation sets provided by Xian et al. (2019a). We use the same hyperparameters tuned on AWA2 for other datasets since they are of similar data type, except for aPY on which we choose learning rate 1.0× 10−3 and weight decay 5.0× 10−4. For the rest of the datasets, we train IPN by Adam (Kingma & Ba, 2015) for 360 epochs with a weight decay factor 1.0× 10−4. The learning rate starts from 2.0× 10−5 and decays by a multiplicative factor 0.1 every 240 epochs. In each epoch, we update IPN on multiple N -way-K-shot tasks (N -classes with K samples per class), each corresponding to an episode mentioned in Section 4.5. In our experiments, the number of episodes in each epoch is n/NK, where n is the total size of the training set, N = 30 and K = 1 (a small K can mitigate the imbalance between seen and unseen classes); hv and hs are linear transformations; we set temperature γ = 10, threshold = cos 40o for the cosine similarities between class prototypes, and weight for consistency loss λ = 1. We use propagation steps τ = 2.

heading: 5.3 MAIN RESULTS

text:
The results are reported in Table 2. Although most previous works (Xian et al., 2019b;a; Sariyildiz & Cinbis, 2019) show that the more complicated generative models usually outperforms the discriminative ones. Our experiments imply that IPN, as a simple discriminative model, can significantly outperform the generative models requiring much more training efforts. Most baselines achieve a
high ACCseen but much lower ACCunseen since they suffer from and more sensitive to the imbalance between seen and unseen classes. In contrast, IPN always achieves the highest H-metric among all methods, indicating less overfitting to seen classes. This is due to the more accurate prototypes achieved by iterative propagation in two interactive spaces across seen and unseen classes, and the episodic training strategy, which effectively improves the generalization.
In scaling the experiments to the two large datasets, discriminative models perform better than generative models, which are easily prone to overfitting or divergence. Moreover, during the test stage, generative models require to synthesize data for unseen classes, which may lead to expensive computations when applied to tasks with many classes. In contrast, IPN scales well to these large datasets, outperforming state-of-the-art baselines by a large margin. The performance of most models on tieredImageNet-Segregated is generally worse than tieredImageNet-Mixed because that the unseen classes in the former do not share the same ancestor classes with the seen classes, while in the latter such sharing is allowed.

heading: 5.4 ABLATION STUDY

text:
Are two prototypes necessary? We compare IPN with its two variants, each using only one out of the two types of prototypes from the two spaces when generating the classifier. The results are shown in Figure 3. It shows that semantic prototype (only) performs much better than visual prototype (only), especially on the unseen classes. This is because that the unseen classes’ semantic embedding is given while its visual information is missing (zero images) during the test stage. Although IPN is capable of generating a visual prototype based on other classes’ images and class dependency, it is much less accurate than the semantic prototype. However, it also shows that the visual prototypes (even the ones of unseen classes) can provide extra information and further improve the performance of the semantic prototype, e.g., they improve the unseen classes’ accuracy from 61.1% to 67.5%. One possible reason is that the visual prototype bridges the query image’s visual feature with the semantic features of classes, and thus provides an extra “visual context” for the localization of the correct class. In addition, we observe that IPN with only the visual prototype converges faster than IPN with only a semantic prototype (30 epochs vs. 200 epochs). This might be an artifact caused by the pre-trained CNN, which already produces stable visual prototypes since the early stages. However, it raises a caveat that heavily relying on a pre-trained model might discourage the learning and results in a bad local optimum.
How’s the benefit of propagation? We then evaluate the effects of the propagation scheme in the two spaces. In particular, we compare IPN with its variants that apply the propagation steps in only one of the two spaces, and the variant that does not apply any propagation after initialization. Their performance is reported in Figure 3. Without any propagation, the classification performance heavily relies on pre-trained CNN. Hence, the accuracy of seen classes can be much higher than that of the unseen classes. Compared to IPN without any propagation, applying propagation in either the visual space or the semantic space can improve the accuracy of unseen classes by 2∼3%, while the accuracy on the seen classes stays almost the same. When equipped with dual propagation, we
observe a significant improvement of the accuracy of the unseen classes but a degradation on the seen classes. However, they lead to the highest H-metric, which indicates that the dual propagation achieves a desirable trade-off between overfitting on seen classes and generalization to unseen classes.
Effect of Isometric Alignment In IPN, we minimize a consistency loss during training for alignment of the visual and semantic space. Here, we consider two other options for alignment that exchange the attention modules used in the two spaces, i.e., using the visual attention module in the semantic space, or using the semantic attention module in the visual space. We also include the IPN trained without consistency loss or any alignment as a baseline. Their results are reported in Figure 3. Compared to IPN with/without consistency loss, sharing a single attention module between the two spaces suffers from the overfitting problem on the seen classes. This is because that the visual features and semantic embeddings are two different types of features so they should not share the same similarity metric. In contrast, the consistency loss only enforces the output similarity scores of the two attention modules to be close, while the models/functions computing the similarity can be different. Therefore, to produce the same similarity scores, it does not require each class having the same features in the two spaces. Hence, it leads to a much softer regularization.

heading: 6 SENSITIVITY OF HYPERPARAMETERS

text: The proposed IPN has some hyperparameters as mentioned in Section 5.2. To analyze the sensitivity of those hyperparameters, such as threshold, temperature, N and K for N-way-K-shot task, propagation steps, etc. We try different values and show the performance on the AWA2 dataset in Figure 4. The temperature γ is not sensitive for the accuracy. The threshold needs to be bigger than cosine(30o) to give IPN some space for the filtering. The propagation steps τ is best at 2. Weight decay is a sensitive hyperparameter and this is also found in previous ZSL literature (Zhang & Shi, 2019; Liu et al., 2019d).

heading: 7 CONCLUSIONS

text: In this work, we propose an Isometric Propagation Network, which learns to relate classes within each space and across two spaces. IPN achieves state-of-the-art performance and we show the importance of each component and visualize the interpretable relationship of the learned class representations. In future works, we will study other possibilities to initialize the visual prototypes of unseen classes in IPN.

heading: A EVALUATION CRITERIA

text:
Considering the imbalance between test classes, by following the most recent works (Xian et al., 2019a), given a test set D, we evaluate ZSL methods’ performance based on the per-class accuracy averaged over a targeted set of classes Y , i.e.,
ACCY = 1 |Y| ∑ y∈Y 1 |Dy| ∑
(x,y)∈Dy
1[ŷ = y], (14)
Dy , {(xi, yi) ∈ D : yi = y}.
Following Xian et al. (2019a), we report ACCY when Y = Yseen and Y = Yunseen, and the harmonic mean of them, i.e.,
H = 2 ·ACCYseen ·ACCYunseen ACCYseen +ACCYunseen . (15)

heading: B EXPERIMENTS ON ZERO-SHOT LEARNING SETTING

text: The comparison between IPN to other baselines on the setting of Zero-shot Learning is shown in Table 3. On CUB, AWA2, aPU, tiered-M, and tiered-S, our IPN outperforms other algorithms by a large margin.

heading: C MORE EXPERIMENTS ON LARGE-SCALE DATASETS

text: In our work, we follow the train/test split suggested by Frome et al. (2013), who proposed to use the 21K ImageNet dataset for zero-shot evaluation. Here, 2-hops and 3-hops represent that the evaluation is over the classes which are 2/3 hops away from ImageNet-1k. Different from experiments on AWA2, we use N=20 and K=5 for the full ImageNet. Besides, since the edges between each class are provided on the full ImageNet, we directly use them instead of calculating by Eq. (3).

title: ISOMETRIC PROPAGATION NETWORK FOR GENERALIZED ZERO-SHOT LEARNING