# Revisiting Social Welfare in Bandits: UCB is (Nearly) All You Need

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 16 references that are in the map.
- First posted on arXiv 24 Oct 2025.

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

- [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)
- [Fairness and Welfare Quantification for Regret in Multi-Armed Bandits](https://mlsanity.com/paper/2205.13930/) (2022)
- [Socially Fair Reinforcement Learning](https://mlsanity.com/paper/2208.12584/) (2022)
- [Universal and Tight Online Algorithms for Generalized-Mean Welfare](https://mlsanity.com/paper/2109.00874/) (2021)
- [An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret](https://mlsanity.com/paper/2209.11817/) (2022)
- [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)
- [p-Mean Regret for Stochastic Bandits](https://mlsanity.com/paper/2412.10751/) (2024)
- [Tractable Fragments of the Maximum Nash Welfare Problem](https://mlsanity.com/paper/2112.10199/) (2021)
- [DP-NCB: Privacy Preserving Fair Bandits](https://mlsanity.com/paper/2508.03836/) (2025)

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

- [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)
- [Online Social Welfare Function-based Resource Allocation](https://mlsanity.com/paper/2602.01400/) (2026)
- [Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret](https://mlsanity.com/paper/2610.07737/) (2026)

## Abstract (arXiv)

Regret in stochastic multi-armed bandits traditionally measures the difference between the highest reward and either the arithmetic mean of accumulated rewards or the final reward. These conventional metrics often fail to address fairness among agents receiving rewards, particularly in settings where rewards are distributed across a population, such as patients in clinical trials. To address this, a recent body of work has introduced Nash regret, which evaluates performance via the geometric mean of accumulated rewards, aligning with the Nash social welfare function known for satisfying fairness axioms. To minimize Nash regret, existing approaches require specialized algorithm designs and strong assumptions, such as multiplicative concentration inequalities and bounded, non-negative rewards, making them unsuitable for even Gaussian reward distributions. We demonstrate that an initial uniform exploration phase followed by a standard Upper Confidence Bound (UCB) algorithm achieves near-optimal Nash regret, while relying only on additive Hoeffding bounds, and naturally extending to sub-Gaussian rewards. Furthermore, we generalize the algorithm to a broad class of fairness metrics called the p-mean regret, proving (nearly) optimal regret bounds uniformly across all p values. This is in contrast to prior work, which made extremely restrictive assumptions on the bandit instances and even then achieved suboptimal regret bounds.