On Computation and Reinforcement Learning

Summary

The paper argues for a computational view of RL policies in which forward-pass compute (time) is a separate axis from parameter count (memory), and asks whether policies can profitably use more compute at fixed parameter count. Treating a policy as a time-bounded model of computation rather than a static state-to-action function is a useful reframing that connects RL to complexity theory and to the recent "reasoning by iterating" trend in language modelling. The theoretical contribution imports the classical time-hierarchy theorem into policy classes $\Pi_t$ of Turing machines with bounded description length (Assumption 1) and derives two existence results: policies with strictly more compute solve MDPs that lower-compute policies cannot (Theorem 4.1), and can generalise to longer-horizon test tasks even when the low-compute class overfits (Theorem 4.2). Empirically, the authors introduce a minimal recurrent block (IRU, a stripped-down LSTM/GRU cell) and show that unrolling it more times consistently improves goal-conditioned DQN, PPO and IQL agents on ~31 boxpick, lightsout and OGBench tasks, matching or beating a ResNet baseline that uses several times more parameters. A "value of compute" quantity, analogous to the value of information in POMDPs, is introduced to measure return lost by using fewer recurrent steps, and a yoked-agent experiment argues that most improvement comes from added expressivity rather than better exploration. The strongest contribution is the framing plus the empirical demonstration that a fixed-parameter recurrent policy can unlock long-horizon generalisation on tasks where strong prior algorithms with static architectures achieve trivial performance. The most important conceptual limitation is a gap between theory and experiment: the theorems are diagonalisation results on constructed self-referential MDPs and speak about strictly larger policy classes, whereas the empirical claim is about a single fixed-parameter architecture unrolled for different numbers of steps. This gap is never bridged, and several supporting claims ("generalisation is provable", "no deterministic policy solution", "most benefits from expressivity") are stated more strongly than what is shown.

Strengths

• Conceptual reframing. Making compute-time an axis distinct from parameter count is a clean, forward-looking framing that connects RL to reasoning-in-LLMs work and immediately suggests new questions (compute-adaptive policies, value of compute).
• Theory–complexity bridge. Casting policy classes as time-bounded Turing machines and importing the time-hierarchy theorem is a well-chosen technical device; the assumption structure (bounded description length $K_{max}$, time-constructibility) is standard and the theorem statements are precise even where the proofs need typographical work.
• IRU architecture is minimal and effective. A stripped-down interpolation cell (two linears + skip connections) that is faster and smaller than an LSTM but recovers most of its gain is a nice empirical result on its own; the ablation shows LSTM is only marginally better despite twice the parameters.
• Wide empirical coverage. ~31 tasks across discrete (boxpick, lightsout) and offline continuous (OGBench: scene, cube, puzzle, antmaze, pointmaze) settings, with three underlying algorithms (DQN, PPO, IQL) — the trend that more recurrent steps help is unusually consistent.
• Non-trivial long-horizon wins. On lightsout-4x5 and boxpick-exact-4, MLP and deep ResNet baselines are at or near zero success while IRU-(5) is well above 50%; on unseen long-horizon eval, IRU frequently outperforms a ResNet with $\approx 6\times$ more parameters.
• Yoked control. Following Ostrovski et al. (2021) to isolate expressivity from exploration is the right control for the causal story, even if the "most benefits" phrasing overreaches.
• Value-of-compute construct. Analogous to value of information, easy to interpret, and Figure 5's shape (peaks early in the episode) is a nice qualitative observation that points at compute-adaptive follow-ups.

Weaknesses

