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:
- 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.
- $\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.
- 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