REVIEW 4 major objections 4 minor 28 references
p-Mean Regret for Stochastic Bandits
T0 review · 4 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read The paper proves that a single two-phase algorithm, Explore-then-UCB, achieves near-optimal $p$-mean regret for every $p\leq 1$, unifying average regret and Nash regret under one fairness-efficiency parameter.
desk verdict The p-mean regret framework is a good idea and the positive-p results look right, but the headline negative-p theorem rests on a concrete algebra error and the exponents don't match across abstract, theorem, and conclusion. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the $p$-mean regret $R_p = \mu^* - \left(\frac{1}{T}\sum_{t=1}^T (\mathbb{E}[\mu_{I_t}])^p\right)^{1/p}$, a power-mean aggregation of expected rewards that interpolates from utilitarian ($p=1$) to Rawlsian ($p\to -\infty$) evaluation. The mechanism that carries the argument is Explore-then-UCB: a uniform exploration phase of length $\tilde T$ followed by UCB1, together with the good event $G=G_1\cap G_2$ and Lemma 3 ('only good arms in phase two'), which guarantees that arms pulled after exploration have mean within $O(\sqrt{\log T/(T_i-1)})$ of $\mu^*$. This lemma is what turns the negative-$p$ case into a sum-of-inverse-means bound, and it is exactly where Assumption 1 (a lower bound on all arm means) is needed, to keep the key quantity $\mu^*-\beta$ positive.
What would settle it
Simulate Explore-then-UCB with the paper's exploration periods on a two-armed instance with means $1$ and $T^{-1/2}$ for increasing $T$ (for example $T=10^6$, where $T^{-1/2}$ lies below the Assumption 1 threshold) and compute the $p=-1$ harmonic-mean regret; if the regret does not vanish at the claimed rate, Assumption 1 is genuinely load-bearing, and if it does vanish, the assumption is stronger than needed.
Extended reading notes
Core claim
The central claim is that the entire $p$-mean regret spectrum for $p\le 1$ can be minimized by a single algorithm: explore every arm uniformly for a period $\tilde T$ that depends on $p$, $k$, and $T$, then run UCB1. The proof rests on a 'good event' in which Phase I samples every arm enough and all empirical means stay within $O(\sqrt{\log T/s})$ of their true values; on that event, Lemma 3 shows that every arm pulled in Phase II has mean at least $\mu^* - 6\sqrt{\log T/(T_i-1)}$, so the power mean of the selected arms stays close to the optimal mean. Choosing the exploration period as $\tilde T = 16\sqrt{T k^p \log T/\log k}$ for $p>0$ and $16\sqrt{T \log T/k^{|p|}}$ for $p<0$ balances the fairness cost of exploration against the accuracy it buys, yielding the stated upper bounds. The Nash case ($p\to 0$) follows as a limit and matches the regret of a purpose-built Nash confidence-bound algorithm up to constants, using only the standard UCB confidence bound after exploration.
Load-bearing premise
The load-bearing premise is Assumption 1: every arm's expected reward must be at least about $32\sqrt{k\log T\,\log k}/T^{1/4}$; if any arm has a lower mean, the good event and the 'only good arms' lemma that support the negative-$p$ bounds no longer hold, so the regret guarantees can fail.
Editorial extensions
If this is right
- For $0<p\le 1$, Explore-then-UCB attains the minimax average-regret rate $\tilde O(\sqrt{k/T})$ up to log factors, so adding fairness for positive $p$ costs nothing in regret scaling.
- Nash regret, the $p\to 0$ case, is handled by the same algorithm at rate $\tilde O(\sqrt{k/T})$, matching the dedicated Nash confidence-bound algorithm up to constants without a new confidence bound.
- For $-1<p<0$ and $p\le -1$, the algorithm gives unified upper bounds on $p$-mean regret, with rates $\tilde O(k^{3/4}/T^{1/4})$ and $\tilde O(\sqrt{k}\,T^{-1/(4|p|)})$ respectively.
- Because $p$-mean regret with $p\le 1$ satisfies the Pigou-Dalton principle, the same algorithm family can be tuned to respect a designer-chosen degree of equity across rounds, from average welfare to worst-round welfare.
- The exploration period is shorter for more negative $p$, so the algorithm spends less time on uniform exploration exactly when the metric punishes low-reward rounds most heavily.
Reading between the lines
- The analysis is asymptotic: for fixed $k$, Assumption 1's threshold $32\sqrt{k\log T\,\log k}/T^{1/4}$ tends to zero, but for the finite horizons in the paper's own experiments (e.g. $k=50$, $T=20{,}000$) the threshold exceeds 1, so the experiments operate outside the theorem's stated assumptions; this makes the empirical tables a test of practical behavior rather than a verification of the bounds
- If the same two-phase template works with any average-regret minimizer replacing UCB1, as the paper suggests in its conclusion, then $p$-mean regret guarantees could be imported to linear, contextual, and other structured bandits by inheriting their average-regret bounds.
- For growing $k$, Assumption 1 and the negative-$p$ bounds interact: with $k\approx T$, the threshold $32\sqrt{k\log T\,\log k}/T^{1/4}$ grows rather than vanishes, and the claimed $p\le -1$ rate $\tilde O(\sqrt{k}\,T^{-1/(4|p|)})$ need not go to zero; characterizing the exact $k$-$T$ tradeoff is a natural next step.
- A prior counterexample shows plain UCB1 can suffer Nash regret close to $1-1/T$; the assumption of a positive minimum mean is what excludes that failure mode, so the theorem's domain is exactly the regime where the fairness metric is not dominated by near-zero arms.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper defines a p-mean regret objective for stochastic multi-armed bandits, generalizing average cumulative regret (p=1) and Nash regret (p→0). It proposes a two-phase Explore-then-UCB algorithm and claims upper bounds for all p≤1: O~(√(k/T)) for 0<p≤1, O~(k^{3/4}/T^{1/4}) for -1≤p<0, O~(√k/T^{1/(4|p|)}) for p≤-1, and O~(√(k/T)) for Nash regret, under an assumption that all arm means are bounded below by a T^{-1/4}-decaying quantity. The paper also reports small synthetic experiments comparing Explore-then-UCB with UCB1 and NCB.
Significance. The p-mean regret formulation is a natural and appealing extension of Nash regret, and a single simple algorithm covering the whole fairness-efficiency spectrum would be a useful contribution. The lower-bound observation that p-mean regret dominates average regret for p≤1 is correct, and the authors should be credited for making the framework precise and for releasing code for their experiments. However, the paper's central technical claims are not established by the proofs given. The proof of the main negative-p theorem (Theorem 4) contains a concrete algebraic error in the q>1 case, the proof for 0<p<1 uses a reversed convexity inequality, and the Nash-regret proof appears to rely on an incorrect Phase-I lower bound. These are load-bearing problems, not presentation issues, and they affect the advertised results across the whole p≤1 range.
major comments (4)
- [Regret analysis of p-mean regret for p < 0, proof of Theorem 4, q>1 case] The step after substituting ~T = 16√(T log T)/k^q is algebraically wrong. The displayed bound contains β = 6√(2k log T/~T), which is Θ(k^{(q+1)/2} T^{-1/4}). After taking the 1/q-th power, this term contributes k^{(q+1)/(2q)} T^{-1/(4q)} = k^{1/2+1/(2q)} T^{-1/(4q)}, not k^{1/2} T^{-1/(4q)}. The proof's justification, 'since 1/4+1/(2q)≤1/2 for q≥1', is false for every 1<q<2 (e.g., at q=3/2 it gives 7/12>1/2), and even its form seems to assume an exponent k^{1/4+1/(2q)} rather than the actual k^{1/2+1/(2q)}. The proof also writes k^{q/4} where the calculation gives k^{(q+1)/2}. Thus the claimed \~O(√k/T^{1/(4q)}) bound for q>1 is not derived.
- [Assumption 1 and the proof of Lemma 3/Theorem 4] The proof repeatedly asserts that Assumption 1 implies β/μ* ≤ 1/2 and μ* - β > 0. With β = Θ(k^{(q+1)/2} T^{-1/4}) and μ_min = Θ(√(k log T)/T^{1/4}) under Assumption 1, the ratio is β/μ* = Θ(k^{q/2}/√(log T)). This is ≤1/2 only when T is exponentially large in k^q (or, if k is fixed, in a T→∞ limit that is not stated in the theorem). Since Theorem 4 states a bound as a function of both k and T without such a qualification, the steps requiring μ*-β>0, the lower bound on (μ*-β)^q, and the use of the Weierstrass inequality are not justified in the stated parameter regime.
- [Appendix, proof of Theorem 8 (0<p≤1 case)] The proof of the 0<p<1 case uses the inequality (μ*-β_i)^p ≥ (μ*)^p - pβ_i(μ*)^{p-1}. For 0<p<1, x↦x^p is concave, so the tangent at μ* gives the opposite inequality: (μ*-β_i)^p ≤ (μ*)^p - pβ_i(μ*)^{p-1}. For example with μ*=1, β=0.25, p=0.5, the left side is ≈0.866 and the right side is 0.875. The displayed lower bound on y is therefore invalid, and the p-mean regret bound for 0<p<1 is not proved by the argument given. The p=1 case reduces to standard average regret and is unaffected, but the claimed range p∈(0,1] is not established.
- [Appendix, Nash-regret proof, Eq. (8)] The Nash-regret proof asserts that the Phase-I contribution satisfies (∏_{t=1}^{~T} E[μ_{I_t}])^{1/T} ≥ (μ*)^{~T/T}(1 - 16√(k log k log T)/√T). But under Algorithm 1's Phase I, which samples I_t uniformly from [k], one has E[μ_{I_t}] = (1/k)Σ_{i=1}^k μ_i for every t≤~T, not μ*. The best uniform-exploration lower bound is (k^{-1}Σ_i μ_i)^{~T/T}, which can be much smaller than (μ*)^{~T/T} when there is a single high-mean arm and many low-mean arms. The appeal to the NCB analysis of Barman et al. 2023 does not repair this because the algorithm's Phase I is stated to be identical uniform exploration. Consequently Theorem 6/7 is not proved by the given argument.
minor comments (4)
- [Theorem 4 statement and proof] The theorem statement places q=1 in the first case, while the proof treats q=1 in the q≥1 case and concludes only for q>1; the two cases give different k-exponents at q=1 (k^{3/4} versus k^{1/2}), so the boundary case p=-1 is ambiguous.
- [Appendix organization] The appendix labels 'Lemma 2' as if it proves the good event G, while the main text defines Lemma 2 as UCB correctness and Lemma 1 as the good-event probability; the proofs are not clearly separated and the reader has to infer which lemma is being proved.
- [Notation and typesetting] There are several typographical issues, including inconsistent use of K and k, unclear radicals in Assumption 2 (e.g., '16√√T/log k'), and equation references that do not match between the main text and appendix; these should be cleaned up in any revision.
- [Assumption 1 discussion] The paper acknowledges that UCB fails on the Barman et al. counterexample and that Assumption 1 excludes low-mean arms, but it should explicitly discuss that this is precisely the regime where fairness objectives are most relevant; as written, the negative-p results are conditional on an assumption that excludes a substantial part of the motivating applications.
Circularity Check
No significant circularity: the p-mean regret bounds are derived from explicit assumptions and standard UCB analysis; the only circularity-adjacent element is a minor non-load-bearing self-citation to Barman et al. (2020).
-
other
[Contributions, range-of-p discussion citing Proposition 1 of Barman et al. (2020)]
"As p decreases beyond −T log T , the p-mean welfare for any bandit instance becomes a constant factor approximation of egalitarian welfare. Consequently, achieving vanishing p-mean regret is not possible with even two arms for p≤−T log T (see Proposition 1 in (Barman et al. 2020))."
This is a self-citation: Barman et al. (2020) includes current author Anand Krishna, and the proposition is invoked to delimit the range of p for which vanishing p-mean regret is impossible. It is not, however, load-bearing for the upper-bound proofs in Theorems 4-6: those theorems are proved directly from Assumptions 1-2 via the good-event argument and UCB1 analysis, and the cited proposition only places the boundary of the regime the authors claim to cover. Thus the self-citation is minor and does not make the central derivation circular.
full rationale
Theorems 4, 5, and 6 are derived from explicit assumptions (Assumption 1 lower-bounds all arm means; Assumption 2 requires a sufficiently long exploration period) through Chernoff-Hoeffding concentration, the good event G=G1∩G2, and the UCB-correctness lemma; the final regret expressions follow by substituting the chosen exploration period. No parameter is fitted to data and then renamed a prediction, and no theorem's conclusion is assumed in its hypotheses. The 0<p≤1 bound matches the average-regret lower bound via the generalized-mean inequality, a legitimate reduction rather than a circular definition. The only circularity-adjacent element is the citation of Proposition 1 from Barman et al. (2020), a paper co-authored by one of the present authors; it is used only to state the range of p for which vanishing regret is impossible and is not needed for the main upper-bound derivations. The algebraic issue in Theorem 4 flagged by reviewers (the inequality 1/4+1/(2q)≤1/2 is false for 1<q<2) is a correctness risk, not a circularity, and is outside this pass's scope.
Assumptions & free parameters
assumptions (4)
- domain assumption Assumption 1: μ_i ≥ 32√(k log T)√(log k)/T^{1/4} for all arms i
- domain assumption Assumption 2: exploration period \tilde T ≥ 8k log(Tk) + 16√(T/log k)
- standard math Unproved Claim 2 from Barman et al. 2023
- standard math Standard concentration inequalities (Chernoff, Hoeffding) and Jensen, Weierstrass, Cauchy-Schwarz inequalities
Cite this review
Pith. "Pith review of p-Mean Regret for Stochastic Bandits." pith.science (2026). https://pith.science/paper/KZRLSKWB
@misc{pith2026241210751,
author = {Pith},
title = {Pith review of: p-Mean Regret for Stochastic Bandits},
year = {2026},
howpublished = {\url{https://pith.science/paper/KZRLSKWB}},
note = {Machine review of arXiv:2412.10751}
}
abstract
In this work, we extend the concept of the $p$-mean welfare objective from social choice theory (Moulin 2004) to study $p$-mean regret in stochastic multi-armed bandit problems. The $p$-mean regret, defined as the difference between the optimal mean among the arms and the $p$-mean of the expected rewards, offers a flexible framework for evaluating bandit algorithms, enabling algorithm designers to balance fairness and efficiency by adjusting the parameter $p$. Our framework encompasses both average cumulative regret and Nash regret as special cases. We introduce a simple, unified UCB-based algorithm (Explore-Then-UCB) that achieves novel $p$-mean regret bounds. Our algorithm consists of two phases: a carefully calibrated uniform exploration phase to initialize sample means, followed by the UCB1 algorithm of Auer, Cesa-Bianchi, and Fischer (2002). Under mild assumptions, we prove that our algorithm achieves a $p$-mean regret bound of $\tilde{O}\left(\sqrt{\frac{k}{T^{\frac{1}{2|p|}}}}\right)$ for all $p \leq -1$, where $k$ represents the number of arms and $T$ the time horizon. When $-1<p<0$, we achieve a regret bound of $\tilde{O}\left(\sqrt{\frac{k^{1.5}}{T^{\frac{1}{2}}}}\right)$. For the range $0< p \leq 1$, we achieve a $p$-mean regret scaling as $\tilde{O}\left(\sqrt{\frac{k}{T}}\right)$, which matches the previously established lower bound up to logarithmic factors (Auer et al. 1995). This result stems from the fact that the $p$-mean regret of any algorithm is at least its average cumulative regret for $p \leq 1$. In the case of Nash regret (the limit as $p$ approaches zero), our unified approach differs from prior work (Barman et al. 2023), which requires a new Nash Confidence Bound algorithm. Notably, we achieve the same regret bound up to constant factors using our more general method.
Reference graph
Works this paper leans on
-
[1]
, " * write output.state after.block = add.period write newline
ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...
-
[2]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...
-
[3]
Auer, P.; Cesa-Bianchi, N.; and Fischer, P. 2002. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47: 235--256
work page 2002
-
[4]
Auer, P.; Cesa-Bianchi, N.; Freund, Y.; and Schapire, R. E. 1995. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of IEEE 36th annual foundations of computer science, 322--331. IEEE
work page 1995
-
[5]
Barman, S.; Bhaskar, U.; Krishna, A.; and Sundaram, R. G. 2020. Tight approximation algorithms for p-mean welfare under subadditive valuations. arXiv preprint arXiv:2005.07370
work page Pith review arXiv 2020
-
[6]
Barman, S.; Khan, A.; and Maiti, A. 2022. Universal and tight online algorithms for generalized-mean welfare. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, 4793--4800
work page 2022
-
[7]
Barman, S.; Khan, A.; Maiti, A.; and Sawarni, A. 2023. Fairness and welfare quantification for regret in multi-armed bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, 6762--6769
work page 2023
-
[8]
Bubeck, S.; Cesa-Bianchi, N.; et al. 2012. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning , 5(1): 1--122
work page 2012
Show all 28 references
-
[9]
Bubeck, S.; Munos, R.; and Stoltz, G. 2009. Pure exploration in multi-armed bandits problems. In Algorithmic Learning Theory: 20th International Conference, ALT 2009, Porto, Portugal, October 3-5, 2009. Proceedings 20, 23--37. Springer
2009
-
[10]
E.; Kapoor, S.; Salehi, F.; and Vishnoi, N
Celis, L. E.; Kapoor, S.; Salehi, F.; and Vishnoi, N. 2019. Controlling polarization in personalization: An algorithmic framework. In Proceedings of the conference on fairness, accountability, and transparency, 160--169
2019
-
[11]
Clement, B.; Roy, D.; Oudeyer, P.-Y.; and Lopes, M. 2013. Multi-armed bandits for intelligent tutoring systems. arXiv preprint arXiv:1310.3174
2013 arXiv
-
[12]
Eckart, O.; Psomas, A.; and Verma, P. 2024. On the Fairness of Normalized p-Means for Allocating Goods and Chores. arXiv preprint arXiv:2402.14996
2024
-
[13]
Garg, J.; Husi \'c , E.; Murhekar, A.; and V \'e gh, L. 2021. Tractable fragments of the maximum nash welfare problem. arXiv preprint arXiv:2112.10199
2021 arXiv
-
[14]
Hossain, S.; Micha, E.; and Shah, N. 2021. Fair algorithms for multi-agent multi-armed bandits. Advances in Neural Information Processing Systems, 34: 24005--24017
2021
-
[15]
Jones, M.; Nguyen, H.; and Nguyen, T. 2023. An efficient algorithm for fair multi-agent multi-armed bandit with low regret. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, 8159--8167
2023
-
[16]
H.; and Roth, A
Joseph, M.; Kearns, M.; Morgenstern, J. H.; and Roth, A. 2016. Fairness in learning: Classic and contextual bandits. Advances in neural information processing systems, 29
2016
-
[17]
Kaneko, M.; and Nakamura, K. 1979. The Nash social welfare function. Econometrica: Journal of the Econometric Society, 423--435
1979
-
[18]
Kozma, L. 2021. Useful Inequalities
2021
-
[19]
L.; and Robbins, H
Lai, T. L.; and Robbins, H. 1985. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1): 4--22
1985
-
[20]
Lattimore, T.; and Szepesv \'a ri, C. 2020. Bandit algorithms. Cambridge University Press
2020
-
[21]
Mandal, D.; and Gan, J. 2022. Socially fair reinforcement learning. arXiv preprint arXiv:2208.12584
2022 arXiv
-
[22]
Moulin, H. 2004. Fair division and collective welfare. MIT press
2004
-
[23]
Patil, V.; Ghalme, G.; Nair, V.; and Narahari, Y. 2021. Achieving fairness in the stochastic multi-armed bandit problem. Journal of Machine Learning Research, 22(174): 1--31
2021
-
[24]
Sawarni, A.; Pal, S.; and Barman, S. 2024. Nash regret guarantees for linear bandits. Advances in Neural Information Processing Systems, 36
2024
-
[25]
M.; Bradlow, E
Schwartz, E. M.; Bradlow, E. T.; and Fader, P. S. 2017. Customer acquisition via display advertising using multi-armed bandit experiments. Marketing Science, 36(4): 500--522
2017
-
[26]
Thompson, W. R. 1933. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4): 285--294
1933
-
[27]
S.; Bowden, J.; and Wason, J
Villar, S. S.; Bowden, J.; and Wason, J. 2015. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical science: a review journal of the Institute of Mathematical Statistics, 30(2): 199
2015
-
[28]
D.-C.; and Luo, H
Zhang, M.; Vuong, R. D.-C.; and Luo, H. 2024. No-Regret Learning for Fair Multi-Agent Social Welfare Optimization. arXiv preprint arXiv:2405.20678
2024 arXiv
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.