CS Paper Radar

Optimal Learning in Fairness-Aware Contextual Bandits

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

cs.LG math.STstat.MEstat.ML ·submitted 2026-10-31 14:22 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairness

cs.LG ·2026-10-01 ·Junhyuk Huh, Seoungbin Bae, Dabeen Lee
similarity 0.72
Abstract

We study causal logistic bandits with counterfactual fairness constraints. The causal structure is given through known factual and counterfactual feature maps that share an unknown logistic reward parameter, but the learner observes only factual rewards. Consequently, the directions determining counterfactual feasibility need not be identifiable from the available feedback. The closest prior analyses either omit a coverage condition or impose a comparatively strong one, and do not establish matching lower bounds. We first show that some coverage condition is necessary: without a coverage-type restriction, factually indistinguishable environments with different optimal fair actions force $Ω(T)$ expected joint loss. Under a weaker full-rank condition on the factual covariance pooled across actions, we identify a target-specific information scale $V_\star$ that measures the difficulty of estimating rewards and counterfactual effects from factual feedback. We construct worst-case families satisfying this condition on which every policy incurs expected joint loss $Ω\left(\left[V_\star\min\{\log K,d\}\right]^{1/3}T^{2/3}\right)$. We also give an explore--then--exploit procedure tuned using $V_\star$ and an adaptive algorithm that does not require its value. Both algorithms achieve $\max\{R_T,V_T\}=\widetilde{O}\left(\left[V_\star\min\{\log K,d\}\right]^{1/3}T^{2/3}+κd/σ_0^2\right)$, where $R_T$ is regret relative to the best fair action and $V_T$ denotes the cumulative stage-wise positive violations. Thus the upper and lower bounds match in their leading dependence on $T$, $V_\star$, and $\min\{\log K,d\}$, up to logarithmic factors.

0.20

Safety by Design: Realized-Cost Constraints for Contextual Bandits with Continuous Actions

cs.LG ·2026-08-27 ·Spyros Dragazis, Aldo Pacchiano
theory similarity 0.72
Abstract

Contextual bandits are a standard framework for sequential decision-making under uncertainty, with applications in clinical trials, dosage selection, recommendation systems, and autonomous systems. Safety is central in many of these applications, since a single unsafe decision in settings such as dosage selection or autonomous driving can have catastrophic consequences. A common way to model safety in bandit problems is to associate each action with both a reward signal and a cost signal, and to optimize reward subject to constraints on cost. Most existing safety-constrained bandit models enforce safety by requiring the expected cost of each action to remain below a prescribed threshold. However, this may be insufficient in heteroscedastic settings, where the chosen action affects not only the expected reward and cost, but also the variability of the observed outcomes. We study contextual bandits with one-dimensional continuous actions and stage-wise high-probability constraints on the realized cost. We propose High-Probability Constrained UCB, an optimistic-pessimistic algorithm that explores for reward while conservatively estimating the safe action set. For linear reward and cost models, we prove a tight $\tilde{\mathcal{O}}(d\sqrt{T})$ regret bound, and we extend the analysis to general function classes using the eluder dimension. Experiments show that enforcing realized-cost safety substantially reduces violations compared with expected-cost constrained baselines.

0.08

Conservative Dueling Bandits: Preference Learning under Baseline Constraints

cs.LG cs.AIstat.ML ·2026-10-27 ·Rohan Deb, Mohammad Ghavamzadeh, Arindam Banerjee
similarity 0.71
Abstract

