summaries: 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.   This 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.   The paper is generally well-written. 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. 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. 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).
abstractText: Effectively tackling the 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, 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 δ-exploration, an exploration strategy that extends SAU from bandits to the general sequential Reinforcement Learning scenario. We empirically study δ-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.
references.authors: Yasin Abbasi-Yadkori
references.title: Online learning for linearly parametrized control problems
references.venue: PhD thesis, University of Alberta,
references.authors: Yasin Abbasi-Yadkori David Pal Csaba Szepesväri
references.title: Improved algorithms for linear stochastic bandits
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Shipra Agrawal Navin Goyal
references.title: Further optimal regret bounds for Thompson sampling
references.venue: In Proceedings of the 16th International Conference on Artificial Intelligence and Statistics,
references.authors: P. Auer
references.title: Using confidence bounds for exploitation-exploration trade-offs
references.venue: Journal of Machine Learning Research,
references.authors: Peter Auer Nicolo Cesa-Bianchi Paul Fischer
references.title: Finite time analysis of the multiarmed bandit problem
references.venue: Machine Learning,
references.authors: Marc G Bellemare Yavar Naddaf Joel Veness Michael Bowling
references.title: The arcade learning environment: An evaluation platform for general agents
references.venue: Journal of Artificial Intelligence Research,
references.authors: M.G. Bellemare S. Srinivasan G. Ostrovski T. Schaul D. Saxton R. Munos
references.title: Unifying countbased exploration and intrinsic motivation
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Olivier Chapelle Lihong Li
references.title: An empirical evaluation of Thompson sampling
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Meire Fortunato Mohammad Gheshlaghi Azar Bilal Piot Jacob Menick Ian Osband Alex Graves Vlad Mnih Remi Munos Demis Hassabis Olivier Pietquin
references.title: Noisy networks for exploration
references.venue: arXiv preprint arXiv:1706.10295,
references.authors: T. Jaksch R. Ortner P. Auer
references.title: Near-optimal regret bounds for reinforcement learning
references.venue: Journal of Machine Learning Research,
references.authors: V. Mnih K. Kavukcuoglu D. Silver A.A. Rusu J. Veness M.G. Bellemare A. Graves M. Riedmiller A.K. Fidjeland G. Ostrovski S. Petersen C. Beattie A. Sadik I. Antonoglou H. King D. Kumaran D. Wierstra S. Legg D. Hassabis
references.title: Human-level control through deep reinforcement learning
references.venue: Nature, 518:529–533,
references.authors: B. O’Donoghue I. Osband R. Munos V. Mnih
references.title: The uncertainty Bellman equation and exploration
references.venue: In Proceedings of the 35rd International Conference on Machine Learning,
references.authors: I. Osband D. Russo B. Van Roy
references.title: more) efficient reinforcement learning via posterior sampling
references.venue: In Advances in neural information processing systems,
references.authors: I. Osband C. Blundell A. Pritzel B. Van Roy
references.title: Deep exploration via bootstrapped dqn
references.venue: In Advances in neural information processing systems,
references.authors: V. Perchet P. Rigollet
references.title: The multi-armed bandit problem with covariates
references.venue: The Annals of Statistics,
references.authors: M. Rigotti R. Zhu
references.title: Deep bandits show-off: Simple and efficient exploration with deep networks
references.venue: arXiv preprint arXiv:2105.04683,
references.authors: Carlos Riquelme George Tucker Jasper Snoek
references.title: Deep Bayesian bandits showdown: An empirical comparison of Bayesian deep networks for Thompson sampling
references.venue: In Proceedings of the 6th International Conference on Learning Representations,
references.authors: Patt Rusmevichientong John Tsitsiklis
references.title: Linearly parameterized bandits
references.venue: Mathematics of Operations Research,
references.authors: D. Russo B. Van Roy
references.title: Learning to optimize via information-directed sampling
references.venue: In Advances in Neural Information Processing Systems,
references.authors: A. Slivkins
references.title: Contextual bandits with similarity information
references.venue: Journal of Machine Learning Research,
references.authors: A.L. Strehl M.L. Littman
references.title: An analysis of model-based interval estimation for Markov decision processes
references.venue: Journal of Computer and System Sciences,
references.authors: M. Strens
references.title: A bayesian framework for reinforcement learning
references.venue: In Proceedings of the 17th international conference on Machine learning,
references.authors: Richard S. Sutton Andrew G. Barto
references.title: Reinforcement Learning: An Introduction
references.venue: The MIT Press, second edition edition,
references.authors: H. Tang R. Houthooft D. Foote A. Stooke X. Chen Y. Duan J. Schulman F. De Turck P. Abbeel
references.title: Exploration: A study of count-based exploration for deep reinforcement learning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: William R. Thompson
references.title: On the likelihood that one unknown probability exceeds another in view of the evidence of two samples
references.authors: H. van Hasselt A. Guez D. Silver
references.title: Deep reinforcement learning with double Q-learning
references.venue: In Proceedings of the 30th AAAI Conference on Artificial Intelligence,
references.authors: C.J.C.H. Watkins
references.title: Learning from Delayed Rewards
references.venue: PhD thesis, King’s College,
references.authors: Z. Wen B. Van Roy
references.title: Efficient exploration and value function generalization in deterministic systems
references.venue: In Advances in neural information processing systems,
references.authors: R. Zhu M. Rigotti
references.title: Self-correcting q-learning
references.venue: arXiv preprint arXiv:2012.01100,
sections.heading: 1 INTRODUCTION
sections.text: In Reinforcement Learning (RL) an agent interacts with an 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 a typical scenario, the RL agent does not 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-exploitation dilemma, i.e. deciding whether to exploit the actions that are known to maximize immediate reward or whether to explore unfamiliar actions and states in order to potentially find ways to increase future rewards.
  Efficient exploration requires the agent to quantify the accuracy of its current estimates of the stateaction values (the conditional expected rewards), so as to trade off expected rewards and uncertainty in a 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 exploration-exploitation 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 et al., 2002), and Thompson Sampling (TS), which instead models the posterior distribution over values (Thompson, 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 to 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 -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 a 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 on 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 an estimated
  variance by plugging in the estimated values. Finally, Rigotti & Zhu (2021) were able to use SAU to developed two SAU-based exploration strategies, SAU-UCB and SAU-Sampling, which were shown to display state-of-the-art performance in multi-armed bandits, contextual bandit, and deep bandits.
  In this work, we exploit the simplicity of SAU in Rigotti & Zhu (2021) and extend it from the bandits to the more general sequential RL setting. This extension results in δ2-exploration, a class of exploration strategies for RL which share the implementation simplicity of SAU for bandits as well as its effectiveness. Our δ2-exploration algorithms are implementable with a minimal computational overhead that is comparable to -greedy exploration, while being empirically more effective.
  As a practical demonstration, we apply δ2-exploration 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 -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 δ2-exploration could serve as a competitive baseline and as a simple and straight-forward replacement to -greedy action selection in a 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 δ2-exploration. Section 3 establishes the notation and states the problem. Section 4.2 presents the SAU measure, and summarized SAUbased exploration strategies in the setting of multi-armed bandits as developed in Rigotti & Zhu (2021). In Section 5 we then extend these strategies to the sequential RL setting and develop δ2exploration. Section 6 includes empirical evaluations showing substantial performance improvements over conventional exploration strategies in Q-learning and DQN. Section 7 concludes the paper.
sections.heading: 2 RELATED WORK
sections.text: The most common exploration strategy in Reinforcement Learning (RL) is arguably -greedy action selection, which consists in following the action with the highest estimated value with high probability, but occasionally with a 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 or even their value, because of its simplicity -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; Rusmevichientong & Tsitsiklis, 2010; Abbasi-Yadkori et al., 2011; Abbasi-Yadkori, 2012; Perchet & Rigollet, 2013; Slivkins, 2014). This approach is based on the principle of optimism in the face of uncertainty, which elegantly addresses the exploration-exploitation 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; Wen & Van Roy, 2013) due to the complexity of computing its uncertainty measure.
  A related class of strategies to UCB are count-based methods (Strehl & Littman, 2008; Bellemare et al., 2016) that directly turn the counts of state-action visitations into reward bonuses to encourage the exploration of less visited ones. Despite performing near-optimally for small discrete Markov decision processes, count-based methods suffer the curse of dimensionality in high-dimensional environments (although see Tang et al. (2017) that proposed a possible 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 a Bayesian approach that follows the principle of sampling in the face of uncertainty, i.e. 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 Learning problems (Strens, 2000; Osband et al., 2013). However, because calculating the posterior
  distributions over values is intractable in the general case, implementations of TS in even 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, are known to be inefficient (see Riquelme et al. (2018)).
sections.heading: 3 PROBLEM FORMULATION
sections.text: We recall the definition of a Markov Decision Process (MDP) as a set of states S and actionsA so that, given a current state s ∈ S and an action a ∈ A, the probability of ending up in the next state s′ ∈ S is Pss′(a), where P : S×A×S → [0, 1] is a fixed state transition distribution with ∑ s′ Pss′(a) = 1. Moreover, the reward r is drawn from a reward distribution with E[r|s, a, s′] = Rss′(a). The optimal value function Q∗(s, a) solves an MDP by satisfying the following set of Bellman equations for a given discount factor γ ∈ [0, 1):
  Q∗(s, a) = ∑ s′ Pss′(a) [ Rss′(a) + γ max a′∈A Q∗(s′, a′) ] ∀s, a.
  MDPs can be solved using Q-learning (Watkins, 1989). Let Q(s, 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 r be the corresponding reward. Then Q-learning consists in updating the action-value function using a learning rate α as follows:
  Q(s, a)← Q(s, a) + α [ r + γ max
  a′∈A Q(s′, a′)−Q(s, a)
  ] .
  In this update rule, Q-learning uses the max operator as an estimate the value of the next state. The term in the squared brackets
  δ = r + γ max a′∈A Q(s′, a′)−Q(s, a) (1) is known as the TD-error, because it is a generalization of the reward prediction error in the case of a Temporal-Difference learning algorithm.
  A last element that is crucial for the Q-learning algorithm to converge to the optimal value function is exploration. That is why Q-learning is typically implemented in combination with -greedy action selection, a simple and rather successful exploration strategy proposed in Sutton & Barto (2018) that prescribes to fix a small probability and choose an action at time t as follows:
  at = { a ∈ A uniformly at random, with probability ; a∗ = arg maxa∈A {Q(st, a)} , with probability 1− .
  (2)
  As mentioned in the previous section, -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 -greedy action selection is typically the exploration strategy of choice in many successful RL applications, such as Mnih et al. (2015).
sections.heading: 4 SAMPLE AVERAGE UNCERTAINTY FOR CONTEXTUAL BANDITS
sections.text: The Sample Average Uncertainty (SAU) is a measure of uncertainty that was recently proposed as a simple and scalable mechanism to promote exploration in the bandit setting (Rigotti & Zhu, 2021). For ease of exposition we introduce SAU from the contextual bandit perspective and notation.
sections.heading: 4.1 CONTEXTUAL BANDITS
sections.text: In contextual bandits at each step t the agent observes a context vector st ∈ X , selects an action at from a set A, after which a reward rt corresponding to the chosen action is received. The value of an action a in context st is defined as the expected reward given that a is selected, and is assumed to be a fixed but unknown function of st and a: E[rt|at = a] = µ(st, a). The goal is to design a decisionmaking policy π : X → A that maximizes the expected reward. This goal is readily quantified in terms of minimizing expected regret, where, if action at is chosen at step t after observing context st, we say that we incur expected regret maxa′∈A{µ(st, a′)} − µ(st, at), which is the difference between the optimal value received by playing the optimal action and the value received following the chosen action.
sections.heading: 4.2 SAMPLE AVERAGE UNCERTAINTY EXPLORATION IN BANDITS
sections.text: 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 {µ̂(st, at)}t∈Ta of µ(s, a). The Sample Average Uncertainty (SAU (Rigotti & Zhu, 2021)) statistic τ(a)2 is defined as
  τ(a)2 = 1
  n(a) ∑ t∈Ta e2t with et = rt − µ̂(st, at). (3)
  Obviously, computing the SAU measure only requires the prediction residuals et = rt − µ̂(st, at), without any need to model or access the uncertainty of µ̂(st, at).
  Reference Rigotti & Zhu (2021) 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 τ(a)2 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 t, define Y (st, a) = µ̂(st, a) + √ n(a)−1τ(a)2 log t, where n(a) is the times action a was taken. Then choose the action by maximizing over that: at = arg maxa∈A {Y (st, a)}.
  SAU-Sampling. Thompson Sampling (TS) promotes exploration by sampling value estimates from a modelled posterior distribution. The SAU-Sampling algorithm (Rigotti & Zhu, 2021) also adopts this principle of “sampling in the face of uncertainty”, but unlike TS it does so by sampling values from a parametric Gaussian distribution with a mean given by the prediction and a variance proportional to τ(a)2, resulting in values Y (st, a) ∼ N ( µ̂(st, a), τ(a) 2/n(a) )
  from which then an action is again selected by maximization: at = arg maxa∈A {Y (st, a)}. In summary, in contrast to uncertainty-based exploration strategies like UCB and TS that first measure the uncertainty of the action-value estimates µ̂(s, 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 is that it is much simpler and more computationally efficient, while at the same time providing the same quality of uncertainty estimates, and often even better exploration than the more complex algorithms that rely on estimating the uncertainty of the action-value function (see empirical results in (Rigotti & Zhu, 2021)).
  5 δ2-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 in the contextual bandit setting, including the deep contextual bandit case where the reward is being parametrized by a deep neural network (Rigotti & Zhu, 2021). We now propose an extension of SAU to adapt it from the bandit to the sequential reinforcement learning scenario. We call the resulting class of exploration algorithms δ2-exploration.
  5.1 δ2-EXPLORATION IN Q-LEARNING
  Contextual bandits are essentially simplified MDPs with horizon 1, so that each episode only consists of one state observation (which in contextual bandits is called “context”), an action and a reward, after which the environment is reset. Because of this relationship, the first step to extend results in bandits to sequential reinforcement learning is to substitute the bandit feedback rt in equation 3 with the multi-step cumulative return Gt, defined as Gt = ∑T−t−1 k=0 rt+k+1 in the case of episodic
  tasks or Gt = ∑∞ k=0 γ
  krt+k+1 with discount rate γ in the case of infinite horizon tasks. The value prediction terms, µ(s, a) in equation 3 correspond in a sequential RL setting to the state-action value qπ(s, a) under some policy π, and can therefore be substituted with Q(s, a), its current estimate at a given time.
  At this point, we notice that Q-learning uses a target to approximate the cumulative return Gt with the one-step iteration rt+1 + γmaxa′ Q (st+1, a′) (Sutton & Barto, 2018), and we can therefore use the same approximation in our extension of SAU from bandits to sequential RL.
  Note that the SAU measure is not a function of the current context st but just depends on action a. A key mechanism explaining why this simple method works is the assumption that the noise in each arm is homogeneous. This is a 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 τa in equation 3 that we call δ2-uncertainty:
  ∆2(a) = 1
  n(a) ∑ t∈Ta δ2(st, at), (4)
  where δ(st, at) denotes the TD-error in equation 1 at an observed sequence st, at, rt+1, st+1, i.e.:
  δ(st, at) = rt+1 + γ max a′∈A
  Q (st+1, a ′)−Q(st, at),
  and the sum in equation 4 is over the set Ta of time steps when action a was chosen up until the current time, and n(a) denotes the number of times that the action a was observed.
  In practice, ∆2(·) in equation 4 can be efficiently computed by incrementally updating a running estimate that accumulates the TD-error:
  ∆2(a)← ∆2(a) + [ δ2(s, a)−∆2(a) ] /n(a). (5)
  Comparing the derived expression equation 4 for the δ2-uncertainty ∆2 with the definition equation 3 of the SAU measure τa solidifies the intuition that the role played by the prediction residual et in equation 3 for the bandit feedback is naturally taken up by the TD-error δ(st, at) in sequential RL.
  As in the case of SAU-based exploration in bandit problems, once the δ2-uncertainty is available it can simply be plugged into the action selection process to implement a class of exploration algorithms that we call δ2-exploration. The δ2-exploration algorithm that is obtained by using the δ2-uncertainty as in UCB will be called δ2-UCB. Analogously, the δ2-exploration algorithm obtained by combining the δ2-uncertainty with sampling-based exploration will be called δ2-Sampling.
  More specifically, given action-valuesQ(st, a) at a given state st at time t, δ2-exploration implements exploration by “perturbing” action-values Q̃(st, a) according to one of the following schemes, depending on which specific exploration algorithm we want to use:
  1. δ2-UCB: Q̃(st, a) = Q(st, a) +
  √ ∆2(a) log t
  n(a) ∀a ∈ A;
  2. δ2-Sampling: Q̃(st, a) ∼ N ( Q(st, a), ∆2(a)
  n(a)
  ) ∀a ∈ A.
  Then an action is selected by maximization: at = arg maxa∈A { Q̃(st, a) } .
  The two δ2-exploration algorithms δ2-UCB and δ2-Sampling are detailed in Algorithm 1.
  5.2 COMPARISON BETWEEN VALUE UNCERTAINTY EXPLORATION AND δ2-EXPLORATION
  Let us take a moment to compare the functioning of δ2-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
  Algorithm 1 δ2-exploration in Q-learning. Parameters: step size α ∈ (0, 1], discount factor γ ∈ (0, 1], and β ≥ 1. Initialize: Q(s, a) such that Q(terminal, ·) = 0, ∆2(a) = 0, and n(a) = 1 for all a ∈ A. for all episodes do
  Initialize state s while s in episode is not terminal do
  (1) Use δ2-exploration strategy (a) or (b):
  (a) δ2-UCB: Q̃(s, a) = Q(s, a) +
  √ ∆2(a) log ∑ a n(a)
  n(a) ;
  (b) δ2-Sampling: Q̃(s, a) ∼ N ( Q(s, a), ∆2(a)
  n(a)
  ) .
  (2) Select a in state s: a = arg maxa′∈A{Q̃(s, a′)} n(a)← n(a) + 1. (3) Take action a, observe r, s′.
  (4) Update Q(·) and ∆2(·): δ(s, a) = r + γmax
  a′ Q (s′, α)−Q(s, a)
  Q(s, a)← Q(s, a) + α · δ(s, a) ∆2(a)← ∆2(a) + ( δ2(s, a)−∆2(a) ) /n(a).
  (5) Step to next state: s← s′ end while
  end for
  computationally costly, to the point of being computationally intractable for large state spaces. Thompson Sampling in particular assumes a prior distribution over value functions that is updated based on observed transitions, a process that is only feasible for simple environments.
  In contrast, rather than maintaining the internal uncertainty of value function estimates, δ2-exploration simply updates its propensity for exploration by accumulating the reward prediction error δ as in equation 5. In other words, δ not only has a role in policy evaluation by representing the extent to which the value function should be update, but also has a role in the control policy by representing the extent to which exploration is needed to prevent the policy from being suboptimal.
  Figure 1 gives a schematic overview of the difference between value uncertainty exploration methods and our proposed method δ2-exploration, emphasizing the simplicity of δ2-exploration whose exploration mechanism does not need to rely on estimating the distributional uncertainty over the value function, but only needs access to the reward prediction error δ to compute the δ2-uncertainty ∆.
  Once the δ2-uncertainty ∆ is available, it is directly passed to the action selection step (see step (2) in Algorithm 1). This means that the δ2-uncertainty, besides being cheap to compute, is also simple to use to instantiate the exploration mechanism: it is simply used to “perturbe” the estimated action-values (either as an exploration bonus in the case of δ2-UCB or as sampling noise in the case of δ2-Sampling) before greedily selecting the next action. This underscores that from a computational standpoint the action selection process of δ2-exploration is as simple as -greedy action selection (equation 2). Indeed, δ2-exploration inherits this trait from SAU-exploration (Rigotti & Zhu, 2021), and similarly to that algorithm can be used as a flexible drop-in replacement for -greedy selection.
  5.3 δ2-EXPLORATION IN DEEP Q-LEARNING
  Deep Q-learning consists in parameterizing the action-value functionQ(s, a) as a deep neural network, i.e. a Deep Q Network (DQN) policy network (Mnih et al., 2015). Because of the complexity of such an action-value function, it is notoriously difficult to implement efficient exploration strategies in DQN. As a result, dithering heuristics such as -greedy are commonly used in practice. Fortunately,
  Environment
  Agent
  value function
  exploration
  r as
  uncertainty
  Environment
  Agent
  value function
  exploration
  r as (a) Value uncertainty exploration (b) d2-exploration Figure 1: (a) Value uncertainty exploration algorithms like UCB and Thompson Sampling rely on an estimate of the uncertainty of the current value function, a quantity that is intractable already for moderately complex value functions and environments. (b) δ2-exploration on the other hand only needs access to the reward prediction error δ to compute how to select an action that trades off exploration and exploitation in a principled way.
  δ2-exploration just depends on the prediction of the value function, so it is versatile enough to be easily applicable to DQN.
  A direct way to combine δ2-exploration with DQN would be to implement Algorithm 1 using a deep neural network (in addition to the policy network) that would fit the δ2-exploration measure ∆. To avoid the computational and memory overhead of an additional network we took inspiration from recent papers that harnessed the target network in DQN (a delayed parameter version of the policy net used in Mnih et al. (2015) to stabilize training) in order to implement unbiased estimators of the value (van Hasselt et al., 2016; Zhu & Rigotti, 2020). We reasoned that the difference between the online policy net Q(s, a) and the delayed parameter target net Q−(s, a) should reflect a minimization of the reward prediction error. This suggests to replace the expression equation 4 with the following expression for the δ2-uncertainty ∆:
  ∆2dqn(s, a) = (
  max a′
  Q(s, a′)−Q−(s, a) )2 .
  We propose to use this variation of the δ2-uncertainty to implement the DQN version of δ2-exploration algorithms δ2-UCB and δ2-Sampling. Using δ2-exploration in DQN therefore comes down to implementing DQN learning as usual (see e.g. Mnih et al. (2015)), except that the action selection part of the algorithm (which typically would use -greedy action selection) is replaced as in Algorithm 2.
  Algorithm 2 δ2-exploration in 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 ∈ A.
  2: Replace action selection ACT(·) in regular DQN with:
  3: function ACT-δ2-EXPLORATION(s) 4: for a = 1, . . . , |A| do
  5: (1) Compute ∆2dqn(s, a) = (
  max a′
  Q(s, a′)−Q−(s, a) )2
  6: (2) Use δ2-exploration strategy (a) or (b):
  7: (a) δ2-UCB: Q̃(s, a) = Q(s, a) +
  √ ∆2dqn(s, a) log ∑ an(a)
  n(a) ;
  8: (b) δ2-Sampling: Q̃(s, a) ∼ N ( Q(s, a), ∆2dqn(s, a)
  n(a)
  ) .
  9: end for 10: Select action a∗ = arg maxa∈A{Q̃(s, a)}. 11: Update global count n(a∗)← n(a∗) + 1. 12: Return action a∗ 13: end function
sections.heading: 6 EMPIRICAL RESULTS
sections.text: We now empirically evaluate the performance of our proposed δ2-exploration strategies in a series of reinforcement learning tasks, including classical tabular Q-learning and Deep Q Learning tasks.
  We will benchmark δ2-exploration against -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 δ2-exploration as a flexible drop-in replacement for -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-LEARNING ON CLIFF-WALKING TASK
  = 1/
  √
  n(s), where n(s) is the number of times state s has been visited. Learning rate is set to αn(s, a) = 0.1(100+1)/(100+n(s, a)), where n(s, a) is the number of updates of each state-action. Data points are averaged over 1000 runs.
  We evaluate the performance of δ2-exploration on the cliff-walking task (Example 6.6 in Sutton & Barto (2018)), a 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 a reward of −100 and is instantly sent back to the start. We vary the environment size by considering 10× 5 and 20× 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 δ2-exploration δ2-UCB and δ2-Sampling against -greedy action selection with = 1/ √ n(s). As Fig. 2 shows the δ2-exploration strategies perform much better than -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 δ2-exploration strategies display much lower variability (i.e. are more stable) than -greedy action selection.
sections.heading: 6.2 DEEP Q NETWORK ON THE ATARI 2600 DOMAIN
sections.text: As a final empirical validations for δ2-exploration 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 δ2-exploration algorithms with the conventional -greedy action selection that consists of annealing for the first 1M steps from 1.0 linearly to F = 0.1, 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. 3 compares the performance at the end of training for -greedy, Bootstrapped DQN, noisy nets and our δ2-exploration algorithms. The advantage of δ2-exploration is particularly remarkable for harder games, and in particular MsPacman, where our algorithms finds
  policies that reach scores that are almost double what the other competitors reach, and Centipede, where δ2-Sampling vastly outperforms even Bootstrapped DQN.
sections.heading: 7 CONCLUSIONS AND DISCUSSION
sections.text: Here we extended Sample Average Uncertainty, a recently proposed uncertainty measure for exploration, from bandit problems to the general sequential reinforcement learning setting. This resulted in our δ2-exploration 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 replacements for -greedy action selection in Q-learning and DQN, resulting in effective and computationally efficient learning and superior empirical performance over the -greedy baseline.
  Our work provides a simple, scalable and robust exploration algorithms, that can be effortlessly deployed to mitigate the exploration-exploitation dilemma. While the resulting consequences of the deployment of an RL algorithm, ethical or otherwise, will clearly depend on the specific applications, we believe that providing efficient uncertainty estimates and more reliable exploration than the common -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 -greedy exploration, given its importance and ubiquity, and because our method was developed specifically as a natural drop-in replacement for -greedy exploration. Our δ2-exploration algorithms have in fact a comparably low computation footprint and can be implemented through a minimal API that is the same as for -greedy exploration, 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 δ2-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 to update the value uncertainty.
  That said, the remarkable performance of our simulation results and the flexibility of δ2-exploration 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.
  REPRODUCIBILITY STATEMENT
  We provide detailed pseudo-code of our proposed algorithms and tried our best to indicate important hyperparameters to 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 to release the code to replicate all our numerical experiments on github.