{"id":"1f2834be-f599-4f60-a727-30fbd7211c66","arxiv_id":"2411.12154","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"TRAiL, a tangential forced-exploration algorithm for linear bandits, achieves Omega(sqrt(T)) inference quality and O(sqrt(T) log T) regret with high probability, and a new lower bound shows regret and inference quality must trade off.","lead":"An online learning algorithm called TRAiL is introduced for linear bandits: it adds sideways random noise to the currently best-looking action, then projects back onto the allowed set. The paper proves the algorithm learns the unknown reward parameter at an optimal rate while keeping regret near the theoretical minimum.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 7 applies geometric bounds to a⋆(θ̂_t) without proving θ̂_t ∈ Θ; the unconstrained RLS estimate can leave Θ, so the inference guarantee's engine is not established as written.","rationale":"The reader's weakest-assumption call is exactly the concern I find most load-bearing: the geometric lemmas are proved for a ⋆(θ) with θ ∈ Θ, but Algorithm 1 uses a ⋆(θ̂_t) for arbitrary RLS estimates. My stress-test agrees with the reader's assessment that this is a genuine gap in the proof of Theorem 6 as written. It does not show the theorem is false; a likely repair exists by either proving θ̂_t remains in a region where Assumption 3 holds, modifying Algorithm 1 to project θ̂_t onto Θ before choosing a ⋆, or extending Assumption 3 to all reachable estimates. But none of those moves is present in the manuscript. Because the central claim depends on Lemma 7, and Lemma 7's proof is not valid on the current hypotheses, the paper should not be accepted as establishing the announced guarantees. The reader already assigned CONDITIONAL with moderate confidence, and this concern supports that verdict; I see no reason to move to REJECT, since the gap is identifiable and plausibly fixable, and no evidence of circularity or dishonest claims appears. The secondary omission of Lemma 9's proof also warrants attention, but the geometric-domain mismatch is the more fundamental issue: even a correct matrix Freedman inequality would not repair Lemma 7. The proposed concrete test directly probes the disputed inequality and would settle whether the concern lands.","tokens_in":35670,"tokens_out":7321,"duration_ms":78491,"concrete_test":"Construct a concrete falsification test for Lemma 7. Take n = 2, A = {x : ||x|| ≤ 1}, Θ = {θ = (cos φ, sin φ) : φ ∈ [−π/6, π/6]}, θ* = (1,0), and set the initial estimate θ̂_1 = (0,1) ∉ Θ. Run Algorithm 1 with λ and D satisfying Assumption 4, using zero noise. At each round, compute E_{s-1}[a_s a_s^T] explicitly from the known perturbation distribution, and check whether Σ_{s=1}^t λ_min(E_{s-1}[a_s a_s^T]) ≥ D c0√t − c2 for t up to F(1/T). If the inequality fails, Lemma 7 is false as stated and Theorem 6 has an unproven hypothesis. A simpler analytical check: verify that a⋆((0,1)) = (0,1) lies outside A⋆(m′) for small m′, so Assumption 3(c) gives no bound on ℓ1_s in Eq. (71).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is Lemma 7 (Eq. 57), the deterministic source of the Ω(√t) growth in λ_min. Its Steps 1–2 invoke Assumption 3(b) and 3(c) at a⋆(θ̂_s), e.g. in Eq. (71) and in the bound mφ/a⋆(θ̂_s) ≤ mφ/amin. Those assumptions are stated only for a ∈ A⋆(m′), the m′-neighborhood of maximizers for θ ∈ Θ. However, θ̂_s = V_{s-1}^{-1} Σ_{j<s} a_j Y_j is an unconstrained RLS estimate; nothing in Algorithm 1 or in the assumptions forces θ̂_s ∈ Θ, and before the Theorem 6 event begins at F(δ) no control over a⋆(θ̂_s) is available. If θ̂_s points outside Θ, a⋆(θ̂_s) can leave A⋆(m′), and for a thin strongly convex sublevel set it can even have norm below amin or have an angle with its own normal violating (9). Then the per-step lower bound (59) can fail, and the compensation λ = c2 in Lemma 7 may be insufficient because the missing Dc0√s contributions accumulate over a growing interval. Lemma 4 does not repair this: it is stated only for θ1, θ2 ∈ Θ. This is a domain mismatch in the proof, not a matter of constants. The separate omission of Lemma 9's proof is secondary: even granting Lemma 9, the geometric-domain issue remains.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces TRAiL, a forced-exploration linear bandit algorithm for action sets that are sublevel sets of strongly convex functions. At each round, TRAiL computes an RLS estimate θ̂_t, selects the myopic maximizer a⋆(θ̂_t), perturbs it randomly along the tangent plane, and projects back onto the action set. The main theoretical claims are: (i) under Assumptions 1–4, λ_min(V_t) = Ω(√t) with high probability, yielding the inference guarantee in Theorem 6 that ‖θ̂_{t+1} − θ⋆‖² ≤ O(log(t/δ)/√t) simultaneously over t; (ii) a high-probability regret bound R_θ⋆(T) = O(√T log T) in Theorem 12; and (iii) a minimax lower bound Ω(√T/I_ε) in Theorem 15, derived through a van Trees inequality, together with an inference-regret trade-off of the form E[R]·λ_min(E[V_T]) ≳ T. The paper also presents experiments on ellipsoidal action sets and on L^p balls, including a discussion of why apparent violations of the trade-off on A_10 are transient.","tokens_in":35937,"tokens_out":13649,"duration_ms":147792,"significance":"If the Section 5 proof gaps are repaired, this is a strong contribution: TRAiL is computationally lightweight, explores and exploits simultaneously, and the paper promises simultaneous high-probability inference guarantees and order-optimal regret for a broad class of strongly convex sublevel-set action spaces. The matrix-martingale treatment of λ_min(V_t) and the van Trees lower bound connecting regret and inference quality are genuinely novel directions for linear bandits. The paper also provides a useful discussion, supported by experiments, of how near-non-smooth action sets such as L^p balls with large p can exhibit transient apparent violations of the inference-regret trade-off. The empirical section is suggestive rather than exhaustive, but it is clearly reported. The main reservations are technical and concentrated in Section 5, where the concentration argument currently does not go through as written.","major_comments":[{"comment":"The proof of Lemma 7 applies Assumption 3 and Lemma 3 to a⋆(θ̂_s) at every time s, but Assumption 3 is stated only for a ∈ A⋆(m′) and Lemma 3 only for a ∈ A⋆. The RLS estimate θ̂_s = V_{s−1}^{-1}Σ_{j<s} a_j Y_j is an unconstrained vector; nothing in Algorithm 1 or in Assumptions 1–4 keeps θ̂_s in Θ, and before the high-probability event of Theorem 6 begins at F(δ) there is no control over θ̂_s. Consequently, Eq. (71), the bound m_φ/a⋆(θ̂_s) ≤ m_φ/a_min in Step 2, and the projection bound borrowed from Lemma 3 are not justified for arbitrary s. This is load-bearing: the per-step lower bound (59) is the deterministic source of the Ω(√t) growth in λ_min(V_t) used in Lemma 10 and hence in Theorem 6. The same domain issue recurs in the proof of Theorem 12, where Lemma 4 is applied to θ̂_{t+1} even though Lemma 4 is stated only for θ_1, θ_2 ∈ Θ. A repair requires either a separate argument that θ̂_s stays in Θ, or a modification of the algorithm such as using a⋆(proj_Θ θ̂_t), or an explicit two-stage argument in which the rounds before F(δ) are absorbed into the additive constant c_2.","section":"Section 5, Lemma 7 (Eqs. (57), (59), (71))"},{"comment":"Lemma 9, the modified matrix Freedman inequality on which the entire high-probability inference guarantee rests, is stated without proof. Since it is a custom adaptation of Tropp's inequality rather than a verbatim quotation, the proof or an exact statement of the modification should appear in the manuscript. More seriously, the application of Lemma 9 in Lemma 10 is not correct as written. Lemma 8 bounds the predictable quadratic variation Σ_{s=1}^t E_{s−1}[(E_{s−1}[a_sa_s^T] − a_sa_s^T)^2], but Eq. (86) claims ||Σ_{s=1}^t (X_s)^2|| ≤ Cψ_t almost surely and then uses this random quadratic variation in the Freedman event. Since each X_s is bounded by 2a_max², the random sum can be O(t), not O(√t). If the intended event in Lemma 9 is the predictable quadratic variation, then Eq. (86) and the sentence 'Lemma 8 allows us to infer' must be rewritten accordingly; as written, the deduction of Eq. (87) does not follow.","section":"Section 5, Lemmas 9–10 (Eqs. (83)–(86))"}],"minor_comments":[{"comment":"The index shift between a_t and θ̂_{t+1} should be made explicit: Eqs. (92)–(95) provide bounds for a⋆(θ̂_{t+1}), while the regret sum in Eq. (100) is over t = ⌊√T⌋+1 to T for actions a_t. The argument is likely salvageable by relabeling, but as written the matching of indices is unclear.","section":"Section 6, proof of Theorem 12"},{"comment":"The heading 'Emprical Comparison with Other Algorithms' contains a typo and should read 'Empirical'.","section":"Section 8, heading"},{"comment":"The notation t ∼ log_2(1/δ) is informal; please state explicitly the range of t, e.g., t ≥ F(δ) for a specific function F, as is done in Theorem 6.","section":"Section 3, Eq. (13)"},{"comment":"The sentence 'with 1/log t log(λ_min(V_t)) → 0.4 within 5000 iterations' mixes a limiting statement with a finite-time empirical observation; please clarify whether this is a fitted finite-sample slope or an asymptotic claim.","section":"Section 9"}],"recommendation":"major_revision","confidential_remarks":"The central contribution is potentially significant, but the Section 5 concentration argument has two load-bearing problems: the geometric lemmas are applied outside their stated domain, and the Freedman step appears to use the random rather than predictable quadratic variation. Both appear repairable within the scope of the paper, so I recommend major revision rather than rejection. The lower-bound section is more solid and would be a valuable contribution once the upper-bound proof is made rigorous."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a genuinely new forced-exploration scheme for linear bandits, with a clean geometric idea and a useful inference-regret tradeoff. But the paper as written has a load-bearing proof gap: Lemma 7 applies Assumption 3 to a*(theta_hat_t) without ever showing the RLS estimate stays in Theta. I think the gap is fixable, but it needs to be fixed before the guarantees are taken as established.\n\nWhat's actually new: the tangential random walk plus projection is a neat alternative to FEL; the matrix-martingale argument for lambda_min(V_t) = Omega(sqrt(t)) on strongly convex sublevel sets is new to me; and the van Trees-based lower bound yielding the regret-inference product constraint is a solid contribution. The experiments on ellipsoids are honest, and Section 9's discussion of Lp balls is a thoughtful treatment of why short-run behavior can look like it violates the tradeoff. No circularity: the bounds are derived, not fitted.\n\nSoft spots, in order of seriousness:\n1. Lemma 7's domain mismatch. The proof of (59) uses Assumption 3(b)-(c) at a*(theta_hat_s), including the norm lower bound and the angle condition (9). But theta_hat_s is an unconstrained RLS estimate; nothing in Algorithm 1 or the assumptions keeps it in Theta. The stress-test note has this right. It's likely fixable by splitting the sum into a burn-in period and a post-F(delta) period, since the burn-in contribution is O(sqrt(log)) and can be absorbed into c2. But as written, the proof is incomplete.\n2. Lemma 9, the modified matrix Freedman inequality, is stated without proof. If it is truly a minor variant of Tropp, putting the derivation in the appendix would settle it. In a paper where the main result hinges on it, omitting it is a bad look.\n3. The 'universal' lower bound rests on Assumption 5(a), which the authors themselves note can fail for Lp balls at large p. So the universality claim should be softened.\n\nMinor: the experiments tune D beyond what Assumption 4 allows; that is fine for practice but means the empirical section does not validate the theory's regime.\n\nBottom line: the paper is worth a serious referee. I would send it out, with instructions to the authors to supply the proof of Lemma 9 and to close the theta_hat_t not-in-Theta gap in Lemma 7. If the fixes check out, this is a solid paper. If not, the central inference guarantee is unproven.","headline":"A novel forced-exploration scheme with a real but probably fixable proof gap at the heart of its inference guarantee; worth sending to referees.","tokens_in":36518,"tokens_out":3249,"would_cite":true,"duration_ms":34474,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L05","62C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"TRAiL perturbs the optimal action along the tangent plane to guarantee both √T-order inference and order-optimal regret in linear bandits.","keywords":["linear bandits","forced exploration","tangential randomization","inference quality","regret bounds","matrix martingales","minimax lower bound","strongly convex action sets"],"falsifier":"Simulate TRAiL on a strongly convex sublevel set where θ̂_t is forced (by initialization or adversarial noise) to lie outside the parameter set Θ for the first F(δ) rounds; if λ_min(V_T) fails to grow as √T with high probability, the geometric lemmas' requirement that estimates remain in Θ is load-bearing. Alternatively, run a regret-optimal algorithm on an L^p ball with p > 2 and measure regret × λ_min(V_T) empirically: if the product stays below cT permanently in the long run, the asymptotic trade-off (Regret)(Inference) ≳ T is false.","tokens_in":35401,"feed_emoji":"🎯","tokens_out":5906,"duration_ms":57224,"temperature":0.7,"pith_summary":"TRAiL is a linear bandit algorithm that, at each step, takes the action that maximizes expected reward under the current least-squares estimate, adds a random perturbation within the tangent plane of the action set, and projects back onto the set. The paper proves that with high probability the smallest eigenvalue of the design matrix grows as Ω(√T), giving an inference error bound that shrinks as 1/√t, and that cumulative regret is O(√T log T). It then proves a minimax lower bound of Ω(√T) for any algorithm on a wide class of action sets and noise models, via a Bayesian Cramér–Rao (van Trees) argument. The central trade-off is that cumulative regret and inference quality multiply to at least T: an algorithm with O(T^α) regret must have Ω($T^{{1−α}}$) inference quality. If correct, TRAiL is order-optimal up to log factors and shows that forced exploration can guarantee inference and control simultaneously.","feed_headline":"Tangential randomization gets √T inference with √T regret","feed_subtitle":"A forced-exploration bandit algorithm proves inference and control must improve at matching rates.","key_machinery":"The mechanism is tangential randomization: at each round, TRAiL solves a convex program for a*(θ̂_t), finds an orthonormal basis whose first vector is the surface normal (which Lemma 1 shows is proportional to θ̂_t), perturbs along the remaining basis vectors by independent subgaussian random variables with variance D/√t, and projects back to A. The geometry of strongly convex sublevel sets (Lemmas 2–4) ensures the projection error is O(m²) and that per-round regret is quadratic in the action distance, while a matrix Freedman inequality (Lemma 9, adapted from Tropp) controls the matrix martingale ata_t^T − E[ata_t^T] so that the eigenvalue lower bound in Lemma 7 transfers from expectation to high-probability V_t.","core_discovery":"The paper's central discovery is that random exploration confined to the tangent plane of the optimal action—with perturbation variance decaying as 1/√t—forces the design matrix of a linear bandit to fill all directions at the rate λ_min(V_T) ≳ √T with high probability (Theorem 6). This inference guarantee directly yields a high-probability regret bound O(√T log T) (Theorem 12). Equally central, the paper proves a trade-off: over any policy, the cumulative regret and the minimum-eigenvalue inference quality satisfy (regret)(inference) ≳ T in a Bayesian sense (Theorems 13 and 15), implying an Ω(√T) minimax lower bound for a broad family of action sets and noise distributions. As a corollary, regret-optimal control cannot be achieved with inference that is too slow or too fast; the rates must match.","pith_inferences":["The regret–inference product inequality suggests a design heuristic for adaptive experiments: when the goal is both optimization and estimation, choose exploration noise so that information accumulation tracks the regret rate, rather than maximizing information independently.","The transient 'illusion' on L^p balls implies that finite-horizon comparisons of bandit algorithms that focus only on regret may miss inference deficits that become decisive asymptotically; evaluating both metrics is safer.","The matrix-martingale deviation argument may transfer to other forced-exploration schemes (e.g., posterior sampling variants) and to adaptive control settings such as LQR, where a similar inference–control trade-off is being studied.","A testable quantitative prediction: for any policy with exactly O(T^α) regret on a strongly convex action set, the empirical product (regret × λ_min(V_T)) should stay above a constant multiple of T over long horizons once the burn-in phase ends."],"forward_implications":["If TRAiL's guarantees hold, linear bandits on strongly convex sublevel sets admit a single algorithm that gives both high-probability inference and order-optimal regret without separate exploration/exploitation phases.","Any algorithm that achieves O(T^α) expected regret must accumulate Ω(T^{1−α}) inference quality, so \"free\" inference is impossible: regret and inference rates are locked together.","The minimax regret lower bound Ω(√T) extends to general action sets and noise processes with finite Fisher information I_ε, not just spheres or L^p balls.","Empirically observed \"cheap control\" on L^p balls—near-optimal regret with poor inference—is transient and must vanish asymptotically for smooth strongly convex sets.","The proof technique also yields high-probability regret and inference guarantees for the earlier FEL forced-exploration algorithm, as shown in Appendix B."],"supporting_citations":[{"why":"Supplies the confidence-ellipsoid lemma (Lemma 11) that converts λ_min growth into a bound on parameter-estimation error.","marker":"Abbasi-yadkori et al. (2011)"},{"why":"Provides the matrix Freedman inequality adapted as Lemma 9, the concentration tool for the design-matrix martingale.","marker":"Tropp (2011)"},{"why":"The prior forced-exploration algorithm FEL that TRAiL builds on, and whose high-probability guarantees the proof technique extends to in Appendix B.","marker":"Abbasi-Yadkori et al. (2009)"},{"why":"Prior work on exploration and inference in linear bandits with rich action sets; source of the L^p-ball experiments reinterpreted in Section 9.","marker":"Banerjee et al. (2023)"},{"why":"Source of the van Trees/Bayesian Cramér-Rao bound used in the lower-bound proof of Theorem 15.","marker":"Ziemann and Sandberg (2021)"},{"why":"Dynamic-pricing analysis that inspired the lower-bound technique connecting estimation and control.","marker":"Keskin and Zeevi (2014)"}],"fun_headline_variants":["Forced tangent exploration achieves √T inference and √T regret","TRAiL: matching rates for inference and regret in bandits","Tangent randomization provably balances inference and regret","Linear bandits: optimal regret demands matched inference rate","Trade-off proved: regret and inference must grow at same rate"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The geometric lemmas that give the projection and regret bounds are proved for actions in A* and parameters in Θ, but the paper never shows that the RLS estimates θ̂_t (and hence the actions a*(θ̂_t)) stay in Θ before the high-probability event in Theorem 6 starts.","fun_headline_variants_meta":{"raw":{"variants":["Forced tangent exploration achieves √T inference and √T regret","TRAiL: matching rates for inference and regret in bandits","Tangent randomization provably balances inference and regret","Linear bandits: optimal regret demands matched inference rate","Trade-off proved: regret and inference must grow at same rate"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000596,"raw_usage":{"total_tokens":2859,"prompt_tokens":1084,"completion_tokens":1775,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":700,"completion_tokens_details":{"reasoning_tokens":1693}},"tokens_in":700,"tokens_out":1775,"duration_ms":10425,"temperature":1.0,"reasoning_tokens":1693,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T17:52:49.967986+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate TRAiL on a strongly convex sublevel set where θ̂_t is forced (by initialization or adversarial noise) to lie outside the parameter set Θ for the first F(δ) rounds; if λ_min(V_T) fails to grow as √T with high probability, the geometric lemmas' requirement that estimates remain in Θ is load-bearing. Alternatively, run a regret-optimal algorithm on an L^p ball with p > 2 and measure regret × λ_min(V_T) empirically: if the product stays below cT permanently in the long run, the asymptotic trade-off (Regret)(Inference) ≳ T is false.","supporting_citations":[{"cited_title":"Improved algorithms for linear stochastic bandits","cited_arxiv_id":null,"evidence_quote":"Supplies the confidence-ellipsoid lemma (Lemma 11) that converts λ_min growth into a bound on parameter-estimation error."},{"cited_title":"Forced-exploration based algorithms for playing in stochastic linear bandits","cited_arxiv_id":null,"evidence_quote":"The prior forced-exploration algorithm FEL that TRAiL builds on, and whose high-probability guarantees the proof technique extends to in Appendix B."},{"cited_title":"On uninformative optimal policies in adaptive lqr with unknown b-matrix","cited_arxiv_id":null,"evidence_quote":"Source of the van Trees/Bayesian Cramér-Rao bound used in the lower-bound proof of Theorem 15."}],"review_version":1}