Contextual dueling bandits learn from pairwise comparisons, the same feedback used to fine-tune language models from human preferences. Standard algorithms explore aggressively and can show users two poor options. We study conservative contextual dueling bandits, which require that, at every round, the cumulative score of the better displayed item stay above a $(1-α)$ fraction of a trusted baseline's. An item's score is its probability of beating the best available item, so the constraint depends only on utility differences and needs no absolute rewards. This also changes how safety can be certified: we show that transferring the safety test of the conservative bandit algorithm CLUCB unchanged can incur linear regret, even when the baseline's utilities are known exactly. For linear utilities, we develop MaxInP-BC, which certifies scores through utility gaps and, when it must fall back, pairs the baseline with an informative partner so that fallback rounds still drive learning. It is safe with high probability at all times, with regret $\tilde{O}(d\sqrt{T}/κ)$ plus an additive cost of conservatism that does not grow with the horizon. For general utility classes, we develop BTIGW-BC, which turns the guarantee of an online logistic-regression oracle into cumulative safety certificates. It is safe at all times, makes finitely many fallbacks, and has sublinear regret whenever the oracle's logistic regret is sublinear. In experiments, both satisfy the constraint, which their unconstrained counterparts often violate, at a moderate cost in regret.

0.13

Action-Centered Causal Bandits for Budget-Constrained Promotion Targeting

cs.LG ·2026-11-06 ·Yifan Lin, Kaixu Yang, Di Mo
publishedbenchmarktheory similarity 0.71
Abstract · Accepted at the 20th ACM International Conference on Web Search and Data Mining (WSDM 2027)

Web platforms select among costly interventions for each user to maximize incremental outcomes under a global budget. We formulate this problem as a budget-constrained contextual bandit with heterogeneous treatment effects. Although an action-independent outcome baseline cancels from treatment comparisons, modeling a nonlinear baseline can increase statistical complexity. We propose DR-CATE-CBwK, an action-centered causal bandit that directly learns treatment contrasts. Its online update remains valid under baseline-model misspecification without inverse-propensity weighting. It combines an offline doubly robust learner to warm-start treatment-effect estimates, an online action-centered estimator for sequential contrast learning, and a primal-dual controller with an affordable-action rule to enforce the effective-cost budget pathwise. For linear conditional average treatment effects (CATEs) in a stationary i.i.d. setting, we prove a high-probability (\widetilde{O}(Kd\sqrt{T})) regret bound, where K is the number of priced actions, d the context dimension, and T the horizon. We benchmark against the fluid linear program (LP) under the coverage-guaranteed action rule. We further show that the action-centered estimating moment remains unbiased under any predictable baseline estimate, whereas a specified separate-arm reward regression can exhibit asymptotic contrast bias under action-dependent logging and shared-baseline misspecification. On a semi-synthetic job-marketplace benchmark with real logged features and simulated outcomes, our practical Thompson-restricted variant achieves the lowest regret among evaluated budget-feasible methods in the operating regime. It reduces regret by approximately 20% versus the strongest reward-based baseline, outperforming raw-reward contextual bandits, BwK baselines, and a static offline policy, while never exceeding the effective-cost budget.

0.27

Explore Once, Evaluate Many: Multiple Policy Evaluation for Stochastic Linear Bandits

cs.LG stat.ML ·2026-10-15 ·Spyros Dragazis, Yilei Chen, Aldo Pacchiano
theory similarity 0.70
Abstract

We study how to evaluate $K$ target policies simultaneously in stochastic contextual bandits with linear reward structure. Given a known $d$-dimensional feature map and reward-free access to policy queries, we propose PRISMA (Policy evaluation through Regularized Information Sharing and Mixture Allocation), an algorithm that estimates every target policy's value to accuracy $\varepsilon$ with probability at least $1-δ$. The algorithm uses $\widetilde{\mathcal{O}}\!\left( \frac{(L^2S^2+β^2)(1\veeρ^\star)}{\varepsilon^2} \cdot \log(K) \right)$ context draws and reward observations, where $ρ^\star\le d$ is an instance-dependent measure of the difficulty of designing a shared sampling distribution. Here, $L$, $S$, and $β$ bound the feature norm, reward parameter norm, and reward noise, respectively, and the suppressed factors are logarithmic in $K$, $d$, and $1/δ$. Our method combines reward-free planning, a regularized sampling design, and a single ridge regression estimator shared across all target policies. An adaptive doubling procedure selects the regularization scale without knowledge of $ρ^\star$. The guarantees require no numerical lower bound on second-moment eigenvalues and have no explicit dependence on the cardinalities of the context and action spaces. Policy-query costs are accounted for separately, with $K$ queries per shared planning context.

