On Computation and Reinforcement Learning

• URL: http://arxiv.org/abs/2602.05999v1
• Date: Thu, 05 Feb 2026 18:45:57 GMT
• Title: On Computation and Reinforcement Learning
• Authors: Raj Ghugare, Michał Bortkiewicz, Alicja Ziarko, Benjamin Eysenbach,
• Abstract summary: We show that policies which use more compute can solve problems and generalize to longer-horizon tasks.<n>We propose a minimal architecture that can use a variable amount of compute.
• Score: 27.084991943054657
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Accelerating RL for LLM Reasoning with Optimal Advantage Regression [52.0792918455501]
  We propose a novel two-stage policy optimization framework that directly approximates the optimal advantage function.<n>$A$*-PO achieves competitive performance across a wide range of mathematical reasoning benchmarks.<n>It reduces training time by up to 2$times$ and peak memory usage by over 30% compared to PPO, GRPO, and REBEL.
  arXiv  Detail & Related papers  (2025-05-27T03:58:50Z)
• TD-M(PC)$^2$: Improving Temporal Difference MPC Through Policy Constraint [11.347808936693152]
  Model-based reinforcement learning algorithms combine model-based planning and learned value/policy prior.<n>Existing methods that rely on standard SAC-style policy iteration for value learning often result in emphpersistent value overestimation.<n>We propose a policy regularization term reducing out-of-distribution (OOD) queries, thereby improving value learning.
  arXiv  Detail & Related papers  (2025-02-05T19:08:42Z)
• Multilinear Tensor Low-Rank Approximation for Policy-Gradient Methods in Reinforcement Learning [27.868175900131313]
  Reinforcement learning (RL) aims to estimate the action to take given a (time-varying) state.<n>This paper postulates multi-linear mappings to efficiently estimate the parameters of the RL policy.<n>We leverage the PARAFAC decomposition to design tensor low-rank policies.
  arXiv  Detail & Related papers  (2025-01-08T23:22:08Z)
• Policy Agnostic RL: Offline RL and Online RL Fine-Tuning of Any Class and Backbone [72.17534881026995]
  We develop an offline and online fine-tuning approach called policy-agnostic RL (PA-RL)<n>We show the first result that successfully fine-tunes OpenVLA, a 7B generalist robot policy, autonomously with Cal-QL, an online RL fine-tuning algorithm.
  arXiv  Detail & Related papers  (2024-12-09T17:28:03Z)
• Jump-Start Reinforcement Learning [68.82380421479675]
  We present a meta algorithm that can use offline data, demonstrations, or a pre-existing policy to initialize an RL policy. In particular, we propose Jump-Start Reinforcement Learning (JSRL), an algorithm that employs two policies to solve tasks. We show via experiments that JSRL is able to significantly outperform existing imitation and reinforcement learning algorithms.
  arXiv  Detail & Related papers  (2022-04-05T17:25:22Z)
• Learning Large Neighborhood Search Policy for Integer Programming [14.089039170072084]
  We propose a deep reinforcement learning (RL) method to learn large neighborhood search (LNS) policy for integer programming (IP) We represent all subsets by factorizing them into binary decisions on each variable. We then design a neural network to learn policies for each variable in parallel, trained by a customized actor-critic algorithm.
  arXiv  Detail & Related papers  (2021-11-01T09:10:49Z)
• Improving Generalization of Deep Reinforcement Learning-based TSP Solvers [19.29028564568974]
  We propose a novel approach named MAGIC that includes a deep learning architecture and a DRL training method. Our architecture, which integrates a multilayer perceptron, a graph neural network, and an attention model, defines a policy that sequentially generates a traveling salesman solution. Our training method includes several innovations: (1) we interleave DRL policy updates with local search (using a new local search technique), (2) we use a novel simple baseline, and (3) we apply gradient learning.
  arXiv  Detail & Related papers  (2021-10-06T15:16:19Z)
• Deep Reinforcement Learning with Adjustments [10.244120641608447]
  We propose a new Q-learning algorithm for continuous action space, which can bridge the control and RL algorithms. Our method can learn complex policies to achieve long-term goals and at the same time it can be easily adjusted to address short-term requirements.
  arXiv  Detail & Related papers  (2021-09-28T03:35:09Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  In this paper, we establish an efficient online sub-sampling framework that measures the information gain of data points collected by an RL algorithm. For a value-based method with complexity-bounded function class, we show that the policy only needs to be updated for $proptooperatornamepolylog(K)$ times. In contrast to existing approaches that update the policy for at least $Omega(K)$ times, our approach drastically reduces the number of optimization calls in solving for a policy.
  arXiv  Detail & Related papers  (2021-06-14T07:36:25Z)
• RL-DARTS: Differentiable Architecture Search for Reinforcement Learning [62.95469460505922]
  We introduce RL-DARTS, one of the first applications of Differentiable Architecture Search (DARTS) in reinforcement learning (RL) By replacing the image encoder with a DARTS supernet, our search method is sample-efficient, requires minimal extra compute resources, and is also compatible with off-policy and on-policy RL algorithms, needing only minor changes in preexisting code. We show that the supernet gradually learns better cells, leading to alternative architectures which can be highly competitive against manually designed policies, but also verify previous design choices for RL policies.
  arXiv  Detail & Related papers  (2021-06-04T03:08:43Z)
• Policy Information Capacity: Information-Theoretic Measure for Task Complexity in Deep Reinforcement Learning [83.66080019570461]
  We propose two environment-agnostic, algorithm-agnostic quantitative metrics for task difficulty. We show that these metrics have higher correlations with normalized task solvability scores than a variety of alternatives. These metrics can also be used for fast and compute-efficient optimizations of key design parameters.
  arXiv  Detail & Related papers  (2021-03-23T17:49:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.