SMiRL: Surprise Minimizing Reinforcement Learning in Unstable Environments
Authors: Glen Berseth
Daniel Geng
Coline Manon Devin
Nicholas Rhinehart
Chelsea Finn
Dinesh Jayaraman
Sergey Levine
Venue: ICLR 2021 Oral (2021)
Keywords: Reinforcement learning

Abstract: Every living organism struggles against disruptive environmental forces to carve out and maintain an orderly niche. We propose that such a struggle to achieve and preserve order might offer a principle for the emergence of useful behaviors in artificial agents. We formalize this idea into an unsupervised reinforcement learning method called surprise minimizing reinforcement learning (SMiRL). SMiRL alternates between learning a density model to evaluate the surprise of a stimulus, and improving the policy to seek more predictable stimuli. The policy seeks out stable and repeatable situations that counteract the environment's prevailing sources of entropy. This might include avoiding other hostile agents, or finding a stable, balanced pose for a bipedal robot in the face of disturbance forces. We demonstrate that our surprise minimizing agents can successfully play Tetris, Doom, control a humanoid to avoid falls, and navigate to escape enemies in a maze without any task-specific reward supervision. We further show that SMiRL can be used together with standard task rewards to accelerate reward-driven learning.

Published as a conference paper at ICLR 2021
SMIRL: SURPRISE MINIMIZING REINFORCEMENT LEARNING IN UNSTABLE ENVIRONMENTS
Glen Berseth UC Berkeley
Daniel Geng
Coline Devin
Nicholas Rhinehart UC Berkeley
UC Berkeley
UC Berkeley
Chelsea Finn Stanford
Dinesh Jayaraman University of Pennsylvania
Sergey Levine
UC Berkeley
ABSTRACT
Every living organism struggles against disruptive envirommental forces to carve out and maintain an orderly niche. We propose that such a struggle achieve and preserve order might offer principle for the emergence of useful behaviors in artificial agents. We formalize this idea into an unsupervised reinforcement learn- ing method called surprise minimizing reinforcement learning (SMiRL). SMiRL alternates between learning a density model to evaluate the surprise of a stimulus, and improving the policy to seek more predictable stimuli. The policy seeks out stable and repeatable situations that counteract the environment's prevailing sources of entropy. This might include avoiding other hostile agents, or finding stable, balanced pose for a bipedal robot in the face of disturbance forces. We demonstrate that our surprise minimizing agents can successfully play Tetris, Doom, control a humanoid to avoid falls, and navigate to escape enemies a maze without any task-specific reward supervision. We further show that SMiRL can be used together with standard task rewards to accelerate reward-driven learning.
INTRODUCTION
Organisms can carve out environmental niches within which they can maintain relative predictability amidst the entropy around them (Boltzmann, 1886; Schrödinger, 1944; Schneider & Kay, 1994; Friston, 2009). For example, humans go to great lengths to shield themselves from surprise - we band together to build cities with homes, supplying water, food, gas, and electricity to control the deterioration of our bodies and living spaces amidst heat, cold, wind and storm. These activities exercise sophisticated control over the environment, which makes the environment more predictable and less "surprising" (Friston, 2009; Friston et al., 2009). Could the motive of preserving order guide the automatic acquisition of useful behaviors in artificial agents?
We study this question in the context of unsupervised reinforcement learning, which deals with the problem of acquiring complex behaviors and skills with supervision (labels) incentives (external rewards). Many previously proposed unsupervised reinforcement learning methods focus on novelty- seeking behaviors (Schmidhuber, 1991; Lehman & Stanley, 2011; Still & Precup, 2012; Bellemare et al., 2016; Houthooft et al., 2016; Pathak et al., 2017). Such methods can lead to meaningful behavior in simulated environments, such as video games, where interesting and novel events mainly happen when the agent executes specific and coherent pattern of behavior. However, we posit that in world euvironments, natural forces outside of the agent's control already offer an
more realistic open-world excellent source of novelty: from other agents to unexpected natural forces, agents in these settings must contend with a constant stream of unexpected events. In such settings, rejecting perturbations and maintaining a steady equilibrium may pose greater challenge than novelty seeking. Based on this observation, we devise an algorithm, surprise minimizing reinforcement learning (SMiRL), that specifically aims to reduce the entropy of the states visited by the agent.
SMiRL maintains an estimate of the distribution of visited states, ps)s.. and a policy that seeks to reach likely future states under (s). After each action, ps(s) is updated with the new state, while the policy is conditioned on the parameters of this distribution to construct a stationary MDP. We illustrate this with diagram in Figure la. We empirically evaluate SMiRL in range of domains that

---

Published as a conference paper at ICLR 2021
St
2 po, (Rr).
O2 arg
log polse)
8
at
(b)
Figure 1: Left: SMiRL observes a state 8, and computes a reward rs as the negative surprise under its current model p (Sz). given by p (s:). Then the model is updated on the agents state history, including st, to yicld ps,, The policy To [a 8r, 1) then generates the action ae Right: This procedure leads to complex behavior in environments where surprising events happen on their own. In this cartoon, the robot experiences wide variety of weather conditions when standing outside, but can avoid these surprising conditions by building a shelter, where it can reach a stable and predictable states in the long run.
are characterized by naturally increasing entropy, including video game environments based on Tetris and Doom, and simulated robot tasks that require controlling a humanoid robot to balance and walk. Our experiments show that, in environments that satisfy the assumptions of our method, SMiRL automatically discovers complex and coordinated behaviors without any reward signal, learning to successfully play Tetris, shoot enemies in Doom, and balance a humanoid robot at the edge of a cliff. We also show that SMiRL can provide effective auxiliary objective when reward signal is provided, accelerating learning in these domains substantially more effectively than pure novelty-seeking methods. Videos of our results are available online'
2 RELATED WORK
Prior work on unsupervised learning has proposed algorithms that learn without a reward function, such as empowerment (Klyubin al., 2005; Mohamed & Jimenez Rezende, 2015) or intrinsic motivation (Chentanez et al., 2005; Oudeyer & Kaplan, 2009; Oudeyer et al., 2007). Intrinsic motivation has typically focused on encouraging novelty-secking behaviors by maximizing model uncertainty (Houthooft et al., 2016; Still & Precup, 2012; Shyam et al., 2018; Pathak et al., 2019), by maximizing model prediction error improvement (Lopes et al., 2012: Pathak et al., 2017), through state visitation counts (Bellemare et al., 2016), via surprise maximization (Achiam & Sastry, 2017b; Schmidhuber, 1991; Sun al., 201 2011), and through other novelty-based reward bonuses (Lehman & Stanley, 2011; Achiam & Sastry, 2017a; Burda et al., 2018a; Kim et al., 2019). We do the opposite. Inspired by the free energy principle (Friston, 2009; Friston et al., 2009; Ueltzhöffer, 2018; Faraji et al., 2018; Friston et al., 2016) including recent methods that train policies using RL (Tschantz et al., 2020a;b; Annabi et al., 2020) that encode a prior over desired observations, we instead incentivize an agent to minimize surprise over the distribution of states generated by the policy in unstable environments, and study the resulting behaviors. In such environments it is non- trivial to achieve low entropy state distributions, which we believe are more reflective of the real world. Learning progress methods that minimize model parameter entropy (Lopes et al., 2012; Kim et al., 2020) avoid the issues novelty- based methods have with noisy distractors. These methods are based on learning the parameters of the dynamics where our method is learning to control the marginal state distribution.
Several works aim to maximize state entropy encourage exploration (Lee al., 2019; Hazan et al., 2019). Our method aims to do the opposite, minimizing state entropy. Recent work connects the free energy principle, empowerment and predictive information maximization under the same framework to understand their differences (Bichl et al., 2018). Existing work has also studied how competitive self-play and competitive, multi-agent environments can lead to complex behaviors with minimal reward information (Silver et al., 2017: Bansal et al., 2017; Sukhbaatar et al., 2017; Baker et al., 2019; Weihs al., 2019; Chen al., 2020). Like these works, we also consider how complex behaviors environments, but instead of multi-agent competition, we utilize
can emerge in resource-constraiie surprise minimization to drive the emergence of complex skills.
2

---

