{"id":"a2857b2b-4da2-4198-9a9b-eac99ce80916","arxiv_id":"2602.05999","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Policies with more compute can provably solve and generalize to longer-horizon RL tasks that policies with less compute cannot, and a minimal recurrent (IRU) architecture realizes these benefits.","lead":"This paper proves that reinforcement-learning policies with more computation can solve harder problems than policies with less computation, even with the same number of parameters. It also introduces a recurrent architecture that gets better as it is allowed more computation.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.1's 'any π∈Π_g' outruns Assumption 1; proof only covers policies with |⟨M⟩|<K_max, so the literal statement is not justified.","rationale":"The reader identified Assumption 1 as the most fragile step; I agree and sharpen it. The proof's uniformity argument is valid for the class of policies with bounded description length, but the theorem statement does not carry the restriction, so it is strictly stronger than what is proven. This is the most load-bearing concern because it directly affects the central claim that any less-compute policy is arbitrarily worse. However, the gap is easily repaired by stating the theorem for finite/bounded-description policy classes, which is the practically relevant case (fixed parameter count). The empirical work is broadly supportive and not undermined by this formal issue. The reader's CONDITIONAL verdict remains appropriate; no verdict change is needed.","tokens_in":18806,"tokens_out":33191,"duration_ms":396621,"concrete_test":"Formalize Theorem 4.1 in a proof assistant (e.g., Lean) with Definition 2 exactly as written and Assumption 1 used only as a separate assumption. Attempt to discharge the universal quantifier over all π∈Π_g. If the proof needs to add the hypothesis '|⟨M_π⟩|<K_max' to the theorem statement (or to restrict Π_g), the concern lands. Alternatively, analytically re-derive the construction of S and p(s0) (eqs. 6–8) for a policy with |⟨M_π⟩|>K_max and check whether that policy's failure states have positive measure; if not, the literal theorem fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 4.1 quantifies over all π∈Π_g (Definition 2), but the proof in Appendix A implicitly restricts to policies satisfying Assumption 1: it needs a uniform n_max, obtained by bounding the universal simulator's overhead c(|M|)≤c(K_max), and it needs the start distribution to sample machine descriptions uniformly from {0,1}^{≤K_max}. For any g-bounded policy whose canonical TM has length ≥K_max, its diagonalizing input ⟨M_π⟩10^l lies outside the support of p(s0), so the proof gives no reason such a policy fails; it could agree with D on every state in S and achieve optimal return. Thus the theorem as worded is false/unsupported. The intended result is a policy-class separation for the finite class of policies with description length <K_max. This is fixable and does not sink the paper's practical claim, but it is a genuine correctness gap in the central theoretical statement.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper argues that reinforcement learning policies should be viewed as computational processes whose time budget is distinct from their parameter count. It defines time-bounded policy classes via Turing machines and proves two results: Theorem 4.1 (Policy Hierarchy Theorem), claiming that for suitable time bounds g(n) and t(n) there exists an MDP where the optimal policy is in Π_f for f(n)∈O(t(n)) while every policy in Π_g obtains arbitrarily lower return; and Theorem 4.2, claiming a similar separation for long-horizon generalization. The paper also introduces a minimal recurrent architecture, the Interpolation Recurrent Unit (IRU), and reports experiments on 31 discrete and continuous tasks showing that increasing the number of recurrent steps improves performance and generalization to longer-horizon tasks relative to MLPs and ResNets, even when the ResNet has roughly 5× more parameters.","tokens_in":19078,"tokens_out":11981,"duration_ms":117357,"significance":"If the theoretical claims are made rigorous, the contribution is significant: it provides a formal vocabulary for compute-constrained RL, supports the intuition that test-time compute matters independently of parameters, and gives a simple architecture that empirically delivers consistent gains over standard feedforward baselines. The paper is also commendable for sharing code, using standard hyperparameters, and including yoked experiments and a value-of-compute diagnostic. The main reservation is that the central theorems are currently over-stated relative to the proof: the proof only works for policies with description length below a fixed constant, while the theorem quantifies over all policies in Π_g. Once this is repaired by restricting the policy class, the formal result is weaker but still meaningful, and the empirical contribution stands largely unaffected.","major_comments":[{"comment":"Theorem 4.1 (and by inheritance Theorem 4.2) quantifies over all policies in Π_g, but the proof in Appendix A only establishes the claim for policies whose canonical description satisfies |⟨M⟩|<K_max. The constructed state space S={(⟨M⟩10^*): |⟨M⟩|<K_max} excludes the diagonalizing input of any g-bounded policy whose description length is at least K_max; for such a policy the time-hierarchy argument provides no state on which it must differ from D, so it could agree with D on all reachable states and achieve optimal return. Thus the theorem as stated is unsupported under the given definition of Π_g. This is a load-bearing issue for the central theoretical claim. Please either (a) reformulate the theorems and Assumption 1 so that the policy class is explicitly the finite set {π∈Π_g : |⟨M_π⟩|<K_max}, or (b) provide a construction that separates infinite policy classes with unbounded descri","section":"Theorem 4.1 / Appendix A (Assumption 1)"},{"comment":"Assumption 1 is not a well-formed restriction on the class Π_t defined in Definition 2. As written, 'For all policies we consider π∈Π_t' claims that every t-bounded policy has a canonical description shorter than K_max; but Π_t, as defined, contains all t-bounded functions, and any computable policy has infinitely many Turing machine encodings of arbitrary length (e.g., by padding). Hence the assumption is false under the given definitions. If the intended meaning is to restrict attention to policies with description length < K_max, this restriction must be incorporated into Definition 2 or into the theorem statements; otherwise it is unclear which policy class the results apply to.","section":"Assumption 1, Definition 2"}],"minor_comments":[{"comment":"The text says 'after 2.5 (50%) and 5 (50%) million environment steps'; the second percentage should be '100%'.","section":"Section 6.3, Table 1"},{"comment":"The VoC formula should specify which policy generates the trajectory s_1,...,s_n (presumably π_{t2}) and whether the expectation is over start states or trajectories; the text below mentions deterministic transitions, but the general case needs a precise definition.","section":"Section 6.5, Eq. (Value of Compute)"},{"comment":"The notation is inconsistent: S is written as a set of strings of the form ⟨M⟩10^*, but the transition function T operates on pairs (⟨M⟩, w). Use pair notation consistently throughout.","section":"Appendix A, Theorem A.2 proof"},{"comment":"The caption refers to 'lightsout-4x4', but the figure panels and the text describe 'lightsout-4x5'. Please correct.","section":"Figure 4 caption"}],"recommendation":"major_revision","confidential_remarks":"The main issue is the quantifier gap in Theorems 4.1 and 4.2. It is likely fixable by restating the theorems for a finite policy class with bounded description length, so I recommend major revision rather than rejection. Please also ask the authors to clarify the status of Assumption 1 relative to Definition 2. The empirical study is broad and appears fair, though it relies on baselines and environments from the authors' own prior work; make sure those are publicly available or clearly cited. The paper's central conceptual message—compute and parameters are distinct axes in RL—remains valuable even with the weakened theorem."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the empirical contribution is solid and the framing is useful, but the headline theory overreaches. The stress-test note is right: Theorem 4.1 quantifies over all g-time-bounded policies, but the proof only works for policies whose Turing machine description is shorter than a fixed K_max. The state space is { (⟨M⟩10^*): |⟨M⟩<K_max }, and the start distribution only samples those, so any policy with a longer description is never evaluated on its own diagonalizing input and could achieve optimal return. The theorem needs to be restated with the description-length bound explicit (or by defining Π_g with that bound). Theorem 4.2 inherits the issue. This is fixable, and it doesn't invalidate the empirical story, but the paper as written should not claim an unconditional policy hierarchy.\n\nWhat's new: the formalization of policies as time-bounded Turing machines, the two theorems as RL applications of the time hierarchy theorem, and the IRU architecture. Even though the proofs are close corollaries of Sipser's result, applying it to RL is a genuinely new step. The experiments are broad—31 tasks across discrete and continuous domains—with parameter/compute tradeoffs against MLPs and ResNets, a yoked experiment that separates data quality from model expressivity, and a value-of-compute measure. The ablation is honest: LSTM is marginally better, IRU is half the parameters and faster. Code is available.\n\nSofter spots: hyperparameters are 'standard' and not tuned; some OGBench baselines are taken from prior work rather than rerun; the ResNet 'overfitting' claim is inferred from high variance, not directly measured; the value-of-compute figure is illustrative only. None of these are fatal.\n\nThis paper deserves a serious referee. The empirical results are useful, and the theory can be repaired. I'd send it to review with the requirement that the authors fix the quantifier in Theorems 4.1 and 4.2 and clarify Assumption 1. After that it would be a solid contribution.","headline":"Useful empirical paper with a genuinely flawed theorem quantifier: Theorem 4.1 overclaims by not restricting policies to the description-length bound that the proof requires.","tokens_in":19538,"tokens_out":3783,"would_cite":true,"duration_ms":40225,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q15","68Q25","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Policies that spend more compute can solve reinforcement-learning tasks that cheaper policies provably cannot.","keywords":["compute-bounded policies","time hierarchy theorem","policy hierarchy","recurrent RL","long-horizon generalization","interpolation recurrent unit","value of compute","goal-conditioned reinforcement learning"],"falsifier":"Run the proof's construction for a concrete pair (g, t): enumerate all g-bounded Turing machines with description length below K_max and test them on the MDP's states s = (⟨M⟩10^l) with l > n_max; if any such machine matches the optimal policy D on all those states, the claimed uniform separation is false.","tokens_in":18714,"feed_emoji":"⚙️","tokens_out":4817,"duration_ms":52551,"temperature":0.7,"pith_summary":"This paper argues that the compute a reinforcement-learning policy spends at decision time is a separate axis from its number of parameters, and that this axis can be as decisive as expressivity. To make this precise, it defines time-bounded policies via Turing machines and proves two separation results: for suitable time bounds, there exist MDPs where the optimal policy needs more compute and every less-compute policy is arbitrarily worse; and there exist goal-conditioned MDPs where a less-compute policy matches the optimum on all training tasks yet fails on infinitely many longer-horizon test tasks. The paper then introduces a minimal recurrent architecture, the interpolation recurrent unit (IRU), which repeats the same gated block a variable number of times with identical parameters, and shows across 31 tasks that more recurrent steps improve performance and long-horizon generalization, often beating residual networks with several times more parameters. A sympathetic reader would take away that 'thinking longer' is not just an engineering trick: it is a formal expressiveness and generalization boundary in RL.","feed_headline":"More compute provably widens what RL policies can solve","feed_subtitle":"A formal policy hierarchy plus a minimal recurrent unit shows extra thinking steps beat 5x larger networks.","key_machinery":"The central objects are time-bounded Turing machines and the policy classes Π_t they define: deterministic policies computable in at most t(n) steps on length-n binary state encodings. The argument's load-bearing step is the classical time hierarchy theorem, which supplies a language L decidable in O(t(n)) but not in o(t(n)/log t(n)); the MDP is built so that acting optimally on a state s requires deciding s ∈ L. To carry this from individual machines to whole policy classes, the paper relies on Assumption 1: every policy's Turing-machine description has length below a fixed constant K_max, which makes the hierarchy theorem's failure threshold uniform across all g-bounded policies. On the em","core_discovery":"The central claim is a computational view of RL policies: a deterministic policy is identified with a time-bounded Turing machine, so the policy class Π_t contains all policies computable within t(n) steps on inputs of length n. The Policy Hierarchy Theorem then states that for any time-constructible g(n) ∈ o(t(n)/log t(n)), there is an MDP whose optimal policy lies in Π_{O(t(n))} while every g-bounded policy earns arbitrarily lower return. The Long-Horizon Generalization Theorem states that in some goal-conditioned MDP, the best g-bounded policy matches the optimal value function on the finite training-task distribution but is arbitrarily worse on infinitely many longer-horizon test tasks.","pith_inferences":["If compute is a separate axis, a natural next step is adaptively choosing the number of recurrent steps per state; the paper's own value-of-compute curves already show per-episode variation that a compute controller could exploit.","The hierarchy results suggest a testable parallel: compute-boundedness can act like partial observability, so recurrent or non-Markov policies may be necessary even in fully observed MDPs—a prediction that could be checked in benchmark design.","A concrete extension would be training IRU policies with a curriculum over the number of recurrent steps rather than a fixed N, then measuring whether the long-horizon generalization gap shrinks further.","The theory focuses on time complexity for single-tape Turing machines; analogous separations for space complexity or boolean circuits would likely carry the same conclusions to architectures closer to modern neural networks."],"forward_implications":["Compute-boundedness is an expressiveness boundary: there exist tasks where no policy with a smaller time budget can reach the optimal return, so RL theory that ignores compute is incomplete.","Additional compute can translate into better generalization rather than worse: a less-compute policy can overfit the training distribution of goals while a more-compute policy generalizes to longer horizons.","The same parameters can be reused across different compute budgets: IRU-(N) improves performance by changing only the number of recurrent steps, decoupling compute from parameter count.","The value-of-compute estimator gives a per-state measure of how much return is lost by temporarily using fewer recurrent steps, and it peaks early in episodes when choosing correctly is both hard and crucial.","Yoked experiments suggest the gains from more compute are mostly due to the policy's added expressivity rather than better data collection, though using compute to explicitly aid exploration remains open."],"fun_headline_variants":["Extra compute, not extra parameters, beats bigger nets in RL","More thinking steps widen what RL policies can learn","Compute-bounded RL: more compute, better generalization","Thinking longer outperforms 5x larger networks in RL","In RL, compute beats parameters: formal hierarchy and tests"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof needs every policy's Turing-machine description to fit in a fixed constant length K_max, so that the time-hierarchy theorem's failure point can be made uniform across all cheaper policies; if descriptions can grow without bound, the constructed MDP's separation could collapse.","fun_headline_variants_meta":{"raw":{"variants":["Extra compute, not extra parameters, beats bigger nets in RL","More thinking steps widen what RL policies can learn","Compute-bounded RL: more compute, better generalization","Thinking longer outperforms 5x larger networks in RL","In RL, compute beats parameters: formal hierarchy and tests"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000176,"raw_usage":{"total_tokens":1108,"prompt_tokens":710,"completion_tokens":398,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":454,"completion_tokens_details":{"reasoning_tokens":319}},"tokens_in":454,"tokens_out":398,"duration_ms":4302,"temperature":1.0,"reasoning_tokens":319,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T04:00:04.209645+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the proof's construction for a concrete pair (g, t): enumerate all g-bounded Turing machines with description length below K_max and test them on the MDP's states s = (⟨M⟩10^l) with l > n_max; if any such machine matches the optimal policy D on all those states, the claimed uniform separation is false.","supporting_citations":[],"review_version":1}