# Online Learning with an Unknown Fairness Metric

arXiv: https://arxiv.org/abs/1802.06936 · HTML: https://mlsanity.com/paper/1802.06936/

## Key facts

- Cited by 62 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2018.

## Built on by (most cited first, 30 of 62)

- [Aligning AI With Shared Human Values](https://mlsanity.com/paper/2008.02275/) (2020)
- [Bias Mitigation for Machine Learning Classifiers: A Comprehensive Survey](https://mlsanity.com/paper/2207.07068/) (2022)
- [Fair and Optimal Classification via Post-Processing](https://mlsanity.com/paper/2211.01528/) (2022)
- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [A Survey on Intersectional Fairness in Machine Learning: Notions, Mitigation, and Challenges](https://mlsanity.com/paper/2305.06969/) (2023)
- [Representation Bias in Data: A Survey on Identification and Resolution Techniques](https://mlsanity.com/paper/2203.11852/) (2022)
- [Evaluating Fairness of Machine Learning Models Under Uncertain and Incomplete Information](https://mlsanity.com/paper/2102.08410/) (2021)
- [Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration](https://mlsanity.com/paper/2302.06726/) (2023)
- [Simple and near-optimal algorithms for hidden stratification and multi-group learning](https://mlsanity.com/paper/2112.12181/) (2021)
- [A Sociotechnical View of Algorithmic Fairness](https://mlsanity.com/paper/2110.09253/) (2021)
- [Fair Exploration via Axiomatic Bargaining](https://mlsanity.com/paper/2106.02553/) (2021)
- [Fairness-Aware Online Meta-learning](https://mlsanity.com/paper/2108.09435/) (2021)
- [What-is and How-to for Fairness in Machine Learning: A Survey, Reflection, and Perspective](https://mlsanity.com/paper/2206.04101/) (2022)
- [Survey on Fair Reinforcement Learning: Theory and Practice](https://mlsanity.com/paper/2205.10032/) (2022)
- [Individually Fair Gradient Boosting](https://mlsanity.com/paper/2103.16785/) (2021)
- [Beyond "Fairness:" Structural (In)justice Lenses on AI for Education](https://mlsanity.com/paper/2105.08847/) (2021)
- [Bandit Algorithms for Precision Medicine](https://mlsanity.com/paper/2108.04782/) (2021)
- [Fairness with Continuous Optimal Transport](https://mlsanity.com/paper/2101.02084/) (2021)
- [Uncertainty Quantification for Fairness in Two-Stage Recommender Systems](https://mlsanity.com/paper/2205.15436/) (2022)
- [An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret](https://mlsanity.com/paper/2209.11817/) (2022)
- [Fairness in Reinforcement Learning: A Survey](https://mlsanity.com/paper/2405.06909/) (2024)
- [Multi-disciplinary fairness considerations in machine learning for clinical trials](https://mlsanity.com/paper/2205.08875/) (2022)
- [Individual Preference Stability for Clustering](https://mlsanity.com/paper/2207.03600/) (2022)
- [No-Regret Learning for Fair Multi-Agent Social Welfare Optimization](https://mlsanity.com/paper/2405.20678/) (2024)
- [Fairness Maximization among Offline Agents in Online-Matching Markets](https://mlsanity.com/paper/2109.08934/) (2021)
- [BanditQ: Fair Bandits with Guaranteed Rewards](https://mlsanity.com/paper/2304.05219/) (2023)
- [Precarity: Modeling the Long Term Effects of Compounded Decisions on Individual Instability](https://mlsanity.com/paper/2104.12037/) (2021)
- [Fairer LP-based Online Allocation via Analytic Center](https://mlsanity.com/paper/2110.14621/) (2021)
- [Individually Fair Learning with One-Sided Feedback](https://mlsanity.com/paper/2206.04475/) (2022)
- [Human-Guided Fair Classification for Natural Language Processing](https://mlsanity.com/paper/2212.10154/) (2022)

## Abstract (arXiv)

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(√T) regret bound to the best fair policy.