summaries: This 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.

summaries: The 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.

summaries: 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.

abstractText: 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 modelfree 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 modelbased 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 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 1.

authors:
Rishabh Agarwal
Dale Schuurmans
Mohammad Norouzi

title: An optimistic perspective on offline reinforcement learning

venue: In International Conference on Machine Learning (ICML),

authors:
Oron Anschel
Nir Baram
Nahum Shimkin

title: Averaged-dqn: Variance reduction and stabilization for deep reinforcement learning

venue: In International Conference on Machine Learning,

authors:
Ronen I Brafman
Moshe Tennenholtz

title: R-max-a general polynomial time algorithm for nearoptimal reinforcement learning

venue: Journal of Machine Learning Research,

authors:
Jacob Buckman
Danijar Hafner
George Tucker
Eugene Brevdo
Honglak Lee

title: Sampleefficient reinforcement learning with stochastic ensemble value expansion

venue: In Advances in Neural Information Processing Systems,

authors:
Kamil Ciosek
Quan Vuong
Robert Loftin
Katja Hofmann

title: Better exploration with optimistic actor critic

authors:
Ignasi Clavera
Violet Fu
Pieter Abbeel

title: Model-augmented actor-critic: Backpropagating through paths

venue: arXiv preprint arXiv:2005.08068,

authors:
Kefan Dong
Yuping Luo
Tianhe Yu
Chelsea Finn
Tengyu Ma

title: On the expressivity of neural networks for deep reinforcement learning

venue: International Conference on Machine Learning (ICML),

authors:
Yan Duan
Xi Chen
Rein Houthooft
John Schulman
Pieter Abbeel

title: Benchmarking deep reinforcement learning for continuous control

authors:
Stefan Faußer
Friedhelm Schwenker

title: Neural network ensembles in reinforcement learning

venue: Neural Processing Letters,

authors:
Meire Fortunato
Mohammad Gheshlaghi Azar
Bilal Piot
Jacob Menick
Ian Osband
Alex Graves
Vlad Mnih
Remi Munos
Demis Hassabis
Olivier Pietquin

title: Noisy networks for exploration

authors:
Roy Fox
Ari Pakman
Naftali Tishby

title: Taming the noise in reinforcement learning via soft updates

venue: arXiv preprint arXiv:1512.08562,

authors:
Scott Fujimoto
Herke van Hoof
Dave Meger

title: Addressing function approximation error in actor-critic methods

venue: arXiv preprint arXiv:1802.09477,

authors:
Scott Fujimoto
David Meger
Doina Precup

title: Off-policy deep reinforcement learning without exploration

authors:
Tuomas Haarnoja
Aurick Zhou
Pieter Abbeel
Sergey Levine

title: Soft actor-critic: Offpolicy maximum entropy deep reinforcement learning with a stochastic actor

venue: arXiv preprint arXiv:1801.01290,

authors:
Tuomas Haarnoja
Aurick Zhou
Kristian Hartikainen
George Tucker
Sehoon Ha
Jie Tan
Vikash Kumar
Henry Zhu
Abhishek Gupta
Pieter Abbeel

title: Soft actor-critic algorithms and applications

venue: arXiv preprint arXiv:1812.05905,

authors:
Peter Henderson
Riashat Islam
Philip Bachman
Joelle Pineau
Doina Precup
David Meger

title: Deep reinforcement learning that matters

venue: In Thirty-Second AAAI Conference on Artificial Intelligence,

authors:
Riashat Islam
Peter Henderson
Maziar Gomrokchi
Doina Precup

title: Reproducibility of benchmarked deep reinforcement learning tasks for continuous control

venue: arXiv preprint arXiv:1708.04133,

authors:
Michael Janner
Justin Fu
Marvin Zhang
Sergey Levine

title: When to trust your model: Modelbased policy optimization

title: Do recent advancements in model-based deep reinforcement learning really improve data efficiency

venue: arXiv preprint arXiv:2003.10181,

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Aviral Kumar
Justin Fu
Matthew Soh
George Tucker
Sergey Levine

title: Stabilizing off-policy q-learning via bootstrapping error reduction

authors:
Arsenii Kuznetsov
Pavel Shvechikov
Alexander Grishin
Dmitry Vetrov

title: Controlling overestimation bias with truncated mixture of continuous distributional quantile critics

venue: arXiv preprint arXiv:2005.04269,

authors:
Hang Lai
Jian Shen
Weinan Zhang
Yong Yu

title: Bidirectional model-based policy optimization

venue: arXiv preprint arXiv:2007.01995,

authors:
Qingfeng Lan
Yangchen Pan
Alona Fyshe
Martha White

title: Maxmin q-learning: Controlling the estimation bias of q-learning

venue: arXiv preprint arXiv:2002.06487,

authors:
Eric Langlois
Shunshi Zhang
Guodong Zhang
Pieter Abbeel
Jimmy Ba

title: Benchmarking model-based reinforcement learning

venue: arXiv preprint arXiv:1907.02057,

authors:
Donghun Lee
Boris Defourny
Warren B Powell

title: Bias-corrected q-learning to control maxoperator bias in q-learning

venue: IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL),

authors:
Kimin Lee
Michael Laskin
Aravind Srinivas
Pieter Abbeel

title: Sunrise: A simple unified framework for ensemble learning in deep reinforcement learning

venue: arXiv preprint arXiv:2007.04938,

authors:
Zhunan Li
Xinwen Hou

title: Mixing update q-value for deep reinforcement learning

venue: In 2019 International Joint Conference on Neural Networks (IJCNN),

authors:
Timothy P Lillicrap
Jonathan J Hunt
Alexander Pritzel
Nicolas Heess
Tom Erez
Yuval Tassa
David Silver
Daan Wierstra

title: Continuous control with deep reinforcement learning

venue: arXiv preprint arXiv:1509.02971,

authors:
Lingheng Meng
Rob Gorbet
Dana Kulić

title: The effect of multi-step methods on overestimation in deep reinforcement learning

venue: arXiv preprint arXiv:2006.12692,

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Alex Graves
Ioannis Antonoglou
Daan Wierstra
Martin Riedmiller

title: Playing atari with deep reinforcement learning

venue: arXiv preprint arXiv:1312.5602,

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Andrei A Rusu
Joel Veness
Marc G Bellemare
Alex Graves
Martin Riedmiller
Andreas K Fidjeland
Georg Ostrovski

title: Human-level control through deep reinforcement learning

authors:
Ian Osband
Charles Blundell
Alexander Pritzel
Benjamin Van Roy

title: Deep exploration via bootstrapped dqn

authors:
Kei Ota
Tomoaki Oiki
Devesh K Jha
Toshisada Mariyama
Daniel Nikovski

title: Can increasing input dimensionality improve deep reinforcement learning

venue: arXiv preprint arXiv:2003.01629,

authors:
Aravind Rajeswaran
Igor Mordatch
Vikash Kumar

title: A game theoretic framework for model based reinforcement learning

venue: arXiv preprint arXiv:2004.07804,

authors:
Richard S Sutton
Andrew G Barto

title: Reinforcement learning: An introduction

venue: MIT press,

authors:
Sebastian Thrun
Anton Schwartz

title: Issues in using function approximation for reinforcement learning

venue: In Proceedings of the 1993 Connectionist Models Summer School Hillsdale, NJ. Lawrence Erlbaum,

authors:
Emanuel Todorov
Tom Erez
Yuval Tassa

title: Mujoco: A physics engine for model-based control

venue: In Intelligent Robots and Systems (IROS),

title: Asynchronous stochastic approximation and q-learning

venue: Machine learning,

title: Double q-learning

authors:
Hado Van Hasselt
Arthur Guez
David Silver

title: Deep reinforcement learning with double qlearning

venue: In AAAI,

authors:
Hado P van Hasselt
Matteo Hessel
John Aslanides

title: When to use parametric models in reinforcement learning

authors:
Che Wang
Yanqiu Wu
Quan Vuong
Keith Ross

title: Striving for simplicity and performance in off-policy drl: Output normalization and non-uniform sampling

authors:
Chi Zhang
Sanmukh Rao Kuppannagari
Viktor K Prasanna

title: Maximum entropy model rollouts: Fast model based policy optimization without compounding errors

venue: arXiv preprint arXiv:2006.04802,

authors:
Zongzhang Zhang
Zhiyuan Pan
Mykel J Kochenderfer

title: Weighted double q-learning

venue: In IJCAI,

heading: 1 INTRODUCTION

text:
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 sample efficiency by using a high Update-To-Data (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), is a state-of-the-art model-based algorithm which updates the agent with a 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-Critic (SAC), which is model-free and uses a UTD of 1, MBPO achieves much higher sample efficiency in the OpenAI 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 a model?
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-art 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 a UTD ratio that is 1, but unlike MBPO it is model-free, has no roll outs, and performs all updates with real data. In addition to using a 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 a 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 to: Keith Ross <keithwross@nyu.edu>.
zero for most of training, even when the UTD is very high. Furthermore, by adjusting the number of randomly selected Q-functions for in-target minimization, REDQ can control the average Q-function bias. In comparison with standard ensemble averaging and with SAC with a 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 a small ensemble and a 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 7x the sample efficiency of SAC to reach a 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 score at that point.
To ensure our 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 code1. For all algorithmic comparisons, we use the same codebase (except for MBPO, for which we use the authors’ code).

