Research map / Bandits and online learning / Multi-armed bandits
On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces affinity bandits, a non-stationary bandit variant where observed feedback is multiplicatively reweighted by each arm's pull fraction, proves an instance-dependent regret lower bound for consistent policies, and gives a phased-elimination algorithm nearly matching it without knowing the bias.
Problem
Bandit learning under affinity bias in a hiring feedback loop: only biased feedback is observed, and the bias of each arm depends on the fraction of past pulls of that arm, while the goal is regret with respect to unobserved real rewards.
Approach
Models feedback whose mean is the real mean times a non-decreasing function of an arm's pull fraction (shared across arms via the feedback loop), shows that standard UCB/EXP3 fail, derives a lower bound larger than the standard one by a factor depending on K via a new divergence decomposition with stopping times, and shows a phased elimination algorithm with unknown bias nearly matches it.
Key results
- Lower bound: regret of any consistent policy is at least roughly fraction-reweighting-inverse-squared times sum of log(n)/Delta_i, larger than the standard 2 log(n)/Delta_i bound by a factor depending on K.
- Phased elimination algorithm achieves regret of order sum log(n)/Delta_i scaled by f(1/(15K))^{-2}, matching the lower bound up to poly log(K) for polynomial bias functions.
- Simulations show UCB, EXP3 and EXP3-IX pull the suboptimal arm more than half the horizon with non-negligible probability for high initial weight on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the phased elimination algorithm that samples active arms in sequence and eliminates arms by empirical feedback | Affinity bandits · Affinity bandits | regret | Helped |
| Ignore the bias model and run UCB | Affinity bandits · Affinity bandits | regret | Hurt |
| Ignore the bias model and run EXP3 | Affinity bandits · Affinity bandits | regret | Hurt |
Surprising findings
- Standard UCB, EXP3 and EXP3-IX suffer linear regret in this setting even though the real reward is unchanged.
- Even with the bias model known, the lower bound holds, showing the feedback loop itself makes the problem harder.
Limitations
- Assumes groups have different expected real rewards, which may be problematic when groups are defined by sensitive attributes.
- Assumes the bias depends on the whole unbounded history, unlike a bounded hiring committee of size M.
- Requires the time horizon to be known and sufficiently large.
Experimental setup
Metrics: pseudo-regret probability of pulling suboptimal arm
Baselines: UCB EXP3 EXP3-IX UCB-V
Builds on: UCB-V EXP3 Lai and Robbins lower bound divergence decomposition lower bound framework
Closest papers by meaning
- Robustly Improving Bandit Algorithms with Confounded and Selection Biased Offline Data: A Causal Approach (AAAI 2024 · similarity 0.87)
- Improved Analysis for Bandit Learning in Matching Markets (NeurIPS 2024 · similarity 0.87)
- Bandits with Ranking Feedback (NeurIPS 2024 · similarity 0.86)
- Learning from Imperfect Human Feedback: A Tale from Corruption-Robust Dueling (ICLR 2025 · similarity 0.85)
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.85)
- Enhancing Preference-based Linear Bandits via Human Response Time (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.