# The price of unfairness in linear bandits with biased feedback

arXiv: https://arxiv.org/abs/2203.09784 · HTML: https://mlsanity.com/paper/2203.09784/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 52 references that are in the map.
- First posted on arXiv 18 Mar 2022.

## Builds on (most cited first, 18 of 18)

- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Avoiding Discrimination through Causal Reasoning](https://mlsanity.com/paper/1706.02744/) (2017)
- [Fairness in Machine Learning](https://mlsanity.com/paper/2012.15816/) (2020)
- [Mitigating Bias in Algorithmic Hiring: Evaluating Claims and Practices](https://mlsanity.com/paper/1906.09208/) (2019)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits](https://mlsanity.com/paper/1610.04491/) (2016)
- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [Information Directed Sampling for Linear Partial Monitoring](https://mlsanity.com/paper/2002.11182/) (2020)
- [Fairness in Algorithmic Decision Making: An Excursion Through the Lens of Causality](https://mlsanity.com/paper/1903.11719/) (2019)
- [Asymptotically Optimal Information-Directed Sampling](https://mlsanity.com/paper/2011.05944/) (2020)
- [A Unified Approach to Fair Online Learning via Blackwell Approachability](https://mlsanity.com/paper/2106.12242/) (2021)
- [Experimental Design for Regret Minimization in Linear Bandits](https://mlsanity.com/paper/2011.00576/) (2020)
- [An Algorithmic Framework to Control Bias in Bandit-based Personalization](https://mlsanity.com/paper/1802.08674/) (2018)
- [Individual Fairness in Advertising Auctions through Inverse Proportionality](https://mlsanity.com/paper/2003.13966/) (2020)
- [Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem](https://mlsanity.com/paper/2102.09704/) (2021)
- [Phased Exploration with Greedy Exploitation in Stochastic Combinatorial Partial Monitoring Games](https://mlsanity.com/paper/1608.06403/) (2016)
- [Diversity-Preserving K-Armed Bandits, Revisited](https://mlsanity.com/paper/2010.01874/) (2020)
- [Computing exact D-optimal designs by mixed integer second-order cone programming](https://mlsanity.com/paper/1307.4953/) (2013)

## Built on by (most cited first, 3 of 3)

- [Fair Online Bilateral Trade](https://mlsanity.com/paper/2405.13919/) (2024)
- [A Critical Review of Predominant Bias in Neural Networks](https://mlsanity.com/paper/2502.11031/) (2025)
- [On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback](https://mlsanity.com/paper/2503.05662/) (2025)

## Abstract (arXiv)

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 O(kappa_*1/3log(T)1/3T2/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.