# Nash Regret Guarantees for Linear Bandits

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 28 references that are in the map.
- First posted on arXiv 3 Oct 2023.

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

- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [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)
- [Regret Minimization in Heavy-Tailed Bandits](https://mlsanity.com/paper/2102.03734/) (2021)
- [A near-optimal algorithm for approximating the John Ellipsoid](https://mlsanity.com/paper/1905.11580/) (2019)
- [A Contextual-bandit-based Approach for Informed Decision-making in Clinical Trials](https://mlsanity.com/paper/1809.00258/) (2018)
- [Fairness and Welfare Quantification for Regret in Multi-Armed Bandits](https://mlsanity.com/paper/2205.13930/) (2022)
- [My Fair Bandit: Distributed Learning of Max-Min Fairness with Multi-player Bandits](https://mlsanity.com/paper/2002.09808/) (2020)
- [The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis](https://mlsanity.com/paper/2102.05077/) (2021)

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

- [No-Regret Learning for Fair Multi-Agent Social Welfare Optimization](https://mlsanity.com/paper/2405.20678/) (2024)
- [p-Mean Regret for Stochastic Bandits](https://mlsanity.com/paper/2412.10751/) (2024)
- [Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies](https://mlsanity.com/paper/2408.12845/) (2024)
- [Stochastic Bandits for Egalitarian Assignment](https://mlsanity.com/paper/2410.05856/) (2024)
- [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)
- [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 obtain essentially tight upper bounds for a strengthened notion of regret in the stochastic linear bandits framework. The strengthening -- referred to as Nash regret -- is defined as the difference between the (a priori unknown) optimum and the geometric mean of expected rewards accumulated by the linear bandit algorithm. Since the geometric mean corresponds to the well-studied Nash social welfare (NSW) function, this formulation quantifies the performance of a bandit algorithm as the collective welfare it generates across rounds. NSW is known to satisfy fairness axioms and, hence, an upper bound on Nash regret provides a principled fairness guarantee. We consider the stochastic linear bandits problem over a horizon of T rounds and with set of arms X in ambient dimension d. Furthermore, we focus on settings in which the stochastic reward -- associated with each arm in X -- is a non-negative, nu-sub-Poisson random variable. For this setting, we develop an algorithm that achieves a Nash regret of Oleft( √fracdnuT log( T |X|)right). In addition, addressing linear bandit instances in which the set of arms X is not necessarily finite, we obtain a Nash regret upper bound of Oleft( fracd^frac54nu^frac12√T log(T)right). Since bounded random variables are sub-Poisson, these results hold for bounded, positive rewards. Our linear bandit algorithm is built upon the successive elimination method with novel technical insights, including tailored concentration bounds and the use of sampling via John ellipsoid in conjunction with the Kiefer-Wolfowitz optimal design.