heading: 2 RANDOMIZED ENSEMBLED DOUBLE Q-LEARNING (REDQ)

text:
Janner et al. (2019) proposed Model-Based Policy Optimization (MBPO), which was shown to be much more sample efficient than popular model-free algorithms such as 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 a 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-art modelbased algorithm for the MuJoCo benchmark. The pseudocode for REDQ is shown in Algorithm 1. REDQ can be used with any standard off-policy model-free algorithm, such as SAC (Haarnoja et al., 2018b), SOP (Wang et al., 2019), TD3 (Fujimoto et al., 2018), or DDPG (Lillicrap et al., 2015). For the sake of concreteness, we use SAC in Algorithm 1. REDQ has the following key components: (i) To improve sample efficiency, the UTD ratio G is much greater than one; (ii) 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; (iii) To reduce over-estimation bias, the target for the Q-function includes a minimization over a random subsetM of the N Q-functions. The size of the subsetM 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 to the algorithm as Randomized Ensembled Double Q-learning (REDQ).
REDQ shares some similarities with Maxmin Q-learning (Lan et al., 2020), which also uses ensembles 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 in 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 1.
1Code and implementation tutorial can be found at: https://github.com/watchernyu/REDQ
Algorithm 1 Randomized Ensembled Double Q-learning (REDQ) 1: Initialize policy parameters θ, N Q-function parameters φi, i = 1, . . . , N , empty replay buffer D. Set target parameters φtarg,i ← φi, for i = 1, 2, . . . , N
2: repeat 3: Take one action at ∼ πθ(·|st). Observe reward rt, new state st+1. 4: Add data to buffer: D ← D ∪ {(st, at, rt, st+1)} 5: for G updates do 6: Sample a mini-batch B = {(s, a, r, s′)} from D 7: Sample a setM of M distinct indices from {1, 2, . . . , N} 8: Compute the Q target y (same for all of the N Q-functions):
y = r + γ ( min i∈M Qφtarg,i (s ′, ã′)− α log πθ (ã′ | s′) ) , ã′ ∼ πθ (· | s′)
9: for i = 1, . . . , N do 10: Update φi with gradient descent using
∇φ 1 |B| ∑
(s,a,r,s′)∈B
(Qφi(s, a)− y) 2
11: Update target networks with φtarg,i ← ρφtarg,i + (1− ρ)φi 12: Update policy parameters θ with gradient ascent using
∇θ 1 |B| ∑ s∈B
( 1
N N∑ i=1 Qφi (s, ãθ(s))− α log πθ (ãθ(s)|s)
) , ãθ(s) ∼ πθ(· | s)

heading: 2.1 EXPERIMENTAL RESULTS FOR REDQ

text:
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 a 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 to those reported in 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 is given in the Appendix.
Figure 1 shows the training curves for REDQ, MBPO, and SAC. For each algorithm, we plot the average return of 5 independent trials as the solid curve, and plot the standard deviation across 5 seeds as the transparent shaded region. For each environment, we train each algorithm for exactly the same number of environment interactions as done in the MBPO paper. Figure 1 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 at the end of training. These results taken together are perhaps counter-intuitive. They show that a simple modelfree algorithm can achieve as good or better sample-efficiency performance as the state-of-the-art 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 network and the policy network, we use a multi-layer perceptron with two hidden layers, each with 256 units. For MBPO, we use the default network architectures for the Q networks, policy network, and model ensembles (Janner et al., 2019). The Appendix provides a table comparing the number of parameters: REDQ uses fewer parameters than MBPO for all four environments, specifically, between
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.

heading: 3 WHY DOES REDQ SUCCEED WHEREAS OTHERS FAIL?

text:
REDQ is a simple model-free algorithm that matches the performance of a state-of-the-art modelbased algorithm. Key to REDQ’s sample efficiency is using a UTD 1. Why is it that SAC and ordinary ensemble averaging (AVG) cannot do as well as REDQ by simply increasing the UTD?
To address these questions, let Qπ(s, a) be the action-value function for policy π using the standard infinite-horizon discounted return definition. Let Qφ(s, a) be an estimate of Qπ(s, a), which is defined as the average of Qφi(s, a), i = 1, . . . , N , when using an ensemble. We define the bias of an estimate at state-action pair (s, a) to be Qφ(s, a) − Qπ(s, a). We are primarily interested in the accuracy of Qφ(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 is similar to 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, we obtain both the discounted Monte Carlo return and the estimated Q value using Qφ, 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 Qφ 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 it does not change the action selection. Thus near-uniform bias can be preferable to a highly non-uniform bias with a 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 std does not seem to have received much attention.
Since the MC return values can change significantly throughout training, to make comparisons more meaningful, we define the normalized bias of the estimate Qφ(s, a) to be (Qφ(s, a) − Qπ(s, a))/|Es̄,ā∼π[Qπ(s̄, ā)]|, which is simply the bias divided by the absolute value of the expected discounted MC return for state-action pairs sampled from the current policy. We focus on the normalized bias in our analysis since it helps show how large the bias is, compared to the scale of the current MC return.
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 as the underlying off-policy algorithm). The only difference is how the targets are calculated in lines 7 and 8 of Algorithm 1.
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 in 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 ofG = 20. In the later ablation section we also have a 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 2 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 a 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 is robust to random initial conditions.
SAC with a UTD ratio of 20 performs poorly for the most challenging environments Ant and Humanoid. For SAC-20, the high UTD ratio leads to an average bias that fluctuates during training. 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, as 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.
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-target minimization can give REDQ a further performance boost.

heading: 3.1 THEORETICAL ANALYSIS

text:
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 (1993) and extended in Lan et al. (2020). We do this for the tabular version of REDQ, for which the target for Qi(s, a) for each i = 1, . . . , N is:
r + γ max a′∈A min j∈M
Qj(s′, a′) (1)
where A is the finite action space, (s, a, r, s′) is a transition, andM is again a uniformly random subset from {1, . . . , N} with |M| = M . The complete pseudocode for tabular REDQ is provided in the Appendix.
Let Qi(s, a) − Qπ(s, a) be the pre-update estimation bias for the ith Q-function, where Qπ(s, a) is once again the ground-truth Q-value for the current policy π. We are interested in how the bias changes after an 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 (1) and the target when using the ground-truth:
ZM,N , r + γ max a′∈A min j∈M Qj(s′, a′)− (r + γ max a′∈A Qπ(s′, a′))
= γ(max a′∈A min j∈M Qj(s′, a′)−max a′∈A Qπ(s′, a′))
Here we write ZM,N to emphasize its dependence on both M and N . Following Thrun & Schwartz (1993) and Lan et al. (2020), fix s and assume each Qi(s, a) has a random approximation error eisa:
Qi(s, a) = Qπ(s, a) + eisa
where for each fixed s, {eisa} are zero-mean independent random variables such that {eisa} are identically distributed across i for each fixed (s, a) pair. Note that due to the zero-mean assumption, the expected pre-update estimation bias is E[Qi(s, a)−Qπ(s, a)] = 0. Thus if E [ ZM,N ] > 0, then the expected post-update bias is positive and there is a tendency for over-estimation accumulation; and if E [ ZM,N ] < 0, then there is a tendency for under-estimation accumulation.
Theorem 1. 1. For any fixed M , E [ ZM,N ] does not depend on N .
2. E [ Z1,N ] ≥ 0 for all N ≥ 1.
3. E [ ZM+1,N ] ≤ E [ ZM,N ] for any M < N .
4. Suppose that eisa ≤ c for some c > 0 for all s, a and i. Then there exists an M such that for all N ≥M , E [ ZM,N ] < 0.
Points 2-4 of the Theorem indicate that we can control the expected post-update bias E [ ZM,N ] , 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 sizeN 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 a strong assumption, namely, the error term is uniformly distributed. Because our assumption is much weaker, our proof methodology in the Appendix is very different.
We also consider a variant of REDQ where instead of choosing a random set of size M in the target, we calculate the target by taking the expected value over all possible subsets of size M . In this case, the target in the tabular version becomes
YM,N = r(s, a) + γ 1( N M ) ∑ B⊂N |B|=M max a′ min j∈B Qj(s′, a′)
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 N → ∞. We note, however, that in practice, some variance in the target may be beneficial in reducing overfitting or help exploration. We can retain some variance by keeping N finite or using the unweighted REDQ scheme.
Let vM := Var(maxa′ minj∈B Qj(s′, a′)) for any subset B ⊂ N where |B| = M . (It is easily seen that vM only depends on M and not only the specific elements of B.)
Theorem 2. Var(YM,N ) ≤ GM (N)
for some function GM (N) satisfying
lim N→∞
GM (N)
M2vM/N = 1
Consequently, lim N→∞ Var(YM,N ) = 0
Also in the Appendix we show that the tabular version of REDQ convergences to the optimal Q function with probability one.

heading: 4 REDQ VARIANTS AND ABLATIONS

text:
In this section, we use ablations to provide further insight into REDQ. We focus on the Ant environment. We first look at how the ensemble size N affects REDQ. The top row in Figure 3 shows REDQ with N = 2, 3, 5, 10, 15. We can see that when we increase the ensemble size, we generally get a more stable average bias, a lower std of bias, and stronger performance. The result shows that even a small ensemble (e.g., N = 5) can greatly help in stabilizing bias accumulation when training under high UTD.
The middle row of Figure 3 shows how M , the in-target minimization parameter, can affect performance. When M is not an integer, e.g., M = 1.5, for each update, with probability 0.5 only one
randomly-chosen 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 Figure 3 shows the results for different target computation methods. The Maxmin curve in the figures is a 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 a 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 in 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-dimensional 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) is 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: it is similar to ensemble average (AVG), but with more randomization (Agarwal et al., 2020).
For Weighted, the target is computed as the expectation of all the REDQ targets, where the expectation is taken over all N -choose-2 pairs of Q-functions. This leads to a formula that is 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 1 can be considered as a random-sample 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.
From Figure 3 we see 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 Q bias, REM has a 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.

heading: 4.1 IMPROVING REDQ WITH AUXILIARY FEATURE LEARNING

text:
We now investigate whether we can further improve the performance of REDQ by incorporating better representation learning? Ota et al. (2020) recently proposed the online feature extractor network (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 together 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.
REDQ-OFE achieves 7x the sample efficiency of SAC to reach 5000 on Ant and Humanoid, and outperforms MBPO with 3.12x and 1.26x the performance of MBPO at 150K and 300K data, respectively. A more detailed performance comparison table can be found in the Appendix.

heading: 5 RELATED WORK

text:
It has long been recognized that maximization bias in Q-learning can significantly impede learning. Thrun & Schwartz (1993) first highlighted the existence of maximization bias. Van Hasselt (2010) proposed Double Q-Learning to 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 to deep Q networks (DQN) (Mnih et al., 2013; 2015) gives a major performance boost for the Atari games benchmark. For continuous-action spaces, Fujimoto 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 et al., 2013), using weighted Q estimates (Zhang et al., 2017; Li & Hou, 2019), penalizing deterministic policies at early stage of training (Fox et al., 2015), using multi-step methods (Meng et al., 2020), performing weighted Bellman updates to mitigate error propagation (Lee et al., 2020), and truncating sampled Q estimates with distributional networks (Kuznetsov et al., 2020).
It has also long been recognized that using ensembles can improve the performance of DRL algorithms (Faußer & Schwenker, 2015; Osband et al., 2016). For Q-learning based methods, Anschel et al. (2017) use the average of multiple Q estimates to reduce variance. Agarwal et al. (2020) introduced 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 in discrete action domains it has been found that fine-tuning DQN variants, including the UTD, can boost performance, little experimental or theoretical analysis is given to explain how this improvement is obtained (Kielak, 2020; van Hasselt et al., 2019).
To address some of the critical issues in model-based learning (Langlois et al., 2019), recent methods such as MBPO combine a model ensemble with a carefully controlled rollout horizon to obtain better performance (Janner et al., 2019; 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).

heading: 6 CONCLUSION

text: The contributions of this paper are as follows. (1) We propose a simple model-free algorithm that attains sample efficiency that is as good as or better than state-of-the-art 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, we 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.

heading: A THEORETICAL RESULTS

text:
A.1 TABULAR VERSION OF REDQ
In the tabular algorithm below, for clarity we use G = 1.
Algorithm 2 Tabular REDQ 1: Initialize { Qi(s, a), s ∈ S, a ∈ A }N i=1
, 2: repeat 3: Choose a ∈ A based on { Qi(s, a) }N i=1 , observe r, s′
4: Randomly choose a subsetM of size M from { 1, .., N } 5: y = r + γmaxa′∈Aminj∈MQj(s′, a′) 6: for i = 1, . . . , N do: 7: Qi(s, a)← Qi(s, a) + α(y −Qi(s, a)) 8: s← s′ 9: until end
Alternatively in Algorithm 2, at each iteration we could just update one of the Qi 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 Xm and let τ = inf{x : F (x) > 0}. Also let Ym = min{X1, X2, . . . , Xm}. Then Y1, Y2, . . . converges to τ almost surely.
Proof:
Let Fm(x) be the cdf of Ym. Since X1, ..., Xm are independent,
Fm(x) = 1− [1− F (x)]m
For x < τ , Fm(x) = 0 since F (x) = 0. For x > τ , Fm(x) m→∞−−−−→ 1. Therefore, Ym weakly converges to τ .
Moreover, for each ω ∈ Ω, {Ym(ω)} is a decreasing sequence. So {Ym(ω)} either converges to a real number or −∞. Therefore Ym → Y almost surely for some random variable Y . Combined with the result that Ym d−→ τ , we can conclude that
Ym a.s.−−→ τ
Proof of Theorem 1: 1. Let B1, B2 be two subsets of N = { 1, ..., N }
of size M . First of all, since {Qj(s, a)}Nj=1 are i.i.d for any a ∈ A, minj∈B1 Qj(s, a) and minj∈B2 Qj(s, a) are identically distributed. Furthermore, since Qj(s, a) are independent for all a ∈ A and 1 ≤ j ≤ N , { minj∈B Q j(s, a) } a∈A are independent for any B ⊂ N . Denote the distribution function of maxa minj∈B1 Qj(s, a) as F1(x) and the distribution function of maxa minj∈B2 Q j(s, a) as F2(x). Then for any x ∈ R,
F1(x) = P (
max a min j∈B1
Qj(s, a) ≤ x ) = P ( ∩a∈A {min
i∈B1 Qj(s, a) ≤ x} ) = ∏ a∈A P ( min j∈B1 Qj(s, a) ≤ x ) = ∏ a∈A P ( min j∈B2 Qj(s, a) ≤ x )
= P (
max a min j∈B2
Qj(s, a) ≤ x )
= F2(x)
Therefore, we have proved that maxa minj∈B1 Q j(s, a) and maxa minj∈B2 Q j(s, a) are identically distributed. Then
E [ ZM,N ] = γE [ (max
a min j∈M Qj(s, a)−max a
Qπ(s, a)) ]
= γE [ 1(
N M ) ∑ B⊂N |B|=M max a min j∈B Qj(s, a) ] − γmax a Qπ(s, a)
= γ ( E [
max a min 1≤j≤M
Qj(s, a) ] −max
a Qπ(s, a) ) which does not depend on N .
2. It follows from 1 that E [ Z1,N ] = γ ( E [
max a
Q1(s, a) ] −max
a Qπ(s, a) ) Since maxaQ1(s, a) ≥ Q1(s, a′) for all a′ ∈ A, we have
E [
max a
Q1(s, a) ] ≥ E [ Q1(s, a′) ] for all a′ ∈ A. Consequently,
E [
max a
Q1(s, a) ] ≥ max a E [ Q1(s, a) ] = max a Qπ(s, a)
Hence
E [ Z1,N ] = γ ( E [
max a
Q1(s, a) ] −max
a Qπ(s, a)
) ≥ 0
3. Since maxa min1≤j≤M Qj(s, a) ≥ maxa min1≤j≤M+1Qj(s, a),
E [ ZM,N ] = γ ( E [
max a min 1≤j≤M
Qj(s, a) ] −max
a Qπ(s, a) ) ≥ γ ( E [
max a min 1≤j≤M+1
Qj(s, a) ] −max
a Qπ(s, a)
) = E [ ZM+1,N ] 4. Let Fa(x) be the cdf of Qj(s, a) and let τa = inf{x : Fa(x) > 0}. Here we assume the approximation error eisa is non-trivial, which implies τa < Q
π(s, a). Note that τa can be equal to −∞. Let
YMa = min 1≤i≤M Qj(s, a)
From Lemma 1 we have YMa converges to τa almost surely for each a. Because the action space is finite, it therefore follows that
YM = max a YMa
converges almost surely to τ = maxa τa. Furthermore, for each a we have
YMa = min 1≤j≤M Qj(s, a) ≥ min 1≤j≤M+1 Qj(s, a) = YM+1a
from which it follows that YM ≥ YM+1. Thus {YM} is a monotonically decreasing sequence. We also note that due to the assumption eisa ≤ c for all a and i, and because Qπ(s, a) is finite for all s and a, it follows that YM ≤ d for all M for a finite d. Thus {YM} is a bounded-above, monotonically-decreasing sequence of random variables which converges almost surely to τ . We can therefore apply the monotone convergence theorem, giving
E [ ZM,N ] = γ ( E [
max a min 1≤j≤M
Qj(s, a) ] −max
a Qπ(s, a) ) = γ ( E[max
a YMa ]−max a Qπ(s, a)
) M→∞−−−−→ γ ( max a τa −max a Qπ(s, a) ) < 0,
where the last inequality follows from τa < Qπ(s, a) for all actions a.
A.3 PROOF OF THEOREM 2
For convenience, define YB = maxa′ minj∈B Qj(s′, a′). Suppose N > 2M .
Var(YM,N ) = γ2( N M )2 Var( ∑ B⊂N |B|=M YB)
= γ2(M !)2( ΠM−1i=0 (N − i) )2 [ ∑ B⊂N Var(YB) + 2 · ∑ B1,B2⊂N B1 6=B2 Cov(YB1 , YB2) ]
Let A = ∑ B1,B2⊂N B1 6=B2
Cov(YB1 , YB2), which consists of((N M ) 2 ) = 1 2 · N ! (N −M)!M ! · (
N ! (N −M)!M ! − 1 )
= 1
2(M !)2 ·ΠM−1i=0 (N − i) 2 − N ! 2 ·M !(N −M)!
terms. ((NM)
2
) can be seen as a polynomial function of N with degree 2M . The coefficient for the
term N2M is 12(M !)2 . The coefficient for the term N 2M−1 is 12(M !)2 · (−2 ∑M−1 i=0 i).
Note that YB1 and YB2 are independent ifB1∩B2 = ∅. The total number of different pairs (B1, B2) such that B1 ∩B2 = ∅ is(
N
2M
) · ( 2M
M
) · 1
2 =
1 2(M !)2 · N ! (N − 2M)! =
1
2(M !)2 ·Π2M−1i=0 (N − i)
This is again a polynomial function of N with degree 2M . The coefficient of the term N2M is 1
2(M !)2 . The coefficient of the term N 2M−1 is 12(M !)2 · (− ∑2M−1 i=0 i). So the number of non-zero terms in A is at most 1
2(M !)2 ·ΠM−1i=0 (N − i) 2 − N ! 2 ·M !(N −M)! − 1 2(M !)2 ·Π2M−1i=0 (N − i)
= M2
2(M !)2 ·N2M−1 +O(N2M−2)
Moreover, by Cauchy-Schwarz inequality, for any B1, B2 ⊂ N Cov(YB1 , YB2) ≤ √
Var(YB1) ·Var(YB2) = vM Therefore,
A ≤ [ M 2
2(M !)2 ·N2M−1 +O(N2M−2)]vM
which implies
Var(YM,N ) = γ2(M !)2( ΠM−1i=0 (N − i) )2 [ ∑ B⊂N Var(YB) + 2 · ∑ B1,B2⊂N B1 6=B2 Cov(YB1 , YB2) ]
= γ2(M !)2( ΠM−1i=0 (N − i) )2 [ ∑ B⊂N Var(YB) + 2A ]
≤ γ2 [ M2 · N 2M−1
ΠM−1i=0 (N − i)2 +O(
1 N2 ) ] vM N→∞−−−−→ 0
Moreover,
lim N→∞ M2vM/N[ M2 · N2M−1
ΠM−1i=0 (N−i)2 +O( 1N2 )
] vM = lim N→∞ ΠM−1i=0 (N − i)2 N2M = 1
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 to the optimal Q function. In fact, for our Weighted scheme, where we take the expectation over all sets of sizeM , the convergence conditions in Lan et al. (2020) are fully satisfied.
For the randomized case, only very minor changes are needed in the proof in Lan et al. (2020). Note that in the case of REDQ, the underlying deterministic target is:
F ( Q1, Q2, . . . , QN ) (s, a) = r(s, a) + γ ∑ s′ p (s′ | s, a) ∑ B⊂N |B|=M 1( N M ) max a′ min j∈B Qj(s′, a′)
Let T be the operator that concatenates N identical copies of F , so that T : RS×A×N → RS×A×N where S and A are the cardinalities of the state and action spaces, respectively. It is easy to show that the operator T is a contraction with the l∞ norm. The stochastic approximation noise term is given by
ω(s, a) = R− r(s, a) + γ [
max a′ min j∈B Qj(s′, a′)− ∑ s′ p (s′ | s, a) ∑ B⊂N |B|=M 1( N M ) max a′ min j∈B Qj(s′, a′) ]
It is straightforward to show E [ ω2(s, a) | Fpast ] ≤ Var (R | s, a) + max
1≤i≤N max s′,a′
( Qi(s′, a′) )2 (2)
As in Lan et al. (2020), it follows from the contraction property and (2) that REDQ converges with probability 1 to the optimal Q function (Tsitsiklis, 1994; Bertsekas & Tsitsiklis, 1996).

