Breaking the Performance Ceiling in Reinforcement Learning requires Inference Strategies

We thank the reviewer for their feedback and for highlighting the strengths of our paper.

> W1: The algorithmic novelty is rather limited, as it is simply applying a now widely-known principle from works on LLM inference-time compute.

Our main message is that practitioners often miss an opportunity to achieve significant performance improvements. Hence, this message is made stronger by the fact that these methods are already accessible, and often ignored despite having been published in top-tier conferences several years ago: online fine-tuning [5] at ICLR 2017, SGBS [6] at Neurips 2022, and COMPASS [3] at Neurips 2023.

Methods presented in the paper are not all applicable to LLMs (e.g. online fine-tuning is intractable for LLMs) and are more closely related to the RL for CO literature. Even though the algorithmic contribution is not the core contribution of our paper, it is worth mentioning that we are the first to generalise COMPASS to the multi-agent setting.

In summary, we agree with the reviewer that our algorithmic novelty is rather limited; however, we emphasize that this aspect reinforces the significance of our main message.

[3] Combinatorial Optimization with Policy Adaptation using Latent Space Search, Neurips 2023
[5] Neural Combinatorial Optimization with Reinforcement Learning, ICLR 2017
[6] Simulation-guided Beam Search for Neural Combinatorial Optimization, Neurips 2022

> Q1: Please provide more experiment details and/or report error bars for Figure 4.

We thank the reviewer for pointing this out. Please see the table below where we give the mean and 95% bootstrap confidence intervals. The 20M timestep values are aggregated over 10 independent runs and computed directly from the benchmarking data provided along with the Sable [2] paper, for the policy trained to convergence and for COMPASS, we give the results aggregated over 128 independent runs.

To avoid overcrowding Figure 4 in the main paper, we propose to include these detailed confidence intervals and error bars in a dedicated table and an extended version of the plot, both placed in the Appendix. We will clearly reference this supplementary information in the caption of Figure 4.

[2] Sable: a Performant, Efficient and Scalable Sequence Model for MARL, ICML 2025

Values and error bars of results reported in Figure 4:

> Q2: Since the experiments were only done on multi-agent domains, perhaps the title is a bit of an overly stated claim.

We agree with the reviewer that the inclusion of single-agent experiments is helpful to substantiate our title. In the following reply, we discuss published results on single-agent tasks, we provide new empirical evidence on a complex single-agent RL task (Craftax), and we reaffirm why our current benchmark is enough to sufficiently support our main message.

First, we can refer to the experimental results reported in the seminal works that introduced the inference strategies used in our paper [3, 5, 6]. All of these evaluate on single-agent tasks (TSP, CVRP, JSSP, Knapsack, FFSP) and show that inference strategies bring statistically significant improvements over zero-shot performance. However, we recall the limitations we have identified on these experimental results (Section 2, lines 103 to 109): the limited breadth of the time/compute settings, methods’ reliance on problem-specific tricks and saturated benchmarks where zero-shot performance is already very high.

We however provide additional results to support our core message in the single-agent case within the time allowed for the rebuttal. Specifically, we trained a Sable base policy on Craftax [7] (ICML 2024) and matched the current state-of-the-art performance reported on the Craftax-1B leaderboard, which is 18.3% of the maximum score. We then ran a 30-second inference-time search with the simplest inference strategy (stochastic sampling). The results are reported in the table below. Strikingly, and similar to our main results, using only a 30-second inference-time search yields a 37% performance gain, reaching 25.8% of the maximum score. To further put this into context, this performance boost is of the same magnitude as that of the last 300 million steps of training the base policy.

We are happy to add these discussions and the additional results on Craftax in a new section in the Appendix of the revised manuscript.

We nevertheless believe that our current benchmark and experimental protocol provides enough evidence in the main paper to support our message because: (i) it is peer-reviewed [1] and recognised in the RL community (accepted at Neurips 2021, widely cited), (ii) even the current SOTA method Sable [2] (ICML 2025) is far from optimal on a third of this benchmark, hence providing a 17-task suite to test our hypothesis, (iii) its formulation as a Dec-POMDPs makes it generic and closer to real-world RL settings.

