Research map / Bandits and online learning / Multi-armed bandits
No-Regret Learning for Fair Multi-Agent Social Welfare Optimization
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.
Studies online multi-agent Nash social welfare maximization, giving tight-in-T stochastic UCB regret, impossibility under adversarial bandit feedback, and sqrt(T) full-information algorithms via FTRL with log-barrier or Tsallis regularizers.
Problem
Online multi-agent Nash social welfare (geometric mean of expected agent utilities) maximization in multi-armed bandits, where prior work only handled the product of utilities; the non-Lipschitz NSW objective makes standard regret analysis fail.
Approach
Replaces the Lipschitz-based analysis of product-welfare UCB with a Bernstein-type confidence width and a two-case decomposition to handle non-Lipschitz NSW; in the adversarial full-information setting, FTRL with a log-barrier (or Tsallis entropy) regularizer gives a small local norm despite unbounded gradients.
Key results
- Stochastic bandit UCB with Bernstein-type widths achieves Õ(K^{2/N} T^{(N-1)/N}) regret for NSW, with a matching Ω̃(T^{(N-1)/N}) lower bound in T.
- With adversarial bandit feedback, Ω(T) regret is unavoidable for NSW (and for product welfare), so no sublinear-regret algorithm exists.
- With full-information feedback, FTRL with log-barrier achieves O(sqrt(KT log T)) regret for any concave Pareto-optimal welfare function, independent of N; Tsallis FTRL gives Õ(K^{1/2-1/N} sqrt(NT)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Bernstein-type confidence intervals instead of Hoeffding-type confidence intervals (ablation) | UCB for stochastic NSW maximization · Stochastic N-agent K-armed bandits, bandit feedback | expected regret: \otil(K^{\frac{1}{2N}}T^{\frac{2N-1}{2N}}) -> \otil(K^{\frac{2}{N}}T^{\frac{N-1}{N}}+K) | Helped |
| Use UCB with Bernstein-type confidence intervals | NSW maximization · Stochastic N-agent K-armed bandits, bandit feedback | expected regret: \otil(K^{\frac{2}{N}}T^{\frac{N-1}{N}}+K); lower bound: \Omega\left(\frac{(\log K)^3}{N^3}\cdot K^{\frac{1}{N}}T^{\frac{ | Mixed |
| Use bandit feedback in the adversarial setting | NSW maximization · Adversarial N-agent K-armed bandits | expected regret: \Omega(T) | Hurt |
| Use full-information feedback with FTRL and a log-barrier regularizer | NSW and concave Pareto-optimal welfare functions · Adversarial N-agent K-armed bandits, full-information feedback | regret: \order(\sqrt{KT\log T}) | Helped |
| Use FTRL with a Tsallis entropy regularizer | NSW maximization · Adversarial N-agent K-armed bandits, full-information feedback | regret: \otil(K^{\frac{1}{2} - \frac{1}{N}} \sqrt{N T}) | Helped |
| Require at least M agents to be indifferent about the learner's arm choice each round | EWOO for NSW maximization · Adversarial N-agent K-armed bandits, full-information feedback | regret: \order\left(\frac{N - M}{M} \cdot K \log T\right) | Helped |
Surprising findings
- Despite NSW being concave, no algorithm achieves sublinear regret under adversarial bandit feedback, unlike bandit convex optimization where sqrt(T) is achievable.
- Stochastic NSW regret scales as T^{(N-1)/N}, polynomially worse than the sqrt(T) achievable for product welfare.
Limitations
- Stochastic upper and lower bounds match only in T; dependence on K and N is not tight.
- Tsallis bound has polynomial dependence on N, and log-barrier results apply to concave Pareto-optimal welfare functions only.
Experimental setup
Metrics: regret
Baselines: UCB for product welfare (Hossain et al. 2021) Jones et al. 2023 efficient UCB for product welfare
Builds on: UCB FTRL EWOO Hossain et al. 2021 product-welfare bandits
Closest papers by meaning
- An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret (AAAI 2023 · similarity 0.92)
- Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret (NeurIPS 2026 · similarity 0.91)
- Honor Among Bandits: No-Regret Learning for Online Fair Division (NeurIPS 2024 · similarity 0.88)
- Improved Regret Bounds for Online Fair Division with Bandit Learning (AAAI 2025 · similarity 0.88)
- p-Mean Regret for Stochastic Bandits (AAAI 2025 · similarity 0.87)
- Nash Incentive-compatible Online Mechanism Learning via Weakly Differentially Private Online Learning (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.