summaries: This paper presents a deep reinforcement algorithm, Ensemble Deep Deterministic Policy Gradients (ED2), for continuous control tasks. The algorithm is empirically derived and is claimed to represent SotA performance on several tasks and while providing more stable results. These claims are justified based primarily on the (reward and stability) results on 4 MuJoCo environments.

summaries: This paper has two main contributions: it introduces an ensemble-based actor-critic method, and it answers some pertinent questions in policy optimization by focusing on its different components. The ensemble is different from multi-actor learners that interact with multiple environments simultaneously, violating the standard RL setup. Instead, the learner of this paper maintains multiple actors and critics but uses only a single actor at a time to interact with the environment. All actors and critics are trained on a common replay buffer. The base method is the streamlined off-policy (SOP) method, which unlike soft actor-critic (SAC) doesn’t use an entropy bonus. Additionally, no exploration noise is added, resulting in their Ensemble Deep Deterministic (ED2) method.  The proposed algorithm ED2 is shown to be superior and more stable in performance according to different measures compared to existing methods. It is also revealed that actor initialization affects performance less than critic initialization. ED2 uses deterministic actors, and its exploration comes from sampling among the actors. Such a form of exploration is also shown to be superior to UCB-style exploration.

summaries: The paper presents an empirical study evaluating the commonly accepted design choice in off-policy Deep RL algorithms in continuous control settings. The use of additive exploration noise, initialization choices, update frequency, and precision for retraining are tested empirically highlighting some interesting results. The paper also introduces ED2 - an ensemble method utilizing the design choices from the study which is demonstrated to achieve SOTA results on Mujoco benchmarks.

summaries: This paper conducted an experimental study over a range of tricks that are often exploited to facilitate ensemble deep reinforcement learning. The experiment results show several interesting findings. For example, it was found that commonly used additive action noise may not be necessary for effective exploration. Meanwhile, experiments show that the initialization of critics perhaps has a higher impact on learning performance than the initialization methods adopted for actors. These findings can be quite important to guide future design of more effective ensemble reinforce learning algorithms.

abstractText: The growth of deep reinforcement learning (RL) has brought multiple exciting tools and methods to the field. This rapid expansion makes it important to understand the interplay between individual elements of the RL toolbox. We approach this task from an empirical perspective by conducting a study in the continuous control setting. We present multiple insights of fundamental nature, including: a commonly used additive action noise is not required for effective exploration and can even hinder training; the performance of policies trained using existing methods varies significantly across training runs, epochs of training, and evaluation runs; the critics’ initialization plays the major role in ensemble-based actor-critic exploration, while the training is mostly invariant to the actors’ initialization; a strategy based on posterior sampling explores better than the approximated UCB combined with the weighted Bellman backup; the weighted Bellman backup alone cannot replace the clipped double Q-Learning. As a conclusion, we show how existing tools can be brought together in a novel way, giving rise to the Ensemble Deep Deterministic Policy Gradients (ED2) method, to yield state-of-the-art results on continuous control tasks from OpenAI Gym MuJoCo. From the practical side, ED2 is conceptually straightforward, easy to code, and does not require knowledge outside of the existing RL toolbox.

title: Spinning Up in Deep Reinforcement Learning

venue: GitHub repository,

authors:
Marcin Andrychowicz
Anton Raichuk
Piotr Stanczyk
Manu Orsini
Sertan Girgin
Raphael Marinier
Léonard Hussenot
Matthieu Geist
Olivier Pietquin
Marcin Michalski
Sylvain Gelly
Olivier Bachem

title: What Matters in On-Policy Reinforcement Learning

venue: A Large-Scale Empirical Study,

authors:
OpenAI: Marcin Andrychowicz
Bowen Baker
Maciek Chociej
Rafal Jozefowicz
Bob McGrew
Jakub Pachocki
Arthur Petron
Matthias Plappert
Glenn Powell
Alex Ray

title: Learning dexterous in-hand manipulation

venue: The International Journal of Robotics Research,

authors:
Marc G. Bellemare
Sriram Srinivasan
Georg Ostrovski
Tom Schaul
David Saxton
Rémi Munos

title: Unifying count-based exploration and intrinsic motivation

venue: Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016,

authors:
Christopher Berner
Greg Brockman
Brooke Chan
Vicki Cheung
Przemysław Dębiak
Christy Dennison
David Farhi
Quirin Fischer
Shariq Hashme
Chris Hesse

title: Dota 2 with large scale deep reinforcement learning

venue: arXiv preprint arXiv:1912.06680,

authors:
Stephanie C.Y. Chan
Samuel Fishman
Anoop Korattikara
John Canny
Sergio Guadarrama

title: Measuring the Reliability of Reinforcement Learning Algorithms

venue: In 8th International Conference on Learning Representations,

authors:
Xi Liang Chen
Lei Cao
Chen Xi Li
Zhi Xiong Xu
Jun Lai

title: Ensemble Network Architecture for Deep Reinforcement Learning

venue: Mathematical Problems in Engineering,

authors:
Kurtland Chua
Roberto Calandra
Rowan McAllister
Sergey Levine

title: Deep reinforcement learning in a handful of trials using probabilistic dynamics models

venue: NeurIPS

authors:
Stanislav Fort
Huiyi Hu
Balaji Lakshminarayanan

title: Deep ensembles: A loss landscape perspective

authors:
Meire Fortunato
Mohammad Gheshlaghi Azar
Bilal Piot
Jacob Menick
Matteo Hessel
Ian Osband
Alex Graves
Vlad Mnih
Remi Munos
Demis Hassabis
Olivier Pietquin
Charles Blundell
Shane Legg

title: Noisy networks for exploration

venue: In 6th International Conference on Learning Representations,

authors:
Scott Fujimoto
Herke van Hoof
David Meger

title: Addressing function approximation error in actor-critic methods

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

authors:
Tuomas Haarnoja
Aurick Zhou
Pieter Abbeel
Sergey Levine

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

venue: In 35th International Conference on Machine Learning,

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

title: Soft actor-critic algorithms and applications

authors:
Matteo Hessel
Joseph Modayil
Hado Van Hasselt
Tom Schaul
Georg Ostrovski
Will Dabney
Dan Horgan
Bilal Piot
Mohammad Azar
David Silver

title: Rainbow: Combining improvements in deep reinforcement learning

venue: AAAI Conference on Artificial Intelligence,

authors:
Zhewei Huang
Shuchang Zhou
Bo Er Zhuang
Xinyu Zhou

title: Learning to run with actor-critic ensemble, 2017

authors:
Andrew Ilyas
Logan Engstrom
Shibani Santurkar
Dimitris Tsipras
Firdaus Janoos
Larry Rudolph
Aleksander Madry

title: A closer look at deep policy gradients

authors:
Diederik P. Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations,

authors:
Aviral Kumar
Abhishek Gupta
Sergey Levine

title: Discor: Corrective feedback in reinforcement learning via distribution correction

venue: Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems

authors:
Thanard Kurutach
Ignasi Clavera
Yan Duan
Aviv Tamar
Pieter Abbeel

title: Model-ensemble trust-region policy optimization

authors:
Tze Leung Lai
Herbert Robbins

title: Asymptotically efficient adaptive allocation rules

venue: Advances in applied mathematics,

authors:
Balaji Lakshminarayanan
Alexander Pritzel
Charles Blundell

title: Simple and scalable predictive uncertainty estimation using deep ensembles

venue: In NIPS 2017,

authors:
Kimin Lee
Michael Laskin
Aravind Srinivas
Pieter Abbeel

title: SUNRISE: A Simple Unified Framework for Ensemble

venue: Learning in Deep Reinforcement Learning,

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: In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Representations,

authors:
Kendall Lowrey
Aravind Rajeswaran
Sham Kakade
Emanuel Todorov
Igor Mordatch

title: Plan online, learn offline: Efficient learning and exploration via model-based control

authors:
Piotr Miłoś
Łukasz Kuciński
Konrad Czechowski
Piotr Kozakowski
Maciek Klimek

title: Uncertainty-sensitive learning and planning with ensembles

venue: arXiv preprint arXiv:1912.09996,

authors:
Ian Osband
Benjamin Van Roy

title: Why is posterior sampling better than optimism for reinforcement learning

venue: In 34th International Conference on Machine Learning,

authors:
Ian Osband
Benjamin Van Roy
Daniel Russo

title: More) efficient reinforcement learning via posterior sampling

venue: In Advances in Neural Information Processing Systems,

authors:
Ian Osband
Charles Blundell
Alexander Pritzel
Benjamin Van Roy

title: Deep exploration via bootstrapped DQN

authors:
Ian Osband
John Aslanides
Albin Cassirer

title: Randomized prior functions for deep reinforcement learning

venue: In NeurIPS,

authors:
Ian Osband
Benjamin Van Roy
Daniel J. Russo
Zheng Wen

title: Deep exploration via randomized value functions

venue: J. Mach. Learn. Res.,

authors:
Matthias Plappert
Rein Houthooft
Prafulla Dhariwal
Szymon Sidor
Richard Y. Chen
Xi Chen
Tamim Asfour
Pieter Abbeel
Marcin Andrychowicz

title: Parameter space noise for exploration

venue: In 6th International Conference on Learning Representations, ICLR 2018 - Conference Track Proceedings,

authors:
David Silver
Aja Huang
Chris J Maddison
Arthur Guez
Laurent Sifre
George Van Den Driessche
Julian Schrittwieser
Ioannis Antonoglou
Veda Panneershelvam
Marc Lanctot

title: Mastering the game of go with deep neural networks and tree

venue: search. nature,

title: A bayesian framework for reinforcement learning

