Research map / Reinforcement learning / Visual and representation RL
PUZZLES: A Benchmark for Neural Algorithmic Reasoning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces PUZZLES, a Gymnasium-based RL benchmark of 40 scalable logic puzzles from Simon Tatham's Portable Puzzle Collection, and evaluates standard RL algorithms on it.
Problem
Existing RL benchmarks lack a unified testbed for evaluating logical and algorithmic reasoning in single-agent, perfect-information settings.
Approach
Wraps 40 adjustable-difficulty logic puzzles from Simon Tatham's collection as a Gymnasium environment with internal-state and pixel observations, discrete actions, action masking, and early termination on state repetition, then benchmarks many RL algorithms against an optimal-steps upper bound.
Key results
- DreamerV3 achieved the best average successful episode length of 1334 steps across puzzles in the easiest setting, versus an optimal upper bound of 217 steps.
- DreamerV3 solved 62.7% of puzzle instances; PPO and TRPO solved 61.6% and 70.8%.
- A2C, RecurrentPPO, DQN and QRDQN performed worse than a random policy; action masking improved training efficiency on both internal-state and pixel observations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use DreamerV3 instead of PPO | PUZZLES baseline evaluation · easiest-setting aggregate | average successful episode length | Helped |
| increase puzzle difficulty from the overall easiest to easiest-for-humans setting | PPO and DreamerV3 · Netslide, Same Game, Untangle | success rate | Hurt |
| select the best checkpoint using generalization-environment performance (ablation) | PPO (Transformer) · Same Game 5x5c3s2 generalization | success rate: 9.4\% -> 18.1\% | Helped |
| enable action masking (ablation) | PPO / MaskablePPO · PUZZLES (internal-state and pixel observations) | training performance | Helped |
| use pixel observations instead of discrete internal game-state observations (ablation) | PPO · PUZZLES | training performance | Hurt |
| increase maximum training episode length from 10,000 to 100,000 steps (ablation) | DreamerV3 · selected human-difficulty puzzles | success rate | No clear effect |
| terminate episodes after visiting the same state more than 10 times (ablation) | DreamerV3 · selected human-difficulty puzzles | success rate: 25.2\% vs. 31.5\% | Helped |
Surprising findings
- A2C, RecurrentPPO, DQN and QRDQN performed worse than a purely random policy.
- Simple PPO and TRPO were competitive with the more complex DreamerV3 and MuZero.
Limitations
- Baselines use default hyperparameters without puzzle-specific tuning.
- Sparse rewards make many puzzles intractable for all evaluated algorithms.
- Discrete action spaces exclude algorithms such as SAC and TD3.
Experimental setup
Datasets: Simon Tatham's Portable Puzzle Collection (procedurally generated puzzles)
Benchmarks: PUZZLES
Metrics: average episode length of successful episodes success rate optimal steps upper bound
Baselines: PPO TRPO A2C RecurrentPPO DQN QRDQN MaskablePPO MuZero DreamerV3
Builds on: Gymnasium Stable Baselines 3 Simon Tatham's Portable Puzzle Collection Atari benchmark
Closest papers by meaning
- DeepSearch: Overcome the Bottleneck of Reinforcement Learning with Verifiable Rewards via Monte Carlo Tree Search (ICLR 2026 · similarity 0.89)
- Reasoning Gym: Reasoning Environments for Reinforcement Learning with Verifiable Rewards (NeurIPS 2025 · similarity 0.89)
- Enigmata: Scaling Logical Reasoning in Large Language Models with Synthetic Verifiable Puzzles (NeurIPS 2025 · similarity 0.88)
- Reasoning with Exploration: An Entropy Perspective (AAAI 2026 · similarity 0.87)
- MATH-Beyond: A Benchmark for RL to Expand Beyond the Base Model (ICLR 2026 · similarity 0.87)
- Prioritize the Process, Not Just the Outcome: Rewarding Latent Thought Trajectories Improves Reasoning in Looped Language Models (ICML 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.