The World Is Bigger! A Computationally-Embedded Perspective on the Big World Hypothesis

AI summary

Overview

• Research area: Reinforcement learning theory and continual learning, specifically the formalization of the "big world hypothesis" through computability theory, algorithmic information theory, and embedded agency.
• Technical level: Advanced. The paper relies on algorithmic (Kolmogorov) complexity, universal Turing machines, Markov processes over countable state-spaces, and meta-gradient reinforcement learning.
• Scope in one sentence: The paper formalizes an agent as an automaton simulated inside a computationally universal, uniformly local environment, defines an algorithmic-complexity objective called "interactivity," and shows empirically that deep linear networks sustain interactivity while deep ReLU networks collapse.

What This Paper Is About

Continual learning is often justified by the big world hypothesis — the idea that "the world is bigger" than the agent — but prior problem settings capture this by imposing explicit, often ad hoc constraints on the agent (storage limits, function-approximator expressivity, information-theoretic capacity). The authors propose instead that an agent is implicitly constrained simply by being embedded in and simulated by its environment. Their goal is a general problem setting in which any agent, regardless of capacity, is both constrained and suboptimal if it stops learning.

Key Contributions

1. Universal-local environments. The authors define an "algorithmic Markov process" (Definition 2), a discrete process on a countable state-space whose transition function is computable in time polynomial in the state size, and show (Proposition 1) that any Turing machine can be represented as one. They then add uniform locality (Definition 5): the transition function decomposes into identical local transition functions, each determined by a finite portion of the state-space plus a boundary-space. A "universal-local environment" is a universal Markov process that is also uniformly local.

2. The computationally-embedded agent. An embedded automaton is defined as 𝒜 := (Ω|_X, Ω|_Y, Ω|_Θ, u, π), with input space, output space, internal state space, an internal state update function u, and an output function π (Definition 6). Proposition 2 proves that when the boundary space of the internal state matches the input space (b^k(Θ) = X), the automaton is equivalent to a k-horizon boundaried Markov process, its environment is a partially observable Markov decision process, and its interaction is equivalent to a stateful policy acting on that environment. The abstract states the automaton is equivalent to an agent interacting with a POMDP over a countably infinite state-space.

3. Interactivity as a formal objective. Interactivity (Definition 7) is defined as the difference between the algorithmic complexity of the agent's T-horizon future behaviour and that same complexity conditioned on past behaviour. It is high when future behaviour is complex and predictable from the past. Theorem 1 states that an embedded agent's maximum interactivity is asymptotically upper- and lower-bounded by a quantity depending on its capacity.

4. A tractable relaxation and an evaluation task. Because algorithmic complexity is generally uncomputable, the authors adopt a distortion-rate view and measure complexity as temporal-difference prediction error under the agent's own predictor (Definition 8), yielding "agent-relative interactivity." They build a model-based RL algorithm around this and use it to construct a synthetic, environment-free evaluation of continual adaptation. Theorem 2 ("Big World") states that an agent maximizing agent-relative interactivity is limited by its finite capacity and is suboptimal if it stops learning.

Main Findings

• Implicit constraint replaces explicit constraint. Proposition 3 shows that an embedded automaton's capacity is upper bounded by the size of its finite internal state space |Θ|, so there exist input–output sequences the automaton cannot realize. This constraint arises from embedding rather than from a hand-imposed limit, and the authors argue explicit constraints (storage, expressivity, compute, energy, information-theoretic capacity) are ad hoc, hard to measure beyond analytically tractable cases, and limit the benefits of scaling up capacity.
• A computationally embedded agent necessarily faces a POMDP. Given b^k(Θ) = X, the automaton is equivalent to a k-horizon boundaried Markov process whose environment is a POMDP. The environment always has greater capacity than any agent contained within it.
• Interactivity trades off complexity against predictability. An interactivity-seeking agent pursues behaviour that is increasingly complex while remaining predictable given its past experience; the authors compare this balance to how definitions of open-endedness balance novelty and learnability with respect to an observer.
• Both the policy and the value function must keep changing. If the value function stops changing, interactivity is trivially zero; if the policy stops changing, the value function can converge to a fixed point. Interactivity-seeking agents therefore create their own non-stationarity.
• Deep ReLU networks fail to sustain interactivity. In the evaluation task, the deep nonlinear (ReLU) policy could not plan an action sequence for which the dynamic value function has low prediction error but the current static value function has high prediction error, and failed to produce actions with any predictable structure.
• Deep linear networks sustain interactivity, and scale with capacity. The deep linear policy sustained interactivity and, per the abstract, sustains higher interactivity as capacity increases. It learned to produce actions following a non-stationary wave, locally predictable by a static linear function and globally by a dynamic linear function.
• Non-stationarity may look like plasticity loss. The authors suggest interactivity-seeking agents produce non-stationarity that can lead to apparent loss of plasticity, which linear methods have been shown to avoid.
• Quantitative results are not reported in the available content. The text ends mid-sentence ("Observing the actions chosen by each pol..."), and no numeric interactivity values, dataset sizes, or benchmark scores appear in the material provided.

Methodology in Plain English

The authors start from a computability argument rather than an experiment. Because of the Church–Turing thesis, they can pick any computational model (they use Turing machines) and still describe a general class of environments that can simulate an agent. They describe the environment as a Markov process whose state is a finite string of symbols and whose transition function runs in polynomial time, and they require the transition function to be local: every part of the state updates using the same rule, based on a small finite neighbourhood. Conway's Game of Life is offered as an existence proof, where each cell's next value depends on its 8 neighbouring cells.

