Efficient Exploration Is Enough

1 Introduction

• When models generalize, uniform coverage—and even maximizing immediate prediction error—need not be the most efficient exploration strategy.Experience from one region may help predict dynamics in unseen scenarios.Source: §1 · pp. 1–2
• Efficient exploration prioritizes experience that supports world models predicting across the environment, reducing global prediction error over time.Experience is the agent’s history of interactions, and generalization is assessed against a broader target distribution.Source: §1 · p. 2
• The authors argue that efficient exploration alone can drive increasingly complex behaviors, including survival mechanisms traditionally associated with extrinsic rewards.The introduction illustrates survival as preserving time to gather data and progressively more complex behaviors as ways to increase exploration efficiency.Source: §1 · p. 2
• The paper investigates this purely intrinsic objective without extrinsic rewards, using theoretical analysis and empirical study to examine its implications.The framework treats an agent’s optimality as determined solely by exploration efficiency.Source: §1 · p. 2

2 Preliminaries

• Agents map histories to action distributions, while environments map histories and actions to observation distributions; the framework covers Markovian and non-Markovian, fully and partially observable, episodic and non-episodic settings.Histories are sequences of action-observation pairs, with actions preceding observations.Source: §2 · p. 3
• A world model predicts observation distributions from histories and actions, and serves as an external construct for evaluating how well an agent’s experience generalizes.The formalism can also accommodate agents that act using an internal world model learned from experience.Source: §2 · p. 3
• A learning rule maps histories to world models, and the discrepancy between a model and the environment is measured with a divergence or metric.The total variation distance and Kullback-Leibler divergence are given as examples of discrepancy measures.Source: §2 · pp. 3–4
• Global loss aggregates model discrepancies across actions and realizable histories, weighting each transition by the probability of its preceding history under a uniform agent.The uniform policy acts as an unbiased history sampler, so errors in unlikely environment scenarios are discounted relative to errors in likely ones.Source: §2 · p. 4
• Because an agent observes only a small fraction of the full history space, efficient exploration requires strategically gathering experience that yields generalizable data.The world model is estimated from interactions collected up to each step.Source: §2 · p. 4

3 Exploration efficiency

• Expected cumulative error aggregates the expected global losses of world models estimated from an agent’s histories over the interaction horizon; lower error means more efficient exploration.Each model is evaluated across histories up to its step, and efficiency is ordinal: agents are compared relative to one another.Source: §3 · pp. 4–5
• Optimal explorers form a set of agents minimizing expected cumulative error, because distinct behaviors can produce equally informative histories and identical generalization properties.The paper gives different study fields and clockwise versus counterclockwise sweeps as examples of distinct but similarly informative trajectories.Source: §3 · p. 5
• At least one fully deterministic optimal explorer exists, while some environments also have stochastic optimal explorers.Stochastic choices can be optimal when multiple pathways are equally informative.Source: §3 · p. 5

• The analysis assumes a controlled Markov process, stationary Markovian agents, a tabular world model, and squared L2 discrepancy.The world model is a smoothed empirical estimator built from transition frequencies in the agent’s history.Source: §4 · pp. 5–6
• State-action contributions to global error combine a visit-weighted variance term that grows with transition entropy and decays as O(1/N), and a bias term that decays as O(N^-2).The bias term decreases as transition entropy rises; the variance term increases with transition entropy.Source: §4 · pp. 6–7
• Efficient explorers prioritize low-entropy, deterministic transitions, where bias falls quickly, over highly stochastic transitions with slower error reduction.At maximal entropy, the prior aligns with the true distribution, yielding zero initial ECE and discouraging visits.Source: §4 · p. 7
• Because learning costs vary across state-action pairs, optimal explorers may under-sample difficult transitions rather than distribute visits uniformly.They allocate finite interactions to regions that improve global predictive accuracy more rapidly and reliably.Source: §4 · p. 7
• An absorbing state consumes the remaining visitation budget on a learned transition, so optimal explorers avoid it and preserve interactions for unexplored regions.Repeated visits to the deterministic absorbing transition yield diminishing error reduction at O(N^-2).Source: §4 · p. 7

5 Empirical analysis

• The study uses four partially observable grid environments and optimizes GRU agents with OpenES to minimize an MC estimate of ECE.The authors describe this method as a tool for empirical analysis rather than a primary contribution.Source: §5 · pp. 7–8

5.1 Results

• In Empty, efficient agents shift from broad coverage to a helix-like path that periodically samples regions informative for predicting incoming walls.Homogeneous floor observations make incoming walls harder for the world model to predict.Source: §5.1 · p. 8, Figure 3 · p. 8
• In Blocks, the most efficient agent intensely samples one of two symmetric block regions because their identical dynamics make sampling both redundant.Data from one region supports generalization to structurally similar areas.Source: §5.1 · p. 8, Figure 3 · p. 8
• In Maze, efficient agents use a cyclic path, sampling informative walls and corners before open areas and avoiding redundant resampling of the starting region.The environment’s lack of structural symmetries leads to full coverage.Source: §5.1 · p. 8, Figure 4 · p. 9
• RandColors agents first traverse the deterministic corridor and low-entropy room, then move to the higher-entropy room, whose irreducible error is five times the left room’s.They later devote more interaction time to the right room because reducing its prediction error demands more data.Source: §5.1 · pp. 8–9, Figure 4 · p. 9

