Adaptive Ensemble Q-learning: Minimizing Estimation Bias via Error Feedback
Authors: Hang Wang
Sen Lin
Junshan Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Q-learning
Ensemble method
Adaptive control
Function approximation

Abstract: The ensemble method is a promising way to mitigate the overestimation issue in Q-learning, where multiple function approximators are used to estimate the action values. It is known that the estimation bias hinges heavily on the ensemble size (i.e., the number of  Q-function approximators used in the target), and that determining the 'right' ensemble size is highly nontrivial, because of the time-varying nature of the function approximation errors during the learning process. To tackle this challenge, we first derive an upper bound and a lower bound on the  estimation bias, based on which the ensemble size is  adapted to drive the bias to be nearly zero, thereby coping with the impact of the time-varying approximation errors accordingly. Motivated by the theoretic findings, we advocate that the ensemble method can be combined with Model Identification Adaptive Control (MIAC) for effective ensemble size adaptation. Specifically, we devise Adaptive Ensemble Q-learning (AdaEQ), a generalized ensemble method with two key steps: (a) approximation error characterization which serves as the feedback for flexibly controlling the ensemble size, and (b) ensemble size adaptation tailored towards minimizing the estimation bias.   Extensive experiments are carried out to show that AdaEQ can  improve the learning performance than the existing methods for the MuJoCo benchmark.

Adaptive Ensemble Q-learning: Minimizing Estimation Bias via Error Feedback
Hang Wang Arizona State University Tempe, Arizona, USA hwang4420asu.edi
Sen Lin Arizona State University Tempe, Arizona, USA slin708asu. edu
Junshan Zhang
Arizona State University Tempe, Arizona, USA Junshan Zhanggasunnuuu..aa edu
Abstract
The ensemble method is promising way to mitigate the overestimation issue in Q-learning, where multiple function approximators are used to estimate the action values. It is known that the estimation bias hinges heavily the ensemble size (i.e., the number of Q-function approximators used in the target), and that determining the 'right' ensemble size is highly nontrivial, because of the time-varying nature of the function approximation errors during the learning process. To tackle this challenge, we first derive an upper bound and lower bound on the estimation bias, based on which the ensemble size is adapted to drive the bias be nearly zero, thereby coping with the impact of the time-varying approximation errors accordingly. Motivated by the theoretic findings, we advocate that the ensemble method can be combined with Model Identification Adaptive Control (MIAC) for effective ensemble size adaptation. Specifically, we devise Adaptive Ensemble Q-learning (AdaEQ), generalized ensemble method with two key steps: (a) approximation error characterization which serves as the feedback for flexibly controlling the ensemble size, and (b) ensemble size adaptation tailored towards minimizing the estimation bias. Extensive experiments are carried out to show that AdaEQ can improve the learning performance than the existing methods for the MuJoCo benchmark.
Introduction
Thanks to recent advances in function approximation methods using deep neural networks (20]. Q-learning 35 has been widely used to solve reinforcement learning (RL) problems in a variety of applications, e.g., robotic control 23 13. path planning [1] 24 and production scheduling
34 21.
Despite the great success, it is well recognized that Q-learning may suffer from the notorious
[0] 33]. which would significantly impede the learning efficiency, overestimation bias 220] 32
Recent work I indicates that this problem also persists in the actor-critic setting. To address this issue, the ensemble method [6 26 7 has emerged as promising solution in which multiple Q-function approximators are used to get better estimation of the action values. Needless to say, the ensemble size, i.e., the number of Q-function approximators used in the target, has intrinsic impact on Q-learning. Notably, it is shown in (6, [7] that while a large ensemble size could completely remove the overestimation bias, may go the other extreme and result in underestimation bias and unstable training, which is clearly not desirable. Therefore, instead of simply increasing the ensemble
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

size to mitigate the overestimation issue, a fundamental question to ask is:" Is it possible to determine the right ensemble size on the fly so as to minimize the estimation bias?"
Some existing ensemble methods 2 19 adopt a trial-and-error strategy to search for the en- semble size, which would be time-consuming and require lot of human engineering for dif- ferent RL tasks. The approximation error of the Q-function during the learning process plays nontrivial role in the selection of the ensemble size, since directly impacts the Q-target es- timation accuracy. This however remains not well understood. In particular, the fact that the approximation error is time-varying, due to the iterative nature of Q-learnnng [6 5], gives rise to the question that whether fixed ensemble size should be used in the learning process. To answer this question, we show in Section 2.2 that using a fixed ensemble size is likely to lead to either overestimation or underestimation bias, and the bias may shift between overestimation and underestimation because of the time-varying approximation error, calling for an adaptive ensemble size so as to drive the bias close to zero based on the underlying learning dynamics.
Thus motivated, in this work we study effective ensemble size adaptation to minimize the estimation bias that hinges heavily on the time-varying approximation errors during the learning process. To this end. we first characterize the relationship among the ensemble size. the function approximation errors, and the estimation bias, by deriv- ing an upper bound and a lower bound on the estimation bias. Our findings reveal that the ensemble size should be selected adaptively in a way to cope with the impact of the time-varying approximation errors. Building upon the theoretic results, we cast the estimation bias minimization as adaptive control problem where the approximation error during the learning process is treated as the control object, and the ensemble size is adapted based on the feedback of the control output, i.e., the value of the approximation error from the last iteration. The key idea in this approach is inspired from the classic Model Identification Adaptive Control (MIAC) framework B3 25), where at each step the current system identification of the control object is fed back to adjust the controller, and consequently a new control signal is devised following the updated control law.
Ensemble Size Adaptation
Feedback ees
Approsimation Erros Quantification
Ensemble Q-learning
Target
Q-value
Update Q-function Approximators-
Figure 1: A sketch of the adaptive en- semble Q-learning (AdaEQ).
One main contribution of this work lies in the development of AdaEQ, a generalized ensemble method for the ensemble size adaptation, aiming to minimize the estimation bias during the learning process. Specifically, the approximation error in each iteration is quantified by comparing the difference between the Q-estimates and the Monte Carlo return using the current learned policy over testing trajectory [2]]1]], Inspired by MIAC, the approximation error serves as the feedback to adapt the ensemble size. Besides, we introduce a 'tolerance' parameter in the adaptation mechanism to balance the control tendency towards positive or negative bias during the learning process. In this way, AdaEQ can encompass other existing ensemble methods special cases, including Maxmin [17]. by properly setting this hyperparameter. A salient feature of the bhedback-adaptatte used effectively in conjunction with both standard Q-learning (22 and actor-critic methods [8] IT]. Experimental results on the continuous-contre MuloCo benchmark [30 show that AdaEQ is robust to the initial ensemble size in different environments, and achieves higher average return, thanks to keeping the estimation bias close to zero, when compared to the state-of-the-art ensemble methods such as REDQ 6 and Average-DQN
mechanism is that it can be
Related Work. Bias-corrected Q-learnngg 18 introduces the bias correction term to reduce the overestimation bias. Double Q- Q-learning is proposed in [3) to address the overestimation issue in vanilla Q-lcarning, by leveraging two independent Q-function approximators to estimate the maximum Q-function value in the target. S-DQN and S-DDON use the softmax operator instead of the max operator to further reduce the overestimation bias 27]. Self-correctigg Q-learning aims to balance the underestimation in double Q-learning and overestimation in classic Q learning by introducing a new self-correcting estimator (38). Weighted Q-learning proposes a new estimator based on the weighted average of the sample means, and conducts the empirical analysis in the discrete action space []] Weighted Double Q-learning (37] uses the Q-approximator together with balance the overestimation and underestimation bias. Nevertheless,
the double Q-approximator acquiring independent approximators is often intractable for large-scale tasks. To resolve this issue, the Twin- Swin-Delayed Deep Deterministic policy gradient algorithm (TD3) [9] and Soft -ctor-Critic
2

