Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret
Abstract
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 = μ⋆ − (∏t=1T 𝔼μ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 \emph{trajectory-wise Nash regret} NR̃T = μ⋆ − 𝔼[(∏t=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, NR̃T ≥ NRT, making it a strictly stronger metric. We also introduce \emph{high probability Nash regret} NR̂T = μ⋆ − (∏t μIt)1/T, giving the first high probability regret bounds in fair bandits. Our two-phase algorithm, Round Robin Nash Confidence Bound (\texttt{RR-NCB}), combines round robin exploration with a Nash confidence bound index policy. We show NR̃T ≤ 𝒪̃(√(klog T/T)) and, with probability 1−δ, NR̂T ≤ 𝒪̃(√(klog(kT/δ)/T)), matching the optimal 𝒪̃(√(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.
Related
- Expected Sample Complexity in Multi-Armed Bandits
- Adaptive Node Distribution via Probability Density Functions for Birkhoff Pseudospectral Trajectory Optimisation
- SAG-RS: Trajectory-Aware Probability Stacking with Contextual-Bandit Reliability Gating for ICD-Audited Diabetes Phenotype Identification in MIMIC-IV
- There can be equitable social welfare orders but no fair voting system
- An Improved Advanced Social Memory Optimization Framework for Global Optimization Problem and UAV Obstacle Avoidance Trajectory Planning
BibTeX
@misc{ghosh2026nash,
title = {{Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret}},
author = {Avishek Ghosh},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07737},
eprint = {2610.07737},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07737},
}
RIS
TY - UNPB
TI - Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret
AU - Avishek Ghosh
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.07737
UR - https://arxiv.org/abs/2610.07737
AB - 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 NR_T = μ^⋆ − (∏_t=1^T 𝔼μ_I_t)^1/T, where μ_I_t is the mean reward of the recommended arm I_t 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 \emph{trajectory-wise Nash regret} NR̃_T = μ^⋆ − 𝔼[(∏_t=1^T μ_I_t)^1/T], which computes the geometric mean over complete sample paths before taking expectations, capturing NSW fairness more faithfully. By Jensen's inequality, NR̃_T ≥ NR_T, making it a strictly stronger metric. We also introduce \emph{high probability Nash regret} NR̂_T = μ^⋆ − (∏_t μ_I_t)^1/T, giving the first high probability regret bounds in fair bandits. Our two-phase algorithm, Round Robin Nash Confidence Bound (\texttt{RR-NCB}), combines round robin exploration with a Nash confidence bound index policy. We show NR̃_T ≤ 𝒪̃(√(klog T/T)) and, with probability 1−δ, NR̂_T ≤ 𝒪̃(√(klog(kT/δ)/T)), matching the optimal 𝒪̃(√(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.
ER -