The price of unfairness in linear bandits with biased feedback

Solenne Gaucher, Alexandra Carpentier, Christophe GiraudNeurIPS 2022 · OpenReview

Introduction

When decision-making algorithms rely on biased feedback—such as a hiring tool trained on prejudiced human evaluations—they often fail to identify the best options. In a standard "linear bandit" problem, an agent chooses actions (like showing an ad or selecting a job candidate) and receives a noisy reward. Over time, the agent learns which actions yield the highest rewards. But what happens if the feedback itself is systematically biased against a specific group?

Imagine a recruiter using an AI to screen candidates. If historical evaluations were prejudiced against a minority group, the AI observes lower "perceived" rewards for those candidates, even if their "true" potential is high. A standard algorithm would quickly stop picking candidates from the minority group, never realizing they were undervalued. This leads to two critical failures: it is ethically unfair, and it is economically sub-optimal because the agent misses out on high-performing individuals.

This paper tackles this "biased feedback" loop. The authors model a scenario where the agent knows the sensitive attribute (e.g., group membership) but must figure out how much the feedback is skewed while simultaneously trying to maximize the true, unbiased reward. They introduce the Fair Phased Elimination algorithm, which explicitly estimates and corrects for this bias, proving that the "price" of achieving fairness is a fundamental shift in performance: from the standard $\mathcal{O}(\sqrt{T})$ regret to a much steeper $\mathcal{O}(T^{2/3})$.

The Fair Phased Elimination Algorithm

To solve this, the authors propose the Fair Phased Elimination (FPE) algorithm. It operates in phases, progressively narrowing down the set of "potentially optimal" actions. Its unique architecture handles two distinct tasks to separate true reward from bias:

  1. G-Exploration (Within-Group): This standard technique uses "G-optimal design" to estimate the rewards of actions within the same group. Since the bias is constant for everyone in a specific group, the relative ranking within that group remains reliable.
  2. $\Delta$-Exploration (Across-Groups): This is the novel core of the approach. To compare a candidate from Group A with one from Group B, the agent must estimate the bias parameter. The authors develop a "$\Delta$-optimal design" that specifically selects actions to minimize the variance of this bias estimate.

Crucially, the algorithm includes a stopping criterion. Estimating bias can be "expensive" in terms of regret because it often requires picking very sub-optimal actions just to observe how the bias behaves. If the gap between groups is small enough that the bias doesn't matter for the final decision, the algorithm stops trying to be precise and focuses purely on exploitation.

Key Insights: The Geometry and Price of Bias

The paper uncovers several fundamental properties of learning under biased feedback:

  • The $T^{2/3}$ Barrier: In standard linear bandits, the "regret" (the reward lost by not knowing the best action from the start) grows at a rate of $\mathcal{O}(\sqrt{T})$. The authors prove that with biased feedback, the agent is forced into a "partial monitoring" regime where regret grows much faster, at $\mathcal{O}(T^{2/3})$. This steeper curve is the literal "price of unfairness."
  • The Geometry of Bias ($\kappa_*$): The difficulty of the problem depends heavily on an explicit geometric constant, $\kappa_*$. If the two groups look very similar in their features, it is hard to tell if a low reward is due to the action's quality or the group bias. Conversely, if the groups are "well-separated" in feature space, bias estimation becomes easier.
Geometric representation of the bias difficulty constant $\kappa_*$.
  • Regime Transition: The paper reveals a fascinating "phase transition." If one group is clearly better than the other, the problem eventually collapses back into a standard linear bandit (the "easy" regime). However, if both groups contain near-optimal actions, the agent is trapped in the "hard" regime where it must constantly pay the price to debias its observations.

Theoretical Guarantees

The authors provide rigorous mathematical proofs that their algorithm's performance matches the fundamental limits of the problem:

  • Upper Bound: The FPE algorithm achieves a worst-case regret of $\mathcal{O}(\kappa_*^{1/3} \log(T)^{1/3} T^{2/3})$. This confirms that the algorithm efficiently balances the cost of debiasing with the need to earn rewards.
  • Lower Bound: A matching lower bound is proven, showing that no algorithm can do better than $T^{2/3}$ in this setting. This establishes their result as a fundamental limit of sequential decision-making under bias.
  • Gap-Dependent Regret: A more granular analysis shows that if there is a large "gap" between the best and second-best actions, the regret grows only logarithmically with time, though the constant factor is still influenced by the difficulty of bias estimation ($\kappa_*$).

Limitations and Future Directions

While theoretically robust, the current framework has limitations that pave the way for future research:

  • Two-Group Limitation: The primary model focuses on two groups (e.g., privileged vs. discriminated). While extensions to multiple groups are suggested, the complexity and regret bounds for many groups or intersecting identities remain open.
  • Linearity Assumption: The model assumes rewards and biases are linear. In many real-world scenarios, these relationships are non-linear, requiring more complex estimation techniques.
  • Known Sensitive Attributes: The algorithm requires knowing which group an action belongs to at the time of decision. While some legal frameworks mandate "unawareness" (ignoring sensitive attributes), this paper argues that awareness is mathematically necessary to correct for systemic bias. Future work may explore models with multi-dimensional or continuous sensitive attributes.

Summary updated

Abstract

In this paper, we study the problem of fair sequential decision making with biased linear bandit feedback. At each round, a player selects an action described by a covariate and by a sensitive attribute. The perceived reward is a linear combination of the covariates of the chosen action, but the player only observes a biased evaluation of this reward, depending on the sensitive attribute. To characterize the difficulty of this problem, we design a phased elimination algorithm that corrects the unfair evaluations, and establish upper bounds on its regret. We show that the worst-case regret is smaller than $\mathcal{O}(\kappa_* ^{1/3}\log(T)^{1/3}T^{2/3})$, where $\kappa_*$ is an explicit geometrical constant characterizing the difficulty of bias estimation. We prove lower bounds on the worst-case regret for some sets of actions showing that this rate is tight up to a possible sub-logarithmic factor. We also derive gap-dependent upper bounds on the regret, and matching lower bounds for some problem instance. Interestingly, these results reveal a transition between a regime where the problem is as difficult as its unbiased counterpart, and a regime where it can be much harder.
BibTeX
@inproceedings{gaucher2022price,
  author = {Solenne Gaucher and Alexandra Carpentier and Christophe Giraud},
  title = {{The price of unfairness in linear bandits with biased feedback}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=fbBFptemOj7},
}
Figure