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 as a fairness-respecting performance metric. Existing formulations define Nash regret as $NR_T = \mu^\star - (\prod_{t=1}^T \mathbb{E}\mu_{I_t})^{1/T}$, where $\mu_{I_t}$ is the mean reward of the recommended arm $I_t$ and $T$ is the learning horizon. We observe that, since ensemble Nash regret operates on per-round marginal expectations before applying the geometric mean, it does not capture the joint distribution of rewards across rounds — leaving an aspect of the NSW fairness motivation unaddressed at the trajectory level. To address this, we propose \emph{trajectory-wise Nash regret} $\widetilde{NR_T}= \mu^\star - \mathbb{E}[(\prod_{t=1}^T \mu_{I_t})^{1/T}]$, where the geometric mean is computed over complete sample paths before taking expectations. This formulation captures the fairness properties of NSW more faithfully and requires controlling the joint distribution of rewards across rounds, rather than merely per-round marginals. By Jensen's inequality applied to the concave geometric mean, $\widetilde{NR_T} \geq NR_T$, making it a strictly stronger metric. We additionally introduce \emph{high probability Nash regret} $\widehat{NR_T} = \mu^\star - (\prod_t \mu_{I_t})^{1/T}$, obtaining the first high probability regret bounds in the fair bandits literature. We propose a two-phase algorithm, Round Robin Nash Confidence Bound (\texttt{RR-NCB}), combining structured round robin exploration with a Nash confidence bound index policy. We establish that $\widetilde{NR_T} \leq \widetilde{\mathcal{O}}(\sqrt{k\log T/T})$ and $\widehat{NR_T} \leq \widetilde{\mathcal{O}}(\sqrt{k\log(kT/\delta)/T})$ with probability $1-\delta$, matching the optimal $\widetilde{\mathcal{O}}(\sqrt{k/T})$ scaling despite operating under strictly stronger metrics. Optimality follows from a lower bound chain via AM-GM and standard $k$-armed bandit minimax arguments. We validate our theoretical findings through simulations.