heading: B HYPERPARAMETERS AND IMPLEMENTATION DETAILS

text:
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). Table 1 gives a list of hyperparameter used in the experiments. 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 MuJoCo environments, which is the same value that was used in the MBPO paper. Thus most of the hyperparameters are made to be the same as in the MBPO paper to ensure fairness and consistency in comparisons.
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 easily lead to complete divergence on SAC-20. Sampling a 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 (Haarnoja et al., 2018a; Fujimoto et al., 2018; Janner et al., 2019).
For the REDQ-OFE experiments, we implemented a minimal version of the OFENet in 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 is we now first collect 20,000 random data points (which is 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 4. We tried a simple hyperparameter search on Ant with 200,000, 100,000 and 50,000 pre-train updates, and learning rates of 1e-4, 3e-4, 5e-4, and a OFENet UTD of 1, 4 and 20. However, the results are not very different. It is possible that better results can be obtained through a more extensive hyperparameter search or other modifications.
B.1 EFFICIENT CALCULATION OF TARGET FOR WEIGHTED VERSION OF REDQ
In section 4 we provided experimental results for the Weighted version of REDQ. Recall that in this version, instead of sampling a random subsetM in the target, we average over all subsets B in
{1, . . . , N} of size M :
y = r + γ 1( N M ) ∑ B ( min i∈B Qφtarg,i (s ′, ã′) ) In practice, however, we do not need to sum over all N choose M subsets. Instead we can re-order the indices so that
Qφtarg,i (s ′, ã′) ≤ Qφtarg,i+1 (s′, ã′)
for i = 1, . . . , N − 1. After the re-ordering, we can use the identity:
1( N M ) ∑ B ( min i∈B Qφtarg,i (s ′, ã′) ) = 1( N M ) N−M+1∑ i=1 ( N − i M − 1 ) Qφtarg,i (s ′, ã′)

heading: C SAMPLE EFFICIENCY COMPARISON FOR REDQ, SAC AND MBPO

text:
The sample efficiency claims made in the main paper are based on Table 2 and Table 3. Table 2 shows that compared to 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. If we average all the numbers for the four environments, then REDQ is 5.0x as sample efficient, and 6.4x after including OFE results.
Table 3 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 et 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 the performance of SAC at 150K and 300K. REDQ is also stronger than MBPO, with 1.4x and 1.1x the performance of MBPO at 150K and 300K. If we include the results of REDQ-OFE, 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 at 150 and 300K.

heading: D NUMBER OF PARAMETERS COMPARISON

text: Table 4 gives the number of parameters for MBPO, REDQ and REDQ-OFE, for all four environments. As discussed in the main paper, REDQ uses fewer parameters than MBPO for all four 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 parameters on Ant and Humanoid. In particular, it is surprising that REDQ-OFE can achieve a much stronger result on Humanoid with much fewer parameters.

heading: E ADDITIONAL RESULTS FOR REDQ, SAC-20, AND AVG

text: Due to lack of space, Figure 2 in Section 3 only compared REDQ with SAC-20 and AVG for the Ant environment. Figure 5 presents the results for all four environments. We can see 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 to 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 is consistently higher. This shows the importance of having a low std of the bias in addition to a close-to-zero average bias.

heading: F REDQ AND SAC WITH AND WITHOUT POLICY DELAY

text:
Note that in the REDQ pseudocode, the number of policy updates is always one for each data point collected. We set the UTD ratio for the policy update to 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 a 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 et 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 6 compares 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 a smaller effect on REDQ than on SAC. Performance-wise SAC always gets a performance boost with policy delay, while 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 not 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.

heading: G REDQ AND SAC WITH DIFFERENT UTD RATIOS

text: How do different UTD ratio values G impact the performance of REDQ and SAC? Figure 7 compares the two algorithms under UTD ratio values of 1, 5, 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 not 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.

heading: H ADDITIONAL RESULTS FOR WEIGHTED VARIANT

text: In this section we provide additional results for the Weighted variant. Figure 8 shows the performance 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 Hopper, 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 et al., 2016; Fortunato et al., 2018). This can be important since positive bias in Q learning-based methods can sometimes help exploration. This is 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 to the problem of pessimistic underexploration (Ciosek et al., 2019). An interesting future work direction is to study how robust and effective exploration can be achieved without relying on optimistic estimates.

title: RANDOMIZED ENSEMBLED DOUBLE Q-LEARNING: LEARNING FAST WITHOUT A MODEL


summaries: The method introduces the DIDA architecture to learn from distributions and be invariant to feature ordering and size.  The authors extend the ideas proposed by Maron et al. (2020) to the continuous domain and generalize their results.  The experiments are done on two tasks.  The patch identification (out-of-distribution test) clearly show the invariance to feature and dataset size. Nevertheless, it is not clear whether the method is invariant to feature permutation.  The performance model task shows properties of the architecture to predict global structures of the dataset within their meta-features.

