# On Penalization in Stochastic Multi-armed Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 54 references that are in the map.
- First posted on arXiv 15 Nov 2022.

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

- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Fair Resource Allocation in Federated Learning](https://mlsanity.com/paper/1905.10497/) (2019)
- [Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatment](https://mlsanity.com/paper/1610.08452/) (2016)
- [Fairness of Exposure in Rankings](https://mlsanity.com/paper/1802.07281/) (2018)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [A Convex Framework for Fair Regression](https://mlsanity.com/paper/1706.02409/) (2017)
- [Fairness in Recommendation Ranking through Pairwise Comparisons](https://mlsanity.com/paper/1903.00780/) (2019)
- [FairBatch: Batch Selection for Model Fairness](https://mlsanity.com/paper/2012.01696/) (2020)
- [Ranking with Fairness Constraints](https://mlsanity.com/paper/1704.06840/) (2017)
- [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)
- [Doubly-Robust Lasso Bandit](https://mlsanity.com/paper/1907.11362/) (2019)
- [On Explore-Then-Commit Strategies](https://mlsanity.com/paper/1605.08988/) (2016)
- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [Thompson Sampling for Budgeted Multi-armed Bandits](https://mlsanity.com/paper/1505.00146/) (2015)
- [Double Explore-then-Commit: Asymptotic Optimality and Beyond](https://mlsanity.com/paper/2002.09174/) (2020)
- [No Regret Bound for Extreme Bandits](https://mlsanity.com/paper/1508.02933/) (2015)
- [Extreme Bandits using Robust Statistics](https://mlsanity.com/paper/2109.04433/) (2021)

## Abstract (arXiv)

We study an important variant of the stochastic multi-armed bandit (MAB) problem, which takes penalization into consideration. Instead of directly maximizing cumulative expected reward, we need to balance between the total reward and fairness level. In this paper, we present some new insights in MAB and formulate the problem in the penalization framework, where rigorous penalized regret can be well defined and more sophisticated regret analysis is possible. Under such a framework, we propose a hard-threshold UCB-like algorithm, which enjoys many merits including asymptotic fairness, nearly optimal regret, better tradeoff between reward and fairness. Both gap-dependent and gap-independent regret bounds have been established. Multiple insightful comments are given to illustrate the soundness of our theoretical analysis. Numerous experimental results corroborate the theory and show the superiority of our method over other existing methods.