MADE: Exploration via Maximizing Deviation from Explored Regions
Authors: Tianjun Zhang
Paria Rashidinejad
Jiantao Jiao
Yuandong Tian
Joseph E. Gonzalez
Stuart Russell
Venue: NeurIPS 2021 Poster (2021)
Keywords: Deep reinforcement learning
exploration
intrinsic reward

Abstract: In online reinforcement learning (RL), efficient exploration remains particularly challenging in high-dimensional environments with sparse rewards. In low-dimensional environments, where tabular parameterization is possible, count-based upper confidence bound (UCB) exploration methods achieve minimax near-optimal rates. However, it remains unclear how to efficiently implement UCB in realistic RL tasks that involve non-linear function approximation. To address this, we propose a new exploration approach via *maximizing* the deviation of the occupancy of the next policy from the explored regions. We add this term as an adaptive regularizer to the standard RL objective to balance exploration vs. exploitation.  We pair the new objective with a provably convergent algorithm, giving rise to a new intrinsic reward that adjusts existing bonuses. The proposed intrinsic reward is easy to implement and combine with other existing RL algorithms to conduct exploration. As a proof of concept, we evaluate the new intrinsic reward on tabular examples across a variety of model-based and model-free algorithms, showing improvements over count-only exploration strategies. When tested on navigation and locomotion tasks from MiniGrid and DeepMind Control Suite benchmarks, our approach significantly improves sample efficiency over state-of-the-art methods.