0.17

Saturation-Insensitive Dueling Bandits with General Function Approximation

cs.LG ·2026-09-26 ·Chenggong Zhang, Xuheng Li, Qiwei Di, Weitong Zhang, Quanquan Gu
similarity 0.70
Abstract · 29 pages

We study contextual dueling bandits with general function approximation under the Bradley-Terry-Luce (BTL) preference model. A key challenge in this setting is the saturation of the preference model: when the current reward model can already distinguish two actions with high confidence, the resulting preference feedback becomes weakly informative, making it difficult to further improve reward estimation. Consequently, existing sample-complexity analyses often depend on the inverse-derivative factor $1 / σ'[Δ_{r^\ast}]$ which can be prohibitively large when the link function $σ$ saturates for large reward gaps $Δ_{r^\ast}$. To address this issue, we introduce `SI-CDB`, an algorithm that selects opponent arms using a carefully designed heuristic for arm selection. This design enables saturation-insensitive reward learning and recovers the near-optimal dependence for linear reward classes, eliminating the unfavorable $1/σ'(\cdot)$ factor. The core of our analysis is a localized Eluder dimension framework tailored to dueling bandits with general function approximation. Our theoretical results also explain why two-arm regret analysis is crucial for improving single-arm performance in dueling bandits.

0.24

Contextual Non-Convex Bandit Optimization with Two-Point Feedback

cs.LG ·2026-11-13 ·Khaled Eldowa, Pierre Gaillard
similarity 0.69
Abstract

We study a non-stochastic contextual bandit problem with Lipschitz losses. At every round, the learner observes the context then picks two actions, observes the difference between their losses, and incurs their mean. The aim is to minimize the regret against a generic non-parametric comparator class of policies mapping contexts to actions; for example, Lipschitz policies and Hölder-smooth policies. We show how relying on a hierarchical discretization technique allows us to improve upon the regret rates achievable under one-point feedback, and even recover the full-information rate in some cases; notably, for sufficiently smooth policy classes or low-dimensional instances. Additionally, for Lipschitz policies, we present an algorithm whose per-round computational complexity is only logarithmic in the time horizon.

0.13

Multi-Objective Causal Bandits: Minimal Intervention Space and Policy-Level Learning

cs.LG ·2026-11-14 ·Muhammad Qasim Elahi, Mahsa Ghasemi, Murat Kocaoglu
top venue similarity 0.69
Abstract · To appear in Proceedings of NeurIPS 26

Many decision-making problems involve multiple objectives, where actions affect several performance metrics, fairness criteria, or safety constraints. We study multi-objective causal bandits with multiple reward nodes, where actions correspond to interventions on subsets of variables in a causal graph and performance is evaluated through Pareto optimality. Existing approaches to multi-objective bandits often rely on pairwise Pareto dominance or optimize a fixed scalarization. However, pairwise comparisons alone can fail to identify actions dominated by randomized policies, whose expected reward vectors lie in the convex hull of action-level rewards. Thus, an intervention may be suboptimal even if no single intervention dominates it, because it can be dominated by a randomized policy over other interventions. We formalize this policy-level phenomenon and show that it has consequences for both causal action-space reduction and online learning. First, we provide a necessary-and-sufficient graphical characterization of possibly Pareto- optimal minimal intervention sets. Our characterization yields a minimal, sound, and complete candidate intervention family from the graph alone, correcting prior formulations that may include intervention sets that are never Pareto-optimal under any compatible structural causal model. Second, over this reduced intervention space, we design an online UCB-style algorithm that eliminates actions using dominance tests against convex combinations of other actions, and prove logarithmic gap-dependent Pareto regret. Finally, we study constrained multi-objective causal bandits, where feasibility and optimality may be realized only with randomized policies, and develop an online UCB-style constrained bandit algorithm with sublinear regret and constraint-violation guarantees.

0.26