{"id":"877c4866-f3c9-4d14-a007-853d853c9283","arxiv_id":"2411.10906","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":3.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"Two memory-saving variants of LSVI-UCB for linear MDPs are proposed; the fixed-reset variant has a sublinear space-regret trade-off proof, while the adaptive variant lacks a regret guarantee despite the abstract claiming sublinear regret.","lead":"The paper modifies a standard reinforcement learning algorithm for linear MDPs so it uses less memory and time by periodically wiping its workspace. One variant gets a proven space-regret trade-off; the other adaptively skips learning steps but has no regret proof and only limited experimental support.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 3's only theoretical support conflates its subset-based Q-function with LSVI-UCB's full-history Q-function, so the claimed sublinear regret for the adaptive variant is unproved.","rationale":"The reader's weakest assumption correctly identified that the adaptive variant's Learn trigger is not justified under the linear MDP model and that no regret bound is proved. My stress-test sharpens this into an internal inconsistency: the proof of Proposition 7/Corollary 17 explicitly equates Algorithm 3's subset-based Q with LSVI-UCB's full-history Q at learning episodes, which is contradicted by Algorithm 3's own definition (lines 12-16 vs. Algorithm 1 lines 5-9). This is a correctness flaw, not merely a disagreement with a broader consensus. It is load-bearing because the abstract and contributions claim sublinear regret for both variants, and Proposition 8 only gives time/space bounds for Algorithm 3. I give credit for the fixed-reset variant (Algorithm 2), which is a plausible extension of LSVI-UCB, though its proof is a sketch; the experimental plots suggest reasonable behavior but are single runs without error bars or released code, and the baseline is stopped early on one benchmark. Those issues are secondary: the decisive gap is the missing regret guarantee for the adaptive variant. My proposed test directly checks the false equality and, if extended, measures the regret impact, so it would settle whether the concern lands. Since the reader already rejected the paper for essentially this area, my read does not change the verdict.","tokens_in":20565,"tokens_out":6381,"duration_ms":69555,"concrete_test":"Instrument Algorithm 3 and LSVI-UCB on the synthetic linear MDP of §5.3 with a fixed random seed. At every learning episode k' after at least one skipped episode, compare bQ_{h,k'} (computed by Algorithm 3 using only I_h) with Q_{h,k'} (LSVI-UCB's full-history regression) for each h and a set of state-action pairs. If any pair differs, the equality in Corollary 17 is falsified. To assess regret impact, run Algorithm 3 for K = 10^4 episodes under Assumptions 19-20 and compare its cumulative regret against LSVI-UCB's eO_d(√K); a linearly growing regret gap would confirm that the Learn trigger does not control regret.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim includes both variants maintaining sublinear regret, but Algorithm 3 has no regret theorem. Its only theoretical support is Proposition 7, proved in Appendix A.3.1. The proof's key step, in Corollary 17, states: 'By construction of Algorithm 3, we have bQ_{h,k} = bQ_{h,k'} = Q_{h,k'},' where Q is the action-value function of LSVI-UCB. This equality is false. Algorithm 3 (lines 12-16) computes Λ_h and w_h by summing only over i ∈ I_h, the set of previous learning episodes, whereas LSVI-UCB (Algorithm 1, lines 5-9) sums over all previous episodes i = 1,...,k-1. After even one non-learning episode, I_h is a proper subset, so the regressions differ and bQ_{h,k'} ≠ Q_{h,k'}. The subsequent closeness argument (Lemmas 15-16) compares LSVI-UCB's own Q at different times, not Algorithm 3's subset-based Q, so it cannot transfer stability to bQ. Furthermore, even if bQ were pointwise close to Q, no argument shows that greedily following a stale, non-optimistic bQ yields sublinear regret. Thus the adaptive variant's efficiency-to-regret tradeoff, a central contribution, is unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two memory-reduced variants of LSVI-UCB (Jin et al., 2023) for episodic linear MDPs. LSVI-UCB-Fixed (Algorithm 2) partitions episodes into phases of length K^rho and resets the regression workspace at each phase boundary; Proposition 6 claims time O_d(|A|K^{1+rho}), space O_d(|A|K^rho), and regret ~O_d(K^{1-rho/2}). LSVI-UCB-Adaptive (Algorithm 3) performs the ridge-regression update only when a trigger (Eq. (1)) detects sufficient change in the inverse covariance and when per-step budget and phase counters allow; Proposition 8 claims time O_d(|A|K*Budget) and space O_d(|A|Budget), and Section 5 claims experimentally that its regret is indistinguishable from LSVI-UCB. Proposition 7, proved in Appendix A, is the adaptive variant's only theoretical support: it asserts that operator-norm convergence of the inverse covariance sequence implies closeness of the learned Q-function to LSVI-UCB's Q-function. Experiments on a synthetic linear MDP and on two CTRL-linearized Atari environments (Alien, Phoenix) compare regret, space, and running time with LSVI-UCB.","tokens_in":20938,"tokens_out":24436,"duration_ms":229124,"significance":"Proportionate to its claims, the paper would be useful: replacing LSVI-UCB's O(|A|K) memory with O(|A|K^rho) at a K^{rho/2} regret penalty is a natural and practically motivated trade-off, and the CTRL linearization of Atari environments is a valuable experimental contribution. The manuscript is honest in important places: Assumptions 19-20 are stated explicitly in Appendix A, and Remark 9 concedes that linear MDP feature maps need not exist for arbitrary benchmarks. These strengths do not offset the central gap: the adaptive variant, which accounts for one of the paper's two main contributions, has no regret theorem, and the proof of its only theoretical justification (Proposition 7) is invalid at a specific step (Corollary 17), as detailed below. The abstract's statement that both variants maintain sublinear regret is therefore unsupported, and I do not see a local repair: validating the adaptive variant's regret claim requires either a new analysis or an honest demotion of that claim.","major_comments":[{"comment":"Corollary 17's assertion that \"By construction of Algorithm 3, we have bQ_{h,k} = bQ_{h,k'} = Q_{h,k'}\" is false. Algorithm 3 (lines 12-16) computes bQ_h by ridge regression over the set I_h of prior learning episodes only, whereas Algorithm 1 (lines 5-9) regresses over episodes 1,...,k'-1; as soon as one episode in the phase is non-learning, I_h is a proper subset and the regression weights differ. Moreover, if layers h+1,...,H did not learn in episode k, the target values max_a Q_{h+1}(s_{h+1,i},a) in line 14 come from an older stored Q-function, so a 'learning' episode of Algorithm 3 does not reproduce LSVI-UCB's update. Lemmas 15-16 bound the drift of LSVI-UCB's own Q sequence and cannot transfer to the subset-based bQ; the claimed equality conflates the two regression sets. Since Corollary 17 is the only bridge from the adaptive algorithm's value function to LSVI-UCB's, Proposition 7's first clause is unproved. The proof of Lemma 15 additionally relies on informal '=F' substitutions (replacing a k-term sum by k*Sigma and setting lambda = o(1)) that need norm bounds to be verifiable.","section":"Appendix A.3.1, Corollary 17"},{"comment":"Algorithm 3 has no regret theorem. Even if Proposition 7's pointwise-closeness conclusion were correct, it would not imply a sublinear regret bound for Algorithm 3: the executed policy is greedy with respect to a stale, non-optimistic Q-function, and the appendix supplies no optimism, bonus, or eluder-type argument converting closeness into regret. The manuscript effectively concedes this: Section 1.1 and Section 4.3 describe the adaptive variant's regret only as 'within reasonable bounds' and 'indistinguishable' empirically, and Proposition 8 is only a time/space statement. The abstract's claim that the two modifications maintain sublinear regret, and the conclusion's phrase 'provably space efficient variants... perform well in terms of accumulated regret,' overstate what is proved.","section":"Section 4.3, Proposition 7; Abstract"},{"comment":"Proposition 21, and hence the formal content of Proposition 7, holds only under Assumptions 19-20, which are not part of the linear MDP model of Definition 2 and are partially incompatible with it. Assumption 19 sets Ph(s,a) = pS for all (s,a), so transitions no longer depend on the state or action; Assumption 20 makes the features independent Gaussian draws, whereas in a linear MDP phi is a fixed feature map. Lemmas 14-16 and Theorem 13 likewise presuppose Gaussianity. The appendix should state plainly that the convergence result concerns a random-feature, action-independent model; as written, Proposition 7 is presented as supporting Algorithm 3 in the standard linear MDP setting, which it does not.","section":"Appendix A.3.2, Assumptions 19 and 20"},{"comment":"The fixed variant's analysis is a sketch at a load-bearing point. The claim that each phase incurs ~O_d(sqrt(K^rho)) regret 'by the correctness of LSVI-UCB for K^rho episodes' requires (i) a formal identification of each phase with an LSVI-UCB run of length K^rho against adaptively chosen initial states and (ii) a union bound over the K^{1-rho} phases; both are plausible but not given. In addition, Algorithm 2's pseudocode executes the reset (line 19, 'Delete the working space; I_h := empty') at episode k = K0 + K^rho before the action-selection loop (lines 21-24) of that same episode, so the policy executed at reset episodes is undefined; the regret accounting must specify which Q-function is used then.","section":"Section 4.2, Proposition 6 and Algorithm 2"},{"comment":"The empirical claim that the adaptive variant's regret is 'indistinguishable' from LSVI-UCB's is the only evidence for that variant's regret behavior, but it is presented without supporting statistics: Figures 1, 6, and 7 show single runs on log-scale axes, with no error bars, no multiple seeds, and no statistical test. There is also a factual inconsistency: Section 5.4 states 'We have stopped LSVI-UCB algorithm at K = 280,' yet Table 1 and Table 2 list Phoenix LSVI-UCB values at K = 500 (reward 50306.24, space 2.054 GiB). The experimental section needs to resolve this and report variance.","section":"Section 5.3-5.4"}],"minor_comments":[{"comment":"The hypothesis reads 'If Algorithm 2 converges at sqrt(K)' although the statement concerns Algorithm 3; the surrounding text also alternates between the two algorithms, which impedes verification.","section":"Corollary 17, Appendix A.3.1"},{"comment":"The phase counting in the proof sketch (K^{1-rho} intervals, each of length K^rho) is off by one episode because the reset occurs at k = K0 + K^rho rather than after action selection; the off-by-one is harmless asymptotically but should be made consistent with the pseudocode.","section":"Section 4.2, Proposition 6 sketch"},{"comment":"The symbol r_h denotes both a distribution over [0,1] and the scalar expected reward (Definition 2 versus the definition of Q^pi_h); the notation should be disambiguated.","section":"Section 3.1"},{"comment":"No guidance is given for setting m and tau consistently with any guarantee, and the reader should be told explicitly that in the absence of a regret theorem these triggers are heuristics; a one-sentence disclaimer would make the contribution's scope clear.","section":"Section 4.3, Algorithm 3 parameters"},{"comment":"The statement that the resampled distribution 'is the same as the distribution D' is only true marginally; the proof establishes that the m samples are i.i.d. from D with probability at least 1 - delta, which is what should be stated.","section":"Lemma 11, Appendix A.2"},{"comment":"The relevance of [HO23], a paper on multinomial logistic function approximation, to the claimed non-existence of inducing feature maps should be spelled out, or the remark should cite a directly relevant reference.","section":"Remark 9"},{"comment":"The reset deletes 'the working space' but the Learn trigger needs the stored window L^{-1}_{h,k-m},...,L^{-1}_{h,k} of full-history matrices; the pseudocode should specify precisely which data survive a reset.","section":"Algorithm 3, lines 21-24"},{"comment":"The regime of rho should be stated: sublinearity of regret requires rho < 2, whereas the advertised space saving requires rho < 1, and the proposition's usefulness depends on rho in (0,1).","section":"Proposition 6"}],"recommendation":"reject","confidential_remarks":"I agree with the reader's assessment. The Corollary 17 step is a genuine conflation of two different regressions rather than a typo: the appendix's bounds are for LSVI-UCB's full-history Q-function while Algorithm 3's Q-function is subset-based, and the two differ by construction as soon as a single episode is skipped. Because the adaptive variant is advertised as a main contribution that maintains sublinear regret, this is not a locally fixable gap; a viable revision would need either a new regret analysis or an honest reframing of that contribution as empirical. The fixed-variant analysis looks salvageable with a complete proof. I would not block a future submission that restricts the theoretical claims, but the present manuscript's central claims do not hold as stated."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is two separate contributions bundled together, and they should be treated differently. Algorithm 2, the fixed-reset variant, is a simple and plausible extension of LSVI-UCB: split the horizon into K^{1-rho} intervals of length K^rho, reset the workspace each time, and cite the original regret bound per interval. The claimed space O_d(|A|K^rho), time O_d(|A|K^{1+rho}), and regret O_d(K^{1-rho/2}) are all consistent with that logic. It is not deeply novel, and it should have compared against ZCVJ22's LSVI-UCB-Restart, but as a standalone contribution it is sound enough.\n\nAlgorithm 3, the adaptive variant, is where the paper overreaches. The trigger based on the Frobenius deviation of inverse covariance matrices is new, and I can see why it would make sense as a heuristic. But the theoretical support does not hold. The stress-test is right: Corollary 17 claims bQ_{h,k'} = Q_{h,k'} by construction, but Algorithm 3 computes its regression only over learning episodes in I_h, while LSVI-UCB uses all previous episodes. After the first skipped episode, the two regressions differ, so the equality is false. Lemma 15 and Lemma 16 bound LSVI-UCB's own Q function, not the subset-based Q used by Algorithm 3, so the closeness argument does not transfer. And even if pointwise closeness were true, nothing in the paper shows that acting greedily with respect to a stale, non-optimistic Q gives sublinear regret. The appendix's convergence result for Lambda^{-1} is proven only under Assumptions 19 and 20, which are far stronger than the linear MDP condition and effectively make the state distribution independent of actions. So the paper's central claim, stated in the abstract, that both variants maintain sublinear regret, is unsupported for Algorithm 3.\n\nThe experiments are weaker than the text suggests. Single-run curves with no error bars, the baseline stopped early on the real benchmarks, and the adaptive algorithm actually uses more space than LSVI-UCB on the linearized environments at K=500 (around 2.7 GiB). The synthetic regret curves are consistent with the fixed variant's behavior, but they do not substitute for a regret bound on the adaptive rule.\n\nWho gets value from this? Someone interested in space-efficient RL with linear function approximation might want to build on the fixed-reset idea, and the adaptive trigger might be worth testing as a heuristic. But the paper needs major revision: either prove a regret bound for Algorithm 3 under standard linear MDP assumptions, or explicitly reposition it as an empirical method with no guarantee. I would not cite it as it stands.\n\nRecommendation: send it to peer review, because Algorithm 2 is a legitimate trade-off result and the adaptive idea is worth refereeing seriously. Tell the referee to focus on whether the adaptive variant can be either fixed or honestly relabeled.","headline":"A modest but plausible fixed-reset result and a genuinely new adaptive scheme whose only theoretical support is built on a false equality; the paper deserves referee time but not acceptance as-is.","tokens_in":21398,"tokens_out":3078,"would_cite":false,"duration_ms":36269,"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":"This paper claims that two variants of LSVI-UCB that alternate learning and non-learning episodes reduce space and time usage while keeping regret sublinear.","keywords":["linear MDPs","LSVI-UCB","online reinforcement learning","regret bounds","space efficiency","memory-constrained learning","adaptive learning intervals","linear function approximation"],"falsifier":"Run LSVI-UCB-Adaptive with Budget $K^{0.5}$ on a linear MDP that satisfies Definition 2 but whose initial states are chosen adversarially so that Equation (1) rarely fires; if regret is linear in $K$ while space stays sublinear, the Learn trigger is not a valid proxy for regret.","tokens_in":20344,"feed_emoji":"🧠","tokens_out":12624,"duration_ms":112350,"temperature":0.7,"pith_summary":"LSVI-UCB is one of the few online reinforcement learning algorithms with formal regret guarantees for linear MDPs, but it stores data from every episode, so memory grows linearly in the episode count $K$. This paper proposes two variants that deliberately stop learning for stretches of episodes and discard accumulated samples. The fixed-interval variant resets the workspace every $K^{\\rho}$ episodes and is proved to use space $O_d(|A| K^{\\rho})$ and time $O_d(|A| K^{1+\\rho})$ while keeping regret at $\\tilde O_d(K^{1-\\rho/2})$; the adaptive variant learns only when a cheap matrix-change test fires, and is proved to use space $O_d(|A| \\mathrm{Budget})$ and time $O_d(|A| K \\mathrm{Budget})$, with experiments showing regret close to the original. The payoff is a tunable space-versus-regret trade-off that could make provable RL algorithms usable where memory is scarce.","feed_headline":"Skipping learning rounds cuts RL memory while holding regret low","feed_subtitle":"Periodic resets and change-detection shrink memory from linear to sublinear with mild regret cost.","key_machinery":"The load-bearing mechanism is the workspace reset combined with the fact that LSVI-UCB's regression step needs only the current covariance matrix and the stored feature-reward pairs. The fixed variant caps the number of stored samples by resetting every $K^{\\rho}$ episodes, and Sherman-Morrison rank-one updates keep covariance inverses current without recomputation. The adaptive variant's central object is its Learn trigger (Equation 1), which compares inverse covariance matrices from the last $m$ episodes in Frobenius norm and skips learning when they have not moved by at least $\\tau$; the paper argues that convergence of these inverse matrices in operator norm implies the learned $Q$-function stays close to the one LSVI-UCB would have produced, and proves such convergence under a fixed-state-distribution and independent-Gaussian-feature assumption.","core_discovery":"The paper's central claim is that LSVI-UCB's memory bottleneck can be removed by alternating short learning phases with phases in which the agent only executes its latest policy and stores nothing. The first algorithm, LSVI-UCB-Fixed, resets all accumulated data every $K^{\\rho}$ episodes; over $K$ episodes this gives space $O_d(|A| K^{\\rho})$, time $O_d(|A| K^{1+\\rho})$, and regret $\\tilde O_d(K^{1-\\rho/2})$ with constant probability, interpolating between the original algorithm's linear memory and a much smaller footprint. The second algorithm, LSVI-UCB-Adaptive, keeps a rolling window of the last $m$ inverse covariance matrices and learns only when the maximum Frobenius-norm difference among them crosses a threshold $\\tau$, subject to a per-phase budget on learning episodes; the paper proves space $O_d(|A| \\mathrm{Budget})$ and time $O_d(|A| K \\mathrm{Budget})$, and reports that on synthetic linear MDPs and linearized Atari RAM environments its regret is experimentally indistinguishable from LSVI-UCB. The fixed variant's regret bound is proved; the adaptive variant's regret claim is experimental rather than proved.","pith_inferences":["The same learn-skip-reset pattern could be applied to other regression-based RL algorithms that maintain a design or covariance matrix, provided a cheap error proxy exists; this is our inference, not a paper claim.","A natural next step the paper leaves implicit is a regret bound for LSVI-UCB-Adaptive under assumptions weaker than its fixed-distribution and Gaussian-feature assumptions; without such a bound the adaptive variant's practical claim rests on the reported experiments.","The Learn trigger itself could be made cheaper by using a sketched or spectral approximation of the inverse-covariance difference instead of exact Frobenius norms; we offer that as a testable extension."],"forward_implications":["Setting $\\rho=1/2$ in LSVI-UCB-Fixed gives space $O_d(|A| \\sqrt{K})$ and time $O_d(|A| K^{3/2})$ with regret $\\tilde O_d(K^{3/4})$, a concrete memory-regret knob for deployments.","The adaptive variant decouples memory from total episode count: space remains within $O_d(|A| \\mathrm{Budget})$ no matter how long the agent runs, once the budget and lookback window are fixed.","On linearized Atari RAM environments, both variants completed 500 episodes while the baseline LSVI-UCB was stopped at 280 because of time and memory, suggesting the approach transfers beyond synthetic MDPs.","If the adaptive variant's regret is truly close to LSVI-UCB, provable RL becomes usable on embedded or low-power devices where linear-in-$K$ memory is infeasible."],"supporting_citations":[{"why":"Defines the LSVI-UCB algorithm and its regret, time, and space bounds; the fixed variant's proof reuses LSVI-UCB correctness over each interval.","marker":"[JYWJ23]"},{"why":"Supplies the covariance concentration result used in Appendix A to show the inverse design matrices converge under Gaussian features.","marker":"[Ver10]"},{"why":"Provides the companion eigenvalue concentration bounds cited with [Ver10] in Lemma 14.","marker":"[ALPTJ12]"},{"why":"Supplies the contrastive representation learning procedure used to turn Atari RAM environments into linear MDPs for the real-world benchmarks.","marker":"[ZRY+22]"},{"why":"Supplies the ALE environments (Alien and Phoenix) whose RAM states are linearized and used in the experiments.","marker":"[MBT+18]"}],"fun_headline_variants":["RL memory slashed by skipping learning rounds, regret stays low","Periodic resets shrink RL memory, regret barely moves","Linear MDP RL: learn less, remember less, regret low","LSVI-UCB tweak: skip learning, save memory, keep regret"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The adaptive variant's savings depend on the assumption that a small change in the regression matrix used by the algorithm means it can safely skip learning; this is proved only in a special setting where states come from a fixed distribution and features are independent Gaussian draws.","fun_headline_variants_meta":{"raw":{"variants":["RL memory slashed by skipping learning rounds, regret stays low","Periodic resets shrink RL memory, regret barely moves","Linear MDP RL: learn less, remember less, regret low","LSVI-UCB tweak: skip learning, save memory, keep regret"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000819,"raw_usage":{"total_tokens":3579,"prompt_tokens":931,"completion_tokens":2648,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":547,"completion_tokens_details":{"reasoning_tokens":2573}},"tokens_in":547,"tokens_out":2648,"duration_ms":22384,"temperature":1.0,"reasoning_tokens":2573,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T19:10:13.437686+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run LSVI-UCB-Adaptive with Budget $K^{0.5}$ on a linear MDP that satisfies Definition 2 but whose initial states are chosen adversarially so that Equation (1) rarely fires; if regret is linear in $K$ while space stays sublinear, the Learn trigger is not a valid proxy for regret.","supporting_citations":[],"review_version":1}