Temporal Difference Uncertainties as a Signal for Exploration
Authors: Sebastian Flennerhag
Jane X Wang
Pablo Sprechmann
Francesco Visin
Alexandre Galashov
Steven Kapturowski
Diana L Borsa
Nicolas Heess
Andre Barreto
Razvan Pascanu
Venue:  (2021)
Keywords: deep reinforcement learning
deep-rl
exploration

Abstract: An effective approach to exploration in reinforcement learning is to rely on an agent's uncertainty over the optimal policy, which can yield near-optimal exploration strategies in tabular settings. However, in non-tabular settings that involve function approximators, obtaining accurate uncertainty estimates is almost as challenging as the exploration problem itself. In this paper, we highlight that value estimates are easily biased and temporally inconsistent. In light of this, we propose a novel method for estimating uncertainty over the value function that relies on inducing a distribution over temporal difference errors. This exploration signal controls for state-action transitions so as to isolate uncertainty in value that is due to uncertainty over the agent's parameters. Because our measure of uncertainty conditions on state-action transitions, we cannot act on this measure directly. Instead, we incorporate it as an intrinsic reward and treat exploration as a separate learning problem, induced by the agent's temporal difference uncertainties. We introduce a distinct exploration policy that learns to collect data with high estimated uncertainty, which gives rise to a curriculum that smoothly changes throughout learning and vanishes in the limit of perfect value estimates. We evaluate our method on hard exploration tasks, including Deep Sea and Atari 2600 environments and find that our proposed form of exploration facilitates efficient exploration.

Under review as a conference paper at ICLR 2021
TEMPORAL DIFFERENCE UNCERTAINTIES AS A SIGNAL FOR EXPLORATION
A Anonymous authors Paper under double-blind review
ABSTRACT
An effective approach to exploration in reinforcement learning is to rely on an agent's uncertainty over the optimal policy, which can yield near-optimal explo- ration strategies in tabular settings. However, in non-tabular settings that involve function approximators, obtaining accurate uncertainty estimates is almost as chal- lenging as the exploration problem itself. In this paper, we highlight that value estimates are easily biased and temporally inconsistent. In light of this, we propose a novel method for estimating uncertainty over the value function that relies on inducing a distribution over temporal difference errors. This exploration signal controls for state-action transitions so to isolate uncertainty in value that is due to uncertainty over the agent's parameters. Because our measure of uncertainty con- ditions on state-action transitions, we cannot act this measure directly. Instead, we incorporate as an intrinsic reward and treat exploration as a separate learning problem, induced by the agent's 's temporal difference uncertainties. We introduce distinct exploration policy that learns to collect data with high estimated uncertainty, which gives rise "curriculum" that smoothly changes throughout learning and vanishes in the limit of perfect value estimates. We evaluate our method on hard- exploration tasks, including Deep Sea and Atari 2600 environments and find that our proposed form of exploration facilitates efficient exploration.
INTRODUCTION
Striking the right balance between exploration and exploitation fundamental the reinforcement learning problem. A common approach is to derive exploration from the policy being learned. Dithering strategies, such as e-greedy exploration, render a swwrd-maximising policy stochastic around its reward maximising behaviour (Williams & Peng, 1991). Other methods encourage higher entropy in the policy (Ziebart et al., 2008), introduce an intrinsic reward (Singh et al., 2005), or drive exploration by sampling from the agent's belief over the MDP (Strens, 2000).
While greedy or maxrrpiimaximising policies cannot facilitate temporally extended exploration (Osband al., 2013; 201 the efficacy of intrinsic rewards depends crucially on how they relate to the extrinsic reward that comes from the environment (Burda et al., 201 8a). Typically, intrinsic rewards for exploration provide bonus for visiting novel states (e.g Bellemare al., 2016) or visiting states where the agent cannot predict future transitions (c.g Pathak et al., 2017; Burda et al., 2018a). Such approaches can facilitate learning an optimal policy, but they can also fail entirely in large environments as they prioritise novelty over rewards (Burda et al., 2018b).
Methods based on the agent's uncertainty over the optimal policy explicitly trade off exploration and exploitation (Kearns & Singh, 2002). Posterior Sampling for Reinforcement Learning (PSRL; Strens, 2000; Osband et al., 2013) is one such approach, which models a distribution over Markov Decision Processes (MDPs). While PSRL is near-optimal in tabular settings (Osband et al., 2013; 2016b), it cannot be easily scaled to complex problems that require function approximators. Prior work has attempted to overcome this by instead directly estimating the agent's uncertainty over the policy's 's value function (Osband et al., 2016a; Moerland et al., 2017; Osband et al., 2019; O' Donoghue et al., 2018: Janz et al., 2019). While these approaches can scale posterior sampling complex problems and nonlinear function approximators. estimating uncertainty over value functions introduces issues that cause a bias in the posterior distribution (Janz et al., 2019).

---

Under review as a conference paper at ICLR 2021
In response these challenges, we introduce Temporal Difference Uncertainties (TDU), which de- rives an intrinsic reward from the agent's uncertainty over the value function. Concretely, TDU relies on the Bootstrapped DQN (Osband et al., 201 and separates exploration and reward-maximmisin behaviour into two separate policies that bootstrap from a shared replay buffer. This separation allows us derive an exploration signal for the exploratory policy from estimates of uncertainty of the daward-maximising policy. Thus, TDU encourages exploration to collect data with high model uncertainty over mavimmiiaxiiisng behaviour, which is made possible by treating exploration as separate learning problem. In contrast to prior works that directly estimate value function uncertainty, we estimate uncertainty over temporal difference (TD) errors. By conditioning on observed state- action transitions, TDU controls for environment uncertainty and provides an exploration signal only insofar as there is model uncertainty. We demonstrate that TDU can facilitate efficient exploration in challenging exploration problems such as Deep Sea and Montezuma's 's Revenge.
2 ESTIMATING VALUE FUNCTION UNCERTAINTY IS HARD
We begin by highlighting that estimating uncertainty over the value function can suffer from bias that very hard overcome with typical approaches (see also Janz et al., 2019). Our analysis shows that biased estimates arise because uncertainty estimates require integration over unknown future state visitations. This requires tremendous model capacity and in general infeasible. Our results show that we cannot escape a bias in general, but we can take steps to mitigate it by conditioning on an observed trajectory. Doing so removes some uncertainty over future state-visitations and we show in Section 3 that it can result in a substantially smaller bias.
We consider a Markov Decision Process (S, A, P. 7) for some given state space (S), action space (AA), transition dynamics (P), reward function (R) and discount factor (7). For a given (deterministic) policy æ : S + A, the action value function is defined as the expected cumulative reward under the policy starting from state with action
(s( YrTh 80 = 5, = E E (2 (s xsd))),
(I)
s'mP(ss))
where / index time and the expectation Ex is with respect to realised rewards sampled under the policy h; the right-hand side characterises Q recursively under the Bellman equation. The action- value function Qu is estimated under function approximator Q9 parameterised by 0. Uncertainty over Qx is expressed by placing distribution over the parameters of the function approximator, p(0). We overload notation slightly and write p(0) denote the probability density function pe over random variable 6. Further, we denote by 0 ~ p(0) random sample f from the distribution defindd by pe. Methods that rely on posterior sampling under function approximators assume that the induced distribution, p(Qa). is an accurate estimate of the agent's 's uncertainty over its value function, p(Qx), so that sampling QA ~ p(Qo) is approximately equivalent to sampling from Qx ~ p(Q²).
For this to hold, the moments of p(Qo) at each state-action pair (s, a) must correspond to the expected moments in future states. In particular, moments of p(Q,) must satisfy a Bellman Equation akin to Eq. (O' Donoghue et al., 2018). We focus on the mean (IE) and variance (V):
Es(Qe(s a)] = Eo t (ss))]] Vo (Q0 a)] = Vo [Br. + Qols'' क (s))).].
(2)
(3)
If [o] and Ve[Qe] fail to satisfy these conditions, the estimates of E[Qa] and V[Qa] are biased, causing a bias in exploration under posterior sampling from p(Qo). Formally, the agent's uncertainty over p(Q) implies uncertainty over the MDP (Strens, 2000). Given a belief over the MDP, i.e., distribution p(M). we can associate each M ~ p(M) with a distinct value function Q Lemma 1 below shows that, for p()) to be interpreted as representing some p(M) by push-forward to p(Qo). the induced moments must match under the Bellman Equation.
Lemma 1. Eo [2ol and Vo [olQo] fail to satisfy Eqs. 2 and 3. respectively, they are biased estimators of Ex [Q4] and V. M [QM for any choice of PM))
2

---

