# Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 27 references that are in the map.
- First posted on arXiv 6 Oct 2026.

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

- [Fair Algorithms for Infinite and Contextual Bandits](https://mlsanity.com/paper/1610.09559/) (2016)
- [No-Regret Learning for Fair Multi-Agent Social Welfare Optimization](https://mlsanity.com/paper/2405.20678/) (2024)
- [Revisiting Social Welfare in Bandits: UCB is (Nearly) All You Need](https://mlsanity.com/paper/2510.21312/) (2025)
- [Improved Algorithms for Nash Welfare in Linear Bandits](https://mlsanity.com/paper/2601.22969/) (2026)

## Abstract (arXiv)

We study fair multi-armed bandits under the Nash Social Welfare (NSW) objective, which measures performance via the geometric mean of accumulated rewards. Existing work defines Nash regret as NRT = μ^star - (prodt=1T mathbbEμIt)1/T, where μIt is the mean reward of the recommended arm It and T is the horizon. Since it applies the geometric mean to per-round marginal expectations, it ignores the joint distribution of rewards across rounds, leaving the NSW fairness motivation unaddressed at the trajectory level. We propose trajectory-wise Nash regret widetildeNRT = μ^star - mathbbE[(prodt=1T μIt)1/T], which computes the geometric mean over complete sample paths before taking expectations, capturing NSW fairness more faithfully. By Jensen's inequality, widetildeNRT ≥ NRT, making it a strictly stronger metric. We also introduce high probability Nash regret widehatNRT = μ^star - (prodt μIt)1/T, giving the first high probability regret bounds in fair bandits. Our two-phase algorithm, Round Robin Nash Confidence Bound (textttRR-NCB), combines round robin exploration with a Nash confidence bound index policy. We show widetildeNRT ≤ widetildeO(√klog T/T) and, with probability 1-δ, widehatNRT ≤ widetildeO(√klog(kT/δ)/T), matching the optimal widetildeO(√k/T) rate despite the stronger metrics. Optimality follows from a lower bound via AM-GM and standard k-armed bandit minimax arguments. Simulations validate our theory.