acceptodds
Under review as a conference paper at ICLR 2027

Perform better and spend less: Variable-compute policies in runtime-aware RL

Abstract

We study control problems where an agent is penalized for the time it takes to compute an action. Consequently, in scenarios where taking more time to compute an action results in a better outcome, a trade-off emerges: how should an agent balance the short-term cost incurred for calculating an action against the long-term total reward that taking that action would result in. We formalize such problems as runtime aware MDPs (RAMDPs) that track the compute spent by an agent for determining each action it takes, and discuss some interesting consequences of this formalization. Notably, in some cases, only variable-compute policies, i.e., policies that vary their computation time depending on the environment's state, are optimal in RAMDPs. We also conduct experiments on three simulated environments to illustrate how variable-compute policies can maintain performance while spending less compute when compared to uniform-compute policies.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning, computation, variable compute

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_HgBWOpenReview ↗
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 cmaxc_{\mathrm{max}} 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
AuthorsOpenReview ↗

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.

Weakness 1: Environment state should be changing while the policy is computing

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.

Weakness 2: Embedding computational state/action into the MDP (“Moreover, when the computational state space is fixed … enlarging the computational action set.”)

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.

Weakness 3: Dependence of computational effects on state

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.

AuthorsOpenReview ↗

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.

Reviewer_b18GOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

Proposed: model-agnostic runtime-aware MDP’s, which incorporate the wall-clock time of policy computation/iteration in the MDP

Critical strengths

Strengths:

  • The proposed MDP extension is broad and simple
  • Introduces variable-compute policies, and includes intuitive examples demonstrating their optimality
  • Analysis with the RAMDPs show that a uniform-compute optimum exists for finite MDPs, whereas a restricted controlled must optimal use variable compute
Critical weaknesses

Weaknesses:

  • Despite the broad extension of MDPs, the paper is mostly theoretical/conceptual as the experiments are limited to three small puzzle environments which lack reactivity (no mujoco/atari)
  • If being critical, the RAMDP is pretty must just a semi-MDP where the agent picks each actions duration. Note, Lemma 6 is the SMDP discount identity.
  • Ultimately, the inclusion of the wall time amounts to additional discounting on the reward, which can be implemented somewhat trivially with less elegant methods (see below), making the practical contribution weaker
  • Variable compute only helps under a restricted controller — the results show c=1 is optimal when possible
  • Baselines are missing some related methods like ACT/PonderNet-style halting penalties, early-exit networks, explicit compute-constrained RL, Thought-MDP agents

Ultimately, the paper is well written and appears like the start of an interesting idea but as it stands, lacks novelty against semi-MDP’s or thought-MDPs. Moreover, the experiments are too simple to claim broad empirical evidence of superiority and lack adaptive-computation baselines like ACT, PonderNet etc.

Questions for authors

Integrated in weaknesses

2 comments
AuthorsOpenReview ↗

Response 1/2

We thank you for your comments, constructive feedback, and for appreciating this line of research! We address the weaknesses you raised in the following.

Weakness 1: Missing experiments on reactive environments.

As we understand, reactive environments differ from “thinking” type environments in the sense that different states in a reactive environment are all of the same “difficulty”, i.e., a similar (and minimal) amount of computation would suffice for all the states. We appreciate the reviewer pointing this fact out. However, even for reactive environments, where a uniform-compute policy is optimal, we can still squeeze out additional performance by finding a minimal circuit representation of that uniform compute policy (and thereby saving some amount of computation).

We refer the reviewer to the general response regarding “Theoretical results are somewhat weak or trivial” as we have included experiments to address this concern.

Weakness 2: RAMDP is essentially semi-MDPs, where the agent picks action duration.

Thank you for raising the point that one can cast a RAMDP as a semi-MDP. 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 also want to emphasize that in countable state semi-MDPs, variable computation will again become important and RAMDPs complement semi-MDPs well. For example, consider MDPs with countable state space with computable functions as the policy class. By time-hierarchy theorem from complexity theory, we know that there are decision problems that require beyond constant time depending on the input, i.e., variable-compute functions (see Theorem 11). Furthermore, it is generally impossible to have constant-compute functions that map each state to a particular runtime, action duration, or option (as this is effectively equivalent to solving the halting problem).

Weakness 3: Walltime amounts to additional discounting, which can be implemented by less “elegant” methods.

We believe that you are referring to the fact that since walltime only changes the discounting, we can view the RAMDP as an MDP (where, as the agent computes an action, the environment transition “pauses” while the reward keeps getting discounted). This is absolutely correct.