Published as a conference paper at ICLR 2021
3 SURPRISE MINIMIZING AGENTS
We propose surprise minimization means to operationalize the idea of learning useful behaviors by seeking out low entropy state distributions. The long term effects of actions on surprise can be subtle, since actions change both (i) the state that the agent is in, and (ii) its beliefs, represented by model pa (s),, about which states are likely under its current policy. SMiRL induces the agent to modify its policy π so that it encounters states with high pe(s), as well as to seek out states that will change the model Po (s) so that future states are more likely. In this section, we will first describe what we mean by unstable environments and provide the surprise minimization problem statement, and then present our practical deep reinforcement learning algorithm for learning policies that minimize surprise.
Many commonly used reinforcement learning benchmark environments are stable, in the sense the agent remains a narrow range of starting states unless it takes coordinated and purposeful actions. In such settings, unsupervised RL algorithms that seek out novelty However, many environments - including, as we argue, those that reflect properties commonly found in the real world, - are unstable, in the sense that unexpected and disruptive events naturally lead to novelty and increased state entropy even if the agent does not earry out any particularly meaningful or purposeful behavior. In unstable environments, minimizing cumulative surprise requires taking actions to reach a stable distribution of states, and then acting continually and purposefully to stay in this distribution. An example of this is illustrated in Figure lb: the agent's environment is unstable due to varied weather. If the robot builds a shelter, it will initially experience unfamiliar states, but in the long term the observations inside the shelter are more stable and less surprising than those outside. Another example is the game of Tetris (Figure 2), where the environment spawns new blocks and drops them into random configurations, unless a skilled agent takes actions to control the board. The challenge of maintaining low entropy in unstable settings forces the SMiRL agent to acquire meaningful skills. We defer a more precise definition of unstable environments to Section 4, where we describe several unstable environments and contrast them with the static environments that are more commonly found in RL. benchmark tasks. In static environments, novelty seeking methods must discover complex behaviors increase entropy, leading to interesting behavior, while SMiRL may trivially find low entropy policies. We show that the reverse is true for unstable environments: a novelty seeking agent is satisfied with watching the environment change around it, while surprise minimizing agent must develop meaningful skills to lower entropy.
discover meaningful behaviors.
Problem statement. To instantiate SMiRL,, we design reinforcement learning agent that receives larger rewards for experiencing more familiar states, based on the history of states it has experienced during the current episode. This translates to learning policy with the lowest state entropy. We assume a fully-observed controlled Markov process (CMP), where we use S; to denote the state at time f. ae to denote the agent's 's action, p(su) to denote the initial state distribution, and T( (ss, az) to denote the transition probabilities. The agent learns policy (a)s), parameterized by ø. The goal minimize the entropy of its state marginal distribution under its current policy Tie at each time step of the episode. We can estimate this entropy by fitting an estimate of the state marginal d (sx) at each time step I, given by pa. (8y), using the states seen so far during the episode, 7 = {s1,..... s,) that is stationary. The sum of the entropies of the state distributions over episode can then be estimated as
T =
T
Σ H(s))
Σ 1
E, nd (xx) Dog d (S:))
E -d (xx) Plogpo (s:).,
(1)
where the inequality becomes an equality if po. (s:) accurately models d= (s:). Minimizing the right-hand side of this equation corresponds to maximizing an RL objective with rewards:
r(s:) = log (s:).
However, an optimal policy for solving this problem must take changes in the distribution Pa.., (s,) into account when selecting actions, since this distribution changes at each step. To ensure that the underlying RL optimization corresponds to a stationary and Markovian problem, we construct an augmented MDP to instantiate SMiRL in practice, which we describe in the following section.
3

---

