- Rating
- 2
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 1
Read review
Paper summary
This paper introduce a framework called runtime aware MDP (RAMDP), which considers computational time of a policy and discounts reward according to it. The authors also introduce a notion of variable-compute policy, which abstract computational architectures with varying computational time, such as CoT.
Experimentally, it is observed that a variable-compute policy with the IRU architecture can tune appropriate the number of computational steps in puzzle-solving environments.
Critical strengths
The consideration of computational time strategy in multi-step reinforcement learning seem practically important. The notion of variable-computation policies is enough general and can be used in several fields.
The results that a IRU policy can obtain the appropriate number of computational steps after training is interesting.
Critical weaknesses
One of my complaints is that the runtime only affects the reward discount. Practically, one motivation to consider computational time is that the state of the environment changes over real times. I believe the framework can be extended to include such situations: it can be thought that, when a computational step proceeds, the state of environments proceeds also one step. Moreover, when the computational state space is fixed, a MDP whose states are pairs of environment states and computational states can be considered. The difference between this framework and RAMDP in this paper is whether the transition on the computational state space depends on the parameters or not: however, the parameter dependence of computational transition can be absorbed into the controller's parameter dependence by enlarging the computational action set.
My major concern to this research is that the dependence of computational efforts on states is not investigated, although it is the novel point. The dependence on instances is not novel because it can be realized in single-turn settings, which is already studied in prior work. At the environments of lightsout and sliding puzzle, since the reward is only given when an instance is solved, when thought time is taken does not affect to the trajectory return. Thus, these experiments are essentially the same as the prior studies of reasoning effort.
While the RAMDP formulation seems to assume positivity of reward implicitly, it is strange the negative reward is set in Sokoban environment. Actually, the authors say, "we would expect the variable-compute policy to always spend compute steps", then why does such an experiment have been conducted? Moreover, although this paper says, "we focus on long-term decision-making problems where the generated action leads to a stochastic next state," all environments in experiments seem deterministic. As a result, the experiments in this paper do not reflect the generality of the formulation.
In RAMDP formulation, the reward is discounted with computational time rather than depending on walltime. Thus, theoretical results on Section 3 seem trivial.
It is also insufficient that the dependence of optimal policy on the discount factor is not discussed because it should control the tradeoff between computational cost and environmental reward.
Minor comments:
- In the last section, the paper says that the experiments have been conducted in 'control tasks,' but these environments are puzzle-solving rather than control tasks.
- The fact that "having more compute steps can be detrimental to generalization capabilities" is not "quite surprising" to me because an increase of expressive capability leads to a rist of overfitting in general.
- There exists a typo "Since the there" in the page 8.
Questions for authors
In Figure 5, what does the correlation between the numbers of compute steps and actions mean? What was the purpose of including these graphs?
8 comments
Response (2/2)
Weakness 4: Clarifying non-negative rewards in formulation and Sokoban’s negative reward
Thank you for raising this gap between the theory and the experiments. We have rerun the Sokoban experiments to only use non-negative rewards, removing the negative step penalty (see Figure 3 [third column], lines 392-411 and Figure 4 [third column], lines 432-450 of the updated manuscript). Our experiments show that variable-compute policies continue to be competitive to uniform-compute policies, achieving a slightly better success rate while maintaining the compute.
As a side point, we note that practitioners might add dense reward signals to encourage exploration, such using as a negative step penalty (e.g. Vasan et al. (2024) discuss some varieties of reward design in real world robotics tasks). Given this preference, in order to use the RAMDP framework, we can ensure the reward range remains positive by appropriate reward shaping (e.g. see Chapter 3 of the excellent thesis by Ng (2003); or the paper by Ng, Harada, & Russell (1999)) so that the optimal policy remains the same.
Weakness 5: Missing stochastic transitions
Thank you for pointing this out, indeed stochastic environments should be considered! We refer the reviewer to the general response regarding “On improving the clarity of the experimental setup and the conclusions from the empirical results” where we thoroughly address this concern.
Weakness 6: Example in section 3 seems trivial
We refer the reviewer to the general response regarding “Theoretical results are somewhat weak or trivial” for the detailed response to addressing your concerns.
Weakness 7: Insufficient discussion on the impact of discount factor
Thank you for raising this concern. In the original manuscript we had deferred such a discussion (along with an ablation experiment) to Appendix G. We have updated the manuscript to include this discussion in Section 6 of the main paper now (see Figure 5 on lines 451-466 and the discussion on lines 486-493).
The theory suggests that with larger discount factors, the penalty on spending computation decreases, thus the variable-compute agent can afford to spend more compute time without losing performance. We conducted experiments in the lightsout environment with implicit CoT to test this hypothesis (see Figure 5). From the experimental results, we observed that as we increased the discount factor, the variable-compute agent spent more compute without decreasing the discounted return. At the same time its success rate is consistent across discount factors. This suggests that this agent can trade off performance and compute-time based on the cost induced by the discount factor.
Minor comment 1: Interpretation of “control task”
We believe the confusion stems from the definition of “control”. We say “control” to mean having an agent making decisions that change the environment (Sutton and Barto, 2018). To minimize the confusion we have updated the manuscript by dropping the word “control”.
Minor comment 2: Unsurprising finding
Thank you for the input, we agree that the phrase "having more compute steps can be detrimental to generalization capabilities" was unnecessary and have removed it from the updated manuscript.
Minor comment 3: Typo
Thank you for catching the typo; we have fixed it in the updated manuscript.
Question 1 (for the authors): Utility of the “action vs. compute-time” plot (Figure 5 in the old manuscript; Figure 13, left, in Appendix F in the updated manuscript)
We agree that the plot can seem out of place and is not critical to the main research questions addressed in the experiments—we have moved them to Appendix F. To summarize the findings, we observe that the trained policy spends less computation on particular actions in both environments (Figure 13, left) but this phenomenon does not seem to correlate with the action frequency (Figure 13, right). We speculate that this is more so due to the learning dynamics of the policy, which we leave to future work.
We again thank you for your service. Please reach out if something is still unclear. Additionally, if we were able to answer your concerns satisfactorily, please consider revising your score.
Thank you for detailed response!
However, I maintain my rating because my main concern is not resolved.
While I agree that studies considering reasoning effort in non-LLM model is rare, the fact that the model is not LLM is weak as novelty, especially because LLMs solve more practical tasks. I still believe that the truely novel and interesting point is not non-LLM setting but multi-turn setting.
Thinking why states are equilavent to instances, I have noticed that the policy has no memory in the setting of this paper because the computational state is reset in each step. However, I believe this setting is not natural for considering reasoning effort in multi-step tasks, because the presence or absence of memory is likely to affect computational cost even if the environment has the Markov property. Even if the task has multi-step, when computational process is done in each one step, it is not so much different from single step computation. In my opinion, to investigate essentially different situation from the single-turn setting, a policy with memory which distributes computational costs in one episode depending to states should be considered.
Response (1/2)
We thank you for your detailed review and positive comments! It has provided us with a lot of good feedback and helped improve the paper’s presentation.
Changing environment states, while the agent computes an action, is often studied under the keyword “real-time RL”, and we agree that it is a more general framework with important applications such as RL control for robotics.
However, in this paper, we’re interested in (and further investigating the consequences of) the fact that computing the “optimal action” has some irreducible computation time. If we include environment state transition over time, the potential stochasticity of proceeding states can conflate with identifying this computation. For instance, with a changing environment, the agent would also have to trade-off taking quick but sub-optimal actions that result in favourable occupancy measures. Whereas in RAMDP, where the environment pauses, the agent only needs to consider the discounted reward. Another concern is how one should handle proceeding states while the policy is computing (e.g. see Anokin et al. (2025)) which yields a different type of conflation. Nevertheless, based on our results, we found that even in this simpler setting, a source of requiring variable-computation stems from having a constrained policy class—this is an additional source of delay that is different from the randomness due to hardware execution of a uniform-budget policy in Ramstedt and Pal (2019). We have updated the manuscript (lines 155-158) to clarify this choice. We believe that extending our analyses on RAMDPs to real-time RL would be a very fruitful and practical next step.
Thank you for raising the point that one can embed computational state/action into MDPs. We refer the reviewer to the general response regarding “Why RAMDP over other variants of MDPs” as we have included experiments to address this concern.
We believe that our choice of words might have been confusing—in the analysis of Figure 6, an instance is equivalent to a state. We compute the minimum distance of a given state to the goal state in terms of the number of actions required (shortest path). We have updated the manuscript to not use the term “instance”.
Regarding prior studies on reasoning efforts for these environments. As far as we know, Guez et al. (2019), Ghugare et al. (2026), Chung et al. (2023) are few non-LLM RL papers where they conduct experiments to investigate whether increasing uniform-compute budget can improve performance on (a subset of) these environments. In contrast, our work shows that our variable-compute agents can spend varying compute times on different states, albeit this is not always correlated to state difficulty. We would be happy to include additional references that conduct similar analyses in the non-LLM RL setting, i.e., non-textual based.