However, note since even a finite-state RAMDP contains the walltime, the equivalent MDP no longer remains finite, but becomes countable. As a result, naively applying methods like, say, policy gradient with TD-style critic learning can be prohibitively inefficient. To resolve this problem we asked whether one can use time-independent representations. It was not immediately obvious to us that time-independent policies are sufficient, and in fact the results are slightly different between deterministic policies and stochastic policies (Theorem 4 and Theorem 17). Specifically in the former the walltime-independent policy is uniformly better than the walltime policy, while in the latter the walltime-independent policy is only better with a fixed initial walltime.

Consequently we can use runtime factorization (Lemma 5) that gives us better learning bounds (Theorems 30 and 34):

  • Please refer to Figure 7 (lines 1620-1634), where we show that default methods, indicated by red and blue curves, have a much higher variance than our factorized variant, indicated by a green curve.
  • Also see Figure 9 (lines 1890-1902), where we show similar trends on metrics such as return and compute time.

We also believe that you mean ACT and PonderNet as the “less elegant” methods. Note that without the above theoretical results, both ACT and PonderNet still require policies that take walltime as input in RAMDPs—we address this in the discussion on other baselines (please see the response to weakness 5 below). On the other hand, if what you meant is to ignore the RAMDP formulation completely and train with ACT or PonderNet, then the corresponding auxiliary losses will indeed drive the policy to use less computation in general. However, this alternative will not take into account how the current compute expenditure affects downstream rewards.

AuthorsOpenReview ↗

Response (2/2)

Weakness 4: Variable compute only helps under a restricted controller

This is true: variable-compute methods are only helpful under countable state MDPs or when the agent is smaller than the world. However, note that both these settings arise almost everywhere. In traditional machine learning, we have been able to avoid this by restricting attention to smallish problems where we can have over-parameterized models, but with the advent of LLMs, even this is changing. Also recall that in CS, we use variable-compute policies all the time: e.g. sorting function takes longer for bigger inputs. Another example is that of Huffman coding where more frequent inputs have smaller representations. In this paper, our hope is to re-emphasize this computational aspect in RL, thereby helping make progress towards making current RL methods more practical for real-world large-scale problems (also see the big-world hypothesis; references below).

References for the big-world hypothesis:

Weakness 5: Missing related baseline such as ACT/PonderNet

We acknowledge this point. Architectures such as ACT or PonderNet are another way to implement variable compute policies, and can potentially perform better than the methods we adopted in this paper—simply using the discounted return to guide the halting mechanism and policy learning without using auxiliary losses or any regularization to a runtime prior. However, we don’t expect any of the architectures to be uniformly better than other architectures across a wide range of tasks, and as such, when applying RL with variable-compute policies to real-world problems, it would be important to tune the architecture to the problem at hand as well.

Having said that, we want to point out that the focus of this paper is not on particular implementation, rather it is on the exposition of the ideas such as,

  • variable-compute policies can be helpful and result in performance gains over uniform-control policies in different kinds of environments (including, as you pointed out, even reactive environments)
  • formulating the problem of policy computation and separating that from the MDP dynamics, using the RAMDP framework (Section 3),
  • studying some theoretical properties of RAMDPs, such as the necessity (Section 4 and Appendix A) and learnability of variable-compute policies in this formulation (Section 5, and Appendices C and D), and
  • empirically providing proof-of-concept for these ideas (Section 6).

We again thank you for your service. Your review has definitely helped us understand and improve our presentation further. Please reach out if something is still unclear. Additionally, if we were able to answer your concerns satisfactorily, please consider revising your score.

Reviewer_goCzOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes runtime-aware MDP (RAMDP), which takes runtime of a policy into consideration and the longer the runtime, the less the received reward. The paper demonstrates that some standard policy algorithm can fail in this new formulation. The it proposes variable-compute policy that can determine when to stop computation of an action. Finally, the paper conducts experiments to show the learning performance.

Critical strengths
  1. The studied problem is interesting and is important under the context of LLMs and chain-of-thought.
  2. The proposed variable-compute policy is interesting and I think it could be useful.
Critical weaknesses
  1. The theoretical part is somewhat weak. It only characterizes some existence without any learning guarantees. For example, section3 provides some example to explain when the variable-compute policy is useful, but do not give a general property to show that certain class of RAMDP requires a variable-compute policy to be optimal.
  2. The experiments does not show a clear advantage across tasks, especially for the large-scale case.
Questions for authors
  1. Is it possible to find some sufficient conditions on the RAMDP and the computationally realizable policy class under which variable-compute policies achieve a strictly higher optimal value than fixed-runtime policies?
3 comments

We thank you for your constructive feedback, for appreciating the usefulness of this work and its connection with LLMs, and helping us make the paper’s presentation better for the readers! We address the weaknesses you raised in the following.

Weakness 1 and Question 1: Theoretical part is somewhat weak: no learning guarantees nor general property where variable-compute is optimal

We refer the reviewer to the general response regarding “Theoretical results are somewhat weak or trivial” for the detailed response to addressing your concerns.