venue: In Proceedings of the Seventeenth International Conference on Machine Learning (ICML

authors:
Hado van Hasselt
Arthur Guez
David Silver

title: Deep reinforcement learning with double qlearning

venue: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17,

authors:
Oriol Vinyals
Igor Babuschkin
Wojciech M Czarnecki
Michaël Mathieu
Andrew Dudzik
Junyoung Chung
David H Choi
Richard Powell
Timo Ewalds
Petko Georgiev

title: Grandmaster level in starcraft ii using multi-agent 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

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

authors:
Marco A. Wiering
Hado van Hasselt

title: Ensemble algorithms in reinforcement learning

venue: IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics,

authors:
Zeyu Zheng
Junhyuk Oh
Satinder Singh

title: On Learning Intrinsic Rewards for Policy Gradient Methods

venue: Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems

authors:
Zhuobin Zheng
Chun Yuan
Zhihui Lin
Yangyang Cheng
Hanghao Wu

title: Self-adaptive double bootstrapped DDPG

venue: In IJCAI International Joint Conference on Artificial Intelligence, 2018b. ISBN 9780999241127

title: The average test returns across the training of our method and ED2 with the UCB exploration. Gaussian noise While our method uses ensemble-based temporally coherent exploration, the most popular choice of exploration is injecting i.i.d. noise (Fujimoto et al., 2018

heading: 1 INTRODUCTION

text:
Recently, deep reinforcement learning (RL) has achieved multiple breakthroughs in a range of challenging domains (e.g. Silver et al. (2016); Berner et al. (2019); Andrychowicz et al. (2020b); Vinyals et al. (2019)). A part of this success is related to an ever-growing toolbox of tricks and methods that were observed to boost the RL algorithms’ performance (e.g. Hessel et al. (2018); Haarnoja et al. (2018b); Fujimoto et al. (2018); Wang et al. (2020); Osband et al. (2019)). This state of affairs benefits the field but also brings challenges related to often unclear interactions between the individual improvements and the credit assignment related to the overall performance of the algorithm Andrychowicz et al. (2020a); Ilyas et al. (2020).
In this paper, we present a comprehensive empirical study of multiple tools from the RL toolbox applied to the continuous control in the OpenAI Gym MuJoCo setting. These are presented in Section 4 and Appendix B. Our insights include:
• The normally distributed action noise, commonly used for exploration, hinders training. • The current state-of-the-art methods are unstable under several stability criteria. • The critics’ initialization plays a major role in ensemble-based actor-critic exploration, while
the training is mostly invariant to the actors’ initialization. • The approximated posterior sampling exploration (Osband et al., 2013) outperforms approx-
imated UCB exploration combined with weighted Bellman backup (Lee et al., 2020). • The weighted Bellman backup (Lee et al., 2020) can not replace the clipped double Q-
Learning (Fujimoto et al., 2018). To address some of the issues listed above, we introduce the Ensemble Deep Deterministic Policy Gradient (ED2) algorithm1, see Section 3. ED2 brings together existing RL tools in a novel way: it is
1Our code is based on SpinningUp (Achiam, 2018). We open-source it at: https://github.com/ ed2-paper/ED2.
an off-policy algorithm for continuous control, which constructs an ensemble of streamlined versions of TD3 agents and achieves the state-of-the-art performance in OpenAI Gym MuJoCo, substantially improving the results on the two hardest tasks – Ant and Humanoid. Consequently, ED2 does not require knowledge outside of the existing RL toolbox, is conceptually straightforward, and easy to code.

heading: 2 BACKGROUND

text:
We model the environment as a Markov Decision Process (MDP). It is defined by the tuple (S,A, R, P, γ, p0), where S is a continuous multi-dimensional state space, A denotes a continuous multi-dimensional action space, P is a transition kernel, γ ∈ [0, 1) stands for a discount factor, p0 refers to an initial state distribution, and R is a reward function. The agent learns a policy from sequences of transitions τ = [(st, at, rt, st+1, d)]Tt=0, called episodes or trajectories, where at ∼ π(·|st), st+1 ∼ P (·|st, at), rt = R(st, at, st+1), d is a terminal signal, and T is the terminal time-step. A stochastic policy π(a|s) maps each state to a distribution over actions. A deterministic policy µ : S −→ A assigns each state an action. All algorithms that we consider in this paper use a different policy for collecting data (exploration) and a different policy for evaluation (exploitation). In order to keep track of the progress, the evaluation runs are performed every ten thousand environment interactions. Because of the environments’ stochasticity, we run the evaluation policy multiple times. Let {Ri}Ni=1 be a set of (undiscounted) returns from N evaluation episodes {τi}Ni=1, i.e. Ri = ∑ rt∈τi rt. We evaluate the
policy using the average test return R̄ = 1N ∑N i=1Ri and the standard deviation of the test returns
σ = √
1 N−1 ∑N i=1(Ri − R̄)2.
We run experiments on four continuous control tasks and their variants, introduced in the appropriate sections, from the OpenAI Gym MuJoCo suite (Brockman et al., 2016) presented in Figure 1. The agent observes vectors that describe the kinematic properties of the robot and its actions specify torques to be applied on the robot joints. See Appendix D for the details on the experimental setup.

heading: 3 ENSEMBLE DEEP DETERMINISTIC POLICY GRADIENTS

text:
For completeness of exposition, we present ED2 before the experimental section. The ED2 architecture is based on an ensemble of Streamlined Off-Policy (SOP) agents (Wang et al., 2020), meaning that our agent is an ensemble of TD3-like agents (Fujimoto et al., 2018) with the action normalization and the ERE replay buffer. The pseudo-code listing can be found in Algorithm 1, while the implementation details, including a more verbose version of pseudo-code (Algorithm 3), can be found in Appendix E. In the data collection phase (Lines 1-9), ED2 selects one actor from the ensemble uniformly at random (Lines 1 and 9) and run its deterministic policy for the course of one episode (Line 4). In the evaluation phase (not shown in Algorithm 1), the evaluation policy averages all the actors’ output actions. We train the ensemble every 50 environment steps with 50 stochastic gradient descent updates (Lines 10-13). ED2 concurrently learns K · 2 Q-functions, Qφk,1 and Qφk,2 where k ∈ K, by mean square Bellman error minimization, in almost the same way that SOP learns its two Q-functions. The only difference is that we have K critic pairs that are initialized with different random weights and then trained independently with the same batches of data. Because of the different initial weights, each Q-function has a different bias in its Q-values. The K actors, πθk , train maximizing their corresponding first critic, Qφk,1 , just like SOP.
Algorithm 1 ED2 - Ensemble Deep Deterministic Policy Gradients Input: init. params for policy θk and Q-functions φk,1, φk,2, k ∈ [1...K]; replay buffer D;
1: Sample the current policy index c ∼ U([1...K]). 2: Reset the environment and observe the state s. 3: repeat 4: Execute action a = µθc(s) . µ uses the action normalization 5: Observe and store (s, a, r, s′, d) in the replay buffer D. 6: Set s← s′ 7: if episode is finished then 8: Reset the environment and observe initial state s. 9: Sample the current policy index c ∼ U([1...K]).
10: if time to update then 11: for as many as steps done in the environment do 12: Sample a batch of transitions B = {(s, a, r, s′, d)} ⊂ D . uses ERE 13: Update the parameters θk, φk,1 and φk,2 by one gradient step. 14: until convergence
Utilizing the ensembles requires several design choices, which we summarize below. The ablation study of ED2 elements is provided in Appendix C.

heading: Ensemble

text:
Used: We train the ensemble of 5 actors and 5 critics; each actor learns from its own critic and the whole ensemble is trained on the same data.
Not used: We considered different actor-critic configurations, initialization schemes and relations, as well as the use of random prior networks (Osband et al., 2018), data bootstrap (Osband et al., 2016), and different ensemble sizes. We also change the SOP network sizes and training intensity instead of using the ensemble. Besides the prior networks in some special cases, these turn out to be inferior as shown in Section 4 and Appendix B.1.

heading: Exploration

text:
Used: We pick one actor uniformly at random to collect the data for the course of one episode. The actor is deterministic (no additive action noise is applied). These two choices ensure coherent and temporally-extended exploration similarly to Osband et al. (2016).
Not used: We tested several approaches to exploration: using the ensemble of actors, UCB (Lee et al., 2020), and adding the action noise in different proportions. These experiments are presented in Appendix B.2.

heading: Exploitation

text:
Used: The evaluation policy averages all the actors’ output actions to provide stable performance.
Not used: We tried picking an action with the biggest value estimate (average of the critics’ Qfunctions) in evaluation (Huang et al., 2017).
Interestingly, both policies had similar results, see Appendix B.3.

heading: Action normalization

text:
Used: We use the action normalization introduced by Wang et al. (2020).
Not used: We experimented with the observations and rewards normalization, which turned out to be unnecessary. The experiments are presented in Appendix B.4.

heading: Q-function updates

text:
Used: We do 50 SGD updates (ADAM optimizer (Kingma and Ba, 2015), MSE loss) to the actors and the critics every 50 environment interactions, use Clipped Double Q-Learning (Fujimoto et al., 2018).
Not used: We also examined doing the updates at the end of each episode (with the proportional number of updates), using the Hubert loss, and doing weighted Bellman backups (Lee et al., 2020). However, we found them to bring no improvement to our method, as presented in Appendix B.5.

heading: 4 EXPERIMENTS

text: In this section, we present our comprehensive study and the resulting insights. The rest of the experiments verifying that our design choices perform better than alternatives are in Appendix B. Unless stated otherwise, a solid line in the figures represents an average, while a shaded region shows a 95% bootstrap confidence interval. We used 30 seeds for ED2 and the baselines and 7 seeds for the ED2 variants.

heading: 4.1 THE NORMALLY DISTRIBUTED ACTION NOISE, COMMONLY USED FOR EXPLORATION, HINDERS TRAINING

text:
In this experiment, we deprive SOP of its exploration mechanism, namely additive normal action noise, and call this variant deterministic SOP (det. SOP). It causes relatively minor deterioration in the Humanoid performance, has no significant influence on the Hopper or Walker performance, and substantially improves the Ant performance, see Figure 2. This result shows that no additional exploration mechanism, often in a form of an exploration noise (Lillicrap et al., 2016; Fujimoto et al., 2018; Wang et al., 2020), is required for the diverse data collection and it can even hinder training.
ED2 leverages this insight and constructs an ensemble of deterministic SOP agents presented in Section 3. Figure 3 shows that ED2 magnifies the beneficial effect coming from the deterministic exploration.
ED2 achieves state-of-the-art performance on the OpenAI Gym MuJoCo suite. Figure 4 shows the results of ED2 contrasted with three strong baselines: SUNRISE (Lee et al., 2020), SOP (Wang et al., 2020), and SAC(Haarnoja et al., 2018b).
For completeness, we plot the Humanoid velocities in Figure 5 which shows that our method accelerates to a much higher velocity than the baselines.

heading: 4.2 THE CURRENT STATE-OF-THE-ART METHODS ARE UNSTABLE UNDER SEVERAL STABILITY CRITERIA

text:
We consider three notions of stability: inference stability, asymptotic performance stability, and training stability. ED2 outperforms baselines in each of these notions, as discussed below. Similar metrics were also studied in Chan et al. (2020).
Inference stability We say that an agent is inference stable if, when run multiple times, it achieves similar test performance every time. We measure inference stability using the standard deviation of test returns explained in Section 2. We found that that the existing methods train policies that are surprisingly sensitive to the randomness in the environment initial conditions2. Figure 4 and Figure 6 show that ED2 successfully mitigates this problem. By the end of the training, ED2 produces results within 1% of the average performance on Humanoid, while the performance of SUNRISE, SOP, and SAC may vary as much as 11%.
2The MuJoCo suite is overall deterministic, nevertheless, little stochasticity is injected at the beginning of each trajectory, see Appendix D for details.
Asymptotic performance stability We say that an agent achieves asymptotic performance stability if it achieves similar test performance across multiple training runs starting from different initial networks weights. Figure 7 shows that ED2 has a significantly smaller variance than the other methods while maintaining high performance.
Training stability We will consider training stable if performance does not severely deteriorate from one evaluation to the next. We define the root mean squared deterioration metric (RMSD) as follows:
RMSD = √√√√ 1 M M∑ i=1 ( max(R̄i−20 − R̄i, 0) )2 ,
where M is the number of the evaluation phases during training and R̄i is the average test return at the i-th evaluation phase (described in Section 2). We compare returns 20 evaluation phases apart to ensure that the deterioration in performance doesn’t stem from the evaluation variance. ED2 has the lowest RMSD across all tasks, see Figure 8.

heading: 4.3 THE CRITICS’ INITIALIZATION PLAYS A MAJOR ROLE IN ENSEMBLE-BASED ACTOR-CRITIC EXPLORATION, WHILE THE TRAINING IS MOSTLY INVARIANT TO THE

text:
ACTORS’ INITIALIZATION
In this experiment, actors’ weights are initialized with the same random values (contrary to the standard case of different initialization). Moreover, we test a corresponding case with critics’ weights initialized with the same random values or simply training only a single critic.
Figure 9 indicates that the choice of actors initialization does not matter in all tasks but Humanoid. Although the average performance on Humanoid seems to be better, it is also less stable. This is quite interesting because the actors are deterministic. Therefore, the exploration must come from the fact that each actor is trained to optimize his own critic.
On the other, Figure 9 shows that the setup with the single critic severely impedes the agent performance. We suspect that using the single critic impairs the agent exploration capabilities as its actors’ policies, trained to maximize the same critic’s Q-function, become very similar.

heading: 4.4 THE APPROXIMATED POSTERIOR SAMPLING EXPLORATION OUTPERFORMS APPROXIMATED UCB EXPLORATION COMBINED WITH WEIGHTED BELLMAN BACKUP

text:
ED2 uses posterior sampling based exploration method (Osband et al., 2016). SUNRISE, on the other hand, approximates the Upper Confidence Bound (UCB) exploration technique and does weighted Bellman backups (Lee et al., 2020). For the fair comparison between ED2 and SUNRISE, we substitute the SUNRISE base algorithm SAC for the SOP algorithm used by ED2. We call this variant SUNRISE-SOP.
We test both methods on the standard MuJoCo benchmarks as well as delayed (Zheng et al., 2018a) and sparse (Plappert et al., 2018) rewards variants. Both variations make the environments harder from the exploration standpoint. In the delayed version, the rewards are accumulated and returned to the agent only every 10 time-steps. In the sparse version, the reward for the forward motion is returned to the agent only after it crosses the threshold of one unit on the x-axis. For a better perspective, a fully trained Humanoid is able to move to around five units until the end of the episode. All the other reward components (living reward, control cost, and contact cost) remain unchanged. The results are presented in Table 1.
ED2 outperforms the non-ensemble method SOP, supporting the argument of coherent and temporallyextended exploration of ED2. Moreover, we observe that performance in MuJoCo environments benefits from the ED2 approximate Bayesian posterior sampling exploration (Osband et al., 2013) in contrast to the approximated UCB in SUNRISE, which follows the OFU principle. The posterior sampling is proved to be theoretically superior to the OFU strategy (Osband and Van Roy, 2017).
The experiment where the ED2’s exploration mechanism is replaced for UCB is in Appendix B.2. This variant also achieves worse results than ED2. The additional exploration efficiency experiment in the custom Humanoid environment, where an agent has to find and reach a goal position, is in Appendix A.

heading: 4.5 THE WEIGHTED BELLMAN BACKUP CAN NOT REPLACE THE CLIPPED DOUBLE Q-LEARNING

text:
We applied the weighted Bellman backups proposed by Lee et al. (2020) to our method. It is suggested that the method mitigates error propagation in Q-learning by re-weighting the Bellman backup based on uncertainty estimates from an ensemble of target Q-functions (i.e. variance of predictions). Interestingly, Figure 10 does not show this positive effect on ED2.
Our method uses clipped double Q-Learning to mitigate overestimation in Q-functions (Fujimoto et al., 2018). We wanted to check if it is required and if it can be exchanged for the weighted Bellman backups used by Lee et al. (2020). Figure 11 shows that clipped double Q-Learning is required and that the weighted Bellman backups can not replace it.

heading: 5 RELATED WORK

text:
Off-policy RL Recently, multiple deep RL algorithms for continuous control have been proposed, e.g. DDPG (Lillicrap et al., 2016), TD3 (Fujimoto et al., 2018), SAC (Haarnoja et al., 2018b), SOP (Wang et al., 2020), SUNRISE (Lee et al., 2020). They provide a variety of methods for improving training quality, including double-Q bias reduction van Hasselt et al. (2016), target policy smoothing or different update frequencies for actor and critic Fujimoto et al. (2018), entropy regularization Haarnoja et al. (2018b), action normalization Wang et al. (2020), prioritized experience replay Wang et al. (2020), weighted Bellman backups Kumar et al. (2020); Lee et al. (2020), and use of ensembles Osband et al. (2019); Lee et al. (2020); Kurutach et al. (2018); Chua et al. (2018).
Ensembles Deep ensembles are a practical approximation of a Bayesian posterior, offering improved accuracy and uncertainty estimation Lakshminarayanan et al. (2017); Fort et al. (2019). They
inspired a variety of methods in deep RL. They are often used for temporally-extended exploration; see the next paragraph. Other than that, ensembles of different TD-learning algorithms were used to calculate better Q-learning targets (Chen et al., 2018). Others proposed to combine the actions and value functions of different RL algorithms Wiering and van Hasselt (2008) or the same algorithm with different hyper-parameters Huang et al. (2017). For mixing the ensemble components, complex self-adaptive confidence mechanisms were proposed in Zheng et al. (2018b). Our method is simpler: it uses the same algorithm with the same hyper-parameters without any complex or learnt mixing mechanism. Lee et al. (2020) proposed a unified framework for ensemble learning in deep RL (SUNRISE) which uses bootstrap with random initialization Osband et al. (2016) similarly to our work. We achieve better results than SUNRISE and show in Appendix B that their UCB exploration and weighted Bellman backups do not aid our algorithm performance.
Exploration Various frameworks have been developed to balance exploration and exploitation in RL. The optimism in the face of uncertainty principle Lai and Robbins (1985); Bellemare et al. (2016) assigns an overly optimistic value to each state-action pair, usually in the form of an exploration bonus reward, to promote visiting unseen areas of the environment. The maximum entropy method Haarnoja et al. (2018a) encourages the policy to be stochastic, hence boosting exploration. In the parameter space approach Plappert et al. (2018); Fortunato et al. (2018), noise is added to the network weights, which can lead to temporally-extended exploration and a richer set of behaviours. Posterior sampling Strens (2000); Osband et al. (2016; 2018) methods have similar motivations. They stem from the Bayesian perspective and rely on selecting the maximizing action among sampled and statistically plausible set of action values. The ensemble approach Lowrey et al. (2018); Miłoś et al. (2019); Lee et al. (2020) trains multiple versions of the agent, which yields a diverse set of behaviours and can be viewed as an instance of posterior sampling RL.

heading: 6 CONCLUSIONS

text: We conduct a comprehensive empirical analysis of multiple tools from the RL toolbox applied to the continuous control in the OpenAI Gym MuJoCo setting. We believe that the findings can be useful to RL researchers. Additionally, we propose Ensemble Deep Deterministic Policy Gradients (ED2), an ensemble-based off-policy RL algorithm, which achieves state-of-the-art performance and addresses several issues found during the aforementioned study.

heading: 7 REPRODUCIBILITY STATEMENT

text:
We have made a significant effort to make our results reproducible. We use 30 random seeds, which is above the currently popular choice in the field (up to 5 seeds). Furthermore, we systematically explain our design choices in Section 3 and we provide a detailed pseudo-code of our method in Algorithm 3 in the Appendix B. Additionally, we open-sourced the code for the project3 together with examples of how to reproduce the main experiments. The implementation details are explained in Appendix E and extensive information about the experimental setup is given in Appendix D.
3https://github.com/ed2-paper/ED2

heading: A EXPLORATION EFFICIENCY IN THE CUSTOM HUMANOID ENVIRONMENT

text:
To check the exploration capabilities of our method, we constructed two environments based on Humanoid where the goal is not only to move forward as fast as possible but to find and get to the specific region. The environments are described in Figure 12.
Because the Humanoid initial state is slightly perturbed every run, we compare solved rates over multiple runs, see details in Appendix D. Figure 13 compares the solved rates of our method and the three baselines. Our method outperforms the baselines. For this experiment, our method uses the prior networks (Osband et al., 2018).

heading: B DESIGN CHOICES

text:
In this section, we summarize the empirical evaluation of various design choices grouped by topics related to an ensemble of agents (B.1), exploration (B.2), exploitation (B.3), normalization (B.4), and Q-function updates (B.5). In the plots, a solid line and a shaded region represent an average and a 95% bootstrap confidence interval over 30 seeds in case of ED2 (ours) and 7 seeds otherwise. All of these experiments test ED2 presented in Section 3 with Algorithm 2 used for evaluation (the ensemble critic variant). We call Algorithm 2 a ’vote policy’.
Algorithm 2 Vote policy 1: Input: ensemble size K; policy θk and Q-function φk,1 parameters where k ∈ [1, . . . ,K]; max
action scale M ; 2: function VOTE_POLICY(s, c)
ak = M tanh (µθk(s)) for k ∈ [1, . . . ,K] (1)
3: if use arbitrary critic then
qk = Qφc,1(s, ak) for k ∈ [1, . . . ,K] (2)
4: else use ensemble critic
qk = 1
K ∑ i∈[1...K] Qφi,1(s, ak) for k ∈ [1, . . . ,K] (3)
5: return ak for k = argmaxk qk

heading: B.1 ENSEMBLE

text:
Prior networks We tested if our algorithm can benefit from prior networks (Osband et al., 2018). It turned out that the results are very similar on OpenAI Gym MuJoCo tasks, see Figure 14. However, the prior networks are useful on our crafted hard-exploration Humanoid environments, see Figure 15.
Ensemble size Figure 16 shows ED2 with different ensemble sizes. As can be seen, the ensemble of size 5 (which we use in ED2) achieves good results, striking a balance between performance and computational overhead.
Data bootstrap Osband et al. (2016) and Lee et al. (2020) remark that training an ensemble of agents using the same training data but with different initialization achieves, in most cases, better performance than applying different training samples to each agent. We confirm this observation in Figure 17. Data bootstrap assigned each transition to each agent in the ensemble with 50% probability.
SOP bigger networks and training intensity We checked if simply training SOP with bigger networks or with higher training intensity (a number of updates made for each collected transition) can get it close to the ED2 results. Figure 18 compares ED2 to SOP with different network sizes, while Figure 19 compares ED2 to SOP with one or five updates per environment step. It turns out that bigger networks or higher training intensity does not improve SOP performance.

heading: B.2 EXPLORATION

text:
Vote policy In this experiment, we used the so-called "vote policy" described in Algorithm 2. We use it for action selection in step 5 of Algorithm 3 in two variations: (1) where the random critic, chosen for the duration of one episode, evaluates each actor’s action or (2) with the full ensemble of critics for actors actions evaluation. Figure 20 shows that the arbitrary critic is not much different from our method. However, in the case of the ensemble critic, we observe a significant performance drop suggesting deficient exploration.
UCB We tested the UCB exploration method from Lee et al. (2020). This method defines an upper-confidence bound (UCB) based on the mean and variance of Q-functions in an ensemble and selects actions with the highest UCB for efficient exploration. Figure 21 shows that the UCB exploration method makes the results of our algorithm worse.
Gaussian noise While our method uses ensemble-based temporally coherent exploration, the most popular choice of exploration is injecting i.i.d. noise (Fujimoto et al., 2018; Wang et al., 2020). We evaluate if these two approaches can be used together. We used Gaussian noise with the standard deviation of 0.29, it is the default value in Wang et al. (2020). We found that the effects are taskspecific, barely visible for Hopper and Walker, positive in the case of Humanoid, and negative for Ant – see Figure 22. In a more refined experiment, we varied the noise level. With more noise the Humanoid results are better, whereas the And results are worse – see Figure 23.

heading: B.3 EXPLOITATION

text: We used the vote policy, see Algorithm 2, as the evaluation policy in step 21 of Algorithm 3. Figure 24 shows that the vote policy does worse on the OpenAI Gym MuJoCo tasks. However, on our custom Humanoid tasks introduced in Section 4, it improves our agent performance – see Figure 25.

heading: B.4 NORMALIZATION

text:
We validated if rewards or observations normalization (Andrychowicz et al., 2020a) help our method. In both cases, we keep the empirical mean and standard deviation of each reward/observation coordinate, based on all rewards/observations seen so far, and normalize rewards/observations by subtracting the empirical mean and dividing by the standard deviation. It turned out that only the observations normalization significantly helps the agent on Humanoid, see Figures 26 and 27. The action normalization influence is tested in Appendix C.
B.5 Q-FUNCTION UPDATES
Huber loss We tried using the Huber loss for the Q-function training. It makes the results on all tasks worse, see Figure 28.

heading: C ABLATION STUDY

text:
In this section, we ablate the ED2 components to see their impact on performance and stability. We start with the ensemble exploration and exploitation and then move on to the action normalization and the ERE replay buffer. In all plots, a solid line and a shaded region represent an average and a 95% bootstrap confidence interval over 30 seeds in all but action normalization and ERE replay buffer experiments, where we run 7 seeds.
Exploration & Exploitation In the first experiment we wanted to isolate the effect of ensemblebased temporally coherent exploration on the performance and stability of ED2. Figures 29-32 compare the performance and stability of ED2 and one baseline, SOP, to ED2 with the single actor (the first one) used for evaluation in step 21 of Algorithm 3. It is worth noting that the action selection during the data collection, step 5 in Algorithm 3, is left unchanged – the ensemble of actors is used for exploration and each actor is trained on all the data. This should isolate the effect of exploration on
the test performance of every actor. The results show that the performance improvement and stability of ED2 does not come solely from the efficient exploration. ED2 ablation performs comparably to the baseline and is even less stable.
In the next experiment, we wanted to check if the ensemble evaluation is all we need in that event. Figure 33 compares the performance of ED2 and one baseline, SOP, to ED2 with the single actor (the first one) used for the data collection in step 5 of Algorithm 3. The action selection during the evaluation, step 21 in Algorithm 3, is left unchanged – the ensemble of actors is trained on the data collected only by one of the actors. We add Gaussian noise to the single actor’s actions for exploration as described in Appendix B.2. The results show that the ensemble actor test performance collapses, possibly because of training on the out of distribution data. This implies that the ensemble of actors, used for evaluation, improves the test performance and stability. However, it is required that the same ensemble of actors is also used for exploration, during the data collection.
Action normalization The implementation details of the action normalization are described in Appendix E. Figure 34 shows that the action normalization is especially required on the Ant and Humanoid environments, while not disrupting the training on the other tasks.
ERE replay buffer The implementation details of the ERE replay buffer are described in Appendix E. In Figure 35 we observe that it improves the final performance of ED2 on all tasks, especially on Walker2d and Humanoid.

heading: D EXPERIMENTAL SETUP

text:
Plots In all evaluations, we used 30 evaluation episodes to better access the average performance of each policy, as described in Section 2. For a more pleasant look and easier visual assessment, we smoothed the lines using an exponential moving average with a smoothing factor equal 0.4.
OpenAI Gym MuJoCo In MuJoCo environments, that we used, a state is defined by (x, y, z) position and velocity of the robot’s root, and angular position and velocity of each of its joints. The observation holds almost all information from the state except the x and y position of the robot’s root. The action is a torque that should be applied to each joint of the robot. Sizes of those spaces for each environment are summarised in Table 2.
MuJoCo is a deterministic physics engine thus all simulations conducted inside it are deterministic. This includes simulations of our environments. However, to simplify the process of data gathering and to counteract over-fitting the authors of OpenAI Gym decided to introduce some stochasticity. Each episode starts from a slightly different state - initial positions and velocities are perturbed with random noise (uniform or normal depending on the particular environment).
E IMPLEMENTATION DETAILS
Architecture and hyper-parameters In our experiments, we use deep neural networks with two hidden layers, each of them with 256 units. All of the networks use ReLU as an activation, except on the final output layer, where the activation used varies depending on the model: critic networks use no activation, while actor networks use tanh() multiplied by the max action scale. Table 3 shows the hyper-parameters used for the tested algorithms.
Action normalization Our algorithm employs action normalization proposed by Wang et al. (2020). It means that before applying the squashing function (e.g. tanh()), the outputs of each actor network are normalized in the following way: let µ = (µ1, . . . , µA) be the output of the actor’s network and let G = ∑A i=1 |µi|/A be the average magnitude of this output, where A is the action’s dimensionality. If G > 1 then we normalize the output by setting µi to µi/G for all i = 1, . . . , A. Otherwise, we leave the output unchanged. Each actor’s outputs are normalized independently from other actors in the ensemble.
Algorithm 3 ED2 - Ensemble Deep Deterministic Policy Gradients Input: ensemble sizeK; init. policy θk andQ-functions φk,1, φk,2 param. where k ∈ [1, . . . ,K]; replay buffer D; max action scale M ; target smoothing std. dev. σ; interpolation factor ρ;
1: Set the target parameters φ̄k,1 ← φk,1, φ̄k,2 ← φk,2 2: Sample the current policy index c ∼ U([1, . . . ,K]). 3: Reset the environment and observe the state s. 4: repeat 5: Execute action a = M tanh (µθc(s)) . µ uses the action normalization 6: Observe and store (s, a, r, s′, d) in the replay buffer D. 7: Set s← s′ 8: if episode is finished then 9: Reset the environment and observe initial state s. 10: Sample the current policy index c ∼ U([1, . . . ,K]). 11: if time to update then 12: for as many as steps done in the environment do 13: Sample a batch of transitions B = {(s, a, r, s′, d)} ⊂ D . uses ERE 14: Compute targets
yk(r, s ′, d) = r + γ(1− d) min
i=1,2 Qφ̄k,i(s
′, a′k)
a′k = M tanh (µθk(s ′) + ) , ∼ N (0, σ)
15: Update the Q-functions by one step of gradient descent using
∇φk,i 1 |B| ·K ∑
(s,a,r,s′,d)∈B
( Qφk,i(s, a)− yk(r, s′, d) )2 for i ∈ {1, 2}, k ∈ [1, . . . ,K]
16: Update the policies by one step of gradient ascent using
∇θk 1 |B| ·K ∑ s∈B Qφk,1(s, µθk(s)) for k ∈ [1, . . . ,K]
17: Update target parameters with
φ̄k,i ← ρφ̄k,i + (1− ρ)φk,i for i ∈ {1, 2}, k ∈ [1, . . . ,K]
18: if time to evaluate then 19: for specified number of evaluation runs do 20: Reset the environment and observe the state s. 21: Execute policy a = 1K ∑K i=1M tanh (µθi(s)) until the terminal state. 22: Record and log the return. 23: until convergence
Emphasizing Recent Experience We implement the Emphasizing Recent Experience (ERE) mechanism from Wang et al. (2020). ERE samples non-uniformly from the most recent experiences stored in the replay buffer. Let B be the number of mini-batch updates and |D| be the size of the replay buffer. When performing the gradient updates, we sample from the most recent cb data points stored in the replay buffer, where cb = |D| · ηb 1000 B for b = 1, . . . , B.
The hyper-parameter η starts off with a set value of η0 and is later adapted based on the improvements in the agent training performance. Let Irecent be the improvement in terms of training episode returns made over the last |D|/2 time-steps and Imax be the maximum of such improvements over the course of the training. We adapt η according to the formula:
η = η0 · Irecent Imax + 1− Irecent Imax
Our implementation uses the exponentially weighted moving average to store the value of Irecent. More concretely, we define Irecent based on two additional parameters Rrecent and Rprev so that Irecent = Rrecent −Rprev . Those parameters are then updated whenever we receive a new training episode return ep_ret:
Rrecent = λrecent · ep_ret+ (1− λrecent) ·Rrecent Rprev = λprev · ep_ret+ (1− λprev) ·Rprev
where λprev = T/b |D|2 c, λrecent = 10 · λprev and T is the maximum length of an episode.
Hardware During the training of our models, we employ only CPUs using a cluster where each node has 28 available cores of 2.6 GHz, alongside at least 64 GB of memory. The running time of a typical experiment did not exceed 24 hours.


summaries: This paper studies the problem of fair supervised learning under the Equalized Loss (EL) fairness notion, which is formulated as a non-convex constrained optimization problem. The authors introduce two algorithms that find the global (sub-)optimal solution by solving a sequence of convex (constrained) optimizations. Empirically, the algorithms perform well.

summaries: The authors consider minimization of convex losses constrained by either bounded loss on each group, or bounded difference of losses over two groups. The second formulation is non-convex, whereas the first formulation is convex.   When the losses are strictly convex on both the demographic groups, so that their optima are distinct (I think this is the condition they need, but they use a more restrictive condition in the paper), they can find the "EL" fair predictor by solving a sequence of convex constrained optimizations, by exploiting a monotonicity property. They next give a more computationally efficient approximate algorithm for finding the EL fair predictor.

summaries: The authors study fair prediction subject to Equalized Loss (EL), and they introduce a variety of approaches for exactly and approximately solving the problem of finding the globally optimal predictor that satisfies EL. First, they show how to solve a sequence of convex constrained optimization problems in order to solve the larger non-convex problem. Next, they show how to approximately solve this problem more efficiently by using unconstrained convex optimization. Lastly, they evaluate both of their approaches on two datasets.

summaries: This paper studies supervised learning models with fairness constraints. They specifically consider equalized loss fairness constraint.  When a traditional (convex) loss minimization problem is cast with additional fairness constraints, the corresponding problem is non-convex. They provide algorithms to efficiently solve this problem up to global optimality. They demonstrate the performance of their algorithms on real-world data.

abstractText: Supervised learning models have been increasingly used in various domains such as lending, college admission, natural language processing, face recognition, etc. These models may inherit pre-existing biases from training datasets and exhibit discrimination against protected social groups. Various fairness notions have been introduced to address fairness issues. In general, finding a fair predictor leads to a constrained optimization problem, and depending on the fairness notion, it may be non-convex. In this work, we focus on Equalized Loss (EL), a fairness notion that requires the prediction error/loss to be equalized across different demographic groups. Imposing this constraint to the learning process leads to a non-convex optimization problem even if the loss function is convex. We introduce algorithms that can leverage off-the-shelf convex programming tools and efficiently find the global optimum of this non-convex problem. In particular, we first propose the ELminimizer algorithm, which finds the optimal EL fair predictor by reducing the non-convex optimization problem to a sequence of convex constrained optimizations. We then propose a simple algorithm that is computationally more efficient compared to ELminimizer and finds a sub-optimal EL fair predictor using unconstrained convex programming tools. Experiments on real-world data show the effectiveness of our algorithms.

authors:
Alekh Agarwal
Alina Beygelzimer
Miroslav Dudı́k
John Langford
Hanna Wallach

title: A reductions approach to fair classification

venue: In International Conference on Machine Learning,

authors:
Alekh Agarwal
Miroslav Dudik
Zhiwei Steven Wu

title: Fair regression: Quantitative definitions and reduction-based algorithms

authors:
Animashree Anandkumar
Rong Ge

title: Efficient approaches for escaping higher order saddle points in non-convex optimization

venue: In Conference on learning theory,

authors:
Peter L Bartlett
Shahar Mendelson

title: Rademacher and gaussian complexities: Risk bounds and structural results

venue: Journal of Machine Learning Research,

authors:
Aharon Ben-Tal
Michael Zibulevsky

title: Penalty/barrier multiplier methods for convex programming problems

venue: SIAM Journal on Optimization,

authors:
Richard Berk
Hoda Heidari
Shahin Jabbari
Michael Kearns
Aaron Roth

title: Fairness in criminal justice risk assessments: The state of the art

venue: Sociological Methods & Research,

authors:
Asia J Biega
Krishna P Gummadi
Gerhard Weikum

title: Equity of attention: Amortizing individual fairness in rankings

venue: In The 41st international acm sigir conference on research & development in information retrieval,

authors:
Flavio P Calmon
Dennis Wei
Bhanukiran Vinzamuri
Karthikeyan Natesan Ramamurthy
Kush R Varshney

title: Optimized pre-processing for discrimination prevention

venue: In Proceedings of the 31st International Conference on Neural Information Processing Systems,

authors:
L Elisa Celis
Vijay Keswani
Nisheeth Vishnoi

title: Data preprocessing to mitigate bias: A maximum entropy based approach

authors:
Vincent Conitzer
Rupert Freeman
Nisarg Shah
Jennifer Wortman Vaughan

title: Group fairness for the allocation of indivisible goods

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

title: Amazon scraps secret ai recruiting tool that showed bias against women

venue: http: //reut.rs/2MXzkly,

authors:
Julia Dressel
Hany Farid

title: The accuracy, fairness, and limits of predicting recidivism

venue: Science advances,

authors:
Cynthia Dwork
Moritz Hardt
Toniann Pitassi
Omer Reingold
Richard Zemel

title: Fairness through awareness

venue: In Proceedings of the 3rd innovations in theoretical computer science conference,

authors:
Jack Fitzsimons
AbdulRahman Al Ali
Michael Osborne
Stephen Roberts

title: A general framework for fair regression

authors:
Rong Ge
Furong Huang
Chi Jin
Yang Yuan

title: Escaping from saddle points—online stochastic gradient for tensor decomposition

authors:
Swati Gupta
Vijay Kamble

title: Individual fairness in hindsight

venue: In Proceedings of the 2019 ACM Conference on Economics and Computation,

authors:
Moritz Hardt
Eric Price
Nati Srebro

title: Equality of opportunity in supervised learning

venue: Advances in neural information processing systems,

title: The accent gap

authors:
Christopher Jung
Michael Kearns
Seth Neel
Aaron Roth
Logan Stapleton
Zhiwei Steven Wu

title: Eliciting and enforcing subjective individual fairness

authors:
Faisal Kamiran
Toon Calders

title: Data preprocessing techniques for classification without discrimination

venue: Knowledge and Information Systems,

authors:
Mohammad Mahdi Khalili
Xueru Zhang
Mahed Abroshan
Somayeh Sojoudi

title: Improving fairness and privacy in selection problems

venue: arXiv preprint arXiv:2012.03812,

title: Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid

venue: In Kdd,

authors:
Junpei Komiyama
Akiko Takeda
Junya Honda
Hajime Shimao

title: Nonconvex optimization for regression with fairness constraints

venue: In International conference on machine learning,

authors:
Mehrdad Mahdavi
Tianbao Yang
Rong Jin
Shenghuo Zhu
Jinfeng Yi

title: Stochastic gradient descent with only one projection

authors:
Angelia Nedić
Asuman Ozdaglar

title: Subgradient methods for saddle-point problems

venue: Journal of optimization theory and applications,

authors:
Christian Reimers
Paul Bodesheim
Jakob Runge
Joachim Denzler

title: Towards learning an unbiased classifier from biased data via conditional adversarial debiasing

venue: arXiv preprint arXiv:2103.06179,

authors:
Shai Shalev-Shwartz
Shai Ben-David

title: Understanding machine learning: From theory to algorithms

venue: Cambridge university press,

title: On the convergence of the newton/log-barrier method

venue: Mathematical programming,

authors:
Muhammad Bilal Zafar
Isabel Valera
Manuel Gomez-Rodriguez
Krishna P Gummadi

title: Fairness constraints: A flexible approach for fair classification

venue: The Journal of Machine Learning Research,

authors:
Brian Hu Zhang
Blake Lemoine
Margaret Mitchell

title: Mitigating unwanted biases with adversarial learning

venue: In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society,

authors:
Xueru Zhang
Mohammadmahdi Khaliligarekani
Cem Tekin

title: Group retention when using machine learning in sequential decision making: the interplay between user dynamics and fairness

venue: Advances in Neural Information Processing Systems,

authors:
Xueru Zhang
Mohammad Mahdi Khalili
Mingyan Liu

title: Long-term impacts of fair machine learning

venue: Ergonomics in Design,

heading: 1 INTRODUCTION

text:
As machine learning (ML) algorithms are increasingly being used in applications such as education, lending, recruitment, healthcare, criminal justice, etc., there is a growing concern that the algorithms may exhibit discrimination against protected population groups. For example, speech recognition products such as Google Home and Amazon Alexa were shown to have accent bias (Harwell, 2018). The COMPAS recidivism prediction tool, used by courts in the US in parole decisions, has been shown to have a substantially higher false positive rate for African Americans compared to the general population (Dressel & Farid, 2018). Amazon had been using automated software since 2014 to assess applicants’ resumes, which were found to be biased against women (Dastin, 2018).
Various fairness notions have been proposed in the literature to measure and remedy the biases in ML systems; they can be roughly classified into two classes: 1) individual fairness focuses on the equity at individual level and it requires the similar individuals to be treated similarly (Dwork et al., 2012; Biega et al., 2018; Jung et al., 2019; Gupta & Kamble, 2019); 2) group fairness requires certain statistical measures to be (approximately) equalized across different groups distinguished by some sensitive attributes. Their suitability for use is often application dependent, and many of them are incompatible with each other (Zhang et al., 2019; Hardt et al., 2016; Conitzer et al., 2019; Zhang et al., 2020; Khalili et al., 2020). Extensive approaches have been developed to satisfying a given definition of fairness and they generally fall under three categories: pre-processing, by modifying the original dataset such as removing certain features and reweighing, e.g., (Kamiran & Calders, 2012; Celis et al., 2020); in-processing, by modifying the algorithms such as imposing fairness constraints or changing objective functions, e.g., (Zhang et al., 2018; Agarwal et al., 2018; 2019; Reimers et al., 2021; Calmon et al., 2017); post-processing, by adjusting the output of the algorithms based on sensitive attributes, e.g., (Hardt et al., 2016).
In this paper, we focus on group fairness and we aim to mitigate unfairness issues in supervised learning using in-processing approaches. The problem can be cast as a constrained optimization problem where a fair predictor can be found by minimizing the prediction error (i.e., loss) subject to certain group fairness constraint. In Section 2.1, we present a number of definitions of commonly used group fairness notions, namely, statistical parity (Dwork et al., 2012), equal opportunity (Hardt et al., 2016), equalized loss (Zhang et al., 2019), and bounded group loss (Agarwal et al., 2019). Here we are particularly interested in equalized loss which requires the expected loss to be equalized across different groups.
Constrained optimization problems for finding a fair predictor have been studied in the iterature. In general, imposing a fairness criterion to the optimization problem may lead to a non-convex optimization problem. Existing works have proposed various approaches to solving such a non-convex optimization in different settings. For example, Komiyama et al. (2018) studied the non-convex optimization for regression problems under the coefficient of determination constraint. Agarwal et al. (2019) proposed an approach to finding a fair regression model under bounded group loss and statistical parity fairness constraints. Agarwal et al. (2018) studied classification problems and aimed at finding fair classifiers under various fairness notions including statistical parity and equal opportunity. In particular, they considered zero-one loss as the objective function and trained a randomized fair classifier over a finite hypothesis space; this problem was reduced to a problem of finding the saddle point of a linear Lagrangian function in (Agarwal et al., 2018). Zhang et al. (2018) proposed an adversarial debasing technique to find a fair classifier under equalized odd, equal opportunity, and statistical parity. However, there is no guarantee that this technique finds the global optimal solution. The main difference between the present work and the existing in-processing approaches are as follows: 1) we consider a non-convex problem for finding a fair predictor satisfying Equalized Loss fairness notion, which has not been studied in the literature to the best of our knowledge. 2) We propose algorithms for finding the global optimal solution to this non-convex problem efficiently. 3) Our algorithms are easy to implement and are applicable to both regression and classification problems. 4) Unlike (Agarwal et al., 2018), our algorithms are not limited to finite hypothesis space.
Non-convex optimization problems have also been studied in other contexts such as learning overparametrized models. For example, deep neural networks are typically trained by solving unconstrained, non-convex problems, and methods such as gradient descent may not be suitable as they are likely to find saddle points but not optimums. To address this issue, approaches have been proposed in recent works by incorporating the higher order derivatives (Celis et al., 2020; Anandkumar & Ge, 2016) or noisy gradients (Ge et al., 2015). However, these methods only find a local minimum (not a global minimum) and are not applicable to our problem with a non-convex constraint.
In this work, we develop novel algorithms that find the fair (sub-)optimal solutions under Equalized Loss fairness constraint efficiently. Note that while our approach and algorithms are presented in the context of fair machine learning, they are applicable to any problem that can be formulated as a constrained optimization problem in the form of minw L0(w)+αL1(w) s.t. |L0(w)−L1(w)| < γ, where α is a constant
Our main contributions and findings are as follows. 1. We study the relationship between Equalized Loss (EL) and Bounded Group Loss (BGL) fairness
notions. We show that given the existence of feasible solutions satisfying (approximate) BGL fairness, imposing (approximate) EL fairness constraint never increase losses of both groups simultaneously (Theorems 1 and 2 in Section 2.1). These results help policy makers to have a better understanding of these two fairness notions.
2. We develop an algorithm (ELminimizer) to solve a non-convex constrained optimization problem that finds the optimal (approximate) EL fair solution. We show that such non-convex optimization can be reduced to a sequence of convex constrained optimizations and the convergence property of the algorithm is analyzed (Theorems 3 and 4, Section 3).
3. We develop a simple algorithm for finding a sub-optimal (approximate) EL fair solution. We show that a sub-optimal solution is a linear combination of optimal solutions to two unconstrained optimizations and it can be found efficiently without solving constrained optimizations (Theorem 5, Section 4).
4. We conduct sample complexity analysis and provide the guarantee on generalization performance (Theorem 7, Section 5).
5. We validate the theoretical results by conducting experiments on real-world data (Section 6).

heading: 2 PROBLEM FORMULATION

text:
Consider a supervised learning problem where the training dataset consists of triples (X,A, Y ) from two social groups. Random variableX ∈ X ⊂ Rdx is the feature vector (in form of a column vector), A ∈ {0, 1} is the sensitive attribute (e.g., race, gender) indicating the group membership, and Y ∈ Y ⊂ R is the label. The feature vector X may or may not include sensitive attribute A. Label Y can be either discrete or continuous depending on the given problem: if Y is discrete (resp. continuous), then the problem is a classification (resp. regression) problem. Let F be a set of predictors fw : X → R parameterized by weight vector w ∈ Rdw .1 Consider loss function l : Y×X → Rwhere l(Y, fw(X )) measures the error of fw in predicting label Y . Denote the expected loss with respect to the joint probability distribution of (X,Y ) by L(w) := E{l(Y, fw(X ))}. Then, La(w) := E{l(Y, fw(X ))|A = a} denotes the expected loss of the group with attribute A = a. A predictor that minimizes the total expected loss, i.e., argminw L(w), can be biased against certain groups. To mitigate the risk of unfairness, various fairness notions have been proposed in the literature. Some of the most commonly used notions of group fairness are as follows: 1) Statistical Parity (SP) (Dwork et al., 2012) implies that the predictor and the sensitive attribute should be independent, i.e., fw(X ) ⊥ A; 2) Equal Opportunity (EqOpt) (Hardt et al., 2016) requires that conditional on Y = 1, prediction and sensitive attribute are independent, i.e., fw(X ) ⊥ A|Y = 1; 3) Equalized Odds (EO) (Hardt et al., 2016) requires the conditional independence between prediction and sensitive attribute given Y , i.e., fw(X ) ⊥ A|Y ; 4) Equalized Loss (EL) (Zhang et al., 2019; Berk et al., 2021) requires that the losses experienced by different groups are equalized, i.e., L0(w) = L1(w); 5) Bounded Group Loss (BGL) (Agarwal et al., 2019) requires that the loss experienced by each group is bounded.
With fairness consideration, the goal is to find weight vectorw that minimizes total expected loss in predicting Y givenX , subject to certain fairness condition, i.e., minw L(w) s.t. fairness constraint. This is a typical formulation in fair machine learning literature, and above method of finding a fair predictor belongs to in-processing approaches. Because such constrained optimization can be nonconvex, finding the optimal solution efficiently can be challenging. In this work, we develop novel algorithms that solves such an optimization problem udder EL fairness constraint.
2.1 EQUALIZED LOSS (EL) AND BOUNDED GROUP LOSS (BGL)
As mentioned in Section 2, various fairness notions have been introduced in the literature. Among them, Statistical Parity (SP), Equal Opportunity (EqOpt), Equalized Odds (EO), and Bounded Group Loss (BGL) have been studied extensively in the literature, and both in-processing and postprocessing approaches have been developed to satisfy these constraints (Dwork et al., 2012; Agarwal et al., 2018; Hardt et al., 2016; Zafar et al., 2019; Fitzsimons et al., 2019). Note that different fairness notions may be conflict with each other and which one to adopt is application and context dependent. In this work, we are interested in Equalized Loss (EL) fairness notion (Zhang et al., 2019; Berk et al., 2021) which implies that the prediction error should be the same across different groups,2 and Group Bounded Loss (BGL) fairness notion (Agarwal et al., 2019) which requires the prediction error of every group to be bounded. We consider a relaxed version of EL fairness defined as follows.
Definition 1 (γ-EL) A predictor f satisfies γ-EL if the expected losses experienced by different demographic groups satisfy the following,
− γ ≤ L0(w)− L1(w) ≤ γ. (1)
Parameter γ controls the degree of fairness; the smaller γ implies the stronger fairness. When γ = 0, the exact EL fairness is attained. We say a group is disadvantaged if it experiences a larger loss. Similarly, Group Bounded Loss (BGL) fairness notion is formally defined as follows.
Definition 2 (γ-BGL) A predictor f satisfies γ-BGL if the expected loss of each demographic group is bounded by γ, i.e.,
La(w) ≤ γ, ∀a ∈ {0, 1}. (2) 1Predictive models such as logistic regression, linear regression, deep learning models, etc., are parameter-
ized by a weight vector. 2EL has also been referred to as Overall Accuracy Equality in (Berk et al., 2021; Agarwal et al., 2019).
2.2 RELATIONS BETWEEN γ-EL AND γ-BGL
In this section, we formally study the relations between γ-EL and γ-BGL fairness notions. Under γ-EL fairness constraint, finding a fair predictor is equivalent to solving the following constrained optimization problem:
minw L(w) s.t. |L0(w)− L1(w)| ≤ γ. (3)
Letw∗ be denoted as the solution to (3) and fw∗ is the optimal γ-EL fair predictor. Theorem 1 below shows that given the existence of a feasible point satisfying γ-BGL fairness, it’s impossible for both groups experiencing loss larger than γ from the optimal γ-EL fair predictor.
Theorem 1 Consider the following optimization for finding the optimal γ-BGL fair predictor,
minw L(w) s.t. La(w) ≤ γ, ∀a ∈ {0, 1}. (4)
If L0(w∗) > γ and L1(w∗) > γ, then optimization problem (4) does not have a feasible point.
Proof 1 We prove by contradiction. Assume w̃ is a feasible point of optimization (4). Note that w̃ is a feasible point for optimization problem (3) as well. Since both L0(w∗) and L1(w∗) are larger than γ, we have,
E{l(Y, fw∗)} = Pr{A = 0}L0(w∗) + Pr{A = 1}L1(w∗) > γ, E{l(Y, fw̃)} = Pr{A = 0}L0(w̃) + Pr{A = 1}L1(w̃) ≤ γ.
Therefore,w∗ can not be the solution to (3). This contradiction proves that the optimization problem (4) cannot have a feasible point.
Theorem 1 implies that if γ-EL notion leads to an increase of the loss of every demographic group, then there is no optimal predictor under γ-BGL.3 The next theorem further shows that for any predictor satisfying γ-EL, it must satisfy 2γ-BGL.
Theorem 2 Assume optimization problem (4) has at least one feasible point. Then, we have,
min{L0(w∗), L1(w∗)} ≤ γ and max{L0(w∗), L1(w∗)} ≤ 2γ.
Proof 2 Let w̃ be a feasible point of optimization problem (4), then w̃ is also a feasible point to (3). If min{L0(w∗), L1(w∗)} > γ, then L(w∗) > γ ≥ L(w̃) must hold. This is a contradiction because it implies thatw∗ is not an optimal solution to (3). Therefore, min{L0(w∗), L1(w∗)} ≤ γ. Similarly, we can prove max{L0(w∗), L1(w∗)} ≤ 2γ by contradiction. Assume max{L0(w∗), L1(w∗)} > 2γ. Then, max{L0(w∗), L1(w∗)} − min{L0(w∗), L1(w∗)} > γ which shows that w∗ is not a feasible point for (3). This is a contradiction. Therefore, max{L0(w∗), L1(w∗)} ≤ 2γ.
Theorems 1 and 2 investigated the relations between EL and BGL fairness notions. Since γ-EL implies 2γ-BGL and it additionally requires the approximate equality across different groups, we will focus on γ-EL fairness notion in the rest of the paper. Because optimization problem (3) is a non-convex optimization, finding the optimal fair γ-EL solution efficiently can be challenging. In the next sections, we propose a number of algorithms that are easy to implement and can solve the optimization (3) efficiently.

heading: 3 OPTIMAL FAIR MODEL UNDER EL FAIRNESS

text:
In this section, we consider the optimization problem (3) under the EL fairness constraint. Note that this optimization problem is non-convex and finding the global optimal solution is difficult. However, we propose an algorithm which is able to find the solution to non-convex optimization (3) by solving a sequence of convex optimization problems. Before presenting the algorithm, we need to introduce two assumptions.
Assumption 1 L0(w), L1(w), and L(w) are strictly convex functions inw. 3Theorem 1 is related to (Agarwal et al., 2019). In particular, they considered γ-BGL fairness and mentioned that the equalized loss fairness notion may increase the loss of both groups.
Algorithm 1: Function ELminimizer 1 ELminimizer(wG0 ,wG1 , , γ): 2 λ0start = L0(wG0) 3 λ0end = L0(wG1) 4 Define L̃1(w) = L1(w) + γ 5 i = 0
6 while λ(i)end − λ (i) start > do 7 λ (i) mid = (λ (i) end + λ (i) start)/2; 8 Solve the following convex optimization problem,
w∗i = argmin w L̃1(w) s.t. L0(w) ≤ λ(i)mid (5)
9 λ(i) = L̃1(w ∗ i );
10 if λ(i) ≥ λ(i)mid then 11 λ
(i+1) start = λ (i) mid; λ (i+1) end = λ (i) end;
12 end 13 else 14 λ
(i+1) end = λ (i) mid; λ (i+1) start = λ (i) start;
15 end 16 i = i+ 1; 17 end
18 Returnw∗i
Example 1 Consider a linear classifier fw(X ) = wTX with squared loss l(Y, fw(X )) = (wTX − Y )2. In this example, E{l(Y, fw(X ))} = wTE{XXT }w − 2E{YXT }w + E{Y 2} is strictly convex in w if covariance matrix E{XXT } is positive definite. Similarly, La(w) is strictly convex if E{XXT |A = a} is positive definite.
LetwGa be the weight vector minimizing the loss associated with group A = a. That is,
wGa = argmin w La(w). (6)
Since optimization problem (6) is an unconstrained convex optimization problem,wGa can be found efficiently by the first order condition or the gradient descent. We make the following assumption.
Assumption 2 We assume that the following holds,
L0(wG0) ≤ L1(wG0) and L1(wG1) ≤ L0(wG1).
Algorithm 2: Solving Optimization Problem (3) Input: wG0 ,wG1 , ,γ
1 wγ = ELminimizer(wG0 ,wG1 , , γ); 2 w−γ = ELminimizer(wG0 ,wG1 , ,−γ); 3 if L(wγ) ≤ L(w−γ) then 4 w∗ = wγ ; 5 end 6 else 7 w∗ = w−γ ; 8 end
Output: w∗
Assumption 2 implies that when a group experiences its lowest possible loss, it should not be the disadvantaged group. Under Assumption 2, given wG0 and wG1 , Algorithm 1 with γ = 0 (i.e., function ELminimizer(wG0 ,wG1 , , 0)) finds the optimal 0-EL fair solution, where parameter > 0 specifies the stopping criterion; as → 0, the output approaches to the optimal solution. Intuitively, Algorithm 1 solves non-convex optimization (3) by solving a sequence of convex and constrained optimization problems. If γ > 0, Algorithm 2 finds the optimal predictor under γ-EL using function ELminimizer.
The convergence of Algorithm 1 for finding the optimal 0-EL fair solution, and convergence of Algorithm 2 for finding the optimal γ-EL fair solution are proved in the following theorems.
Theorem 3 Consider sequences {λ(i)mid|i = 1, 2, . . .} and {w∗i |i = 1, 2, . . .} generated by Algorithm 1 when γ = 0, i.e., ELminimizer(wG0 ,wG1 , → 0, 0). Under Assumptions 1 and 2, we have,
lim i→∞
w∗i = w ∗ and lim i→∞ λ (i) mid = E{L(Y, fw∗(X))}
where fw∗ is the optimal 0-EL fair predictor.
Similarly, we can prove the convergence for the approximate EL fairness when γ 6= 0.
Theorem 4 Assume that L0(wG0) − L1(wG0) < −γ and L0(wG1) − L1(wG1) > γ. Then, as → 0, the output of Algorithm 2 goes to the optimal γ-EL fair solutionw∗.
Complexity Analysis: The While loop in Algorithm 1 is executed for O(log(1/ )) times. Therefore, Algorithm 1 needs to solve a constrained convex optimization problem for O(log(1/ )) times. Note that constrained convex optimization problems can be efficiently solved via sub-gradient methods (Nedić & Ozdaglar, 2009), brier methods (Wright, 2001), stochastic gradient descent with one projection (Mahdavi et al., 2012), etc. For instance, Nedić & Ozdaglar (2009) introduces a subgradient method that finds the saddle point of the Lagrangian function corresponding to (5) and it converges at the rate ofO(1/k) (k is the number of iterations). Therefore, if is the maximum error tolerance for (5), the total time complexity of Algorithm 2 is O(1/ log(1/ )).
4 SUB-OPTIMAL FAIR MODEL UNDER γ-EL
In Section 3, we have shown that non-convex optimization problem (3) can be reduced to a sequence of convex constrained optimizations (5), and based on this we proposed an algorithm (Algorithm 2) that finds the optimal γ-EL fair predictor. However, the proposed algorithm still requires solving a convex constrained optimization in each iteration. In this section, we propose another algorithm which finds a sub-optimal solution to optimization (3) without solving constrained optimization in each iteration.
The algorithm consists of two phases in sequence: (1) finding two weight vectors by solving two unconstrained convex optimization problems; (2) generating a new weight vector satisfying γ-EL fairness with the two weight vectors found in the first phase. Because of the convexity, two unconstrained convex optimization problems in the first phase can be solved efficiently.
Phase 1: Unconstrained optimization. In this phase, we remove EL fairness constraint and first solve the following uncontrained optimization problem,
wO = argmin w L(w) (7)
Because L(w) is strictly convex inw, the above optimization problem can be solved efficiently using the gradient descent method. Predictor fwO is the optimal predictor without fairness constraint, and L(wO) is the smallest overall expected loss that is attainable. Let â = argmaxa∈{0,1} La(wO), i.e., group â is the group that is disadvantaged under predictor fwO . Then, for the disadvantaged group â, we findwGâ by solving unconstrained optimization problem (6).
Phase 2: Binary search to find the fair predictor. For β ∈ [0, 1], we define the followings, g(β) = Lâ ( (1− β)wO + βwGâ ) − L1−â ( (1− β)wO + βwGâ ) ;
h(β) = L ( (1− β)wO + βwGâ ) ,
where function g(β) can be interpreted as loss disparity between two demographic group under predictor f(1−β)wO+βwGâ , and h(β) is the corresponding overall expected loss. Some properties of functions g(.) and h(.) are summarized in the following theorem.
Theorem 5 Under Assumptions 1 and 2, the followings hold,
1. There exists β0 ∈ [0, 1] such that g(β0) = 0. 2. h(β) is strictly increasing in β ∈ [0, 1]; g(β) is strictly decreasing in β ∈ [0, 1].
Theorem 5 implies that in a dw dimensional space, if we start fromwO and move towardwGâ along a straight line, the overall loss increases and the disparity between two groups decreases until we reach (1 − β0)wO + β0wGâ , at which 0-EL fairness is satisfied. Note that β0 is the unique root of g. Since g(β) is a strictly decreasing function, β0 can be found using binary search. For the approximate γ-EL fairness, there are multiple values of β such that (1− β)wO + βwGâ satisfies γEL. Since h(β) is strictly increasing in β, among all β that satisfies γ-EL fairness, we would choose the smallest one. The method for finding a sub-optimal solution to optimization (3) is described in Algorithm 3.
Algorithm 3: Sub-optimal solution to optimization problem (3) 1 Input: wGâ ,wO, , γ 2 Initialization: gγ(β) = g(β)− γ, i = 0, β(0)start = 0, β (0) end = 1 3 if gγ(0) ≤ 0 then 4 w = wO, and go to line 16; 5 end 6 while β(i)end − β (i) start > do 7 β (i) mid = (β (i) start + β (i) end)/2; 8 if gγ(β (i) mid) ≥ 0 then 9 β (i+1) start = β (i) mid, β (i+1) end = β (i) end;
10 end 11 else 12 β
(i+1) start = β (i) start, β (i+1) end = β (i) mid;
13 end 14 end 15 w = (1− β(i)mid)wO + β (i) midwGâ ; 16 Output: w
Note that while loop in Algorithm 3 is repeated for O(log(1/ )) times. Since the time complexity of operations in each loop isO(1), the total time complexity of Algorithm 3 isO(log(1/ )). We can formally prove that the output returned by Algorithm 3 satisfies γ-EL fairness constraint.
Theorem 6 Assume that Assumption 1 holds. If gγ(0) ≤ 0, then wO satisfies the γ-EL fairness; if gγ(0) > 0, then limi→∞ β (i) mid = β (∞) mid exists, and (1 − β (∞) mid)wO + β (∞) midwGâ satisfies the γ-EL fairness constraint.
It is worth mentioning, since h(β) is incrasing, we are intrested in finding the smallest possible β that (1 − β)wO + βwGâ satisfies γ-EL. Here, β (∞) mid is the smallest possible β under which (1 − β)wO + βwGâ satisfies γ-EL.

heading: 5 GENERALIZATION PERFORMANCE

text:
So far we proposed algorithms for solving optimization (3). In practice, the joint probability distribution of (X,A, Y ) is often unknown and the expected loss needs to be estimated using the empirical loss. Specifically, given n samples (X i, Ai, Yi), i = 1, . . . , n and predictor fw , the empirical losses of entire population and each group are defined as follows,
L̂(w) = 1
n n∑ i=1 l(Yi, fw(X i)); L̂a(w) = 1 na ∑ i:Ai=a l(Yi, fw(X i)), (8)
where na = |{i|Ai = a}|. Because γ-EL fairness constraint is defined in terms of expected loss, the optimization problem of finding an optimal γ-EL fair predictor using empirical losses is as follows,
ŵ = argmin w
L̂(w) s.t. |L̂0(w)− L̂1(w)| ≤ γ̂. (9)
Note that γ̂ 6= γ and one goal in this section is to find relation between γ̂ and γ. We aim to investigate how to determine γ̂ so that with high probability the predictor found by solving problem (9) satisfies
γ-EL fairness, and meanwhile ŵ is a good estimate of w∗. To present our result, we make the following assumption.
Assumption 3 With probability 1− δ, we have the following, sup fw∈F |L(w)− L̂(w)| ≤ B(δ, n,F), where B(δ, n,F) is a bound that goes to zero as n goes to infinity.
Note that if the class F is learnable with respect to loss function l, then there exists such a bound B(δ, n,F) that goes to zero as n goes to infinity (Shalev-Shwartz & Ben-David, 2014).4
Theorem 7 Let F be a set of learnable functions, and let fŵ and fw∗ be the solution to (9) and (3) respectively with γ̂ = γ + ∑ a∈{0,1}B(δ, na,F). Then, with probability at least 1 − 6δ the followings hold, L(ŵ)− L(w∗) ≤ 2B(δ, n,F) and |L0(ŵ)− L1(ŵ)| ≤ γ + 2B(δ, n0,F) + 2B(δ, n1,F).
Theorem 7 shows that as n0, n1 go to infinity, γ̂ → γ, and both empirical loss and expected loss satisfy γ-EL. In addition, as n goes to infinity, the expected loss at ŵ goes to the minimum possible expected loss. Therefore, solving (9) using empirical loss is equivalent to solving (3) if the number of data points from each group is sufficiently large.

heading: 6 EXPERIMENTS

heading: 6.1 EXPERIMENT 1: QUADRATIC FUNCTIONS

text:
First, we solve optimization problem (3) given the following quadratic functions, L0(w) = (w1 + 5) 2 + (w2 + 2) 2 + (w3 + 1)
2 + 4w1 · w3, L1(w) = (w1 − 9)2 + (w2 − 9)2 + (w3 − 9)2 + w1 · w2 + w2 · w3 + w1 · w3 + 1, L(w) = L0(w) + L1(w).
By the first order condition, we obtainwG0 ,wG1 ,wO as follows, wG0 = [1,−2,−3]T , wG1 = [4.5, 4.5, 4.5]T , wO = [24.53, 3.0, 26.53]T We use Algorithm 1 to find the optimal solution to (3) and run Algorithm 3 to find a sub-optimal solution. In particular, we adopt the penalty method (Ben-Tal & Zibulevsky, 1997) to solve constrained convex optimization (5), i.e., by solving the following unconstrained optimization,
min w
L1(w) + t ·max{0, (L0(w)− λ(i)mid)} 2, (10)
where t is the penalty parameter. We solve the optimization problem (10) using gradient descent with learning rate 0.001 and 10000 iterations. We set penalty parameter t = 0.5 and increase t by 0.1 after every 250 iterations. Note that optimization (5) is convex and the penalty method for a constrained convex optimization converges to the optimal solution (Ben-Tal & Zibulevsky, 1997).
We compare the our algorithms with a baseline: the solution to optimization problem (3) found using the penalty method, i.e., by solving the following unconstrained optimization, min w L0(w) +L1(w) + t · [ max{0, (L0(w)− L1(w)− γ)}2 +max{0, (L1(w)− L0(w)− γ)}2 ] . (11) When solving the optimization problem (11), we use learning rate 0.001. We set penalty parameter t = 0.5 and increase it by 0.1 every 250 iterations. Figure 1a illustrates the overall loss L(w) at the (sub-) optimal points obtained from Algorithms 2 and 3 and the baseline. x-axis represents fairness parameter γ. Since Algorithm 2 converges to the optimal solution, it achieves the smallest loss. Figure 1b illustrates the distance of the optimal point w∗ from the sub-optimal solutions obtained by Algorithm 3 and the baseline penalty method. It shows that when γ is sufficiently large (less strict fairness constraint), a sub-optimal solution generated by Algorithm 3 is closer to the optimal solution than the solution found using the baseline method.
4As an example, if F is a compact subset of linear predictors in Reproducing Kernel Hilbert Space (RKHS) and loss l(y, f(x)) is Lipschitz in f(x) (second argument), then Assumption 3 can be satisfied (Bartlett & Mendelson, 2002). Vast majority of linear predictors such as support vector machine and logistic regression can be defined in RKHS.

heading: 6.2 EXPERIMENT 2: LOGISTIC REGRESSION AND THE ADULT INCOME DATASET

text:
The adult income dataset is a public dataset containing the information of 48,842 individuals (Kohavi, 1996). Each data point includes 14 features including age, education, race, etc. Consider race (White or Black) as the sensitive attribute, we denote White demographic group byA = 0 and Black group by A = 1.
We first pre-process the dataset by removing the data points with a missing value or with the race other than Black and White and obtain 41,961 data points. Among these data points, 4585 belong to Black demographic group. For each data point, we convert all the categorical features to one-hot vectors and result in dx = 110 dimensional features. We then normalize the feature vectors such that they have zero mean value and unit variance. Our goal is to find a logistic regression model satisfying γ-EL to predict whether the income of an individual is above $50K or not.
We use Algorithm 2 and Algorithm 3 with = 0.01 to find the optimal logistic regression model under EL. We use the penalty method described in equation (11) as the baseline. Similar to Experiment 1, we set learning rate as 0.001 for solving (10) and (11). Penalty parameter t is set to be 0.5 and increases by 0.1 every 250 iterations. Figure 1c illustrates the loss of logistic regression model trained by Algorithm 2, Algorithm 3, and the baseline. It shows that Algorithm 2 outperforms the baseline; this is because that the baseline only finds a sub-optimal solution while Algorithm 2 finds the global optimal solution. As mentioned in Section 4, Algorithm 3 finds a sub-optimal solution that satisfies γ-EL, and its performance can vary from case to case. Even though Algorithm 3 has a good performance in Experiment 1, it does not outperform the baseline in Experiment 2. Figure 1d illustrates the distances from the optimal point w∗ to the sub-optimal solutions obtained by Algorithm 3 and the baseline penalty method. It shows that the distance fromw∗ to the solution obtained under Algorithm 3 is slightly larger than that fromw∗ to the solution obtained under the baseline.

heading: 7 CONCLUSION

text: In this work, we studied the problem of fair supervised learning under the Equalized Loss (EL) fairness notion which requires the prediction error/loss to be the same across different demographic groups. By imposing EL constraint, the learning problem can be formulated as a non-convex optimization problem. We introduce a number of algorithms that find the global optimal solution to this non-convex optimization problem. In particular, we showed that the optimal solution to such a non-convex problem can be found by solving a sequence of convex constrained optimizations. We also introduced a simple algorithm for finding a sub-optimal solution to the non-convex problem without solving constrained convex optimization problems. In addition to the theoretical guarantees, we demonstrated the performance of the proposed algorithm through numerical experiments.

heading: 8 REPRODUCIBILITY STATEMENT

text:
Regarding the theoretical results: This paper includes six Theorems. The proof of Theorem 1 and Theorem 2 have been provided in the main text. Due to the page limit, the proofs of the other theorems have been provided in the appendix.
Regarding the numerical examples: the first experiment does not use any dataset, and we study the performance of our proposed method on quadratic objective functions. The values for hyperparameters (including learning and penalty parameter) have been explicitly mentioned in section 6. In the second numerical example, we used the adult income dataset which is a well-known public dataset in our community. We explained the data pre-processing procedure in Section 6.2 in details.

heading: 9 ETHICS STATEMENT

text: In this work, we proposed algorithms to find fair predictors under the EL fairness notion. We want to emphasize that selecting a right fairness notion depends on the application and the authors do not make any suggestions to policy/law makers about choosing or avoiding this fairness notion.