We appreciate the reviewer raising this important point and hope the additional single-agent results provided here demonstrate the generality of our main message.

[1] Benchmarking Multi-Agent Deep Reinforcement Learning Algorithms in Cooperative Tasks, Neurips 2021
[2] Sable: a Performant, Efficient and Scalable Sequence Model for MARL, ICML 2025
[3] Combinatorial Optimization with Policy Adaptation using Latent Space Search, Neurips 2023
[5] Neural Combinatorial Optimization with Reinforcement Learning, ICLR 2017
[6] Simulation-guided Beam Search for Neural Combinatorial Optimization, Neurips 2022
[7] Craftax: A Lightning-Fast Benchmark for Open-Ended Reinforcement Learning, ICML 2024

We are grateful for the reviewer's feedback, especially their observation regarding the potential discussions our work could spark within the RL community. Below, we address the choice of benchmark, the connection to meta-RL and offline RL, and provide real-world examples, alongside proposed revisions for our manuscript.

> W1: Limitation to the MARL case. It would have been interesting to see for at least some single-agent case how inference strategies perform.

We agree that discussing the single-agent case is valuable. In the following reply, we discuss published results on single-agent tasks, we provide new empirical evidence on a complex single-agent RL task (Craftax), and we reaffirm why our current benchmark is enough to sufficiently support our main message.

First, we can refer to the experimental results reported in the seminal works that introduced the inference strategies used in our paper [3, 5, 6]. All of these evaluate on single-agent tasks (TSP, CVRP, JSSP, Knapsack, FFSP) and show that inference strategies bring statistically significant improvements over zero-shot performance. However, we recall the limitations we have identified on these experimental results (Section 2, lines 103 to 109): the limited breadth of the time/compute settings, methods’ reliance on problem-specific tricks and saturated benchmarks where zero-shot performance is already very high.

We however provide additional results to support our core message in the single-agent case within the time allowed for the rebuttal. Specifically, we trained a Sable base policy on Craftax [7] (ICML 2024) and matched the current state-of-the-art performance reported on the Craftax-1B leaderboard, which is 18.3% of the maximum score. We then ran a 30-second inference-time search with the simplest inference strategy (stochastic sampling). The results are reported in the table below. Strikingly, and similar to our main results, using only a 30-second inference-time search yields a 37% performance gain, reaching 25.8% of the maximum score. To further put this into context, this performance boost is of the same magnitude as that of the last 300 million steps of training the base policy.

We are happy to add these discussions and the additional results on Craftax in a new section in the Appendix of the revised manuscript.

We nevertheless believe that our current benchmark and experimental protocol provides enough evidence in the main paper to support our message because: (i) it is peer-reviewed [1] and recognised in the RL community (accepted at Neurips 2021, widely cited), (ii) even the current SOTA method Sable [2] (ICML 2025) is far from optimal on a third of this benchmark, hence providing a 17-task suite to test our hypothesis, (iii) its formulation as a Dec-POMDPs makes it generic and closer to real-world RL settings.

We appreciate the opportunity to engage with this thoughtful discussion and hope that our response and additional results provide valuable insights.

[1] Benchmarking Multi-Agent Deep Reinforcement Learning Algorithms in Cooperative Tasks, Neurips 2021
[2] Sable: a Performant, Efficient and Scalable Sequence Model for MARL, ICML 2025
[3] Combinatorial Optimization with Policy Adaptation using Latent Space Search, Neurips 2023
[5] Neural Combinatorial Optimization with Reinforcement Learning, ICLR 2017
[6] Simulation-guided Beam Search for Neural Combinatorial Optimization, Neurips 2022
[7] Craftax: A Lightning-Fast Benchmark for Open-Ended Reinforcement Learning, ICML 2024

> Q1: Relation to few-shot meta-RL and fine-tuning in offline RL.

We acknowledge that relating meta-RL and offline-to-online RL to inference strategies is an interesting addition to the paper, and we are happy to add these to our related work (Section 2).

