Randomized Ensembled Double Q-Learning: Learning Fast Without a Model
Authors: Xinyue Chen
Che Wang
Zijian Zhou
Keith W. Ross
Venue: ICLR 2021 Poster (2021)
Keywords: Artificial Integlligence
Machine Learning
Deep Reinforcement Learning

Abstract: Using a high Update-To-Data (UTD) ratio, model-based methods have recently achieved much higher sample efficiency than previous model-free methods for continuous-action DRL benchmarks. In this paper, we introduce a simple model-free algorithm, Randomized Ensembled Double Q-Learning (REDQ), and show that its performance is just as good as, if not better than, a state-of-the-art model-based algorithm for the MuJoCo benchmark. Moreover, REDQ can achieve this performance using fewer parameters than the model-based method, and with less wall-clock run time. REDQ has three carefully integrated ingredients which allow it to achieve its high performance: (i) a UTD ratio $\gg 1$; (ii) an ensemble of Q functions; (iii) in-target minimization across a random subset of Q functions from the ensemble. Through carefully designed experiments, we provide a detailed analysis of REDQ and related model-free algorithms. To our knowledge, REDQ is the first successful model-free DRL algorithm for continuous-action spaces using a UTD ratio $\gg 1$. 

Published as a conference paper at ICLR 2021
RANDOMIZED ENSEMBLED DOUBLE Q-LEARNING: LEARNING FAST WITHOUT A MODEL
Xinyue Chen
Che Wang 1.2+
Zijian Zhou
Keith Ross! 1.21
1 New York University Shanghai
2 New York University
ABSTRACT
Using high Update-To-Data (UTD) ratio, model-based methods have recently achieved much higher sample efficiency than previous model-free methods for continuous-action DRL benchmarks. In this paper, we introduce a simple model- free algorithm, Randomized Ensembled Double Q-Learning (REDQ), and show that its performance is just as good as, if not better than, a state-of- ofrthe--rt model- based algorithm for the MuJoCo benchmark. Moreover, REDQ can achieve this performance using fewer parameters than the model-based method, and with less wall-clock run time. REDQ has three carefully integrated ingredients which allow it to achieve its high performance: (i) a UTD ratio > 1; (ii) an ensemble of Q functions; (iii) in-target minimization across random subset of Q functions from the ensemble. Through carefully designed experiments, we provide a detailed analysis of REDQ and related model-free algorithms. To our knowledge, REDQ is the first successful model-fre DRL algorithm for continuous- action spaces using UTD ratio >> 1.
INTRODUCTION
Recently, model-based methods in continuous action space domains have achieved much higher sample efficiency than previous model-free methods. Model-based methods often attain higher sam- ple efficiency by using high Update-To- To-tat (UTD) ratio, which is the number of updates taken by the agent compared to the number of actual interactions with the environment. For example, Model-Based Policy Optimization (MBPO) (Janner et al., 2019), a state-of-the-arr model-based algorithm which updates the agent with mix of real data from the environment and "fake" data from its model, and uses a large UTD ratio of 20-40. Compared to Soft-Actor is model-free and uses UTD of 1, MBPO achieves much higher sample efficiency in the Ope- nAI MuJoCo benchmark (Todorov et al., 2012 Brockman et al. 2016). This raises the question of whether it is also possible to achieve such high performance without model?
(SAC), which
In this paper, we introduce a simple model-free algorithm called Randomized Ensemble Double Q learning (REDQ), and show that its performance is just as good as, if not better than, MBPO. The result indicates, that at least for the MuJoCo benchmark, simple model-free algorithms can attain the performance of current state-of-the thett-trrrtttt model-based algorithms. Moreover, REDQ can achieve this performance using fewer parameters than MBPO, and with less wall-clock run time.
Like MBPO, REDQ employs UTD ratio that is > but unlike MBPO it is model-free, has no roll outs, and performs all updates with real data. In addition to using UTD ratio that is > 1, it has two other carefully integrated ingredients: an ensemble of Q functions; and in-target minimization across a random subset of Q functions from the ensemble.
Through carefully designed experiments, we provide detailed analysis of REDQ. We introduce the metrics of average Q-function bias and standard deviation (std) of Q-function bias. Our results show that using ensembles with in-target minimization reduces the std of the Q-function bias to close to
"Equal contribution. in alphabetical order. Correspondence Keith Ross <keithwross @ @ny..edu>

---

Published as a conference paper at ICLR 2021
zero for most of training, even when the UTD is very high. Furthermore. by adjusting the number of randomly selected O-functions for in-tar minimization, REDQ can control the average O-function bias. In comparison with standard ensemble averaging and with SAC with higher UTD, REDQ has much lower std of Q-function bias while maintaining an average bias that is negative but close to zero throughout most of training, resulting in significantly better learning performance. We perform an ablation study, and show that REDQ is very robust to choices of hyperparameters, and can work well with small ensemble and small number of Q functions in the in-target minimization. We also provide a theoretical analysis, providing additional insights into REDQ. Finally, we consider combining the REDQ algorithm with an online feature extractor network (OFENet) (Ota et al.) 2020) to further improve performance, particularly for the more challenging environments Ant and Humanoid. We achieve more than the sample efficiency of SAC to reach score of 5000 for both Ant and Humanoid. In Humanoid, REDQ-OFE also greatly outperforms MBPO, reaching a score of 5000 at 150K interactions, which is 3x MBPO's s score at that point.
To ensure comparisons are fair, and to ensure our results are reproducible (Henderson et al. 2018 Islam et al., 2017 Duan et al. 2016), we provide open source code For all algorithmic comparisons, use the same codebase (except for MBPO, for which use the authors' code).
2 RANDOMIZED ENSEMBLED DOUBLE Q-LEARNING (REDQ)
Janner et al. (0099) proposed Model-Based Policy Optimization (MBPO), which was shown to be much more sample efficient than popular model-free algorithms such SAC and PPO for the MuJoCo environments. MBPO learns a model, and generates "fake data" from its model as well as "real data" through environment interactions. It then performs parameter updates using both the fake and the real data. One of the distinguishing features of MBPO is that it has UTD ratio >> 1 for updating its Q functions, enabling MBPO to achieve high sample efficiency.
We propose Randomized Ensembled Double Q-learning (REDQ), a novel model-free algorithm whose sample-efficiency performance is just as good as, if not better than, the state-of-the-ar model- based algorithm for the MuloCo benchmark. The pseudocode for REDQ is shown in Algorithm REDQ can be used with any standard off-policy frede--free algorithm, such as SAC (Haarnoja et al. 2018b), SOP (Wang et al.) 2019). TD3 (Fujimoto et al.) 20188). DDPG (Lillicrap et al.) 2015). For the sake of concreteness, we use SAC in Algorithm L REDQ has the following key components: (i) To improve sample efficiency, the UTD ratio G is much greater than one; (ti) To reduce the variance in the Q-function estimate, REDQ uses an ensemble of N Q-functions, with each Q-function randomly and independently initialized but updated with the same target; (fii) To reduce over-estimation bias, the target for the Q-function includes a minimization over a random subset M of the N Q-functions. The size of the subset M is kept fixed, and is denoted as M, and is referred to as the in-target minimization parameter. Since our default choice for M is M = 2, we refer the algorithm as Randomized Ensembled Double Q-learning (REDQ).
REDQ shares some similarities with Maxmin Q-learning (Lan et al. 2020), which also uses ensem- bles and also minimizes over multiple Q-functions in the target. However. Maxmin Q-learning and REDQ have many differences, e.g., Maxmin Q-learning minimizes over the full ensemble in the target, whereas REDQ minimizes over a random subset of Q-functions. Unlike Maxmin Q-learning, REDQ controls over-estimation bias and variance of the Q estimate by separately setting M and N. REDQ has many possible variations, some of which are discussed the ablation section.
REDQ has three key hyperparameters, G, N, and M. When N = M = 2 and G = 1, then REDQ simply becomes the underlying off-policy algorithm such as SAC. When N = M > 2 and
G' 1, then REDQ is similar to, but not equivalent to, Maxmin Q-learning (Lan et al., 2020). In practice, we find M = 2 works well for REDQ, and that a wide range of values around N = 10 and
G 20 work well. To our knowledge, REDQ is the first successful model-free DRL algorithm for continuous-action spaces using a UTD ratio G >
Coode and implementation tutorial be found httpp://ggitubb..c/////ttteeeeee
2

---

