{"id":"6421bcdd-9ea5-47d7-834a-4e36f1460982","arxiv_id":"2506.14479","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"A hypothetical-context estimator is claimed to make Thompson Sampling minimax optimal for linear contextual bandits under arbitrary contexts, though the proof has a critical gap.","lead":"This paper presents a Thompson Sampling algorithm for linear contextual bandits that claims a near-optimal regret bound without distributional assumptions on the contexts. The method augments the data with hypothetical orthogonal contexts and couples them to the real problem by resampling, a technique that could close a long-standing gap in bandit theory.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2's coupling equality incorrectly replaces the final, successfully resampled action with the first-draw action under the success event; the HCSA estimator is therefore not shown to be controlled by the HSA bound. This invalidates Theorem 5 and the claimed O(d sqrt(T) log T) regret bound.","rationale":"The reader's weakest_assumption matches my own: Lemma 2's second equality is not a distributional identity. I checked all downstream uses: Theorem 5's proof begins 'by the definition of the proposed estimator and the coupling inequality (Lemma 2)'; Lemma 4 bounds only the HSA estimator; Theorem 3's regret decomposition uses Theorem 5 through Lemma 6 and Lemma 7. No other route connects the computable HCSA estimator to a full-Gram self-normalized bound. The Bernoulli example shows the inequality fails already for a single round, so this is an internal inconsistency, not a disagreement with prior assumptions. The paper is creative and the construction is interesting, but the advertised 'first nearly minimax-optimal LinTS without distributional assumptions' is unsupported as written. I therefore recommend REJECT; a corrected coupling argument could change this assessment.","tokens_in":23406,"tokens_out":12411,"duration_ms":119761,"concrete_test":"Re-derive Lemma 2 on the one-round model: set t=1, gamma=1/2, M_1=3 (achievable with delta=3/4), and let tilde a_1(1), tilde a_1(2), tilde a_1(3) be iid with P(tilde a = N_1)=1/2, S_1={tilde a_1(m)=N_1 for some m<=3}. For any x with p=P(F(N_1)>x)>0, compute both sides of the equality in Lemma 2: the left equals P(S_1)*p = (7/8)p, the right equals P(tilde a_1(1)=N_1)*p = (1/2)p. The mismatch (3/8)p settles that the coupling inequality as written is false. If the intended bound can be proved by conditioning on the full stopping-time path, that corrected argument should be supplied and checked.","verdict_should_be":"REJECT","load_bearing_attack":"Lemma 2 is the only bridge from the computable HCSA estimator (Eq. 15) to the idealized HSA estimator (Eqs. 11-12). Its proof asserts, for S_t = intersection_{s<=t} M_s, that P({F(tilde a_1(M_1), ..., tilde a_t(M_t)) > x} intersect S_t) = P({F(tilde a_1(1), ..., tilde a_t(1)) > x} intersect S_t intersect intersection_s {tilde a_s(1) = N_s}), justified by 'the tilde a_s(m) are IID for each s'. This ignores the selection bias of the stopping time xi_s: on M_s the final draw satisfies tilde a_s(M_s) = N_s, but M_s also contains paths in which tilde a_s(1) != N_s and success occurs only at a later resampling trial. Conditioning on eventual success changes the law of tilde a_s(1); it is not exchangeable with tilde a_s(M_s). Concretely, with t=1, M_1=3, gamma=1/2, P(M_1)=7/8 while P(tilde a_1(1)=N_1)=1/2; whenever F(N_1)>x has positive probability, the claimed equality would force 7/8 = 1/2. Moreover the HCSA estimator uses the hypothetical contexts of the final a_s(M_s), while the HSA estimator uses the first draw, so replacing one by the other changes the Gram matrix and pseudo-rewards, not merely the argument of F. Since Theorem 5 is proved from Lemma 2 and Theorem 3 relies on Theorem 5, the central regret bound is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes HCSA+TS, a Thompson Sampling algorithm for linear contextual bandits that uses a new estimator based on hypothetical contexts, adaptive data augmentation, and a resampling/coupling mechanism. The main theoretical claim is a nearly minimax-optimal regret bound of O(d sqrt(T) log T) under arbitrary (non-IID, non-stationary) context distributions, removing IID and minimum-eigenvalue assumptions used in prior work. The paper also contains experiments comparing the proposed method with several baselines on simulated data. The central result depends on a coupling inequality (Lemma 2) that relates the computable HCSA estimator to an idealized hypothetical-sample-augmented estimator.","tokens_in":23728,"tokens_out":4409,"duration_ms":44662,"significance":"If established, the claimed regret bound would be a significant advance: it would provide the first minimax-optimal (up to log factors) frequentist regret guarantee for Thompson Sampling in linear contextual bandits without distributional assumptions on contexts. The construction of orthogonal hypothetical contexts, the attempt to control a full Gram matrix including unselected arms, and the coupling mechanism are creative and could be of independent interest. However, the main theorem is not supported because Lemma 2, which is the sole bridge between the computable estimator and the idealized estimator, is proved via a false equality. The central claim is therefore currently unsubstantiated.","major_comments":[{"comment":"The proof of Lemma 2 contains a false equality. It asserts that P({F(tilde a_1(M_1), ..., tilde a_t(M_t)) > x} cap S_t) equals P({F(tilde a_1(1), ..., tilde a_t(1)) > x} cap S_t cap cap_s {tilde a_s(1) = N_s}), justified by the IID property of resampling trials. This is incorrect because S_t = cap_s M_s includes paths where success occurs only at a later resampling trial, so the event M_s does not imply tilde a_s(1) = N_s; conditioning on eventual success changes the distribution of the first draw. Moreover, F is not invariant under replacing tilde a_s(M_s) with tilde a_s(1): the coupled pseudo-rewards in (14) and the resulting estimator depend on the final successful draw. A concrete counterexample with t=1, gamma=1/2, M_1=3 gives P(M_1)=7/8 while P(tilde a_1(1)=N_1)=1/2, so the claimed equality would force 7/8=1/2 whenever the event F(N_1)>x has positive probability. Because Theorem 5 is proved from Lemma 2 and Theorem 3 relies on Theorem 5, the central regret bound is not derived.","section":"Section 4.4, Lemma 2"},{"comment":"The proof of Theorem 5 depends on Lemma 2 to replace the HCSA estimator with the HSA estimator on the success event S_t. Since Lemma 2 is invalid, the self-normalized bound for the HCSA estimator is not established. Additionally, the proof in Appendix A.2 applies the triangle inequality to the decomposition from Lemma 4 but then substitutes definitions of the reference estimator and the matrix P_t in a way that appears to require V_t - A_t to be positive semidefinite on the relevant event; this is not shown and is another gap that would need to be addressed even if the coupling equality were repaired.","section":"Section 5.1 and Appendix A.2, proof of Theorem 5"},{"comment":"The proof of Lemma 9 states 'Using Lemma 9 and Lemma 10 from Abbasi-Yadkori et al. (2011)', but Lemma 9 is the lemma being proved in this paper; the intended reference is presumably Theorem 1 of Abbasi-Yadkori et al. (2011), which is not stated. This leaves the claimed noise bound of (sigma/gamma) sqrt(d log(1+t/delta)) for the term St without a clear supporting citation or proof. This issue is secondary to the failure of Lemma 2 but still needs correction.","section":"Appendix A.3, Lemma 9"},{"comment":"The derivation of the leading regret term contains unresolved notation and inequalities. In particular, the text moves from a bound involving '2h_T' to '2T_1', uses the expression 't=∈[T]', and the transition from regret(t) <= 2 x_t ||btheta_{t-1}-theta*||_{V_{t-1}} + sqrt(...) to the factored form involving sqrt(2) x_t is not fully justified, though it may be repairable. This is not the main obstruction but indicates that the regret analysis needs careful rewriting.","section":"Section 5.3, regret decomposition"}],"minor_comments":[{"comment":"The definition of N_s in (7) and the description of the orthogonal-basis augmentation in Section 4.2 are inconsistent with Algorithm 2: line 11 and line 14 of Algorithm 2 appear to swap the 't in A_t' and 'otherwise' cases relative to the text above equation (8).","section":"Section 4.2, equation (8)"},{"comment":"The statement of Lemma 4 contains stray text 'and. and.' before the displayed equation, and the proof uses 'rs+1' in sums where the full range should be 'N_s' as defined in (7).","section":"Appendix A.1, Lemma 4"},{"comment":"The proof introduces a sequence 'nu_s' without definition, and the sentence 'for ts such that t<=h_t, we have t in A_t and 1 in A_t for all t in [T]' is confusing; the intended argument that the regularization rounds are nonempty and well-ordered should be stated more clearly.","section":"Appendix A.5, Lemma 7"},{"comment":"The phrase 'arbitral context distributions' should be 'arbitrary context distributions'.","section":"Section 5.1, Theorem 5"},{"comment":"The hyperparameter tuning procedure is described only briefly; reporting the selected hyperparameter values for each method and the variance across runs would improve reproducibility.","section":"Section 6, experimental setup"}],"recommendation":"reject","confidential_remarks":"The paper's central contribution is a regret bound that would be a significant result in the linear contextual bandit literature. However, the key coupling lemma (Lemma 2) is false, and the consequences propagate to Theorem 5 and Theorem 3. The error is not a minor fix: the equality in the proof conflates the first resampling draw with the successful draw under the event of eventual success, and the estimator itself changes when the final draw is used. The authors would need to either find a different proof technique for the coupling inequality or substantially revise the algorithmic construction. Given the central claim is unsupported, rejection is appropriate, though the underlying idea may be salvageable in future work."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read Kim's arXiv paper. The headline: the core construction is genuinely clever, but the main proof has a false equality in Lemma 2 that invalidates the central regret bound as written.\n\nWhat is new and good: the paper compresses K contexts into at most d+1 hypothetical contexts (orthogonal eigenvectors plus the selected arm's context) while preserving the full Gram matrix, then couples the hypothetical bandit to the original by resampling until the sampled hypothetical arm matches the original arm. That is a clean idea, and the HCSA estimator is a natural way to get a self-normalized bound with a full Gram matrix. The paper also frames the target correctly: O~(d sqrt T) for arbitrary context sequences would close a known gap for TS. Section 4.2 and the coupling mechanism are worth reading.\n\nThe soft spot is load-bearing. In Lemma 2, the proof replaces the final resampled actions {tilde a_s(M_s)} with the first draws {tilde a_s(1)} while keeping the success event S_t. That is not valid. On M_s, the final draw satisfies tilde a_s(M_s)=N_s, but M_s includes trajectories where tilde a_s(1) != N_s and success occurs only at a later trial. Conditioning on eventual success changes the law of the first draw; the IID property across m does not give exchangeability between the first draw and the stopped draw. The stress-test's t=1 example makes it concrete: for M_1=3 and gamma=1/2, P(M_1)=7/8 but P(tilde a_1(1)=N_1)=1/2, so the asserted equality would force 7/8=1/2 whenever F(N_1)>x has positive probability. Since Theorem 5 and Theorem 3 rely directly on Lemma 2, the central bound is not established. There are also smaller issues: the proof of Lemma 7 uses an undefined nu_s, Lemma 8's F_t notation is confusing, and Algorithm 2 has a stale index in the V_t update. Those are minor by comparison.\n\nWhere does that leave us? The paper is not a waste of time. The hypothetical-context construction may be repairable, and if a correct coupling inequality exists, the result would be important. But as submitted, the main theorem is not proven. I would not cite it yet. I would send it to peer review, with the expectation of major revision or rejection, because the idea deserves a serious look. Worth a reading group discussion on the coupling step.","headline":"Clever hypothetical-context construction and coupling idea, but Lemma 2 has a false equality that breaks the main self-normalized bound; the claimed O~(d sqrt T) regret for Thompson Sampling is not established as written.","tokens_in":24343,"tokens_out":3399,"would_cite":false,"duration_ms":32636,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims Thompson Sampling can be made nearly minimax optimal in linear contextual bandits.","keywords":["Thompson Sampling","linear contextual bandits","minimax optimal regret","data augmentation","coupling","hypothetical bandit","self-normalized bound","adaptive regularization"],"falsifier":"For a single round with $N_s=2$ and $\\gamma=1/2$, enumerate the resampling tree: if the first draw misses but the second hits, the HCSA estimator uses the second draw while the hypothetical estimator in Lemma 2 uses the first, so computing the two probabilities in Lemma 2 at any $x>0$ will show they differ.","tokens_in":23099,"feed_emoji":"🎲","tokens_out":7179,"duration_ms":72781,"temperature":0.7,"pith_summary":"The paper sets out to close a long-standing gap: Thompson Sampling, despite its strong empirical record in linear contextual bandits, has a regret bound of order $d^{3/2}\\sqrt{T}$, while the best possible is $\\Omega(d\\sqrt{T})$. It proposes a Thompson Sampling variant, HCSA+TS, whose estimator is built from hypothetical contexts---a small orthogonal set that preserves the Gram matrix of all $K$ arms---augmented on selected rounds by a full orthonormal basis. A resampling-coupling step makes the hypothetical rewards observable, and the resulting self-normalized bound uses a Gram matrix that includes every arm's context, not just the played one. If the proof is correct, this yields $O(d\\sqrt{T}\\log T)$ regret under arbitrary context distributions, removing the IID or positive-covariance assumptions that earlier results needed.","feed_headline":"Thompson sampling nears the optimal regret rate in linear bandits","feed_subtitle":"Adaptive hypothetical-context augmentation gives O(d√T) regret without assumptions on contexts.","key_machinery":"The load-bearing construction is the hypothetical bandit: at each round, the unplayed contexts' Gram matrix $G_t$ is eigen-decomposed, and the hypothetical contexts $Z_{i,t}$ are $\\sqrt{\\lambda_{i,t}}u_{i,t}$ plus the played context $X_{a_t,t}$, so the identity $\\sum_{i=1}^{r_t+1} Z_{i,t}Z_{i,t}^\\top = \\sum_{k=1}^K X_{k,t}X_{k,t}^\\top$ holds with far fewer arms. On selected rounds, an orthonormal basis is added, giving a Gram matrix bounded below by $\\sum_{s\\notin A_t}\\sum_{k=1}^K X_{k,s}X_{k,s}^\\top + \\max\\{x_{\\max}^2,1\\}h_t I_d$. The coupling step resamples the Thompson draw until the hypothetical arm equals the played arm, so the pseudo-rewards become computable; Lemma 1, the coupling inequality, and the maximal elliptical potential lemma are the three supports of the regret analysis.","core_discovery":"The paper's central claim is Theorem 3: with probability at least $1-3\\delta$, the cumulative regret of HCSA+TS is bounded by a sum whose leading order is $O(d\\sqrt{T}\\log T)$, matching the $\\Omega(d\\sqrt{T})$ minimax lower bound up to logarithmic factors. The mechanism is a new estimator, the hypothetical coupled sample augmented (HCSA) estimator, whose normalization matrix $V_t$ includes contexts from all $K$ arms plus an adaptively scheduled orthonormal augmentation. The coupling argument lets the algorithm use only $N_t \\le d+1$ pseudo-samples per round instead of $K$, and the paper argues that this removes the IID and strictly-positive-covariance context assumptions used by prior estimators, giving the first nearly minimax-optimal regret guarantee for Thompson Sampling in fully general linear contextual bandits.","pith_inferences":["The coupling step is the fragile point: the paper does not verify numerically that the stopping-time distribution equals the first-trial distribution, so a small simulation comparing the two probabilities in Lemma 2 would settle the proof.","Because the hypothetical-context construction is distribution-free, a natural extension would be to generalized linear bandits, replacing the Gram matrix identity with a Fisher-information version.","One could test the algorithm's practical claim on a fully deterministic context sequence (for example, cyclic basis vectors) where earlier Thompson Sampling variants are known to suffer; the paper's experiments only use random contexts with masking."],"forward_implications":["Linear contextual bandits would get a single Thompson Sampling algorithm whose $O(d\\sqrt{T}\\log T)$ regret holds even when contexts are deterministic, adversarial, or non-stationary.","The regret bound would no longer grow with the number of arms $K$ or with the context norm $x_{\\max}$, because the Gram matrix contains information about all arms.","The estimator would deliver accurate reward predictions for all arms, not only the played one, which is exactly what is needed for offline evaluation and for settings with missing context features.","The compression identity (3) could be reused by any algorithm that needs a well-conditioned Gram matrix, since it reduces $K$ context vectors to $r_t+1$ orthogonal ones without losing the sum of outer products."],"supporting_citations":[{"why":"Supplies the self-normalized martingale machinery and the elliptical potential lemma adapted in the proof.","marker":"Abbasi-Yadkori et al. (2011)"},{"why":"Provides the baseline $\\tilde O(d^{3/2}\\sqrt{T})$ Thompson Sampling regret bound that the paper aims to improve.","marker":"Agrawal and Goyal (2013)"},{"why":"Gives the best-known frequentist bound for LinTS that the paper compares against.","marker":"Abeille et al. (2017)"},{"why":"Introduces the doubly robust estimation idea with all-arm augmentation that the hypothetical construction compresses.","marker":"Kim et al. (2021)"},{"why":"Provides the most recent all-arm Gram matrix self-normalized bound whose IID assumption is dropped here.","marker":"Kim et al. (2023c)"},{"why":"States the $\\Omega(d\\sqrt{T})$ minimax lower bound that the claimed rate matches.","marker":"Lattimore and Szepesvári (2020)"},{"why":"Achieves $O(d\\sqrt{T})$ only under a Gaussian prior; the comparison target for removing prior assumptions.","marker":"Huix et al. (2023)"},{"why":"Provides the matrix concentration inequality used in Lemma 10 to control the spectral norm of the augmented estimator terms.","marker":"Tropp (2012)"}],"fun_headline_variants":["Adaptive augmentation pushes Thompson sampling to near-optimal regret","Thompson sampling hits near-optimal regret in linear bandits","New estimator closes regret gap for Thompson sampling","No context assumptions: Thompson sampling gets near-optimal regret"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The regret bound rests on the claim that once every resampling trial succeeds, the estimator's error distribution is the same as if the first hypothetical sample had been used in every round; that equality is the load-bearing premise of the proof.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive augmentation pushes Thompson sampling to near-optimal regret","Thompson sampling hits near-optimal regret in linear bandits","New estimator closes regret gap for Thompson sampling","No context assumptions: Thompson sampling gets near-optimal regret"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000567,"raw_usage":{"total_tokens":2608,"prompt_tokens":788,"completion_tokens":1820,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":404,"completion_tokens_details":{"reasoning_tokens":1756}},"tokens_in":404,"tokens_out":1820,"duration_ms":15975,"temperature":1.0,"reasoning_tokens":1756,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:19:45.171622+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a single round with $N_s=2$ and $\\gamma=1/2$, enumerate the resampling tree: if the first draw misses but the second hits, the HCSA estimator uses the second draw while the hypothetical estimator in Lemma 2 uses the first, so computing the two probabilities in Lemma 2 at any $x>0$ will show they differ.","supporting_citations":[],"review_version":1}