{"id":"a80df894-8d9f-4352-8f62-48390918c3fc","arxiv_id":"2501.02926","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Offline data from a distribution of bandit tasks provably identifies near-optimal algorithm hyperparameters, with inter-task sample complexity depending on a new piecewise-complexity measure QD.","lead":"This paper gives sample-complexity guarantees for learning bandit hyperparameters, such as the UCB exploration parameter, from offline runs on related tasks, and proves that fully online tuning is information-theoretically impossible. The framework covers UCB, LinUCB, and GP-UCB, and the authors argue it beats corralling-style methods in experiments.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 6.2's n>QD policy cannot compute the regret-based loss from bandit feedback; un-pulled arm rewards are never observed, so the claimed min{n,QD}T intra-task complexity is unsupported.","rationale":"The paper's core contribution is a transfer-learning bound for bandit hyperparameters with both inter- and intra-task complexity. The reader's weakest assumption is exactly the load-bearing gap: computing l^{P,z}_T(rho) from bandit feedback within the stated budget. I agree. The proof of Theorem 6.2 (Appendix D) assumes that running the algorithm once per piece gives the loss for that piece, but under bandit feedback it gives only the rewards of pulled arms; the regret baseline requires the full reward realization. This is an internal inconsistency with the paper's own Algorithm 2, which inputs the complete n x T reward matrix. The flaw is not about disagreement with consensus; it is a concrete correctness gap in a headline theorem. I also note the manuscript's Limitation section says intra-task bounds 'can be improved with more careful arguments,' but it does not acknowledge this identifiability problem. If the concern is settled by the proposed two-arm/T=2 test, the verdict should remain REJECT (i.e., unchanged), since the advertised intra-task guarantee is unsupported. The inter-task framework may be salvageable, but the central claim as stated fails.","tokens_in":23689,"tokens_out":6510,"duration_ms":63248,"concrete_test":"Take n=2, T=2, with a fixed task and a rho whose loss piece is constant. Run the Theorem 6.2 policy for one piece, recording only pulled-arm rewards. Compute the empirical loss from these observations. Then compute the true l^{P,z}_T(rho) using the complete reward matrix (including the arm not pulled). Choose two realizations of the un-pulled arm's rewards that keep the observed data identical but change the best-arm baseline; the two true losses differ, so the offline data cannot determine the loss. This directly refutes the claim that QD*T pulls suffice to implement the ERM.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Under bandit feedback, the loss l^{P,z}_T(rho) used by the ERM is regret against the best arm in the fixed realization z, i.e. max_a sum_t r_{t,a} - sum_t r_{t,A_t(rho)}. The n<=QD case of Theorem 6.2 is valid: pulling each arm T times reveals the full reward matrix. The n>QD case is not. Appendix D claims 'for any single piece, we need at most T arm pulls to compute the loss over the piece' by running A_rho once per piece. But one run reveals rewards only for pulled arms. The cumulative reward of the best arm, which may be pulled rarely or never, is not observed, so the regret baseline is uncomputable. Two reward realizations that induce the same pulled-arm rewards but differ on un-pulled arms yield different l^{P,z}_T(rho) yet identical offline data. This is not a missing detail: Algorithm 2 requires the full n x T reward matrix as input, i.e. nT pulls per task, confirming that the QD*T policy cannot evaluate its objective. Hence Theorem 6.2's intra-task bound does not follow, and the abstract's promised pull complexity is unsupported. The inter-task bound (Theorem 6.1) and piece-count analysis may still hold; the flaw is specific to the bandit-feedback intra-task claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies offline-to-online transfer of hyperparameters for stochastic bandits. The authors define a task distribution over bandit problems, introduce a derandomized dual complexity QD that counts the expected number of piecewise-constant regions of the per-task loss as a function of the hyperparameter, and prove an inter-task sample complexity bound N = O((H/epsilon)^2 (log QD + log 1/delta)) for uniform convergence of the empirical loss. They further claim an intra-task sample complexity of min{n, QD}T pulls per task, instantiate QD for UCB, LinUCB, and GP-UCB, present an impossibility result for tuning without transfer, and report experiments against corralling baselines.","tokens_in":23930,"tokens_out":12869,"duration_ms":129819,"significance":"If the results held, the paper would provide a clean application of data-driven algorithm design to stochastic bandits, with a useful separation of inter-task and intra-task sample complexity. The inter-task uniform convergence argument via piecewise-constant derandomized losses is plausible and may be of independent interest, and the piece-count bounds for UCB, LinUCB, and GP-UCB are competent. However, the central intra-task claim is invalid under bandit feedback: the proposed policy cannot compute the loss function it needs, and the experiments do not validate the claimed bandit-feedback regime. Since the abstract and Section 6 advertise this intra-task complexity as a main contribution, the paper in its current form does not establish its principal claim.","major_comments":[{"comment":"The claim that an offline policy with E[To] = min{n, QD}T suffices for the ERM is not supported in the bandit-feedback setting. For a fixed realization z, the loss l^{P,z}_T(rho) is regret against the best arm, i.e., max_a sum_t r_{t,a} - sum_t r_{t,A_t(rho)}. A single run of A_rho observes only the rewards of pulled arms; the best-arm baseline may involve arms pulled rarely or never, so it is unobservable. Two reward realizations that agree on all pulled-arm rewards but differ on un-pulled arms produce identical offline data but different l^{P,z}_T(rho). Moreover, the piece boundaries themselves cannot be computed online: Algorithm 3 recursively computes critical points from the future reward arrays R_i for all arms, and Appendix D's 'sequentially compute the pieces' presupposes access to the full reward realization. Under bandit feedback, neither the pieces nor the per-piece loss are computable, so the ERM objective in Algorithm 2 cannot be evaluated. This is confirmed by Algorithm 2's input, which is the complete n x T reward matrix for each task, i.e., nT pulls per task. The n <= QD case is valid, but the n > QD case, which delivers the advertised min{n, QD}T bound, is unsupported. The conclusion's remark that the intra-task bound 'can be improved with more careful arguments' understates the problem: the proposed policy is not merely suboptimal but infeasible.","section":"Section 6, Theorem 6.2 and Appendix D"},{"comment":"The experiments do not provide evidence for the claimed bandit-feedback intra-task complexity. Algorithm 2 requires the full n x T reward matrix as input, and in the CIFAR experiments the offline data consist of the classification accuracy for all 11 learning-rate arms over To = 20 steps, which is full-information data collection with cost n*To per task. The synthetic experiments similarly appear to generate complete reward matrices. Thus the empirical protocol corresponds to the full-information variant (or to the n <= QD case), not to a bandit-feedback policy with E[To] = min{n, QD}T. The advertised practical relevance of low intra-task complexity in the bandit setting is therefore not validated by the experiments.","section":"Section 9 and Appendix I"}],"minor_comments":[{"comment":"The line 'Adding up over all time steps, we have at most (T - n)(T - 1)^{n-1} <= T^{n-1} critical points' is arithmetically incorrect: the hockey-stick identity gives sum_{t=n+1}^T C(t-1, n-1) = C(T, n), which is O(T^n), not O(T^{n-1}). The final conclusion log QD = O(n log T) is unaffected, but the proof should be corrected.","section":"Appendix E, proof of Theorem 7.1"},{"comment":"The text refers to 'Figure ??' for the variation of expected regret with alpha, but the figure is not properly referenced or included in the main text; please fix the placeholder.","section":"Section 7 and Appendix J"},{"comment":"The symbol P is used both for the parameter space (P subset of R^d) and for a problem instance (P in Pi), which is confusing; consider renaming one of them.","section":"Section 5"},{"comment":"There are several typos and missing references: 'addtitional' in Section 9, 'piecewise constant function..' in Theorem 6.1, 'Barlett' in Appendices C and H (should be Bartlett), and 'CIFAR-10 and CIFAR-100 [?]' missing citation.","section":"Throughout"},{"comment":"The return statement minimizes sum_k l^{Pk,zk}_T(alpha) over alpha, but does not specify tie-breaking and does not state how l^{Pk,zk}_T(alpha) is computed under bandit feedback; this is connected to the first major comment.","section":"Algorithm 2"}],"recommendation":"reject","confidential_remarks":"The inter-task machinery and the piece-count bounds appear sound as far as I checked, and the Theorem 7.1 counting typo is minor. The rejecting issue is the invalidity of Theorem 6.2's intra-task claim under bandit feedback, together with the experiments' full-information protocol. If the authors resubmit with the bandit-feedback intra-task claim removed or replaced by a clearly stated full-information assumption, the inter-task results could form the basis of a useful, if less ambitious, paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, the paper is worth reading, but not as-is. The genuinely new material is the inter-task transfer framework built on derandomized dual complexity (QD): finite-sample guarantees for tuning UCB, LinUCB, and GP-UCB from offline logs, plus an impossibility result showing single-instance hyperparameter tuning is information-theoretically hard. Those parts are mostly solid. Theorem 6.1 is a standard Rademacher uniform convergence argument, and the piece-counting bounds in Theorems 7.1–8.1 are plausible. The small counting typo in Theorem 7.1 (O(T^{n-1}) vs O(T^n)) does not change the log QD = O(n log T) conclusion. The experiments are suggestive, though not the main point.\n\nThe serious problem is Theorem 6.2's intra-task guarantee under bandit feedback. The claim is that E[To] = min{n, QD}T pulls suffice, and for n > QD the policy runs A_rho once per piece of the piecewise-constant loss. But with bandit feedback, one run of A_rho reveals rewards only for pulled arms. The loss l^{P,z}_T(rho) includes a baseline max_a sum_t r_{t,a} that can involve arms never pulled, and more importantly the piece boundaries—where the algorithm's arm selection changes—depend on the full reward realization z. A single trajectory cannot determine those boundaries or evaluate all pieces. The paper's own Algorithm 2 requires the complete n x T reward matrix as input, i.e., nT pulls per task, which confirms the issue. This is not a minor gap; it breaks the headline claim that near-optimal hyperparameters can be learned from bandit-feedback offline data within the stated intra-task budget. The inter-task results may survive, but only if the intra-task claim is either restricted to full-information feedback or replaced by an offline policy that actually works under bandit feedback. There are also signs of a rushed draft: unresolved figure references and a placeholder citation.\n\nIf you work on data-driven algorithm design or bandit hyperparameter tuning, the QD framework and the piece-counting arguments are worth citing; the impossibility result is a useful sanity check. I would not rely on Theorem 6.2 as stated. This paper deserves a serious referee—it is not a desk reject—but acceptance would reward an overstated claim. My recommendation: send to peer review with a clear instruction that the intra-task guarantee must be fixed or removed.","headline":"Solid inter-task transfer framework and QD bounds, but the headline intra-task guarantee under bandit feedback is unsupported; worth peer review, not acceptance as-is.","tokens_in":24510,"tokens_out":4343,"would_cite":true,"duration_ms":47144,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T05","62L05","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"Near-optimal bandit hyperparameters are learnable from finitely many offline runs, with explicit sample complexity bounds; per-instance tuning is provably impossible.","keywords":["stochastic bandits","hyperparameter tuning","transfer learning","sample complexity","UCB","LinUCB","GP-UCB","derandomized dual complexity"],"falsifier":"Take a two-armed bandit with fixed reward draws, record only pulled-arm rewards under the piece-by-piece policy of Theorem 6.2 when n > QD, and compare the empirical loss recovered to the true loss computed from the complete reward realization; if they differ for some α, the intra-task budget min{n, QD}T cannot support the claimed guarantee under bandit feedback.","tokens_in":23449,"feed_emoji":"🎰","tokens_out":5840,"duration_ms":50774,"temperature":0.7,"pith_summary":"This paper asks whether good hyperparameters for stochastic bandit algorithms can be learned once and reused across similar problems. It shows that tuning for a single unknown problem is information-theoretically impossible, even for the simplest multi-armed bandit, and instead studies transfer: given offline bandit runs from several tasks drawn from a fixed but unknown distribution, how many tasks and how many arm pulls are needed to pick a hyperparameter that is nearly optimal on a new task? The answers are expressed through a new quantity, the derandomized dual complexity QD, which counts the effective number of regimes in the loss landscape. The main results bound QD for UCB, LinUCB, and GP-UCB, giving inter-task sample complexity that grows logarithmically in QD and intra-task complexity of at most min{n, QD}T pulls, alongside experiments showing the learned parameter beats corralling baselines.","feed_headline":"Finite offline runs suffice to tune bandit hyperparameters","feed_subtitle":"New bounds show UCB, LinUCB, and GP-UCB parameters transfer across tasks with near-optimal regret.","key_machinery":"The central object is the derandomized dual complexity QD = E_{P~D, z~D_P} q($l^{{P,z}}$_T(·)), the expected number of constant pieces in the loss $l^{{P,z}}$_T(ρ) when the random rewards are fixed before the horizon. This quantity is the distribution-dependent complexity measure that controls the sample complexity: uniform convergence follows from bounding the Rademacher complexity of the piecewise-constant function class via Massart's lemma, and the ERM is made tractable by computing the critical points of α at which the chosen arm changes, recursively, in expected time O(QD). Pseudo-dimension arguments extend the analysis to the two-hyperparameter (α, prior means) case and to GP-UCB's noise parameter.","core_discovery":"The paper claims that the expected loss of a bandit algorithm as a function of its hyperparameter is, for a fixed reward realization, a piecewise constant function, and that the number of pieces QD controls both how many offline tasks are needed and how many pulls each task requires. Theorem 6.1 gives a uniform-convergence bound: N = O((H/ε)^2 (log QD + log 1/δ)) offline tasks suffice to guarantee that the empirical loss approximates the expected loss uniformly over the hyperparameter space. Theorem 6.2 provides an offline data collection policy achieving near-optimal transfer with an expected intra-task pull count of min{n, QD}T, and the ERM over the critical points of the piecewise loss realizes the bound. Specializing QD yields log QD = O(n log T) for UCB, O(log KT) for categorical rewards, O(T log n) for LinUCB, and a corresponding O(T log nT) bound for GP-UCB's noise parameter.","pith_inferences":["The paper's intra-task policy for n > QD runs the algorithm once per piece of the derandomized loss; under pure bandit feedback only the pulled arm's reward is seen, so computing the loss on a piece may require the full n×T reward matrix, which costs nT pulls per task rather than QDT.","The small empirical values of QD suggest that the worst-case-looking bounds translate into modest data requirements in practice, and that the piecewise structure could be exploited by other meta-learning pipelines beyond UCB-style algorithms.","Strategic design of the offline data collection policy (which tasks, which pulls) is left open; the paper's bounds assume a fixed policy, so adaptively choosing pulls could lower intra-task complexity below min{n, QD}T.","The impossibility result implies that any fully online hyperparameter tuner must either pay suboptimal regret or rely on structure across tasks, which sharpens the practical motivation for transfer-based tuning."],"forward_implications":["A practitioner who has collected offline bandit data from related tasks can provably transfer the exploration parameter: roughly O(n log T / ε²) tasks with at most min{n, QD}T pulls each give an ε-suboptimal hyperparameter on a new task.","For categorical (e.g., Bernoulli) rewards the inter-task requirement improves to O(log(KT)/ε²), making the approach practical for small horizons.","The same machinery tunes the GP-UCB noise parameter with O(T log nT / ε²) tasks, which is most useful when the online horizon T is small, as in expensive evaluations.","The ERM over critical points is computationally efficient, running in expected time O(QD), so the theoretical bounds correspond to a feasible algorithm, not just an existence proof.","Learning both the exploration parameter and arm priors simultaneously is also possible with inter-task complexity O((n+T)T log n / ε²)."],"supporting_citations":[{"why":"Massart's lemma is used to bound the empirical Rademacher complexity of the piecewise-constant loss class in Theorem 6.1.","marker":"[Mas00]"},{"why":"Rademacher complexity generalization bounds convert the complexity estimate into the uniform-convergence sample complexity of Theorem 6.1.","marker":"[BM02]"},{"why":"The data-driven algorithm design framework supplies the pseudo-dimension and ERM tools used for the GP-UCB and general hyperparameter tuning analysis.","marker":"[Bal20]"},{"why":"The GJ algorithm and pseudo-dimension bounds for parameterized loss functions are used in the proof of Theorem 7.4 for simultaneous tuning of α and arm priors.","marker":"[BIW22]"},{"why":"Defines the GP-UCB algorithm whose noise parameter is the target of the transfer bounds in Section 8.","marker":"[SKKS10]"},{"why":"Provides the pseudo-dimension uniform-convergence sample complexity results used for the GP-UCB and high-dimensional tuning bounds.","marker":"[AB99]"}],"fun_headline_variants":["Offline data tunes bandits on new tasks","Finite offline samples suffice for bandit tuning","Offline runs tune UCB, LinUCB, GP-UCB","Cross-task bandit tuning from offline pulls"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The central claim depends on the assumption that the derandomized dual function $l^{{P,z}}$_T(ρ) is piecewise constant and that it can be computed from offline bandit feedback within the stated intra-task pull budget, even though bandit feedback reveals rewards only for pulled arms, not the full realization needed to evaluate the loss.","fun_headline_variants_meta":{"raw":{"variants":["Offline data tunes bandits on new tasks","Finite offline samples suffice for bandit tuning","Offline runs tune UCB, LinUCB, GP-UCB","Cross-task bandit tuning from offline pulls"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00158,"raw_usage":{"total_tokens":6301,"prompt_tokens":938,"completion_tokens":5363,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":554,"completion_tokens_details":{"reasoning_tokens":5299}},"tokens_in":554,"tokens_out":5363,"duration_ms":38073,"temperature":1.0,"reasoning_tokens":5299,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:03:06.153607+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a two-armed bandit with fixed reward draws, record only pulled-arm rewards under the piece-by-piece policy of Theorem 6.2 when n > QD, and compare the empirical loss recovered to the true loss computed from the complete reward realization; if they differ for some α, the intra-task budget min{n, QD}T cannot support the claimed guarantee under bandit feedback.","supporting_citations":[],"review_version":1}