Research map / Bandits and online learning / Multi-armed bandits
p-Mean Regret for Stochastic Bandits
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.
Extends p-mean welfare to bandit regret and proposes Explore-Then-UCB, a uniform-exploration-then-UCB1 algorithm with p-mean regret bounds across all p ≤ 1, including Nash regret as a special case.
Problem
Standard bandit objectives (average and simple regret) ignore fairness across rounds; the paper targets a regret measure that interpolates between utilitarian and egalitarian welfare via the p-mean of expected rewards.
Approach
Define p-mean regret as the gap between the optimal mean and the p-mean of per-round expected rewards, and show a simple calibrated uniform-exploration phase followed by UCB1 achieves bounds for all p ≤ 1 under a mild minimum-mean assumption, avoiding a specialized Nash Confidence Bound algorithm.
Key results
- Explore-Then-UCB achieves p-mean regret Õ(sqrt(k/T)) for p in (0,1] and Nash regret Õ(sqrt(k/T)), matching the lower bound up to log factors.
- For p ≤ -1 the bound is Õ(sqrt(k) T^{-1/(4|p|)}), and for -1<p<0 it is Õ(k^{1.5/2} T^{-1/2}) as stated in the paper.
- In experiments, EUCB is best or tied for negative p (e.g., Bernoulli-100k at p=-2: 0.242 vs UCB1 0.964 and NCB 0.409), while UCB1 is better for p=1 and 0.5.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Explore-Then-UCB (EUCB) instead of the strongest baseline | UCB1 or NCB · Bernoulli-100k, Triangular, Beta, and Uniform | p-mean regret (p=1): 0.214 -> 0.320; 0.139 -> 0.155; 0.306 -> 0.399; 0.240 -> 0.332 | Hurt |
| Use Explore-Then-UCB (EUCB) instead of the strongest baseline | UCB1 or NCB · Bernoulli-100k, Triangular, Beta, and Uniform | p-mean regret (p=0.5): 0.219 -> 0.322; 0.139 -> 0.139; 0.310 -> 0.312; 0.242 -> 0.247 | Mixed |
| Use Explore-Then-UCB (EUCB) instead of UCB1 | UCB1 · Bernoulli-100k, Triangular, Beta, and Uniform | Nash regret (p=0): 0.964 -> 0.964; 0.653 -> 0.653; 0.909 -> 0.909; 0.940 -> 0.940 | No clear effect |
| Use Explore-Then-UCB (EUCB) instead of the strongest baseline | UCB1 or NCB · Bernoulli-100k, Triangular, Beta, and Uniform | p-mean regret (p=-0.5): 0.359 -> 0.230; 0.141 -> 0.141; 0.315 -> 0.316; 0.335 -> 0.244 | Mixed |
| Use Explore-Then-UCB (EUCB) instead of the strongest baseline | UCB1 or NCB · Bernoulli-100k, Triangular, Beta, and Uniform | p-mean regret (p=-1): 0.377 -> 0.232; 0.142 -> 0.158; 0.320 -> 0.317; 0.244 -> 0.336 | Mixed |
| Use Explore-Then-UCB (EUCB) instead of the strongest baseline | UCB1 or NCB · Bernoulli-100k, Triangular, Beta, and Uniform | p-mean regret (p=-2): 0.409 -> 0.242; 0.144 -> 0.144; 0.325 -> 0.324; 0.255 -> 0.247 | Helped |
Surprising findings
- Vanilla UCB1 incurs near-constant Nash regret (about 1 - 1/T) on some instances, so plain UCB fails for negative p; the explore phase is needed.
- For p=1 and 0.5, plain UCB1 outperforms both the proposed EUCB and NCB in experiments, because uniform exploration is a handicap for positive p.
Limitations
- Requires an assumption that every arm's mean is at least on the order of sqrt(k log T / T^{1/4}) (effectively positive), which may not hold in general.
- Asymptotic analysis for T sufficiently large; no anytime or unknown-horizon guarantees.
- Experiments are limited to small synthetic instances with k=50 arms and a single seed setup.
Experimental setup
Datasets: synthetic bandit instances (Bernoulli, Triangular, Beta, Uniform) with k=50 arms
Benchmarks: synthetic stochastic bandit instances (k=50)
Metrics: p-mean regret for p in {1, 0.5, 0, -0.5, -1, -2}
Baselines: UCB1 NCB (Nash Confidence Bound)
Builds on: UCB1 Nash Confidence Bound p-mean welfare
Closest papers by meaning
- Nash Regret Guarantees for Linear Bandits (NeurIPS 2023 · similarity 0.93)
- Fairness and Welfare Quantification for Regret in Multi-Armed Bandits (AAAI 2023 · similarity 0.93)
- Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret (NeurIPS 2026 · similarity 0.92)
- Stochastic Multi-armed Bandits: Optimal Trade-off among Optimality, Consistency, and Tail Risk (NeurIPS 2023 · similarity 0.92)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.90)
- Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (NeurIPS 2025 · similarity 0.90)
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.