summaries: The paper presents a neural network layer designed to process distribution samples that is invariant to permutations of the samples and the features. The proposed method is compared empirically to DSS, which achieves the same types of invariance but is restricted to point sets rather than discrete or continuous probability distributions. The two tasks used for the empirical evaluation in the paper are: a) patch identification (are two blocks of data extracted from the same original dataset?) and b) model configuration assessment (is one configuration of a learning algorithm going to produce a more accurate model for a particular dataset than another one?). On the first task, the paper compares to models built using Dataset2Vec embeddings as well as DSS. On the second task, the paper compares to handcrafted features as well as DSS. In both tasks, the proposed method produces more accurate predictors than DSS, etc. The paper also has some theoretical results regarding the universality of the proposed architecture and its robustness w.r.t. Lipschitz-bounded transformations.

summaries: This paper proposes a novel set/distribution representation architecture DIDA, which leverages pairwise embedding of the set’s elements. The method can be used to represent discrete and continuous distribution representation. The authors also provide the theoretical proofs of the universality of the invariant layers, the local consistency. The experiments show that the architecture improves some dataset representation tasks

abstractText: Recent advances in deep learning from probability distributions successfully achieve classification or regression from distribution samples, thus invariant under permutation of the samples. The first contribution of the paper is to extend these neural architectures to achieve invariance under permutation of the features, too. The proposed architecture, called DIDA, inherits the NN properties of universal approximation, and its robustness with respect to Lipschitz-bounded transformations of the input distribution is established. The second contribution is to empirically and comparatively demonstrate the merits of the approach on two tasks defined at the dataset level. On both tasks, DIDA learns meta-features supporting the characterization of a (labelled) dataset. The first task consists of predicting whether two dataset patches are extracted from the same initial dataset. The second task consists of predicting whether the learning performance achieved by a hyper-parameter configuration under a fixed algorithm (ranging in k-NN, SVM, logistic regression and linear SGD) dominates that of another configuration, for a dataset extracted from the OpenML benchmarking suite. On both tasks, DIDA outperforms the state of the art: DSS and DATASET2VEC architectures, as well as the models based on the hand-crafted meta-features of the literature.

authors:
Shai Ben-David
John Blitzer
Koby Crammer
Fernando Pereira

title: Analysis of representations for domain adaptation

venue: Advances in Neural Information Processing Systems

authors:
Shai Ben-David
John Blitzer
Koby Crammer
Alex Kulesza
Fernando Pereira
Jennifer Wortman Vaughan

title: A theory of learning from different domains

venue: Machine Learning,

authors:
Taco Cohen
Max Welling

title: Group equivariant convolutional networks

venue: Proceedings of The 33rd International Conference on Machine Learning,

authors:
David A. Cox
John Little
Donal O’Shea

title: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3/e (Undergraduate Texts in Mathematics)

title: Approximation by superpositions of a sigmoidal function

venue: Mathematics of control, signals and systems,

authors:
Gwendoline De Bie
Gabriel Peyré
Marco Cuturi

title: Stochastic deep networks

venue: Proceedings of the 36th International Conference on Machine Learning,

authors: Casey Graff. UCI machine learning repository.

title: URL http://archive

authors:
Chelsea Finn
Kelvin Xu
Sergey Levine

title: Probabilistic model-agnostic meta-learning

authors:
Robert Gens
Pedro M Domingos

title: Deep symmetry networks

authors:
Jason Hartford
Devon R Graham
Kevin Leyton-Brown
Siamak Ravanbakhsh

title: Deep models of interactions across sets

venue: Proceedings of the 35th International Conference on Machine Learning,

authors:
Tatsunori Hashimoto
David Gifford
Tommi Jaakkola

title: Learning population-level diffusions with generative rnns

authors:
Mikael Henaff
Joan Bruna
Yann LeCun

title: Deep convolutional networks on graph-structured data

authors:
Geoffrey Hinton
Li Deng
Dong Yu
George E Dahl
Abdel-rahman Mohamed
Navdeep Jaitly
Andrew Senior
Vincent Vanhoucke
Patrick Nguyen
Tara N Sainath

title: Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups

venue: IEEE Signal processing magazine,

