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

Nov 12, 2026

Near-Optimal Regret for Oracle-Efficient Adversarial Contextual Bandits

We study contextual bandits with KK actions, a class of NN policies, and i.i.d.\ contexts from a distribution that the learner can sample. For any sequence of loss functions fixed before play, we give an oracle-efficient algorithm with expected regret O(KTlog⁡(2N) log⁡(2KT))O(\sqrt{KT\log(2N)}\,\log(2KT)) against the best policy in hindsight on the realized contexts. This improves the T2/3T^{2/3} dependence on the horizon in prior oracle-efficient bounds and achieves the optimal regret rate in this setting up to logarithmic factors. Our algorithm perturbs policy scores using a Poisson sample of auxiliary contexts. At each sampled context, the perturbation assigned to an action is a Laplace noise draw multiplied by a scale specific to that context and action. We show that choosing these scales to minimize a convex objective determined by past observations yields the stated regret bound. We further approximate the minimizing scales by projected stochastic gradient descent using only an exact offline cost-sensitive optimization oracle that returns the optimum value. Since the table of scales can be large, the algorithm represents the SGD iterates implicitly by storing the random draws that determine each update and evaluates the scales only at queried contexts. Both the oracle complexity and the remaining resource bounds are polynomial in TT, KK, and log⁡(2N)\log(2N).
May 7, 2026

Constrained Contextual Bandits with Adversarial Contexts

We study constrained contextual bandits with adversarial contexts, where each action yields a random reward and incurs a random cost. The conditional mean reward and cost belong to known function classes and are learned through online regression oracles. The benchmark is a stationary randomized policy whose expected cost is non-positive at every observed context. We extend the seminal SquareCB\mathsf{SquareCB} algorithm of Foster and Rakhlin (2020), which reduces the contextual bandits to a regression problem, to the constrained setting. A surrogate reward function is constructed which penalizes the positive part of the expected cost of an action distribution, and an auxiliary variable accumulates its predicted value. Then we use an exponential Lyapunov function to control both regret and cumulative constraint violation via a single inequality. If the cumulative squared prediction error is at most UTU_T, our algorithm achieves O(KTUT)O(\sqrt{KTU_T}) regret and O(KTUTlog⁡T)O(\sqrt{KTU_T}\log T) cumulative expected cost, with high probability, improving upon the previous O(T3/4)O(T^{3/4}) type bounds obtained in stochastic contextual settings with an unknown context distribution. Our results require neither additional margin conditions nor probabilistic assumptions on the context sequence.
May 31, 2026

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

Decision-focused learning (DFL) trains predictive models by optimizing downstream decision quality rather than standalone prediction accuracy. For contextual linear optimization, most existing DFL methods assume offline data and full observations of the objective cost vector. We develop an on-policy learning method for sequential contextual linear optimization under partial feedback, generalizing the standard bandit feedback setting. Our method learns a stochastic predict-then-optimize policy that samples a cost-vector prediction from a conditional distribution and solves the resulting downstream linear optimization problem. To update this distributional model, we introduce a two-component hybrid gradient estimator. The first component is a score function estimator, which provides an unbiased but potentially high-variance policy gradient estimate. The second is a decision-focused plug-in component that uses an auxiliary nuisance estimate of the latent cost vector to exploit the downstream optimization structure, becoming more informative as the estimate improves. We prove an O(T^-1/2) bound on the average squared policy-gradient norm, matching the standard non-convex SGD rate. Experiments on top-k selection, shortest path, combinatorial pricing, and a real-data energy-scheduling benchmark show that, under bandit feedback, the hybrid gradient approach achieves lower mean cumulative regret than the contextual-bandit baselines on all four benchmarks and than linear Thompson sampling on three, and that it also works with richer conditional generative cost models. Code is available at https://github.com/Joeyetinghan/on-policy-bandit-dfl.