MADE: Exploration via Maximizing Deviation from Explored Regions
Tianjun Zhang
Paria Rashidinejad
Jiantao Jiao
Yuandong Tian
Joseph E. Gonzalez!
Stuart Russell*
University of California, Berkeley
(tianjunz, paria. raw.ii....aaiiiieeaa jaaaaadd,iatttt,raaaaaoo riaeelll edu
Facebook Al Research yuandong@fb.co com com
Abstract
In online reinforcement learning (RL), efficient exploration remains particularly challenging in high-dimensional environments with sparse rewards. low- dimensional environments. where tabular parameterization is possible, count-based upper confidence bound (UCB) exploration methods achieve minimax near-optimal rates. However, it remains unclear how to efficiently implement UCB in realistic RL tasks that involve nonlinear function approximation. To address this, we propose a exploration approach via maximizing the deviation of the occupancy of the next policy from the explored regions. We add this term as an adaptive regularizer the standard RL objective trade off between exploration and exploitation. We pair the new objective with a provably convergent algorithm, giving rise to a intrinsic reward that adjusts existing bonuses. The proposed intrinsic reward is easy to implement and combine with other existing RI algorithms to conduct exploration. As proof of concept, we evaluate the new intrinsic reward tabular examples across a variety of model-based and model-free algorithms, showing improvements over count-only exploration strategies. When tested on navigation and locomotion tasks from MiniGrid and DeepMind Control Suite benchmarks, our approach significantly improves sample efficiency over sfate-o-the-asd methods
1 Introduction
Online RL a useful tool for an agent to learn how to perform tasks, particularly when expert demon- strations are unavailable and reward information needs to be used instead 92] To learn satisfactory policy, an RL agent needs to effectively balance between exploration and exploitation, which remains central question in RL. 2 15].
Exploration is particularly challenging in environments with sparse rewards. One popular approach to exploration is based on intrinsic motivation, often applied by adding intrinsic reward (or bonus) to the extrinsic reward provided by the environment. In provable exploration methods, bonus often captures the value estimate uncertainty and the agent takes an action that maximizes the upper confidence bound (UCB) 55 g bonuses are often constructed based on either Hoeffding's 's inequality, which only uses visitation counts, or Bernstein's inequality, which uses value function variance in addition to visitation counts.
K In tabular setting, UCB
"Equal Contribution.
Our code is available at htttp:://gicuub..o////aaa///////
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Norsalizdd Speedup in MiniGrid
Normalized Speedup DeepMind Control Suite (Spase)
KIDE
Bebeld
AXD00
X0422
MADE
CURL
DrQ
-
RAD
- RAA--EE
RAD+RND
-MADS
42
20107225
244
UP
SCesKa
Hopper,
Figure 1: Normalized samples use of different methods with respect to MADE (smaller values are better). MADE consistency achieves a better sample efficiency compared other baselines. Infinity means the method fails to achieve maximum reward in given steps.
The latter is proved to be minimax near-optimal environments with bounded rewards 401 651 as
well as bounded total reward [122 and reward-free settings [64 3o 45 |I It remains open question how one can efficiently compute confidence bounds to construct UCB bonus in non-linear function approximation. Furthermore, Bernstein-style bonuses often hard to compute in practice beyond tabular setting, due to difficulties in computing value function variance.
In practice, various approaches are proposed to design intrinsic rewards: visitation pseudo-count bonuses estimate count-based UCB bonuses using function approximation [TC] 15), curiosity-bar -based
bonuses seek states where model prediction error is high, uncertainty- bbased bonuses 777 87 adopt ensembles of networks for estimating variance of the Q-function, empowerment based approaches
52
34
84
68
lead the agent to states over which the agent has control, and information gain bonuses [51
reward the agent based on the information gain between state-action pairs and next states.
Although the performance of practical intrinsic rewards is good in certain domains, empirically they are observed suffer from issues such as detachment, derailment, and catastrophic forgetting 23
Morcover, these methods usually lack clear objective and can get stuck in local optimum 3 Indeed, the impressive performance currently achieved by some deep RL algorithms often revolves around manually designing dense rewards [13] complicated exploration strategies utilizing a significant
amount of domain knowledge [23] or operating in the known environment regime [S
Motivated by current practical challenges and the gap between theory and practice, we propose a new algorithm for exploration by maximizing deviation from explored regions. This yields practical algorithm with strong empirical performance. To be specific, we make the following contributions:
Exploration via maximizing deviation Our approach is based on modifying the standard RL objective (i.e. the cumulative reward) by adding a regularizer that adaptively changes across iterations. The regularizer can be general function depending on the state-action visitation density and previous state-action coverage. We show that the regularized objective naturally admits several common existing exploration methods. We then choose a particular regularizer that MAximizes the DEviation (MADE) of the next policy visitation d from the regions covered by prior policies p&ov:
Lx(dd) J(d")
Σ
d (s.a)
Here, ls is the iteration number, (dd) is the standard RL objective, and the regularizer encourages d" (Ts a) to be large when (s. is small. We give algorithm for solving the regularized objective and prove that with access to an approximate planning oracle, it converges to the global optimum. We show that objective 1 results in an intrinsic reward that be easily added any RL algorithm to improve performance, as suggested by our empirical studies. Furthermore, the intrinsic reward applies a simple modification the UCB-style bonus that considers prior visitation counts. This simple modification can also be added to existing bonuses in practice.
Tabular studies In the special case of tabular parameterization, we show that MADE only applies some simple adjustments to the creffding-style count- bonus. We compare the performance of MADE Hoeffding and Bernstein bonuses in three different RL algorithms, for the exploration task in the stochastic diabolical bidirectional lock 3 66) which has sparse rewards and local optima. Our results show that MADE robustly improves over Hoeffding bonus and competitive the Bernstein bonus, across all three RL algorithms. Interestingly, MADE bonus and exploration strategy

---

appear to be very close to the Bernstein bonus, without computing or estimating variance, suggesting that MADE potentially captures some environmental structures. Additionally, we empirically show that MADE regularizer can improve the optimization rate in policy gradient methods.
3. Experiments on MiniGrid and DeepMind Control Suite We empirically show that MADE works well when combined with model-free (IMAPLA [25] RAD (551) and model-based (Dreamer 35 RL algorithms, greatly improving the sample efficiency over existing baselines. When tested in the procedurally--eenraaed MiniGrid environments, MADE manages to converge with two to five times fewer samples compared to state-of-the-ard method BeBold [ΣЛ. In DeepMind Control Suite 195 we build upon the model-fie pooeel-free method RAD [5 and the model-based method Dreamer [35], improving the return up to 150 in 500K steps compared to baselines. Figure ! shows normalized sample size to achieve maximum reward with respect to our algorithm.
2 Background
Markov decision processes. An infinite-horizon discounted MDP is described by a tuple M (S,A,P,r, p. 7), where S is the state space, A is the action space, P S x A A(S) is the
+ [0, 1] is the (extrinsic) reward function, p S + ( is the initial distribution, and 7 E [0, 1) is the discount factor. A stationary (stochastic) policy т A(A S) specifies a distribution over actions in each state. Each policy π induces a visitation density over state-action pairs d= S x A + [0, 1] defined as dx ()) == (1-?) Σ 7" P' 8, at R),, where (st s, d2 a: T) denotes (s, visitation probability at step t, starting 8o p(.) and following x. An important quantity is the value a policy я, which is the discounted sum of rewards (s) = E E== 7'r, 80 0, ... 8e) for all 2 0] starting at state S.
transition kernel, r : S x A
Policy mixture. For a sequence of policies C* ( .Tk) with corresponding mixture dis- tribution w E A the policy mixture m (C* w/) is obtained by first sampling a policy from w² and then following that policy over subsequent steps [36.. The mixture policy induces state-action visitation density according to d (s,a) = Σ wid ( (s. a). While the Tiix may not be stationary in general, there exists a stationary policy n' such that d=' dm Puterman [S)]
Online reinforeement learning. Online RL is the problem of finding policy with maximum value from an unknown MDP, using samples collected during exploration. Oftentimes, the following objective is considered, which is scalar summary of the performance of policy
JM (T) = - [V* (s) (1 -- (e (..) (or((s [r(s.a)]=
J(d").
We drop index M when it is clear from context. We denote optimal policy by x- E arg max, (T) and use the shorthand V = V= to denote the optimal value function. It is straightforward to check that J (T) can equivalently be represented by the expectation of the reward over the visitation measure of π. We slightly abuse the notation and sometimes write J (d=) to denote the RL objective.
3 Adaptive regularization of the RL objective
3.1 Regularization to guide exploration
In online RL, the agent faces dilemma in each step: whether it should select a seemingly optimal policy (exploit) or should explore different regions of the MDP. To allow flexibility in this choice and trade off between exploration and exploitation, we propose to add a regularizer to the standard RL objective that changes throughout iterations of an online RL algorithm:
L (ddd))
(dd +Th R(d"; (dTT JE
(3)
exploitation
exploration
Here, R(d"; (d }/=)) )) is a function of state-action visitation of I as well as the visitation of prior policies TI...., -T. The temperature parameter тıe determines the strength of regularization. Objec- tive 3 a population objective the sense that it does not involve empirical estimations affected by the randomness in sample collection. In the following section, we give our particular choice of regularizer and discuss how this objective can describe some popular exploration bonuses. We then provide convergence guarantee for the regularized objective in Section 3.2
3

---

3.2 Exploration via maximizing deviation from policy cover
We develop our exploration strategy MADE based on simple intuition: maximizing the deviation from the explored regions, i.c. all states and actions visited by prior policies. We define policy cover at iteration & to be the density over regions explored by policies II..... TT, i.c. Pam a) =
I E
d (s, a). We then design our regularizer to encourage d' to be different from Par
d ds a)
Re(d";
( (d
= s,a
Σ
(4)
Panr (3,0)
It is easy to check that the maximizer of above function is (8, x Pen (s.a]] Our motivation behind this partieular deviation is that it results in a simple modification of UCB bonus in tabular case.
We now compute the reward yielded by the new objective. First, define policy mixture Tmix, with policy sequence ( (#1...., TT) and weights (1-n))* (1- s7)* 217, (1 (1-1)) (-))))>......................... .......77 77) for 1j > O. Let m be the visitation density of mixx, We compute the total reward at iteration k by taking the gradient of the new objective with respect to d at ddlmix.:::
(* a) = (1 - L d = =r(s,a) a) + (1 - T) Ra (d (e=))==)) (a=i)aamdmine (5)
which gives the following reward
(1 (1- 72
rx( = r(s VdTimx..o a) (0 (s.
(6)
The intrinsic reward is constructed based on two densities: Peov a uniform combination of past visitation densities and d & a weighted mixture of the past visitation densities. As we will discuss shortly, policy cover p&ov (s, a) is related to the visitation count of (s, a) pair in previous iterations or their approximates such as RND [3]. Therefore, for an appropriate choice of Tk. MADE intrinsic reward decreases as the number of visitations increases.
and resembles count-based bonuses [CC EE!
MADE intrinsic reward is also proportional to // dd (s, a). which can be viewed as a correction applied the count-based bonus. In effect, due to the decay of weights in m the above construction gives a higher reward to (s, a) pairs visited earlier. Experimental results suggest that this correction may alleviate major difficulties in sparse reward exploration, namely detachment and catastrophic forgetting, by encouraging the agent to revisit forgotten states and actions.
Empirically, MADE's intrinsic reward is computed based on estimates d and p from data collected by iteration k. Furthermore, practically consider smoothed version of the above regularizer by adding X >> O to both numerator and denominator; see Equation
MADE intrinsic reward in tabular case. In tabular empirical setting, the empirical estimation of policy cover simply Pt.. (s, a) Ne(e.e) where N& a) is (s, a) pair's visitation count and N& is the total count, by iteration k. Setting & = 1/VN,, MADE simply modifies the Hoeffding- tyype bonus via the mixture density and is proportional to 1/ dd (s, (s.
N₂
Bemnstein bonus is another tabular UCB bonus that modifies Hoeffding bonus via an empirical estimate of the value function variance. Bernstein bonus is shown to improve over Hoeffding count-only bonus by exploiting additional environment structure [166] and close the gap between algorithmic
upper bounds and information-theoretic limits up to logarithmic factors [12 [K3] However, a practical and efficient implementation of a bonus that exploits variance information in non-linear function approximation parameterization still remains an open question; see Section 6 for further discussion. On the other hand, our proposed modification based on the mixture density can be easily and efficiently incorporated with non-linear parameterization.
Deriving some popular bonuses from regularization. The regularization in can describe some popular bonuses. Exploration bonuses that only depend on state-action visitation counts can be expressed in the form by setting the regularizer linear function of d= and the exploration bonus ri(s, a), i.e., R2 (d"; {d 1/=) - d" (s, ()r,(s,a)))))))) a). One can check that taking the gradient of the regularizer with respect to d recovers ri(s, a). As another example, one can set the regularizer to Shannon entropy R₁ (d";; {d 1) = E.e d= (s, a) log d' (s, a), which gives the intrinsic reward
log d' (s, a) (up to additive constant) and recovers the result in Zhang et al. [109]

---

Algorithm Policy computation for adaptively regularized objective
1: Inputs: Iteration count K, planning error Ep. visitation density error edt
2: Initialize policy mixture Tmix,1 = with C = (TT) and w² (1)
3: for k k= =......44 K do
4: Estimate the visitation density d of A via visitation density oracle.
5: Compute reward rs(s,a) r(s, + (1 - 7) VaRg (d: { mix.
6: Run approximate planning on modified MDP M (S, P,rk, 7) and return Th+1-
7: Update policy mixture Ck+1 (Ck, mx++1) and w ((1 n) .n).
8: Return:
T = (C*, )
3.3 Solving the regularized objective
Recall that our goal to find a policy that maximizes the regularized objective arg arg max (x(d))= = J(d)) + Tx R(d"; {d + Despite being nonconcave in æ, this objective is concave in d=. Therefore, one can solve the following constrained concave optimization problem instead: max ev LA (d=), where V is the set of all valid visitation densities.
To solve this constrained optimization problem, use the conditional gradient method the Frank- Wolfe algorithm BII, which has been used in the context of RL in works such as 36 JI [05]. The con- ditional gradient method involves iteratively solving dd arg max, (d, La =a===a and obtaining d from a weighted combination of d and 1 Note that the first step is equivalent planning via reward function proportional to Va La (dd) =d= which justifies they way we computed the total reward in Equation 5
We provide convergence guarantee for Algorithm T in the following theorem whose proof is given in Appendix A.
Theorem 1. Consider the following regularizer for with > and a valid visitation density d
Rx(d; (d
Σ
d(s, a) +
Fi=1
Pen ( +
Set Th =T/K", where O < < and > 0. For any e > 0 and n < 0.4cX2. 2 there exists Eps Ed, c, B such that T returned by Algorithm I after K 2 log(10Be iterations satisfies (dddaaii.)) ..). 2 max, Lg ( e.
Remark 1. One does not need maintain the functional forms of past policies estimate minik Practically, may truncate the dataset to a (prioritized) buffer and estimate the density over that.
4 A tabular study
We first study the performance of MADE in tabular toy examples. In the Bidirectional Lock experiment, we compare MADE to theoretically guaranteed Hoeffding-style and Bernstein-style bonuses in a sparse reward exploration task. In the Chain MDP, we investigate whether MADE's regularizer provides any benefits in improving optimization rate in policy gradient methods.
valto
G Qebemming
bidirectional lock
0.1
0.1
0.1
0.1
01.0
0.D
2
0.00
0.25
1U.0
0.76
1.20
CANTOOULDEE Stop
covpponmnctt stop
>110"
CoriooatOn stop
x10P
BadBlnng
Burzatión
MADE
In bidirectional lock, the agent starts 8o and enters of the chains based on the selected action. Each chain has a positive reward at the end, good states, and H dead states. Both actions available to the agent lead it to the dead state, one with probability one and the other with probability p < 1. MADE performs better than Hoeffding-styy style bonus and comparable to Bernstein-style bonus across all three RL algorithms.
Figure 2:
5

---

good states
dead states
Hordding
Berustein
MADE [ours]
steps
Hoofiding
Bernstein
MADE
Figure 3: Hoeffding, Bernstein, and MADE intrinsic rewards over iterations bidirectional lock.
4.1 Exploration in bidirectional lock
We consider a stochastic version of the bidirectional combination lock (Figure D. which is considered particularly difficult exploration task in tabular setting 666 3]. This environment is challenging because: (1) positive rewards are sparse, (2) a small negative reward is given when transiting to good state and thus, moving to dead state locally optimal, and (3) the agent may forget to explore one chain and get stuck in local minima upon receiving an end reward in one lock K
RL algorithms and exploration strategies. We compare the performance Hoeffding and Bern- stein bonuses 44 to MADE in three different RI. algorithms. To implement MADE in tabular setting, we simply use two buffers: one that stores all past state-action pairs to estimate Poor and another one that only maintains the most recent B pairs to estimate dz. We use empirical counts to estimate
both densities, which give a bonus x 1/VNN NN,(s, a Bx as, where N& a) is the total count and (s,s, a) is the recent buffer count of (s, a) pair. We combine three bonuses with three RL algorithms:
(1) value iteration with bonus 37 (2) proximal policy optimization (PPO) with a model [16], and
(3) Q-learning with bonus
47
Results. Figure Souure2sumce summarizess our results showing MADE improves over the Hoeffding bonus and competitive the Bernstein bonus in all three algorithms. Unlike Bernstein bonus that hard to compute beyond tabular setting. MADE bonus design is simple and can be effectively combined with any deep RL algorithm. The experimental results suggest several interesting properties for MADE. First, MADE applies simple modification to the Hoeffding bonus which improves the performance. Second, illustrated in Figure bonus values and exploration pattern of MADE somewhat similar to the Bernstein bonus. This suggests that MADE may capture some structural information of the environment, similar to Bernstein bonus, which captures certain environmental properties such as degree of stochasticity [106].
4.2 Policy gradient in chain MDP
We consider the chain MDP (Figure presented in 2 which suffers from vanishing gradients with policy gradient approach [X]] as positive reward is only achieved if the agent always takes action a1- This leads an exponential iteration complexity lower bound on the convergence of vanilla policy
Policy gradient on
02
d1
0.0
0.5
itocations
1
PG-RE
PG+E
PG-MADEE
Figure 4: deterministic chain MDP that suffers from vanishing gradients 2 We consider
constrained tabular policy parameterization with (als) 0s.a and En On,a 1. The agent always starts from Sn and the only non-zero reward r(8H+1, 01)

---

gradient approach even with access to exact gradients [2. In this environment the agent always starts state So and recent guarantees on the global convergence of exact policy gradients are vacuous This is because the rates depend on the ratio between the optimal and learned visitation or the ratio between the optimal 32 82
M
2
62
densities, known as concentrability coefficient visitation density and initial distribution 2
RL algorithms. Since goal in this experiment is to investigate the optimization effects and not exploration, we assume access to exact gradients. In this setting, we consider MADE regularizer with the form >., (d a). Note that policy gradients take gradient of the objective with respect to the policy parameters 0 and not d". We compare optimizing the policy gradient objective with four
methods: vanilla version PG (e.g. uses policy gradient theorem 99 93 53) ). relative policy entropy regularization PG+RE
22 policy entropy regularization PG+E
67 62
and MADE regularization.
Results. Figure g illlstrates our results on policy gradient methods. As expected [2]. the vanilla version has a very slow convergence rate. Both entropy and relative entropy regularization methods are proved to achieve linear convergence rate of exp(-() in the iteration count / 62 2 Interestingly, MADE seems to outperforms the policy entropy regularizers, quickly converging to globally optimal policy.
Experiments on MiniGrid and DeepMind Control Suite
In addition to the tabular setting, MADE can also be integrated with various model-free and model- based deep RL algorithms such as IMPALA 225] RAD [57], and Dreamer [35. As we will see
shortly, MADE exploration strategy on MiniGrid 19] and DeepMind Control Suite 955 tasks
achieves state-of-the-ar sample efficiency.
For practical estimation of Peov and dm we adopt the two buffer idea described in the tabular setting. However, since now the state space is high-dimensional, we use RND [5] to estimate N& (s, a) (and thus p(.)) and use a variational auto-encoder (VAE) to estimate dd Specifically, for RND, we minimize the difference between a predictor network o' (s, a) and randomly initialized target network Φ(s, a) and train it in an online manner as the agent collects data. We sample data from the recent buffer B to train VAE. The length of ablation study. Thus, the intrinsic reward in deep RL setting takes the following form
design choice for which we do an
[|0(, a) ds(s,a)))
TM
v mmix (8.a)
MAAE
KM
IIND
R12E
ANKO
BiBokl
1.00
1.50
MrP-Room-4P-00
1.00
KrF-Room-11-44
1.00
KeyCordderCRR
7007000 Recum
Aoeeage Ruturn
0.75
0.75
0.25
0.25
0.25
0.25
0.00
0.30
0.00
0.00
167
EeyCarster00
167
KeySoosser58tt
187
167
Demggeee Retum Reeum
0.75
0.75
0.52
0.50
Anerage
0.50
0.30
0.25
1.00
1.50
1.00
1.00
ClairactedNeaa-ful
Regrog Rocum
Koenage Setum
0.22
0.75
0.25
Rvenge
0.25
0.25
0.35
0.00
0.20
0.00
0.00
Environment Stops
167
Enviormmett Stops
1n7
Enviroomere Staps
1x7
Envronment Stops 197
Figure Results for various hard exploration tasks from MiniGrid. MADE successfully solves all the environments while other algorithms (except for BeBold) fail to solve several environments. MADE finds the optimal solution with 2-5 times fewer samples, yielding much better sample efficiency.
7

---

R6O
cartooii
Chestal Stune
booser
Avocapp Netum
620
Retum
303
120
920
203
Roorge
200
100
penduam
cuadruped
1050
820
-00-
Auseoge
202
Envitommntt Stops
140
Envronment Stops
Envirrment Staes
105
Figure 6: Results for several DeepMind control suite locomotion tasks. Comparing to all baselines, the performance of MADE is consistently better. Sometimes baseline methods even fail solve the task.
Model-free RL baselines. We consider several baselines in MiniGrid: IMPALA 25 is a variant of policy gradient algorithms which we use as the training baseline; ICM 76 learns a forward and reverse model for predicting state transition and uses the forward model prediction error as intrinsic reward; RND [15) trains predictor network to mimic a randomly initialized target network as discussed above; RIDE 8T learns representation similar to ICM and uses the difference of learned representations along a trajectory as intrinsic reward; AMIGo 17 learns a teacher agent to assign intrinsic reward; BeBold [ adopts a regulated difference of novelty measure using RND. In DeepMind Control Suite, we consider RE3 [6 as a baseline which uses a random encoder for state embedding followed by a k-nearest neighbour bonus for a maximum state coverage objective.
Model-based RL baselines. MADE can be combined with model-based RI. algorithms to improve sample efficiency. For baselines, we consider Dreamer, which is well-known model-based RL algorithm for DeepMind Control Suite, as well as Dreamer+RE3 which includes RE3 bonus on top of Dreamer.
MADE achieves state-of-the-art results on both navigation and locomotion tasks by a substantial margin, greatly improving the sample efficiency of the RL exploration in both model-free and model-based methods. Details on experiments and hyperparameters are provided in Appendix B.
5.1 Model-free RL on MiniGrid
MiniGrid [9 is widely used benchmark for exploration in RL. Despite having symbolic states and a discrete action space, MiniGrid tasks are quite challenging. The easiest task is MultiRoom (MR) in which the agent needs to navigate to the goal by going to different rooms connected by the doors. In KeyCorridor (KC), the agent needs to search around different rooms to find the key and then use it to open the door. Obstructed.Maze (OM) is harder version of KC where the key is hidden in box and sometimes the door is blocked by an obstruct. In addition to that, the entire environment is pocedurally-geeeeaan
This adds another layer of difficulty to the problem.
From Figure 5 we can see that MADE manages to solve the challenging tasks within 90M steps while all other baselines (except BeBold) only solve up to 50% of them. Compared to BeBold, MADE uses significantly (2-5 times) fewer samples.
5.2 Model-free RL on DeepMind Control
We also test MADE on image-based continuous control tasks of DeepMind Control Suite 95 which is a collection of diverse control tasks such as Pendulum, Hopper, and Acrobot with realistic simulations. Compared to MiniGrid, these tasks are more realistic and complex they involve stochastic transitions, high-dimensional states, and continuous actions. For basclines, we build our algorithm on top of RAD [57]. strong model-free RL algorithm with competitive sample efficiency. We compare our approach with ICM, RND, as well as RE3, which is the SOTA algorithm Fl Note that we compare MADE very strong baselines. Other algorithms such DrQ (44 CURL (9)
ProtoRL [104), SAC+AE HOX)) ) perform worse based on the results reported in the original papers.
As we were not provided with the source code, we implemented ICM and RND ourselves. The performance for ICM is slightly worse than what the author reported, but the performance of RND and RE3 is similar.
8

---

Cartaoric BUE-120
MADE
Luf-150005
Chestal
booser
600-
-.00
200
220
105
1n5
Figure 7: Ablation study on buffer size in MADE. The optimal buffer size varies in different tasks. We found
that a buffer size of 10000 empirically works consistently reasonable.
carpolo, Swingup Sp3rSE
Cheetah run sporse
hoaser hop
820
Reaum
620
Recurrs
0.00
200
candulam
cuadruped
1020
Accagee Moym
750
400
-20
220
Enuimomentt
Stepe
Ensiromment
Stope
Enderement Stape
145
Figure 8: Results for DeepMind control suite locomotion tasks in model-based RI. setting. Comparing all baselines, the performance MADE consistently hetter. Some baseline methods even fail solve the task.
MADE show consistent improvement in sample efficiency: 2.6 times over RAD+RE3, 3.3 times over RAD+RND, 19.7 times over CURL, 15.0 times over DrQ and 3.8 times over RAD.
From Figure i we can see that MADE consistently improves sample efficiency compared to all base- lines. For these tasks, RND and ICM do not perform well and even fail achieves a comparable performance in two tasks, however, its performance on Pendul um um-Swingup. Quadruped- Run, Hopper-Hie Hop and Walker-Rui Swingup. MADE achieves reward of around 800 in only 30K steps while RE3 requires 300k samples. In Quadruped-Rie Runn, there a 150 reward gap between MADE and RE3, which seems to be still enlarging. These tasks show the strong performance of MADE in model-free RL.
Sertpole-Swingup. RE3
significantly worse than MADE. For example, in
Ablation study. We study how the buffer length affects the performance of our algorithm some DeepMind Control tasks. Results show that for different tasks the optimal length is slightly different. We empirically found that using a buffer length of 1000 consistently works well across different tasks.
5.3 Model-based RL on DeepMind Control
We also empirically verify the performance of MADE combined with the SOTA model-based RL algorithm Dreamer 35 We compare MADE with Dreamer and Dreamer combined with RE3 in Figure g Results show that MADE has great sample efficiency maps like Cheetah- Sean---Rnn-Saaaana Hopper-Hop and Pendul Sanlllu-Swwtt -wm-wwnnup. For example, in Hopper-Hop, MADE achieves more than 100 higher return than RE3 and 250 higher than Dreamer, achieving new SOTA result.
Related work
Provable optimistic exploration. Most provable exploration strategies are based on optimism in the face of uncertainty (OFU) principle. In tabular setting, model-based exploration algorithms
include variants of UCB 550
12 UCRL [56 41 106
49
64 and Thompson sampling [1O 5 [
98 90 60, (55 and ialue-iteration with UCB 180211111 45 These methods are recently extended to linear MDP setting leading to variety
and value-based methods include optimistic Qeleamnig
of model-based Going beyond linear function approximation, systematic exploration strategies are developed based on structural assumptions on MDP such as low Bellman rank
[15, value-based 197 Add and policy-based algorithms [16. [0S] B.
4K and block MDP (22). These
methods are either computationally intractable 4K 91
96 or only oracle efficient

---

26 4.. The recent work (27 provides a sample efficient approach with non- policies, however, the algorithm requires maintaining the functional form of all prior policies.
Practical exploration via intrinsic reward. Apart from previously-diseuseee methods. other works give intrinsic reward based on the difference (abstraction of) consecutive states [TT (1 However, this approach is inconsistent: the intrinsic reward does not converge to zero and thus, even with infinite samples, the final policy does not maximize the RL objective. Other intrinsic rewards try to estimate pseudo-counts [10
inspired by provable count-based methods. Though favoring novel states, practically these methods might suffer from detachment and
94 15 75
derailment 23 24,, and forgetring 3] More recent works propose combination of different criteria.
RIDE 81 learns a representation using curiosity criterion and uses the difference of consecutive states along the trajectory as the bonus. AMIGo [1 learns teacher agent for assigning rewards for exploration. Go-Explore [23] explicitly decouples the exploration and exploitation stage, yields a more sophisticated algorithm with many hand-tuned hyperparameters. Prior work also tries add bonus on maximizing the KL-divergence between the current policy and the previous policies [39] However, we emphasize that this is indeed an entirely different principle compared with ours, simply because difference of visitation density of the policies is not equivalent to the KL-divergence between policies. In another word, two significantly different policies do not necessarily induce significantly different visitation densities and vice versa.
Maximum entropy exploration. Another line of work encourages exploration via maximizing some type of entropy. One category maximizes policy entropy 667 or relative entropy [2] in addition to the RL objective. The work (28] modifies the RL objective by introducing an adversarial policy which results in the next policy to move away from prior policies while staying close to the current policy. In contrast, our approach focuses on the regions explored by prior policies as opposed to the prior policies themselves. Recently, effects of policy entropy regularization have been studied In policy gradient methods with access to exact gradients, policy entropy regularization results in faster convergence by improving the optimization landscape [62 66] [8]
theoretically 722 3
Another category considers maximizing the entropy of state or state-action visitation densities such as or Rényi entropy [09]. Empirically, our approach achieves better performance over entropy-based methods.
Shannon entropy [6 40 58 Xo
Other exploration strategies. Besides intrinsic motivation, other strategies are also fruitful in encouraging the RL agent to visit a wide range of states. One example is exploration by injecting noise to the action action space [59 E
[4] or parameter space [BC (78). Another example is the
reward-shaping category. in which diverse goals are set to guide exploration 20
7 Discussion
We introduce a new exploration strategy MADE based on maximizing deviation from explored regions. We show that by simply adding a regularizer to the original RL objective, we get an easy-to- implement intrinsic reward which can be incorporated with any RL algorithm. We provide a policy computation algorithm for this objective and prove that it converges to a global optimum, provided that we have access to an approximate planner. In tabular setting, MADE consistently improves over the Hoeffding bonus and shows competitive performance to the Bernstein bonus, while the latter is impractical to compute beyond tabular. We conduct extensive experiments on MiniGrid, showing significant (over 5 times) reduction of the required sample size. MADE also performs well in DeepMind Control Suite when combined with both model-free and model-based RL algorithms, achieving SOTA sample efficiency results. One limitation of the current work is that it only uses the naive representations of states (e.g., one-hot representation in tabular case). In fact, exploration could be conducted much more efficiently if MADE is implemented with a more compact representation of states. We leave this direction to future work.
Acknowledgements
The authors are grateful to Andrea Zanette for helpful discussions. The authors thank Alekh Agarwal, Michael Henaff, Sham Kakade, and Wen Sun for providing their code. Paria Rashidinejad is partially supported by the Open Philanthropy Foundation, Intel, and the Leverhulme Trust. Jiantao Jiao is partially supported by NSF grants IIS- 1901252, CCF-1909499, and DMS-2023505. Tianjun Zhang is supported by the BAIR Commons at UC-Berkeley and thanks Commons sponsors for their support. In
10

---

addition to NSF CISE Expeditions Award CCF-1730628 UC Berkeley research is supported by gifts from Alibaba, Amazon Web Services, Ant Financial, CapitalOne, Ericsson, Facebook, Futurewei, Google, Intel, Microsoft, Nvidia, Scotiabank, Splunk and VMware.
References
[1] Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-first international conference on Machine learning, page 1, 2004.
[2] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. arXiv preprins arXiv:/908.0002 2019.
[3] Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. PC-PG: Policy cover directed exploration for provable policy gradient learning. arXiv preprint arXiv:2007.0855) 2020.
[4] Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank MDPs. arXiv preprint arXiv:2006.10814, 2020.
[5] Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: Worst-case regret bounds. In Proceedings of the 31st International Conference Neural Information Processing Systems, pages 1184-1194, 2017.
[6] Zafarali Ahmed, Nicolas Le Roux, Mohammad Norouzi, and Dale Schuurmans. Understanding the impact of entropy policy optimization. In International Conference on Machine Learning, pages 151-160. PMLR, 2019.
[7] Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based rein- forcement learning with valge-targeted regression. In International Conference Machine Learning, pages 463-474, PMLR, 2020.
[8] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272.
PMLR, 2017.
[9] Adrià Puigdomènech Badia, Pablo Sprechmann, Alex Vitvitskyi. Daniel Guo, Bilal Piot, Steven Kapturowski, Olivier Tieleman, Martín Arjovsky, Alexander Pritzel, Andew Bolt, et al. Never give up: Learning directed exploration strategies. arXiv preprint arXiv:2002.06033 2020.
[10] Marc Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying bount-based exploration and intrinsic motivation. In Advances in neural information processing systems, pages 1471-1479, 2016.
[11] Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint arXiv: 1eo::/906007866 2019.
[12] Ronen Brafman and Moshe Tennenholtz. R-max: A general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research, 300231 2002.
[13] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schncider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint
2016.
[14] Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A Efros. Large-scale study of curiosity-driven learning. arXiv preprint arXiv:1808. 04355, 2018.
[15] Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprint arXiv: 12894, 2018.
[16] Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pages 1283-1294, PMLR, 2020.
11

---

[17] Andres Campero, Roberta Raileanu, Heinrich Küttler, Joshua B Tenenbaum, Tim Rocktäschel, and Edward Grefenstette. Learning with AMIGo: Adversarially motivated intrinsic goals. arXiv preprint arXiv:2006. /2/22, 2020.
[18] Shicong Cen, Chen Cheng. Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. arXiv preprint x08x:20007.065588 2020.
[19] Maxime Chevalier-Boisverd Lucas Willems, and Suman Pal. Minimalistic gridworld environ- ment for OpenAI Gym.
2018.
[20] Cédric Colas, Pierre Fournier, Mohamed Chetouani, Olivier Sigaud, and Pierre-Yve Oudeyer. CURIOUS: Intrinsically motivated modular multi-goal reinforcement learning. In International conference on machine learning, pages 1331- PMLR, 2019.
[21] Kefan Dong, Jiaqi Yang, and Tengyu Ma. Provable model- nonlinear bandit and reinforce- ment learning: Shelve optimism, embrace virtual curvature. arXiv preprint arXiv:2102. 102.04 2021.
[22] Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient RL with rich observations via latent state decoding. In Interna- tional Conference Machine Learning, pages 1665-1674. PMLR, 2019.
[23] Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Go-explore: A new approach for hard-exploration problems. arXiv preprint arXiv: 1901.1095,, 2019.
[24] Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. First return then explore. arXiv preprint 2ttp::0004.299191 2020.
[25] Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Volodymir Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, et al. Impala: Scalable distributed deep- RL with importance weighted actor-learnr architectures. arXiv preprint arXiv: vrXiiv1882.000 1802.01561.. 0156, 2018.
[26] Fei Feng, Ruosong Wang. Wotao Yin, Simon S Du, and Lin Yang. Provably efficient explo- ration for reinforcement learning using unsupervised learning. Advances in Neural Information Processing Systems, 33, 2020.
[27] Fei Feng, Wotao Yin, Alekh Agarwal, and Lin Yang. Provably correct optimization and exploration with non-linear policies. arXiv preprint arXiv:2 /559, 2021.
[28] Yannis Flet-Berliac, Johan Ferret, Olivier Pietquin, Philippe Preux, and Matthieu Geist. Adversarially guided actor-critic. In International Conference on Learning Representations, 2021.
[29] Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel. Automatic goal generation for reinforcement learning agents. In International conference on machine learning, pages 1515-1528. PMLR, 2018
[30] Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Osband, Alex Graves, Vlad Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, et al. Noisy networks for exploration. International Conference on Learning Representations, 2018.
[31] Marguerite Frank, Philip Wolfe, et al. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95-110, 1956.
[32] Matthieu Geist, Bilal Piot, and Olivier Pietquin. Is the Bellman residual a bad proxy? In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 3208-30--000 3217, 2017.
[33] Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized Markov decision processes. In International Conference on Machine Learning, pages 2160-2169. PMLR, 2019.
[34] Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. arXiv preprint wxXiv:161.00707.. 2016.
12

---

[35] Danijar Hafner, Timothy Lillicrap, Jimmy Ba, and Mohammad Norouzi. Dream to control: Learning behaviors by latent imagination. arXiv preprint 1rXiv:1912.01603, 2019.
[36] Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. In International Conference on Machine Learning, pages 2681 1-911, 2019.
[37] Jiafan He, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for discounted MDPs. arXiv preprint arXiv:2010.00587 2020.
[38] Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. arXiv preprint arXiv: 2017.
[39] Zhang-Waz Wei Hong, Tzu- Yun Shann, Shih- Yang Su, Yi-Hsiang Chang. and Chun-Yi Lee. Diversity-driven exploration strategy for deep reinforcement learning. arXiv preprini arXiv:/802.04555 2018
[40] Riashat Islam, Zafarali Ahmed, and Doina Precup. Marginalized state distribution entropy regularization in policy optimization. arXiv preprint arXiv: 2019.
[41] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4), 2010.
[42] Zeyu Jia, Lin Yang, Csaba Szepesvari, and Mengdi Wang. Model- based reinforcement learning with value-targeted regression. In Learning for Dynamics and Control, pages 666-686. PMI.,, 2020.
[43] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contextual decision processes with low Bellman rank are PAC-learnable. In International Conference on Machine Learning, pages 1704-1713. PMLR, 2017.
[44] Chi Jin, Zeyuan Aluen-Zhu, Sebastien Bubeck, and Michael Jordan. Is Q-learning provably efficient? In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 4868-4878, 2018
[45] Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages 4870- 4879. PMLR, 2020.
[46] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR, 2020.
[47] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proc. 19th International Conference on Machine Learning. Citeseer, 2002.
[48] Sham Kakade, Mengdi Wang, and Lin Yang. Variance reduction methods for sublinear 2018.
reinforcement learning. arXiv preprint
[49] Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward- exploration. In Algorithmic Learning Theory, pages 865-891. PMLR, 2021.
[50] Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine learning, 49(2):209-232. 2002.
[51] Hyoungseok Kim, Jackyeom Kim, Yeonwoo Jeong, Sergey Levine, and Hyun Oh Song. Emi Exploration with mutual information. arXiv preprint 1rXiv:1810.01176 2018.
[52] Alexander S Klyubin, Daniel Polani, and Chrystopher L Nehaniv. All else being equal be empowered. In European Conference on Artificial Life, pages 744-753. Springer, 2005.
[53] Vijay R Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances neural informa- tion processing systems, pages 1014. Citeseer, 2000.
13

---

[54] Ilya Kostrikov, Denis Yarats, and Rob Fergus. Image augmentation is all you need: Regulariz- ing deep reinforcement learning from pixels. arXiv preprint arXiv:2004. 1,000 2020.
[55] Michael Laskin, Kimin Lee, Adam Stooke, Lerrel Pinto, Pieter Abbeel, and Aravind Srinivas. Reinforcement learning with augmented data. arXiv preprint arXiv:2004. 14990, 2020.
[56] Tor Lattimore and Marcus Hutter. PAC bounds for discounted MDPs. In International Conference on Algorithmic Learning Theory, pages 320-334. Springer, 2012.
[57] Kimin Lee, Kibok Lee, Jinwoo Shin, and Honglak Lee. Network randomization: A simple technique for generalization in deep reinforcement learning. arXiv preprint 1910005399 2019.
[58] Lisa Lee, Benjamin Eysenbach, Emilio Parisotto, Eric Xing, Sergey Levine, and Rus- lan Salakhutdinov. Efficient exploration via state marginal matching. arXiv preprini 1rXi::9906005274, 2019.
[59] Timothy P Lillicrap. Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint
2015.
[60] Shuang Liu and Hao Su. Regret bounds for discounted MDPs. arXiv:2000.051:88 2020.
arXiv preprint
[61] Kenneth Marino, Abhinav Gupta, Rob Fergus, and Arthur Szlam. Hierarchical RL using ensemble of proprioceptive periodic policies. In International Conference on Learning Representations, 2019. URL httpps://oppnrreiiieet
[62] Jincheng Mci, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global con- vergence rates of softmax policy gradient methods. In International Conference Machine Learning, pages 6820-6829. PMLR, 2020.
[63] Jincheng Mei, Yue Gao, Bo Dai, Csaba Szepesvari, and Dale Schuurmans. Leveraging non-uniformity in first-order non-convex optimization. arXiv preprint 11X:v22105.06072, 2021.
[64] Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. arXiv preprint arXiv: 13442, 2020.
[65] Pierre Menard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. UCB mo- mentum Q-learning: Correcting the bias without forgetting. arXiv preprint 103002210 2021.
[66] Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstraction and provably efficient rich-observation reinforcement learning. In International conference machine learning, pages 6961-666 1671. PMLR, 2020.
[67] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lilli- crap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference machine learning, pages 1928 1928-1937, 2016.
[68] Shakir Mohamed and Danilo Jimenez Rezende. Variational information maximisation for intrinsically motivated reinforcement learning. In Advances neural information processing systems, pages 2125-2133, 2015.
[69] Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisy, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508-57) 513, 2017.
[70] Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Bridging the gap be- tween value and policy based reinforcement learning. In Proceedings of the 3 International Conference on Neural Information Processing Systems, pages 2772-2783 2017.
14

---

[71] Ashvin V Nair, Vitchyr Pong, Murtaza Dalal, Shikhar Bahl, Steven Lin, and Sergey Levine. Visual reinforcement learning with imagined goals. Advances in Neural Information Processing Systems, 31:9191-9200, 2018.
[72] Gergely Neu, Anders Jonsson, and Vicenç Gómez. A unified view of entropy intropy-regularizee Markov decision processes. arXiv preprint wrxiv:/705.077990 2017.
[73] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped DQN, In Advances in neural information processing systems, pages 4026-4034, 2016.
[74] Ian Osband, Benjamin Van Roy, Daniel J Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124):1-62, 2019.
[75] Georg Ostrovski, Marc G Bellemare, Aaron van den Oord, and Rémi Munos. Count-based exploration with neural density models. arXiv preprint arXiv: 1703001300, 2017.
[76] Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driver explo- ration by self- supervsu prediction. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pages 16-17, 2017.
[77] Deepak Pathak, Dhiraj Gandhi, and Abhinav Gupta. Self-supervised exploration via disagree- ment. arXiv preprint arXiv: 04161, 2019.
[78] Matthias Plappert, Rein Houthooft, Prafulla Dhariwal, Szymon Sidor, Richard Y Chen, Xi Chen, Tamim Asfour, Pieter Abbeel, and Marcin Andrychowicz. Parameter space noise for exploration. International Conference on Learning Representations, 2018.
[79] Vitchyr Pong, Murtaza Dalal, Steven Lin, Ashvin Nair, Shikhar Bahl, and Sergey Levine Skew-Fit: State-covering self-supervised reinforcement learning. In International Conference on Machine Learning, pages 7783-7792. PMLR, 2020.
[80] Martin L Puterman. Markov decision processes. Handbooks in operations research and management science, 2:33 1-444, 1990.
[81] Roberta Raileanu and Tim Rocktäschel. Ride: Rewarding impact-driven exploration for procedurally--enenaa environments. arXiv preprint arXiv:2002. 12292, 2020.
[82] Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. arXiv preprint arXiv:2103. 2021.
[83] Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. arXiv preprint arXiv:1906.0222 02870, 2019.
[84] Christoph Salge, Cornelius Glackin, and Daniel Polani. Empowerment: An introduction. In Guided Self- relf-Organization: Inception, pages 67-114. Springer, 2014.
[85] Bruno Scherrer. Approximate policy iteration schemes: A comparison. In International Conference on Machine Learning, pages 1314-1322. PMLR, 2014.
[86] Younggyo Seo, Lili Chen, Jinwoo Shin, Honglak Lee, Pieter Abbeel, and Kimin Lee. State entropy maximization with random encoders for efficient exploration. arXiv preprint arXiv:2102.09430, 2021.
[87] Pranav Shyam, Wojciech Jaskowski, and Faustino Gomez. Model-based active exploration. In International Conference Machine Learning, pages 5779-5788 2019.
[88] David Silver, Julian Schritwieserr, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of Go without human knowledge. nature, 550(7676):554-39) 2017.
[89] Aravind Srinivas, Michael Laskin, and Pieter Abbeel. Curl: Contrastive unsupervised repre- sentations for reinforeement learning, arXiv preprint arXi::2004.041356 2020.
15

---

[90] Alexander L Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman. PAC model-free reinforcement learning. In Proceedings of the 23rd international conference on Machine learning, pages 881-888 2006.
[91] Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model- based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Conference on Learning Theory, pages 2898-2933. PMLR, 2019.
[92] Richard S Sutton and Andrew Barto. Reinforcement learning: An introduction. MIT press, 2018.
[93] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Proceedings of the 12th International Conference on Neural Information Processing Systems, pages 1057-1063, 1999.
[94] Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAl Xi Chen, Yan Duan, John Schulman, Filip DeTurck, and Pieter Abbeel. #Exploration: A study of count-based exploration for deep reinforcement learning. In Advances in neural information processing systems, pages 2753-2762, 2017.
[95] Yuval Tassa, Saran Tunyasuvunakool, Alistair Muldal, Yotam Doron, Piotr Trochim, Siqi Liu, Steven Bohez, Josh Merel, Tom Erez, Timothy Lillicrap, et al. dm_control: Software and tasks for continuous control. arXiv preprint arXiv:2006. 12983, 2020.
[96] Ruosong Wang, Russ R Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded Eluder dimension. Advances in Neural Information Processing Systems, 33, 2020.
[97] Yining Wang, Ruosong Wang, Simon S Du, and Akshay Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint 19Xiv:1912.04135 136, 2019.
[98] Yuanhao Wang, Kefan Dong, Xiaoyu Chen, and Liwei Wang. Q-learning with UCB explo- ration is sample efficient for infinit--horizon MDP. In International Conference on Learning Representations, 2019.
[99] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist rein- forcement learning. Machine learning, 8(3-4):229-25) 256, 1992.
[100] Ronald J Williams and Jing Peng. Function optimization using connectionist reinforcement learning algorithms. Connection Science, 3(3):441-268, 1991.
[101] Zhihan Xiong, Ruoqi Shen, and Simon Du Randomized exploration is near-optimal for tabular MDP. arXiv preprint arXiv:2 2021.
[102] Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael I Jordan. Bridging exploration and general function approximation in reinforcement learning: Provably efficient kernel and neural value iterations. arXiv preprint arXiv:2011.04622 2020.
[103] Denis Yarats, Amy Zhang, Ilya Kostrikov, Brandon Amos, Joelle Pineau, and Rob Fergus. Improving sample efficiency in model-free reinforcement learning from images. arXiv preprint arXiv:1910.01741, 2019.
[104] Denis Yarats, Rob Fergus. Alessandro Lazaric, and Lerrel Pinto. Reinforcement learning with prototypical representations. arXiv preprint arXiv:2102. 12271, 2021.
[105] Tom Zahavy, Alon Cohen, Haim Kaplan, and Yishay Mansour. Apprenticeship learning via frank-wolfe. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pages 6720-6728, 2020.
[106] Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforce- ment learning without domain knowledge using value function bounds. International Conference on Machine Learning, pages 7304-7312. PMLR, 2019.
16

---

[107] Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent Bellman error. In International Conference on Machine Learning, pages 10978-10989, PMLR, 2020.
[108] Andrea Zanette, Ching-Ar An Cheng, and Alekh Agarwal. Cautiously optimistic policy optimiza- tion and exploration with linear function approximation. arXiv preprint arXiv:2103. 12923, 2021.
[109] Chuheng Zhang, Yuanying Cai, and Longbo Huang Jian Li. Exploration by maximizing Rényi entropy for reward-free RL framework. Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[110] Jingwei Zhang, Niklas Wetzel, Nicolai Dorka, Joschka Boedecker, and Wolfram Burgard. Scheduled intrinsic drive: A hierarchical take on intrinsically motivated exploration. arXiv preprint arXiv:1903.074000 2019.
[111] Tianjun Zhang, Huazhe Xu, Xiaolong Wang, Yi Wu, Kurt Keutzer, Joseph E Gonzalez, and Yuandong Tian. BeBold: Exploration beyond the boundary of explored regions. arXiv preprint arXiv:2012.08622 2020.
[112] Zihan Zhang, Xiangyang Ji, and Simon S Du. Is reinforcement learning more difficult than ban- dits? near-optimal algorithm escaping the curse of horizon. arXiv preprint arXiv:2009. 13503, 2020.
[113] Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference- advantage decomposition. Advances in Neural Information Processing Systems, 33, 2020.
[114] Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture Markov decision processes. arXiv preprint arXiv:2012.08507 2020.
[115] Dongruo Zhou, Jiafan Hc, and Quanquan Gu. Provably efficient reinforcement learning for discounted MDPs with feature mapping. arXiv preprint arXiv:2006.13166 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We claim to propose efficient exploration criterion that achieves strong results. The experiments conducted in MiniGrid, and DeepMind Control.
(b) Did you describe the limitations of your work? Discussion section.
[Yes] We discuss limitations in the
(c) Did you discuss any potential negative societal impacts of your work? [No] We do not foresee any obvious negative societal impacts from our work, which contributes peneral-purpose exploration algorithm.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results....
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We state the full set assumptions
(b) Did you include complete proofs of all theoretical results? [Yes] The complete proof is in Appendix.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as a URL)? [Yes] We upload the code in supplemental material.
17

---

(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We include the training detail in supplemental material.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] We include the error bars for experiments.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'le using/curating? [No] We use publicly available datasets/tasks.
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [No] We don't use data this sort.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
18


Reviews:
[{"review_id": "pJu8-C7zLbx", "reviewer": "Reviewer_Xa1c", "summary": "The paper proposes an alternative exploration strategy by MAximizing the DEviation (MADE) of the next policy from explored regions of prior policies by adding an adaptive regularizer (function of state-action visitation counts) to the primary RL objective at each iteration to balance between exploration the new state space and exploit the visited states.  In addition, MADE has been theoretically proven to converge to the global optimum given access to an approximate planning oracle.  The authors show that MADE applies some simple adjustments to the Hoeffding-style count-based bonus. Moreover, experiments in three different RL algorithms (Value iteration, PPO, Q-Learning) show the superiority over the state-of-the-art UCB-bonus methods (Hoeffding and Bernstein bonus). In addition, the authors demonstrate that MADE can practically work both in Model-based (Dreamer) and Model-Free (IMPALA, RAD) RL algorithms, significantly improving sample-efficiency over baselines.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The paper proposes an interesting method for addressing the problem of exploration in RL, with theoretical results about the global convergence to the optimum and solid empirical performance compared to the SOTA. Overall, I like the paper, but I still have few doubts that I would like the authors to address:\n\n- It is not clear how we can get the total reward at iteration k by taking the gradient of the new objective as shown in equation (5).\n- As far as I understand, can $r(s,a)$ be derived from equation (2)?\n- But then still, how is that the total reward can be derived from the gradient of the regularized objective function?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "avS7X6Qpxr3", "reviewer": "Reviewer_dMyV", "summary": "The authors propose adding a regularisation term, that encourages a policy to visit states, less visited by previous policies, to the RL problem to address the exploration-exploitation tradeoff. The result is a convex regularised optimisation problem in the state occupancy of the policy. In addition, the authors propose an algorithm to solve this problem that is based on the Frank-Wolfe algorithm, similar to Hazan et al. i.e., they iteratively find a policy that has a state occupancy with maximal correlation with the negative gradient of the objective. Experiments are performed in several domains and include a comparison with various baselines from the reward free literature. ", "questions": "", "limitations": "", "rating": 5, "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": "The problem of balancing exploration and exploitation with function approximation is perhaps one of the most important problems in current DRL research. The authors propose to tackle the problem by introducing a convex regulariser on the state occupancy that will encourage the policy to visit states that were unvisited by previous policies. \n\nHowever, this construction has two fundamental flaws. The first one is that there are no guarantees that adding a convex regulariser indeed balances the exploration-exploitation tradeoff in an efficient manner. This statement is true in general, so far, no paper in the literature of reward free exploration have claimed to balance exploration and exploitation efficiently. Instead, adding a convex regulariser results in a different problem, that perhaps covers the state space better but does not lead, for example, for an efficient regret algorithm for the RL problem unless it is combined with a proper exploration method. The second issue is that in order to solve the convex regularised problem efficiently, in terms of regret, efficient exploration must be used, on top of the intrinsic reward. These two comments stress that the motivation abstract and intro of the paper are misleading. That said, the proposed algorithm and the convex regulariser are interesting contributions by themselves, taking ideas from the reward free literature as regularisers to the RL setup, and I will continue the review addressing them as a separate problem. \n\nBaselines and related work. The proposed algorithm solves an MDP with an objective that is convex in the state occupancy of the agent, and specifically, a Frank-Wolfe algorithm. That said, I feel that the paper fails to cite relevant papers on the topic. The one paper that is cited (from Hazan et al.) is not compared to empirically, while being the most similar. That said, the baselines that were implemented and compared to are strong baselines and the comparison is done well, I enjoyed reading the experimental section and I feel that if the paper was focused on it, I might have given it a higher score. I believe that further discussion on how to think of these baselines in the lens of convex regularised MDPs would make their introduction better, i.e., do they solve the same problem? I included several papers on Franke Wolfe, FW algorithms in RL and convex regularised MDPs at the end of this review. \n\nRegarding Theorem 1. I feel that the way the theorem was introduced in the main paper is highly misleading. The Theorem states a linear convergence rate for a FW algorithm with an approximate best response which is not a common result. For that reason I checked the supplementary which adds 4 assumptions on the function f in order for this result to hold, with assumption 4 being non trivial in my opinion. The assumption states that there exists a constant that bounds the iteration error of the FW method and the final sample complexity is given in terms of this constant. On the other hand, the authors state that the constants only depend on the MDP parameters. More broadly, the analysis of FW methods with approximate best response is summarised in \"Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimisation\", which shows that when an approximate best response is used (the planning oracle that finds the optimal policy in this case) the convergence of FW has a slower rate. The linear convergence in the non approximate case is discussed in \"On the Global Linear Convergence of Frank-Wolfe Optimisation Variants\" (with MDPs being a special case where d_\\pi is in a polytope), but there is not a general result that shows a linear rate with an approximate best response to the best of my knowledge. Furthermore, the linear rate is typically shown for a strongly convex function, which was not assumed by the authors. If the authors can convince me that assumption number 4 is not \"stating the linear rate\" by construction or will show me some evidence that a similar assumption was used in FW analysis elsewhere, I will consider changing my score. In particular, I would like to see how $\\delta_k, \\zeta$ and $\\tau$ can be expressed as a function of the MDP parameters, without $k$, and without making the strong convexity assumption. \n\nQuestion: both the \\pi_\\mix and \\rho_cover are mixed policies that weight the previous policies seen by the agent. Therefore, it is not clear what role does the different weights play. Can you elaborate on this? \n \n[1] \"Apprenticeship Learning via Inverse Reinforcement Learning\"\nThe first FW algorithm https://ai.stanford.edu/~ang/papers/icml04-apprentice.pdf (see the supplementary)\n[2] \"Apprenticeship Learning via Frank-Wolfe\" on linear convergence for FW in RL https://arxiv.org/pdf/1911.01679.pdf\n[3] \"Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization\" FW with approximate best response http://proceedings.mlr.press/v28/jaggi13-supp.pdf\n[4] \"On the Global Linear Convergence of Frank-Wolfe Optimization Variants\" https://arxiv.org/pdf/1511.05932.pdf\n[5] \"Online Apprenticeship Learning\" on why exploration is still needed in the convex regularised problem https://arxiv.org/pdf/2102.06924.pdf \n3 papers on solutions to the convex regularised problem: \n[6] \"Concave Utility Reinforcement Learning: the Mean-field Game viewpoint \"https://arxiv.org/pdf/2106.03787.pdf\"\n[7] \"Reward is enough for convex MDPs\" https://arxiv.org/pdf/2106.00661.pdf\n[8] \"Variational Policy Gradient Method for Reinforcement Learning with General Utilities\" https://arxiv.org/pdf/2007.02151.pdf", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not relevant. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "Y1YVB7QESus", "reviewer": "Reviewer_zDng", "summary": "This paper introduces a new exploration technique called MADE that computes a bonus that depends on the ratio between the visitation densities of the current policy and policy cover of previous policies. This incentivizes the agent towards it has not been before and leads to more exploration. The authors provide a convergence result for this bonus and evaluate it on grid worlds, Mini Grid and Mujoco environment to show that it leads to better exploration than existing techniques.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall I think that this is a good paper, it builds on previous ideas about using policy covers for exploration but is able to derive a bonus that can be used with any reinforcement learning algorithm, model based or model free and not limited to policy gradient method. I found the paper well written and easy to follow. The empirical evaluation was really thorough, MADE was evaluated on grid worlds, discrete actions and continuous control environments.\nMADE showed really good results on MiniGrid, however on DM control while results look promising it is hard to interpret them without knowing the number of seeds used for each.\n\nHow was Eq (4) chosen vs other possible solutions? Could we use those insights to derive other exploration bonuses? And could we hope to find an optimal regularizer?\nIn section 4.1 and Figure 3 MADE is shown to work similarly to Bernstein bonuses which are as good as we can hope. Does it mean that this choice of regularizer is somewhat optimal?\n\nL139: What happened to the term $\\sqrt{N_k}$? To match equation 4 it should be included and would lead to different bonuses.\nI found the paragraph L148 to be interesting, being able to fit any bonus through the MADE paradigm could be powerful, however little to no insight is actually gained from this. Do you think there is anything we can learn through this point of view?\n\nWhen looking at Equation (4) it is not clear that the bonus actually goes down to zero. Is that the case? If not that might explain the regularizer instead of exploration bonus. In that case can the bonus impact the reward and change the optimal policy of the problem being solved?\n\nSmall typos:\nL194 \"gradients.= In\"\nL215 \"we as the training\"\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "GL4NnNYc-5s", "reviewer": "Reviewer_2ECg", "summary": "The paper proposes an new approach for exploration in reinforcement learning (RL). The idea is to give an exploration bonus to visiting with the new policy state-action pairs which have low visitation density compared to previously visited state-action pairs. The paper provides a convergence proof assuming a perfect oracle provides visitation densities for a chosen mixture policy. The proposed approach is compared in experiments to RL baselines in both continuous and discrete control tasks with function approximation and in tabular benchmarks.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The idea behind the proposed exploration bonus is not surprising by itself. There are other methods that try to explore in parts which have not been explored before. For example, [Hong et al., 2018] adds an exploration bonus for a policy which is different from previous policies. In addition, as mentioned in this paper count based methods also try to visit state-action pairs which have not been visited before. One of the main contributions is to propose an exploration bonus that is efficient and simple and can be implemented in practice.\n\nAuthors: how is the proposed approach related to prior work where the new policy is regularized by maximizing the difference to prior policies such as [Hong et al., 2018]? Intuitively, maximizing the difference to prior policies also maximizes the differences to prior state-action distributions indirectly. Is there a benefit to the approach you are using? An experimental comparison to [Hong et al., 2018] would make sense.\n\nThe submission appears technically sound. The theoretical proof is nice. It would be good to have a discussion on what the theoretical proof means in practice since there is the assumption on the oracle providing visitation densities. The discussion on how the proposed exploration bonus can be seen as another form of other exploration bonuses is interesting and valuable. The empirical results show the approach outperforming baselines and the results are analyzed in a reasonable way. Having both tabular and continuous tasks is valuable.\n\nThe paper should provide timing results. How much computation time does each method use per sample? Is the proposed approach computationally intensive compared to other approaches?\n\nThe paper is clear and well written. Emphasizing even more that Algorithm 1 is a theoretical proof but not actually used in the experiments would improve clarity. The practical implementation of the methods is one of the key things for a practitioner in RL and this could be also emphasized (although it is relatively straightforward to find it in the text).\n\nI expect the results of the paper to be used by other researchers. While similar ideas have been proposed before, exploration is an important unsolved problem and the idea proposed in this paper is simple and seems to perform well in the experiments.\n\n[Hong et al., 2018] Hong, Z.W., Shann, T.Y., Su, S.Y., Chang, Y.H., Fu, T.J. and Lee, C.Y., 2018, December. Diversity-driven exploration strategy for deep reinforcement learning. In Proceedings of the 32nd International Conference on Neural Information Processing Systems (pp. 10510-10521).\n\nUPDATE: I am happy with the author's rebuttal and the changes they are planning for the next version of the paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The initial reviews were overall positive (and raised concerns well addressed in the rebuttal), except for one review that raised concerns about the proof of the provided theoretical result. This led to an engaged discussion between the authors and the reviewers, that clarified many aspects of the proof and of the approach. Some questions remained about the interpretation of some quantities ($\rho_{cover}$, which is part of the iteration-dependent regularizer, and $d^{\pi_{mix}}$, the iterate computed by the algorithm). Maybe that making a parallel with mirror descent could help clarify this aspect (for the idea of regularizing wrt the last iterates, even though $\rho_{cover}$ is not the last iterate due to different weighting of the involved occupancy measures, and even though the regularizer is not a Bregman divergence).

Overall, I do think that this helpful discussion addressed sufficiently the initial concerns, and that the theoretical result is technically correct. Beside, this is not the sole contribution of this paper, it also provides a strong empirical analysis, where the approach compares favourably to strong baselines. 

To sum up, I think this paper would be a solid addition to the neurips program, and I recommend its acceptance.

I strongly encourage the authors to revise their paper taking into account the discussion with reviewer dMyV as well as other reviews (notably, it is more than Frank-Wolfe, but less general), I think it will widen the audience and increase the impact of this contribution.
Decision: Accept (Poster)