{"id":"26fe1e1e-3aeb-40be-a900-f96cdb75dc60","arxiv_id":"2501.13390","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"BOSS achieves tilde-O(N m sqrt(tau) + N^(2/3) tau^(2/3) d m^(1/3) + N d^2 + tau m d) meta-regret for sequential linear bandits with shared low-rank representations and no task diversity assumption.","lead":"A new algorithm, BOSS, learns a shared low-dimensional structure across a sequence of bandit tasks even when the tasks are not diverse, and provably beats the default per-task baseline when there are enough tasks. It is the first provable guarantee of this kind for sequential multi-task linear bandits without a task-diversity assumption.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 6's realizability step is unsound: an epsilon=alpha cover expert can have surrogate cost Cmiss even when every estimate is within alpha, so the EWA baseline is Theta(N) and the claimed o(N d sqrt(tau)) bound does not follow from the proof.","rationale":"The central reduction and the importance-weighted EWA decomposition are coherent, and the parameter tuning is algebraically consistent; the reader's flagged Assumption 2 norm lower bound is not the weakest point. The load-bearing gap is Lemma 6's 'realizable sequence' claim: B_eps is only alpha-close to the true subspace, while the surrogate loss uses an alpha-threshold on theta_hat_n. Cover error and estimation error add, so on a constant fraction of exploration rounds B_eps is classified as a miss. This inflates the EWA baseline by Theta(N) and injects a Theta(N tau/p) term into the regret, which in the tuned regime is not o(N d sqrt(tau)) when N >> m sqrt(tau). The flaw is internal to the proof rather than a disagreement with existing consensus, and it is plausibly repairable by separating the surrogate threshold from the true-cost threshold with a constant gap. For that reason I would keep the reader's CONDITIONAL verdict but for a more substantive reason: the theorem as stated needs a corrected Lemma 6 before it can be relied upon.","tokens_in":21480,"tokens_out":43083,"duration_ms":1101392,"concrete_test":"Re-derive Lemma 6 on the 2D counterexample (d=2, m=1, B=span(e1), B_eps at angle alpha, theta_n=e1, theta_hat_n=e1 - alpha n_eps). On this event every condition in F holds but Ctilde_n(B_eps)=Cmiss, disproving the assertion that I(F) sum l_n(B_eps)=0. Then recompute the EWA regret against B_eps with per-round loss about (Cmiss - Chit)/Cmiss and verify the extra N tau/p term appears; if it does, Theorem 7 requires a threshold-gap repair (e.g., true-cost threshold 3 alpha with surrogate threshold 2 alpha) before the stated o(N d sqrt(tau)) bound is supported.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In Lemma 6 the proof asserts that on F (the event that every exploration estimate satisfies norm error at most alpha) the fixed expert B_eps from Lemma 12 satisfies sum_n l_n(B_eps)=0. This requires Ctilde_n(B_eps)=Chit, i.e. norm(B_eps_perp^T theta_hat_n) <= alpha. But Lemma 12 sets epsilon=alpha and only gives norm(B_eps_perp^T theta_n) <= alpha; the triangle inequality gives at most 2 alpha. The first bullet of Remark 2 would give the needed alpha-cover of theta_hat only if theta_n lay in span(B_eps), which a finite cover does not guarantee. Concrete failure: d=2, m=1, B=span(e1), B_eps spanned by (cos alpha, sin alpha), theta_n=e1, and theta_hat_n=e1 - alpha n_eps where n_eps is the unit vector along B_eps_perp. Then the estimation error is exactly alpha, so the accuracy event holds, but norm(B_eps_perp^T theta_hat_n)=2 alpha > alpha, so Ctilde_n(B_eps)=Cmiss. For Gaussian noise this misclassification happens with non-negligible probability, so sum_n l_n(B_eps) is Theta(N), not 0. Re-running the EWA bound yields sum E[C_n] <= N Chit + (Cmiss/p)(N + log|E|); with the paper's p=(m sqrt(tau)/N)^{2/3} the extra N tau/p = N^{5/3} tau^{1/3}/m^{2/3} is not o(N d sqrt(tau)) when N >> m sqrt(tau). Thus Theorem 7 is not established by the proof as written.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies sequential multi-task linear bandits where all task parameters lie in an unknown m-dimensional subspace of R^d, without assuming task diversity. The proposed algorithm, BOSS, alternates between meta-exploration rounds that estimate the current task parameter in the full d-dimensional space and meta-exploitation rounds that use an online-chosen subspace from an epsilon-cover of the Grassmannian. The choice of subspace is driven by an exponential-weights algorithm over a surrogate cost whose evaluation is importance-weighted by the exploration indicator. The main theoretical claim is Theorem 7: with suitable choices of the exploration probability and exploration lengths, the meta-regret is tilde-O(N m sqrt(tau) + N^{2/3} tau^{2/3} d m^{1/3} + N d^2 + tau m d), which is the first o(N d sqrt(tau)) guarantee in this setting. The experimental section compares BOSS against PEGE, an oracle PEGE, and a reimplementation of Qin et al. on synthetic data with adversarially revealed subspace dimensions.","tokens_in":21774,"tokens_out":14758,"duration_ms":139922,"significance":"If the main theorem is correct, the paper makes a genuine contribution: it removes the task-diversity assumption that all prior sequential representation-transfer guarantees relied on, and it introduces a clean reduction from sequential multi-task bandits to an online subspace-selection problem with partial feedback. The decomposition of regret into exploration and exploitation terms is natural, and the paper is accompanied by code and by experiments targeted at the diversity-free regime. The appendices contain detailed derivations and the main decomposition is coherent up to constants. However, the load-bearing realizability step in Lemma 6 is not justified as written; without it the claimed o(N d sqrt(tau)) bound does not follow from the proof. The issue appears repairable by adjusting the thresholds in the surrogate cost, so I view the result as promising but the current manuscript as requiring a major revision.","major_comments":[{"comment":"The realizability step in the proof of Lemma 6 is unsound. Lemma 12 guarantees only that the cover expert B_epsilon satisfies dist(theta_n, span(B_epsilon)) <= epsilon theta_max <= alpha for every task; it does not put theta_n in span(B_epsilon). For an exploration task with ||hat_theta_n - theta_n|| <= alpha, the best triangle-inequality conclusion is dist(hat_theta_n, span(B_epsilon)) <= 2 alpha. Since the surrogate cost tilde C_n in Eq. (3) uses threshold alpha, this is not enough to conclude tilde C_n(B_epsilon) = C_hit. Concretely, for d=2, m=1, B = span(e_1), B_epsilon spanned by (cos alpha, sin alpha), theta_n = e_1, and hat_theta_n = e_1 - alpha n_epsilon, the estimation-accuracy event holds but ||B_{epsilon,perp}^T hat_theta_n|| = 2 alpha, so tilde C_n(B_epsilon) = C_miss. Thus the assertion I(F) sum_n ell_n(B_epsilon) = 0 in the proof of Lemma 6 is false. Re-running the EWA bound with a fixed expert that has nonzero loss gives an extra Omega(N C_miss) = Omega(N tau) term after converting back to bar C_n, which is not o(N d sqrt(tau)) and invalidates the proof of Theorem 7 as written. The argument appears repairable by widening the thresholds, e.g. defining C_n with threshold 3 alpha and tilde C_n with threshold 2 alpha, which would restore the zero-loss baseline expert up to constants; this is why I treat the issue as a major gap rather than a fatal flaw in the underlying approach.","section":"Appendix F, Lemma 6 (with Lemma 12 and Remark 2)"}],"minor_comments":[{"comment":"Algorithm 3 and the full Algorithm 4 in Appendix B do not list tau_1, tau_2, alpha, or epsilon among their inputs, although the calls to Algorithm 1 and Algorithm 2 and the EWA update with the surrogate cost in Eq. (3) require these values; please include them in the input lists and pass them explicitly.","section":"Algorithm 3 and Algorithm 4"},{"comment":"In the display in Lemma 11, the definition of tilde C_n is written with the condition ||B_perp^T theta_n|| <= 2 alpha, which matches C_n rather than the surrogate in Eq. (3); it should be written with hat_theta_n and threshold alpha to be consistent with the surrounding case analysis.","section":"Appendix C, Lemma 11"},{"comment":"The simplification N tau d^2 / tau_1 + N p tau_1 = N d sqrt(tau p) + N d^2 silently assumes that tau_1 = d sqrt(tau / p) is not clipped to tau. When d sqrt(tau / p) > tau, one has tau_1 = tau and the expression becomes N d^2 + N p tau; please add a short case analysis showing that N p tau is absorbed by the stated bound in that regime, e.g. by N m sqrt(tau).","section":"Appendix G, proof of Theorem 7"},{"comment":"The shifted and scaled loss in Algorithm 4 is written with an inline conditional and a repeated expression; the case distinction for Z_n = 1 versus Z_n = 0 would be clearer if written as separate lines, as in the surrounding text.","section":"Algorithm 4, line 10"},{"comment":"The statement E_Z[bar C_n(B)] >= C_n(B) in the proof sketch uses the symbol '≳' without specifying the constant or the high-probability event; the precise statement is given later in Lemma 6, but a pointer there would avoid confusion.","section":"Section 4, proof sketch"},{"comment":"The theorem statement does not explicitly include the condition tau >> d^2, although Lemma 6 relies on it and the discussion in Section 4 mentions that the burn-in terms can exceed N tau otherwise; please state the required regime in Theorem 7.","section":"Theorem 7"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses an important open gap in sequential representation transfer for linear bandits, and the algorithmic reduction to EWA over a subspace cover is elegant. The main concern is the proof of Lemma 6: the claimed realizability of the loss sequence with a zero-loss cover expert is not established, and the proof as written does not yield the stated o(N d sqrt(tau)) bound. I believe the intended argument can be repaired by changing the threshold constants in the surrogate cost, so I recommend major revision rather than rejection. Please ask the authors to either fix the thresholds and verify the constants, or provide a different argument for the zero-loss expert. If the repair is successful, the paper would likely be acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper makes a genuinely new claim: the first o(N d sqrt(tau)) meta-regret for sequential multi-task linear bandits without task diversity, via a reduction to online subspace selection with importance-weighted EWA. The high-level machinery is thoughtful and the paper is honestly written. But I would not rely on Theorem 7 as proven: there is a real gap in Lemma 6.\n\nThe problem is the realizability step. Lemma 12 only guarantees a cover expert B_eps with dist(theta_n, span(B_eps)) <= epsilon <= alpha. On the good event, theta_hat_n is within alpha of theta_n, so dist(theta_hat_n, span(B_eps)) <= 2alpha. The surrogate cost Ctilde_n uses threshold alpha, so B_eps can be classified as Cmiss even when all estimates are accurate. The paper's Remark 2 first bullet is misapplied: it requires theta_n in span(B_eps), which the cover does not give. The d=2 counterexample in the stress-test note is correct: B_eps at angle alpha, theta_n = e1, theta_hat_n = e1 - alpha n_eps. Estimation error is exactly alpha, but ||B_eps_perp^T theta_hat_n|| = 2alpha, so the surrogate is miss. The EWA baseline then accumulates Theta(N) miss costs, and the bound gains an extra N*Cmiss/p term, which for large N is not o(N d sqrt(tau)). This is not a cosmetic issue; it breaks the proof of the main theorem as written.\n\nWhat the paper does well: the reduction to bandit online subspace selection is new and the proof decomposition in Section 4 is clear. The experiments are honest—adversarial task schedule, a no-oracle variant, comparison to the diversity-based baseline, and released code. The paper also flags its own restrictive assumptions: fixed ellipsoid action set and norm bounds away from zero. The pseudocode omissions (Algorithms 3 and 4 miss tau_1, tau_2, and alpha) and the existential constant c2 are minor by comparison and easy to fix.\n\nMy guess is the result may be salvageable—perhaps by setting epsilon = alpha/2 or by using a 2alpha threshold in the surrogate—but that needs to be shown. As it stands, this is a conditional accept at best: the core idea deserves referee time, but Lemma 6 must be repaired before the bound is trusted.","headline":"The paper's no-diversity sequential multi-task bandit bound is a genuinely new claim with a clean overall design, but Lemma 6 has a load-bearing gap that the main theorem currently depends on.","tokens_in":22347,"tokens_out":2924,"would_cite":false,"duration_ms":41464,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","62L05","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"By randomizing meta-exploration instead of assuming task diversity, the BOSS algorithm achieves the first $o(N d \\sqrt{\\tau})$ meta-regret bound for sequential multi-task linear bandits, approaching the oracle rate $N m \\sqrt{\\tau}$ as…","keywords":["sequential multi-task linear bandits","representation transfer","task diversity assumption","meta-exploration","low-rank subspace","online subspace selection","exponential weights","meta-regret"],"falsifier":"Take the same low-rank task sequence but let one task parameter have norm far below $\\theta_{\\min}$, or replace the ellipsoid action set with a convex body for which the canonical-basis actions $\\lambda_0 e_i$ are infeasible, run BOSS with the paper's parameter choices, and check whether cumulative regret still follows the claimed curve. The sharpest target is Lemma 3's conversion $\\max_{a \\in A} \\langle a - A_{n,t}, \\theta_n \\rangle \\le J \\lVert \\theta_n - \\hat{\\theta}_n \\rVert / \\lVert \\theta_n \\rVert$: as $\\lVert \\theta_n \\rVert$ approaches zero the advertised $\\tilde{O}(N m \\sqrt{\\tau})$ regime must break, so a single task with near-zero norm is the cleanest counterexample.","tokens_in":21216,"feed_emoji":"🎰","tokens_out":16790,"duration_ms":135292,"temperature":0.7,"pith_summary":"Sequential multi-task linear bandits — a learner faces $N$ tasks, each for $\\tau$ rounds, with all reward parameters hidden in a shared $m$-dimensional subspace of $\\mathbb{R}^d$ — previously had no provable improvement over the naive $\\tilde{O}(N d \\sqrt{\\tau})$ baseline unless the tasks were assumed to be diverse, meaning any large batch of task parameters spans the subspace. This paper removes that assumption. It presents BOSS, an algorithm that randomly meta-explores in each task with probability $p$ and otherwise exploits a candidate subspace chosen online, and proves a meta-regret of $\\tilde{O}(N m \\sqrt{\\tau} + N^{2/3} \\tau^{2/3} d m^{1/3} + N d^2 + \\tau m d)$ under the assumption that the action set is a fixed well-conditioned ellipsoid and all task-parameter norms lie between positive constants. This is the first $o(N d \\sqrt{\\tau})$ guarantee for the sequential setting without task diversity, and it approaches the oracle rate $N m \\sqrt{\\tau}$ once the number of tasks grows large.","feed_headline":"First sublinear regret for bandits without task diversity","feed_subtitle":"BOSS learns a shared low-rank representation on the fly, beating the no-transfer baseline when tasks are many.","key_machinery":"The argument rides on an importance-weighted surrogate cost for the subspace-selection game. For a candidate subspace $B$, define $C_n(B) = C_{\\mathrm{hit}}$ when $B$ approximately covers $\\theta_n$ and $C_{\\mathrm{miss}} := \\tau$ otherwise; by Lemma 4, $C_n(\\hat{B}_n)$ is, up to constants, an upper bound on the regret of running Algorithm 2 with $\\hat{B}_n$. Because $\\theta_n$ is never observed, BOSS instead minimizes $\\tilde{C}_n(B)$, the same threshold function applied to the $\\alpha$-accurate estimate $\\hat{\\theta}_n$ obtained in meta-exploration rounds, and multiplies it by $Z_n/p$ with $Z_n \\sim \\mathrm{Bernoulli}(p)$ so that $\\mathbb{E}[\\tilde{C}_n(B) Z_n/p] \\ge C_n(B)$: the surrogate is an upper bound in expectation, which is all the exponential-weights analysis needs. The experts are an $\\varepsilon$-cover of the Grassmannian (the set of all $m$-dimensional subspaces) in the principal-angle metric, of size $(\\sqrt{dm}/\\varepsilon)^{O(dm)}$, and the EWA guarantee (Lemma 6) turns the exploration probability $p$ and the cover size into a cost accumulation of $\\tilde{O}(N C_{\\mathrm{hit}} + \\tau d m / p)$. Two exploration lengths, $\\tau_1$ (full-dimensional, in units of $d$) and $\\tau_2$ (subspace, in units of $m$), balance estimation error against per-task regret, and the regret-to-error conversion in Lemmas 3 and 4 divides by $\\lVert \\theta_n \\rVert$, which is why the lower norm bound matters.","core_discovery":"The discovery is that meta-exploration can be scheduled randomly and priced online rather than forced to happen up front. BOSS runs a two-level procedure: with probability $p$ a task is spent on full-dimensional exploration (Algorithm 1), producing an unbiased estimate $\\hat{\\theta}_n$ of $\\theta_n$ with per-task regret $\\tilde{O}(\\tau_1 + \\tau d^2/\\tau_1)$; otherwise the task is played inside a candidate subspace $\\hat{B}_n$ drawn from an $\\varepsilon$-cover of the set of $m$-dimensional subspaces (Algorithm 2), whose per-task regret is $\\tilde{O}(\\tau_2 + \\tau (m^2/\\tau_2 + \\lVert \\hat{B}_{n,\\perp}^{\\top} \\theta_n \\rVert^2))$. The subspace-selection problem is cast as prediction with expert advice, the experts being the $\\varepsilon$-cover of size $(\\sqrt{dm}/\\varepsilon)^{O(dm)}$, with surrogate costs $\\tilde{C}_n(B)$ built from $\\alpha$-accurate estimates and importance-weighted by $1/p$ so that they upper-bound the true costs in expectation. Theorem 7 states the resulting meta-regret is $\\tilde{O}(N m \\sqrt{\\tau} + N^{2/3} \\tau^{2/3} d m^{1/3} + N d^2 + \\tau m d)$ with exploration probability $p = \\min((2 m \\sqrt{\\tau}/N)^{2/3}, 1)$; the term $N^{2/3} \\tau^{2/3} d m^{1/3}$ is the sublinear-in-$N$ overhead for learning the representation, and $N d^2$ plus $\\tau m d$ are burn-in costs.","pith_inferences":["The importance-weighted subspace-selection scheme is a natural template for extending the result to general or time-varying action sets, which the paper leaves open; the concrete obstruction is that the exploration schedule needs a set of actions whose Gram matrix is well-conditioned in all $d$ directions.","A matching lower bound without task diversity would test whether the $N^{2/3} \\tau^{2/3} d m^{1/3}$ middle term is intrinsic to online meta-exploration or an artifact of the expert-cover reduction; the paper only speculates about the gap.","The certified algorithm is not computationally practical as stated, since the expert set has size $(\\sqrt{dm}/\\varepsilon)^{O(dm)}$; the experiments use $10^5$ random subspaces as a proxy, so a scalable version would need a compact expert representation or a direct online method on the Grassmannian.","The lower bound $\\theta_{\\min}$ quietly plays the role of a signal-to-noise guarantee, ensuring the meta-exploration estimate $\\hat{\\theta}_n$ carries directional information about $\\theta_n$; replacing it with a per-task adaptive exploration budget looks like the clearest route to a fully assumption-free statement."],"forward_implications":["For $\\tau \\gg d^2$ and $N \\gg m \\sqrt{\\tau}$, the BOSS bound $\\tilde{O}(N m \\sqrt{\\tau} + N^{2/3} \\tau^{2/3} d m^{1/3} + N d^2 + \\tau m d)$ beats the individual single-task baseline $\\tilde{O}(N d \\sqrt{\\tau})$, so representation transfer provably pays with no diversity assumption.","The representation-learning overhead $N^{2/3} \\tau^{2/3} d m^{1/3}$ grows sublinearly in $N$ and is dominated by the oracle term once $N \\gg d^3 \\sqrt{\\tau}/m^2$, meaning the shared subspace is learned at vanishing marginal cost in the large-task limit.","Knowledge of the number of tasks $N$ can be removed with a doubling trick at constant-factor cost, and the subspace dimension $m$ only needs to be known up to an upper bound.","The remaining gap to the lower bound $\\Omega(N m \\sqrt{\\tau} + d \\sqrt{m \\tau N})$ is larger than for diversity-assuming algorithms, which the paper reads as the price of online meta-exploration under adversarial task arrivals.","In synthetic experiments where new subspace dimensions appear at adversarial task indices, BOSS and its variants outperform the diversity-assuming baseline SeqRepL even when the expert set is just a random sample of the theoretical cover."],"supporting_citations":[{"why":"Supplies the PEGE base algorithm whose greedy-after-exploration regret guarantee is restated as Lemma 3 for meta-exploration tasks.","marker":"[Rusmevichientong and Tsitsiklis, 2010]"},{"why":"Supplies the subspace-informed estimation argument (their Lemma 17) that underlies Lemma 4's regret bound for meta-exploitation with a candidate subspace.","marker":"[Yang et al., 2020]"},{"why":"The prior sequential algorithm whose task-diversity assumption BOSS removes, and the source of the lower bound $\\Omega(N m \\sqrt{\\tau} + d \\sqrt{m \\tau N})$ used for comparison.","marker":"[Qin et al., 2022]"},{"why":"The EWA/Hedge algorithm whose regret bound is the engine of Lemma 6's guarantee for the online subspace-selection game.","marker":"[Freund and Schapire, 1997]"},{"why":"The nearest related sequential analysis without task diversity, whose guarantee degrades to $O(N d \\sqrt{\\tau})$ and therefore marks the baseline this work must beat.","marker":"[Bilaj et al., 2024]"}],"fun_headline_variants":["Bandits learn shared structure without task diversity assumption","BOSS: online representation transfer for sequential linear bandits","Sublinear regret for multi-task bandits without diversity","Learning low-rank representations on the fly in linear bandits","Meta-exploration beats no-transfer baseline in linear bandits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantee collapses without Assumption 2: the action set must be a fixed well-conditioned ellipsoid $A = \\{x : x^{\\top} M^{-1} x \\le 1\\}$, and every task parameter must satisfy $\\theta_{\\min} \\le \\lVert \\theta_n \\rVert \\le \\theta_{\\max} \\le 1$, because Algorithm 1's exploration plays $\\lambda_0 e_i$ (which must lie in $A$) and the regret-to-estimation-error conversion divides by $\\lVert \\theta_n \\rVert$.","fun_headline_variants_meta":{"raw":{"variants":["Bandits learn shared structure without task diversity assumption","BOSS: online representation transfer for sequential linear bandits","Sublinear regret for multi-task bandits without diversity","Learning low-rank representations on the fly in linear bandits","Meta-exploration beats no-transfer baseline in linear bandits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000342,"raw_usage":{"total_tokens":1997,"prompt_tokens":1172,"completion_tokens":825,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":788,"completion_tokens_details":{"reasoning_tokens":748}},"tokens_in":788,"tokens_out":825,"duration_ms":7833,"temperature":1.0,"reasoning_tokens":748,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T16:00:40.876769+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the same low-rank task sequence but let one task parameter have norm far below $\\theta_{\\min}$, or replace the ellipsoid action set with a convex body for which the canonical-basis actions $\\lambda_0 e_i$ are infeasible, run BOSS with the paper's parameter choices, and check whether cumulative regret still follows the claimed curve. The sharpest target is Lemma 3's conversion $\\max_{a \\in A} \\langle a - A_{n,t}, \\theta_n \\rangle \\le J \\lVert \\theta_n - \\hat{\\theta}_n \\rVert / \\lVert \\theta_n \\rVert$: as $\\lVert \\theta_n \\rVert$ approaches zero the advertised $\\tilde{O}(N m \\sqrt{\\tau})$ regime must break, so a single task with near-zero norm is the cleanest counterexample.","supporting_citations":[{"cited_title":"Linearly parameterized bandits","cited_arxiv_id":null,"evidence_quote":"Supplies the PEGE base algorithm whose greedy-after-exploration regret guarantee is restated as Lemma 3 for meta-exploration tasks."},{"cited_title":"Non-stationary representation learning in sequential linear bandits","cited_arxiv_id":null,"evidence_quote":"The prior sequential algorithm whose task-diversity assumption BOSS removes, and the source of the lower bound $\\Omega(N m \\sqrt{\\tau} + d \\sqrt{m \\tau N})$ used for comparison."},{"cited_title":"Meta learning in bandits within shared affine subspaces, 2024","cited_arxiv_id":null,"evidence_quote":"The nearest related sequential analysis without task diversity, whose guarantee degrades to $O(N d \\sqrt{\\tau})$ and therefore marks the baseline this work must beat."}],"review_version":1}