authors:
Frank Hutter
Lars Kotthoff
Joaquin Vanschoren (eds

title: Automated Machine Learning: Methods, Systems, Challenges. Springer, 2018

authors:
Nicolas Keriven
Gabriel Peyré

title: Universal invariant and equivariant graph neural networks

authors:
Risi Kondor
Shubhendu Trivedi

title: On the generalization of equivariance and convolution in neural networks to the action of compact groups

venue: Proceedings of The 35th International Conference on Machine Learning,

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks. Advances in neural information processing

authors:
Moshe Leshno
Vladimir Ya Lin
Allan Pinkus
Shimon Schocken

title: Multilayer feedforward networks with a nonpolynomial activation function can approximate any function

venue: Neural networks,

authors:
Haggai Maron
Heli Ben-Hamu
Nadav Shamir
Yaron Lipman

title: Invariant and equivariant graph networks

venue: 7th International Conference on Learning Representations,

authors:
Haggai Maron
Ethan Fetaya
Nimrod Segol
Yaron Lipman

title: On the universality of invariant networks

authors:
Haggai Maron
Or Litany
Gal Chechik
Ethan Fetaya

title: On learning sets of symmetric elements

venue: International Conference on Machine Learning (ICML),

authors:
Mario A. Muñoz
Laura Villanova
Davaatseren Baatar
Kate Smith-Miles

title: Instance spaces for machine learning classification

authors:
Mario A Muñoz
Laura Villanova
Davaatseren Baatar
Kate Smith-Miles

authors:
Valerio Perrone
Rodolphe Jenatton
Matthias W Seeger
Cedric Archambeau

title: Scalable hyperparameter transfer learning

authors:
Bernhard Pfahringer
Hilan Bensusan
Christophe G. Giraud-Carrier

title: Meta-learning by landmarking various learning algorithms

venue: Proceedings of the Seventeenth International Conference on Machine Learning,

authors:
Charles R Qi
Hao Su
Kaichun Mo
Leonidas J Guibas

title: Pointnet: Deep learning on point sets for 3d classification and segmentation

venue: Proc. Computer Vision and Pattern Recognition (CVPR),

authors:
Qazi Inamur Rahman
Gerhard Schmeisser

title: Analytic theory of polynomials

authors:
Siamak Ravanbakhsh
Jeff Schneider
Barnabás Póczos

title: Equivariance through parametersharing

venue: Proceedings of the 34th International Conference on Machine Learning,

title: The algorithm selection problem

venue: Advances in Computers,

title: Optimal transport for applied mathematicians

venue: Birkäuser, NY,

authors:
Nimrod Segol
Yaron Lipman

title: On universal equivariant set networks

venue: 8th International Conference on Learning Representations,

title: Symmetries and discriminability in feedforward network architectures

venue: IEEE Transactions on Neural Networks,

authors:
Jost Tobias Springenberg
Aaron Klein
Stefan Falkner
Frank Hutter

title: Bayesian optimization with robust bayesian neural networks

authors:
Oriol Vinyals
Samy Bengio
Manjunath Kudlur

title: Order matters: Sequence to sequence for sets

venue: 4th International Conference on Learning Representations,

title: The lack of A priori distinctions between learning algorithms

venue: Neural Computation,

authors:
Jeffrey Wood
John Shawe-Taylor

title: Representation theory and invariant neural networks

venue: Discrete applied mathematics,

authors:
Jaesik Yoon
Taesup Kim
Ousmane Dia
Sungwoong Kim
Yoshua Bengio
Sungjin Ahn

title: Bayesian model-agnostic meta-learning

heading: 1 INTRODUCTION

text:
Deep networks architectures, initially devised for structured data such as images (Krizhevsky et al., 2012) and speech (Hinton et al., 2012), have been extended to enforce some invariance or equivariance properties (Shawe-Taylor, 1993) for more complex data representations. Typically, the network output is required to be invariant with respect to permutations of the input points when dealing with point clouds (Qi et al., 2017), graphs (Henaff et al., 2015) or probability distributions (De Bie et al., 2019). The merit of invariant or equivariant neural architectures is twofold. On the one hand, they inherit the universal approximation properties of neural nets (Cybenko, 1989; Leshno et al., 1993). On the other hand, the fact that these architectures comply with the requirements attached to the data representation yields more robust and more general models, through constraining the neural weights and/or reducing their number.
Related works. Invariance or equivariance properties are relevant to a wide range of applications. In the sequence-to-sequence framework, one might want to relax the sequence order (Vinyals et al., 2016). When modelling dynamic cell processes, one might want to follow the cell evolution at a macroscopic level, in terms of distributions as opposed to, a set of individual cell trajectories (Hashimoto et al., 2016). In computer vision, one might want to handle a set of pixels, as opposed to a voxellized representation, for the sake of a better scalability in terms of data dimensionality and computational resources (De Bie et al., 2019).
Neural architectures enforcing invariance or equivariance properties have been pioneered by (Qi et al., 2017; Zaheer et al., 2017) for learning from point clouds subject to permutation invariance or equivariance. These have been extended to permutation equivariance across sets (Hartford et al., 2018). Characterizations of invariance or equivariance under group actions have been proposed in the finite (Gens & Domingos, 2014; Cohen & Welling, 2016; Ravanbakhsh et al., 2017) or infinite case (Wood & Shawe-Taylor, 1996; Kondor & Trivedi, 2018).
On the theoretical side, (Maron et al., 2019a; Keriven & Peyré, 2019) have proposed a general characterization of linear layers enforcing invariance or equivariance properties with respect to the whole permutation group on the feature set. The universal approximation properties of such architectures have been established in the case of sets (Zaheer et al., 2017), point clouds (Qi et al., 2017), equivariant point clouds (Segol & Lipman, 2019), discrete measures (De Bie et al., 2019), invariant (Maron et al., 2019b) and equivariant (Keriven & Peyré, 2019) graph neural networks. The approach most related to our work is that of (Maron et al., 2020), handling point clouds and presenting a neural architecture invariant w.r.t. the ordering of points and their features. In this paper, the proposed distribution-based invariant deep architecture (DIDA) extends (Maron et al., 2020) as it handles (discrete or continuous) probability distributions instead of point clouds. This enables to leverage the topology of the Wasserstein distance to provide more general approximation results, covering (Maron et al., 2020) as a special case.
Motivations. A main motivation for DIDA is the ability to characterize datasets through learned meta-features. Meta-features, aimed to represent a dataset as a vector of characteristics, have been mentioned in the ML literature for over 40 years, in relation with several key ML challenges: (i) learning a performance model, predicting a priori the performance of an algorithm (and the hyperparameters thereof) on a dataset (Rice, 1976; Wolpert, 1996; Hutter et al., 2018); (ii) learning a generic model able of quick adaptation to new tasks, e.g. one-shot or few-shot, through the so-called meta-learning approach (Finn et al., 2018; Yoon et al., 2018); (iii) hyper-parameter transfer learning (Perrone et al., 2018), aimed to transfer the performance model learned for a task, to another task. A large number of meta-features have been manually designed along the years (Muñoz et al., 2018), ranging from sufficient statistics to the so-called landmarks (Pfahringer et al., 2000), computing the performance of fast ML algorithms on the considered dataset. Meta-features, expected to describe the joint distribution underlying the dataset, should also be inexpensive to compute. The learning of meta-features has been first tackled by (Jomaa et al., 2019) to our best knowledge, defining the DATASET2VEC representation. Specifically, DATASET2VEC is provided two patches of datasets, (two subsets of examples, described by two (different) sets of features), and is trained to predict whether those patches are extracted from the same initial dataset.
Contributions. The proposed DIDA approach extends the state of the art (Maron et al., 2020; Jomaa et al., 2019) in two ways. Firstly, it is designed to handle discrete or continuous probability distributions, as opposed to point sets (Section 2). As said, this extension enables to leverage the more general topology of the Wasserstein distance as opposed to that of the Haussdorf distance (Section 3). This framework is used to derive theoretical guarantees of stability under bounded distribution transformations, as well as universal approximation results, extending (Maron et al., 2020) to the continuous setting. Secondly, the empirical validation of the approach on two tasks defined at the dataset level demonstrates the merit of the approach compared to the state of the art (Maron et al., 2020; Jomaa et al., 2019; Muñoz et al., 2018) (Section 4).
Notations. �1; m� denotes the set of integers {1, . . .m}. Distributions, including discrete distributions (datasets) are noted in bold font. Vectors are noted in italic, with x[k] denoting the k-th coordinate of vector x.

heading: 2 DISTRIBUTION-BASED INVARIANT NETWORKS FOR META-FEATURE LEARNING

text: This section describes the core of the proposed distribution-based invariant neural architectures, specifically the mechanism of mapping a point distribution onto another one subject to sample and feature permutation invariance, referred to as invariant layer. For the sake of readability, this section focuses on the case of discrete distributions, referring the reader to Appendix A for the general case of continuous distributions.

heading: 2.1 INVARIANT FUNCTIONS OF DISCRETE DISTRIBUTIONS

text:
Let z= {(xi, yi) ∈ Rd, i ∈ �1; n�} denote a dataset including n labelled samples, with xi ∈ RdX an instance and yi ∈ RdY the associated multi-label. With dX and dY respectively the dimensions
of the instance and label spaces, let d def.= dX +dY . By construction, z is invariant under permutation on the sample ordering; it is viewed as an n-size discrete distribution 1n �n i=1 δzi in Rd with δzi the Dirac function at zi. In the following, Zn(Rd) denotes the space of such n-size point distributions, with Z(Rd) def.= ∪nZn(Rd) the space of distributions of arbitrary size.
Let G def.= SdX × SdY denote the group of permutations independently operating on the feature and label spaces. For σ = (σX ,σY ) ∈ G, the image σ(z) of a labelled sample is defined as (σX(x),σY (y)), with x = (x[k], k ∈ �1; dX�) and σX(x) def.= (x[σX(k)], k ∈ �1; dX�). For simplicity and by abuse of notations, the operator mapping a distribution z = (zi, i ∈ �1; n�) to {σ(zi)} def.= σ�z is still denoted σ. Let Z(Ω) denote the space of distributions supported on some domain Ω ⊂ Rd, with Ω invariant under permutations in G. The goal of the paper is to define and train deep architectures, implementing functions ϕ on Z(Ω ⊂ Rd) that are invariant under G, i.e. such that ∀σ ∈ G,ϕ(σ�z) = ϕ(z)1. By construction, a multi-label dataset is invariant under permutations of the samples, of the features, and of the multi-labels. Therefore, any meta-feature, that is, a feature describing a multi-label dataset, is required to satisfy the above sample and feature permutation invariance properties.

heading: 2.2 DISTRIBUTION-BASED INVARIANT LAYERS

text:
The building block of the proposed architecture, the invariant layer meant to satisfy the feature and label invariance requirements, is defined as follows, taking inspiration from (De Bie et al., 2019). Definition 1. (Distribution-based invariant layers) Let an interaction functional ϕ : Rd×Rd → Rr be G-invariant:
∀σ ∈ G, ∀(z1, z2) ∈ Rd × Rd, ϕ(z1, z2) = ϕ(σ(z1),σ(z2)). The distribution-based invariant layer fϕ is defined as
fϕ : z = (zi)i∈�1;n� ∈ Z(Rd) �→ fϕ(z) def.=   1 n n�
j=1
ϕ(z1, zj), . . . , 1
n
n�
j=1
ϕ(zn, zj)
  ∈ Z(Rr).
(1)
By construction, fϕ is G-invariant if ϕ is G-invariant. The construction of fϕ is extended to the general case of possibly continuous probability distributions by essentially replacing sums by integrals (Appendix A) Remark 1. (Varying dimensions dX and dY ). Both in practice and in theory, it is important that fϕ layers (in particular the first layer of the neural architecture) handle datasets of arbitrary number of features dX and number of multi-labels dY . The proposed approach, used in the experiments (Section 4), is to define ϕ as follows. Letting z = (x, y) and z� = (x�, y�) be two samples in RdX × RdY , let u be defined from R4 onto Rt, consider the sum of u(x[k], x�[k], y[�], y�[�]) for k ranging in �1; dX� and � in �1; dY �, and apply mapping v from Rt to Rr on this sum:
ϕ(z, z�) = v
� dX�
k=1
dY�
�=1
u(x[k], x�[k], y[�], y�[�]) � (2)
Likewise, by construction ϕ is G-invariant, i.e. it is invariant to both feature and label permutations. As shown in Section 4, this invariance property is instrumental to a good empirical performance. Remark 2. (Varying sample size n). By construction, fϕ is defined on Z(Rd) = ∪nZn(Rd) (independent of n), such that it supports inputs of arbitrary cardinality n. Remark 3. (Discussion w.r.t. (Maron et al., 2020)) The above definition of fϕ is based on the aggregation of pairwise terms ϕ(zi, zj). The motivation for using a pairwise ϕ is twofold. On the one hand, capturing local sample interactions allows to create more expressive architectures, which is important to improve the performance on some complex data sets, as illustrated in the experiments (Section 4). On the other hand, interaction functionals are crucial to design universal architectures
1As opposed to G-equivariant functions that are characterized by ∀σ ∈ G,ϕ(σ�z) = σ�ϕ(z)
(Appendix C, theorem 2). The proposed theoretical framework relies on the Wasserstein distance (corresponding to the convergence in law of probability distributions), which enables to compare distributions with varying number of points or even with continuous densities. In contrast, Maron et al. (2020) do not use interaction functionals, and establish the universality of their DSS architecture for fixed dimension d and number of points n. Moreover, DSS happens to resort to max pooling operators, discontinuous w.r.t. the Wasserstein topology (see Remark 6).
Two particular cases are when ϕ only depends on its first or second input:
(i) if ϕ(z, z�) = ψ(z�), then fϕ computes a global “moment” descriptor of the input, as fϕ(z) = 1n �n j=1 ψ(zj) ∈ Rr.
(ii) if ϕ(z, z�) = ξ(z), then fϕ transports the input distribution via ξ, as fϕ(z) = {ξ(zi), i ∈ �1; n�} ∈ Z(Rr). This operation is referred to as a push-forward.
Remark 4. (Localized computation) In practice, the quadratic complexity of fϕ w.r.t. the number n of samples can be reduced by only computing ϕ(zi, zj) for pairs zi, zj sufficiently close to each other. Layer fϕ thus extracts and aggregates information related to the neighborhood of the samples. Remark 5. (Link to kernels) The use of an interaction functional ϕ is inspired from kernel ideas, albeit with significant differences: (i) in fϕ(zi), the detail of the pairwise interactions ϕ(zi, zj) is lost through averaging; (ii) ϕ takes into account labels; (iii) ϕ is learnt. Further work will be devoted to investigating the properties of the fϕ(zi) matrix.

heading: 2.3 LEARNING META-FEATURES

text:
The proposed distributional neural architectures defined on point distributions (DIDA) are sought as
z ∈ Z(Rd) �→ Fζ(z) def.= fϕm ◦ fϕm−1 ◦ . . . ◦ fϕ1(z) ∈ Rdm+1 (3) where ζ are the trainable parameters of the architecture (below). Only the case dY = 1 is considered in the remainder. The k-th layer is built on the top of ϕk, mapping pairs of vectors in Rdk onto Rdk+1 , with d1 = d (the dimension of the input samples). Last layer is built on ϕm, only depending on its second argument; it maps the distribution in layer m − 1 onto a vector, whose coordinates are referred to as meta-features.
The G-invariance and dimension-agnosticity of the whole architecture only depend on the first layer fϕ1 satisfying these properties. In the first layer, ϕ1 is sought as ϕ1((x, y), (x
�, y�)) = v( �
k u(x[k], x �[k], y, y�)) (Remark 1), with u(x[k], x�[k], y, y�) = (ρ(Au ·(x[k];x�[k])+bu,1y �=y�) in Rt × {0, 1}, where ρ is a non-linear activation function, Au a (t, 2) matrix, (x[k];x�[k]) the 2-dimensional vector concatenating x[k] and x�[k], and bu a t-dimensional vector. With e = � k u(x[k], x
�[k], y, y�)), function v likewise applies a non-linear activation function ρ on an affine transformation of e: v(e) = ρ(Av · e + bv), with Av a (t, r) matrix and bv a r-dimensional vector.
Note that the subsequent layers need neither be invariant w.r.t. the number of samples, nor handle a varying number of dimensions. However, maintaining the distributional nature among several layers is shown to improve performance in practice (Section 4). Every ϕk, k ≥ 2 is defined as ϕk = ρ(Ak ·+bk), with ρ an activation function, Ak a (dk, dk+1) matrix and bk a dk+1-dimensional vector. The DIDA neural net thus is parameterized by ζ def.= (Au, bu, Av, bv, {Ak, bk}k), that is classically learned by stochastic gradient descent from the loss function defined after the task at hand (Section 4).

heading: 3 THEORETICAL ANALYSIS

text: This section analyzes the properties of invariant-layer based neural architectures, specifically their robustness w.r.t. bounded transformations of the involved distributions, and their approximation abilities w.r.t. the convergence in law, which is the natural topology for distributions. As already said, the discrete distribution case is considered in this section for the sake of readability, referring the reader to Appendix A for the general case of continuous distributions.

heading: 3.1 OPTIMAL TRANSPORT COMPARISON OF DATASETS

text:
Point clouds vs. distributions. Our claim is that datasets should be seen as probability distributions, rather than point clouds. Typically, including many copies of a point in a dataset amounts to increasing its importance, which usually makes a difference in a standard machine learning setting. Accordingly, the topological framework used to define and learn meta-features in the following is that of the convergence in law, with the distance among two datasets being quantified using the Wasserstein distance (below). In contrast, the point clouds setting (see for instance (Qi et al., 2017)) relies on the Haussdorff distance among sets to theoretically assess the robustness of these architectures. While it is standard for 2D and 3D data involved in graphics and vision domains, it faces some limitations in higher dimensional domains, e.g. due to max-pooling being a non-continuous operator w.r.t. the convergence in law topology.
Wasserstein distance. Referring the reader to (Santambrogio, 2015; Peyré & Cuturi, 2019) for a more comprehensive presentation, the standard 1-Wasserstein distance between two discrete probability distributions z, z� ∈ Zn(Rd)× Zm(Rd) is defined as:
W1(z, z�) def. = max
f∈Lip1(Rd)
1
n
n�
i=1
f(zi)− 1
m
m�
j=1
f(z�j)
with Lip1(Rd) the space of 1-Lipschitz functions f : Rd → R. To account for the invariance requirement (making indistinguishable z = (z1, . . . , zn) and its permuted image (σ(z1), . . . ,σ(zn)) def. = σ�z under σ ∈ G), we introduce the G-invariant 1-Wasserstein distance: for z ∈ Zn(Rd), z� ∈ Zm(Rd): W1(z, z�) = min
σ∈G W1(σ�z, z�)
such that W1(z, z�) = 0 if and only if z and z� belong to the same equivalence class (Appendix A), i.e. are equal in the sense of probability distributions up to sample and feature permutations.
Lipschitz property. In this context, a map f from Z(Rd) onto Z(Rr) is continuous for the convergence in law (a.k.a. weak convergence on distributions, denoted �) iff for any sequence z(k) � z, then f(z(k)) � f(z). The Wasserstein distance metrizes the convergence in law, in the sense that z(k) � z is equivalent to W1(z(k), z) → 0. Furthermore, map f is said to be C-Lipschitz for the permutation invariant 1-Wasserstein distance iff
∀z, z� ∈ Z(Rd), W1(f(z), f(z�)) � CW1(z, z�). (4) The C-Lipschitz property entails the continuity of f w.r.t. its input: if two input distributions are close in the permutation invariant 1-Wasserstein sense, the corresponding outputs are close too.

heading: 3.2 REGULARITY OF DISTRIBUTION-BASED INVARIANT LAYERS

text:
Assuming the interaction functional to satisfy the Lipschitz property:
∀z ∈ Rd, ϕ(z, ·) and ϕ(·, z) are Cϕ − Lipschitz. (5) the robustness of invariant layers with respect to different variations of their input is established (proofs in Appendix B). We first show that invariant layers also satisfy Lipschitz property, ensuring that deep architectures of the form (3) map close inputs onto close outputs. Proposition 1. Invariant layer fϕ of type (1) is (2rCϕ)-Lipschitz in the sense of (4).
A second result regards the case where two datasets z and z� are such that z� is the image of z through some diffeomorphism τ (z = (z1, . . . , zn) and z� = τ�z = (τ(z1), . . . , τ(zn)). If τ is close to identity, then the following proposition shows that fϕ(τ�z) and fϕ(z) are close too. More generally, if continuous transformations τ and ξ respectively apply on the input and output space of fϕ, and are close to identity, then ξ�fϕ(τ�z) and fϕ(z) are also close. Proposition 2. Let τ : Rd → Rd and ξ : Rr → Rr be two Lipschitz maps with respectively Lipschitz constants Cτ and Cξ. Then,
∀z ∈ Z(Ω), W1(ξ�fϕ(τ�z), fϕ(z)) � sup x∈fϕ(τ(Ω)) ||ξ(x)− x||2 + 2r Lip(ϕ) sup x∈Ω ||τ(x)− x||2
∀z, z� ∈ Z(Ω), if τ is equivariant, W1(ξ�fϕ(τ�z), ξ�fϕ(τ�z�)) � 2r Cϕ Cτ CξW1(z, z�)

heading: 3.3 UNIVERSALITY OF INVARIANT LAYERS

text:
Lastly, the universality of the proposed architecture is established, showing that the composition of an invariant layer (1) and a fully-connected layer is enough to enjoy the universal approximation property, over all functions defined on Z(Rd) with dimension d less than some D (Remark 1). Theorem 1. Let F : Z(Ω) → R be a G-invariant map on a compact Ω, continuous for the convergence in law. Then ∀ε > 0, there exists two continuous maps ψ,ϕ such that
∀z ∈ Z(Ω), |F(z)− ψ ◦ fϕ(z)| < ε where ϕ is G-invariant and independent of F .
Proof. The sketch of the proof is as follows (complete proof in Appendix C). Let us define ϕ = g◦h where: (i) h is the collection of dX elementary symmetric polynomials in the features and dY elementary symmetric polynomials in the labels, which is invariant under G; (ii) a discretization of h(Ω) on a grid is then considered, achieved thanks to g that aims at collecting integrals over each cell of the discretization; (iii) ψ applies function F on this discretized measure; this requires h to be bijective, and is achieved by h̃, through a projection on the quotient space Sd/G and a restriction to its image compact Ω�. To sum up, fϕ defined as such computes an expectation which collects integrals over each cell of the grid to approximate measure h�z by a discrete counterpart �h�z. Hence ψ applies F to h̃−1� (�h�z). Continuity is obtained as follows: (i) proximity of h�z and �h�z follows from Lemma 1 in (De Bie et al., 2019)) and gets tighter as the grid discretization step tends to 0; (ii) Map h̃−1 is 1/d-Hölder, after Theorem 1.3.1 from (Rahman & Schmeisser, 2002)); therefore Lemma 2 entails that W1(z, h̃−1� �h�z) can be upper-bounded; (iii) since Ω is compact, by BanachAlaoglu theorem, Z(Ω) also is. Since F is continuous, it is thus uniformly weakly continuous: choosing a discretization step small enough ensures the result.
Remark 6. (Comparison with (Maron et al., 2020)) The above proof holds for functionals of arbitrary input sample size n, as well as continuous distributions, generalizing results in (Maron et al., 2020). Note that the two types of architectures radically differ (more in Section 4). Remark 7. (Approximation by an invariant NN) After theorem 1, any invariant continuous function defined on distributions with compact support can be approximated with arbitrary precision by an invariant neural network (Appendix C). The proof involves mainly three steps: (i) an invariant layer fϕ can be approximated by an invariant network; (ii) the universal approximation theorem (Cybenko, 1989; Leshno et al., 1993); (iii) uniform continuity is used to obtain uniform bounds. Remark 8. (Extension to different spaces) Theorem 1 also extends to distributions supported on different spaces, via embedding them into a high-dimensional space. Therefore, any invariant function on distributions with compact support in Rd with d ≤ D can be uniformly approximated by an invariant network (Appendix C).

