$\sbf{\delta^2}$-exploration for Reinforcement Learning
Authors: Rong Zhu
Mattia Rigotti
Venue: ICLR 2022 Submitted (2022)
Keywords: Reinforcement learning
exploration
Q-learning
DQN

Abstract: Effectively tackling the \emph{exploration-exploitation dilemma} is still a major challenge in reinforcement learning.
Uncertainty-based exploration strategies developed in the bandit setting could theoretically offer a principled way to trade off exploration and exploitation, but applying them to the general reinforcement learning setting is impractical due to their requirement to represent posterior distributions over models, which is computationally intractable in generic sequential decision tasks.

Recently, \emph{Sample Average Uncertainty (SAU)} was develop as an alternative method to tackle exploration in bandit problems in a scalable way.
What makes SAU particularly efficient is that it only depends on the value predictions, meaning that it does not need to rely on maintaining model posterior distributions.
In this work we propose \emph{$\delta^2$-exploration}, an exploration strategy that extends SAU from bandits to the general sequential Reinforcement Learning scenario. 
We empirically study $\delta^2$-exploration in the tabular as well as in the Deep Q-learning case, proving its strong practical advantage and wide adaptability to complex reward models such as those deployed in modern Reinforcement Learning.

Under review as a conference paper at ICLR 2022
8² - -EXPLOATION FOR REINEORCEMENT LEARNING
Anonymous authors Paper under Nouble-blind review
ABSTRACT
Effectively tackling the exploration-xxploiaiion dilemma is still a major challenge in reinforcement learning. Uncertainty- -bsed exploration strategies developed in the bandit setting could theoretically offer a principled way to trade off exploration and exploitation, but applying them to the general reinforcement learning setting is impractical due to their requirement to represent posterior distributions over models, which is computationally intractable in generic sequential decision tasks. develop an alternative method to tackle exploration in bandit problems in a scalable way. What makes SAU particularly efficient is that it only depends on the value predictions, meaning that it does not need to rely on maintaining model posterior distributions. In this work we propose 8 explloraaio,,, an exploration strategy that extends SAU from bandits to the general sequential Reinforcement Learning scenario. We empirically study 6² df-exploration in the tabular as well as in the Deep Q-learning case, proving its strong practical advantage and wide adaptability to complex reward models such as those deployed in modern Reinforcement Learning.
Recently, Sample Average Uncertainly (SAU)
INTRODUCTION
In Reinforcement Learning (RL) agent interacts with external environment taking sequences of actions that cause transitions between states of the environment, with the scope to maximize the sum of rewards that are gathered at each state. In typical scenario, the RL agent does initially posses perfect knowledge of the consequences of its actions on the environment, but has to learn that through experience. It therefore has to face the classical exploration-exploiaaio dilemma, i.c. deciding whether to exploit the actions that are known to maximize immediate reward or whether to explore unfamiliar actions and states order to potentially find ways to increase future rewards.
Efficient exploration requires the agent to quantify the accuracy of its current estimates of the state- action values (the conditional expected rewards), so as to trade off expected rewards and uncertainty in principled way (Strehl & Littman 2008 O' Donoghue et al. 2018). Measuring the uncertainty associated with the value of each state-action is thus a key component of conventional algorithms for addressing the wwwoorrtiiiooeppitttttttti dilemma. These ideas have been developed into successful uncertainty- based exploration strategies such as the Upper Confidence Bound (UCB) algorithm, which quantifies uncertainty through confidence intervals (Auer al. 2002), and Thompson Sampling (TS), which instead models the posterior distribution over values ( [Thompoon] 1933). However, obtaining either of these measures of uncertainty for general sequential Reinforcement Learning problems has proven arduous because of their reliance on a measure of uncertainty around the current value predictions, which is typically infeasible to obtain for complex environments and value functions. This difficulty limits the applicability of explorations strategies based on UCB and TS for general RL problems, compromising in particular their adaptability algorithms such as Q-learning (Watkins) 1989 Watkins & Dayan 1992) and DQN (Mnih et al. 2015), which consequently typically resort to addressing exploration via inefficient heuristics like e-greedy action selection.
Recently, Rigotti & Zhu (2021) ) tackled the mentioned limitations of conventional exploration strategies in the constrained but interesting case of bandit problems. Central to that effort was the development of novel uncertainty measure, the Sample Average Uncertainty (SAU), which departs from the approach of estimating the uncertainty of expected rewards of selected actions. In contrast to what is done in UCB and TS, SAU is an uncertainty measure that only depends the value prediction of each action. Specifically, it consists in quantifying the variance of sample averages of rewards under the assumption of known values, which can be used to simply construct estimated

---