• Theory–experiment gap. Theorems 4.1/4.2 are existential results on self-referential, constructed MDPs; they show that strictly larger classes $\Pi_f \supset \Pi_g$ can solve tasks $\Pi_g$ cannot. The empirical claim is that a single fixed-parameter IRU unrolled longer improves. Nothing in the paper argues that unrolling IRU for more steps traverses the compute hierarchy in the sense of the theorems, so the "theory explains the results" narrative is essentially motivational. This gap should be made explicit rather than blurred.
• "Same value function as $\pi^*$" (Theorem 4.2). As written this is a global equality of value functions, which contradicts the immediately-following clause that $\pi_g^*$ is arbitrarily worse on test tasks. The scoping to the training distribution is intended but not stated.
• "No deterministic policy solution" overreaches. The Section 7 aside asserts that "common knowledge that all MDPs have a deterministic policy solution is no longer true when using computationally bounded policies". The theorems show non-representability within a bounded class, not non-existence.
• Multiple typographical faults in the appendix proofs. The Condition 2 probability and return expressions (Theorem A.1) are visibly scrambled; the running-time inequality has a footnote interleaved with the main sentence; the VoC formula in Section 6.5 does not render at all. These are not just cosmetic — the load-bearing constants and the sign convention of VoC are impossible to verify from the current PDF.
• Compute-controlling story is inconsistent. Section 6.2 says the ResNet has the same effective depth as IRU and hence "a similar amount of compute". Section 6.3 says the ResNet uses "$\approx 2\times$ more compute". These cannot both be true; the compute vs parameter disentangling is central and needs a concrete FLOP measurement.
• Numerical / labelling inconsistencies. Table 1 caption text labels both env-step milestones "50%"; Figure 4 caption references a nonexistent "lightsout-4x4"; the main text says ResNet is beaten on "4/6 tasks" while the Figure 4 caption reports "4/5"; 3M / 500K = 6× parameters, not the headline "5×".
• Peak-at-5 vs 8x-at-10 claim. Figure 2 caption says performance "often peaks at five recurrent steps", but Section 6.3 states an up-to-8× gain going 1 → 10. The relevant tasks and the definition of the ratio (final success? AUC?) are not stated.
• Yoked causal claim overstated. The text concedes an off-policy confound in the complementary comparison ("off-policy bias or the inability of policies with less compute to learn good policies despite high quality data") yet still concludes "most of the benefits of more compute comes from the additional expressivity" — the word "most" is stronger than the evidence with an uncontrolled confound.
• Ablation is single-task. Figure 7 covers only boxpick-exact-4, yet is used to draw broad architectural conclusions ("recurrent ResNet blocks do not achieve the same benefits", "deep recursion works relatively worse"). One task cannot support the generalisation.
• Statistical support is thin. Five seeds with reported std up to 15.2 (boxpick-exact-4 ResNet), 13.6 (lightsout-3x3 ResNet) and 8.9 (lightsout-4x5 IRU) leaves several of the paper's ordering claims within seed noise; no statistical tests accompany the "IRU is more stable" or "peaking at five" claims.
• Fixed-N contradicts the motivating story. The theoretical framing and the VoC analysis motivate compute-adaptive policies, but the actual architecture uses a hard-coded number of recurrent steps. This limitation is acknowledged only in the Conclusion; it deserves a more prominent statement in Section 5 tied to the VoC discussion.
• VoC sign convention. With the definition specifying "$\pi_{t_2}$ over $\pi_{t_1}$" and the plot using $t_1=5$, $t_2=1$, the positive-and-growing curve labelled "IRU-(1) over IRU-(5)" is only interpretable under an unstated sign convention.
• Active/passive mapping in Figure 6. The text discusses varying active compute and passive compute separately, but the figure has three joint (active, passive) pairs per panel; specific claims are not tied to specific bars.
• Self-reference in Theorem A.2. The transfer from A.1's single-step diagonalisation to A.2's multi-step string-reduction MDP requires the test state to encode $\pi_g^*$ itself — this closure is asserted, not shown. Similarly the ordering of $K_{train}$ vs $n_{max}$ is left implicit.

Reproducibility & code

• Seeds and evaluation protocol not published. The paper says "five random seeds" but neither the paper nor the supplied Appendix B tabulates which seeds are used, how many rollouts feed each evaluation point in Figures 2–4, or the smoothing/CI convention. For a table whose std values are as large as 15.2, the difference between a directional and a numerical reproduction depends on these details.
• OGBench IQL settings deferred to another paper. Section 6.1 and Figure 3 are the only continuous-control evidence, but the IQL hyperparameters are not tabulated (unlike DQN and PPO in Tables 2 and 3) and the MLP baseline is imported wholesale from Park et al. (2025) rather than re-run in the same codebase. The comparison mixes result sources with no explicit control that evaluation protocols match.
• Yoked experiment under-specified. Section 6.6 gives only two sentences of protocol. Data volume for the passive agent, its training length, off-policy correction, and the exact (active, passive) pair for each Figure 6 bar are all missing.
• Ablation-block configurations. Section 6.7 replaces the IRU with an LSTM, a feedforward residual block, and IRU + deep supervision, but does not tabulate hidden dimensions, block depths, or the deep-supervision configuration; the last is deferred to a figure in Jolicoeur-Martineau (2025). This makes "recurrent ResNet blocks do not achieve the same benefits" difficult to attribute to the architecture rather than under-tuning.
• Value-of-Compute computation. The rendered VoC formula is missing, and the number of trajectories, sampling policy, and aggregation over successful vs unsuccessful rollouts are unspecified. Figure 5 cannot be numerically reproduced from the paper.
• Compute ratios never measured. The "$\approx 2\times$ compute" / "roughly half the compute" / "$\approx 5\times$ parameters" ratios that carry the central compute-vs-parameters story are stated verbally; no FLOP count or wall-clock measurement is reported in the codebase. For a paper whose contribution is a computational view of RL, actual compute expenditure of every architecture should be measured and released.

