RLP: A reinforcement learning benchmark for neural algorithmic reasoning

We thank the reviewer for their effort on reviewing our work. We address their concerns in the following.

While the benchmark is proposed to assess the logical reasoning capabilities of RL agents, no serious attempt is made to truly assess these capabilities, nor to evaluate specific agents which may possess such capabilities (see below). It is disappointing that the authors discuss the lack of such capabilities in RL agents in the introduction, but they do not conclude to the need of designing RL agents specifically endowed with such capabilities. They just discuss the way to increase the performance of standard RL agents that do not have such capabilities represented explicitly.

For each puzzle, we have now included an upper bound of steps required to solve an episode for an optimal policy. Further, we include two new algorithms in our experiments, DreamerV3 and MuZero. In our results, we show that DreamerV3 outperforms the other algorithms, but still only achieves optimal performance for a limited number of puzzles in the easiest difficulty setting. Furthermore, DreamerV3 is also not able to achieve good performance in the easiest human-level difficulty setting.

We agree that RL agents would profit from extending their capabilities correspondingly. For this reason we have extended the discussion and conclusion section in the revised manuscript accordingly.

Could you categorize the various puzzles in terms of the logical reasoning capabilities they require? Could you then evaluate RL algorithms in terms of displaying such capabilities or not?

We have chosen to categorize the puzzles into numbers of steps required to solve them. We believe this may be a valid proxy for the complexity of a logical puzzle. These values can be found in the appendix of the revised manuscript.

In the first paragraph of the related work, you list a few RL agents that seem to be endowed with some logical reasoning capabilities. Is the source code of some of these agents available? Could you evaluate some of them on your benchmark?

While unfortunately the source code of the mentioned algorithms was not available to us, we now include results for the algorithms DreamerV3 and MuZero.

Eventually, are there some non-RL based agents that can be used as an oracle to determine the shortest number of steps you need to solve a particular maze, or at least a good performance?

We have added a table containing an upper-bound for the number of steps needed to solve each puzzle in the revised manuscript.

Could you elaborate on the interest of assessing logical reasoning capabilities of RL agents in puzzles rather than in real world situations where reasoning helps? I think I can find some good arguments, but making such points may make the paper stronger.

While assessing logical reasoning capabilities in real world situations might serve a clear purpose, it also comes with a set of variables that cannot be controlled. This makes it hard to understand what the underlying factors are, and if logical reasoning was indeed the governing variable in the outcome. In contrast, logic puzzles offer a simple, controlled, and standardized approach to assess logical and algorithmic reasoning capabilities.

Would it be easy to provide a JAX interface so as to speed up the execution of many instances of the puzzles in parallel, as done in Brax and isaac-gym?

We agree that a direct JAX interface would prove beneficial for performance reasons. In principle, this should not be an issue, and we will consider building this in a future work.

All RL algorithms used in the empirical study are episodic, and using them in environments without a time limit raises a number of questions. If an agent fails to solve an environment, do you run it forever? "Eternity is very long, particularly when you get close to the end" (Woody Allen, approximate translation from another language). So, probably, you stop it after some time. But what time? How do you make sure it wouldn't have succeeded two steps after you stopped it? If you think of it seriously, a preset time limit is mandatory in RL experiments. You may take as time limit an empirical estimate of the time it takes to a random policy to solve it (not the mean, something closer to an upper quantile estimate).

For computational reasons we decided on a time limit of 10k steps. We selected difficulties that were solvable with high probability within these 10k steps, which generally resulted in the simplest non-trivial difficulty setting.

In practice, choosing the time limit for each puzzle as an upper quantile of the time it takes a random policy might make sense. But the problem of premature stopping before solving the puzzle will still exist, this is the drawback of a single final reward and possibly endless execution.

Using intermediate rewards would be one possible way to alleviate this problem, where an early termination of an episode has a smaller effect if some rewards have already been awarded. Unfortunately, these rewards need to be designed for each puzzle individually.

The empirical results with "length bars" (Figs 3, 4 and several in appendix) are not easy to read. In particular, the error bars in black can hardly be distinguished from the mean performance in Fig 1. Maybe the main paper should rather show aggregated results (mean over puzzles clustered into relevant groups?) and the full view deferred to an appendix, with environments organized horizontally rather than vertically?

We have reworked the figures and added tables in the revised manuscript.

