# p-Mean Regret for Stochastic Bandits

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 22 references that are in the map.
- First posted on arXiv 14 Dec 2024.

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

- [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)
- [Fair Algorithms for Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.06699/) (2020)
- [Multi-Armed Bandits for Intelligent Tutoring Systems](https://mlsanity.com/paper/1310.3174/) (2013)
- [Universal and Tight Online Algorithms for Generalized-Mean Welfare](https://mlsanity.com/paper/2109.00874/) (2021)
- [Nash Regret Guarantees for Linear Bandits](https://mlsanity.com/paper/2310.02023/) (2023)
- [Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations](https://mlsanity.com/paper/2005.07370/) (2020)
- [No-Regret Learning for Fair Multi-Agent Social Welfare Optimization](https://mlsanity.com/paper/2405.20678/) (2024)
- [On the Fairness of Normalized p-Means for Allocating Goods and Chores](https://mlsanity.com/paper/2402.14996/) (2024)
- [Tractable Fragments of the Maximum Nash Welfare Problem](https://mlsanity.com/paper/2112.10199/) (2021)

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

- [Revisiting Social Welfare in Bandits: UCB is (Nearly) All You Need](https://mlsanity.com/paper/2510.21312/) (2025)
- [DP-NCB: Privacy Preserving Fair Bandits](https://mlsanity.com/paper/2508.03836/) (2025)
- [Improved Algorithms for Nash Welfare in Linear Bandits](https://mlsanity.com/paper/2601.22969/) (2026)
- [Price of Fairness in Bandits: A Tight Minimax Characterization](https://mlsanity.com/paper/2607.13402/) (2026)
- [Multi-agent Multi-armed Bandits with Minimum Reward Guarantee Fairness](https://mlsanity.com/paper/2502.15240/) (2025)
- [Online Social Welfare Function-based Resource Allocation](https://mlsanity.com/paper/2602.01400/) (2026)

## Abstract (arXiv)

In this work, we extend the concept of the p-mean welfare objective from social choice theory (Moulin 2004) to study p-mean regret in stochastic multi-armed bandit problems. The p-mean regret, defined as the difference between the optimal mean among the arms and the p-mean of the expected rewards, offers a flexible framework for evaluating bandit algorithms, enabling algorithm designers to balance fairness and efficiency by adjusting the parameter p. Our framework encompasses both average cumulative regret and Nash regret as special cases. We introduce a simple, unified UCB-based algorithm (Explore-Then-UCB) that achieves novel p-mean regret bounds. Our algorithm consists of two phases: a carefully calibrated uniform exploration phase to initialize sample means, followed by the UCB1 algorithm of Auer, Cesa-Bianchi, and Fischer (2002). Under mild assumptions, we prove that our algorithm achieves a p-mean regret bound of tildeOleft(√frackT^frac12|p|right) for all p ≤ -1, where k represents the number of arms and T the time horizon. When -1<p<0, we achieve a regret bound of tildeOleft(√frack1.5T^frac12right). For the range 0< p ≤ 1, we achieve a p-mean regret scaling as tildeOleft(√frackTright), which matches the previously established lower bound up to logarithmic factors (Auer et al. 1995). This result stems from the fact that the p-mean regret of any algorithm is at least its average cumulative regret for p ≤ 1. In the case of Nash regret (the limit as p approaches zero), our unified approach differs from prior work (Barman et al. 2023), which requires a new Nash Confidence Bound algorithm. Notably, we achieve the same regret bound up to constant factors using our more general method.