ADDQ: Adaptive distributional double Q-learning
Authors: Leif Döring
Benedikt Wille
Maximilian Birr
Mihail Bîrsan
Martin Slowik
Venue: ICML 2025 poster (2025)
Keywords: Reinforcement learning
Q-learning
overestimation bias
distributional RL
Atari
MuJoCo
Primary area: reinforcement_learning
TL;DR: A novel algorithm is introduced that uses distributional RL to locally adjust the overestimation bias in Q-learning.

Abstract: Bias problems in the estimation of Q-values are a well-known obstacle that slows down convergence of Q-learning and actor-critic methods. One of the reasons of the success of modern RL algorithms is partially a direct or indirect overestimation reduction mechanism. We introduce an easy to implement method built on top of distributional reinforcement learning (DRL) algorithms to deal with the  overestimation in a locally adaptive way. Our framework ADDQ is simple to implement, existing DRL implementations can be improved with a few lines of code. We provide theoretical backup and experimental results in tabular, Atari, and MuJoCo environments, comparisons with state-of-the-art methods, and a proof of convergence in the tabular case.

ADDQ: Adaptive Distributional Double Q-Learning
Leif Döring o
Benedikt Wille! Maximilian Birr! Mihail Birsan? 2 Martin Slowik !!
Abstract
soft actor-critic (SAC) of (Haarnoja et al., 2018). Motivated by statistical approaches to the estimation of the expecta- tion of maxima of random variables the concept of double Q-learning (DQL) was introduced in (van Hasselt, 2010). Instead of using one set of random variables two inddpen- dent sets are used. One is used to detect the maximal index, the other to evaluate the random variable corresponding to the maximal index. For Q-learning this translates keeping track of two copies of the Q-matrix that are alternated in order to detect the best action and evaluate the correspond- ing Q-value, DQL and its actor-critic variants reduce the overestimation (see for instance Figure 2 in (Fujimoto et al., 2018)) and sometimes even underestimate Q-values. This, for example, can be seen in simple chain MDP (Example 6.7 in (Sutton & Barto, 2018) and also (Lan et al., 2020) for the underestimation effect in the same example). (Fujimoto et al., 2018) argue that overestimation should be addressed particularly in state-action regions with high uncertainty. Indirectly, this is taken into account by ensemble methods such as Maxmin QL (Lan et al., 2020). These methods use ensembles of more than two Q-estimators. Different ensem- ble estimators take the minimum, full ensemble averages (Anschel al., 2017), or random ensemble averages (Chen et al., 2021). A related line of research uses uncertainty- based RI., also with the goal of reducing overestimation, see for instance (Wu et al., 2021), (Ghasemipour et al., 2022),
Bias problems in the estimation of Q-values are a well-known obstacle that slows down conver- gence of Q-learning and actor-critic methods. One of the reasons of the success of modern RL algorithms is partially a direct or indirect overesti- mation reduction mechanism. We propose an easy to implement method built on top of distributional reinforcement learning (DRL) algorithms to deal with the overestimation in a locally adaptive way. Our framework is simple to implement, existing distributional algorithms can be improved with few lines of code. We provide theoretical evi- dence and use double Q-learning show how to include locally adaptive overestimation control in existing algorithms. Experiments are provided for tabular, Atari, and MuloCo environments.
1. Introduction
A fundamental building block of many modern reinforce- ment learning (RL) algorithms is Watkins' Q-learning (QL) (Watkins& & Dayan, 1992). In each round the agent observes new reward signal and updates the currently estimated state-action function by combining the new reward signal with the best currently estimated action in the next step. Unfortunately, the update rule involves a maximum and maxima suffer both from overestimation bias and function approximation uncertainty. Thus, estimated Q values are initially way too large. Although convergence of Q-learning and its variants for tabular cases can be proved rigorously, the convergence can often be seen only after millions of iterations. In the context of Q-learning we refer to the sem- inal paper (Thrun & Schwartz, 1993). The overestimation effect is harmful not only for simple QL and variants with function approximation such as DQN (Mnih et al., 2015), but also for critic estimation in actor-critic methods such as
There is no rule whether QL, DQL, or any ensemble variant works well for a given environment. Algorithms sometimes perform well and sometimes fail. This article proposes novel approach. We propose take QL and (at least) one other method and try control if the QL update should be replaced or mixed with another underestimating method. The control must be locally adaptive, and the need to manage the bias depends on the local uncertainty (aleatoric and epistemic randomness, function approximation). For an approach similar in spirit to ours, see (Dorka al., 2021).
We show theoretically how distributional RL helps the agent identify the need for overestimation control.
'Instituee of Mathematics, University of Mannheim, Ger- many 'Department of Mathematics and Computer Science, Freie Universität Berlin, Germany. Correspondence to: Leif Döring <docring @ uni mannheim.de>.
As a test case, we combine QL and DQL using a local weighting that we call ADDQ.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Convergence of ADDQ is proved, experiments are per- formed on tabular, Atari, and MuloCo environments.

---

