MaxMin-Novelty: Maximizing Novelty via Minimizing the State-Action Values in Deep Reinforcement Learning
Authors: Ezgi Korkmaz
Venue: Submitted to ICLR 2023 (2023)

Abstract: Reinforcement learning research has achieved high acceleration in its progress starting from the initial installation of deep neural networks as function approximators to learn policies that make sequential decisions in high-dimensional state representation MDPs. While several consecutive barriers have been broken in deep reinforcement learning research (i.e. learning from high-dimensional states, learning purely via self-play), several others still stand. On this line, the question of how to explore in high-dimensional complex MDPs is a well-understudied and ongoing open problem. To address this, in our paper we propose a unique exploration technique based on maximization of novelty via minimization of the state-action value function (MaxMin Novelty). Our method is theoretically well motivated, and comes with zero computational cost while leading to significant sample efficiency gains in deep reinforcement learning training. We conduct extensive experiments in the Arcade Learning Environment with high-dimensional state representation MDPs. We show that our technique improves the human normalized median scores of Arcade Learning Environment by 248% in the low-data regime.

Under review as a conference paper at ICLR 2023
MAXMIN-NOVELTY: MAXIMIZING NOVELTY VIA MINIMIZING THE STATE-ACTION VALUES IN DEEP REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Reinforcement learning research has achieved high acceleration in its progress starting from the initial installation of deep neural networks as function approxi- mators to learn policies that make sequential decisions in high-dimensional state representation MDPs. While several consecutive barriers have been broken deep reinforcement learning research (i.e. learning from high-dimensional states, learning purely via self-play), several others still stand. On this line, the ques- tion of how to explore in high-dimensional complex MDPs is a well-understudied and ongoing open problem. To address this, in our paper we propose a unique exploration technique based maximization of novelty via minimization of the state-action value function (MaxMin Novelty). Our method is theoretically well motivated, and comes with zero computational cost while leading to significant sample efficiency gains in deep reinforcement learning training. We conduct ex- tensive experiments in the Arcade Learning Environment with high-dimensional state representation MDPs. We show that our technique improves the human nor- malized median scores of Arcade Learning Environment by 248% in the low-data regime.
INTRODUCTION
Utilization of deep neural networks as function approximators enabled learning functioning policies in high-dimensional state representation MDPs (Mnih et al., 2015). Following this initial work, current line of work trains deep reinforcement learning policies to solve highly complex problems from game solving (Hasselt et al.] 2016) Schrittwieser et al. 2020) to self driving vehicles (Lan al. 2020). Yet there are still remaining unsolved problems restricting the current capabilities of deep neural policies.
One of the main intrinsic open problems in deep reinforcement learning research is exploration in high-dimensional state representation MDPs. While prior work extensively studied the explo- ration problem in bandits and tabular reinforcement learning, and proposed various algorithms and techniques optimal to the tabular form or the bandit setting (Kearns & Singh [202 Brafman & Ten- nenholtz 2002 Lu & Roy 2019 Wang al. 20200] Karnin al. [0113] Wagenmaker al. 2022)
exploration in deep reinforcement learning remains an open challenging problem.
Despite the provable optimality of these exploration techniques in the tabular bandit setting, they generally rely strongly on the assumptions of tabular reinforcement learning, and in particular on the ability record tables of statistical estimates for every state-action pair. Thus, in high- nigh-dimensional complex MDPs, for which deep neural networks are used as function approximators, the efficiency and the optimality of exploration methods proposed for tabular settings not transfer well to deep reinforcement learning exploration. This is primarily due to the increase in the MDP dimensions and the incline in the complexity. Hence, in deep reinforcement learning research still, naive and simple exploration techniques (e.g. c-greedy) are preferred over the optimal tabular techniques (Mnih al.
2015
Hasselt et al. 2016 Wang et al. 2016 Anschel et al. 2017 Bellemare et al. 2017 Lan et al.
2020
Sample efficiency in deep neural policies still one of the main challenging problems restricting research progress in reinforcement learning. The magnitude of the number of samples required to

---

Under review as a conference paper at ICLR 2023
learn and adapt continuously is of the main limiting factors preventing current state-of of-the-art deep reinforcement learning algorithms from being deployed in many diverse settings, but most importantly one of the main challenges that needs to be dealt with on the way to building general artificial intelligence. In our paper we aim to seek answers for the following questions:
Can we explore dige-siiaa state representation MDP more efficiently with zero additional computational cost?
Is there natural theoretical motivation that can be used to design zero-cost exploration strategy while achieving high sample efficiency?
To be able answer these questions. our paper we focus on exploration in deep reinforcement learning and make the following contributions:
We propose novel exploration technique based on minimizing the state-action value func- tion to increase the information gain from each particular experience acquired in the MDP.
We conduct extensive study in the Arcade Learning Environment 100K benchmark with the state-of-the-an algorithms and demonstrate that our proposed method achieves significant performance improvement.
We show the efficacy of our proposed MaxMin Novelty method in terms of sample effi- ciency. Our method based on maximizing novelty via minimizing the state-action value function reaches approximately to the same performance level as model-based deep rein- forcement learning algorithms, without building and learning any model of the environ- ment.
BACKGROUND AND PRELIMINARIES
2.1 DEEP REINFORCEMENT LEARNING
The reinforcement learning problem is formalized a Markov Decision Process (MDP) M (S, A. 7. Po. P) that contains continous set of states s E S, set of discrete actions a A,, probability transition function T(x, s') on S x x S, discount factor 7, a reward function a(s,a)= a) S x A - IR with initial state distribution po. A policy TTs, : S + P(A) in an MDP is a mapping function between states and actions assigning a probability distribution over actions for each state S. The main goal in reinforcement learning is to learn optimal policy that maximizes the discounted expected cumulative discounted rewards.
R Eayor(s Σ 2'r(Se; at),
where a, :(...).. In Q-learnig the learned policy parameterized by state-action value function Q S x A - IR, which represents the value of taking action a in state The optimal state-action value function learnt via iterative Bellman update
Q(si, = r((; + E ETss 8441 (1441))
where V(5411) max, Q( a). Let a be the action maximizing the state-action value function, a" (s) arg max, a(),a), in state Once the Q-function is learnt the policy is determined via taking action a" (8) = arg max, ((s, a). In deep reinforcement learning, the state space or the action space is large enough that it is possible learn and store the state-action values tabular form. Thus, the Q-function is approximated via deep neural networks.
0. = 8, + a(r(s,, a.) + (s arg max Q(5 a; 0,); 0.) Q(s,, a,; 0.)) Va, Q(s,, 0,)
In deep double-Q learning, two Q-networks are used to decouple the Q-network deciding which action to take and the Q-network to evaluate the action taken.
Q(s ((; Ve) Ve.s, a(;,,,;;)) 0.11 0, a(r(st, a:) + (S arg max Q(5++1, a; o:00):;))
2

---

Under review as a conference paper at ICLR 2023
Current deep reinforcement learning algorithms e-greedy exploration during training (Mnih jet al. 2013 Hasselt et al. 2016 Wang et al., 2016; Hamrick et al., 2020; Flennerhag et al. 2022). In particular, the e-greedy algorithm takes action ag ~ U[A) with probability in a given state 8, i.e. T(8, ax) = c and takes an action a* = arg max, Q(s a) with probability 1 - 6, i.e.
TAI.
((s a(ssaa)= a=)=a))=1 =1 - + [
2.2 EXPLORATION IN REINFORCEMENT LEARNING
In the tabular MDP setting, there has been extensive theoretical work proving optimal regret bounds using the principal of optimism in the face of uncertainty. One prominent class of algorithms in this setting utilizes a bonus value estimates based on the Upper Confidence Bound (UCB) approach (Auer et al.) 2008). In fact, the recent work of Afzrr et al. (2017) achieves minimax optimal regret using a carefully designed variant of the UCB approach. Furthermore, the UCB approach to explo- ration continues to be active area of research for deriving new algorithms with provable regret bounds in reinforcement learning (Zanette & Brunskill 2019; Jin et al.) 2020). The basic idea of UCB algorithms is to explore by adding optimistic bonus to the actton values, based on an estimate of the uncertainty in the current value function. The basic UCB approach (Sutton & Barto, 2018) is use visit-count statistics Nz(8, a) representing the number of times action a has been taken in state & by time step / in order to estimate the variance of the current state-action values. The variance estimate is then used construct a confidence interval around the current value estimate,
usually given by some multiple of the standard deviation ev (.(a.a) Finally, the action with the highest value for the upper end of its confidence interval is selected. In this sense the UCB algo- rithm is optimistic, as it chooses an action based on the highest plausible estimate of its value given the previously observed data. Note also that as the state action pair (s, a) is visited more frequently, the corresponding confidence interval becomes smaller, eventually converging to the final estimated value. A second general class of theoretically--ussee justtified algorithms for exploration is based on ran- domized value functions, where specifically tuned randomness is added to value estimates in order to encourage exploration. Notable examples of algorithms in this category include Thompson sam- pling (Osband et al.) 2013 Agrawal & Jia 2017), based on sampling from posterior distribution on actions given past observations, and randomized least-squares value iteration (RLSVI) (Osband ct al. 2016), based on using tuned Gaussian noise to sample randomized value function.
logt
Despite the strong theoretical performance of the aforementioned approaches, there are significant difficulties in effectively extending to the setting of deep reinforcement learning. The primary obsta- ele is that these methods utilize count-based uncertainty estimates (e.g. the state-action visit counts (s, a)), which are generally not immediately available in deep reinforcement learning where the state space is modeled as a continuous nigh-dimensional vector space (e.g. in deep reinforcement learning from pixels). Instead, incorporating count-based methods into deep reinforcement learn- ing requires significant complexity including training additional deep neural networks to estimate counts or other uncertainty metrics. As a result, many saate-of-the-ee deep reinforcement learning algorithms use simple, randomized exploration methods such the e-greedy approach of sampling a uniformly random action with probability 6 (Mnih et al. 2015) Hasselt et al. 2016 Wang et al., 2016 [Hamrick al. 2020 Flennerhag et al. 2022), or the injection of random noise via noisy- networks (Hessel et al. 2018).
3 MAXIMIZING NOVELTY
In deep reinforcement learning the state-action value function is initialized with random weights (Mnih et al.) 2015 2016. Hasselt et al.) 2016 Wang et al.) 2016 [Shhaul et al.] 2016: Oh et al.) 2020 Schritwiessr et al. 2020; Hubert et al. 2021). Thus, in the early phase of the training the Q-function will behave more like random function rather than providing
accurate representation of the optimal state-action values. In particular, early in training the Q-function, on average, will assign approximately similar values to states that are similar, and will have little correlation with the immediate rewards. We first formalize this intuition in the following definitions.
Definition 3.1 (n-unninormmdd Q). Let 1) > y-uninformed if for any state & E S with a min = arg min, Qa a) we have
0. A Q-function parameterized by weights 0 O is
Ea-e(r(ss, a min)] Ea-u(s)) (1 a)]l < n-
3