Published as a conference paper at ICLR 2021
Training SMiRL agents. In order to instanti- ate SMiRL, we construct an augmented MDP out of the original CMP, where the reward in Equation (2) can be expressed entirely as a func- tion of the state. This augmented MDP has
Algorithm SMiRL
1:
while not converged do
2:
B 4- O
> Reset experience
3:
for episode = ...... M do
a state space that includes the original state
4:
p(s)); To {
Initialize state
St, as well the sufficient statistics of pe, (s). For example, if Po, (s) is normal distribu-
8o + (so; 0,0)
Initialize aug. state
6:
for each t= 0...., ...., do
7:
a ~ T (e.
D. Get action
tion with parameters 8,, then (ft, the pa-
8:
St+1 T(s++1|s:
Step dynamics
rameters of the distribution and the number
logpo, (8t+1)
SMiRL reward
of states seen so far - represents a sufficient
10:
T+ + U (S
Record state
statistic. Note that it is possible to use other, 11:
041 + (((((+1)
P Fit model
more complicated, methods to summarize the
12:
8 + {(1111, 0441, (
statistics, including reading in the entirety of Te using a recurrent model. The policy condi-
13:
B < B ((5,, at To. 8
14:
end for end for each
tioned on the augmented state is then given by
15:
(a (S,, Oz, t). The parameters of the sufficient
16:
& <- ())
b Update policy
statisties are updated 0, (Tr) using maxi-
17:
end while
mum likelihood state density estimation process
a. max 0 En=o log (s()..) over the experience within the episode Tr. When (0,, t) is a suf- ficient statistic, the update may be written as A, 2(ss 0,-1, 1). Specific update functions ((T.)) used in our experiments are described in Appendix C and at the end of the section. Since the reward is given by rs,,, 0. f- - 1) = log - (s.). and 0, is function of s, and (0,-1, 1), the resulting RL problem is fully Markovian and stationary, and as a result standard RL algorithms will converge to locally optimal solutions. Appendix D include details on the MDP dynamics. Figure 8, we illustrate the evolution of pa, (s) during episode of the game Tetris. The pseudocode for this algorithm is presented in Algorithm 1.
Density estimation with learned representations. SMiRL may, in principle, be used with any choice model class for the density model pe, (s). As we show in our experiments, relatively simple distribution classes, such as products of independent marginals, suffice to run SMiRL in many environments. However, it may be desirable in more complex environments to use more sophisticated density estimators, especially when learning directly from high-dimensional observations such as images. In these cases, we can use variational autoencoders (VAEs) (Kingma & Welling, 2014) to learn a non-linear state representation. A VAE is trained using the standard BLBO objective to reconstruct states after encoding them into a latent representation z via an encoder qw (z s). with parameters w. Thus, z can be viewed as a compressed representation of the state.
When using VAE representations, we train the VAE online together with the policy. This approach necessitates two changes to the procedure described Algorithm 1. First, training a VAE requires more data than the simpler independent models, which can easily be fitted to data from individual episodes. We propose to overcome this by not resetting the VAE parameters between training episodes, and instead training the VAE across episodes. Second, instead of passing the VAE model parameters to the policy, we only update a distribution over the VAE latent state, given by pe, (z). such that pe, (z) replaces pe, (s) in the SMiRL algorithm, and is fitted to only that episode's (encoded) state history. We represent Po. (z) as a normal distribution with a diagonal covariance, and fit it to the VAE encoder outputs. Thus, the mean and variance of po, (z) are passed the policy at each time step, along with t. This implements the density estimate in line 9 of Algorithm 1. The corresponding update (1 (T)) is:
20, Z0,..., Ze (z|ss] for S E Tt p 1/141
Zjj 0 1/1+1
(M 2,) [u.a].
Training the VAE online, over all previously seen data, deviates from the recipe in the previous section, where the density model was only updated within an episode. In this case the model is updated after collection of episodes. This makes the objective for RL somewhat non-stationary and could theoretically cause issues for convergence, however we found in practice that the increased representational capacity provides significant improvement in performance.
4

---

Published as a conference paper at ICLR 2021
4 EVALUATION ENVIRONMENTS
We evaluate SMiRL range of environments, from video game domains to simulated robotic control scenarios. In these unstable environments, the world evolves automatically, without the goal- driven behavior of the agent, due disruptive forces and adversaries. Standard RL benchmark tasks are typically static, in the sense that unexpected events don not happen unless the agent carries out a specific and coordinated sequence of actions. We therefore selected these environments specifically to be unstable, as we discuss below. This section describes each environment, with details of the corresponding MDPs in Appendix B. Illustrations of the environments are shown in Figure 2.
Figure 2: Evaluation environments. Top row, left to right: Tefris environment, VizDoom TakeCover and DefendThel HauntedHouse with pursuing "enemies," where the agent can reach a more stable state by finding the doors and leaving the region with enemies. Bottom row, left to right: Humanoid next to Cliff. Humanoid
Treadmill, Pedestal, Humanoid learning to walk.
Tetris. The classic game offers a naturally unstable environment- - the world evolves according its own dynamics even in the absence of coordinated agent actions, piling pieces and filling the board. The agent's task is to place randomly supplied blocks to construct and eliminate complete rows. The environment gives a reward of when the agent fails dies by stacking a column too high. Otherwise, the agent gets 0.
VizDoom. We consider two VizDoom environments from Kempka et al. (2016): TakeCover and DefendTheLine where enemies throw fireballs at the agent, which can move around to avoid damage. TakeCover is unstable and evolving, with new enemies appearing over time and firing at the player. The agent is evaluated on how many fireballs hit it, which we term the "damage" taken by the agent.
HauntedHouse. This partially observed navigation task. The agent (red) starts on the left of the map, and is pursued by "enemies" (blue). To escape, the agent navigate down the hallways and through randomly placed doors (green) to reach the safe room on the right, which the enemies cannot enter. To get to the safe room the agent must endure increased surprise early on, since the doors appear in different locations in each episode.
Simulated Humanoid robots. A simulated planar Humanoid agent must avoid falling in the face of external disturbances (Berseth et al., 2018). We evaluate four versions of this task. For Cliff' the agent is initialized sliding towards cliff, for Treadmill, the agent on small platform moving backwards at 1 m/s. In Pedestal, random forces are applied to it, and objects are thrown at it. In Walk, we evaluate how the SMiRL reward stabilizes an agent that is learning to walk. In all four tasks, we evaluate the proportion of episodes the robot does not fall.
Training Details. For discrete action environments, the RL algorithm used is DQN (Mnih al., 2013) with a target network. For the Humanoid domains, we use TRPO (Schulman et al., 2015). For Tetris and the Humanoid domains, the policies are parameterized by fully connected neural networks, while VizDoom uses a convolutional network. Additional details are in Appendix Section B.
Environment Stability, In Section 3, we described the connection between SMiRI. and unstable environments. We can quantify how unstable an environment is by computing a relative entropy gap. We compare the entropy between three methods: entropy minimizing (SMiRL), entropy maximizing (RND) methods, and an initial random (Random) policy (or, more generally, an uninformed policy, such as a randomly initialized neural network). In stable environments, an uninformed random policy would only attain slightly higher state entropy than one that minimizes the entropy explicitly (SMiRL Random ~ 0). whereas a novelty-seeking policy should attain much higher entropy (RND Random 0). indicating relative entropy gap in the positive direction. In unstable environment,
5

---

Published as a conference paper at ICLR 2021
Sewapy
6.115
0.193
C.100
loand
Crede Doso ceaned
6.05
1e4
364
Deall
8.05
1.45
Revard
Rowert
Femadd -M
Eslodea
Figure 3: Comparison between SMiRL, ICM, RND, and Oracle baseline that uses the true reward, evaluated on Tetris with (top-left) number of deaths per episode (lower is better), (top-center) rows cleared per episode (higher is better), and in TakeCover (top-right) and DefendTheLine (bottom-left) on amount of damage taken (lower is better). In all cases, the RL algorithm used for training is DQN, and all results are averaged over random seeds, with the shaded areas indicating the standard deviation. In Tetris (bottom-center) and Cover (bottom-right) methods are evaluated on how they improve learning when added to the environment reward function.
expect random policies and novelty-secking policies should attain similar entropies, whereas entropy minimization should result in much lower entropy (SMiRL- Rand < 0), indicating negative entropy gap. To compute the entropy used in this evaluation, we used the approximation in Eq. multiplied by 1 for three of our tasks well many Atari games studied in the RND paper (Burda et al., 2018b), with numbers shown in Table and full results in Appendix E. Our environments have a large negative entropy gap, whereas most Atari games lack this clear entropy gap.? 2 We therefore expect SMiRL to perform well on these tasks, which we use in the next section, but poorly on most Atari games. We show animations of the resulting policies on our anonymous project website.
EXPERIMENTAL RESULTS
Our experiments aim to answer the following questions: (1) Can SMiRL learn meaningful and complex emergent behaviors without pervision? (2) Can we improve SMiRL by in- corporating representation learning via VAES, as described in Section 3? (3) Can SMiRL. serve as joint training objective to acceler- ate the acquisition of reward- reward-guided guided behavior, and does it outperform prior intrinsic motivation methods in this role? We also illustrate sev- eral applications of SMiRL, showing that it can accelerate task learning, facilitate exploration, and implement a form of imitation learning. Video results of leamned behaviors are available at https:::/ / sites.. google. com/ com/view/ view/ surpriss semi nimi i
Environment
RND
SMiRL*
Relative
DefendTheLine
-0.311.66
43.1
-43.4
Tetris
1.5+2.7
-11.922.1
-10.4
TakeCover
-1.2=0077
-7.3+0.7
-8.5
Assault
11.3+1.44
-56.942.33
-45.6
Spacelnvaders
1.943.4
-10.244.2
-8.3
Carnival
20.411.4
-23.1
-2.7
RiverRaid
-5.543.4
5.8+3.2
0.3
Gravitar
30.8+11.7
-26.5+1..3
4.3
Berzerk
17.2+1.4
-2.9+4.7
14.3
Table 1: Difference in entropy vs. a Random policy SMMRLL=-MiRLLRRamee and HUD*=RND-Randon More negative values in- dicate more unstable environments. Note the negative relative entropy gap on our tasks and for Assault and Spacelwvaders.
Raative=RND*++MMiRRR

---

Published as a conference paper at ICLR 2021
5.1 EMERGENT BEHAVIOR WITH UNSUPERVISED LEARNING
To answer (1), we evaluate SMiRL on the Tetris, VizDoom and Humanoid tasks, studying its ability to generate purposeful coordinated behaviors without engineered task-specific rewards. We compare SMiRL to two intrinsic motivation methods, ICM (Pathak et al., 2017) and RND (Burda et al., 2018b), 8b), which seek out states that maximize surprise or novelty. For reference, we also include an Oracle baseline that directly optimizes the task reward. We find that SMiRL acquires meaningful emergent behaviors across these domains. In both the Tetris and VizDoom environments, stochastic and chaotic events force the SMiRL agent to take coordinated course of action to avoid unusual states, such as full Tetris boards or fireball explosions. On Tetris, after training for 3000 epochs, SMiRL achieves near-perfect play, on par with the oracle baseline, with deaths, indicating that SMiRL may provide better dense rewards than the Oracle reward, as shown in Figure 3 (top-left. top-middle). Figure 3 top-left and top-center show data from the same experiment that plots two different metrics, where the Oracle is optimized for minimizing deaths. We include another oracle, Oracle (rows cleared) where the reward function is the number of rows cleared. ICM and RND seek novelty by creating more and more distinct patterns of blocks rather than clearing them, leading to deteriorating game scores over time. The SMiRL agent also learns emergent game playing behavior in VizDoom, acquiring an effective policy for dodging the fireballs thrown by the enemies, illustrated in Figure 3 (top-right and bottom-left))
sevelty-seeking seeking methods once again yield deteriorating rewards over time. In Cliff,, the SMiRL agent learns to brace against the ground and stabilize itself at the edge, as shown in Figure 2. In Treadmill, SMiRL learns to jump forward to increase the time it stays on the treadmill. In Pedestal, the agent must actively respond to persistent disturbances. We find that SMiRL learns policy that can reliably keep the agent atop the pedestal, as shown in Figure 2. Figure 4 plots the reduction in falls in the Humanoid environments. Novelty-seeking methods learn irregular behaviors that cause the humanoid to jump off the Cliff and Pedestal tasks and roll around on the Treadmill, maximizing the variety (and quantity) of falls.
Next, we study how representation learning with a VAE improves the SMiRL algorithm (question (2)). In these experiments, we train VAE model and estimate surprise in the VAE latent space. This leads to faster acquisition of the emergent behaviors for TakeCover (Figure 3, top-right), Cliff' (Figure 4, left), and Treadmill (Figure 4, middle), where it also leads to more successful locomotion behavior.
At first glance, the SMiRL surprise minimization objective appears to be the opposite of standard intrinsic motivation objectives (Bellemare et al., 2016; Pathak et al., 2017: Burda et al., 2018b) that seek out states with maximal surprise (i.e., novel states). However, while those approaches measure surprise with respect to all prior experience, SMiRL minimizes surprise over each episode. We demonstrate that these two approaches are in fact complementary. SMiRL can use conventional intrinsic motivation methods to aid in exploration minimizing surprise. We can, therefore, combine these two methods and learn more sophisticated behaviors. While SMiRL on its own does not successfully produce good walking gait on Treadmill, the addition of novelty-sekking intrinsic motivation allows increased exploration, which results in an improved walking gait that remains on the treadmill longer, as shown in Figure (middle). We
discover more effective policies for
We expect that in all cases, random policies will have somewhat higher state entropy than SMiRI., so the entropy gap should be interpreted in a relative sense.
Treadel: Comocks
Podimled Caaacdr
SMRL Jun
VAG TRUn 10N
02
Figure 4: Cliff. Treadmill and Pedestal results. In all cases, SMiRL reduces episodes with falls (lower is better). SMiRL that uses the VAE for representation learning typically attains better performance. Trained using TRPO with results averaged over 12 random seeds, showing mean and standard deviation in the shaded area.
7

---

Published as a conference paper at ICLR 2021
Tecket PL Poward
SMIRL:
SMIRL+Counis
Here we show SMiRL's incentive for longer-term planning in the HauntedHouse envi- ronment. On the top-left, we see that SMiRL on its own does not explore well enough to reach the safe room on the right. Adding exploration via Counts (bottom-left) allows SMiRL to discover more optimal entropy reducing policies, shown on the right.
Figure 5:
evaluate this combined approach across environments including Pedestal and Cliff as well, where learning to avoid falls is also a challenge. For these two tasks SMiRL can already discover strong surprise minimizing policies and adding exploration bonuses does not provide additional benefit. In Figure 5 adding a bonus enables the agent to discover improved surprise minimizing strategies.
SMiRL and long term surprise. Although the SMiRL objective by itself does not specifically encourage exploration, we observe that optimal SMiRL policies exhibit active "searching" behaviors, seeking out objects in the environment that would allow for reduced long-term surprise. For example, in HauntedHousee, the positions of the doors leading to the safe room change between episodes, and the policy trained with SMiRI. learns to search for the doors to facilitate lower future surprise, even finding the doors themselves yields higher short-term surprise. This behavior is illustrated in Figure 5, along with the "delayed gratification" plot, which shows that the SMiRL agent incurs higher surprise early in the episode, for the sake of much lower surprise later.
5.2 APPLICATIONS OF SMIRL
While the focus of this paper is on the emergent behaviors obtained by SMiRL, here we study more pragmatic applications. We show that SMiRL can be used for basic imitation and joint training accelerate reward-driven learning.
Targets States attained SMiRL
Imitation. SMiRL can be adapted to perform imitation by initial- izing the prior via the buffer Do with states from demonstrations, or individual desired outcome states. We initialize the buffer Do Tetris with user-specified desired board states. An illustration of the Tetris imitation task is presented in Figure 6, showing imitation of box pattern (top) and checkerboard pattern (bottom), with the leftmost frame showing the user-specified example, and the other frames showing actual states reached by the SMiRL agent. While several prior works have studied imitation without example actions (Liu et al., 2018; Torabi et al., 2018a; Aytar et al., 2018; Torabi al., 2018b 8b; Edwards et al., 2018; Lee al.), this capability emerges automatically in SMiRL, without any further modification to the algorithm.
Figure 6: Tetris imitation by
starting (o with left image.
SMiRL as an auxiliary reward. We explore how combining SMiRL with task reward can lead to faster learning. We hypothesize that, when the task reward is aligned with avoiding unpredictable situations (c.g., falling or dying), adding SMiRL as an auxiliary reward can accelerate learning by providing a dense intermediate signal. The full reward is given by Toombined (s) Fima ar arsMiRI. (s). where a chosen to put the two reward terms at a similar magnitude. We study this application of SMiRL in the tasks: Tetris in Figure 3 (bottom DefendTheLine and Walk. On the easier tasks Tetris and TakeCover task (Figure 7), prior exploration methods generally lead to significantly worse performance and SMiRL improves learning speed. On the harder Walk and DefendTheLine tasks, the SMiRL reward accelerates learning substantially, and also significantly reduces the number of falls deaths. We found that increasing the difficulty of Tover and DefendTheLine (via the environment's difficulty setting (Kempka et al., 2016)) resulted in clearer separation between SMiRI and other methods
TakeCover in Figure 3 (bottom-right),
8

---

Published as a conference paper at ICLR 2021
Wal Town Falls
Wel Took Rowerd
684
0.4
Savend ID4
SURL YAUT
Fonard 1ND
02
60
groodss
Eppcciss
Figure 7: Left: We combine SMiRL with the survival time task reward in the DefendTheLine task. Middle/Right: We combine the SMiRL reward with the Walk reward and initialize SMiRL without walking prior walking data (ours) and with (prior data). Results over 12 seeds with standard deviation indicated by the shaded area.
In Walk, we include a version of SMiRL with prior data, where (o() is initialized with 8 walking trajectories (256 timesteps each), similar to the imitation setting. Incorporating prior data requires no modification to the SMiRL algorithm, and we can see in Figure 7 (middle and right) that this variant ("Reward SMiRL prior data") further accelerates learning and reduces the number of falls. This shows that while SMiRL can learn from scratch, it is possible to encode prior knowledge in (s) to improve learning.
6 DISCUSSION
We presented an unsupervised reinforcement learning method based on minimizing surprise. We show that surprise minimization can be used to learn a variety of behaviors that reach "homeostasis." putting the agent into stable state distributions in its environment. Across a range of tasks, these cycles correspond to useful, semantically meaningful, and complex behaviors: clearing rows in Tetris, avoiding fireballs in VizDoom, and learning to balance and hop with bipedal robot. The key insight utilized by our method is that, in contrast to simple simulated domains, realistic environments exhibit unstable phenomena that gradually increase entropy over time. An agent that resists this growth in entropy must take effective and coordinated actions, thus learning increasingly complex behaviors. expler This stands in contrast to commonly proposed intrinsic exploration methods based on novelty.
Besides fully unsupervised reinforcement learning, where show that our method can give rise to intelligent and sophisticated policies, we also illustrate several more practical applications of our approach. We show that surprise minimization can provide a general-purpose auxiliary reward that, when combined with task rewards, can improve learning in environments where avoiding catastrophic (and surprising) outcomes is desirable. We also show that SMiRL can be adapted to perform rudimentary form of imitation.
Our investigation of surprise minimization suggests several directions for future work. The particular behavior of a surprise minimizing agent is strongly influenced by the choice of state representation: by including or excluding particular observation modalities, the agent will be more or less surprised. Thus, tasks may be designed by choosing an appropriate state or observation representations. Explor- ing this direction may lead to new ways of specifying behaviors for RL agents without explicit reward design. Other applications of surprise minimization may also be explored in future work, possibly for mitigating reward misspecification by disincentivizing any unusual behavior that likely deviates from what the reward designer intended. The experiments in this work make use of available or easy to learn state representations. Using these learned representations does not address the difficulty of estimating and minimizing surprise across episodes or more generally over long sequences (possibly a single episode) which is challenge for surprise minimization- non-episodic surprise minimization is promising direction for future research study how surprise minimization can result in intelligent and sophisticated behavior that maintains homeostasis by acquiring increasingly complex behaviors.
methods. We believe that
The authors thank Aviral Kumar and Michael Janner for discussion. This research was supported by a DARPA Young Faculty Award #D13AP0046, Office of Naval Research, the National Science Foundation, NVIDIA, Amazon, and ARL DCIST CRA 1911NF-117--0118
Acknowledgments

---

Published as a conference paper at ICLR 2021
REFERENCES
Joshua Achiam and Shankar Sastry. Surprise-based intrinsic motivation for deep reinforcement learning. CoRR, abs/1703.01732. 2017a. URL http: www.orgg////.... abs/ 703. 01 732.
Joshua Achiam and Shankar Sastry. Surprise-based intrinsic motivation for deep reinforcement learning. arXiv preprint arXiv: 170.00133, 2017b.
Louis Annabi, Alexandre Pitti, and Mathias Quoy. Autonomous learning and chaining of motor primitives using the free energy principle. arXiv preprint arXiv:2005.05151, 2020.
Yusuf Aytar, Tobias Pfaff, David Budden, Thomas Paine, Ziyu Wang. and Nando de Freitas. Playing hard exploration games by watching youtube. In Advances in Neural Information Processing Systems, pp. 2930-2941, 2018.
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. arXiv preprint 1rXiv:1909.000 1909.07529, 2019.
Trapit Bansal, Jakub Pachocki, Szymon Sidor, lya Sutskever, and Igor Mordatch. Emergent com- plexity via multi-agent competition. arXiv preprint 171.v:/710.033444 2017.
Mare Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems, pp. 1471 1471-1479, 2016.
Glen Berseth, Xue Bin Peng, and Michiel van de Panne. Terrain RL simulator. CoRR, abs/1804 180.0064444 2018. URL hwtp:ttttt/a/...trrreeeee aabs////////// abs///////41 /0044 06424.
M. Bichl, C. Guckelsberger, C. Salge, Smith, and D. Polani. Free energy, empowerment, and predictive information compared. 2018.
Ludwig Boltzmann. The second law of thermodynamics. 1886.
Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A. Efros. Large-Scale Study of Curiosity-Drivee Driven Learning. 2018a. URL hattp://arxiv.or// 1808. 04355.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. ICLR, 2018b.
Boyuan Chen, Shuran Song, Hod Lipson, and Carl Vondrick. Visual hide and seek. In Artificial Life Conference Proceedings, pp. 645-655 655. MIT Press, 2020.
Nuttapong Chentanez, Andrew G Barto, and Satinder P Singh. Intrinsically motivated reinforcement learning. In Advances in neural information processing systems, pp. 1281-1288, 2005.
Maxime Srevalier-Boivvers Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. https: : / ///ggituuu com/maxe httm///axmecb////mmmmmmm gym-gymmmmmi comm-minngrrd., 2018.
Ashley D Edwards, Himanshu Sahni, Yannick Schroecker, and Charles Isbell. Imitating latent policies from observation. arXiv preprint arXiv:1805.072 1805.0795 2018.
Mohammadjavad Faraji, Kerstin Preuschoff, and Wulfram Gerstner. Balancing new against old information: the role of puzzlement surprise in learning. Neural computation, 30(1):34-83, 2018.
Karl Friston. The free-energy principle: a rough guide to the brain? Trends in cognitive sciences, 13 (7):293-301, 2009.
Karl Friston, Thomas FitzGerald, Francesco Rigoli, Philipp Schwartenbeck, Giovanni Pezzulo, et al. Active inference and learning. Neuroscience & Biobehavioral Reviews, 68:862-879, 2016.
Karl J. Friston, Jean Daunizeau, and Stefan J. Kiebel. Reinforcement learning active inference? PLOS ONE, 4(7):1-13, 07 2009. doi: Ijj377/jourall.oon 0006421. 0006.44 URL https: /doii org/10. 13.00.1111///0 /jornnal .oo.aa...p........m.......om pone. 6006421.
10

---

Published as a conference paper at ICLR 2021
Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. In International Conference on Machine Learning, pp. 2681-2691, 2019.
Rein Houthooft, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. VIME: Variational Information Maximizing Exploration. 2016. URL httpp://arxiv..rg////a 1605. 09674.
Michat Kempka, Marek Wydmuch, Grzegorz Runc, Jakub Toczek, and Wojciech Jaskowski. Vizdoom: A doom- ai research platform for visual reinforcement learning. In 2016 IEEE Conference on Computational Intelligence and Games (CIG), pp. 1-8. IEEE, 2016.
Kuno Kim, Megumi Sano, Julian De Freitas, Nick Haber, and Daniel Yamins. Active world model learning with progress curiosity. arXiv preprint arXiv:2007.07883, 2020.
Youngjin Kim, Wontae Nam, Hyunwoo Kim, Ji-Hoon Kim, and Gunhee Kim. Curiosity-bottlenek:: Exploration by distilling task-specific novelty. In International Conference on Machine Learning, pp. -3798,388,.1. 2019.
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. ICLR, 2014.
Alexander S. Klyubin, Daniel Polani, and Chrystopher L. Nehaniv. All else being equal be empow- ered. In Mathieu S. Capcarrère, Alex A. Freitas, Peter J. Bentley, Colin G. Johnson, and Jon Timmis (eds.), Advances in Artificial Life, pp. 744-753, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. ISBN 978-3-540-3181633
Lisa Lee, Benjamin Eysenbach, Emilio Parisotto, Ruslan Salakhutdinov, and Sergey Levine. State marginal matching with mixtures of policies.
Lisa Lee, Benjamin Eysenbach, Emilio Parisotto, Eric Xing, Sergey Levine, and Ruslan Salakhutdinov. Efficient exploration via state marginal matching. arXiv preprint arXiv: 05274, 2019.
Joel Lehman and Kenneth O Stanley. Abandoning objectives: Evolution through the search for novelty alone. Evolutionary computation, 19(2):189-223, 2011.
YuXuan Liu, Abhishek Gupta, Picter Abbecl, and Sergey Levine. Imitation from observation: Learning to imitate behaviors from raw video via context translation. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 1118-1125. IEFE, 2018
Manuel Lopes, Tobias Lang, Mare Toussaint, and Pierre-Y Yves Oudeyer. Exploration in model- based reinforcement learning by empirically estimating learning progress. Advances in neural information processing systems, pp. 206-214, 2012.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 13 2013.
Shakir Mohamed and Danilo Jimenez. Rezende. Variational information maximisation for intrinsically motivated reinforcement learning. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems 28, pp. 2125-2133. Curran Associates, Inc., 2015.
Fierre-Yver Oudeyer and Frederic Kaplan. What is intrinsic motivation? a typology of computational approaches. Frontiers in neurorobotics, 1:6, 2009.
Pierre-Yve Yves Oudeyer, Frdric Kaplan, and Verena Hafner. Intrinsic motivation systems for au- tonomous mental development. IEEE transactions evolutionary computation, 11(2):265-266. 2007.
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity Exploration by Self-supervised Prediction. 2017.
Deepak Pathak, Dhiraj Gandhi, and Abhinav Gupta. Self-Supervised Exploration via Disagreement. 2019.
11

---

Published as a conference paper at ICLR 2021
Jürgen Schmidhuber. Curious model-building control systems. In Proc. internationaa joint conference on neural networks, pp. 1458-1463. 1991.
Eric D Schneider and James J Kay. Life as manifestation of the second law of thermodynamics. Mathematical and computer modelling, 1966-8)25548,, 1994.
Erwin Schrödinger. What life? The physical aspect of the living cell and mind. Cambridge University Press Cambridge, 1944.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897, 2015.
Pranav Shyam, Wojciech Jaškowski, and Faustino Gomez. Model-based active exploration. arXiv preprint 1rXiv:18100 12162, 2018.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with general reinforcement learning algorithm. arXiv preprint 172.01171..01815, 2017.
Susanne Still and Doina Precup. An informatioo-theorett approach to curiosity-driven reinforcement learning. Theory in Biosciences, 131(3):139-143 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 arXiv:1003.05407, 2017.
Yi Sun, Faustino Gomez, and Jürgen Schmidhuber. Planning to be surprised: Optimal bayesian ex- ploration in dynamic environments. In International Conference on Artificial General Intelligence, pp. 41-51. Springer, 2011.
Faraz Torabi, Garrett Warnell, and Peter Stone. Behavioral cloning from observation. arXiv preprint arXiv: 1805.01944 2018a.
Faraz Torabi. Garrett Warnell, and Peter Stone. Generative adversarial imitation from observation. arXiv preprint arXiv: 1807.0615..5 2018b.
Alexander Tschantz, Manuel Baltieri, Anil Seth, and Christopher L Buckley, Scaling active inference. In 2020 International Joint Conference on Neural Networks (IJNN), pp. 1-8. IEEE,
2020a.
Alexander Tschantz, Beren Millidge, Anil Seth, and Christopher L Buckley. Reinforcement learning through active inference. arXiv preprint arXiv:2002.12636 2020b.
Kai Ueltzhöffer. Deep active inference. Biological Cybernetics, 11(())547-573, 2018.
Luca Weihs, Aniruddha Kembhavi, Winson Han, Alvaro Herrasti, Erie Kolve, Dustin Schwenk, Roozbeh Mottaghi, and Ali Farhadi. Artificial agents learn flexible visual representations by playing a hiding game. arXiv preprint arXiv:1912.08) 2019.
12

---

Published as a conference paper at ICLR 2021
A STATE ENTROPY MINIMIZATION DERIVATION
Here we will show that the SMiRL reward function leads to policy objective that lower- bounds the negative entropy of the state marginal distribution, (d In the infinite hori- setting, the value of trajectory
(Su. ag, $1, .2..1.....) is given the discounted cumu-
lative rewards: R(T) = (1 7) Li=o 7'r(s,, ae). In our case, r(s,, at) is a function only of state:
r(s,, 04) (st) log (s.). The policy and dynamics define trajectory distribution
p(T(Ø) = p(so) I p(S++1 St, az) ) (ar(s)). The value of a policy is its expected cumulative
reward:
v = Errp(tr = (1-7) m Σ rr(ss).
Using the indicator function [(a = b) _ 1f a b; + b, the t-step state distribution and the discounted state marginal are given
d p(s: = s|Ta) E s)
d (s) (1 7) Σ (s)
1=0
The expected reward under the discounted state marginal equivalent to the policy value V
R (6) (n)(((s)] = f f (*)
= -11-))B,~
76 1(s: = s)r(s)ds
= -11-))
r'((s)) = V
After incorporating the rewards, the policy value becomes:
v = Ex- (r)s) = = B (og]]====)== 0(0,0) = (d (dd < (dd
where (dd Pa) denotes the cross-entropy between d and po. Thus, by optimizing vs with reward function log (s) via RL, we maximize the policy value, equivalent to the negative cross cross-entropy from the discounted state marginal and the model. By optimizing pe with density estimation (minimizing forward cross-entropy) of states induced by πæ. we tighten the bound towards Hdd (s)). When the model is perfect (i.e., Po dd the inequality becomes tight. As discussed in the main text, we cannot draw samples from (s). We can only sample trajectories of finite length T by rolling out the policy Tg. In this case, the finite-horizon discounted state marginal can be written as:
T-1 1
Te T (s)
4
1-7 7
Σ
7'p(s, = s/
1 - TT
1=1
T-1
1 1 7
Σ
" (Brrp(TTEs) ((: =8 <T).
T 1=
Note that To (s) 2 Vs, and Eg n.. (8)=
Σt 1 7. Σ, (s - T <T)=1. =1.
T (s) converges to d (s) as T oo: limy J (1- Σe ' ( 1 1(s = = o
Thus, by using d (s) in place a (s), we obtain an objective, - -d (s)))) that we approximate with sample of finite-length trajectories and optimize with respect Φ using
13

---

Published as a conference paper at ICLR 2021
seflcy-gradienttt reinforcement learning algorithm on the equivalent finite-horizon value function:
J(b; - -1 (d (s).pa(s) = V=L.T
T-1
1 1 7
1 7 Er~ p(
7' po.)).
The approximation to ((;; improves as T + oo, since +o d=aif = d=
B ADDITIONAL IMPLEMENTATION DETAILS
Additional Training Details. The experiments in the paper used two different RL algorithms for discrete action environemnts (Double DQN) and continuous action environments (TRPO). For all environments trained with Double-DQN (Tetris, VizDoom, HauntedHfouse) we use a fixed episode length of 500 for training and collect 1000 sample between training rounds that perform 1000 gradient steps on the network. The replay buffer size that is used is 50000. The same size is used for additional data buffers for RND and ICM. For Tetris and HauntedHouse network with layer sizes [128, 64, 32] is used for both Q-networks. For VizDoom the network include 3 additional convolutional layers with [64, 32, 8] filters with strides [5, 4, 3]. all using relu activations. A learning rate of 0.003 is used to train the Q networks.
For the Humanoid environments the network uses relu activations with hidden layer sizes [256, 128). TRPO is used to train the policy with the advantage estimated with Generalize Advantage Estimation. The training collects 4098 sample at a time, performs 64 gradient steps on the value function and one step with TRPO. A fixed variance is used for the policy of 0.2 which is scaled according to the action dimensions from the environment. Each episode consisted of 4 rounds of training and it typically take 20 hours train one of the SMiRL policies using threads. A kl constraint of 0.2 is used for TRPO and learning rate of 0.001 is used for training the value function. Next, we provide additional details on the state and action spaces of the environments and how 0 was represented for each environment.
Tetris We consider a 4 X 10 Tetris board with tromino shapes (composed of 3 squares). The observation is a binary image of the current board with one pixel per square, as well as an indicator integer for the shape that will appear next. A Bernoulli distribution is used to represent the sufficient statistics 0 given the to policy for SMiRL. This distribution models the probability density of a block being in each of the boad locations. Double-DOp -DQ is used to train the policy for this environment. The reward function used for this environment is based on the Tetris game which gives more points for eliminating more rows at single time.
VizDoom For the VizDoom environment the images are scaled down to be 48 x 64 grayscale. Then a history of the latest 4 images are stacked together to use as in separate channels. To greatly reduce the number of parameters 8, SMiRL needs to estimate in order to compute the state entropy the image is further reduces to 20. A Gaussian distribution is used to model the mean and variance over this state input. This same design is used for Tove and DefendThel.ine An episode timelimit of 500 is used for each environent. Double-DQN is used to train the policy for this environment.
Simulated Humanoid robots. A simulated planar Humanoid agent must avoid falling in the face of external disturbances (Berseth et al., 2018). The state-space comprises the rotation of each joint and the linear velocity of each link. We evaluate four versions of this task: Cliff, Treadmill, Pedestal, and Walk. The Cliff task initializes the agent at the edge of a cliff, in a random pose and with a forward velocity of m/s. Falling off the cliff leads to highly irregular and unpredictable configurations. so a surprise minimizing agent will want to learn to stay on the cliff. In Treadmill, the agent starts on a platform that is moving backwards objects are thrown at it. In this environment, the agent starts on a thin pedestal and random forces are applied to the robot's links and boxes of random size are thrown at the agent. In Walk, we evaluate how the SMiRL reward stabilizes an agent that is learning to walk. In all four tasks, evaluate the proportion of episodes the robot does not fall. A state is classified a fall if the agent's 's links, except for the feet, touch the ground, or if the agent is -5 meters more below the platform state is continuous, We model (s) as independent Gaussian for these tasks. The full pose and link velocity state is used for the Humanoid environments 0. The simulated robot has control frequency
m/s. In Pedestal, random forces are applied to it, and
cliff. Since the
14

---

Published as a conference paper at ICLR 2021
Figure 8: Frames from Tetris, with state the left and parameters 8, of an independent Bernuulli distribution for each board location on the right, with higher probability shown in yellow. The top row indicates the newly added block and bottom row shows how the state changes due to the newly added block along with the updated Oz.
of 30hz. TRPO is used train the policy for this environment. Similar to VizDoom p(s) is modeled as an independent Gaussian distribution for each dimension in the observation. Then, the SMiRL reward can be computed as:
SSMRL (s) = Σ - (8: p4: (8-)))²
(b)²)
207
where is a single state, (4, and o2 are calculated as the sample mean and standard deviation from Dr and S; is the tt observation feature of s.
This partially observed navigation environment is based on the zym_minigrid toolkit (Chevalier-Boois et al., 2018). The agent vision if changed to be centered around the agent. The experiments in the paper combine SMiRL with curiosity measures for Counts that are computed using the agent locations in the discrete environment. Similar, to the VizDoom and Humanoid environments a Gaussian distribution over the agents observations is used to estimate 0. Double-DQN is used to train the policy for this environment.
HauntedHouse.
SMiRL VAE training The encoders and decoders of the VAEs used for VizDoom and Humanoid experiments are implemented as fully connected networks. The coefficient for the KI.-divergence term in the VAE loss was 0.1 and 1.0 for the VizDoom and Humanoid experiments, respectively. We found it very helpful to train the VAE in batches. For the Humanoid experiments where TRPO is used to train the policy the VAE is trained every 4 data collection phases for TRPO. This helped make the learning process more stationary, increasing convergence. The design of the networks used for the VAE mirrors the size and shapes of the policies used for training described earlier in this section.
Fixed Length Episodes For SMiRL it helped to used fixed length episodes during training to help keep SMiRL from terminating early. For example, in the VizDuom environments SMiRL would result in policies that would terminate
as possible the agent would return to similar initial state. In fact, for training we need to turn on god mode to prevent this behaviour. Similarly, to discourage SMiRL from terminating Tetris early by quickly stacking pieces in the same tower (resulting in low entropy) we added "soft resets" where the simulation will reset when the game fails and the episode will continue on forcing the SMiRL agent learn how to eliminate rows reduce the number of blocks in the scene.
C SMIRL DISTRIBUTIONS
SMiRL on Tetris. In Tetris, since the state is binary image, we model p(s) as product of independent Bernoulli distributions for each board location. The SMiRL reward log (s()) becomes:
TSMIRL (s) Σ s; log 0g + (1 (s) log(1 - 02).
where s is a single state, the update procedure 8; = (D,,) returns the sample mean of De, indicating the proportion of datapoints where location i has been occupied by block, and s; is a binary variable indicating the presence of a block at location i. If the blocks stack to the top, the game board resets, but the episode continues and the dataset D, continues accumulate states.
15

---

Published as a conference paper at ICLR 2021
Environment
RND
Random
SMiRL
Relative
Tetris
18.6+2..7
17.1
5.2+2.1
43,44
Tover
-4.7=10.7
-5.9=1.1
-13.2=0.7
-0..4
DefendThel.ine
19.6+-0.6
19.9+0.77
-23.4+10.4
-8.5
Assault
193.1#1.4
181882.77
124.942.3
-4..6
Spacelnvaders
208.44+3.4
206.5+5.2
196.3+4.2
-8.3
Carnival
151.2-11.4
130.8+22.7
107.7+4.3
-2.7
RiverRaid
264.4113.4
269.1+2.22
274.9+3.22
0.3
Gravitar
198.6:11.7
167.842.7
141.341.3
4.3
Berzerk 197.2
180.042.7
177.144.7
14.3
Table 2: Estimated entropies for three of our tasks, and example Atari games studied by Burda et al. (2018b), where novelty-seeking exploration works well. Note the large negative Relative entropy gap in our tasks with overall lower initial entropy, which are both absent in most Atari games. This data shows the mean and std over 3 seeds.
D SMIRL MDP
Note that the RL algorithm SMiRL is provided with a standard stationary MDP (except in the VAE setting,
that below), where the state is augmented with the parameters of the belief over states and the timestep f. We emphasize that this MDP is Markovian, and therefore it is reasonable to expect any convergent reinforcement learning (RL) algorithm to converge
near-optimal solution. Consider the augmented state transition p( Oc+1 1, & + 1 1|, ax, Or, t). This transition model does are deterministic when given s, and t. The reward st, dz. f) is also stationary, and is in fact deterministic given and 0, Because SMiRL uses RL in MDP, we benefit from the same convergence properties as other RL methods.
not change over time because the updates function r(st,
Transition dynamics of 6;. Given the augmented state (st, fc. t), we show that the transition dynamics the MDP are Markovian. The S; portion of the augmented state are from the environment, therefore all convergence properties of RI. hold. Here we show that (0,, t) is also Markovian given 8,41- To this end, we describe the transition dynamics of (0,, for an incremental estimation of Gaussian distribution, which is used in most experiments. Here we outline 0 = Us,,, 0,,t).
0, (Mi, o?)
t44 +
Pc+1
1+1
0,1 t(0? + 1 + 8:
-1
++1
0.11 (1441, o241
4+1 4, +1
These dynamics dependant the current augmented state (st, () and the state 8 of the RI. environment and do not require an independent model fitting process.
However, the version of SMiRL that to not adding the VAE parameters to the state s, and thus the reward function changes over time. We find that this does not hurt results, and note that many intrinsic reward methods such ICM and RND also lack stationary reward functions.
representation learned from VAE is not Markovian due
E MORE ENVIRONMENT STABILITY DETAILS
Here include the full data on the stability analysis in Figure 2. From this data and the additional results on the website we can see the SMiRL can reduce the entropy of a few of the Atari environments well. These include Assault, where SMiRL hides on the left but is good at shooting ships and Camival, where SMiRL also reduces the number of moving objects. RND on the other hand tends to induce entropy and cause many game flashes.
16

---

Published as a conference paper at ICLR 2021
Humanee
05
Traidri
Sptardka
Figure 9: SMiRL results when the Humanoid environments are trained without early termination based resets (fixed episode lengths), Cliff and Pedestal still produce entropy minimizing policies that reduce falls. RL has difficulty with optimizing the more challenging Treadmill environment.
F ADDITION NOTES ON UNSUPERVISED RL RELATED WORK
The works in Tschantz et al. (2020b); Annabi et al. (2020) are interesting and discuss connections to active inference and RL. However, these methods and many based on active inference "encode" the task reward function as a "global prior" and minimizing KI. between the agents state distribution this "global prior". Our work instead actively estimates marginal over the distribution of states the agent visits (with prior data) and then minimizes this "online" estimate of the marginal, as described in Section 3. Our work differs from LP-based methods (Kim et al., 2020; Lopes et al., 2012; Schmidhuber, 1991) because SMiRL is learning to control the marginal state distribution rather than identifying the system parameters.
G ADDITIONAL RESULTS
To better understand the types of behaviors SMiRL produces we conducted an experiment with fixed episode lengths the Humanoid environments (Figure 9). This shows that SMiRL results in surprise minimizing behaviors independent of how long the episode is.
17


Reviews:
[{"review_id": "XssQGoHC2vD", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors target the unsupervised reinforcement learning problem. An opposite idea from the existing approaches by maximizing state entropy is adopted to minimize state entropy. It is interesting that such an idea has achieved good performance in unstable environments. A state distribution is fitted during the interaction with an environment and the probability of the current state is used as a virtual reward. The parameters or sufficient statistics are also applied to the policy. The motivation is clear and verified. It is generally a good paper.\n\nIt is surprising that the exploration is achieved in the long term even minimizing state entropy. Is that possible the exploration events are from the 'unstable' environment? What if there are some patterns underlying the exploration events but only part of the 'unstable' environment? Is that OK to totally rely on unexpected events from the environment to explore the environment? Is that possible to add some exploration strategy in the developed model? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "McceVXFRRC6", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents and studies an unsupervised learning approach to the emergence of \"meaningful/useful\"\nbehaviour in a Deep RL setting, based on an algorithm which objective consists in minimizing surprise.\nIt is possible to see this paper as studying a Deep RL implementation of cognitive homeostasis, an old idea\nrecently popularized through the work on the free energy principle by Friston and colleagues.\nThe paper presents two versions of this algorithm, one without representation learning, and one with\nrepresentation learning (VAE), and compares it to Deep RL algorithms that maximize prediction error/novelty\nfrom two perspectives: emergence of behaviours and utility as an auxiliary reward to solve sparse reward problems.\nThe paper discusses the relevance of the approach in environments that are said to be \"unstable\" (with an attempt\nto formalize this concept). The paper also shortly presents an application of the algorithm for imitation learning.\nExperiments are presented in a variety of environments.\n\nMajor strengths:\n+ The paper is globally clear and well-written\n+ The qualitative results showing and analyzing emergent behaviour are stimulating\n+ Implementation of the free-energy principle in high-dimensional spaces is known to be challenging and this\npaper contributes towards understanding how to do it (yet the precise formal articulation between SMIRL and the\nFEP remains to be done, and this does not seem to be the primary objective of the paper)\n+ The discussion of the complementarity of within-episode SMIRL and across-episode novelty seeking intrinsic\nrewards is interesting\n+ The shortly described application for imitation learning is promising\n+ The are many and varied environments in experiments \n\nMajor weaknesses:\n- The environments chosen for experimentation are such that minimizing surprise aligns very well with either\nproducing \"interesting\" behaviour or maximizing an external reward. One could easily consider slight modifications\nof most environments where a trivial solution to minimizing surprise could be found instead (e.g. giving the ability to push\non the \"pause\" button in the Tetris game or having safe rooms in opposite directions than enemies in Vizdoom/HauntedHouse).\nIn a real robot, this would lead a robot to hide in the corner of a room and just look at a uniform wall that does not move.\nThis problem of trivial solutions to surprise minimization approaches has been called the Dark Room problem in\nthe FEP literature. This is known to be a limit of this general approach when applied to the real world, and how to address it\noperationnally (in a tractable manner) under this paradigm remains an open question.\n- Related to the point above, the fact that different environments are used in different experiments of the paper does not\nallow to get a good grasp of the general behaviour of the algorithm: I would recommend to run all experiments in all\nenvironments (maybe to report in Annex), and at least to justify why environmnets change across experiments.\n-  The paper is positioned in comparison with novelty seeking/prediction error maximizing agents, and motivates\nthe surprise minimizing approach by arguing that real-world situations are problematic for novelty seeking agents,\nas the real world spontenously generates novelty through distractors that should be avoided rather than explored.\nThis is accurate, but an incomplete discussion of the literature in the area of unsupervised learning of behaviours:\napproaches maximizing learning progress were precisely introduced to adress these limits of novelty seeking approaches\nand to scale to real world environments with two families of distractors: novel unlearnable parts of the environments\n(which is a problem for novelty seeking approaches) and trivial low-entropy parts of the environments (which are a problem\nin principle for surprise minimization approaches). Thus, the paper should position itself in comparison with LP-based\napproaches and show experiments with at least some of the existing LP-based algorithms (e.g. Schmidhuber, 1991; Lopes et al., 2012;\nKim et al., 2020).\n- As the authors acknowledge, the version of SMIRL using represention learning is not fully \"within episode surprise minmization\",\nas the learned representation depends on past episodes: as a consequence, it is unclear what one should conclude about the relation\nbetween within vs across episode mechanisms and the properties of emergent behaviours\n- The paper lacks discussion of related work aiming to implement surprise minimization approaches that scale to high-dimensional\nspaces, especially in a RL framework, e.g. Tschantz et al., 2020; Annabi et al., 2020\n- The paper does not provide code to enable reproducibility of results (and does not say it will)\n\nOverall, the topic of this paper is interesting and the work could make a valuabe contribution, especially from the perspective\nof studying incentives to emergent structured behaviour in unsupervised learning,. However, the weaknesses mentionned above need\nto be addressed to better establish the contributions of this paper, both in terms of understanding the generality of the\nresults and the contributions in relation to the existing litterature.\n\nReferences:\n\nAnnabi, L., Pitti, A., & Quoy, M. (2020). Autonomous learning and chaining of motor primitives using the Free Energy Principle. arXiv preprint arXiv:2005.05151.\nKim, K. H., Sano, M., De Freitas, J., Haber, N., & Yamins, D. (2020, January). Active world model learning in agent-rich environments with progress curiosity. In International Conference on Machine Learning (ICML).\nLopes, M., Lang, T., Toussaint, M., & Oudeyer, P. Y. (2012). Exploration in model-based reinforcement learning by empirically estimating learning progress. In Advances in neural information processing systems (pp. 206-214).\nJ. Schmidhuber, “Curious model-building control systems,” in Proc. Int. Joint Conf. Neural Netw., Singapore, 1991, vol. 2, pp. 1458–1463.\nTschantz, A., Baltieri, M., Seth, A. K., & Buckley, C. L. (2020, July). Scaling active inference. In 2020 International Joint Conference on Neural Networks (IJCNN) (pp. 1-8). IEEE.\nTschantz, A., Millidge, B., Seth, A. K., & Buckley, C. L. (2020). Reinforcement Learning through Active Inference. arXiv preprint arXiv:2002.12636.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "K9NW0mzoYle", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "------------------------------------        \n**Summary:**\n\nThis paper proposes a new intrinsic objective for RL agents: surprise minimization. This may come as a surprise, as other related works usually propose to maximize surprise, or to maximize novelty. The authors present motivations and conduct an empirical study on several environments to support their idea.\n\n------------------------------------        \n**Strong points:**\n\nOverall, I think it is a good paper. Let me list some strong points:\n\n* The idea is simple, novel and well motivated. The paper positions this new intrinsic objective with respect to variants of novelty maximization objectives and brings a new perspective.\n* It’s well written and organized\n* The algorithm is tested on a relevant selection of environments and against state-of-the-art algorithms using intrinsic objectives.\n* The empirical evidence seems to support the claims.\n* The related work is quite complete.\n* I liked the discussion about stable vs unstable environments. It is the first time I see it discussed.\n* The website brings visualizations of trained policies.\n------------------------------------        \n**Weak points:**\n\nI will now list a few weak points of the paper.\n* Some descriptions of the results are missing. In figures, what does the shaded area represent? (std, sem, confidence intervals, etc). In Table 1, what are the numbers? (what is the central tendency, what is the error, how many seeds?). Same for Appendix D.\n* The paper does not provide all necessary information to reproduce the results. There is no detail about the RL algorithms (TRPO and DQN), no description of the architectures, and no hyperparameters. This is important and should be contained somewhere in the Appendix. \n* Will the code be released? If not, why so? Same questions for the environments, are they accessible somewhere? \n* It seems to me that this approach could potentially tackle harder problems, but the paper is limited to a simplification of the tetris game, planar humanoid variants and Doom. The x-axes of the figures also tell us that only a few episodes were needed to solve them. I am not saying that I need the hardest games solved to find an algorithm interesting, but I am wondering whether it would scale. Could you tell us whether you attempted to tackle harder environments, and if so, why do you think SMiRL failed? I think we can gain a lot of understanding by looking at negative results. \nFor example, I feel like testing this algorithm on a 3D humanoid would better demonstrate the power of this approach. \n* It seems to me that there might be a confounding factor that could partially explain the success of the surprise reward. Indeed, it seems that all environments presented here can terminate when the agent dies. This is a guess, as I could not find this information in the paper (please add it). If so, then the expected cumulative rewards is an increasing function of the lifetime of the agent in the game. Because of this, maximizing the cumulative surprise might be a good idea because it goes in the same direction (by construction) as maximizing survival.\nA counter-argument from the paper can be the performance of SMiRL + reward in Walk, that is superior to the performance of reward alone. However, this is unclear as I could not find the description of the reward function in the paper (please add it). \nAnother way to disprove this hypothesis would be to compare the performance of SMiRL to the performance of an agent maximizing a reward function that gives +1 whenever the agent is alive (survival bonus). If it performs better, then surprise maximization brings something to the table, if it does not, then it might work because it is correlated to the survival time.\nAnother way could be to have episodes that do not include death-related resets (fixed length episodes).\n\n------------------------------------        \n**Recommendation and justification:**\nThis is overall a strong paper. However I’m concerned about the potential confounding factor of the survival time. I’ll give a score of 6, but I would happily increase that score if \n1. The authors convince me that the success of the surprise maximization is not due to the survival confounding factor.\n2. The authors include all necessary details for reproducibility and/or release the code. \n3. Discuss the scalability to harder problems (e.g. 3D Humanoid).\n\n------------------------------------        \n**Feedback to improve the paper (not part of assessment)**\n\n* I would move the discussion about how surprise minimization and novelty maximization can be complementary to the intro. These two approaches seem to go in opposite directions and, as a reader, I would be happy to read this discussion early.\n* It would be interesting to discuss how it plays out in natural agents. The intuition is that minimizing surprise leads to finding a stable configuration and staying there. In practice, it is probably balanced with other driving needs like the need for food. I guess it is discussed in related papers like Friston 2009. In natural agents, surprise minimization must also be model-based. Indeed, animals do not need to jump out of cliffs several times to know that it’s bad. \n* Not sure I understand the inequality in Eq1. Maybe I missed something.\n* Discuss the surprise maximization approach of Achiam et al and whether it differs from yours. \n* Table 1: the legend seems to disagree with the results. It seems to me that the entropy difference is as low in your environment as in the others, but the caption says “note the clear negative  entropy gap on our tasks, whereas this clear trend is absent on the Atari games”.\n* Fig 4. Is it really training in 80 episodes? There are very few images to train a VAE, especially if the episode resets when the agent falls (does it?) How many steps per episode?\n* How do you get demos for humanoid tasks? I guess there are not human demos but previously trained agents? \n* Results in Fig. 6 are not super satisfying, they are quite far from the target (although I guess it is a difficult task). I am not even sure the second example is achievable. In the traditional Tetris, wouldn’t cubes fall due to gravity?\n\n**Typos:**                \n* “our results are available online” → missing full stop.\n* “In such environments, which we believe are more reflective of the real world” → previous sentences do not discuss environments but intrinsic objectives.\n* “unexpected events don’t happen” → “do not”\n* “deep DQN” → “Deep Q-Networks”, or “DQN”\n\n\n**Update post-rebuttal**\nThe authors addressed most of my concerns, especially the one about the confounding factor. I am updating the score from 6 to 7.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "J0VfFbrJ7Vv", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work proposes an RL approach SMiRL that is able to learn effective policies in unstable environments without the need for external reward. The idea at a high-level is almost the opposite of intrinsic motivation RL approaches, which encourage novelty-seeking behaviors. The proposed method instead aims to minimize surprise or state entropy. To train the agent, rewards come from state marginal estimates, but because this distribution is changing, the authors create an augmented MDP. Through experiments on game domains and robot control tasks, the authors show that SMiRL outperforms intrinsic motivation methods. The authors also show that SMiRL can be used to do imitation and can be combined with regular reward signals.\n\nPros:\n- The problem formulation is interesting and novel. Intrinsic motivation is well studied, but this problem considers the setting where the environment is unstable rather than static, which requires new methods.\n- The paper is written well and is clear. The motivation is described well.\n- The authors evaluate on many domains, highlighting the diversity of settings in which the approach can be applied.\n\nCons:\n- It seems like this approach is only applicable to unstable environments. Does the approach fail for regular, static environments? I’m assuming the agent might just end up staying still because it’s trying to seek stable states. It can be combined with the external reward signal but will the minimizing entropy objective hurt you?\n- Without common sense knowledge, this approach would take many iterations to learn. So while this formulation might be more similar to the real world, the real world would only allow for a few interactions with the world.\n\nComments:\n- How is SMiRL doing better than the oracle in Figure 3 center?\n- In Figure 3 left, it might be a problem that with minimal episodes, SMiRL does worse. If SMiRL is useful for more real-world unstable environments, this would require a simulator good enough to model the real world.\n\nRecommendation:\nOverall, the paper is interesting and novel. The approach is reasonable and experiments show the value of the method in unstable environments. I recommend “accept”.\n\n------------\nPost-rebuttal response:\nThe authors addressed most of my concerns so I continue to recommend acceptance of the paper. Specifically, they answered my question about whether the approach will work in static environments and how prior data can be used to improve sample efficiency. They also conducted additional experiments to verify some of my questions.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is studying a new intrinsic motivation RL setup in a dynamic environment, where the authors minimize the state entropy instead of the common approach of maximizing it. The resulting idea is simple but also surprising that it works so well. All reviewers appreciated the new problem formulation of using dynamic environments and found the idea very promsing. In addition, they identified the following strengths of the paper:
- The experiments are exhaustive, identifying many domains where the approach can be applied
- The presented results are compelling
- The paper is well written
- The paper introduces a new problem setup that has not been studied before

I agree with the reviewers that this paper contains many interesting contributions and therefore recommend acceptance.


Decision: Accept (Oral)