# Improved Algorithms for Nash Welfare in Linear Bandits

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 23 references that are in the map.
- First posted on arXiv 30 Jan 2026.

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

- [Introducing LETOR 4.0 Datasets](https://mlsanity.com/paper/1306.2597/) (2013)
- [A near-optimal algorithm for approximating the John Ellipsoid](https://mlsanity.com/paper/1905.11580/) (2019)
- [Fairness and Welfare Quantification for Regret in Multi-Armed Bandits](https://mlsanity.com/paper/2205.13930/) (2022)
- [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)
- [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)
- [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)

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

- [Price of Fairness in Bandits: A Tight Minimax Characterization](https://mlsanity.com/paper/2607.13402/) (2026)
- [Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret](https://mlsanity.com/paper/2610.07737/) (2026)

## Abstract (arXiv)

Nash regret has recently emerged as a principled fairness-aware performance metric for stochastic multi-armed bandits, motivated by the Nash Social Welfare objective. Although this notion has been extended to linear bandits, existing results suffer from suboptimality in ambient dimension d, stemming from proof techniques that rely on restrictive concentration inequalities. In this work, we resolve this open problem by introducing new analytical tools that yield an order-optimal Nash regret bound in linear bandits. Beyond Nash regret, we initiate the study of p-means regret in linear bandits, a unifying framework that interpolates between fairness and utility objectives and strictly generalizes Nash regret. We propose a generic algorithmic framework, FairLinBandit, that works as a meta-algorithm on top of any linear bandit strategy. We instantiate this framework using two bandit algorithms: Phased Elimination and Upper Confidence Bound, and prove that both achieve sublinear p-means regret for the entire range of p. Extensive experiments on linear bandit instances generated from real-world datasets demonstrate that our methods consistently outperform the existing state-of-the-art baseline.