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 ${\mathrm{N}\mathrm{R}}_T={\mu }^{\star }-({\prod }_{t=1}^T\mathbb{E}{\mu }_{I_t}{)}^{1\mathrm{/}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 \emph{trajectory-wise Nash regret} ${\widetilde{\mathrm{N}\mathrm{R}}}_T={\mu }^{\star }-\mathbb{E}[({\prod }_{t=1}^T{\mu }_{I_t}{)}^{1\mathrm{/}T}]$, which computes the geometric mean over complete sample paths before taking expectations, capturing NSW fairness more faithfully. By Jensen’s inequality, ${\widetilde{\mathrm{N}\mathrm{R}}}_T\ge {\mathrm{N}\mathrm{R}}_T$, making it a strictly stronger metric. We also introduce \emph{high probability Nash regret} ${\widehat{\mathrm{N}\mathrm{R}}}_T={\mu }^{\star }-({\prod }_t{\mu }_{I_t}{)}^{1\mathrm{/}T}$, giving the first high probability regret bounds in fair bandits. Our two-phase algorithm, Round Robin Nash Confidence Bound ($\mathtt{\text{RR-NCB}}$), combines round robin exploration with a Nash confidence bound index policy. We show ${\widetilde{\mathrm{N}\mathrm{R}}}_T\le \tilde{\mathcal{O}}(\sqrt{k\log T\mathrm{/}T})$ and, with probability $1-\delta$, ${\widehat{\mathrm{N}\mathrm{R}}}_T\le \tilde{\mathcal{O}}(\sqrt{k\log (kT\mathrm{/}\delta )\mathrm{/}T})$, matching the optimal $\tilde{\mathcal{O}}(\sqrt{k\mathrm{/}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.