An agent is then just a small pattern inside that environment, described by inputs, outputs, an internal state, a policy, and an update rule — like observations, actions, parameters, and a learning rule in standard RL. The authors prove this pattern behaves like a stateful policy in a POMDP.

To define what "continually adapting" means, they use algorithmic complexity: how long is the shortest program that produces the agent's future behaviour, with and without knowledge of its past? The gap is interactivity — the part of future behaviour that is complex but learnable from experience. Since this quantity is not computable in general, they replace it with a practical proxy: the difference between prediction errors made by a frozen predictor and prediction errors made by a predictor that keeps learning. They then set up a meta-learning problem: roll out actions from the current policy through a differentiable model, measure this error difference, and take gradients to make the policy choose experiences that are learnable but not yet learned. The value function is a linear map of behaviour, the policy is a deep network (linear or ReLU) with RMSNorm-normalized output, and RMSProp was found to balance performance and stability better than Adam or vanilla gradient descent. The evaluation is environment-free — the agent observes only its own actions, like self-play.

Why This Matters

• It reframes the big world hypothesis as an implicit rather than explicit constraint. Instead of measuring and enforcing a capacity limit, the setting inherits one from the fact that the agent is simulated inside the environment. This connects the continual learning literature to embedded agency and universal AI, and gives capacity-dependent bounds on achievable adaptive behaviour (Theorem 1).
• It provides a clean desideratum. Theorem 2 states the two properties previously described as conditions for a big world simulator: the agent is limited by finite capacity and is suboptimal if it stops learning. Any algorithm satisfying this can be said to face a genuine continual learning problem.
• It offers an environment-free evaluation. Because the self-predicting agent reads and writes its own experience stream, algorithms can be evaluated by continually learning from their own online experience, without an environment or pre-collected data, in a manner similar to self-play.
• It connects algorithmic information to intrinsic motivation. Interactivity is related to forecasting complexity, statistical complexity, predictive information, and light cone complexity, but uses algorithmic rather than Shannon information, so it operates on individual sequences rather than requiring probability distributions — a natural fit for an agent's own behaviour stream.

Real-world applications implied by the framing (the paper does not enumerate applications; these are extrapolations):

• Continual-learning systems deployed over long horizons, where the environment keeps changing and a fixed solution degrades.
• Agents evaluated without simulators, using self-generated experience streams, which is relevant when environment access is expensive or unavailable.
• Designing objectives for open-ended learning, where the goal is behaviour that stays complex but learnable rather than merely novel or merely predictable.
• Understanding plasticity loss in deep networks, since the paper ties its ReLU-versus-linear finding to non-stationarity and apparent loss of plasticity.

Industry relevance: The paper does not discuss commercial applications directly, but its central question — whether scaling capacity actually improves continual adaptability — bears on the scaling assumptions behind large learned systems. The finding that a deep linear policy sustains interactivity while a deep ReLU policy collapses is a caution about the assumption that more parameters alone yields more adaptive behaviour. The authors also explicitly frame their approach as an alternative to capacity constraints that limit the effectiveness of scaling up.

Future Directions

• Extending beyond the self-predicting setting. The evaluation uses an idealized agent with full control over its experience stream via the internal boundary space Ω|_{b(Θ)}. How interactivity-seeking behaves with an external, non-cooperative environment is left open.
• Explaining and mitigating the nonlinear failure. The paper reports that the deep ReLU policy fails to sustain interactivity and links this to apparent plasticity loss; what architectural or algorithmic changes would let nonlinear networks sustain interactivity is not resolved.
• Measuring interactivity more faithfully. Agent-relative interactivity replaces algorithmic complexity with temporal-difference error under a constrained reference machine. How closely this tracks the exact quantity, and which predictor choices are appropriate, remains open.
• Testing other learning algorithms and capacities. The experiments instantiate a linear value function and deep linear or ReLU policies optimized with RMSProp. Whether other optimizers, architectures, or update rules change the linear-versus-nonlinear conclusion is not reported in the available content.

Target Audience

Readers with a background in reinforcement learning theory, algorithmic information theory, or the foundations of continual learning. The paper is most valuable to researchers working on the big world hypothesis, embedded agency, universal AI, intrinsic motivation, and open-endedness, and to those interested in why capacity scaling does or does not translate into sustained adaptive behaviour. Practitioners looking for applied continual-learning recipes will find the setting abstract and the empirical section narrow.

Authors’ abstract

Continual learning is often motivated by the idea, known as the big world hypothesis, that "the world is bigger" than the agent. Recent problem formulations capture this idea by explicitly constraining an agent relative to the environment. These constraints lead to solutions in which the agent continually adapts to best use its limited capacity, rather than converging to a fixed solution. However, explicit constraints can be ad hoc, difficult to incorporate, and may limit the effectiveness of scaling up the agent's capacity. In this paper, we characterize a problem setting in which an agent, regardless of its capacity, is constrained by being embedded in the environment. In particular, we introduce a computationally-embedded perspective that represents an embedded agent as an automaton simulated within a universal (formal) computer. Such an automaton is always constrained; we prove that it is equivalent to an agent that interacts with a partially observable Markov decision process over a countably infinite state-space. We propose an objective for this setting, which we call interactivity, that measures an agent's ability to continually adapt its behaviour by learning new predictions. We then develop a model-based reinforcement learning algorithm for interactivity-seeking, and use it to construct a synthetic problem to evaluate continual learning capability. Our results show that deep nonlinear networks struggle to sustain interactivity, whereas deep linear networks sustain higher interactivity as capacity increases.