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

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.