{"id":"2aa02e1f-5949-4f0d-ae8b-e69aa1ea284b","arxiv_id":"2412.10751","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A new p-mean regret framework for stochastic bandits is proposed with an Explore-then-UCB algorithm, but the headline negative-p bounds are not reliably derived.","lead":"The authors introduce a p-mean regret metric for multi-armed bandits, interpolating between average regret and Nash regret, and analyze a simple Explore-then-UCB algorithm. They prove regret bounds for all p ≤ 1, but the negative-p proofs contain algebraic errors and the experiments appear flawed.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's p≤−1 bound is not derived: the proof uses 1/4+1/(2q)≤1/2 for q≥1, which is false for 1<q<2, and the β term gives a k-exponent larger than √k.","rationale":"I read the paper in good faith. The p-mean regret framework is clearly motivated, and the p∈(0,1] results (Theorem 5) and the Nash-regret theorem are plausible and largely consistent with standard UCB analyses. The experiments, while limited, do not contradict the framework. However, the paper's distinctive contribution is the negative-p regime, and there the proof of Theorem 4 has an internal algebraic inconsistency: the final exponent step uses 1/4+1/(2q)≤1/2 for all q≥1, which is false for 1<q<2, and the β term's k-dependence is not compatible with the claimed √k rate. This is not a disagreement with external consensus; it is a failure of the proof as written to establish the stated theorem. The reader's weakest-assumption point about Assumption 1 is also valid, but I regard the proof algebra as the more load-bearing issue: even granting the assumption, the claimed negative-p bounds are not derived. Because the central claim depends on Theorem 4, and the proof gap is concrete and checkable, the REJECT verdict is supported. I therefore recommend no change to the reader's verdict.","tokens_in":19768,"tokens_out":13630,"duration_ms":120639,"concrete_test":"Re-derive the q>1 branch of Theorem 4 for the concrete value q=3/2, keeping the exact β term β = 6√(2k log T / ˜T). Substitute ˜T = 16√(T log T)/k^{3/2}, take μ* = 1, and evaluate the displayed bound R_q ≤ μ*·( ((k^q−1)˜T)/T + c/T + qβ/μ* )^{1/q}. The β term alone is Θ(k^{5/4} T^{−1/4} (log T)^{1/4}); raising it to the power 1/q=2/3 gives Θ(k^{5/6} T^{−1/6}), whereas the theorem claims O˜(k^{1/2} T^{−1/6}). The k-exponent discrepancy (5/6 vs 1/2) shows the proof cannot yield the stated rate on the stated range 1<q<2. If the check instead reveals an extra assumption on T (e.g. T ≥ k^{2(q+1)}(log T)^{...}) that restores the stated rate, the theorem needs to be re-stated with that condition.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central novelty of the paper is the negative-p regret theorem (Theorem 4), and its proof for q>1 has a concrete algebraic failure. After deriving R_q ≤ μ*·( ((k^q−1)˜T)/T + c/T + qβ/μ* )^{1/q}, the proof substitutes ˜T = 16√(T log T)/k^q and claims the result is O˜(√k T^{−1/(4q)}) with the justification 'since 1/4 + 1/(2q) ≤ 1/2 for q≥1'. That inequality is false for every 1<q<2: e.g. at q=3/2, 1/4+1/(2q)=1/4+1/3=7/12>1/2. This is not a cosmetic detail: it is exactly the step that converts the k-exponent of the β-term into √k. With the correct algebra, β = 6√(2k log T / ˜T) = Θ(k^{(q+1)/2} (log T)^{1/4} T^{−1/4}), so the term inside the q-th root contributes k^{1/2+1/q} after the root is taken, and multiplying by μ* still leaves k^{1/4+1/(2q)} unless μ* is assumed to saturate a lower bound. That exceeds k^{1/2} for all q>1, so the claimed √k scaling is not established. In addition, Assumption 1 does not by itself imply μ*−β>0 for q≥1 in the range k,T where the proof is applied; the ratio β/μ* can be large unless T is exponentially large in k, a regime not stated in the theorem. Because Theorem 4 is the paper's main claimed advance over prior Nash-regret work, this gap undermines the central claim as stated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":20181,"tokens_out":20775,"duration_ms":181824,"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":[{"comment":"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.","section":"Regret analysis of p-mean regret for p < 0, proof of Theorem 4, q>1 case"},{"comment":"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.","section":"Assumption 1 and the proof of Lemma 3/Theorem 4"},{"comment":"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.","section":"Appendix, proof of Theorem 8 (0<p≤1 case)"},{"comment":"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.","section":"Appendix, Nash-regret proof, Eq. (8)"}],"minor_comments":[{"comment":"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.","section":"Theorem 4 statement and proof"},{"comment":"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.","section":"Appendix organization"},{"comment":"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.","section":"Notation and typesetting"},{"comment":"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.","section":"Assumption 1 discussion"}],"recommendation":"reject","confidential_remarks":"The manuscript is not ready for publication. The advertised negative-p theorem (Theorem 4) has a clear algebraic error in the q>1 case, the 0<p<1 proof uses a reversed convexity inequality, and the Nash-regret proof appears to rely on an incorrect Phase-I lower bound. These are not merely local gaps: they affect the paper's central claims across the whole p≤1 range. A revision that corrects these issues would need to change the main results, the algorithm's exploration schedule, or the assumptions, so I recommend rejection rather than major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the p-mean regret framework is genuinely new and worth having, and the p∈(0,1] and Nash pieces look right. But the headline negative-p theorem (Theorem 4) has a concrete algebraic failure, and the exponents in the abstract, theorem statement, and conclusion don't even agree.\n\nThe main contribution is the objective itself: p-mean regret interpolating between average regret and Rawlsian/worst-case behavior, with Nash regret as the p→0 limit. That's a natural and useful extension of Barman et al. 2023, and the two-phase Explore-then-UCB algorithm is a reasonable simple candidate. The p∈(0,1] bound Õ(√(k/T)) follows from standard UCB analysis plus the generalized mean inequality — that part is fine. The Nash bound, Õ(√(k/T)) with a uniform exploration phase, is also plausible and matches prior work up to constants.\n\nThe problem is Theorem 4. The proof substitutes ~T=16√(T log T)/k^q into R_q ≤ ... The β term becomes Θ(k^{(q+1)/2} (log T)^{1/4}/T^{1/4}), not the k^{q/4} term in the write-up. After the 1/q root the k-exponent is 1/2+1/(2q), which is larger than 1/2 for any q>1. The line 'since 1/4+1/(2q)≤1/2 for q≥1' is simply false for 1<q<2. So the claimed √k scaling for p≤-1 is not established. To make it worse, the theorem statement says T^{-1/(2q)} while the abstract and conclusion promise T^{-1/(4q)} — a factor-of-two discrepancy in the time exponent. That's not a cosmetic detail; the abstract's advertised bound is what reviewers will remember.\n\nOther soft spots: Assumption 1 (μ_i ≥ 32√(k log T log k)/T^{1/4}) is load-bearing and rules out low-mean arms — the regime where fairness concerns are sharpest. It's true asymptotically for fixed k, but it changes the problem. The experiments share identical p=0 values (0.964, 0.653, 0.909, 0.940) across UCB1, NCB, and EUCB, which looks like an artifact, and there are no error bars.\n\nI don't think there's a circularity problem; the lower bound for p≤1 is honestly inherited from average regret. The citation pattern looks fine, and the authors are transparent about the UCB counterexample.\n\nWho should read this? Anyone working on fairness metrics for bandits will want the p-mean regret definition. But as a paper, the central claim isn't supported. I'd send it to a serious referee, but the verdict should be reject with an invitation to resubmit after the negative-p proof is fixed and the exponents are reconciled. The framework is worth keeping alive; the current proof isn't.","headline":"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.","tokens_in":20752,"tokens_out":5476,"would_cite":false,"duration_ms":44577,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["p-mean regret","Nash regret","stochastic multi-armed bandits","UCB1","fairness","power mean","Explore-then-UCB","social welfare"],"falsifier":"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.","tokens_in":19548,"feed_emoji":"⚖️","tokens_out":11518,"duration_ms":91862,"temperature":0.7,"pith_summary":"This paper introduces $p$-mean regret for stochastic multi-armed bandits, a welfare-style objective that contains average regret at $p=1$, Nash regret in the limit $p\\to 0$, and increasingly egalitarian metrics as $p$ becomes negative. It proves that one simple algorithm, Explore-then-UCB, achieves vanishing $p$-mean regret across the whole range $p\\leq 1$: under an assumption that all arm means are bounded away from zero at a rate depending on $k$ and $T$, the regret scales as $\\tilde{O}(\\sqrt{k/T})$ for $0<p\\leq 1$ and for Nash regret, as $\\tilde{O}(k^{3/4}/T^{1/4})$ for $-1<p<0$, and as $\\tilde{O}(\\sqrt{k}\\,T^{-1/(4|p|)})$ for $p\\leq -1$. A sympathetic reader would care because this bundles previously separate analyses of average and Nash regret into a single fairness-efficiency dial, and shows that a calibrated uniform exploration phase rescues the standard UCB1 algorithm for fairness-sensitive metrics.","feed_headline":"Explore then UCB1 yields vanishing p-mean regret for all p≤1","feed_subtitle":"A single two-phase recipe matches average-regret and Nash-regret rates, with p as the fairness-efficiency dial.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the UCB1 algorithm and its confidence-bound analysis, the Phase II subroutine the whole construction is built on.","marker":"Auer, Cesa-Bianchi, and Fischer (2002)"},{"why":"Defines Nash regret, gives the Nash confidence-bound algorithm this work generalizes, and provides the counterexample showing vanilla UCB1 can have Nash regret close to 1.","marker":"Barman et al. (2023)"},{"why":"Provides the axiomatic p-mean welfare framework from social choice theory that motivates defining p-mean regret.","marker":"Moulin (2004)"},{"why":"The minimax lower bound for average regret that the p>0 bound matches up to log factors.","marker":"Auer et al. (1995)"},{"why":"Supplies the canonical bandit model and the standard regret-analysis lemmas (e.g. Lemma 8.2) that Lemma 3 strengthens.","marker":"Lattimore and Szepesvári (2020)"},{"why":"Gives Proposition 1, used to show that vanishing p-mean regret is impossible for p ≤ -T log T even with two arms.","marker":"Barman et al. (2020)"}],"fun_headline_variants":["One algorithm minimizes p-mean regret for every p≤1","Explore-then-UCB nails p-mean regret across the whole spectrum","A single recipe for fairness-efficiency in bandits: p-mean regret","Unified UCB approach matches Nash regret without new algorithms","Power-mean regret tamed: Explore once, then UCB1"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["One algorithm minimizes p-mean regret for every p≤1","Explore-then-UCB nails p-mean regret across the whole spectrum","A single recipe for fairness-efficiency in bandits: p-mean regret","Unified UCB approach matches Nash regret without new algorithms","Power-mean regret tamed: Explore once, then UCB1"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000679,"raw_usage":{"total_tokens":3216,"prompt_tokens":1207,"completion_tokens":2009,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":823,"completion_tokens_details":{"reasoning_tokens":1916}},"tokens_in":823,"tokens_out":2009,"duration_ms":12785,"temperature":1.0,"reasoning_tokens":1916,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T15:40:31.643376+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the UCB1 algorithm and its confidence-bound analysis, the Phase II subroutine the whole construction is built on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines Nash regret, gives the Nash confidence-bound algorithm this work generalizes, and provides the counterexample showing vanilla UCB1 can have Nash regret close to 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the axiomatic p-mean welfare framework from social choice theory that motivates defining p-mean regret."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The minimax lower bound for average regret that the p>0 bound matches up to log factors."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the canonical bandit model and the standard regret-analysis lemmas (e.g. Lemma 8.2) that Lemma 3 strengthens."},{"cited_title":"Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations","cited_arxiv_id":"2005.07370","evidence_quote":"Gives Proposition 1, used to show that vanishing p-mean regret is impossible for p ≤ -T log T even with two arms."}],"review_version":1}