{"id":"9d0bcf09-717f-4025-af38-539a6fde8dc9","arxiv_id":"2601.22969","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"FairLinBandit achieves order-optimal Nash regret Õ(d/√T) and the first sublinear p-mean regret bounds in linear bandits for every real p.","lead":"FairLinBandit uses a short data-adaptive exploration phase followed by a standard linear bandit algorithm to hit order-optimal fairness-aware regret, Õ(d/√T), in linear bandits. It also gives the first p-mean regret bounds for all p, letting practitioners dial between fairness and efficiency.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Phase-I stopping rule as written is not the one analyzed: zero-initialization skips Phase I, and the proof never establishes the lower conjunct needed to prevent premature stopping.","rationale":"I read the paper as attempting to resolve the d^{5/4}-vs-d gap by using a data-adaptive Phase I that feeds UCB-style confidence intervals into Phase II. The claimed rate is consistent with the AM-GM lower bound, and the high-level two-phase design is plausible. However, the stopping rule is the linchpin: both the pseudocode and the proof of Lemma B.8 fail to guarantee the Phase I length on which Theorem 4.1 depends. The zero-initialization issue the reader identified is real and immediately makes the printed algorithm non-executable. But even after that is patched, Lemma B.8 proves only the upper inequality of the stopping condition; the lower inequality A < t is not shown to hold at early checkpoints, so the algorithm can legally stop after one epoch. This is a deeper defect than a typo, because it undermines the τ lower bound used by Lemma B.16. The compactness issue and the dS dimension typo in Lemma B.8 are secondary and fixable. I therefore agree with the reader's CONDITIONAL verdict rather than moving to ACCEPT or REJECT: the intended algorithm may work, but the printed algorithm and its proof are not yet aligned.","tokens_in":31324,"tokens_out":28843,"duration_ms":314197,"concrete_test":"Analytical check: Fix the zero-initialization bug by running one PullArms epoch before evaluating condition (1). Then verify whether Lemma B.8's proof establishes both conjuncts of (1) for all t ≤ 864S. In the current proof it establishes only t ≤ B; it never shows A < t. To settle the issue, construct a realization consistent with G1 in which after the first epoch M ≤ C (e.g., d=10, σ=1, T=10^6, Δ=0.5, with noise pushing the maximum least-squares estimate below C). For that realization, the printed while condition is false, Phase I exits with τ ≈ 72logT, and the Phase-II welfare lower bound (Lemma B.16) fails because τ ≪ 48d²σ²logT/Δ². This demonstrates a concrete instance where the proof's τ lower bound is violated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing weak point is the Phase-I stopping rule and the proof that it runs for the required τ. Two concrete defects compound. First, with θ̂ = 0 at initialization, M = max_x ⟨x, θ̂⟩ = 0, so the left conjunct 48σ²d²logT/M² < t is +∞ < 1 (or a division by zero); Algorithm 1 as printed therefore never enters Phase I. Second, the proof of Lemma B.8 analyzes a corrected rule that has already performed exploration, but even that corrected rule is not established: Lemma B.8 derives only the upper inequality t ≤ 900p²σ²d²logT/(M−C)² for t ≤ 864dS. The while condition is the conjunction A < t ≤ B, with A = 48σ²d²logT/M² and C = √(48σ²d²logT/t). To show Phase I does not stop before 864dS, the proof must also show A < t, i.e. M > C, at every early checkpoint. Under the paper's own good event G1, only M ≥ Δ − C is available; for t ≈ 72logT this gives M − C ≥ Δ − 2C, and C = 4σd√(3logT/t) can exceed Δ/2 for all Δ ≤ 1 when σd is order 1. Hence the first epoch may legally terminate Phase I with τ ≪ 864dS, and Lemma B.16's lower bound on Phase II rewards — which requires τ ≥ c d²σ²logT/Δ² — has no basis. Theorem 4.1 is therefore a statement about a different stopping rule than the one printed and analyzed.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Nash regret and the more general p-means regret in stochastic linear bandits. It proposes FairLinBandit, a two-phase meta-algorithm: Phase I performs a data-adaptive exploration schedule that mixes D-optimal design and John-ellipsoid sampling; Phase II runs either LinUCB or LinPE initialized with the Phase I statistics. The main theoretical claims are an O(σ d log T / √T) Nash regret bound, claimed to match the Ω(d/√T) lower bound and thereby resolve an open problem of Sawarni et al. (2023), and corresponding p-means regret bounds for all p ∈ R. Experiments on learning-to-rank datasets compare the two instantiations against LinNash.","tokens_in":31796,"tokens_out":9270,"duration_ms":90776,"significance":"If the central theorem were established, this would be a significant contribution: it would close the d^{5/4}-vs-d dimension gap for Nash regret in linear bandits, introduce the first p-means regret analysis in this setting, and provide a general reduction from Nash/p-means regret to average-regret bandit algorithms. The paper also supplies a code repository and gives detailed proof sketches. However, the printed algorithm and the proof of the key Phase-I stopping lemma do not currently match, and at least one assumption needed for the geometric tools is missing. These are load-bearing issues that must be repaired before the claimed results can be accepted.","major_comments":[{"comment":"The stopping rule as printed is not executable. At initialization θ̂ = 0, so max_{x∈X} ⟨x, θ̂⟩ = 0; the left inequality 48σ²d²logT / (max_x⟨x,θ̂⟩)² < t divides by zero and is not satisfied, so the while loop never enters. Thus Phase I runs zero rounds, and Theorem 4.1 is not a statement about the printed algorithm. The τ bookkeeping is also inconsistent: line 7 doubles eT and advances t, but line 10 sets τ = eT/2, which is not the total number of Phase-I pulls after more than one epoch. The proof in Lemma B.8 analyzes a corrected rule with a positive design matrix and with τ interpreted as the total Phase-I length. This correction must be made explicit in Algorithm 1 and the pseudocode must produce the τ used in the proof.","section":"Algorithm 1, lines 4–10 and Eq. (1)"},{"comment":"The proof of Lemma B.8 does not establish the full while condition. It derives only the upper inequality (6) for t ≤ 864dS, i.e. the right-hand conjunct of Eq. (1). It never proves the left-hand conjunct 48σ²d²logT / M_t² < t at every checkpoint, where M_t = max_x ⟨x, θ̂_t⟩. Under the paper's own good event G1, the available bound is M_t ≥ Δ − C_t with C_t = 4σd√(3logT/t), and for early checkpoints C_t can be larger than Δ/2 even when Δ ≤ 1. Hence the algorithm as analyzed could legally stop Phase I much earlier than 864dS. Since Lemma B.16 and Lemma B.20 both require τ ≥ c d²σ²logT/Δ², the lower bound on Phase-II rewards has no basis. The authors must either prove the lower conjunct or change the stopping rule so that a minimum exploration length is enforced.","section":"Lemma B.8 and Eq. (1)"},{"comment":"The paper assumes only norm-boundedness of the arms, but the D-optimal design results used in Phase I (Lemma B.6, Kiefer–Wolfowitz/G-optimality) and the John-ellipsoid distribution require compactness of X (and that X spans R^d). For a countably infinite, merely bounded set, the supremum defining G-optimality need not be attained, and the John ellipsoid of a non-closed convex hull is not guaranteed to exist. This compactness assumption is load-bearing for the definition of λ* and ρ and for the Phase-I guarantees. It should be stated explicitly in Assumption 2.1 or the text should show that norm-boundedness alone suffices.","section":"Assumption 2.1 and Section 3.1"}],"minor_comments":[{"comment":"The subroutine mutates the global arm set X by permanently removing arms once their round-robin count exceeds ⌈λ*_z eT/3⌉. If X is shared across epochs, this destroys the support of λ* and invalidates the guarantee V_t ⪰ (t/3)U(λ*) used in Lemma B.7. Please clarify that the removal is local to a single PullArms call or otherwise maintain the design support.","section":"Algorithm 2, line 9"},{"comment":"The definition of S is typeset ambiguously and appears inconsistent with the proof: the proof uses τ = 864|p_a|²d²σ²logT/⟨x*,θ*⟩², which would correspond to S containing d², while the displayed dS then gives Θ(d²). Please make the definition of S and the constant in Lemma B.8 unambiguous.","section":"Lemma B.8"},{"comment":"The statement says R_p^T ≤ O(σd logT / T), but the proof and Theorem 4.2 give O(σd logT / √T). This is a typo, but the published version should state the correct rate.","section":"Lemma C.2"},{"comment":"The text refers to 'Figures 4(a) and 4(b)' for the ablation on number of arms, but the main paper shows Figures 1 and 2 only. Please renumber or fix the cross-reference.","section":"Appendix D, Figure references"},{"comment":"The proof cites 'Lemma 11' where Lemma B.1 (Chernoff bound) is meant. Please correct the cross-reference.","section":"Lemma B.2 proof"}],"recommendation":"major_revision","confidential_remarks":"The high-level idea—using a data-adaptive initial exploration phase to enable additive UCB confidence widths—is plausible and potentially important, and the claimed rate may be recoverable. But the current manuscript's Algorithm 1 does not execute the stopping rule that is analyzed, and the proof of the key Phase-I length lemma is incomplete. These are fixable within the scope of the paper, but they are central rather than cosmetic, so the paper should be returned for a careful revision. I would also ask the authors to add the compactness assumption explicitly and to double-check the pseudocode/τ bookkeeping before resubmission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this if you follow fairness-aware linear bandits. The paper has the right target: beat Sawarni et al.'s d^{5/4} Nash regret by using estimate-independent UCB widths after a data-adaptive exploration phase, and extend to p-mean regret. The conceptual move is sound — explore long enough that UCB width stays below the optimal reward, then run any optimistic algorithm. The d dependence in the announced bound matches the lower bound, and the p≥0 case follows cleanly from the generalized mean inequality. The paper also broadens the reward model to sub-Gaussian and ships code. Credit where due: this is a genuinely better framework than LinNash if the stopping rule works.\n\nBut as printed it doesn't quite work. Three problems, in increasing order:\n\n1. Algorithm 1 initializes θ̂ = 0, so the while condition divides by zero and Phase I never runs. Minor editorial fix, but it means Theorem 4.1 describes a different algorithm.\n\n2. Lemma B.8 has a dimension mismatch: S contains d², but the bound is stated as dS, giving Θ(d³). Likely a typo, but it shows the appendix was not carefully checked.\n\n3. The real issue: the proof of Lemma B.8 only establishes the upper inequality t ≤ 900.../...². The stopping condition also needs the lower inequality, 48σ²d²logT/M² < t, to prevent early termination. That lower conjunct is never proved. At early checkpoints, the good event only gives M ≥ Δ − C, and C can exceed Δ/2, so Phase I can legally stop after the first epoch with τ far below the needed Θ(d²/Δ²). Lemma B.16's Phase II lower bound then has no basis. This isn't a cosmetic typo; it is the load-bearing part of the main theorem.\n\nI also note the D-optimal-design step needs compactness of the arm set, while Assumption 2.1 only states norm-boundedness. Minor and fixable. The citation pattern is honest; the facts reused from the authors' prior papers are elementary inequalities, not fitted constants to make the rate work.\n\nWho should read this: anyone working on Nash or p-mean regret in linear bandits. The reduction idea is worth engaging with even before the proof is fixed. But I wouldn't cite it as a theorem yet.\n\nRecommendation: send to peer review, yes, but with the expectation of major revision. The first referee report should demand a corrected, executable stopping rule and a proof of both conjuncts. If that gap closes, the paper is a solid NeurIPS/COLT-level contribution. If it doesn't, the claimed improvement over Sawarni et al. is not established.","headline":"The d-versus-d^{5/4} fix is real and the meta-framework is sensible, but the printed algorithm cannot run and the stopping-rule proof has a load-bearing gap, so the claims need major revision before they hold as stated.","tokens_in":32258,"tokens_out":3210,"would_cite":false,"duration_ms":36108,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L05","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"FairLinBandit, a two-phase meta-algorithm for linear bandits, achieves Nash regret O(σd logT/√T), matching the known lower bound up to log factors and closing the dimension gap left by prior work.","keywords":["Nash regret","linear bandits","p-means regret","Nash social welfare","fairness-aware learning","upper confidence bound","D-optimal design","John ellipsoid"],"falsifier":"Run Phase I of Algorithm 1 exactly as printed: with θ̂ initialized to zero the while-condition divides by zero and no exploration rounds occur, so the claimed τ = Θ(d²σ²logT/⟨x*,θ*⟩²) Phase I length is not what the pseudocode produces. Then, using the corrected stopping rule from the proof of Lemma B.8, measure the empirical Phase I length and the Nash regret for d = 10–40 over T = 10^5–10^8: the claim stands if Phase I terminates near d²/⟨x*,θ*⟩² and regret decays at roughly d logT/√T.","tokens_in":31229,"feed_emoji":"⚖️","tokens_out":14568,"duration_ms":138113,"temperature":0.7,"pith_summary":"The paper's central claim is that fairness-aware learning in linear bandits costs no more, in the worst case, than ordinary utility maximization. Nash regret — the gap between the best and the achieved geometric mean of per-round expected rewards — can be driven to O(σd logT/√T) by a two-phase meta-algorithm called FairLinBandit, matching the Ω(d/√T) lower bound up to log factors and closing the d^(5/4) gap left open by prior work. The mechanism is a data-adaptive stopping rule that keeps exploring until the estimated best reward safely clears the width of standard UCB-style confidence intervals, which keeps the geometric mean from collapsing and lets Phase II use ordinary additive concentration bounds. The same framework gives the first p-means regret bounds for linear bandits, interpolating between utilitarian and Rawlsian fairness, and relaxes the non-negative-reward assumption of earlier work to general sub-Gaussian noise.","feed_headline":"Bandit meta-algorithm hits the optimal d/√T Nash regret rate","feed_subtitle":"A data-adaptive warm-up lets standard UCB bounds hit the lower bound, closing the gap left in earlier work.","key_machinery":"The load-bearing object is Phase I's data-adaptive stopping rule, executed over geometrically doubling epochs. Exploration alternates between a D-optimal design over the arms — which, via the Kiefer–Wolfowitz theorem, keeps predictive variance ∥x∥²_{V⁻¹} at most 3d/t and shrinks estimation error uniformly — and sampling from a John ellipsoid distribution over the convex hull, which guarantees every pull has expected reward at least ⟨x*,θ*⟩/(d+1). The stopping rule halts Phase I once the estimated best reward exceeds the UCB width, after τ = Θ(d²σ²logT/⟨x*,θ*⟩²) rounds. That choice is what makes Phase II's estimate-independent confidence intervals safe: their width, of order d/√τ, no longer e","core_discovery":"FairLinBandit's core claim: the bottleneck in fair linear bandits is the exploration phase, not the optimization routine after it. Prior work fixed the exploration length and used confidence intervals that depend on reward estimates, forcing multiplicative concentration inequalities and a d^(5/4)/√T rate. The new algorithm ends Phase I with a data-dependent rule — explore until the estimated best reward clears the UCB width — which guarantees both an accurate θ* and per-round expected rewards of at least ⟨x*,θ*⟩/(2(d+1)). Phase II then runs any optimistic algorithm on ordinary estimate-independent UCB intervals, restoring additive bounds and yielding Nash regret O(σd logT/√T); the same Phase","pith_inferences":["Inference: the Phase I length scales as 1/⟨x*,θ*⟩², so the hidden cost of fairness is concentrated on instances where the best arm's expected reward is small; reparameterizing the bounds by the reward gap would expose this per-instance price rather than averaging it into the worst case.","Inference: because Phase II accepts any optimistic average-regret algorithm, the reduction transfers future improvements in utility-maximizing linear bandits directly to fairness objectives — the fairness gap becomes hostage only to the underlying algorithm's confidence-width rate.","Inference: the same two-phase template — adaptive exploration followed by estimate-independent intervals — is a natural candidate for logistic and generalized linear bandits, giving a concrete test of the paper's conjecture that the reduction extends beyond linear payoffs."],"forward_implications":["Nash regret of order σd logT/√T is achievable in linear bandits, matching the Ω(d/√T) lower bound up to log factors and closing the gap left by the previous d^(5/4) analysis.","p-means regret matches the Nash rate for every p ≥ 0; for p < 0 it degrades to σ d^{1+|p|/2} logT/√T · max{1,|p|}, quantifying the added cost of stronger fairness guarantees.","Fairness-aware linear bandits no longer require non-negative (sub-Poisson) rewards: the analysis covers general σ-sub-Gaussian noise, where rewards may be negative on individual rounds.","The meta-algorithm turns any optimistic average-regret linear bandit algorithm into a fair one; both instantiations given here, LinUCB and LinPE, attain the same order-optimal Nash rate."],"fun_headline_variants":["Data-adaptive exploration closes Nash regret gap","FairLinBandit reaches optimal d/√T regret","Adaptive warm-up yields optimal fairness regret","Linear bandits: adaptive phase fixes suboptimality"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that Phase I actually explores for on the order of d²σ²logT/⟨x*,θ*⟩² rounds: as printed, the stopping rule in Algorithm 1 divides by zero (the estimate starts at zero) and stops immediately, so the theorem rests on a corrected rule that appears only in the proof — and it also needs the arm set to be compact and the best arm's expected reward to be strictly positive.","fun_headline_variants_meta":{"raw":{"variants":["Data-adaptive exploration closes Nash regret gap","FairLinBandit reaches optimal d/√T regret","Adaptive warm-up yields optimal fairness regret","Linear bandits: adaptive phase fixes suboptimality"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000233,"raw_usage":{"total_tokens":1321,"prompt_tokens":727,"completion_tokens":594,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":471,"completion_tokens_details":{"reasoning_tokens":534}},"tokens_in":471,"tokens_out":594,"duration_ms":6100,"temperature":1.0,"reasoning_tokens":534,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T06:17:57.136687+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Phase I of Algorithm 1 exactly as printed: with θ̂ initialized to zero the while-condition divides by zero and no exploration rounds occur, so the claimed τ = Θ(d²σ²logT/⟨x*,θ*⟩²) Phase I length is not what the pseudocode produces. Then, using the corrected stopping rule from the proof of Lemma B.8, measure the empirical Phase I length and the Nash regret for d = 10–40 over T = 10^5–10^8: the claim stands if Phase I terminates near d²/⟨x*,θ*⟩² and regret decays at roughly d logT/√T.","supporting_citations":[],"review_version":1}