# Fairness and Welfare Quantification for Regret in Multi-Armed Bandits

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 32 references that are in the map.
- First posted on arXiv 27 May 2022.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Causal Bandits: Learning Good Interventions via Causal Inference](https://mlsanity.com/paper/1606.03203/) (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)
- [My Fair Bandit: Distributed Learning of Max-Min Fairness with Multi-player Bandits](https://mlsanity.com/paper/2002.09808/) (2020)

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

- [Proportional Aggregation of Preferences for Sequential Decision Making](https://mlsanity.com/paper/2306.14858/) (2023)
- [Socially Fair Reinforcement Learning](https://mlsanity.com/paper/2208.12584/) (2022)
- [Nash Regret Guarantees for Linear Bandits](https://mlsanity.com/paper/2310.02023/) (2023)
- [Achieving Fairness in Multi-Agent Markov Decision Processes Using Reinforcement Learning](https://mlsanity.com/paper/2306.00324/) (2023)
- [No-Regret Learning for Fair Multi-Agent Social Welfare Optimization](https://mlsanity.com/paper/2405.20678/) (2024)
- [Multi-objective Reinforcement Learning with Nonlinear Preferences: Provable Approximation for Maximizing Expected Scalarized Return](https://mlsanity.com/paper/2311.02544/) (2023)
- [Equitable Restless Multi-Armed Bandits: A General Framework Inspired By Digital Health](https://mlsanity.com/paper/2308.09726/) (2023)
- [Avoiding Catastrophe in Online Learning by Asking for Help](https://mlsanity.com/paper/2402.08062/) (2024)
- [Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies](https://mlsanity.com/paper/2408.12845/) (2024)
- [Revisiting Social Welfare in Bandits: UCB is (Nearly) All You Need](https://mlsanity.com/paper/2510.21312/) (2025)
- [Fairness Aware Reinforcement Learning via Proximal Policy Optimization](https://mlsanity.com/paper/2502.03953/) (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)
- [Online Social Welfare Function-based Resource Allocation](https://mlsanity.com/paper/2602.01400/) (2026)
- [Envy-Free Allocation of Indivisible Goods via Noisy Queries](https://mlsanity.com/paper/2602.06361/) (2026)
- [Multi-User Dueling Bandits: A Fair Approach using Nash Social Welfare](https://mlsanity.com/paper/2605.01961/) (2026)

## Abstract (arXiv)

We extend the notion of regret with a welfarist perspective. Focussing on the classic multi-armed bandit (MAB) framework, the current work quantifies the performance of bandit algorithms by applying a fundamental welfare function, namely the Nash social welfare (NSW) function. This corresponds to equating algorithm's performance to the geometric mean of its expected rewards and leads us to the study of Nash regret, defined as the difference between the -- a priori unknown -- optimal mean (among the arms) and the algorithm's performance. Since NSW is known to satisfy fairness axioms, our approach complements the utilitarian considerations of average (cumulative) regret, wherein the algorithm is evaluated via the arithmetic mean of its expected rewards. This work develops an algorithm that, given the horizon of play T, achieves a Nash regret of O left( √frack log TT right), here k denotes the number of arms in the MAB instance. Since, for any algorithm, the Nash regret is at least as much as its average regret (the AM-GM inequality), the known lower bound on average regret holds for Nash regret as well. Therefore, our Nash regret guarantee is essentially tight. In addition, we develop an anytime algorithm with a Nash regret guarantee of O left( √fracklog TT log T right).