Fairness in Learning: Classic and Contextual Bandits

By Matthew Joseph, Michael Kearns, Jamie H. Morgenstern, Aaron Roth. 2016

514 citations recorded by the source corpus.

We introduce the study of fairness in multi-armed bandit problems. Our fairness definition can be interpreted as demanding that given a pool of applicants (say, for college admission or mortgages), a worse applicant is never favored over a better one, despite a learning algorithm's uncertainty over the true payoffs. We prove results of two types. First, in the important special case of the classic stochastic bandits problem (i.e., in which there are no contexts), we provide a provably fair algorithm based on "chained" confidence intervals, and provide a cumulative regret bound with a cubic dependence on the number of arms. We further show that any fair algorithm must have such a dependence. When combined with regret bounds for standard non-fair algorithms such as UCB, this proves a strong separation between fair and unfair learning, which extends to the general contextual case. In the general contextual case, we prove a tight connection between fairness and the KWIK (Knows What It Knows) learning model: a KWIK algorithm for a class of functions can be transformed into a provably fair contextual bandit algorithm, and conversely any fair contextual bandit algorithm can be transformed into a KWIK learning algorithm. This tight connection allows us to provide a provably fair algorithm for the linear contextual bandit problem with a polynomial dependence on the dimension, and to show (for a different class of functions) a worst-case exponential gap in regret between fair and non-fair learning algorithms

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning, Safety, Robustness & Interpretability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

In Safety, Robustness & Interpretability

Citations in the corpus

Measurement and Fairness (2019, background): “earning|within the literature of solutions, not problems|designed with purpose of achieving fairness in settings such as as hiring, college admissions, and lending. In one line of work, Joseph et al. [36, 35] focus on the setting where individuals are selected based on their quality. Here, the goal ”
Inherent Trade-Offs in the Fair Determination of Risk Scores (2016, methodology): “consider how fairness issues can arise during the process of learning, modeling this using a multi-armed bandit framework [20].”
Beyond Individual and Group Fairness (2020, background): “…2018], online learning and multi-armed bandit problems [Liu et al., 2017, Joseph et al., 2018], in particular stochastic and contextual bandits [Joseph et al., 2016, Gillen et al., 2018, Gupta and Kamble, 2019] and reinforcement learning [Jabbari et al., 2017, Doroudi et al., 2017, Wen et al.,…”
Prediction-Based Decisions and Fairness: A Catalogue of Choices, Assumptions, and Definitions (2018, methodology): “The notion of “quality” in the contextual bandit setup [89, 88] is analogous to “true risk” in the rest of our”
A Unified Approach to Quantifying Algorithmic Unfairness: Measuring Individual &Group Unfairness via Inequality Indices (2018, background): “3220046 learning mechanisms for fair decision making by imposing additional constraints or conditions [12, 13, 17, 18, 40, 41].”
Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness (2017, methodology): “We note that the individual fairness definition of Joseph et al. [2016] (when restricted to the binary classification setting) can be viewed as asking for equalized false positive rates across the singleton subgroups, containing just one individual each1 — but naturally, in order to achieve this str”
Aequitas: A Bias and Fairness Audit Toolkit (2018, background): “Kleinberg et al. (2016), Joseph et al. (2016) and Chouldechova (2017) discuss the relationship between model calibration, prevalence 1 , false negative and false positive rates in risk assessment tasks.”
How Do Fairness Definitions Fare?: Examining Public Attitudes Towards Algorithmic Definitions of Fairness (2018, methodology): “Joseph et al. (2016) apply this definition of fairness to the setting of contextual bandits, a classical sequential decision-making process, by utilizing the expected reward to determine the quality of an action (an arm as in the bandit setting).”
The Price of Fair PCA: One Extra Dimension (2018, background): “Much of the other work on fairness for learning algorithms focuses on fairness in classiﬁcation or scoring [Dwork et al., 2012; Hardt et al., 2016; Kleinberg et al., 2016; Chouldechova, 2017], or online learning settings [Joseph et al., 2016; Kannan et al., 2017; Ensign et al., 2017b,a].”
The Frontiers of Fairness in Machine Learning (2018, background): “[JKMR16] suggest a deﬁnition which roughly corresponds to “less qualiﬁed individuals should not be favored over more qualiﬁed individuals”, where quality is deﬁned with respect to the true underlying label (unknown to the algorithm).”
FairGAN: Fairness-aware Generative Adversarial Networks (2018, background): “Currently, many organizations or institutes adopt machine learning models trained on historical data to automatically make decisions, including hiring, lending and policing [1].”
Delayed Impact of Fair Machine Learning (2018, background): “A growing literature on fairness in the “bandits” setting of learning [see Joseph et al., 2016, et sequelae ] deals with online decision making that ought not to be confused with our one-step feedback setting.”
On Fairness and Calibration (2017, background): “Fairness has also been considered in online learning [21, 24], unsupervised learning [5], and causal inference [25, 27].”
A Convex Framework for Fair Regression (2017, background): “This suggests that the academic discussion about whether to allow disparate treatment (as explicitly allowed in e.g. [9, 17]) – i.e. whether sensitive attributes such as race and gender should be “forbidden” vs. used in building more accurate models for each subpopulation, is perhaps less…”
Algorithmic Decision Making and the Cost of Fairness (2017, background): “disparities of this kind, several authors recently have proposed a variety of fair decision algorithms [16, 21, 23, 24, 26].”
Learning Fair Rule Lists (2019, background): “…to estimate the effects of sensitive attributes and build algorithms that ensure a tolerable level of discrimination with respect to these attributes, individual notions of fairness [21, 29], which require the same decisions for individuals that are similar, and statistical notions of fairness .”
From Parity to Preference-based Notions of Fairness in Classification (2017, background): “A flurry of recent research on fair learning has focused on defining appropriate notions of fairness and then designing mechanisms to ensure fairness in automated decision making [12, 14, 18, 19, 20, 21, 28, 32, 33, 34].”
On the (im)possibility of fairness (2016, methodology): “[12] also contributes a new fairness definition, akin to those introduced in this paper and by Dwork et al.”