---

(SAC) I have been devised to take the minimum over two approximators in the target network. Along a different avenue, the ensemble-basee methods generalize double Q-learning correct the overestimation bias by increasing the number of Q-function approximators. Particularly, Average- DQN takes the average of multiple approximators error, and Random Ensemble Mixture (REM) [ estimates the target value using the random convex combination of the approximators. completely eliminate the overestimation bias. Most recently, Maxmin Q-learning [17] defines proxy Q-function by choosing the minimum Q-value for each action among all approximators. Similar to Maxmin, Random Ensembled Q-learning (REDQ) [6] formulates the proxy Q-function by choosing only a subset the ensemble. Nevertheless, both Maxmin and REDQ use a fixed ensemble size. In this study, we introduce adaptation mechanism for the ensemble size to drive the estimation bias to be close to zero, thereby mitigating the possible overestimation and underestimation issues.
the target to reduce the overestimation
is worth noting that both Average-DQN and REM cannot
2 Impact of Ensemble Size on Estimation Bias
2.1 Ensemble Q-learning
As is standard, consider a Markov decision process (MDP) defined by the tuple (S,A,P,r, where S and A denote the state space and the action space, respectively. P(s'|s; S x x [0, denotes the probability transition function from current state to the next state s' by taking action a E A, and r(s, a): S x + R is the corresponding reward. y E (0, 1] is the discount factor. At each step f, the agent observes the state 8t, takes an action a, following policy S + A, receives the reward rt. and evolves to a new state 8t+1- The objective is to find an optimal policy " to maximize the discounted return R = Ei=0 7'rz.
By definition, Q-function the expected return when choosing action state s and following with the policy æ: Q* = E E 7 7're(8;, a2) (5) 8, Gg = a). Q-learning is an off-polic value-hased method that aims at learning the optimal Q-function Q" S x X + I, where the optimal Q-function is a fixed point of the Bellman optimality equation 44]
TQ" a) = rr(s,)) a) + + [maxa (" "d))a
Given transition sample (s, r, s'),, the Bellman operator can be employed to update the Q-function as follows:
( a) < (1 (s) + az, y = r + ma a')
where a is the step size and y is the target. Under some conditions, Q-learning can converge to the optimal fixed-point solution asymptotically [31]. In deep Q-learning, the Q-function is approximated by a neural network, and it has been shown (33 that the approximation error, amplified by the max operator in the target, results in the overestimation phenomena. One promising approach address this issue is the ensemble Q-learning method, which is the main subject of this study.
The Ensemble Method. Specifically, the ensemble method maintains N separate approximators Q².Q" ......... QN of the Q-function, based on which a subset of these approximators is used to devise a proxy Q-function. For example, in Average-DON DDN [2], the proxy Q-function is obtained by computing the average value over all N approximators to reduce the overestimation bias:
(-ye(-) = N.N Q'(-)
However, the average operation cannot completely eliminate the overestimation bias, since the average of the overestimation bias is still positive. To tackle this challenge, Maxmin [17 and REDQ 66] take the 'min' operation over a subset M size M) of the ensemble:
(3) The target value in the ensemble-based Q-learning is then computed as y r + ma Quroxy, It worth noting that in the existing studies, the in-target ensemble size M, pre-determined for a given environment, remain fixed in the learning process.
Quonay (-) mingeM Q'(-).
2.2 An Illustrative Example
It is known that the determination of the optimal ensemble size is highly nontrivial, and a poor choice of the ensemble size would degrade the performance of ensemble Q-learning significantly [7]. As mentioned earlier, it is unclear priori if a fixed ensemble size should be used in the learning process.
3

---

State action Valoo
action action
Estiasiion Ereor
Olk 40
State
State
State
State
(a) Function approxima- (b) Five function approxi- tion.
(c) Ensemble via 'min' op- (d) Estimation error.
mators.
erator.
Figure 2: Illustration of estimation bias in the ensemble method. (a) Each approximator is fitted to the noisy values (green dots) the sampled states independently. (b) Five Q-function approximators obtained for both actions (green lines and blue lines). (c) Apply the min operator over M (M = 3) randomly selected approximators to obtain proxy approximator for each action. (d) The estimation error is obtained by comparing the underlying true value (purple line in (a)) and the target value using the proxy approximator.
Estination Baas
Adaptive Ensemble
Estinnation fiom Blus
Ad Ensemble
0
20
12:
18
18
Approxination Error
(b) Estimation bias vs. numbers actions. Number of Actions
(a) Estimation bias vs. T.
Figure 3: Illustration of overestimation and underestimation phenomena for different ensemble sizes.
In what follows, we use an example to illustrate the potential pitfalls in the ensemble methods by examining the sensitivity of the estimation bias to the ensemble size 66 17].
Along the same line as 33), we consider an example with real-valued continuous state space. In this example, there are two discrete actions available at each state and the optimal action values depend only on the state, ie.. each state both actions result in the same optimal value (s, +). which is assumed to be Q" (s.-) sin(s). Figure demonstrates how the ensemble method is carried out in four stages:
(I) For each Q-function approximator Q' 1,2, 5, we first generate 10 noisy action-value samples independently (green dots in Figure 2(a)) Let et (s, denote the approximation error Q':
(4) where 7, 24, 7) models the approximation error distribution for the i-th approximator, Note that the assumption on the uniform error distribution is commonly used to indicate that both positive and negative approximation error are possible in Q-function approximators
=(ssa)=Q0(( + (s,aa,,, with el(s,a) ~ U((T(, 7s),
29
(II) Next, Figure 2(b) illustrates the ensemble (N = 5) of approximators for two actions, where each approximator is 6- dedgre polynomial that fits the noisy values at sampled states.
(III Following the same ensemble approach in 6 17], we randomly choose M approximators from the ensemble and take the minimum over them to obtain proxy approximator for each action, resulting in the dashed lines in Figure 2(c)
(IV) Finally, the maximum action value of the proxy approximator is used as the target to update the current approximators, To evaluate the target value estimation error, Figure 2 depicts the difference between the obtained target value and the underlying true value when using different ensemble size M. As B3,, we utilize the average estimation error (i.e., estimation bias) to quantify the performance of current approximators. For example, when the ensemble size M = 2, the red line above zero for most states, implying the overestimation tendency in the target. Clearly, Figure 2(d) indicates that the estimation bias is highly dependent on the ensemble size, and even a change of M can lead the shift from overestimation to underestimation. Since the Q-function approximation error of each approximator changes over time in the training process [5] (examples for this phenomenon

---

can be found in Appendix B.3), we next analyze the impact of the ensemble size on the estimation bias under different approximation error distributions. As shown in Figure [(a) with a fixed ensemble size M, the estimation bias may shift between positive and negative and be 'dramatically" large for some error distributions. In light of this observation, departing from using a fixed size, we advocate to adapt the in-target ensemble size, e.g., set M = 4 when the noise parameter > 1.5 and M 3 otherwise. The estimation bias resulted by this adaptation mechanism is much closer to zero. Besides, Figure 3(b) characterizes the estimation bias under different action spaces, which is also important considering that different tasks normally have different action spaces and the number of available actions may vary in different states even for the same task. The adaptive ensemble approach is clearly more robust in our setting. In a nutshell, both Figure 3(a) and 3(b) suggest that a fixed ensemble size would not work well to minimize the estimation bias during learning for different tasks. This phenomenon has also been observed in the empirical results [7]. In stark contrast, adaptively
changing the ensemble size based on the approximation error indeed can help reduce the estimation bias in different settings.
3 Adaptive Ensemble Q-learning (AdaEQ)
Motivated by the illustrative example above, we next devise a generalized ensemble method with ensemble size adaptation to drive the estimation bias be close to zero, by taking into consideration the time-varying feature of the approximation error during the learning process. Formally, we consider an ensemble of N Q-function approximators, i.e., ( with each approximator initialized independently and randomly. We use the minimum of subset M of the N approximators in the
Q-learning target as in (3), where the size of subset |M = M $ N.
3.1 Lower Bound and Upper Bound on Estimation Bias
We first answer the following key question:"How does the approximation error, together with the ensemble size, impact the estimation bias?". To this end, based on (29). we characterize the intrinsic relationship among the ensemble size M, the Q-function approximation error and the estimation bias, and derive an upper bound and a lower bound on the bias in the tabular case. Without loss of generality, assume that for each state s, there A available actions.
Let e'(s, a) A Q'(ss a) (s, a) be the approximation error for the i-th Q-function approximator, where (T(s,, a) is the ground-truth of the Q-value for the current policy æ. By using (3) to compute the target Q-value, we define the estimation error in the Bellman equation for transition (s, a, 8') as Zy:
ZM A + y max,'e minjeM Q'(s', aa) (r + max.'e Q" ,d)))
Here positive M[ implies overestimation bias while a negative E[ZM] implies underestimation bias. Note that we use the subscription M to emphasize that the estimation bias is intimately related to M.
The case with two distributions for Q-function approximation errors. For ease of exposition, first consider the case when the approximation errors follow one of the two uniform distributions, Specifically, assume that for K. M with |AC] = K, e (s(ss) a)
as illustrated in Figure 4(a) u(-T1,71) T1), and for i E M K., e'. a) ~ U T2, T2). Without loss of generality, we assume that 7i > T2 O. It is worth noting that in (29 61. the approximation error for all approximators is assumed to follow the same uniform distribution, i.c., T1 T2, which is clearly more restrictive than the case here with two eтror distributions. For instance, when only one approximator chosen to be updated at each step [17,, the approximation error distribution of this approximator would change over time and hence differ from the others. We have the following results on the upper bound and lower bound of the estimation bias E[ZM}
Theorem 1. For the case with two distributions for Q-function approximation errors, the estimation bias E Ma) satisfies that
E|Zu] 2 7 (11
-1 fAK - 2fAM) + T2 fAMM))
(5)
E ZM < (TI + (1 2f -MM -113
(6)
where BK =
)) fAK = 5 A+1) = I(A+1)](1+})
A(A-1)
T(a++-1) (A+ 1 k (1+
with B(.,)) being the Beta function.
5

---

Apprecimator Q'
Approsimator.
Appresimator Q"
Lower Bound
Estimation Bins
Upper Bound
Ensemble Size
Random selection of
Underestimation Overestimation
0.0
7
Q Approsimation error distribution
Approximation error distribation 12
0.5
0.6
0.7
-0.8
5(-5.5)
Ensemble Size
Impact of approximation error the estimation bias: overesti- mation vs. underestimation.
(a) Q-function approximation ror distributions.
(b) Lower bound and upper bound Estimation bias.
Figure 4: Illustration of upper bounds and lower bounds on estimation bias in Theorem | (a) The case where the approximation errors of the Q-approximators can be categorized into two uniform distributions. (b) The lower bound and the upper bound corresponding to (5) and (6). for given T1, T2. A: The blue point represents the 'critical' point where decreasing the ensemble size may lead overestimation (the lower bound is positive); and the red point denotes the 'critical' point where increasing ensemble size may lead underestimation (the upper bound is negative). (c) Due to time-varying feature of the approximation error, the blue curve and the red curve depict the 'critical' points for the lower bound and the upper bound, respectively.
The proof of Theorem jis relegated to the Appendix A.1. Theorem reveals that the estimation bias depends on the ensemble size as well as the approximation error distributions. To get a more concrete sense of Theorem 1 we consider example where TI 0.5 and 72 0.4, as depicted in Figure 4(b) and characterize the relationship between the estimation bias and the ensemble size M. Notably, the estimation bias turns negative when the ensemble size M M.. 9 (red point: the value of M where the upper bound is 0) and becomes positive when M < MM = (blue point: the value of M where the lower bound is 0). In Figure 4(c) we fix 72 0.4 and show how those two critical points (M,, and MD) change along with Here the red shaded area indicates underestimation bias when M > Ma,, and the blue shaded area indicates overestimation bias when M < M,. Clearly, in order to avoid the positive bias (blue shaded area). it is desirable to increase the ensemble size when the approximation error is large, e.g., Ti 0.6. On the other hand, decreasing the ensemble size is more preferred to avoid underestimation (red shaded area) when the approximation error is small, e.g. 71 < 0.6.
The general case with heterogeneous distributions for Q-function approximation errors. Next, we consider general case, which the approximation errors for different approximators { are independently but non-identically distributed. Specifically, we assume that the approximation error e'(s, a) for Q'(s,a),, i We use a multitude of tools to devise the upper bound and lower bound on the estimation bias E[ZM]. As expected, this general case technically more challenging and the bounds would be not as sharp as in the special case with two distributions.
M, follows the uniform distribution (1-Ts; Tz). where T; > 0.
Theorem 2. For the general case with heterogeneous error distributions, the estimation bias E 7M satisfies that
E M 2" (Tiiin - Tinax (f +ffMM))
(7)
E M ST (2Tmin Tmax (fAM 22gAM))
(8)
where Twin min; T; and Tmax max; TO 9AM 1 40.5 + 1) with 1o.((;.)) being the regularized incomplete Beta function.
Observe from Theorem that the lower bound in 7 is positive when Tmin 2fAM) >
Tiaa Tiaax A(M -1): indicating the existence of the overestimation issue. On thew contrary, the upper bound in ( is negative when 2Tmin < Tmax (1 fAM 2yAM) pointing to the underestimation issue. In general, when Tuan is large enough, decreasing ensemble size M is likely to cause overesti- mation, e.g., s.., E 2 ( when M < 2. On the other hand, when Tmax is small enough, increasing ensemble size M is likely to cause underestimation, e.g., E M < O when M sufficiently large.
Determination of parameter c. As illustrated in Figure A(c) for given approximation emor charac- terization, threshold e can be chosen such that increasing the ensemble size would help to correct the overestimation bias when Tmax > c, and decreasing the ensemble size is more conductive to mitigate

---

the underestimation bias when Tmax < Specifically, parameter e is determined in two steps. Step 1: To estimate approximation error distribution parameters Tmin and Tmax by running an ensemble based algorithm (e.g, Algorithm [ for few epochs with fixed ensemble size. In particular, testing trajectory is generated from random initial state using the current policy to compute the (discounted) MC return Q" and the estimated Q-function value Q', i = 1, 2,2,... ..... N. We next fit uniform distribution model Ul( (T;, v²) of the approximation error (Q' - QT) for each Q-function approximator Q'. Then, Tmin and Tmax can be obtained by choosing the minimum and maximum values among Tı, i = 1, 2..,.... .N. Step 2: To obtain the upper bound and the lower bound in Theorem 2 by using { Tmax },7). We investigate the relationship between ensemble size M and the estimation bias by studying the bounds and identifying the 'critical' points as illustrated in Figure 4(b). Observe that 'proper' ensemble size should be chosen between the 'critical' points, so to reduce the overestimation and underestimation bias as much as possible. Since the approximation error is time-varying during the learning process, these two 'critical' points vary along with (Tmax) and [Tmin] } (as shown in Figure 4(c)). Intuitively, it is desirable to drive the system to avoid both the red region (underestimation) and the blue region (overestimation). It can be clearly observed that there is a wide range of choice for parameter e (e.g., [0.5, 0.7] in Figure 4(c)) for the algorithm to stay in the white region, indicating that even though the pre-determined above is not optimized, can still serve the purpose well.
The proof of Theorem 2 and numerical illustration can be found in the Appendix A.3. Summarizing, both Theorem aad Theorem Lindicate that the approximation error characterization plays a critical role in controlling the estimation bias. In fact, both the lower bound and the upper bound in Theorem depeend on miin and Timax which are time-varying due to the iterative nature of the learning process, indicating that it is sensible to use adaptive ensemble size drive the estimation bias to be close to zero, as much as possible.
3.2 Practical Implementation
Based on the theoretic findings above, we next propose AdaEQ that adapts the ensemble size based on the approximation error feedback on the fly, so as to drive the estimation bias close to zero Particularly, as summarized in Algorithm [ AdaEQ introduces two important steps at each iteration t, i.c., approximation error characterization (line 3) and ensemble size adaptation (line 4), which can be combined with the framework of either Q-learning or actor-critic methods.
Characterization of the time-varying approximation error. As outlined in Algorithm I the first key step is to quantify the time-varying approximation error at each iteration (for ease of exposition, we omit the subscript & when it is clear from the context). Along the same line as in [9] 33 G we run testing trajectory of length H, T (Su, au; $1, a1, $H 0H) ), from random initial state using the current policy π,, and compute the discounted Monte Carlo return Q" (s, a) and the estimated Q-function value Q' a), i 1, 1,.... NN for each visited state-action pair (s, a). The empirical standard derivation of Q'(x, a) - Q" a) can be then obtained to quantify the approximation error of each approximator Q'. Then, we take the average of the empirical standard derivation over all approximators to characterize the approximation error at the current iteration f, i.c.,
न = ~ M (Qd a) - Q= a)), (s. e T.
Grror-feedback based ensemble size adaptation. Based on the theoretic results and Figure 4(c) we update the ensemble size M at each iteration t based the approximation error using the following piecewise function:
rand [M,1++1 1, 7 e, M + +15 N
M,-
rand M,-1-111
--1 e, M - 122
(10)
M,-1
otherwise,
where rand(-:)) -) is uniform random function and is pre-determined parameter to capture the "tolerance" of the estimation bias during the adaptation process. Recall that parameter e can be determined by using the upper bound and the lower bound in Theorem (Theorrmm [T]. Particularly, a larger e implies that more tolerance of the underestimation bias is allowed when adapting the ensemble size Mr. A smaller e, on the other hand, admits more tolerance of the overestimation. In this way, AdaEQ can be viewed as generalization of Maxmin and REDQ with ensemble size adaptation. In particular, when e = 0 and M, + & N. the adaptation mechanism would increase the ensemble size until it is equal to N. Consequently, AdaEQ degenerates to Maxmin [7 where M = N, leading
7

---

end for Algorithm Adaptive Ensemble Q-learning (AdaEQ)
1: Empty replay buffer D, step size a, number of the approximators N, initial in-target ensemble size Mo N, initial state Initialize N approximators with different training samples.
2: for Iteration t = 1, 2, ... do
3: Identify approximation error parameter Fy using 9
4: Update ensemble size M, according to (T))
5: Sample M of M, different indices from (1,2,-.-,,)
6:
Obtain the proxy approximator Q (s, a) <- mingeM ('
((s,a) a), Va E A
7:
Choose action a from current state s using policy derived from Quixky (e.g. e-greedy)
8:
Take action observe r and next state s' Update replay buffer + DU (8,,,r,8')
9:
10:
for i = 2, ....,............. N do
11:
Sample random mini-batch B from
12:
Compute the target: y(s, a, r') + + max. Update Q-function Q': ('ss + (1 - aa) (s, ay(s.a..,,))
13:
14:
end for
15:
6-
16:
possible underestimation bias. Meantime, when is set sufficiently large, the ensemble size M would decrease until reaching the minimal value 2 during the learning process, where the estimation bias would be positive according to Theorem 2] In this case, AdaEQ degenerated REDQ 6 with ensemble size M = 2. We show the convergence analysis of AdaEQ in Appendix A.5.
Remark. We random sampling in Eqn. (T) for reasons. Firstly, the characterization of the approximation error in Eqn. (9) is noisy in nature. In particular, Monte Carlo returns with finite-length testing trajectory may introduce empirical errors when estimating the underlying ground true value of Q*. This noisy estimation is often the case when the policy is not deterministic, or the environment deterministic. Thus, we use random sampling to 'capture' the impact of this noisy estimation. Secondly, in general it is infeasible to characterize the exact relationship between estimation bias ZM and ensemble size M. Without any further prior information except from the bounds obtained in Theorem and Theorem 2 about the approximation error, the random sampling can be viewed as the "exploration' in AdaEQ.
Experimental Results
In this section, we evaluate the effectiveness of AdaEQ by answering the following questions: 1) Can AdaBQ minimize the estimation bias and further improve performance comparison to existing ensemble methods? 2) How does AdaEQ perform given different initial ensemble sizes? 3) How does the "tolerance' parameter e affect the performance?
To make a fair comparison, we follow the setup of [6] and use the same code base to compare the performance of AdaEQ with REDQ 6 and Average-DQN (AVG) 2 on three MuloCo continuous control tasks: Hopper, Ant and Walker2d. The same hyperparameters are used for all the algorithms. Specifically, we consider N 10 Q-function approximators in total. The ensemble size M 10 for AVG, while the initial M for AdaEQ is set as 4. The ensemble size for REDQ is set M 2, which is the fine-tuned result from (6. For all the experiments, we set the 'tolerance' parameter e in (TO) 0.3 and the length of the testing trajectories as H 500. The ensemble size is updated according to (10) every epochs in AdaEQ. The discount factor is 0.99. Implementation details and hyperparamter settings are fully described in Appendix B.I.
Evaluation of estimation bias. To investigate the impact of the adaptation mechanism in AdaEQ. we begin by examining how the estimation bias changes in the training process. After each epoch, we run an evaluation episode of length H 500, starting from an initial state sampled from the replay buffer. We calculate the estimation error based on the difference between the Monte Carlo return value and the Q-estimates as in 33 deviation of the average evaluation over training seeds. As shown in the first row of Figure 5 AdaEQ can reduce the estimation bias to nearly zero all three benchmark environments, contrast to REDQ and AVG. The AVG approach tends to result in positive bias in all three environments
For each experiment, the shaded area represents standard

---

H2
Aut
Walker3d
Humanko92
Unttmation Liee
Deimution floe
Letimaation
1.
63
06
Timestaps
Linesopo
Dopper-22
Art
Wallee--dd
Unraaoodd-
5006
5014
Adabi RED0
5ox
A
Evergg
REDO Average-O
100
Timostape
Timodape
Timodape
Timcorpe
Figure 5: Comparison in terms of the estimation bias (first row) and average return (second row) in three MuJoCo tasks. Solid lines are the mean values and the shaded areas are the standard derivations across three random seeds. We use the undiscounted sum of all the reward in the testing episode to evaluate the performance of the current policy after each epoch. The estimation error is evaluated by comparing the difference between the Monte Carlo return and the average Q-value for each state-action pair visited during the testing episode. We take the average of those error values as estimation bias. For AdaEQ, we use the same hyperparameter for ensemble size adaptation.
4304
Nette
Ealinroon
1800
AduE REDO Aweeage-
REDO Awerge
Timesige
Tinosiia
Tincoigo
Tinclloo
(a) Hopper-v2 task. Aver- (b) Hopper-v2 task. Esti- (c) Ant task. Average (d) Ant task. Estima- age returns over different mation bias over different returns over different ini- tion bias over different ini- initial ensemble size M initial ensemble size M tial ensemble size M tial ensemble size M 2,3,5. 5.
2,3,5.
3, 5.
3,5,7. 7.
Figure 6: Impacts of the initial ensemble size M on the performance of AdaEQ in Hopper-v2 and Ant task. The solid lines are the mean values and the shaded areas are the standard derivations across three ensemble size settings.
during the learning procedure, which is consistent with the results obtained in (6]. Notably, it can be clearly observed from Hopper and Walker2d tasks that the estimation bias for AdaEQ is driven to be close to zero, thanks to the dynamic ensemble size adjustment during the learning process. Meantime, in the Ant task, even though the fine-tuned REDQ can mitigate the overestimation bias, tends to have underestination bias, whereas AdaEQ is able to keep the bias closer to zero (gray dashed line) even under a 'non-optimal" choice of the initial ensemble size.
Performance MuJoCo benchmark. We evaluate the policy return after each epoch by calculating
the undiscounted sum of rewards when rumning the current learnt policy [6] [4]. The second row of
Figure demonstratsss the average return during the learning process for AdaEQ. AVG and REDQ. respectively. Especially, we choose the fine-tune ensemble size for REDQ 6 As observed in Figure AdaEQ can efficiently learn a better policy and achieve higher average return in all three challenging MuJoCo tasks, without searching the optimal parameters beforehand for each them. Meantime, AdaEQ only incurs slightly more computation time than REDQ in most MuJoCo tasks. Due to space limitation, we have relegated the wall-clock training time comparison to Table 2 in Appendix B.2.
Robustness to the initial ensemble size. Next, we investigate the performance of AdaRQ under different settings of the initial ensemble size in the Hopper-v2 and Ant environment, i.c., M (2,3,5)

---

R 1g 8
Avenyy Kettm
Eariadoo
130
Tamolopa
(a) H2 task. Aver- (b) Hopper-v2 task. Esti- (c) Ant task. Average re- (d) Ant task. Estimation age returns over different mation bias over different turns over different param- bias over different parame- parameter in AdaEQ. parameter in AdaEQ.
eter c in AdaEQ.
ter c in AdaEQ.
Impacts of parameter с on the performance of AdaEQ in Hopper-v2 and Ant task. The initial ensemble size is set be M 4. The mean value and the standard derivation are evaluated across three training seeds.
Figure 7:
and MM (3 7). As shown in Figure 6 AdaEQ consistently outperforms the others in terms of the average performance over different setups, which implies the benefit of adjusting the in-target ensemble size based on the error feedback. It can be seen from the shaded area that the performance of AVG and REDQ, may vary significantly when the ensemble size changes.
Robustness to parameter e a wide range. As illustrated in Figure 7 we conduct the ablation study by setting c 0.001, 0.3, 0.5, 0.7, 1.5 on the Hopper-v2 and Ant tasks. Clearly, AdaEQ works better for E [0.3, 0.7]. The experiment results corroborate our analysis in Section 3.1 that our algorithm not sensitive parameter i wide range. As mentioned in Section (3.2 when parameter is close to zero, AdaEQ degenerates to Maxmin, which is known to suffer from underestimation bias when the ensemble size large O Further, as illustrated in Figure 7b) when e is large, e.g..
= 1.5, the ensemble size would gradually decrease to the minimum and hence would not be able to throttle the overestimation tendency during the learning process.
Conclusion
Determining the right ensemble size highly nontrivial for the ensemble Q-learning correct the overestimation without introducing significant underestimation bias. In this paper, we devise AdaEQ. generalized ensemble Q-learning method for the ensemble size adaptation, aiming minimize the estimation bias during the learning process. More specifically, by establishing the upper bound and lower bound of the estimation bias, we first characterize the impact of both the ensemble size and the time-varye vime-narying approximation error the estimation bias. Building upon the theoretic results, we treat the estimation bias minimization as an adaptive control problem, and take the approximation error feedback to adjust the ensemble size adaptively during the learning process. Our experiments show that AdaEQ consistently and effectively outperforms the existing ensemble methods, such as REDQ and AVG in MuJoCo tasks, corroborating the benefit of using AdaEQ to drive the estimation bias close to zero.
There are many important avenues for future work. In terms of the bounds of the estimation bias, our analysis builds upon the standard independent assumption as previous works. It's worth noting that in practice, the errors are generally correlated [29] and the theoretical analysis for this case remains not well understood. Additionally, this work, we use heuristic tolerance parameter the adaptation mechanism to strike the halance in controlling the positive bias and negative bias. It is of great interest to develop a systematic approach to optimize this tolerance parameter.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their constructive comments. This work was supported part by NSF grants CNS-2130125, CCSS-2121222 and CNS-2003081.
10

---

References
[1] Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. An optimistic perspective on offline reinforcement learning. In International Conference Machine Learning, pages 104-114, PMLR, 2020.
[2] Oron Anschel, Nir Baram, and Nahum Shimkin. Averaged-dqn: Variance reduction and stabilization for deep reinforcement learnin In International Conference on Machine Learning, pages 176-185. PMLR, 2017.
[3] K Johan Astrom. Adaptive feedback control. Proceedings of the IEEE, 75(2):185-217, 1987.
[4] Richard Bellman. Dynamic programming and stochastic control processes. Information and control, 133):228-23, 1958.
[5] Dimitri P Bertsekas. Reinforcement learning and optimal control. Athena Scientific Belmont, MA, 2019.
[6] Xinyue Chen, Che Wang, Zijian Zhou, and Keith Ross. Randomized ensembled double learning: Learning fast without a model. arXiv preprint arXiv:2101.05982, 2021.
[7] Thomas G Dietterich. Ensemble methods in machine learning. In International workshop on multiple classifier systems, pages 1-15. Springer, 2000.
[8] Carlo D' D'Eramo, Marcello Restelli, and Alessandro Nuara. Estimating maximum expected value through gaussian approximation. In International Conference Machine Learning, pages 1032-1040. PMIR, 2016.
[9] Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In International Conference on Machine Learning, pages 1587-1596. PMLR, 2018.
[10] Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International Conference Machine Learning, pages 2052-2062. PMLR, 2019.
[11) Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. In International Conference Machine Learning, pages 1861-1870, PMLR, 2018.
[12] Hado Hasselt. Double q-leariig. Advances neural information processing systems, 23:2613- 2621, 2010.
[13] Julian Ibarz, Jie Tan, Chelsea Finn, Mrinal Kalakrishnan, Peter Pastor, and Sergey Levine. How to train your robot with deep reinforcement lcarning: lessons we have learned. The International Journal of Robotics Research, 40(4-5):698-7211 2021.
[14] Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model-based policy optimization. arXiv preprint 2XXv:1906.08253. 2019.
[15] Amit Konar, Indrani Goswami Chakraborty, Sapam Jitu Singh, Lakhmi Jain, and Atulya K Nagar. A deterministic improved q-learning for path planning of mobile robot. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 43(5): 141-1151 1133, 2013.
[16] Aviral Kumar, Justin Fu, George Tucker, and Sergey Levine. Stabilizing off- off-policy q-learning via bootstrapping error reduction. arXiv preprint arXiv:1906.000 1906.0099, 2019.
[17] Qingfeng Lan, Yangchen Pan, Alona Fyshe, and Martha White. Maxmin g-learning: Controlling the estimation bias of g-learning arXiv preprint arXiv:2002.06487, 2020.
[18] Donghun Lee, Boris Defoumy,, and Warren B Powell. Bias-corrected q-learning to control max- operator bias in q-learning. In 2013 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL), pages 93-99, IEEE, 2013.

---

[19] Kimin Lee. Michael Laskin, Aravind Srinivas, and Pieter Abbeel. Sunrise: A simple unified framework for ensemble learning in deep reinforcement learning. arXiv preprint arXiv:2007.04933. 2020.
[20] Shiyu Liang and Rayadurgam Srikant. Why deep neural networks for function approximation? arXiv preprint arXiv:1610.04161, 2016.
[21] Hongzi Mao, Mohammad Alizadeh, Ishai Menache, and Srikanth Kandula. Resource man- agement with deep reinforcement learning. In Proceedings of the 15th ACM workshop on hot topics in networks, pages 50-56, 2016.
[22] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
[23] Hamidreza Modares, Frank L Lewis, and Mohammad -Bahher Naghibi-Sistanl Sisttan. Adaptive optimal control of unknown constrained-input systems using policy iteration and neural networks. IEEE transactions on neural networks and learning systems, 24(10):1513-1)
2013.
[24] Soroush Nasiriany, Vitchyr H Pong, Steven Lin, and Sergey Levine. Planning with goal- conditioned policies. arXiv preprint arXiv: 1et.191110084555 1.08453, 2019.
[25] Romeo Ortega and Yu Tang. Robustness of adaptive controllers- a survey. Automatica, 25(5):651-677, 1989.
[26] Oren Peer, Chen Tessler, Nadav Merlis, and Ron Meir. Ensemble bootstrapping for q-learning. arXiv preprint arXiv: 103 10445 2021.
[27] Zhao Song, Ron Parr, and Lawrence Carin. Revisiting the softmax bellman operator: New benefits and new perspective. In International Conference on Machine Learning, pages 5916- 5925. PMLR, 2019.
[28] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[29] Sebastian Thrun and Anton Schwartz. Issues in using function approximation for reinforcement learning. In Proceedings of the 1993 Connectionist Models Summer School Hillsdale, NJ. Lawrence Erlbaum. 1993.
[30] Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 0033. IEEE, 2012.
[31] Christos Tsanikidis and Javad Ghaderi. On the power of randomization for scheduling real- time traffic in wireless networks. In IEEE INFOCOM 2020-IEEE Conference on Computer Communications, pages 59-68. IEEE, 2020.
[32] Hado Van Hasselt, Yotam Doron, Florian Strub, Matteo Hessel, Nicolas Sonnerat, and Joseph Modayil. Deep reinforcement learning and the deadly triad. arXiv preprint 1XXi:18122002648 2018.
[33] Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q-learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
[34] Yi-Chi Wang and John M Usher. Application of reinforcement learning for agent-based production scheduling. Engineering Applications of Artificial Intelligence, 18(1):73-82, 2005.
[35] Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-292,
1992.
[36] Baohe Zhang, Raghu Rajan, Luis Pineda, Nathan Lambert, André Biedenkapp. Kurtland Chua, Frank Hutter, and Roberto Calandra. On the importance of hyperparameter optimization for model-based reinforcement learning. International Conference on Artificial Intelligence and Statistics, pages 4015-4023, PMLR, 2021.
12

---

[37] Zongzhang Zhang, Zhiyuan Pan, and Mykel J Kochenderfer. Weighted double q-learning. In LICAI, pages 3455-3461, 2017.
[38] Rong Zhu and Mattia Rigotti. Self-correcting q-learning. arXiv preprint arXiv:2012.01100, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See section
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
3.1
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix A.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi-
mental results (either in the supplemental material or URL)? [Yes] See Appendix
B.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section and and Appendix B.1.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] See Section 4
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix B.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 4
(b) Did you mention the license of the assets? [Yes] See Appendix.
(c) Did you include any new assets either in the supplemental material or as a URL?
Yes] Our training code and training logs will be available at /https://githeie com/ ustcmike/ A NeurIPS21
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] We did not use any data from the other individuals.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A] We did not the use any personally information or offensive content.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "zcqULPmGwEQ", "reviewer": "Reviewer_Cgf5", "summary": "This paper proposes an ensemble Q-learning which can adaptively adjust the ensemble size based on estimation error. The authors find that the ensemble min(Q_1, Q_2, ..., Q_M) may suffer from overestimation or underestimation with different M, so they propose to adapt M based on approximation error, which can minimize the estimation bias correspondingly. \n\nThe paper analyzes both in theoretically and empirically, show better performance than the existing ensemble q-learning methods on a few MuJoCo benchmark tasks. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The major contribution of this paper is to establish the correlation between the ensemble size and estimation bias under the ensemble q-learning framework(min operator). \n\nOverall Clarity is good. The idea is clear and easy to follow, and the authors show the motivation why they propose this adaptive ensemble size q-learning. \n\nOriginality/Significance: I did not see exactly the same work before (to address the ensemble size). This paper tries to solve the ensemble size problem in ensemble q-learning, but it creates a new problem here, for example how to adjust the new hyperparameter c in Eq. 10. And the experiment show it impacts performance significantly in Fig.6(d). If we need to try different c and also need to set different M to get a good result, I do not see any practical advantage compared to TD3, SAC, etc\n\nRegarding correctness of the algorithm: my main concern is when τ1 > τ2 > 0, \\mathcal{K} \\in [-τ1, τ1] but how do you get M\\K \\in [-τ2, τ2] in line 194-196. The problem is how do you define the set range \\mathcal{M}. Another question your result in Eqs. 5 and 6 is from uniform distribution assumption, but you decide τ based on Gaussian in Eq. 9. Also you randomly sample in the following equation to get M does not make much sense to me. \n\nRegarding experimental evaluation: The experimental results show this method is sensitive to new hyperparameter c and it needs to carefully tuned to get good result compared to REDQ. As the authors propose a new ensemble q-learning by adjusting the size M, it is important to compare with TD3 and SAC on a wide range of tasks in MuJoCo environments on which most current continuous control algorithms have been evaluated and compared.\n\nOverall, the authors need to address these concerns above before acceptance. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NO", "review_text": "", "extra_scores": {"ethical_concerns": "NO", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "m4RR9IfGZL4", "reviewer": "Reviewer_UaYC", "summary": "This paper proposes a DRL method AdaEQ to solve the overestimation problem of Q-function. The experiment results show that AdaEQ can outperform the baseline methods.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The overestimation of Q is the targeting problem of this paper. The proposed AdaEQ solves this problem in a two-stage procedure: approximate error characterization and ensemble size adaptation to minimize the bias. This is a natural solution for the targeting problem.\n \nOriginality: The authors propose to optimize the estimation of Q-value through modifying the number of the ensembled Q_{n}. The authors provide the guarantees of estimation error on Q_i in the proposed method. Unlike the existing ensemble methods, AdaEQ can adaptively choose the ensemble size due to the learning process. The experiment results prove that AdaEQ works.\n \nClarity: The theoretical elaboration part (section3) of this paper is very detailed and logical. But the exposition of the experiment is relatively less comprehensive. The introduction of the environment and the description of the task are unclear. It is unclear whether the authors have made any adjustments and modifications to the environment of Mujoco. It would be better to add some necessary description in the experimental background. Overall, the paper is well-written and easy to understand.\n \nQuality: The theoretical part of this article is comprehensive. The experimental part should be enhanced by adding some necessary ablation studies—for example, the effect of the choice of c (in eq.10) on the result. Similarly in eq.10, whether the different sample methods of M affect the result.\n \nBelow are some questions and suggestions for this paper.\n1. In fig.5, In the Ant environment, AdaEQ has a pronounced fluctuation. Considering that Ant is a relatively stable environment, this phenomenon should not happen. How to explain this phenomenon?\n2. Does AdaEQ need more compute time than REDQ? If yes, how much time does AdaEQ take more than REDQ in each environment step?\n3. Is AdaEQ sensitive to c(in eq.10)?\n4. How does AdaEQ perform on other Mujoco tasks? Such as humanoid, hammock? If you have done this experiment, you can also show the results, even if the results are not competitive.\n \nOverall, the experimental results can support the claim that AdaEQ can indeed improve performance on some tasks. Although this method is straightforward, it also provides a very general idea for optimization, which is very impressive. The experimental part of this article could be enhanced to provide strong support for the claim.\n\n=== Post Rebuttal ===\n\nThe paper proposes a novel idea with a comprehensive theoretical analysis. The experiment can provide basic support to its claims.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See comments in \"Main Review\".", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "m2hNv-nKrv", "reviewer": "Reviewer_54UB", "summary": "To mitigate the overestimation issue in Q-learning, this paper proposes an adaptive way to control the ensemble size of Q-function approximators. \nExperimentally, this paper demonstrates how the ensemble size affects the estimation bias.\nTheoretically, this paper gives the upper bound and lower bound of the estimation bias according to the ensemble size. \nFinally, this paper evaluates the proposed algorithm in the MuJoCo environment. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: \nThis paper studies the effect of ensemble size on the estimation bias. There are several works studying the ensemble size of Q-function approximators. But this is the first to study how to adaptively control ensemble size on the fly. The originality is incremental.\n\nQuality: \nIn response to the estimation bias, this paper discusses the upper and lower bounds experimentally and theoretically. \n\nClarity: \nThis paper is well written, clear and easy to read. \n\nSignificance: \nThe ensemble size heavily affects the estimation bias. This paper proposes a randomized algorithm which updates the ensemble size according to a pre-determined \"tolerance\". It is a rough way to adjust the ensemble size. In total, this paper makes an incremental contribution.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "(1) This paper states in line 264-265 that \"Recall that parameter c can be determined by using the upper bound and the lower bound in Theorem 2 (Theorem 1).\" However, the upper bound and lower bound are determined by \\tau_\\min and \\tau_\\max, which are unknown variables. \nIt is not clear how to determine c by the upper and lower bound, since upper and lower bound are unknown. \n(2) This paper studies the estimation bias of the ensemble size. It lacks analysis of how ensemble size affects the cumulative reward. \n(3) This paper selects three MuJoCo environments to evaluate the proposed algorithms. How about the rest MuJoCo environments? More experiments on discrete control tasks can make more evaluation of the algorithm.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Pr0RpvcG2I", "reviewer": "Reviewer_u8Dd", "summary": "This paper proposes an adaptive ensemble size to prevent the over/under estimation bias that a too small/large ensemble creates due to time-varying approximation errors. They derive bounds on the estimation bias for an argmin ensemble method and propose an adaptive ensemble method to mitigate this over/under estimation bias problem.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall: The paper proposes an interesting problem and an interesting solution. However the paper\nspends a lot of time using simple examples to show intuition where it is not clear whether these examples are “degenerate” examples (Figures 2 and 3 are unnecessary and so is Theorem 1 which is a simple case of Theorem 2). Furthermore they need to spend to spend more time justifying their more unusual generative assumptions (Uniform noise and using the argmin ensemble estimator). It is not clear whether this bias changing “signs” above a certain ensemble size problem is an artifact of the unusual “min” estimator. \n\nMajor Comments: \n\nLine 122: Is the overestimation bias being positive proven in [16] or [6] or somewhere else, if so please state where and how. Otherwise, this seems like an extremely aggressive assumption. Or if by definition a bias being positive implies overestimation, then why can the bias not be negative? Is this not underestimation?\n\nWhy is it assumed that the approximation error has Uniform noise, not Gaussian noise? Furthermore the variance of distribution of the noise for each of the ensemble members depends heavily on \\tau. For example if \\tau is large, then the N \\tau_i have higher variance, and this in turn makes the distributions of each error_i be more different from each other.\n\nIf too large of an ensemble size causes underestimation bias, and this bias is negative according to Line 189, why does averaging not reduce bias overall. Furthermore, why is Z_M being studied for only the argmin ensemble method and not the averaging ensemble method in Line 188/189. If only the argmin estimator exhibits both positive and negative biases, wouldn’t averaging an “ensemble” of those estimators create an unbiased estimator?\n\nWhat is K and what is M in the example described after Theorem 1?\n\nIn the experiments in Figure 5, why is the bias almost always positive even for the “optimized” methods? Shouldn’t the bias be as likely to be positive as negative if the methods have been “optimized” and centered? Also what is the very large dip (between 1 and 1.5) in the AdaEQ model for Ant?\n\nMinor Comments:\n\nLine 106 missing “the” in “By definition, (the) Q-function is the expected return when” and this phrase is strangely worded “and following with the policy”\n\nLine 230: Typo “thew”\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations: Addressed\nSocietal Impact: Not relevant", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "3MBZKO7X3Fs", "reviewer": "Reviewer_hyzH", "summary": "Some Reinforcement Learning algorithms like Q-learning are subject to a bias known as the maximization or overestimation bias. This is due to the fact that value iteration approximates the value of the next state as the max over actions of Q-values. As a consequence, if the Q-values are approximate, the maximum over such approximations tends to be skewed towards high values. Ensembling many independent estimates of the Q-values helps mitigatin the overestimation bias, but often at the risk of achieving the opposite effect, i.e. an underestimation bias, if the ensemble is too large.\nThe point of this paper is to propose and develop a method to estimate the current bias, and use that to estimate to dynamically choose the size of the ensemble so as to find a trade-off between over- and underestimation that minimizes the estimation bias.\nThe method is demonstrated on a simple toy task and then on control tasks with continuous action spaces simulated with MuJoCo physics engine.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper starts with an illustrative synthetic example of how an approximation error in the Q-values gives rise to an estimation bias that persists in the ensemble case, and motivating that an adaptive ensemble size would actually potentially mitigate this problem.\nIt then develops a theory that bounds the estimation bias of an ensemble of Q-values under the assumption of an approximation error that is uniform across across states and actions, an assumption that allows the authors to postulate an analytic expression for the approximation error that is used in developing the theory. This results in analytical bounds for the bias as a function of the size of the ensemble size M and the approximation error tau.\nThey then go on to develop a way to estimate the approximation error tau, relying on Monte Carlo returns computed over rollouts of the current policy.\nThe bias mitigation algorithm AdaEQ then basically consists in using this last estimate of the approximation error tau by plugging it into the expressions for the bias in order to recover a value of the ensemble size M that results in a bias that is between the estimated upper bound indicating overestimation and lower bounds indicating underestimation. \nThe authors then demonstrate their algorithms against other ensemble-based bias mitigation strategies (REDQ and Average-Q) on three tasks from MuJoCO demonstrating competitive performance both in faithfully minimizing the estimation bias, and achieving higher average returns.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. The paper gives a good overview of the relevant literature, but is failing to cite some recent related work like the following published papers:\n- Zhu, R; Rigotti, M. 2021. Self-correcting Q-learning, AAAI 2021\n- Song, Z.; Parr, R.; and Carin, L. 2019. Revisiting the Soft-max Bellman Operator: New Benefits and New Perspective. ICML 2019\n- D’Eramo, C.; Nuara, A.; and Restelli, M. 2016. Estimatingthe Maximum Expected Value through Gaussian Approxi-mation. ICML 2016\nIt would be nice if for completeness the authors considered citing these in relation to their work.\n\n2. The paper is proposing a new and interesting theory-driven way of mitigating the estimation bias in Q-learning. Given how general this issue is, one of the main limitations of the paper is arguably the limited number of tasks and settings under which the algorithm has been empirically evaluated. Obviously, one cannot try everything, but it would have been instructive for instance to examine at least a few tasks with discrete action spaces, like for instance Atari 2600, to verify that AdaEQ properties extend to that case and the bias estimation can be used in other settings like DQN.\n\n3. The assumption that the approximation error is uniform across states and actions seems like a big assumption. It is true that the width of the distribution is dynamically re-estimated at each iteration, but it would be instructive if the authors had a way of showing that this is an assumption that can be borne out empirically or if they could at least elaborate on it and why it is not too strong of an assumption.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a novel method to tackle overestimation bias in Q-learning. The majority of reviewers agreed that the paper is a good contribution to the NeurIPS community, albeit empirical evidence could be expanded further to consider additional ablation studies and environments. 
Decision: Accept (Poster)