math.STOct 31, 2026

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

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 \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})O(\sqrt{T} + T^{(d-2)/(d-1)}{\indc\{d\geq 4\}}) up to poly-logarithmic factors, where dd is the dimension of the contexts. A matching minimax lower bound for ℓ1\ell_1-based fairness establishes optimality, and reveals an unavoidable nonparametric cost of learning the decision boundary, which dominates the parametric learning cost when d≥4d \geq 4. Experiments on synthetic and real data support our theoretical findings and demonstrate the practical effectiveness of our methods.

Explore similar work

CardsList
  1. Near-Optimal Regret for Oracle-Efficient Adversarial Contextual Bandits

    Nov 12, 2026Kiarash Banihashem, MohammadTaghi HajiaghayiContextual BanditsAdversarial Bandits

  2. Constrained Contextual Bandits with Adversarial Contexts

    May 7, 2026Dhruv Sarkar, Abhishek SinhaContextual BanditsAdversarial Bandits

  3. Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback

    May 31, 2026Wyame Benslimane, Tinghan Ye, Pascal Van Hentenryck +1Predict-Then-OptimizeDecision-Focused Learning