Published as a conference paper at ICLR 2021
Algorithm Randomized Ensembled Double Q-learning (REDQ)
1: Initialize policy parameters 0, NN Q-function parameters Oi,
N, empty replay buffer
D. Set target parameters (harg, f- Øs; for 1,2,...,!.
2: repeat
3: Take one action ag ~ (T)-( Observe reward rv, new state 81+1-
4: Add data buffer: D < D U {(5) ac, Fe.
5: for G updates do
6:
a(,,,, Sample mini-batch B {(s, r, 8')} from D Sample a set M of M distinct indices from {1, 21,,,..,... N Compute the Q target y (same for all of the N Q-functions):
7:
8:
y セート min Qowas (5',a') aog To (ā' 181) ä' te (.15) iEM
9:
for i = 1, .N do Update o; with gradient descent using
10:
Σ
(Q, - yy)
(S.0.):")EB
11:
Update target networks with Otarg,i porarg,i + (1 - p)ds Update policy parameters with gradient ascent using
N
V B
Σ SEB
Σ 2ml
Qs (s, (s)))) a log no (ão()))))) ao(s) ~ =ol.
N
2.1 EXPERIMENTAL RESULTS FOR REDQ
We now provide experimental results for REDQ and MBPO for the four most challenging MuJoCo environments, namely, Hopper. Walker2d, Ant, and Humanoid. We have taken great care to make fair comparison of REDQ and MBPO. The MBPO results are reproduced using the author's open source code, and we use the hyperparameters suggested in the MBPO paper, including G = 20. We obtain MBPO results similar those reported the MBPO paper. For REDQ, we use G 20, N = 10, and M 2 for all environments. We use the evaluation protocol proposed in the MBPO paper. Specifically, after every epoch we run one test episode with the current policy and record the performance as the undiscounted sum of all the rewards in the episode. A more detailed discussion on hyperparameters and implementation details given in the Appendix.
Figure I shows the training curves for REDQ, MBPO, and SAC. For each algorithm, plot the average return 5 independent trials as the solid curve, and plot the standard deviation across train each algorithm for exactly
seeds the transparent shaded region. For each environment, the same number of environment interactions as done in the MBPO paper. Figure [ shows that both REDQ and MBPO learn much faster than SAC, with REDQ performing somewhat better than MBPO on the whole. In particular, REDQ learns significantly faster for Hopper, and has somewhat better asymptotic performance for Hopper, Walker2d, and Humanoid. A more detailed performance comparison is given in the Appendix. where it is shown that, averaging across the environments, REDQ performs 1.4x better than MBPO half-way through training and 1.1x better the end of training. These results taken together are perhaps counter-intuitive. They show that simple model- free algorithm can achieve as good or better sample-efficiency performance as the state-of-the-arr model-based algorithm for the MuJoCo environments.
Does REDQ achieve its sample efficiency using more computational resources than MBPO? We now compare the number of parameters used in REDQ and MBPO. With REDQ, for each Q net- work and the policy network, we use a multi-layer perceptron with two hidden layers, each with 256 units. For MBPO, model ensembles (Janner et al., (019)). The Appendix provides table comparing the number of pa- rameters: REDQ uses fewer parameters than MBPO for all four environments, specifically, between
the default network architectures for the networks, policy network, and
3

---

Published as a conference paper at ICLR 2021
Avergge retum
Mostrormen tranaccionn
enwernmment mitractions
(a) Hopper
(b) Walker2d
2009
envtrement Intermntnnn
envecnment mecertion
(c) Ant
(d) Humanoid
Figure 1: REDQ compared to MBPO and SAC. Both REDQ and MBPO use G 20.
26% and 70% as many parameters depending on the environment. Additionally, we measured the runtime on a 2080-Ti GPU and found that MBPO roughly takes 75% longer. In summary, the results in this section show that the model-free algorithm REDQ is not only at least as sample efficient as MBPO, but also has fewer parameters and is significantly faster in terms of wall-clock time.
WHY DOES REDQ SUCCEED WHEREAS OTHERS FAIL?
REDQ is a simple model-free algorithm that matches the performance of state-of-theear model- based algorithm. Key to REDQ's sample efficiency is using UTD >> 1. Why is it that SAC and ordinary ensemble averaging (AVG) cannot do as well REDQ by simply increasing the UTD?
To address these questions, let Q" (s, a) be the action-value function for policy π using the standard infmite-horizon discounted return definition. Let Q+ (s, a) be an estimate of Q" (s, a), which is 1....,N .N when using of an estimate at state-action pair (s,a) to be Qo the accuracy of Qp(s, a) over the state-action distribution of the current policy æ. To quantitatively analyze how estimation error accumulates in the training process, we perform an analysis that similar previous work (Van Hasselt et al. 2016 Fujimoto et al. 2018), but not exactly the same. We run a number of analysis episodes from different random initial states using the current policy и. For each state-action pair visited, estimated Q value using Qs, and then compute the difference to obtain an estimate of the bias for that state-action pair. We then calculate the average and std of these bias values. The average gives us an idea of whether Qo is in general overestimating or underestimating, and the std measures how uniform the bias is across different state-action pairs. We argue that the std is just as important as the average of the bias. As discussed in Van Hasselt et al. (2016). a uniform bias is not necessarily harmful as does not change the action selection. Thus near-uniform bias can be preferable highly non-uniform bias with small average value. Although average bias has been analyzed in several previous works (Van Hasselt et al., [2016] Fujimoto et al. 2018 Anschel et al. 2017), the does not seem to have received much attention.
defined as the average of Qg (s. a).
ensemble. We define the bias Q" (s, a). We are primarily interested in
obtain both the discounted Monte Carlo return and the
Since the MC return values can change significantly throughout training, to make comparisons more meaningful, we define the normalized bias of the estimate Qo(s,a) to be (Qa(s,a) Q= a))/ (Q" (5, a)]l, which is simply the bias divided by the absolute value of the ex- pected discounted MC return for state-action pairs sampled from the current policy. We focus on the normalized bias in our analysis since helps show how large the bias is, compared to the scale of the current MC return.
4

---

Published as a conference paper at ICLR 2021
In this and the subsequent section, we compare REDQ with several algorithms and variants. We emphasize that all of the algorithms and variants use the same code base as used in the REDQ experiments (including using SAC the underlying off- aff-policy algorithm). The only difference is how the targets are calculated in lines 7 and 8 of Algorithm
We first compare REDQ with two natural algorithms, which we call SAC-20 and ensemble averaging (AVG). SAC-20 is SAC but with G increased from 1 (as standard SAC) to 20. For AVG, we use an ensemble of Q functions, and when computing the Q target, we take the average of all Q values without any in-target minimization. In these comparisons, all three algorithms use a UTD Gf 20. In the later ablation section we also have detailed discussion on experimental results with Maxmin, and explain why it does not work well for the MuJoCo benchmark when using a large ensemble.
Figure presents the results for Ant; the results for the other three environments are consistent with those for Ant and are shown in the Appendix. For each experiment we use 5 random seeds. We first note REDQ learns significantly faster than both SAC-20 and AVG. Strikingly, relative to the other two algorithms, REDQ has very low normalized std of bias for most of training, indicating the bias across different in-distribution state-action pairs is about the same. Furthermore, throughout most of training, REDQ has a small and near-constant under-estimation bias. The shaded areas for mean and std of bias are also smaller, indicating that REDQ robust to random initial conditions.
1E00
SAC-70
AVG
Avengge: retur
enviromment into actions
in
La enstenment inceractions
environment envfrormennkieeracaooo
intoractions
(a) Performance, Ant
(b) Average bias, Ant
(c) Std of bias, Ant
Figure 2: Performance, mean and std of normalized Q bias for REDQ, AVG, and SAC for Ant. Figures for the other three environments have similar trends and are shown in the Appendix.
SAC with a UTD ratio of 20 performs poorly for the most challenging environments Ant and Hu- manoid. For SAC-20, the high UTD ratio leads We also see a high normalized std of bias, indicating that the bias is highly non-uniform, which can be detrimental. The bias values also have large variance across random initial seeds, indicated by the large shaded area, showing that the bias in SAC-20 is sensitive to initial conditions. Comparing AVG and SAC-20, we see AVG performs significantly better than SAC-20 in Ant and Humanoid. This can be explained again by the bias: due to ensemble averaging, AVG can achieve a lower std of bias; and when it does, its performance improves significantly faster than SAC-20.
average bias that fluctuates during training.
REDQ has two critical components that allow it to maintain stable and near-uniform bias under high UTD ratios: an ensemble and in-target minimization. AVG and SAC-20 each has one of these components but neither has both. Thus the success of REDQ is largely due to a careful integration of both of these critical components. Additionally, as shown in the ablation study, the random selection of Q functions in the in-targer minimization can give REDQ further performance boost.
3.1 THEORETICAL ANALYSIS
We now characterize the relation between the estimation error, the in-target minimization parameter M and the size of the ensemble N. We use the theoretical framework introduced in Thrun & Schwartz (993) and extended in Lan et al. (2020), We do this for the tabular version of REDQ, for which the target for Q'(s, a) for each i 1, 1....,4 N is:
r r 7 max min ('s''a') d'EAjEM
where A is the finite action space, (s, a, s') is a transition, and M is again a uniformly random subset from [1....,N] N} with M = M. The complete pseudocode for tabular REDQ is provided in the Appendix.
5

---

Published as a conference paper at ICLR 2021
Let ( be the pre-update estimation bias for the ith Q-function, where Q=(s.a) once again the sround-truth Q-value for the current policy и. We are interested in how the bias changes after update, and how this change is effected by M and N. Similar to Thrun & Schwartz (1993) and Lan et al. (2020), define the post-update estimation bias as the difference between the target and the target when using the ground-truth:
ZMN _ r Y max min
(r max Q" (s',''')) a'EA
'EAJEM
(mmx min Q* JEM.jEM
max
(T d'EA
Here we write ZM.N to emphasize its dependence on both M and N. Following Thrun & Schwartz 1993) and Lan et al. (2020), fix and assume each Q*(s, a) has random approximation error ega
Q' a) = (s, + ea
where for each fixed s, {e are identically distributed across for each fixed (s, a) pair. Note that due to the zero-mean assumption, the expected pre-update estimation bias is E[Q'(s, (s, a) Q" (s. a)] = 0. Thus if I [M, > 0, then the expected post-update bias is positive and there tendency for over-estimation accumulation; and if E [2M,N] < 0, then there is tendency for under-estimation accumulation.
independent random variables such that {ceu are
Theorem 1.
For any fixed M, E [M.N] does not depend on N.
2. E [ for all N 2
3. EE [[] S E [M.NN] for any M < N.
4. Suppose that e' < cfoor some c > 0 for all s, a and i. Then there exists an M such that for all N 2 M, [[ZM,,]] <.
Points 2-4 of the Theorem indicate that we can control the expected post-update bias EE M bringing it from above zero (over estimation) to under zero (under estimation) by increasing M. Moreover, from the first point, the expected bias only depends on M, which implies that increasing N can reduce the variance of the ensemble average but does not change the expected post-update bias. Thus, we can control the post-update bias with M and separately control the variance of the average of the ensemble with N. Note that this is not possible for Maxmin Q-learning, for which M = N,, and thus increasing the ensemble size N will also decrease the post-update bias, potentially making it more negative, which can be detrimental. Note that this also cannot be done for standard ensemble averaging, for which there is no in-target minimization parameter M.
Note we make very weak assumptions on the distribution of the error term. Thrun Schwartz 1993) and Lan et al. (2020) make strong assumption, namely, the eтror term is uniformly distributed. Because our assumption much weaker, our proof methodology in the Appendix very different.
We also consider variant of REDQ where instead of choosing random set of size M in the target, we calculate the target by taking the expected value over all possible subsets of size M. this case, the target in the tabular version becomes
YM,N (s) +1
max min Q' (s',,'))
N
a' JEB
BCN BB=M
We write the target here as YM.N to emphasize its dependence on both M and N. We refer to this variant of REDQ as "Weighted" since we can efficiently calculate the target as a weighted sum of a re-ordering of the N Q-functions, as described in the Appendix.
The following theorem shows that the variance of this target goes to zero as + 0o. We note, however, that in practice, some variance in the target may be beneficial in redueing overfitting or help exploration. We can retain some variance by keeping N finite or using the unweighted REDQ scheme.
Let UM == (ar(maxx/ minjer a Q (s', aa)) for any subset B C N where [B] = M. (It is easily seen that UM only depends on M and not only the specific elements of B.)

---

Published as a conference paper at ICLR 2021
Theorem 2.
Var(YM.N) - (M)
for some function Gas (N) satisfying
lim (M N
M /
Consequently,
lim Var(YM.N) = N
Also in the Appendix we show that the tabular version of REDQ convergences to the optimal Q function with probability one.
REDQ VARIANTS AND ABLATIONS
In this section, we use ablations provide further insight into REDQ. We focus on the Ant envi- ronment. We first look at how the ensemble size N affects REDQ. The top row in Figure shows REDQ with N = 2,3, 5, 10, 15. We can see that when we increase the ensemble size, we generally get more stable average bias, lower std of bias, and stronger performance. The result shows that even a small ensemble (c.g., 5) can greatly help in stabilizing bias accumulation when training under high UTD.
REDIO M15 Do-Don DOCNO
Avergee NeSSF
08
m
enviromment Intor actiicooon
environment Interactions enwronmenikneeerciooor
envirorment Interactions
(a) Performance, Ant
(b) Average bias, Ant
(c) std of bias, Ant
REDG-MM2
REDG-N2
REDO N3
REIDQ-NS
enviromment actions
envtronment interaciinn
(d) Performance, Ant
(c) Average Q bias, Ant
(f) std Q Bias, Ant
nedt
Anrengge m80m
wuighaed
envircement inter retacctions
Lt
ensrerment incerctioos
10
envirenment Interactione
(g) Performance. Ant
(h) Average bias, Ant
std of bias, Ant
Figure 3: REDQ ablation results for Ant. The top row shows the effect of the ensemble size N. The middle row shows the effect of the in n-target minimization parameter M. The bottom row compares REDQ to several variants.
The middle row of Figure 3 shows how M, the in-target minimization parameter, can affect perfor- mance. When M is not integer, e.g., M 1.5, for each update, with probability 0.5 only one

---

Published as a conference paper at ICLR 2021
mandomly-chosed Q function is used in the target, and with probability 0.5, two randomly-chosen functions are used. Similarly, for M = 2.5, for each update either two or three Q functions are used. Consistent with the theoretical result in Theorem 1, by increasing M we lower the average bias. When M gets too large, the Q estimate becomes too conservative and the large negative bias makes learning difficult.
M = 2, which has the overall best performance, strikes a good balance between average bias (small underestimation during most of training) and std of the bias (consistently small).
The bottom row of [ the results for different target computation methods. The Maxmin curve in the figures is variant based on Maxmin Q-learning, where the min of all the Q networks in the ensemble is taken to compute the Q target. As the ensemble size increases, Maxmin Q-learning shifts from overestimation to underestimation (Lan et al.) 2020): Figure 3 shows Maxmin with N 3 instead of N = 10, since large N value will cause even more divergence of the Q values. When varying the ensemble size of Maxmin, we see the same problem as shown in the middle row of Figure 3 When we increase the ensemble size to be larger than 3, Maxmin starts to reduce the bias so much that we get a highly negative Q bias, which accumulates quickly, leading to instability the Q networks and poor performance. In the Maxmin paper, it was mainly tested on Atari environments with a small finite action space, in which case it provides good performance. Our results show that when using environments with high-dimensiona continuous action spaces, such as MuJoCo, the rapid accumulation of (negative) bias becomes a problem. This result parallels some recent research in offline (i.e., batch) DRL. In Agarwal et al.) (2020), it is shown that with small finite action spaces, naive offline training with deep Q-networks (DQN) only slightly reduces performance. However, continuous action Q-learning based methods such as Deep Deterministic Policy Gradient and SAC suffer much more from Q bias accumulation compared to discrete action methods. Recent work shows that offline training with these methods often lead to poor performance, and can even entirely diverge (Fujimoto et al. 2019 Kumar et al. 2019).
Random ensemble mixture (REM) a method originally proposed to boost performance of DQN in the discrete-action setting. REM uses the random convex combination of Q values to compute the target: is similar to ensemble average (AVG), but with more randomization (Agarwal al. 2020).
For Weighted, the target is computed as the expectation of all the REDQ targets, where the expec- tation is taken over all N-choose-2 pairs of Q-functions. This leads to a formula that a weighted sum of the ordered Q-functions, where the ordering is from the lowest to the highest Q value in the ensemble, as described in the Appendix. Our baseline REDQ in Algorithm I can be considered as a sandom-sampe version of Weighted. For the MinPair REDQ variant, we divide the 10 Q networks into 5 fixed pairs, and during an update we sample a pair of Q networks from these 5 fixed pairs.
that REDQ and MinPair are the best and their performance is similar. For Ant, the performance of Weighted is much lower than REDQ. However, as shown in the Appendix, Weighted and REDQ have similar performance for the other three environments. The randomization might help alleviate overfitting in the early stage, or improve exploration. REM has performance similar to AVG, studied in Section 3 In terms of the bias, REM has positive average bias, while REDQ, MinPair, and Weighted all have a small negative average bias. Overall these results indicate that the REDQ algorithm is robust across different mechanisms for choosing the functions, and that randomly choosing the Q functions can sometimes boost performance. Additional results and discussions are provided in the appendix.
From Figure 3
4.1 IMPROVING REDQ WITH AUXILIARY FEATURE LEARNING
We now investigate whether we can further improve the performance of REDQ by incorporating better representation learning? Otta et al. (2020) recently proposed the online feature extractor net- work (OFENet), which learns representation vectors from environment data, and provides them to the agent as additional input, giving significant performance improvement.
Is it possible to further improve the performance of REDQ with OFENet? We trained an OFENet to- gether with REDQ to provide extra input, giving the algorithm REDQ-OFE. We found that OFENet did not help much for Hopper and Walker2d, which may be because REDQ already learns very fast, leaving little room for improvement. But as shown in Figure 4 online feature extraction can further improve REDQ performance for the more challenging environments Ant and Humanoid.
8

---

Published as a conference paper at ICLR 2021
REDQ-OFE achieves 7x the sample efficiency of SAC reach 5000 on Ant and Humanoid, and outperforms MBPO with 3.12x and 1.26x the performance of MBPO at 150K and 300K data, re- spectively. A more detailed performance comparison table can be found in the Appendix.
Aveegg: re0
REDI
SAC
REDO OFE
12 envienment nttraciions
(a) Performance, Ant
(b) Performance, Humanoid
Figure 4: Performance of REDQ, REDQ with OFE, and SAC.
RELATED WORK
It has long been recognized that maximization bias in Q-learning can significantly impede learning.
Thrun Schwartz (1993) first highlighted the existence maximization bias. [Van Hasselt (2010) proposed Double Q-Learning address maximization bias for the tabular case, and showed that in
general it leads to an under-estimation bias. Van Hasselt et al. (2016) showed that adding Double
Q-learning deep Q networks (DQN) (Mnih et al.) 2013 2015 gives a major performance boost for the Atari games benchmark. For continuous-action spaces, Lujimoto et al. (2018) introduced clipped-double Q-learning (CDQ), which further reduces maximization bias and brings significant improvements over the deep deterministic policy gradient (DDPG) algorithm (Lillicrap et al., (2015).
CDQ was later combined with entropy maximization in SAC to achieve even stronger performance (Haarnoja et al. 2018a b). Other bias reduction techniques include using bias-correction terms (Lee al. 2013), using weighted Q estimates (Zhang al.. 2017] Li Hou 2019), penalizing deterministic policies at early stage of training (Fox et al. 2015), using multi-stpp methods (Meng
cct al. 2020), performing weighted Bellman updates to mitigate error propagation (Lee et al. 2020).
and truncating sampled estimates with distributional networks (Kuznetsov et al. (0200).
has also long been recognized that using ensembles can improve the performance of DRL algo- rithms (Fauler & Schwenker 2015 Osband et al. 2016 For Q-learning based methods, Anschel
et al. (017) use the average of multiple Q estimates to reduce variance. Agarwal et al. (2020) intro- duced Random Ensemble Mixture (REM), which enforces optimal Bellman consistency on random convex combinations of multiple Q estimates. Lan et al.) (2020) introduced Maxmin Q-learning, as discussed in Sections 2-4. Although discrete action domains has been found that fine-tuning DQN variants, including the UTD, can boost performance, little experimental or theoretical analysis
given explain how this improvement obtained (Kielak 2020 van Hasselt al. 2019).
To address some of the critical issues in model-based learning (Lagglois et al. 2019). recent methods such as MBPO combine model ensemble with carefully controlled rollout horizon obtain better performance (Janner et al.] [019 [Buckman et al.] 2018). These model-based methods can also be enhanced with advanced sampling (Zhang et al.
2020). bidirectional models (Lai et al.) 2020))
or backprop through the model (Clavera et al. 2020), and be analyzed through new theoretical
frameworks (Rajeswaran et al. 2020 Dong et al.
2020
CONCLUSION
The contributions of this paper are as follows. (1) We propose simple model-free algorithm that attains sample efficiency that as good as or better than state-of-the-ar model-based algorithms for the MuJoCo benchmark. This result indicates that, at least for the MuJoCo benchmark, models may not be necessary for achieving high sample efficiency. (2) Using carefully designed experiments, explain why REDQ succeeds when other model-free algorithms with high UTD ratios fail. (3) Finally, we combine REDQ with OFE, and show that REDQ-OFE can learn extremely fast for the challenging environments Ant and Humanoid.

---

Published as a conference paper at ICLR 2021
REFERENCES
Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. An optimistic perspective on offline reinforcement learning. International Conference on Machine Learning (ICML), 2020.
Oron Anschel, Nir Baram, and Nahum Shimkin. Averaged-dgn: Variance reduction and stabilization for deep reinforcement learning. In International Conference on Machine Learning, pp. 176-185, 2017.
Dimitri P Bertsekas and John N Tsitsiklis. Neuro-dynamic programming, volume 5. Athena Scien- tific Belmont, MA, 1996.
Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near- optimal reinforcement learning. Journal of Machine Learning Research, 3(Oct):213-231, 2002.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint crXiv:1606.01540. 2016.
Jacob Buckman, Danijar Hafner, George Tucker, Eugene Brevdo, and Honglak Lee. Sample- efficient reinforcement learning with stochastic ensemble value expansion. In Advances Neural 2018.
Information Processing Systems, pp.
Kamil Ciosek, Quan Vuong, Robert Loftin, and Katja Hofmann, Better exploration with optimistic actor critic. In Advances in Neural Information Processing Systems, pp. 1787-1798, 2019.
Ignasi Clavera, Violet Fu, and Pieter Abbeel. Model-augmented actor-critie: Backpropagating through paths. arXiv preprint wxXiv:2005.08065 2020.
Kefan Dong, Yuping Luo, Tianhe Yu, Chelsea Finn, and Tengyu Ma. On the expressivity of ral networks for deep reinforcement learning. International Conference on Machine Learning (ICML). 2020.
Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In International Conference Machine Learning. pp. 1329-1338, 2016.
Stefan FauBer and Friedhelm Schwenker. Neural network ensembles in reinforcement learning. Neural Processing Letters, 41(1):55-69, 69, 2015.
Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Osband, Alex Graves, Vlad Mnih, Remi Munos, Demis Hassabis, Olivier Pictquin, et al. Noisy networks for exploration. ICLR, 2018.
Roy Fox, Ari Pakman, and Naftali Tishby. Taming the noise in reinforcement learning via soft updates. arXiv preprint arXiv:1512.08566 2015.
Scott Fujimoto, Herke van Hoof, and Dave Meger. Addressing function approximation eroo in actor-critic methods. arXiv preprint arXiv: 1802
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International Conference on Machine Learning, pp. 2052-2002000 2062, 2019.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. arXiv preprint arXiv:1801.01290. 2018a.
Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, et al. Soft actor-critic algorithms and appli- cations. arXiv preprint 10/2:008/0 2018b
Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep reinforcement learning that matters. In Thirty-Second AAAI Conference on Artificial Intel- ligence, 2018.
10

---

Published as a conference paper at ICLR 2021
Riashat Islam, Peter Henderson, Maziar Gomrokchi, and Doina Precup. benchmarked deep reinforcement learning tasks for continuous control. arXiv preprint 0ttp::778.041333. 2017.
Reproducibility of
Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model- based policy optimization. In Advances in Neural Information Processing Systems, pp. 12519- 12530, 2019.
Kacper Kielak. Do recent advancements in model- based deep reinforcement learning really improve data efficiency? arXiv preprint arXiv:2003.1018/ 2020.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 112.69941,.6980, 2014.
Aviral Kumar, Justin Fu, Matthew Soh, George Tucker, and Sergey Levine. Stabilizing off-policy q-learning via bootstrapping error reduction. In Advances in Neural Information Processing Sys- tems, pp. 11784-10 11794, 2019.
Arsenii Kuznetsov, Pavel Shvechikov, Alexander Grishin, and Dmitry Vetrov. Controlling overes- timation bias with truncated mixture of continuous distributional quantile critics. arXiv preprint WwXiv:2005.04269, 2020.
Hang Lai, Jian Shen, Weinan Zhang, and Yong Yu. Bidirectional model-based policy optimization. arXiv preprint urXiv:2007.01995, 2020.
Qingfeng Lan, Yangchen Pan, Alona Fyshe, and Martha White. Maxmin q-learning: Controlling the estimation bias of q-learning. arXiv preprint arXiv:2002.06487, 2020.
Eric Langlois, Shunshi Zhang, Guodong Zhang, Pieter Abbeel, and Jimmy Ba. Benchmarking masel-based reinforcement learning. arXiv preprint arXiv:1907.02057 2019.
Donghun Lee, Boris Defourny, and Warren B Powell. Bias-corrected q-learning to control max- operator bias in g-learning. In 2013 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL), pp. 93-99. IEEE, 2013.
Kimin Lee, Michael Laskin, Aravind Srinivas, and Pieter Abbecl. Sunrise: A simple unified frame- work for ensemble learning in deep reinforcement learning. arXiv preprint arXiv:2007.04938, 2020.
Zhunan Li and Xinwen Hou. Mixing update q-value for deep reinforcement learning. 2019 International Joint Conference Neural Networks (IJCNN), pp. 1-6. IEEE, 2019.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver. and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv: http:::50900977/ 2015.
Lingheng Meng, Rob Gorbet, and Dana Kulić. The effect multi-step methods on overestimation in deep reinforcement learning. arXiv preprint arXiv:2006. /2692, 2020.
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602. 2013.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver. Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 51 518(7540):529, 2015.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. In Advances in neural information processing systems, pp. 4026-4034, 2016.
Kei Ota, Tomoaki Oiki, Devesh K Jha, Toshisada Mariyama, and Daniel Nikovski. Can increasing input dimensionality improve deep reinforcement learning? arXiv preprint arXiv:2003.0162) 2020.

---

Published as a conference paper at ICLR 2021
Aravind Rajeswaran, Igor Mordatch, and Vikash Kumar. A game theoretic framework for model based reinforcement learning. arXiv preprint arXiv:2004.07888 2020.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
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 Erlhaum, 1993.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physies engine for model-based control. In Intelligent Robots and Systems (IROS), 2012 IEEE/RSJ International Conference on, pp. 5026- 5033. IEEE, 2012.
John N Tsitsiklis. Asynchronous stochastic approximation and q-learning. Machine learning, 16 (3):185-202, 1994.
Hado Van Hasselt. Double q-learning. In Advances in neural information processing systems, pp- 2613-2621, 2010.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In AAAI, volume 2, pp. 5. Phoemix, AZ, 2016.
Hado P van Hasselt, Matteo Hessel, and John Aslanides. When parametric models in rein- forcement learning? In Advances in Neural Information Processing Systems, pp. 14322-14333, 2019.
Che Wang, Yanqiu Wu, Quan Vuong, and Keith Ross. Striving for simplicity and performance in off-policy drl: Output normalization and non-uniform sampling. arXiv, pp. arXiv-1910, 2019.
Chi Zhang, Sanmukh Rao Kuppannagari, and Viktor K Prasanna. Maximum entropy model rollouts: Fast model based policy optimization without compounding errors. arXiv preprint arXiv:2006. 04802, 2020.
Zongzhang Zhang, Zhiyuan Pan, and Mykel Kochenderfer. Weighted double q-learning. In IJCAI, pp. 3455-3461, 2017.
12

---

Published as a conference paper at ICLR 2021
A THEORETICAL RESULTS
A.1 TABULAR VERSION OF REDQ
In the tabular algorithm below, for clarity use G 1.
Algorithm Tabular REDQ
1: Initialize {Q'(s, E, N
2: repeat
3: Choose a E A based on {Q'(s, a)} } observe r, s
4: Randomly choose subset M of size M from [I,,,N]
5: y maxx' EA minjeM (ss
6: for i = I....,,, N do:
7:
('(s,a) + (s) + aly Q' (s,
8:
9:
until end
Alternatively in Algorithm 2, at each iteration we could just update one of the Q' functions.
A.2 PROOF OF THEOREM 1
We first prove the following lemma:
Lemma 1. Let X1, X2.... be an infinite sequence of i.i.d. random variables. Let F(x:) be the cdf of X and let in FF(x) 0}. Also let Yn. min (1,, X2,..., Xm Then Y1, . converges to T almost surely.
Proof:
Let (x) be the edf of Ym- Since X Xm are independent,
Fm = - F())
For x. < (m( = 0 since F(x) 0. For x Fm (x) converges to T.
1. Therefore, Yn weakly
Moreover, for each w Ω2 (Ym (w)) is decreasing sequence. So (Ym (w)) either converges to real number or -O0 Therefore Yn + Y almost surely for some random variable Combined with the result that Y.. 4 T, conclude that
Y.
0.5.
Proof of Theorem 1:
1. Let B1, B2 be two subsets of N = (1,..., N} of size M. First of all, since (Q' a)} are ii.d for any E A, minjeB, (s, and minje B2 Q' (s, a) are identically distributed. Further- more, since Q*(s a) independent for all A and 1 S j N, minjee Q (s, a) aaaaaaee. independent for any c N. Denote the distribution function of max, minjeB, Q' (s, a) as F (x) and the distribution function of max, minjen, (s. a) as Fz)). Then for any x R.
(x) P( max min Q' < 2) PP OrEA {min (s. S x))
a jEB,
iER,
II PP min
(s, S <x) II
P( min Q' <x)
jEB
JEB,
A
a
P max
min Q' a) < x) F2(x)
a JEB₁
13

---

Published as a conference paper at ICLR 2021
Therefore, have proved that max₃ minjeBi (s),) and max, minjeBs Q' a) are identically distributed. Then
E [
[mmxx
min Q' (s. max (s),
JEM
= =yR
max
min ('(s - max (s,
M
a
JEB
a
E8
max
min ISISM
Q'(s, a)] max Q* (s. (s.a)
which does not depend on N. It follows from that
E E[Z = 2 [ax Q' a)] max Q" (s, (s,a)
Since max, (s, 2 a', for all a' E A. we have
E max (s. 2 ((Q'(s,
for all a' E A. Consequently,
max Q [s) max ( as) max (s,
Hence
E [ =7 E max (s max (* 2 0
3. Since max, minigigm (3 a) 2 max. minlsisM (8,a).
E B[MM,N]
=7 E max min (s( max Q" (s, a)
ISSS
27 E
E| max min 1SSEM+1
('(s, a)] max Q" (8( = =E ZM[iNN
4. Let Fx(x) be the edf of ('(s, a) and let T, = inf(x : Fx(x) > 0}. Here we assume the
approximation error eto is non-trivial, which implies Ta a8) Note that Ta can be equal to
-0.. Let
Y.M min (s) ISSM
From Lemma have Y.M converges to almost surely for each Because the action space is finite, it therefore follows that
y max Y.M
converges almost surely to max, Ta. Furthermore, for each we have
Y.M = min (s, 2 min Q' - M+1 15/5M+1
ISiSM
from which it follows that V 2 YM+1 Thus {Y-} is monotonically decreasing sequence.
We also note that due to the assumption ei, < c for all a and and because (= a) finite for all s and a, it follows that YM < for all M for a finite d. Thus {Y is a bounded-above, aamooonncallyydderrasing sequence of random variables which converges almost surely т. We can therefore apply the monotone convergence theorem, giving
[M.N] =
R. max min (s max (*(()))
15J5M
a
=7 B|max Y.M max Q*
M M-+00
max
max Q (s, (5s.))
< <0,
a
where the last inequality follows from va (8, a) for all actions
14

---

Published as a conference paper at ICLR 2021
A.3 PROOF OF THEOREM 2
For convenience, define YB - maxa minjen ("(s',d') Suppose N > 2M.
72
Var(YM.N) =
Var( Σ
YB)
MM
(N)
BCN
|B|-M
(M!)2
+ar(Y))+2 Σ
Cov YBa)
(T i=0 (N i))²
BCN
B. B.B.C B1
Let A = EB, Bg CN Cov(YB, YB,), which consists of Bi B B2
(M)
1
N
N (N MJIM!
1)
2
2
(N MY!M!
N!
T - i)2 M!(N M)!
2(M!)
terms. ((x)) can seen as a polynomial function N with degree 2M. The coefficient for
term N2M is 2(M)JT The coefficient for the term 22M-1 is .ा
2- i).
Note that YB, and YB, are independent if BinBy = Ø. The total number of different pairs (B1, B2) such that B1 B2 2 is
2MM
1
N
122M-1 -i)
2M
M
2
2(M1)² (N- 2M)! 2(M!)²
==0
This is again polynomial function of N with degree 2M. The coefficient of the term N2M is 2(M/)2 The coefficient of the term N2M-1 is terms in A is at most
2(1r1)2 (- 1== i). So the number of non-zero
1
1
-
ITA-1(N - -)² 2 MI(N M)!
N
-T i) =
((1))²
2(M1)
M
-0N2M-2
2(M1)2
Moreover, by Cauchy-Schwarz inequality, for any B1, B2 CN
Cov(YB, YB,) S VVr(YB.)) Var(YB,) UMM
Therefore,
S [ M 22M +((22M-2)JUM
2M1)2
which implies
?2(22
Var(YM.N)
Var(YB) +2- +2
Σ
Cov(YB,, YBa)
(11.-- (N -)))
BCN
B. B,C Biy
(M!12
Var(YB) +2A
MII (N - i))²
BCN
2
< < IIM- (N - -i)
+ +0
UM
No000 0
N2
Moreover,
M /N
II M- M-1 (N - 1)2
Noc
lim
M
NaM
(N-1j² + +0 UM
lim No
N2M
=
15

---

Published as a conference paper at ICLR 2021
A.4 PROOF OF CONVERGENCE OF TABULAR REDQ
Assuming that the step size satisfies the standard Robbins-Monro conditions, it is easily seen that the tabular version of REDQ converges with probability 1 the optimal Q function. In fact, for Weighted scheme, where we take the expectation over all sets of size M, the convergence conditions in Lan al. (2000) are fully satisfied.
For the randomized case, only very minor changes are needed in the proof in Lan et al. (2200) Note that in the case of REDQ, the underlying deterministic target is:
F
(s. a) = r(s, + Σ p
s,a)
max min Q' a²)
jEB
BCN [B|=M
M
Let T be the operator that concatenates N identical copies of F, so that T: RSAXN SXAXN where and A are the cardinalities of the state and action spaces, respectively. easy to show that the operator T is contraction with the loo norm. The stochastic approximation noise term is given by
(ss, a) R a) +
max min a'd, Ep(5'1s,
Σ BCN BB=M
min Q'(s', a') JEB
JEB
(M
N
It is straightforward to show
E w (s, (s
Fastt I Var (Rt s,a) + max max
(Q'()',a'))²
(2)
ISEN s'a
As in Lan 2020). follows from the contraction property and (2) that REDQ converges with probability 1 to the optimal Q function (Tiitsiklis) 1994 Bertsekas & Tsstsiklis 1996).
16

---

Published as a conference paper at ICLR 2021
B HYPERPARAMETERS AND IMPLEMENTATION DETAILS
Since MBPO builds on top of a SAC agent, to make our comparisons fair, meaningful, and consistent with previous work, we make all SAC related hyperparameters exactly the same as used in the MBPO paper (Janner et al., 2019). T For all the REDQ curves reported in the results section, we use a Q network ensemble size N of 10. We use a UTD ratio G of 20 on the four MuloCo environments, which is the same value that was used in the MBPO paper. Thus most of the hyperparameters are made be the same as in the MBPO paper ensure fairnsss and consistency in comparisons.
list of hyperparameter used in the experiments.
For all the algorithms and variants, we also first obtain 5000 data points by randomly sampling actions from the action space without making parameter updates. In our experiments we found that using a high UTD from the very beginning with a very small amount of data can casily lead to complete divergence SAC-20. Sampling number of random datapoints at the start of training is also a common technique that has been used in previous model-free as well as model-based works
(Haarooja al. 2018a Fujimoto al. 2018 Janner al. 2019
Table I: REDQ hyperparameters
Parameter
Value
Shared
optimizer
Adam
Kingma & Ba 2014
learning rate
3 10
discount (7)
0.99
target smoothing coefficient (p)
0.005
replay buffer size
106
number of hidden layers for all networks
2
number of hidden units per layer mini-batch size nonlinearity
256
256
ReLU
random starting data
5000
REDQ
ensemble size N
10
in-target minimization parameter M
2
UTD ratio G
20
OFENet
random starting data
20,000
OFENet number of pretraining updates
100,000
OFENet UTD ratio
4
For the REDQ-OFE experiments, we implemented a minimal version of the OFENet the original paper, with no batchnorm layers. We use the recommended hyperparameters as described in the original paper (Ota et al. 2020). Compared to REDQ without OFENet, the main difference we now first collect 20.000 random data points (which accounted for in the training curves), and then pre-train the OFENet for 100,000 updates, with the same learning rate and batch size. We then train OFENet together with REDQ agent, and the OFENet uses a UTD ratio of We tried a simple hyperparameter search on Ant with 200,000, 100,000 and 50,000 pre-train updates, and learning rates of le-4, 3e-4, 5e-4, and a OFENet UTD of and 20. However, the results are not very different. It is possible that better results can be obtained through more extensive hyperparameter search or other modifications.
B. EFFICIENT CALCULATION OF TARGET FOR WEIGHTED VERSION OF REDQ
In section 4 we provided experimental results for the Weighted version REDQ. Recall that in this version, instead of sampling random subset M in the target, average all subsets B in
17

---

Published as a conference paper at ICLR 2021
{1....,N) N} of size M:
Q (s', (d,,d))
min
EEB
M
B
In practice, however, we do not need to sum over all N choose M subsets. Instead we can re-order the indices that
Q (8,, d') S Q som (d',") for = I,.... 1. After the re-ordering, we can use the identity:
N M-M+1
Σ
min derng (8', (2) ()f,a))= REB
N -
Q Qereg (8', a²)
M 1)
M
t=l
18

---

Published as a conference paper at ICLR 2021
C SAMPLE EFFICIENCY COMPARISON FOR REDQ, SAC AND MBPO
The sample efficiency claims made in the main paper are based on Table and Table 3 Table shows that compared naive SAC, REDQ is much more sample efficient. REDQ reaches 3500 on Hopper with 8x sample efficiency, and reaches 5000 for Ant and Humanoid with 5x and 3.7x sample efficiency. After adding OFE, this becomes more than 7x on Ant and Humanoid. average all the numbers for the four environments, then REDQ is 5.0x as sample efficient, and 6.4x after including OFE results.
Table compares REDQ to SAC and MBPO. As in the MBPO paper, we train for 125K for Hopper, and 300K for the other three environments (Janner al., 2019). The numbers in Table 3 show the performance when trained to half and to the full length of the MBPO training limits. When averaging the numbers, we see that REDQ reaches 4.5x and 2. 1x performance of SAC at 150K and 300K. REDQ is also stronger than MBPO, with 1 1.4x and 1.1x the performance of MBPO at 150K and 300K. we include the results REDQ-OFF then the numbers become 5.5x and 2.3x the SAC performance at 150K and 300K, and 1.8x and 1.2x the MBPO performance 150 and 300K.
Table 2: Sample efficiency comparison of SAC and REDQ. The numbers show the amount of data collected when the specified performance level is reached. The last two columns show how many times REDQ and REDQ-OFE are more sample efficient than SAC in reaching that performance.
Score
SAC
REDQ
REDQ-OFE
REDQ faster
REDQ-OFE faster
Hopper 3500
933K
116K
8.04
Walker2d at 3500
440K
141K
3.12
Ant 5000
771K
153K
106K
7.27 5.04
Humanoid at 5000
945K
255K
134K
3.71
7.05
Table 3: Performance comparison of REDQ, REDQ-OFE, MBPO and SAC. The numbers show the performance achieved when the specific amount of data collected. The last two columns show the ratio of REDQ or REDQ-OF REDQ-OFE performance compared to SAC and MBPO performance.
Amount of data
SAC
MBPО
REDQ
REDQ/SAC
REDQ/MBPO
Hopper at 62K
594
1919
3278
5.52
1.7I
Hopper at 125K
2404
3131
3517
1.46
1.12
Walker2d at 150K
760
3308
3544
4.66
1.07
Walker2d at 300K
2556
3537
4589
1.80
1.30
Ant at 150K
1245
4388
4803
3.86
1.09
Ant at 300K
2485
5774
5369
2.16
0.93
Humanoid at 150K
674
1604
2641
3.92
1.65
Humanoid at 300K
1633
4199
4674
2.86
1.11
Amount of data
SAC
MBPO
REDQ-OFE
OFE/SAC
OFE/MBPO
Ant at 150K
1245
4388
5524
4.44
1.26
Ant at 300K
2485
5774
6578
2.65
1.14
Humanoid at 150KK
674
1604
5011
7.43
3.12
Humanoid at 300K
1633
4199
5309
3.25
1.26
19

---

Published as a conference paper at ICLR 2021
D NUMBER OF PARAMETERS COMPARISON
Table 4 gives the number of parameters for MBPO, REDQ and REDQ-OFE, for all four environ- ments. As discussed in the main paper, REDQ environments: between 26% and 70% as many parameters depending on the environment. After adding OFENet, REDQ still uses fewer parameters than MBPO, with 80% and 35% as many pa- rameters on Ant and Humanoid. In particular, it is surprising that REDQ-OFE can achieve much stronger result on Humanoid with much fewer parameters.
fewer parameters than MBPO for all four
Table Number of parameters millions. REDQ uses the same network structure and ensemble size for all four environments. The difference in the number of parameters comes from the fact that the environments have very different observation and action dimensions, which will affect the size of the input and output layers of the networks.
Algorithm MBPO
Hopper
Walker2d
Ant
Humanoid
1.106M
1.144M
1.617M
7.087M
REDQ N 10
0.769M
0.795M
1.066M
1.840M
REDQ-OFE N 10
1.294M
2.460M
20

---

Published as a conference paper at ICLR 2021
E ADDITIONAL RESULTS FOR REDQ, SAC-20, AND AVG
Due to lack of space, Figure in Section only compared REDQ with SAC-20 and AVG for the Ant environment. Figure presents the results for all four environments. We can that in all four environments, REDQ has much stronger performance and much lower std of bias compared to SAC-20 and AVG. Note in terms of average normalized bias, AVG is slightly closer zero in Ant compared to REDQ, and SAC-20 is a bit closer to zero in Humanoid compared to REDQ; however, their std of normalized bias consistently higher. This shows the importance of having a low std of the bias in addition to a close-to-zero average bias.
environment Interactions
cnvironment Interactions
envrrnmmnt intractions
(a) Performance, Hopper
(b) Average bias, Hopper
(c) Std of bias, Hopper
REDO
SAL:J0
AVG
Noee roum
(d) Performance, Walker2d
(e) Average bias, Walker2d
(f) Std of bias, Walker2d
REDO
SAC-20
Avergg return
Aowegge nommered
AVG
enviroment Internations
entirrment inceractions
endfronment interactions
Performance, Ant.
(h) Average bias, Ant
(i) Std of bias, Ant
SAC
Auerage ro3r
00
(i) Porformance, Humanoid
(k) Average bias, Humanoid
(1) Std bias, Humanoid
Figure 5: Performance, mean and std of normalized Q bias for REDQ, AVG, and SAC. All three algorithms have UTD ratio of 20.
21

---

Published as a conference paper at ICLR 2021
F REDQ AND SAC WITH AND WITHOUT POLICY DELAY
Note that the REDQ pseudocode, the number policy updates is always one for each data point collected. We set the UTD ratio for the policy update always be one in order to isolate the effect of additional policy updates from Q updates. Note in this way, REDQ, SAC-20 and SAC-1 all take the same number of policy updates. This helps show that the performance gain mainly comes from the additional Q updates.
Having lower number of policy updates can also be seen as a delayed policy update, or policy delay, and is a method that has been used in previous works to improve learning stability (Fujimoto al., 2018). In this section we discuss how delayed policy update, or policy delay, impact the performance of REDQ and SAC (with UTD of 20). Figure[Jcomppres REDQ and SAC-20 with and without policy delay (NPD for no policy delay). We can see that having the policy delay consistently makes the bias and std of bias lower and more stable, although they have smaller effect on REDQ than on SAC. Performance-wee REDQ sees improvement in Hopper and Humanoid, and becomes slightly worse in Walker2d and Ant. The results show that policy delay can be important under high UTD when the variance is properly controlled. However, with enough variance reduction, the effect of policy delay is diminished, and in some cases having more policy update can give better performance.
SAC always gets a performance boost with policy delay, while
22

---

Published as a conference paper at ICLR 2021
Aptrrp PROUT
nomobred
environment Interactions
environment Internctions
enwfromment interactions
(a) Performance, Hopper
(h) Average bias, Hopper
(c) Std of Bias, Hopper
REDO
REDO MPD
S4C-20
Avergg rours
SAC-25-1PD-
go temalzedd
1o cnvironment Interactions
environment Interactions
envirormnnt Interactions
(d) Performance, Walker2d
(c) Average bias, Walker2d
Std of Bias, Walker2d
HEUPC-PUU
Rureey toeed bien
Avcerpe mohmm
56C-29HPP
envecoment nite actons
ensrerment inceractions
environmett menk oo
(g) Performance, Ant
(h) Average bias, Ant
(i) Std of bias, Ant
REDO
SAC-20
Aeeragee retum
-1%
Man
ii) Performance, Humanoid
(k) Average bias, Humanoid
Std bias, Humanoid
Figure 6: Performance, mean and std of normalized Q bias of REDQ and SAC, with and without policy delay.
23

---

Published as a conference paper at ICLR 2021
G REDQ AND SAC WITH DIFFERENT UTD RATIOS
How do different UTD ratio values G impact the performance of REDQ and SAC? Figure com- pares the algorithms under UTD ratio values of I, 10 and 20 for the Ant environment. The results show that in the Ant environment, REDQ greatly benefits from larger UTD values, with UTD of 20 giving the best result. For SAC, performance improves slightly for UTD ratios of 5 and 10, but becomes much worse at 20. Looking at the normalized bias and the std of the bias, we see that changing the UTD ratio does change the values very much for REDQ. while for SAC, we see that as the UTD ratio increases, both the mean and the std of the bias becomes larger and more unstable.
ccom-
Averaye ndomm
REDC-UTD)
nomalodd
anvicomenn
inveaction
anstrnmmett Internttion
(a) Performance, Ant
(b) Average bias, Ant
(c) Std of bias, Ant
XAGATTI2
S4C UTD10
S4C-UTDS
Averag return
SACUTC1
nomeloed
15 enviromment Interactions
envrroment incercctions
enxtronment Interactions
(d) Performance, Ant.
(e) Average bias, Ant
(f) Std of bias, Ant
Figure 7: Performance, mean and std of normalized Q bias for REDQ, and SAC, with different UTD ratios, Ant environment.
24

---

Published as a conference paper at ICLR 2021
H ADDITIONAL RESULTS FOR WEIGHTED VARIANT
In this section we provide additional results for the Weighted variant. Figure shows the perfor- mance and bias comparison on all four environments. Results show that Weighted and REDQ have similar average bias and std of bias. In terms of performance, Weighed is worse in Ant and Hop- per, similar in Humanoid and slightly stronger in Walker2d. Overall REDQ seems to have stronger performance and is more robust. Randomness in the networks might help alleviate overfitting in the early stage, or improve exploration, as shown in previous studies (Osband al. 2016 Fortunato et al. 2018). This can be important since positive bias in Q learning-based methods can sometimes help exploration. This commonly referred to as optimistic initial values, or optimism in the face of uncertainty (Sutton & Barto 2018 Brafman & Tennenholtz 2002). Thus conservative Q estimates in recent algorithms can lead the problem pessimistic underexploration (Ciosek et al.) 2019). An interesting future work direction is study how robust and effective exploration be achieved without relying on optimistic estimates.
REDC
Weighord
Aveengg return
Interactors
environment intrracioon
envronment insraciions
(a) Performance, Hopper
(b) Average bias, Hopper
(c) Std of bias, Hopper
REDO Weightdd
Erronge: re0mm
anvvrcement intercctioss
Lt
anverontentt Interactions
enviromment interactions
(d) Performance, Walker2d
(e) Average bias, Walker2d
(I) Std of bias, Walker2d
REDO Weighted
Aterage 740m
pomaated
anvercmment interactions
WnVEremment Infernctoons
wnstrnmmett Infernatione
(g) Performance, Ant
(h) Average bias, Ant
(i) Std of bias, Ant
RED00 Weighted
Avergg returnerettmm return
nometoord
enviroement Interaations
insimmment Intercctoons
enstrement Inberactions
Performance, Humanoid
(k) Average bias, Humanoid
Std of bias, Humanoid
Figure 8: Performance, mean and std of normalized Q bias for REDQ and Weighted.
25


Reviews:
[{"review_id": "jQ5RrAdDQl7", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper proposes a new model-free algorithm called Randomized Ensemble Double Q Learning (REDQ) for the optimal control problem. Also, this paper empirically shows that the performance of REDQ is not worse than the model-based algorithm, MBPO. \n\nComments: \nPro. \n1. Empirical studies significantly show that REDQ takes less environment interactions but achieves much higher average return compared to SAC algorithm. Also, the performance of REDQ is even better than MBPO in the Hopper problem and Humanoid problem.\n2. The theoretical analysis introduces the relation among two hyper-parameters (M, N) and the expected random approximation error. \n\nCon. \n1. In Section 3.1 Theoretical Analysis, the theoretical result is not complete enough. The Maxmin Q-Learning paper, Lan et al. (2020), also proves that Maxmin Q-learning algorithm has a vanishing approximation variance (with N tends to infinity). This result is vaguely mentioned below Theorem 1 but there is no rigorously proof provided. \n2. The authors claim that the REDQ algorithm is at least no worse than MBPO. This statement is based on the empirical studies or intuitive explanations rather than theoretical analysis. It will be better to provide more comprehensive analysis of the algorithm. \n\n%--------------------------------%\nI thank the authors for clarifying my questions and concerns. The authors have included further theoretical developments in the revision, and they look satisfactory to me. Overall, I tend to accept this paper.", "extra_scores": {}, "extra_text": {}}, {"review_id": "_uIvVmQLj-K", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\nThe paper proposes three techniques that altogether greatly improves the performance of soft actor-critic (SAC), resulting in a new algorithm called REDQ. (1) A higher update-to-data ratio, which speeds up the critic update. (2) Using the average ensemble Q for the policy gradient, therefore reducing its variance. (3) Taking the min of a small subset of the ensemble Qs to compute the target Q, therefore reducing the Q bias. The paper also performs extensive ablation studies to prove the importance of each technique.\n\nRecommendation\nOverall I think the paper deserves an acceptance. The proposed solution is simple, effective, and justified.\n\nStrengths\n1. REDQ is simple and effective. Implementation requires little change to the backbone of SAC. The authors also provide example code. Fig 1 shows clear advantage over SAC.\n2. Ablation studies are rigorous: e.g. Fig 3 even studies fractional M = 2.5, when M = 3 is clearly under-performing.\n3. The paper is very well written. In particular, the most important algorithm block and experimental results are shown early, leading to a smooth reading experience. \n\nWeaknesses\n1. The paper analyzes the normalized standard deviation of Q bias, but in fact the gradient of Q against actions is more important (line 12, Alg 1). It would be great to see analysis on the gradient as well.\n\n2. Some (minor) missing studies. \n(a). I am surprised that “Weighted” performs much worse than REDQ  on Ant (Fig 3g). The authors suggest overfitting as a potential cause. But I am curious whether exploration is the real issue, and whether the same happens on other envs.\n(b). Algorithm 1 suggests training Q G times before training the policy once. Does training the policy more frequently help? It makes sense since the avg Q has lower variance.\n(c). Why not train up to 1, 3, 10 million steps as in the SAC paper (Fig 1)? Especially for Humanoid, The performance isn’t near 6,000 as reached in the SAC paper.\n\nOther feedbacks\nMujoco envs are rather deterministic and the noise comes from the policy itself. Have you considered other more noisy envs? The ensemble could have a larger impact there.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "7cI0qz49cYu", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work proposes a modification for double Q-learning, termed as randomized ensembled double Q-learning (REDQ). REDQ maintains $N$ different Q functions, and for each update, the target value is a minimization over $M$ randomly chosen Q functions, where $1 \\le M \\le N$. In addition, REDQ adopts a high update-to-data ratio to improve the sample efficiency. Empirical results show that the proposed method outperforms state-of-the-art model-based algorithms in certain tasks with continuous action space.\n\nOverall, I think this is a well written paper. \n\nPros:\n\n- The algorithmic idea of REDQ is quite intuitive and reasonable. In particular, setting $M$ and $N$ separately allows for more flexibility (compared with double Q and other variants): by increasing $M$, one can achieve a smooth transition from over-estimation of value functions to under-estimation (as validated by a simple theoretical analysis). Moreover, this idea is quite general and can be easily plugged into many existing off-policy model-free algorithms.\n\n- The numerical experiments are quite extensive. The results convincingly show that the proposed REDQ algorithm achieves a minor underestimation bias with low standard deviation, leading to better overall performance. In addition, REDQ is also computationally efficient.\n\nCons:\n\n- The novelty in the algorithmic idea of REDQ is a bit simple and not very significant. \n\n- The theoretical analysis of this work is quite limited, e.g. lacking the (most basic) asymptotic convergence analysis in the tabular case.\n\nA minor comment: it might be better to use \"\\gg\" and \"\\ll\" in latex, instead of \">>\" and \"<<\". ", "extra_scores": {}, "extra_text": {}}, {"review_id": "5lT-ZXnIXT", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "[Summary]\n\nThis paper proposes Randomized Ensembled Double Q-Learning (REDQ), a new model-free RL algorithm that aims to improve the sample efficiency over existing model-free methods. Experiments on Mujoco show that REDQ achieves better sample efficiency than popular model-free methods such as SAC and is comparable with model-based methods such as MBPO. The paper further provides extensive ablation studies that justify the necessity of the algorithmic components in REDQ and show that improved Q estimation bias may have been the key reason for the performance gain. The paper also provides some theoretical analysis of the Q estimation bias.\n\n[Pros]\n\n--- The empirical performance of REDQ seems rather strong: significantly better than SAC and can match or exceed MBPO depending on the environment.\n\n--- Section 3 provides a rather convincing explanation of the performance gain through the perspective of the Q estimation bias: REDQ manages to achieve a low bias in terms of both average and std across (s,a) pairs. In comparison SAC fails on both grounds, while AVG (naive ensemble without the in-target minimization) achieves a low std but still a rather high average. The theoretical analysis (Theorem 1) also helped improve my understanding on this front by illustrating how the factors (M, N) could affect the bias. \n\n--- The ablation study in Section 4 is very detailed and answers a lot of questions I had (e.g. importance of M, N) and I liked it a lot. \n\n--- Overall the paper is quite clearly written and conveys the message quite clearly.\n\n[Cons, and comments]\n\n--- My main concern is that the most similar approach Maxmin (Lan et al. 2020) which the authors cited multiple times was not comprehensively tested in the experiments. More concretely, Maxmin was not presented in the main plots (Figure 1 and 2) and only showed up (and in a modified fashion) as an ablation point in Figure 3 where it seemed like its performance was pretty bad. From the original Maxmin paper it seemed like they did not try Mujoco; is it the case that Maxmin did not really scale up to Mujoco? \n\nSpecifically, it is a bit disturbing that Maxmin did not appear in Figure 2 which studied the Q estimation bias. Compared with the baselines in that figure (SAC20, AVG), Maxmin sounds much better in terms of reducing the Q estimation error (it also has both ensemble and in-target minimization). I am quite curious how Maxmin does on the bias, and specifically if it does well on the bias but performs worse than REDQ, what is really going on.\n\n\n--- The key algorithmic novelty of REDQ seems to be the combination of two existing ideas: an ensemble of N=10 networks, as well as in-target minimization over only M=2 randomly sampled networks from the ensemble. I am not entirely sure whether this could be considered as of enough novelty in this area (I am not super familiar with the literature here, so authors / other reviewers please feel free to correct me if I am wrong.) Also, given that the ablation studies showed that having both parts (large N, small M) is indeed important, at this moment I am only thinking of this as a weak concern.\n\n------\nAfter rebuttal: Thank the authors for their efforts in the rebuttal and revision. The authors' response to the Maxmin question (along with the revised discussions) sound convincing to me. I would like to keep my original evaluation and would lean towards acceptance for this paper.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper develops an effective model-free algorithm that achieves high sample efficiency. The empirical performance is appealing, which is comparable to model-based policy optimization and significantly outperforms SAC. The paper is well-written, and contains rigorous ablation studies. Weakness: the theoretical analysis is Section 3.1 is not thorough yet,  and it would be helpful to include more numerical comparisons with the Maxmin approach by Lan et al. 
Decision: Accept (Poster)