Under review as a conference paper at ICLR 2022
variance by plugging in the estimated values. Finally, Rigotti & Zhu (2021) able to use SAU to developed two SAU-based exploration strategies, SAU-UCB and SAU Sampling, which were shown to display sate-of-the-arr performance in multi-armes bandits, contextual bandit, and deep bandits.
In this work, we exploit the simplicity of SAU in Rigotti & Zhu (02T) and extend it from the bandits to the more general sequential RL setting. This extension results in 8 02-exploration, class of exploration strategies for RL which share the implementation simplicity of SAU for bandits as well as its effectiveness. Our -e-exploration algorithms are implementable with a minimal computational overhead that is comparable to e-greedy exploration, while being empirically more effective.
As a practical demonstration, we apply -e-xxplraation to Q-leaning (Watkins) 1989). We then show that the resulting strategies display empirically efficient exploration, which very quickly reach near optimal policies. As mentioned, in terms of computation and memory requirements, these exploration strategies do not add any additional cost compared to for instance a simple c-greedy action selection strategy. Finally, we apply SAU-based exploration to Deep Q Networks (DQN), and observe convincing performance gains over standard DQN in several games we tested from the Atari 2600 domain.
Thanks to its efficiency, flexibility and implementation simplicity, we argue that -x-exorrrti could serve as a competitive baseline and as a simple and strwight-forward replacement to e-greedy action selection in wide class of RL scenarios.
In the remainder of this paper, Section 2 summarizes common exploration strategies in bandits and Reinforcement Learning in order to set the stage for de-exploration. Section establishes the notation and states the problem. Section 4.2 presents the SAU measure, and summarized SAU- based exploration strategies in the setting of multi-armed bandits as developed in |Rigotti & Zhu (2021). In Section we then extend these strategies to the sequential RL setting and develop d=- exploration. Section 6 includes empirical evaluations showing substantial performance improvements over conventional exploration strategies in Q-learning and DQN. Section 7 concludes the paper.
2 RELATED WORK
The most common exploration strategy in Reinforcement Learning (RL) is arguably e-greedy ac- tion selection, which consists in following the action with the highest estimated value with high probability, but occasionally with small fixed probability choosing any other available action uniformly at random. Despite the clear inefficiency of not differentiating lower value actions based on their uncertainty even their value, because of its simplicity e-greedy action selection is still the exploration strategy of choice in RL.
One of the most popular and efficient exploration algorithms is the Upper Confidence Bound (UCB)
algorithm, which is very successful in the bandit setting (Auer et al. 2002 Auer 2003 Rusmevichien
tong & Tsitsiklis 2010 Abbasi- Aubbai--yddkrii Yadkori et al., [011] Abbasi- Yadkori
2012 Perchet & Rigollet
2013:SSivvinn 2014). This approach is based on the principle of optimism in the face of uncertainty,
which elegantly addresses the exploration-exploitatoon trade-off by maintaining confidence intervals
for action-value estimates and choosing actions optimistically within these intervals. Unfortunately.
UCB is difficulty to apply to RL problems on complex domains (Jaksch et al. 2010 2013) due to the complexity of computing its uncertainty measure.
Wen & Van Roy
A related class of strategies UCB are count-based methods (Strehl Littman| 2008 Bellemare
lt al. 2016) that directly turn the counts of state-action visitations into reward bonuses to encourage the exploration of less visited ones. Despite performing optroopti for small discrete Markoy decision processes, count-based methods suffer the curse of dimensionality in high-dimensional environments (although see TTag et al.) (207)) that proposed a possible high high-dimensional extension using learned hashing to discretize the state space).
Another popular exploration strategy is Thompson Sampling (TS) which was introduced by Thompson (1933). This is Bayesian approach that follows the principle of sampling in the face of uncertainty, iee. it samples action-values from a known posterior distribution, then selects the action with the
highest sampled value. TS has been successfully applied in bandit settings (Chapelle & Li 2011
Agrawal & Goyal| 2013; Russo & Van Roy| 2014). It has also been applied to simple Reinforcement
I Learning problems (Strens Oshand et al. 2013). However, because calculating the posterior
2

---

