Online Learning with an Unknown Fairness Metric

By Stephen Gillen, Christopher Jung, Michael Kearns, Aaron Roth. 2018

152 citations recorded by the source corpus.

We consider the problem of online learning in the linear contextual bandits setting, but in which there are also strong individual fairness constraints governed by an unknown similarity metric. These constraints demand that we select similar actions or individuals with approximately equal probability (arXiv:1104.3913), which may be at odds with optimizing reward, thus modeling settings where profit and social policy are in tension. We assume we learn about an unknown Mahalanobis similarity metric from only weak feedback that identifies fairness violations, but does not quantify their extent. This is intended to represent the interventions of a regulator who "knows unfairness when he sees it" but nevertheless cannot enunciate a quantitative fairness metric over individuals. Our main result is an algorithm in the adversarial context setting that has a number of fairness violations that depends only logarithmically on $T$, while obtaining an optimal $O(\sqrt{T})$ regret bound to the best fair policy.

Subfields: Artificial Intelligence, Safety Research

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 Safety Research

Citations in the corpus

Fairness Through Computationally-Bounded Awareness (2018, background): “[10] study metric-based individually fair online decision-making in the presence of an unknown fairness metric.”
The Frontiers of Fairness in Machine Learning (2018, background): “Similarly, [GJKR18] assumes the existence of an oracle which can identify fairness violations when they are made in an online setting, but cannot quantify the extent of the violation (with respect to the unknown metric).”
Individual Fairness in Hindsight (2018, background): “Liu et al. (2017) and Gillen et al. (2018) study the model of Joseph et al. (2016b) under different notions of individual fairness.”
On preserving non-discrimination when combining expert advice (2018, background): “[13], a line of work aims to treat similar people similarly in online settings [33, 18].”
Fairness in Machine Learning: A Survey (2020, background): “The application of bandits to ML fairness [93, 146, 147, 189, 108] is nascent.”
Are My Deep Learning Systems Fair? An Empirical Study of Fixed-Seed Training (2021, background): “Bias metrics: Many metrics [6, 15, 19, 24, 26, 31, 35, 44, 46, 67, 82, 102, 103] have been proposed to measure biases of ML systems.”
Individual Fairness in Pipelines (2020, background): “There is a wide variety of work concerning fairness in machine learning [9, 14, 25, 17, 3, 18, 26, 22, 10, 16, 15, 11, 12, 20, 19, 4, 24, 5].”
Fairness Under Composition (2018, background): “Two subsequent works in this general vein explore approximating individual fairness with the help of an oracle that knows the task-specific metric [15, 7].”
Eliciting and Enforcing Subjective Individual Fairness (2019, methodology): “…were taken as constraints on error minimization with respect to the actual recidivism outcomes over the entire COMPAS dataset, and our algorithm was applied to solve this constrained optimization problem, using a linear threhsold heuristic as the underlying learning oracle (Kearns et al. [2018]).”
Average Individual Fairness: Algorithms, Generalization and Experiments (2019, background): “Gillen et al. (2018) study a contextual bandit learning setting in which a human judge points out metric fairness violations whenever they occur, and show that with this kind of feedback (under assumptions about consistency with a family of metrics), it is possible to quickly converge to the…”
Fairness in Machine Learning (2020, methodology): “…problem via the method of Lagrange multipliers [3, 15, 34, 37, 38, 59, 97, 135, 183, 185] or add penalties to the objective [5, 14, 22, 44, 46, 56, 58, 62, 73, 74, 75, 79, 82, 87, 88, 89, 93, 94, 95, 98, 104, 115, 119, 123, 133, 134, 135, 138, 139, 154, 165, 176, 179, 180, 182], others use…”
Fair Decisions Despite Imperfect Predictions (2019, methodology): “We build on previous work on counterfactual inference and policy learning (Athey & Wager, 2017; Ensign et al., 2018; Gillen et al., 2018; Heidari & Krause, 2018; Joseph et al., 2016; Jung et al., 2018; Kallus, 2018; Kallus & Zhou, 2018; Lakkaraju & Rudin, 2017).”