# Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 64 references that are in the map.
- First posted on arXiv 19 Aug 2022.

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

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Delayed Impact of Fair Machine Learning](https://mlsanity.com/paper/1803.04383/) (2018)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Fairness in Reinforcement Learning](https://mlsanity.com/paper/1611.03071/) (2016)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017)
- [Algorithms for Fairness in Sequential Decision Making](https://mlsanity.com/paper/1901.08568/) (2019)
- [On the Long-term Impact of Algorithmic Decision Policies: Effort Unfairness and Feature Segregation through Social Learning](https://mlsanity.com/paper/1903.01209/) (2019)
- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [Fair Contextual Multi-Armed Bandits: Theory and Experiments](https://mlsanity.com/paper/1912.08055/) (2019)
- [Fair Algorithms for Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.06699/) (2020)
- [What does it mean to solve the problem of discrimination in hiring? Social, technical and legal perspectives from the UK on automated hiring systems](https://mlsanity.com/paper/1910.06144/) (2019)
- [Online Learning with Vector Costs and Bandits with Knapsacks](https://mlsanity.com/paper/2010.07346/) (2020)
- [A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret](https://mlsanity.com/paper/1508.03769/) (2015)
- [Contextual Blocking Bandits](https://mlsanity.com/paper/2003.03426/) (2020)
- [Long-Term Resource Allocation Fairness in Average Markov Decision Process (AMDP) Environment](https://mlsanity.com/paper/2102.07120/) (2021)
- [Addressing the Long-term Impact of ML Decisions via Policy Regret](https://mlsanity.com/paper/2106.01325/) (2021)

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

- [Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem](https://mlsanity.com/paper/2404.01198/) (2024)
- [Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problem](https://mlsanity.com/paper/2511.10619/) (2025)
- [Combinatorial Rising Bandits](https://mlsanity.com/paper/2412.00798/) (2024)
- [Ads that Stick: Near-Optimal Ad Optimization through Psychological Behavior Models](https://mlsanity.com/paper/2509.20304/) (2025)
- [Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting](https://mlsanity.com/paper/2409.05980/) (2024)
- [Multi-agent Multi-armed Bandits with Minimum Reward Guarantee Fairness](https://mlsanity.com/paper/2502.15240/) (2025)
- [Rising Multi-Armed Bandits with Known Horizons](https://mlsanity.com/paper/2602.10727/) (2026)
- [Prior-Free Competitive Ratios for Improving Bandits: Scale, Curvature and Horizon Are Free, but Not Jointly Under Noise](https://mlsanity.com/paper/2609.17595/) (2026)

## Abstract (arXiv)

We study the Improving Multi-Armed Bandit (IMAB) problem, where the reward obtained from an arm increases with the number of pulls it receives. This model provides an elegant abstraction for many real-world problems in domains such as education and employment, where decisions about the distribution of opportunities can affect the future capabilities of communities and the disparity between them. A decision-maker in such settings must consider the impact of her decisions on future rewards in addition to the standard objective of maximizing her cumulative reward at any time. In many of these applications, the time horizon is unknown to the decision-maker beforehand, which motivates the study of the IMAB problem in the technically more challenging horizon-unaware setting. We study the tension that arises between two seemingly conflicting objectives in the horizon-unaware setting: a) maximizing the cumulative reward at any time based on current rewards of the arms, and b) ensuring that arms with better long-term rewards get sufficient opportunities even if they initially have low rewards. We show that, surprisingly, the two objectives are aligned with each other in this setting. Our main contribution is an anytime algorithm for the IMAB problem that achieves the best possible cumulative reward while ensuring that the arms reach their true potential given sufficient time. Our algorithm mitigates the initial disparity due to lack of opportunity and continues pulling an arm till it stops improving. We prove the optimality of our algorithm by showing that a) any algorithm for the IMAB problem, no matter how utilitarian, must suffer Omega(T) policy regret and Omega(k) competitive ratio with respect to the optimal offline policy, and b) the competitive ratio of our algorithm is O(k).