{"id":"c77d0255-2723-4fa5-818d-6be73e679dc4","arxiv_id":"2506.02386","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"The paper claims a posterior-sampling algorithm achieves the optimal error exponent for fixed-budget linear best feasible arm identification, but the proof has scaling and direction errors.","lead":"This paper proposes an algorithm for finding the best reward-maximizing arm that satisfies an unknown cost constraint in a linear bandit, claiming it attains the optimal exponential error rate under a fixed sampling budget. If correct, it would resolve a long-standing open rate for constrained best-arm identification, but the proof as written contains several inconsistencies that undermine the claim.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Upper-bound proof of Theorem 4.3 hinges on unverified Lemma 12/Corollary 1 from Kone et al. [2024] in Lemma F.8; if inapplicable to the non-convex truncation set Θ_z*, the claimed exponent Γ is unsupported.","rationale":"The central claim is asymptotic optimality: BLFAIPS achieves error exponent Γ matching the lower bound. The upper bound (Theorem 4.3) is the part specific to this algorithm; the lower bound (Theorem 4.1) is standard in spirit. Within the upper-bound proof, the chain Lemma 5.5 → Lemma 5.6 → Theorem 4.3 depends on showing the six F_i terms are o(1). The F5 term is the most delicate: it converts the average posterior loss under the truncated posterior into the infimum over Θ_z*. Lemma F.8 handles F5, and its proof invokes Lemma 12 and Corollary 1 from Kone et al. [2024] for two key estimates. These results are not stated in the present paper, and the paper does not check that the non-convex, union-of-half-spaces set Θ_z* satisfies the hypotheses (convexity, specific posterior structure) under which those results were proven. This is load-bearing because no alternative derivation of F5 ≤ o(1) is offered. The other issues noted by the reader—the sign error in the lower-bound event algebra, the ratio of identical integrals in the upper-bound proof, and the V_T scaling notation—look like fixable typos/notational slips; the external-lemma dependency is a genuine unverified assumption. I therefore agree with the reader's weakest_assumption and recommend keeping the REJECT verdict (no change). A concrete check is to inspect the Kone et al. preprint and attempt to instantiate its lemmas on Θ_z*.","tokens_in":1284,"tokens_out":995,"duration_ms":154069,"concrete_test":"Obtain Kone et al. [2024] (arXiv:2411.04939), locate Lemma 12 and Corollary 1, and check their hypotheses. In particular, verify whether Corollary 1's concavity condition requires the truncation set to be convex; Θ_z* here is {θ2ᵀz* > τ} ∪ ⋃_{z≠z*} {θ1ᵀz ≥ θ1ᵀz*, θ2ᵀz ≤ τ}, which is generally non-convex. Then re-derive the two O(√T log²T) bounds in Lemma F.8 for a non-convex domain; if they fail, recompute F5 and the exponent in Theorem 4.3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma F.8, used to prove Lemma 5.6 and hence Theorem 4.3, bounds the critical term F5 by o(1) using two results imported from the unpublished preprint Kone et al. [2024]: Lemma 12 and Corollary 1. The paper does not restate these lemmas, and their applicability to the constrained truncation set Θ_z* (a union of half-spaces, not necessarily convex) is not demonstrated. Corollary 1 is invoked to guarantee concavity of exp(-Γ1) under the choice η_r ≤ 1/(8L²R1²) and η_c ≤ 1/(8L²R2²); Lemma 12 is invoked to assert that ∑(2a1 + a1²/(2D1²)) and ∑ log E_{p̃_t} exp(Γ2) are O(√T log²T) with probability 1-4/T. These estimates are exactly what turns the Laplace-approximation error into the claimed exponent Γ. If either lemma is false, or if the truncated posterior over Θ_z* violates its hypotheses (e.g., convexity, boundedness, or the specific Pareto-set structure), the F5 ≤ o(1) step collapses and the upper bound P(error) ≐ exp(-TΓ) is unsupported. No alternative derivation is supplied, so the central optimality claim rests on this external result.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper considers fixed-budget best feasible arm identification in linear bandits with Gaussian noise, where the learner sequentially pulls training arms to estimate unknown reward and cost parameters, and at the end recommends the feasible test arm with highest estimated reward. The central claim is that the proposed algorithm BLFAIPS, which combines a posterior-sampling 'min-learner' with an AdaHedge 'max-learner', achieves an error probability that decays as exp(-TΓ), and that no algorithm can achieve a faster exponential rate, so the algorithm is asymptotically optimal. The paper provides a proof sketch, a supplementary appendix with detailed arguments, and empirical comparisons on synthetic and real-world instances.","tokens_in":39858,"tokens_out":8618,"duration_ms":75730,"significance":"If the claims were correct, this would be a valuable first asymptotic optimality result for constrained fixed-budget best feasible arm identification in linear bandits, with an attractive game-theoretic formulation and a tuning-free algorithm. The use of AdaHedge to remove the doubling trick, the attempt to unify Bayesian and frequentist rate formulations, and the inclusion of empirical experiments are all positive features. However, the verification is currently incomplete: the rate definition is inconsistent between the algorithm and the analysis, the lower-bound proof does not cover arbitrary algorithms, and the key upper-bound step depends on unstated results from an unpublished preprint.","major_comments":[{"comment":"The matrix V_T is defined inconsistently. Algorithm 1, line 18, sets V_t = V_{t-1} + X_t X_t^T, so V_T is the cumulative sum (with V_0 = I), while the notation table in Appendix A and the statements of Lemmas 5.5 and 5.6 define V_T := (1/T)(I + Σ_{t=1}^T X_t X_t^T), the average. Theorem 4.3 defines p_{T+1} := N(hat θ^r_{T+1}, σ^2 V_T^{-1}) ⊗ N(hat θ^c_{T+1}, γ^2 V_T^{-1}) | Θ. If V_T is the average, this covariance does not decay with T, the log-density ratio in Lemma 5.5 is of order 1 rather than T, the event E5,∞ as written does not hold, and the Laplace exponent -TΓ is not obtained. If V_T is the sum, then the notation in Lemmas 5.5/5.6 and Theorem 4.3 must be changed. This inconsistency is load-bearing for Theorem 4.3.","section":"Algorithm 1, Theorem 4.3, Appendix A"},{"comment":"The claimed lower bound is not proved for arbitrary sampling rules. The proof computes the probability that a sample from the posterior distributions Π^r_T and Π^c_T declares some arm z ≠ z* feasible and better than z*, or declares z* infeasible (Lemmas B.2-B.5). That is exactly the error probability of the posterior-sampling recommendation rule used by the algorithm; it is not a change-of-measure lower bound that applies to any algorithm. No alternative parameter pair (θ1, θ2) ∈ Θ_{z*} is constructed and no divergence between the true and alternative environments is bounded uniformly over algorithms. Hence the statement 'for any sampling rule' in Theorem 4.1 is not established, and the claimed matching lower bound is circular, since the same posterior-sampling rule appears in the upper bound.","section":"Appendix B (proof of Theorem 4.1)"},{"comment":"The crucial step F5 = o(1) in the proof of Lemma 5.6 relies on two results imported from Kone et al. [2024] without statement or proof: Corollary 1, used to assert concavity of exp(-Γ1) under η_r ≤ 1/(8L^2 R1^2) and η_c ≤ 1/(8L^2 R2^2), and Lemma 12, used to assert that the sums involving a1, a2 and log E_{p~_t} exp(Γ2) are O(√T log^2 T) with probability 1 - 4/T. These results are not available to the reader, and their hypotheses are not checked for the set Θ_{z*}, which is a union of half-spaces rather than a convex set. Since Lemma F.8 is the only argument turning the Laplace-approximation error into the claimed exponent Γ, Theorem 4.3 is unsupported without these lemmas.","section":"Appendix F.8 (Lemma F.8)"},{"comment":"Theorem 4.3 states 'with probability 1', but the good-event lemmas have failure probabilities that are not summable. Lemma 5.6 gives probability at least 1 - 28/T (and the other lemmas give probabilities of order 1/T or similar); the sum over T of 28/T diverges, so the Borel-Cantelli lemma cannot yield an almost-sure statement. A liminf in probability, or an additional argument, is needed. As written, the 'with probability 1' claim in Theorem 4.3 is not justified.","section":"Section 5 (Lemmas 5.1-5.6)"}],"minor_comments":[{"comment":"The symbol γ_t denotes both the exploration rate t^{-α} and the cost noise; please use distinct symbols to avoid ambiguity.","section":"Algorithm 1, lines 5 and 15"},{"comment":"The expression 'λ_t = (1−γ_t)λ_t + γ_tλ_G' is self-referential; introduce a separate symbol, such as \\tilde λ_t, for the mixture distribution used to sample X_t.","section":"Algorithm 1, line 13"},{"comment":"The notation table defines p_{T+1} with η_r^{-1}V_T^{-1} and η_c^{-1}V_T^{-1}, while Algorithm 1 and Theorem 4.3 use σ^2V_T^{-1} and γ^2V_T^{-1}; align these definitions.","section":"Appendix A, notation table"},{"comment":"Theorem 4.1 states Θ_r = Θ_c = R^d, which is inconsistent with Assumption 2.1's boundedness of Θ_r and Θ_c; clarify whether the lower bound is intended for unbounded parameters or whether the assumption should be modified.","section":"Theorem 4.1"},{"comment":"The proof of Theorem 4.2 derives the explicit f_i(w,z) expression, but the theorem statement does not display it; state the equivalence explicitly for readability.","section":"Theorem 4.2"}],"recommendation":"reject","confidential_remarks":"The paper addresses a timely problem and the algorithmic idea is appealing, but the central optimality claim is not established. The V_T inconsistency alone breaks the rate as written, the lower-bound proof is circular rather than a true information-theoretic lower bound, and the key concentration argument relies on unverified results from an unpublished preprint. These are load-bearing issues that would require substantial new proofs rather than local fixes; I therefore recommend rejection, while noting that a corrected version with a genuine change-of-measure lower bound and a self-contained upper bound could be resubmitted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know about this paper. First, the problem it sets up—fixed-budget linear BAI with an unknown linear cost constraint—is genuinely new and worth working on. Second, the main theorems as written do not support the claimed asymptotic optimality, and the proof issues are load-bearing, not cosmetic.\n\nThe authors do real work here. They adapt the PEPS framework to a two-parameter constrained setting, replace exponential weights with AdaHedge to remove the doubling trick, and give a clean unified hardness parameter. The empirical section, though not reproducible without code, shows the algorithm outperforming sensible baselines. Those are legitimate contributions.\n\nBut the soft spots are serious. The lower-bound proof in Appendix B computes the probability of correct identification and then treats it as an error probability. The asymptotics as written put P(error) near 1, not exponentially small. A proper exponential lower bound needs a change-of-measure argument over arbitrary algorithms; the proof as given doesn't do that, so the claimed information-theoretic matching is not established. The upper bound in Theorem 4.3 depends on Lemma F.8, which imports Lemma 12 and Corollary 1 from the unpublished Kone et al. preprint without restating them. The stress-test note is right: applicability of Corollary 1 to the possibly non-convex truncation set is not demonstrated, and if that fails the F5 term is not o(1). There is also a definitional inconsistency: Algorithm 1 uses V_t as a cumulative sum, while the theorem statements and the notation table define V_T as an average. That is not a typo; it changes the exponent by a factor of T.\n\nWho should read this? Someone working on constrained BAI or posterior-sampling fixed-budget methods will find the formulation useful and the mistakes instructive. But as a paper claiming to close an open problem, it needs major revision: the lower bound must be redone, the external lemmas must be stated and verified, and the notation fixed. I would not cite it in this form.\n\nIt does deserve a serious referee, because the problem is significant and the approach is plausible, but the referee should be asked to check the proofs line by line and the authors should be prepared for heavy revision.","headline":"The problem is new and worth studying, but the main theorems as written do not support the claimed asymptotic optimality: the lower bound has a direction error, the upper bound leans on unverified external lemmas, and the V_T definitions are inconsistent.","tokens_in":40345,"tokens_out":3018,"would_cite":false,"duration_ms":29397,"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":"A sampling rule matches the best possible error rate for identifying the best feasible arm in linear bandits under a fixed budget.","keywords":["best feasible arm identification","fixed budget","linear bandits","asymptotic optimality","error exponent","posterior sampling","AdaHedge","constrained bandits"],"falsifier":"Simulate BLFAIPS on a small linear instance with known $\\theta_r$ and $\\theta_c$, and compute the empirical exponent $-\\log P(\\hat{z}_{\\mathrm{out}} \\neq z^*)/T$ at large $T$; if it is ever strictly below the hardness $\\Gamma$ computed from Theorem 4.1, the central claim is false. The End-of-Optimism instance with a feasibility threshold used in Section 6 is a natural testbed.","tokens_in":39340,"feed_emoji":"🎯","tokens_out":6510,"duration_ms":66712,"temperature":0.7,"pith_summary":"This paper closes a gap in fixed-budget best arm identification: for linear bandits where an arm is acceptable only if an unknown linear cost is below a threshold, no earlier algorithm had a proven exponential error rate matching the information-theoretic limit. The authors propose BLFAIPS, a posterior-sampling algorithm that plays a zero-sum game between a min-learner and a max-learner, and prove that its error probability decays as $e^{-T\\Gamma}$, where $\\Gamma$ is exactly the hardness constant that no sampling rule can beat. If correct, this is the first asymptotically optimal algorithm for constrained best feasible arm identification under a fixed budget, and it unifies a Bayesian and a frequentist expression of the exponent. The claim is supported by experiments on synthetic instances and a MovieLens-based benchmark.","feed_headline":"One sampling rule hits the exact bound on feasible-arm errors","feed_subtitle":"BLFAIPS matches the information-theoretic error exponent for fixed-budget linear bandits with cost constraints","key_machinery":"The load-bearing object is the hardness constant $\\Gamma := \\max_{w \\in \\Delta_{\\mathcal{X}}} \\inf_{(\\theta_1,\\theta_2) \\in \\Theta_{z^*}} \\frac{1}{2}\\left( \\frac{\\|\\theta_1-\\theta_r\\|^2_{A(w)}}{\\sigma^2} + \\frac{\\|\\theta_2-\\theta_c\\|^2_{A(w)}}{\\gamma^2} \\right)$, where $A(w)$ is the design matrix of the sampling distribution over training arms. The algorithm mirrors this max-min structure: AdaHedge acts as the max-learner, adaptively choosing sampling weights to maximize distinguishability, while posterior sampling acts as the min-learner, drawing parameters from the posterior truncated to $\\Theta_{z^*}$ to simulate the hardest alternative. A G-optimal exploration mixture ensures that the design matrix fills all relevant directions. The proof relates the algorithm's error probability to a Laplace approximation of the posterior ratio, showing that it is asymptotically $e^{-T\\Gamma}$.","core_discovery":"The paper's central claim is that BLFAIPS attains $\\liminf_{T\\to\\infty} -\\frac{1}{T}\\log P(\\hat{z}_{\\mathrm{out}} \\neq z^*) \\ge \\Gamma$ and, together with Theorem 4.1's converse bound $\\limsup \\le \\Gamma$, this makes the algorithm asymptotically optimal. The exponent $\\Gamma$ is the maximum over sampling distributions $w$ of the minimum KL divergence to parameters for which the recommended arm is not the best feasible arm; it splits into four terms corresponding to superoptimal-infeasible arms, suboptimal-feasible arms, suboptimal-infeasible arms, and false infeasibility of the true best arm. The paper also proves that the Bayesian posterior form and the frequentist change-of-measure form of this hardness constant are equivalent, and that setting the cost threshold to infinity recovers the unconstrained linear bandit hardness.","pith_inferences":["The same min-learner/max-learner game with a modified loss should extend to other constrained identification problems, such as variance-constrained or safety-threshold identification, where the feasible set is defined by a different functional of the parameters.","A testable extension is to sub-Gaussian or heavy-tailed noise: since the exponent is built from KL-type divergences, the Gaussian assumption likely enters only through the posterior form, and one might recover the same $\\Gamma$ with a different posterior construction.","The four-term hardness decomposition suggests a diagnostic tool: computing each $f_i(w,z)$ for a problem instance would reveal which arm class limits performance, potentially guiding algorithmic tuning before experiments are run.","Because AdaHedge makes BLFAIPS anytime, an implicit practical consequence is that the algorithm can be stopped at an unknown, externally determined deadline without losing the matching exponent; this is a stronger anytime guarantee than existing tuned Top-Two Thompson sampling variants."],"forward_implications":["If Theorem 4.3 is correct, no fixed-budget algorithm for this problem can drive the error probability to zero faster than BLFAIPS, settling the asymptotic rate for linear best feasible arm identification.","The four-term decomposition of $\\Gamma$ identifies which kind of confusion dominates a given instance: a practitioner can compute each term and see whether the bottleneck is feasibility, reward suboptimality, or the risk of declaring the best arm infeasible.","Replacing exponential weights with AdaHedge removes the doubling trick, so BLFAIPS is anytime and does not need the budget $T$ to be known in advance; the paper demonstrates this advantage empirically against PEPS when $T$ is unknown.","Setting the cost threshold $\\tau \\to \\infty$ recovers the unconstrained linear bandit hardness, showing that the constrained result strictly generalizes the existing theory.","The proven equivalence of the Bayesian and frequentist forms of $\\Gamma$ means the exponent can be computed and communicated from either perspective in practice."],"supporting_citations":[{"why":"Supplies the posterior-sampling game structure, the G-optimal exploration lemma (Lemma C.14), and the unconstrained PEPS algorithm that BLFAIPS extends and compares against.","marker":"Li et al. [2024]"},{"why":"Provides Lemma 12 and Corollary 1, which the upper-bound proof uses to bound the log-partition function of the truncated posterior over $\\Theta_{\\hat{z}_t}$.","marker":"Kone et al. [2024]"},{"why":"Supplies the AdaHedge regret bound used to control the max-learner's adaptive sampling distribution.","marker":"De Rooij et al. [2014]"},{"why":"Provides the ridge-regression concentration inequalities (Lemmas G.1 and G.2) on which the good events for the empirical reward and cost estimates rest.","marker":"Abbasi-Yadkori et al. [2011]"},{"why":"Gives the unconstrained linear best-arm identification hardness to which the constrained exponent $\\Gamma$ reduces when the cost threshold tends to infinity.","marker":"Jedra and Proutiere [2020]"}],"fun_headline_variants":["Optimal error-rate bound reached for fixed-budget linear bandits","Feasible-arm identification hits theoretical exponent limit","Posterior sampling achieves exact error decay in linear bandits","BLFAIPS proves asymptotically optimal in fixed-budget setting"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire upper bound rests on an imported concentration inequality for the posterior truncated to the 'not best feasible arm' parameter set; if that inequality fails for the constrained set, the claimed matching exponent is not established.","fun_headline_variants_meta":{"raw":{"variants":["Optimal error-rate bound reached for fixed-budget linear bandits","Feasible-arm identification hits theoretical exponent limit","Posterior sampling achieves exact error decay in linear bandits","BLFAIPS proves asymptotically optimal in fixed-budget setting"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000537,"raw_usage":{"total_tokens":2571,"prompt_tokens":929,"completion_tokens":1642,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":545,"completion_tokens_details":{"reasoning_tokens":1574}},"tokens_in":545,"tokens_out":1642,"duration_ms":11404,"temperature":1.0,"reasoning_tokens":1574,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:26:45.161665+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate BLFAIPS on a small linear instance with known $\\theta_r$ and $\\theta_c$, and compute the empirical exponent $-\\log P(\\hat{z}_{\\mathrm{out}} \\neq z^*)/T$ at large $T$; if it is ever strictly below the hardness $\\Gamma$ computed from Theorem 4.1, the central claim is false. The End-of-Optimism instance with a feasibility threshold used in Section 6 is a natural testbed.","supporting_citations":[{"cited_title":"Pareto Set Identification With Posterior Sampling","cited_arxiv_id":"2411.04939","evidence_quote":"Provides Lemma 12 and Corollary 1, which the upper-bound proof uses to bound the log-partition function of the truncated posterior over $\\Theta_{\\hat{z}_t}$."},{"cited_title":"Follow the leader if you can, hedge if you must","cited_arxiv_id":null,"evidence_quote":"Supplies the AdaHedge regret bound used to control the max-learner's adaptive sampling distribution."},{"cited_title":"Improved algorithms for linear stochastic bandits","cited_arxiv_id":null,"evidence_quote":"Provides the ridge-regression concentration inequalities (Lemmas G.1 and G.2) on which the good events for the empirical reward and cost estimates rest."},{"cited_title":"Optimal best-arm identification in linear bandits","cited_arxiv_id":null,"evidence_quote":"Gives the unconstrained linear best-arm identification hardness to which the constrained exponent $\\Gamma$ reduces when the cost threshold tends to infinity."}],"review_version":1}