Temporally-Extended ε-Greedy Exploration
Authors: Will Dabney
Georg Ostrovski
Andre Barreto
Venue: ICLR 2021 Poster (2021)
Keywords: reinforcement learning
exploration

Abstract: Recent work on exploration in reinforcement learning (RL) has led to a series of increasingly complex solutions to the problem. This increase in complexity often comes at the expense of generality. Recent empirical studies suggest that, when applied to a broader set of domains, some sophisticated exploration methods are outperformed by simpler counterparts, such as ε-greedy. In this paper we propose an exploration algorithm that retains the simplicity of ε-greedy while reducing dithering. We build on a simple hypothesis: the main limitation of ε-greedy exploration is its lack of temporal persistence, which limits its ability to escape local optima. We propose a temporally extended form of ε-greedy that simply repeats the sampled action for a random duration. It turns out that, for many duration distributions, this suffices to improve exploration on a large set of domains. Interestingly, a class of distributions inspired by ecological models of animal foraging behaviour yields particularly strong performance.

Published as a conference paper at ICLR 2021
TEMPORALLY-EXTENDER E- G-REEDY EXPLORATION
Will Dabney, Georg Ostrovski & André Barreto
DeepMind London, UK
(wdabney, ostrovski, andrebbarreoooegoogee.cco
ABSTRACT
Recent work exploration in reinforcement learning (RL) has led to series of increasingly complex solutions to the problem. This increase in complexity often comes at the expense of generality. Recent empirical studies suggest that, when applied to a broader set of domains, some sophisticated exploration methods are outperformed by simpler counterparts, such e-greedy. In this paper we propose an exploration algorithm that retains the simplicity of e-greedy while reducing dithering. We build on a simple hypothesis: the main limitation of e- greedy exploration is its lack of temporal persistence, which limits its ability to escape local optima. We propose temporally extended form of c-greedy that simply repeats the sampled action for a random duration. It turns out that, for many duration distributions, this suffices to improve exploration on a large set domains. Interestingly, a class of distributions inspired by ecological models of animal foraging behaviour yields particularly strong performance.
INTRODUCTION
Exploration is widely regarded as one of the most important open problems reinforcement learning (RL). The problem has been theoretically analyzed under simplifying assumptions, providing reas- surance and motivating the development of algorithms (Brafman and Tennenholtz 2002 Asmuth jet al. 2009; Azar, Osband, and Munos 2017). Recently, there has been considerable progress on the empirical side as well, with new methods that work in combination with powerful function approximators perform well challenging large-scale exploration problems (Bellemare et al.)
2016 Ostrovski et al., 2017 Burda et al. 2018: Badia et al., (020b).
Despite all of the above, the most commonly used exploration strategies are still simple methods like c-greedy, Boltzmann exploration and entropy regularization (Peters, Mulling, and Altun 2010 Sutton and Barto 2018). This is true for both work of more investigative nature (Mnih al. 2015 and practical applications (Levine et al. 2016 Li et al. (011). In particular, many recent successes of deep RL, from data-center cooling Atari game playing, rely heavily upon these simple exploration strategies (Mnih et al. 2015 Lazic et al. 2018 Kapturowski et al. 2019).
Why does the RL community continue to rely on such naive exploration methods? There are several possible reasons. First, principled methods usually do not scale well. Second, the exploration problem often formulated as separate problem whose solution itself involves quite challenging steps. Moreover, besides having very limited theoretical grounding, practical methods are often complex and have significantly poorer performance outside a small set of domains they were specifically designed for. This last point is essential, as effective exploration method must be generally applicable.
Naive exploration methods like e-greedy, Boltzmann exploration and entropy regularization are general because they do not make strong assumptions about the underlying domain. As consequence, they are also simple, not requiring too much implementation effort or per-domain tuning. This makes them appealing alternatives even when they not efficient as some more complex variants.
Perhaps there a middle ground between simple yet inefficient exploration strategies and more complex, though efficient, methods. The method propose in this paper represents such compro- mise. We ask the following question: how can we deviate minimally from the simple exploration strategies adopted in practice and still get clear benefits? In more pragmatic terms, want

---

Published as a conference paper at ICLR 2021
simple-to-mmplement algorithm that can be used in place of naive methods and lead to improved exploration.
In order to achieve our goal propose method that can be seen generalization of e-greedy, perhaps the simplest and most widely adopted exploration strategy. As is well known, the e e-greedy algorithm selects exploratory action uniformly at random with probability at each time step. Besides its simplicity, <-greedy exploration has two properties that contribute to its universality:
It is stationary, i.e. its mechanics do not depend on learning progress. Stationarity is important for stability, since an exploration strategy interacting with the agent's learning dynamics results in circular dependencies that can in turn limit exploration progress. In simple terms: bad exploratory decisions can hurt the learned policy which can lead to more bad exploration.
2 It provides full coverage of the space of possible trajectories. All sequences of states, actions and rewards are possible under e-greedy exploration, albeit some with exceedingly small probability. This guarantees, at least in principle, that solutions excluded from consideration. Conver- gence results for RL algorithms rely on this sort of guarantee (Singh et al. 2000). This may also explain sophisticated exploration methods' use of e-greedy exploration (Bellemare et al. 2016).
However, c-greedy in its original form also comes with drawbacks. Since it does not explore persistently, the likelihood of deviating more than a few steps off the default trajectory is vanishingly small. This can be thought of as an inductive bias (or "prior") that favors transitions that are likely under the policy being learned (it might be instructive to think of a neighbourhood around the associated stationary distribution). Although this is not necessarily bad, it is not difficult to think of situations in which such an inductive bias may hinder learning. For example, it may be very difficult to move away from a local maximum if doing requires large deviations from the current policy.
The issue above arises in part because e-greedy provides little flexibility to adjust the algorithm's inductive bias to the peculiarities of given problem. By tuning the algorithm's 's only parameter, c, one can make deviations more or less likely, but the nature of such deviations is not modifiable. To see this, note that all sequences of exploratory actions are equally likely under e-greedy, regardless of the specific value used for e. This leads to a coverage of the state space that is largely defined by the current ("greedy") policy and the environment dynamics (see Figure T for an illustration).
In this paper we present an algorithm that retains the beneficial properties of e-greedy while at the same time allowing for more control over the nature of the induced exploratory behavior. In order to achieve this, we propose a small modification to c-greedy: we replace actions with temporally- extended sequences of actions, or options (Sutton, Precup, and Singh 1999). Options then become a mechanism to modulate the inductive bias associated with c-greedy. We discuss how by appropriately defining a set of options one can "align" the exploratory behavior of e-greedy with a given environment or class of environments; we then show how very simple set of domain-agnostic options work surprisingly well across a variety of well known environments.
2 BACKGROUND AND NOTATION
Reinforcement learning can be set within the Markov Decision Process (MDP) formalism (Puterman 1994). An MDP M is defined by the tuple (X' A, P, R, 7), where & E & is state in the state space, a E A is an action in the action space, P(x' x,, a) is the probability of transitioning from state x to state x' after taking action a, R: X x A RR is the reward function and 7 E [0, 1) is the discount factor. Let P (AA) denote the space of probability distributions over actions; then, a policy given state. We will denote by Te = 1. the policy which takes action deterministically in every state.
:: X' + P (A) assigns some probability to each action conditioned
The agent attempts to learn a policy π that maximizes the expected return or value in a given state,
DO Σ
V EA QT A) E,r
R( Ar) Xo -
where T Q" are the value and action-value functions of म. The greedy policy for action-value function Q takes the action arg max,e,4 Q(z, Yz E X. In this work we primarily rely upon methods based on the Q-learning algorithm (Watkins and Dayan 1992), which attempts to learn the
2

---

Published as a conference paper at ICLR 2021
(6) c-Gredy
(b) Temporaly-xxienaa --reedy
0.11
0.5
0.0.9
c=1.0
c-0.1
C-0
-09
Figure I: Average (estimated) first-visit times, comparing e-greedy policies (a) without and with (b) temporal persistence, in an open gridworld (blue represents fewer steps to and red states rarely or never seen). Greedy policy moves directly down from the top center. See Appendix for details.
optimal policy by approximating the Bellman optimality equation:
Q(x, a) R(x, a) + x-m(()
max Q(X) a'EA
In practice, the state space X' is often too large to represent exactly and thus have Qo a) se Q a) for a function approximator parameterized by 6. We will generally use some form of differentiable function approximator Qo, whether it be linear in fixed set of basis functions, or artificial neural network. We update parameters 0 to minimize a squared or Huber loss between the with the right-hand side held fixed (Mnih et 2015).
left- and right-hand sides of equation I
In addition to function approximation, it has been argued that in order to scale to large problems, RL agents should be able to reason at multiple temporal scales (Dayan and Hinton 1993 Parr and Russell 1998 Sutton, Precup, and Singh, 1999. Dietterich] 2000). One way to model temporal abstraction via options (Sutton, Precup, and Singh 1999p. L.c. (emporally-extender courses of action. In the most general formulation, an option can depend on the entire history between its initiation time step t and the current time step k. her+ k =\t 10.00=/--1...0-k----00 (Iw, Tw, Bw), where In C X' is the set of states where
Let H. be the space of all possible
histories; semi-Markov option is tuple the option can initiated, Tu H- (AA) is history-dependent policy, and 8. H + [0, 1] gives the probability that the option terminates after observing some history (Sutton. Precup, and Singh 1999). As in this work we will use options for exploration, we will assume that In, X, Vw.
Once option is selected, the agent takes actions T- h)) after having observed history E H and at each step terminates the option with probability (h). It is worth emphasizing that semi-Markov options depend on the history since their initiation, but not before. Also, they usually defined with respect to a statistic of histories E H; for example, by looking at the length of one can define an option that terminates after fixed number of steps.
EXPLORATION IN REINFORCEMENT LEARNING
At its core, RL presents the twin challenges of temporal credit assignment and exploration. The agent must accurately, and efficiently, assign credit to past actions for their role in achieving some long-term return. However, to continue improving the policy, it must also consider behaviours it estimates to be sub-optimal. This leads to the well-known exploration intooraatioo-epllitattiooo trade-off.
Because of its central importance in RL, exploration has been among the most studied topics in the field. In finite state-action spaces, the theoretical limitations of exploration, with respect to sample complexity bounds, are fairly well understood (Azar, Osband, and Munos 2017 Dann, Lattimore| and Brunskill 2017). However, these results are of limited practical use for two reasons. First, they bound sample complexity by the size of the state-action space and horizon, which makes their immediate application in large-scale or continuous state problems difficult. Second, these algorithms tend be designed based on worst-case scenarios, and can be inefficient on problems of actual interest. Bayesian RL methods for exploration address the explore-exploit problem integrated with the itself (Kolter and Ng 2009). Generally such methods strongly depend
estimation of the upon the quality of their priors, which can be difficult to set appropriately. Thompson sampling methods [Thompson] 1933 Osband, Russo, and Van Roy 2013) estimate the posterior distribution of value-functions. and act greedily according to sample from this distribution. As with other methods which integrate learning and exploration into a single estimation problem, this creates non-stationary, but temporally persistent, exploration. Other examples of this type of exploration strategy include randomized prior functions (Osband, Aslanides, and Cassirer, 2018), uncertainty Bellman equations (O' Donoghuu al. 2018), NoisyNets (Fortunato et al. 2017 and successor uncertainties (Janz
3

---

Published as a conference paper at ICLR 2021
et al. 2019). Although quite different from each other, they share key commonalities: non-stationary targets, temporal persistence, and exploration based on the space of value functions.
At the other end of the spectrum, there have recently been successful attempts to design algorithms with specific problems of interest in mind. Certain games from the Atari-57 benchmark (c.g. MON- TEZUMA'S S REVENGE, PITFALL!, PRIVATE EYE) have been identified as 'hard exploration games' (Bellemare et al.) 2016), attracting the attention of the research community, leading to significant progress in terms of performance (Ecoffet et al. 2019 Burda et al., 2018). On the downside, these results have been usually achieved by algorithms with little or no theoretical grounding. adopting specialized inductive biases, such as density modeling of images (Bellemare et al., 2016 Ostrovski
et al., (017), error-seeking intrinsic rewards (Pathak et al. 2017 Badia et al. 2020a). or perfect deterministic peward-modelss (Ecoffet et al. 2019).
Generally, such algorithms are evaluated only on the very domains they are designed to perform well on, raising questions of generality. Recent empirical analysis showed that some of these methods perform similarly to each other on hard exploration problems and significantly under-perform greedy otherwise (Ali Taīga et al., 2020). One explanation is that complex algorithms tend to be more brittle and harder to reproduce, leading to lower than expected performance in follow-on work. However, these results also suggest that much of the recent work on exploration is over- weer-fitting to a small number of domains.
TEMPORALLY-EXTENDD EXPLORATION
There are many ways to think about exploration: curiosity, experimentation, reducing uncertainty, etc. Consider viewing exploration
search for undiscovered rewards shorter paths to known rewards. In this context, the behaviour of e-greedy appears shortsighted because the probability of moving consistently in any direction decays exponentially with the number of exploratory steps. In Figure Th we visualize the behaviour of uniform e-greedy in an open gridworld, where the agent starts at the center-top and the greedy policy moves straight down. Observe that for S 0.5 the agent is exceedingly unlikely to reach states outside a narrow band around the greedy policy. Even the purely exploratory policy (c 1.0) requires a large number of steps to visit the bottom corners of the grid. This is because, under the uniform policy, the probability of moving consistently in any direction decays exponentially (see Figure ( By contrast, method that explores persistently with a directed policy leads to more efficient exploration of the space at various values of (Figure [p).
The importance of remporally-extendee exploration has been previously highlighted (Osband et al., 2016), and in general, count-based (Bellemare et al., (2166) or curiosity-based (Burda et al.) 2018) ex- ploration methods are inherently semporally-extende
due to integrating cxploration and exploitation into the greedy policy. Here our goal is to leverage the benefits of lemporally-extendee exploration without modifying the greedy policy.
There has been wealth of research on learning options (McGovern and Barto 2001 Stolle le and
Precup 2002 Şimşek and Barto 2004 [Bacon, Harb, and Precup Har Harutyunyan et al. 2019). and specifically for exploration Machado, Bellemare, and Bowling 2017 7 Machado et al. 201 8b) Jinnai et al. 2019 22200 Hansen et al. 2020). These methods use options for exploration and to augment the spacce adding learned options to actions available at states where they can be
initiated.
In the remainder of this work, we argue for temporally-extended exploration, using options encode a set of inductive biases to improve cumple-efficiency This fundamental message is found throughout the existing work on exploration with options, but producing algorithms that are empirically effective on large environments remains a challenge for the field. In the next section, we discuss in more detail how the options' policy mu and termination 3 can used to induce different types of exploration.
c-Greedy A temporally-extender c-greedy exploration strategy depends on choosing an exploration probability e, a set of options 12, and a sampling distribution p with support Ω. On each step the agent follows the current policy for one step with probability 1 - e, with probability samples an option w ~ p(?) and follows it until termination. Standard e- c-greedy has three desirable properties that help explain its wide adoption in practice: it is simple, stationary, and promotes full coverage of the state-action space in the limit (guaranteeing convergence to the optimal policy under the right conditions). We now discuss to what extent the proposed algorithm retains
Temporally-Extent
4

---

Published as a conference paper at ICLR 2021
these properties. Although somewhat subjective, it seems fair to call temporally-extendee e-greedy simple method. It is also stationary when the set of options Q2 and distribution p are fixed, for in this case its mechanics are not influenced by the collected data. Finally, it is easy to define conditions under which lemporally-extendded <-greedy covers the entire state-action space, as we discuss next.
Obviously, the exploratory behavior of temporally-extender e-greedy will depend on the set of options Ω. Ideally we want all actions a E AA to have a nonzero probability of being executed in all states X' regardless of the greedy policy π. This is clearly not the case for all sets Q. In fact, this may not be the case even if for all (2c, a) E X' x A there is an option w E S such that Tu Tw (al/tx) > 0, where ha represents all histories ending in x. To see why, note that, given a fixed Q and e > 0. it may be impossible for an option w E Q to be "active" in state 2 (that is, either start at or visit r). For example, if all options Q terminate after a fixed number of steps that a multiple of k temporally-extendee
1 will only visit states of an unidirectional chain whose indices are also multiples of k. Perhaps even subtler is that, even if all options can be active at state æ, the histories ha E H associated with given action a may themselves not be realizable under the combination of S2 and the current π.
e-greedy with
It is clear then that the coverage ability of temporally-extendeer e-greedy depends the interaction between π. 92 e, and the dynamics P(I|z, a) of the MDP. One way to reason about this is to consider that, once fixed, these elements induce stochastic process which in turn gives rise to a well-defined distribution over the space of histories H.
Property 1 (Full coverage). Let M be the space of all MDPs with common state-action spaces X' A. and Q a set of options defined over this state-action space. Then, Q has full coverage for M if VM E M, c > O, and the semi-Markon policy == (1 - c)x + cTw, where w is random variable uniform over f2, visits every state-action pair with non-zero probability. Note that μ itself random variable and not an average policy.
We can then look for simple conditions that would lead to having Property [ For example, if the options' policies only depend on the last state of the history, Th (-Ihar) = T [((2) (i.e. they are Markov, rather than semi-Markov policies), we can get the desired coverage by having (a|()) >> 0 for all x E X and all a E A. The coverage of X x A also trivially follows from having all primitive actions E A as part of Ω. Note that if the primitive actions are the only elements of S we recover standard e-greedy, and thus coverage of X x A. Of course, in these and similar cases, temporally-extee -extende e-greedy allows for convergence to the optimal policy under the same conditions as its precursor.
This view of temporally-cxter extended e-greedy, as inducing a stochastic process, also helps us to under- stand its differences with respect its standard counterpart. Since the induced stochastic process defines a distribution over histories we can also talk about distributions over sequences of actions. With standard e-greedy, every sequence of l exploratory actions has probability of occurrence of exactly (e/LA))*, where |A| is the size of the action space. By changing e one can uniformly change the probabilities of all length-k: sequences of actions, but no sequence can be favored over the others. Temporally- remporally-extended extended e-greedy provides this flexibility through the definition of Q; specifically, by defining the appropriate set of options one can control the temporal correlation between actions. This makes it possible to control how quickly the algorithm converges, as we discuss next.
Efficient exploration For sample-effccienc we want to cover the state-action space quickly.
Definition 1. The cover time of an RL algorithm is the number of steps needed to visit all state-action pairs at least once with probability 0.5 starting from the initial state distribution.
Even- Even-Daraae and Mansour (2003) show that the sample efficiency of Q-learning can be bounded in terms of the cover time of the exploratory policy used. Liu and Brunskill 2018) provide an upper bound for the cover time of a random exploratory policy based on properties of the MDP. Putting these results together, we have the characterization of class of MDPs for which Q-lcarning plus e-greedy exploration is sample efficient (that is, it converges in polynomial time).
Normally, the efficiency of e-greedy Q-learning is completely determined by the MDP: given an MDP, either the algorithm is efficient or it is not. We now discuss how by replacing e-greedy exploration with its cimporally-extendee
counterpart we can have efficient exploration on much broader class of MDPs. To understand why this is so, note that the definition of the set of options Q can be seen as the definition of new MDP in which histories play the role of states and options play the role of actions.
5

---

Published as a conference paper at ICLR 2021
(a) Chain: Q-Learning
(b) Atari: R2D2
6g
41
0.00
Capoud Ma
2
Zetn
Uniform
Exponential
0910
0200
0300
0.31
L1c
135
150
175
2.0
235
250
275
310
uST
Figure 2: (a) Modified chain MDP, action do moves right, d1 terminates with specified reward. Rewards follow pattern of zeros followed by single reward n, etc. Evaluation of performance under various duration distributions and hyper-paramen parammareettrrs on the chain. (b) Duration distribution similarly compared for R2D2-based deep RL agent in Atari.
Hence, by appropriately defining Ω2 we can have MDP in which random exploration is efficient.
We now formalize this notion by making explicit properties of Z that lead to efficient exploration:
Assumption 1. For an MDP M and set of options S2 there exists Raxx E N such that Vx, y E X, Ei leading to [t, Fg x, 24 = yl S 7mmax
Theorem 1. For any irreducible MDP, let be a set of options satisfying Assumption with Amaz < @[[x)]AA)) Then, comporally-extendee e-greedy with sampling distribution p satisfying p(w) S {((I))))), Vi E Ω has polynomial sample complexity.
In many cases is easy to define options that satisfy Assumption I as we will discuss shortly. But even when this is not the case, one can learn options deliberately designed to have this property. For example, Jinnai et al.] (2019) 2020) learn point-options (transitioning from one state to one other state) that explicitly minimize cover time. The approach proposed by Machado et al. (2017) 2018b) also leads to options with a small cover time, Alternatively, Whitney et al. (2020) learn an embedding of action sequences such that sequences with similar representations also have similar future state distributions. They observe that sampling uniformly in this abstracted action space yields action sequences whose future state distribution is nearly uniform interpret such an embedding, coupled with a corresponding decoder back into primitive actions, as an appealing approach learning open-loop options for temporally-extender e-greedy exploration.
reachable states. We can
Next, we propose a concrete form of temporally-extended e-greedy which requires neither learning Ω specific domain knowledge. These options encode commonly held inductive bias: actions have (largely) consistent effects throughout the state-space.
ez-Greedy We begin with the options We (X, Tas 3), where no (h) = 1. and 3(h) for all h E H. and consider a single modification, temporal persistence. Let Wan = (X, Ta, Bhh) be the option which takes action for steps and then terminates. Our proposed algorithm. to let Ω J 22 and p to be uniform over actions with durations distributed according to some distribution 2. Intuitively, we are proposing the set of semi- Memi-Markov options made up of all "action-repeat" policies for all combinations of actions and repeat durations, with a parametric sampling distribution on durations.
mn) [
This exploration algorithm described by two parameters, e dictating when to explore, and z dictating the degree of persistence. Notice that when z puts all mass n = 1, this is standard e-greedy; more generally this combination of distributions forms a composite distribution with support [0, oo), which is to say that with some probability the agent explores for = 0 steps, corresponding to following its usual policy, and for all other n > 0 the agent explores following an action-repeat policy.
A natural question arises: what distribution over durations should we use? To help motivate this question, and to help understand the desirable characteristics, consider Figure 2 which shows a modified chain MDP with two actions. Taking the 'down' action immediately terminates with the specified reward, whereas taking the 'right' action progresses to the next state in the chain. Similar to other exploration thaen-like MDPs, e-greedy performs poorly here because the agent must move consistently in one direction for an arbitrary number of steps (determined by the discount) to reach the optimal reward. Instead, we consider the effects of three classes of duration distribution: exponential

---

Published as a conference paper at ICLR 2021
(a) DeepSea
<-Greedy
cz-Greedy
(c) Mountain
G-Greeyy
ez-Greedy
Sreel pn
GridWorld
GGreedyy
Greedy
(d) Cart Pole (sparse)
e-Greedy
e2-Greedy
2003
Figure 3: Comparing e-greedy with ez-greedy on four small-scale domains requiring exploration. (a) DeepSea is a tabular problem in which only one action-sequence receives positive reward, and uniform exploration is exponentially inefficient, (b) GridWorld is a four-action gridworld with a single reward, (c) MountainCar is the sparse reward (only goal) version of the classic RL domain, and (d) CartPole swingup-spa sparse only gives non-zero reward when the pole is perfectly balanced and the cart near-center. For each, show performance comparing e-greedy with ez-greedy (left), as well as average first-visit times over states for both algorithms during pure exploration (e = 1). In all first-visit plots, color levels are linearly scaled, except for DeepSea which we use log scale.
(2(n) oc >"=1), uniform (=(n) Lnns/N /N), and zeta (z(n) oc "). Figure 2p shows the average return achieved by these distributions as their hyper-parameter are varied. This problem illustrates that, without prior knowledge of the MDP, is important to support long durations, such as with heavy-tailed distribution (e.g. the zeta distribution).
Why not simply allow uniform over an extremely large support? Doing so would effectively force 'pure' exploration without any exploitation, because this form of ballistic exploration would simply continue exploring indefinitely. Indeed, we can see in Figure 2 that the uniform distribution leads to poor performance (the same is true for the zeta distribution as μ 1, which also leads to ballistic exploration). On the other hand, short durations lead to frequent switching and vanishingly small probabilities of reaching larger rewards at all. This trade-off leads to the existence of an optimal value of j for the zeta distribution that can vary by domain (Humphries et al. 2010), and is illustrated by the inverted U-curve in Figure 2 class of ecological models for animal foraging known Lévy flights follow a similar pattern of choosing a direction uniformly at random, and following that direction for duration sampled from a heavy-tailed distribution. Under certain conditions, this has been shown to be an optimal foraging strategy, a form of exploration for food source of unpredictable location Viswanathan al.) 1996 1999). particular, a value of μ 2 has consistently been found as sweep. Thus, in the remainder of this work we will use the zeta distribution, with μ = 2 unless otherwise specified, and call this combination of chance to explore and reta-distributed durations, 62 Greeddy exploration
the best for modeling animal foraging, as well as performing best in our
5 EXPERIMENTAL RESULTS
We have emphasized the importance of simplicity, generality (via convergence guarantees), and stationarity of exploration strategies. We proposed a simple temporally-extent e-greedy algorithm, ez-greedy, and saw that heavy-tailed duration distribution yielded the best trade-off between temporal persistence and sample efficiency. In this section, we present empirical results on tabular, linear, and deep RI settings, pursuing objectives: The first is demonstrate the generality of our method in applying it across domains as well as across multiple value- based reinforcement learning algorithms (Q-learning, SARSA, Rainbow, R2D2). Second, we make the point that exploration comes at cost, and that ez-greedy improves exploration with significantly less loss in efficiency on dense-reward domains compared with existing exploration algorithms.
Small-Scale: Tabular & Linear RL We consider four small-scale environments (DeepSea, Grid- World, MountainCar, CartPole swingup-sparse), configured to challenging sparse-reward explo-
Pronounce 'easy-greedy'.

