Optimal Learning in Fairness-Aware Contextual Bandits
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}) 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.
Related
- Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits
- Online Autotuning of Algebraic Multigrid via Contextual Bandits and Reinforcement Learning
- Set Membership Estimation for Stochastic Linear Contextual Bandits
- Diversified Multinomial Logit Contextual Bandits
- Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts
BibTeX
@misc{xue2026optimal,
title = {{Optimal Learning in Fairness-Aware Contextual Bandits}},
author = {Gengyu Xue and Fan Wang and Feiyu Jiang and Zifeng Zhao and Yi Yu},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00979},
eprint = {2611.00979},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00979},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Learning in Fairness-Aware Contextual Bandits
AU - Gengyu Xue
AU - Fan Wang
AU - Feiyu Jiang
AU - Zifeng Zhao
AU - Yi Yu
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00979
UR - https://arxiv.org/abs/2611.00979
AB - 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.
ER -