Explore and Control with Adversarial Surprise
Authors: Arnaud Fickinger
Natasha Jaques
Samyak Parajuli
Michael Chang
Nicholas Rhinehart
Glen Berseth
Stuart Russell
Sergey Levine
Venue: ICLR 2022 Submitted (2022)
Keywords: reinforcement learning
intrinsic motivation
exploration
multi-agent

Abstract: Unsupervised reinforcement learning (RL) studies how to leverage environment statistics to learn useful behaviors without the cost of reward engineering. However, a central challenge in unsupervised RL is to extract behaviors that meaningfully affect the world and cover the range of possible outcomes, without getting distracted by inherently unpredictable, uncontrollable, and stochastic elements in the environment. To this end, we propose an unsupervised RL method designed for high-dimensional, stochastic environments based on an adversarial game between two policies (which we call Explore and Control) controlling a single body and competing over the amount of observation entropy the agent experiences. The Explore agent seeks out states that maximally surprise the Control agent, which in turn aims to minimize surprise, and thereby manipulate the environment to return to familiar and predictable states. The competition between these two policies drives them to seek out increasingly surprising parts of the environment while learning to gain mastery over them. We show formally that the resulting algorithm maximizes coverage of the underlying state in block MDPs with stochastic observations, providing theoretical backing to our hypothesis that this procedure avoids uncontrollable and stochastic distractions. Our experiments further demonstrate that Adversarial Surprise leads to the emergence of complex and meaningful skills, and outperforms state-of-the-art unsupervised reinforcement learning methods in terms of both exploration and zero-shot transfer to downstream tasks.

Under review as a conference paper at ICLR 2022
EXPLORE AND CONTROL WITH ADVERSARIAL SURPRISE
Anonymous authors Paper under double-blind review
ABSTRACT
Unsupervised reinforcement learning (RL) studies how leverage environment statistics to learn useful behaviors without the cost of reward engineering. How- ever, central challenge in unsupervised RL is to extract behaviors that meaning- fully affect the world and cover the range of possible outcomes, without getting distracted by inherently unpredictable, uncontrollable, and stochastic elements the environment. To this end, we propose an unsupervised RI method designed for high- -ige-dimensional, stochastic environments based on an adversarial game be- tween two policies (which call Explore and Control) controlling single body and competing over the amount of observation entropy the agent experiences. The Explore agent seeks out states that maximally surprise the Control agent, which in turn aims to minimize surprise, and thereby manipulate the environment to return familiar and predictable states. The competition between these two policies drives them to seek out increasingly surprising parts of the environment while learning to gain mastery over them. We show formally that the resulting algo- rithm maximizes coverage of the underlying state in block MDPs with stochastic observations, providing theoretical backing to our hypothesis that this procedure avoids uncontrollable and stochastic distractions. Our experiments further demon- strate that Adversarial Surprise leads to the emergence of complex and meaningful skills, and outperforms state-of-the-ae unsupervised reinforcement learning meth- ods in terms of both exploration and zero-shot transfer to downstream tasks.
INTRODUCTION
Reinforcement learning methods have attained impressive results across number of domains (e.g.. Berner et al. (2019); Kober et al.] (2033: Levine et al. (2016): Vinyals et al. (2019)). However, current RL methods typically require large number of samples for each new task (Dann et al.] 2018). In other areas of machine learning, an effective way to mitigate high data requirements has been the use of unsupervised or self-supervised learning (Sutskever et al.) 2014| Radford et al.) 2019). Similarly, humans and animals seem be able to learn rich priors from their own experience without being told what to do, and children engage in structured but unsupervised play in part as a way acquire functional understanding of the world (Smith & Gasser 2005). Based on this intuition, unsupervised RL methods rely on intrinsic motivation (IM): task-agnostic objectives that incentivize the agent autonomously explore the world and learn behaviors that can be used to solve a range of downstream tasks with little supervision. A general strategy is to exactly or approximately express this task-agnostic objective in the form of a reward function that uses only environment statistics, and then optimize it using standard RL algorithms.
reasonable goal for a good unsupervised learning algorithm is to fully explore the state space of the environment, since this ensures the agent will have the experience which with to learn the optimal policy for a downstream task. Therefore, past work on IM has frequently focused on novelty-seeking agents that maximize surprise or prediction error (Achiam & Sastry] 2017) Schmidhuberr 1991 Ya-
mamoto & Ishikawa 2010 Pathak et al.) 2017 Burda et al. 20188) However, these methods are vuinerable to becoming distracted by inherently stochastic elements of the environment, such "noisy TV" (Schmidhuber 2010). In contrast, active inference researchers inspired by biological agents have focused on developing agents that seek to control their environment and minimize sur- prise (Friston 2009 Friston et al.) 2009; 2016 Berseth et al., (02T). These methods suffer from the opposite issue, the "dark room problem", ", in which surprise- minniiiin agent in low-entropy

---

Under review as a conference paper at ICLR 2022
Learning
Control
Explore
Control
Explore
Figure I: Adversarial Surprise is multi-agent competition in which two policies take turns con- trolling a single agent. The Explore policy acts first, and tries to put the agent into surprising, high entropy states. On its turn, the Control policy tries to minimize surprise by finding familiar, low-entropy, predictable states. As training continues, the competition drives the agents learn increasingly complex behaviors. In the above example, the Control policy eventually learns to pick up a key and lock the door to prevent the Explore agent from taking into the room with randomly moving objects (a noisy TV state).
environment does not need to learn any behaviors all order satisfy its objective (Friston al. 2012). Yet humans seem to maintain a balance between optimizing for both novelty and familiarity. For example, a child in play room does not just try to toss their toys the floor in every possible pattern, or immediately put them away in the toy box, but instead tries to stack them together, find new uses for parts, or combine them in various structured ways.
We argue that an effective unsupervised RL method should find the right balance between explo- ration and control. With this goal in mind, we introduce new algorithm based on an adversarial game between two policies, which take turns sequentially acting for the same RL agent. 'he goal of the Control policy to minimize surprise, by learning to manipulate its environment in order to return safe and predictable states. In turn, the Explore policy is novelty-seeking, and attempts to maximize surprise for the Control policy, putting it into a diverse range of novel states. When combined, the two adversaries engage in arms race, repeatedly putting the agent into challenging new situations, then attempting to gain control of those situations. Figure Saarre&Sshe shows an illustration of the method, including a sample interaction. Rather than simply adding noise to the environment, the Explore policy learns to adapt to the Control policy, and to search for increasingly challenging sit- uations from which the Control policy must recover. Thus our method, Adversarial Surprise (AS), leverages the power of multi-agent training to generate curriculum of increasingly challenging exploration and control problems, leading the emergence of complex, meaningful behaviours.
The contributions of this paper are: i) The Adversarial Surprise algorithm: ii) Theoretical results which prove that when the environment formulated as a stochastic Block MDP (Du et al., 2019), traditional surprise-mxxiizzing methods will fail to fully explore the underlying state space, but Adversarial Surprise will succeed; iii) Empirical evidence which supports the theoretical results, and shows that AS fully explores the state space of both Block MDPs and traditional benchmark- ing environments like VizDoom: iv) Experiments that compare AS to state-of-the-arr unsupervised RL basclines Random Network Distillation (RND) (Burda al. 2018). Asymmetric Self-Play (ASP) (Sukhbaatar et al., 2017). Adversarially Guided Actor- Critic (AGAC) (Flet-Berliac et al.) 2021) and Surprise Minimizing RL (SMiRL) (Berseth et al.) (02T). and show that AS is able to explore more effectively, learn more meaningful behaviors, and achieve higher task reward when transferred zero-shot common benchmarking environments Atari and VizDoom. Videos of agents are available on the project website: adversarialsun wwwarrrssssupsssee........ae.see home) and show that AS is able learn interesting, emergent be- haviors in Atari, VizDoom, and MiniGrid, even without ever having trained with the game reward.
google. wwwo///oo//iiereeeeeeeeeeeeeeeee
2 RELATED WORK
Novelty-seeking and exploration methods lead the agent to increase coverage of the environment.
A simple way to implement novelty-seeking is to maximize the prediction error of world model
Ishikawa 2010 Pathak et al. 2017] Burda et al. 2018 Raileanu & Rocktäschell 2020 Zhang al. (2020b). Random Network Distilla- tion (RND) (Brdda et al. (0188) a highly effective example of one such method. However, a major
(Achiam & Sastry 2017; Schmidhuber 1991] Yamamoto
problem of prediction-errorbbase methods is that the intrinsic reward is not useful when the envi-
2

---

Under review as a conference paper at ICLR 2022
ronment contains aleatoric uncertainty, iec inherently stochastic elements. This problem is often referred to as the noisy TV problem, after Schmiicuhhrrr (2010) used the example of an agent becom- ing stuck staring at static TV screen. We show in this work that RND is indeed vulnerable to this problem. performing poorly in stochastic environments.
Several works have proposed solutions to deal with aleatoric uncertainty. For example, some ap- proximate information gain on the agent's 's dynamics model of the environment (Houthooft et al.) 2016 Still & Precup 2012: Bellemare al. 2016 Pathak et al. [0177] (Schmidhuberr [191]) using variational Bayes or ensemble disagreement (Shyam et al. 2019; Pathak et al. 2019 Houthooft al. 2016). However. implementing such Bayesian procedures is difficult, because requires scal- able and effective modeling of epistemic uncertainty. which itself is a major open problem with high-dimensional models such as neural networks (Bhattacharya & Maiti 2020). Another method based on maximizing information gain between the agent's ' actions and future state is known as em- powerment (Klyubin et al., 2005 Salge et al.) 2014, Bysenbach et al.] 2018 [Sharma et al. 2019). but can also be difficult to approximate for high-dimensional states (Karl et al. 2015 Zhao et al. 2020 de Abril & Kanai 2018 Zhang et al. 2020a] Mohamed & Rezende 2015 Gregor et al. 2016 Hansen et al.) 2019). Instead of attempting to directly approximate information gain, approach maximizes state coverage via an adversarial competition over observation entropy. As we will show, this recovers an effective coverage strategy even in the presence of rich, stochastic observations, and performs well in practice.
The asymptotic policy learned by standard novelty-seeking methods is not exploratory. Recent work tries to learn a policy that approximately maximizes the state marginal entropy at convergence (Hazan et al. 2019 Lee et al. 2019). The state marginal entropy is hard to compute in general, and recent work has proposed various approximations (Seo et al. 2021 Liu & Abbeel [02T]] Mutti al., 2021). We prove that even with only noisy observations of the underlying state, our method asymptotically maximizes the state marginal entropy at convergence under some assumptions.
Surprise minimization and active inference: The design of the Control agent in our method draws on ideas from surprise minimization and active inference (Friston) 2009) Friston et al., 2009: 2016). The free energy principle, originating in the neuroscience community, argues that complex niche- secking behaviors of biological systems are the result of minimizing long-term average surprise on system sensors, leading agents to stay in safe and stable states (Friston) 2009). SMiRL is an unsupervised RL method that leverages surprise minimization stabilize an otherwise chaotic environment (Berseth et al.] 2021). However, such approaches require strong assumptions on the stochasticity of the environment. In low-entropy environments, surprise minimization will not lead to learning interesting behavior due to the dark room problem. in which the agent is not incentivized to explore the environment find better niche (Friston et al.) 2012)_ Our method does not require that the env is stochastic, since the Explore agent itself drives the Control agent into situations from which surprise minimization is challenging.
means to discover skills that
Multi-Agent competition has been shown to drive the emergence of complex behavior (Baker et al.
2019 Dennis et al. 2020 Xu et al. 2020 Leibo et al. 2019 Schmidhuber [1977] Campero et al., 2020 Asymmetric Self-Play (ASP) aims to learn increasingly complex skills via a competition between two policies, where one policy (Bob) tries to imitate or reverse the trajectory of the other policy (Alice) (Sukhbaatar et al.] [017] OpenAl et al., 202T). Our empirical results compare to ASP, and demonstrate that it can fail in stochastic environments, because Alice can easily produce random trajectories which are very difficult for Bob to imitate. Similar to ASP, Adversarially-Guuiee Actor Critic (AGAC) (Fret-Berliac et al.) 202T) introduces an adversary agent which attempts to mimic the action distribution of the actor, while the actor tries to differentiate itself from the adversary. Like these methods, Adversarial Surprise uses a two-player game to induce exploration and emergent complexity. However, our objective is general and information--heeretie focusing on minimization or maximization of surprise rather than reaching specific states. Unlike these methods, we pro- vide theoretical results showing AS provides a principled approach to maximizing state coverage in stochastic environments. Finally, our method is reminiscent of recent work that learns separate exploration and exploitation policies but without competition between them (Badia et al. 2020b a Campos et al. 2021)
3

---

Under review as a conference paper at ICLR 2022
3 BACKGROUND
where 8 E S are states, a E A are actions, r(a,s) 8) is the reward function, and y E [0, 1) is a discount factor. At each timestep an RL agent selects action a, according to its policy x [s)) receives reward r(a,, st), and the environment transitions to the next state according to (s ot). The agent uses RL to maximize its cumulative discounted reward over the episode: R = Σt= ('r"(at,
Markov Decision Process (MDP): An MDP is tuple (S,A,T,r,)) ,T,
Block MDP (BMDP): BMDP (Du et al., 2019) extends the MDP formalism to the case where the agent cannot observe the true state but rather observes rich observations 0~ p(O]s). Unlike traditional partially-observed MDP (POMDP), a BMDP has an additional disjointness assumption: for any 8, 8 E S, o s' = supp(p(() s)) n supp(p(O) x)) 0. The same assumption has been used in several prior works (Azizzadenesheli et al. 2016 Dann et al. 2018: Krishnamurthy et al.) 2016 Misra et al. 2020), and enables the BMDP to naturally capture a wide range of environments which have rich, high-dimensional observations. We are interested in stochastic BMDPs, in which the observation distribution is inherently entropic for some states, i.e. 3s H (p(Oss)) O, where H is the entropy. This is a conceptual model of stochastic environments with uncontrollable factors.
Maximizing state marginal entropy: The state marginal distribution d (s) of policy æ is the probability that the policy visits state s: (s) = Ea-a.s-Il7 Et 1st = s)] (Lee et al, 2019). The observation marginal density is defined analogously:
1 T
d' (0) = -
Σ t=
11 =o)
(1)
We are interested in agents that are able to fully explore the underlying state space of a stochastic BMDP; that is, agents that can maximize the entropy of the state marginal distribution: H Hdd However, in the context of a BMDP, agents cannot directly observe the underlying state and must attempt to maximize H (s)) purely through their ability to alter d= do))
4 ADVERSARIAL SURPRISE
The design of our method is guided by the following desiderata: It should be able to learn mean- ingful behaviors even if the environment has high-dimensional, stochastic observations, and avoid the noisy TV problem. Thus, our method should favour low-entropy states when possible, while still seeking novelty. ii) It should enable the emergence of skills. Since multi-agent training can lead to the emergence of complex skills, we create a multi-agent adversarial game between two policies. iii) The optimized objective should be theoretically sound, in the sense that we can provably show that it optimizes a well-defined exploration metric under some assumptions. In our case, we will show that our two-player game maximizes coverage of the underlying state space of stochastic BMDP.
To achieve these goals, we design an adversarial game that pits two policies against each other in a competition over the amount of surprise encountered through exploration. Specifically, learn an Explore policy, x and a Control policy, c The goal of the Control policy is to minimize its own surprise, or observation entropy, using learned density model po(o). The Explore policy's goal is to maximize the surprise that the Control policy experiences. The policies take turns taking actions for the agent, switching back and forth throughout the episode. To simplify notation, assume the policy taking actions switches every k steps, such that for the first k steps, at 7 (a(aa (the Explore policy acts), then for timesteps continue switching until the end of the episode. Each policy is given & steps to act to enable it to reach states that will be challenging for the other policy to recover from, thus facilitating learning more complex and long-term exploration and control behaviors (see Figure B).
2k, at (aelo,) (the Control policy acts). The policies
Surprise is computed using a learned density model that estimates the agent's likelihood of expe- riencing observation o, po po()). Following Berseth et al. (2021). po(o) is re-initialized each episode and trained using maximum likelihood estimation (MLE) to fit the observations of the agent within single episode, which are stored in buffer 3. The density model is either represented using multivariate Gaussian distribution fit to the pixels within o (as in Berseth et al. (202T)) or using independent categorical distributions for each pixel. For more details see Appendix
4

---

Under review as a conference paper at ICLR 2022
Because the Control policy is surpris-minimizzee its reward is r = log (o()), which resembles SMiRL (Berseth et al. 202T). except using the observation in place of the state. The goal of the Explore policy is to maximize the observation surprise during the Control agent's 's turn. This creates an adversarial game, in which the Explore policy attempts to find surprising situations with which to expose the Control policy, and the Control policy's objective is to recover from them. Therefore, the Explore policy's reward is based on the surprise for the observations of the Control policy. Assume that the Control policy's turn begins timestep to, and it receives a total reward of Rt
Lt=c +k 7t log (ot) for that turn. Then, the Explore policy's ' reward is - R², and is applied to the last timestep of the Explore policy's turn (i.e. timestep 1 - 1). Thus, Adversarial Surprise defines the following adversarial game between the two policies:
c++
max min ST
TE
logpo(ar) t=
Σ
STC
where the Explore policy can only effect po(or) through the final state that it produces at the end of its tumn which is the initial state for the Control policy. Algorithm [ (Appendix D gives the full training procedure.
We can show that optimizing these rewards leads the two players to compete over the amount of observation entropy, where the Explore policy's " objective is to maximize observation entropy:
c0 +
JB JB= = Σ L=
log Po()) = H(d'' (o)),
(3)
And the Control policy's 's goal is to minimize its observation entropy: - (dd=c(o)) We prove the relationship between log (o) and the observation entropy in Appendix A
Implementation details: We parameterize the policies for the Explore and Control policy using deep neural networks (NN) with parameters d² and ΦC, respectively. The policy is based on convolutional NN, which takes in the last 4 observation frames. The networks are trained using Proximal Policy Optimization (PPO) (Schulman et al. 2017); further details are given in Appendix C We have found it helpful to only compute the surprise reward using observations from the second half of the Control policy's turn. This gives the agent greater ability to take actions that may lead to initial surprise, but reduce entropy over the long term. Finally, we allow the Explore and Control policys to act for a different number of timesteps (that is, we have separate k.C and h. enabling us to tune the emphasis on exploration or control depending on the environment.
4.1 ADVERSARIAL SURPRISE MAXIMIZES STATE COVERAGE IN BLOOK MDPs
We will show that AS covers the underlying state space of a Block MDP, under some assumptions about the density of states with low observation entropy. Full proofs are in Appendix A
We are interested in maximizing the entropy of the marginal state distribution (s)). using a density model of the observation, po(o). To that end, prove the following lemma in Appendix A
Lemma 1. The cumulative surprise measured by the observation density model po po(o) forms an up- per bound the observation marginal entropy H (d (o)), which becomes tight when the observation density model fits the observation marginal d (o): -Ex Eizo log po (o.) ) Z H (d (o)).
Lemma 2. Given the disjointness assumption of the BMDP stated in Section 3
we show useful
relation between observation marginal entropy and state marginal entropy:
(dd (o)) = RRz Hpp(O) = s)) + H(d'
See Appendix A for the proof. Equation shows that maximizing entropy in the marginal obser- vation distribution d' (o) amounts to maximizing two terms: the emission entropy H (p(O)))), and the state marginal entropy H (dd"(s).
Denote by HRND the state stationary distribution of an RND agent trying to maximize the obser- vation stationary distribution. follows by lemma that HRND is the solution to the entropy- regularized L.P
,RND = aarg max h1 (1))
5

