Temporal abstractions, often instantiated as options, have long been regarded as a mechanism for accelerating credit assignment, facilitating exploration, and enabling generalisation in reinforcement learning (RL). However, developing general option discovery methods that are effective in large-scale, high-dimensional domains remains a fundamental challenge. Existing option discovery methods are either confined to relatively simple domains, depend on handcrafted or quasi-symbolic representations, or offer little improvement over learning without options. We present Wayfarer, a general, domain-agnostic, online deep RL agent that discovers options through Laplacian representation learning from high-dimensional observations and leverages them for control. We show that the resulting options simultaneously improve exploration, accelerate credit assignment, and generalise effectively to unseen settings, enabling substantially faster learning of complex policies. Wayfarer achieves state-of-the-art performance among single-stream agents on the most challenging Atari 2600 games, with the largest gains in games that require long-horizon exploration and strategic behaviour, such as Montezuma's Revenge and Private Eye.
Figures & tables
Figure 1: Wayfarer learns a representation, derives options from it, and learns a policy over actions and options.
Figure 2: The Atari 2600 challenging set . From left to right: Beam Rider , Freeway , Montezuma’s Revenge , Pitfall! , Pong , Private Eye , Skiing , Solaris , Surround , and Venture . The set was assembled by Badia et al. [8] to highlight games where progress has historically been much slower than average due to challenging exploration and credit assignment problems. Designed for entertainment, these games offer test beds of intelligent behaviour free of the experimenter’s design bias [ 12 , 4 ] .
Figure 3: Aggregate metrics on the Atari 2600 challenging set, over 200M frames, with 95% CIs. Higher mean, median, and IQM and lower optimality gap are better. We report results on ten games with five runs per game, except for DreamerV3, for which we use four—the minimum available number of published runs available across games.
Figure 4: Three options discovered by Wayfarer in Pitfall!. One option ( pink ) travels left, crossing a deadly puddle in a coordinated sequence. Another ( green ) travels right, crossing holes and using ladders where needed. The third ( blue ) underground.
Figure 6: Options discovered in the first room of Montezuma’s Revenge use ropes and avoid deadly skulls in unseen rooms without further learning. (Left) Option #9 moves right and descends ladders. (Right) Option #8 moves left, also using a rope-like pole along the way. Starting points/directions are marked with yellow arrows, ropes and poles with red stars, and deadly enemies with skull icons.
Figure 7: Aggregate metrics on the Atari 2600 challenging set, over 100M frames, with 95% CIs. Higher mean, median, and IQM and lower optimality gap are better. Ten games; three runs per game.
Appendix figures & tables15 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 8: Examples of Laplacian eigenvectors from a 4×6 grid environment.
Figure 9: The three Wayfarer networks: (A) The agent-centric Laplacian representation network, whose outputs are used to provide intrinsic rewards for training (B) the skill network, which learns the options that augment the action set of (C) the main network learning the extrinsic task. Blue blocks are convolutional components; green ones are linear blocks; red ones are their noisy variants.
Figure 10: The first level of Montezuma’s Revenge. Rooms that appear dark to the agent without a torch in its inventory are marked here with a black overlay. In game, the rooms are numbered from 0 to 23, row-major. The agent starts from room 1, and the level ends in room 15. To pass the level, at least three of the four keys have to be collected, which requires visiting at least 15 of the 24 rooms.
Figure 11: Empirical option-selection rates (EOSR) over the first 100M frames in Montezuma’s Revenge: at each checkpoint, the observations in the agent’s experience replay buffer are grouped by room; each observation is passed through the main network, and EOSR is the fraction of cases in which the network selects an option over a primitive action. Each cell quantifies whether the agent prefers options ( red ) or primitive actions ( blue ) relative to uniform selection over the 18 primitive actions and 10 options ( \nicefrac1028≈0.36 ), in a particular room of Montezuma’s Revenge at a particular point in time during training. White cells mark rooms absent from that checkpoint’s replay buffer. (Left) EOSR under the main network’s noisy value estimates, averaged over 100 noise resamples per observation. (Right) EOSR with noise disabled, using the argmax of the learned value estimates over temporally extended and primitive actions.
Symbol
Value
Meaning
d,K
6,2(d−1)=10
number of eigenfunctions, eigenoptions
γ,n
0.99,3
discount factor, multi-step returns n
N,N′,Nsel
64,64,32
IQN online, target, selection quantiles
mτ,κ
64,1
cosine embedding dims, Huber threshold
B,Brep
32,512
main & skill minibatch, rep & aux minibatch
Adam [ 40 ]
optimiser
Appendix
Table 1: Wayfarer’s hyperparameters in the Arcade Learning Environment [ 12 ] .
Figure 12: Aggregate metrics on the Atari 2600 challenging set, over 200M frames, with 95% CIs, using AUC of mean episodic returns over the full training period instead of the mean over last 10%. Higher mean, median, and IQM and lower optimality gap are better.
Figure 13: Interquartile mean (IQM) human-normalised scores (HNS) with 95% bootstrapped CIs.
Figure 14: Mean episodic returns per game over 200M frames. The individual runs are plotted faintly, with a darker line showing the IQM across seeds (5 per game for all methods except DreamerV3, which has 4–6).
Figure 15: Mean episodic returns per game over 100M frames. The individual runs are plotted as separate lines (3 per configuration per game).
Task
Random
Human
DQN
Rainbow
IQN
DreamerV3
Wayfarer
Beam Rider
363.9
16926.5
6044.7
17143.4
18865.5
33863.5
5168.2
Freeway
0.0
29.6
27.9
34.0
33.6
33.5
33.7
Montezuma
0.0
4753.3
0.0
0.0
0.0
2524.0
5107.9
Pitfall
-229.4
6463.7
-86.2
0.0
-41.0
-0.1
-2.5
Pong
-20.7
14.6
17.2
21.0
20.6
20.5
20.1
Private Eye
24.9
69571.3
121.8
100.0
171.8
39990.2
40468.4
Appendix
Table 2: Mean episodic returns from the last 10% of training: median across all available seeds (5 per game for all methods except DreamerV3, which has 4–6).
Task
Random
Human
DQN
Rainbow
IQN
DreamerV3
Wayfarer
Beam Rider
363.9
16926.5
6059.9
17023.1
18890.5
34681.6
5086.0
Freeway
0.0
29.6
27.9
34.0
33.6
33.5
33.7
Montezuma
0.0
4753.3
0.0
0.0
0.0
1998.2
4326.7
Pitfall
-229.4
6463.7
-245.6
0.0
-41.7
-0.1
-2.9
Pong
-20.7
14.6
17.1
21.0
20.6
20.5
20.2
Private Eye
24.9
69571.3
119.4
100.0
171.2
28538.7
38749.9
Appendix
Table 3: Mean episodic returns from the last 10% of training: IQM across all available seeds (5 per game for all methods except DreamerV3, which has 4–6).
Task
Random
Human
DQN
Rainbow
IQN
DreamerV3
Wayfarer
Beam Rider
363.9
16926.5
5882.4
16930.2
18829.5
35640.4
5077.1
Freeway
0.0
29.6
22.4
34.0
33.6
33.4
33.7
Montezuma
0.0
4753.3
0.0
39.7
0.0
1828.8
4186.9
Pitfall
-229.4
6463.7
-338.1
0.0
-41.8
-0.1
-3.1
Pong
-20.7
14.6
17.0
21.0
20.6
20.4
20.1
Private Eye
24.9
69571.3
132.2
159.9
179.6
26287.2
34418.4
Appendix
Table 4: Mean episodic returns from the last 10% of training: mean across all available seeds (5 per game for all methods except DreamerV3, which has 4–6).
Figure 16: Freeway. (Left) . An RGB frame from the game. (Center) The smoothest non-constant eigenfunction tracks exogenous structure—the two slowest cars—whose motion is unaffected by the agent. (Right) With agent-centric regularisation, the smoothest non-constant eigenfunction tracks only the agent’s vertical position, which is the part of the observation under the agent’s control.
Figure 17: Montezuma’s Revenge (rooms 1, 2, and 7). The learned Laplacian representation is sensitive to changes in pixels associated with progress, including keys, doors, skulls, laser gates, and parts of the heads-up display. When these features change, the behaviours that can lead to further progress may also change, making them plausible indicators of transitions between weakly connected regions of the experienced state space.
Figure 18: Mean episodic return in Montezuma’s Revenge with NaP and a constant effective step size.
Temporal abstraction via options can improve exploration in large environments. However, existing option discovery algorithms find subgoals that target all aspects of the state simultaneously. This state-reaching approach produces options that only apply in narrow regions of the state-space, eventually causing an explosion in the number of options that overwhelms the agent, and impedes progress on its primary task of reward maximization. We introduce an algorithm that instead identifies a small, relevant subset of features for each subgoal, yielding options that generalize broadly and accelerate exploration. Our approach learns abstract, transferrable options and achieves rapid exploration in three sparse-reward, image-based domains, including the Atari game MontezumasRevenge.
Akhil Bagaria, Anita De Mello Koch, George Konidaris
The Arcade Learning Environment (ALE) has been a cornerstone of Deep Reinforcement Learning research, providing a standardized benchmark for evaluating general agents. However, its lack of native support for object-extraction and environment modification restricts research into evaluating whether agents learn robust causal models or rely on brittle visual heuristics. Furthermore, the ALE's dependence on CPU-based emulation creates a significant bottleneck in modern GPU-accelerated training pipelines, limiting both experimental scale and iteration frequency. In this work, we introduce JAXtari, an open-source, high-performance reimplementation of Atari 2600 environments. By leveraging massive GPU parallelization, JAXtari allows PPO agents to finish training on 100M environment steps on a single A100-GPU in under an hour. Beyond speed, it provides object-centric observations and a flexible modification system, allowing researchers to, e.g. develop neuro-symbolic methods or discover novel shortcuts and subsequently train and adapt their agents rapidly, sometimes in only minutes.
Quentin Delfosse, Raban Emunds, Paul Seitz +5
Department of Computer Science, Technical University Darmstadt, Germany · Google Intrinsic AI Research · Hessian Center for Artificial Intelligence (hessian.AI) +2
Much of the advancement in Multi-Agent Reinforcement Learning (MARL) for imperfect-information games has historically depended on the manual, iterative refinement of algorithmic baselines. Recently, evolutionary coding agents powered by Large Language Models (LLMs) have emerged as powerful tools to automate this discovery process. In this work, we deploy one of such agentic frameworks, AlphaEvolve, to navigate the design spaces of two distinct game-theoretic paradigms: counterfactual regret minimization (CFR) and policy-space response oracles (PSRO). This automated search yielded two algorithms: Volatility-Adaptive Discounted (VAD-) CFR and Smoothed Hybrid Optimistic Regret (SHOR-) PSRO, which are consistently competitive with state-of-the-art human-designed baselines across an 18-game evaluation suite spanning Poker, Goofspiel, Liar's Dice, Blotto, and Battleship variants. However, because the LLM optimizes for fitness on a specific training set, it often constructs highly synergistic, complex mechanisms tailored to those environments. Through systematic ablation studies, we demonstrate that while these mechanisms are tightly coupled, the true driver of generalization lies in a minimal algorithmic core. By distilling the LLM's discoveries down to their most fundamental principles, we produce two minimal solvers: Warm-started Optimistic Predictive (WOP-)CFR and Projection Matching (PM-)PSRO. These distilled versions achieve superior performance on generalization with greatly reduced structural complexity, providing a clear methodology for using LLMs in algorithmic discovery.