Under review as a conference paper at ICLR 2022
distributions over values is intractable in the general case, implementations of TS in moderately sophisticated domains require the application of posterior approximation methods, like for instance in Osband et al. (2016). which, at least in the contextual bandit setting, known to be inefficient (see Riquelme et al. (018)).
PROBLEM FORMULATION
We recall the definition of a Markov Decision Process (MDP) set of states S and actions A so that,
given a current state E S and an action a E A, the probability of ending up in the next state s' E S (ss((a). where P : S x A x S - [0; 1] is fixed state transition distribution with Eg Pso (a) Morcover, the reward r is drawn from reward distribution with EE[rls, a. s = -Rs (a). The optimal
1.
value function (s, a) solves an MDP by satisfying the following set of Bellman equations for given discount factor E 10;
(=(s,a)= P Pos (a) Res + + max ('(' .o) a'EA
Vs,a. a.
MDPs can be solved using Q-learning (Watkins 1989.. Let Q a) be the current estimate of the value of action a in state s, and let s be the state that follows s upon taking a, and be the corresponding reward. Then Q-learning consists in updating the action-value function using learning rate a as follows:
((s + ((s,a) + r + max Q(s'sa') Q(s,
a'EA
In this update rule, Q-learning uses the max operator as an estimate the value the next state. The term in the squared brackets
a'EA 8= max Q(5 Q(s,a)
known as the TD-error, because it is a generalization of the reward prediction error in the case of Temporal-Differet learning algorithm.
A last element that is crucial for the Q-learning algorithm to converge the optimal value function is exploration. That is why Q-learning is typically implemented combination with c-greedy action selection, a simple and rather successful exploration strategy proposed in /Sttonn & Barto (2018) that prescribes to fix a small probability and choose an action at time / as follows:
a A uniformly at random, with probability e: al
(2)
a = arg max.cA {Q(s,, ()),,,)),, with probability 1.
As mentioned in the previous section, e-greedy exploration has the obvious inefficiency that, during an exploratory event of probability actions are selected without differentiating on their uncertainty or even their value. But because of its simplicity c-greedy action selection typically the exploration strategy of choice in many successful RL. applications, such as Mnih et al. (2015).
4 SAMPLE AVERAGE UNCERTAINTY FOR CONTEXTUAL BANDITS
The Sample Average Uncertainty (SAU) is measure of uncertainty that was recently proposed as simple and scalable mechanism to promote exploration in the bandit setting (Rigotti & Zhu (021). For ease exposition we introduce SAU from the contextual bandit perspective and notation.
4.1 CONTEXTUAL. BANDITS
In contextual bandits at each step t the agent observes a context vector 8; E X, selects an action aa from a set A, after which a reward r, corresponding the chosen action received. The value of an action a in context is defined as the expected reward given that is selected, and is assumed to be a fixed but unknown function of 8; and a: [] = a] = past, a). The goal is to design a decision- making policy ग X A that maximizes the expected reward. This goal is readily quantified in terms of minimizing expected regret, where, if action a is chosen at step f after observing context AfMsse
st, say that incur expected regret max (M(s), a')} u(st, a.), which is the difference between the optimal value received by playing the optimal action and the value received following the chosen action.
3

---

Under review as a conference paper at ICLR 2022
4.2 SAMPLE AVERAGE UNCERTAINTY EXPLORATION IN BANDITS
Let Ta denote the set of time steps when action a was chosen so far, and let n(a) be the size of this set. Assume there is a sequence of estimators {ā(s, aE), of pa(sa)) a). The Sample Average Uncertainty (SAU (Rigotti & Zhu 2021 ) statistic raa) is defined as
T(a)² = a(
2 EET
Σ
with 6 = - -0(8, 0z).
(3)
Obviously, computing the SAU measure only requires the prediction residuals e, = Tt Mrst, ar). without any need to model or access the uncertainty of a))),
Reference Rigotti Zhu (022)) combined this uncertainty measure with UCB and Posterior Sampling exploration and proposed two exploration strategies for contextual bandits named SAU-UCB and SAU-Sampling.
SAU-UCB. SAU-UCB (Rigotti & Zhu 2021 consists in the use the SAU uncertainty measure Ta)? as the exploration bonus in the principle of "optimism in the face of uncertainty". This works as follow: given value predictions ((st, a) at step define Y (st, a) jass,, a) vn(a)->r(a)' log t, where n(a) is the times action a was taken. Then choose the action by maximizing over that: ag arg m {Y (s),a))
Thompson Sampling (TS) promotes exploration by sampling value estimates from modelled posterior distribution. The SAU-Sampling algorithm (Rigotti & Zhu 2021) also adopts this principle of "sampling the face of uncertainty", but unlike TS it does so by sampling values from parametric Gaussian distribution with mean given by the prediction and a variance proportional r(a)², resulting in values Y (st. ~ N (p(s), r(a)2/n(a)) from which then an action is again selected by maximization: a, arg max (s;,a))
SAU-Sampling.
In summary, in contrast to uncertainty-basee exploration strategies like UCB and TS that first measure the uncertainty of the action-value estimates j a) given the past observations, SAU-based exploration directly quantifies the uncertainty associated with each action through equation 3 by measuring the uncertainty of the sample average rewards. The clear advantage of this procedure that it is much simpler and more computationally efficient, while at the same time providing the same quality uncertainty estimates, and often even better exploration than the more complex algorithms that rely on estimating the uncertainty of the value function (see empirical results in (Rigotti & Zhu (02I))
5
8 EXPLORATION: SAU-BASED EXPLORATION FOR SEQUENTIAL RL
The SAU-exploration algorithms summarized in the previous section have been shown to be very effective exploration strategies despite their low computation footprint including the deep contextual bandit case where the reward is being parametrized by deep neural network (Rigotti & Zhu| (202I). We now propose an extension SAU to adapt from the bandit to the sequential reinforcement learning scenario. We call the resulting class of exploration algorithms 5² expllorrai....
contextual bandit setting,
5.1 DXEEXLLRRNIION IN Q-LEARNING
Contextual bandits are essentially simplified MDPs with horizon so that each episode only consists of state observation (which in contextual bandits is called "context"), an action and reward, after which the environment is reset. Because of this relationship. the first step to extend results in bandits to sequential reinforeement learning is substitute the bandit feedback r, equation with the multi-step cumulative return Gr, defined as G, = Σr= Tt+++1 the case of episodic tasks or G. = Eiep ~ *r++++ with discount rate in the case of infinite horizon tasks. The value prediction terms, 14(s, a) in equation 3 correspond in sequential RL setting the state-action value qa (s, a) under some policy π, and can therefore be substituted with Q a), its current estimate at a given time.
4

---

Under review as a conference paper at ICLR 2022
At this point, we notice that Q-learning uses target approximate the cumulative return G2 with the one-step iteration r2+1 + y max,' Q ($t+1. aa)) (Suttoon ( & Barto 2018), and we can therefore use the same approximation in extension of SAU from bandits to sequential RL.
Note that the SAU measure is not function of the current context 8; but just depends on action a. A key mechanism explaining why this simple method works is the assumption that the noise in each arm homogeneous. This is good approximate description of the data-generating process underlying complicated reward models such as deep neural networks, in particular when there wouldn't anyway be enough data to provide an accurate fit of uncertainty as a function of context. In sequential RL, the reward models might indeed be complicated, which bodes well for applying the SAU measure in this setting, especially in the deep RL case.
We now have everything to formulate the sequential RL version of the SAU uncertainty measure To in equation 3 that we call -e-uncertainty:
(a)
(s,,
(4)
n(aa)
where 6ss,, az) denotes the TD-error in equation
| at an observed sequence 8t, az T++1, 81+1, i.e.:
Ö(5,, 0z) T + max a'EA
Q (s++1, Q(se, ae),
and the sum in equation 4 is over the set T. of time steps when action was chosen up until the current time, and v((a) denotes the number of times that the action a was observed.
In practice, (-) in equation 4 can be efficiently computed by incrementally updating running estimate that accumulates the TD-error:
( (a) (a)) + (s) /n(a).
(5)
Comparing the derived expression equation for the -2-uncertay 2 with the definition equation of the SAU measure solidifies the intuition that the role played by the prediction residual in equation 3 for the bandit feedback is naturally taken up by the TD-error 5(st, az) in sequential RL.
As in the case of SAU-based exploration in bandit problems, once the -uuncertainty is available it can simply be plugged into the action selection process to implement class of exploration algorithms that we call 8 oe-exploration. The expllrrran algorithm that is obtained by using the de-uncertainty as in UCB will be called 82-UCB. Analogously, the expllorran algorithm obtained by combining the -u-uncertaint with sampling-based exploration will be called 82 -amplinn
More specifically, given action-values Q(*t, a) at a given state 8; at time i, 8e-exploration implements exploration by "perturbing" action-values ((s,, a) according to one of the following schemes, depending on which specific exploration algorithm we want use:
1. 5C-UCB:
A ( logt n(a)
((s,, a) = Q(st, a) + V
Va E A:
2. d²-Sampling:
((s. 0) ~ N (Q(er,))
A2(a)
Va A. a))
n(a)
Then an action is selected by maximization: a; arg max
The two 8² o2-exlloration algorithms 82-UCB and -a-Samling are detailed in Algorithm |
5.2 COMPARISON BETWEEN VALUE UNCERTAINTY EXPLORATION AND 82 EXPLORATION
Let take moment to compare the functioning of 5e-exploration to conventional exploration strategies based on estimating uncertainty of value estimates, such as UCB and posterior sampling (Thompson Sampling) methods. We call these methods "value uncertainty exploration methods" because the mechanism that they use to promote exploration relies on quantifying the uncertainty of the current value function estimates. Maintaining this "internal uncertainty" measure is typically
5

---

Under review as a conference paper at ICLR 2022
Algorithm 1 8 -e-expoort in Q-learning.
Parameters: step size E (0, 1], discount factor n, E (0, 11, and B21 1. Initialize: Q(s, a) such that ((terminal,-) - 0, A aa = 0, and n(a) = 1 for a E A. for all episodes do
Initialize state 8
while in episode is not terminal do
(1) Use 82-exploration strategy (a) or (b):
(a) 82-UCB:
(a log Eo n(a)
Q(s,a)= - Q(s,a) +
n((a)
(b) Sa-minnnn
((s, ~N N ((N(000 (((,,a)
A2(a)
n(a)
(2) Select a in state s:
arg max l (Q(s, (0()
n(a) + (a) +1.
(3) Take action a, observe r, 8'
(4) Update Q(+) and A-
8(s,0) + 7 -(s's))
Q(s,a) + +a aa.
(² + A²(a) (s) <²(a)) /n(a).
(5) Step to next state: +- s end while end for
computationally costly, to the point of being computationally intractable for large state spaces. Thompson Sampling in particular assumes prior distribution over value functions that is updated based on observed transitions, a process that only feasible for simple environments.
In contrast, rather than maintaining the internal uncertainty of value function estimates, e2-exlloration simply updates its propensity for exploration by accumulating the reward prediction error in equation 55 In other words, ó not only has role in policy evaluation by representing the extent to which the value function should be update, but also has a role the control policy by representing the extent to which exploration is needed to prevent the policy from being suboptimal.
Figure gives a schematic overview of the difference between value uncertainty exploration methods and our proposed method d ox-explor,,,on, emphasizing the simplicity of oe-exploration whose explo- ration mechanism does not need to rely on estimating the distributional uncertainty over the value function, but only needs access the reward prediction error 8 compute the 52-unncrtainty A.
Once the uncceraaay is available, is directly passed to the action selection step (see step (2) in Algorithm []. This means that the -uuucertain besides being cheap compute, is also simple to use to instantiate the exploration mechanism: it is simply used to "perturbe" the estimated action-values (either as exploration bonus in the case of 52-UCB or sampling noise in the case of S2mSanlligg) before greedily selecting the next action. This underscores that from computational standpoint the action selection process of oe-explora is as simple as e-greedy action selection (equation 2). Indeed, exploorran inherits this trait from SAU-exploration (Rigotti & Zhu 2021). and similarly to that algorithm can be used flexible drop-in replacement for c-greedy selection.
5.3 8 E'-ELLLRANIO IN DEEP Q-LEARNING
Deep Q-learning consists in parameterizing the ie. Deep Q Network (DQN) policy network (Mnih et al. 2015).. Because of the complexity of such an action-value function, it is notoriously difficutt to implement efficient exploration strategies in DON. As result, dithering heuristics such as e-greddy are commonly used in practice. Fortunately,
function Q(s,, a) as a deep neural network,

---

Under review as a conference paper at ICLR 2022
Figure 1: (a) Value uncertainty exploration algo- rithiss like UCB and Thompson Sampling rely on an estimate of the uncertainty of the current value functtio,, quantity that is intractable already for moderately complex value functions and environ- ments. (b) oe-exploration on the other hand only needs access to the reward prediction error to compute how to select action that trades off exploration and exploitation in a principled way.
unceriainly exploration
-xxploraatoo
Agent
Agent
exploration
exploration
Movertalarry
valuu function
value function
Environment
Environment
8 -e-explorai just depends on the prediction of value function, so versatile enough to be easily applicable to DQN.
direct way to combine 8 -e-explortioon with DQN would be to implement Algorithm | Jsiig a deep neural network (in addition to the policy network) that would fit the de-exploration measure A. To avoid the computational and memory overhead of an additional network we took inspiration from recent papers that harnessed the targer network in DQN (a delayed parameter version of the policy net used in Mnih et al. (2015) 5 to stabilize training) in order to implement unbiased estimators of the value (van Hasselt al. 2016 Zhu & Rigotti 2020). We reasoned that the difference between the online policy net ((8, (5,a a) and the delayed parameter target net Q (s, a) should reflect a minimization of the reward prediction error. This suggests replace the expression equation 4 with the following expression for the 0² -n-uncerty A:
A 2p, a) (max (ss.a') Q- (s.
We propose to use this variation of the 82 ---uncertainty to implement the DQN version of ex-exlrorai algorithms 82-UCB and d2-Sampling. Using expxoorraai DQN therefore comes down to implementing DQN learning usual (see e.g. et al. (2015), except that the action selection part of the algorithm (which typically would use e-greedy action selection) is replaced as Algorithm
Algorithm 82 -e-exploration Deep Q-Networks.
1: Initialize: Regular DQN (Mnih et al. 2015) with policy network Q(s, a), target network Q- (s, a), and global action counts n(a) initialized at 1 for all a E A.
2: Replace action selection ACT(-) in regular DQN with:
3: function ACT-8--EXPLORATIOON -EXPLORATIOO(()
4: for 1, 1,..., [A] do
Lin (8, a) (mmx))(mxx(mm00)
(max ((xx))
((to)aa)(((sssaa)) (s,a))²
5:
Compute
6:
(2) Use 62-exploration strategy (a) or (b):
7:
(a) UCBBB
A2 dgn (s, log n(a)
Q(s,a)
n(aa)
(b) Samplinn
(s,
(( N ((s,a))
n(a)
9:
end for
Select action arg (((x
11:
Update global count n((*) f- n((a) +
Return action a*
13: end function
7

---

Under review as a conference paper at ICLR 2022
6 EMPIRICAL RESULTS
We now empirically evaluate the performance of our proposed oe-exploration strategies in a series of reinforcement learning tasks, including classical tabular Q-learning and Deep Q Learning tasks.
We will benchmark 8 ee-expooan against c-greedy action selection, the de facto go-to exploration strategy in Q-learning, and also the closest exploration strategy in terms of computational and implementation efficiency. In fact, we propose -e-explorttion as a flexible drop-in replacement for 6- e-greedy action selection that we now demonstrate is remarkably more efficient, despite being comparably simple in terms of computation and implementation complexity.
6.1
Q Q-LEARNING ON
TASK
Surn of revards
eploode
225
sum of rewerdds
-20
s.d. of the fhat sptodds
25
50
20
40
15
15
e-greed
10
e-greedy 5-UCB 6-8ampling
Sampling
5+
0
1000
episode
3000
5000
E-grady
Semp
1000
episoci
5000
5000
grawndy
s-cce
8 Samp
(a) 10 5 grid.
(b) 20 grid.
Figure 2: Clikf-walking RL task. Both 8² -eeelorration algorithms achieve higher cumulative reward faster rate than e-greedy action selection for both grid sizes, even attaining the optimal reward (indicated by the black dotted line). Moreover, as the bar plots show, de-exploration reaches a lower variability of received rewards, which indicates that is more stable. e-greedy exploration with e = 1=1//n(a where ns)) is the number of times state s has been visited. Learning rate is set to (5, 0.1 1)/ (100 + +n(s a)). where n(ss, a) is the number of updates of each state-action. Data points are averaged over 1000 runs.
We evaluate the performance of 82 Pexploraation on the cliff-walking task (Example 6.6 in Sutton & Barto (2018), standard undiscounted episodic task with start and goal states, and four movement actions: up, down, right, and left. Reward is -1 on all transitions except those into the "Cliff" region (bottom row except for the start and goal states). If the agent steps into this region, she gets reward of 100 and instantly sent back to the start. We vary the environment size by considering 10 x and 20 x 5 grids.
We measure performance as cumulative reward during episodes, and report average values for 1000 runs and standard deviation of values of the final episode in Fig. 2 We compare our two proposed 8 -eexlooraai 52-UCB and 82-Sampling against e-greedy action selection with 1/ 1/vn(ss). As Fig. 2 shows the 52-exloorttion strategies perform much better than e-greedy, quite quickly attaining near optimal values (the reard value indicated by the black dotted lines in the plot). We also compute the standard deviation of rewards of the final rewards of 1000 runs, which show that 8 -e-exlorrt strategies display much lower variability (i.e. are more stable) than e-greedy action selection.
6.2 DERP Q NETWORK ON THE ATARI 2600 DOMAIN
As final empirical validations for o2-expoorationn we study the performance of our DQN adaptation Algorithm 2 on 8 representative games from the Atari 2600 domain (Bellemare et al. 2013). We choose 4 "easy" games for which DQN displays super-human performance, and 4 "hard" games for which DQN performs around or below humans. We compared the performance of the 52-exploration algorithms with the conventional e-greedy action selection that consists of annealing for the first
IM steps from 1.0 linearly to e 0. noisy nets (Fortunato et al.) 2017 and Bootstrapped DQN (Osband et al., 2016). a strong baseline, but which requires a form of ensembling resulting in considerable memory overhead. Fig. compares the performance the end of training for e-greedy, Bootstrapped DQN, noisy nets and our 82 explllrrann algorithms. The advantage of 8² -xpllorraa particularly remarkable for harder games, and in particular MsPacman, where our algorithms finds
8

---

Under review as a conference paper at ICLR 2022
policies that reach scores that are almost double what the other competitors reach, and Centipede, where Sammanng vastly outperforms even Bootstrapped DQN.
VidooPiiball
Broakout
Demonfittcck
Assaul:
McPacman
DoubleDurk
Certipodc
2000
40-
(% of human perferranel
50000
1233
204
Nomalize scoee
1:00-
20000
12600
1000
933
300-
903-
300
201-
150+
10+
50C
260
50-
20
200
1000
E-greet boodeite
SUUCB
Figure 3: 8 expploraan DQN policies consistently outperform e-greedy exploration and noisy nets and are on par and sometimes better than the strong but computationally costly Bootstrapped DQN in the Atari 2600 domain. DQN training is done for 20M steps for all games, except VideoPinball which is trained for 80M steps (see Appendix A Performance is then computed as the average score over the last IM frames of training. Bars indicate score normalized to human performance (see MMnh ct al. (2015)) across random seeds, error bars are SEM. 8--UCB and ja-Sampling exploration compared to e-greedy exploration with linearly decreasing over 1M steps starting from 1.0 to 6f 0.1, as standard (Mnih et al. 2015). Both ee-exllort strategies reach consistently competitive policies at the end of training.
7 CONCLUSIONS AND DISCUSSION
Here we extended Sample Average Uncertainty, a recently proposed uncertainty measure for explo- ration, from bandit problems to the general sequential reinforcement learning setting. This resulted in our -e-exoorrt algorithms, two exploration strategies that are extremely simple and flexible to implement, as they only depend on the predicted action-values. These can be used as drop-in replace- ments for e-greedy action selection in Q-learning and DQN, resulting in effective and computationally efficient learning and superior empirical performance over the e-greedy baseline.
Our work provides a simple, scalable and robust exploration algorithms, that can be effortlessly deployed to mitigate the exploration-exploittaaie dilemma. While the resulting consequences of the deployment of an RL. algorithm. ethical or otherwise, will clearly depend on the specific applications, believe that providing efficient uncertainty estimates and more reliable exploration than the common e-greedy action selection strategy will potentially have a positive contribution in terms of sample-efficiency and optimality of the learned policies, as well as in terms of their trustworthiness.
We limited our experiments to comparisons against c-greedy exploration, given its importance and ubiquity, and because our method was developed specifically as a natural drop-in replacement for e-greedy exploration. Our -e-exlooration algorithms have in fact a comparably low computation footprint and can be implemented through a minimal API that is the same as for e-greedy explo- ration, only needing to access the action selection process of the RL agent. This enables modular implementations with minimal change on existing RL code bases, as for instances exemplified by the DQN version of 22-exploration in Algorithm 2 which simply consists in the replacement of the action selection method in a conventional DQN with no modification of the training algorithm. This is in stark contrast with previous exploration strategies based on quantifying value uncertainty, which typically impose limitations on the representation of the value function, need to heavily modify the evaluation process, and introduce costly training loops update the value uncertainty.
That said, the remarkable performance of our simulation results and the flexibility of ee-exlorrtiion suggest that it could be applied to even more sophisticated RL settings and possibly combined with other learning algorithms besides Q-learning and DQN, an option that we are looking forward to investigating in the future.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
We provide detailed pseudo-code of our proposed algorithms and tried our best to indicate important hyperparameters replicate our experiments and reproduce our benchmarks, which are anyway based on tasks that are already publicly available. In addition, upon acceptance of our paper, we plan release the code replicate all our numerical experiments on github.
REFERENCES
Yasin Abbasi- Yadkori. Online learning for linearly parametrized control problems. PhD thesis, University of Alberta, Edmonton, AB, Canada., 2012.
Yasin Abbasi- Yadkori, David Pal, and Csaba Szepesväri. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, volume 24, pp. 2312-2320, 2011.
Shipra Agrawal and Navin Goyal. Further optimal regret bounds for Thompson sampling. In Proceedings of the 16th International Conference on Artificial Intelligence and Statistics, pp. 99-107, 2013.
P. Auer. Using confidence bounds for exploiiation-eepllrraion trade-offs. Journal of Machine Learning Research, 3:397-422, 2003.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite time analysis of the multiarmed bandit problem. Machine Learning. 47:235-2555 256, 2002.
Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279, 2013.
M.G. Bellemare, S. Srinivasan, G. Ostrovski, T. Schaul, D. Saxton, and R. Munos. Unifying count- based exploration and intrinsic motivation, In Advances in Neural Information Processing Systems, 2016.
Olivier Chapelle and Lihong Li. An empirical evaluation of Thompson sampling. In Advances in Neural Information Processing Systems, volume 24, 2011.
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. arXiv preprint arXiv: /706 7706. /0295, 2017.
Jaksch, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11:1563-1600, 2010.
V. Mnih, Kavukcuoglu, D. Silver, A.A. Rusu, Veness, M.G. Bellemare. A. Graves, M. Riedmiller, A.K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Ku- maran, D. Wierstra, S. Legg, and D. Hassabis. Human-level control through deep reinforcement learning. Nature, 518:529-533 2015.
B. O' o'Donoghue, I. Osband, R. Munos, and Mnih. The uncertainty Bellman equation and explo- ration. In Proceedings of the 35rd International Conference on Machine Learning, 2018.
I. Osband, D. Russo, and B. Van Roy. (more) efficient reinforcement learning via posterior sampling. In Advances neural information processing systems, 2013.
I. Osband, C. Blundell, A. Pritzel, and B. Van Roy. Deep exploration via bootstrapped dqn. In Advances in neural information processing systems, 2016.
V. Perchet and P. Rigollet. The multi-armed bandit problem with covariates. The Annals of Statistics, 41(2):6937221. 2013.
M. Rigotti and R. Zhu. Deep bandits show-off: Simple and efficient exploration with deep networks. arXiv preprint arXiv: 105.0.00..4000 046833,, 2021. htR.httt:://arttt wrw. httgg//bb//0000 046883
10

---

Under review as a conference paper at ICLR 2022
Carlos Riquelme, George Tucker, and Jasper Snoek. Deep Bayesian bandits showdown: An empirical comparison Bayesian deep networks for Thompson sampling. In Proceedings of the 6th International Conference Learning Representations, 2018.
Patt Rusmevichientong and John Tsitsiklis. Linearly parameterized bandits. Mathematics of Opera- lions Research, 35(2):395-411, 2010.
D. Russo and B. Van Roy. Learning to optimize via information-dirreted sampling. In Advances in Neural Information Processing Systems, volume 27, pp. 1583-1591, 2014.
A. Slivkins. Contextual bandits with similarity information. Journal of Machine Learning Research, 15(1):2533-2566 2014.
A. L.. Strehl and M. L.. Littman. An analysis of model-based interval estimation for Markov decision processes. Journal of Computer and System Sciences, 74(8):1309-1333 2008.
M. Strens. A bayesian framework for reinforcement learning. In Proceedings of the 17th international conference on Machine learning, pp. 943-950, 2000.
Richard Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition edition, 2018.
H. Tang, R. Houthooft, D. Foote, A. Stooke, X. Chen, Y. Duan, Schulman, F. De Turck, and P. Abbeel. #Exploration: A study of count-based exploration for deep reinforcement learning. In Advances in Neural Information Processing Systems, 2017.
William R. Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25:285-294 294, 1933.
H. van Hasselt, A. Guez, and D. Silver. Deep reinforcement learning with double Q-learning. In Proceedings of the 30th AAAI Conference on Artificial Intelligence, pp. 2094-2100, 2016.
C. J. C. H. Watkins. Learning from Delayed Rewards. PhD thesis, King's College, Cambridge, England, 1989.
C. H. Watkins and Dayan. Q-learning. Machine Learning, 8:279-221 29299292,2222 1992.
Z. Wen and B. Van Roy. Efficient exploration and value function generalization in deterministic systems. In Advances in neural information processing systems, 2013.
R. Zhu and M. Rigotti. Self-correcting q-learning. arXiv preprint arXi:2011..11000
A ADDITIONAL FIGURE

---

Under review as a conference paper at ICLR 2022
Atlantis
Assault
oggeddy
human perfor performance)
performance
buckstrap
Nermalizss cormalized score
(% Normalized score
8000
nskay S1-Sumplingg
P-UCB
1000
300
100
Sampling
J-UCB
0.0
2.5
5.0
7.5
10.0
12.5
16.0
17.5
200
0.0
2.5
5.0
7.5
10.0
12.5
15.0
17.5
200
Frame [X]
Frame [x]]
200000
VideoPinball
55
MsPacman
(36 of human per nerformanze)
busteerrp
engreedy
(5 of human performance aance)))
30
e-gredyy
buststrap
20000
Normalized score
Sampling
11-Sampling
12000
s V-UCB
Normalized
10000
2000
Frame [xc] (P)
Frame
[x [x100]]
1500
Breakout
600
DoubleDunk
(% of human perfon performance)
1200
boststrap
e-gredd
Norm llzdalized (%6 human performance)
500
Normalized score
nolty
6 Sammpling
-yyeedy boctstuu up
UCB
200
(--S F--Samplin
300
UCD
100
0.0
2.5
5.0
7.5
10.0
12.5
16.0
17.5
200
-100
0.00
2.5
10.0
12.5
15.0
17.5
200
Frame [X]]
Frame [x100]]
DemonAttack
50-
Centipede
engreedy
(% of human neformance)
buststrap
Normalized (% of human performance)
Normalized score
s'-Sampingg
300
UCBB
200-
10-
boctstrap
200
Samppigng
10
8-UBB
0.0
255
5.0
7.5
10.0
12.5
15.0
17.5
2010
0.0
10.0
125
15.9
17.5
2000
Frame [X((0P
Frame [x [x100]
Figure 4: Learning curves of e-greedy exploration, bootstrapDQN, noisy nets, 62-UCB and 82_ Sampling on 4 "easy" and "hard" (i.e., performance of DQN is respectively higher and lower than that of human players) additional Atari 2600 games. Scores are averaged in intervals of 500k frames, plots indicate mean score over independent random seeds, and shaded areas indicate min and max scores over the seeds. 52-exploration algorithms consistently have scores among the highest throughout learning compared to the e-greedy strategy, noisy nets and bootstrapD Remarkably, for two "hard games", Assault and DoubleDunk, for which e-greedy only reaches sub- human performance, oe-exploratioo can very rapidly find policies that beat human players by more than 200% and 500%, respectively, rivaling the performance bootstrapDQN, For VideoPinball and Centipede where e-greedy seems unstable, -e-exlorrat strategies able to maintain better stability throughout leamning even beating bootstrpDQN in some cases like Centipede.
12


Reviews:
[{"review_id": "oB55QndWcV", "reviewer": "Reviewer_PFBt", "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": "The paper are well-written and easy-to-understand. However, there are following concerns from my point of view.\n\nThe algorithm looks like a trivial extension of SAU method developed by Rigotti & Zhu. There should be more discussion about the difference between $\\delta^2$-exploration method and SAU method. To me, it seems the technical novelty of the algorithm design is rather weak.\n\nThe authors fail to explain why this simple exploration strategy can work (or at least better than $\\epsilon$-greedy). As far as I am concerned, collecting enough samples for an action on certain states cannot indicate well-exploration of such an action on any other states. There are many simple hard instances that this strategy may fail. For example, we can construct an MDP in which the agent will always enters state $s_1$ with high probability, and occasionally enters $s_2$. The expected reward of $a_1$ is higher than $a_2$ in $s_1$, while the expected reward of $a_2$ is higher than $a_1$ in $s_2$. Using $\\delta^2$-exploration strategy, the agent may never take action $a_2$ in $s_2$ if the expected reward of $(s_2,a_1)$ is higher than $(s_2,a_2)$ in the first several attempts. Therefore, I believe the exploration strategy is not theoretically-convinced enough to obtain good performance on all possible RL tasks.\n\nThe experiments in the paper seems not enough to indicate the benefits of $\\delta^2$ exploration mechanism. The authors evaluate their algorithm on the Cliff-Walking task and the Atari games. For the former, the reason why the $\\epsilon$-greedy algorithm achieves slightly worse performance may be that the agent may occasionally choose the bad action due to the $\\epsilon$-greedy mechanism. This case may not always happen in the general RL tasks. For the latter, the authors only conduct experiments on 8 games. I believe that more experiments are necessary (on other games or even other benchmarks such as Mujoco tasks) if the authors want to argue that $\\delta^2$-exploration could serve as a competitive baseline or even replace the role of $\\epsilon$-greedy in RL. Also, I doubt whether these games are particularly selected or randomly chosen. ", "summary_of_the_paper": "This paper extends a recently-proposed exploration method called SAU in bandits to the RL problem. They combine this exploration approach with the standard Q-learning algorithm. Their experiments show that this approach can obtain better performance compared with the Q-learning algorithm with eps-greedy exploration.", "summary_of_the_review": "Based on the above issues, I am inclined to given a negative score. I will increase the score if the above problems are well-tackled in the rebuttal:\n1. Discussions on the comparison with SAU method by Rigotti & Zhu.\n2. Explanation of the insight behind the exploration strategy.\n3. More experiments to support their conclusion.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "csHzdZlKi5", "reviewer": "Reviewer_zyS1", "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": "\n#### Strengths\n1. SAU has good theoretical justification in bandits. This paper contributes to connecting the RL theory and empirical RL, two largely separated areas. I think this should be encouraged. \n2. The algorithm is simple and can potentially be extended to other methods such as policy gradient.\n\n#### Weakness\n1. The experiments are mainly compared against vanilla DQN. Since the authors' algorithm is a modified DQN, it would be fairer to compare their algorithm against other modified DQN variants, such as Rainbow, etc. In particular, the authors should compare with DQN with random network distillation (RND), because RND can also be interpreted as adding a UCB-type bonus and thus share similarities with the authors' algorithm.\n2. The experimental results seem not improve much upon existing algorithms in RL. \n3. It is strange to use the same counter $n(a)$ across different states, instead of a state-dependent one, e.g. $n(s, a)$. This does not make much sense. May the authors further justify this part? Or provide further ablation studies, e.g. fixing $\\delta^2 \\equiv 1$, to see if the performance of their algorithm is indeed due to the SAU?", "summary_of_the_paper": "This paper studies exploration bonus in practical deep RL based on Sample Average Uncertainty (SAU) and upper confidence bound (UCB). SAU is a recently studied novel uncertainty quantification that works for rather arbitrary estimators. Previous paper has studied how to use SAU to derive UCB-type bonus in multi-armed bandits and proved that it could achieve optimal regret. \n\nThis paper successfully extends the SAU-UCB-type exploration bonus from bandits settings to RL and most importantly, deep RL settings, and shows how to incorporate SAU-UCB-type bonus in (deep) RL. This paper conducts various experiments for RL and deep RL, demonstrating the advantage of their algorithms over the standard benchmarks. \n\nThe paper is generally well-written.", "summary_of_the_review": "I think the novelty outweighs the weakness, and I would recommend weak accept.\n\n**After Discussion:** I read other reviewers' reviews. Weakness 1 pointed out by Reviewer o8hT mentioned a paper that seems to contradict this paper [Zhu and Rigotti, 2021], and the authors seem not responding to this concern. Also, Reviewer uzFB pointed out several other baselines, including Boltzmann exploration and inverse-gap, that the authors did not compare with. I think the first concern downgrades my evaluation on the theoretical strength of this paper, and the second concern downgrades the empirical strength. Thus, I would like to recommend weak reject.\n", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_tTnPFXtKcx", "reviewer": "Reviewer_uzFB", "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": "The method is simple and intuitive, and I think it's an interesting idea. However, I have various concerns about the paper. \n\nThe paper does not try to claim any connection with theory, but I'm wondering what is the intuition behind this approach. In particular, the idea of averaging over states seems very suboptimal in RL. In particular, it is easy to imagine problems where you have only a few actions available (in the extreme case one) in certain states that are visited often. By using your method you are decreasing the uncertainty of these actions (by dividing by the total counter $n(a)$) also in states that are maybe hard to reach, potentially leading to under-exploration. I understand that the numerator is a squared error, but it still seems potentially critical. It would be good to test your method in other tabular domains where this situation may happen.\n\nThis leads me to the second issue: experiments are not enough to support your claims. First, I disagree with the argument that you need only to compare with the $\\epsilon$-greedy strategy. Second, there is not enough diversity in terms of domains and baselines to support your claims.\nThere are plenty of easy methods that could be tested. First of all, you could have tested multiple annealing schedules for $\\epsilon$-greedy and not only $1/\\sqrt{n(s)}$, e.g., $n(s)^{\\alpha}$ with $\\alpha>0.5$ or even action-dependent values $n(s,a)^{\\alpha}$. There are also other techniques, like optimistic initialization of the Q-function, that often help with exploration. I would have also tested softmax exploration, this is another standard technique for randomized exploration with Q-learning. There are also inverse gap techniques, originally introduced in [1]. This is just a short list of easy techniques you could compare with. Clearly, in tabular RL, you could even try to compare with exploration strategies based on upper-confidence bounds or Thompson sampling.\n\nI found also limited the set of experiments in deepRL. Several heuristics have been proposed over time and I believe it is necessary to compare with a few of them even if they are more complicated. It is important for understanding the potential sub-optimality of the proposed strategy.\n\nMoreover, I would add more ablation studies either in tabular and continuos MDPs. For example, you can play with the level of stochasticity in the MDP, the structure of the MDP itself (as mentioned in a previous point) and add other classical control environments.\n\nFinally, you refer to the appendix that seems not to be available. Maybe we could have obtained more details about the setting used in the experiment (or other experiments) from there.\n\n[1] Abe and Long, Associative reinforcement learning using linear probabilistic concepts. ICML 1999\n\nMinor comments:\n- I would suggest adding a dependence on the current time $t$ in the definition of $\\Delta^2(a)$ and providing an explicit definition of $\\mathbb{T}_a$", "summary_of_the_paper": "The paper extends the recently introduced SAU measure from bandits to RL. The idea is to enhance the exploration of action based on an approximation of the estimation error. More precisely, the bonus is proportional to the average squared temporal difference error. This uncertainty measure is easy to compute and can be integrated into both tabular and continuous methods (e.g., Q-learning and DQN).", "summary_of_the_review": "Overall, while I think the idea is interesting, it is necessary to provide a more detailed experimental evaluation of the method to support the claims. I think the paper is not currently ready for publication.", "strength_and_weaknesses": "", "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": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "LuhEpQHahIb", "reviewer": "Reviewer_o8hT", "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": "Strength: \n\n1. This work proposes an exploration strategy that does not hinge on uncertainty estimates, which are typically computationally expensive and require either ensemble of models or specifically designed neural nets.  \n\n2. This work incorporates recent advances in the theoretical study of bandits, which are promising and have been shown to work effectively by various previous studies. e.g. IDS, UCB, Posterior Sampling\n\nWeakness: \n\n1. The work lacks theoretical support. Though incorporating SAU for exploration is promising (as I claimed in the strength part), the proposed incorporation method in this paper is not grounded by theory. Particularly, in Algorithm 1 of this paper, the author directly incorporates SAU for exploration in Q learning, where the SAU hinges only on the actions. It makes sense to estimate uncertainty based only on the novelty of actions under the multi-arm bandit setting. Nevertheless, in the contextual bandit setting, SAU requires a notion of homogeneous context to yield a reasonable uncertainty estimate [1]. Thus, it is questionable if directly incorporating SAU for the more complicated RL setting is provably efficient.\n\n2. In Algorithm 2, it is reasonable to use deviation between the target and the Q network to compute the TD error. However, it seems that $\\Delta_{dqn}$ no longer aggregates the TD errors according to the actions taken as SAU does. Alternatively,$\\Delta_{dqn}$ is defined for each of the individual state-action pairs. It would be better if the author could give some discussion on such an adjustment in DQN implementation.\n\nIn addition, some exploration strategies based on Q-learning are missing in the literature review. For instance, exploration with IDS ([2], [3]) is also an important SOTA, which incorporates bandit exploration strategy into RL exploration. In addition, from the empirical perspective, previous works also incorporate curiosity-driven methods [4] and mutual information ([5],[6],[7]) to construct the exploration bonus.\n\n[1]  Zhu and Rigotti, Deep Bandits Show-Off: Simple and Efficient Exploration with Deep Networks. (2021)\n\n[2] Russo and van Roy, Learning to Optimize Via Information-Directed Sampling. (2017)\n\n[3] Nikolov et al., INFORMATION-DIRECTED EXPLORATION FOR DEEP REINFORCEMENT LEARNING. (2019)\n\n[4] Pathak et al., Curiosity-driven Exploration by Self-supervised Prediction. (2017)\n\n[5] Houthooft et al., VIME: Variational Information Maximizing Exploration. (2017)\n\n[6] Kim et al., EMI: Exploration with Mutual Information. (2017)\n\n[7] Kim et al., Curiosity-Bottleneck: Exploration by Distilling Task-Specific Novelty. (2019)\n\n\n", "summary_of_the_paper": "This work introduces $\\delta^2$-exploration for reinforcement learning (RL), which aims to incorporate sample average uncertainty (SAU) into RL exploration. The authors discussed the background and formulation of SAU. The authors further propose $\\delta^2$-exploration, which incorporates SAU into Q-learning and compare such exploration with value-uncertainty exploration (UCB-type exploration) and $\\epsilon$-greedy. The author then proposes to incorporate $\\delta^2$-exploration into DQN and conduct experiments to compare $\\delta^2$-exploration with SOTA exploration algorithms. Empirical results show that $\\delta^2$-explorations attain comparable results to bootstrapped DQN.", "summary_of_the_review": "The idea of incorporating SAU into RL exploration is promising. Nevertheless, the presence of context and transition dynamics makes it unclear from the theoretical perspective whether SAU can be directly adopted into the exploration of RL. Hence, the work would be stronger if the authors could provide additional quantitative arguments supporting the validity of SAU for RL. In addition, the comparison with other baselines can be made more straightforward if the authors could provide charts of evaluation scores. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Although the reviewers found the idea of the work interesting, they all think it is not ready for publication. The experiments do not properly support the claims. Discussion on the connection to some related work is missing. And also the proposed method is not well motivated. I suggest the authors to take the reviewers' comments into account, revise their work and prepare it for future venues.
Decision: Reject