---

Under review as a conference paper at ICLR 2022
where h is the vector indexed by S giving the emission entropy of all states. This program has ea closed form solution which given by PRND; = E, Therefore, the distribution exponentially favors states with high emission entropy. This explains why algorithms which maximize observation entropy fail to explore environments with noisy TV states.
In Adversarial Surprise, the Controller policy is actively trying to transform the observation distri- bution given by the Explorer policy into low entropic distribution after T steps. Therefore the objective can be written as
min max (Mp, h) H(Mp)
where M must lie in {P is stationary policy). Therefore the Explorer policy is now strained to find a maximum in the image of M. We provide now sufficient condition on the structure of the BMDP such that the Control policy can choose matrix M that induces the Explore policy to maximize the state entropy by maximizing the observation entropy after 7 steps.
We first define (semiquasi metric on the latent state space: d(ss,) 8') ) = min 3m, Pk (8'1s) = 1}, where by convention PT (s]s) = 1 for all In other words, d(s,,') & if there is policy that reaches s' from 8 steps with probability 1. We symmetrize this metric by defining the following semimetric: d(s, s') = max dd(s, s'), d(ss,s)}
Definition 1. We now give a formal definition of "dark rooms". We say that a state s a dark room if it has minimal emission entropy: (p((SSS = s)) = min.es (p(OSSS=== s)).
Assumption 1. We assume that for every state s, there is a dark room such that d(s, s') = That is, the there is dark room can be reached in exactly T steps.
dark rooms is T-cover of the state space with respect d, and from every state
We can now state our main result:
Theorem 1. Under the BMDP assumption and Assumption the Markov chain induced by the following AS game:
max min (df d' (ao) 1.7 (s(s0)
T-covers the latent state space, i.e., for all states s, there is state s' such that d= ds'ss) ) > O and d(s, 8') ST, T, where d the state marginal distribution induced by the game between the Explore (TT) and Control (#c) policies.
Proof. (sketch.) Assumption [ guarantees that for any states that the Explore policy reaches, the Control policy can find a low-emission-entropi state within its turn (T timesteps), that (p()ss) minimized. Thus, by Lemma 2 when the Control policy is factored out, the objective of the Explore policy becomes:
- ((d"
(5)
Therefore the Explore policy's objective is to maximize coverage of the BMDP state space.
5 EXPERIMENTAL RESULTS
We now present experimental results designed to assess the following questions:
Q1. State coverage: How well does AS explore the underlying state space stochastic BMDP, as compared to baselines? Given the theoretical results in Section 4.1 we hypothesize that AS will fully explore the environment, but other methods will become distracted by stochastic elements.
Does AS learn behaviors that are useful for downstream tasks? To assess this, we train AS and baseline methods using only intrinsic reward, then transfer the agents zero-shot to standard benchmark environments in Atari (Bellemare et al.) (013) and VizDoom (Kempka al. 2016b), and measure the amount game reward obtained. While there no reason to expect AS to always correlate with the objectives in arbitrary MDPs, expect that the twin goals of maximizing
Q2. Zero-shot transfer:
AS performance measured the full episode, including both the Explore and Control turns.

---

Under review as a conference paper at ICLR 2022
Number of toome Wtated
-.5
Ramber of Roomm
-5
ASP
1.75
2.30
1.25
1.0
1.00
(a) Environment
Stop
stop
(b) Cumulative exploration
(c) Exploration within episode
the number of rooms (out of 4) explored both (b) cumulatively over training, and (c) within an episode. AS explores better than the state-of-the-as exploration methods RND and ASP, which become distracted by noisy elements. AS outperforms SMiRL, which minimizes observation surprise by turning to face the wall, or remains in dark rooms.
Figure 2: State coverage in stochastic BMDPs:
coverage while achieving high control should correlate well with objectives in many reasonable MDPs. This is particularly true of games, which have notion of progress that roughly corresponds to coverage, but at the same time have many dangerous states that could result in 'death', which leads to unexpected jump back to the starting state. We hypothesize that AS should, without even being aware the task reward, perform well in these environments. Comparing to prior methods in these domains is interesting, because prior work has variously argued that both novelty-secking exploration methods (Burda et al., 2018) and cuprrse-minimizeee should be expected to achieve high scores in these games.
methods (Berseth et al.) 2021
Q3. Emergence of complexity: If AS is able to achieve high zero-shot transfer performance, we hy- pothesize that it will be because the adversarial game drives the acquisition of increasingly complex observable behaviors. Therefore, we track the emergence of specific skills throughout training, and qualitatively examine final performance benchmark environments identify meaningful skills.
Baselines: We compare AS to four competitive unsupervised RL baselines: i) Asymmetric Self- Play (ASP) (Sukhbaatar al., 2017), a state-of-the-art multi-agent curriculum method; ii) Random Network Distillation (RND) (Burda et al.) (2088), a state-of oftte-of-the-arr exploration method; iii) Adver- sarially Guided Actor-Critic (AGAC) (Flet-Berliac et al., (02I). recently proposed adversarial exploration method; and iv) Surprise Minimizing RI. (SMiRL. (Berseth et al., (021), a recently proposed intrinsic motivation based on active inference. All methods use same PPO implemen- tation, with hyperparameters given in Appendix
Environments: To evaluate the above hypotheses, we use three types of environments. To obtain environments that match the precise specifications of the stochastic BMDP formalism, and present an exploration challenge, we constructed a custom family of procedurally generated navigation tasks based on MiniGrid (Chevalier- Boisvvrrrr et al. 2018). These environments contain rooms that are ei- ther empty (dark), or contain stochastic elements such as flashing lights that randomly change color. They also contain elements such doors that be opened with keys, and switches that, when flipped, stop or start the stochastic elements moving. As in MiniGrid, the agent only sees a 5x5 window of the true state. Each room of size 12 represents hard exploration task for the agent (see Figure 2ab. While gridworlds allow us to easily interpret the results and behaviors of the agent, and were used by ASP, SMiRL, and AGAC, we also compare prior work on two standardized benchmarks with high-dimensional observations. Specifically, we use Atari ALE (Bellemare et al., 2013). which was used by both SMiRL and RND to establish their effectiveness, and the ViZDoom environment (Kempka et al. 2016b), which was used by AGAC and SMiRI. Due to limited compu- tational resources, we do not conduct experiments in all possible Atari games (which consistent with prior work (Berseth et al. 2021 Burda et al. 2018)), but we do not cherry-pick results; show results for each of the games that we test.
Q1: State coverage: We measure state coverage in the procedurally-generated BMDPs using the number of rooms the agent visits (since many different observations can be generated from a single room). The results for all algorithms are shown in Figure 2 We measure coverage cumulatively, over the course of training (Figure 2b). to assess whether each method will lead the agent to collect experience from all possible states. This measure is relevant whether the technique be used
7

---

Under review as a conference paper at ICLR 2022
(a) Assault
(b) Berzerk
(c) Freeway
(d) Space Invaders
Figure 4: Zero-shot transfer in Atari: Each method is trained in Atari using only intrinsic reward, then transferred zero-shot to optimizing game reward. Plots show game reward, where error bars are the 95% Confidence Interval (CI) of seeds. The games reward behavior such as staying alive and shooting enemies, so obtaining higher reward indicates the agent has learned meaningful behaviors. Across 3/4 environments, AS outperforms RND, ASP, AGAC, and SMiRL, showing AS provides a general way to learn useful behaviors in the absence of external reward.
as an effective exploration bonus to aid learning a downstream task. We also measure the number of rooms explored within each episode (Figure 2cb. This allows us assess whether the asymptotic policy learned by the algorithms continues to explore once has converged.
As predicted by our theoretical analysis, learns to more fully explore the environments than prior work, visiting all possible rooms over a lifetime (Figure 2b) and significantly more rooms per episode (Figure2c)). learns more quickly and explores more thoroughly than RND, which becomes distracted by stochastic elements that lead to high prediction error. Stochasticity also hin- -10 ders learning for ASP, since Alice can easily produce ran- dom goals that are difficult for Bob to replicate. Finally, that SMiRL, which is designed for fully observed environments, does not explore effectively because it suf- fers from the dark room problem it prefers stay within the empty rooms, and not venture into rooms with high- entropy, stochastic elements.
that AS
Doom environment
log pio)
(b) AS (ours)
10g D(S)
10
15
(c) RND
1og pic)
Figure 3 shows coverage of the latent state space in the VizDoom Take Cover environment as positions along the x-axis. In this environment, agents navigate horizontally while seeing partial view of the underlying state. Figure reveaas that only AS covers all the positions in the map in the first 1000 train steps, whereas RND fails to explore the edges, and SMiRL fails to explore the right edge.
-15
200
400
600
Doom position
(d) SMiRL
Figure 3: State coverage in Doom: the heatmaps show logp(s) over the first 1000 training steps, where s the agent's x-axis position in Doom. Black areas indicate p(s) O, meaning the agent has never visited these coordi- nates. These results show that AS fully explores the state space, while RND fails to explore both edges and SMiRL fails to explore the right edge.
Q2. Zero-shot transfer: Figures and 5 show how each method performs when transferred zero- shot to the task of optimizing game reward in sev- eral Atari environments and VizDoom. Because the game rewards complex behaviors like shooting or avoid- ing enemies, a high game reward indicates the agent has learned interesting skills, purely from optimizing the in- trinsic objective. Across the environments, AS performs better than RND, SMiRL, AGAC, and ASP. While RND is sometimes effective, its performance often decreases over time due the bonus from the prediction error shrinking as more states become familiar. Further, maximizing novelty in environments like Freeway. Space Invaders. and Doom can lead to the agent dying. corresponding to low reward. SMiRL performs best in Freeway, where minimizing entropy corresponds closely to staying alive and not being hit by cars. However, SMiRL. performs poorly in the other environments because it avoids entropy by hiding from enemies (stay- ing in dark rooms when they are available). ASP also performs poorly because it is possible for Alice to quickly reach states which Bob cannot easily replicate, preventing the algorithm from learning meaningful behaviors. For AGAC, the adversary cannot accurately predict the actions of the agent given an observation when the observation has a high entropy emission probability. In contrast, AS consistently obtains high returns across all environments, indicating that optimizing for both explo-
8

---

Under review as a conference paper at ICLR 2022
ration and control provides a broadly useful inductive bias for learning interesting behaviors in the absence of external reward.
Q3. Emergence of complexity: Due to space con- straints, we show results for the emergence series of interesting behaviors in the BMDP environments in Ap- pendix B Figure / reveals that the multi-agent game in- duced by AS leads
RAUD SMIRL AGAC
Spicoda Ramare
curriculum with multiple training phases: the Control agent first learns to go to dark room, the Explore agent learns to go back the Control agent responds by learning to lock door to make more difficult for the Explore agent to expose it to surprising states. This highlights the potential of Ad- versarial Surprise to learn long-term surpris--miniiiziig behaviors. Figure demonstrates that RND and ASP do not learn to try taking even simple actions to control the environment, such as flipping switch to stop stochas- tic elements from moving. In AGAC, the actor chooses actions that maximize the discrepancy between its policy and the Adversary's. Although this proves to be effective for exploration between subsequent trajectories, shown in Figure 55 the interaction between the Control and Ex- plore policies in Adversarial Surprise able facilitate more complex behaviors by not only finding novel states to explore but determining when to exhibit control over safe states. The emergence of interesting behaviour both Atari and Vizdoom is evidenced in the videos available at: hhtpps: ditessgooggle com/ corp / ewweew///e adversar a surpri piprisse /homel Purely through opti- mizing the Adversarial Surprise objective, AS agents learn complex behaviors such as hiding from enemies behind walls or barriers, shooting enemies in Space Invaders, Berzerk, Assault, and Doom, and hopping across the road in Freeway.
250
noisy TV, and
200
150
Figure 5: Zero-shot transfer in Doom. Consistent with the Atari results, AS learns more meaningful behaviors (i.e. moving while avoiding enemy bullets) than other techniques. This leads to higher environment reward.
6 DISCUSSION
We proposed Adversarial Surprise general approach for unsupervised RL. Adversarial Surprise corresponds to two-player adversarial game, in which two policies compete over the amount of surprise, or observation entropy, that an agent experiences. Reminiscent of Dr. Jekyll and Mr. Hyde, the Explore policy acts expose the Control policy highly entropic states from which it must recover by learning to manipulate the environment. We show that AS produces increasingly complex control and exploration strategies, and is able to address exploration in stochastic Block MDPs. In such environments, prior methods can become distracted by noisy elements, or suffer from the dark room problem. We show both theoretically and empirically that AS is robust against these issues, and learns to explore the environment more thoroughly, and control it more effectively. than state-of-the-art prior works like RND, ASP, AGAC, and SMiRL.
Future work: Our evaluation of AS focuses on coverage and unsupervised exploration, where we demonstrate that AS improves over novelty-seeking, surprise minimization, adversarial, and goal- setting methods in stochastic BMDPs and standard benchmarks like Atari and Doom. However, the potential value of unsupervised RL methods extends more broadly: such methods could be used to acquire skills for downstream task learning, controlling an environment to reach states from which more behaviors could be performed successfully. Future work could study how AS and its extensions could enhance applications like robotics, for example by collecting data for downstream reward-guided learning. Further, we see a potentially exciting method which combines AS with hierarchical RL, by training meta-policy to select when to invoke the Explore and Control sub- policies. this way, the meta-policy could explicitly decide when to explore and when to exploit.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Joshua Achiam and Shankar Sastry. Surprise-based intrinsic motivation for deep reinforcement learning. arXiv preprint arXiv: 2017.
Kamyar Azizzadenesheli, Alessandro Lazaric, and Animashree Anandkumar. Reinforcement learn- ing of pomdps using spectral methods. In Conference on Learning Theory, pp. 193-256. PMLR, 2016.
Adrià Puigdomenech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvitskyi, Zhaohan Daniel Guo, and Charles Blundell. Agent57: Outperforming the atari human benchmark. In International Conference on Machine Learning, pp. 507-517. PMLR, 2020a.
Adrià Puigdomènech Badia, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, Bilal Piot, Steven Kapturowski, Olivier Tieleman, Martín Arjovsky, Alexander Pritzel, Andew Bolt, et al. Never give up: Learning directed exploration strategies. arXiv preprint arXiv:2002.06038, 2020b.
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. arXiv preprint arXiv:1909 07528, 2019.
Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279, 2013.
Marc G Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. arXiv preprint arXiv:1606.00 01006.0008..... 2016.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning, arXiv preprint
2019.
Glen Berseth, Daniel Geng, Coline Manon Devin, Nicholas Rhinehart, Chelsea Finn, Dinesh Ja- yaraman, and Sergey Levine. Smirl: Surprise minimizing reinforcement learning in unstable environments. 2021. URL /ttp:////////eeeeeeeee net 1ttpr/oooomm---ooooooooo.
Shrijita Bhattacharya and Tapabrata Maiti. Statistical foundation of variational bayes neural net- works. arXiv preprint arXiv:2006. 15786, 2020.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprint 18/0. /2894, 2018.
Andres Campero, Roberta Raileanu, Heinrich Küttler, Joshua B Tenenbaum, Tim Rocktäschel, and Edward Grefenstette. Learning with amigo: Adversarially motivated intrinsic goals. arXiv preprint 2rXiv:2006.1211 2020.
Víctor Campos, Pablo Sprechmann, Steven Stenberg Hansen, Andre Barreto, Steven Kapturowski, Alex Vitvitskyi, Adria Puigdomenech Badia, and Charles Blundell. Beyond fine-tuning: Transfer- ring behavior in reinforcement learning. In ICML 2021 Workshop on Unsupervised Reinforcement
Learning. 2021.
Maxime Chevalier-Boisvert, Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. attps: /ttgtttttuu//aa
2018.
Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert Schapire. On oracle-efficient pac rl with rich observations. arXiv preprint arXiv: 1r00006803.00006, 2018.
Ildefons Magrans de Abril and Ryota Kanai. A unified strategy for implementing curiosity and empowerment driven reinforcement learning. arXiv preprint arXiv:/806.000 2018
Michael Dennis, Natasha Jaques, Eugene Vinitsky, Alexandre Bayen, Stuart Russell, Andrew Critch, and Sergey Levine. Emergent complexity and zero-shot transfer via unsupervised environment design. arXiv preprint arXiv:2012.02099 2020.
10

---

Under review as a conference paper at ICLR 2022
Prafulla Dhariwal, Christopher Hesse, Oleg Klimov, Alex Nichol, Matthias Plappert, Alec Radford, John Schulman, Szymon Sidor, Yuhuai Wu, and Peter Zhokhov. Openai baselines. https: 2017.
//github. wttp:///oooopaaaaaas.ainoo
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. In International Conference on Machine Learning, pp. 1665-1674. PMLR, 2019.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity all you need: Learning skills without a reward function. arXiv preprint wrXiv:1802.06000 2018.
Yannis Flet-Berliac. Johan Ferret, Olivier Pictquin, Philippe Preux, and Matthieu Geist. Adversari- ally guided actor-critic. arXiv preprint urXiv:21020443 2021.
Karl Friston. The free-energy principle: rough guide to the brain? Trends in cognitive sciences, 13(7):293-301, 2009.
Karl Friston, Christopher Thorton, and Andy Clark. Free-energy minimization and the dark-room problem. Frontiers in psychology, 3:130, 2012.
Karl Friston, Thomas FitzGerald, Francesco Rigoli, Philipp Schwartenbeck, Giovanni Pezzulo, et al.
Active inference and learning. Neuroscience & Biobehavioral Reviews, -8799, 2016.
Karl J Friston, Jean Daunizeau, and Stefan J Kiebel. Reinforcement learning or active inference? PloS one, 4(7):e6421, 2009.
Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. arXiv preprint arXiv:1611.07500 2016.
Steven Hansen, Will Dabney, Andre Barreto, Tom Van de Wiele, David Warde-Farley, and Volodymyr Mnih. Fast task inference with variational intrinsic successor features. arXiv preprint arXiv: 05030, 2019.
Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. In International Conference Machine Learning, pp. 2681-2691. PMLR, 2019.
Rein Houthooft, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. Vime: Variational information maximizing exploration. arXiv preprint 160.09960,.09 2016.
Maximilian Karl, Justin Bayer, and Patrick van der Smagt. Efficient empowerment. arXiv preprint 150.005509 2015.
Michal Kempka, Marek Wydmuch, Grzegorz Runc, Jakub Toczek, and Wojciech Jaskowski. Vizdoom: A doom-based AI research platform for visual reinforcement learning. CoRR, abs/1605.020977, 2016a. URL htttp:://acxi..oog///sss.sseesss
02097
Michal Kempka, Marek Wydmuch, Grzegorz Runc, Jakub Toczek, and Wojeiech Jaskowski. ViZ- Doom: A hoom-based AI research platform for visual reinforcement learning. In IEEE Con- ference on Computational Intelligence and Games, pp. 341-348, Santorini, Greece, Sep 2016b. IEEE. htlhtttppaaxxi...ot/ wwtp:////...bb.....ooom. 02097 The best paper award.
Alexander Klyubin, Daniel Polani, and Chrystopher Nehaniv. All else being equal empow- ered. In European Conference on Artificial Life, pp. 744-753. Springer, 2005.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32(1 (111))223--1244 1274, 2013.
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. arXiv preprint arXiv:1602.02722. 2016.
Lisa Lee, Benjamin Eysenbach, Emilio Parisotto, Eric Xing, Sergey Levine, and Ruslan Salakhutdi- nov. Efficient exploration via state marginal matching. arXiv preprint arXiv: (tto:::90600222 2019.
11

---

Under review as a conference paper at ICLR 2022
Joel Z Leibo, Edward Hughes, Mare Lanctot, and Thore Graepel. Autocurricula and the emergence of innovation from social interaction: A manifesto for multi-agent intelligence research. arXiv preprint arXiv:1903.00742, 2019.
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training deep visuo- motor policies. The Journal of Machine Learning Research, 17(1):1334-1373 2016.
Hao Liu and Pieter Abbeel. Behavior from the void: Unsupervised active pre-training. arXiv preprint 1rX11:2103.04551, 2021.
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state ab- straction and provably efficient rich-observation reinforcement learning. In International confer- ence on machine learning. pp.
PMLR, 2020.
Shakir Mohamed and Danilo Jimenez Rezende. Variational information maximisation for intrinsi- cally motivated reinforcement learning. arXiv preprint arXiv: MXXiv:550900875 2015.
Mirco Mutti, Lorenzo Pratissoli, and Marcello Restelli. Task-agnostic exploration via policy gra-
dient of a con-parametric state entropy estimate. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp.
2021.
OpenAl OpenAI, Matthias Plappert, Raul Sampedro, Tao Xu, 1lge Akkaya, Vineet Kosaraju, Peter Welinder, Ruben D'Sa Arthur Petron, Henrique Ponde de Oliveira Pinto, et al. Asymmetric self-play for automatic goal discovery in robotic manipulation. arXiv preprint arXiv:2101.0488. 2021.
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In International Conference on Machine Learning, pp. 2778-2787. PMLR, 2017.
Deepak Pathak, Dhiraj Gandhi, and Abhinav Gupta. Self-supervised exploration via disagreement. In International Conference on Machine Learning, pp. 5062-5071. PMLR, 2019.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
Roberta Raileanu and Tim Rocktäschel. Ride: Rewarding impact-driven exploration for senoodurally-geeeratee environments. arXiv preprint arXiv:2002.12292, 2020.
Christoph Salge, Cornelius Glackin, and Daniel Polani. Empowerment-et an introduction. In Guided Self-Orgunization: Inception, pp. 67-114. Springer, 2014.
Jürgen Schmidhuber. A possibility for implementing curiosity and boredom in model-building neu- ral controllers. In Proc. of the international conference on simulation of adaptive behavior: From animals to animats, pp. 22222222222222222222222222 227, 1991.
Jürgen Schmidhuber. What's interesting? IDSIA Technical Report, 1997.
Jürgen Schmidhuber. Formal theory creativity, fun, and intrinsic motivation (1990-2010). IEEE Transactions Autonomous Mental Development, 2(3):230-24) 2010.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347. 2017.
Younggyo Seo, Lili Chen, Jinwoo Shin, Honglak Lee, Pieter Abbeel, and Kimin Lee. State entropy maximization with random encoders for efficient exploration. arXiv preprint arXiv:2102.094300 2021.
Archit Sharma, Shixiang Gu, Sergey Levine, Vikash Kumar, and Karol Hausman. Dynamics-aware unsupervised discovery of skills. arXiv preprint arXiv:1907.011 2019.
Pranav Shyam, Wojciech Jaskowski, and Faustino Gomez. Model-based active exploration. In International Conference Machine Learning, pp. 5779-5788. PMLR, 2019.
12

---

Under review as a conference paper at ICLR 2022
Linda Smith and Michael Gasser. The development of embodied cognition: Six lessons from babies. Artificial life, 11(1-2):13-29 2005.
Susanne Still and Doina Precup. An information-thherrtiic approach to curiosity-driven reinforce- ment learning. Theory in Biosciences, 131(3):139-145, 2012.
Sainbayar Sukhbaatar, Zeming Lin, Ilya Kostrikov, Gabriel Synnaeve, Arthur Szlam, and Rob Fergus. Intrinsic motivation and automatic curricula via asymmetric self-play. arXiv preprint 17Xiv:1703.05407, 2017.
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. In Advances in neural information processing systems, pp. 3104-3112, 2014.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782)3500-35,, 2019.
Kelvin Xu, Siddharth Verma, Chelsea Finn, and Sergey Levine. Continual learning of control prim- itives: Skill discovery via reset-games. arXiv preprint urXiv:2011.05286 2020.
Naoyuki Yamamoto and Masumi Ishikawa. Curiosity and boredom based prediction as novel internal rewards. Inspired Information Technology, pp. 51-55. Springer, 2010.
Jin Zhang, Jianhao Wang, Hao Hu, Tong Chen, Yingfeng Chen, Changjie Fan, and Chongjie Zhang. Metacure: Meta reinforcement learning with empowerment-driven exploration. arXiv preprint arXiv:2006.08170 2020a.
Tianjun Zhang, Huazhe Xu, Xiaolong Wang, Yi Wu, Kurt Keutzer, Joseph E Gonzalez, and Yuan- dong Tian. Bebold: Exploration beyond the boundary of explored regions. arXiv preprint arXiv:2012.08621, 2020b.
Ruihan Zhao, Pieter Abbeel, and Stas Tiomkin. Efficient online estimation of empowerment for reinforcement learning. arXiv preprint arXiv:2007.07335 2020.
13

---

Under review as a conference paper at ICLR 2022
A PROOF DETAILS
Firstly, we notice that we have simple relation between marginal observation entropy and marginal state entropy by the structure of the POMDP:
d= (o) - (1 - Σ p'llo 0)
(1
(6)
= (1 7) Σ 7¹ Σ p(s, = =s)p(o|s)
(7)
(1 7) Σ p(ols) Σ Npp(s =
(8)
Σ p(ols)d((s)
We can use this relation to prove the following lemma:
Lemma 3. The cumulative surprise measured by the observation density model po(o) forms an up- per bound of the observation marginal entropy H (dd (o)), which becomes light when the observation density model fits the observation marginal d (o).
Proof.
ES log po po( = Σ d"((s) E E(lols)lon log pog
(10)
Σ (o) log
(11)
2 (o))
(12)
where the last inequality is because - E. dt (0) log (o) = (I(d(())lpo(())
We suppose that we are in the Block MDP setting: Assumption 2 (Block MDP). We suppose that for any s E S, s + s + supp(p(O(s)) n
supp(p(O[s))
In this case the marginal observation entropy can also be simply related to the marginal state entropy:
Lemma 4. In block MDP (BMDP) Misra et al. (2020), by noticing that HSSO) 0, we can decompose the observation marginal entropy as follows:
Hd (o)) = ( =)
5) + (ddd
(13)
Proof.
(o) Σ p(ols)dd (s)
log( Σ (s))s)d((s))
(14)
0,8
Σ d (s) p(ols) (o(ss
(15)
DEO.
dh (s)
Σ p(o|s) log p(ols) + log dl (s)]
(16)
oEO.
Edy (OIS s) + (sd
(17)
that we can also obtain by simply noticing that H (S = 0 in the Block MDP setting and writing the mutual information between S and O.
14

---

Under review as a conference paper at ICLR 2022
Suppose that we have small number of latent states with rich observations, that is, there is such that [OIS = s) > log (S]. In this case, we are trying to maximize the marginal observation entropy, have:
max H(d = max Ra H(OSS= =
(18)
d= (+)
d=)(s)
The RHS is maximized by taking:
d" (s) = [(s = arg max (O 10:00==00 =s)
(19)
That is, we are stuck in a noisy TV.
On the contrary, if we are trying to minimize the marginal observation entropy, equation Eq 17 gives us the exact minimizer:
d" (8) T(s = arg min HOOS = s))
(20)
That is, we are stuck in a dark room.
Now suppose that we are optimizing the following objective:
max min (()) d (50) d (eleo)
(21)
Definition 2. We define the following semiquasimetric in the state space:
å(s, 5 min(k 2m, Pe (s'ls) =1
(22)
where by convention Po (s|s) 1 for all In other words, d(s, k if state there is policy that reaches s' from in steps with probability 1.
Definition 3. We define the following semimetric:
d(s,s) max max{d(ss s'), (d(ss d(s' {)}
(23)
Definition 4. We say that a state is dark room if it has minimal emission entropy:
HOIS =s min HOIS =
(24)
sES
Assumption 3. We make three assumptions concerning the density of dark rooms:
(a) We suppose that for every state there is dark room such that d(s, s') T. That is, the set of dark rooms is a T-cover of the state space with respect to d.
(b) We suppose that for every state 8, there is dark room such that (s = 1, that is dark room can be reached in exactly T steps.
(c) We suppose that for any state s and any dark room s', if d(sss')) S T, then d(s, s') S T, that is if we can reach a dark room from a state s in less than T steps, then we can also reach from this dark room is less than T steps.
Theorem 2. Under Assumptions
and 3 the Markov chain induced by the following AS game:
max min d (80) (o)
H(T (0))
(25)
T-covers the state space, that is for every state 8, there is a state s' such that d (8') > and d(s, 5') < where d is the marginal induced by the game between A and B.
Given an initial state so, Eq 17 shows that the controller will always reach the same state of lowest emission entropy step T. By assumption 3b) the Controller can always reach dark room with probability 1 in exactly T steps. Therefore the game is equivalent to the following constrained objective:
Proof.
max Eg (s) HOOS = 5) + (s) (=))) s.t. d ((s:: H(OSS =) min H(SS S =>}}) =
(26)
(27)
15

---

Under review as a conference paper at ICLR 2022
For any state marginal satisfying the constraint we have:
(s) ()
(28)
where C' is a constant. Therefore, with probability 1, maximizing this objective is equivalent to maximizing the state marginal entropy in the set of dark rooms which form a T-cover of the state space by assumption Bl).. Therefore the Markov chain induced by the game T-covers the state space. Indeed, suppose by contrapositon that this is not the case. That is, there is such that for any s' we have:
d' d' = 0 V d(s, 8')> T
(29)
Since the set of dark rooms is a T-cover by assumption Bia), we know that there is a dark room s" such that d((s, x²) s T, which implies that d' (s") O. Therefore the state marginal entropy in the set of dark rooms is not maximized and the objective is not optimized.
B ADDITIONAL EXPERIMENTAL RESULTS
B.1 EMERGENCE OF COMPLEXITY
To show that Adversarial Surprise leads to emergence of complexity by phases, we plot the temporal acquisition of two behaviors in the MiniGrid environment. The results are shown in Figure 7 This environment includes a dark room and noisy room separated by a door. The position of the door changes at each episode. Initially, the agent is inside the noisy room and the door is open. One episode con- sists of 96 steps: the Control policy takes con- trol of the agent during 32 steps, then the Ex- plore policy takes control of the agent during 32 steps. finally the Control policy takes control of the agent during 32 steps. The first acquired behavior by the Control policy is identifying where the door is and going to the dark room during the first round. is short-term surprise minimizing behavior and an agent trained with SMIRL objective can converge to it. How- ever, the Explore policy learns to go back to the noisy room and to reach the farthest point from the door such that the Control policy does not have the time reach state of minimum entropy before the surprise of the agent is computed in the reward. This in turn incentivizes the acquisition of a more complex behavior by the Control policy: it learns go in the dark room and to lock the agent inside by closing the door during the first round, making it harder for the Explore policy to learn to reach a state that will surprise the agent during the Control policy's 's second round. This behavior reminiscent of Dr. Jekyll and Mr. Hyde highlights the potential of Adversarial Surprise to learn long-term surprise-ming miniiiii behaviors.
8.5
035
Figure 6: Q2. Emergence of Complexity: the average number of times the agent flip switch to stop lights from flashing. ASP and RND do not learn to press the switch, while SMiRL and AS both press the switch a similar number of times. Resetting the AS buffer more frequently enables it to exceed even SMiRL in taking actions to control the environment.
We also investigate the behaviors learned in similar environment, which contains a switch that enables the agent to stop stochastic elements from changing color. Figure 6 measures how often agents trained with different techniques learn to press the switch. Since RND has no incentive to leam to control the environment, it never learns to press the switch. A similar result is observed for ASP, since reducing the entropy would make it easier for the Bob agent to replicate the Alice agent's final state. Thus, ASP will not always lead the agent to learn all possible behaviors relevant to controlling the environment. Both SMiRL and AS learn to take actions to reduce entropy. However, when we train AS by resetting the buffer 3 used to fit the density model po(o) after each round (that is, after both the Explore and Control policy have taken one turn), rather than after each episode, we see that AS increases the number of actions it takes to reduce entropy even over SMiRL. This is likely because resetting the buffer removes any incentive to return to states that the agent has previously seen within its lifetime, and instead gives a stronger incentive reduce entropy immediately.
16

---

Under review as a conference paper at ICLR 2022
bob
Orargencs comple betantors
Tryoor viait cored bab Pordity
(a) The Control policy Ieamss to lock the agent in the (b) Acquisition of two behaviors by phases in order dark room to minimize long-term surprisc.
of complexity and long-term impact the surprisc.
Figure 7: Q3. Emergence of Complexity: a) An example environment which contains a key that be used to lock door separating the agent from stochastic elements. b) We observe two relatively short phase transitions separating three learning phases with three clearly distinguishable behaviors: randomly exploring, going the dark room, locking the agent in the dark room (left). This is evidence of an emergent curriculum induced by the multi-agent competition.
B.2 ABLATION STUDY ON THE EXPLORER AND CONTROLLER HORIZON
We perform an ablation study on the length of each round for the Explore and Control policy in the MiniGrid environment and observe that the optimal horizon is between and 16.
Number of rooms visited per episode
128
64
16
8
32
2.5
1.5
1
0.5
Samples
5M
10M
15M
Figure 8: Ablation Study the Explorer and Controller Horizon.
C HYPERPARAMETER DETAILS
In every experiment, both the explorer's and controller's policies receive stack of the last obser- vations, a sufficient statistic of the current observation density model and the index of the current time step. The 4 last observations are stacked with the sufficient statistic before being fed into convolutional layer. Then the output of the convolutional layer is stacked with the index of the cur- rent time step before being fed into a feed forward layer. At every step of the second-half of the controller's trajectories, we compute the error of the current observation with respect to the current observation density model and then feed the adversarial surprise buffer with the current observation to update the density model. The negative error is the reward of the controller for the current time step. By default, buffer is reset at the beginning of every episode. We also experiment with when to reset the buffer (3; find that resetting the buffer after each round (after the Explore policy and Control policy each take one turn) can sometimes improve performance. In our round buffer variant, used in 6 the buffer is reset at every round.
17

---

Under review as a conference paper at ICLR 2022
0015
000063
X
R
R
69
17
10D
ATTVTSION
(a) Freeway
(b) Berzerk
(c) Assault
(d) Space Invaders
Figure 9: The four Atari environments we used to test each method.
C.I MINIGRID
We use convolutional layers with 16, 32 and 64 output channels and a stride of 2 for ev- ery layers. For the MiniGrid experiments using sity model we use 7 x 7 independent categorical distributions with 12 classes each instead of independent Gaussian distributions, which significantly improve the results. The sufficient statistic is the set of 7 7 x 12 probabilities. In one episode, each agent acts during rounds of 32 steps per round (Explorer-Contee Controller-Exploree (ixxpooer-Controoleer,, for total of 128 steps. We use 16 parallel environments for AS, RND, ASP and SMIRL. For the baselines, we base our RND implementation on the github repo from jewleo, which reliable PyTorch imple- mentation tion on the github repo from the author
observations, for our observation den-
our ASP implementa- http:://giihub..oooo// htt.:///w...ooe/sattoo//ss//ppl our SMIRL imple- mentation the github repo from the author (https://github. com/Neo-X/SMiRLL X/SMiRL.Code), and AGAC implementation is based on the Pytorch version the github repo from the author torch.
C.2 ATART
We use the Atari pre-processing wrappers from Dhariwal et al. (2017) before feeding input into a five-layer architecture with three convolutional layers with 4, 32, and output channels, kernel sizes of 8,4.3, and strides of 4, 2, and for the explorer. We downsize the input images to 4 x 20 x 20 and for our observation density model we use 20 20 independent Gaussian distributions. The sufficient statistic is the set of means and standard deviations of the 4x 20 20 Gaussian distributions. For the Atari environments, we run the explorer for steps and controller for 128 steps and alternate until the end of an episode and reset the buffer after every life lost. The four Atari environments used for testing are shown Figure
C.3 DOOM
We use the Take Cover scenario on the ViZDoom Kempka et (016a) platform. We feed the input to a five-layer architecture with three convolutional layers with 32, 32, and 64 output channels, kernel sizes of 4,4.3, and strides of 2, and for the explorer. We downsize the input images to 4 x 20 x 20 and for our observation density model we use 4 x 20 20 independent Gaussian distributions. The sufficient statistic is the of means and standard deviations of the 4 x 20 20 Gaussian distributions. We similarly run the explorer for 64 steps and controller for 128 steps and alternate until the end an episode and reset the buffer after a life has been lost. The scenario used for testing shown in Figure
C.4 PLOTT
For each environment and each method, we run a total of six random seeds and compare the top three, measure of the best-case performance. Plots generated by smoothing the obtained
18

---

Under review as a conference paper at ICLR 2022
returns using rolling window of steps corresponding 25, 15, 10, 30 for Freeway, 30, 40, 30, 20 for Berzerk, 10,20,5,1 for Assault, and 10, 15, 10, 2 for Space Invaders. Then, we plot both the mean and error bars representing 95% confidence interval over the seeds.
A website with videos of the experiments available here: htew://bberrarrill-aaurrrss/ss/s
D ALGORITHM
Algorithm 1: Adversarial Surprise
Randomly initialize 6² and < for episode = O.... M do
Initialize R for to do if explore then ~ (0r,
01 explore num True, E k, so p((0), 00 ~ p(On) so);
// Explore
~ u (o,
// Control
end
81+1 (s (t), 02+1 paaiippOOup p(0)+1)st41)
// Environment step
log po(o))):));
// Compute intrinsic reward
jurn if not explore turn and t 1 k/2 then
R' +r'; end
3 = BU a,, 0
// Update buffer
if I == 1 then
explore Jurn not explore.tum;
// Switch turns
1 2k:
8 Bc+1 =MLF.uddate( 0c);
Fit density model
end
RL. update -8,--)) ;
// Train Explore policy T² with reward -R R
RL updatee) R');
// Train Control policy d0 with reward R
end
E BROADER IMPACT:
AS is an intrinsic motivation method aimed at enhancing learning in intelligent agents. There has been a rich history of previous work in this area, where goal has been to develop more general algorithms for learning in the absence of task-specifie rewards. This work is in line with previous work and should not directly cause broader harms to society. We are not using any dataset or tool that will perpetuate enforee bias. Nor does method make judgements be misaligned with our values. potential positive impact of this work may be providing interesting insight into the nature of intelligence and learning.
our behalf that could
19


Reviews:
[{"review_id": "u49Ua9bS1Hr", "reviewer": "Reviewer_MoPi", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall this is a neat idea, related to but distinct from previous works. The problem setting of a stochastic block MDP (BMDP) is well motivated although not frequently encountered in RL. The strongest results come from a new custom environment in MiniGrid, which clearly motivates the switching mechanism to discover interesting behaviors and fully explore the environment. In other environments the results are less compelling: in Doom the AGAC baseline is not included, while the Atari experiments are hard to interpret due to the choice of the four games, which is not clear. While I like the paper, I am voting for weak reject primarily because of the reporting protocol, only showing the top 3 seeds. This is known to be bad practice and does not seem justified, at least without presenting full results in the Appendix. As with any review it is possible I missed something, in which case I can change my score to reflect this during the discussion.\n\nMore Detailed Comments:\n\n1. One of the greatest strengths of this work is that is it well motivated, and thorough. The related work section for instance positions the paper effectively within the literature, which is surprisingly rare. The flip side of this, is that the specific setting considered, stochastic BMDPs, seems very specific. It would be great to have more examples of real world settings where this setting would be present.\n2. The MiniGrid experiment is a nice example of a setting where existing methods fail in stochastic environments, with a switch that allows AS to remove the stochasticity. Is it the case that the Explore agent can turn the stochasticity back on? How often does it do this?\n3. Why are the methods in Fig. 2b) and 2c) different? E.g. AGAC is in one but not the other. More of an aesthetic issue but it is confusing switching the colors for methods in plots that are side by side.\n4. The authors say \"ViZDoom environment (Kempka et al., 2016b), which was used by AGAC and SMiRL\", *but then do not include AGAC in the Doom experiments.* Why?\n5. How were the four Atari games chosen? As far as I am aware, the common games used for exploration are Montezuma's Revenge and Pitfall, but these were not included. This makes the reader question the choice, for example if the method works best for these but would do equally poorly on a different set of games. While it isn't the perfect environment by any means, Montezuma's Revenge is a good benchmark because it has been predefined, so if a method does/doesn't work there it can serve as a litmus test.\n6. How does AS combine with rewards? All of the other methods (aside from ASP) are designed for settings where an extrinsic reward is available, and they use this to get their best results. I know \"unsupervised\" or \"self-supervised\" RL is currently a popular topic, but in many cases we may have a reward function. Indeed - the baselines compared against were not designed to work in the regime they were tested in.\n7. How do you choose k? I may have missed it but couldn't find it anywhere. The paper does mention that the ability to tune this per environment is a strength, but as a reviewer it is a concern that this may have led to the performance gains and actually the method could be very sensitive to this hyperparameter. I am thinking if k is less than the size of the room with the switch, Alice and Bob could take turns to turn it on/off and then stay in the same room forever.\n8. The authors should cite RIDE, AMIGo and BeBold, three recent works studying exploration in procedurally generated environments. Comparison against them would be a nice to have but not expected, since AGAC is included and it compares against them.  \n\nMinor Comments/Typos:\n\n* p6, reference Equation 5 but I think you mean Equation 4.\n* p6, after the AS formula (min max) it says BMPD rather than BMDP. Later in that sentence, \"induce\"→ \"induces\".\n* Fig 2.c) has the methods twice on the legend.\n* P7 Minigrid should have a capital G.", "summary_of_the_paper": "This paper introduces Adversarial Surprise, a new approach for unsupervised reinforcement learning in stochastic BMDPs, where the goal is to explore an environment without rewards. The algorithm uses a single agent with two policies, an Explorer and a Controller, which switch during an episode with opposite rewards: to maximize and minimize \"surprise\". The method is supported by a theoretical argument under the assumptions of the stochastic BMDP. When these are present in an environment, the empirical results are strong. The method is also tested in Atari and Doom. ", "summary_of_the_review": "The method is elegant and well motivated, hence a desire to see it accepted despite question marks about the experimental results. In particular, the broader applicability may be limited given the gains are clearest in the setting specifically designed to satisfy the properties which motivated the method. To increase my score I would need clarification around the evaluation protocol, which is already known to be challenging in RL without selecting the top 3 seeds (while saying 5 seeds elsewhere). I would also be happy to increase my score if there are additional baselines (e.g. AGAC for Doom) or benchmark environments (e.g. additional Atari games/MiniGrid environments), clarification around hyperparameter choices or an effective demonstration of combining AS with an extrinsic reward. Overall I could increase multiple times if this is improved. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "gkWHcn3wIA", "reviewer": "Reviewer_gVM6", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "AFTER REBUTTAL\n\nAfter having read the authors response, as well as other reviews and discussions, I am keeping my original, slightly negative, score.\n\nAnyway, I would like to encourage the authors on improving the submitted draft, especially\n- considering a critical evaluation of the state density estimation performance, and comparing their results with non-parametric entropy estimation,\n- clarifying how subsequent RL tasks can benefit from the pre-trained models (other than zero-shot transfer).\nI believe that with these improvements this work will be a nice contribution to the unsupervised RL community.\n\n-------\n\nWhile the proposed methodology is certainly interesting, my main concerns about the current version of this work regard (i) the applicability of observation density estimation and (ii) the robustness and completeness of the experimental evaluation. I report below some detailed comments on this matter.\n\nDENSITY ESTIMATION\n\n1) From my understanding, the method heavily relies on direct estimation of the observation marginal density to compute the objective function. However, direct density estimation is known to scale badly to the dimensionality of the space (e.g., Beirlant et al., Nonparametric entropy estimation: An overview, 1997). Moreover, density estimation does not seem to be required by the method, which just need an estimate of the observation entropy. The recent works (Mutti et al., 2021; Seo et al., 2021; Liu and Abbeel, 2021) showed that non-parametric entropy estimation can be much better in this setting. On the one hand, I would like to understand if density estimation is really working in the reported experiments (such as comparing with an estimate obtained from a huge number of samples). On the other hand, I am wondering if these results could be improved with non-parametric entropy estimation.\n\nEMPIRICAL EVALUATION\n\n2) In Appendix C.4, the paper reports that all the experiments are obtained with six independent runs. This number is not ideal, but reasonable in the reported settings. However, I do not understand why the plots are just showing the average (and confidence intervals) computed over the top-three seeds. The Appendix motivate this as a comparison of the best-case performance, but worst-case performance arguably matters as well. Moreover, can the authors clarify the strategy behind the hyper-parameters selection, and if they experienced any particular sensitivity to the tried values?\n\n3) The experiments do not include a comparison with maximum state entropy methods, especially APT (Liu and Abbeel, 2021) and RE3 (Seo et al., 2021) that have been experimented in analogous domains. Moreover, an observation coverage metric is only reported for the MiniGrid experiment.\n\n4) The experiments do not include any continuous control domain, which might represent a worst-case setting for AS. Previous works have been extensively analyzed in these kind of domains, such as Mujoco tasks in (Laskin et al., URLB: Unsupervised reinforcement learning benchmark, 2021). Note that the latter is very recent and at most concurrent with this work, but it might provide a useful inspiration.\n\n5) I am not completely convinced about the fairness of the zero-shot transfer comparison. On the one hand, the reported results are somewhat confusing: If the setting is zero-shot, why the plots report training steps? They refer to the training steps of the unsupervised exploration phase? On the other hand, I do not clearly understand why AS should actually work in zero-shot transfer, and the reported baselines are not designed for this setting (especially RND). I think that including a comparison over a (more common) fine-tuning to downstream tasks setting would strengthen the analysis.\n\n6) If my previous hypothesis over the interpretation of the zero-shot setting is correct, I am wondering if this couldn't be seen as a partially negative result on the stability of the method. Indeed, the performance of AS is not monotonically improving, which casts some doubts on whether the method is really converging to something that is useful to downstream tasks, or it is only effective in covering the observation space over the process.\n\nGAME-THEORETIC ANALYSIS\n\n7) This is a lesser concern, but I think that the paper somewhat misses the opportunity to analyze the method from a game-theoretic perspective. The min-max game optimization problem is well-posed and actually feasible? What is the solution concept one should aim to achieve in this formulation?\n\nMINOR\n- It is sometimes quite hard to inspect the plots, even when zooming on the pdf;\n- Figure 2: changing colors between the two plots does not help tracking the curves, while there is some mess in the legend of Fig. 2c, and it is not clear which one refer to the SMiRL curve;\n- It is of course hard to fit everything into a 9-pages paper, but I would suggest the authors to try to squeeze the figures on the \"emergence of complexity\" into the main text.", "summary_of_the_paper": "This paper introduces a method, called Adversarial Surprise (AS), for unsupervised reinforcement learning. AS employs a two-player, adversarial, sequential procedure in which an Explore player tries to maximize the approximate entropy of the observations, whereas a Control player tries to minimize this same entropy. The method is then compared against other unsupervised RL baselines in visual domains, over both state coverage and zero-shot adaptation.", "summary_of_the_review": "This paper introduces some interesting ideas. Especially, it provides a practical and smoother reinterpretation of asynchronous self-play (Sukhbaatar et al., 2017), a method holding compelling premises but with some clear limitations. Moreover, it tries to unify under a unique approach the pros of novelty-seeking exploration and surprise minimization, while mitigating some of their cons (such as noisy-tv and dark-room problems respectively). Overall, the proposed methodology seems valuable, and I believe it can help improving the state of the art in some specific settings (e.g., partially observable visual domains). Those might be sufficient reason for accepting the paper.\n\nHowever, I think that the paper has some important limitations as it is, which might significantly reduce its potential impact. Thus, I am currently providing a slightly negative evaluation. I detailed in the main review above some of the concerns that the authors might address in their response.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UrPJfl7cCO", "reviewer": "Reviewer_w5NP", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Positives**\n\n+ The paper is well written and generally easy to follow and understand, and the related work properly puts the proposed method in context.\n+ Section 4.1 provides an interesting formalization of insights that had been experimentally observed in previous works (e.g. noisy TVs, dark rooms) that had not been mathematically described before as far as I know.\n+ The method combines the advantages of surprise maximizing and surprise minimizing strategies in a conceptually simple manner which should be easy to replicate.\n+ Multiple baselines are reported for each experiment.\n\n\n**Concerns**\n\n- The paper uses three metrics to evaluate unsupervised RL methods: coverage (number of rooms in MiniGrid, binned x positions in VizDoom), amount of task reward collected (VizDoom, Atari) and qualitative evaluations based on a few videos available in the project site (at the time of reviewing, videos for MiniGrid and the four Atari games were available). In my opinion, while these metrics can provide some insight on the type of behaviors AS may discover, more thorough quantitative evaluation is required in order to properly assess the usefulness of the method. For instance, a common practice in related works consists in evaluating how the output of the unsupervised pre-training stage helps when solving downstream tasks (i.e. reward functions) in the same environment.\n- Some of the considered baselines were proposed or used to improve exploration in the presence of extrinsic reward (RND, AGAC, SMiRL, ASP). The outputs of other unsupervised methods such as DIAYN, VISR or APT can be used for transfer via Hierarchical RL, Generalized Policy Improvement or fine-tuning. After reading the paper, I'm unclear about how one would use AS to either aid with exploration in the presence of extrinsic reward or how the resulting policies could be used for transfer to downstream tasks. Given that the method produces two sets of neural network weights (one per policy), and the fact that the two policies probably need to be interleaved in order to produce meaningful behavior, it is not obvious how to best leverage them which in my opinion reduces the significance of the results.\n- I have some concerns (and doubts) about the evaluation of unsupervised agents. Appendix C.4 states that plots report the top-3 seeds (out of 6), whereas Figure 4's caption states that 5 random seeds without any kind of filtering are reported. Which method was used in practice? I am particularly concerned about the former, as it would leak information about the task reward via seed selection.\n- The choice of Atari environments is never explained, and I wonder why authors decided to run experiments on this particular subset of games. I believe that it would be much more informative if these methods had been evaluated on some of the 6 hard exploration games identified by Bellemare et al. (NeurIPS, 2016) (cited in the paper): Freeway, Gravitar, Montezuma's Revenge, Pitfall, Private Eye, Solaris and Venture.\n- The experimental setting seems to vary across environments and even plots. For instance, Figure 4 shows a different number of train steps across Atari games (ranging from 180k to >400k). Authors report over 120k train steps when showcasing the advantages of AS in terms of zero-shot performance in VizDoom (Figure 5), whereas Figure 3 shows results after only 1k train steps when reporting coverage in this same environment. I would advise authors to unify the evaluation protocol for each domain (i.e. same protocol for all Atari games, same protocol for all VizDoom experiments, etc). Moreover, the term 'train step' is not always clear in RL and I was not able to find its definition in the manuscript.\n\n\n**Other comments**\n\nI have other suggestions for the authors that did not play an important role in my decision but I believe would improve the overall quality of the paper:\n\n- Many environments feature *irreversible decisions*, i.e. actions that make the agent transition from state $s$ to $s'$ but make it impossible to go back to state $s$. I know that it is difficult to derive theoretical results for these complex environments, but I suggest being more explicit about the limitations of the theory (especially since it seems that even some of the MiniGrid environments have this property, e.g. the ones where the agent can lock a door).\n- The paper mentions that $k^E$ and $k^C$ are independent hyperparameters that can be set to different values. Is AS sensitive to this choice? It would be interesting to include an analysis of the role played by these values in the discovered behaviors.\n- The structure of Section 5 (questions, description about the experimental setup, answers) makes it somewhat hard to read. I would suggest something like *experimental setup, Q1 (question + answer), Q2 (question + answer), Q3 (question + answer)* instead.\n- In Figure 3's caption, I would suggest using $\\log p(x)$ instead of $\\log p(s)$, as the true state is unknown and will probably include more information than just the agent's x position.\n- In page 9, authors mention that the performance of RND decreases over time. Please see Campos et al. in the provided references for an example where using reward normalization enables very long unsupervised pre-training with RND without performance collapse.\n- The text in some figures is too small (2b, 2c, 4, 5) or cropped (4a, 4b). \n- The legend in Figure 2c has repeated elements. Figures 2b and 2c do not include the same baselines (e.g. SMiRL is missing in 2c). Please adjust their x limits to be the same, and adjust the y limit to avoid leaving empty half of the figure.\n\n**Additional references**\n\nEmpowerment\n\n> Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. arXiv preprint arXiv:1611.07507, 2016.\n\nUnsupervised training based on empowerment + fast adaptation via GPI\n> Steven Hansen, Will Dabney, Andre Barreto, Tom Van de Wiele, David Warde-Farley, and Volodymyr Mnih. Fast task inference with variational intrinsic successor features. In ICLR, 2020.\n\nIntrinsic motivation based on episodic curiosity\n> Adrià Puigdomènech Badia, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, Bilal Piot, Steven Kapturowski, Olivier Tieleman, Martín Arjovsky, Alexander Pritzel, Andew Bolt, et al. Never give up: Learning directed exploration strategies. In ICLR, 2020.\n>\n> Adrià Puigdomènech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, and Charles Blundell. Agent57: Outperforming the atari human benchmark. In ICML, 2020.\n\nUnsupervised pre-training with NGU/RND + transfer to downstream tasks\n> Víctor Campos, Pablo Sprechmann, Steven Stenberg Hansen, Andre Barreto, Steven Kapturowski, Alex Vitvitskyi, Adria Puigdomenech Badia, and Charles Blundell. Beyond fine-tuning: Transferring behavior in reinforcement learning. In ICML 2021 Workshop on Unsupervised Reinforcement Learning. 2021.", "summary_of_the_paper": "This paper proposes Adversarial Surprise (AS), a method for unsupervised training of RL agents based on the competition of two policies dubbed Explore and Control. These two policies control compete to maximize/minimize surprise, respectively, by taking turns to control a shared body. Authors show that under some conditions this objective leads to maximizing state entropy within an episode, and formalize the settings where other approaches may fail. Evaluation is performed on three different domains: procedurally generated MiniGrid tasks, VizDoom and four Atari games. AS explores more rooms within an episode in Minigrid, visits more x positions within an episode in VizDoom, and obtains higher zero-shot scores in 3/4 Atari games.", "summary_of_the_review": "The paper presents an interesting method, but the evaluation protocol needs to be improved in order to properly assess the advantages of the proposed approach. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The idea of having two policies with opposing strategies, one aiming to maximize a notion of surprise whereas the other tries to minimize it, is an interesting one. However, even after the author rebuttal, all reviewers have lingering concerns about the evaluation protocol. In addition, there are remaining questions about the bonuses used; there are concerns that these only work for very specific domains. For these reasons, I'm recommending rejection. I encourage the authors to carefully read the concerns of the reviewers about evaluation and consider using a different evaluation protocol for a future version of this work.
Decision: Reject