Optimal Learning in Fairness-Aware Contextual Bandits
Authors: Gengyu Xue, Fan Wang, Feiyu Jiang, Zifeng Zhao, Yi Yu
Organizations: Department of Statistics, University of Warwick · School of Mathematics and Statistics, University of Melbourne · School of Management, Fudan University · Mendoza College of Business, University of Notre Dame
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 \cite{dwork2012fairness}, 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(T+T(d−2)/(d−1)\indc{d≥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≥4. Experiments on synthetic and real data support our theoretical findings and demonstrate the practical effectiveness of our methods.
Algorithmic fairness studies how automated decisions distribute errors, opportunities, and harms across groups, and how to measure and reduce disparities.
Department of Industrial Engineering and Operations Research University of California, Berkeley · H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology