# Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 35 references that are in the map.
- First posted on arXiv 24 Jul 2026.

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

- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2002.10421/) (2020)
- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [A minimax and asymptotically optimal algorithm for stochastic bandits](https://mlsanity.com/paper/1702.07211/) (2017)
- [UCB algorithms for multi-armed bandits: Precise regret and adaptive inference](https://mlsanity.com/paper/2412.06126/) (2024)
- [Online Vector Balancing and Geometric Discrepancy](https://mlsanity.com/paper/1912.03350/) (2019)
- [Approximation-Friendly Discrepancy Rounding](https://mlsanity.com/paper/1512.02254/) (2015)
- [Risk-sensitive Bandits: Arm Mixture Optimality and Regret-efficient Algorithms](https://mlsanity.com/paper/2503.08896/) (2025)
- [A Regret bound for Non-stationary Multi-Armed Bandits with Fairness Constraints](https://mlsanity.com/paper/2012.13380/) (2020)
- [Preference-centric Bandits: Optimality of Mixtures and Regret-efficient Algorithms](https://mlsanity.com/paper/2504.20877/) (2025)
- [Creator Incentives in Recommender Systems: A Cooperative Game-Theoretic Approach for Stable and Fair Collaboration in Multi-Agent Bandits](https://mlsanity.com/paper/2604.08643/) (2026)
- [Fairness under uncertainty in sequential decisions](https://mlsanity.com/paper/2604.21711/) (2026)
- [Simultaneously Achieving Group Exposure Fairness and Within-Group Meritocracy in Stochastic Bandits](https://mlsanity.com/paper/2402.05575/) (2024)
- [Stochastic Multi-Objective Multi-Armed Bandits: Regret Definition and Algorithm](https://mlsanity.com/paper/2506.13125/) (2025)
- [Fairness vs Performance: Characterizing the Pareto Frontier of Algorithmic Decision Systems](https://mlsanity.com/paper/2605.10604/) (2026)

## Abstract (arXiv)

Minimum-exposure constraints arise in recommendation, content curation, and regulated allocation when each provider, arm, or group must receive guaranteed exposure inside a period rather than only in aggregate. We study stochastic bandits with exact exposure floors and show that the right object is a rounding problem: a fractional fair schedule is realized as integral pulls, and the exposure error is exactly a discrepancy vector. The main contribution is a blockwise model with time-varying floors. BDQ-UCB satisfies every block floor deterministically and has fair regret governed by the nonmandatory budget R, not the horizon T, with high-probability regret O(√KRlog(KT)). A MOSS residual variant attains O(√KR), and a matching lower bound gives the minimax rate Theta(√KR), even with positive mandatory exposure; a kl-UCB++ residual rule adds instance-dependent optimality. The formulation becomes essential for overlapping group floors: per-arm rounding can violate a group constraint by Omega(s) in the group size, whereas Beck--Fiala null-space rounding meets every group floor within the block budget with violation below the arm degree t, and composes with UCB at the same R-parametrized regret. For learned group plans, we close disjoint systems at widetildeTheta(√KT), give a dual-ledger decomposition explaining why naive index rules fail under overlap, and prove a plan-sampling rule that is pathwise feasible under an initial cover-slack condition and attains a conditional widetilde O(√KT) guarantee, leaving the condition-free overlap rate open. Experiments on synthetic floors, MovieLens-100k genre exposure, and deployment stress tests show exact feasibility without penalty tuning and regret competitive with tuned Lagrangian baselines.