{"id":"b8405553-3923-49f3-badb-e42fc3448c61","arxiv_id":"1908.09094","paper_version":3,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For distributions with a known bound on an increasing convex moment, the AL1 algorithm identifies the best arm with probability at least 1-δ using asymptotically minimal expected samples as δ goes to 0.","lead":"This paper proves that no reliable algorithm can identify the best arm when distributions have unbounded support unless the user knows a bound on a moment of each arm, and then gives a near-optimal algorithm that does so. The result extends asymptotically optimal best-arm identification to heavy-tailed distributions and adds a practical batching scheme.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Threshold constant in Theorem 10 is µ-dependent, so AL1's stopping rule is not fully specified for unknown arms.","rationale":"The reader accepted the paper and flagged the known moment bound (f,B) as the main fragile assumption. The present concern is different and more internal: even when f and B are known, the stopping threshold β(n,δ) in (10) uses a constant C that, via (16), depends on the unknown true arm distributions through the constants B̃_a of Theorem 13. This is not a numerical detail; it means the algorithm cannot set its stopping rule unless it already knows the quantities it is trying to learn. The example with f(y)=y^2, B=1 shows that B̃_a is unbounded over L, so no universal C computable from f,B,δ,K exists while preserving the matching constant 1/V(µ). The core asymptotic-optimality result may still be salvageable by replacing C with an explicit distribution-free sequence, at the cost of a (1+ε) factor or a different threshold construction, but as written the proof of δ-correctness in Theorem 10 is incomplete. I therefore recommend a conditional accept rather than an unconditional one.","tokens_in":40651,"tokens_out":8106,"duration_ms":88480,"concrete_test":"Set f(y)=y^2, B=1, K=2, and let arm 2 be deterministic at 0. For ε>0 define arm 1 as the equiprobable two-point distribution {1−ε+√(2ε−ε^2), 1−ε−√(2ε−ε^2)}, which lies in L. Compute B̃_1(ε) from the definitions before Theorem 13 and solve inequality (16) for the smallest C(ε); verify that C(ε)→∞ as ε→0. Then fix any distribution-free constant C (or any C chosen from f,B,δ only) and simulate AL1 on the instance with ε small enough that (16) forces a larger C; check whether the empirical error probability still respects P(error)≤δ. If it does not, Theorem 10's δ-correctness claim fails for the algorithm as specified.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The δ-correctness proof of Theorem 10 chooses C through inequality (16), but the left side of (16) contains ∏_a e^{B̃_a}, where B̃_a is defined just before Theorem 13 in terms of the true arm distribution µ_a: it depends on E|X−m(µ_a)|, E|B−f(|X|)|, and the denominators f^{−1}(B)−m(µ_a) and B−f(|m(µ_a)|). Since the algorithm is supposed to act without knowing µ, C must be computable from f, B, δ, and K alone. The class L, however, contains distributions with m(µ_a) arbitrarily close to f^{−1}(B); for those arms the denominator B−f(|m(µ_a)|) tends to zero, and B̃_a can grow without bound. For example, with f(y)=y^2 and B=1, the two-point arm with values 1−ε±√(2ε−ε^2) has mean 1−ε, E X^2=1, and B̃_1 grows like ε^{−1/2}. Hence the minimal C satisfying (16) is unbounded over L. No single algorithmic threshold (10) can therefore be chosen from the stated problem data alone, so AL1 is not a well-defined δ-correct algorithm unless it also receives µ or the theorem is modified to use a threshold with an explicit, distribution-free constant (e.g., by sacrificing tightness in (13)).","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies δ-correct best-arm selection for K distributions with finite means. The authors prove an impossibility result (Theorem 3) for KL-right-dense unbounded-support classes, showing that any δ-correct algorithm must have infinite expected pulls on non-best arms. For the class L defined by a known bound B on E f(|X|) with f strictly increasing, convex, and superlinear, they formulate the max-min lower-bound problem, characterize its solution V(μ) and optimal proportions t*(μ) (Theorem 5), derive a dual representation of the KLinf functional (Theorem 12), prove concentration inequalities for empirical KLinf (Theorems 11 and 13), and propose the sampling algorithm AL1 with a generalized-likelihood-ratio stopping rule (Section 4). They claim that AL1 with threshold β(n,δ) = log(C n^α (log n)^K (log 1/δ)^{2K+1} / δ), with m = o(log(1/δ)), is δ-correct and satisfies limsup E_μ(τ_δ)/log(1/δ) ≤ 1/V(μ) (Theorem 10). The paper also discusses batch-size optimization and includes a numerical study with Pareto arms.","tokens_in":40922,"tokens_out":13126,"duration_ms":138161,"significance":"The negative result and the general moment-bound framework are valuable contributions that extend fixed-confidence best-arm theory beyond single-parameter exponential families and bounded-support settings. The dual representation of KLinf and the concentration inequalities are potentially reusable tools. The paper is also careful to include full proofs in the appendices and a numerical demonstration. However, the main algorithmic claim is currently tied to a threshold constant that is not computable from the stated problem data, and a continuity argument used in the proof of Theorem 5 is not justified as written. These are substantive issues that need to be repaired before the central contribution can be accepted.","major_comments":[{"comment":"The constant C in the threshold β(n,δ) is defined only through inequality (16), whose left side contains the factor ∏_a e^{B̃_a}. As defined before Theorem 13 (and analogously before Theorem 11), B̃_a depends on the true distribution μ_a through E|X−m(μ_a)| and through the denominators f^{-1}(B)−m(μ_a) and B−f(|m(μ_a)|). Since AL1 must be run knowing only f, B, K, and δ, this C is not computable from the problem data. Moreover, B̃_a is unbounded over L: for f(y)=y² and B=1, the two-point distribution at 1−ε±√(2ε−ε²) lies in L with mean 1−ε and E X²=1, while the corresponding constant d_{a1} = c_{a1}/(2(f^{-1}(B)−m(μ_a))) is Ω(ε^{−1/2}) as ε→0. Hence the minimal C satisfying (16) diverges over L, so no single threshold of the form (10) can make AL1 δ-correct over all of L from the stated problem data alone. The authors must either supply an explicit distribution-free constant (possibly via a different concentration argument), replace the threshold with a data-dependent stopping rule, or clearly restrict the theorem to per-instance constants, in which case AL1 would no longer be a well-defined algorithm for unknown μ.","section":"Section 4, Eq. (16) and Theorem 10"},{"comment":"The proof of Lemma 4 asserts without argument that KL(·,·) is continuous on the Wasserstein metric space (P(R), d_W). This is false: with f(y)=y² and B=1, take η = 0.5 δ_0 + 0.5 δ_1 and κ_n = 0.5 δ_{1/n} + 0.5 δ_1. Both are in L, d_W(η, κ_n)→0, but KL(η,κ_n)=∞ for every n. The subsequent use of Berge's maximum theorem to conclude continuity of KLinf(η,x), and through Theorem 5 the continuity of t*(μ), is therefore not justified. Since t* continuity underpins Lemma 14 and the sample-complexity proof, this continuity claim needs a direct proof (or a lower-semicontinuity argument adapted to the compact class L), not an appeal to the global continuity of KL.","section":"Appendix B.1, Lemma 4"}],"minor_comments":[{"comment":"The arXiv title emphasizes 'Heavy-Tailed Distributions' while the manuscript title on the first page is 'Optimal δ-Correct Best-Arm Selection for General Distributions'; please reconcile the titles with the actual scope of the class L.","section":"Title/Abstract"},{"comment":"The argument of the logarithm in (10) is ambiguous; please write it as log(C n^α (log n)^K (log(1/δ))^{2K+1} / δ) with clear parentheses.","section":"Eq. (10)"},{"comment":"The notation B̃_a is used inconsistently: before Theorem 11 it is d1+d2, while before Theorem 13 the displayed definition says B̃_a = c_{a1}+c_{a2}. Please harmonize the notation so that it is unambiguous which quantity appears in the concentration bounds.","section":"Before Theorems 11 and 13"},{"comment":"The text states that results are averaged over 20 independent experiments, but later says 'in all the 15 independent experiments'; please correct the inconsistent count.","section":"Section 5, numerical experiment"},{"comment":"The complexity claim for solving the max-min problem would benefit from a brief explanation of how interpolation error is controlled, since the empirical distributions are reused in the stopping rule.","section":"Remark 7"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Serious paper, worth a careful referee, but the main theorem as written overclaims. The negative result (Thm 3) and the lower-bound analysis are genuinely new and look correct: KL-right-dense unbounded classes force infinite expected samples for any δ-correct algorithm, and the KLinf dual representation plus the moment-bound concentration machinery is a real step beyond the SPEF and bounded-support literature. The proofs are detailed enough to be checkable, and the authors do not hide the hard parts.\n\nThe soft spot is the stopping rule. Theorem 10's threshold β(n,δ) contains a constant C that is only specified through inequality (16). The left side of (16) includes ∏_a e^{B̃_a}, and B̃_a depends on the true arm µ_a through denominators such as B−f(|m(µ_a)|). That denominator can be made arbitrarily small without leaving L. For f(y)=y², B=1, the two-point arm with values 1−ε±√(2ε−ε²) has mean 1−ε and E[X²]=1, and the relevant constant grows like ε^{-1/2}. So no C chosen from f,B,K,δ can make AL1 δ-correct uniformly over L. Since AL1 is supposed to operate without knowing µ, Theorem 10 is not a fully specified algorithm. This is load-bearing, not cosmetic.\n\nThat said, the surrounding work is solid. The impossibility result and the lower bound do not depend on this threshold constant. The sample-complexity argument is careful conditional on a valid δ-correct stopping rule. The numerics are illustrative only: no code, fitted cost constants, and ratios 28-to-16 are not strong evidence by themselves.\n\nRecommendation: serious peer review, but major revision. The authors need to provide a distribution-free C or an explicit threshold that does not involve the unknown arms, and then prove δ-correctness with it; alternatively they should restrict L so that the B̃_a constants are bounded by problem data. If the gap can be closed, the paper will be important. As it stands, I would not cite it as a proof of an asymptotically optimal algorithm for L.","headline":"Significant results and a real gap: the δ-correct algorithm's threshold C depends on the unknown arm distributions, so Theorem 10 is not yet a fully specified algorithm for L.","tokens_in":41423,"tokens_out":7989,"would_cite":false,"duration_ms":86049,"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":"A δ-correct algorithm for unbounded-support arms can match the sample-complexity lower bound when the algorithm knows a moment bound E f(|X|) ≤ B, and is provably impossible without such a restriction.","keywords":["best-arm identification","δ-correct algorithms","heavy-tailed distributions","moment bounds","Kullback-Leibler divergence","sample complexity","multi-armed bandits","ranking and selection"],"falsifier":"Take a two-arm instance with Pareto distributions, set $f(y)=y^2$ and $B$ equal to the second moment of the better arm while the other arm has second moment $B+\\varepsilon$, run AL1 with the declared $B$ for $\\delta=10^{-3},10^{-6},10^{-8}$, and measure the empirical error frequency and $E_\\mu(\\tau_\\delta)/\\log(1/\\delta)$; error above $\\delta$ or a ratio that does not approach $1/V(\\mu)$ would refute Theorem 10 on that instance.","tokens_in":40460,"feed_emoji":"🎯","tokens_out":12410,"duration_ms":117551,"temperature":0.7,"pith_summary":"Best-arm identification asks how many samples are needed to name the arm with the largest mean while keeping the error probability below a prescribed $\\delta$. This paper shows that for unrestricted unbounded-support distributions the answer is 'infinitely many': every $\\delta$-correct algorithm must pull each non-best arm infinitely often in expectation. It then identifies a mild condition that restores tractability: the algorithm knows a strictly increasing convex function $f$ with $f(y)/y \\to \\infty$ and a bound $B$ such that every arm satisfies $E f(|X|) \\le B$, for example a known bound on a moment above the first. Under this condition the paper constructs an algorithm, AL1, whose expected stopping time matches the distribution-dependent lower bound asymptotically as $\\delta \\to 0$: $\\limsup_{\\delta\\to 0} E_\\mu(\\tau_\\delta)/\\log(1/\\delta) \\le 1/V(\\mu)$. This matters because heavy-tailed and other non-exponential-family distributions, common in simulation and recommendation systems, can now be handled with the same efficiency guarantees previously available only for single-parameter exponential families.","feed_headline":"Known moment bounds make heavy-tailed best-arm search provably optimal","feed_subtitle":"A δ-correct algorithm matches the sample-complexity lower bound once a moment bound is known.","key_machinery":"The load-bearing object is $KL_{\\inf}(\\eta,x)$, the minimum Kullback-Leibler divergence from an arm distribution $\\eta$ to any distribution in $\\mathcal{L}$ whose mean lies on the required side of $x$; it measures how hard it is to confuse $\\eta$ with an alternative arm of mean $x$. This functional carries both halves of the argument: the lower bound $V(\\mu)$ is a max-min over allocation proportions of sums of $KL_{\\inf}$, and the algorithm's generalized likelihood-ratio stopping statistic is the same sum evaluated at empirical distributions. Theorem 12 gives a dual representation, $KL_{\\inf}(\\eta,x)=\\max_{(\\lambda_1,\\lambda_2)\\in R_2} E_\\eta \\log(1-(X-x)\\lambda_1-(B-f(|X|))\\lambda_2)$, a two-variable concave maximization over Lagrange multipliers for the mean and moment constraints. That makes the functional computable and yields exponential concentration inequalities for its empirical version; compactness of $\\mathcal{L}$ in the Wasserstein metric plus Berge's maximum theorem then make the optimal proportions $t^*(\\mu)$ and the value $V(\\mu)$ continuous in the arm distributions, so the plug-in sampling rule converges to the oracle proportions.","core_discovery":"The paper's central claim is that a known moment-type bound is the right dividing line between tractable and intractable $\\delta$-correct best-arm selection. On the intractable side, Theorem 3 shows that if the allowed class of distributions is KL right dense — meaning every arm distribution can be perturbed by arbitrarily small KL divergence into another distribution in the class with a larger mean — then under any $\\delta$-correct algorithm $E_\\mu N_k(\\tau) = \\infty$ for every non-best arm $k \\ge 2$. On the tractable side, Theorem 10 shows that for the class $\\mathcal{L} = \\{\\eta : E_\\eta f(|X|) \\le B\\}$, algorithm AL1 with the stopping threshold $\\beta(n,\\delta) = \\log(C n^\\alpha / (\\delta (\\log n)^K (\\log(1/\\delta))^{2K+1}))$ and batch size $m = o(\\log(1/\\delta))$ is $\\delta$-correct and satisfies $\\limsup_{\\delta\\to 0} E_\\mu(\\tau_\\delta)/\\log(1/\\delta) \\le 1/V(\\mu)$, where $V(\\mu)$ is the value of the max-min lower-bound problem. In words, once the algorithm is handed a valid moment bound, it stops with error at most $\\delta$ and its sample complexity reaches the lower bound to first order as $\\delta$ shrinks.","pith_inferences":["Estimating $(f,B)$ from early samples with a conservative confidence multiplier is a natural extension, but the paper does not analyse it; whether $\\delta$-correctness survives with only a $\\log\\log(1/\\delta)$ penalty is open.","The KL right-density impossibility should transfer to $\\delta$-correct selection of other unbounded functionals, such as quantiles or variances: without a known envelope constraint, the same transportation inequality forces infinite expected pulls.","A practical reading of the batch-size analysis is that the user's ratio of sampling cost to computation cost determines whether to batch aggressively (cheap samples) or finely (expensive samples); making the batch size adapt online is left open.","The dual representation of $KL_{\\inf}$ is a reusable template for other constraint sets, e.g., known bounds on $E e^{\\lambda X}$ or on variance, which would yield a family of $\\delta$-correct algorithms beyond the class $\\mathcal{L}$ studied here."],"forward_implications":["For any finite set of arms satisfying a known bound $E f(|X|) \\le B$, AL1 gives first-order optimal sample complexity, roughly $\\log(1/\\delta)/V(\\mu)$, while keeping the error probability at most $\\delta$.","Without such a bound, the problem is hopeless in expectation: every $\\delta$-correct algorithm pulls every suboptimal arm infinitely often when the allowed class is KL right dense.","Under the paper's cost model, the batch size minimizing total sampling-plus-computation cost is $\\Theta(\\log(1/\\delta))$; this preserves $\\delta$-correctness but loses the asymptotic optimality ratio, whereas $m = o(\\log(1/\\delta))$ preserves both.","The theory reduces the previous exponential-family-only setting to a special case: when arms form a single-parameter exponential family, $KL_{\\inf}$ collapses to ordinary KL divergence between exponential-family distributions.","If bounded support is known in advance, the dual problem becomes one-dimensional, and the same algorithm simplifies while retaining $\\delta$-correctness and asymptotic optimality."],"supporting_citations":[{"why":"Supplies the transportation inequality that lower-bounds the sample complexity of any δ-correct algorithm and seeds the max-min lower bound.","marker":"Kaufmann et al. (2016)"},{"why":"Provides the asymptotically optimal δ-correct algorithm for single-parameter exponential families that this paper generalizes to the moment-bounded class L.","marker":"Garivier and Kaufmann (2016)"},{"why":"Gives the dual representation of KLinf for bounded random variables, which the paper extends to unbounded-support distributions in L.","marker":"Honda and Takemura (2010)"},{"why":"Develops the concentration inequality for the sum of Na KLinf terms for Bernoulli arms, generalized here through Theorem 13.","marker":"Magureanu et al. (2014)"},{"why":"Contributes the max-min characterization of optimal allocation proportions in ordinal optimization, extended in Theorem 5.","marker":"Glynn and Juneja (2004)"},{"why":"Establishes the related impossibility of effective mean tests without distributional restrictions, a precedent for Theorem 3.","marker":"Bahadur and Savage (1956)"}],"fun_headline_variants":["Moment bound separates tractable from impossible best-arm search","Without moment bounds, δ-correct best-arm needs infinite samples","Known moment bound yields optimal δ-correct best-arm search","δ-correct best-arm: moment bound gives optimal sample complexity","Moment-bound assumption turns heavy-tailed best-arm tractable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the algorithm is handed a correct pair $(f,B)$ that really bounds $E f(|X|)$ for every arm; if the bound is wrong, unknown, or the true distribution violates it, the $\\delta$-correctness proof and the matching constant $V(\\mu)$ no longer apply.","fun_headline_variants_meta":{"raw":{"variants":["Moment bound separates tractable from impossible best-arm search","Without moment bounds, δ-correct best-arm needs infinite samples","Known moment bound yields optimal δ-correct best-arm search","δ-correct best-arm: moment bound gives optimal sample complexity","Moment-bound assumption turns heavy-tailed best-arm tractable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001097,"raw_usage":{"total_tokens":4637,"prompt_tokens":1062,"completion_tokens":3575,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":678,"completion_tokens_details":{"reasoning_tokens":3492}},"tokens_in":678,"tokens_out":3575,"duration_ms":23467,"temperature":1.0,"reasoning_tokens":3492,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:23:18.639495+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a two-arm instance with Pareto distributions, set $f(y)=y^2$ and $B$ equal to the second moment of the better arm while the other arm has second moment $B+\\varepsilon$, run AL1 with the declared $B$ for $\\delta=10^{-3},10^{-6},10^{-8}$, and measure the empirical error frequency and $E_\\mu(\\tau_\\delta)/\\log(1/\\delta)$; error above $\\delta$ or a ratio that does not approach $1/V(\\mu)$ would refute Theorem 10 on that instance.","supporting_citations":[],"review_version":1}