In particular, it is in no way striking that TRPO and PPO outperform the rest, only a close investigation puzzle by puzzle can reveal this. Maybe tables will numerical results as in appendices and using bold for the 95% best would be more readable without requiring more space?

We have reworked the figures and added tables in the revised manuscript. Figure 3 in the main text now gives a general overview of the performance of each algorithm.

I'm not sure Figure 5 brings any important information. Either it should be exploited in more details, or it might move to some appendix, in my opinion.

We agree and have improved the corresponding Figure in the revised manuscript.

We thank the reviewer for their effort on reviewing our work. We address their concerns in the following.

The presentation of the results could be made a bit clearer as the figures is quite crowded and dense. An aggregate result showing how algorithms perform on average across all environments would likely better highlight that PPO and TRPO have a better performance than other algorithms.

We agree that some aggregation is needed to reduce the crowdedness of the figures. We have updated these figures in the revised manuscript.

The analysis of results might be a bit more detailed. For example, what separates a game like fifteen (where all algorithms seem to perform well) from a game like pegs, pearl or solo? Such a more detailed analysis might help to better convey the usefulness of the proposed benchmark.

We observe two dimensions of difficulty in the logic puzzle collection. One dimension is the inherent difficulty of the puzzle, the other dimension is the difficulty of the puzzle when played with the provided action space (e.g., moving the cursor using keyboard actions). Certain puzzles (e.g., maps) weren’t solved by our agents in the 3x3 setting better than a random policy, which is trivial for humans. We believe this is because of the more complicated sequence of moves that need to be learned to solve this with only keyboard inputs. Using this explanation we conclude that the puzzles which were solved by our agents were easy in both dimensions of difficulty. We have added a more detailed explanation of this topic in the revised manuscript.

To my understanding, the presented results are all for the "easiest" instantiation of the puzzles but no other difficulty levels are provided. If some curated settings for different difficulties would be provided, it would make future comparisons on the benchmark much more straight forward. Without such curated settings users are free to report any setting that works for them, which limits potential comparisons in the future.

We agree with the reviewer. For now we have looked into the easiest human-level difficulty settings as the next milestone for RL agents. While we have looked into generalizing this approach, we believe preset difficulties are too constraining for future evaluations. Especially since the preset difficulty settings found in Simon Tatham’s Puzzle Collection are not consistent across puzzles. We have included formulae for upper-bound optimal number of steps to solve puzzles in the appendix of the revised manuscript. We believe this is a good proxy for the difficulty of any puzzle (i.e., how many steps are needed by an optimal algorithm to solve it). Therefore, while the puzzle setting can be chosen freely, the number of steps needed by an optimal solution is given.

Small side note: The Atari 2600 was introduced by Bellemare et al.. Mnih et al. popularized it due to their success with DQNs.

We thank the reviewer for noticing this error. We have corrected this in the revised manuscript.

What are the episode lengths for the individual environments?

We have added the episode lengths for the individual environments in the appendix of the revised manuscript.

How expensive is training on RLP? Are episodes quick to run due to the c-backend (similar to brax training) or is everything slow due to the pygame bindings?

Unfortunately, there is no speedup due to the c-backend. However, RLP runs adequately fast. Since RLP cannot compete with the performance of brax environments, we will consider a direct implementation in Jax in the future for improved performance.

We thank the reviewer for their effort on reviewing our work. We address their concerns in the following.

The paper does not propose a new method to address the presented challenges.

Although our study does not present a new approach to address the identified challenges, it makes a significant contribution by providing a comprehensive benchmark for evaluating RL algorithms in the area of logical reasoning. This benchmark, focused on classic logic puzzles, reveals the current limitations of existing RL approaches and sets a clear direction for future research. Our work serves as a foundational platform, encouraging and enabling the development of new methods to address these complex problem-solving challenges in reinforcement learning.

The paper does not address the need for the proposed benchmark, provide a detailed analysis of the tested methods' failures, or give a list of open RL problems (related to the challenges offered by RLP).

As we stated in the introduction and in the contributions section of our work, RLP is a necessary benchmark for researchers to test RL agents’ logical and algorithmic reasoning abilities in controlled environments. Furthermore, we demonstrate that this task is far from solved and an important stepping stone to achieving more competent RL agents. Regarding detailed analysis of the tested methods’ failures, we found that the method worked in the simplest setting in the case that a random policy was able to find a solution. In all other cases, i.e., where a random policy was not able to find a solution within the given time limit, the tested methods were also not able to learn a policy.

