Research map / Bandits and online learning / Multi-armed bandits

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

NeurIPS 2026 · Bandits and online learning › Multi-armed bandits · approach: Optimal stochastic bandit algorithms

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces trajectory-wise and high-probability Nash regret for fair bandits and proposes RR-NCB, claiming O~(sqrt(k/T)) bounds for both under a positivity floor on arm means.

Problem

Existing Nash regret for fair bandits takes expectation before the geometric mean, so it does not capture the joint trajectory-level distribution of rewards; no high-probability Nash regret bounds exist.

Approach

Moves the expectation outside the geometric mean (trajectory-wise Nash regret), studies the pathwise geometric mean for high-probability bounds, and uses a round-robin-then-Nash-confidence-bound algorithm (RR-NCB) whose analysis reduces both to cumulative log-regret.</novel_idea>

Key results

• Trajectory-wise Nash regret upper bound O(sqrt(k log T / T)) plus lower-order terms for RR-NCB (Theorem 1).
• High-probability Nash regret bound C' sqrt(k log(kT/delta)/T) holds with probability 1-delta (Theorem 2).
• Simulations (200 seeds, mu*=0.9) show trajectory-wise Nash regret exceeds ensemble Nash regret at small T, with the gap shrinking as T grows.

Surprising findings

• Without a positivity floor on arm means, no algorithm can drive trajectory-wise Nash regret to zero, which the authors show via a proposition.

Limitations

• Requires a positivity floor mu_min on arm means; regret depends on log(1/mu_min) in lower-order terms.
• Results are instance-independent; instance-dependent logarithmic bounds left open.
• Validation limited to simulations on synthetic Bernoulli-like instances.

Experimental setup

Benchmarks: simulated stochastic bandit instances

Metrics: trajectory-wise Nash regret ensemble Nash regret

Baselines: NCB ensemble Nash regret algorithm

Builds on: Nash regret (Barman et al.) NCB algorithm p-mean regret

Closest papers by meaning

• Fairness and Welfare Quantification for Regret in Multi-Armed Bandits (AAAI 2023 · similarity 0.95)
• Nash Regret Guarantees for Linear Bandits (NeurIPS 2023 · similarity 0.94)
• p-Mean Regret for Stochastic Bandits (AAAI 2025 · similarity 0.92)
• No-Regret Learning for Fair Multi-Agent Social Welfare Optimization (NeurIPS 2024 · similarity 0.91)
• Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (NeurIPS 2025 · similarity 0.90)
• Honor Among Bandits: No-Regret Learning for Online Fair Division (NeurIPS 2024 · similarity 0.89)