{"id":"af3d0b05-7754-46b8-84b6-0a34bddce750","arxiv_id":"2607.13402","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Negative-power-mean bandit regret is Θ(σ√(k^{max(1,q)}/T)) up to logs; UCB-HARE matches it.","lead":"Fair bandit algorithms are usually judged by average reward, which lets early rounds be sacrificed; this paper studies a stricter objective that penalizes any single bad round. It pins down the exact worst-case regret for this 'negative-power mean' objective and gives an algorithm that reaches that limit.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Minimax is undefined over the stated class: unbounded non-negative means make R_{T,-q} infinite for T≥1, so the claimed finite rate cannot hold as stated.","rationale":"The reader identified Assumption 1.1 as load-bearing, but focused on non-negativity of means. My concern is the separate missing condition of an upper bound on μ_*. Even with all means non-negative, the class ESG(k,σ)+ contains instances with arbitrarily large μ_*, and the negative-power objective makes regret scale with μ_* unless the algorithm can keep every round's ex-ante reward close to μ_*. For T=1, no algorithm can do better than m_1≤μ_*/k on the worst-case instance, so the minimax regret is infinite. This invalidates the central advertised claim of a finite tight minimax rate over the stated class. The technical machinery of the paper may well be correct for a bounded-mean class or for a normalized regret, but as written the theorems and abstract claim a μ_*-free worst-case rate that is not a consequence of the given assumptions. I would therefore not accept the paper in its current form; it should be revised to state explicitly the bounded-mean normalization or to reframe all claims as instance-dependent with μ_* dependence retained.","tokens_in":30512,"tokens_out":26877,"duration_ms":293735,"concrete_test":"Evaluate the minimax definition at T=1: for any algorithm, let p_i=P(I_1=i), choose the least-probable arm as the unique M-mean arm, and let M→∞. Then R_{1,-q}≥M(1−1/k)→∞, so the finite RHS claimed by the paper for T=1 is falsified. Alternatively, run UCB-HARE on a 2-arm instance with one arm mean M and the other 0, for q=2, T=10^6, σ=1, and M=10^3,10^6,10^9; if the observed regret grows with M while σ√(k^q/T) remains fixed, the claimed minimax rate over ESG(k,σ)+ is contradicted.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Assumption 1.1 only requires μ_i≥0 and μ_*>0; it imposes no upper bound on μ_*. Since M_{-q} is homogeneous and m_t=E[μ_{I_t}], consider T=1. For any algorithm, let p_i=P(I_1=i) and choose i*∈argmin_i p_i, so p_i*≤1/k. Set μ_i*=M, all other means 0, with N(μ,σ^2) rewards. Then the first-round ex-ante reward is m_1=M p_i*≤M/k, so R_{1,-q}≥M−M/k, which is unbounded as M→∞. Thus the minimax over ESG(k,σ)+ is infinite for every T≥1. Consequently, the paper's advertised μ_*-free rate σ√(k^{max(1,q)}/T) cannot be a uniform upper bound over the stated class. Theorem 5.1 is instance-dependent and retains μ_* terms; the introduction/abstract suppress these terms when reading as a minimax rate, while Corollary 5.2's μ_* k^q/T term already grows with μ_* and cannot be bounded uniformly. The results are salvageable only if the class is restricted to bounded means (e.g., μ_i∈[0,1]) or regret is normalized by μ_*, but no such restriction is stated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the strictly fair regime p=-q<0 of the generalized p-mean regret in stochastic k-armed bandits with nonnegative means and sigma-sub-Gaussian rewards. It claims a tight minimax rate sigma*sqrt(k^{max(1,q)}/T): a needle-in-haystack lower bound and a matching upper bound for a new algorithm, UCB-HARE, which combines a harmonic rank schedule with a certified positive-mean anchor. The main technical contributions are an information-cost inequality (Lemma 4.7) and a two-phase analysis that carefully handles the stopping time and the dependence between the block coin flips and the stopping event. The internal derivations appear consistent, but the minimax formulation is not valid as stated because the class ESG(k,sigma)+ has no upper bound on the optimal mean, making the finite-horizon minimax regret infinite.","tokens_in":1441,"tokens_out":1658,"duration_ms":175179,"significance":"If the unbounded-mean issue is repaired by an explicit bound on mu_* or by rephrasing the claims as instance-dependent/asymptotic, the paper would make a substantial contribution. The information-cost abstraction is clean and general, the lower bound is derived from first principles, and UCB-HARE's harmonic anchored exploration is a genuine algorithmic idea with a careful formal analysis. The predicted k^{q/2} penalty for q>1 is crisp and falsifiable. I did not find an internal gap in the main proof chain, but the discrepancy between the claimed 'minimax' rate and the actual theorems is central and must be fixed before publication.","major_comments":[{"comment":"The minimax regret over ESG(k,sigma)+ is infinite as stated. Since Assumption 1.1 imposes no upper bound on mu_*, take any algorithm and any k>=2, T=1. Let p_i=P(I_1=i) and choose i* with p_i*<=1/k. Set mu_*=M and all other means 0. Then m_1=M p_i*<=M/k and R_{1,-q}>=M(1-1/k), which is unbounded as M goes to infinity. Hence R_{T,-q}(k,sigma)=infinity for every T>=1, so no finite rate of the form sigma*sqrt(k^{max(1,q)}/T) can be a uniform upper bound over the stated class. The lower bound in Theorem 1.1 is not false, but it is vacuous as a 'minimax rate' statement, and the claimed matching upper bound cannot hold. The paper needs either (a) an explicit bounded-mean assumption (e.g., mu_i in [0,U]) with asymptotic statements for T sufficiently large, or (b) an explicit reframing of all upper bounds as instance-dependent, keeping the mu_*-dependent term.","section":"Section 1.2, Assumption 1.1, Theorem 1.1"},{"comment":"The advertised clean rate suppresses a mu_*-dependent term that is load-bearing. Theorem 5.1 gives R_{T,-q} <= C_q [ sigma*sqrt(H_k K_q(k) L/T) + mu_* H_k K_q(k)/T + mu_* delta ], and Corollary 5.2 for q>1 retains the term mu_* k^q/T. This term is not bounded uniformly over ESG(k,sigma)+ because mu_* is unbounded; it is also not dominated by sigma k^{q/2}/sqrt(T) for all T,k. Thus the abstract's claim that UCB-HARE achieves O_tilde(sigma*sqrt(k^{max(1,q)}/T)) is not a consequence of the stated theorems. The clean rate is only valid for a fixed instance and T large relative to mu_* (and, under a bounded-mean fix, for T sufficiently large). The authors should either state this qualification explicitly or prove a genuinely uniform bound over a bounded class.","section":"Abstract, Theorem 1.2, Corollary 5.2"}],"minor_comments":[{"comment":"The title line 'PRICE OFFAIRNESS INBANDITS' is missing spaces. The abstract also uses O_tilde without defining it; define it in Section 1 or 3.","section":"Title/Abstract"},{"comment":"The loop 'for slot h in (theta_b,1-theta_b) do' is cryptic. It presumably means iterating over the scheduled and auxiliary slots in an order determined by theta_b; please spell this out in pseudocode or in the caption.","section":"Algorithm 1, line 7"},{"comment":"The handling of zero coordinates for negative-order means is by convention set to zero, but the proof says 'follows by continuity'. Since the convention is discontinuous for p<0, please state explicitly that Lemma 3.1 is applied only where all coordinates are positive, or handle the zero case separately.","section":"Lemma 3.1"},{"comment":"The event names A_t and F_t are introduced with the same letter A as the algorithm in the statement 'Fix an arbitrary algorithm A'. Rename the events (e.g., cal A_t, cal F_t) to avoid confusion.","section":"Lemma 6.5"},{"comment":"The text references Figures 3-6 but the final version should ensure the plots are included with axes and legend labels readable. Experiment D's description says 'we eventually have' in the proof sketch; this is informal and should be aligned with the formal proof.","section":"Section 7"}],"recommendation":"major_revision","confidential_remarks":"The unbounded-mean issue is the main reason for major revision. The technical core - the information-cost lower bound and the UCB-HARE upper bound analysis - appears sound and likely fixable by adding a bounded-mean assumption or by restating the claims as instance-dependent. I would ask the authors to make this correction and re-verify the statements in the abstract and theorems. I do not see a need for rejection, as the mathematical content is substantial and the error is in the formulation rather than in the main derivation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the technical heart is real: the information-cost inequality (Lemma 4.7) and the harmonic-divisor schedule are genuinely new, and the lower-bound proof is careful and self-contained. Second, the advertised minimax claim is not what the class allows. The stress-test note is right. With Assumption 1.1 only requiring μ_i ≥ 0 and μ_* > 0, the class ESG(k,σ)+ has unbounded means. For T=1, any algorithm pulls some arm with probability at most 1/k; make that arm's mean M and all others 0, and regret is at least M(1−1/k). So sup over the class is infinite for every T, and the minimax regret over ESG is ∞. Theorem 1.1's lower bound is vacuously true, and the abstract's \"tight minimax rate\" is not a uniform upper bound. Theorem 5.1 and Corollary 5.2 keep μ_* terms, which grow without bound as μ_* grows.\n\nCredit where it is due. The needle-in-haystack construction, the Jensen averaging over instances, the Fano converse, and the one-step information-gain bound all check out; the integral leading to k^q/λ is sound. The upper-bound analysis is long but the pieces hold: anchor certification, the reward floor in Lemma 6.5, and the Phase-II safety argument. The prefix-balance property of the harmonic schedule is a nice contribution. Experiments are limited but consistent with the theory.\n\nSoft spots, in proportion. The main problem is the normalization and the class definition. The fix is standard: restrict means to [0,1] or another bounded range, or define a scale-invariant regret like (μ_* − M)/μ_*. Also, the presentation oversells: the μ_* k^q/T term in Corollary 5.2 is not a log factor and can dominate for large μ_*, so the \"matching\" only holds for instances where μ_* is of order the statistical scale. Minor: the paper says T ≥ 1 but the lower-bound proof chooses μ = σ√(k^q/T), which is fine, but the statement should be explicit that the bound holds for that subclass.\n\nBottom line: I would not cite the current version's minimax claim, but I would send this to peer review. The machinery deserves scrutiny and the results are likely salvageable with a bounded-mean assumption. This is major-revision material, not a desk reject.","headline":"Solid lower-bound machinery and a clever schedule, but the claimed minimax rate is undefined over the stated class because means are unbounded.","tokens_in":31218,"tokens_out":3403,"would_cite":false,"duration_ms":39552,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62C20","62L05","91B32"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that in k-armed bandits where welfare is the negative-power mean of per-round rewards, the minimax regret is Θ~(σ√(k^{max(1,q)}/T)), so for fairness strength q>1 the k^{q/2} penalty is information-theoretically unavoidable","keywords":["multi-armed bandits","generalized p-mean regret","negative-power welfare","strict fairness","minimax lower bound","UCB-HARE","harmonic schedule","sub-Gaussian rewards"],"falsifier":"Simulate the needle-in-haystack family used in the paper for a fixed q>1 (say q=3) across k=10,30,100 with T large, and fit the scaling of the best achievable regret in k: an exponent of (q+1)/2≈2 rather than q/2=1.5 would contradict the claimed minimax lower bound.","tokens_in":30480,"feed_emoji":"⚖️","tokens_out":7776,"duration_ms":92555,"temperature":0.7,"pith_summary":"This paper asks how much statistical efficiency a learner must sacrifice to guarantee fair treatment of every round in a multi-armed bandit, when fairness is formalized as a negative-power mean of the per-round expected rewards. The authors prove that the minimax regret over sub-Gaussian bandits with nonnegative means is Θ~(σ√(k^{max(1,q)}/T)), where q>0 is the fairness strength. For q>1, this lifts the classical √(k/T) rate to √(k^q/T), meaning the extra arm-count penalty k^{q/2} is an inherent cost of strict fairness, not a flaw of earlier uniform-exploration algorithms. They also introduce UCB-HARE, a two-phase algorithm whose inverse-weighted harmonic exploration schedule matches this lower bound up to logarithmic factors. A sympathetic reader would care because this settles an open question in the fair-bandit literature and tells practitioners exactly how much fairness costs in regret.","feed_headline":"Strict fairness lifts bandit regret to √(k^q/T)","feed_subtitle":"A new lower bound and a matching algorithm show the extra arm-count penalty is intrinsic, not an artifact of uniform exploration.","key_machinery":"The argument turns on two constructions. First, the needle-in-haystack instance family (all means zero except one arm with mean μ>0), together with the information-cost inequality (Lemma 4.7) that converts the rate at which an algorithm can raise its probability of pulling the optimal arm into a lower bound on the cumulative inverse-power penalty. Second, the UCB-HARE algorithm, whose exploration phase uses a harmonic rank schedule—pulling arms with frequency proportional to 1/r—and pairs each risky exploration pull with a certified anchor pull, an arm whose lower confidence bound is strictly positive. The schedule's prefix-balance property (Lemma 3.6) guarantees every arm is adequately samp","core_discovery":"On the paper's own terms, the central discovery is that the minimax (−q)-mean regret over the class of σ-sub-Gaussian bandits with nonnegative means is Ω(σ√(k^{max(1,q)}/T)) (Theorem 1.1), and the UCB-HARE algorithm achieves O~(σ√(k^{max(1,q)}/T)) (Theorem 1.2). For 01 the rate becomes √(k^q/T). The lower bound is obtained from a needle-in-haystack family of instances in which only one arm has positive mean, and the proof is distilled into a general information-cost inequality that lower-bounds the cumulative penalty of any fairness-sensitive objective whose welfare is bottlenecked by the rate of identifying the optimal arm. The upper bound repl","pith_inferences":["The harmonic schedule's success suggests a design principle the authors leave implicit: any fair-exploration scheme must allocate exploration roughly inversely to rank to raise the optimal arm's selection probability from 1/k without paying the full k^{q} penalty; other inverse-frequency schedules might achieve the same endpoint with smaller constants.","The nonnegativity assumption is doing more work than the fairness framing suggests: if arm means are merely lower-bounded by a known negative constant, one could shift all rewards, but the anchor-certification argument and the zero-round convention for the negative-power mean would need reworking. A testable extension is to quantify how the minimax rate degrades as the mean lower bound approaches ","The paper's lower bound construction uses one good arm; instances with many good arms are likely easier. An editor's guess is that a constant fraction of near-optimal arms would yield a smaller k-exponent, so the worst-case rate may only bite in the sparse-optimal-arm regime.","The information-cost inequality could serve as a general tool for sequential decision problems with bottleneck objectives (e.g., minimax regret under constraints on worst-round reward), connecting naturally to the Rawlsian maximin ideal in welfare economics."],"forward_implications":["For q>1, the classical √(k/T) regret rate is superseded by √(k^q/T); this is the exact minimax rate up to log factors.","Algorithms based on uniform early exploration (the prior state of the art) are provably suboptimal in their k-dependence: they incur k^{(q+1)/2}/√T whereas the fundamental limit is k^{q/2}/√T.","The price of strict fairness is zero for 01","Needle-in-haystack lower bound for strict fairness in bandits","No free lunch in fair bandits: extra k penalty unavoidable"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The result depends on the assumption that every arm's expected reward is nonnegative and the best arm's mean is strictly positive; if any arm could have a negative mean, the negative-power welfare objective (which is set to zero when any round's expected reward is zero) and the algorithm's anchor-certification safety argument would both break.","fun_headline_variants_meta":{"raw":{"variants":["Strict fairness in bandits: regret √(k^max(1,q)/T) is tight","Fair bandits: k^q penalty is intrinsic, UCB-HARE matches lower bound","Rawlsian bandits: optimal regret scales as √(k^q/T) for q>1","Needle-in-haystack lower bound for strict fairness in bandits","No free lunch in fair bandits: extra k penalty unavoidable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000244,"raw_usage":{"total_tokens":1459,"prompt_tokens":927,"completion_tokens":532,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":671,"completion_tokens_details":{"reasoning_tokens":420}},"tokens_in":671,"tokens_out":532,"duration_ms":5858,"temperature":1.0,"reasoning_tokens":420,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T05:20:32.599455+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the needle-in-haystack family used in the paper for a fixed q>1 (say q=3) across k=10,30,100 with T large, and fit the scaling of the best achievable regret in k: an exponent of (q+1)/2≈2 rather than q/2=1.5 would contradict the claimed minimax lower bound.","supporting_citations":[],"review_version":1}