Regarding the reviewer’s last point, a list of open RL problems; we pose a single problem: How can RL agents learn logical and algorithmic reasoning? Logical reasoning is a foundational requirement for general intelligence. Logic puzzles are at the pinnacle of logical reasoning under perfect testing conditions, yet current RL approaches fail in all but the most trivial cases. Therefore, we provide this benchmark as a building block for future work towards solving this challenge.

Methods tested in this work do not include the newest development in the RL field. One method is from 2022, another from 2020, and the rest are from 2017 or older.

We have added two more recent approaches, MuZero and DreamerV3, to the tested methods. Unfortunately, both methods still fail to solve any puzzle beyond the most trivial setting, highlighting the need for our benchmark. More details can be found in the revised manuscript.

We thank the reviewer for their effort on reviewing our work. We address their concerns in the following.

All the experiments report mean episode lengths instead of mean discounted returns. This makes the empirical results not very useful by themselves since some games like "Mines" can terminate at failed states.

Report: Failed states do not count as successfully completed episodes if identified (mines, guess, inertia, flood), otherwise terminate with max number steps possible (same game, pegs). Detailed results are reported in the appendix of the revised manuscript. We have improved the wording accordingly.

The experiments do not include model-based algorithms, such as state-of-art ones like MuZero [1] and DreamerV3 [2] would perform in this Benchmark. The experiments also do not include RL algorithms designed specifically for such hard puzzle games (e.g [3]) or for neural algorithmic reasoning in general. Hence, it is unclear if this benchmark is indeed a challenge for current RL algorithms as claimed.

We have added additional experiments to the revised manuscript. In particular implemented and tested MuZero and DreamerV3 on RLP, while DreamerV3 demonstrates promising potential both approaches still cannot pass the “human easy” setting of any puzzles. The “human easy” refers to the predefined settings found in Simon Tatham’s Portable Puzzle Collection. More details can be found in the revised manuscript.

The authors state that one of the benefits of the proposed benchmark is that all of the games have known polynomial-time optimal solutions, but they do not compare the evaluated RL algorithms with the optimal ones in the reported results. Including the optimal performance in the reported results is useful to judge how good the evaluated algorithms are in each game. It is also unclear if the benchmark comes with these optimal solutions.

We have added an upper-bound for the number of steps an optimal solution would need in the appendix. We now measure the steps required by an RL approach compared to the number of steps for the optimal solution. More details can be found in the revised manuscript.

The paper only evaluates RL algorithms for game difficulties where a random policy can find a solution. It is not clear what this means, since all the games at all difficulty levels are solvable by a random policy (just with low probability for higher difficulties). I am guessing the authors meant that the random policy can find a solution in a maximum number of timesteps with high probability.

Yes, this is what we meant. We ran a random policy for 10’000 timesteps and repeated over 1000 runs. The puzzles that were not solved by a random policy were declared unsolvable under these constraints and were not evaluated using the different RL approaches.

The authors also claim that this restriction on evaluated games was necessary to enable any learning for the RL agents. This doesn't seem correct, since we know that many RL algorithms like PPO can solve tasks in which a random policy is highly unlikely to find a solution (for example in robot tasks).

While the reviewer’s statement is correct, this only holds when intermediate rewards are involved. When only the final reward is provided, any RL policy behaves identically to a random policy, as there is no reward to guide it. Therefore, we believe our assessment holds: only when a random policy is able to solve a puzzle with a large enough success rate, an RL approach without intermediate rewards is also able to solve a puzzle.

Given that PPO is solves most of the evaluated tasks, the empirical results do not support the claim that this is a challenging benchmark for current RL. It would have been useful if the paper also evaluated the algorithms for different difficulty levels to show the scaling laws of current RL algorithms for this benchmark.

PPO only manages to solve half of all tasks on the easiest possible setting by surpassing the performance of the random baseline. The easiest possible setting is beyond trivial for humans. In light of these results, we disagree with the reviewer’s statement “PPO solves most of the evaluated tasks”, and continue to argue that this is a challenging benchmark.

Table 3 is referenced on page 9 but does not exist.

Table 3 is located in the appendix. We have changed the references to better reflect this.