Recommended Changes

Essential

• Bridge theorems to experiments. Add a subsection (or extended paragraph) explaining what the theorems do and do not say about the fixed-parameter, variable-unroll IRU. Either exhibit an IRU family that instantiates a compute hierarchy in the theorem's sense, or clearly caveat that the theory is motivational rather than explanatory. Concretely address the "same parameters + more compute" question (opened by the abstract) at the theoretical level.
• Fix the appendix proofs' typography and fill in the gaps. Re-typeset the Condition 2 probability / return expressions in Theorem A.1 and the running-time inequality; add a one-line derivation connecting "cannot decide $L$" to $J(\pi)$ arbitrarily lower than $J(\pi^*)$; explicitly show the self-referential closure that makes Theorem A.2 inherit A.1's diagonalisation; state the ordering between $K_{train}$ and $n_{max}$; scope "same value function as $\pi^*$" to the training distribution.
• Render the VoC formula and pin its sign convention. Include the equation in the main text so Figure 5 is interpretable; align the caption's "IRU-(1) over IRU-(5)" phrasing with the definition's "$\pi_{t_2}$ over $\pi_{t_1}$" ordering.
• Reconcile the compute-vs-parameters accounting. Pick one accounting for the ResNet baseline ("same depth = similar compute" or "$\approx 2\times$ more compute") and back it with actual FLOP counts (or wall-clock) for every architecture in every task. Correct the "$5\times$ parameters" ratio to match the quoted 3M / 500K numbers (or vice versa).
• Fix labelling errors. Change "lightsout-4x4" to "lightsout-4x5" in Figure 4's caption; correct "2.5 (50%) and 5 (50%)" to "2.5 (50%) and 5 (100%)"; reconcile the Figure 4 task count (4/5 vs 4/6) with the panels actually shown.
• Weaken or empirically support the causal claim. Either soften "most of the benefits of more compute comes from the additional expressivity" to a qualitative statement, or add an ablation that controls for the acknowledged off-policy bias in the active-5 / passive-1 comparison.
• Publish seeds and evaluation protocol. List the specific seed set, evaluation rollout counts per figure, smoothing window, and confidence-interval convention. Add a bootstrap or Wilcoxon significance check for the peak-at-5 and "IRU more stable" claims.
• Document the yoked experiment. Expand Section 6.6 (or Appendix B) with data volume, training length, off-policy correction, and a bar-by-bar map from Figure 6 legend to specific (active, passive) settings.
• Rephrase the "no deterministic policy solution" claim in the discussion to "may no longer be representable within a compute-bounded class" so future readers do not conflate representability with existence.

Suggested

• Broaden the ablation. Repeat Figure 7 on at least one long-horizon eval task and one OGBench task before concluding that gating is necessary for compute scaling.
• Tabulate OGBench IQL hyperparameters and re-run the OGBench MLP baseline in the same codebase rather than importing from Park et al. (2025).
• Document ablation baselines. Tabulate LSTM hidden size, recurrent ResNet block depth/width, and the deep-supervision configuration so Section 6.7 stands independently of Jolicoeur-Martineau (2025).
• Move the fixed-N caveat earlier. Reference the "we use a fixed amount of recurrent computation steps" limitation in Section 5 alongside the VoC discussion, framing it as the natural direction for future adaptive-compute work.
• Name the tasks driving the "up to 8×" ratio in Section 6.3, and define whether the ratio is over final success rate or an AUC.
• Replace or reframe the GSM8K/CoT example as intuition rather than an "example of" Theorem 4.2, since the multi-task pre-training confound is exactly what the theorem does not need.
• Flag the compute → partial-observability sentence as a conjecture rather than an implied consequence of Theorem 4.1.