{"id":"7d2977f6-86e0-4f29-94cb-60be52a3f396","arxiv_id":"2506.13862","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"StaQ, a finite-memory Policy Mirror Descent algorithm, converges to the optimal entropy-regularized policy with a sufficiently large window of past Q-functions and performs competitively with baselines.","lead":"StaQ is a reinforcement learning algorithm that stores only the last M learned value functions and provably converges when M is large enough. It gives neural-network based Policy Mirror Descent an exact, optimization-free policy update and reduces performance swings on discrete-action benchmarks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The exact-Q finite-memory convergence proof (Thm 4.4) appears internally sound, but StaQ's deep RL version inherits an unmeasured Q-evaluation error that Thm A.6 amplifies by roughly 10^5 at gamma=0.99, M=300, so the practical convergence guarantee is not actually certified.","rationale":"I read the paper in good faith and checked the central exact-Q argument. The weight-corrected update (Eq. 10), the identity for the logits (Eq. 11), the approximate policy improvement bound (Cor. 4.1.2), and the recurrence in Lemma 4.3 are coherent, and the threshold in Thm 4.4 follows from the d1+d2<1 condition. So the theoretical claim that a large finite M removes the residual error under exact policy evaluation is credible. The load-bearing soft spot is the step from that theorem to the deep RL algorithm. StaQ uses fitted Q-iteration with a replay buffer, target networks, an epsilon-softmax behavior policy, and annealed entropy weights, and nowhere does it bound the resulting evaluation error eps_eval. Thm A.6 does give an explicit bound, but with the default hyperparameters the amplification factor is enormous, and App. B.4 itself shows Q-function spikes that are compatible with a large eps_eval. The reader's weakest_assumption identifies exactly this gap, and I agree with it. The verdict should remain CONDITIONAL: the exact-Q contribution is sound, the deep RL algorithm is plausible and empirically competitive, but the convergence guarantee for StaQ as implemented is not established without measuring or controlling eps_eval.","tokens_in":43270,"tokens_out":14565,"duration_ms":146060,"concrete_test":"During a Hopper-v4 StaQ run with M=300 and gamma=0.99, freeze every 5000-step policy evaluation and estimate eps_eval on 500 held-out states by comparing the learned Q_k(s,a) with multi-rollout Monte Carlo returns of the current policy pi_k. Then compute the Thm A.6 residual (1+gamma^2)eps_eval/((1-gamma)(1-d1-d2)) using the actual beta at that iteration. If the residual exceeds, say, 10% of the scale of the optimal Q-function, the deep-learning convergence claim is unsupported and the paper should state explicitly that StaQ's practical stability rests on an empirically unverified evaluation-error assumption.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Thm 4.4 is a statement about exact policy evaluation. The version that covers StaQ's FQI-based Q-functions, Thm A.6, replaces zero residual with (1+gamma^2)eps_eval/((1-gamma)(1-d1-d2)). At the paper's default gamma=0.99 and with beta near the annealed value 0.95 (M=300), d1+d2 is about 0.9996, so the denominator is about 4e-4 and the multiplier is about 5e5; for beta near 0.98, M=300 fails the d1+d2<1 condition entirely. Because eps_eval is not measured anywhere in the experiments, and App. B.4 (Fig. 10) documents large Q-value swings between iterations, the deep RL algorithm is not shown to satisfy the assumptions of the convergence theorem. This is a gap between the exact finite-memory EPMD result (where the 'no residual error' language is warranted) and StaQ as run: the policy-update step is exact, but the Q-functions entering it are the unquantified weak link.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes memory-limited variants of entropy-regularized Policy Mirror Descent (EPMD). After observing that the exact EPMD policy update requires summing all past Q-functions, the authors introduce two finite-memory updates: a vanilla truncation (Eq. 6), which retains a residual error of order β^M, and a weight-corrected update (Eq. 10), which renormalizes the weights so that, for M above a closed-form threshold, the iterates converge to the optimal entropy-regularized Q-function Q*_τ without residual error (Thm 4.4). The resulting algorithm, StaQ, stores the last M neural-network Q-functions as a stack of frozen weight snapshots, precomputes the logits ξ^k, and uses FQI with an ϵ-softmax behavior policy for policy evaluation. Experiments on discrete-action MuJoCo, classic control, and MinAtar environments compare StaQ with DQN, M-DQN, PQN, PPO, and TRPO, reporting competitive performance and reduced performance oscillation.","tokens_in":43524,"tokens_out":9201,"duration_ms":99683,"significance":"The exact finite-memory result is the main contribution. Theorem 4.4 gives an explicit, parameter-free sufficient condition on M, and the appendix develops the proofs in detail; if correct, it shows that a few hundred stored Q-functions suffice for convergence in the exact policy-evaluation setting. The stacked-network implementation is also a pragmatic engineering contribution, and the stability evidence is suggestive. However, the paper's broader claim that StaQ 'enjoys strong theoretical guarantees' is not fully supported: the deep RL version relies on approximate Q-functions whose error is never measured, and the experimental entropy-annealing schedule can push β into a regime where M=300 no longer satisfies the theorem's sufficient condition. The paper is therefore stronger as a theoretical contribution plus heuristic deep RL demonstration than as a fully certified deep RL algorithm.","major_comments":[{"comment":"The experimental configuration may not satisfy the sufficient M threshold of Theorem 4.4. The theorem requires M > log(((1-γ)^2(1-β))/(γ^2(3+β)+1-β)) / log β. The paper illustrates the threshold with γ=0.99, β=0.95, giving M≈265, and then states that M=300 was used in all experiments. However, Table 3 shows that the scaled entropy coefficient τ̄ is annealed from 2.0 to 0.4, with η=10 for MuJoCo (and η=20 for classic control). Since β=η/(η+τ) and τ=τ̄/log|A|, β increases as τ decreases; for typical MuJoCo action-space sizes, the final β is roughly 0.98-0.99. At γ=0.99 and β=0.98 the threshold is approximately M≈717, and at β=0.99 it is approximately M≈1510. Thus M=300 may be below the sufficient threshold for the late-training β. The comment after Thm 4.4 that larger M was not observed to help empirically is not a formal justification, since the theorem gives only a sufficient condition. The authors should report the actual β range during training and either set M to satisfy the condition for the maximal β or explicitly state that the deep RL results are heuristic and not covered by Thm 4.4.","section":"Sec. 4.2 (Thm 4.4) vs. Sec. 6 / Table 3"},{"comment":"The convergence guarantee for StaQ as run is not established because the policy evaluation error ε_eval is never measured. The deep RL implementation learns Q^k_τ by FQI from a replay buffer generated by an ϵ-softmax behavior policy (Sec. 5 and Eq. 176), and Assumption A.1 only posits a bounded error ε_eval without quantifying it. Theorem A.6 gives a residual term (1+γ^2)ε_eval / ((1-γ)(1-d1-d2)); at γ=0.99, β=0.95, M=300, d1+d2≈0.9996, so the multiplier is on the order of 5×10^5, making the bound vacuous unless ε_eval is extremely small. The paper's own App. B.4 (Fig. 10) documents large Q-value fluctuations between iterations, and Sec. 7 states that 'policy evaluation errors remain significant.' Therefore the no-residual-error guarantee of Thm 4.4 applies only to the exact policy-evaluation setting, and the claim that StaQ 'enjoys strong theoretical guarantees' is not justified for the algorithm as actually run. The authors should either measure or control ε_eval (or a value-error proxy) and verify the margin d1+d2<1, or explicitly separate the exact finite-memory guarantee from the heuristic deep RL evaluation.","section":"App. A (Thm A.6) and Sec. 5-7"}],"minor_comments":[{"comment":"The phrase 'which we adress in this paper' contains a typo; it should read 'address'.","section":"Sec. 1"},{"comment":"Several passages, especially around Fig. 9 and Fig. 12, contain long garbled '/uni000000...' sequences that appear to result from a character-encoding failure; these should be repaired before publication.","section":"App. B.3 / B.4"},{"comment":"The statement that 'with higher values of β, we did not observe in practice better performance when using as large M as suggested by Thm 4.4' is informal and could be misread as contradicting the theorem; reporting the actual β values used and the associated threshold would be clearer.","section":"Sec. 4.2"},{"comment":"The repeated 'LayerNorm LayerNorm LayerNorm' and 'None None None' entries appear to be table-formatting artifacts; the table should be checked so that each column is aligned with its environment group.","section":"Table 6"},{"comment":"No code availability statement is provided; given the complexity of the stacked-network implementation, releasing code would substantially improve reproducibility.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the exact finite-memory EPMD result appears to be a genuine theoretical contribution, and the proofs are detailed and internally consistent at first pass. The main concern is the bridge to the deep RL algorithm: the empirical StaQ uses unmeasured Q-evaluation error and an annealed β that can push the required M beyond 300. These issues are fixable by reporting the β schedule, verifying the theorem's condition, and tempering the claims about the deep RL algorithm's guarantees. I do not see a fatal flaw in the exact-policy-evaluation theorem itself."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real result with an honest gap. The weight-corrected update in Eq. 10 and Theorem 4.4 are new: prior finite-memory PMD schemes either truncated with an irreducible error or had no deletion analysis, and here convergence to Q*_tau without residual error is proven for a sufficiently large finite M. I checked the main proof line and the contraction argument in Appendix A; it holds together, in the exact-evaluation setting where Q-functions are known. The batched stacked-network implementation is also a genuine practical contribution: M=300 costs little wall-clock, and the empirical story is credible, with reduced oscillation shown via tolerance intervals and the MountainCar failure diagnosed rather than hidden.\n\nThe soft spots are real but not fatal. The paper is admirably explicit that only the policy update is exact; the Q-functions entering it come from FQI and are only assumed to satisfy epsilon_eval. Theorem A.6 then says the asymptotic error scales as (1+gamma^2) epsilon_eval / ((1-gamma)(1-d1-d2)). At gamma=0.99 and M=300, with beta near 0.95, that denominator is around 4e-4, so epsilon_eval is amplified by roughly five orders of magnitude. The paper never measures or bounds epsilon_eval, and Appendix B.4 itself shows large Q-value swings. So the practical convergence guarantee for StaQ as run is not certified. That does not invalidate Theorem 4.4—it just means the deep RL stability claim should be stated as heuristic and supported by a measured evaluation-error term or a more stable critic. The M=300 choice also matches the theorem only for one beta value, while beta changes under entropy annealing; worth a sentence.\n\nI disagree with any reading that calls this a load-bearing flaw. The central idea is sound, the proofs are parameter-free, and the empirical baseline comparisons are fair. The paper deserves a serious referee. My recommendation: send to peer review, and ask the authors to (1) measure or upper-bound epsilon_eval on at least a subset of environments, (2) clarify the annealed-beta mismatch with the M threshold, and (3) release code. Who is this for? Anyone working on regularized policy optimization, PMD, or stable deep RL; it gives a clean testbed and a reference point. I would bring it to reading group and would cite the weight-correction theorem.","headline":"Solid theory for exact finite-memory PMD, but the deep RL version ships with an unmeasured Q-evaluation error that the paper's own bound amplifies enormously; referee-worthy with revisions.","tokens_in":44090,"tokens_out":1673,"would_cite":true,"duration_ms":22471,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Finite-memory Policy Mirror Descent can retain the exact convergence guarantee of full PMD, provided it keeps enough Q-functions and re-weights the newest one.","keywords":["Policy Mirror Descent","entropy regularization","finite-memory policy update","stacked neural networks","deep reinforcement learning","Q-function averaging","policy stability"],"falsifier":"Run the weight-corrected finite-memory EPMD update in a small tabular MDP with exact policy evaluation, choose $\\gamma = 0.99$ and $\\beta = 0.95$, and compare $M = 264$ with $M = 265$. Theorem 4.4 predicts $\\|Q^*_\\tau - Q^k_\\tau\\|_\\infty$ decays to zero at $M = 265$ but plateaus at a positive value at $M = 264$.","tokens_in":43070,"feed_emoji":"🧠","tokens_out":7485,"duration_ms":67515,"temperature":0.7,"pith_summary":"The paper's goal is to make Policy Mirror Descent (PMD) implementable in deep reinforcement learning without losing its convergence guarantee. In PMD, the entropy-regularized policy update is a weighted geometric sum of all past Q-functions, which is intractable for neural networks; the authors propose keeping only the last $M$ Q-functions and adding a weight-correction term. Their main theorem states that if $M$ is finite but large enough, this finite-memory scheme converges to the optimal entropy-regularized Q-function with no residual error, unlike a plain truncated sum. The resulting algorithm, StaQ, stores $M$ frozen Q-network snapshots, deletes the oldest when the stack overflows, and performs the policy update by a batched forward pass that is optimization-free. Experiments show StaQ is competitive with established deep RL baselines and exhibits markedly less performance oscillation, so the paper positions it as a stable testbed for separating policy-update error from policy-evaluation error.","feed_headline":"StaQ stores 300 Q-functions and provably converges","feed_subtitle":"The weight-corrected finite-memory PMD update removes the residual error that earlier truncated implementations had.","key_machinery":"The load-bearing object is the logits update for finite-memory entropy-regularized Policy Mirror Descent. Exact EPMD sets $\\xi^{k+1} = \\beta \\xi^k + \\alpha Q^k_\\tau$, which expands into an infinite geometric sum of Q-functions; StaQ replaces it with the weight-corrected finite-memory update $\\xi^{k+1} = \\beta \\xi^k + \\alpha Q^k_\\tau + \\frac{\\alpha \\beta^M}{1-\\beta^M}(Q^k_\\tau - Q^{k-M}_\\tau)$, keeping only the last $M$ Q-functions. The correction term deletes the oldest Q-function while re-weighting the newest one so the retained weights sum to one. The argument is carried by the approximate policy improvement theorem, which bounds the loss in the Q-function at each step by a quantity proportional to the distance between the true previous policy and the policy actually used in the KL regularization; when the stack is long enough, that distance shrinks to zero as the Q-functions converge. The implementation packages this as a stacked neural network: $M$ frozen weight snapshots evaluated in one batched GPU forward pass, a policy update that is a single push onto the stack, and a FIFO deletion when the stack exceeds $M$.","core_discovery":"The central claim is Theorem 4.4: for the weight-corrected finite-memory EPMD update $\\xi^{k+1} = \\beta \\xi^k + \\alpha Q^k_\\tau + \\frac{\\alpha \\beta^M}{1-\\beta^M}(Q^k_\\tau - Q^{k-M}_\\tau)$, if $M > \\frac{\\log\\left(\\frac{(1-\\gamma)^2(1-\\beta)}{\\gamma^2(3+\\beta)+1-\\beta}\\right)}{\\log \\beta}$, then $\\|Q^*_\\tau - Q^k_\\tau\\|_\\infty$ is bounded by $(d_1 + d_2 d_3^{-1})^k \\max\\{\\|Q^*_\\tau\\|_\\infty/\\gamma,\\, \\|Q^*_\\tau\\|_\\infty + \\|Q^0_\\tau\\|_\\infty\\}$, so the iterate converges to $Q^*_\\tau$ without residual error. In plain terms, deleting the oldest Q-function is harmless once the stack is long enough, provided the newest Q-function is slightly overweighted so the geometric weights still sum to one. That re-weighting is the difference between a truncated sum, which leaves a permanent approximation error, and a convergent finite-memory algorithm.","pith_inferences":["The 'keep the last $M$, re-weight the newest' correction is a parameter-isolation trick from continual learning; the same re-normalized sliding-window idea could be transferred to other online learners that maintain geometric averages over stale function snapshots.","The authors sketch a continuous-action extension along SAC lines, replacing the soft target $\\exp(Q/\\tau)$ with $\\exp(\\xi_k)$; a direct test would be whether averaging over many past Q-functions stabilizes the actor target without sacrificing the closed-form update.","Theorem 4.4's memory threshold should be read as pessimistic; the paper's own results use $M=300$, and measuring the actual evaluation error $\\epsilon_{\\mathrm{eval}}$ in the deep experiments would connect the practical stability to the error term in Theorem A.6."],"forward_implications":["A practitioner can run an exact closed-form PMD policy update with only a few hundred stored Q-networks: with $\\gamma = 0.99$ and $\\beta = 0.95$, the theorem requires $M = 265$.","Increasing memory beyond the threshold buys little asymptotically, since the finite-memory convergence rate approaches the exact EPMD rate $\\beta + \\gamma(1-\\beta)$ as $M \\to \\infty$.","Training wall-clock time is nearly independent of $M$ on GPU, because all $M$ Q-networks are evaluated in parallel and the policy update is optimization-free.","Because the policy update introduces no approximation error, any remaining instability in StaQ can be attributed to policy evaluation, which makes the algorithm a clean testbed for improved Q-learning."],"supporting_citations":[{"why":"Supplies the exact EPMD convergence theorem and the approximate-EPMD proof template that the finite-memory analysis extends.","marker":"Zhan et al. (2023)"},{"why":"First to store a small set of past Q-functions in a DKL-regularized policy iteration experiment and observe increased stability.","marker":"Abbasi-Yadkori et al. (2019)"},{"why":"An earlier PMD-style regularized policy iteration algorithm whose replay-based approach StaQ builds on.","marker":"Lazic et al. (2021)"},{"why":"Provides the entropy-regularized Bellman operator properties used throughout Appendix A.","marker":"Geist et al. (2019)"},{"why":"Gives the M-DQN baseline and the KL-plus-entropy value iteration perspective; also documents the discrete-action SAC link.","marker":"Vieillard et al. (2020b)"},{"why":"Gives the PQN baseline that outperforms StaQ on some MinAtar tasks and motivates strengthening the policy-evaluation component.","marker":"Gallici et al. (2025)"}],"fun_headline_variants":["StaQ it: finite-memory PMD that provably converges","StaQ strips PMD's residual error with finite memory","Finite-memory StaQ converges without residual error","StaQ it: deleting old Q-functions is safe if stack is long"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The convergence theory assumes the Q-function estimate used in the update is exact or has a bounded error $\\epsilon_{\\mathrm{eval}}$; the deep StaQ version learns off-policy with a replay buffer and never measures this error, so if Q-learning turns unstable the theorem's bound does not apply.","fun_headline_variants_meta":{"raw":{"variants":["StaQ it: finite-memory PMD that provably converges","StaQ strips PMD's residual error with finite memory","Finite-memory StaQ converges without residual error","StaQ it: deleting old Q-functions is safe if stack is long"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000589,"raw_usage":{"total_tokens":2787,"prompt_tokens":991,"completion_tokens":1796,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":607,"completion_tokens_details":{"reasoning_tokens":1721}},"tokens_in":607,"tokens_out":1796,"duration_ms":13772,"temperature":1.0,"reasoning_tokens":1721,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:27:29.062806+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the weight-corrected finite-memory EPMD update in a small tabular MDP with exact policy evaluation, choose $\\gamma = 0.99$ and $\\beta = 0.95$, and compare $M = 264$ with $M = 265$. Theorem 4.4 predicts $\\|Q^*_\\tau - Q^k_\\tau\\|_\\infty$ decays to zero at $M = 265$ but plateaus at a positive value at $M = 264$.","supporting_citations":[],"review_version":1}