{"id":"17f2152c-937a-4865-bf15-c5f02b0f6e5b","arxiv_id":"2501.06258","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"E2TC achieves Õ((KT)^{4/5}) regret for stochastic contextual bandits with pre-trained neural representations and locally convex risk, without requiring extremely wide networks.","lead":"This thesis analyzes how pre-trained neural network weights can improve contextual bandit learning, proposing the Explore Twice then Commit (E2TC) algorithm. E2TC first fits the last layer with ridge regression, then fine-tunes all weights with SGD, and the paper proves sublinear regret under local convexity conditions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Main result is conditional on an unverified ellipsoidal local-convexity assumption (Assumption 4); no evidence that real neural losses satisfy it, so the conditional claim lacks empirical grounding.","rationale":"The reader's weakest-assumption analysis correctly identifies Assumption 4 as the load-bearing geometric premise. My independent reading of the proofs did not reveal an internal inconsistency: Theorem 5.1's derivation of the trajectory staying in C, the use of convexity only at iterates, and the translation from risk to regret in Theorem 2.1 appear sound under the stated assumptions. The hyperparameter choices in Theorem 5.2 are asymptotically consistent, and the dependence of Assumption 5 on d is controlled by ε0. The genuine soft spot is that the ellipsoidal convexity region is chosen for mathematical convenience (because ridge regression controls ∥·∥_{Σ0}), and no empirical or theoretical evidence is given that realistic neural network losses are convex on this particular set. The paper's own experiments show E2TC works on MNIST and wine, but they do not test whether Assumption 4 holds there. Since the central claim is explicitly conditional, the correct verdict remains CONDITIONAL; no change is needed, but the authors should add a verification of Assumption 4 and ideally provide a public implementation.","tokens_in":54611,"tokens_out":34248,"duration_ms":309627,"concrete_test":"Train the Section 6.1 MNIST network to convergence to estimate (w*, θ*); compute Σ(θ0) on the bandit digits; sample a set of points uniformly in C along dominant eigenvectors of Σ0 and random θ directions; at each sampled point compute the minimum eigenvalue of the Hessian of the empirical risk (or check the gradient inequality R(y) ≥ R(x) + ∇R(x)ᵀ(y−x) for random pairs x,y in C). If any negative eigenvalue or violated inequality is found, Assumption 4 fails for this realistic problem, and the claimed Õ((KT)^{4/5}) regime lacks a validated example.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central regret guarantee of Corollary 5.3 depends on Assumption 4, which requires R to be convex on the specific ellipsoid C = {(w,θ) : ∥w−w*∥²_{Σ(θ0)} + ∥θ−θ*∥² < εc²}. This shape is dictated by the pre-trained representation covariance, not by the loss landscape. Theorem 5.1 and its proof (Appendix A.3) show that the preconditioned SGD trajectory stays inside C only if condition (5.12) holds and if R is convex on all of C; if the true convex basin has a different geometry, or if the pre-trained weights are close in a different norm, the trajectory can leave the convex region and the risk bound, and hence all regret bounds, no longer follow. The paper itself concedes in Section 5.1 that the requirement is 'somewhat contrived,' and the experiments in Chapter 6 do not verify convexity on C for the MNIST or wine datasets. Thus the claim that E2TC achieves Õ((KT)^{4/5}) for pre-trained neural networks is only as strong as an assumption whose practical validity is untested. This is not an internal inconsistency, but it is the point where the conditional result is least supported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript (ETH master's thesis) studies stochastic contextual bandits whose rewards are modeled by a neural network $x \\mapsto w^\\top \\varphi_\\theta(x)$, with pre-training represented by an initial feature-network weight $\\theta_0$. It introduces E2TC, an explore-then-commit algorithm that first estimates the last layer by ridge regression, then runs a preconditioned SGD on all weights, and finally commits to greedy actions. The main technical result, Theorem 5.1 and Corollary 5.3, gives a high-probability suboptimality bound and an $\\tilde O((KT)^{4/5})$ regret bound under Assumptions 1--5, which include realizability, boundedness, local convexity of the risk inside the ellipsoid $C=\\{(w,\\theta):\\|w-w_*\\|^2_{\\Sigma(\\theta_0)}+\\|\\theta-\\theta_*\\|^2<\\varepsilon_c^2\\}$, and a pre-training quality condition $2\\varepsilon_0^2d+\\varepsilon_\\theta^2<\\varepsilon_c^2$. A separate analysis treats the weak-training regime with fixed representations as a misspecified linear bandit. Experiments on MNIST and wine-quality data compare E2TC with greedy baselines and ablations.","tokens_in":127,"tokens_out":23911,"duration_ms":321311,"significance":"If the conditional claims hold, the paper is a real step beyond NTK-width assumptions for neural contextual bandits. The low-risk-to-low-regret reduction (Theorem 2.1) is clean and clearly useful. The high-probability SGD containment results in Sections 4.1--4.2 are carefully argued, and the weak-training bounds expressed through the $\\varepsilon_0$ misspecification measure are nonstandard and interesting; the dimension independence of the $(KT)^{4/5}$ term when $\\varepsilon_0=0$ is a notable observation. The appendix contains substantial, checkable proofs and reproduces the external ridge-regression theorem, which is a concrete strength of the manuscript.","major_comments":[{"comment":"The central regret guarantee of Corollary 5.3 rests on Assumption 4, which requires the risk to be convex in the specific ellipsoid $C$ whose metric is determined by $\\Sigma(\\theta_0)$. This shape is dictated by the ridge-regression analysis, not by any known geometric property of neural-network losses, and the manuscript itself acknowledges in Section 5.1 that the requirement is 'somewhat contrived.' Theorem 5.1's proof in Appendix A.3 needs the SGD trajectory to remain inside $C$; if the true convex basin has a different shape, the bounds do not follow. The experimental chapter does not verify convexity on $C$ for either the MNIST or the wine-quality task, nor does it check the coupled pre-training condition $2\\varepsilon_0^2d+\\varepsilon_\\theta^2<\\varepsilon_c^2$ (Assumption 5), which in particular forces $\\varepsilon_0=O(d^{-1/2})$ when $\\varepsilon_c=O(1)$. This is not an internal inconsistency, but it is the main point where the paper's practical interpretation is less supported than its formal, conditional statement. I would ask for one of the following: an explicit reframing of the main result as purely conditional on an unverified geometric assumption; an empirical validation of local convexity in $C$ (for example, checking gradient monotonicity or Hessian positive semidefiniteness along the E2TC trajectory); or a relaxation of Assumption 4 to a more natural geometric condition.","section":"Section 5.1, Assumptions 4 and 5"},{"comment":"The hyperparameter tuning in Theorem 5.2 requires knowledge of the problem-dependent constants $\\varepsilon_0$, $\\varepsilon_\\theta$, $\\varepsilon_c$, and $\\Delta\\varepsilon$ in order to choose $T_1$, $T_2$, $\\lambda$, $\\zeta$, and $\\varepsilon_w$. As stated, E2TC is therefore not a fully adaptive algorithm: a user cannot instantiate it from the theorem without these unknown quantities, and the experiments search over hyperparameters instead. This is a limitation that should be discussed explicitly rather than left implicit in the statement of Corollary 5.3, which presents $T_1=d^2$, $T_2=(KT)^{4/5}$ as a valid selection while the supporting theorem's conditions depend on quantities that are not available to the learner.","section":"Section 5.2, Theorem 5.2 and Corollary 5.3"}],"minor_comments":[{"comment":"The abstract says 'Stochastic Gradient Decent'; this should be 'Stochastic Gradient Descent'.","section":"Abstract"},{"comment":"The sentence 'Note that $\\theta_0 \\in C_\\theta$, since $\\varepsilon_\\theta < \\varepsilon_{c,\\theta}$' uses undefined notation $C_\\theta$ and $\\varepsilon_{c,\\theta}$; the intended meaning appears to be $\\|\\theta_0-\\theta_*\\|<\\varepsilon_c$.","section":"Section 5.1, after Assumption 4"},{"comment":"The notation $\\varepsilon_0\\sqrt{d}KT$ is ambiguous: it should be typeset as $\\varepsilon_0\\sqrt{d}\\,KT$ or as $\\varepsilon_0\\sqrt{dKT}$, since the two readings differ. A parenthesized form would prevent confusion.","section":"Equations (3.99), (3.100), and abstract"},{"comment":"There is a typo: 'helpfullness' should be 'helpfulness'.","section":"Section 6.2"},{"comment":"The conclusion says 'explore-than-commit' where 'explore-then-commit' is meant.","section":"Section 7"}],"recommendation":"major_revision","confidential_remarks":"This is a carefully written theory thesis, and the main theorems appear internally consistent under the stated assumptions. My recommendation is driven by the gap between the formal conditional result and the practical claims in the abstract and experiments: the central Assumption 4 is explicitly acknowledged as 'somewhat contrived' and is never validated on the tasks where the algorithm is tested. If the authors agree to reframe the contribution as explicitly conditional and discuss the strength of Assumption 5, or add a concrete empirical check of the basin geometry, I would be willing to support acceptance after revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nQuick take: this master's thesis is a real contribution to the theory of pre-trained neural contextual bandits, and the main regret bound is conditionally sound, but the load-bearing geometric assumption — local convexity in an ellipsoid shaped by the pre-training covariance — is as contrived as the author admits, and no empirical evidence addresses it.\n\nWhat's new: E2TC, the ε0 misspecification measure, and the weak-training regret bounds O(ε0√dKT + (KT)^(4/5)) and O(ε0√dKT + d^(1/3)(KT)^(2/3)). The reduction from low risk to low regret (Theorem 2.1) is clean. The proofs are detailed and mostly self-contained, and the paper cites external lemmas properly — including the time-uniform Hoeffding-Azuma from Kassraie et al., which is published and relevant. The weak-training analysis without convexity assumptions is the strongest part, and the dimension-independent sublinear term from stochastic contexts is genuinely interesting.\n\nSoft spots, in proportion: Assumption 4 is the main one. The convex basin C is defined by the covariance of the pre-trained representations, not by the loss landscape. The author calls it 'somewhat contrived' in Section 5.1, which is honest, but the entire Õ((KT)^(4/5)) corollary depends on it. The paper gives no empirical check that real losses satisfy convexity on that specific ellipsoid. That's a real gap, though not a fatal flaw: the result is conditional in a clearly stated way. The hyperparameter feasibility conditions in Theorem 5.2 are complex and asymptotic; making them practical requires non-trivial tuning knowledge. The experiments are honest but show greedy baselines beating E2TC, which the author concedes — so the empirical section is not evidence for the algorithm's practical value, only for its sample-complexity behavior in the wine experiment. No code is provided.\n\nVerdict: the central argument holds up under the stated assumptions, and the paper is clear about what those assumptions are. It deserves a serious referee: the model of pre-training quality as ε0 and the weak-training bounds are worth engaging with even if the main local-convexity theorem is too strong for most real losses. I'd send it to review, and I'd want the authors to add a verification or discussion of Assumption 4 on a real loss landscape.\n\nFor your reading group: maybe — good for a theory group discussing what 'pre-training helps' should mean. I would cite the ε0 misspecification measure in my own work.\n\nRecommendation: engage; send to peer review with requests for Assumption 4 discussion and code/data.","headline":"A genuinely new conditional theory for pre-trained neural bandits, but the load-bearing convexity assumption is unverified and 'somewhat contrived' as the author admits.","tokens_in":55441,"tokens_out":1912,"would_cite":true,"duration_ms":19060,"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":"Pre-training can make neural contextual bandits learnable: if the pre-trained representation is close to the true one and the loss is convex in a specific ellipsoid, the E2TC algorithm achieves ~(KT)^{4/5} regret.","keywords":["contextual bandits","pre-training","neural networks","regret bounds","ridge regression","stochastic gradient descent","local convexity","explore-then-commit"],"falsifier":"Construct a two-layer ReLU network and a context distribution for which the Hessian of the risk is indefinite inside $C$ while Assumption 5 still holds, run E2TC with $T_1 = d^2$ and $T_2 = (KT)^{4/5}$, and check whether the regret stays sublinear; a linear regret curve or an SGD trajectory that exits $C$ would falsify the claimed $\\tilde{O}((KT)^{4/5})$ guarantee.","tokens_in":54319,"feed_emoji":"🎯","tokens_out":4920,"duration_ms":48124,"temperature":0.7,"pith_summary":"The thesis asks whether pre-training, in the form of initial weights for the representation layers of a neural network, can replace the extreme over-parameterization that most theoretical guarantees for neural contextual bandits require. It argues yes: under five assumptions — i.i.d. contexts, realizability, bounded regularity, local convexity of the mean-squared risk in an ellipsoid around the true weights, and pre-trained weights whose misspecification is smaller than the basin size — the Explore Twice then Commit (E2TC) algorithm attains sublinear regret ~(KT)^{4/5}. This matters because it moves neural bandit theory from the neural tangent kernel regime, where network width must grow polynomially with the horizon, to modest networks with a warm start. The thesis also covers the weak training case where only the last layer is learned, giving regret bounds with an explicit misspecification term.","feed_headline":"Pre-trained weights cut neural bandit regret to T^{4/5}","feed_subtitle":"Two-stage explore-then-commit shows smaller networks can learn when the loss is only locally convex.","key_machinery":"The central object is the E2TC algorithm and its compatible convex basin. E2TC first collects $T_1$ random actions and estimates the last layer $w_0$ by ridge regression on the pre-trained features $\\varphi_{\\theta_0}$; it then collects $T_2$ random actions and runs SGD on the joint weights $(w,\\theta)$, with the $w$-update preconditioned by the regularized sample covariance of the pre-trained features; finally it commits to greedy actions. The basin $C$ is defined by the same $\\Sigma(\\theta_0)$-weighted norm that ridge regression controls, so the two exploration stages fit together: ridge regression lands inside $C$, and a time-uniform Hoeffding-Azuma bound keeps the SGD trajectory inside $C$.","core_discovery":"The central claim is that a pre-trained feature map converts an intractable global optimization problem into a local one: if the loss is convex inside the ellipsoid $C = \\{(w,\\theta) : \\|w-w_*\\|^2_{\\Sigma(\\theta_0)} + \\|\\theta-\\theta_*\\|^2 < \\varepsilon_c^2\\}$, and the pre-trained weights satisfy $2\\varepsilon_0^2 d + \\varepsilon_\\theta^2 < \\varepsilon_c^2$, then a two-phase algorithm — ridge regression on the last layer followed by preconditioned SGD on all weights — stays in the basin with high probability and outputs a network with small risk. The regret bound then follows from a low-risk-to-low-regret reduction. The proof combines random-design ridge regression bounds, which control $\\|w_0-w_*\\|$ in the $\\Sigma(\\theta_0)$-norm, with time-uniform martingale concentration to show the SGD trajectory never leaves $C$.","pith_inferences":["The crucial role of the $\\Sigma(\\theta_0)$-dependent ellipsoid suggests a testable design principle: pre-training methods that make representations more isotropic, such as the orthogonality regularization used in the experiments, should reduce the number of samples $T_1$ needed to enter the convex basin.","The basin-containment argument may extend to the Polyak-\\L{}ojasiewicz condition, which the author mentions as future work; if it does, the same two-phase structure could give sublinear regret for over-parameterized networks without the width requirements of the NTK regime.","The dimension-free sublinear term in the weak-training bound relies on contexts being stochastic and actions being drawn uniformly during exploration; for adversarial contexts, the stated $\\Omega(\\varepsilon \\min\\{T,K\\})$ lower bound shows this regime is genuinely easier than the adversarial case."],"forward_implications":["If the conditions hold, E2TC attains regret $\\tilde{O}((KT)^{4/5})$ when $d = O(T^{2/5})$ and $K = O(T^{1/5})$; this is sublinear in the horizon $T$.","When only the last layer is learned, the problem reduces to a misspecified linear bandit with regret $O(\\varepsilon_0\\sqrt{d}KT + (KT)^{4/5})$ or $O(\\varepsilon_0\\sqrt{d}KT) + \\tilde{O}(d^{1/3}(KT)^{2/3})$, depending on the regularization strength.","The first weak-training bound has a dimension-independent sublinear term, made possible by stochastic contexts, so the dependence on $d$ can be dropped while only $K$ and $T$ remain.","If the last-layer risk is strongly convex in $w$, even weak learning achieves sublinear regret, $(\\varepsilon_0\\sqrt{d/\\mu} + 1)(KT)^{4/5}$, suggesting that strong convexity is not the right framework for neural network learning.","The sample-complexity bounds behind these regret guarantees apply directly to offline learning from pre-trained weights, since the exploration phases produce i.i.d. data."],"supporting_citations":[{"why":"Supplies the random-design ridge regression analysis (Theorem 16) that controls the last-layer estimate in the $\\Sigma(\\theta_0)$-norm, which is the key first-stage guarantee.","marker":"[18]"},{"why":"Provides the time-uniform Hoeffding-Azuma inequality (Lemma 26) used to show the SGD trajectory stays inside the convex basin with high probability.","marker":"[22]"},{"why":"Provides the convex SGD analysis and the Rademacher-complexity tools that underlie the high-probability suboptimality bounds in Section 4.","marker":"[36]"},{"why":"Supplies the standard bandit background, including the covering argument used in the noise bound for ridge regression and the low-risk-to-low-regret reduction structure.","marker":"[24]"},{"why":"Defines the prior neural contextual bandit result (NN-UCB) whose width requirements E2TC aims to relax, and provides the baseline regret scaling that motivates the comparison.","marker":"[21]"},{"why":"Introduces a similar local-convexity bandit analysis (GO-UCB) that requires an empirical-risk-minimization oracle; E2TC replaces that oracle with pre-trained weights.","marker":"[30]"}],"fun_headline_variants":["Pre-trained nets cut bandit regret to T^{4/5}","Explore twice, commit once: fast neural bandit learning","Warm-started neural bandits reach T^{4/5} regret","Local convexity makes pre-trained bandits efficient","E2TC: pre-training unlocks sublinear regret in bandits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The mean-squared risk is convex on the specific ellipsoid $C$ whose shape is fixed by the covariance of the pre-trained representations, and the pre-trained weights land inside that ellipsoid; the argument collapses if the true convex basin has a different shape or the weights are not close in that exact norm.","fun_headline_variants_meta":{"raw":{"variants":["Pre-trained nets cut bandit regret to T^{4/5}","Explore twice, commit once: fast neural bandit learning","Warm-started neural bandits reach T^{4/5} regret","Local convexity makes pre-trained bandits efficient","E2TC: pre-training unlocks sublinear regret in bandits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000301,"raw_usage":{"total_tokens":1813,"prompt_tokens":1099,"completion_tokens":714,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":715,"completion_tokens_details":{"reasoning_tokens":626}},"tokens_in":715,"tokens_out":714,"duration_ms":7349,"temperature":1.0,"reasoning_tokens":626,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:20:55.168677+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a two-layer ReLU network and a context distribution for which the Hessian of the risk is indefinite inside $C$ while Assumption 5 still holds, run E2TC with $T_1 = d^2$ and $T_2 = (KT)^{4/5}$, and check whether the regret stays sublinear; a linear regret curve or an SGD trajectory that exits $C$ would falsify the claimed $\\tilde{O}((KT)^{4/5})$ guarantee.","supporting_citations":[],"review_version":1}