---

Under review as a conference paper at ICLR 2023
Definition 3.2 (ō-smooth Q). Let 8 0. A Q-function parameterized by weights 0 θ is d-smooth for any state s and action E A with s' T(s, we have
1 [ mmax Qe a)] _ [max (Q(ss,a))) <
where the expectation is over both the random initialization of the Q-function weights, and the random transition state s' T(x, a).
Definition 3.3 (Disadvantage Gap). For a state-action value function Qe the disadvantage gap in state s E is given by
((s) = Bu.-rca, - Qo a m
where a min arg min, Qo(s,a).
The following proposition captures the intuition that when the Q-function on average assigns sim- ilar maximum values to consecutive states, choosing the action minimizing the state-action value function will achieve an above-average temporal difference loss.
and suppose that Qo(s, a) njuninformed and 8-smooth. Let E be a state, and let am be the action minimizing the state-action value in a given state S1, a arg min, Qa(s;, a). Let smin T(s ammi..)). ()). Then for an action as U(A) with
Proposition 3.1. Let n)
8141 T(s,,0,,) we have
E. Lus ~x(,aamin ),0 (r(s) mii) + max Qo (0(+++1:)) a) Qo(se, a amiin) )
E
az) max Q0($441, a) Qa((s, at)] +D(s) 25 7)
Proof. Since Qo(s, a) is 8-smooth we have
E NT a1t e ( max ( a) - Qe( mmin)]
- e Imax Qa(sr, a)] - - Eg Qo amin)]
y y ( max Q0( a)] - 25 - Ee Eewe(Qo amin]]
max Q0( a) Qo(si, a.)] + D(s) 25
where the last line follows from Definition 3.3 Further, because Qo Qo a) is u-niifformed,
Eg Eg-e/r(s; a min]]
(r, a:)]
Combining with the previous inequality completes the proof.
In words, the proposition shows that the temporal difference loss achieved by the minimum-vale value action is above-average by an amount approximately equal to the disadvantage gap.
The above argument can be extended to the case where action selection and evaluation in the tempo-
ral difference loss are computed with two different sets of weights 0 and 0 as in double Q-learning.
Definition 3.4 (6-smoothness for Double-Q)- Let Ā > 0. A pair of Q-functions parameterized by weights 0 ~ θ and ~ θ are 8-smooth if for any state E S and action à E A with s' ~ T(s, ê. we have
Qo(s, arg max Qo(s, a))
I s' :
a
Qg(6 arg max Qo(s' a)) <8
1<6
E )
where the expectation over both the random initialization the fuuncioo weights and and the random transition to state s' T(s, a)
4

---

Under review as a conference paper at ICLR 2023
With this definition temporal difference loss that is above-average by approximately D(s).
then prove that choosing the minimum valued action will lead
Proposition 3.2. Let 17, 8 > O and suppose that Qo and Qa are n-uniformed and 8-smooth. Let 8t E S be a state, and let mmin = arg min, Qo(se, a). Let smm az ((A) with 8++1 (s,, we have
8411 T(st, a.thn) Then for an action
E Toa.)
7Q (5 arg max (0(s min a)) Qa (st, a am)
( max Q0(s++1, Qo(s),
+ +D(s)-20 28 -0
Proof. Since Qo and Qg are d-smooth we have
E s/4 ~ ",000,,,,,0000000000000000
( 10 1 (+ arg max Qo (stt) ()) Qu(s a
R "4t T 1,00,,000,,,,0000000_000
arg max Qo(st, - Q0(8), am
R ae eag arg max Q0(s++1, a)) - Q0(s,, a aminn)] - 25
2 Ts
max max Qai (0( - Qo(s,, at)] + D(s) -2
where the last line follows from Definition
3.3 Further, because Qo and Qi are n-unnforrmed,
Eg Be- min
(T) a;)]
Combining with the previous inequality completes the proof.
At first, the results in Proposition 3.1 and 3.2 might appear counterintuitive. The fact that the Q- function is 8-smooth and 17-uninformed seem like properties of a random function. Thus, taking the minimum Q-value action should be approximately equivalent taking uniform random action. However, Proposition 3.1 and 3.2 show that the temporal difference loss achieved by taking the minimum action larger than that of random action by an amount equal to the disadvantage gap D(s). In order to reconcile these two statements it is useful at this point to look at the limiting case of the function initialization. In particular, the following proposition shows that, at initialization, the distribution of the minimum value action in given state is uniform by itself, but is constant once we condition on the weights
Proposition 3.3, Let 0 be the random initial weights for the Q-function. For any state S let amin (s) arg min QQ(s,a'). Then for any E A
Powe
arg min Qo(s. = = [AI
e'EA
iee. the distribution Pawola" (in) uniform. Po-el ma (x) [0] is constant.
Simultaneously, the conditional distribution
Since (s .) is random function (given the random choice of 0), each action A is equally likely to be assigned the minimum Q-value state 8. Thus,
Proof.
Po-e
arg min Qo a) =
[AI
e'EAA
However, given the value of 0, the value of (s)) is uniquely determined because
arg min Qo(s.a).
dEA
Therefore, the distribution of a conditional 0 constant.

---

Under review as a conference paper at ICLR 2023
Algorithm 1: MaxMin Novelty
Input: In MDP M with y E (0, 11. s S, a E A with Q(s, a). B experience replay buffer, exploration parameter, .N is the training learning steps. Populating Experience Replay Buffer:
Learning:
for &t in e do
for n. in A do
Sample ~ (0,
Update with probability E:
if K then
TD r(st, aiia)
a arg ming ((s,,a) a) B (r(s,, a mdn). ) St, 8411, amin)
+y max, Q a) Q(5,, am
Update with probability 1
else
TD r((t. a²)
a" arg max, Q(s), a)
+7 max, Q(+++1, - Q(si,
B <- (r(s,, a"), 8t, 80+1,
end for return VL(TD)
end if'
end for
This implies that, in states whose Q-values have not changed much from initialization, taking the minimum action is almost equivalent taking random action. However, while the action chosen early on in training is almost uniformly random when only considering the current state, it is at the same time completely determined by the current value of the weights 0. The temporal difference loss is also determined by the weights 0. Thus while the marginal distribution on actions taken is uniform, the temporal difference loss when taking the minimum action quite different than from the case where an independently random action is chosen.
Algorithm summarizes our proposed exploration method MaxMin Novelty based on minimizing the state-action value function as described in detail in Section Note that populating the experience replay buffer and learning are happening simultaneously with different rates.
4 MOTIVATING EXAMPLE
As motivating example we consider the chain MDP which consists of a chain of states S = {1, 2, ... each with two actions. Each state has one action that transitions the agent up the chain by one step to state i 1, and one ac- tion which resets the agent to state 1 at the beginning of the chain. All transitions have reward zero, except for the last transition returning the agent the beginning from the n- th state. Thus, when started from the first state in the chain, the agent must learn policy that takes n consecutive steps the chain, and then the one final step to reset and get the reward.
Chein
MeaHin Nouely a-gresdy
Iverage Cumuntive Fature
2
20 40
80
100
Endhermeent Interatiinnnne
Figure 1: Exploring the chain MDP with Upper Confidence Bound (UCB) method, e-greedy and our proposed method MaxMin Novelty.
For the chain MDP, we compare standard approaches to ex- ploration tabular Q-learning with our method MaxMin Novelty based on minimization of the state-action values. In particular we compare our method MaxMin Novelty with both the c-greedy action selection method, and the upper confidence bound (UCB) method. In more detail, in the UCB method the number of training steps I, and the number of times Ne(s, a) that each action a has been taken in state by step t are recorded. Furthermore, the action É A selection is determined as follows:
logt Ni(s, a)
a
LCB
arg max Q(s, a) + +2 acA
In a given state s if N(s, a) = 0 for any action a, then an action is sampled uniformly at random from the set of actions a' with N(s, a') O. For the experiments reported in our paper the length of the chain set to n = 10, and e 0.2. The Q-function is initialized by independently sampling each state-action value from normal distribution with μ 0 and 0.1. In each iteration

---

Under review as a conference paper at ICLR 2023
10
100
JamesBond
Gravitar
Tcel lockey
BankHeist
Bowling
Endiam
SturGunner
Amidar
Boxing
KunsFuMaster
Tennis
FishingDerby
Figure 2: The learning curves of StarGunner, FishingDerbb,, Boxing, Enduro, Bowling, IceHockey, BankHeist, JamesBond, KungFuMaster, Amidar, Gravitar and Tennis with our proposed method MaxMin Novelty and the e-greedy algorithm in the Arcade Learning Environment with 200 million frame training.
Figure 3: Temporal difference loss for our proposed algorithm MaxMin-Novelty and the canonical e-greedy algorithm in the Arcade Learning Environment 100K benchmark. Dashed lines report the temporal difference loss for the e-greedy algorithm and solid lines report the temporal difference loss for the MaxMin-Novelty algorithm. Colors indicate games.
train the agent using Q-learning for 100 steps, and then evaluate the reward obtained by the argmax policy using the current Q-function for 100 steps. Note that the maximum achievable reward 100 steps is 10. The learning curves in Figure deemonsttettttt that our method converges more quickly to the optimal policy than either the standard approaches.
LARGE SCALE EXPERIMENTAL RESULTS
The experiments are conducted in the Arcade Learning Environment (ALE) (Bellemare et al. 2013) The Double-Q Network (Hasselt al. (016) initially proposed by (van Hasselt 2010) is trained with prioritized experience replay (Schaul et al. 2016) without the dueling architecture with its original version (Hasselt et al. 2016). The experiments are conducted both in the 100K Arcade Learning Environment benchmark (van Hasselt et al. 2019), and the canonical version with 200 million frame training. Note that the 100K Arcade Learning Environment benchmark an estab- lished baseline proposed to measure sample efficiency in deep reinforcement learning research. The ALE 100K benchmark contains 26 different Arcade Learning Environment games. The policies are evaluated after 100000 environment interactions. All of the polices in the experiments over random seeds. The hyerpparameters and the architecture details are reported in the appendix. All of the results in the paper are reported with the standard error of the mean. The human normal- ized scores are computed as,
trained
HN Scoreagent Score randoom
(I)
Score/uman Score mandonn

---

Under review as a conference paper at ICLR 2023
6.10
MarHin Novelt
Mostin Novelty
>-greedy
F greecd
0.04
0.05
0.25
0.20
0.04
0.13
0.00
0.00
0.00
10
10
Environment Inforactions (LO")
Enviroment Interactions (207)
Median
80 Percentile
Figure 4: Human normalized scores median and 80th percentile over all games in the Arcade Learn- ing Environment (ALE) 100K benchmark for MaxMin Novelty algorithm and the canonical explo- ration algorithm e-greedy.
Table 1: Human normalized scores median and 20th percentile across all of the games in the Arcade Learning Environment 100K benchmark for MaxMin-Novelty, e-greedy and NoisyNetworks.
Method
Human Normalized Median 20th Porcentile
80th Percentile
Maxein-Noovlty
0.0927=0.000
0.0145=0.0003
0.3762=:0.037
e-greedy
0.0377=0.0031 0.0457=0.0035
0.0056++0.0017
0.2942=:0.0333
NoisyNetworks
0.0102::000088
0.1913
For completeness we also report several results with 200 million frame training (i.e. 50 million environment interactions). In particular, diguntaadeonsstratte the learning curves for our proposed algorithm MaxMin Novelty and the original version of the DDQN algorithm with e-greedy training (Hasselt et al.) 2016). In the large data regime we observe that while in some MDPs our proposed method MaxMin Novelty based on exploring with novelty maximization via minimizing the state- action values converges faster, in other MDPs MaxMin Novelty simply converges a better policy. More concretely. while the learning curves of StarGunner, FishingDerby, Boxing, Enduro, Hero, and IceHockey games in Figure demonstrate the faster convergence rate of our proposed algo- rithm MaxMin Novelty, the learning curves of the BankHeist, JamesBond, KungFuMaster, Amidar, Gravitar and Tennis games demonstrate that our exploration technique not only increases the sample efficiency in deep reinforcement learning, but also results in learning policy that is more close to optimal compared to learning a policy with the original method used in the DDQN algorithm.
proposed MaxMin Novelty algorithm with NoisyNetworks as described in Section [2.2] Table further demonstrates that the MaxMin Novelty algorithm achieves significantly better performance results compared to NoisyNetworks. Furthermore, note that Netsykssworks includes adding layers in the Q-network to increase exploration. However, this increases the number of parameters that have been added in the training process; thus, introducing additional cost to increase exploration. Table reports results of human normalized median scores, thth percentile, and thth percentile for the Arcade Learning Environment 100K benchmark. Thus, Table [ demonstrates that our proposed MaxMin-Novelty algorithm improves on the performance of the canonical algorithm e-greedy by 248% and NoisyNetworks by 204%.
Additionally, we also compare
INVESTIGATING THE TEMPORAL DIFFERENCE Loss
The original justification for exploring with the minimum Q-value action, is that taking this ac- tion tends to result in transitions with higher temporal difference loss. The theoretical analysis from Proposition 3.1 indicates that, when the Q function 8-smooth and 7-uninffrrmed, taking the minimum value action results in increase in the temporal difference loss proportional to the dis- advantage gap. In particular, Proposition 3.1 3...sstate states that the temporal difference loss achieved when taking the minimum Q-value action in state exceeds the average loss over uniform random action by D(s) - 25- 17.
In order to evaluate how well the theoretical prediction matches reality, in this section we provide empirical measurements of the temporal difference loss in our experiments. To measure the change in the loss when taking the minimum action versus the average action, we compare the temporal
8

---

Under review as a conference paper at ICLR 2023
ChariN
3.27 UCB
3.25
3.23
Plat
3000
3.20
30
300
Figure 5: Left and Middle: Normalized temporal difference TD gain median across all games in the Arcade Learning Environment 100K benchmark for MaxMin Novelty and NoisyNetworks. Right: Temporal difference loss TD when exploring chain MDP with Upper Confidence Bound (UCB) method, e-greedy and our proposed algorithm MaxMin Novelty.
difference loss obtained by MaxMin Novelty exploration with that obtained by e-greedy exploration. In more detail, during training, for each batch A of transitions of the form (8t, des $1+1) we record, the temporal difference loss
TD = (( (D(st Oe, S2+1)
(e (r(s,, ax) + max Qo Q0(#++1, Qo(ss, a.)]
The results reported in Figure and Figure 5 further confirm the theoretical predictions made via Definition 3.2 and Proposition In addition to the results for individual games reported in Fig- ure 3 we compute a normalized measure of the gain in temporal difference achieved when using MaxMin Novelty exploration and plot the median across games. We define the normalized TD gain to be
Normalized TD Gain + TD TD e-grrddd
(T
where TD mDmethod and TDe-grocd are the temporal difference for any given exploration method and e-greedy respectively. The leftmost and middle plot of Figure 5 report the median across all games of the normalized TD gain results for MaxMin Novelty and Noisy Environment 100K benchmark. Note that, consistent with the predictions of Proposition 3.1] the median normalized temporal difference gain for MaxMin Novelty is up to 25 percent larger than that of e-greedy. The results for NoisyNetworks demonstrate that alternate exploration methods lack this positive bias relative to the uniform random action. The fact that, as demonstrated in Table MaxMin Novelty significantly outperforms noisy networks the low-data regime is further evidence of the advantage the positive bias in temporal difference confers. The rightmost plot of reports TDD for the motivating example of the chain MDP. As in the large- experiments, prior to convergence MaxMin Novelty exhibits a notably larger temporal difference loss relative to the other exploration methods.
in the Arcade Learning
CONCLUSION
In study we focus the following questions in deep reinforcement learning: (i) Is it possible to increase sample efficiency in deep reinforcement learning in a computationally efficient way with conceptually simple choices?, (ii) What is the theoretical motivation of our proposed perspective, simply minimizing the state-action value function in early training, that results in one of the most computational efficient ways to explore in deep reinforcement learning? and, (ii) How would the theoretically motivated simple idea transfer to large scale experiments in high-dimensional state representation MDPs? To be able answer these questions we propose a novel, theoretically mo- tivated method with zero additional computational cost based on following actions that minimize the acte-action value function to explore in deep reinforcement learning. We demonstrate theoret- ically that our method MaxMin Novelty based on minimization of the state-action value results in higher temporal difference loss, and thus creates novel transitions in exploration with more unique experience collection. Following the theoretical motivation we initially show in a toy example in the chain MDP setup that our proposed method MaxMin Novelty results in achieving higher sam- ple efficiency. Then, expand this intuition and conduct large scale experiments in the Arcade Learning Environment, and demonstrate that our proposed method MaxMin Novelty increases the performance on the Arcade Learning Environment 100K benchmark by 248%.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst- case regret bounds. Advances in Neural Information Processing Systems, 30, 2017.
Oron Anschel, Nir Baram, and Nahum Shimkin. Averaged-dqu: Variance reduction and stabilization for deep reinforcement learning. International Conference on Machine Learning (ICML), 2017.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances neural information processing systems, 21, 2008.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In ICML, 2017.
Igor Babuschkin, Kate Baumli, Alison Bell, Surya Bhupatiraju, Jake Bruce, Peter Buchlovsky, David Budden, Trevor Cai, Aidan Clark, Ivo Danihelka, Claudio Fantacci, Jonathan Godwin, Chris Jones, Tom Hennigan, Matteo Hessel, Steven Kapturowski, Thomas Keck, lurii Kemaev, Michael King, Lena Martens, Hamza Merzic, Vladimir Mikulik, Tamara Norman, John Quan, George Papamakarios, Roman Ring, Francisco Ruiz, Alvaro Sanchez, Rosalia Schneider, Eren Sezener, Stephen Spencer, Srivatsan Srinivasan, Wojciech Stokowiec, and Fabio Viola. The Deep- Mind JAX Ecosystem, 2020. URL http: //gtt//// com/ deepmind
Mare Bellemare, Yavar Naddaf, Joel Veness, and Michael. Bowling. The arcade learning envi- ronment: An evaluation platform for general agents. Journal of Artificial Intelligence Research. pp. 253-279, 2013.
Mare G. Bellemare, Will Dabney, and Rémi Munos. A distributional perspective on reinforcement learning. In Proceedings of the 34th International Conference Machine Learning. ICML, volume 70 Proceedings of Machine Learning Research, pp. 449-458. PMLR, 2017.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http:
//github. collbb.cmm/oooo compboogl//oooo//aaa/aaa/
Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near- optimal reinforcement learning. Journal of Machine Learning Research, 2002.
Sebastian Flennerhag, Yannick Schroecker, Tom Zahavy, Hado van Hasselt, David Silver, and Satin- der Singh. Bootstrapped meta-learning. 10th International Conference on Learning Representa- fions, ICLR, 2022.
Jessica Hamrick, Victor Bapst, Alvaro SanchezGonzalez, Tobias Pfaff, Theophane Weber, Lars Buesing, and Peter Battaglia. Combining q-leaming and search with amortized value estimates. In 8th International Conference on Learning Representations, ICLR, 2020.
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. Association for the Advancement of Artificial Intelligence (AAAI), 2016.
Tom Hennigan, Trevor Cai, Tamara Norman, and Igor Babuschkin. Haiku: Sonnet for JAX, 2020.
URL /attp::/githhe
com/ dwwppeed/ddeeeeeeeeeeeeee http://m-hahait haiku
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. In Thirty-second AAAI conference on artificial intelligence, 2018.
Matteo Hessel, David Budden, Fabio Viola, Mihaela Rosca, Eren Sezener, and Tom Hennigan.
Optax: composable gradient transformation and optimisation, in jax!, 2020. URL http://
github. wwtpo///eeeeiinn/d//m opttx
Thomas Hubert, Julian Schrittwieser, loannis Antonoglou, Mohammadamin Barekatain, Simon Schmitt, and David Silver. Learning and planning in complex action spaces. In Proceedings of the 38th International Conference on Machine Learning. ICML, volume 139 of Proceedings of Machine Learning Research, pp. 4476-4486. PMLR, 2021.
10

---

Under review as a conference paper at ICLR 2023
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143 PMLR. 2020.
Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. International Conference Machine Learning (ICML), 2013.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Ma- chine Learning, 2002.
Qingfeng Lan, Yangchen Pan, Alona Fyshe, and Martha White. Maxmin q-learning: the estimation bias of q-learning, International Conference on Learning Representations (ICLR), 2020.
Controlling
Xiuyuan Lu and Benjamin Van Roy. Intoreation-theorrtic confidence bounds for reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), pp. 2458-2466, 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, are Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518: 529-533, 2015.
Volodymyr Mnih, Adrià Puigdomènech Badia, Mehdi Mirza, Alex Graves, Timothy P. Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Proceedings of the 33nd International Conference Machine Learning, JCML 2016, volume 48, pp. 1928-1937, 2016.
Junhyuk Oh, Matteo Hessel, Wojeiech M. Czamnekki, Zhongwen Xu, Hado van Hasselt, Satinder Singh, and David Silver. Discovering reinforcement learning algorithms. In Advances Neural Information Processing Systems (NeurIPS), 2020.
Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. In International Conference on Machine Learning, pp. 2377-2386. PMLR, 2016.
Tom Schaul, John Quan, loannis Antonogloua, and David Silver. Prioritized experience replay.
International Conference on Learning Representations (ICLR), 2016
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy P. Lillicrap, and David Silver. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588, 2020.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Hado van Hasselt. Double q-learning. In Advances in Neural Information Processing Systems 23: 24th Annual Conference Neural Information Processing Systems 2010., pp. 2613-2621. Curran Associates, Inc., 2010.
Hado van Hasselt, Matteo Hessel, and John Aslanides. When to use parametric models in reinforce- ment learning? In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems, pp. 14322-14333, 2019.
Andrew Wagenmaker, Max Simchowitz. and Kevin Jamieson. Curious model-building control sys- tems. In Beyond No Regret: Dastance-Depentee PAC Reinforcement Learning, 35th Annual Conference on Learning Theory, 2022.
Ruosong Wang, Simon S. Du, Lin F. Yang, and Sham M. Kakade. Is long horizon reinforcement learning more difficult than short horizon reinforcement learning? CoRR, 2020.

---

Under review as a conference paper at ICLR 2023
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Van Hasselt, Mare Lanctot, and Nando. De Fre- itas. Dueling network architectures for deep reinforcement learning. Internation Conference on Machine Learning ICML. pp. 1995-2003, 2016.
Andrea Zanette and Emma Brunskill. Tighter problem-dependen, regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7304-7312. PMLR, 2019.
A APPENDIX
A.1 HYPERPARAMETER AND ARCHITECTURE DETAILS
For reproducibility and completeness in research in Table 2 we report the hyperparameter details for our proposed algorithm MaxMin-Novelty, canomical algorithm e-greedy and NoisyNetworks. Furthermore, for all of the algorithms the hyperparameters and the architectures are identical with each other. Note that the architecture parameters are also identical for the 200 million frame training. Note that we did not tune hyperparameters reported below. To increase transparency in research we kept hyperparameters exactly the same with the prior studies. We ran our experiments with JAX implementation Bradbury et al. a (2018). We used Haiku Hennigan et al. (2020) for the neural network library, Optax Hessel et al. (2020) for the optimization library. and RLax for the reinforcement learning library Babuschkin et al. (2020).
Table 2: Hyperparameters and architectures used in the experiments for our proposed algorithm MaxMin-Novelly, canonical algorithm e-greedy and NoisyNetworks.
Hyperparameters
Settings (For all of the algorithms)
Grey-scaling Observation down-sampling
True (84, 84)
Frames stacked
4
Action repetitions
4
Batch Size
32
Update
Double-Q
Max Frames per episode
108000
Exploration epsilon
0.01
Evaluation exploration epsilon
0.01
Exploration epsilon decay frame fraction
0.008
Gradient error bound
0.03125
Learning rate
0.00025
Optimizer epsilon
0.01 /32
Optimizer
Adam
Discount factor
0.99
Maximum absolute rewards
Number of iterations
40
Number of training frames
10*
Nesterov Momentum
True GPU
Hardware NoisyNetwork parameter
0.1
-eNeworrk channels
32,64,64
--Neworrk filter size
8 x 8, 4x 4,3x3 (1, (2, (1,1) 512
--Network stride
Q- --Network hidden units
12

---

Under review as a conference paper at ICLR 2023
A.2 ARCADE LEARNING ENVIRONMENT RESULTS
Table 3 reports the average scores for human, random, our proposed algorithm MaxMin-Novelty, canonical algorithm e-greedy and NoisyNetworks for all of the games in the Arcade Learning En- vironment 100K benchmark. Scores are reported with the mean over random seeds. The highest score amongst the three algorithms is marked with bold font. We also reported human scores and random scores to provide complete information on the learning curves reported in the main body of the paper.
Table 3: Average returns for human, random, our proposed algorithm MaxMinn-Novelty, canonical algorithm e-greedy and NoisyNetworks across all of the games in the Arcade Learning Environment 100K benchmark. Scores are averaged over 5 random seeds.
Games
Human
Random
e-greedy
NoisyNetworks
MaxMin-Novelty
Alien
7127.7
227.8
498.47
466.50
595.70
Amidar
1719.5
5.8
42.31
42.83
41.94
Assault
742.0
222.4
396.00
375.72
383.25
Asterix
8503.3
210.0
306.36
305,64
410.07
BankHeist
753.1
14.2
15.72
13.1
13.45
BattleZone
37187.5
2360.0
1844.61
1100.00
2200.00
Boxing
12.1
0.1
7.25
4.6
7.9
Breakout
30.5
1.7
4.83
5.33
9.03
ChopperCommand
7387.8
811.0
639.48
919.83
987.83
CrazyClimber
35829.4
10780.5
10075.00
18550.00
9870.00
DemonAttack
1971.0
152.1
1365.60
576.5
745.00
Freeway
29.6
0.0
0.00
5.1
14.00
FrostBite
4334.7
65.2
184.41
167.60
206.40
Gopher
2412.5
257.6
633.84
468.66
664.00
Hero
30826.4
1027.0
1628.42
1884.50
1528.40
Jamesbond
302.8
29.0
21.73
22.08
19.33
Kangaroo
3035.0
52.0
251.00
90.00
280.83
Krull
2665.5
1598.0
2206.02
2040.50
1491.5
KungFuMaster
22736.3
258.5
7116.94
5665.00
4045.00
Mspacman
6951.6
307.3
719.16
912.83
671.08
Pong
14.6
-20.7
-8.18
-2.3
-6.30
PrivateEye
69571.3
24.9
0.25
-7.50
30.0
Qbert
13455.0
163.9
519.71
556.08
466.83
RoadRunner
7845.0
11.5
3600.85
1527.35
670.66
Seaquest
42054.7
68.4
206.49
333.66
348.00
UpNdDown
11693.2
533.4
1858.41
1948.00
1953.91
Figure 6 reports learning curves in the Arcade Learning Environment 100K benchmark with proposed algorithm MaxMin Novelty and the canonical algorithm é-greedy. early training (i.e. up to 4 10a environment interactions) in half of the games observe steeper increase in the performance. This again result of the MaxMin Novelty algorithm targeting higher temporal difference bias. particular, Amidar, CrazyClimber, Hero, JamesBond, Kangaroo, RoadRunner, PrivateEye, Seaquest, UpNDown, Freeway, Breakout and Asterix the gradient of the performance curve for MaxMin Novelty is higher than the canonical algorithm c-greedy. This is again supporting Proposition 3.6 in the main body of the paper. In particular, early in the training the Q-function is 7-uninformed and 5-smooth as has been described Definition 3.1 and 3.2 the main body of the paper. Thus, the steep increase in early training matches the predictions of Proposition 3.6 where positive bias temporal difference yields faster learning-
Also further note that in 6 game simple double-Q learning already outperforms Rainbow in the low data regime. Note that Rainbow has several additional components such as dueling network, multi-step return, distributional reinforcement learning that introduces new parameters as large as
Boxing, Breakout, ChopperCommand, DemonAttack, Gopher, Pong
13

---

Under review as a conference paper at ICLR 2023
11
Tomonalecc
Kergeep
Feet
Figure 6: Learning curves in the Arcade Learning Environment 100K benchmark with our proposed algorithm MaxMin Novelty and the canonical algorithm e-greedy.
the number of bins used the algorithm, and NoisyNetworks.. Thus, the fact that MaxMin Nov- city with simple doublc-Q learning achieves a higher score in these games than algorithm that combines all these various techniques is further evidence that demonstrates the NoisyNetworks can future research direction to obtain
be replaced with the MaxMin Novelty algorithm in Rainbow better performance. Also further note that MaxMin Novelty does not introduce any additional new parameters as NoisyNetworks does; more precisely, NoisyNetworks doubles the number of param- eters used in the Q-network. Hence, the fact that MaxMin Novelty achieves higher performance also reported in the main body of the paper without any additional computational cost further demonstrates the benefits of the utilization of MaxMin Novelty in a more diversified portfolio of cost exploration technique.
algorithms
14

---

Under review as a conference paper at ICLR 2023
A.3 MOTIVATING EXAMPLE RESULTS
In this section we provide more results into the motivating example of the chain-MDP. In particular, while the main body of the paper provides results with the baseline chain-MDP in this section provide more results with the modified chain-MDP. In detail, the modified chain-MDP refers to the chain-MDP with increased action size obtain more fine-grained observations into the effects of the exploration techniques. Hence, the modified chain-MDP consists of n states E S 1,2, 1,2,.... each with four actions. In the modified chain-MDP each state i has one action that transitions the agent up the chain by one step to state i + 1, one action that transitions the agent to state two, one action that transitions the agent to state three, and one action which resets the agent to state one at the beginning of the chain. The Figure 7 reports results for MaxMin Novelty, canonical e-greedy, and the UCB method with varying e E [0.15, 0.25] with a step size 0.025. The results reported in Figure once more demonstrate that MaxMin Novelty performs significantly better compared to prior exploration techniques.
Figure 7: Learning curves the chain MDP with our proposed algorithm MaxMin Novelty, the canonical algorithm e-greedy and the UCB algorithm with variations in E.
A.4 EXTENSION OF MAXMIN NOVELTY TO DIFFERENT REINFORCEMENT LEARNING ALGORITIMMS
While the main paper focuses on Deep Double Q-Network, Figure 8 reports human normalized median and human normalized 80th percentile scores for MaxMin Novelty and e-greedy with the QRDQN algorithn across all of the tasks of the Arcade Learning Environment 100K benchmark. With MaxMin Novelty QRDQN is able to achieve 0.15582 human normalized median score. Note that data-efficient Rainbow can only achieve 0.12 human normalized median scores yvan Hasselt it al. 2011)) Furthermore, note that Rainbow contains dueling architecture, multi-step return, noisy networks on top of the distributional reinforcement learning. Thus, the fact that QRDQN, baseline distributional reinforcement learning algorithm, can achieve human normalized median score that already substantially higher than data-efficient Rainbow once more demonstrates the substantial sample efficiency gained by the MaxMin Novelty algorithm. Furthermore, the significantly higher performance gain obtained by MaxMin Novelty over all tasks of the Arcade Learning Environment 100K benchmark reported via the human normalized scores in Figure [8] once more demonstrates that Max Novelty increases the performance of the baseline algorithms further beyond the per- formance of much more complicated al algorithms.
MaxWin
cgrobdy
MasM MusMnhoree hovely
4-guoddy
0.5
Pumas Monna Sosttedees Be Io
0.150
0.225
0.3-
0.75
0.00
0.1
0.00
Interctionn 110%)
Envtrommett inienccions (207)
Median
8 Percentile
Figure 8: Human normalized median and human normalized 80th percentile scores QRDQN with MaxMin Novelty and e-greedy in the Arcade Learning Environment 100K benchmark.
FQRDQN of the baseline distributional reinforcement learning algorithms.
15


Reviews:
[{"review_id": "wBfaQvNmjy", "reviewer": "Reviewer_S1TB", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This method proposed to use minimal action with the lowest Q value to maximize novelty. The experiment demonstrates the effectiveness of the proposed methods. \n\n", "summary_of_the_review": "\n\nThis paper tried to propose a new novelty maximization method with minor computation costs. However, the main motivation for using minimal-valued action is hard to follow. There are some confusing parts in the theorems, experiments, and algorithms that make it hard to assess the idea.\n\n", "strength_and_weaknesses": "\n\nStrength:\n\nIt's interesting to see that using the minimum-valued action could lead to better exploration. The proposed method is very simple and requires minor modifications to existing methods. \n\n\n\nWeakness:\n\nGenerally, it's hard for me to follow the motivation for using minimum-valued action. The paper seems to claim the minium-valued action should be the one that maximizes the novelty. I didn't see the definition of novelty in Section 3. Although the paper provides several theorems in Sec 3, it's hard to get the main idea of these theorems. \n\nThe improvements in Figure 2 are not very significant. Moreover, on some tasks, the paper demonstrates results with 200 million frame training, while on other tasks, the paper demonstrates result with only 50 million frame training (e.g. Enduro). This is very misleading. Did the proposed method converge on these incomplete-reported tasks?\n\n\n\n\n\nSeveral Questions:\n\nAlgorithm 1 seems quite unclear to me.\n\nWhat do you mean by Populating the Experience Replay Buffer? \n\nDo you mean you need the MDP model (including the transition and reward function)?\n\nHow to obtain $s_{t+1}^{min}$ based on $a^{min}$ (and how to obtain $s_{t+1}$)?  \n\nWhat do you mean by $e$?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "51rntYYy25i", "reviewer": "Reviewer_7Z6y", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "As an alternative to the usual $\\epsilon$-greedy exploration used in DQN and similar approaches, the authors propose taking the action with the minimum Q value with probability $\\epsilon$.", "summary_of_the_review": "The proposed approach isn't guaranteed to converge to an optimal policy, even in the tabular case. While this could be acceptable if the experimental part of the paper was very solid, that is not the case either. I expect the authors to clearly state that the approach doesn't converge to the optimal policy if they plan to submit this paper to any conference/journal.", "strength_and_weaknesses": "Strengths\n- I found the chain MDP experiment to be quite interesting to transmit the issue the authors want to tackle. That is, the fixed noise that comes from initialization of parametric Q functions.\n\nUnfortunately, I have some major worries with this paper.\n\nWeaknesses\n- After some thought, I realized that the proposed method isn't guaranteed to converge to an optimal policy even in very simple examples. Take for example a 3-armed bandit problem with rewards 0, 1 and 2 per arm. An agent that learnt the Q-values 0, 1 and 0.5 for the arms (in the same order as before), will take the second arm (maximum Q value), except for when it's exploring that it will take the first arm (minimum Q value). Thus, it will never be able to explore the third arm, which is the most rewarding one. This is already a big red flag about this algorithm.\n- On top of the main issue with the theory of the paper, I don't find the experimental results convincing. In order to make a fair comparison HP-searches must be ran for each individual algorithm. At the very least, the value of $\\epsilon$ should be tuned differently, as it has a very different role in each algorithm. In fact, model-free approaches have been shown to achieve much higher scores in [1]. I suspect the 0.03 of $\\epsilon$-greedy from this paper comes mainly from a lack of proper hyper-parameters.\n\n[1] https://arxiv.org/pdf/1906.05243.pdf", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1Xi9KCuc9g", "reviewer": "Reviewer_3c9Y", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper claims in the abstract that they develop a method for exploration that is \"theoretically well motivated, and comes with zero computational cost while leading to significant sample efficiency gains in deep reinforcement learning training\". The claim about their experiments is that the \"technique improves the human normalized median scores of Arcade Learning Environment by 248% in the low-data regime\".", "summary_of_the_review": "The paper studies a potentially interesting setting but the claims are not well substantiated.", "strength_and_weaknesses": "Strengths:\nThe claims of the paper are ambitious.\n\nWeaknesses:\nThe paper is not sound.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0hyy19fxfGu", "reviewer": "Reviewer_P9oC", "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": "The paper proposes a method for efficient exploration in discrete-action MDP environments. The intuition is to incentivize the agent to take actions that maximize “novelty”, which is measured in terms of the temporal difference (TD) error from the transition. The authors show that under certain assumptions, the expected TD error achieved by the minimum-value action (the actions that minimizes the Q value) is higher than the expected TD error achieved under a uniform action distribution. Based on this motivation, a simple alteration to the $\\epsilon$-greedy exploration is proposed where, instead of sampling a uniform action with probability $\\epsilon$, the minimum-value action is taken with probability $\\epsilon$. Experiments on ALE and ALE 100K benchmarks show that the proposed algorithm compares favorably to the baselines ($\\epsilon$-greedy, NoisyNetworks) in terms of sample efficiency due to improved exploration. ", "summary_of_the_review": "My initial rating is “5: marginally below the acceptance threshold”. The paper introduces a simple and interesting idea to facilitate exploration and improve the sample efficiency in deep-RL. The results are encouraging. However, I have some concerns about the material presentation and would be happy to reconsider after discussion with the authors.", "strength_and_weaknesses": "**Strengths:**\n\nThe paper makes an interesting connection between the expected TD errors under the minimum-value action and the uniform action distribution (proposition 3.1). The proposed exploration strategy is computationally lightweight and, on the evidence of the evaluation section, seems to improve the sample efficiency in several benchmarks, especially in the limited interaction setting. \n\n**Concerns to address:**\n\nI have concerns about a couple of details mentioned in the paper and the overall presentation. I request the authors to address the following:\n1.  As a conclusion to Proposition 3.1, it is mentioned that the expected TD-error achieved by minimum-value action is higher than that achieved by uniform action distribution. Does this require the entity $D(s) – 2\\delta - \\eta$ to be non-negative, and if yes, does that somehow follow from the definitions? \n2.  Propositions 3.1 and 3.2 are fairly similar in terms of the idea and the proof. I’d recommending moving the Double-Q equations to the appendix to improve the reading experience. \n3.  Algorithm 1 box – could you clearly demarcate (with colors preferably) the difference between standard DQN with $\\epsilon$-greedy and MaxMin-Novelty? Are there differences both in the experience-generation and the gradient-calculation aspects? Also, there seems to be some notation errors in the TD definition in the box.\n4.  Motivating example (Section 4) – when there are just 2 actions, does the difference between $\\epsilon$-greedy and MaxMin-Novelty reduce to just the value of $\\epsilon$? Could you add $\\epsilon$-greedy with different values of $\\epsilon$ to Figure 1?\n5.  In Section 6, it’s not clear if the TD values are computed for all transitions, or only for the transitions with the exploratory action (taken with probability $\\epsilon$).\n6.  It would be good to comment on the limitations of the current method, and/or future work. Any thoughts on extensions to continuous-action environments?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject