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

arXiv:2610.07737v1 Announce Type: cross 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 NR_T = mu^star - (prod_{t=1}^T Emu_{I_t})^{1/T}, where mu_{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 trajectory-wise Nash regret widetilde{NR}T = mu^star - E[(prod{t=1}^T mu_{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, widetilde{NR}_T geq NR_T, making it a strictly stronger metric. We also introduce high probability Nash regret widehat{NR}T = mu^star - (prod_t mu{I_t})^{1/T}, giving the first high probability regret bounds in fair bandits. Our two-phase algorithm, Round Robin Nash Confidence Bound (exttt{RR-NCB}), combines round robin exploration with a Nash confidence bound index policy. We show widetilde{NR}_T leq widetilde{O}(sqrt{klog T/T}) and, with probability 1-elta, widehat{NR}_T leq widetilde{O}(sqrt{klog(kT/elta)/T}), matching the optimal widetilde{O}(sqrt{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

• Improved Algorithms for Nash Welfare in Linear Bandits
• Multi-User Dueling Bandits: A Fair Approach using Nash Social Welfare
• Multi-Objective Multi-Agent Bandits: From Learning Efficiency to Fairness Optimization
• Procedural Fairness in Multi-Agent Bandits

Source: arXiv cs.LG | 2026-10-07