6 Discussion

• Optimal efficient exploration can use deliberate, targeted data collection rather than relying on the random noise common in many RL methods.Theorem 3.4 establishes that such exploration can be deterministic.Source: §6 · p. 9
• Under common RL assumptions, optimal explorers prioritize the most learnable and informative regions before regions with higher inherent entropy or irreducible error.The discussion connects this ordering to survival in non-episodic and non-ergodic environments.Source: §6 · p. 9
• Partially observable settings with neural agents and world models produce sophisticated behaviors, including symmetry exploitation and interaction sequences organized by modeling complexity.These behaviors automatically create curricula for world models.Source: §6 · p. 9
• Evolution across generations reveals a meta-level curriculum of progressively more sophisticated behaviors, including a helix pattern in the Empty environment.The authors suggest this could provide a principled mechanism for open-ended behavioral complexity without external objectives or tasks.Source: §6 · p. 9
• Future work includes extending the theoretical analysis to more expressive model classes and developing scalable approximations for complex settings.The latter concerns the basic Monte Carlo ECE estimation used in Section 5.Source: §6 · pp. 9–10

A Connections to previous work

• Count-based methods encourage coverage without distinguishing informativeness, while surprise methods prioritize local prediction errors rather than global model generalization.The discussion contrasts these signals with experience that generalizes more broadly across the environment.Source: A Connections to previous work · p. 15
• The framework avoids Markov, episodic, explicit-reward, and predefined-task-boundary assumptions, and treats exploration as an ongoing intrinsic objective rather than preparation for downstream reward optimization.Reward-free RL instead evaluates collected experience by its usefulness for externally specified reward functions.Source: A Connections to previous work · pp. 15–16
• Open-endedness work emphasizes novelty and serendipity, while UED and related approaches generate diverse tasks or environments and typically assume substantial control over that process.The cited examples include OMNI-EPIC [Faldor et al., 2025] and Voyager [Wang et al., 2024].Source: A Connections to previous work · p. 16
• Active inference shares a model-error-reduction emphasis but relies on prior preferences over sensory causes, whereas this framework assumes no such priors and evaluates model error globally.Active inference is described as minimizing expected surprise over trajectories experienced by a particular agent.Source: A Connections to previous work · p. 16
• Compression progress targets compressibility of lived experience, while Chollet’s account is task-centric; the paper does not present efficient exploration as an intelligence measure.The paper distinguishes compressing the environment itself from immediately improving the compressibility of observed data.Source: A Connections to previous work · p. 17

B.1 Proof of Proposition 2.7

• The uniform-random-agent proof substitutes the same action probability at every history, simplifying the probability expression used to prove Proposition 2.7.The shared action probability is denoted c.Source: §B.1 · p. 17

B.2 Proposition B.1

• For an optimal explorer, every action chosen with positive probability yields the same expected future cumulative global loss.The proof establishes this by contradiction: a higher-loss action could be replaced to improve exploration efficiency.Source: §B.2 · pp. 17–18

B.3 Proof of Theorem 3.4

• At least one fully deterministic optimal explorer exists in every environment.The proof constructs one by selecting a supported action deterministically at each history; backward induction preserves its ECE.Source: §B.3 · p. 18
• Some environments admit stochastic optimal explorers, so determinism is not required for optimality.The proof constructs an environment with a non-deterministic optimal explorer.Source: §B.3 · p. 18
• In the constructed setting, an optimal explorer can mix between two action choices when its remaining choices stay coherent with the selected agent.The proof identifies such mixtures as still achieving optimal ECE.Source: §B.3 · p. 18

B.4 Proof of Proposition 4.3

• The proof relates a history’s transition probability to its final state and action using the environment’s Markovian property.It applies Assumption 4.2 to relate the agent’s action choice to the state.Source: §B.4 · pp. 18–19
• Grouping length-k histories by their last state allows the proof to express expected visits to state s over steps 1 through t−1.The indicator vector for the initial state has value 1 at that state’s index and 0 elsewhere.Source: §B.4 · p. 19
• The proof concludes by completing Proposition 4.3.Source: §B.4 · p. 19

B.5 Proof of Theorem 4.4

• The proof conditions on transition counts and uses a bias–variance decomposition to reformulate the squared L2 objective for Theorem 4.4.The derivation identifies variance and bias contributions to the estimator’s error.Source: §B.5 · pp. 19–20

C.1 SmallWorld environment

• SmallWorld uses scalar-valued grid cells, agent-centered observation matrices, and discrete four-direction movement across environments including Empty, Maze, Blocks, and Random Colors.Negative, zero, and positive cell values denote obstacles, floor, and other entities, respectively.Source: §C.1 · p. 21

C.2 Approximating the ECE