In short, the appendix did include results for learning, but they were not clearly outlined in the main paper. We have updated the manuscript to provide specific references to address these concerns now. The question regarding general property where variable-compute is optimal is indeed a very important and deep question. The current manuscript does give a partial characterization towards answering this question. Unfortunately, a thorough treatment of this direction is out of the scope of the present work, where we primarily focus on developing the framework of runtime-aware MDPs, which can be helpful for studying variable-compute policies.

Weakness 2: Clear advantage of variable-compute policies across tasks

Thank you for pointing this out. 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.

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.

Thanks for the response and the revision. My main concern about the advantage of this method remain. In particular, the variable-compute agent mostly matches rather than outperforms the best uniform-compute agent which does not support the title’s “perform better and spend less”. I therefore keep my score.

We thank the reviewer for the response. We are happy to, and have changed the title to "Variable-compute policies in runtime-aware reinforcement learning", which is permitted during the rebuttal. If this resolves your concern, please consider updating the score accordingly as we have resolved your other concerns.

Comments on the paper

3 comments
AuthorsOpenReview ↗

General response (1/3)

We would like to thank the reviewers (and the AC) for their detailed reviews and service. All the reviewers gave encouraging comments on the importance of studying variable-computation and the usefulness of pursuing this research direction: the studied problem is interesting (goCz, b18G), important and useful (goCz, HgBW), and sufficiently general (b18G, HgBW). Most of the comments were on clarifying the main objectives of the paper, which we have addressed below (and by updating the manuscript). Other important comments included some weaknesses of the old experimental setup, which we have addressed by running a new set of experiments.

Here we address common comments raised by the reviewers. All updates in the manuscripts are presented in red text.

Why RAMDP over other variants of MDPs (b18G, HgBW)

The core difference between a RAMDP and a semi-MDP is that existing works on semi-MDPs (such as the options framework) generally assume that picking the action duration (or the option) spends uniform compute. Our work explicitly claims that choosing any action (or any option) generally requires variable computation, specifically, with very large state spaces where the policy class is (due to practical constraints) underparameterized. Further, in the options literature, the focus is often on either planning with such (pre-specified) options or on how to discover useful options, and how they help with exploration. In contrast, in RAMDPs, our focus is on studying the necessity (Section 4 and Appendix A) and learnability of variable-compute policies in this formulation (Section 5, and Appendices C and D). In the updated manuscript we have clarified this difference (lines 98-103, lines 155-158).

On the other hand, one can also consider more fine-grained MDPs where one explicitly considers the computational actions, e.g. thought MDPs and meta-reasoning MDPs. The difference here is that, regardless of these formulations, there are fundamental limitations in computing the corresponding optimal actions. While the proposed algorithms and the MDP constructions are interesting, they are specific to the details of the computational model. RAMDPs instead abstract away this level of detail, allowing us to focus purely on the relationship between runtime and decision making, and derive general-purpose algorithms that can be applied to any of these constructions. In the updated manuscript we have clarified this difference (lines 112-118, 162-166).

AuthorsOpenReview ↗

General response (2/3)

Theoretical results are somewhat weak or trivial. And results on learning policies (as opposed to representing policies) is missing. (goCz, HgBW)

On the simplicity of example 3 in Section 4: The main purpose of the example was to show that even in finite-MDPs, variable-compute policies are helpful. This section, while being simple, is still important because one of the important findings of the thought MDP paper (Hanna & Corrado, 2025) was that in finite-MDPs, uniform-compute policies suffice. While this statement is correct, it assumes that implementing a tabular policy is possible for all finite-MDPs (no matter how large they are).

  • This assumption may not hold for very large environments, given constraints on memory size and effectiveness of hashing schemes (both of these are required for the validity of true random access, which in turn supports tabular policies).
  • In particular, if the policy class is constrained, as we did in Example 3, we see that variable-compute policies become necessary.
  • To support this point further, we also added another example in the introduction that constraints the class of policies to decision trees (lines 35-53). This example is useful because the decision tree class is very similar to neural network (NN) architectures (both being finite-sized circuits), and a similar line of reasoning can be used to construct an example showing that variable-compute policies can become helpful if we restrict the type of non-linearity in the NN architecture and work with finite-precision numbers.

Establishing the importance and practicality of using variable-compute policies even in finite MDPs was the main purpose of section 4. We have updated the manuscript to emphasize this (lines 254-259).

