pipette
ENEnglish

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

Avishek Ghosh

Preprint

En palabras de los autores

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 , where is the mean reward of the recommended arm and 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 , which computes the geometric mean over complete sample paths before taking expectations, capturing NSW fairness more faithfully. By Jensen's inequality, , making it a strictly stronger metric. We also introduce high probability Nash regret , giving the first high probability regret bounds in fair bandits. Our two-phase algorithm, Round Robin Nash Confidence Bound (RR-NCB), combines round robin exploration with a Nash confidence bound index policy. We show and, with probability , , matching the optimal rate despite the stronger metrics. Optimality follows from a lower bound via AM-GM and standard -armed bandit minimax arguments. Simulations validate our theory.

Resultado principalEl resumen no menciona limitaciones.

Apareció: miércoles, 7 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: Accepted at NeurIPS 2026