Optimal Learning in Fairness-Aware Contextual Bandits
math.ST, cs.LG, stat.ME, stat.ML, stat.TH
Submitted: 2026-10-31
Updated: 2026-10-31
Code: https://github.com/chrisfanwang/fair-contextual-bandits
License: http://creativecommons.org/licenses/by/4.0/
The gist: Mitigating unfair disparities in sequential decision-making is a growing concern in machine learning.
Terminology
Abstract
Mitigating unfair disparities in sequential decision-making is a growing concern in machine learning. We study contextual bandits under a global covariate-based Lipschitz fairness constraint, pioneered by, requiring individuals with similar contexts to receive similar action distributions. We show that this constraint induces a randomisation region near the decision boundary and explicitly quantify the population level cost of fairness. We further establish a canonical representation of the optimal fair policy, which reduces the fair policy design to a lower-dimensional boundary optimisation problem. We develop a lazy fair greedy algorithm that exploits fairness-induced covariate diversity under continuous contexts, with policy updates computed via finite-dimensional linear programming. For general context distributions, including discrete and mixed contexts, we propose a lazy polyhedral upper confidence bound (UCB) algorithm, whose optimistic optimisation reduces to finitely many linear programs over confidence-set vertices. Both methods satisfy fairness at every round and achieve regret of order O(sqrt T + T(d-2)/(d-1) d at least 4) up to poly-logarithmic factors, where d is the dimension of the contexts. A matching minimax lower bound for 1-based fairness establishes optimality, and reveals an unavoidable nonparametric cost of learning the decision boundary, which dominates the parametric learning cost when d at least 4. Experiments on synthetic and real data support our theoretical findings and demonstrate the practical effectiveness of our methods.
Sources
- Collaborative Min-Max Regret in Grouped Multi-Armed Bandits
- $\alpha$-Fair Contextual Bandits
- Fairer LP-based Online Allocation via Analytic Center
- Finite-Sample and Distribution-Free Fair Classification: Optimal Trade-off Between Excess Risk and Fairness, and the Cost of Group-Blindness
- Calibrated Fairness in Bandits
Related papers
- Sigmoid-FTRL: Design-Based Adaptive Neyman Allocation for AIPW Estimators
- Nonparametric Regression on Fixed-Cardinality Subsets:Minimax Risk and Random-Design Effects
- Conformal Prediction for Dyadic Regression Under Complex Missingness
- Optimal Linear Functional Estimation for Proportionally High-Dimensional Linear Models
- Semiparametric Efficient Inference under Non-Informative Complex Survey Designs
- Sharp Asymptotic Theory of Maximum Likelihood Estimation for Gaussian Processes with an RBF Kernel