Authors: Adrian Orenstein, Jessica Jiajing Chen, Gwyneth Anne Delos Santos, Bayley Sapara, Michael Bowling
Organizations: Department of Computing Science, University of Alberta, Canada · Alberta Machine Intelligence Institute (Amii) · Department of Computer Science, University of Toronto, Canada · CIFAR AI Chair
While reinforcement learning agents can achieve superhuman performance in many complex tasks, they typically do not become more computationally efficient as they improve. In contrast, humans gradually require less cognitive effort as they become more proficient at a task. If agents could reason about their compute as they learn, could they similarly reduce their computation footprint? If they could, we could have more energy efficient agents or free up compute cycles for other processes like planning. In this paper, we experiment with showing agents the cost of their computation and giving them the ability to control when they use compute. We conduct our experiments on the Arcade Learning Environment, and our results demonstrate that with the same training compute budget, agents that reason about their compute perform better on 75% of games. Furthermore, these agents use three times less compute on average. We analyze individual games and show where agents gain these efficiencies. An interactive version of this paper is available at https://adrianorenstein.com/paper/toward-compute.
Figures & tables
Figure 1: Improvement of Compute DQN over DQN in human normalized score (HNS) across 46 Atari games. Compute DQN achieves higher HNS in 75% of games. Amidar shows the largest gain of 487%, while the largest loss is 30% below DQN.
Figure 2: Compute DQN learns game-specific decision rates across the Arcade suite. Each green dot shows the average decisions per second for a single game, measured over 10 independently trained agents. The dashed green line indicates the suite-wide mean of 3.6 Hz. For comparison, Compute DQN uses 3.4 times less compute than DQN, which acts at a fixed 12 Hz (red dashed line). These results demonstrate that Compute DQN can adapt its compute use per game while maintaining performance.
Figure 3: Population dynamics of learning: each point is a moment in time during training, reported across 10 seeds per game. Color encodes training progress.
Figure 4: The decision rate within a trajectory differs by game. Pong and Asterix are uni modal, whereas Breakout is bimodal.
Figure 5: Exponentially decayed average of decision rate for Compute DQN on segments of an episode in Pong. Coloured regions indicate when the opponent has just hit the ball , the ball is approaching the player and dotted line indicates when the ball is hit , the player has just hit the ball , and the ball is heading toward the opponent . There are typically rises in decision rate in the red region in anticipation of the ball reaching the player’s paddle.
Figure 6: A sequence of observations (top) with an associated graph of the exponentially decayed average of decision rate at that moment (bottom) for Compute DQN in Breakout. As the game progresses the decision rate increases considerably, in correlation with the ball speeding up as blocks are cleared and a “breakout” occurs. The final image shows an example decision rate dropping while the ball is behind the wall of blocks.
Figure 7: A sequence of observations (top) with an associated graph of the exponentially decayed average of decision rate at that moment (bottom) for Compute DQN in Asterix. The decision rate grows as the waves get faster and have more collectibles. In the first two images, the agent has just finished collecting the objects in a wave, resulting in a spike in decisions followed by a quick decrease awaiting the next wave. The remaining images repeat this structure with very high decision rates as the number and speed of objects rises with dips between waves.
Figure 8: Varying the compute cost, c , changes the learned decision rate and performance. Higher costs yield fewer decisions per-second; low costs increase the decision rate. Each game shows a performance-compute frontier, showing that agents adapt to their cost parameter.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 9: We present the human normalized score to validate that (i) DQN and Compute DQN on average perform better than a human (above 100%), and (ii) the performance loss from Compute DQN (seen on the right-hand side) is marginal relative to the performance benefit (seen on the left).
Environment
Decisions (M)
Updates (M)
Emulator Steps (M)
Alien
40
10
1030
Amidar
40
10
806
Assault
40
10
590
Asterix
40
10
571
Atlantis
40
10
822
BankHeist
40
10
592
Appendix
Table 1: Compute DQN is trained with the same number of forward passes, decisions, and updates as DQN (40M decisions, 10M updates). However, as Compute DQN skips additional frames to reduce its compute cost, the emulator steps more for an agent to be more efficient.
Figure 10: Improvement of Compute DQN over DQN (at 4 Hz) in human normalized score (HNS) across 44 Atari games. Compute DQN achieves higher HNS in 61% of games. StarGunner shows the largest gain of 349%, while the largest loss of 183% below DQN.
Figure 11: We present the human normalized score to validate that (i) DQN (4 Hz) and Compute DQN on average perform better than a human (above 100%). The performance gains for StarGunner and Breakout (both left), and the performance loss on Centipede are large (right). On average, we see that giving agents control over their compute still results in a performance and efficiency improvement averaged across the suite.
Figure 12: Improvement of Compute Rainbow over Rainbow.
Figure 13: Performance of Compute Rainbow and Rainbow.
Figure 14: Compute cost of Compute Rainbow and Rainbow.
Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
We study how to allocate inference-time compute for competitive programming under fixed budgets. Evaluating 216 Codeforces problems across Divisions 1-3, we compare agent-based reasoning with repeated independent sampling (k-shot) as a function of both cost and number of model calls. Across models and difficulty levels, k-shot consistently achieves a better accuracy-cost and accuracy-query tradeoff. This gap persists despite prompt caching in agent frameworks, indicating lower per-call effectiveness. Our results show that, for self-contained algorithmic tasks, independent exploration can outperform deeper agentic reasoning under realistic resource constraints. We also provide a budget-allocation analysis when the inference budget is fixed, and prove that a cost-optimal solver minimizes the principled metric log failure likelihood per dollar.
Advances in inference methods have enabled language models to improve their predictions without additional training. These methods often prioritize raw performance over cost-effective compute usage. However, computational efficiency is key for real-world applications with resource constraints. We provide a systematic analysis of the inference scaling strategies self-consistency, self-refinement, multi-agent debate, and mixture-of-agents, to study their computational performance tradeoffs. We evaluate methods on two reasoning benchmarks (MMLU-Pro, BBH) and include extensive parameter configurations (e.g., scaling the number of parallel predictions, agents, and debate rounds) across different model sizes. Across 34 configurations and over 100 evaluations, we compute the Pareto-optimal front to select methods that achieve the best accuracy with the lowest computational budget. Notably, inference scaling improves accuracy by up to +7.1% points over chain-of-thought at the highest evaluated budgets (20x the CoT compute budget) on MMLU-Pro. With an equal computing budget, debate and mixture-of-agents outperform self-consistency by 1.3% and 2.7% points, respectively. While self-consistency saturates earlier, multi-agent gains persist, particularly on more complicated tasks. We identify a simple multi-agent design guideline: mixture-of-agents is most efficient when the number of parallel generations exceeds the number of sequential aggregations.
Florian Valentin Wunderlich, Lars Benedikt Kaesberg, Jan Philip Wahle +2
How does the amount of compute available to a reinforcement learning (RL) policy affect its learning? Can policies using a fixed amount of parameters, still benefit from additional compute? The standard RL framework does not provide a language to answer these questions formally. Empirically, deep RL policies are often parameterized as neural networks with static architectures, conflating the amount of compute and the number of parameters. In this paper, we formalize compute bounded policies and prove that policies which use more compute can solve problems and generalize to longer-horizon tasks that are outside the scope of policies with less compute. Building on prior work in algorithmic learning and model-free planning, we propose a minimal architecture that can use a variable amount of compute. Our experiments complement our theory. On a set 31 different tasks spanning online and offline RL, we show that (1) this architecture achieves stronger performance simply by using more compute, and (2) stronger generalization on longer-horizon test tasks compared to standard feedforward networks or deep residual network using up to 5 times more parameters.
Raj Ghugare, Michał Bortkiewicz, Alicja Ziarko +1
Department of Computer Science, Princeton University · Warsaw University of Technology · University of Warsaw +2