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

Key points

• Existing work defines Nash regret as $NRT = μ^\star - (\prod{t=1}^T \mathbb{E}μ{It})^{1/T}$, where $μ{It}$ is the mean reward of the recommended arm $It$ and $T$ is the horizon.1
• We propose trajectory-wise Nash regret $\widetilde{NR}T = μ^\star - \mathbb{E}[(\prod{t=1}^T μ{It})^{1/T}]$, which computes the geometric mean over complete sample paths before taking expectations, capturing NSW fairness more faithfully.1
• We also introduce high probability Nash regret $\widehat{NR}T = μ^\star - (\prodt μ{It})^{1/T}$, giving the first high probability regret bounds in fair bandits.1
• Our two-phase algorithm, Round Robin Nash Confidence Bound (RR-NCB), combines round robin exploration with a Nash confidence bound index policy.1

Sources (1)

• [1]Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret
  arXiv (AI, ML, NLP, CV, robotics, multi-agent) · Oct 6, 04:32 AM

  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 = μ^\star - (\prod_{t=1}^T \mathbb{E}μ_{I_t})^{1/T}$, where $μ_{I_t}$ is the mean reward of the recommended arm $I_t$ and $T$ is the horizon.

Extractive summary: sentences quoted from the sources.