Online Learning with an Unknown Fairness Metric

Abstract

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.

References in corpus (4)

• Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness
• On the (im)possibility of fairness
• Fairness Through Computationally-Bounded Awareness
• Probably Approximately Metric-Fair Learning

Cited by in corpus (28)

• Fairness in Machine Learning: A Survey
• Aligning AI With Shared Human Values
• Operationalizing Individual Fairness with Pairwise Fair Representations
• Probably Approximately Metric-Fair Learning
• A Survey on Intersectional Fairness in Machine Learning: Notions, Mitigation, and Challenges
• A Design Framework for operationalizing Trustworthy Artificial Intelligence in Healthcare: Requirements, Tradeoffs and Challenges for its Clinical Adoption
• What-is and How-to for Fairness in Machine Learning: A Survey, Reflection, and Perspective
• Average Individual Fairness: Algorithms, Generalization and Experiments
• Two Simple Ways to Learn Individual Fairness Metrics from Data
• Achieving Fairness in the Stochastic Multi-armed Bandit Problem
• Fair Algorithms for Multi-Agent Multi-Armed Bandits
• SenSeI: Sensitive Set Invariance for Enforcing Individual Fairness
• A Notion of Individual Fairness for Clustering
• Sample Complexity of Uniform Convergence for Multicalibration
• Fairness of Exposure in Stochastic Bandits
• Fair Exploration via Axiomatic Bargaining
• Fair Decisions Despite Imperfect Predictions
• Beyond "Fairness:" Structural (In)justice Lenses on AI for Education
• Bandit Algorithms for Precision Medicine
• Metric-Free Individual Fairness in Online Learning
• Preference-Informed Fairness
• Bandit Learning with Delayed Impact of Actions
• Optimal Contextual Pricing and Extensions
• Individual Fairness Revisited: Transferring Techniques from Adversarial Robustness
• Diversity-Preserving K-Armed Bandits, Revisited
• Providing a Philosophical Critique and Guidance of Fairness Metrics
• Individually Fair Gradient Boosting
• Individual Fairness in Hindsight