Under review as a conference paper at ICLR 2021
All proofs are deferred to Appendix B. Lemma 1 highlights why estimating uncertainty over value functions is so challenging: while the left-hand sides of Eqs. 2 and are stochastic in & only, the right-hand sides depend marginalising over the MDP. This requires the function approximator to generalise to unseen future trajectories. Lemma is therefore a statement about scale; the harder it is to generalise, the more likely are observe bias-eva in deterministic environments.
This requirement "strong generalisation" poses a particular problem for neural networks that tend interpolate over the training data (e.g. Li al., 2020; Liu al., 2020; Belkin et al., 2019), but the issue is more general. In particular, we show that factorising the posterior p(0) will typically cause estimation bias for all but tabular MDPs. This is problematic because infeasible to maintain a full posterior, previous work either maintains a full posterior over the final layer of the function approximator (Osband et al., 2016a; O' Donogguue et al., 2018; Janz et al., 2019) or maintains diagonal posterior over all parameters (Fortunato et al., 2018; Plappert et al., 201 8) of the neural network. Either method limits how expressive the function approximator can be with respect to future states, thereby causing estimation bias. To establish this formally, let Qa == woos. IR" a feature
often computationally
where (W1,.... Way .1..... ,,,), with w E I"" a linear projection and Φ extractor with parameters 0 E R".
Proposition 1. If the number of state state-action pairs where Eg (Q a)] + EolQa(s', d')] is greater than n, where RR, then EEg [Q]] and (o( are biased estimators of M [Q4] and V M [Q*] for any choice of p(M).
This result a consequence of the feature extractor & mapping into co-domain that larger than the space spanned by w; a bias results from having more unique state-action representations (s a) than degrees of freedom in w. The implication is that function approximators under factorised posteriors cannot generalise uncertainty estimates across states (a similar observation in tabular settings was made by Janz et al., 2019)-thyy can only produce temporally consistent uncertainty estimates they have the capacity to memorise point-wise uncertainty estimates for each (s, a), which defeats the purpose of a function approximator. This is a statement about the structure of p(0) (6) and holds for any estimation method. Thus, common approaches to uncertainty estimation with neural networks generally fail to provide unbiased uncertainty estimates over the value function in non-trivial MDPs. Proposition shows that to accurately capture value function uncertainty, we need full posterior over parameters, which is often infeasible. also underscores that the main issue is the dependence on future state visitation. This motivates Temporal Difference Uncertainties as an estimate of uncertainty conditioned on observed state-action transitions.
3 TEMPORAL DIFFERENCE UNCERTAINTIES
While Proposition states that we cannot remove this bias unless we are willing to maintain a full posterior p(0), we can construct uncertainty estimates that control for uncertainty over future state-action transition. In this paper, we propose to estimate uncertainty over a full transition == (s, a, r, 8') to isolate uncertainty due to p(0). Fixing transition, induce a conditional distribution p(ō T) over Temporal Difference (TD) errors, 8(0, T) = =Qa(s +(s')) +r Qo a). that we characterise by its mean and variance:
[s | r] = Eg (5(( [T]
and Vs r] = Vo(5(0, [7]
(4)
Estimators over TD-error is akin to first-difference estimators of uncertainty over the action-value. They can therefore exhibit smaller bias if that bias is temporally consistent. To illustrate, for simplicity assume that [g]] consistently over/under-estimatee EM [QM] by amount b R. The corresponding bias in E, (0. 7) 7] is given by Bias (0, 7) 7]) Bias(?En(Qo(s x(())) r r- Ee (Qo(s, a))) = (Y 1)b. This bias is close to 0 for typical values of y notably for 7 = 1. (,(, 7] is unbiased. More generally, unless the bias is constant over time as in the above example, we cannot fully remove the bias when constructing an estimator over a quantity that relies on Qo. However, as the above example shows, by conditioning on a state-action transition, can make it significantly smaller. We formalise this logic in the following result.
3

---

Under review as a conference paper at ICLR 2021
Proposition 2. For any = as, and any p(M), given p(0). define the following ratios:
Bias (Bo(Qo(s',=(() x =<())())) Bias (Eo (s,(
(5)
Bias (Ee Qo a) Bias [Bal Qu a)l) / Bias (Ea [Qo
Bias (Lo() ((*)))
(6)
(7)
a EM 10 (s', ((())) EM 12 (s,a)]
(8)
If p E (0. (0.2 then Eg 7] has lower bias than Eøl Bo a)}- Moreover, if p = Es(8| r) is unbiased. Additionally, there exists p 1, = 1, K = 1, such that Volō(0, | have less bias than VolQo (s, a)). In particular, if o k = a = 1, then
1/7, then
Biass (Volo(0, -]] = (1-11) 1)2 ( Ve Volees a))) < (Velooooo
(9)
Further, = 1/7, == 1/7, Φ = 1/7?, , then Volo(0, r) r] is unbiased for any a.
The first part of Proposition 2 generalises the example above to cases where the bias varies across action-state transitions. It is worth noting that the required "smoothness" stringent: the bias of [Q]] { (s',
the bias is not very (s()) can be twice as large as that of Egg [Qo] (s, a) and Es[d still produce a less biased estimate. Importantly, it must have the same sign, and Proposition requires temporal consistency. To establish a similar claim for Valō | r). we need a bit more structure. The ratios p. d, and и capture temporal consistency in the bias, while relates the temporal consistency of the underlying estimand. Proposition establishes that if these ratios are close to unity, then (0, r) r] will have less bias. For most transitions, it reasonable to assume that this holds true. In some MDPs, large changes in the reward can cause these requirements to break. Because Proposition 2 only establishes sufficiency, violating this requirement does not necessarily mean that Vo[ō r] has greater bias than Vo (Qoss, (s, a)). Finally, it is worth noting that these are statements about given transition т. most state-action transitions, the requirements in Proposition 2 will hold, in which case [6 r] and 58 r] exhibit less overall bias. We provide direct empirical support that Proposition 2 holds practice through careful ceteris paribus comparisons in Section 5.1.
To obtain a concrete signal for exploration, we follow O' D'Donoguue et al. (2018) and derive an exploration signal from the variance Vo( ()()). Because p(8 ()) is defined per transition, cannot be used as-is for posterior sampling. Therefore, incorporate TDU a signal for exploration via an intrinsic reward. To obtain an exploration signal that is on approximately the same scale as the
extrinsic reward, we use the standard deviation (T) = /Vol6(0. r) to define an augmented reward function
R( = R((sa) () +B
(10)
where 3 E [0, 00) is hyper-parameter that determines the emphasis on exploration. Another appealing property of a is that it naturally decays as the agent converges on a solution (as model uncertainty diminishes); TDU defines a distinct MDP (S, A, P, R, 7) under Eq. 10 that converges on the true MDP in the limit of model uncertainty. For given policy and distribution p(Qu), there exists an exploration policy μ that collects transitions over which p(Qx) exhibits maximal uncertainty, as measured by a. In hard exploration problems, the exploration policy μ can behave fundamentally differently from π. To capture such distinct exploration behaviour, we treat as separate exploration policy that we train to maximise the augmented reward R, along-side training a policy и that maximises the extrinsic reward R. This gives rise a natural separation of exploitation and exploration in the form of a cooperative multi-agent game, where the exploration policy is tasked with finding experiences where the agent is uncertain of its value estimate for the greedy policy m. As æ is trained on this data, we expect uncertainty to vanish (up to noise). As this happens. the exploration policy / is incentivised to find new experiences with higher estimated uncertainty. This induces particular pattern where exploration will reinforce experiences until the agent's 's uncertainty vanishes, at which point the exploration policy expands its state visitation further. This process can allow TDU to overcome estimation bias in the posterior-sine it is in effect exploiting it-in in contrast to previous methods that do not maintain a distinct exploration policy. We demonstrate this empirically both on Montezuma's Revenge and on Deep Sea (Osband et al., 2020).
4

---

Under review as a conference paper at ICLR 2021
4 IMPLEMENTING TDU WITH BOOTSTRAPPING
The distribution over TD-errors that underlies TDU can be estimated using standard techniques for probability density estimation. In this paper, we leverage the statistical bootstrap as it is both easy to implement and provides a robust approximation without requiring distributional assumptions. TDU is easy implement under the statistical bootstrap it requires only few lines of extra code. It can be implemented with value-based as well as actor-critic algorithms (we provide generic pseudo code in Appendix A); in this paper, we focus Q-learning. Q-learning alternates between policy evaluation (Eq. 1) and policy improvement under a greedy policy To (8) = arg max, a Qo a). Deep Q-learning (Mnih al., 2015) learns Qo by minimising its TD-error by stochastic gradient descent on transitions sampled from replay buffer. Unless otherwise stated, in practice we adopt a common approach of evaluating the action taken by the learned network through target network with separate parameters that are updated periodically (Van Hasselt et al., 2016).
Our implementation starts from the bootstrapped DQN (Osband et al., 2016a), which maintains a set of K function approximators Q = (Q0))))) each parameterised by 0h and regressed towards unique target function using bootstrapped sampling of data from a shared replay memory. The Bootstrapped DQN derives a policy Ty by sampling uniformly from Q at the start of each episode. We provide an overview of the Bootstrapped DQN in Algorithm I for reference. To implement TDU in this setting, we make a change to the loss function (Algorithm 2, changes highlighted in green). First, we estimate the TDU signal a using bootstrapped value estimation. We estimate through observed TD-errors {6x jk=1 incurred by the ensemble Q on a given transition:
1k
(
(8(0k) T) -()())
(11)
K
where 8 8= 75''-+++-0 with == E F2 and ='== ((s)). An important assumption underpinning the bootstrapped estimation is that of stochastic optimism (Osband et al., 2016b), which requires the distribution over Q to be approximately as wide the true distribution over value estimates. If not, uncertainty over Q can collapse, which would cause to also collapse. To prevent this. Q can be endowed with prior (Osband al., 2018) that maintains diversity in the ensemble by defining each value function as Q+= + APE, À E [0, oc), where Pk is a random prior function.
Rather than feeding this exploration signal back into the value functions in Q, which would create a positive feedback loop (uncertainty begets higher reward, which begets higher uncertainty ad- infinitum), we introduce a separate ensemble of exploration value functions Q = {Qps }. that we train over the augmented reward (Eqs. 10 and 11). We derive an exploration policy Há by sampling exploration parameters uniformly from 2 as in the standard bootstrapped DQN.
In summary, our implementation of TDU maintains K N value functions. The first K defines standard Bootstrapped DQN. From these, we derive an exploration signal ar, which we use to train the last N value functions. At the start of each episode, we proceed in the standard Bootstrapped DQN and randomly sample parameterisation 0 from QUÔ that we act under for the duration of the episode. All value functions are trained by bootstrapping from a single shared replay memory (Algorithm I); see Appendix A for a complete JAX (Bradbury et al., 2018) implementation. Consequently, we execute the (extrinsic) policy Ha-2 with probability N/(K+N). While visits states around current soward-maximising behaviour, μ searches for data with high model uncertainty. While each population Q and Q can be seen as performing Bayesian inference, is not immediately clear that the full agent admits a Bayesian interpretation. We leave this question for future work.
policy Ta-2 with probability K/(K+N) and the exploration
There are several equally valid implementations of TDU (see Appendix A for generic implementations for value-based learning and policy-gradient methods). In our case, it would be equally valid to define only a single exploration policy (i.e. N = 1) and specify the probability of sampling this policy. While this can result in faster learning. a potential drawback is that it restricts the exploratory behaviour that μ can exhibit at any given time. Using a full bootstrapped ensemble for the exploration policy leverages the behavioural diversity of bootstrapping.
5

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Bootstrapped DQN with TDU
Algorithm 2 Bootstrapped TD-loss with TDU.
Require: M, C: MDP to solve, TDU loss
Require: {00 {Ø" parameters
Require: J,K,N, N.p: p:: hyper-parameters
Require: 7,8, D: hyper-parameters, data
1: Initialise B: replay buffer
1: Initialise +- 0
2: Initialise K + N value functions, QUÔ
2: for 3, 8', E E do
3: while not done do
3: T T (s. 0,V, v, 8 7)
4: Observe and choose Q: QUÔ
Compute {
{8(0', T)
5: while episode not done do
Compute from {ōx k=1 (Eq. 11)
6: Take action arg max Qx(s, a)
Update T by ryr= + 3
7: Sample mask m, m, mn.
7: Compute {6z1 j= = {
8: Enqucue transition (s, a, 5 m) to B
8: t l + Σ m,03 + Σラ= mK+30j
9: Optimise [((0*) K
06)) 11.7, 11,,8 3, D~B)
10: end while
end for 10: return: / 12(2 + KK)
11:
end while
EMPIRICAL EVALUATION
5.1 BEHAVIOUR SUITE
Bsuite (Osband et al., 2020) was introduced as a benchmark for characterising core capabilities of RL agents. We focus on a Deep Sea, which is explicitly designed to test for deep exploration. is challenging exploration problem where only one out of 2 policies yields any positive reward. Performance is compared on instances of the environment with grid sizes E {10, 12. .............................. 50}.
with overall "score" that is the percentage of N for which average regret goes to below 0.9 faster than 2 The stochastic version generates a 'bad' transition with probability 1/N. This is a relatively high degree of uncertainty since the agent cannot recover from a bad transition in an episode.
For all experiments, we use a standard MLP with Q-learning, off-policy replay and a separate target network. See Appendix D for details and TDU results on the full suite. We compare TDU on Deep Sea to a battery of exploration methods, broadly divided into methods that facilitate exploration by (a) sampling from a posterior (Bootstrapped DQN, Noisy Nets (Fortunato et al., 2018), Successor Uncertainties (Janz et al., 2019)) or (b) use an intrinsic reward (Random Network Distillation (RND; Burda et al., 201 8b), CTS (Bellemare et al., 2016), and Q-Explore (QEX; Simmons-Fdil 2019)). We report best scores obtained from a performance varies substantially between methods; only TDU performs (near-) Jottimloy on both the deterministic and stochastic version. Methods that rely on posterior sampling do well on the deterministic version, but suffer a substantial drop in performance on the stochastic version. As the stochastic version serves to increase the complexity of modelling future state visitation, this is clear evidence that these methods suffer from the estimation bias identified in Section 2. We could make Q-explore and NoisyNets perform well in the default Bsuite setup, while Successor Uncertainties suffers a catastrophic loss of performance on the stochastic version of DeepSea.
al., sweep for each method. Overall,
Examining TDU, we find that it facilitates exploration while retaining overall performance except on Mountain Car where 3 > 0 hurts performance (Appendix D). For Deep Sea (Figure 2), prior functions are instrumental, even for large exploration bonuses (8 >> 0). However, for given prior strength, TDU does better than the BDQN (3 = 0). In the stochastic version of Deep Sea, BDQN suffers a significant loss of performance (Figure 2). As this is a ceteris paribus comparison, this performance difference can be directly attributed to an estimation bias in the BDQN that TDU circumvents through its intrinsic reward. That TDU is able facilitate efficient exploration despite environment stochasticity demonstrates that it can correct for such estimation errors.
Finally, we verify Proposition 2 experimentally. We compare TDU to versions that estimate uncer- tainty directly over Q (full analysis in Appendix D.2). We compare TDU to (a) version where is defined as standard deviation over Q and (b) where a (QQ) is used as an upper confidence bound in the policy instead of an intrinsic reward (Figure 2). Neither matches TDU's performance across Bsuite an in particular on Deep Sea. Being ceteris paribus comparisons. this demonstrates that estimating uncertainty over TD-error provides stronger signal for exploration, as per Proposition 2.

---

Under review as a conference paper at ICLR 2021
Deep Sea Deterministic
Deep Sea Stochastic
1
0.75
0.50
0.50
OEX
CTS
RND
TDU
BOQN
SU
NNS
QEX
CTS
RND
TDU
BDQN
SU
NNS
Figure 1: Deep Sea Benchmark. QEX, CTS, and RND use intrinsic rewards; BDQN, SU, and NNS use posterior sampling (Section 5.1). Posterior sampling does well the deterministic version, but struggles on the stochastic version, suggesting an estimation bias (Section 2). Only TDU performs Jottimllp on both the deterministic and the stochastic version of Deep Sea.
Deep Sea Stochastic, ==
8 =
==
A
0.75
Score
0.50
0.25
0
0.0
0.01
0.1
0.5
1.0
2.0
3.0
5.0
0.0
1.0 3.0
0.0
1.0 5.0
Qa Qb TDU Agent
B
A
Figure 2: Deep Sea results. All models solve the deterministic version for prior scale X x= 3 (dashed line). TDU also solves it for À = 1. Left: introducing stochasticity substantially deteriorates baseline performance; including TDU (3 0) recovers close to full performance. Center left: effect of varying X, TDU henefits from diversity in Q estimates. Center right: effect removing prior (A= 0). Increasing improves exploration, but does reach full performance. Right: Qa replaces a (6) with a (Q), Qb acts by argmax, (Q + (s,) a). Estimating uncertainty over Q fails to match TDU.
5.2 ATARI
Proposition 1 shows that estimation bias is particularly likely in complex environments that require neural networks to generalise across states. In recent years, such domains have seen significant improvements from running distributed training platforms that process large amounts of experience obtained through agent parallelism. It thus important to develop exploration algorithms that scale gracefully and can leverage the benefits of distributed training. Therefore, evaluate whether TDU can have a positive impact when combined with the Recurrent Replay Distributed DQN (R2D2) (Kapturowski al., 2018), which achieves state-of-the-arr results the Atari2600 suite by carefully combining set of key components: a recurrent state, experience replay, off-policy value learning and distributed training.
As baseline we implemented distributed version of the bootstrapped DQN with additive prior functions. We present full implementation details, hyper-paramen choices, and results on all games in Appendix E. For our main results, we run each agent on 8 seeds for 20 billion steps. We focus on games that well-known pose challenging exploration problems (Machado al., 2018): montezuma montezuma_reveeeeee pit fa 1, pr vate_eye, solaris. venture, gravitar. and tennis. s. Following standard practice, Figure reports Human Normalized Score (HNS), HNS Agent Random
Human Randoman as an aggregate result across exploration games as well as results on monte umaa aaama__eveetee revenge and tennis, which are both known to be particularly hard exploration games (Machado al., 2018).
7

---

Under review as a conference paper at ICLR 2021
montezuma revenge
tennis
hard exploration games
5000
20
1.5
4000
10
3000
1.0
2000
EDDU-R2D-PRUUS
TDU-R202
1000
0.5
R2D2
210
B-R2D2
0.0
0.5
1.5
2.0
0.0
0.5
2.0
0.0
0.5
2.0
Environment steps 1e10
Environment steps 1e10
Environment steps 1e10
Figure 3: Atari results with distributed training. We compare TDU with and without additive prior functions to R2D2 and Bootstrapped R2D2 (B-R2D2), Left: Results for monte ez euueereeeeeeeeeeeeeeeeee Center: Results for tennis. Right: Mean HNS for the hard exploration games in the Atari2600 suite (including tennis). Shading depicts standard deviation over 8 seeds.
Generally, we find that TDU facilitates exploration substantially, improving the HNS score across exploration games by 30% compared to baselines (right panel, Figure 3). An ANOVA analysis yields statistically significant difference between TDU and non-TDU methods, control- ling for game (F' = 8.17, = 0.0045). Notably, TDU achieves significantly higher returns on and is the only agent that consistently achieves the maximal return on tennis. We report all per-game results in Appendix E.4. We observe no significant gains from including prior functions with TDU and find that bootstrapping alone produces relatively marginal gains. Beyond exploration games, TDU can match or improve upon the baseline, but exhibits sensi- tivity to TDU finding is in line with observations made by (Puigdomènech Badia al., 2020); combining TDU with online hyper-parameter adaptation (Schaul et al., 2019; Xu et al., 2018; Zahavy et al., 2020) are exciting avenues for future research. See Appendix E for further comparisons.
montezuma_revengee
parameterssssss (3, number of explorers (N); see Appendix E.3 for details). This
In Table 1, we compare TDU to recently proposed state-of-the-an exploration methods. While comparisons must be made with care due to different training regimes, computational budgets, and architectures, we note general trend that no method is uniformly superior. Methods that are good on extremely sparse exploration games (mont ezuma_ revenge and pitfall! !) tend to do poorly on games with dense rewards and vice versa. TDU is generally among the top 2 algorithms all cases except on mont tima revenge and pit !, state-based exploration is needed to achieve sufficient coverage of the MDP. TDU generally outperforms both Pixel-CNN (Ostrovski al., 2017), CTS, and RND. TDU the only algorithm to achieve super-human performance on solaris and achieves the highest score of all baselines considered on venture.
6 RELATED WORK
Bayesian approaches to exploration typically use uncertainty as the mechanism for balancing ex- ploitation and exploration (Strens, 2000). A popular instance of this form of exploration is the PILCO algorithm (Deisenroth & Rasmussen, 201 1). While we rely on the bootstrapped DQN (Osband et al., 2016a) in this paper, several other uncertainty estimation techniques have been proposed, such as by placing parameterised distribution over model parameters (Fortunato et al., 2018 8; Plappert et al., 2018) or by modeling distribution over both the value and the returns (Moerland et al., 2017), using Bayesian linear regression the value function (Azizzadenesheli et al.. 2018; Janz et al., 2019), or by modelling the variance over value estimates as a Bellman operation (O' Donoghue et al., 2018). The underlying exploration mechanism in these works is posterior sampling from the agent's 's current beliefs (Thompson, 1933; Dearden et al., 1998); our work suggests that estimating this posterior is significantly more challenging that previously thought.
An alternative to posterior sampling is to facilitate exploration via learning by introducing an intrinsic reward function. Previous works typically formulate intrinsic rewards in terms of state
8

---

Under review as a conference paper at ICLR 2021
Table I: Atari benchmark on exploration games. Ostrovski et al. (2017), *Bellemare et al. (2016), Burda al. (2018b), "Choi al. (2018), *Puigdomênech Badia et al. (2020), + *With prior functions.
Montezuma's Revenge
Private Eye
Algorithm
Gravitar
Pitfall!
Solaris
Venture
Avg. Human
3,351
4,753
6,464
69,571
12,327
1,188
R2D2
15,680
2,061
0.0
5,322.7
3,787.2
1,970.7
DQN-
859.1
2,514
0.0
15,806.5
5,501.5
1,356.3
PixelCNNt
DQN-CTS
498.3
3,706
0.0
8,358.7
82.2
RND
3,906
10,070
8,666
3,282
1,859
CoEx*
11,618
11,000
1,916
NGUS
14,100
10,400
8,400
100,000
4,900
1,700
TDU-R2D2
13,000
5,233
0
40,544
14,712
2,000
TDU-R2D2*
10,916
2,833
0
61,168
15,230
1,977
visitation (Lopes et al., 2012: Bellemare al., 2016; Puigdomênech Badia et al., 2020), state novelty (Schmidhuber, 1991; Oudeyer & Kaplan, 2009; Pathak et al., 2017), or state predictability (Florensa al., 2017: Burda et al., 2018b; Gregor al., 2016; Hausman et al., 2018). Most of these works rely on properties of the state space to drive exploration while ignoring rewards. While this can be effective in sparse reward settings (e.g. Burda al., 201 8b; Puigdomênech Badia al., 2020), can also lead to arbitrarily bad exploration (see analysis in Osband et al., 2019).
smaller body of work uses statisties derived from observed rewards (Nachum al., 2016) or TD-errors to design intrinsic reward functions; our work is particularly related to the latter. Tokic (2010) proposes an extension e-greedy exploration, where the TD-error modulates states with higher TD-error. Gehring & Precup (2013) use the mean absolute TD-error, accumulated over time, to measure controllability of state and reward the agent for visiting states with low mean absolute TD-error. In contrast to our work, this method integrates the TD-error over time to obtain a measure of irreducibility. Simmons-Edie one is trained data collected under both networks and the other obtains intrinsic reward equal to the absolute TD-error the first network on a given transition. In contrast to our work, this method does not have a probabilistic interpretation and thus does not control for uncertainty the environment. TD-errors have also been used in White et al. (2015), where surprise defined in terms of the moving average of the TD-error over the full variance of the TD-error. Kumaraswamy et al. (2018) rely on least-squares TD-errors to derive a context-dependent upper-confidence bound for directed exploration. Finally, using the TD-error an exploration signal related the notion of "learnability" or curiosity prediction error in dynamics model (e.g. Schmidhuber, 1991: Oudeyer al., 2007; Gordon Ahissar, 2011; Pathak et al., 2017).
be higher in
et al. (2019) propose to use two Q-networks, where
signal for exploration, which is often modelled in terms of the
7 CONCLUSION
We present Temporal Difference Uncertainties (TDU), method for estimating uncertainty over an agent's value function. Obtaining well-calibrated uncertainty estimates under function approximation is non-trivial and we show that popular approaches, while in principle valid, can fail to accurately represent uncertainty over the value function because they must represent an unknown future.
This motivates TDU as an estimate of uncertainty conditioned observed state-action transitions, so that the only source of uncertainty for a given transition due to uncertainty over the agent's parameters. This gives rise to intrinsic reward that encodes the agent's model uncertainty, and we capitalise on this signal by introducing a distinct exploration policy. This policy is incentivised to col- lect data which the agent has high model uncertainty and highlight how this separation gives rise to a form of cooperative multi-agent game. We demonstrate empirically that TDU can facilitate efficient exploration in hard exploration games such Deep Sea and Montezuma's Revenge.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Arizzadenesheli, K., Brunskill, E., and Anandkumar, A, Efficient exploration through Bayesian deep Q-Networks. arXiv preprint arXiv: 02, 2018.
Belkin, M., Hsu, D., and Xu, J. Two models of double descent for weak features. arXiv preprint arXiv:190..07577 2019.
Bellemare, M., Srinivasan, S., Ostrovski, G., Schaul, T., Saxton, D., and Munos, R. Unifying
count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems, 2016.
Bradbury, J., Frostig, R., Hawkins, P., Johnson, M. J., Leary, C., Maclaurin, D., and Wanderman- Milne, S. JAX: composable transformations of Python+NumPy programs, 2018. URL http: //github. com/ wwwpe//gogg///eooo jax.
Burda, Y., Edwards, H., Pathak, D., Storkey, A. J., Darrell, T., and Efros, A. A. Large-scale study of curiosity-driven learning. CoRR, abs/1808.0425 04355, 2018a.
Burda, Y., Edwards, H., Storkey, A. J., and Klimov, O. Exploration by random network distillation. arXiv preprint arXiv: 2294,, 2018b.
Choi, J., Guo, Y., Moczulski, M., Oh, J., Wu, N., Norouzi, M., and Lee, Contingency-awan exploration in reinforcement learning. arXiv preprint 181 1at:::1111144444 1.01483, 2018.
Dearden, R., Friedman, N., and Russell, S. Bayesian Q-learning. In Association for the Advancement of Artificial Intelligence, 1998.
Deisenroth, M. and Rasmussen, C. E. Pilco: A model-based and data-efficiem approach to policy search. In International Conference on Machine Learning, 2011.
Florensa, C.,, Duan, Y., and Abbeel, P. Stochastic neural networks for hierarchical reinforcement learning. International Conference on Learning Representations, 2017.
Fortunato, M., Azar, M. G., Piot, B., Menick, J., Osband, I., Graves, A., Mnih, V., Munos, R., Hassabis, D., Pietquin, O., et al. Noisy networks for exploration. In International Conference on Learning Reprexentations, 2018
Gehring, C. and Precup, D. Smart exploration in reinforcement learning using absolute temporal difference errors. Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems, 2013.
Gordon, G. and Ahissar, F. Reinforcement active learning hierarchical loops. In International Joint Conference on Neural Networks, pp. 3008-3015, 2011.
Gregor, K., Rezende, D. J., and Wierstra, D. Variational intrinsic control. CoRR, abs/1611.07500 2016.
Guez, A., Viola, F., Weber, T., Buesing, I.., Kapturowski, S., Precup, D., Silver, D., and Heess, N. Value-driven hindsight modelling. In Advances in Neural Information Processing Systems, 2020.
Hausman, K., Springenberg, J. T., Wang, Z., Heess, N., and Riedmiller, M. Learning an embedding space for transferable robot skills. In International Conference Learning Representations, 2018.
Janz, D., Hron, J., Hernández-Lobate J. M., Hofmann, K. and Tschiatschek, S. Successor un- certainties: exploration and uncertainty in temporal difference learning. In Advances in Neural Information Processing Systems, 2019.
Kapturowski, S., Ostrovski, G., Quan, J., Munos, R., and Dabney, W. Recurrent experience replay in distributed reinforcement learning. In International Conference on Learning Representations, 2018.
Kearns, M. and Singh, Near-optimal reinforcement learning in polynomial time. Machine learning. 49(2-3):209-22 232, 2002.
Kingma, D. P. and Ba, Adam: A method for stochastic optimization. In International Conference Learning Representations, 2015.
10

---

Under review as a conference paper at ICLR 2021
Kumaraswamy, R., Schlegel, M., White, A., and White, M. Context-dependent upper-confidence bounds for directed exploration. In Advances in Neural Information Processing Systems, pp. 4779-4789 2018.
Li, Y., Gimeno, F., Kohli, P., and Vinyals, O. Strong generalization and efficiency in neural programs. arXiv preprini arXiv:2007.03622 2020.
Liu, C., Zhu, L.,, and Belkin, M. Toward a theory of optimization for over-parameterized systems of non-linear equations: the lessons of deep learning. arXiv preprint arXiv:2003.00307 2020.
Lopes, M., Lang, T., Toussaint, M., and Oudeyer, P.-Y. Exploration in model-based reinforcement learning by empirically estimating learning progress. Advances in Neural Information Processing Systems, 2012.
Machado, M. C., Bellemare, M. G., Talvitie, E., Veness, J., Hausknecht, M.. and Bowling, M. Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research, 61 522-5, 2018.
Mnih, V., Kavukcuoglu, K., Silver, D.,, Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Ried- miller, M., Fidjeland, A. K., Ostrovski, G., et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-533 2015.
Moerland, T. M., Broekens, J., and Jonker, C. M. Efficient exploration with double uncertain value networks. In Advances in Neural Information Processing Systems, 2017.
Nachum, O., Norouzi, M., and Schuurmans, D. Improving policy gradient by exploring under- appreciated rewards. In International Conference on Learning Representations, 2016.
Osband, I., Russo, D., and Van Roy, B. (more) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems, 2013.
Osband, I,, Blundell, C., Pritzel, A., and Van Roy, B. Deep exploration via bootstrapped DQN. In Advances in Neural Information Processing Systems, 2016a.
Oshand, I,, Van Roy, B., and Wen, Z. Generalization and exploration via randomized value functions. In International Conference on Machine Learning, 2016b.
Osband, I., Aslanides, J., and Cassirer, A. Randomized prior functions for deep reinforcement learning. Advances in Neural Information Processing Systems, 2018.
Osband, I., Van Roy, B., Russo, J., and Wen, Z. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20:1-62, 2019.
Osband, I., Doron, Y., Hessel, M., Aslanides, J., Sezener, E., Saraiva, A., McKinney, K., Lattimore, T., Szepezvari, C., Singh, S., and Benjamin Van Roy, Richard Sutton, D. S. H. V. H. Behaviour suite for reinforcement learning. In International Conference on Learning Representations, 2020.
Ostrovski, G., Bellemare, M. G., van den Oord, A., and Munos, R. Count-based exploration with neural density models. In Proceedings of the 34th International Conference on Machine Learning-Volas 70, pp. 2721-2730. JMLR. org, 2017.
Oudeyer, P.-Y. and Kaplan, What intrinsic motivation? typology of computational approaches. Frontiers in neurorobotics, 1:6, 2009.
Oudeyer, P.-Y., Kaplan, F., and Hafner, V. Intrinsic motivation systems for autonomous mental development. IEEE transactions on evolutionary computation, 11(2):265-2 -2266666666662-1 2007.
O' D'Doogguue B., Osband, I., Munos, R., and Mnih, The uncertainty bellman equation and exploration. In International Conference Machine Learning, 2018.
Pathak, D., Agrawal, P., Efros, A. A., and Darrell, T. Curiosity-driven exploration by self-supervised prediction. In International Conference on Machine Learning, 2017.
Peng. and Williams, R. J. Incremental multi-step Q-learning. In Machine Learning Proceedings 1994, pp. 226-232. Elsevier, 1994.
11

---

Under review as a conference paper at ICLR 2021
Plappert, M., Houthooft, R., Dhariwal, P., Sidor, S., Chen, R. Y., Chen, X., Asfour, T., Abbeel, P., and Andrychowicz, M. Parameter space noise for exploration. In International Conference on Learning Representations, 2018.
Puigdomenech Badia, A., Sprechmann, P., Vitvitskyi, A., Guo, D., Piot, B., Kapturowski, S., Tieleman, O., Arjovsky, M., Pritzel, A., Bolt, A., and Blundell, C. Never give up: Learning directed exploration strategies. In International Conference on Learning Representations, 2020.
Schaul, T., Borsa, D., Ding, D., Szepesvari, D., Ostrovski, G., Dabney, W., and Osindero, S. Adapting behaviour for learning progress. arXiv preprint arXiv:1912.000 10, 2019.
Schmidhuber, J. Curious model-building control systems. In Proceedings of the International Joint Conference on Neural Networks, 1991.
Simmons-Edke Edler, R., Eisner, B., Mitchell, E., Seung, H. S., and Lee, D. D. Qxplore: Q-learning exploration by maximizing temporal difference error. arXiv preprint 1906::/906.081800 2019.
Singh, S. P., Barto, A. G., and Chentanez, N. Intrinsically motivated reinforcement learning. In Advances in Neural Information Processing Systems, 2005.
Strens, M. A Bayesian framework for reinforcement learning. In International Conference Machine Learning, 2000.
Thompson, W. R. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-294 1933.
Tokic, M. Adaptive e-greedy exploration in reinforcement learning based on value differences. In Annual Conference on Artificial Intelligence, pp. 203-210. Springer, 2010.
Van Hasselt, H., Guez, A., and Silver, D. Deep reinforcement learning with double Q-learning. In Association for the Advancement of Artificial Intelligence, 2016.
White, A. et al. Developing predictive approach knowledge. PhD thesis, University of Alberta, 2015.
Williams, R. and Peng, Function optimization using connectionist reinforcement learning algorithms. Connection Science, 3(3):241-268, 1991.
Xu, T., Liu, Q.. Zhao, L., and Peng, Learning to explore via meta-policy gradient. In International Conference on Machine Learning, 2018.
Zahavy, T. Xu, Z., Veeriah, V.. Hessel, M.. Oh. van Hasselt, H., Silver, D., and Singh, Self-tuning deep reinforcement learning, arXiv preprint arXiv:2002.12928, 2020.
Ziebart, B. D., Maas, A., Bagnell, A., and Dey, K. Maximum entropy inverse reinforcement learning. In Association for the Advancement of Artificial Intelligence, 2008.
12

---

Under review as a conference paper at ICLR 2021
A IMPLEMENTATION AND CODE
In this section, we provide code for implementing TDU in a general policy-agnosien setting and in the specific case of bootstrapped Q-learning. Algorithm 3 presents TDU in policy-agnostic framework. TDU can be implemented as a pre-processing step (Line 9) that augments the reward with the exploration signal before computing the policy loss. Algorithm is used to learn single policy, it benefits from the TDU exploration signal but cannot learn distinct exploration policies for it. In particular, on-policy learning does not admit such a separation. To learn distinct exploration policy, we can use Algorithm to train the exploration policy, while the another policy is trained to maximise extrinsic rewards only using both its own data and data from the exploration policy. case of multiple policies, we need mechanism for sampling behavioural policies. In our experiments we settled on uniform sampling; more sophisticated methods can potentially yield better performance.
In the case of value-based learning, TDU takes special form that can be implemented efficiently as a staggered computation of TD-errors (Algorithm 4). Concretely, we compute an estimate of the dis- tribution of TD-errors from some given distribution over the value function parameters (Algorithm Line 3). These TD-errors are used to compute the TDU signal Ø, which then modulates the reward used train Q function (Algorithm 4, Line 7). Because the only quantities being computed TD-errors, this can be combined into a single error signal (Algorithm 4, Line 11). When implemented under bootstrapping, Qpar denotes the ensemble Q and Qt seeiid__dii cidde_diston disttribtttttiiee ion ion params denotes the ensemble 2; we compute the loss in Algorithm 2.
Finally, Algorithm 5 presents a complete JAX (Bradbury et al., 2018) implementation that can be used along with the Bsuite (Osband al., 2020) codebase.' We present the corresponding TDU agent class (Algorithm 4), which is modified version of the Boot st sappedd class in bsuite/basee http://aseeeeeeeeeeeeeee httpat//bbooogpoeeeeee http://ooooo.oo/age..t.... agent. py py and can be used by direct swap-in.
Algorithm 3 Pseudd-code for generic TDU loss
def (tsantianns,,ons,, pi_params, @t: lei deslldd_dsttrbuttai params,, bato)
2 Ratimate TD-error distribution.
4 arzay [[d_errez (p, transitione) p sample (QUilde distr parpam))))) })
5 Compute
td (0.5 (td * 2))
7
Compute exploration honus.
9
transitions. +- beta * atep_gradient (std(td, axis-1))
t Compute policy loss on transitien with augmented rewerd. pi_less pi__oss__fnnpccceeeeeeaplppossoe par_ppaasspppp,ss params, transitions)
return posl loss
Algorithm 4 Pseudo-code for Q-learning TDU loss
1 def loss (tramasitio p_params, siilde__istribule ion params, peneppiiattio__pammm__. betal:
2 Ratimate TD-error distribution.
3 LdLK ( transitions) Toz in sample http::/eee@eeeeeeesiibooooeoe http::dddisiiotttooopeeeeeeee
4
Compute exploration bonus and g-function reward.
6 lonsittroos...aardd to bata a stoppgradien (td_, axla=1)1 Ld_ercoz pa_par,ms, transitions)
8
9 Combine for overall TD-1oss,
edeerrors (e td_ia), exis=l)
toss m0.5 (td_ersers) ** 2)1
return td_losa
Availlable https: http:/ggttttttet htt.uubb.com//eeppeeeeee nd/ /bsui
13

---

Under review as a conference paper at ICLR 2021
Algorithm 5 JAX implementation of TDU Agent under Bootstrapped DQN
Signal Esploration acthors. Licansed under 2 the Apache License, Version 2.0 ithe "License"I; yeu may not use this tile except in compliance with Lisense attpss//ww. wasch..og//iccass//L/
Copyricht
Tomperal Differance Incartainties
License. may occain copy
4 4 Unlesa requized by applicable las or agreed to la seiting, aufiware distributed under the License ia distributed on an "AS 18" NASтS, MиSrOоT MARRANTTR oe CONDITOONS
RNND, wither express or implied. 6 See the License tor specitic language governing pernissions Linitations under the License.
class YDU (bsuite. baselines. pax.bboe..gn..ooeeseeeeeegg
9
def _iit (self, K: "*"rOU under Bootstrapped DQN with randomized prior functicns. super (TDU, sellr)__ntt.... -t____ntnn________________ [+*kwargs)
kwargs: Any!
setwork, ept iniimiee,, N kwarga ('nnework"], kwargs I' opLimizer'), kwargs aur_eesembbe roise_scale, discount kwazgs noise_scale"), kwergs discount"]
def tparamss: NkrParams, target_params: hkrPara
transitions: (equence[jng.ddaree
-> jup.nderray:
"*TD-arror with added reward roise half-in boatstrap, *** e_tml, a_tml, r_t, d_t, ect, 2_t transitions
g_tml setwork. www.e/ekk.ppyppppp...e (parans, (pray o_tml)
q network. (target__erams, o.t)
noisa_scale return jax.vmap (raa...aelaaarrnnnnggggaoe (g_tml, a_tml, ELt, diacount d_t, a_t)
23
25
def loss (parana: Sequence (hk, Params), parget_paraaa: Sequence [hk, Parama), izansitiona: Sequencel (Squunoe[jsppndaze (dp.ndarzayl)) onng-eearnng loss with TDU, *ea
jap.ndarzay:
28
# Compure ID-orvors for first к members.
o_tmi,
r_t, pargee__araan(K]
mut,
transitions
30
td_K - [pazaas [k], (o_tml, a_tml, r_t, d_t, ect, z_tli, k)l) for ronge
IDU signal on first & TD esrors. beta Jax. -rappggaddien itd wttp..ttckktta axis-0), axis=01)
Compute TD-errors augmented reward last members.
37
Ld_N = [Ld(pazams [k),, parget__arans (o_tml, a_tml, r_t, d.t, out, s_tli, k]]) for range (K, N)
return jep. jap.stack (td_ + tdLK) 2)
def update (staces Trainingstate, gradient: Sequence (jnp.nda-ray)) -> Trainingstacee
"*rrrdientt update ensemble member, *eu updates, new_opt_state new_params optix.apply apply_ (etelly paraae, updates)
44
optimizer.update igradient, state.
(er (pazams-new_psreee zeturn TrainingState ppt_statemncw_pp__tttt step=state.step +
prgget_patam==ataee Larget_params,
1ja
(s.Lae: Sequence
(states:
31
trensiciens: Sequence (jpp.adarray)) -> Sequence (TrainingStatel] "*ppoes a step of SCD for =ipiatistttepaarass Waate.targe__pareet
ensemble over "transitiona uas
params, targes_ gradients jex. gred (params, target_parems, transitions) [update (state, gradient) for state, gradiant in zip (states, gradients)
for states))
56
self sgd sgd_step patch BeotDQN sgd_step with agd_step.
38
def update iself, timestep: dr_env. Timostep,, action: base.Action, new_timestep: delenv. Timestep):
"*"Updata the agent: : add transition to replay and periodically do scE.*">
if new_tinestep. last last self, easemble etg.emmmeee....a..od....aaaaaiid (0, self:_num_enaemble
63
self
65 mask woo.raddmm.biomiiall.. [1, self._nack
self._num_ensemble roise randor, randn (se) feelff_um_met __n__ensembbll)
transitions (timestep. chservation, action, fl.atoat32 (nsw_timee
np. flaa:32 (new_nimeen www.tttmmeppp.te diccuutt,, new timestep..comm..m wtw.ttt.ccseeeaeeeee...........e chservatior, mask,,,, noise)
rell._replay, atd if self._ size self. melf._min_rellay_siie recurn
70
if self._total_step self._agd_perico 0:
transitions sels. www.rpyy.sppllllaate.ee... bttthhh_i_tttttttitett
75
salf salf._ensembl self sgd enssembl,, transitions)
77
for k, state in iae state.step salif___arree_uuuaat perioddeedddd sel enlfa_ensshhllll [(k) state. rept ptr.rrrrrtraarassstttooorrraa
14

---

Under review as a conference paper at ICLR 2021
B PROOFS
We begin with the proof of Lemma 1. First, we show that if Eq. 2 and Eq. fail, p(0) induce distribution p(Qs) whose first two moments biased estimators of the moments of the dis- tribution of interest p)),), for any choice of belief over the MDP, p(M). We restate it here for convenience.
Lemma 1. Ee [Qa] and Vo[Qa] fail to satisfy Eqs. 2 and 3, respectively, they are biased estimators EM [ and Vas [QM for any choice of p(M).
Proof. Assume the contrary, that EM [Q (s, T(s)]] EolQo(s, for all (s.a) E 8 x A. Eqs. and do not hold, then for any M E {TE, V).
Ma I (s, (()))] Mo (s, (s)))
(12)
* Mo E. Ex + 7
(13)
m))(
Ey -d Mo (('))) ((((())()))
(14)
( MM 10 (s', (T's)(ss)
(15)
(w((s)((s))
-M ()) 1r+ m ((),
(16)
-MM 10 (8,
(17)
contradiction; conclude that Mas (s, (s))] * Mo|Qo (s))]. Eqs. 13 and 17 use Eqs. and 3; Eqs. 12, 13 and 15 follow by assumption; Eqs. 14 and 16 use linearity of the expectation operator Iy,,s' by virtue of M being defined over 0. As (s,a,r, and p( (M) are arbitrary, the conclusion follows.
Methods that take inspiration from by PSRL but rely on neural networks typically approximate p(M) by parameter distribution p(0) over the value function. Lemma 1 establishes that the induced distribution p( p(Qa) under push-forward of p(0) must propagate the moments of the distribution p(Qo) consistently over the state-space to be unbiased estimate of p( (M)M, ), for any p(M).
With this in mind, we now turn to neural networks and their ability to estimate value function uncertainty in MDPs. To prove our main result, establish two intermediate results. Recall that we define a function approximator Qo = w o Φg, where = (Wi,..., Wn, 01...., w E R" is linear layer and ø S x A + R" is feature extractor with parameters 0 IR..
As before, let M be an MDP the number of states and actions with E, Qo((s a)] * E, QQ((', a') with A C A S A the set of all such pairs (s, a, d'). This set can be thought of as a minimal MDP-the set of states within larger MDP where the function approximator generates unique predictions. It arises in MDP through dense rewards, stochastic rewards, or irrevocable decisions, such as in Deep Sea. Our first result is concerned with very common approach, where & is taken be a point estimate that p(f) p(w). This approach is often used for large neural networks, where placing a posterior over the full network would be too costly (Osband et al., 2016a; O' Donogguue al., 2018; Azizzadenesheli et al., 2018; Janz et al., 2019).
R. 7) with discrete state and action spaces. We denote by N
Lemma 2. Let p(0) = p(w). N > n, with w E RR,, then Eg (Qo) fail to satisfy the first moment Bellman equation (Eq. 2). Further, if N >> n², then Vo[Qo) fail to satisfy the second moment Bellman equation (Eq. 3).
Proof. Write the first condition of Eq. 2 as
Bg w (o(ss a)] Eo [Frr ot [r Foo ( (ss')]]]
(18)
15

---

Under review as a conference paper at ICLR 2021
Using linearity of the expectation operator along with p(0) p(w), have
[w|w] 6o(s, a) pls,aa + Bw [w]" Eo-loo(s (s))))
(19)
where u((sa)) Ey (r]. Rearrange to get
u(s,a) - =Ewlw]" (os(ss,a) - m(s)))
(20)
By assumption T2 (Q,((, a)] & Eg(Qa(('s d')], which implies @0 a) # D0 =Ts'sssss)))))))))>))) ) by linearity in w. Hence @o(s, a) yLe (ool's TT (s is non-zero and unique for each (s, a). Thus, Eq. 20 forms a system of linear equations over S x A, which can be reduced to full-rank system over N: = $Ew[w] where μ E RRN stacks expected reward μa(s, a) and + E RNxx stacks vectors ( a) - Er (oo(s' (s'))] row-wise. Because is full rank, N > n, this system has no solution. The conclusion follows for Es [Qe]. If the estimator of the mean is used to estimate the variance, then the estimator of the variance is biased. For an unbiased mean, using linearity in w, write the condition of Eq. 3 as
B. Eg [(w Eu (w)) [ Eo [[(e Eu En (w)) Eg (do (+))]]
(21)
Let = (w. - (ull wt (0 = ywu " Es (sha ,')]. Rearrange to get
Eg [x² v²] =Eve(< y)(x T)]
(22)
Expanding terms, we find
0 Eg ( (0T -2E a')il) (wT >BB (
(23)
Eew [ d3 d
Cov (wi, myy) d; dzdj.
(24)
where we define d= ( a) >Bs' (s' a')] and d = Φs(s.a) + [oolss ,')), As before, d' and dt are non-zero by assumption of unique Q-values. Perform change of variables Wa(i.) = Cov(u,, wy), An(i.)) d, dj to write Eq. 24 as 0 = Alw. w. Repeating the above process
for every state and action we have system 0 Aw, where 0 E R-V and A E TR: xxx are defined by stacking vectors À row-wise. This is a system of linear equations and if N > n² no solution exists; thus, the conclusion follows for Ve [Qel, concluding the proof.
Note that if Eg [Q]] is biased and used to construct the estimator Ep [Qu], then this estimator is also biased; hence N > n, p(0) induce biased estimators [Qa] and Vaa [Qo] of EM [2_ and VM (Q4) respectiivlly.
statement about linear uncertainty. While the result is not surprising from this point of view, it is nonetheless frequently used approach to uncertainty estimation. We may hope then that by placing uncertainty over the feature extractor well, we can benefit from its nonlinearity to obtain greater representational capacity with respect to uncertainty propagation. Such posteriors come a price. Placing full posterior over neural network often computationally infeasible, instead a common approach is to use diagonal posterior, i.e. Cov(@, 0,) 0 (Fortunato et al., 2018; Plappert et al., 2018). Our next result shows that any posterior of this form suffers from the same limitations as placing posterior only over the final layer. We establish something stronger: any posterior of the form p(0) = (()) suffers from the limitations described Lemma 2.
Lemma 2 can be
Lemma 3.
Let p(0) (()): if moment Bellman equation (Eq. 2). Further, if N > n², then Vo [Q]] fail to satisfy the second moment Bellman equation (Eq. 3).
with E Ra, then Eg [Qe fail satisfy the first
16

---

Under review as a conference paper at ICLR 2021
Proof. The proof largely proceeds as in the proof of Lemma 2. Re- Eq. 19 as
Ew Eoldo(s, a)] p(s,a) a) + 12 [w]] E. (Boloo(s', (
(25)
Perform a change of variables G = [ol to obtain
pls, a) = Eullv]" (3(5. ~ll Polo', ( m()))
(26)
Because Eg (s,(s a)] + Eg "ss,Q a.)], by linearity in have that ō(s, a) - a') is non-zero for any (s', a') and hence Eq. 26 has no trivial solutions. Proceeding as in the proof of Lemma obtains E [w]] where is analogously defined. Note that if N > there is no solution E. [w] for any admissible (full-rank) choice of Φ, and hence the conclusion follows for the first part. For the second part, using that Eg- E. in Eq. 24 yields
0
Bw وا Eo dd d;
Cov (wi, Wy) Eo (d, dī}
(27)
Perform a change of variables Àa(i.)) Es [dr d7] Again, by Eo[Qo a)] + (Eo( have that À non-zero; proceed as before to complete the proof.
We now ready prove our main result. We restate it here for convenience:
Proposition If the number of state-action pairs where Eg (o a)] + Eg(Qa(s', (oosss'a') d')] is greater than n, where w RR.", then R.o [Q)] and Vo(Qu) are biased estimators of T.M [Q and V M [Q for any choice of p(M).
Proof. Let p(0) be of the form p(0) = p(w) or p(0) = p(w)p(1). By Lemmas 2 and 3, p(0) fail to satisfy Eq. 2. By Lemma 1, this causes E.g [Qal to be a biased estimator of EA [Q. This in turn implies that Vo[Qu] is a biased estimator of V [Q_]_ Further, if N > n V [Q]] is biased independently of Eg [Qo].
We now turn to analysing the bias of our proposed estimators. As before, we will build up to Proposition 2 through series of lemmas. For the purpose of these results, let B S A + R denote bias Eg [oa] in any uple (s, a) E S x A, so that Bias(Ea [oo] (s, a)) = B(s,a).
Lemma 4. Given a transition T == (s, a, s'),,, s'), any p(M), given p(0), if
B(s', (0,2/7)
(28)
B(s, a)
then E, ()) T] has less bias than EE[Qu(5,
Proof. From direct manipulation of Es (00 7) r]. we have
((0, | 7| Bsl: +r Qo(s, a)]
(29)
"TEo\oo(', (('))) + E. (0000ss,
(30)
-TEMQH" (s', ass')) +r EM Q (s, +)B((', B(s, a)
(31)
= EM [5. (r) + B(s'' - a(s
(32)
Consequently, (ias(E, (8(, r]) = =B((s, ((s)) - Bss.a) and for this bias to be less than Bins(Eo(Qo(s.a))
B(s.a).
require BBB(s', ABBs',T((3) (('))) B(s, [B(s, a)). Let
= B(s', (3s'sT(('')) (Ts's((s)))))) ((s)))/B(ssd) a) and write (7p 1)B(s.a) a)l < B(s, a) from which follows that for this to hold true, must have p E (0,2/7), to be proved.
17

---

Under review as a conference paper at ICLR 2021
We turn to characterising the conditions under which Vol0(0, 7] enjoys smaller bias than VolQo(s, a)]. Because the variance term involves squaring the Tr-rrror, we must place some restrictions the expected behaviour of the Q-function to bound the bias. First, with B, let C': A - IE denote the bias of lgg [Q]] for any tuple (s, a) E S x A, so that Bias Egg C(s, a). Similarly, let D S A + denote the bias of EEg [Qo(d', (T)')) a)] for any transition (s, a, 8 AxS.
Lemma 5, For any T and any p(M), given p(0), define relative bias ratios
B(s', B(s,a)
Φ ((s',T(5))
D(s,a,8')
EM QQ (8', π ((5')
(33)
C(s,a)
C(s,a)
EM QQ (8, a)
There exists 1, k z az such that Volō(0, r] have less bias than V VolQo a)) In particular, if = σ K a 1, then
BBass (V, 7) --) = 111-1111))) 1)² Bias Vo (Qu(1, a))) < Bias(Va (s)
(34)
Further, ifp = 1/7, K 1/7, 1/72, then (Vo -) r]) for any
Proof.
We begin by characterising the bias of Vo Vo(Qo(s, a)). Write
V VolQo(s, = Ea (((, w)²| - EElQQ E=]
(35)
= =EM Q (s,0) (s
+ C((s, - (EM (Q (s, + a(s,
(36)
The squared term expands as
(s, (s, + B(s,a))² a))² Eas 1Q (s, (s)" + 2BM 10 (s, a)] B(s,a) + B)s,a)² (37)
Let A(s,a) Ei Q2al (s, a)] B(s, a) and write the bias of V (Qa[(0ss a)] as
Bias (Q(ss a))) C(s, a) + 24 a) + ((s, a)²
(38)
We now turn to Volo(0, 7]. First note that the reward cancels this expression:
8(0,T) - -o(8(0, = Roo(' (ss)) - Q)(s. - (s es)) (39)
Denote by zg ~Qoss',
(s, a) with E. [xo] = - a)). Write
Vo(8(0,T) | 7| = E. [6(0, -) - Eol8(0,T)))
(40)
Rgg (1T [
(41)
E. [n]]]
E. [zo
(42)
Eo (7Qo m Qo(s, - (yEoll0(s', Eoloo(s, a)))²
(43)
Eq. 41 uses Eq. 39 and Eq. substitutes back for æg. We consider each term the last expression (o(s,a))) expanding the square yields
in turn For the first term, Eg (7Qo(s', ((s')) (()osss)()))))))))))))))))()))
Te [Qo(s' (()))) - 27 n (s') a)) E. [Q)
(44)
18

---

Under review as a conference paper at ICLR 2021
From this, obtain the bias as
Bias
Eg (1Qoll'' - -0(s,)))) = ( 2yD(s, a, s') C(s,a) (7²0 - 2n + 1) C(s,
(45)
(46)
We can compare this term to C(s, a) in the bias of of Vo(Qo(s, a)] (Eq. 38). For the bias term in Eq. 46 to be smaller, we require (7²6- 2 + 1) C(s,a) < ((s, a) from which it follows that (7 - 27m + 1) E (-1,1). In terms of d, this means
Φ 2ky 2 2k
(47)
7
If the bias term D is close to C' (R. R 1), this is approximately the same condition as for in Lemma 4. Generally, as i grows large, @ must grow small and vice-versa. The gist of this requirement that the biases should be relatively balanced x zs & Rz 1.
For the second term in Eq. 43, recall that Eg (o(ass' (<\)) EM [Q (s', (((')s'))) + B(8, and Eo Eo(Qo a)] = EM [Q (s, a)] + B(s,a). We have
Ee [o(Qo(s, = ((7a - 11)MM [0, (s, + (70 - ()0s1)B(s,a)) (48) (EelQo x ((\)]|
where a = EM 14 (s', (s'))) /EM 10 (8, a)). This expands as
(ya-1)²BMv 12 (s, as) +2(ya 1)(xp 1) Q (s, a) B(s, (xp B(s,)) (49)
Note that from Eq. 34, (EM [Q (s', <>*))) - EM 10 (s. (s,.aa)) (7a-1)3 11 [Q (s, u)] and so the bias of Ve Ve(0(0, r) r] can be written as
Bias( (ios(Vo)0(0, +) F]) = wn (0
(50)
where
k)) = (220 2xx + 1), p) = - 1)(pp - 1), wa(p) = (np - 112- (51)
Note that the bias in Eq. 50 involves the same terms as the bias of Vo(Qo(s, a)] (Eq. 38) but
weighted. Hence, there always exist as set of weights such that Bias (00(0
7]) <
Bias(VV (VelQa a.)]]. In particular, if p = 1/7, K = 1/7, ò = 1/72, then Bias Vo(0 -)) =
0 for any Further, if
o 1, then we have that w, wi x) (2 p) wz(p)
(7 1)² and so
Bias(Volo(A) (Volo(0,T) - = 1(y - 1)a Bias(VolQooss,.. a))) < (ias(VolQo(s.a))). (52)
as desired.
Proposition 2. For any T and any p(M). given p(f), if p (0,2/7). then Eş(8 7] has lower bias than Eg(Qo(s,a) a)). Additionally, there exists p x 1, & ~ 1, =
1. a = 1 such that Vol8(0, 7) T] have less bias than (s, a)). In particular if ò k a))l Further, if
1, then
Bias ((0, 1,, T)) = ( 1)2 Bias Qa(s, a)) <
P 1/7, K % Φ = 1/72 then Bias (V Vo),(0,T) 7 0 for any
Proof. The first part follows from Lemma 4, the second part follows from Lemma 5.
19

---

Under review as a conference paper at ICLR 2021
C BINARY TREE MDP
In this section, we make a direct comparison between the Bootstrapped DQN and TDU on the Binary Tree MDP introduced by Janz et al. (2019). In this MDP, the agent has two actions in every state. One action terminates the episode with 0 reward while the other moves the agent one step further up the tree. At the final branch, one leaf yields a reward of 1. Which action terminates the episode and which moves the agent to the next branch is randomly chosen per branch, so that the agent must learn an action map for each branch separately. This a similar environment to Deep Sea, but simpler in that an episode terminates upon taking wrong action and the agent does not receive small negative reward for taking the correct action. We include the Binary Tree MDP experiment to compare the scaling property of TDU compared to TDU well-known benchmark.
We use the default Bsuite implementation' the bootstrapped DQN, with the default architecture and hyper-parameters from the published baseline, reported in Table 2. The agent is composed of a two-layer MLP with RELU activations that approximate ( a) and trained using experience replay. In the case of the bootstrapped DQN, all ensemble members learn from shared replay buffer with bootstrapped data sampling, where each member Q9= is separate MIP (no parameter sharing) that is regressed towards separate target networks. We Adam (Kingma & Ba, 2015) and update target networks periodically (Table 2).
We run seeds per tree-depth, for depths L E {10, 20,.... 2503 and report mean performance in Figure 4. Our results are in line with those of Janz et al. (2019), differences are due to how many gradient steps are taken per episode (our results are between the reported scores for the 1 x and 25x versions of the bootstrapped DQN). We observe clear beneficial effect of including TDU, even for small values of 3. Further, we note that performance is largely monotonically increasing in B, further demonstrating that the TDU signal is well-behaved and robust to hyperr-paameete values.
We study the properties of TDU in Figure 5, which reports performance without prior functions (A = 0). We vary / and the number of exploration value functions N. The total number of value functions is fixed at 20, and so varying N is equivalent to varying the degree of exploration. We note that N has similar effect to B, but has slightly larger tendency to induce over-exploration for large values of N.
Phttps:/ www.gtttoo...ee.o........om http://///////////s/s/t////ssse/ n jax/ bootdqn.
20

---

Under review as a conference paper at ICLR 2021
expermman:: BootDQN
bela: 0.0
bela: 0.1
bela: 0.5
3000
#episodes until 90% bad episodes
2000
50
100
150
200
250
experiment: 1.0
experiment:
3000
1000
50
100
150
200
250
50
100
150
200
250
Tree MDP problem size
Figure 4: Performance Binary Tree MDP. Top left: BootDQN (3 0). Others: TDU with varying
strenghts of intrinsic reward (3 > 0). Results with prior strength À = 3. Mean performance over seeds for each tree depth.
experiment:
experiment:
experiment: 0.5
0.5 explooexpeers:
0.5 explorers:
explorers:
5000
4000
#episodes until 90% bad episodes
2000
1000
experiment: TDU beta: 1.0
experiment ent: TDU beta: num explorers:
experiment:
beta: 1.0
num explorers:
num. explorers:
4000
3000
2000
1000
0000
50
Tree MDP problem size
Figure 5: Syper--aramettr sensitivity analysis on Binary Tree MDP. Top: Sweep over number of exploration policies (N) for 3 0.5. Top: Sweep number of exploration value functions (N) for 3 = All results without prior functions (A = 0). Mean performance over 5 seeds for each tree depth.
21

---

Under review as a conference paper at ICLR 2021
Exploration
Exploration
Assignment
Credit Assignment
Generalization
Generalization
25
75.
Basic
25
25,
Bastc
Memory
Memory
agent
Q+UCUI
Scale
0.5
Scale
TDU
QU
Nodsn
Figure 6: Overall performance scores on Bsuite. Left: Effect of varying Right: comparison of TDU to exploration under or () as intrinsic reward (QU) immediate bonus (Q+UCB).
D BEHAVIOUR SUITE
From Osband al. (2020): "The Behaviour Suite for Reinforcement Learning (Bsuite) is collection of carefully-designed experiments that investigate core capabilities of reinforcement learning agent The aim of the Bsuite project is to collect clear, informative and scalable problems that capture key issues in the design of efficient and general learning algorithms and study agent behaviour through their performance these shared benchmarks."
D.1 AGENTS AND HYPER-PARAMETER
baselines use the default Bsuite DQN implemen- tation'. We use the default architecture and hyper- parameters from the published bascline, reported in algorithm-specifie hyper-
Table 2: Hyper- plyper-parameters for Bsuite.
discount factor (?) batch size num hidden layers hidden layer sizes ensemble size learning rate
0.99
Table 2, and sweep parameters, reported in Table The agent is com- posed of two-layer MLP with RELU activations that approximate Qss, a) and is trained using experi- replay. In the case of the bootstrapped DQN, all ensemble members learn from shared replay buffer with bootstrapped data sampling, where each member Qa= is separate MIP (no parameter sharing) that regressed towards separate target networks. We use Adam (Kingma & Ba, 2015) and update target networks periodically (Table 2).
32
2
[64, 64]
20
0.001
mask prob replay size
1.0
10000
steps per gradient step env steps per target update
1
4
Uses two networks Qo and Qa. where Q& is trained to maximise the extrinsic reward, while Qa is trained maximise the absolute TD-error of Qs (Simmons-Edle al., 2019). In contrast to TDU, the intrinsic reward is given as a point estimate the TD-error for a given transition, and thus cannot be interpreted measuring uncertainty such.
QEX
CTS Implements a count- based reward defined by i(s, a, H)) (N a, H) + 0101)-11/2 where H. is the history and ((s, H.) Eren (s.a)er is the number of times (s, a) has appeared in transition (s, a, r,),,s), s'). This intrinsic reward is added to the extrinsic reward to form augmented reward = r + fü used to train DQN agent (Bellemare et al., 2016).
Uses two auxiliary networks fo and fa that map a state into vectors x fo( a fs)s). H E R While is random parameter vector that is fixed throughout, 1 is trained to minimise mean squared error i(s) x -l|. This error simultaneously used as an intrinsic reward the augmented reward function f(x, a) = r(8, a) Bi(s) and is used to train DQN agent. Following
RND
Phtpps //gi /i thub. com cee/dee nd/bsui
te /bsse ines/jax/
dqn.
22

---

Under review as a conference paper at ICLR 2021
Table
grid searches for Bsuite. Best values in bold.
Algorithm
Hyper-parameter
Sweep
QEX
Intrinsic reward scale (5)
[10 3 10', 102, 10%}
CTS
Intrinsic reward scale (5)
100, 100,
RND
Intrinsic reward scale (5)
(10-2,5.10-1, 10,,
10 10 ,00)
x-dim (m
{10, 128]
Moving average decay (ax)
(0.9, 0.99, 0.999) (True,aalse)
Normalise intrinsic reward
BDQN
Prior scale (A)
{0,1,3,5, 10, 50, 100)
SU
Hidden size
(20,64)
Likelihood variance (3)
102) {10-8, ,0-1,,10-000 1000, 10 103}
20- 100 10
Prior variance (0)
NNS
Noise scale (3)
10 100, 102)
TDU
Prior scale (A)
{0,109.3 8 10
Intrinsic reward scale (3)
(10-3, 10-2 10 100 5 100, 10+)
Burda et al. (2018b), we normalise intrinsic rewards by an exponential moving average the mean and the standard deviation that are being updated with batch statistics (with decay a)..
Trains an ensemble = (Qp= H of DQNs (Osband et al., 2a). At the start of each episode, one DQN is randomly chosen from which greedy policy is derived. Data collected is placed in shared replay memory, and all ensemble members have some probability of training on any transition in the replay. Each ensemble member has its own target network. In addition, each DQN is augmented with random prior function fa. where i is fixed parameter vector that is randomly sampled at the start of training. Each DQN is defined by Qa + Afos, where À is a hyper-parameter regulating the scale of the prior. Note that the target network uses distinct prior function.
BDQN
SU Decomposes the DQN as Qa(s, = = w (s, a). The parameters 1 are trained to satisfy the Success Feature identity while w learned using Bayesian linear regression; at the start of each episode, new is sampled from the posterior p(w history) (Janz et al., 2019).*
NNS NoisyNets replace feed-forward layers W x: + by a noisy equivalent (W + E O e )æ (b ② e)), where @ is element-wise multiplication; c ~ (0,3,) and ei (0, are white noise of the same size W and b, respectively. The set (W, E, b, o) learnable parameters that trained on the normal TD-error, but with the noise vector re-sampled after every optimisation step. Following Fortunato et al. (2018), sample noise separately for the target and the online network.
TDU
We fix the number of explorers to 10 (half of the number of value functions in the ensemble). which roughly corresponds to randomly sampling between maximmiinn policy and an exploration policy. Our experiments can be replicated by running the TDU agent implemented in Algorithm in the Bsuite GitHub repository.'
D.2 TDU EXPERIMENTS
Effect of TDU Our main experiment sweeps over 3 to study the effect of increasing the TDU exploration bonus, with 3 e {0, 0.01, 0.3, 1, 3,; corresponds to default bootstrapped DQN. We find that 3 reflects the exploitation-exploratio trade-off: increasing leads better performance on exploration tasks (see main paper) but typically leads to worse performance on
*See 'https: //gi thub. wwt.:/ewmmmccccccteeeeetee/.... http:///aaaat//////a//at/////aaa bew.eeeeeeeeeeeeeeeeeeeeaaaaaaae nes jax.
23

---

Under review as a conference paper at ICLR 2021
tasks that do not require further exploration beyond é-greedy (Figure 6). In particular, we find that 3 > 0 prevents the agent from learning on Mountain Car, but otherwise retains performance on non-exploration tasks. Figure 7 provides an in-depth comparison per game.
Because a is a principled measure of concentration in the distribution p(ò s,a,r,s') 3 can be interpreted as specifying how much of the tail of the distribution the agent should care about. The higher we set 3, the greater the agent's 's sensitivity to the tail-end of its uncertainty estimate. Thus, there no reason in general believe that single should fit all environments, and recent advances in multi-polic, learning (Schaul et al., 2019; Zahavy et al., 2020; Puigdomënech Badia et al., 2020) suggests that promising avenue for further research is incorporate mechanisms that allow either 33 to dynamically adapt or the sampling probability over policies. To provide concrete evidence to that effect, we conduct an ablation study that uses bandit policy sampling below.
Effect of prior functions We study the inter-relationship between additive prior functions (Osband et al., 2019) and TDU. We sweep over À E [0, 1,3), where prior functions define value function estimates by Q* = Qø= + AP* for some random network pk Thus, À = O implies no prior function. We find general synergistic relationship; increasing À improves performance (both with and without TDU), and for given level of X. performance on exploration tasks improve for any / > 0. It should be noted that these effects do no materialise as clearly in our Atari settings, where we find no conclusive evidence to support À > 0 under TDU.
Ablation: exploration under non-TD signals To empirically support theoretical underpinnings of TDU (Proposition 2), we conduct an ablation study where a is re-defined as the standard deviation over value estimates:
K
(
Q Q
(53)
K
In contrast to TDU, this signal does not condition on the future and consequently is likely to suffer from greater bias. We apply this signal both as in intrinsic reward (QU), in TDU, and as an UCB-style exploration bonus (Q+UCB), where a is instead applied while acting by defining a policy by 7(-) arg max, Q(, a) 30 Q ;, a). Note that TDU cannot be applied in this way because the TDU exploration signal depends on and s'. We tune each baseline over the same set of 3 values 1) and report best results in Figure 6. We find that either alternative is strictly worse than TDU. They suffer a sigmificant drop in performance on exploration tasks, but are also less able to handle noise and reward scaling. Because the only difference between QU and TDU is that in TDU, conditions on the next state. Thus, there results are in direct support of Proposition 2 and demonstrates that Vo r] is likely to have less bias than Vp (Qo(s. as)...
as above (incidentally, these coincide
Ablation: bandit policy sampling Our main results indicate, unsurprisingly, that different envi- ronments require different emphasis exploration. To test this more concretely, in this experiment we replace uniform policy sampling with the UCBI I bandit algorithm. However, in contrast to that example, where UCB1 is used to take actions, here it is used to select a policy for the next episode. We treat each N + K value function as an "arm" and estimate its mean reward V x Ex [r]. where the expectation is with respect rewards r collected under policy n² (-) arg max, Q (..a) The mean reward is estimated as the running average
((k n(k)
1
(*())=
Σ Tx
(54)
where n(k) is the number of environment steps for which policy n² has been used and r; are the observed rewards under policy A Prior to an episode, we choose policy to act under according to: arg max ke=I,...,,N+. (n() + 7 log n2/n(k) where n is the total number of environment steps taken so far and 7/ is tlyper-parameter that we tune. As in the bandit example, this sampling strategy biases selection towards policies that currently collect higher reward, but balances sampling by a count-based exploration bonus that encourages the agent to eventually try all policies. This bandit mechanism is very simple as our purpose is to test whether some form of adaptive sampling can provide benefits; more sophisticated methods (e.g. Schaul al., 2019) can yield further gains.
24

---

Under review as a conference paper at ICLR 2021
bandit
minsst
calch
mo mountain car
cartpole
0.50
0.25
bandit noise
maisi noise
catch noise
mounlain, car naise
cartpole noise
0.75
0.50
0.25
bandit scale
mnist
catch mountain scale
cartpole scale
0.75
0.50
0.25
deep. stochastac
cartpole swingup
umbrella length
umbrella distract
0.75
0.50
0
8.00
1.0 + bandit
8 0.5
1.0 + bandit
discounting chain
memory
memory
8
0.75
0.0
0.50
0.01
0.5
0.25
0.8 01
1.0 + bandit
0.5
0.8. 0.0 0.5, 1.0 bandit
0 0.0.01 0.5
1.0 bandit
1.0 bandit
Figure 7: Bsuite per-task results. Results reported for different values of / with prior À = 3. We also report results under UCBI policy sampling ("bandit") for 3 = 1, A 3, 8.
We report full results in Figure 7; we use 3 = 1 and tune 1,.1, We report results the hyper-parameter that performed best overall, " = though differences with > are marginal. While TDU does not impact performance negatively in general, in the one case where it dous-MMuntain introouuuu a bandit to adapt exploration can largely recover performance. The bandit yields further gains in dense reward settings, such in Cartpole and Catch, with an outlying exception the bandit setting with scaled rewards.
E ATARI WITH R2D2
E.
BOOTSTRAPPED R2D2
We augment the R2D2 agent with an ensemble dueling action-value heads Q.. The behavior policy followed by the actors is e-greedy policy before, but where the greedy action is determined according to a single Q, for fixed length time (100 actor steps in all of our experiments), before Qi uniformly at random. The evaluation policy is also c-greedy with 0.001, where the Q-values are averaged only over the exploiter heads.
sampling
Each trajectory inserted into the replay buffer is associated with binary mask indicating which Q; will be trained from this data, ensuring that the same mask is used every time the trajectory is sampled. Priorities are computed in R2D2, except that TD-errors
averaged over all heads.
25

---

Under review as a conference paper at ICLR 2021
Instead of using reward clipping, R2D2 estimates transformed version of the state-action value function to make it easier to approximate for a neural network. One can define a transformed Bellman operator given any squashing function h R + R that is monotonically increasing and invertible. We use the function h b IR defined by
h(z) sign(=) (V[== +1|++11----
+22
(55)
(VIT=
+) -
4c(12 + +1+
-
h (2) sign(2)
(56)
2
for small. In order to compute the TD emrors accurately we need to account for the transformation,
8(0, s, a, s') - (Qo(s
- -r (
(57)
Similarly, evaluation time we need to apply h to the output of each head before averaging.
When making use of a prior we use the form Q* = Q + AP*, where pe is of the same architecture as the O network, but with the widths of all layers cut to reduce computational cost. Finally, instead of n-step returns we utilise Q(A) (Peng & Williams, 1994) was done in (Guez et al., 2020). In all variants we used the
listed in Table 4.
E.2 PRE-PROCESSING
We used the standard pre-process of the frames received from the Arcade Learning Environment See Table 5 for details.
E.3
SELECTION
In the distributed setting we have three TDU- specific hyper-parameters to tune namely: 3, N and the prior weight X. For our main results, we run each agent across 8 seeds for 20 billions steps. For ablations and hyper-parameter tuning, we ran agents across 3 seeds for 5 billion environment steps games: frostbite.gravitaar, hero, ms_pacman,
Table 5:
Atari pre-processing hyperparameters.
Max episode length
30 min
Num. action repeats Num. stacked frames
4
4
Zero discount on life loss Random noops range Sticky actions Frames max pooled
false
subset of 8
30
false
contezzum_rrevengee seaquest, ipacce_inaaers, venture. This subset presents quite bit of diversity including dense-reward games as well as three hard exploration games: gravitar, weteezum_reveeeeee
3 and 4
Grayscaled/RGB
Grayscaled Full
Action set
and venture. To minimise the computational cost, we started by setting À and N while maintaining 3 = 1. We employed a coarse grid of X E {0., 0.05, 0.1} and N E {2, 3, 5). Figure 8 summarises the results in terms of the mean Human Normalised Scores (HNS) across the set. We see that the performance depends on the type of games being evaluated. Specifically, hard exploration games achieve a significantly lower score. Performance does not significantly change with the number of explorers. The largest differences are observed for the exploration games when N = 5. We select best performing sets of hyper parameters for TDU with and without additive priors: (N = 2, = 0.1) and (N = 5, x = 0), respectively.
We evaluate the influence of the exploration bonus strength by fixing (N 5. A = 0) and choosing 3 E {0.1, 1., 2. Figure 9 summarises the results. The set of dense rewards is composed of the games in the ablation set that are considered hard exploration games. We observe that larger values of 3 help on exploration but affect performance on dense reward games. We plot jointly the performance in mean HNS acting when averaging the Q-values for both, the exploiter heads (solid lines) and the explorer heads (dotted lines). We can see that higher strengths for the exploration bonus (higher (9) renders the explorers "uninterested" in the extrinsic rewards, preventing them to converge to exploitative behaviours. This effect is less strong for the hard exploration games.
PPbliccy available //atttss////g thub. com /mwp/ eeeeeeeeeeeae /rw.//aaaaeeeeeeee leeam ig- Envi ronment.
26

---

Under review as a conference paper at ICLR 2021
ablation games
10
10
10
8
8
6
6
4
4
2
2
0
exploration games
2.0
2.0
2.0
1.5
1.5
1.0
1.0
1.0
0.O, N: 2
A: 0.0, N:
A: O.O, N:
0.5
0.5
0.5
À: 0.05, N: 2
A: 0.05, N:
d: 0.05, N:
A: 0.1, N:
A: 0.1, N: 3
0.1, N:
0.0
0.0
0.0
4 Environment steps
2
Environment steps
1e9
Environment steps
1e9
1e9
Figure 8: Ablation for prior scale, À and the number of explorers, N, on the distributed setting. We
fix 1. Refer the text for details on the ablation and exploration of games.
ablation games
dense reward games
exploration games
10
15.0
2.0
12.5
1.5
10.0
7.5
1.0
5.0
0.5
8: 0.1
2
2.5
exploit
8: 1.0
explore
8: 2.0
0.0
0.0
4 Environment steps
Environment steps
1e9
Environment steps
1e9
1e9
Figure 9: Ablation for the exploration bonus strength, 3, the distributed setting. We fix (N 5, A 0). We report the mean HNS for the ensemble of exploiter (solid lines) and the ensemble of explorers (dotted lines). All runs average over three seeds per game. Refer to the text for details on ablation and exploration set of games.
Figure 10 we show how this effect manifests itself on the performance on three games: gravitar, and hero. This finding also applies to the evaluation performed on our evaluation using all 57 games in the Atari suite, as shown below. We conjecture that controlling for the strength of the exploration bonus on a per game manner would significantly improve the results. This finding in line with observations made by (Puigdomènech Badia et al., 2020); combining TDU with adaptive policy sampling (Schaul et al., 2019) or online 2018 8; Zahavy et al., 2020) are exciting avenues for future research.
tuning (Xu et al.,
27

---

Under review as a conference paper at ICLR 2021
gravitar
space invaders
hero
40000
12000
60000
10000
50000
30000
8000
40000
20000
6000
30000
4000
20000
10000
0.1
2000
10000
exploit
8: 1.0
explore
8: 2.0
0
D
0
le9 0
2
Environment steps
10f
Environment steps
Environment steps
1s9
Figure 10: Ablation for the exploration bonus strength, 3, on the distributed setting. We fix (N
5, A 0). We report the score on three different games for the ensemble of exploiter (solid lines) and the ensemble of explorers (dotted lines). All runs are average over three seeds per game.
E.4 DETAILED RESULTS: MAIN EXPERIMENT
In this section we provide more detailed results from our main experiment in Section 5.2. We concen- trated our attention on the subset of games that are well-known pose challenging exploration prob- lems (Machado et al., 2018): mont revenge, pitfall, private_ee venture, gravitat tar, and tennis. s. We also add varied set of dense reward games.
solaris,
Figure 11 shows the performance for each game. We can see that TDU always performs on par or better than each of the baselines, leading to significant improvements data efficiency and final score in games such as monte coontezum_rrevee wuweereeeaeereeeee.eroe private_eyy venture, gravitar, and tennis. Gains in exploration games can substantial, and montezuma_revengee private eye, venture, and gravitar, TDU without prior functions achieves statistically significant improvements. TDU with prior functions achieve statistically significant improvements on monte wwwaa
pri vate_eye, and gravitar Beyond this, both methods improve the rate of convergence on seaquest and tennis s, and achieve higher final mean score. Overall, TDU yields benefits across both dense reward and exploration games, summarised in Figure 12. Note that R2D2's performance on dense reward games is deflated due to particularly low scores on space_invadee invaderss Our results in line with the original publication, where R2D2 does not show substantial improvements until after 35 Bn steps.
E.5 FULL ATARI SUITE
In this section we report the performance on all 57 games of the Atari suite. addition to the two configurations used to obtain the results presented in the main text (reported in Section 5.2), in this section we included a variant of each of them with lower exploration bonus strength of X = 0.1. In all figures refer these variants by adding L. (for lower X) the end of the name, e.g. TDU-R2D2-L. In Figure 13 we report a summary of the results terms of mean HNS and median HNS for the suite well mean HNS restricted to the hard exploration games only. We show the performance on each game in Figure 14. Reducing the value of B significantly improves the mean HNS without strongly degrading the performance exploration standpoint. The difference in performance in terms of mean HNS can be explained by looking few high scoring games, for instance: assault, asterix, demon at tack and gopher (see Figure 14). We can see that incorporating priors to TDU is not crucial for achieving high performance in the distributed setting.
the games that are challenging from an
28

---

Under review as a conference paper at ICLR 2021
seaquest
frostbite
ms pacmen
space invaders
1000000
50000
800000
100000
30000
600000
75000
40000
20000
400000
50000
20000
200000
25000
10000
8.0
0.0
1.0
1.5
0.5
1.0
0.5
1.0
2,0
0.0
0.5
2.0
gravitar
1e10
1e10
1610
montozuma mwvegg Jel0
15000
40000
2500
2000
30000
4000
10000
5000
1000
2000
10000
500
solaris
private
le10
tennis
1el0
15000
80000
20
TDU-R202
TDU-R2D2
R202
10000
5000
20000
8.0
1c10
1e10
1610
Figure Performance on each game in the main experiment in Section 5.2. Shading depicts standard deviation over 8 seeds.
ablation games
dense reward games
exploration games
8
1.5
6
10
4
1.0
TDU-R2D2-PRIOR TDU-R2D2
2
0.5
R2D2
B-R2D2
0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Environment steps 1e10
Environment steps 1e10
Environment steps
1e10
Figure 12: Performance across all games in the main experiment in Section 5.2. We report mean HNS over the full set of games used in the main experiment, dense reward games, and exploration games. Shading depicts standard deviation over seeds.
29

---

Under review as a conference paper at ICLR 2021
Table 4: R2D2 hyperparameters.
Ensemble size
10
Optimizer
Adam (Kingma & Ba, 2015)
Learning rate
0.0002
Adam epsilon
0.001
Adam betal
0.9
Adam beta2
0.999
Adam global clip norm
40
Discount
0.997
Batch size
64
Trace length
80
Replay period
40
Burn length
20
À for RL loss
0.97
R2D2 reward transformation
sign(x)
(v |-|
+1 + 0.001
Replay capacity (num of sequences)
le5
Replay priority exponent
0.9
Importance sampling exponent
0.6
Minimum sequences start replay
5000
Actor update period
100
Target
Q Q-network update period
400
Evaluation
0.001
mean HNS
median HNS
mean HNS exploration
10
1.50
30
8
1.25
20
6
1.00
TDU-R202-
4
0.75
TDU-R2D2-PRIOR-
TDU-R20Z
10
2
0.50
R2022
D. R2D22
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Environment steps 1e10
Environment steps 1e10
Environment steps 1e10
Figure 13:
Performance over the 57 atari games. We report mean and median HNS over the full suite, and mean HNS over the exploration games.
30

---

Under review as a conference paper at ICLR 2021
10000
5500
1000
4000
12000
2000
Esct best
bodo
Lveday
60000
2000
20000
1aly ziatox
40000
10000
30000
7.00
5500
12000
750
1000
80000
30000
Strt
Phomn
7.000
LEM00
3000
2000
3000
5000
20000
5000
TDU R2D2 FRIOR
TDU--230 P.1-2--
TDU-R200
TRU--202-1
B-R2D2
Figure 14: Results for each individual game. Shading depicts standard deviation over seeds.
31


Reviews:
[{"review_id": "eLVCx-cNs7", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe paper proposes a novel heuristic approach to estimate the uncertainty of the value function of an agent. Since this heuristic for estimating the uncertainty can be applied not only to tabular RL, but also when using function approximation, it is an interesting approach.\n\nStrong points:\nThe proposed heuristic can be used to estimate the uncertainty not only for tabular RL, but also when using function approximation, without relying on the ability of the function approximators to specify a value for the uncertainty.\n\nWeak points:\nThe investigated benchmarks are essentially deterministic and cover a very limited range of the spectrum of RL in general.\n\nRecommendation:\nThe paper is well written and clearly structured. It introduces a new approach that is likely to be beneficial in a relevant number of problems. I recommend to accept the paper.\n\nAdditional feedback with the aim to improve the paper:\n„However […] obtaining accurate uncertainty estimates is almost as challenging a problem.“ As challenging as what?\nIt remains unclear, what is meant by \"diverse and deep exploration\".\nAt (\\beta >> 0), please use a proper LaTeX command for >>.\nPlease do correct missing capital letters in the bibliography: e.g.  bayesian, q-\n\n\n-----------------\n(Nov 26.) After reading Review1 I lower my Confidence.\n(Nov 29.) Taking into account the other reviews, the authors' responses to these reviews and the discussion, I now think the paper is not quite ready for publication and lower the score to 5.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "UQ7ohw8s2kP", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a method for exploration in reinforcement learning by using the uncertainty over the value function as an intrinsic reward. It also offers an interesting theoretical analysis on the problem of estimating uncertainty over the value function. The paper is clearly written in general and has mentioned the related methods sufficiently. Moreover, the authors have compared their method with state-of-the-art models. In the experimental results section, the authors have shown that their model works well both in deterministic and stochastic environment. The noise in this stochastic environment, however, is very low (To be more precise the entropy of transition function is low). This is actually my main question/concern about the paper. In the beginning of section 3, the authors have mentioned that they \"fix\" the transition function in calculation of uncertainty over the value function. Does this mean that in that part, p(s'|a, s) is set to 1 for the most probable state and 0 for others? If this is the case, the method might not work well when the entropy of the transition function is high (e.g. the agent goes to one state 50% of the time, and to another 50% with an action), or in continuous state space environments where the actions are noisy. In the mentioned cases, sampling cases might actually work better because at least they consider those states in the future. I think it will improve the paper a lot if the authors add such environments to their analysis and discuss such problems.  \n\nUpdate: Thanks the authors for their response. Based on the other reviews and authors' response I decrease my score by 1 point.  ", "extra_scores": {}, "extra_text": {}}, {"review_id": "0ckDMF5mIeq", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe authors introduce the use of value function variance (conditioned on state transition) as auxiliary reward promoting exploration during training. The variance is estimated using the bootstrap DQN approach. The main difference with similar methods is that the value uncertainty is not used in a Thompson sampling scheme but it is instead use to provide exploration reward. \n\nRelevance:\nThe paper address a central problem in deep RL. \n\nOriginality:\nThe central idea is rather original and it elegantly combine ideas the value uncertainty estimation approach with the auxiliary exploration reward strategy. This new form of auxiliary reward is rather attractive as it automatically scales down during training as the model becomes more certain.\n\n\nScientific quality:\n- The new method is generally well motivated. However, while the author use a Bayesian terminology (e.g. prior, posterior), I am not convinced that the proposed bootstrap method for uncertainty estimation has a clear Bayesian interpretation as a form of approximate inference. Boostrap resampling can lead to proper Bayesian posteriors when the likelihood is used to weight the samples but this does not seem to be the case in this work. \n- The experiment section contain an interesting set of experiments and compare with several relevant baselines. \n-The paper is clear and very well written. However, I am not convinced by some of the claims. For example, the author claims that since reward uncertainty estimation is biased then networks cannot meaningfully generalize. While the claim can definitely be true, I do not think it follows from their premises. I would like to see the authors to expand this argument. \n\nPros:\n- Simple and elegant new method\n- Very good performance when compared with a large number of relevant baselines\n\nCons:\n- Some claims are not completely justified\n- It would have been informative to have a wider range of problems in the experiments section", "extra_scores": {}, "extra_text": {}}, {"review_id": "-ShCtRgNyfm", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes to use an intrinsic reward based on uncertainties calculated from temporal difference errors. The approach, called Temporal Difference Uncertainties (TDU), estimates the variance of td errors across multiple (bootstrapped) parameters, for a given state, action, next state and reward, where variability is due only to variance in parameters. The other addition is to learn a separate set of action-values that use this intrinsic reward, from the bootstrap set. Actions are then taken by randomly sampling an action-value function from the combined set. \n\nThe idea of using td uncertainties as an intrinsic reward is interesting, and should help avoid the fact that bootstrapping value functions alone likely provides insufficient exploration. However, the paper in its current form is not yet ready for publication for two main reasons. First, there are significant gaps in motivating and detailing the TDU technique. In sections 1 and 2, TDU is motivated as an exploration method deriving “an intrinsic reward from the agent’s uncertainty over the value function.”  In particular, it is heavily implied that TDU’s uncertainty estimate does not suffer the bias indicated by Lemma 1.  But it is not detailed how the quantity \\sigma(\\tau) estimates value function uncertainty, nor how it is unbiased. Why is it a better choice than, for example, directly using the bootstrapped set of action-values? There is some intuition provided, as well as an informal argument following from the distribution p(\\delta|\\tau) to uncertainty over value function parameters \\theta.  But this intuition and lack of formality is at odds with the formality highlighting that estimating value function uncertainty is hard.\n\nSecond, the empirical results appear to be obtained with 3 runs and do not provide significant evidence of improvements. Considering the apparent variance in all techniques, no meaningful conclusions may be drawn from comparison between the average of so few samples. The reported shading is also not explained, though I suspect it is standard errors. For only 3 samples, standard errors are not reliable, and in either case here are quite large. It would be better to run on few environments, and try to provide a stronger claim about the role of tdu. Even better would be to also highlight if results change significantly with changes to hyperparameters.   \n \nBelow, more detailed comments are given about the paper. \n\nIt would be useful to better discuss the use of Bootstrapped DQN (BDQN), and why this approach improves on BDQN. In Janz et al. 2019, there is a thoughtful and detailed analysis of one particular failing of BDQN methods (cf. section 5.3) including with a specific demonstrative environment (the binary tree MDP with randomized actions.) While this TDU paper does make a compelling argument that TDU addresses certain challenges of BDQN methods, TDU’s performance on the binary tree MDP (or one sufficiently similar) is not included.  This is a nontrivial omission.  If TDU succeeds on the environment, then a significant challenge is overcome. And if TDU does not succeed, then it is still worthy of publication, just with some discussion.\n\nThe theoretical contribution seems like it could be interesting, but it is not fully clear. Is this a statement about all methods that try to estimate some form of value uncertainty? Or those based on PSRL? Lemma 1 is summarized as “the harder it is to generalise, the more likely we are to observe a bias” in value function estimation, which is helpful, but warrants further detail.  A worked, demonstrative example may be edifying here.\n\nIt would be useful to discuss more why estimating TDUs is easy (as per the title of Section 3). It looks like the quantity in Equation 4 relies on p(theta), which was stated to be difficult to maintain. A bootstrapped distribution is used to get, as described in Section 4, but Section 3 did not make it clear to me why estimating sigma(tau) was straightforward. There are two additional statements here that could use clarification:\n1. Why does using the standard deviation put this bonus on the same scale as the reward?\n2. The paper says: “We compare TDU to (a) a version where σ is defined as standard deviation over Q and (b) where σ(Q) is used as an upper confidence bound in the policy, instead of as an intrinsic reward (Figure 2).”  These choices are very interesting, but should be explained in more detail.  Especially why their results indicate that “the key to TDU’s success is that the intrinsic reward relies on a distribution of TD-errors to control for environment uncertainty.“\n\nMinor comments:\n1. “neural networks, which are prone to overfitting and tend to generalise through interpolation (e.g. Li et al., 2020; Liu et al., 2020; Belkin et al., 2019)”  This is not an accurate representation of the cited results.  Those papers do not argue that neural networks are prone to overfitting.  Indeed, they argue the opposite: neural networks do not seem to overfit in the overparameterized limit, despite their tendency to interpolate the training set.  That is, generalization is maintained, where high generalization is characterized as per convention: low prediction risk w.r.t. an independently sampled test set.  While this is a significant mischaracterization, it does not appear to be critical to the paper, so we choose not to include it in the rejection justification.\n\n2. The colored bar chart to render parameter sweeps (Fig 2 left, center left, and center right) is a bit distracting. The use of color does not seem to be helping here. \n\n3. The related work section describes and cites some of the same work as the introduction, and is hence some of it is a bit redundant.  There is no need to duplicate that part of the survey in this section.\n\n4. There is an incomplete sentence: “While this can be effective in sparse reward settings, ... it can also lead to arbitrarily bad as the exploration (see analysis in Osband et al., 2019).”\n\n5. In appendix section D.1, there appears to be a missing citation: “Finally, instead of n-step returns we utilize Peng’s Q(λ) as was done in (Value-driven Hindsight Modelling: citation needed).”\n\n6. This work looks at computing variances directly, and using that variance for uncertainty, rather than using the bootstrapped action-values. This citation seems relevant: \"Context-Dependent Upper-Confidence Bounds for Directed Exploration\", Kumaraswamy et al., 2018.  \n\n------- Update\nThe response and update was a huge improvement. I now much better understand the goals, and the authors added some content that I think made the paper stronger and clearer. One outstanding issue is still that I do not understand why E_M[Q_M^pi] is the gold standard, and why bias is measured relative to that quantity. I explain this more below, but first mention some of the additions I really liked. For an upcoming paper, if this issue is remedied, I think this will be a good paper. \n\nThank you for introducing Proposition 2 and the explanation about bias beforehand. This very much clarifies the motivation for using TD errors. The result itself highlights that using TDU will have a lower bias to the true expected TD error if the bias for the action-values for (s,a) and (s’,a’) are both in the same direction (both positive or both negative). Otherwise, however, it looks like the bias of TDU is strictly worse. One issue though with this result is that the magnitudes of these quantities could be different. The comparison between bias for TDU and the bias for Q seem a bit like comparing apples and oranges, and I would in fact expect the TD error to be smaller in magnitude and so naturally have a smaller bias. How much is due to this and how much to relative bias reductions? I suspect there is a real bias reduction here, but clarifying this would help.\n\nFor the variance result, it seems better to directly report 47, and the discuss ramifications, rather than writing that they all need to be approximately equal. By the way, it is too bad that the result is a bit weaker for the variance, which is precisely the quantity you care about for defining your rewards. But nonetheless this formalization is helpful and provides solid insight.\n\nI like that the empirical work was improved, including adding some comments about significance. I also very much appreciate the ablation, where you use the variance directly from the bootstrapped action-values as an intrinsic reward. My only concern here is that the magnitude of rewards might be quite different, since the TD error should be smaller than the action-values themselves. This might mean different beta are needed.\n\nHowever, I remain unsure about the importance of this bias that TDU mitigates. You state: “Our analysis shows that biased estimates arise because uncertainty estimates require an integration over unknown future state visitations.“ It remains a strong statement that uncertainty estimates require integration over unknown future states. As one example where this does not seem to be true is the Kumaraswamy paper you have cited. They show that if you use LSTD to get estimates of the action-values for a fixed policy, then you can get an estimate of the variance of the parameters. Maybe this setting assumes too much, and so it does not invalidate your result. But, I do believe a more clear argument is needed in this section for this result, as I expand on below.\n\n“Methods that rely on posterior sampling under function approximators assume that the induced distribution, p(Qθ ), is an accurate estimate of the agent’s uncertainty over its value function, p(Qπ ), so that sampling Qθ ∼ p(Qθ ) is approximately equivalent to sampling from Qπ ∼ p(Qπ ). ” This is a strong statement. I do not see why it is true. Are you suggesting that the agent must have the true Qpi? Is it not enough to use uncertainty estimates (epistemic uncertainty) for a function approximator? This result seems to show: if we want to mimic uncertainty estimates over true action-values for different models, then this is not possible under function approximation. But, that is maybe reasonable. Instead, shouldn’t we ask: how can we mimic uncertainty over approximate action-values for different models? (i.e., relative to our function class)\n\nAdditionally, you call E_theta[Q_theta] an estimator and discuss it’s bias. But, isn’t that quantity not random? I presume E_theta[Q_theta] is the expectation, and the difference to E_M[Q_pi] is the bias. But, then what is the estimator that is biased?\n\nMinor comments:\n\n“However, in non-tabular settings that involve function approximators, obtaining accurate uncertainty estimates is almost as challenging as the exploration problem itself. “ What does this mean?\n“state-action transitions ” what is that? I think you mean just transition, since you condition on the whole thing\nIn the proof of Lemma 1, the Variance would remove the expectation over r term. Your result still holds, but the proof itself looks like it should be separated into the two cases.\n“While Proposition 1 states that we cannot remove this bias unless we are willing to maintain a full posterior p(θ), ” It is not clear how this result shows this. What if I maintained a full Gaussian posterior over theta? Would that solve the problem? What is a partial posterior?\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submitted paper contains interesting theoretical insights into common approaches for exploration and proposes a new way for deriving intrinsic rewards for exploration which is evaluated in several benchmark environments. While all reviewers appreciate these aspects, there are concerns about whether the paper is ready for publication. In particular, the authors’ response did not clarify all open questions and concerns (although the authors already improved the paper a lot by updating the submitted paper according to recommendations/questions of the reviewers). After discussions and author feedback, 3 knowledgable reviewers suggest (weak) rejection of the paper and 1 reviewer suggested acceptance of the paper. Considering this, I recommend to reject the paper but I would like to encourage the authors to consider the comments of the reviewers to revise their paper accordingly, as I expect the paper to then turn into a strong and impactful one.
Decision: Reject