# Optimal Learning in Fairness-Aware Contextual Bandits

DevFeed: [Optimal Learning in Fairness-Aware Contextual Bandits](<https://devfeed.tech/articles/optimal-learning-in-fairness-aware-contextual-bandits-114470.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.00979>)

Author: Gengyu Xue, Fan Wang, Feiyu Jiang, Zifeng Zhao, Yi Yu

Published: 2026-11-03T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Machine learning](<https://devfeed.tech/topics/machine-learning.md>), [responsible-ai](<https://devfeed.tech/topics/responsible-ai.md>), [Reinforcement learning](<https://devfeed.tech/topics/reinforcement-learning.md>), [decision-making](<https://devfeed.tech/topics/decision-making.md>), [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [bandits](<https://devfeed.tech/tags/bandits.md>), [boundary](<https://devfeed.tech/tags/boundary.md>), [canonical](<https://devfeed.tech/tags/canonical.md>), [confidence](<https://devfeed.tech/tags/confidence.md>), [constraint](<https://devfeed.tech/tags/constraint.md>), [context](<https://devfeed.tech/tags/context.md>), [contextual-bandits](<https://devfeed.tech/tags/contextual-bandits.md>), [continuous](<https://devfeed.tech/tags/continuous.md>), [cost](<https://devfeed.tech/tags/cost.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [data](<https://devfeed.tech/tags/data.md>), [decision-making](<https://devfeed.tech/tags/decision-making.md>), [design](<https://devfeed.tech/tags/design.md>), [dimension](<https://devfeed.tech/tags/dimension.md>), [distributions](<https://devfeed.tech/tags/distributions.md>), [diversity](<https://devfeed.tech/tags/diversity.md>), [experiments](<https://devfeed.tech/tags/experiments.md>), [fairness](<https://devfeed.tech/tags/fairness.md>), [greedy](<https://devfeed.tech/tags/greedy.md>), [learning](<https://devfeed.tech/tags/learning.md>), [math-st](<https://devfeed.tech/tags/math-st.md>), [stat-me](<https://devfeed.tech/tags/stat-me.md>), [stat-ml](<https://devfeed.tech/tags/stat-ml.md>), [stat-th](<https://devfeed.tech/tags/stat-th.md>)

## AI overview

The study finds that a global Lipschitz fairness constraint--requiring similar contexts to receive similar action distributions--creates a randomization region near the decision boundary and imposes a quantifiable population-level cost. It represents the optimal fair policy through a lower-dimensional boundary optimization. For continuous contexts, a lazy fair greedy algorithm uses finite-dimensional linear programs; for general, including discrete and mixed, context distributions, a lazy polyhedral UCB algorithm optimizes over confidence-set vertices using finitely many linear programs. Both enforce fairness at every round and achieve regret O(√T + T^((d−2)/(d−1))-1{d>=4}), up to polylogarithmic factors. A matching minimax lower bound for ℓ1-based fairness establishes optimality and shows that boundary-learning cost dominates parametric learning when d>=4. The abstract reports supporting experiments on synthetic and real data.

## Source excerpt

arXiv:2611.00979v1 Announce Type: cross 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(\sqrt{T} + T^{(d-2)/(d-1)}{\indc\{d\geq 4\}})$ up to poly-logarithmic factors, where $d$ is the dimension of the contexts. A matching minimax lower bound for $\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 \geq 4$. Experiments on synthetic and real data support our theoretical findings and demonstrate the practical effectiveness of our methods.