# A Unified Approach to Fair Online Learning via Blackwell Approachability

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 28 references that are in the map.
- First posted on arXiv 23 Jun 2021.

## Builds on (most cited first, 10 of 10)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [On Fairness and Calibration](https://mlsanity.com/paper/1709.02012/) (2017)
- [Minimax Pareto Fairness: A Multi Objective Perspective](https://mlsanity.com/paper/2011.01821/) (2020)
- [On Formalizing Fairness in Prediction with Machine Learning](https://mlsanity.com/paper/1710.03184/) (2017)
- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [Equal Opportunity in Online Classification with Partial Feedback](https://mlsanity.com/paper/1902.02242/) (2019)
- [Approachability, Regret and Calibration; implications and equivalences](https://mlsanity.com/paper/1301.2663/) (2013)
- [On preserving non-discrimination when combining expert advice](https://mlsanity.com/paper/1810.11829/) (2018)
- [A Primal Condition for Approachability with Partial Monitoring](https://mlsanity.com/paper/1305.5399/) (2013)

## Built on by (most cited first, 12 of 12)

- [Pseudonorm Approachability and Applications to Regret Minimization](https://mlsanity.com/paper/2302.01517/) (2023)
- [Solving optimization problems with Blackwell approachability](https://mlsanity.com/paper/2202.12277/) (2022)
- [Group-blind optimal transport to group parity and its constrained variants](https://mlsanity.com/paper/2310.11407/) (2023)
- [Rate-Preserving Reductions for Blackwell Approachability](https://mlsanity.com/paper/2406.07585/) (2024)
- [Computing Optimal Regularizers for Online Linear Optimization](https://mlsanity.com/paper/2410.17336/) (2024)
- [The price of unfairness in linear bandits with biased feedback](https://mlsanity.com/paper/2203.09784/) (2022)
- [Fairness in Streaming Submodular Maximization over a Matroid Constraint](https://mlsanity.com/paper/2305.15118/) (2023)
- [Small Total-Cost Constraints in Contextual Bandits with Knapsacks, with Application to Fairness](https://mlsanity.com/paper/2305.15807/) (2023)
- [Achieving Optimal Static and Dynamic Regret Simultaneously in Bandits with Deterministic Losses](https://mlsanity.com/paper/2602.07418/) (2026)
- [Time-Dependent Blackwell Approachability and Application to Absorbing Games](https://mlsanity.com/paper/2303.04956/) (2023)
- [Efficient Opportunistic Approachability](https://mlsanity.com/paper/2602.21328/) (2026)
- [The Theorems of Dr. David Blackwell and Their Contributions to Artificial Intelligence](https://mlsanity.com/paper/2604.06621/) (2026)

## Abstract (arXiv)

We provide a setting and a general approach to fair online learning with stochastic sensitive and non-sensitive contexts. The setting is a repeated game between the Player and Nature, where at each stage both pick actions based on the contexts. Inspired by the notion of unawareness, we assume that the Player can only access the non-sensitive context before making a decision, while we discuss both cases of Nature accessing the sensitive contexts and Nature unaware of the sensitive contexts. Adapting Blackwell's approachability theory to handle the case of an unknown contexts' distribution, we provide a general necessary and sufficient condition for learning objectives to be compatible with some fairness constraints. This condition is instantiated on (group-wise) no-regret and (group-wise) calibration objectives, and on demographic parity as an additional constraint. When the objective is not compatible with the constraint, the provided framework permits to characterise the optimal trade-off between the two.