heading: APPENDIX

heading: PROOFS

text:
In order to prove Theorem 3, we first introduce two lemmas.
Lemma 1 Under assumption 2, there exists w ∈ Rdw such that L0(w) = L1(w) = L(w) and λ (1) start ≤ L(w) ≤ λ (1) end.
Proof. Let h0(β) = L0((1 − β)wG0 + βwG1) and h1(β) = L1((1 − β)wG0 + βwG1), and h(β) = h0(β) − h1(β), β ∈ [0, 1]. Note that ∇wLa(wGa) = 0 because wGa is the minimizer of La(w). Moreover, ∇2wLa(w) is positive semi-definit because La(.) is a strictly convex function. First, we show that L0((1− β)wG0 + βwG1) is an increasing function in β, and L1((1− β)wG0 + βwG1) is a decreasing function in β. Note that h ′ 0(0) = (wG1 − wG0)T∇wL0(wG0) = 0, and h′′0(0) = (wG1 −wG0)T∇2wL0(wG0)(wG1 −wG0) ≥ 0. This implies that h′0(β) ≥ 0,∀β ∈ [0, 1]. Similarly, we can show that h′1(β) ≤ 0,∀β ∈ [0, 1]. Note that under Assumption (2), h(0) < 0 and h(1) > 0. Therefore, by the intermediate value theorem, the exists β ∈ (0, 1) such that h(β) = 0. Definew = (1− β)wG0 + βwG1 . We have,
h(β) = 0 =⇒ L0(w) = L1(w) = L(w) (12) wG0 is minimizer of L0 =⇒ L(w) = L0(w) ≥ λ (1) start (13)
h′0(β) ≥ 0,∀β ∈ [0, 1] =⇒ h0(1) ≥ h0(β) =⇒ λ (1) end ≥ L0(w) = L(w) (14)
Lemma 2 L0(w∗i ) = λ (i) mid, wherew ∗ i is the solution to (5).
Proof. We proceed by contradiction. Assume that L0(w∗i ) < λ (i) mid. SincewG1 is not in the feasible set of (5),∇wL1(w∗i ) 6= 0. This is a contradiction becausew∗i is an interior point of the feasible set of a convex optimization and cannot be optimal if∇wL1(w∗i ) is equal to zero.

heading: Proof [Theorem 3]

text:
Let Ii = [λ (i) start, λ (i) end] be a sequence of intervals. It is easy to see that I1 ⊇ I2 ⊇ · · · and λ (i) end−λ (i) start → 0 as i→∞. Therefore, by the Nested Interval Theorem, ∩∞i=1Ii consists of exactly one real number λ∗, and both λ(i)start and λ (i) end converge to λ ∗. Because λ(i)mid = λ (i) start+λ (i) start 2 , λ (i) mid also converges to λ∗.
Now, we show that L(w∗) ∈ Ii for all i. Note that L(w∗) = L0(w∗) ≥ λ(1)start because wG0 is the minimizer of L0. Moreover, λ (1) end ≥ L(w∗) otherwise L(w) < L(w∗) (w is defined in Lemma 1) andw∗ is not optimal solution under 0-EL. Therefore, L(w∗) ∈ I1. Now we proceed by induction. Suppose L(w∗) ∈ Ii. We show that L(w∗) ∈ Ii+1 as well. We consider two cases.
• L(w∗) ≤ λ(i)mid. In this case w∗ is a feasible point for (5), and λ(i) ≤ L(w∗) ≤ λ (i) mid.
Therefore, L(w∗) ∈ Ii+1.
• L(w∗) < λ(i)mid. In this case, we proceed by contradiction to show that λ (i) ≥ λ(i)mid.
Assume that λ(i) < λ(i)mid. Define g(β) = g0(β)−g1(β), where gi(β) = Li((1−β)wG0 + βw∗i ). Note that λ (i) = g1(1) By Lemma 2, g0(1) = λ (i) mid. Therefore, g(1) = λ (i) mid − λ(i) > 0. Moreover, under Assumption 2, g(0) < 0. Therefore, by the intermediate value theorem, there exists β ∈ (0, 1) such that g(β) = 0. Similar to the proof of Lemma 1, we can show that g0(β) in an increasing function for all β ∈ [0, 1]. As a result g0(β) <
g0(1) = λ (i) mid. Definew = (1− β)wG0 + βw∗i . We have,
g0(β) = L0(w) = L1(w) = L(w) < λ (i) mid (15)
L(w∗) < λ (i) mid (16)
The last two equations imply that w∗ is not an optimal fair solution under 0-EL fairness constraint. This is a contradiction. Therefore, if L(w∗) > λ(i)mid, then λ
(i) ≥ λ(i)mid. As a result, L(w∗) ∈ Ii+1
By two above cases and the nested interval theorem, we conclude that,
L(w∗) ∈ ∩∞i=1Ii, lim i→∞ λ (i) mid = L(w ∗)
For the second part of the theorem, consider the following,
w∗∞ = argmin w L1(w)s.t., L0(w) ≤ λ∞mid = L(w∗)
lim i→∞
w∗i = w ∗ ∞
In order to show that w∗∞ is equal to w ∗, we proceed by contradiction. Suppose w∗∞ 6= w∗. As a result, L1(w∗∞) < L(w ∗). Define η(β) = η0(β)− η1(β), where ηi(β) = Li((1− β)wG0 + βw∗∞). Note that L1(w∗∞) = η1(1). By Lemma 2, the condition in (5) is binding and η0(1) = L(w ∗). Therefore, η(1) = L(w∗) − L1(w∗∞) > 0. Moreover, under Assumption 2, η(0) < 0. Therefore, by the intermediate value theorem, there exists β ∈ (0, 1) such that η(β) = 0. Similar to the proof of Lemma 1, we can show that η0(β) is an increasing function for all β ∈ [0, 1]. As a result η0(β) < η0(1) = L(w ∗). Definew = (1− β)wG0 + βw∗∞. We have,
η0(β) = L0(w) = L1(w) = L(w) < L(w ∗) (17)
The last equation implies thatw∗ is not an optimal fair solution under 0-EL fairness constraint. This a contradiction. As a result,w∗∞ = ŵ.

heading: Proof [Theorem 4 ]

text:
Letw∗ be the optimal weight vector under γ-EL.
Step 1. we show that one of the following holds,
L0(w ∗)− L1(w∗) = γ (18) L0(w ∗)− L1(w∗) = −γ (19)
Proof by contradiction. Assume −γ < L0(w∗) − L1(w∗) < γ. This implies that w∗ is an interior point of the feasible set of optimization problem (3). Since w∗ 6= w∗O, then ∇L(w∗) 6= 0. As a result, object function of (3) can be improved at w∗ by moving toward −∇L(w∗). This a contradiction. Therefore, |L0(w∗)− L1(w∗)| = γ. Step 2. Function wγ = ELminimizer(wG0 ,wG0 , , γ) is the solution to the following optimization problem,
min w
Pr{A = 0}L0(w) + Pr{A = 1}L1(w), s.t., L0(w∗)− L1(w∗) = γ (20)
To show the above claim, notice that the solution to optimization problem (20) is the same as the following,
min w
Pr{A = 0}L0(w) + Pr{A = 1}L̃1(w), s.t., L0(w∗)− L̃1(w∗) = 0, (21)
where L̃1(w) = L1(w) + γ. Since L0(wG0) − L̃1(wG0) < 0 and L0(wG1) − L̃1(wG1) > 0, by Theorem 3, we know thatwγ = ELminimizer(wG0 ,wG0 , , γ) find the solution to (21).
Lastly, because |L0(w∗)− L1(w∗)| = γ, we have,
w∗ = { wγ if L(wγ) ≤ L(w−γ) w−γ o.w.
(22)
Thus, Algorithm 2 finds the solution to (3).

heading: Proof [Theorem 5]

text:
1. Under Assumption 2, g(1) < 0. Moreover, g(0) ≥ 0. Therefore, by the intermediate value theorem, there exists β0 ∈ [0, 1] such that g(β0) = 0. 2. Since wO is the minimizer of L(w), h′(0) = 0. Moreover, since L(w) is strictly convex, h′′(0) > 0. As a result, h′(β) > 0 for β > 0.
3. SincewGâ is the minimizer ofLâ(w), andLâ(w) is strictly convex, Lâ((1−β)wO+βwGâ) is strictly decreasing function. Note that since h(β) = Pr{A = â}Lâ((1− β)wO + βwGâ) +Pr{A = 1− â}L1−â((1− β)wO + βwGâ) is strictly increasing and Lâ((1 − β)wO + βwGâ) is strictly decreasing, we conclude that L1−â((1− β)wO + βwGâ) is strictly increasing. As a result, g should be strictly decreasing.
Proof [Theorem 6] First, we show that if gγ(0) ≤ 0, thenwO satisfies γ-EL.
gγ(0) ≤ 0 =⇒ g(β)− γ ≤ 0 =⇒ Lâ(wO)− L1−â(wO) ≤ γ
Moreover, Lâ(wO)−L1−â(wO) ≥ 0 because â = argmaxa La(wO). Therefore, γ-EL is satisfied. Secondly, assume that gγ(0) > 0. Under Assumption 1, gγ(1) = Lâ(wGâ)−L1−â(wGâ)− γ < 0. Therefore, by the intermediate value there exists β0 such that gγ(β0) = 0. Moreover, gγ is a strictly decreasing function. Therefore, the binary search proposed in Algorithm 3 converges to root of gγ(β). As a result, (1 − β(∞)mid)wO + β (∞) midwGâ satisfies satisfies γ-EL. Moreover, Lâ(wO) − L1−â(wO) ≥ 0 because â = argmaxa La(wO). Note that since g(β) is decreasing, β(∞)mid is the smallest possible β under which (1 − β)wO + βwGâ γ-EL. Since h is increasing, the smallest possible β gives us a better accuracy.

heading: Proof [Theorem 7]

text:
By the triangle inequality, the following holds,
sup fw∈F ||L0(w)−L1(w)| − |L̂0(w)− L̂1(w)|| ≤ sup fw∈F |L0(w)− L̂0(w)|+ sup fw∈F |L1(w)− L̂1(w)|. (23) Therefore, with probability at least 1− 2δ we have,
sup fw∈F
||L0(w)− L1(w)| − |L̂0(w)− L̂1(w)|| ≤ B(δ, n0,F) +B(δ, n1,F) (24)
As a result, with probability 1− 2δ holds,
{w|fw ∈ F , |L0(w)− L1(w)| ≤ γ} ⊆ {w|fw ∈ F , |L̂0(w)− L̂1(w)| ≤ γ̂} (25) Now consider the following,
L(ŵ)− L(w∗) = L(ŵ)− L̂(ŵ) + L̂(ŵ)− L̂(w∗) + L̂(w∗)− L(w∗) (26) By (25), L̂(ŵ)− L̂(w∗) ≤ 0 with probability 1−2δ. Thus, with probability at least 1−2δ, we have,
L(ŵ)− L(w∗) ≤ L(ŵ)− L̂(ŵ) + L̂(w∗)− L(w∗). (27) Therefore, under assumption 3, we can conclude with probability at least 1− 6δ, L(ŵ)− L(w∗) ≤ 2B(δ, n,F). In addition, by (24), with probability at least 1− 2δ, we have,
|L0(ŵ)− L1(ŵ)| ≤ B(δ, n0,F) +B(δ, n1,F) + |L̂0(w)− L̂1(w)| ≤ γ̂ +B(δ, n0,F) +B(δ, n1,F) = γ + 2B(δ, n0,F) + 2B(δ, n1,F)