heading: 4 EXPERIMENTAL VALIDATION

text:
The experimental validation presented in this section considers two goals of experiments: (i) assessing the ability of DIDA to learn accurate meta-features; (ii) assessing the merit of the DIDA invariant layer design, building invariant fϕ on the top of an interactional function ϕ (Eq. 1). As said, this architecture is expected to grasp contrasts among samples, e.g. belonging to different classes; the proposed experimental setting aims to empirically investigate this conjecture.
Baselines. These goals of experiments are tackled by comparing DIDA to three baselines: DSS layers (Maron et al., 2020); hand-crafted meta-features (HC) (Muñoz et al., 2018) (Table 5 in Appendix D); DATASET2VEC (Jomaa et al., 2019). We implemented DSS, the code being not available.2 In order to cope with varying dataset dimensions (as required by the UCI and OpenML benchmarks), the original DSS was augmented with an aggregator summing over the features. Three DSS baselines are considered: linear or non-linear invariant layers, possibly preceded by equivariant layers. Similarly, the original DATASET2VEC implementation has been augmented to address our experimental setting. The baselines are detailed in Appendix D.3.
2The code source of DIDA and (our implementation of) baselines are available in supplementary materials.
Experimental setting. Two tasks defined at the dataset level are considered: patch identification (section 4.1) and performance modelling (section 4.2). The dataset preprocessing protocols are detailed in Appendix D.1. On both tasks, the same DIDA architecture is considered (Fig 1), involving 2 invariant layers followed by 3 fully connected (FC) layers. Meta-features Fζ(z) consist of the output of the third FC layer, with ζ denoting the trained DIDA () parameters. All experiments run on 1 NVIDIA-Tesla-V100-SXM2 GPU with 32GB memory, using Adam optimizer with base learning rate 10−3.

