Fairness in Learning: Classic and Contextual Bandits

Abstract

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

A condensed version of this work appears in the 30th Annual Conference on Neural Information Processing Systems (NIPS), 2016

References in corpus (1)

• Certifying and removing disparate impact

Cited by in corpus (38)

• Fairness Testing: Testing Software for Discrimination
• Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness
• Explaining Models: An Empirical Study of How Explanations Impact Fairness Judgment
• Towards Long-term Fairness in Recommendation
• A Unified Approach to Quantifying Algorithmic Unfairness: Measuring Individual & Group Unfairness via Inequality Indices
• Clustering without Over-Representation
• Online Learning with an Unknown Fairness Metric
• FlipTest: Fairness Testing via Optimal Transport
• How Do Fairness Definitions Fare? Examining Public Attitudes Towards Algorithmic Definitions of Fairness
• Probably Approximately Metric-Fair Learning
• Out of Context: Investigating the Bias and Fairness Concerns of "Artificial Intelligence as a Service"
• Bias Discovery in Machine Learning Models for Mental Health
• Average Individual Fairness: Algorithms, Generalization and Experiments
• Training Fair Models in Federated Learning without Data Privacy Infringement
• Adversarial training approach for local data debiasing
• An Algorithmic Framework to Control Bias in Bandit-based Personalization
• How Do Fair Decisions Fare in Long-term Qualification?
• Two-stage Algorithm for Fairness-aware Machine Learning
• Measuring justice in machine learning
• A Notion of Individual Fairness for Clustering
• On Ensuring that Intelligent Machines Are Well-Behaved
• Using Adaptive Bandit Experiments to Increase and Investigate Engagement in Mental Health
• Fair Exploration via Axiomatic Bargaining
• Sample Complexity of Uniform Convergence for Multicalibration
• Fairness in Reinforcement Learning
• Getting too personal(ized): The importance of feature choice in online adaptive algorithms
• Metric-Free Individual Fairness in Online Learning
• Bandit Algorithms for Precision Medicine
• Fair Sequential Selection Using Supervised Learning Models
• A Smoothed Analysis of the Greedy Algorithm for the Linear Contextual Bandit Problem
• Improving Fairness in Adaptive Social Exergames via Shapley Bandits
• Debiasing representations by removing unwanted variation due to protected attributes
• Fair Algorithms for Learning in Allocation Problems
• Fair Clustering Through Fairlets
• Fairness-aware Online Price Discrimination with Nonparametric Demand Models
• Bandit based centralized matching in two-sided markets for peer to peer lending
• Access to Population-Level Signaling as a Source of Inequality
• GrowSpace: Learning How to Shape Plants