---

Published as a conference paper at ICLR 2021
(a) Rainbow
(b) R2D2
Median Normallzed
Human Gap
Median Normalized
Gap
39
Raiboww
2.4
0.35
Humoo norriieed
Groedy
2.8
Rainbonr CCTS
0.20
Humon
R202
H0D
333
753
200
100
100
1/3
1.3
25
Enwrormment framns Imillorr
Envronment framos (mdllio))
Enaionmment formes
Ensrroemmntt fromes
Figure 4: Results on the Atari-57 benchmark for (a) Rainhow-based and (b) R2D22-based agents.
ration problems. Full details for each are given in the Appendix. DeepSea and GridWorld use a tabular representation while MountainCar and CartPole use linear function approximation order 5 and 7 Fourier basis respectively (Konidaris, Osentoski, and Thomas 2011).
In Figure 3 we present results comparing e-greedy and ez-greedy these four domains. Unless otherwise specified. the spper-parameters and training settings for these two methods are identical. For each domain we show (i) learning curves showing average return against training episode (ii) average first-visit times on states during pure (c = 1.0) exploration for 6-greedy and (iii) e2-greedy. The results show that ez-greedy provides significantly improved performance these domains, and the first-visit times indicate significantly better state-space coverage compared to c-greedy.
Atari-57: Deep RL Motivated by the results in tabular and linear settings, we now turn to deep RL and evaluate performance on 57 Atari 2600 games in the Arcade Learning Environment (ALE) (Bellemare et al. 2013). To demonstrate the generality of the approach, we apply ez-greedy two state-of-ther -ftt--r- deep RL agents, Rainbow (Hessel et al. 2018) and R2D2 (Kapturowski et al., 2019). We compare with baseline performance as well as the performance of recent intrinsic motivation- based exploration algorithm: -TS--ased pseudo-counts (Bellemare et al., 2016) in Rainbow and RND (Burda et al., 2018) in R2D2, each tuned for performance comparable with published results. Finally, in R2D2 experiments we also compare with Bootstrapped DQN version of R2D2 (Osband) (et al.) 2016). providing an exploration baseline without intrinsic rewards. We include pseudo-code and hyper-parameters in the Appendix, though the implementation of ez-greedy in each case is trivial. Syper-parameters are mostly identical to previous work, and we fix μr = 2 for results in this section. Our findings (see Figure 4 show that ez-greedy improves performance on the hard exploration tasks with little to no loss in performance on the rest of the suite. By comparison, we observe that the intrinsic motivation methods often (although not always) outperform es-greedy on the hard exploration tasks, but at a significant loss of performance on the rest of the benchmark.
The results in Figure 4 show median numan-normalizer score over the 57 games and the human-gap, measuring how much the agent under- under-performs humans on average (see Appendix D for details). We consider the median to indicate overall performance on the suite and the human-gaa to illustrate gains on the hard exploration games where agents still under-perfone
relative to humans, with full per-game and mean performance given in the Appendix. Table I gives the final performance of each of the agents in terms of these summary statistics. Figure 5 shows representative examples of per-game performance for the R2D2- based agents. These per-game results make strong point, that even on the hard exploration games the inductive biases of intrinsic motivation methods may be poorly aligned, and that outside a small number of games these methods significantly hurt performance, whereas our proposed method improves exploration while avoiding this significant loss elsewhere.
To demonstrate that the effectiveness of our method does not crucially depend on evaluation on deterministic domains, in Appendix [ we additionally show similar comparison of the Rainbow- based agents on a stochastic variant of the Atari-57 benchmark using 'sticky actions' (Machado et al.. 2018a). The results qualitatively similar: while all agent variants do somewhat worse on the stochastic compared to the deterministic case, ex-greedy improves over the baseline and e-greedy on the hardest exploration domains while not substantially affecting performance in others, and coming performance as well as human-gap (TTble
out on top in terms of mean and median
Figures
10 21
TTo compare with previous work DeepSea, we report expected time leam versus problem scale.
8

---

Published as a conference paper at ICLR 2021
yoste
TEAC teddos
levb
430
56
21
18
Figure 5: Results on the Atari-57 selected games showing R2D2-based agents.
Algorithm (@3)
Median
Mean
H-Gap
||
Algorithm ( (@200M)
Median
Mean
H-Gap
R2D2
14.31
39.55
0.102
Rainbow
2.09
8.82
0.139
R2D2+RND
9.40
42.17
0.151
Rainbow+e-Greedy
2.26
9.17
0.143
R2D2+Bootstrap
15.75
37.69
0.096
Rainbow+CTS
1.72
6.77
0.150
R2D22tz--reedy
16.64
40.16
0.077
Rainhow+c2-Greedy
2.35
9.34
0.130
Table 1: Atari-57 final performance. H-Gap denotes the human-gap, defined fully in the Appendix.
DISCUSSION AND CONCLUSIONS
We have proposed temporally-extended c-greedy, a form of random exploration performed by sam- pling an option and following it until termination, with simple instantiation which we call cz-greedy. We showed, across domains and algorithms spanning tabular, linear and deep reinforcement learning that ez-greedy improves exploration and performance in sparse-reward environments with minimal loss in performance on easier, dense-reward environments. Further, we showed that compared with other exploration methods (pseudo-counts, RND, Bootstrap), e2-greedy has comparable performance averaged over the hard-exploration games in Atari, but without the significant loss in performance on the remaining games. Although action-repeats have been a part of deep RL algorithms since DQN, and have been considered as a type of option (Schoknecht and Riedmiller 2202 2003); Braylan et al. 2015 Lakshminarayanaa Sharma, and Ravindran [017 Sharma, Lakshminarayanan and Ravindran 2017), their use for exploration with sampled durations does not appear to have been studied before.
Generality and Limitations. Both e- and ez-greedy are guaranteed to converge in the finite state- action case, but they place probability mass over exploratory trajectories very differently, thus encoding different inductive biases. We expect there to be environments where ex-greedy significantly under-performs 6-greedy. Indeed, these are easy to imagine: DeepSea with action effects randomized per-state (see Appendix Figure 14), GridWorld with many obstacles that immediately end the episode ('mines"), ), maze changing direction every few steps, etc. More generally, the limitations of ez-greedy are: (i) Actions may not homogeneously (over states) correspond to a natural notion of shortest-pan --ate directions in the MDP. (ii) Action spaces may be biased (e.g. many actions have the same effect), so uniform action sampling may produce undesirable biased drift through the MDP. (iii) Obstacles and dynamics in the MDP can cause long exploratory trajectories waste time (e.g. running into a wall for thousands of steps), or produce uninformative transitions (e.g. end of episode, death). In Appendix F we report on series of experiments investigating ez-Greddy's sensitivities such modifications of the Gridworld domain and find that its performance degrades gracefully overall.
These limitations are precisely where we believe future work is best motivated. How can an agent learn stationary, problem-specific notions of direction, and explore in that space efficiently? How to avoid wasteful long trajectories, perhaps by truncating early? This form of exploration bears similarity to the Lévy-flights model of foraging, where an animal will abruptly end foraging as soon as food is within sight. Could we use discrepancies in value along trajectory to similarly truncate exploration early? Recent work around learning action representations appear to be promising directions (Tennenholtz and Mannor, 2019: Chandak al., 2019).
REFERENCES
Ali Taiga, A.; Fedus, W.; Machado, M. C.; Courville, A.; and Bellemare, M. G. 2020. On Bonus Based Exploration Methods In The Arcade Learning Environment. In International Conference Learning Representations.
Asmuth, J.; Li, L.; Littman, M. L.; Nouri, A.; and Wingate, D. 2009. A Bayesian sampling approach
to exploration in reinforcement learning. In Conference on Uncertainty in Artificial Intelligence,

---

Published as a conference paper at ICLR 2021
19-26. AUAI Press.
Azar, M. G.; Osband, I.; and Munos, R. 2017. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, 263-272. JMLR. org.
Bacon, P.-..; Harb, J.; and Precup, D. 2017. The option-critic architecture. In AAAI Conference on Artificial Intelligence.
Badia, A. P. Piot, B.; Kapturowski, S.; Sprechmann, P.; Vitvitskyi, A.; Guo, D.; and Blundell, C. 2020a. Agent57: Outperforming the atari human benchmark. arXiv:2003.13350
Badia, A. P.; Sprechmann, P.; Vitvitskyi, A.; Guo, D.; Piot, B.; Kapturowski, S.; Tieleman, O.:
Arjovsky, M.; Pritzel, A.; Bolt, A.; and Blundell, C. 2020b. Never Give Up: Learning Directed Exploration Strategies. International Conference on Learning Representations.
Barto, A. G.; Sutton, R. S.; and Anderson, C. W. 1983. Neuronlike adaptive elements that can solve difficult learning control problems. IEEE transactions systems, man, and cybernetics (5): 834-846.
Bellemare, M.; Srinivasan, S.; Ostrovski. G.; Schaul, T.; Saxton, D.; and Munos, R. 2016. Unifying count-based exploration and intrinsic motivation. Advances in Neural Information Processing Systems, 1471-1479
Bellemare, M. G.; Naddaf, Y.; Veness, J.; and Bowling, M. 2013. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research 47: 253-279,
Brafman, R. L; and Tennenholtz, M. 2002. R-max-a general polynomial time algorithm for near- optimal reinforcement learning. Journal of Machine Learning Research 3: 213-231.
Braylan, A.; Hollenbeck, M.; Meyerson, E.; and Mikkkulanenn, R. 2015. Frame skip is a powerful
parameter for learning play atari. In Workshops at AAAI Conference on Artificial Intelligence.
Burda, Y.; Edwards, H.; Storkey, A.; and Klimov, O. 2018. Exploration by random network distillation. 1'Xiv:811011294
Chandak, Y.; Theocharous, G.; Kostas, J.; Jordan, S.; and Thomas, P. 2019. Learning Action
Representations for Reinforcement Learning. In International Conference on Machine Learning, 941-950.
Dann, C.; Lattimore, T:; and Brunskill, E. 2017. Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, 5713-5723.
Dayan, P.; and Hinton, G. E. 1993. Feudal reinforcement learnnnn In Advances in neural information processing systems, 271-278.
Dietterich, T. G. 2000. Hierarchical reinforcement learning with the MAXQ value function decompo- sition. Journal of Artificial Intelligence Research 13: 227-303.
Ecoffet, A.; Huizinga, J.; Lehman, J.; Stanley, K. O.; and Clune, J. 2019. Go-Explore: New Approach for Hard-Exploration Problems. arXiv:
Even-Dar, E.; and Mansour, Y. 2003. Learning rates for Q-learning. Journal of machine learning Research 1-25.
Fortunato, M.; Azar, M. G.; Piot, B.; Menick, J.; Osband, I:; Graves, A.; Mnih, V:; Munos, R.;
Hassabis, D.; Pietquin, O.; et al. 2017. Noisy networks for exploration. arXiv: 1706. 10295.
Hansen, S.; Dabney, W.; Barreto, A.; Warde-Farley, D.; de Wiele, T. V:; and Mnih, V. 2020. Fast Task Inference with Variational Intrinsic Successor Features. In International Conference on Learning Representations.
Harutyunyan, A.; Dabney, W.; Borsa, D.; Heess, N.; Munos, R.; and Precup. 2019. The Termination Critic. In International Conference Artificial Intelligence and Statisties, 2231-2240.
10

---

Published as a conference paper at ICLR 2021
Hessel, M.; Modayil, J.; Van Hasselt, H.;; Schaul, T.; Ostrovski, G.; Dabney, W.; Horgan, D.; Piot, B.; Azar, M.; and Silver, D. 2018. Rainbow: Combining improvements in deep reinforcement learning. In AAAI Conference on Artificial Intelligence.
Humphries, N. E.; Queiroz, N.; Dyer, J. R.; Pade, N. G.; Musyl, M. K.; Schaefer, K. M.; Fuller, D. W.; Brunnschweiler, J. M.; Doyle, T. K.; Houghton. D.; et al. 2010. Environmental context explains Lévy and Brownian movement patterns of marine predators. Nature 465(7301): 1066.
Janz, D.; Hron, J.; Mazur, P:; Hofmann, K.; Hernández- Lobato, J. M.; and Tschiatschek, S. 2019. Successor Uncertainties: exploration and uncertainty in temporal difference learning. In Advances in Neural Information Processing Systems, 4509-4515
Jinnai, Y.; Park, J. W.; Abel, D.; and Konidaris, G. 2019. Discovering options for exploration by minimizing cover time. arXiv: /90:::90300000
Jinnai, Y.; Park, J. W.; Machado, M. C.; and Konidaris, G. 2020. Exploration Reinforcement Learning with Deep Covering Options. In International Conference on Learning Representations.
Kapturowski, S.; Ostrovski, G.; Quan, J.; Munos, R.; and Dabney, W. 2019. Recurrent expe-
rience replay in distributed reinforcement learning. In International Conference on Learning Representations.
Kolter, Z.; and Ng, A. Y. 2009. Near- Bear-Bayesian exploration in polynomial time. In International Conference on Machine Learning, 513-520.
Konidaris, G.; Osentoski, S.; and Thomas, P. 2011. Value function approximation in reinforcement
learning using the Fourier basis. In AAAI conference on artificial intelligence.
Lakshminarayanan, A. S.; Sharma, S.; and Ravindran, B. 2017. Dynamic action repetition for deep reinforcement learning. In AAAI Conference on Artificial Intelligence.
Lazic, N.; Boutilier, C.; Lu, T.; Wong, E.; Roy, B.; Ryu, M.; and Imwalle, G. 2018. Data center cooling using model-predictive control. In Advances in Neural Information Processing Systems, 1823-3
Levine, S.; Finn, C.; Darrell, T.; and Abbeel, P. 2016. End-to-end training of deep visuomotor policies. The Journal of Machine Learning Research 17(1): 1334-1373.
Li, Y.; Wen, Y.; Tao, D.; and Guan, K. 2019. Transforming cooling optimization for green data center via deep reinforcement learning. IEEE Transactions on Cybernetcss.
Liu, Y.; and Brunskill, 2018. When simple exploration is sample efficient: Identifying sufficient conditions for random exploration to yield pac rl algorithms. arXiv:1805.0000
Machado, M. C.; Bellemare, M. G.; and Bowling, M. 2017. A Laplacian Framework for Option Discovery in Reinforcement Learning. In International Conference on Machine Learning. 2295- 2304.
Machado, M. C.; Bellemare, M. G.; Talvitie, E.; Veness, J.; Hausknecht, M.; and Bowling, M. 2018a. Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research 61: 523-562.
Machado, M. C.; Rosenbaum, C.; Guo, X.; Liu, M.; Tesauro, G.; and Campbell, M. 2018b. Eigenop- tion Discovery through the Deep Successor Representation. In International Conference on Learning Representations.
McGovern, A.; and Barto, A. G. 2001. Automatic discovery of subgoals in reinforcement learning using diverse density. In International Conference on Machine Learning.
Mnih, V.; Kavukcuoglu, K.; Silver, D.; Rusu, A. A.; Veness, J.; Bellemare, M. G.; Graves, A.; Riedmiller, M.; Fidjeland, A. K.; Ostrovski, G.; al. 2015. Human-level control through deep reinforcement learning. Nature 518(7540): 529-533.
O' DDonoghue, B.; Osband, I.; Munos, R.; and Mnih, V. 2018. The uncertainty bellman equation and exploration. In International Conference Machine Learning, 3836-3845.

---

Published as a conference paper at ICLR 2021
Osband, 1.; Aslanides, J.; and Cassirer, A. 2018. Randomized prior functions for deep reinforcement learning. Advances in Neural Information Processing Systems, 8617-8629.
Osband, I,; Blundell, C.; Pritzel, A.; and Van Roy, B. 2016. Deep exploration via bootstrapped DQN. In Advances neural information processing systems, 4026-4034
Osband, I.; Russo, D.; and Van Roy, B. 2013. (More) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems, 3003-3011.
Ostrovski, G.; Bellemare, M. G.; van den Oord, A.; and Munos, R. 2017. Count-based exploration with neural density models. International Conference on Machine Learning, 2721-2730.
Parr, R.; and Russell, S. J. 1998. Reinforcement learning with hierarchies of machines. In Advances in neural information processing systems, 1043-1049.
Pathak, D.: Agrawal, P:; Efros, A. A.; and Darrell, T. 2017. Curiosity-driven exploration by self-supervised prediction. In IEEE Conference on Computer Vision and Pattern Recognition Workshops, 16-17.
Peters, J.; Mulling, K.; and Altun, Y. 2010. Relative entropy policy search. AAAI Conference on Artificial Intelligence.
Puterman, M. L. 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc.
Schoknecht, R.; and Riedmiller, M. 2002. Speeding-up reinforcement learning with multi-step actions. In International Conference on Artificial Neural Networks, 813-818. Springer.
Schoknecht, R.; and Riedmiller, M. 2003. Reinforcement learning on explicitly specified time scales.
Neural Computing & Applications 12(2): 61-80.
Sharma, S.; Lakshminarayanann A. S.; and Ravindran, B. 2017. Learning repeat: Fine grained action repetition for deep reinforcement learning. arXiv: 702.06054.
Şimşek, Ö.; and Barto, A. G. 2004. Using relative novelty identify useful temporal abstractions in reinforcement learning. In International Conference on Machine Learning. 95.
Singh, S.; Jaakkola, T.; Littman, M. L.; and Szepesvári, C. 2000. Convergence results for single-step on-policy reinforcement-teariing algorithms. Machine learning 38(3): 287-308.
Stolle, M.; and Precup, D. 2002. Learning options in reinforcement learning. In International Symposium on abstraction, reformulation, and approximation, 212-223. Springer.
Sutton, R. S.; and Barto, A. G. 2018. Reinforcement learning: An introduction. MIT press.
Sutton, R. S.; Precup, D.; and Singh, S. 1999. Between MDPs and semi-MDPs: framework for
temporal abstraction in reinforcement learning. Artificial intelligence 12((12): 181-211.
Tassa, Y.; Doron, Y.; Muldal, A.; Erez, T.: Li. Y.; Casas, D. L.; Budden, D.; Abdolmaleki, A.;
Merel, J.; Lefraneq, A.; et al. 2018. Deepmind control suite. arXiv:1801 1801.0069..
Tennenholtz, G.; and Mannor, S. 2019. The Natural Language of Actions. In International Conference on Machine Learning. 6196-6205.
Thompson, W. R. 1933. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika 25(3/4): 285-294.
Van Seijen, H.; Van Hasselt. H.; Whiteson, S.; and Wiering, M. 2009. A theoretical and empiri- cal analysis of Expected Sarsa. In IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, 177-184. IEEE.
Viswanathan, M.; Afanasyev, V.; Buldyrev, S.; Murphy, E.; Prince, P.; and Stanley, H. E. 1996. Lévy flight search patterns of wandering albatrosses. Nature 381 381(6581): 413.
12

---

Published as a conference paper at ICLR 2021
Viswanathan, G. M.; Buldyrev, S. V.; Havlin, S.; Da Luz, M.; Raposo, E.; and Stanley, H. E. 1999. Optimizing the success of random searches. Nature 401(6756): 911.
Wang, Z.; Schaul, T.; Hessel, M.; Van Hasselt, H.; Lanctot, M.; and De Freitas, N. 2015. Dueling network architectures for deep reinforcement learning. vrXiv:/511006500
Watkins, J.; and Dayan, 1992. Q-learning. Machine learning 8(3-4): 279-292.
Whitney, W.; Agarwal, R.; Cho, K.; and Gupta, A. 2020. Dynamics- Embeddings. In
International Conference on Learning Representations. Corum?id-Ba BJg
13

---

Published as a conference paper at ICLR 2021
APPENDICES
A COVER TIME ANALYSIS
Assumption 1. For MDP M and set of options Q, there exists Texa E N such that Vz, y E X, Eu E leading to E.,, To = 2, 2t = yl I Omax-
Theorem 1. For any irreducible MDP, let Ω be a set of options satisfying Assumption I with Amaz < AI))) Then, temporally-extern extended e-greedy with sampling distribution p satisfying
p(w) I (I))) Ve E ft has polynomial sample complexity.
Proof. Liu and Brunskill (2018) establish PAC RL bound, leading polynomial sample complexity, for random exploration using primitive actions when min, ø(2] and π are polynomial in states and actions, with steady-state distribution & and Cheeger constant h. However, their result does not require actions to be primitive, and here we show how temporally-extended actions the form of exploratory options can be used for similar result.
We begin by bounding the steady-state probability for any state x E X, where zig == arg max, d(x) and Rlmax the maximum expected path distance between two states. We can understand this as bounding the steady-state probability of x by the product of (1) the maximal steady-state probability
states, (2) the probability of choosing option from To that reaches Let be any option satisfying Assumption I for starting in state 2y and reaching x,
((*I)))
x(x) 2 o(xo) x p(w),
min, ((x)
6(5o)
Next, we can similarly bound the Cheeger constant. Recall from (Liu and Brunskill, 2018) that F(8U)
info (in(F(U).F(T)) where U denotes the set of states not in U,
F(u. (())((u F(BU)=
E F(u,v), F(U) = Σ o(u).
WEU,EEU
uEt
Let U" = =x0), then, the Cheeger constant can be bounded by,
F(AU)
h inf
min(F(U), F(U)}'
F(OU")
min [in()( F(U'))
E Ex 6(FO) P(zo, x)
6(10)
Σ 2)
$400
2 p(w),
s (((
EXAMPLE: CHAIN MDP
Theorem clarifies the conditions under which temporall--extender e-greedy is efficient. Given an MDP, this will depend on two factors: the options and the sampling distribution. To illustrate this point, use the well known Chain MDP, for which ez zz-Gredyy satisfies Assumption[] Specifically, the requirement on is satisfied by the zeta distribution distribution (exponential decay). This implies that e2 ez-greedy on the Chain MDP will have polynomial sample complexity when is zeta distributed, but not when exponentially distributed.
(a(n)
((p) but not by the geometric
14

---

Published as a conference paper at ICLR 2021
(a) Deep Sea
(b) Grid World
(c) Mountain Car
(d) Pole
(e) Atari-57
Fool
Carvelocity ER
Car (o)
Figure Environments used this work: (a) DeepSea, (b) GridWorld, (c) MountainCar, (d) CartPole, (e) Atari-57.
We can see this by observing that in a Chain MDP of size any state can be reached from the starting state within at most N steps, yielding Amaz I |.|]. The sampling distribution p is uniform over actions meaning that p(w) 2 (fmmaz)//44 Finally, we consider the specific form of the duration distribution When given by zeta distribution, =(n) -M "t/nn///C///p /C(s), have
1 p(w)
[AI
z(nmaax)
(AIŞ(u)
Remax
AA Almmma S(1),
S |
thus satisfying our assumption. On the other hand, if we let the duration distribution be geometric, =(n) X(1 >)=-1, we have
A
S
p(w)
(Rmaaw)
|AA]
X(1
2)n-I:
1
Amaz
141
1- x
12111
S
|A|
A
As 1)(1-A) 1 and Amaz is only bounded by the number of states, this results in an upper bound that is exponential in the number of states and therefore does not satisfy the assumptions.
B DOMAIN SPECIFICATIONS
Parameterized by problem size N, this envi- ronment can be viewed the lower triangle of N N gridworld with two actions: "down-left" and "down-righh" which move diagonally down either left or right. There is single goal state in the far bottom-right corner, which can only be reached through a single sequunnee The goal reward is 1.0, and there is per-step reward of -0.01 /N. Finally, all episodes end after exactly N steps, once the agent reaches the bottom. Therefore, the maximum possible undiscounted return is 0.99. example with N 20 is shown in Figure 6p. Average first- tast-p times shown for problem size of N = 20 in Figure 3h, and unlike other plots are logarithmically scaled, log(EE [fpt] + 1) with contour levels in the range [0, 16).
DeepSea (Osband, Aslanides, and Cassirer 2018)
In this work we use the deterministic variant of DeepSea; however, the standard stochastic version randomizes the action effeets every state. That is, "down-left" may correspond to action index 0 in one state and in another, and these assignments are performed randomly for each training run (consistently across episodes). We briefly mention this variant in conclusions
example in
15

---

Published as a conference paper at ICLR 2021
which our proposed method should be expected to perform poorly. Indeed, in Figure 14 show that such an adversarial modification reduces ez-greedy's performance back to that of e-greedy.
For experiments, used Q-learning with tabular function approximator, learning rate 1.0, and = LO + 1) for problem size N. Experiment results are averages over 30 random seeds.
Grid Shown in Figure 6p, this is an open single-roon gridworld with four actions ("up", "down". "left", and "right"), and single non-zero reward the goal state. The initial state is in the top center of the grid (offset from the wall by one row), and the goal state is diagonally across from it the other end of the room. Notice that if the goal were the same row or column, as well if were placed directly next to wall, this could be argued to advantage an action-repea, exploration method. Instead, the goal location was chosen to be harder for ez-greedy to find (offset from wall, far from and not in same row/column as start state).
For experiments, we used Q-learning with tabular function approximator, learning rate a = 0.1, 0.1, and maximum episode length 1000. Experiment results averages over 30 random seeds.
Figure D shows average first- pirs-ppssage times on a similar gridworld, but with fixed greedy policy which takes the "down" action deterministically.
MountainCar (Sutton and Barto 2018) This environment models an under-poweree car stuck in the valley between two hills. The agent must build momentum in order to reach the top of one hill and obtain the goal reward. In this version of the domain all rewards are zero except for the goal, which yields reward of 1.0. There are two continuous state variables, corresponding to the agent location, x, and velocity, at
The dewse-reward version of this environment can be solved reliably in less than a dozen episodes using linear function approximation on top of a low-order Fourier basis (Konidaris, Osentoski, and Thomas 2011)
In our experiments using the sparse-reward variant of the environment, we used SARSA(A) with a linear function approximation
top of an order 5 Fourier basis. We used learning rate 0.005, <= 0.05, 7 = 0.99, and À = 0.9. The maximum episode length was set to 5000, Experiment results averages 30 random seeds. A near-optimal policy, given this discount and c, but without confounds due to function- pnnctionaaproximaaiin,, should reach approximately 0.29 episodic discounted return.
CartPole (Barto, Sutton, and Anderson 1983) We use the "swingup sparse" variant as imple- mented in Tassa et al. (2018). In this sparse reward version of the environment, the agent receives zero reward unless [x] 0.25 and cos(O) > 0.995, for the cart location x and pole angle All episodes run for 1000 steps, and observations are 5-dimensional continuous observation.
For experiments, we used SARSA(A) with a linear function approximation on top of an order 7 Fourier basis. We used learning rate 0.0005, 0.01, 7 = 0.99, and À = 0.7. The maximum episode length was 1000. Weights were initialized randomly from mean-zero normal distribution with variance 0.001. Experiment results averages over 30 random seeds.
Atari-57 (Bellemare et al. 2013), is a benchmark suite of 57 Atari 2600 games in the Arcade Learning Environment (ALE). Observations are 210 x 160 color images (following Mnih et al. (2015), many agents these are down-scaled to 84 x 84 and converted to grayscale). For the primary results in this work we use the original ALE version of Atari 2600 games, which does not include subsequently added games (beyond the 57) or features such as "sticky actions".. For results with sticky actions enabled consult Appendix E
Many existing results on Atari-57 report performance of the best agent throughout training, or simply the maximum evaluation performance attained during training. We do not report this metric in the main text because it does not reflect the true learning progress of agents and tends to reflect an over estimate. However, for comparison purposes, "best" performance is included later in the Appendix. In the next section, alongside other agent details, we will give experiments. An example frame from the game PRIVATE EYE is shown in Figure
used in the Atari-57
16

---

Published as a conference paper at ICLR 2021
C AGENT AND ALGORITHM DETAILS
Except for ablation experiments on the duration distribution, all cz-greedy experiments use duration distribution z(n) X n~" with μ 2.0. These durations were capped at S 10000 for all experiments except for the Rainbow-basse agents which were limited to S 100, but in this case no other values were attempted.
PSEUDO-CODE
Algorithm ez-Grredy exploration policy
1:
function EZGREEDY(Q,
2:
n 0
3:
+--
-11
4:
while True do
5:
Observe state if == 0 then
6:
7:
if raadomm) S then
8:
Sample duration: n ~ Sample action: (AA)
9:
10:
Assign action: 4- w
else
12:
Greedy action: a t arg maxa Q a)
13:
else
14:
Assign action: a +- w
4- n1
16:
Take action a
NETWORK ARCHITECTURE.
Rainbow-based agents use an identical network architecture as the original Rainbow agent (Hessel al., 2018). In particular, these include the use of NoisyNets (Fortunato et al., 2017), with the exception of Rainbow-CTT CTS, which uses a simple dueling value network like the "no noisy-nets" ablation in Hessel et al. (2018). preliminary experiment showed this setting with Rainbow-CTS performed slightly better than when NoisyNets were included.
R2D2-based agents use slightly enlarged variant of the network used in the original R2D2 Kap turowski et al. 2019), namely a 4-layer convolutional neural network with layers of 32, 64, 128 and 128 feature planes, with kernel sizes of 7, 5, and 3, and strides of 4, 2, 2 and 1, respectively. These are followed by fully connected layer with 512 units, an LSTM with another 512 hidden units, which finally feeds dueling architecture of size 512 (Wang et al. 2015). Unlike the original R2D2, Atari frames are passed to this network without frame-stacking and at their original resolution of 210 x 160 and in full RGB. Like the original R2D2, the LSTM receives the reward and one-hot action vector from the previous time step inputs.
HYPER-PARAMETER PARAMETERS AND IMPLEMENTATION NOTES
Unless stated otherwise, hyper- parameerrss for our Rainbow-basee agents follow the original im- plementation in Hessel et al. (2018), see Table 2 An exception is the Rainbow-CTS agent, which uses a regular dueling value network instead of the NoisyNets variant, and also makes use of an e-greedy policy (whereas the baseline Rainbow relies on its NoisyNets value head for exploration). The e parameter follows linear decay schedule 1.0 to 0,01 over the course of the first 4M frames, remaining constant after that. Evaluation happens with an even lower value of 0.001. The same e-schedule is used in hainbow+e-greedy and Rainbow+c2-greedt greedy, on top of Rainbow 's regular Noisy based policy.
The intrinsic reward implementation follows Bellemare et al. (016).. with the scale of intrinsic rewards to lower value of 0.0005. This agent was informally tuned for better
17

---

Published as a conference paper at ICLR 2021
performance hard-exploration games: Instead of the "mixed Monte- Carlo return" update rule from Bellemare et al. 2016)) Rainbow-CT uses an n-step Q-learning rule with n = 5 (while the baseline Rainbow uses n 3), and differently from the baseline does not a target network.
All of our R2D2-based agents are based on slightly tuned variant of the published R2D2 agent (Kapturowski al., 2019) with sypee--arametens unchanged, unless stated otherwise see Table
3] Instead of an n ste Q-learning update rule, our R2D2 uses expected SARSA(2) with À = 0.7 (Van Seijen et al., 2009). It also uses somewhat shorter target network update period of 400 update steps and the higher learning rate of 2 x 10-4. For faster experimental turnaround, we also use slightly larger number of actors (320 instead of 256). This tuning was performed on the vanilla R2D2 in order to match published results.
The RND agent modification of our baseline R2D2 with the addition of the intrinsic reward generated by the error signal of the RND network from Burda et al. (2018). The additional networks ("predictor" and "target" in the terminology of Burda et (018)) are small convolutional neural networks of the same sizing as the one used in Mnih et al. (2015), followed by single linear layer with output size 128. The predictor trained on the same replay batches as the main agent network, using the Adam optimizer with learning rate 0.0005. The intrinsic reward derived from its loss is normalized by dividing by its variance, utilizing running estimates of its empirical mean and variance. Note, the RND agent includes the use of e-greedy exploration.
The Bootstrapped R2D2 agent closely follows the details Osband et al. (211)). The R2D2 network is extended have k = 8 action-value function heads which share common convolutional and LSTM network, but with distinct fully-connected layers on top (each with the same dimensions in R2D2). During training, each actor samples head uniformly at random, and follows that action-value function's e-greedy policy for an entire episode. Each step, a mask is sampled, and added replay, with probability p 0.5 indicating which heads will be trained on that step of experience. During evaluation, we compute the average of each head's ' e-greedy policy to form an ensemble policy that is followed.
Rainbow (baseline)
Replay buffer size
10 observations
Priority exponent
0.5
Importance sampling exponent
annealed from 0.4 to 1.0
(over the course of 200M frames) 3
Multi-step returns n2
Discount y
0.99
Minibatch size Optimiser
32
Adam
Optimiser settings
learning rate = 6.25 x 10-5, c 1.5 x 10-4 2000 updates (32K environment frames) 0.0 (i.e. e-greedy used) 0.0 (i.e. no e-greedy used)
Target network update interval (training) (evaluation)
Rainbow+elez-greedly Rainbow+CTS 6 (training)
linear decay from 1.0 to 0.001 (over the course of 4M frames) 0.001
(evaluation)
Rainbow+CT'S only
Multi-step returns n
5
Intrinsic reward scale (3 in Bellemare et al. (0016)
0.0005
Target network update interval
1 (i.e., no target network used)
Table 2: values used in Rainbow- based agents (deviations from Hessel al. 2018 highlighted in boldface).
18

---

Published as a conference paper at ICLR 2021
Number of actors
320
Actor parameter update interval
400 environment steps
Sequence length
80 (+ prefix 20 for burn-in)
Replay buffer size
4 x 106 observations (10 part-overlapping sequences)
Priority exponent
0.9
Importance sampling exponent
0.6
Learning rule Discount y
Expected SARSA(A), X 0.7
0.997
Minibatch size
64
Optimiser
Adam
Optimiser settings
learning rate = 2 x 10
10-4,114-000 E 10
Target network update interval
400 updates
Table 3: Hyper-pan
Hyper-parameters parameters values used in R2D2-based agents (deviations from Kapturowski et al. (2019) highlighted in boldface).
Environment
# Trials
# Steps
Max Episode Length
Contour Scale
Discretization
DeepSea
30
500000 xN
Log
None
GridWorld
100
5000
5000
Linear
None
MountainCar
50
5000
5000
Linear
12
CartPole
100
5000
5000
Linear
20
Table 4: Settings for experiments used to generate average first-visit visualizations found in main
text.
D EXPERIMENT DETAILS
First-visit visualizations These results (e.g. see Figure are intended to illustrate the differences in trat-viiiittiinn patterns between e-greedy and ez-greedy. These are generated with some fixed e, often e = 1.0 for pure-cxploration independent of the greedy policy, and are computed using Monte-Carke rollouts with each state receiving integer indicating the first step at which that state was visited on a given trial. States that are never seen a trial receive the maximum step count, and then average these many trials. For continuous-stan problems discretize the state-space and count any state within small region for the purposes of visitation. We give these precise values in Table 4
Atari experiments The experimental setup for the Rainbow-based and R2D2-based agents each match those used in their respective baseline works. In particular, Rainbow-based agents perform mini-batch gradient update every steps and every 1M environment frames learning frozen and the agent is evaluated for 500K environment frames. In the R2D2-based agents, acting, learning, and evaluating all occur simultaneously and parallel, as the baseline R2D2.
In the Atari-57 experiments, all results for Rainbow agents are averaged over 5 random seeds, while results for R2D2-based agents are averages over 3 random seeds.
Atari-57 is most often used with built-in number (4) of action-repeats for every primitive action taken (Mnih et al. 2015). We did not change this environment parameter, which means that an exploratory action-repeat policy of length will, in the actual game, produce 4 x n low-level actions. Similarly, DQN- based agents typically use frame-stacking, while agents such as R2D2 which use an RNN do not. The robustness of our results across these different algorithms suggests that ez-greedy not greatly impacted by the presence or absence of frame-stacking.
Atari metrics
The human-normalized score defined as
agent random
score human random
where agent, random, and human are the per- ger-game scores for the agent, a random policy, and human player respectively. The human-gap is defined as the average, games, performance difference
19

---

Published as a conference paper at ICLR 2021
(a)
(b)
Scale 6.50
hofes Scale 0.17
Naite Scale 0.32
Notee Sca
Depouted neum
7.4
e-Gredyy
Ubcckatten NAr
Darrunie siur
Discumted reuur
22-
00'
3.0
0.
Eppoddss
Essoddss
Figure 7: Stochastic Gridworld experiments. (a) We show averaged training performance (over 100 episodes) with respect to the noise scale. (b) Example learning curves from these experiments showing the effect of stochasticity on both agents.
between human-level over all games,
human.gap- 1.0 E min(1.0, score).
Computational Resources Small-scale experiments were written Python and run on commodity hardware using CPU. Rainbow-basee agents were implemented in Python using JAX, with each configuration (game, algorithm, apper-parameter setting) run on a single V100 GPU, Such experi- ments generally required less than week of wall-clock time. R2D22-based agents were implemented in Python using Tensorflow, with each configuration run on a single V100 GPU and a number of actors (specified above) each run on single CPU, These agents were trained with distributed training regime, described in the R2D2 paper (Kapturowski et al. 2019), and required approximately 3 days to complete.
E EXPERIMENTAL RESULTS: STOCHASTICITY
In this section we present series of experiments focused on the effects of stochasticity and non- determinism in the environment on the performance of ez-Greedy.
SMALL-SCALE ENVIRONMENTS
We consider stochastic versions of two of our small-scale environments: GridWorld, and MountainCar. In the Gridworld domain the "noise scale" is the probability of the action transitioning to a random neighboring state. In MountainCar, where actions apply force in -1, 0, 1 to the car, we add mean zero Gaussian noise to this force with variance given by the specified noise scale. Finally, note that these forces are clipped to be within the original range of [-1,
Figure 7 shows the discounted return, averaged over the 100 episode training runs, as function of the noise scale. Figure 7 gives example learning curves for the agents (e-Greedy and ez-Greedy) for four levels of noise. We first note that for near-deterministic settings we replicate the original findings in the main text, but that the performance of the e-Greedy agent actually improves for small amounts of transition noise, while both agents degrade performance this noise becomes larger. We interpret this to suggest that the e-Greedy agent is initially benefiting from the increased exploration, whereas z-Greedy was already exploring more and begins degrade slightly sooner.
Figure & similarly shows the two agent's performance on MountainCar as we increase the scale of the transition noise. Here we both agents generally suffer reduced performance the level of noise increases and is maximal for both in the deterministic case, unlike in Gridworld.
ATARI-57 WITH STICKY-ACTION
The Areade Learning Environment (Bellemare al. 2013 ALE), supports form of -eterttermin called sticky actions where with some probability ( (typically set to 0.25) the agent's 's action is ignored and instead the previously exccuted action is repeated (Machado et al. 2018a). This is not exactly equivalent simpler transition noise, such as we used in the small-scale experiments above, because there is now a non- Mankovvan dependence on the previous action executed in the environment. Two additional details are important to keep in mind. First, the agent does not observe the action that was executed, and instead only observes the action that it intended to take. Second, the sticky-action effect applies at every step of the low-level ALE interaction. That is, it is standard practice to
20

---

Published as a conference paper at ICLR 2021
(a)
(b)
holsa Scale
Moine Scale m:25
hetee Scale =0.45
Noite Scale 0.75
Decouped reuu
mn-Gredy
Uiscontedd MAr
Discumes reurr
3.0
Eptiotes
Escoddss
Figure 8: Stochastic MountainCar experiments. (a) We show averaged training performance (over 1000 episodes) with respect to the noise scale. (b) Example learning curves from these experiments showing the effect of stochasticity on both agents.
Algorithm (@ (@200M)
Median
Mean
Human-gap
Rainbow
1.81
13.47
0.172
Greedy
2.10
14.13
0.152
Rainbow+e:-Greedy
2.17
14.53
0.141
Table 5: Sticky-action Atari-57 final performance summaries for Rainbow-base agents after 200M environment frames.
an action-reppe repiet (usually 4) in Atari, such that each action selected by the agent is repeated some number of times in the low-level interaction. Thus, sticky actions apply every step of this low-level interaction.
Because of the non-Markovian effects and the relatively fast decay in probability of action-repeats, sticky actions do not provide similar exploration benefits seen in ez-Greedy. Unlike in exploration using action-repeats the agent is unable to learn about the actions that were actually executed, making the underlying learning problem more challenging. In some environments, where precise control is needed for high performance, sticky actions tend to significantly degrade performance agents.
We note that sticky actions are modification usually applied the problem, not the agent, and usually make the problem harder. The reason for this is that sticky actions increase the level of stochasticity of the environment, but do with non-Markovian dependency on the previously executed action. Given the superficial similarity with action-repeats, one might ask whether using sticky actions might benefit exploration hard exploration games similar to ez-Greedy. In order to answer this question we compare our Rainbow-based e-Greedy and ez-Greedy agents on the Atari-57 benchmark with sticky actions enabled (Ç 0.25).
Figure g gives the median, mean, and human-gan gap values for the human-normalinn normalized scores. We observe that much of the gap performance in mean and median have disappeared. and that even for human-gap gap the performance benefits of c2-Greedy over c-Greedy have been partially reduced. Nonetheless, we continue see significant improvements in performance on the same set of harder exploration games as in the non-sticky-acto action results (see Figure I0). Finally, we give the numeric values for the final performance of these agents Table
F EXPERIMENTAL RESULTS: LIMITATIONS
To further study the limitations of ez-Greedy, and motivate work on learned options for exploration, we consider the effect on performance of adding "obstacles" and "traps" in the Gridworld domain. For our purposes, an obstacle is an interior wall in the gridworld, such that if the agent attempts to occupy the location of the obstacle the result is no-op action with no state transition. On the other hand, a "trap" results in the immediate end of an episode, with zero reward, if the agent attempts to occupy the same location as the trap. Figure II shows a set of example gridworlds with obstacles and traps generated at varying target densities. We generate the environments by filling 20 x 20 gridworld with either obstacles or traps (not both), where each state has some probability of being so filled (given by the target density). We then identify the largest connected component of open cells and select the goal and start states randomly without replacement from the states in this component. This ensures that all gridworlds can be solved.
21

---

Published as a conference paper at ICLR 2021
Median Normelized
Mean Normalized
Mean Human Gap
16
0.40
Rainbow
Rainbow+
12
Rainbow+ or Greedy
0.30
1.5
1.0
0:25
0.20
0.15
0.0
25
100
175
0
25
100
150
175
25
150
150
175
Environment frames (million)
Ervironment frames (million)
Ervironment frames (million)
Figure 9: Sticky-action Atari-57 summary curves Rainbow-based agents.
Figure 10: Sticky-action Atari-57 results for selected games showing Rainbow-based agents. Curves averages over seeds.
Note that increasing the density of obstacles and traps has two opposite effects: on one hand it reduces the overall state space, thus making the problem easier, on the other hand it also makes exploration more difficult, since obstacles result in a sparser transition graph and traps result in many absorbing states. Based on observations, the latter effect tends to be stronger than the former.
Our experiments focus on studying the performance of e-Greedy and ez-Greedy as we scale the density of the obstacles or traps. Figure 12 & 1 show our results in these two sets of experiments. In both cases we observe that the gap in performance between c2- ez-Greedy and c-Greedy decreases with the density of the problematic states. Interestingly, We believe this is partly to be expected because e-Greedy is exploring more locally and more densely around the start state, making navigating around obstacles somewhat easier. Note that have increased the number of episodes from 100 (used in the main text) to 1000 in order to increase the likelihood of both agents solving a given problem. Additionally, unlike in the main text, every trial of these experiments is performed on a randomly generated gridworld with randomly selected start and goal locations; although we do ensure that each agent is trained on the same environment, the environment itself is different for each seed. This is reflected in the larger variances in performance indicated by the shaded regions in the figures.
see that c-Greedy is not impacted as seriously.
G FURTHER EXPERIMENTAL RESULTS
In this section, we include several additional experimental results that do not fit into the main text but may be helpful to the reader. In the conclusions we highlight a limitation of ez-greedy which occurs when the effects of actions differ significantly between states. In Figure 14 we present results for such an adversarial setting in the DeepSea environment, where the action effects are randomly permuted for every state. We observe, as expected, that in this setting ez-greedy no longer provides more efficient exploration than é-greedy.
we compare with RMax (Brafman and Tennenholtz 2002) on the Gridworld domain. We consider two values for the threshold for state-action being marked as known: N 1, effectively encoding an assumption that the domain is deterministic, and N = 10 which is a more generally reasonable value. We observe that, if tuned aggressively, RMax significantly outperform ez- Greedy, as should be expected. However, we note that unlike RMax c2- e2-Greedy does not assume access to tabular representation and can scale to large-scale problems.
In Figure 15
Next, in Figures [6 & 17 we report the per-game percentage of relative improvement, using human- normalized scores, over an e-greedy baseline for ez-greedy in both the Rainbow and R2D2 agents.
22

---

Published as a conference paper at ICLR 2021
0.00
w0.0
Density 0000
Density 0.05
Densty =0.10
Density 00.55
Example Gridworlds with varying density of (top) obstacles and (boftom) traps. The shades of grey represent the type of each cell: white cells are open states, light grey cells are the start state, grey cells are traps, dark grey cells are goal states, and black cells are obstacles. These environments are randomly generated to target density of obstacle / trap, while ensuring there exists a path between the start and goal states.
Figure 11:
(b)
Demsity 6:50
Dereky =0
Density 0.20
Deroby -0
Dopounted
DiScu Discoaeee udar
Dic 1dtam
An-reeyy Greddy
2.6
-32
033
630 635 Denaly
132 030
250
500
750
3000
257
SE6
1920
3993
Escodda
Eplases
Eipodas
Figure 12: Gridworld with obstacles at varying density. (a) We show averaged training performance (over 1000 episodes) with respect the obstacle density. (b) Example learning curves from these experiments showing the effect on both agents.
In both cases we give the corresponding results for improvement of CTS, for Rainbow, and RND, for R2D2, over the same baselines. Additionally, we give these results for both the final agent performance and the performance averaged over training. The percent relative improvement of score over baseline computed as
Score - boseline
100
bascline
Note that we limit the maximum vertical axis in such way that improvement in some games is cut off. This is because for some games these relative improvements are so large that it becomes difficult to see the values for other games on the same scale.
the main text we give summary learning curves on Atari-57 for Rainbow- and R2D2-based agents in terms of median human-normalian score and human-gap. In Figure 18 we show these as well as mean numan-nnormlizee score learning curves. Figures 19|& T9]
20 we give full, per-game results for Rainbow- and R2D2-based agents respectively. These results offer additional context those reported in the main text, demonstrating more concretely the nature of the performance trade-offs being made by each algorithm.
Finally, in Table we give mean and median human- normalized scores and the human-gap on Atari-57 for the final trained agents. However, this is slightly different evaluation method than is often used (Mnih et al. 20155 Hessel et al., 22118), in which only the best performance for each game, training, considered. For purposes of comparison we include these results in Table 6
23

---

Published as a conference paper at ICLR 2021
Decivees (
codlocc e-Oreeff
(b)
Cendtty 5.50
DeraBl +1 05
Denally +0300
Denaby 0.15
Diowented 1our
Couuetted rour
d-rredy
200 040
760
Deastt
Ecltddas
Tplescen
Echedds
Episades
Figure 13: Gridworld with traps at varying density. (a) We show averaged training performance (over 1000 episodes) with respect to the trap density. (b) Example learning curves from these experiments showing the effect both agents.
DeepSea (Adv)
<-Greedy
ez-Greedy
210
24
Fribiem
Figure 14: Adversarial modification to DeepSea environment causes ez-greedy to perform no better than e-greedy.
Algorithm (@30B)
Median
Mean
Human-gap
Median (best)
Mean (best)
R2D2
14.31
39.55
0.102
19.36
46.98
R2D2+RND
9.40
42.17
0.151
14.34
48.02
R2D2+Bootstrap
15.75
37.69
0.096
19.35
43.87
R2D2+ez-greed
16.64
40.16
0.077
22.63
45.33
Algorithm (220M)
Rainbow
2.09
8.82
0.139
2.20
12.24
Rainbow+e-Greedy
2.26
9.17
0.144
2.56
12.23
Rainbow+CTS
1.72
6.77
0.157
2.09
7.62
Rainbow+e>-Grredd 2.35
9.34
0.130
2.74
12.28
Table 6: Atari-57 final performance summaries. R2D2 results are after 30B environment frames, and Rainbow results are after 200M environment frames. We also include median and mean human- normalized scores obtained by using best (instead of final) evaluation scores for each training run, to allow comparison with past publications which often used this metric (e.g. Hessel al. (2018)..
0.8
Discounted return
ARA AM
0.6
Ez-Greedy
M
e-Greedy
0.4
RMax(1)
RMax(10)
0.2
0.0
0
20
40
60
80
100
Episodes
Figure 15: Experiment in the Gridworld domain comparing Rmax, with visitation thresholds 1 and 10 with e-Greeyy and ez-Greedy
24

---

Published as a conference paper at ICLR 2021
Groedy improvement (Ra
CTS Imprevame Gready (Rankoww
Crredd improvement Over Caeedy (a rbox Avarage
CTS improvament Over Creadyy Marboow Averagel
Figure 16: Percent relative improvement of exploration methods (ez-Greedy and CTS) over e-Greedy for the Rainbow-based agents on Atari-57 per-game. We report this for both final performance (top) and average over training (bottom).
Groddy improvement Overe Geedy /R2D2, Anal)
Ingrovement Over Gredd (R202 Rial
Grodd improvement O Gredd (R20L Ansegg)
impromment eCowedy (RZT)) Auerage)
Figure 17: Percent relative improvement of exploration methods (ez- Gre-rrydyy and RND) over e-Greedy for the R2D2-based agents on Atari-57 per-game. We report this for both final performance (top) and average over training (bottom).
25

---

Published as a conference paper at ICLR 2021
Median Normalized
Normalized
Gap
0.18
10
0.14
0.12
R2D2
RND
Bootstrap
15
cz-Greedy
0.08
2
3.0
Environment frames
Environment frames
Environment frames
Median Normalized
Mean Normalized
Mean Human Gap
Rainbow
Human-normalized Poomallzzdeeee Score Score
2.0
8
Rainbow+ Greedy
Rainbow+ es-Greedy
Rainbow CTS
1.0
00
0.15
0.10
0.0
25
50
100 125 150 175 200
25 50
100
125
150
175
200
50
100
125
150 175 200
Environment frames (million)
Environment frames (million)
Environment frames (million)
Figure 18: Atari-57 summary curves for R2D2-based methods (top) and Hhinbow-based methods (bottom).
26

---

Published as a conference paper at ICLR 2021
133
110
0000
0801
055
09
120
140
1789
2013
Ted Namer
robotant
18.9g
1001. Irnders
1379.70
-10
2m0
150
yer. Tivenge
Sahrow
Figure 19; Per-game Atari-57 results for Rainbow-back based methods.
27

---

Published as a conference paper at ICLR 2021
1X0100
300
20190
36
3000
100.9
101.0
120.0
100
10:05
10000
100109
63
20
63
15
20
65
17
63
L0 15
13
03
10
13
03
10
Sedee
000.8
10:40)
130400
12000
2176
00phWr
101003
2.0
1000
1610
100
1750)
10rgarte
1000
20080
30.00
15080
sung maiCe
sfowddc
140.00
20000
2080
0009
100g
13780
1000
19093
2008
8000
13080
2303
340
140
180
70:00
2080
R232
RND
13000
10080
45 LC
30
45
L0
45 LE
Figure 20: Per-game Atari-57 results for R2D2-based methods.
28

---

Published as a conference paper at ICLR 2021
3900
200
400
1189
1780
1900
2. 22.00
1108
1050
800
130
00010294.000 Weage
1350
27482
424
300
2.00
3609
2800
1190
2000
7000
1800
180
18 611
12.08
00
14. 1.1.
6117
18..1 18..12883
10:99
1200
300
Ralthme Grent
Orcoly
3000
Figure 21: Per-game Sticky-action Atari-57 results for Rainbow-based methods.
29


Reviews:
[{"review_id": "x1btFJ1WXm", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "##########################################################################\nSummary:\n\nThis paper proposes a simple yet general approach for exploration in discrete-action problems. The proposed approach, called ez-greedy, combines randomly selected options with the well-adopted e-greedy exploration policy to achieve temporally-extended e-greedy exploration. The paper overviews the publicized exploration methods from the perspective of their inductive biases, and clearly states where the inductive bias of ez-greedy would be better suited over e-greedy. The paper reports results in tabular, linear, and deep RL settings, on numerous domains ranging from classic toy problems to Atari-57. The results are interesting, and the analysis aligns and supports nicely the narrative of the paper.    \n\n##########################################################################\nReasons for Score:\n\nOverall, I vote for accepting this paper. The idea is simple (a generalization of e-greedy) and the discussions nicely illustrate the main properties of an ideal generally-applicable exploration method. The experiments clearly show where ez-greedy exploration would be useful. Also, they show that the inductive bias of ez-greedy does not hurt much the performance in simpler dense-reward domains while more specialized algorithms suffer significantly.  \n\n##########################################################################\nPros:\n\nSee \"Reasons for Score\" above.\n\n##########################################################################\nCons:\n\n1) The results in Atari are based on a deterministic version of Atari (i.e. not using \"sticky actions\"). Also, in DeepSea the deterministic version of the task is used. Ideally, I would've liked to see empirical results in stochastic domains as well. More importantly, I'm not sure why only deterministic domains are used?\n\n2) The literature on action-repeats are discussed briefly. But it's hard to know how the former related works were different in their formulation and use of action-repeats. Also, could you clarify how sticky-actions are positioned w.r.t. ez-greedy (beyond that the purpose behind sticky-actions was to induce stochasticity in the environment as opposed to being used explicitly for exploration)? For instance, do sticky-actions actually improve learning performance in the same domains were ez-greedy improves performance?\n\n3) The rainbow + e-greedy vs. Rainbow + ez-greedy Median and Mean plots do not show significant findings. I think a bar-plot should be added to show per-game relative human-normalized improvements for these versions. The same should be done for R2D2 (e-greedy) vs. R2D2 + ez-greedy as well. I think what this could reveal is symmetric bars over the 57-Atari games (i.e. number of games in which ez-greedy outperforms and underperforms e-greedy are the same). Also, the extent of improvements on average is the same as shown in the Mean plot of Figure 8. \nTo clarify, I don't see an issue with this outcome (i.e. if the bars are symmetric; meaning overall there are as many games in Atari-57 that would benefit from ez-greedy over e-greedy as there are games in which the opposite is the case). This does not go against the narrative of the paper which makes it clear that they each have an inductive bias that suits some tasks over others. But I think this should be made super clear in the results section, through such bar plots. For the same reason, I think the Mean plots should also be brought to the main text and shown next to the Median curves.   \n\n4) Why only 5 random seeds in DeepSea? I suggest showing results for 30 randoms seeds like in the other toy problems.\n  \n##########################################################################\nQuestions during the rebuttal period:\n\nPlease address and clarify the \"Cons\" above.\n\n##########################################################################\nMinor comments:\n\n- It would be useful to replace \"Rainbow\" with \"Rainbow (NoisyNet)\" in Figure 3 so as to emphasize the difference between \"Rainbow\" and \"Rainbow + e-greedy\". Similarly, for \"R2D2\" it'd make it easier for the reader if the Figures show \"R2D2 (e-greedy)\". \n\n- Table 1: \"Algorithm (@200M)\": M doesn't need to be italicized (to be consistent with \"Algorithm (@30B)\").\n\n- It'd make it easier if \"(100%)\" is added to the y-axis of Median/Mean plots.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "sAeoh5Wzew4", "reviewer": "AnonReviewer1", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a generalized overview of temporally extended e-greedy exploration. Basic principle of temporally extended e-greedy exploration is to apply the e-greedy exploration policy for an extended period of time. Specifically, authors use a heavy-tailed zeta distribution. \n\nStrong points\n- This paper analyze theoretical properties of temporally extended e-greedy exploration in Theorem 1. \n- ez-Greedy policy outperforms e-Greedy policy in some experiments environments qualitative and quantitatively.\n\nWeak points\n- The theoretical analysis is too general under too strong assumptions. Thus, the presented results are not unexpectedly novel.\n- The presented methods based on the zeta distribution are not concrete enough. \n- Algorithm is not clearly specified. Thus, it is hard to evaluate the algorithmic contributions of this paper.\n\nAlthough this paper presents a general analysis on temporally extended e-greedy exploration, the presented ideas are too general. Thus, it is very hard to verify the technical contributions (in terms of models and algorithms) of this paper.", "extra_scores": {}, "extra_text": {}}, {"review_id": "MRTarz4lnQ7", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents an extension of \\eps-greedy strategy in order to increase the coverage of exploration in RL problems. The main idea is to take an exploratory option instead of a single action e.g., by repeating an action for n steps, where the duration of repeat is sampled from some distribution. The authors demonstrate that given certain conditions, the algorithm will converge in polynomial time for Q-learning method.\n\nOverall, the paper provides a simple yet effective exploration technique for RL methods. However, there are some unclear points regrading the impact of the approach on the filed, I thus vote for a weak reject. \n\nPros:\n- A simple and universal approach to promote full coverage in reinforcement learning\n- Scalable and easy to implement\n- Interesting inspiration from animal foraging behavior\n- Demonstrates effective performance in conducted experiments\n\n\nComments:\n\n- The key concern about the paper is whether gaining the full coverage in exploration is beneficial at any cost. In my view, RL favors smarter exploration over the total coverage. For instance , the exemplary scenario in figure 1 shows how the proposed approach increases the coverage of the state space.  But why we would need to search the whole space if we are on the right path to the goal. Unnecessary coverage will lead to higher regret and delayed convergence that is the result of naive exploration.\n\n- Another problem with \\eps-greedy is that it explores forever. Hence, it would be an improvement to stop/reduce exploration at some point rather than intensify it. Assume in the steps close to the goal, the worst action has the same probability to be chosen as the second-best action and it repeats for n times which moves the agent farther from the goal. I would suggest to add evaluation in terms of regret and/or convergence time in such scenarios.\n\n- The limitations both enumerated in the paper and the dependency of the approach on some strong conditions on the options seem to be more than the benefits of the proposed method. Besides, it is not general in terms of class of applications; e.g., in complex tasks we can not simply repeat an action in different states.\n\n- How does the approach behave in very simple settings, e.g., bandits? I would recommend to add such analysis for online exploration into the paper.\n\nMinor:\nTable 1 is not referenced in the text", "extra_scores": {}, "extra_text": {}}, {"review_id": "1r-RCJtYHGP", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 proposes an easy-to-implement algorithm for the efficient exploration, which is a temporally-extended version of \\eps-greedy. Instead of uniformly selecting primitive actions with probability \\eps for exploration, the algorithm explores using options. In theory, it has been shown that if the option set is well-designed with a sublinear expected reaching time, the algorithm achieves a polynomial sample complexity. Empirically, the authors tested a simple instantiation, ez-greedy, in multiple environments and claimed that ez-greedy improves exploration and performance in sparse-reward environments with minimal loss in performance on easier, dense-reward environments.\n\nI appreciate this work for its motivation and the algorithm is simple-to-implement and not computationally expensive, which points to an interesting direction for future study. \n\nBut there are several concerns I have: \n1. The conditions in Thm. 1, i.e. a sublinear upper bound on visiting time and 1/p(w), is not straightforward for me to realize. How should one construct such an option set if no prior knowledge is given? Do the option-learning methods in [Jinnai et al. 2019, 2020] and [Machado et al. 2017 2018] satisfy these conditions? Does ez-greedy satisfy these conditions? If not, what approximately are the upper bounds for these heuristics? There should be more discussion about this.\n2. In the tabular RL, it would be more complete if the authors can compare with UCB-based exploration strategies as well, e.g. the UCB-Q as in http://papers.nips.cc/paper/7735-is-q-learning-provably-efficient.\n3. As mentioned by the authors, the performance of ez-greedy depends on whether the effects of actions differ significantly across states. There should be more adversarial cases to show the possible outcomes of ez-greedy compared with other exploration strategies.\n4. As mentioned by the authors, action-repeats are not new in deep RL. The novelty of this work lies in using it for exploration with sampled duration. However, the selection of zeta-distribution for duration sampling is only partially empirically demonstrated as well as the choice of \\mu. It would be better if the authors can support it with a theoretical justification or some quantitive analysis in terms of e.g., how the value of \\mu affects the final performance.\n\nI am open to adjusting the score if the rebuttal can address my concerns.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "-4eTo3jrZx", "reviewer": "AnonReviewer5", "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": "**Summary:**\n\nThis paper offers a critique of current exploration techniques as being overly complex and engineered to only work on specific tasks. As an alternative, the paper proposes temporally extended $ \\epsilon$-greedy exploration which maintains the simplicity and generality of $ \\epsilon$-greedy while offering better . More specifically, the proposed algorithm simply repeats the randomly chosen action for a random number of steps (where the number of steps comes from a specific distribution), this is a specific instantiation of the more general algorithm presented in the paper where any set of semi-markov options can be used.\n\n--------------------------------------------------------------------\n\n**Strengths:**\n\n1. Clarity. This paper is very well-written and clear, making it enjoyable to read. It sets up the shortcomings of prior methods and offers a simple solution. I also especially appreciated the clear discussion of the limitations of the proposed method.\n\n2. Strong critique of prior methods to provide motivation. It is an important observation that while many exploration methods are developed in the theory and deep RL communities, they are often inferior in practice to simple strategies like $ \\epsilon$-greedy. While this is not a novel contribution, this paper really drives home the point by providing a slightly smarter variant of dithering that competes favoriable with much more complicated algorithms. This is an especially important contribution of this paper since it makes the point to the RL community that simple exploration strategies may be more effective in practice, but there is still room to innovate while maintaining simplicity and generality.\n\n3. Strong empirical results. The experiments clearly show an improvement over $ \\epsilon$-greedy in small benchmark problems. Then, they demonstrate how $ \\epsilon z$-greedy even improves over more complocated exploration strategies for deep RL algorithms applies to atari relative to more complicated exploration algorithms like RND (at least in the \"average\" case, but not on \"hard exploration\" games like Montezuma's revenge).\n\n   \n\n--------------------------------------------------------------------\n\n**Weaknesses:**\n\n1. The theory could be tightened. The paper would be stronger if the theorem were stated more formally (defining polynomial sample complexity) and the proof provided the specific results being used from the cited papers (maybe as lemmas in the appendix). At a more substantive level, it is not clear how exhaustive the list of desired properties of an exploration algorithm is. The paper lists three desiderata for an exploration strategy: (1) that it is simple, (2) that it is stationary, and (3) that it promotes full coverage of the state-action space. Each of these goals makes sense, but the paper does not provide any framework to explain why these are a necessary or sufficient set of properties to yield the desired behavior. Moreover, it is not clear what the tension or tradeoffs are between the properties. A more clear discussion of these issues or formal framework could go a long way toward clarifying the landscape of exploration algorithms. \n\n--------------------------------------------------------------------\n\n**Recommendation:**\n\nI reccomend accepting this paper and gave it a score of 8. I think the paper provides a clear argument for simple and general exploration strategies and that $ \\epsilon z$-greedy seems to be an algorithm that achieves these goals. Moreover, I think that the paper makes an important point to the community working on exploration algorithms that the complicated algorithms being developed can often be beaten by simple strategies when considering a broad range of problems.\n\n--------------------------------------------------------------------\n\n**Additional feedback:**\n\n- One reference that I think should be included when discussing learning temporally extended representations of actions is [1].\n\n- Typo: line 2 of the last paragraph on page 1 should be \"such a compromise\".\n- The discussion of the choice of distribution over durations was somewhat abrupt. This is an interesting part of the algorithm and it would be nice if it was fleshed out a bit more. \n\n\n\n[1] Whitney, W., Agarwal, R., Cho, K., & Gupta, A. (2019). Dynamics-aware Embeddings. *arXiv preprint arXiv:1908.09357*.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a simple generalization to epsilon-greedy exploration that induces temporally extended probes and can leverage options.  The idea and analysis are trivial.  Computational results demonstrate when this sort of exploration is helpful.  The paper is well written and the authors offer a fair assessment of when these ideas do or do not address challenging exploration tasks.  A range of computational results support and offer insight into the concepts.

Decision: Accept (Poster)