In Appendix A, we show that there exist MDPs with a countable state space, where we necessarily require variable-compute policies (see Theorem 10).

  • As an illustration, consider a single-state MDP (bandit environment), where at the beginning of each episode the agent is arbitrarily given an array of natural numbers and it needs to count the number of elements of the array that are prime. If the agent outputs the correct answer it gets a reward of one, otherwise zero. Clearly, the optimal policy will necessarily need to go through each element of the array, making it variable-compute. We can also have an (uncomputable) optimal tabular policy that can just take the state as input and output the correct answer within a single compute step, but such a policy can’t be implemented on a computer. On the other hand, we can also have a sub-optimal policy that takes a constant amount of time for each state, e.g. output a random number at each time. Anyways, the main point here is that there exist MDPs, where under reasonable assumptions (such as the computability of the policy), variable computation is the only way to go.

We have updated the manuscript to include this discussion (lines 259-262)

On learning: Since a finite-state RAMDP contains the walltime, the equivalent MDP no longer remains finite, but becomes countable. As a result, naively applying methods like, say, policy gradient with TD-style critic learning can be prohibitively inefficient. We show that time-independent representations can be as expressive as time-dependent representations (Theorem 4 and Lemma 5). However, even then, in Appendix C we show that planning methods require uncomputable oracles under constrained policy class (Theorem 29). On the other hand, in appendix D we show that it is possible to obtain better sample complexity for estimating Q-functions (Theorem 30) and improved variance reduction for policy gradient (Theorem 34).

Due to space constraints in the main text, we only focus on the foundational results (Theorem 4 and Lemma 5) that are used for the theoretical results in the appendix—we have updated the manuscript to mention the specific theorems and their consequences (line 310, lines 341-343).

AuthorsOpenReview ↗

General Response (3/3)

Experimental results are limited to puzzle tasks only (as opposed to reactive or stochastic tasks such as Atari) and the variable-compute policies do not seem advantageous across all tasks (goCz, b18G, HgBW)

We acknowledge this limitation of the original manuscript and agree that including reactive and stochastic environments, even if the environment waits while the policy computes, is a worthwhile experiment. Based on this feedback, we have conducted experiments on MinAtar (miniaturized version of the Atari benchmark; Young and Tian, 2019). Here, we observed that variable-compute policies were competitive to uniform compute policies (except for Breakout).

The following table shows the discounted return across different uniform-compute agents and variable-compute agents. Each cell shows the mean +/- standard error over five seeds. (We also included the learning curve in Figure 4, lines 432-450 in the updated manuscript.)

Envc=1c=1c=2c=2c=3c=3c=4c=4c=5c=5c∈[1,5]c\in[1,5]
Asterix54.23 ± 1.7056.06 ± 1.6956.76 ± 0.8355.15 ± 2.0755.90 ± 0.8855.71 ± 1.56
Breakout86.41 ± 2.4972.05 ± 9.0067.60 ± 9.1979.51 ± 6.8271.15 ± 8.4661.22 ± 7.32
Freeway57.98 ± 0.6859.10 ± 0.9860.10 ± 0.3660.57 ± 0.5760.19 ± 0.1560.19 ± 0.56
Seaquest56.62 ± 2.5361.57 ± 1.7767.95 ± 3.1664.83 ± 4.7063.73 ± 2.9371.95 ± 4.19
Space Invaders143.92 ± 9.55154.07 ± 4.21155.62 ± 4.49143.80 ± 3.38156.20 ± 4.18158.55 ± 5.62

On improving the clarity of the experimental setup and the conclusions from the empirical results (goCZ, b19G, HgBW)

We acknowledge that we could have better clarified the goal of the experiments and how we conducted them. First, our goal is not to say that variable-compute policies are always advantageous, but to show that variable-compute policies can be advantageous. Indeed, if the uniform-compute policy that only spends one compute step is optimal, then no other policy can do better. Secondly, in the process of trying to better clarify our experiments, we found that there could have been some confounders in the experiments on the sliding-puzzle environment. We explain this in the next paragraph.

In the updated manuscript, for all puzzle environments we now split the training instances (i.e. episodes where the start-states come from one particular set of states, and on which the policy is trained) and the evaluation instances (i.e. episodes where the start-states come from a different set of states, and where the trained policy is only evaluated) differently. We performed this split based on the number of steps required to solve that puzzle, with training instances containing “shorter” problems. Such a split also allows us to study the generalization behavior of the learned policies, and our experimental results show that variable-compute policies show promising behavior for generalization capabilities as well.

Doing so resulted in cleaner graphs. For instance, in the updated manuscript, Figure 3 (lines 392-411) shows how for both lightsout and sliding-puzzle environments, variable-compute policies (black color) achieve a similar performance (success rate of solving the puzzle) as uniform-compute policies while using less computation. For Sokoban, results are slightly less cleaner, but variable-compute policies (black color) are still competitive, in terms of success rate, to uniform-compute policies.

Also, based on the feedback from reviewer HgBW, we removed the negative rewards from the Sokoban environment and re-ran the experiments. We have updated the experimental setup accordingly (lines 365-367 of the updated manuscript).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.