heading: 4.1 TASK 1: PATCH IDENTIFICATION

text:
The patch identification task consists of detecting whether two blocks of data are extracted from the same original dataset (Jomaa et al., 2019). Letting u denote a n-sample, d-dimensional dataset, an nz, dz patch z is constructed from u by selecting nz examples in u (sampled uniformly with replacement) and retaining their description along dz features (sampled uniformly with replacement). The size nz and number dz of features of the patch are uniformly selected in fixed intervals (Table 4, Appendix D). To each pair of patches z, z� with same number of instances nz = nz� , is associated a binary meta-label �(z, z�) set to 1 iff z and z’ are extracted from the same initial dataset u. DIDA parameters ζ are trained to minimize the cross-entropy loss of model �̂ζ(z, z�) = exp (−||Fζ(z)− Fζ(z�)||2), with Fζ(z) and Fζ(z�) the meta-features computed for z and z�:
Minimize L(ζ) = − �
z,z� �(z, z�) log(�̂ζ(z, z�)) + (1− �(z, z�)) log(1− �̂ζ(z, z�)) (6)
DIDA and all baselines are trained using a Siamese approach (Figure 1, bottom left): the same DIDA (or baseline) architecture is used to compute meta-features Fζ(z) and Fζ(z�) from patches z and z�, and trained to minimize the cross-entropy loss w.r.t. �(z, z�). The classification results on toy datasets and UCI datasets (Table 1, detailed in Appendix D) show the pertinence of the DIDA meta-features, particularly so on the UCI datasets where the number of features widely varies from one dataset to another. The relevance of the interactional invariant layer design is established on this problem as DIDA outperforms both DATASET2VEC, DSS as well as the function learned on the top of the hand-crafted meta-features.
An ablation study is conducted to assess the impact of (i) the feature permutation invariance; (ii) considering one vs two invariant layers of type (1). The so-called NO-FINV-DSS baseline, detailed in Appendix D, is built upon (Zaheer et al., 2017); it only differs from the DSS baseline as it is not feature permutation invariant. With ca the same number of parameters as DSS, its performances are
significantly lower (Table 1), showcasing the benefits of enforcing the feature invariance property. Secondly, we compare the 2-invariant layers DIDA, with the 1-invariant layer DIDA (1L-DIDA and 2L-DIDA for short): 1L-DIDA yields significantly lower performances, which confirms the advantages of maintaining the distributional nature among several layers, as already noted by (De Bie et al., 2019). Note that the 1L-DIDA still outperforms the non feature-invariant baseline, while requiring much fewer parameters.

heading: 4.2 TASK 2: PERFORMANCE MODEL LEARNING

text:
The performance modelling task aims to assess a priori the accuracy of the classifier learned from a given machine learning algorithm with a given configuration θ (vector of hyper-parameters ranging in a hyper-parameter space Θ, Table 6 in Appendix D), on a dataset z (for brevity, the performance of θ on z) (Rice, 1976).
For each ML algorithm, ranging in Logistic regression (LR), SVM, k-Nearest Neighbours (k-NN), linear classifier learned with stochastic gradient descent (SGD), a set of meta-features is learned to predict whether some configuration θ1 outperforms some configuration θ2 on dataset z: to each triplet (z, θ1, θ2) is associated a binary value �(z, θ1, θ2), set to 1 iff θ2 yields better performance than θ1 on z. DIDA parameters ζ are trained to build model �̂ζ , minimizing the (weighted version of) cross-entropy loss (6), where �̂ζ(z, θ1, θ2) is a 2-layer FC network with input vector [Fζ(z); θ1; θ2], depending on the considered ML algorithm and its configuration space.
In each epoch, a batch made of triplets (z, θ1, θ2) is built, with θ1, θ2 uniformly drawn in the algorithm configuration space (Table 6) and z a n-sample d-dimensional patch of a dataset in the OpenML CC-2018 (Bischl et al., 2019) with n uniformly drawn in [700; 900] and d in [3; 10]. Algorithm 1 summarizes the training procedure.
The quality of the DIDA meta-features is assessed from the ranking accuracy (Table 2), showing their relevance. The performance gap compared to the baselines is higher for the k-NN modelling
Algorithm 1 Performance Modeling 1: Fζ ← meta-feature extractor (DIDA, DSS, DATASET2VEC, or Hand-crafted) 2: MLP ← NN[Linear(64)-ReLU-Linear(32)-ReLU-Linear(1)] 3: CLF ← machine learning classifier (SGD, SVM, LR or k-NN) 4: error ← 3-CV classification error function 5: for iteration=1, 2, . . . do 6: Sample (θ1, θ2), two hyper-parameters of CLF � Search space: Table 6 7: Sample patch z from dataset u � Patch dimension: Table 4 8: pred ← softmax(MLP(Fζ(z), θ1), MLP(Fζ(z), θ2)) 9: Backpropagate logloss(pred, 0 if error(z, CLF(θ1)) < error(z, CLF(θ2)) else 1) 10: end for
task; this is explained as the sought performance model only depends on the local geometry of the examples. Still, good performances are observed over all considered algorithms. Note that the 2LDIDA yields significantly better (respectively, similar) performances than 1L-DIDA on the k-NN model (resp. on all other models).
Meta-feature assessment. A regression setting is thereafter considered, aimed to predict the actual performance of a configuration θ based on the (frozen) meta-features Fζ(z). The regression accuracy is illustrated for the configurations of the k-NN algorithm on Figure 2, left (results for other algorithms are presented in Appendix D). The comparison with the regression models based on DSS meta-features or hand-crafted features (Figure 2, middle and right) shows the merits of the DIDA architecture; a tentative interpretation for the DIDA better performance is based on the interactional nature of DIDA architecture, better capturing local interactions.

heading: 5 CONCLUSION

text: The theoretical contribution of the paper is the DIDA architecture, able to learn from discrete and continuous distributions on Rd, invariant w.r.t. feature ordering, agnostic w.r.t. the size and dimension d of the considered distribution sample (with d less than some upper bound D). This architecture enjoys universal approximation and robustness properties, generalizing former results obtained for point clouds (Maron et al., 2020). The merits of DIDA are demonstrated on two tasks defined at the dataset level: patch identification and performance model learning, comparatively to the state of the art (Maron et al., 2020; Jomaa et al., 2019; Muñoz et al., 2018). The ability to accurately describe a dataset in the landscape defined by ML algorithms opens new perspectives to compare datasets and algorithms, e.g. for domain adaptation (Ben-David et al., 2007; 2010) and meta-learning (Finn et al., 2018; Yoon et al., 2018), in light of kernel methods.