Inference strategies, just like meta-RL and offline-to-online RL, benefit from policy adaptation methods in order to produce better solutions. Consequently, methods developed in these fields can benefit the others. Interestingly, COMPASS shares similar concepts with VariBAD [8], a seminal work in meta RL: both condition a policy on a latent space and search this space to adapt. Other inference strategies from the literature have close links to meta learning. For instance, MEMENTO [9] shares similarities with RL2 [10], using a memory to search (respectively to adapt). And DIMES [11] is an inference strategy which explicitly does meta RL (following MAML’s methodology [12]). We do not compare to DIMES because it is highly domain-specific (only applicable to graphs, e.g. TSP and MIS). While we are not aware of inference strategies directly inspired by the offline-to-online RL literature, methods such as Cal-QL [13] and PA-RL [14] introduce adaptation mechanisms that would likely be beneficial during inference.

We will also recall some fundamental distinctions between these fields. In particular, inference strategies care about (i) the solutions found rather than the policy obtained, (ii) the maximum performance rather than average performance, and (iii) treat single instances at a time, whereas most meta-RL and offline-to-online RL methods adapt from a distribution to another distribution.

[8] VARIBAD: A Very Good Method for Bayes-Adaptive Deep RL via Meta-Learning, ICLR 2020
[9] Memory-Enhanced Neural Solvers for Efficient Adaptation in Combinatorial Optimization, arxiv (2024)
[10] RL^2: Fast Reinforcement Learning via Slow Reinforcement Learning, arxiv (2016, cited 1000+)
[11] DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems. Neurips 2022
[12] Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks, ICML 2017
[13] Cal-QL: Calibrated Offline RL Pre-Training for Efficient Online Fine-Tuning, Neurips 2023
[14] Policy Agnostic RL: Offline RL and Online RL Fine-Tuning of Any Class and Backbone, ICLR 2025

> Q2: Would it be possible to use short episode stubs?

When per-timestep rewards are accessible, it is indeed possible to use short episode stubs instead of entire episode rollouts. We stayed as close as possible to the existing methods published in the literature; hence, we only ever used full episode information, but we do not see any restrictions to extend these methods to use smaller episode stubs since the benchmarks we are using provide per-timestep rewards.

> Q3: Can you provide real-world examples in which a user might permit inference time adaptation?

Applying RL in real-world applications is a key driver of our research. Here are three such real-world cases where we have first-hand experience: in all these, the user would allow for a time budget, and a proxy of the solution’s quality is accessible to inform the search:

• Printed Circuit Board Routing. The user submits the specification of a PCB board they want to route. This task can take up to several days/weeks, even for an expert, depending on the complexity of the board. Therefore, users are typically completely satisfied with allowing an AI model to take at least a few minutes or even hours for search to obtain a better solution (routed board). Additionally, the user will find it beneficial to leave more time and to grant more computation in order to improve the board further, which could then be easier to manufacture or reduce its production cost.
• Bin Packing. When a logistics company wants to load containers with objects that need to be shipped overseas. The operators can typically have a few hours or days when planning which objects need to be transported, and can hence allow inference-time search. Here as well, the energy and money gains from having a better object dispatching (thus fewer containers to ship for the same amount of objects) will always justify a few hours of search (or the allowance of more computing spend).
• Train scheduling: designing train schedules to meet some demand forecast, while proposing a feasible schedule (e.g., no collisions between trains). This only happens once or twice a year, and takes months, hence no need to rely on a single rollout of the trained policy, and an inference-time search can be conducted over several days.

We appreciate the reviewer's suggestion; these examples will be added to a new appendix section to illustrate the link of this work with real-world applications.

We thank the reviewer for their positive feedback and comments. We provide additional insight on the benchmark used and explanations concerning inference strategies, which we will include in the revised manuscript.

> W1: it feels like the benchmark environments are already somewhat saturated.

Our benchmark actually focuses on tasks from the literature that are still far from being saturated. We chose tasks from the benchmark introduced in [1] (Neurips 2021) where the most recent state-of-the-art method Sable [2] (ICML 2025) reports an average performance below 50% normalised return (see grey crosses on Figure 4 of our main paper). To isolate the effect of a potential lack of training, we re-train Sable until convergence on these tasks and we observe that the zero-shot performance is plateauing under 70% (see orange crosses on Figure 4), and reaching only 5% on the hardest task (con-15x15x23a), hence demonstrating that the zero-shot performance is reaching a ceiling on these tasks.