ADDQ: Adaptive Distributional Double Q-Learning
2. Q -learnnng and the overestimation problem
the estimator is positively biased. Thus, the update targets + 7 max Qe a') can be seen overestimating the true Bellman optimality operator at each step. The conse- quences of overestimation are less obvious than it seems at first sight. Shifting Q-values the same amount globally has no effect, neither for Q-based exploration purposes nor for best action selection. It is the local difference in overestima- tion that must be avoided to not confuse the agent. Thus, is crucial understand the root causes of overestimation to then mitigate by taking alternative updates to QL if needed.
2.1. Tabular Q-learning
Let us fix a (discrete) Markov decision model (S,A, R, p). where S is a finite sate-space, A a finite space of allowed actions, R the reward space, and p a transition kernel de- scribing the distribution of the reward and the new state s' when action is played in state Given a time-stationary policy T, Markov kernel on S x A, there is a Markov reward process (St, Ac, Re) with transitions
There is little quantitative understanding of the overestima- tion; for some rough bounds see (van Hasselt, 20.1). We used tools from probability theory to compute estimation bounds for simple ex explanatory example. The example
(R, r,, S++1 = A++1 = d'IS, = A, a) = = s')((r, s': :.s00 s.a).
The goal of the agent in reinforcement learning is to use roll- outs of the MDP to find policy that maximizes Q (s) ET 7 R. = s, A. = a), the expected discounted reward. The discounting factor 7 E (0, 1) is fixed. In the discrete setting with S and A finite it is well-known that optimal stationary policies exist and can be found as greedy policy obtained by the unique solution matrix Q" to T Q. The non-linear operator (T))) a) r(s,a) a) + -W's
90
82
:
ki NN of) actions
0
l/2 N( 0z) actions
{s'} 8, a max E Q(s, a') is called Bellman's 's optimality operator. Bellman's 's optimality operator is a max-norm contraction on the S x A matri- ces. Using Banach's 's fixed point theorem, the solution can in principle be found by iteratively applying T to some initial matrix Qo. The drawback of this approach is the need to know the operator T*, thus having knowledge about the transitions p. Using standard stochastic approximation algorithms the fixed point Q" can be approximated by
Figure 1. Two-sided bandit MDP, start in so. gray boxes terminal
intriguing. it is simple but hard to learn even more so if one side is replaced by a chain of decisions. Each side gives a reward (for simplicity 0) followed by a Gaussian reward from one of k actions. QL and DQL can both fail badly (each on one side) for the same parameter configuration. If μı > 0 > P2, then the optimal action in so is "left", If a2 (and/or kz) is large compared to σ (and/or ky) then the overestimated Q-values of QL will confuse the agent and lead him to believe that "right" is optimal. Similarly, underestimating can make the agent believe "down" is op- timal. Our approach of learning locally to use QL or DQL (or another variant) can mitigate that problem by learning to use QL for one side and DQL for the other. The method is motivated by two theoretical results, lower bound on over- estimation (Proposition 2.1) and computation with DRL to connect estimated sample variances and overestimation (Proposition 2.2). If step-sizes are chosen in the common way as oz (s a) = 1 Tt)(()) with (t, the number of visits at (s. a) up time t, then results sums and maxima of Gaussian random variables can be used to prove lower bound on the expected overestimation of the true value ypp. Proposition 2.1. If the left side has been explored Nk1 times and the exploration was sufficienily exploratory (see Theorem A.2), then the Q Q-estimate at (so. "left") has bias at (log(k)) and analogously at (50, "right"). JN
(ss, a) - - ( a) + a(r + 7 ((dlaa)))
a'
called Q-learning (QL). The state-action pairs can be cho- sen synchronously or asynchronously using rollouts. Typi- cally, to update at (s, a) one-step sample s',r is obtained from p(- 8, a) and the step-sizes are assumed to satisfy the Robbins-Monro conditions. The exploration (choices of (s, to be updated) can be on-policy (using the Q- estimates) or off-policy (using a behavior policy). The only requirement is infinite visits for all state-action pairs. The recursively defined matrix-sequence (Q.) was proved to converge in the tabular setting, see e.g. (Tsitsiklis, 1994).
2.2. The overestimation problem
Even though QL converges to Q* for the number of updates going to infinity, the convergence is very slow. One of the known sources is the so-called overestimation problem of QL. The algorithm does not provide unbiased estimates of as) Instead, the estimates Qe(s, a) tend to overes- timate Q* a). A statistical explanation is based on the simple fact that the point estimator max [X_..., X, is not an unbiased estimator of max max(T[(X (B[(1)) [[,x,] but
least
(2g
The lower bound quantifies the idea that uncertainty forces overestimation and the bias only decreases slowly over time. A proof is given in Appendix A. Since the estimate is rela- tively tight one gets a feeling for how many reward samples
2

---

ADDQ: Adaptive Distributional Double Q-Learning
are needed to get sufficiently precise estimates of the Q- values so the agent makes the right decision.
etc. It was shown in (Bellemare et al., 2017: 2023) that the return distribution function is the unique solution to "f" = T" where 7 : PP())SXA + P(R)SxA is the distributional Bellman operator defined as (TT n)(s = End' E''R'' D #Tyss ( r;;8 a) with bootstrap function (,, = r + y2 and push-forward of measures 5# [B) := (B)) In essence, sample based dynamic programming can also be carried out in a distributional sense replacing the classical Bellman operator by its analogue in the distributional sense. Distributional QL proceeds similarly to classical expectation QI.:
There has been considerable interest for the past years to understand the sources of uncertainty in RL. While many sources of uncertainty exist, they are often categorized as either aleatoric or epistemic. Aleatoric uncertainty is model given and cannot be improved by more data or learning. In RL this is uncertainty implied by random variables govern- ing rewards and transitions. Epistemic uncertainty refers to the uncertainty that could potentially be reduced using more data and better algorithms (including better function approx- imation). Epistemic uncertainty in RL. is induced by all random variables to run the learning procedure (exploration, replay buffer, etc.) and function approximation in deep RL. Keeping in mind the different sources of uncertainty is useful in order to identify algorithmic potential for improve- ment but also theoretical limitations. It is also important to realize that aleatoric and epistemic randomness strongly in- fluence each other. If a reward has large variance (aleatoric uncertainty) then the estimation with samples creates more epistemic uncertainty. For estimating expectations, this is due to the central limit theorem.
n|s, a) + - ()na))(ss a) + albrntt(ss',a (a)),,
with a' argmax, Q(s',a', where Q(s', a') are the expectations of the probability measures 17(5', a'). In or- der to work algorithmically with DRL parametrizations F of measures need to be used. Distributional learning algorithms in practice then work similarly to deep learn- ing algorithms, alternating Bellman operators and function class projection, see Algorithm 1. There are two simple
Algorithm Distributional Q-learning update step Require: Proxy 17 for 17" and pair (s, a) to be updated Determine step-size a
In deep RL one of the major sources of epistemic uncer- tainty is function approximation. As in (Thrun & Schwartz, 1993) we could add to our analysis independent error-noise modeling the function approximation. If the error noise is assumed Gaussian then our results readily extend, by adding additional noise-variance to our results. Since the model- ing assumption as independent noise is rather special we restrain from studying the effect of function approximation on epistemic uncertainty. Instead, we will now show how to use additional information from distributional QL to deal with overestimation in a local way.
Sample reward/next state (r,
# Compute target
a" < argmax, Ez-n(s', .a) [Z]
n. +- br, .a))
# Project target back onto support
i) < (f))
# Move n1s, a) towards the target, for tabular RL e.g.
n(s,a) + (1 - a))((, a) + an
parametrization that have been used frequently. The categor- ical parametrization (fixing number of atoms with variable weights at fixed locations) and the quantile parametriza- tion (fixing number of atoms with fixed weights but vari- able locations). For the categorical parametrization a set of m evenly spaced locations 0₃ < .... < On needs to be fixed, the categorical measures are then defined by Fc.m = { E.= proo. Pp: 2 O, E.= Pt 1}. That is, measures in Fc.m are parametrized by an mddim probability vector with weights for the m fixed atoms. In contrast, the quantile parametrization Fq.m- = Em 1 de, 0 E IR fixes the weights to 1 with variable atom locations.
2.3. Tabular distributional Q-learning
To make this article as self-contained as possible we give minimal overview on DRL. For concise treatment we refer to the recent book (Bellemare et al., 2023). Given a Markov decision model and a stationary policy n, (Rowland et al., 2018) define the return distribution function as
17" (s) = pa Σ R'RR
Blso = A0
for B E ((B). The expectation over the measure 17" the classical state-action value function Q In con- trast ordinary RL, the target in DRL is to learn return distributions instead of only return expectations. There have been a lot of theoretical articles on DRL (Bellemare et al., 2017: Dabney et al., 2018; Rowland et al., 2018; Lyle et al., 2019; Bellemare et al., 2023; Rowland et al., 2023b;a) establishing distributional Bellman operators, con- tractivity, convergence proofs of dynamic programming,
2.4. Overestimation mitigation using distributional RL
We follow insight from Proposition 2.1 that large uncer- tainty, aleatoric (large a) as well as epistemic (small N additional a if function approximation is modeled as Gaus- sian error), implies large overestimation of Q-values. While we skip function approximation for theoretical considera- tions we are as precise as possible in the simplest tabular
3

---

ADDQ: Adaptive Distributional Double Q-Learning
settings. The estimate from Proposition 2.1 suggests to re- place QL-updates in (8,a) if uncertainty is large (compared to other actions). Unfortunately, in standard QL the agent has no direct access to such information in order to adjust the update rule at (x, a). This is where our idea comes into play. DRL gives the agent exactly the needed information using distribution insight into the return estimate 7// (),(s, a). crucial to note that DRL learns random measures as ((s, a) is a probability measure that depends the random samples used in the updates so it has an expectation and variance that are both random in terms of the random samples. The situation becomes tricky as we are going to take variances of the variances. To avoid confusion an analogy to statistics is used. We speak of sample averages M (resp. sample variances 5²) of vnss, a) and expectation E (resp. variance V) for the integrals against the random- ness induced by the probability space behind all random variables.
update a mixture). Since "large" has no absolute meaning in RL we will compare variances among all actions in and reduce according to the relative sample variance.
Exploration and overestimation control with ensembles and double Q-learning: Known algorithms that directly try to better estimate the Q-values require to set up a par- ticular algorithmic architecture. Most use an ensemble of Q-copies which are then combined by taking minima (Lan et al., 2020), averages (Peer et al., 2021), averages with random choices (Chen et al., 2021). Ensemble methods are promising in theory (assuming independent ensembles) but more problematic for deep RL. as storage problems force ensembles to be parametrized by the same neural network. The optimal number of copies (a hyperparameter) varies for different environments, some choices work well, others fail.
Our approach is different. We suggest to use QL when it works well (small sample variance) and another algorithm where QL fails (large sample variance). We could combine QL with ensemble methods but for this article decided to combine QL with DQL a bit in the spirit of weighted DQL (Zhang et al., 2017) but with completely different weights we compare to weighted DQL in Appendix C.2. For DQL (van Hasselt, 2010) two copies QA and QB are stored. The update mechanism is similar to QL where the matrix to be updated is chosen randomly in every step. The main differ- ence is the target used, matrices Q4 and QB are flipped:
We now use the bandit MDP from above to explain why the DRL agent has access to uncertainty estimates dur- ing the learning process. To allow concrete computations with distributions, we use a particularly simple QL update mechanism (the one also used for estimates in (van Hasselt, 2011)). First explore all actions NN times, then propagate to (so, "left"). In fact, this is nothing but distributional QL with cyclic exploration and target-matrix trick (Mnih et al., 2015) as we explain in Appendix A. The obtained estimate of ry" (so, "left") will be denoted by fss,, "left").
QA/B(s, + (1 + a((r a (QBIAAA)
Proposition 2.2. The sample variance of f((0o "left"). analogousty for "right". after Nk1 steps is of distributed. The expectation is of the variance is N-1'
20 N-IXN-1
with =" = max, QA/B(S', (s)) Here and in the follow- ing we use QA/B to allow either the choice of QA or Q Double Q-learning reduces the overestimation strongly but sometimes leads to severe underestimation.
A proof is given in Appendix A. It is surprising that the sample variance distribution can be identified explicitly chi-squared, unlike the sample expectations (maxima of independent Gaussians). This is a consequence of the well- known fact in statistics that sample variances of Gaussians are independent of sample expectations. Thus, if return esti- mates are Gaussian the max-operation of QL (with respect to sample averages) is only delicate for sample expectations, not for sample variances. We emphasize that in contrast to QL the agent in distributional QL does have access to the x² -isttibbuted sample variance by computing sums of the atoms! Hence, the agent can make use of an unbiased estimate for the aleatoric uncertainty o² which is conflicted by epistemic uncertainty that decreases with N.
The use of sample variance of estimated return distributions is not new to RL. For bandits the simplest example is the UCB exploration bonus for unknown variances that uses this for exploration. In the context of exploration in RL uncertainty dependent exploration has been applied using distributional RI. (see for instance (Mavrin et al., 2019), (Moerland et al., 2018)). The use of sample variances in distributional RL to locally mitigate the overestimation is new to the best of our knowledge. In order to not mix up effects we stick to the standard exploration choices.
N
3. ADDQ: Tabular setting
Implications from of our theoeretical considerations: We propose the following locally adaptive overestimation mitigation method. (i) Use distributional QL. (ii) At every update compute the sample variance of the current return estimate ne (s, a). (iii) If the sample variance is large replace the QI. update by another update (e.g. DQL or an ensemble
Based the theoretical insight we will now introduce concrete method. We use DQL-updates as an alternative to QL-updates when the agent expects QL-updates to be harmful (large estimated uncertainty by means of sample variance). The weighted apL-approach we suggest is read- ily implemented into existing DRL. implementations.
4

---

ADDQ: Adaptive Distributional Double Q-Learning
3.1. Weighted DQL: From SARSA-trick to ADDQ
instance gradient steps to minimize KL loss) are straight forward. The algorithm is seen to be combination of distri-
To derive the algorithm let us recall the SARSA convergence proof of (Singh et al., 2000) that was also used to prove convergence for DQL (van Hasselt, 2010) and variants such as clipped Q-learning (Fujimoto et al., 2018) or Maxmin (Lan et al., 2020). The idea is to add a clever O, adding and subtracting what is missing to the QL update, thus, writing the algorithm as QL with a bias. If the bias can be proved to disappear, a comparison QL implies convergence to Q*:
Algorithm 2 ADDQ update step
Require: Proxies 1/* 11 for v)", pair (s, a) to be updated
Determine step-size
Sample reward/next state (r,
Randomly choose Update(A) or Update(B)
if Update(A) then
# Compute target with locally adapted weight
Qleamingg update
a" < argmax, Be (e',a) ..) [Z]
QA/B(s,a) + (1 (1-0)Q (s, (s,a) + tarr + (
Determine weight B3 E [0. 1] based on Vold Vold
(1-3)n (s', (,, + A (s',a")
= -s,a8(ssa)
n.2 + br.
+ aa(1QB/A (2 ( 2)),
# Project target back onto support 1 + (
with =x argmax (s, Taking this point of view there are plenty of possibilities to modify DQL to achieve more less over//underestimation. As example, choosing the negative bias-terms bA/B a min (5),""s"""""""""" ////// 2²),0}
# Move v)(s, a) towards the target, for tabular RL e.g. 7 a) t (1 - (s, + arj
end if
if Update(B) then
yields so-called clipped Q-learning introduced as part of TD3 in (Fujimoto et al., 2018). As motivated in Section 2.4 we suggest a locally adaptive overestimation control. The main insight is as follows. One can locally interpolate between QL and DQL by multiplying bias terms with local adaptive weights:
Proceed analogously with A and B exchanged end if
butional QL and distributional DQL. Keeping 3 constant to is distributional QI., constant 0 distributional DQL. The key is to chose /3 dependent on the uncertainty that drives the skewed QL overestimation for different actions. Extend- ing arguments from the literature, notably the convergence proof of (Rowland et al., 2018) for categorical Q-learning with stochastic approximation target upate and the SARSA trick of (Singh et al., 2000), we prove convergence of Algo- rithm 2 for categorical measure parametrizations:
BA/B (s/ (s,a) = (A/B((s a) (s,
new
Replacing bias terms b by b generalizes the update. The aggressive choice B = results in QL updates (overesti- mation), 3 = 0 results in DQL updates (tendency of under- estimation). Choices of 3 suggested in the present article are motivated by the propositions of Sections 2.2 and 2.4. If lot of uncertainty is present, the algorithm uses large 3, otherwise small B. The aggressive choices are not nec- essarily the best, in our experiments below softer choices were more effective. Since overestimation is a priori not problematic for the learning process (if all estimates are equally overestimated the best action does not change, only skewed overestimation slows down the learning) we suggest choice of 3 that takes into account the local structure, normalizing variances over possible actions.
Theorem 3.1. Given some initial return distribution func- tions ngē ni supported within [0,, Om]. If
rewards are bounded in [Rminy Rmaz) and it holds Rmin Rmaz] 1-
C [0,, 0m);
step-sizes fulfill the Robbins- Monroo conditions and ny or n are updated randomly,
the sequences (3x) (5 )EEN only depend on the past and fulfill lim 18 138 almost surely,
3.2. New algorithm: locally adaptive distributional double Q-learning
then the induced Q-values converge almost surely towards Q If additionally the MDP has a unique optimal policy n², then (nε) ), (nf2) converge almost surely in l2 to some ne E Fc.m and the greedy policy with respect to ne: is n."
Following the ideas above we introduce ADDQ, integrat- ing locally adaptive overestimation mitigation in DQL. The pseudo-code given in Algorithm 2 extends distributional RL pseudo-code to include the double algorithm and adap- tive weights. For the tabular target update we follow the prasure--mixtue approach of (Rowland et al., 2018). Sec- tion 8. Changes to the code for other target updates (for
According to Theorem 3.1 symmetric sequences 3 BB that can depend on past distributions 1/ , yield conver- gence. A particularly simple choice compares the deviations in A/B locally as a local measure for uncertainty.
5

---

ADDQ: Adaptive Distributional Double Q- Q-Learning
10.91 Actan Deart
State Jal
SEd44 EASA Dore
C40
Saar: Plone
0.004 0.3c
1200 1330 2000 2000 M00t
1500 2300 1500 Xide
500 1500 2000 2000 1500
300 1550
500 5000 1000 2005
Figure 2. Grid world. First column: Biases summed over all state-action pairs. Other columns highlight the relation of sample variance (bottom) and the effect on Q-value (top) estimation. For more experiments and comparisons Maxmin, EBQL, REDQ see Appendix C.
An exemplary choice of adaptive 3: As motivated earlier QI suffers from overestimation in the presence of uncer- tainty (function approximation, aleatoric randomness, epis- temic randomness) which is reflected in the sample variance (or other measures of the spread of the distribution) of the discrete (random) distributions f)c A/B As uniform overesti- mation is not particularly troubling (e.g. adding a constant to all Q-values does not harm all) the learning process is slowed down by differences in sample variances for allowed actions. There many other possibilities to choose 33 but we decided to fix this example for all our experiments. For a finite atomic measures v= = Σi= i piòa, define the sam- ple mean (v) = 1 n a.P; and the sample variance n
3.3. A grid world example
To show the advantages of ADDQ we present grid world that highlights, in a more complicated and more realistic way, the main effects of the bandit MDP. For more details, see Appendix C. In particular, in Appendix C.3 we compare ADDQ to other algorithms for overestimation reduction.
Deep RL experiments presented below use essentially deterministic environments with uncertainty mainly from function ap- proximations. We thus provide a grid world with complicated stochasticity that, depending on parameters, is hard for QL and DQL. The high stochasticity region with low rewards confuses the QL agent. The agent strongly overestimates subopti- mal Q-values that lead to the gray area, in the gray area Q-values are overesti- mated for actions that stay in the gray area. Hence, all E-greedy exploration mecha- nisms spend much time in the gray area. On the other hand, DQL is motivated by estimators of iid random variables and underestimates strongly if action-values for different actions are unevenly distributed. Thus, the DQL agent gets confused by the local deviations caused by the fake goal and the stochastic region. What results in overestimation for QL. results in underestimation for DQL. In contrast, ADDQ locally combines update-rules of QL and DQL reduce the estimation biases lot. In Appendix C we show ex- perimentally that the choice of thresholds in , is relatively harmless, more or less aggressive updates still perform well. In contrast, constant 3 and the non-distributional choice from (Zhang et al., 2017) with c = 10 have larger biases.
F
2
S
4
5
6
7
8
10
11
12
G
14
15
(²(v) = - 1 pi(a. - (v))? Now define
Figure 3. Start S. goal in G, fake goal F, high stochasticity and low reward area in gray
($
(nf ( (s) + (2
2
$2 1 Σ S2,0 and a) = aEA
53 = A
S
According to our computations in the two-sided bandit model, evenly distributed relative sample variances (i.e. all values around 1) correspond to balanced overestimation ef- fects. Otherwise, overestimation unbalanced. We define locally adaptive weights for the next update (8, a):
0.75
S a) < 0.75
B =
0.5
(x, a) E [0.75, 1.25]
(1)
0.25
(s, a) > 1.25
For algorithmic simplicity one could also use squared devia- tions to the median instead of the mean as the median can be red off directly for measures in the Fc.m and Fq.m. The choice combines and DQ rather softly, more aggressive choices reduce the length of the interval and increase (resp. decrease) towards 3 = and 3 = O. In practice, (tabu- lar, all Atari, all MuJoCo) the choice worked well without any tuning. The thresholds in the definition of 3 can be seen as hyperparameters to the algorithm. We leave the development of adaptive thresholds for future research.
Plots the figure above show a few key insights, more in Appendix C. First, the estimation bias of ADDQ is much smaller than those of QL and DQL. Most importantly in the complicated states 1, 4, 6, 7. The reason ADDQ better estimates the Q-values is the adaptive choice to prefer QL or DQL, depending on (relatively) large variances.
6

---

ADDQ: Adaptive Distributional Double Q-Lcarning
3.4. ADDQ adaptation for distributional DQN
and X arginin Qu , ,0 ="".!;
Our DRL based local adaptive overestimation mitigation can be integrated into existing code for DRL with few extra lines. In the following we describe the integration into C51 (Bellemare et al., 2017). We run experiments on Atari environments from the Arcade Learning Environment (Bellemare et al., 2013) using the Gymmasium API (Towers et al., 2023). Algorithms are few line modifications based on the RL Baselines3 Zoo (Raffin, 2020) training framework, without any further tuning of hyperparameters.
ADDQ (us): The ADDQ target uses
TA/B B (5', 20 + (1 Bi (5', (s),"")
2²",
where =" argmax, QAArD ( ( The locally adaptive weights 33 may depend on entire state-action return distribu- tions. For the experiments we used the choice from Equation (1) based on the online networks A B
Results for two Atari environments and a RLiable compar- ison (Agarwal et al., 2021) are presented in Figure 4 and more extensively in Appendix E. The experiments show that ADDQ is more stable than QL. and DQL (it never fails completely) and achieves higher scores in different metrics.
The C51 algorithm obtained its name from using cate- gorical representation of return distributions with m = 51 atoms. The weights of the parametrization are parametrized via feedforward neural networks following the DQN archi- tecture (Mnih et al., 2015). The state 8 serves as input and the last layer outputs m 51 logits for each action fol- lowed by softmax return probability weights. We write (s a) > (i a; w0,, where wt comprises the on- line networks weights. We add a bar v to denote delayed target network which is kept constant and is overwritten from 1 every e.g. 10000 steps with the parameters from the online network. The corresponding expectation is de- noted by (s, a) = Σ (s,, a; w), Given a transition (s, a, r, s') the projected target is
3.5. ADDQ adaptation for QRDQN
Modifications and results for quantile DRL (Dabney et al., 2018) are similar to the categorical setting. The setup is explained in Appendix D; for quick view two experiments and a RLiable plot for probability of improvements can be found in Figure 4. More experimental results are provided in Appendix E. ADDQ is more stable (it never fails completely) and achieves higher scores in different metrics.
3.6. ADDQ adaptation for quantile SAC
m
1 = TTe (br. #n (5', aa)
prdo,3
Compared to Atari environments it is known that overestima- tion in MuloCo environments is more severe. Using the dou- ble estimator in critic estimation is not enough, the clipping trick of TD3 (Fujimoto et al., 2018) greatly improves perfor- mance. Recall that, in the formulation of biased Q-learning of Section 3.1, clipping uses bias min ( - Q A/B .0} instead of QB/A - QA/B. Thus, using our distributional overestimation identification to combine QL and DQL does not hint towards an algorithm competitive with SAC/TD3 or algorithms with more refined overestimation control such as REDQ (Chen et al., 2021) or TQC (Kuznetsov et al., 2020). For completeness of the article we still consider the ADDQ effect with standard single and double estimator. We used the base implementations from SAC with quantile regression. With a single critic estimator (we call this QRSAC), with double estimator, clipped double estimator (QB-SAC in the terminology of (Kuznetsov et al., 2020)), and ADDQ estimator (ADORSAC). Experiments are shown in Figure 5 and more extensively in Appendix E.
where a" argmaxx Q=(s'a') a'). Gradient descent on the weights with respect to some loss (here: cross-entropy) is used to move the distribution (s, a) towards the target distribution fj. As for the tabular algorithm variants with overestimation reduction intervene in the target definition. We keep track of two independently initialized online net- works denoted by w wB and a pair of respective target networks @- ". For each gradient step simulate vector of random variables with the same size as the batch size with each element determining which of the two esti- mators is being updated based on the respective transition with the same position in the batch. Accordingly, we use twice the batch size for these methods, so that on average per gradient step, the same number of transitions is used for each estimator, compared to the single-estimaton case. We can now describe how to modify the targets for given transition (s, a, r, s'). With the placeholder I' in
to study
A/B = #LA/B)
As expected ADDQ improves QRSAC and double QRSAC but is not competitive with clipping. We leave for future work to experiment distributional RL based overestimation identification for REDQ and TQC.
only the place holder is modified for different algorithms: Double C51: Set TA/B = (8,,") with x* argmax, Qaain (s',a).
'TD3 [Fujimoto et al., 2018)] introduced clipping in an actor- critic setting, where the action is given by the actor. In our C51 adaptation, we select the greedy action based on the target network.
Clipped C51: Inspired by (Fujimoto et al., 2018). Set TA/B nox (s',²*) ) with z" = argmax, Q (8', a')
7

---

ADDQ: Adaptive Distributional Double Q- Q-Learning
BattleZone NoFromeskprrt
50003
ADDO (19]
G51
400000
25403
DOUBLE
CLIP
10s Meevarr
20003
220003
DOU DOUBLE
5003
ADCO (Mg)
CM
5
15
20
13
20
2.5
Timestops (1e()
Timesteps (1:66)
PXC-1
BettieZono Prrniiokoo/
300000
ADDO (US)
10000
QRDIN
200000
GROON
CLI GRION
Rowar
TMt (owwrrd
AigeridanX
Alguriton'
880000
20003
ADDO JAC
CLI ORDON
100000
ADD0 PM)
DOUBLE GRDON
30000
10000
4070
ORTON
10
10
15
20
Timesteos (1e8)
Timeslipa (1u6)
Figure 4. Our method ADDQ (blue) compared to distributional DQN (orange), with double estimator (green) and clipped double estimator (red). First row with categorical, second row quantile parametrization. Learning curves given for two environments, more in Appendix E. We used 10 seeds. RLiable probability of improvement plots are for all 10 environments, more metrics in Appendix E.
Humanadd-v
HarCChodihho
10020
15002
ADGRSAC
CRSAC
1973
140032
15000
CLIP GRSAC
DOUSLE GRSAC
12000
Algeritie
Alpontin
10000
ADORSAC
GUPCREAC
Total
4003
8000
ADORSAC
DOUBLE GRSAC
3000
2003
ADORRAC
GRSAC
0.4 2.6
Timestepe
Figure 5. For completeness: Learning curves for two MuloCo environments and RLiable probability of improvement 5 environments. Adapting locally (bluc, us) the double critic estimator (green) and direct estimator (orange) cannot (by far) reach performance of the clipping estimator (red). Nonetheless, ADDQ improves distributional direct and double critic estimators with almost no change to the code. Runs are averaged on 10 seeds, more details can be found in the Appendix E.
4. Summary, limitations, and future work
While ADDQ improves QL and DQL in different settings there is future work to be done. (i) It is clear that our proba- bilistic calculations can be extended. It is quite likely that results from Gaussian processes can be used for computa- tions in more general settings. (ii) The exemplary choice of 3 can be improved. It would be interesting to replace the hy- perparameter thresholds by some adaptive learnable choice. (iii) The MuJoCo simulation study was only included for completeness, it would have been very surprising if local adaptation of simple and double critic estimates could im- prove the clipped critic estimate (or even better algorithms such as REDQ or TQC). It is interesting future research to include local overestimation mitigation into REDQ (make the chosen ensemble number depend locally on sample vari- ances) or TQC (make the number of truncated atoms depend locally on sample variances). (iv) Use sample variances to perform updates of target networks after non-constant steps.
Built on theoretical insight for bandit MDP we suggest to use sample variances in distributional RL to mitigate the novel
overestimation of QL. Our approach does not estimation procedure for Q-values but instead combines known estimators and tries to use the better one. Using DRI, the agent in state-action pair (s, a) has access to next- state information that predicts the overestimation of QL- updates and accordingly prevers QL- or an alternative. The approach can be incorporated in different estimation meth- ods (e.g. (random) ensemble methods, truncation methods). For the present article we decided to improve DQL, leading to our algorithm ADDQ. The algorithm has the expected feature that in contrast to DQ/DQL it does not fail com- pletely on some environments. Probability of improvement and normalized scores using the RLiable library show clear improvement of ADDQ to underlying deep DQ/DQL.
8

---

ADDQ: Adaptive Distributional Double Q-Lcarning
Code
Learning- Volume 70, ICML'17, pp. 449-458. JMLR.org. 2017.
The code used in our experiments can be found on GitHub: https: githb.. com/ Ho ADDQ. git.
Bellemare, M. G., Dabney, W., and Rowland, M. Dis- tributional Reinforcement Learning. MIT Press, 2023. http: /wwww wwwstiiiuiionnaa--o.....oi
Acknowledgement
The authors acknowledge support by the state of Baden- Württemberg through bwHPC and the German Research Foundation (DFG) through grant INST 35/1597-1 FUGG.
Bertsekas, D. P. and Tsitsiklis, J. N. Neuro-dynamic pro- gramming.. volume Optimization and neural compu- tation series. Athena Scientific, 1996. ISBN 1886529108.
Impact statement
Castro, P. S., Moitra, S., Gelada, C., Kumar, S., and Belle- mare, M. G. Dopamine: A Research Framework for Deep Reinforcement Learning. Preprint available on urXiv:/812.0611 2018. URL abs/ 06110.
This paper presents work whose goal is advance the field of machine learning, in particular reinforcement learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Chen, X., Wang. C., Zhou, Z., and Ross, K. Randomized ensembled double q-learning: Learning fast without a model. Preprint available on wrXiv22101.0588, 2021. URL http: puttt://arxiie www.rriii....r..iooooo.oe abs 2211 05982.
References
Adler, R. J. and Taylor, J. E. Random fields and geometry. Springer Monographs in Mathematics. Springer, New York, 2007. ISBN ----888--8881--88
Dabney, W., Rowland, M., Bellemare, M. G., and Munos, R. Distributional reinforcement learning with quantile regression. In Proceedings of the Thirty-Scoond AAAI Conference on Artificial Intelligence and Thirlieth Inno- vative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium Educational Advances in Artificial Intelligence, LAAI' 18. AAAI Press, 2018. ISBN 978-1-57735-800
Agarwal, R., Schwarzer, M., Castro, S., Courville, C.,, and Bellemare, M. Deep reinforcement learning at the edge of the statistical precipice. In Ranzato, M., Beygelz- imer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 19304-29322 Curran Associates, Inc., 2021. URL. https::tpp....ccc.tpc ptttpp:://rroceed:: http://pcoeeeeeeeeeeeeee neurriiipppinnnniiopop neurips. cc /cc/ppee_filleeeppprrr/////////
Dorka, N., Welschehold, T., Boedecker, J., and Bur- gard, W. Adaptively calibrated critic estimates for deep reinforcement learning. IEEE Robotics and Automation Letters, 8:624-631, 2021. URL https:
0blleccllccl45555577777722222223 pdf.
Anschel, O., Baram, N., and Shimkin, N. Averaged-DQN:
Variance reduction and stabilization for deep reinforce- ment learning. In Precup, D. and Tch, Y. W. (eds.), Pro- ceedings of the 34th International Conference on Ma- chine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 176-185. PMLR, 06-11 Aug 2017. URL StRhttps:: httptttpp://pooceeiinnno http///preeeeennccceeeeeece mlr, mwwrrpreee press/ v70 v70/anschellaa. html.
/ / 244527082.
Fernique, X. Regularité des trajectoires des fonctions aléatoires gaussiennes. In École d' d'Ééé de Probubilités de Saint-Flour IV-1974, volume Vol. 480 of Lecture Notes in Math., 1-96. Springer, Berlin-New York, 1975.
Badia, A., Piot, B., Kapturowski, S., Sprechmann, P., Vitvit- skyi, A., Guo, D., and Blundell, C. Agent57: Outper- forming the atari human benchmark, 03 2020. URL http:://arat
Fujimoto, S., Hoof, H., and Meger, D. Address- ing function approximation error in actor-critic methods. Preprint available on arXiv: 182. 2018. URL http: http//xxivvvv.... wtw.//rgg/bbbbssaooo wtt.i//.orrr/bba//...... 09477.
orw//ogg//........ abs////3..00.... 13350.
Bellemare, M. G., Naddaf, Y., Veness, J., and Bowling, M.
Ghasemipour, K., Gu, S. S., and Nachum, O. Why so pes- simistic? estimating uncertainties for offline rl through ensembles, and why their independence matters. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, Red Hook, NY, USA, 2022. Curran Associates Inc ISBN 9781713871088.
The arcade learning environment: an evaluation platform for general agents. J. Artif. Int. Res., 47(1):253-279 may 2013. ISSN 1076-9757.
Bellemare, M. G., Dabney, W., and Munos, R. distribu- tional perspective on reinforcement learning. In Proceed- ings of the 34th International Conference on Machine

---

ADDQ: Adaptive Distributional Double Q-Learning
Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S. Soft actor-critic: Off- Off-policy maximum entropy deep reinforce- ment learning with stochastic actor. In International conference on machine learning, pp. 1861-1870. PMLR, 2018.
Raffin, A. RI baselines3 zoo. https: http://tttuubb.ccoo DLR-RM/=1-basellneese
2020.
Raffin, A., Hill, A., Gleave, A., Kanervisto, A., Ernestus, M., and Dormann, N. Stable-baselines3: Reliable rein- forcement learning implementations. Journal of Machine Learning Research, 22(268):1-8, 2021. URL http: 13m4..
Kuznetsov, A., Shvechikov, P., Grishin, A., and Vetrov, D. Controlling overestimation bias with truncated mixture of continuous distributional quantile critics. In Proceed- ings of the 37th International Conference on Machine Learning, ICML'20. JorR. 2020.
papers //jmrr. www.oorrggpppp...oeeee
Rowland, M., Bellemare, M. G., Dabney, W., Munos, R., and Teh, Y. W. An analysis of categorical distri- butional reinforcement learning. In Storkey, A. and Perez-Cruz, F. (eds.), Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learn- ing Research, pp. 29-37. PMLR, 09-11 Apr 2018. URL http::://ppooceeeeii www..press/v.... rowland1 8a html.
Lan, Q. Pan, Y., Fyshe. A., and White, M. Maxmin q- learning: Controlling the estimation bias of q-learning. In 8th International Conference on Learning Repre- sentations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https: //openreview.. net. forum? wotrrrmmiddBggguSee 1d=Bkg
Lyle, C., Bellemare, M. G., and Castro, P. S. A comparative analysis of expected and distribu- tional reinforcement learning. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01): 4504-4511, Jul. 2019. doi: 10.1609/aamivv33001.. 33014504. URL.https:// aaai org/ index. http///A//aaaiiieeevveee
Rowland, M., Munos, R., Azar, M. G., Tang, Y., Ostrovski, G., Harutyunyan, A., Tuyls, K., Bellemare, M. G., and Dabney, W. An analysis of quantile lemporal-differenne learning. Preprint available on arXiv:2301.044400 042230000044, 2023a. URL http:htpp//. / arxiv. orgg abs/////////
2301 abs//3C1
04462.
Rowland, M., Tang, Y., Lyle, C., Munos, R., Bellemare, M. G., and Dabney, W. The statistical benefits of quan- tile lemporal-difference -iffferenee learning for value estimation. In Proceedings of the 40th International Conference on Ma- chine Learning, ICML'23, JMLR.org, 2023b.
Mavrin, B., Yao, H., Kong, I.., Wu, K., and Yu, Y. Distributional reinforcement learning for effi- cient exploration. In Chaudhuri, K. and Salakhutdi- nov, R. (eds.), ICML, volume 97 of Proceedings of Machine Learning Research, pp. 4424 4434. PMLR, 2019. URL http: / / /dblp...... uni cuni-triercom del.dde/ddde/// db/ conf 1 cml / cml 201 9. html #MavrinYKWY* 9.
Singh. S., Jaakkola, T., Littmann M., and Szepesvári, C. Con- vergence results for single-step on-policy reinforcement- learning algorithms. Machine Learning, 38(3):287-300 2000. doi: 10. 100022///11000679935553
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Ve- ness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg, S., and Hassabis, D. Human-level control through deep reinforcement learning. Nature, 518 (7540):529-533, 2015. doi: 10. 10.1038/nature 14236 URL https: / /ww.i//o.oo/////// /r / 038 naturel 14236. 4236.
Sudakov, V. N. Gaussian random processes, and measures of solid angles in Hilbert space. Dokl. Akad. Nauk SSSR, 197:43-45, 1971. ISSN 0002-3264.
Sudakov, V. N. Geometric problems of the theory of infinite- dimensional probability distributions. Trudy Mat. Inst. Steklov, 141:191, 1976. ISSN 0371-9685.
14236.
Sutton, R. S. and Barto, A. G. Reinforcement Learn- ing: An Introduction. The MIT Press, second edition, 2018. URL http: www.mpeeeeeeeeeeee eeeeeeeeeeess..eeeee . book/the-book- bonk-ondk22d.. html.
Moerland, T., Broekens, J., and Jonker, C. The potential of the return distribution for exploration in rl, 06 2018. URL
http://arxiv.. ort.:/orrraaaa hoog/abbs abs 18066110111111 04242.
Peer, O., Tessler, C., Merlis, N., and Meir, R. Ensemble bootstrapping for q-learning. In International Con- ference on Machine Learning, 2021. URL https: //api. wwwanticscholaalte.. org Cor//orp::ID: 232076148.
Thrun, S. and Schwartz, A. Issues in using function approximation for reinforcement learning. In Mozer, M.. Smolensky, P., Touretzky, D., Elman, J., and Weigend, A. (eds.), Proceedings of the 1993 Connectionist Models Summer School, pp. 255-263, Lawrence Erlbaum, 1993. URL http: /tl:::/www.... ri. cmu www.//u...uuuuuccc.mmm.e padd//uuuuapeee ccduuuuuufless////_/eeddeeeeeeee htt//thrun__ebastiiin 1993 199t__thr_n____ sebastian__993_1.ppp
Quan, J. and Ostrovski, G. DQN Zoo: Reference imple- mentations of based agents, 2020. URL http:
//github. cww/ ceoom//eemiid///eee deepmind/ddn_nae zdnoooo
10

---

ADDQ: Adaptive Distributional Double Q-Learning
Todorov, E., Erez, T., and Tassa, Y. Mujoco: A physies engine for model-basee control. In 20/2 IEEE/RS Inter- national Conference Intelligent Robots and Systems, 5026-5033 2012. doi: 10.1 109/RROOOO... 2012.6386109.
Zhang, Z., Pan, Z., and Kochenderfer, M. J. Weighted double q-learning. In Proceedings of the Twenry-Sinn International Joint Conference Artificial Intelligence, IJCAI-17, PP. 3455-3461, 2017. doi: 10.24963/ijcai. 2017/483. URL https: htt.///i..ooooooooo//o /4963/ 3jcai.2017/44
Towers, M., Temry, J. K., Kwiatkowski, A., Balis, J. U., Cola, G. d., Deleu, T., Goulão, M., Kallinteris, A., KG, A., Krimmel, M., Perez- Vicentee R., Pierré, A., Schulhoff, S., Tai, J. J., Shen, T. J., and Younis, O. G. Gymna- sium, March 2023. URL https:///entt record/ 8127025.
org/
Tsitsiklis, J. N. Asynchronous stochastic approximation and q-learning- Machine Learning, 16(3):185-202, 1994. doi: 10. 10.10023/A11022699155541 URL https::/dde org/10 1tt...1110222A111022222222222000
van Handel, R. Probabiltiy in High Dimensions. Princeton University, lecture notes, 2016.
van Hasselt, H. Double q-learning. In Lafferty, J., Williams, C., Shawe-Taylor, J., Zemel, R., and Culotta, A. (eds.), Advances in Neural Information Process- ing Systems, volume 23. Curran Associates, Inc., 2010. URL
oo ccc/ppee_ffleee/ppprr//000//111 1LLcBBFccc001122554822233338812 pdf.
van Hasselt, H., Guez, A., and Silver, D. Deep reinforcement learning with double q-learning- Preprint available arXiv:1509.06461. 2015. URL http: /attpv///xxi...o/// org/ abs/ 1509. 06461. cite Comment: AAAI 2016.
1xiiv:10090066 011.006461100
van Hasselt, H. P. Insights in Reinforcement Learn- ing: formal analysis and empirical evaluation of temporal-differncce learning algorithms. PhD thesis, Universiteit Utrecht, January 2011.
URL
http:://oompagess cwi aari.nn//hassel papers/Insighte. htw.:ggtte_ii_eeeeereereeeeete Learning Hado__an
van Htwpeaaa_a___aassee..ppooopo
Watkins, J. C. H. and Dayan, P. Q-learning. Machine Learning, 8(3):279-292, May 1992. ISSN 1573-0565. doi: 10. 1007//099800992299 URL htthhttss///oi.... 10. 1007 /F0099268..
Wu, Y., Zhai, S., Srivastava, N., Susskind, M., Zhang, J., Salakhutdinov, R., and Goh, H. Uncertainty weighted actor-critic for offline reinforcement learning. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th In- ternational Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 11328. PMLR, 18-24 Jul 2021. URL https: /// proceedi ngs mlr. press vv33 www1///w222 9/wu21 html.

---

ADDQ: Adaptive Distributional Double Q-Lcarning
A. Theoretical backup from probability theory
Theoretical backup for all known overestimation reduction algorithms is rather weak, the update rule of Q-learning makes precise computations very difficult. As we discuss below, the stochastic approximation rule requires computations with sums of random variables which is not well compatible with computations of maxima of random variables. Justifications for overestimation reduction algorithms are typically based on qualitative arguments for the estimation bias of expectations [[maxx[Xi, Xx) }} of maxima of independent random variables even though random variables appearing in Q-learning maxima are clearly not independent. We will give explicit estimates using probabilistic insights for sums and maxima of independent random variables.
We should make very clear that there are different factors to the overestimation problem that are captured in the algorithmic approach of ADDQ. To provide some rigorous theoretical evidence, we focus in this section on the tabular setting without function approximation error. We refer the reader the seminal article (Thrun & Schwartz, 1993) for some simplified computations on the overestimation effect caused by approximation errors.
A.1. A lower bound computation for the overestimation bias in an episodic bandit MDP (Proof of Proposition 2.1)
$0
$2
kj actions
0
l/2 actions
The two-sided bandit MDP from the main text can be analyzed side by side. Without loss of generality we thus study the overestimation of the left-side which is essentially the bandit MDP that appeared quite a bit in the literature on overestimation of Q-learning (see (van Hasselt, 2011), Example 6.7 of (Sutton Barto, 2018), or (Lan et al., 2020)).
Before stating our results on the overestimation bias we state technical lemma that is based on the Sudakov-Fernique inequality, see (Sudakov, 1971; 1976; Fernique, 1975), which is comparison inequality for Gaussian processes.
Lemma A.1. Let k E N and suppose (X)))ENNEE by are iid ((, Further, let myy..., Tk N such that n1 + ..... + ns I kn and set y == max SK 1/nn, + 1/nn 2/nl. Then,
E
max
x
E
max
1
Σ xj
S 22 lnk.
(2)
Isisk
ISisk n2
j=l
j=l
In particular, if. additionally, 1/n, + 1/n 2 f/n all i E fl,..., k} with i + i' then
E
max
X
< E
max Isisk
X
(3)
ISisk
Tl
nu
j=1
Proof. Given M1....,, n E N with ni + nk 1 kn, set Y n Σラ X and Z n, Σう Xj for any
i. E {1,...,,k) k). Clearly, Y = (Y1 "rl,...,y' yk) and = (7) 7%) are Gaussian vectors with E[ = TE Z for all
i E [1,1 [l,...,k) k) and
F (rri'' yd = 2/n and
//. = E (z' 2²)
1/14. + 1/ne
for all i, {1...., (.....,k) k} with i # V. Thus, (2) is immediate consequence of Adler & Taylor, 2007, Theorem 2.2.5, Eq. (2.2.11). If, in addition, 1/n: + 1/nz 2 2 for all i i i' then T. S 1 and (3) follows from Adler & Taylor, 2007, Theorem 2.2.5, Eq. (2.2.12).
We are now in a position to give a lower bound on the overestimation bias for all exploration policies under the typical viiiitss -step-size schedule. This extends the overestimation analysis (van Hasselt, 2011) which was based on a simple synchronous exploration mechanism. The step-size schedule is crucial for our probabilistic analysis as turns the analysis in a computation with sums and maxima of independent random variables. The sum structure consequence of the
12

---

ADDQ: Adaptive Distributional Double Q-Learning
simple fact that 2e := E a solves the stochastic approximation recursion žt+1 (1 0z) + ayut, 20 0, with Og E.I. Here is formal lower bound of the overestimation bias in the episodic bandit MDP. As mentioned above only consider exploration of the left-side of the bandit MDP.
Theorem A.2. Suppose Qu is initialized as the zero matrix and step-sizes are chosen as a4(s,a) = (ty' with (t,)(t) the
number of updates of (s,, o.). If rewards are N Nu, disttribi, then every sufficient exploratory exploration rule leads overestimation bias at least
o <Vog(()
E[QN "left")] - (so, "left" 2
?
n log(22
VN
By sufficient exploratory we mean that (.(
2 for all actions a, d' with na = Ts. (t).
(
N
In simple words, the expected overestimation in n episodes Q-learning on the left-side of the bandit MDP is at least of the order " log(k) Higher variance and more actions obviously lead to stronger overestimation.
V
Proof. In contrast to (van Hasselt, 2011) we do not assume synchronous exploration all actions each episode. Instead, we give a comparison argument that allows to reduce sufficiently exploratory exploration to simple cyclic exploration. The approach is motivated by the target network (here: target matrix) trick from DQN (Mnih et al., 2015). With target networks the update works follows:
Q4+1(8,0) - (1 ax)Qu(s, + + max Qa(s',
where Q is kept constant for a fixed number of steps and then updated from the current Q-matrix. Although the target network was introduced DQN to reduce overfitting in function approximation, it also reduces the overestimation of Q-values. We use the latter effect locally in this proof to construct lower bound. The target matrix kept constant (0 matrix) so until the last update. We show that (i) this target matrix trick with cyclic exploration yields lower bound for the overestimation bias of standard Q-learning with sufficient exploratory exploration strategy and (ii) allows for computations using elements of probability theory. In what follows we denote by X the reward obtained when playing chosing for the äth time. By assumption all (XF1) are iid.
Step 1: In the first step we show that using cyclic exploration (playing one action after the other) for N rounds (Nk steps in total) followed by one update at (so, "left") minimizes the overestimation of Q-learning estimators Qeye,tar (sg, "left") that explore each action most N times. For the claim we compare arbitrary Q-learning with the cyclic variant. Recalling the Q-learning update (with arbitrary exploration rule) and the step-size schedule shows that
Tha (1)
Qe(s1;a)=
Σ
X ~N(nt,,t
(ta((t)
1=1
Since sq is explored once per episode the step-size schedule of regular Q-learning yields
Nk
QNk(Sp, "left") =
max Q1(s),
Nk
for the Nth episode. We next show that (NQ "left"))
> E E eqecctar (so, "left")).
Denoting n1(() Tsy (1) and
13

---

ADDQ: Adaptive Distributional Double Q-Learning
using Lemma A.1 obtain
1
(s0, "left") E
Σ 7 max {Qe(s1, Q((1,
Nk:
Nk
R2(()
(x(()
1
B
max
Σ
x
Nk
12
T
(t)
jml
j=1
Nk
NN
N
2
B
max
X
Σ
x
}
Nk
N
N
1=1
E max
X
Σ
x5
}
BEQryettor (so. "left")].
Step 2: We analyze the overestimation bias for the Q-learing with target matrix trick after Nk episodes. To deduce the claim we use fact the expectation of the maximum of independent N(u, (",,,") ddistrbbbte random variables:
11 +
o log( S (X X&M] < μ + V20 v (lg(())
log(2)
The incquality can for instance be found in (van Handel, 2016). According to the step-size schedule the update as follows. If N nk, i.e. in cyclic exploration every action played n times, then Qeyc.tar NNk (s1, a) t Σi X for independent
N o²) o(p,o")-ddsstiibe ddistribuue reward samples. Thus, QN)($1, -..y QNK((1, are iid and N(s, Nv disstributed. The final update after N episodes is to set
Qeyc,tar (51, "left") 7 max(QN az), QN ax)) (d) 7 max x (Z1, ..., Z
for Zi...., Z iid (H, N The claim follows from the lower bound on the expectation of maxima of independent Gaussians.
The computations give a number of quantitative insights. First, it becomes very clear why explicit computations for Q-learning are complicated. The stochastic approximation update is closely related sums (exactly equal to sums for #visits step-sizes, while the update target involves maximum. Unfortunately, sums and maxima of random variables do not get along well. We thus performed computations for Gaussian reward distributions for which sums Gaussian again. Maxima of Gaussian random variables (processes) are well-studied field in Mathematics and estimates can be derived.
Finally, the computations show how variances influence the overestimation problem. Stochastic rewards with high variance are more problematic than rewards with small variance. In the next section we study distribution RL in the same simple problem.
A.2. On the use of variance in local overestimation control via distributional RL (Proof of Proposition 2.2)
Our computations for the bandit MDP above suggest uncertainty at next states (aleatoric uncertainty of rewards, epistemic uncertainty through small N) lead to larger overestimation. Thus, algorithms mitigating the overestimation problem locally at (s, a) must somehow use uncertainty at next states s'. In the following proposition we analyze the distributional Q-learning update scheme (compare Section of (Rowland et al., 2018))
a) (1 - (1-a)((s, a) - a #b., a")),
with a² = argmax, Q(s',a') where Q(s', aa) are the (random) sample means of the estimated return distributions 17(s,, a'). The bootstrap function is by, (2) = r + 72 and f = = (B)) denotes the push-forward of measures. Recall from the main text that distributional QL learns random measures, 17(s,, a) itself is probability measure that depends on the random samples used in the updates. As a probability measure r7(s, a) has an expectation and a variance that are both random in terms of the random samples. The situation becomes bit tricky as we are going to take variances of the variances.
14

---

ADDQ: Adaptive Distributional Double Q-Learning
To avoid confusion we use an analogy statistics and speak of (random) sample averages M (resp. sample variances S of v(s, a) and expectation E (resp. variance V) for the integrals against the true randomness induced by the probability space behind all appearing random variables.
Motivated by the previous section we only study eyclic exploration with "target measure", i.c. all actions in are explored N times before bootstrapping the estimates to 8p- Using the standard #visits -step-size schedule allows us to earry out fairly explicit computations using tools from probability theory. Most importantly we can derive the exact distribution for sample variance of 17( "left"), the state-action pair at risk for overestimation. The insight obtained from the computation motivates our ADDQ algorithm.
Proposition A.3. Consider the bandit MDP introduced above with N ((, o²) reward distributions and k actions. Denote by ifryc,tar (50: "left") the return distribution of distributional Q-learning with cyclic exploration, step-size schedule as(s, a) To.. and "target distribution". More precisely, all arms are N times explored before the first and only update
at (51, "left"). It then follows that
o²
(froeee tar (sn. "left"))
~ N 1-1 XN-1
where X denotes the chi-squared distribution with n degrees of freedom.
interesting note that while there is a simple distributional expression for the sample variance there no simple expression for the distribution of the sample mean max N independent Gaussians.
N X .... 3o Ei= xx*) which is the maximum of
Proof. For the proof we need to spell-out the distributional Q-learning update and then use basic results from statistic for
Let us first understand the distributional update at the last step. Similar to scalar stochastic approximation schemes, the x+1 step-size schedule also gives the distributional estimator
neye,tar ($1,0)=
1
Σ 6x?
(4)
for the pre-terminal state 31 after N explorations action a. To see why write The := 1/2 Ei oxp to get
Mh+1 Σ 6xp (1
1
1 5x (1 al-n)mm.. + andx
8xy +
and recall that there is no max-term in the update for pre-terminal states. Note that the equal weights 1 are consequence of the step-size schedule. To compute the return distribution 8o for action "left" we need to identify a". For that sake must identify the sample means of seyeettarsss (s1,a):
N
Qeye,tar (on.,ar(s11,,)
(s),
Σ X N(m,02/N) N
1
Now we chose a" arg max, taye,tar a) and set
nove,tar (s0. "left") = bo. coyyett tar (81, a") =: =:7X.
While we do not know much about X (it is the empirical distribution of the set of Gaussians XI, .... X2. with maximal sum) we know the exact distribution of the sample variance for the following reason. The sample variance of every ve (81, a) nothing what is called sample variance of the iid observation X1. ..., Xg in statistics. If M, Ei X is the sample 2 the sample variance then it well-known that
mean and $2 = x N (X, - )
EES =
15

---

ADDQ: Adaptive Distributional Double Q- Q-Learning
S is N-IXN- disttrbuute
Ma and 52 are independent.
The third property implies that if 41 Sa, are independent sample variances and a" is chosen to maximize the sample means, then also Sg.
o² - while Ma- Ma.
As a consequence, even though we cannot compute the distribution of the sample mean of jjeyctoo(ss) "left") we can compute the distribution of its sample variance o² X-1X--1- The expectation is E[S?] o² while the variance is 2n¹ V(S2) N-1 Note that might be tempted believe the sample variance is independent of the number k of actions. This is not the case, as the number of explorations Nk: needed for N explorations depends on k. Alternatively, one might denote the number of total episodes by n and replace N by L
We now come back to the motivation our ADDQ algorithm, in particular the choice of 3. Let us consider the two-sided bandit MDP with N ((u1.ff (resp. .V (p2,07 oï)) distributed rewards. Suppose μ4 > P2 are small but of < oz and/or ky < 2- The MDP delicate as the following can happen using QL (overestimation) and DQL (global overestimation reduction). In QL the agent will believe for long time that "right" the optimal action in so. In DQL the agent will believe for long time that "down" is the optimal action both non-trivial Q-values be underestimated to be negative. It is thus more reasonable to mitigate overestimation locally instead of globally. This is what ADDQ achieves through the choice of B.
To use our explicit computations above, the agent explores both sides with cyclic exploration and target-matrix update. Now assume both sides have been explored with a total number of n episodes each. The agent knows the estimates f(so, "left") (resp. (ss., "right")) and the corresponding Q-values (sample means of return distributions) Q(50, "left") (resp. (su, "right")).. From the overestimation study of the previous section, the agent unwittingly overestimated the true Q-values in the order of (1gh1) log(ks)
(resp. / log(kz)) and will believe "right" is the correct action. Now the smart agent also knows he/she should take into account the sample variances that is known to the agent and know are of the order of (resp. o2) with concentration depending on ki (resp. k2). The local overestimation control of 3 (based on relative sample variances) from (1) thus compares of to o and suggests to mitigate overestimation of Q(so, "right"). In our algorithm we use double Q-learning to mitigate, the same idea can of course be integrated into other algorithms (such as changing number of truncation atoms truncated quantile critics algorithms (Kuznetsov et al., 2020)).
vn
16

---

ADDQ: Adaptive Distributional Double Q-Learning
B. Experimental confirmation of theoretical results for two-sided bandit MDP
We provide an experimental analysis of the two-sided bandit MDP for which we proved theoretical results on the overesti- mation. For reimplementation purposes we collect here all required information on the environment and the training for all plots.
Environment:
7 0.9
A1 -0.1, 0.1, h:2 5, 1; the correct decision is thus moving to the right in the Start State.
Distributional properties for ADDQ:
categorical parametrization, 51 atoms equally spaced on [-3,3]
initialization do
Algorithmic choices:
S is chosen according to (1)
1 step-size schedules a)) Tea(1)" with (t) the number of visits in (s,a) up time t, i.e. " counted
state-action wise
exploration: either e-greedy with linearly decreasing from 1 to 0.1 in 10000 steps, then constant (E) or uniform random (U)
Policy evaluation: evaluation of steps with frequency of every 500 steps using current greedy policy, correct action rates refer to if the exploration was greedy
In order to demonstrate the proven proportionality of the overestimation of Q-values by QL in the number of arms and the variance to the left, we keep one of the values fixed and compare different values the other one.
First experiment: d1 5 fixed, iterating over k 5, 10, 15, 20, denoted as K in the legend
Second experiment: k fixed, iterating over σ 2, 4, 6, 8, denoted as the legend
The plots also demonstrate that
ADDQ is much better in terms bias, leveraging local information given by the (relative) variances
the variances and relative variances at state 0 capture the real variances given by the MDP
although our theorems assumed sufficiently exploratory policy, the results seem generalize the much more commonly used e-greedy setting
17

---

ADDQ: Adaptive Distributional Double Q-Lcarning
number on the apalion-greecy cration
sight
2202
6.00
8.03
0.:0
225
205
6.50
2000
-25
100
10.0
2000
ght
00-1LD
A000 SWLLE)
600
E00
12302
2005
680
1X03
1232
200
6.00
200
-205
10.0
200
Rebative torlances
Aebitive Varbaicos Hight
Folafiet Vo aroes
onpty
3.13
311
3.0
2002
4003
12300
2200
10302
2306
K.02
200
2310
the uniform acter
010-300
4000 (00.
0.-
2004
Talaive Warlatoos
Litir Nelaatos
Pada Yea a1ti
335
4003
2000
2004
630
2000
4008
Figure 6. Comparing ADDQ and Ql. on two-sided bandit MDP with different number of the left side and different exploration settings.
18

---

ADDQ: Adaptive Distributional Double Q- Q-Learning
choices vartance on opallon-greedy exploration
sight
044
6.00
A.07
0.00
256
10:00
205
6.50
2000
-25
100
10.0
2000
ght
4.34
ADCDIS
04
600
8003
12300
2000
6.00
1003
1230
2005
6.00
200
-205
10.0
200
Rebitiie torlances
Aebative Varbaicos audkan Hight
Folafiet Vo aroes
onpty
23-
2002
4003
B003
12300
2206
10302
2300
K.22
200
2310
Differont
Unifform
Left
Uublues pader
2.5
3.0
ARRIC (14nk
0.4
2004
TJ. Litii Neliatoo
Pada Yea a1tE
340
035
4003
2000
2004
630
2000
4008
Trarr
Figure 7. Comparing ADDQ and QL on two-sided bandit MDP with different variances the left side and different exploration settings.
19

---

ADDQ: Adaptive Distributional Double Q-Lcarning
C. Grid world details
C.1. Experiment from the main text
For reimplementation purposes we collect here all required information on the environment and the training for all plots.
Environment:
= 0.9
white low stochastic high average reward region: rewards -0.05, +0.05 with equal probabilities
gray high stochastic low average reward region: rewards 22.1, with equal probabilities
goal: deterministic reward of 1, fake goal: deterministic reward of 0.65
Distributional properties for CategoricalQ. CategoricalDouble, and ADDQ:
categorical parametrization, 51 atoms equally spaced on [-3,3]
initialization as 60
Algorithmic choices:
3 is chosen according to (1)
step-size schedule (s,8, a) (T) with Te.o the number of visits in a) up to time t, i.e. 1 state-action wise counted,
exploration: e-greedy with e linearly decreasing from to 0.1 10000 steps, then constant
Policy evaluation: evaluation of 6 steps with a frequency of every 500 steps, correct action rates refer to if the exploration was greedy
action retes, scores
Poll
Conrect epechs
stobet 1,8.6, and
Summeeed total Blsses
Summed Intal sousred Bases
0.5
0.00
-20
022
1030
10000 15000 25903
29203 R000
105
12:00
3500
3020 33000 19230 2000O 23003 12300
1200 2000 19000 20000 25203 XOOO
Longth
Langth esochs
MA wrrhmaa
0.0
0.1
-02
inèen vveer seiin Seoeear
Figure 8. additional plots
For completeness we give plots pairing learning curves for Q-values with the corresponding sample variance. We give all state-action combinations for the interesting states and 4 next to the fake goal, and next to the region with high stochasticity, and 10 and 14 before leaving the region with high stochasticity.
20

---

ADDQ: Adaptive Distributional Double Q- Q-Learning
Lxpue Celnccin valata
CEo TROE 208 Lobee
Sata
ond
2027 17Th
060
2008
2007
640
Oiabe Calaanty
Statr Jetinn
Buae duiee
1000
350 1008 1800 3000 2008 B010
D4E 3800
M00
0000 0000
A-Aerctton values and Sample the stochantic
3.5
1/7
20th Eore
21

---

ADDQ: Adaptive Distributional Double Q- Q-Learning
ua Samrpi vagaresy cooggng stechostig
550 1500
3500 11.00 1088 M500
625 1600 1000 12.00
11,00
2008
1500
Finally, the following plot demonstrates that, in this GridWorld example, the relative variances also strongly determined by the variances of the next state.
Alloe
Gale
Due Edlle
2000
22

---

ADDQ: Adaptive Distributional Double Q-Lcarning
C.2. Ablation study
In the following, on the same environment as before, experiment with different choices for & and compare with weighted DQL (Zhang et al., 2017) with 10 (WDQ), the standard choice from that paper. The choice of beta's names comprised as follows:
(Optional) First two letters: Left-tilted (It), Right-tilted (rt)
First/Third letter: Neutral (n), Aggressive (a), Conservative (c)
Final digit: Refers to the number of intervals in the definition of Beta (3 or 5)
The choices of Aggressive, Conservative, and Neutral refer to the trade-off of no interpolation (just choosing which Algorithm's s update to take) and softening the interpolation, with neutral being in between the two choices and corresponding to the choice presented in the main body. Left- and Right-tilted refers to shifting the intervals for the relative Variance to fall into while choosing the interpolation coefficient. Left-tilted favors the Q update, Right-tilted the DQ update. The concrete choices are:
0.75
(s, < 0.75
(s, < 0.99
n3:
B =
0.5
(s, E [0.75, 1.25]
a3:
:
0.5 (s, E [0.99, 1.01]
0.25
(s,)) 1.25
Sta(s,)) 1.01
0.75
(,,() < 1.25
(,a(s, 1.49
ltm3:
B =
0.5
(s, E [1.25, 1.75]
Ita3:
B =
0.5
S,a(s,) E [1.49, 1.51]
0.25
(aa(s, 1.75
Sta(s, > 1.51
0.75
(s)))))) 0.25
(,a(s,a) 0.49
rtn3:
B =
0.5
(s, [0.25, 0.75|
rta3:
0.5
(aa(s,a) E [0.49, 0.51]
0.25
S (s, > 0.75
Sta(s,)) > 0.51
(Sa((s,)) S 0.25
0.6 ( a) < 0.6
0.75 Sha(ss E (0.25, 0.75)
c3:
B =
0.5 (s, E [0.6, [0.6, 1.4]
n5:
8=
0.5 (,,,sa) E [0.75, 1.25]
0.4
S (s,(s))) 1.4
0.25
(ta(ss)) E (1.25, 1.75)
(ha(s,a) 2 1.75
()a((s,) < 0.75
0.6 (s, <
0.75 (a,(s))) E (0.75, 1.25)
Itc3:
B =:=0
0.5 82 (s E [.9)
Itn5:
B =
0.5 (ha((,)) E [1.25, 1.75]
0.4 S% > 1.9
0.25 (8a(()))) E (1.75, 2.25)
(ha((s)) 2 2.25
(ta(s,)) -0.25 --0.5
0.6 (, a) < 0.1
0.75 (aa(s,)) E (-0.25, 0.25)
rtc3:
B =
0.5 (s E 0.9.
rtn5:
0.5
(s, E [0.25, 0.75]
0.4 22 (s, > 0.9
0.25 82 (ta(s,)) E (0.75, 1.25)
S 2 1.25
23

---

ADDQ: Adaptive Distributional Double Q-Lcarning
S (s, 2 0.99
0.7 S (s 0.1
0.75
(s, E (0.99, 0.995)
0.6 ( (0.1,0.7)
a5:
B
0.5
(s,)) E [0.995, 1.005]:
c5:
B
0.5 (,,)) E [0.7, 1.3
0.25
(s, E (1.005, 1.01)
0.4 (s (1.3,
(s,() 2 1.01
0.3 (s)(s, 1.9
(s,() v 1.49
0.7 (, 0.6
0.75
(s,(s, E (1.49, 1.495)
0.6 (,,() E (0.6, 1.2)
Ita5:
B =
0.5
(s, E [1.495, 1.505]:
ltc5:
0.5 S,a(s,0) [1.2,188]
0.25
(ta(s, E (1.505, 1.51)
0.4 (
(,,(), 2 1.51
0.3 (
(s,(a))) S 0.49
0.7 ())())) -0.4
0.75
(s,)) E (0.49, 0.495)
0.6 (s,()))) ( (-0.4,0.)
rtaS:
8
0.5
(s,()) E [0.495, 0.505]
rtc5:
0.5 (,,(s,) E (0.2,088]
0.25
(s, E (0.505, 0.51)
0.4 (sa(), (0.8, 1.4)
(s, 2 0.51
0.3 ()) 214
24

---

ADDQ: Adaptive Distributional Double Q-Lcarning
Ablation study Summed tocal artiens
Summed tobal siaees
Gummed lotal
hed arhone
0-
10
23
-20
-30
State Action Lp
State Action fight
State 1 Action Down
State 3 Action Left
035
ACD0
20R0 LEVE
XCT0
N200 10AE
NG00 (C3
X000 11221
13300
8051
X001 17300
4.22
1291
X001
17309
2023
1300
19601
1667
132
1902
Up
17
study al best activve
Surmmed
Spmmmed Intal bisoet
Gummed Irbel oquared have
bee actione
1200
1000
1000
5000
12300
2003
4025
6990
1003
12300
2023
4000
6602
8005
10000
2204
4200
6602
1002
1p
WC0
ACD0 (ryd1
1000 (ru0t
20100
N000 (PCS)
Lombha
Static
Stati Action
Action Dowt
Action
1.32
1.0
1200
1000
123.0
2003
412E
1000
5003
12200
2053
1200
30003
0007
920
30005
Figure 9. Ablation study plots regarding bias improvement. State 1 is adjacent to the fake goal, state 6 adjacent to the stochastic region.
25

---

ADDQ: Adaptive Distributional Double Q-Lcarning
It turns that
the choice of thresholds in 3 (hyperparameter to the algorithm) is harmless, results do not vary a lot,
conservative choices seem to work especially well.
weighted double Q-learning, an algorithm that is similar to ADDQ with non-distributional choice 3 improved by our locally adaptive distributional RL based choice of B.
C.3. Comparison to other algorithms
We compared ADDQ with other bias reduction methods using different hyperparameters used in the respective papers on the same Grid environment.
Maxmin with 2, 4, 6, and 8 ensembles (Lan et al., 2020)
Ensemble Bootstrapped QL (EBQL) with 7, 10, and 15 ensembles (Peer et al., 2021)
Randomized Ensemble DQL (REDQ) with 3 and 5 ensembles and size and 2 of random update subset sizes (Chen et al., 2021)
It turns out that ADDQ decreases the estimation bias stronger than those algorithms while only using two ensembles.
26

---

ADDQ: Adaptive Distributional Double Q- Q-Lcarning
Correct action retes, blases, and scores
Policle F210 statee red
Correctacton on
Gammed Intal Sinces
Summed trbal flages
12
03
24
ACD4 lai
20000
13:0
Scores Suing ONiMusions
Length atllo
Scores CUTig ez0cls
Length of spocts
8:00
05-
3.2
3:2
0.1%
425
4:0
2322 12030 15090 X640 25600 12300
5200 3060 1965 Xaccs 25602 M003
230
402
800
230
d-fuuction
goel
State 1 Action Up
State 1 Action 101
State Acbinn Doen
State L. auttion
1.4
0.0
02
0.0
5300 23090 2020
2000 3305 1300 2030 20090 26000
3030 3300 1500 J5000 X0200
1208
0.6
Galeperall
23000
3000 1000 1300 20300 2509 X000
3000 330C 1500 20300 23000 X000
15008 20300 25000
Aettonn
Artin Right
fefetinn Town
Antin
3.2
02
-1.
State Addiion
A.lam Nigh
Stele Aclion Cown
Sladi 7Ali Loll
3.2
0.2
5020 10900 1500 20003 35000 30:30
3000 330C 15000 22300 25000 X0200
5000 1300 1500 70300 25800 X220
5000 3303 15000 70300 7500 2000
Figure 10. Comparison to MaxMin.
27

---

ADDQ: Adaptive Distributional Double Q- Q-Lcarning
Correct action retes, blases, and scores
Policie F210 statee aed
Correct on
Gammed Intal Sinnes
Summed tobal flages
12
05
Gatgercaboaaee
165399 20000
ACD4 inl
(00L3
Scores Suring ONIMAsIIn
Length oval. alora
Scores CUTIO cz0cls
Length of spocts
1R0
8:00
3.23
3.23
02-
0.1
425
4:0
5322 12030 15090 Xd40 25600 12300
5200 30660 1965
Xaccs 20602 8603
200
next goel
State Action Up
State 1 Action Riln
State Acbin Doen
State 1 Action
1.2
25009 35000 2005
3000 12,00 1300 20033 25000 2000
2500
3300
1500
20300
20090 20090
3000
12008
15000 2000
12
1.5
044
0.0
0.6
22
02-
02-
Galeperall Eallgea
62
10000 25000 25000 300C
300 12900 -300 2000 2008
300
3300 1500
20300 25090 3009
30000 15008 2030 25000 3000
(E0L3
120l Aeriton Up
8 Action Right
Giste Aeticnn Town
Shil Eelttinne
3.2
1100104
3747201
0700301
AAllaa
7 Action Sight
Stete Action Cown
State 7 Adlion Lafi
2.50
1.2
0.3
8.75
0.00
5000 10000 15000 2006 75000 2000
3000 12000 15000 2063 25000 2000
5006 3300E 15000 20300 25000 2000
5000 30000 15600 70300 7500 1000
Figure 11. Comparison to EBQL
28

---

ADDQ: Adaptive Distributional Double Q- Q-Learning
Correct action retes, blases, and scores
Poliie's correchness ra50 riiiler and
Correct acton ra00s
Summed totel
Summed total
-22
-12
ADD4 le!
Gatgercabaale
3500e
Scores during evoluations
Longth of eval.ations
Scorss during spocts
Length of spocts
WOGIL()
5:3-1
2.00
0.22
0.50
5000 12000 1000 J9KE 20ice 3063
3000 3660 15699 M600 2560 2000
2000
500
300
222
O-function
next to goel
State Accion Lp
Statc Action 1914
Siate Addin Dumi
State Action Left
1.0
32-
2.0
06
C2
03
3000 20.60 15090 2000 2000
5000 J6230 13000 25030 2000
35003 20090 1000 3000
5002
12000
12099 20000 20050 2030
2.4
0.-
02-
Gdogerall
3600 3000 12000 20000 2000 300C
5000 -6030 1300 2001 25000 300C
5000
1300
2500
20000 23900 3009
3007
12000 12000 20000 2003 3000
REDOILU
Qpale A.t
1pale Artimn Right
Crete Artion Bowm
State Laft
1.2
3.3
1.50
1.25
1.00
2.0
22-
11-1
Stati
Stati AAliin light
7 Aulion Down
State Adlion Left
2.5
1,00
3.0
8.75
8.50
-02
2600 3266 12000 2000 2000 2000
5300
10230 15000 3003 25030 2000C
5300 15900 2500 20000 2500 3000
5003 12000 15000 2000 22000 2030
Figure 12. Comparison to REDQ.
29

---

ADDQ: Adaptive Distributional Double Q-Lcarning
D. ADDQ adaptation for QRDQN -setup
To not double too much in the main text we moved the adaptation of ADDQ to the quantile setup (Dabney et al., 2018) to the appendix. In this section we explain how to adapt the ADDQ idea into QRDQN. experimental results are provided the next section.
The categorical approach has multiple visadvan most notably rewards and the fixed atom positions must be compatible. The categorical algorithm was included in the main text to keep notation simple. For quantile distributional RI. the return distributions are parametrized by
m
Fq.m
do. m1
0 E R. 3
In contrast to the categorical setting the positions of the atoms not fixed, but the weights of all atoms set equal. The computation of the target is equal to the categorical version (except using the projection on Fq.m instead of Fc.m). The update step is a gradient step in computing the prroeeetiinnoooecttiinn on FQ.m of the target distribution f), that is gradient step in the quantile Huber-loss minimization:
771
min
E Bp (Z (s
0f (s.a)...... B2 (s,aa)
with quantile mid-points T;
2:-1 and 2m
|T 1 [ luso|<((ul xx)
|u| < |u] > K
pF(u)
The quantile Q-learning modification of classical DQN (Mnih et al., 2015) is called QRDQN. Using the same network architecture as C51, QRDQN approximates return distributions using the quantile representation. Therefore the last layer outputs the quantile locations for each action. In the quantile setup write (s, a) 1 Σ (0,(s,a;w) with induced mean values (s, a) m Σ (s, w). Given sample transition s"',, the network parameters are updated via gradient descent with respect to the loss function
((w) = - Σ (r -
-0( x" argmax Qz(s', a');
(5)
:1==1
and the quantile mid-points Ti
2-1 2m
In what follows we turn three known double variants of DQN with overestimation reduction into QRDQN variants and compare them on several Arcade environments to our algorithms. We use double DQN (van Hasselt et al., 2015), a Q-learning adaptation of the clipping trick included in TD3 (Fujimoto et al., 2018), quantile version of our ADDQ algorithm, and additional variant of ADDQ. Using the Stable- Basellesss framework [(affin et al., 2021)] there is very little that must be modified. Return distributions 1 and 17 are parametrized with two independently initialized neural networks denoted by A and " As in DQN we use delayed target networks, one for A, one for B, that are indicated with an additional bar. For each gradient step we simulate a vector of random variables with the same size as the batch size with each element determining which of the two estimators is being updated based on the respective transition with the same position in the batch. Accordingly, we use twice the batch size for these methods, so that on average per gradient step, the same number of transitions is used for each estimator, compared to the single- ingle-estimator case. The only difference in different algorithms is the target used update the neural networks.
Similar to modifying C51 implementations we only modify the target return distributions br. (s', x²) for an appropriate action z². In the quantile setup those are given by the locations of their atoms:
r {r + (
L, I....,,.. m}
We again use the compact A/B notation to indicate how the update applies for A and B
Double QRDQN: DA/B_ Maasa (s', 2²²,, where 2* = argmax, Qea/D a')
30

---

ADDQ: Adaptive Distributional Double Q-Lcarning
Clipped QRDQN: PAIB F1x (8', ;²), where =² argmaxx Qaa/D (5', a') and X argmiin (s',="")))
ADDQ (us): DA/B A (s', 2²) + (1 B/ (s', ="), where x" = argmax, Qa ('', The weights B (WW) are essentially arbitrary and can depend on the current estimated return distributions 17²2 and sy For the experiments we take the same choice from as used for the tabular and the categorical settings.
Experimental results are presented in the next section.
31

---

ADDQ: Adaptive Distributional Double Q-Lcarning
E. Deep reinforcement learning experiments
To ensure fair comparison we modified the algorithms C51 [(Bellemare et al., 2017)] and QRDQN [(Dabney et al., 2018)] within the Stable-Baselinee framework [(Rafiin al., 2021)]. The C51 implementation has been added to this framework by adapting from the Dopamine framework [(Castro et al., 2018)] and the DQN Zoo [[Quan Ostrovski, 2020)]. We run Atari environments from the Arcade Learning Environment [(Bellemare al., 2013)] and MuJoCo [(Todorov al., 2012)] environments both using the Gymnasium API [(Towers et al., 2023)]. We run the experiments via the RL Baselines3 Zoo [(Raffin, 2020)] training framework.
The experiments were executed on a HPC cluster with NVIDIA Tesla V100 and NVIDIA A100 GPUs. The replay buffer on Atari environments takes around 57GB of memory and less than GB of memory for MuJoCo environments.
For the experiments the training has been interrupted every 50000 steps and 10 evaluation episodes on 10 evaluation environments without exploration have been performed. The plots below show the mean total reward (sum of all rewards) averaged over 10 seeds with standard errors of seeds the shaded regions. To improve visibilityy rolling window of size 4 is applied. Atari runs took less than 48 hours for 20 million train steps and periodic evaluations and MuJoCo runs less than 36 for 10 million train steps (Humanoid) and periodic evaluations. Note that one timestep in the Atari environments corresponds to 4 frames, which are stacked together. This corresponds to repeating every action times in the actual game. Therefore 20 million timesteps correspond to 80 million frames. Additionally, small ablation study comprising of 10 seeds on one evaluation environment with some the choices of beta detailed in Appendix C.2 has been conducted.
32

---

ADDQ: Adaptive Distributional Double Q-Learning
E. Full experimental results for the categorical parametrization
As in (Bellemare al., 2017) we use 51 atoms for all C51 variants.
wosauthheFramcskkipee
Auterisk-Franssip-d
ADDG (US]
500000
CS1
DOUBLE
8000
400200
1ta Reword
6500
Total (awwnni
500000
200030
2000
100000
10
15
20
15
20
Timestop (1e8)
Timestopa (168)
RattnzorehoFrmmeelppr
35
25000
100000
30
25
15a) Rowerd
Toaa Dewant
20
Tele
15
1000
40000
10
15
20
0
20
0
50
20
Timesleps (1e6)
Timestops((et
Timestppo (1e6)
DopharhhoFFameekkppoo
ADDO
DOUBBE CS1
50000
12, Cb7
Ranurd
400030
800n
35003
Tolal
4000
20000
(1w5)
(1w6)
TenrishoF
.40003
-2.5
50000
120003
Total Revard
100000
Raaard
-7.5
Total Naward
80003
00000
12.6
19000
-5.0
10000
22000
-175
-20.0
Timestipa (1e6)
(148)
Timestips (168)
Figure 13. Learning curves on Atari environments, averaged over 10 seeds
33

---

ADDQ: Adaptive Distributional Double Q-Lcarning
We additionally provide plots using the RLiable library (Agarwal al., 2021).
Algorithm
Algorithm
DOUBLC C51
CLIP C51
CLIP
C51
DOUBLE C51
ADDQ (us)
CLIP
ADDQ (us)
DOUBLE C51
ADI (us)
C51
0.4
0.5
0.8
0.7
P(X*
Figure 14. RLiable probability of improvement plot
Median
IQM
Maan
Optimality Gap
CLIP
JOUBLE
ADDQ (Us)
3
12
5.0
7.5
10.0
10.0
12.5
15.0
17.5 0.06
0.09
0.12
0.15
Normalized Score
Figure 15. RLiable human normalized scores plot (based on (Badia et al., 2020)
34

---

ADDQ: Adaptive Distributional Double Q-Learning
E.2. Full experimental results for the quantile parametrization
Astetten.Framzsip..k 24
ADCQ (US)
300000
ORDON
17500
DOUBLE ORDON
250020
CLIP ORDON
15000
R00000
Total (lnowrd
200020
10000
150000
5000
2500
50000
15
Timeslopa (1e8)
Timeslopa (1x6)
FrocessoFFonesilp..
120000
Taba Roword
Total Dareer
ancon
Rareen
20000
00000
15
40000
10
10000
0
15
20
Timeslopa (106)
Timestopa (1o6)
Timastapa (106)
Gopherhiof CophenhhoFommmekpprr romeekip-ot
ADCG (1M)
QHIJON
10000
DOURL QUION
80000
T0oa Roward
80000
8000
Total
4000
20000
2000
15
20
10
15
20
Timesteps (1e0)
Tiimesteos (1e6)
Phoertchiol rameskip-ot
lenreaNic nemnedic prodt
Yarn/eevargefeor ramestip-ol
120003
80003
-0.0
25000
Tobal Rowart
Total Rloovrrs
-7.1
10tal Mowarr
19000
40000
20000
-10.0
5000
-17.5
10
15
20
10
15
0
10
20
limesteps (1wS))
limeddese (1v6)
|imestaps (1et))
Figure 16. Learning curves on 10 Atari environments, averaged over 10 seeds
35

---

ADDQ: Adaptive Distributional Double Q-Learning
Algorithm x
Algorithm
DOUBLE QRDQN
CLIP QRDQN
QRDQN
CLIP QRDQN
QRDQN
DOUBLE QRDON
ADDQ (us)
CLIP QRDQN
ADDQ (us)
DOUBLE QRDQN
ADDQ (us)
QRDQN
0.5
0.6
0.7
P(X Y)
Figure 17. RLiable prohahility of improvement plot
Median
IQM
Mean
Optimality Gap
CLIP QRDQN
IOUBLE QRDQN
QRDQN
ADDQ (us)
12
0.12 0.16 0.20
Normalized Score
Figure 18. RI Rable human normalized scores plot (based (Badia et al., 2020))
36

---

ADDQ: Adaptive Distributional Double Q-Lcarning
E.3. Full experimental results for the actor critic setting
Ant-vo
HarCheetth--s
ADGRSAC (Us)
8000
CINSAG
7000
DOUBLE GRSAC
10000
8000
12000
4000
Total
5000
Total
10000
2003
8000
1000
6000
Timestopa (1e6)
Timestepa (1o66)
Humanold-vv4
Walker22
2500
5000
2003
Total
Total
Total
2000
1000
2000
500
0
Timestaps (1e6)
Timeolepe (1v06)
Timestaps (1e8)
Figure 19, Learning curves on MuJoCo environments, averaged over 10 seeds
Algorithm X
Algorithm
DOUBLE QRSAC
CLIP QRSAC
QRSAC
CLIP QRSAC
QRSAC
DOUBLE CRSAC
ADORSAC (us)
CLIP QRSAC
ADORSAC (us)
ADORSAC
QRSAC
0.2
0.4
0.6
0.8
P:X
Figure 20. RLiable probability improvement plot
37

---

ADDQ: Adaptive Distributional Double Q-Learning
Modian
ICM
Moan
Optimlity Gap
GRSAC
QUBLE ORSAC
QRSAC
(DG
0.25
0.50
0.75
1.00
0.26
0.50
0.75
1,00
0.4
0.8
1.2
1.6
0.2
0.4
Score
Figure RLiable normalized scores plot, based highest and lowest performance on each environment
38

---

ADDQ: Adaptive Distributional Double Q-Learning
F. Convergence proof in the tabular categorical setup
In this section we give a convergence proof for the adaptive distributional double-Q algorithm the simplest setting, the categorical setting. The proof is based on known arguments from the literature and requires some modifications work in our generality. Since many papers only sketched proofs we decided spell out all details. Remark F.1 (Notation and short recap). The Cramer distance Eg for probability distributions v, E ((R) is given by
(2(,,0) (L
F2 Fu
1/2
Following (Rowland et al., 2018; Bellemare et al., 2023) the supremum extension probability metric d between two return distribution functions 77, n/ E IPSAA is denoted as
d(n, 1/) = sup d()(s,a), s.0ESxA
The iterates 7 = IIeT" 7/ converge to the unique fixed point in F.m with respect to &a based on Banach's fixed point Theorem. This follows from the contraction property
(TTTTc TcT (la())))))
[compare (Rowland et al., 2018; Bellemare et al., 2023)].
Theorem F22 (Convergence of adaptive distributional Q-learning in the categorical setting). Given some initial return distribution functions no no supported within 101, 6.) the induced Q-values, i.e. the expected values of the return distributions (ny() ) (nt)), recursively defined by Algorithm converge almost surely towards Q" if the following conditions are satisfied:
1. the step sizes as(s, a) almost surely fulfill the Robbins-Monro conditions condicttion Ei (s) 0o and 2x as a) < cc.
2. rewards are bounded in [Rmins Rmax] and
Rmii 1-7
Ramax
C (ml
1-7
3. the choice of updating T7 or 17 random and independent of all previous random variables
4. the sequences (3,) )oEN, (3.) )eEN only depend on the past and fulfill lim; 13,- - -, = 0 almost surely.
If additionally the MDP has unique optimal policy n", then (Nt (viP) converge almost surely in E2 some limit ie E Fc and the greedy policy with respect ve is the optimal policy.
Note that the algorithm and proof uses 8/4/ (s, a) with index & + 1 when updating 1/1 A/B This is to show that in general the parameter is allowed to depend on S and the respective greedy action, i.c. it must only be Fe+1 measurable. To portray this generality in the following we will only write 3,4/3 without referencing state-action pair.
The simplest way to guarantee the assumptions the adaptive parameters 3
8 to be satisfied is to chose them equal.
As in (van Hasselt, 2010), the proof is based on the following stochastic approximation result, see also (Bertsekas & Tsitsiklis, 1996), Proposition 4.5.
Lemma F.3 (SSingh et al., 2000), Lemma 1). Suppose (2, A. P, (F.) is a filteeee probability space on which all appearing random variables are defined. Suppose that
1. stochastic process (Fa)ner C Rdd with the coordinates Fi, for i = 1,....d such that Fú, Fat1-mmasuuue and for all ,....,d dd
F... S Sallo + cn and V[F.../F.) < K(1 + X n n21,
where E [0, 1), an adapted, stochastic process (Cx)NEN C. R+ that converges to 0 almost surely and some constant > O.
39

---

ADDQ: Adaptive Distributional Double Q-Lcarning
2. the non-negalive stochastic process (an)nEN C RR, with the coorlinates di,n for 1,.... . is adapted with
0i and
in
2 < 00
a.s.
Then, for any Fu-measurable initial condition No the stochastic process (Xn]nEN C R with coordinates Xi, for i = 1,..., d that is recursively defined by
Xin+1 = (1 0iin + ainFiin n MEN,
converges almost surely to zero.
Furthermore, we follow (Rowland al., 2018) by first showing the convergence of the mean-values Q and afterwards showing convergence of the return distribution functions, under the assumption of unique optimal policy, by coupling it with policy evaluation. The convergence of the latter is easier prove and we will do so at the end.
Lemma F.4 (Adaptive Double Categorical Temporal Difference for Policy Evaluation). Given some initial return distribution functions No B supported within [01, 0m] and a stationary policy x E IIg, the return distribution functions (nz)), (n)) ) recursively defined by Algorithm I, but with a' ( S.+1) instead, converge almost surely towards the unique fixed point Ic E P(B))xA of the operator lcT with respect to Ez if the following conditions are satisfied:
1. the step sizes as a) fulfill the Babbins-Monre conditions:
Di a) oc Ei of (s,a) < oo,
2. rewards are bounded in [Bmins Rmax] and
Rain 1-
Ramau I-7
S
[0,, 0ml,
3. the choice of updating T or T random and independent of all other previous random variables
The above result is only relevant for the proof of Theorem F.2, as policy evaluation with a double estimator is not of interest. Note that convergence of categorical temporal difference for policy evaluation (in the single estimator case) has been proven in [(Rowland et al., 2018) Theorem mimicking (Tsitsiklis, 1994) Theorem 2] and [(Blllemare al., 2023) Theorem 6. 12 applying (Tsitsiklis, 1994) Theorem (Bertsekas & Tsitsiklis, 1996) Proposition 4.5J.
Lemma F.5. Let (oo)teNo be sequence fulfilling the Robbins-Monn conditions and (Yt)een an iid sequence of Bernoulli(0.5) random variables, i.e. P(Y, = 1) = P(Y 0) = 0.5 for all t E No. Then (a.Y (a.Yi)LeN, also fulfills the Robbins-Mone Monro condition.
Proof. The almost sure convergence of the summed squares is obviously fulfilled due to
E(art)
Σ
a almost surely.
t=0
Due to independence of each Y, with (Yn/n= No. + t well as with (at) will consider two stage experiment, where we first draw the sequence a = (a and then independently of this realization sample the iid sequence Y = (Yr) Due to the independence the joint measure of a and Y is the product measure. Consider the product space (12, F) = (Pa x Qy Fa @ Fy, & 1) where Pa fy = [0, 1) Fa. Fy = B([o, 1)) Then, using that 2i 0g = oc -ll-at surely, we have
=/ Py
P Σ
a.y - = 00)
a,Yi = 00 oodPaa(a
Ssa
1=0
Py
Σ
a.Y: = 00 do)PPaa)
(lar) a000)
1=
(a)
40

---

ADDQ: Adaptive Distributional Double Q-Lcarning
where (a) can be seen as follows. Consider any deterministic sequence (b,) S [0, fulfilling Σe= b, xc. Then
b b,Y, +
b,1y
t=0
Now notice that A Ei=o b,Y, and B infinity, almost surely either one of them is infinite. Given the identical distribution, we infer
=
Ei= by ly.=0 are identically distributed and since the sum of A and B is always
Py
b,Y 00) > 0.
t=
But since (b) is an independent sequence of random variables and the event that the infinite sum diverges is in the tail sigma algebra, the Kolmogorov 0-1 law yields:
be Y xc)
t=
Remark F.6. As outlined in (Rowland et al., 2018), proof of Proposition denoting by (R) the space of all finite signed measures on (R, ((R),, the subspace
Mo(R) = jv E M(R))((R)= = 0, Fo < oc),
"where Fx(x) =[1-o0,x)) for x E R, is isometrically isomorphic to a subspace of the Hilbert space (2R) with inner product given by
(11, / Fr, (t)d,
Then the affine translation 5n + Mo is also Hilbert space endowed with the same inner product. It contains probability measures / E P(R) satisfying
f Fz(2)² de < and l/(1 (1-F((x)) Fx())) ((or))dd dr <0.
To see this, consider μ P- fulfills Fx(x) Fx)x) for and Fạ(x) Fx(x) 1 for 1. Hence, μ E Ma- The conditions assure that the tails decay fast enough.
Note that the inner product induces a norm through || (1, v). And we have (2 || 112lee In the following proof, we will make use of the relationship
Ci + U2, v/2 1/2) = llu1 -illls + 11 1/112,, + 2(1 1/1u2 -1/2
holding by bilinearity of the inner product.
Proof of Thoerem F22. Step 1: Convergence of mean values to Q*
The proof mainly follows (Rowland et al., 2018) and (van Hasselt, 2010). Let the filtration be given by F, (n6,, 8 so, ao, av Ro, S1, Y1. , ......... St. az, ar), where (Yn)ee is an iid sequence of Bernoulli(.55) random vari- ables, independent of all other appearing random variables, such that A is updated when Yz+1 = 1. Denote the expected values of the return-distributtion by (s, = (=.)) and overloading notation, let us further write B[v] for the expected value ER- of probability distribution v E P().. We will first consider how the expected values evolve. Due to the symmetry of the updates sufficient to show convergence of QA Q". It implied that a(s, a) 0 for (s, a) + (St. az). Further, define
Xx(st, (it, (s))
Ft)s 11 Re + 733 Qi (S++,, (( (1 =0 a.)
Q" (st,
F(s,a) a) 0 whenever (s,a) a) f (st, at)

---

ADDQ: Adaptive Distributional Double Q-Learning
with a² arg max Q ( d'). According to [(Lyle et al., 2019) Proposition projection Ile is mean- preserving, i.e E[[ = E for when y is distribution supported within [81 fm]. This is the case for every nt as in Algorithm 1, which can be seen as following. Assume vi (&c. 0z), th (8t, 02) E F.m. Then also
V == 3 m (S+1,,")) a²) + (1 B/4 dnt (St+1, E Fc
and suppose v = Li=1 p:0g; for some p;. Then
9r = #V
Σ
PiO P
i=1
But now
Riin
Ruiin S
81 5 1
S
m
1 1-9
(Assumption (ii) guarantees that
0, S Rg + 70; fm ViE (L...,,,,
and fj. is supported within (0,, Om]. Similarly for a realized transition with (Be, Sc-1) (re, 8141), have for the
expected value of the distribution
(11 - +11-844)n (st+1, E Drent # (1 a"
(s441,
=r, (B4 (s+11, (1- (s++1,a")). ((t))))))(())))))
Hence, the expected values of the return distributions 1/ subtracted by Q* indeed evolve as
X (s, a) (1
+ az aF
We now proceed similarly as in (van Hasselt, 2010) to show that the conditions of Lemma F.3 are satisfied. We first show that (s, [i] is bounded for all a) S x A and therefore satisfies V[Fi FF] < <[ as required. Since the rewards were assumed to bounded there is an R > 0 such that [r], 101, 10 I Vr E R. Hence, we have
[F. at)) S|R, 73//1 (S, a²) +1
(*,,
+|Xr(st,(::)
R
SR+ 3R 2 1-
Next, we need to show that EFF Filllo xe|lXelloo + cn. Let therefore decompose
ai) =1 =1 F. (st, + (0 (1
- (((+,,aa))))
Xr +ly (4
with (5 at) = RS + - (S Q" (st, a1). This yields
1 11 F.2 (Sz, ax) + 1 1y at) Xe FFll
1 BlR + 7 (S+11, (aa0]][Q((AA ar) + (st. 1
(*
17 (A,,Ass, ar) TT* a.)l + +1 (x(s
s s110er - -Q"Il + ||
1 1 + 2 ||
=
42

---

ADDQ: Adaptive Distributional Double Q-Learning
since the Bellman optimality operator is 7-contraction. Subsequently, it only remains show that
(1 C = E 1 - (S++1, Qi (S a² FFF]
goes zero almost surely. This is immediate we verify that
x a) (..))))
goes to zero almost surely for all (s, E S x A which will be achieved by another application of Lemma F.3. We infer that
X BA (Sn, an)
= =XBA BBA an) + an (n1 an)
1y
(Su+1, Pn + ( + (1 10, (Sa+1, Q (sns un)
-1y+111
Rn + (B8 (S++1,a))) + (1- 3 1 (Sn+1,a))) - ( an)
- =(1-0a(8a x
(8n, an) + an an an)
1y Pn + 7 (B (Su+1,,b))) + (1 - 1 (Sn+1,,
-1yn41=1 Rn + ( (Sn+1, a") + - -11-) (5
+ly +1y Qu an) 1 ly 1x (sps an)
=(1 an(Sns an) x (Ann an) an (sn: On Fn an);
with
Fa(sn;
an) an)
1y Rn + + (Sn+1, ( + (1 1 (Sn1,,b)))
-1 Rn + ( Q (S,41, (1 p (Sn+1,
11
Iy 1 (Sn, an)
Now, using that O. an), (s an), ( az), (sn an) are F, measurable and Y,41 is independent of F,. the conditional expectation satisfies
1
(n an) Fn]]
2 [ 2 (Snt1, (1- (1 (S.+1,)))) ( (Sn+1, 0-
-8 Qn
(11 -1- 1 (S+
1
10 (8n, an) Q (8n, an)l
2
7 n+1 (0 (Sn+ b²) QA (S [
[1813
B[(1 3 (Q. (S b²) - Q (S ())
B[ 3 Q (Sn+1, 11, a² a²)) F
B[((1 - -3 (1 - 1 (Sxt1, (FF([()))))
2 |x,llo
43

---

ADDQ: Adaptive Distributional Double Q-Learning
Now if it holds E (S FR) > (1 Fn)) by definition of a' we have (S
(1 As Q
2 (S b*) and therefore
ElQz Q ( (S a)),,, )) = =[ (Sn+1, b*) - Q (S Fn)
- <RIQ (5)+ Q (S b' [Fn) S x Ix--
Analogously, (5++, E|QnnSn+111 (S b*) - Q (S.+1, a [Fa] (S a²) -. (S b" Fn S E|Q, (S Q (S,+1, a
(Sx+1, a²
Fr.), then we have by definition of 6*
a F S ||
Similarly, by distinguishing cases, one shows that
[[QA - ( S ||x || + 2 ||,
Combining the above yields
[1 an) Fr & 2 73 n+1 (1-B,) p 11))
hE[(S n+1 - p (S
Full + hB[((1 b -
111-B-11 b(++))
( Frn
<R000
<Re00
6m -+0 since
[8 |/ converges to 0 for n-+oo due to (év)
Hence, we invoke Lemma F.3 to obtain convergence of X converges to zero which finally implies (s a) (and also @² as) converges Q"(ss, a) almost surely for every (s, (s,a) S A.
BA and thus with another application of Lemma F.3, Xx(s, a)
Since S,A are finite, for every > 0, there exists random variable N have
> 0 such that for all > N. we
max =E(A.
l - Q < almost surely.
Step 2: Convergence of return distributions
Suppose the MDP has unique optimal policy x². Now following (Rowland et al., 2018), we take to be half the minimum action gap for the optimal action-value function Q' = Q i.e.
min min(Qi (Q" (s, max Q (s, a))
af
which is greater than zero by assumption (v). Hence, denoting the action of the deterministic optimal policy in a certain state s by (s)) we get
max QA max Qf (s. π (s)
for all > N. For some initial condition no E F&,m let now ii be the iterates created by double categorical policy evaluation algorithm for the optimal policy n², i.e.
7 ax) =(1 1 ax
(Sk. (sk. ak)
+ 1 ax Ic
bRuni (3 ( ( (Sk41, (((++1))
+(1 - 3 ) (Sk (+ (Sk+z)))
nh (s, a) - (s, a) for (s, + (sk. ax).
and analogously for 7 Note that the appearing Yx. ags 3 o are chosen to be the same as in the control case above. Then / B converges almost surely to the unique fixed point ne of the projected operator ITT with respect &g by
44

---

ADDQ: Adaptive Distributional Double Q-Learning
Lemma F.4. Similarly (Rowland et al., 2018), we now proceed by coupling argument. Denote by क "े any greedy selection rule with respect to ni and v and A {Th = x² for all k). Then A₁ S Ak+1 and by the above explanation we have P(Ax) / 1. Additionally, let B be the event of probability for which the (double) policy evaluation algorithm converges. Now on the event B U Ag. we have
(i no) + and 20 ne) -
Then by the triangle inequality it suffices to show l2 m/)) + 0 and & (m ( + 0 on this event too, since then the Theorem follows by P(B U A₂) 7
To prove this we will again apply Lemma F.3. This time with d = 2 |||| where we identify
(1 7
X,
( mm)
2 B
E R
Additionally, expand the filtration by F, (Fn, Y.4) and define (s,a) = an(s,a) and (8,a) an (s, y By Lemma F.5 these steps-size sequences still fulfill the Robbins- Monno conditions. Then, writing
A 3d V (Su+1, xt" (Sa+1)) (1 13tt))m ( x" (Sn+1)) (Sa+1, 7 = 3 mi (Sn+1, Tt (Sn+1)) + (1 - 1)hh (Sn+1, αt (Sx+1))
for short, for 2 k: on Ag we have
( an), Tho (8ns Un))
=(1 āZ (s an)) ) 11 (8no an) - 1mn (8m, On 11
+ + Sn, an)) (IlobbR,,, #
II (bR., # 112
+(1 ( (Sn, an) ) (8n: an ( (sn; an) in (8n, an), (b.. -TT (bn..... #0*) Me:
This can be rewritten in terms of Lemma F.3 as
XA (8a, an) (1 5o (Sn, an) X (Sn, an) So (Sn Or FA an)
with Cd an) 20 (8n: an) - (a(ons )²) and
FA (A an) =
(ā an (b lI #D (b
SA (An) an)
+(1 an
( an ) (Sn, an )2(2 (sn an) - m/ (Sn, on),
Nc(bn. [T #1A))
and (s, if (s,a) a) (sn, an). It is mentioned that (Sn, an) > Notice that,
AA (Sn, an) >
(2ā a (Sn; an) - a (sn, 20 a.s.
Σ AA (8n, ann
Σ
4 (sm, Un)² ) 40 )z) CA Un)² < a.s.
n=1
45

---

ADDQ: Adaptive Distributional Double Q-Learning
Finally have
in (8 an) an) (n)3 + (1 - A Dmm B 12+1
17 + (1 - pxtz)
+(1 ā (s: On an) sn, On / (m -imh
Bn A + (1 - / mm
B - 3, mm - (1 - Mn 222))
(ā (5ns an) 727 max
P2 Pg min)
Cn (8n; an)
=E(A.)
+11 - ān (s:: On an)) (sn: On 2
max
Eg (2/ (T))
(E(A.B)
0 (Sn, an
)n) 12 + (1 G (8n, an an)) ) (Sn: On /2
(2 mh) =E(A
20 (5n, Un) 0r (8n (n,)
(2ā (sn: an) ān (sp: am))) //
(2 1 =E(A,B}
max
2 (sn: an) ān (Sn; an)
V max =E(A,))
(g (h.) = Vlllll
where we used regularity and 1/2- 1/2-henogynyity of the &g metric as described in [(Bellemare et al., 2023) Section 4.6] as well as that He is non-expansion in fz and
Ku, Bu + (1 B)o} Blu, u) + (1 - ku, w) S B max([|ul]] (oll) + (1 -) < maxx[|ul]? ||]||²)
by the Cauchy-Schward inequality. Further, by the above the Variance also fulfills VITA (Sn,
(sn; an) [a] B[ (sn; an)
31Fm)) B[FA (sm: an [F,)
S 2(v7 =E(A,))
(2 172)) max
$ 27
sup
Eg 17) < 00.
Therefore, by Lemma E.3 we obtain convergence (n ;7) + and ( n. + 0 on Aμ. As already described above, this results
E2( nT)) + 0 and t nt) + 0 almost surely.
Proof of Lemma F.4. Let the filtration be given by F, = nb so, ap, ag, Ro, S1. Yi, 11,88,888 ...., at ar, Y(41), where (Yn)eNN is iid sequence of Bernoulli(0.5) random variables, independent of all other appearing random variables, such that A is updated when Ya41 1. 1. To clarify, abbreviating
a 3411 U1 (S--1, A++1) + - -1-())1))" (S++1, Ac+1)
B = 3 th
B (S++1, A.41) + (1- -1 (St+1, where
A ~ 7 S1+1);
we are confronted with the updates
// (8, a) = n1, (s, a) +
1/ (s.a)) a))
(s, a) = " a) + aa a) aol (bR,, B) - T/ ( a)).
As in the proof above, define (s a) = (s a) 1y and a (s, a) = (s, a) ay,, By Lemma F.5 these steps- size sequences still fulfill the Robbins- Monno conditions. Also note that as in step of the proof of Theorem F.2, Y441
46

---

ADDQ: Adaptive Distributional Double Q-Learning
A/B order align this with Lemma F.3, we rewrite Fe-meauurable and hence so is di
a) (s) (c...)
-(1 - (1 (s, nc
nc
+(1 10=
a)) (c((R..HH no(s,a))
=(1 - (x + (s.
with ()( = (s, ā²" (s)
(gp TC))
Bi nce]] E (R2S
X,
and
(s, (F(s,a) at (6
nC (8.
+(1 - af (s, (s. no(s, a), II [b #1 -
As in Equation (7), the sequence (s a) fulfills the Robbins-Monro condition. Additionally, note that there exists K 0, such that (bllc(bb,, #v (n) K independent of s, a, Further, observe that
Ct == max
xE{A,B) (s) 1a af a) + 0 for + co almost surely.
We use that Hc is mean- mean-preserving [(Lyle et al., 2019) Proposition 1] for discrete distributions supported within [0,, Om.) which is satisfied by b #VA, due to Assumption (ii) and vA E Fm- Together with the fact that IIc is 77-contraction with respect to & and the Cauchy-Schwarr inequality, we have
=nn a) - ni(ss, a). E IT bb. ) - ([)
E[in (s, a) (s a). (oCbn, #
(s, nics,, a), El # / [Fi] - (nc(s,a))
(s, - no(s, a). I (3 o7
(1 B mm (s, a) (IccT a))
/V7 - nc. (3/4 mh + (1- 11 - 1c))ip
SV7(34) P((h (1) + (1- ( nc. th nc)),
SV7(311 max T Li n1) + (1 841))l -
-olli 1l (12,)
2E(A.B)
SV7 max (E(
( (C))
Xelloo
In total, this yields
[[FFAss as,
1 (A(s,)) 1 lallsa)2o(1 SA (s (a (s,,8)))
$ a Villx
Since (2 7/) < K for every n, r// E FXx some > 0, the conditional variance V[FAA[FF) can be bounded uniformly in
Therefore, the requirements of Lemma F.3 are fulfilled, and its application yields X/(s, a) (n a), (c(,, and XP (s) ( 0. Hence, also n v converge to ne with respect lg.
47


Reviews:
[{"review_id": "ASly6SzCaC", "reviewer": "Reviewer_amjr", "summary": "The paper introduces ADDQ (Adaptive Distributional Double Q-learning), a novel reinforcement learning (RL) algorithm that addresses the overestimation bias in Q-learning by leveraging distributional reinforcement learning (DRL). The key claim is that ADDQ provides a flexible and computationally efficient way to mitigate overestimation, improving learning stability and efficiency.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Dear reviewer, thank you very much for your careful reading and thougths on our article! \n\n**Please check the anonymous repository https://anonymous.4open.science/r/ADDQ-B776 for figures addressing some of your thoughts.**\n\n* You are totally right that the suggested **choice of $\\beta$** is somewhat arbitrary. There are plenty of stochastic approximation algorithms that converge to the optimal Q-matrix. In some sense one could argue that all of them (double Q, clipped, maxmin, averaged, weighted, ADDQ, etc.) are somewhat arbitrary choices from the set of all converging algorithms, none is the result of a rigorous derivation. Only Q-learning itself might be seen natural as it is the direct (but inefficient) stochastic counterpart of value iteration. There are no convincing theoretical arguments in the literature, and also no variants that are equally convincing over different environments. Clipped is perhaps a good example, it performs well in combination with SAC on MuJoCo but not on Atari - Q/DQL the opposite. For a new environment, the RL researcher has no other choice but to compare different variants plus some educated guessing. We have no better answer than saying that we add a new family of animals to the zoo of algorithms which is more flexible and combines the advantages of two other algorithms. The form of $\\beta$ we propose is the natural choice based on our theoretical observation, only the choice of constants (hyper parameters) is somewhat artificial. We added a much more extensive ablation study (see the repository) to show that the choice of hyperparameters in $\\beta$ is actually pretty harmless. Interestingly enough, the same choice of $\\beta$ improves QL/DQL on diverse settings as tabular, Atari, MuJoCo. \n\n* **Hyperparameter tuning**: To ensure fair comparison, we did not tune any hyperparameter and stick to the choices from stable baselines 3. We did not even try to optimise the choices of $\\beta$ and used our first choice for all experiments. Usually researchers tune their methods before publication, but our entire point is that the method is very robust. It is a harmless trick to improve distributional algorithms without effort.\n\n* **Deep Theory**: We would love to provide theory in the deep setting. But to be honest, that seems pretty hope less. Not only for our article, but we are not aware of any convincing result in the RL literature. \n\n* **Computational overhead**: ADDQ has no computational overhead compared to double distributional QL (the runtime is almost identical). The only difference is to compute $\\beta$ (a small finite sum), which compared to evaluating large NN is almost nothing. The computational effort mainly comes from distributional deep Q-learning, which is significantly more expansive (but more sample efficient) than ordinarly deep Q-learning.\n\n* **Failure cases**: We did not encounter failure cases (even though failure might be hard to judge). With the choice of $\\beta$, ADDQ works stably if either Q or double Q works reasonably well. In contrast, in situations with diverse randomness as our grid world example, ADDQ works much better than Q and double Q. One could interprete the MuJoCo examples as a failure. In this case clipping is much more effective than both Q and double Q (the negative bias of double Q is not enough) so a combination of Q and double Q has no chance to beat clipping. MuJoCo is more a failure of Q and double Q (ADDQ still improves both!) compared to clipping. From an advertisement perspective it might have been smarter to locally combine for MuJoCo the Q and the clipped estimator (algorithmically this is almost identical) but the current presentation is scientifically more honest. After all, in this paper we wanted to show how to improve Q and DQ by a combination of both.\n\n* **Implementation**: The implementation overhead is adding one line and changing two lines of code to existing (here: stable baselines 3) distributional code: Compute $\\beta$ from the distributions (i.e. compute a finite sum) and then change the double Q updates. That's it.\n\n* **Integration in other algorithms**: Yes, the main idea can be combined with other approaches in which an algorithm has a parameter that steers the over/underestimation *and* the parameter can be adapted on the fly. In that case we would suggest to locally change the parameter according to the sample variance. Here are two examples: (i) In TQC a number of top atoms is truncated. The number is a hyperparameter and must be chosen for every environment. We would suggest to chose the number of truncated atoms locally according to the sample variance. (ii) In randomized ensemble DQL we would suggest to make the number of chosen ensemble members for the updates locally dependent on the sample variance.", "claims_and_evidence": "The paper makes several strong claims regarding ADDQ's advantages:\n- Reduction of Overestimation Bias – Supported by a theoretical analysis using probability bounds.\n- Better Stability than QL and DQL – Demonstrated through experiments in various environments.\n- Improved Sample Efficiency – Shown via empirical comparisons in Atari and MuJoCo environments.\n\nWhile the theoretical analysis is compelling, some claims (e.g., optimality of the chosen weighting function) could be more rigorously justified with additional ablation studies.", "methods_and_evaluation_criteria": "The methodology is well-designed and aligns with the problem at hand:\n- The use of sample variance as an indicator of uncertainty is well-motivated.\n- The local weighting mechanism between QL and DQL is clearly explained.\n- The evaluation benchmarks (Atari, MuJoCo) are appropriate for demonstrating generalization.\n\nHowever, the choice of hyperparameters for β (the weighting factor) is somewhat heuristic. It would be valuable to analyze different settings of β to ensure robustness across environments.", "theoretical_claims": "The paper provides proofs of convergence for the ADDQ algorithm in tabular settings. The theoretical analysis is rigorous, but the following concerns arise:\n- The impact of function approximation (i.e., deep RL settings) is not fully addressed in the theoretical framework.\n- Some assumptions (e.g., independence of updates in DQL) may not hold in practical scenarios with deep learning.\n\nA discussion on these limitations and potential extensions would strengthen the theoretical contribution.", "experimental_designs_or_analyses": "Strengths:\n- Baseline comparisons include standard QL, DQL, and clipped QL, ensuring a fair evaluation.\n- RLiable evaluation metrics (probability of improvement) provide a robust statistical comparison.\n\nWeaknesses:\n- No ablation studies on the choice of β and its sensitivity to different environments.\n- No analysis of computational overhead (Does ADDQ introduce additional costs?).", "relation_to_broader_scientific_literature": "The paper is well-positioned in the reinforcement learning literature. The paper clearly distinguishes ADDQ from previous approaches.", "essential_references_not_discussed": "While the paper covers the key references, it could benefit from discussing:\n- More recent advances in Bayesian RL, which also address uncertainty estimation.\n- Work on uncertainty-aware RL methods beyond variance-based heuristics, such as Bootstrapped DQN (Osband et al., 2016).", "other_strengths_and_weaknesses": "Strengths:\n- Theoretical grounding: Provides mathematical insight into overestimation bias.\n- Practical implementation: Easily adaptable to existing DRL frameworks.\n- Empirical validation: Strong benchmark comparisons with standard methods.\n\nWeaknesses:\n- Limited ablation studies: The choice of β is not fully justified.\n- No computational cost analysis: Would ADDQ increase training time or memory usage?\n- Limited discussion on failure cases: When does ADDQ not work well?", "other_comments_or_suggestions": "- Provide more discussion on practical implementation (e.g., how easy is it to integrate ADDQ into existing RL libraries?).\n- Include an analysis of computational efficiency.", "questions_for_authors": "- How does ADDQ compare in terms of computational cost? Since it requires computing sample variances, does it introduce a significant overhead?\n- Why was β chosen heuristically rather than learned adaptively? Would an adaptive β (e.g., learned via meta-learning) improve performance?\n- How does ADDQ perform with function approximation errors? The theoretical results focus on tabular settings—how well do they generalize to deep RL?\n- Could ADDQ be combined with other overestimation reduction methods? For instance, can it be integrated with ensemble-based RL (e.g., Averaged-DQN)?", "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": "", "extra_scores": {"ethical_review_flag": "Flag this paper for an ethics review.", "ethics_expertise_needed": ["Other expertise"], "ethical_review_concerns": "Lack of *Impact Statements* section."}}, {"review_id": "50pQqFSnSu", "reviewer": "Reviewer_C9ok", "summary": "This paper proposes ADDQ, an adaptive distributional double Q-learning method that mitigates Q-value overestimation bias by locally adjusting update weights based on distributional uncertainty estimates. Built upon distributional RL frameworks (e.g., C51, QRDQN), ADDQ dynamically combines Q-learning and double Q-learning updates using sample variance information from return distributions. Theoretical analysis in a tabular bandit MDP quantifies overestimation bounds, and experiments across tabular, Atari, and MuJoCo environments demonstrate improved stability and performance compared to baseline methods.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "Dear reviewer, thank you very much for your careful reading and thoughts on our article! \n\n**Please check the anonymous repository https://anonymous.4open.science/r/ADDQ-B776 for figures addressing some of your thoughts.**\n\n**Weaknesses:**\n\n* **Ablation study**: We included a more comprehensive ablation study for $\\beta$, plotting many choices of $\\beta$ showing that the choice is relatively irrelevant. We also compare ADDQ to ensemble bootstrapped Q-learning, maxmin Q-learning, random ensemble double Q learning. We hope that is more convincing. Note that we only provide tabular comparisons as there is no benchmark implementation available for distributional EBQL/maxmin/REDQ.\n\n* **MuJoCo**: Our presentation of MuJoCo was not the smartest move from an advertisement point of view, we tried to keep the highest scientific standards and compare the same algorithmic idea over all experiments. For MuJoCo both Q and DQ estimators are clearly inferior to the clipped estimator (in contrast to Atari). The reason is that DQ does not substract enough positive bias, the main finding of the TD3 paper. The purpose of the experiment was to show that cleverly combining Q and DQ estimators (ADDQ) beates both ingredients Q and DQ. Of course, the combination of both won't beat clipped. Here is the but: Our main idea (using sample variances to locally adjust overestimation) is not restricted to combine Q and DQ, but this is the most natural setting for a presentation. In the same way one could use a locally adaptive mixing of Q (or double Q) and clipped Q to avoid too extreme underestimation of the clipped estimator.\n\n**Questions:**\n\n* You are totally right that the suggested **choice of $\\beta$** is somewhat arbitrary. There are plenty of stochastic approximation algorithms that converge to the optimal Q-matrix. In some sense one could argue that all of them (double Q, clipped, maxmin, averaged, weighted, ADDQ, etc.) are somewhat arbitrary choices from the set of all converging algorithms, none is the result of a rigorous derivation. Only Q-learning itself might be seen natural as it is the direct (but inefficient) stochastic counterpart of value iteration. There are no convincing theoretical arguments in the literature, and also no variants that are equally convincing over different environments. Clipped is perhaps a good example, it performs well in combination with SAC on MuJoCo but not on Atari - Q/DQL the opposite. For a new environment, the RL researcher has no other choice but to compare different variants plus some educated guessing. We have no better answer than saying that we add a new family of animals to the zoo of algorithms which is more flexible and combines the advantages of two other algorithms. The form of $\\beta$ we propose is the natural choice based on our theoretical observation, only the choice of constants (hyper parameters) is somewhat artificial. We added a much more extensive ablation study (see the repository) to show that the choice off hyperparameters in $\\beta$ is actually pretty harmless. Interestingly enough, the same choice of $\\beta$ improves QL/DQL on diverse settings as tabular, Atari, MuJoCo. \n\n* **$b^{A/B}(s,a)$ notation**: Thanks for your comment, we will improve the notation to make readability easier.\n\n* **$\\nu$ from Algorithm 2**: Thanks for your careful reading! This is a typo, and was realised only one hour after submission. The implementation is correct.\n\n* **Theorem 3.1**: The theorem holds for **arbitrary** such sequences, we will add the word \"arbitrary\". You are right about your question, it is unclear how to check equality in the limit. The easiest way (and this is what we do) is to chose $\\beta^A_t=\\beta^B_t$ for all $t$ so the condition is trivially satisfied.\n\n* **Compilation error**: Thanks for spotting!", "claims_and_evidence": "Claims:\n- Overestimation bias in Q-learning can be mitigated by locally adapting updates using distributional variance.\n- ADDQ integrates seamlessly into existing distributional RL algorithms with minimal code changes.\n- The method converges theoretically and outperforms QL/DQL in stochastic and high-uncertainty environments.\n\nEvidence:\n- Proposition 2.1 derives a lower bound for QL overestimation in a bandit MDP, linking bias to reward variance and sample size.\n- Theorem 3.1 proves ADDQ’s convergence under Robbins-Monro conditions.\n- Experiments on grid worlds, Atari, and MuJoCo show ADDQ reduces bias and achieves higher scores than QL, DQL, and clipped variants (Figures 2, 4-5).", "methods_and_evaluation_criteria": "Methods:\n- Distributional RL: Uses return distribution variances to identify uncertain state-action pairs.\n- Adaptive Weighting: Adjusts interpolation weights ($\\beta$) between QL and DQL updates based on relative sample variances.\n- Algorithm Integration: Modifies C51 and QRDQN with dual networks and adaptive targets.\n\nEvaluation Criteria:\n- Bias Reduction: Measured via Q-value deviations in tabular settings (Figure 2).\n- Performance: Normalized scores and probability of improvement (RLiable plots) across 10 Atari and 5 MuJoCo environments.\n- Stability: Comparison of failure rates and learning curve variances.", "theoretical_claims": "- Proposition 2.1 provides a tight lower bound for QL overestimation in Gaussian bandits, highlighting the role of variance and action count. While insightful, the analysis assumes cyclic exploration and ignores function approximation.\n- Theorem 3.1 guarantees convergence under symmetric $\\beta$ schedules. The proof leverages stochastic approximation theory but does not address deep RL settings with neural networks.", "experimental_designs_or_analyses": "Strength:\n- Comprehensive evaluation across tabular, Atari, and MuJoCo benchmarks.\n- Inclusion of RLiable metrics (e.g., interquartile mean, probability of improvement) enhances statistical rigor.\n\nWeakness:\n- MuJoCo experiments show limited gains (even worse) compared to clipped QRSAC , but this is not deeply analyzed.\n- Ablation studies for $\\beta$ thresholds (Section B.2) are preliminary; sensitivity to hyperparameters is unclear.", "relation_to_broader_scientific_literature": "The main results of this paper could contribute to applications and methodologies in robust RL learning and improve the performance of learning.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "NA", "questions_for_authors": "- I suggest to add detailed  discussion on the choice of $\\beta$ considering its essential role in this paper , the threshold to determine $\\beta$ seems careless and randomly. You must tell readers how to set the threshold by some criterion instead of using some fixed value.\n- I believe the $b^{A/B}(s,a)$ in left panel of line 247 is aligned with that in left panel of line 234, but you also  have claimed $b^{A/B}(s,a)$ in left panel line 239, which would cause a confusion for readers.\n- I wonder the $\\nu \\leftarrow \\beta\\eta^{B}(s^{\\prime,a^*})+(1-\\beta)\\eta^{A}(s^{\\prime},a^*)$ in Algorithm 2 is correct? It seems not akin to $\\beta$ defined in equation (1).\n- It is not clear how $(\\beta_t^A)_{t\\in\\mathbb{N}}$ and its counterpart\n in Therorem 3.1 are defined and what is the relationship between them and  $\\beta$ in Algorithm 2. I also wonder how to guarantee  the two $\\beta$ would meet in limit behavior in your algorithm.\n- Compile error occurs in line 1537.", "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": "", "extra_scores": {}}, {"review_id": "uCBXzH308j", "reviewer": "Reviewer_idYs", "summary": "The authors propose ADDQ, a distributional reinforcement learning (DRL) algorithm which adaptively combines two RL algorithms to combat overestimation. Specifically, sample variances from DRL are used to adaptively balance the updating scheme of an algorithm with a tendency to overestimation (e.g. Q-Learning) with one with a tendency to under-estimation (e.g. Double Q-Learning). The authors provide theoretical analysis on a simple bandit MDP as well as an tabular illustrative practical analysis in a gridworld setting in comparison to distributional QL and distributional DQN, as well a comparison to C51 and QRSAC on Atari and MuJoCo benchmarks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Dear reviewer, thank you very much for your careful reading and thougths on our article!\n\n**Please check the anonymous repository https://anonymous.4open.science/r/ADDQ-B776 for figures addressing some of your thoughts.**\n\n**Bandit example:**\n* We agree with your summary about the main contribution of the article and the discussion of the bandit example. We would like to stress that this simplified theoretical contribution is  more reasonable than most of what appeared in the past DQL literature. In past theoretical contributions the max estimator is typically studied for IID random variables or for \"chain MDPs\" without any actions. Also the step-sizes are not very unrealistic even though practitioners like to use other schedules. The Robbins-Monroe conditions require asynchronous (that's why number of visits) step-sizes of the order $1/n^p$, for $p\\in (1/2,1]$ so choosing $p=1$ is not particularly unrealistic. Our Lemma A.1 sheds light on the general situation - the simplified Q-learning analysed is a lower bound mechanism, the general situation is even worse. What is behind the Gaussian estimate is the following thought: The overestimation error of the max is governed by the worst single overestimation, thus, distributing the exploration evenly makes equally good estimators or, equivalently, minimises the worst single overestimation. We actually believe, and we are currently working on it, that the bandit MDP computation combined with Lemma A.1 can also shed light on the overestimation of general  MDPs. A backwards induction (dynamic programming) from terminal states for stochastic shortest paths problems (or the random geometric time-horizon for discounted MDPs) should allow to derive lower bounds for the overestimation also for general Q-learning exploration on general MDPs. It might be interesting to highlight that our simplified computation shows clearly where the difficulties of computations in distributional Q-learning come from. The update mechanism naturally combines sums and maxima of random variables, so it lives in the intersection of extremal value theory and the central limit theorem. Since there are no distributions that are sum-stable and max-stable at the same time, there is no shortcut in exact probabilistic computations.\n* We now performed a simulation of the bandit example to make our theoretical point clearer.\n\n**Experimental design:**\n* We now compare ADDQ to ensemble bootstrapped Q-learning, maxmin Q-learning, and random ensemble double Q learning. The difficulty of the example (very different local randomness) shows clearly the local overestimation control of ADDQ over all other methods. Note that we only provide tabular comparisons on the delicate grid world example as there is no benchmark implementation available for distributional EBQL/maxmin/REDQ.\n\n\nWe also plotted the relative sample variances (and, thus, the choice of $\\beta$) for the non-trivial grid world example in order to make the point clear: our algorithm automatically spots the problematic state-action pairs to mitigate the overestimation.\n\n**References:**\n* Thank you very much for providing additional literature, which we will certainly include in a revised version! While we believe that our approach is not directly related to approaches using uncertainty Bellmann, we agree that ACC is much closer in spirit. This is a very nice paper, thanks for sharing. As you point out, the approach resembles of what we sketched under future research for TQC. The way ACC is formulated (using the replay buffer), ACC does not control overestimation locally on state-action level but globally (averaging over state-action pairs from the replay buffer). This way the algorithm would struggle for instance on our delicate grid world example just as much as maxmin and ensemble methods. In the tabular situation this might be adjusted, with function approximation probably not. For ADDQ we use that the distributions (thus variances) are learned on state-action level.\n\n**Other comments:**\n* We will improve your minor comments, thanks!\n* We included plots to visualize the choices made by $\\beta$, thanks!\n\n**Questions:**\nThanks for reading carefull, yes, this can be seen as the core contribution. From statistical theory the observation is somewhat obvious (large variance means large sample variance, means large overestimation bias for max estimator) and this was essentially worked out for the bandit MDP and then translated in $\\beta$ for ADDQ. Our intuition then uses dynamic programming (backwards induction) to bootstrap the idea up the decision tree. We added plots for our delicate grid world example for a state-action pair facing towards the stochastic region. The plots show that relative sample variance and overestimation are both large and decrease together (very slowly for Q-learning, much faster for ADDQ). In contrast, for less vulnerable state-action pairs both overestimation and relative sample variances are much smaller.", "claims_and_evidence": "The authors claim that they “show theoretically how distributional RL helps the agent identify the need for overestimation control”. This claim, or rather the connection between the utilized sample variance (from distributional RL) and the actual overestimation is crucial for the method, as “overestimation regularization” is applied whenever sample variance is high for a given action wrt. the other actions in a state. Thus this connection should, in my opinion, be shown to the reader clearly and optimally illustrative.\nThe main body of text does contain Proposition 2.1 and 2.2 related to this claim. \nProposition 2.1 states that the overestimation (lower bound of bias) is connected, among other things, to σ and N.\nThe Proposition 2.2. states that, among other things, the sample variance is decreasing with number of updates N to a given action and is proportional to σ. Thus the sample variance and the overestimation are both connected to the variance σ, and via that to each other.\n\nHowever, corresponding proof for Proposition 2.2., contained in A.2, makes the assumptions that  “all actions in s1 are explored N times before bootstrapping the estimates to s0” and that “the standard 1 /#visits -step-size schedule” is used, which appears rather unrealistic. Further, in practice, bootstrapping and corresponding overestimation is typically propagated over multiple states.\n\nI suggest making this relation more apparent and clear, and perhaps include a practical analysis on the bandit task which shows the overestimation bias in relation to the sample variance and how ADDQ, by adapting β, alleviates the problem at hand.", "methods_and_evaluation_criteria": "The proposed method and evaluation of said method appears reasonable and convincing, assuming that the sample variance can be used to identify the need for overestimation control.\nHowever, I feel that a broader comparison, especially to uncertainty-driven RL, would paint a clearer picture with respect of to the algorithms performance. More on that in “Experimental Designs or Analyses”.", "theoretical_claims": "I had a look at the proofs provided in the appendix but did not check all of them.", "experimental_designs_or_analyses": "The experimental design and analysis is sound and I found no issues. However, I’d suggest adding more related algorithms for comparison.\nThere has been a large body of literature regarding uncertainty estimation in (offline) Reinforcement Learning, often using ensemble methods.\nThe authors state that “Ensemble methods are promising in theory (assuming independent ensembles) but more problematic for deep RL as storage problems force ensembles to be parametrized by the same neural network.”. However, there have been ensemble methods with hundreds of ensembles with distinct networks [1].\nAs it appears quite related, integrating an uncertainty-based method into the comparison could help giving an insight into the performance of the proposed method.\nFor example [2] tries to find a balance between over and underestimation using uncertainty estimates.\nFurther, Maxmin Q-learning [3], which the authors also mention in the introduction, combines the update rule of QL with DQL an should be a simple baseline to add.\n\n[1] An, G., Moon, S., Kim, J. H., & Song, H. O. (2021). Uncertainty-based offline reinforcement learning with diversified q-ensemble. Advances in neural information processing systems, 34, 7436-7447.\n\n[2] Li, S., Tang, Q., Pang, Y., Ma, X., & Wang, G. (2021). Balancing value underestimation and overestimation with realistic actor-critic. arXiv preprint arXiv:2110.09712.\n\n[3] Lan, Q., Pan, Y., Fyshe, A., & White, M. Maxmin Q-learning: Controlling the Estimation Bias of Q-learning. In International Conference on Learning Representations.", "relation_to_broader_scientific_literature": "For me, this paper is related to many works in the field of uncertainty-based Reinforcement Learning. While it is also mentioned in the introduction that “overestimation should be addressed particularly in state-action regions with high uncertainty”, the authors disregard the field of uncertainty-based RL and instead only put a focus on ensemble methods.\nIn the field of uncertainty-based RL many works try to reduce Q-values for uncertain states [1, 2, 3, 4], which is conceptually similar to “putting more weight on DQN” for high variance samples as proposed here. \n\n[1] Wu, Yue, et al. \"Uncertainty Weighted Actor-Critic for Offline Reinforcement Learning.\" International Conference on Machine Learning. PMLR, 2021.\n\n[2] Ghasemipour, K., Gu, S. S., & Nachum, O. (2022). Why so pessimistic? estimating uncertainties for offline rl through ensembles, and why their independence matters. Advances in Neural Information Processing Systems, 35, 18267-18281.\n\n[3] Bai, C., Wang, L., Yang, Z., Deng, Z., Garg, A., Liu, P., & Wang, Z. (2022). Pessimistic bootstrapping for uncertainty-driven offline reinforcement learning. arXiv preprint arXiv:2202.11566.\n\n[4] Li, S., Tang, Q., Pang, Y., Ma, X., & Wang, G. (2021). Balancing value underestimation and overestimation with realistic actor-critic. arXiv preprint arXiv:2110.09712.", "essential_references_not_discussed": "In [1] an adaptive balance (ACC), using a balance controlling parameter β, between over- and under-estimation in TQC is proposed. Instead of deriving β from the sample variance as in this work, Monte-Carlo Rollouts area used. The strong similarity between ACC and ADDQ in my opinion requires discussing said similarity. Further, ACC is evaluated on MuJoCo which indicates that it could be also used for comparison in this work's experiments. Especially since a combination with TQC is listed as promising future work, it appears especially important to discuss and compare to [1].\n\n[1] Dorka, N., Welschehold, T., Bödecker, J., & Burgard, W. (2022). Adaptively calibrated critic estimates for deep reinforcement learning. IEEE Robotics and Automation Letters, 8(2), 624-631.\n\nFurther, many related works in “Relation to Broader Scientific Literature” would be suitable for discussion, however I would not refer to those as essential.", "other_strengths_and_weaknesses": "Weaknesses as discussed above.\n\nStrengths:\n- Mostly self-contained\n- General writing style\n- Extensive experiments\n- Use of RLiable library for probability of improvement", "other_comments_or_suggestions": "- Line 159, “[(“ brackets can be removed.\n- Function class projection, introduced in line 128 (right) and Algorithm 1 could benefit from a proper introduction to be more self-contained.\n- Line 187 left, could use an inline citation.\n- Formatting issues with page 18, 24,26 in Appendix, Figures too large.\n- In Figure 4 and 5, the color coding of the RLiable plots does not match the color coding of the evaluation progress plot. Setting the colors to match could ease readability.\n- Perhaps figure 2. could benefit from a graph which shows what fraction of updates used which beta values over time, such that the adaptivity of the proposed method can be observed.", "questions_for_authors": "Could you illustrate your intuition for the connection between sample variance and the overestimation bias, also for more realistic settings than the one used for the proofs? As is, it remains unclear whether sample variance is a good proxy for measuring overestimation, which is the main contribution of this paper. If this can be justified by more extensive analysis and experiments, I am willing to increase my score.\n\n--\nThe rebuttal addressed most of my concerns and I increased my score accordingly.", "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": "", "extra_scores": {}}, {"review_id": "xEJDV1gXZ7", "reviewer": "Reviewer_SxzX", "summary": "Based on double Q-learning, this paper proposes a set of theoretical and practical solutions to reduce the bias of Q value estimation. The paper conducts some experiments in Atari, mujoco and table environments. Some results have demonstrate their effectiveness.\n\n## Update after rebuttal\nDuring the rebuttal, the additional experiments greatly increase the persuasiveness of the paper and address my main concern, so I am very happy to update my evaluation/rate to weak accept.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Dear reviewer, thank you very much for your careful reading and thougths on our article! \n\n**Please check the anonymous repository https://anonymous.4open.science/r/ADDQ-B776 for figures addressing some of your thoughts.**\n\n**Methods and evaluation criteria:**\n* The metrics that you claimed to be missing are given in the Appendix, please have another look at Appendix D.\n\n**Theoretical claims:**\n* The experiments are not designed to validate theoretical claims. In opposite, the theoretical results motivate the design of the ADDQ algorithm. Nonetheless, since it is an interesting remark, to answer your question we now provide simulations for the bandit MDP as well. Please check the linked repository above for the plots.\n* A full convergence proof is indeed provided in the tabular setup, in the RL literature there seems generally little hope to provide convergence proofs for function approximation with neural networks in non-trivial settings.\n\n**Relation to literature:**\n* We now added comparisons (see the link above for the plots) with several algorithms: ensemble bootstrapped Q-learning, maxmin Q-learning, and random ensemble double Q learing. Note that we only provide tabular comparisons as there is no benchmark implementation available for distributional EBQL/maxmin/REDQ. \n* Our presentation of MuJoCo was not the smartest move from an advertisement point of view, we tried to keep the highest scientific standards and compare the same algorithmic idea over all experiments. For MuJoCo both Q and DQ estimators are clearly inferior to the clipped estimator (in contrast to Atari). The reason is that DQ does not substract enough positive bias, the main finding of the TD3 paper. The purpose of the experiment was to show that cleverly combining Q and DQ estimators (ADDQ) beates both ingredients Q and DQ. Of course, the combination of both won't beat clipped. Here is the but: Our main idea (using sample variances to locally adjust overestimation) is not restricted to combine Q and DQ, but this is the most natural setting for a presentation. In the same way one could use a locally adaptive mixing of Q (or double Q) and clipped Q to avoid too extreme underestimation of the clipped estimator.\n* This paper contributes to a fundamental method in RL, Q-learning. The goal is not specifically to solve Atari or MuJoCo problems, these examples serve for illustration purposes as we cannot prove much in deep RL. Comparing to different methods can be interesting for general curiosity, but does not serve the main purpose of this article which is to improve QL/DQL with very little extra effort.\n\n**Weaknesses:**\n* Again, please have a quick look at Appendix D for the metrics and for MuJoCo to our comment above.\n\n**Comments:**\n* We agree, more theory on convergence rates, etc. would be very desirable. Our paper (just as the entire RL literature away from unrealistic simple situations) does not provide insight.\n* Environmental rules of our research team do not allow to run all Atari examples. In fact, there is not much to learn from more Atari examples and the computational/environmental effort is quite big. That's why we used the RLiable metrics to get as much information as possible from the runs. We know that QL and DQL work reasonably well, so there is no reason to expect ADDQ to perform weaker. It would be much more interesting to attack complicated environments on which (distributional) deep Q-learning fails. But here we run in the usual problem of our community to have too few very different benchmark examples.\n\n**Questions:**\n* Question 1: See Appendix D\n* Question 2: The performance on MuJoCo is not bad. As expected, the algorithm improves the two base algorithms using Q or double Q estimators. It cannot be expected to beat the clipped estimator and we included the example for completeness.", "claims_and_evidence": "The paper mentions that it combines Q-learning and Double Q-learning through direct linear weighting, proves its convergence, and conducts experiments in environments such as tables and Atari to prove its effectiveness.\nIn the experiment, the paper demonstrates the effectiveness of the proposed method with DDQN and  SAC. It is worth mentioning that it only considers a small number of selected tasks on the Atari task, which may not be convincing enough. It is also difficult to distinguish the performance from the baseline method on the Mujoco task, which may greatly reduce the persuasiveness of the paper.", "methods_and_evaluation_criteria": "The metrics used in the experiment part of the paper are final score, final reward, etc. However, the metrics commonly used in Atari tasks such as IQM and human normliazed score are missing, making it difficult to evaluate the overall performance of the algorithm.", "theoretical_claims": "The paper seems to have some theoretical motivations that are not well validated in the experiment. In addition, the paper may benefit from more specific discussion and proof of convergence.", "experimental_designs_or_analyses": "The overall design of the experimental part is reasonable, but at least on the Atari task, it lacks sufficient comprehensive analysis metrics, such as IQM, HNS, etc. In addition, the paper also lacks discussion and comparison on the core contribution (i.e., reducing the evaluation variance of Q) in the experiment.", "relation_to_broader_scientific_literature": "Bias control in Q-learning is an issue worth discussing. The paper also applies its improvements to existing methods such as SAC and DDQN, but due to the lack of sufficiently convincing experiments and the fact that in some experiments (such as mujoco)  the proposed method is even far below the baseline method,  the effectiveness of proposed method is thus less convincing.", "essential_references_not_discussed": "I think the paper would at least benefit from comparison with some recent SOTA methods on Atari tasks, such as MEME, EfficientZero, etc.", "other_strengths_and_weaknesses": "The core contribution of the paper is to propose a simple and easy-to-use solution to reduce Q value over-estimation.\n\nThe main disadvantage of the paper is that the experimental part does not prove the  effectiveness of the proposed method. First, the number of Atari tasks is small, and there are no comprehensive metrics such as IQM and Mean HNS. In addition, the proposed method on the Mujoco task is even far surpassed by the baseline method, which makes it difficult to prove the effectiveness of the algorithm.", "other_comments_or_suggestions": "The paper may benefit from discussing the more  experimental and theoretical proof of the proposed method on the convergent behavior and convergence speed of the algorithm. In addition, more Atari tasks and more comprehensive evaluation metrics may enhance the persuasiveness of the paper.", "questions_for_authors": "1. Have the authors considered showing more performance on Atari tasks, such as more tasks, more comprehensive metrics such as IQM[1], etc.\n2. Could the author give a detailed introduction on how the proposed method improves the efficiency of the algorithm and why the performance on the mujoco task is not good?\n\n[1] Deep Reinforcement Learning at the Edge of the Statistical Precipice", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviews alone would make this a very borderline paper, but actually evaluating the paper directly, it has strengths and weaknesses that largely balance out. Focusing on the essentials, the work motivates an insight into addressing over-estimation bias, provides a method to do so, and demonstrates that it is effective. However, when it comes to how well this translates into policy performance the story is much more mixed. Here the results are certainly not bad, but nor are they especially exceptional. That said, they are thorough and rigorous, and as is the overall treatment of the research problem itself, both of which should count for something.

So, while I think this is a paper I would be more supportive of at a different venue, I think it on balance teaches me more about the nature of the RL problem than a fair swath of the accepted RL papers at ICML.
Decision: Accept (poster)