• ECE is estimated by Monte Carlo sampling, with deviated-agent histories added in some environments to better distinguish competing agents and stabilize ES convergence.The deviations are stochastic action perturbations, ranging from the unmodified agent at α = 0 to uniform random actions at α = 1.Source: §C.2 · pp. 21–22

C.3 Method overview

• The method estimates ECE by sampling histories, training world models, and optimizing the agent population with an evolutionary strategy.World-model training uses transition-prediction MSE and AdamW; the outer loop uses OpenES.Source: §C.3 · p. 22

C.4 Hyperparameters

• Experiments default to a 5 × 5 observation window, and the agents use a feed-forward layer, GRU, and two further feed-forward layers.World models use a fully connected MLP; Blocks and Maze use α = 1 for history sampling.Source: §C.4 · p. 22

C.5 Hardware details

• Experiments ran on a cluster node with eight Nvidia A5000 GPUs, an AMD EPYC 7252 CPU, and 377GB of RAM; one run took approximately 10 hours.Source: §C.5 · p. 23

Empty

• In Empty, the efficient visitation pattern is helix-like and largely avoids the center and immediate edges.The agent targets paths where walls fall just outside its observation window, making wall prediction harder and supporting learning of wall-to-wall dimensions.Source: §C.6 · pp. 23, 25, Figure 6 · p. 24, Figure 7 · p. 25
• The Empty pattern’s distance from the nearest wall is consistently (n −1)/2 cells for an observation window of size n.The authors hypothesize that the center and extreme edges yield repetitive, easily predictable observations.Source: §C.6 · p. 25, Figure 7 · p. 25

Blocks

• In Blocks, agents focus on the lower-middle gap, allowing the world model to predict the symmetric upper gap without direct exploration.Prediction error is low across the block gaps but accumulates where the symmetry does not hold.Source: §C.6 · p. 25, Figure 8 · p. 25

Maze

• In Maze, the lack of spatial symmetries accompanies approximately uniform visitation, achieved through a structured cyclic route rather than a random walk.The agent systematically traverses the maze in both directions.Source: Figure 6 · p. 24, §C.6 · p. 25

Random Colors

• In Random Colors, agents concentrate interaction in both upper rooms but spend more total time in the rightmost room, where best achievable error is 0.0125 versus 0.0025 in the left, reflecting greater modeling difficulty.Source: §C.6 · p. 25

C.7 Increasingly complex behaviors

• Across Empty, Blocks, and RandColors, ES optimization produces a sequence of increasingly structured and complex behaviors.The authors describe this empirical pattern as evidence connecting exploration-efficiency optimization with open-endedness.Source: §C.7 · pp. 25, 27, Figure 10 · p. 26
• In Empty, near-uniform early coverage develops into a rotating ring-like pattern and then a helix-like strategy as population ECE improves.The final helix achieves higher exploration efficiency than the circular pattern.Source: Figure 9 · p. 26, §C.7 · p. 27
• In Blocks, later strategies emphasize difficult edges and corners, eventually prioritizing the region between the lower and middle blocks to exploit symmetry.An earlier strategy already focused on the middle-to-upper gap.Source: Figure 10 · p. 26, §C.7 · p. 27
• In RandColors, the visitation sequence develops from the corridor to the left room and then the harder right room.The left room initially reduces model error more readily; later strategies allocate more time to the right room after exploring the easier regions.Source: Figure 10 · p. 26, §C.7 · p. 27

D Extended Discussion

• The extended discussion frames experience sequencing as an active curriculum for the world model and relates emergent behaviors at interaction and behavioral levels to open-endedness.Source: D Extended Discussion · p. 27

D.1 The importance of order in experience and implicit curricula

• Visitation order matters because reaching equally informative regions can incur different path costs and make some routes require redundant sampling.In Maze, the agent explores upper sections before the rightmost room to avoid retraversing the starting room.Source: §D.1 · pp. 27–28
• The optimal ordering of experience depends on the world-model hypothesis space and learning rule, making the explorer a curriculum generator for that model class.An experience’s informativeness depends on prior knowledge, as illustrated by the child encountering set theory.Source: §D.1 · p. 28
• Because informative experiences may require prior context, global model error and ECE cannot necessarily decrease abruptly.The informativeness of an experience is relative to what has already been learned.Source: §D.1 · p. 28
• Limited model capacity and plasticity can make efficient exploration require strategically revisiting, reinforcing, or selectively forgetting experiences.In these settings, exploration involves deciding which experiences to generate and which to forget.Source: §D.1 · p. 28

D.2 Open-endedness

• At the agent-environment interface, efficient exploration schedules novel, learnable interactions from informative regions toward areas with higher inherent entropy.This process is bounded by the horizon and by agent, environment, and world-model complexity.Source: §D.2 · p. 28
• Optimizing for efficient exploration yields increasingly complex behaviors, but this meta-level process is bounded by optimization capability and human interpretive capacity.The helix-like trajectory in the Empty environment becomes more interpretable as a progression from simpler behaviors.Source: §D.2 · pp. 28–29