We discuss this aspect of the benchmark in paragraph “Tasks” (Section 4, line 233) and paragraph “Training base policies” (Section 4, line 263/264). We can further clarify by updating the sentence on line 263/264: “... the converged policy stays below 70% normalised performance, demonstrating that the benchmark is still far from saturated”.

[1] Benchmarking Multi-Agent Deep Reinforcement Learning Algorithms in Cooperative Tasks, Neurips 2021
[2] Sable: a Performant, Efficient and Scalable Sequence Model for MARL, ICML 2025

> Q1: How do inference strategies work? Do the models consider multiple actions before deciding on a single action at each time step?

Section 3 defines an inference strategy as a function that uses the base policy and any additional inference-time search, adaptation, storage, or optimisation methods under the time and compute budget to produce the best possible solution to the problem instance (lines 169 to 171). Inference strategies represent a broad concept, encompassing various approaches. The effectiveness of these strategies is contingent on specific contextual factors, such as the size of the pre-trained policy, the problem's inherent structure, the duration of the episode, the nature of the reward function, and the available time and computational budget.

Concerning the action selection, all four inference strategies studied in the paper use a pre-trained policy which outputs an action distribution at each time step. The next action is always selected by sampling from this action distribution. In other words, any (allowed) action can be selected, with a probability which corresponds to the logits given by the pre-trained policy to this action.

These inference strategies differ in the way they incorporate outcomes of previous attempts to impact the way future actions will be sampled. Online fine-tuning uses the past attempts to derive a policy gradient and update the policy’s parameters. COMPASS uses the past attempts to update the distribution used to sample the latent vectors which condition the policy. SGBS (tree search) re-starts from the partial solutions which led to the best performance so far (whereas other methods always re-sample solutions from scratch). In contrast, stochastic sampling does not take past attempts into account.

We will add these details at the beginning of Section 3.2 in order to better link the methods under study with the definitions introduced in Section 3.1. We thank the reviewer for their comments which will help clarify the paper.

We thank the reviewer for highlighting the contributions of our work and for their thoughtful comments, which we address in the responses below. We will update the manuscript to clarify the points raised in the review.

> Q1: Explain details of how the specialized policy in COMPASS is trained.

At each training step, a batch of latent vectors is sampled from the latent space, using a fixed random uniform distribution. The latent-conditioned policy is evaluated on the same problem instance, with each of the sampled latent vectors. The episode returns obtained for each latent vector are compared, and only the best trajectory is kept to train on. In line with the original implementation of COMPASS [3] (Neurips 2023), we use REINFORCE to estimate the policy gradient, using a batch of instances evaluated in parallel.

Only the best latent vector in the batch is used to train the policy, thus creating a specialisation within the latent space. In doing so, different areas of the latent space learn to specialise for different subdistributions of the training instances.

This training process is explained in Appendix E.2 (lines 945 to 976), which we omitted to refer to in the main paper. We will revise the manuscript to add this reference at the end of the paragraph “Diversity-based approach” (line 204, Section 3.2).

We can also extend this paragraph if the reviewer(s) feel this would be useful, or use the additional page allowed for the camera-ready version to include it directly in the main paper.

[3] Combinatorial Optimization with Policy Adaptation using Latent Space Search, Neurips 2023

> Q2: Comparison of the model size.

Creating a COMPASS checkpoint from a pre-trained base policy does indeed require adding new parameters to process the latent vectors (line 953, App. E.2), hence increasing the model size. However, this increase is small, never exceeding 2% of the total base policy model size.

We report the parameter count for all base policy checkpoints and all corresponding COMPASS checkpoints in the table below. We observe that (i) for IPPO and MAPPO, the increase in model size stays below 1.6%, and (ii) for Sable, it typically adds 0.5% to the total parameter count. Consequently, this model size increase has a minor impact on the memory and computational footprint of the method, which is confirmed by our study of the attempts achieved over time (reported in Appendix G).

We thank the reviewer for highlighting this aspect of COMPASS, which was not yet discussed in the paper. We will add this table to our appendix, along with a paragraph to comment on these values.

> Q3: Explain the reason behind COMPASS being better.

We highlight three main reasons why COMPASS is better.

First, COMPASS trains a “multiple attempts” objective, unlike other methods, which are training for “single attempt” performance. Thus, COMPASS’s training objective anticipates that what matters is the maximum performance over multiple attempts, rather than the average performance over these attempts.

Second, COMPASS creates a dense space of diverse and specialised policies, hence creating a strong exploration capacity. While most other methods rely on the entropy of the action distribution to explore (i.e. sampling stochastically from the pre-trained policy), COMPASS can use the wide diversity encoded in its latent space to build much more diverse policies.

Finally, the Covariance Matrix Adaptation mechanism (CMA-ES [4]) used by COMPASS at inference time enables it to navigate the latent space and identify the most adapted (suitable) latent for the problem instance at hand. Using a CMA-ES search in a 16-dimensional space is more efficient and less prone to getting stuck in local optima compared to using gradient descent in the entire policy parameter space (i.e. online fine-tuning).

Some of these elements are discussed in a paragraph in Section 4.3 to interpret the scaling capacity of COMPASS. We will add a section in the Appendix to discuss the elements that were not yet mentioned.

[4] Completely derandomized self-adaptation in evolution strategies, Evolutionary Computation 2001

The following tables present the parameters count for the checkpoints used in our experiments.

MAPPO:

IPPO:

Sable:

> If the distribution of "multiple attempts" is the same as "single attempt", why does it perform better?

A policy trained for “single attempt” optimises the average performance over attempts. At inference time, such a policy tends to produce many good solutions but rarely an excellent one.

In contrast, a policy trained for “multiple attempts” optimises the maximum performance over a batch of attempts. While its average solution quality may be lower, it has a higher probability of producing one excellent solution. This makes it inherently better suited for inference-time search where multiple attempts are allowed.

We will clarify this point in the updated manuscript.

> It will be good to explain more on how the "z" selection is diversified during training.

The latent space is a fixed prior distribution, it is not explicitly diversified during training. Instead, the conditioned policy is trained to process samples from this prior in a way that promotes diversity in the generated solutions. Our reply to "Q1: Explain details of how the specialized policy in COMPASS is trained” describes the training mechanism that achieves this effect, and we are happy to elaborate further if any aspect remains unclear.

> Could the authors explain more on the contribution compared to "COMPASS" original paper?

Our main contribution is to show that many practitioners miss an opportunity to achieve significant performance gains by using inference-time search. We demonstrate this on a benchmark that is:

• Non-saturated: tasks mostly below 60% zero-shot performance (see Figure 4)
• Broad: covering 17 tasks without requiring domain-specific tricks

This contrasts with COMPASS, since most tasks considered were already getting over 95% zero-shot performance, and relied on domain-specific tricks (e.g., using input augmentations based on symmetries in the problem formulation). These limitations are discussed in section Related Work (lines 103 to 109).

We also contribute the largest study to date of inference strategies for complex RL, evaluating methods across a wide range of time and compute budgets (Section 4.2, Figure 6), whereas prior work (including COMPASS) typically focused on a narrow, arbitrary budget. Finally, even though the algorithmic contribution is not the core contribution of our paper, it is worth mentioning that we are the first to generalise COMPASS to the multi-agent setting.

We hope these clarifications strengthen the reviewer’s understanding of our work, and we will incorporate them to refine the manuscript. We are happy to elaborate further if needed.

I'm wondering if the distribution of "multiple attempts" are same as "single attempt", why it performs better?

"COMPASS creates a dense space of diverse and specialised policies, hence creating a strong exploration capacity. While most other methods rely on the entropy of the action distribution to explore", I see that the "COMPASS" is from a reference without a clear explanation of how "the latent vector z" which the policies is conditioned on. It will be good to explain more on how the "z" selection is diversified during training although it is from another paper.

Could the authors explain more on the contribution compared to "COMPASS" original paper?