The World Is Bigger! A Computationally-Embedded Perspective on the Big World Hypothesis
Authors: Alex Lewandowski
Aditya A. Ramesh
Edan Meyer
Dale Schuurmans
Marlos C. Machado
Venue: NeurIPS 2025 spotlight ()
Keywords: big world hypothesis
computational constraints
continual learning
reinforcement learning
algorithmic complexity
Primary area: reinforcement_learning

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.

The World Is Bigger!
A Computationaly--mmeeddee Perspective on the Big World Hypothesis
Alex Lewandowskil.2- Aditya A. Ramesh Edan Meyer
Dale Schuurmans 1.244,
Marlos C. M
University of Alberta *Canada CIFAR AI Chair
Amii
Thhe Swiss AI Lab IDSIA, USI & SUPSI
'Google DeepMind
Abstract
Continual learning is often motivated by the idea, known the big world hy- pothesis, 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 fixed solution. However, explicit constraints can be ad hoc, difficult to incorporate, and may limit the effectiveness of scaling up the agent's 's capacity. In this paper, we characterize a problem setting which an agent, regardless of its capacity, is constrained by being embedded in the environment. In particular, we introduce a cmmputationlly--mbellae that represents embedded agent as an automaton simulated within universal (formal) computer. Such an automaton is always constrained; we prove that it is equivalent
perspective
agent that interacts with partially observable Markov decision process over a countably infinite state-space. We propose an objective for this setting, which we call interactivity, that measures agent's ability to continually adapt its behaviour by learning new predictions. We then develop a moodel-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 sustain interactivity, whereas deep linear networks sustain higher interactivity as capacity increases.
Introduction
The goal of this paper is to characterize a general problem setting in which the best use an agent's limited capacity is to continually adapt (Ring) 1994 Thrun 1998 Abel et al. 2023). Our approach motivated by the idea, known as the big world hypothesis, that "the world is bigger" than the agent (Javed and Sutton 2024). That is, agent in big world may lack the capacity learn the fixed optimal solution, and should instead continually adapt to new experience by updating its approximate solution (i.e., by tracking, [Sutton et al.) 2007). However, formalizing the relationship between the agent and the enviroument presents a challenge, because they are typically treated as separate entities in reinforcement learning (see Figures Ta Tb). We address this by introducing compurationally-emeedede
agent that is simulated by the environment's 's dynamics, thus constraining the agent within the environment. With this perspective, any such agent is (i) constrained by its capacity, and (ii) suboptimal if it stops learning.
construct problem setting in which
Explicit constraints on the agent have been previously considered in continual learning means of capturing the big world hypothesis. For example, in continual learning experiments, the agent's
*Correspondence to: Alex Lewandowski Rewaandowkii@ullbettt.co
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Bounded Env
Scalable Agent
Universal Env
AIXI Agent
Universal-Local Env
Embedded Agent
(a) Traditional RL
(b) Universal AI
(c) This work
Figure 1: Comparing the agent and environment in different problem formulations. Each problem formulation differs in the constraints that it imposes the agent relative to the environment. Traditional RL: A given environment typically has a bounded capacity, but a scalable agent can increase its capacity. Such agent is unconstrained in principle because its capacity can always be scaled beyond the environment. Universal AI: Both the computationally universal environment and the AIXI agent are unbounded. AIXI is thus unconstrained but computable. This work: The universal-lowe environment is unbounded, but it can simulate an embedded agent of any bounded capacity within its state-space. An embedded agent is implicitly constrained because the environment necessarily has greater capacity than any agent contained within it.
learning algorithm is often explicitly constrained by what it can store (Prabhu et al. 2020), or by the expressivity of its function approximator (Meyer et al.) 2024). Other real-world constraints on the agent's hardware have also been considered. Such constrants include limits on the agent's 's compute (see discussion on measuring compute in Section 4.1, Verwimp et al.) 2024) and on the agent's energy use (Javed and Sutton 2024). One recent formalization of continual learning uses an explicit constraint on the agent's cntommation-thhoreee capacity (Kumar et al. 22033] 2024). However, beyond analytically tractable agents and environments, this measure and enforce, limiting its generality as problem setting for continual learning. Furthermore, explicitly constraining the agent limits the effectiveness of scaling up the agent's capacity, which has been a major source of progress in machine learning more broadly (Hestness et al. 2017 Kaplan iet al. 2020; Hoffmann et al.) 2022). These limitations suggest that explicit constraints may not be an effective way of capturing the big world hypothesis.
constraint is difficult to
In contrast explicit constraints, our approach considers the implicit constraint that arises from an agent embedded in an environment (see Figure Ic). Specifically, an embedded agent is, in principle, fully defined within the environment's state, and simulated by the environment's dynamies. The embedded nature of agents that they exist within and as part of their environment is typically treated as outside the scope the problem formulation (Demski and Garrabrant 2019). However, the physical world is clear example of world bigger than any agent, suggesting that embedded agency can provide a natural formalization of the big world hypothesis and of continual learning.
To formalize an agent embedded in an environment, we define a universal-locad environment: Markov process whose transition dynamics can simulate an agent within a finite portion of its state-space. Computational universality guarantees that the environment can simulate any algorithm (Church) 1936 Turing 1937). Uniform locality decomposes the environment's transition dynamics into a collection of identical Markov processes, each operating on finite portion of the state-space embedded agent is then represented an automaton simulated within the environment, formalized as one of these local Markov processes. When the automaton's dynamics are determined solely by its input and output, we prove it interacts with a partially observable Markov decision process: receives inputs (observations), updates its internal state, and produces outputs (actions). We then propose interactivity, defined through algorithmic complexity (Kolmogorov) [9655] Solomonoff 1964 Chaitin| 1966), to measure automaton's 's ability continually adapt its future input-output behaviour. An ineeractivity-seekii remaining predictable given its past experience. Crucially, we prove that an agent's interactivity is constrained by its capacity, which can be allocated either to increase its behavioural complexity or to improve its behavioural predictability.
agent pursues behaviour that increasingly complex while
Universal artificial intelligence similarly considers universal environments (Hutter 2000 2005), in which the uncomputable AIXI agent was extended to an embedded formulation (Orseau and Ring 2012). However, these works did not consider the problem of learning under limited capacity. By con- sidering universal environment that is also local, show that an
agent must

---

continually adapt to its experience, regardless of its capacity, Interactivity also relates to intrinsic moti- vation objectives (Schmidhuber 1991| Chenttanz et al. (2004), such as forecasting complexity (Grass) berger 1986). statistical complexity (Crutchfield and Young 1989), predictive information (Bialek
et al. So00ppStil and Precup, 2012), and light cone complexity (Shalizi et al. 2004] Aaronson et al. 2014p. These objectives are defined through Shannon information as measures of past-future depen- dence in the agent's behaviour, requiring a probability distribution over behaviour sequences. Interac- tivity, however, uses algorithmic information, allowing it to operate directly on individual sequences, without requiring probability distributions. Since an agent's behaviour is an individual sequence rather than probability distribution, this formulation provides natural computational framework for contin- ual learning. Moreover, by tying the agent's 's objective to its computational capacity, which is naturally constrained relative to the environment, our formalism further captures the big world hypothesis.
Lastly, we develop a reinforcement learning algorithm for maximizing interactivity, and use it to construct a task that evaluates a learning algorithm's 's capability for continually adaptive behaviour. Specifically, we operationalize algorithmic complexity in terms of the prediction error. Interactivity is then measured as the reduction in this error attributable to continual learning, relative to baseline agent that stops learning. Interactivity-secking behaviour thus involves learning a policy to steer the agent's 's behaviour to new experiences that are learnable, but that would have high prediction error without learning. We show that interactivity-seekinn agents create their own non-stational -ontstationarity by changing their policy, thereby satisfying key desiderata of the continual learning problem: every agent is constrained by its capacity, and any agent that stops learning is suboptimal. Our results indicate that, in this setting, deep nonlinear networks struggle to sustain interactivity, whereas deep linear networks effectively scale their interactivity with increased capacity.
2 Background
We formalize an embedded agent from a computational perspective, viewing the environment as computational process that also simulates the agent. Specifically, consider computationally universal environment that, through its state transitions, simulates the computational steps of any algorithm. Our approach is general, by making use of the Church-Turiin computationally universal systems are equivalent in what they can simulate, and that any such system can simulate another (Church 1936) Turing (997)). This allows us adopt particular model of computation (e.g., Turing machines) while retaining a general class of environments that are capable of simulating an embedded agent.
thesis, which asserts that all
We characterize the capabilities of an agent, relative to its environment, in terms of its input-output behaviour finite sequence (i.e., string). In particular, use the algorithmic complexity of string, which is the length of the shortest program that computes it and halts (Kolmogorov 1965
Solomonoff 1964; Chaitin 1966)..
Definition (Algorithmic Complexity). Given strings x, y E E", where E is fiite symbol-set and Ex is the set of strings, the conditional algorithmic complexity the length of the shortest program, |c], that halts and outputs x given y input,
(u(zly) == minfle] Ul(c,))) = =x},
where Ut is a reference universal machine. The unconditional algorithmic complexity is given by Ku(x) == Ku(x) ()., where is the empty string.
While algorithmic complexity depends on the choice of a reference universal machine, any specific choice affects the algorithmic complexity by, at most, an additive constant independent of the specific string (Li and Vitányi, 2019). Moreover, in this work, we will consider the given computationally universal environment, defineed in the next section, as the canonical reference universal machine.
3 A Universal-Local Environment
We begin by defining universal- loccll environments, general class of environments in which an agent can be embedded, These environments are characterized by two key properties: computational universality (Section(..] which establishes that any algorithm can be simulated by the environment's transition dynamics, and uniform locality (Section 3.2). which ensures that any finite computation can be confined to a bounded portion of the environment's 's state-space. Section 4 we use these properties to define embedded agent as automaton simulated on the environment's 's space.
3

---

3.1 Markov Representation of a Computationally Universal Environment
We first connect computational processes with Markov processes defined over a countable state-space with transition function that is computable in polynomial-tine time with respect to the size of the state.
Definition 2. An algorithmic Markov process, E (.), is a discrete process defined on a count- able stale-space, Ω {w = : [wi| < &x). where E is a finite symbol set with distinguished blank symbol O E Σ, E is countable set used for indexing, and w| := K{ E E w(g) & OJll counts the number of non-blank symbols. Given an initial state w E Z with |w| oc, the process produces the next state w' = T( such that [w') < oo and where the transition function, T - Ω is computable time po (oloy(l)))
The significance of this formulation is that any Turing machine can be represented as an algorithmic Markov process. Specifically, the Markov state represents the entire configuration of the Turing machine, including its head position, current tape contents, and control state. The Markov transition function represents the Turing machine's 's transition function, which is a lookup table that can be applied to the Markov state in polynomial non-deterministic transitions are also possible, and would involve multiple possible next states.
We will consider only deterministic transitions, but
Proposition (Representing Turing machines). The computational process followed by a Turing machine can be represented as an algorithmic Markov process.
All proofs of propositions and theorems can be found in Section of the Appendix. One consequence of Proposition is that there exists a universal Markov process (an algorithmic Markov process corresponding to universal Turing machine). This result highlights how an algorithmic Markov process is more general than the Markov processes typically considered in reinforcement learning. In particular, a universal Markov process capable of simulating any algorithm, which is crucial for defining an embedded agent in Section 4
3.2 Defining Uniform Locality with Boundaried Markoy Processes
Intuitively, uniform locality means that the transition function can be decomposed into identical local transition functions with dynamics that are determined by a finite portion of the state-space. To make this precise, we first formalize a finite portion of the state-space as a substate space.
Definition 3. Given an algorithmic Markov process, & (S, E, T), a substate-space, M defined as a restriction of the state-space, Ωt to a finite index-set, F E F(E) := I < x): R| = [w|p : E [2 where w|F > Σ is defined by, w| (E) == for E
We now consider the transition function restricted to substate-space, 12 p. In particular, we define a boundaried Markov process in which the restricted transition function, T) depends on both the substate-space, 82)F., and an additional substate- spacee S2 called the boundary-spann
Definition 4. Given an algorithmic Markov process, E (2, E, T), substate-space, F. admits a k-horizon boundaried Markov process if there exists a substate-space (2(BA(F) (referred to as a boundary-space) and a restricted transition function T 8 x M)N(() + 00 that is equivalent to the k-step transition function on the substate-space. T (m] (wwpp,, wl)+(()) Ω. We denote the k-horrion boundaried Markov process as E = (M Plut(m: TH)), and, if l 1, we refer to simply as boundaried Markov process, E|r = (3)r, (1(F)).(())
T(t) T()(w) F for all
Typically, the size of the boundary-space increases the transition horizon & becomes larger. This is because the current substate, W|F E 2 F. and the current boundary, w| w/b(F)) E Mlb(F)) only determine the next substate, wlpp E Sl and not the next boundary.
An algorithmic Markov process is uniformly local if every index admits a boundaried Markov process single reference boundaried Markov process.
that is isomorphic
Definition 5 (Uniform Locality), An algorithmic Markov process, E =9,E,, is uniformly local if there exists a boundary function, b: + + and a reference e. E E, such that every & E E admits boundaried Markov process isomorphic to the reference &.. That is, there exist bijections ag Rl(e) + 1l and 3g Ω Dbten + 1lb((E.)) }) satisfying, for all w E Ω.
ag (T) (wl (wl (wllee/..lole))) wlo(t)))) Tl... ) (w) (w) (e(w)o(t))))

---

+
Figure 2: Conway's Game of Life is cellular automaton and an example of universal-local environment. The state state-space is an infinite 2D grid, = Zz where each cell in the grid takes one of values, Σ [black, white). J. Every cell uses the same local transition function in which the boundary-space consists of its 8 adjacent neighbours. The blue and green borders (left) correspond to 1 and 2 horizon boundary-spaces, which determine the center cell at time-steps i (middle) and t 2+2 2 (right), respectively. Longer-term transition dynamics depend on larger boundary-space
Uniform locality guarantees that the transition function can be computed by simultaneously applying an identical local transition function to each singleton of the state-space. Consequently, the transition dynamics for any substate-spant [ can be determined from the collective boundary, defined by b(F)) = Uçer b(E))). This ensures that every substate-space admits a boundaried Markov process.
Thus, we use the term universal-local environment for universal Markov process that is also uniformly local. We call it an environment because, as we will show, an embedded agent can be simulated as a boundaried Markov process within it.
3.3 Example of a Universal- Environment: Conway's 's Game of Life
Conway's 's Game of Life (or Life) is an example of a universal-local environment (Conway) 1970). This environment is computationally universal because it can simulate universal Turing machine (Berlekamp et al. 1982, Rendell 201T). A substate-space in Life is finite subset of cells on the grid and the possible values taken by those cells. Furthermore, Life is uniformly local because the one-step transition dynamics for each individual cell is determined by its adjacent neighbouring cells, which defines the boundary-space (see Figure
We point Life an existence proof for universal- local environments, but we are not suggesting to program an agent within it. Instead, we use our formalism to characterize the constraints that would be faced by an agent if were embedded any such environment.
cnaputatiioally-EEmeedde
Agent
We represent an embedded agent as an automaton simulated within the universal-local environment, formalized as boundaried Markov process. Specifically, we prove that when the automaton's ss boundary space coincides with its input-output space, it constitutes a formal agent-environment boundary (Jiang] 2019 Harutyunyan, 2020). Consequently, the automaton is equivalent to stateful policy interacting with a partially observable Markov decision process. We then introduce interactivity to measure capability for continually adaptive behaviour, proving that therractvittyssekiin automata are constrained by their computational capacity.
4.1 Embedding an Automaton in a Universal-Loca Environment
A universal-local environment can simulate any algorithm; this property enables us to define an automaton, A4, within the environment's 's state space, Ω, such that its operation is simulated by the environment's 's transition dynamics, T. Moreover, uniform locality ensures that the automaton can be represented as a boundaried Markov process (see Figure 3 left).
Definition Given a uniivrrsal-loce environment, by A == (2)x, Kly, Rl u, T), where ?le is the automaton's 's internal state space, Ω 21xx 2/yy are input and output spaces, म S2|x x Ω + 12/y is the output function, and 2 x Ω + Ule is the automaton's 's internal state update function.
(Q.E.T) an embedded automaton defined
Relating this to an agent in reinforcement learning, we may think the inputs as observations, the internal state as the parameters of function approximator, the outputs as actions, the internal state
5

---

E ?
Self-Predicting Agent
Q (()))
ee
1
A
Figure 3: An illustrative depiction of poapppttttiinlll--mmeedeeee agent interacting with its environment. An embedded automaton, A (52 x. Oly S2 u, πT, represents an agent embedded within the universal- process within the environment, in which iteratively receives an input from the environment, E Ω|x, produces the corresponding output = <(;; 0) E 12 and updates its internal state, 8' [x; 0) Se Right: We will also consider an idealized setting in which a self preficcre agent exerts full control over its experience by reading and writing to an internal boundary-space [lb(())
environment. Left: The agent is simulated by boundaried Markov
update function as a learning rule, and the output function as a policy. The input-space may also provide external reward to the automaton, but this need not be the case.
Relationship). Given an embedded automaton, A = (12 Sle, u, T), there exists a horizon k such that (e) X, then:
Proposition 2
The automaton is equivalent a k-horizon boundaried Markov prucess
2. The automaton's environment is partially observable Markov decision process.
3. The automaton's interaction with the environment is equivalent to a stateful policy.
Now that we have defined both the embedded automaton and its environment within the same universal-local environment, we can show that any such automaton is constrained by the size of its internal state-space, which determines its memory and computational capacity.
Proposition 3 (Implicitly Constrained). The capacity of an embedded automaton is upper bounded by the size of its internal state space, [θ), which is finite. Thus, there exists input- coput-output sequences that the automaton cannot realize.
An embedded automaton is constrained by its capacity, which constrains the behaviours that it can produce. While more complex behaviour be produced with capacity, will show that this constraint specificaly limits its ability to produce behaviour that continually adapts to past experience.
4.2 Interactivity as a Computational Measure Adapatability
An agent's is capability for learning can be characterized by its ability to adapt its future behaviour using its past experience. We propose interactivity to measure this capability directly in terms of algorithmic complexity. Specifically, interactivity measures the difference between the algorithmic complexity of future behaviour with and without conditioning on past experience.
Following Proposition 2] we represent an embedded agent as an embedded automaton A where its input space constitutes termined by the values taken the boundary-space, corresponding output, b, (t). ) At time the behaviour can be separated into finite sequences: the past, bo--1 == bob ... bb- and the T -'-oorzonn future, b == bebe+1 ... b1+T-1
boundary-space, 92|x = ())+(e)- Thus, the behaviour of the agent is de-
E (()) which combines the input and the
Definition (Interactivity)) Given an embedded automaton, A == (Ω) x R|y Aee u, T), we define its T-horizon interactiviry relative to its environment. E, as the difference between the al algorithuicc complexity of its future behaviour with and without conditioning on its past behaviour.
[ Ft, boa-1) == 1kg(beetTT) (e) (k bbxt-1);
where is the empty string, F4 is the current observation, O,-1 is the internal state, yt = π (are; 0--1) is the action, Or u(x,, 0(-1) is the next internal state, and b, (It, yt) is the next behaviour tuple.

---

That is. interactivity measures the predictable complexity of an agent's future behaviour, given its past behaviour. Interactivity is high if both (i) the future behaviour, T has high unconditional algo- rithmic complexity, and (ii) the past behaviour, 1p is predictive of this future behaviour, thereby yielding a low conditional algorithmic complexity. interactivity-seekinn complexity and predictability with respect to the agent's s past behaviour, similar to how definitions of open-endedness balance novelty and learnability with respect to an observer (Hughes et al. 2024).
behaviour thus balances
4.3 An Interactivity- Agent Faces Big World
The interactivity of any embedded agent is always constrained by its capacity. That is, an interactivity- seeking agent can only sustain a given level of interactivity with given capacity. However, an anteractivity-seekiie agent can always use additional capacity to achieve higher interactivity.
Theorem 1. Given an embedded agent,
(Ωlx Rly, , e u, RT. its maximum interactivity asymptotically upper and lower bounded by quantity that depends on its capacity.
The goal of an interactivity-ssekingg agent can be understood as balancing the complexity and predictability of its future behaviour, given its past behaviour. Seeking achieve this goal requires that the agent continually adapt to its experience, learning about its computational limitations, and tracking its environment with predictions learned within these limitations. This suggests the following interactivity thesis:
Interactivity measures a capability for continually adaptive behaviour.
We refer to this as the interactivity thesis, rather than a hypothesis, reflect its speculative and philo- sophical nature. With low interactivity, the future behaviour of an agent is either i) simple, or ii) com- plex and unpredietable. In either case, the thesis asserts that the agent's capability for continually adap- tive behaviour is limited. A simple agent has limited range of possible behaviours and thus has rela- tively lower capability for adaptive behaviour. A complex agent could have a relatively high capability for adaptive behaviour, but only if its future behaviour is influenced by. and can be predicted from, past experience. Embracing the interactivity thesis naturally leads to spectrum of adaptive capability.
5 Maximizing Agent- Interactivity with Reinforcement Learning
Maximizing interactivity poses a fundamental computational challenge: it depends on algorithmic complexity, which is generally uncomputable. While algorithmic complexity can be computed for finite automata through exhaustive program enumeration (Li and Vitányi| 2019), this requires computational resources that exceed the automaton's own capacity. Consequently, an interactivity- seeking agent must approximate interactivity rather than compute it exactly.
To approximate interactivity, we take distortion-rate view of algorithmic complexity, which measures complexity in terms of prediction error under a constrained reference machine, rather than under an unconstrained universal Turing machine (Vereshchagin and Vitányi 2010). The embedded agent, heing an automaton, provides a natural choice for the constrained reference machine. We then augment this agent include a predictor function function of agent-state, and measure agent-relative complexity by the incurred temporal difference errors under this predictor.
Definition 8. Given an embedded agent A = (52 Gly Si u. T) with a predictor v: Oxxur 2 + SXxuy and 7 E [0, 1], the agent-relative complexity of future behaviour bac+T-1, conditioned on past behaviour bo.t-1, is the sum of future temporal difference errors,
T-1
Ba(bestT-1lbo--
Σ
(be+k + prubbexs:0 0(0-=--1(0+
where 0z4k-1 is the agent-state after processing bott11 followed by bea+k-1 through repeated application of the agenf's 's update function u.
Complexity, measured in this way, is relative to the agent's capabilities. If the future prediction emrors are large (small), then the future behaviour relatively complex (simple). These future prediction errors depend crucially the agent through its predictor, its current agent-state, its
7

---

learning algorithm, its policy, and its observations from the environment. With this prediction error formulation of complexity, we now consider the agent-relative interactivity.
(AA 2t, Dua-1) a (c) (Ka 1100.111).
5.1 Learning to Maximize Agent-Relative Interactivity
We now develop a reinforcement learning algorithm for maximizing agent-relative interactivity. Our algorithm is summarized in the following three steps: (i) learning prediction of the discounted future behaviour using a value function, (ii) computing the agent-relative interactivity, defined as the difference between static prediction enrors (unconditional complexity) and dynamic prediction errors (conditional complexity), and (iii) meta-leaming a policy to maximize agent-relative interactivity.
The first step involves learning prediction of the future input-output behaviour, where we consider the deterministic setting and omit the expectation over trajectories. This value function predicts both future observations and actions, similar to successor features (Barreto et al. (017)) and the successor representation (Dayan 1993). Specifically, with temporal difference learning (Sutton 1984, 1988). we train value function to predict the discounted sum of future input-output behaviour,
o(be; 0+)
be+R41
(0) be+ + yu(br+ 0) 1a00-v(lii u(b++k-1;0),
k=
where B.4 can understood as dynamic parameters which are updated using semi remi-gradient TD(0): 0.+ = 8 + (B Vo -= where is a step-size.
For the second step, measure the conditional and unconditional complexity terms using dynamic and static temporal difference errors, respectively. From the first step, we can readily compute the conditional complexity using the dynamic temporal difference errors just described.
T-1
k (h
= Σ 2 (0+1x11) k=0
Unlike the conditional complexity term, the unconditional complexity term is not conditioned on past experience, which means means that cannot be computed using the dynamic parameters. Instead, computing the unconditional complexity involves static and unchanging reference state, Oref- One convenient choice the current state, Oref = 9:-1, which we adopt to yield the following form for agent-relative interactivity,
l x bo.t-1) Rd
& (0 (0+((0+
static
dynamic
Lastly, we outline how a policy can be trained to maximize interactivity. To obtain the future prediction errors, assume access differentiable model that of observations and actions using the current policy. Interactivity is estimated on the roll-out by computing the cumulative difference between the static and dynamic prediction errors. The policy is then updated using interactivity!" Crucially, both the policy and value function must be continually updated to sustain interactivity: if the value function stops changing then interactivity is trivially zero, and if the policy stops changing then the value function can converge fixed point.
roll-out sequence
muddentt-based optimizer with the objective of maximizing the estimated
5.2 Maximizing Interactivity as Continual Learning Problem
We now show that interactivity-seekin reinforcement learning agent faces continual learning problem. Intuitively, this because interactivity-seet -eeeking behaviour is directed towards experience which can be predicted by a dynamic value function that learns from experience, but which cannot be predicted by the current value function it were to remain static. Specifically, interactivity-seeking agents are suboptimal if they stop learning, such as when the parameters of their policy and value stop changing. Similar to our previous result on embedded automata (Theorem [T] we also show that the agent's maximum possible interactivity increases the its capacity increases.
Optimiziin the dynamic errors involves meta- gradients through the value function's parameter update.

---

Activot on
0.70
Linor
0.70
PULL
Interdiitty 32
0.15
0.55
0133
0.33
0.59
0.50
Insar
0.43
0.43
0.38
Iranationn
Figure 4: Deep ReLU networks fail to sustain performance on the interactivity evaluation task. Interag simulates a big world to evaluatesa learning algorithm's 's capability for continually adaptive behaviour. Right: The deep linear network sustains interactivity, whereas the deep ReLU collapses in performance. Middle: Each colour corresponds to one component of the action vector. The deep linear policy learns to produce actions following non-stationary wave, which can be predicted by a dynamic linear function. Left: The deep ReLU policy fails to produce actions with any predictable structure, despite its increased expressivity
Theorem 2 (Big World). An agent that seeks to maximize its agent-relative interactivvry is (i) limited by its finite capacity and, (ii) suboptimal if it stops learning.
The desiderata of Theorem 2 were previously described as conditions for a big world simulator (Kumar et al. 2024). Thus, interactivity-seeki captures the big world hypothesis: the best use of an agent's 's limited capacity is to continually adapt.
appears to be general problem setting which
6 Evaluating Continual Adaptation With Egent-Relative Interactivity
We now use interactivity-seeking to construct a synthetic problem to evaluate a learning algorithm's capability for continually adaptive behaviour. In particular, we consider a setting in which the agent only observes its own actions (see the self- sefe-prediting agent in Figure 3 right). Even though such an agent has full control over its experience stream, its interactivity is still implicitly constrained by its capacity. That is, the interactivity objective depends on the parameters and learning algorithm of the value function, which the agent does not directly observe. An advantage of this evaluation approach is that it is enviromment-free allowing direct evaluation of an algorithm outside of an environment, or any collected data. Instead, algorithms are directly evaluated by continually learning from their own online experience in a manner similar to self-play.
We instantiate the reinforcement learning agent outlined in Section 5 with linear parameteriza- tion of the value function, b(b,; W == W.b. = Σg > bb+++++1 Linearity provides stability for learning online with TD(0), compared to temporal difference learning with deep nonlinear networks. For the policy parameterization, we consider a deep network architecture (using either linear or ReLU activations), where we normalize the output to ensure that the output has bounded range, by+1 == RMSNorm (T (bx; 0z)). This policy is optimized using the model-based approach described in Section 5 Optimizing the agent-relative interactivity is a bi-level optimization problem as the dynamic prediction errors depend on the value function's 's learning process. Thus, our model-based approach maximizing interactivity is similar the cross-prop algorithm (Veeriah et al., (017)). which is an online version of and the value function, we found RMSProp (Hinton et al. 2012) to balance performance and stability better than either Adam (Kingma and Ba 2015), or vanilla gradient descent.
meta-learning (Finn et al. 2017). For both the policy
Our results demonstrate that deep nonlinear policy is unable sustain interactivity (see Figure 4 right). That is, the deep nonlinear policy is unable to plan an action sequence for which the dynamic value function has low prediction error, but for which the current static value function has high prediction error. However, we find that a deep linear policy is able to sustain interactivity. This finding suggests that siteeractivityssekkii
agents produce non-stationarity that can lead to apparent loss of plasticity, which linear methods have been shown to avoid (Lewandowski et al. 2025b) Dohare al. 2024). Observing the actions chosen by each policy, we found that the deep linear policy learned to produce actions with predictable structure, resembling a non-stationary wave (see Figure 4 middle). These actions can be locally predicted by linear function, but global prediction requires a dynamic linear function. In contrast, the deep nonlinear policy leamed failed to produce actions with any predictable structure (see Figure 4 left). Furthermore, in Figure 5 we found that deep linear networks are also capable of increasing their interactivity with more capacity, in the form of deeper or wider networks. These findings demonstrate that interactivity-seeking simulates the challenges of big world in which any policy is limited by its finite capacity, and suboptimal if it stops learning.
9

---

Width
Depth
12-
10.
10.
Interactivity
Interactivity
8-
6-
128
512
2
256
1024
2
0 2000 4000
2000
4000
6000
8000
10000
6000
8O00
10000
lterations
Iterations
Figure 5: Deep linear networks are capable of sustaining higher interactivity with more com- putational resources. By increasing the width and depth of the deep linear network, we increase the network's capacity for continual adaptation, which allows more quickly change its linear function approximator. Left: Increasing width marginally increases the sustained interactivity. Right: Increasing depth results in a large increase in interactivity, as well as more oscillatory behaviour.
7 Discussion
In this paper, we introduced a computationally-embeddee perspective on the big world hypothesis, where we (i) characterize the implicit constraint faced by an embedded agent, (ii) propose interactivity as computational measure of adaptability, and (iii) develop a reinforcement learning algorithm for maximizing interactivity. We show that interactivity-seekinn leads to the common desideratum of the continual learning problem in which any agent that stops learning is suboptimal.
Our work departs from dogmas common in reinforcement learning (Abel et al. 2024) by formalizing the agent as embedded in the environment, and by proposing interactivity as an objective defined agents are implicitly constrained
relative to agent and its learning algorithm. Interactivity-seekie because the interactivity objective depends on components, such as parameters, that are not directly observable but evolve through learning. As we demonstrated in the environment-free evaluation task, this perspective has a critical consequence: an anteractivity-seekeee adapt rather than converging to fixed point. Unlike existing continual learning problems that often involve manually designed non-stationarity. an interactivity-seekie the non-stationarity through its learning algorithm. This task thus provides several unique challenges: (i) the task complexity scales with the complexity of the learning algorithm, (ii) hyperparameters influence the non-stationarity produced by the learning algorithm, requiring more careful procedures for tuning (Mesbahi et al., (222),, and (iii) the task incentivizes the design of continual learning
agent must continually
agent autonomously produces
algorithms that can both sustain plasticity to learn from new experience (Lyle et al. 2024] Dohare et al.. 2024), and use plasticity and prior learning to create more new experience through non non-stationanity.
evaluation task for continual learning, interactivity can also objective for agents in reinforcement learning environments. Unlike the environment-fre evaluation task investigated in this paper, estimating the interactivity of agent in an environment would involve learning a model of the environment to calculate meta-gradients, or learning a value function that directly approximates interactivity. The change in temporal difference error due learning would then serve as an intrinsic reward, similar to curiosity-driven methods, to incentivize directed exploration.
Beyond serving
auxiliary
This practical potential for directed exploration suggests refinement of the interactivity thesis. We speculate that an agent can sustain a particular level of interactivity. then it possesses the capacity to learn any behaviour with equal or lower cetuuctvittyinnnluuut cumulative sum a reward signal. That is, the ability to sustain high interactivity may reflect a more general capacity for acquiring goal-directed behaviours.
those that maximize the discounted
Acknowledgments
We would like to thank Saurabh Kumar and Hong Jun Jeon for helpful discussion during earlier stages of this work, David Abel and Anna Harutyunyan for their encouraging discussion regarding dogmas in reinforcement learning, and the anonymous reviewers for their feedback. The research supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC), the Canada CIFAR AI Chair Program, and the Digital Research Alliance of Canada.
10

---

References
Aaronson, S., Carroll, M., and Ouellette, L. (2014). Quantifying the rise and fall of complexity in closed systems: The coffee automaton. CoRR, 40.614005..00v.
Abel, D., Barreto, A.. Van Roy, B., Precup, D., van Hasselt, H. P., and Singh, S. (2023). A definition of continual reinforcement learning. Neural Information Processing Systems.
Abel, D., Ho, M. K., and Harutyunyan, A. (2024). Three dogmas of reinforcement learning. Reinforcement Learning Journal, 1.
Baez, C.,, Fong, B.,, and Pollard, B. S. (2016). A compositional framework for Markov processes. Journal of Mathematical Physics, 57(3).
Barreto, A., Dabney, W., Munos, R., Hunt, J. Schaul, T., van Hasselt, H. P., and Silver, D. (2017). Successor features for transfer in reinforcement learning. In Neural Information Processing Systems.
Barto, A. G. (2013). Intrinsic motivation and reinforcement learning. Intrinsically motivated learning in natural and artificial systems, pages 17-47.
Berlekamp, E. R., Conway, H., and Guy, (1982). Winning Ways for Your Mathematical Plays, Vol. 2. Academic Press.
Bialek, W., Nemenman, I., and Tishby, N. (2001). Predictabilityy complexity, and learning. Newral computation, 13(11):2409-244
Chaitin, G. (1966). On the length of programs for computing finite binary sequences. Journal of the ACM, 13:547-569.
Chentanez, N., Barto, A. G., and Singh, S. (2004). Intrinsically motivated reinforcement learning. In Neural Information Processing Systems.
Chomsky, N. (1959). On certain formal properties of grammars. Information and Control, 2(2):13~ 167.
Church, A. (1936). An unsolvable problem of elementary number theory. American journal of mathematics, 58(2):345333,
Conway, J. H. (1970). The game of life. Scientific American, 223(4):4.
Crutchfield, J. P. and Young, K. (1989). Inferring statistical complexity. Physical review letters, 63:105.
Dayan, P. (1993). Improving generalization for temporal difference learning: The successor represen- tation. Neural computation, 5.613-624.
Demski, A. and Garrabrant, S. (2019). Embedded agency. CoRR, abs/1902.00446vv
Dohare, S., Hernandez-Garcia, J. F., Lan, Q., Rahman, P., Mahmood, A. R., and Sutton, R. S. (2024). Loss of plasticity in deep continual learning. Nature, 632:768-774.
Finn, C., Abbeel, and Levine, S. (2017). Model-agnostic meta-learning for fast adaptation of deep networks. In International Conference on Machine Learning.
Flennerhag, S., Schroecker, Y., Zahavy, T., van Hasselt, H., Silver, D., and Singh. S. (2022). Boot- strapped meta-learning. International Conference on Learning Representations.
Friston, J., Daunizeau, J., Kilner, J., and Kiebel, (2010). Action and behavior: A free-energy formulation. Biological Cyberneties, 102:227-260.
Grassberger, P. (1986). Toward quantitative theory of self-generated complexity. International Journal of Theoretical Physics, 25:907-938.
Gregor, K., Rezende, D. J., and Wierstra, (2016). Variational intrinsic control. arXiv preprint arXiv:1611.07507

---

Grossberg, S. and Grossberg, S. (1982). How does a brain build a cognitive code? Studies of mind and brain: Neural principles of learning, perception, development. cognition, and motor control, pages 1-52.
Harutyunyan, A. (2020). What is agent?
Hestness, J., Narang, S., Ardalani, N., Diamos, G., Jun, H., Kianinejad, H., Patwary, M. M. A., Yang. Y., and Zhou, Y. (2017). Deep learning scaling is predictable, empirically, arXiv preprint arXiv:1712.00409,
Hinton, G., Srivastava, N., and Swersky, K. (2012). Neural networks for machine learning. lecture 6a. overview of mini-batch gradient descent.
Hoffmann, J. et al. (2022). Training compute-optimal large language models. CoRR, 1555220
Houthooft, R., Chen, X., Duan, Y., Schulman, J., De Turck, F., and Abbeel, P. (2016). Vime: Variational information maximizing exploration.
Hughes, E.,, Dennis, M. D., Parker-Holder, J., Behbahani, F., Mavalankar, A., Shi, Y., Schaul, T., and Rocktäschel, T. (2024). Position: Open-endedness is essential for artificial superhuman intelligence. In International Conference on Machine Learning.
Hutter, M. (2000). A theory of universal artificial intelligence based on algorithmic complexity. arXiv preprint cs/0004001.
Hutter, M. (2005). Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Probability. Springer, Berlin.
Javed, K. and Sutton, R. S. (2024). The big world hypothesis and its ramifications for artificial intelligence. In Finding the Frame Workshop at Reinforcement Learning Conference.
Jiang, N. (2019). On value functions and the agent-environmen boundary. CoRR, abs//905.... 1334133
Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D. (2020). Scaling laws for neural language models. arXiv preprint arXiv:2001.088
Kingma, D. P. and Ba, J. (2015). Adam: A method for stochastic optimization. In International Conference on Learning Representations
Kirchhoff, M., Parr, T., Palacios, E., Friston, K., and Kiverstein, J. (2018). The markov blankets of life: autonomy, active inference and the free energy principle. Journal of the Royal Society Interface, 15(138):20170792.
Klyubin, A. S., Polani, D., and Nehaniv, C. L. (2005). Empowerment: A universal agent-centric measure of control. In 2005 ieee congress on evolutionary computation, volume 1, pages 128-135. IEEE.
Kolmogorov, A. N. (1965). Three approaches the quantitative definition of information. Problems of Information Transmission, 1:1-11.
Kumar, S., Jeon, J., Lewandowski, A., and Van Roy, B. (2024). The need for a big world simulator: A scientific challenge for continual learning. Finding the Frame Workshop at Reinforcement Learning Conference.
Kumar, S., Marklund, H., Rao, A., Zhu, Y., Jeon, J.J. Liu, Y., and Van Roy, B. (2023). Continual learning as computationally constrained reinforcement learning. CORR, Abs/2307.04344
Lewandowski, A., Bortkiewicz, M., Kumar, S., György, A., Schuurmans, D., Ostaszewski, M., and Machado, M. C. (2025a). Learning continually by spectral regularization. In International Conference on Learning Representations.
Lewandowski, A., Schuurmans, D., and Machado, M. C. (2025b). Plastic learning with deep fourier features. In International Conference Learning Representations.
12

---

Li, M. and Vitányi, P. M. B. (2019). An Introduction to Kolmogorov Complexity and Its Applications, 4th Edition. Texts in Computer Science. Springer.
Lyle, C., Zheng, Z., Khetarpal, K., Martens, J., van Hasselt, H. P., Pascanu, R., and Dabney, W. (2024). Normalization and effective learning rates in reinforcement learning. Advances in Neural Information Processing Systems.
Mesbahi, G., Panahi, P. M., Mastikhina, O., Tang, S., White, M., and White, A. (2025). Position: Lifetime tuning is incompatible with continual reinforcement learning. In International Conference on Machine Learning, Position Paper Track.
Meyer, J., White, A., and Machado, M. C. (2024). Harnessing discrete representations for continual reinforcement learning. Reinforcement Learning Journal, 2:606-628.
Mohamed, S. and Jimenez Rezende, D. (2015). Variational information maximisation for intrinsically motivated reinforcement learning. volume 28.
Nichol, A., Achiam, J., and Schulman, J. (2018). On first-order meta-learning algorithms. CoRR, abs//8003.n 803.02999v3.
Orseau, L. and Ring, M. (2012). Space-time embedded intelligence. In International Conference on Artificial General Intelligence.
Parisi, G. I., Kemker, R., Part, J. L.., Kanan, C., and Wermter, S. (2019). Continual lifelong learning with neural networks: A review. Neural networks, 113:54-71.
Prabhu, A., Torr, P. H., and Dokania, P. K. (2020). GDumb: A simple approach that questions our progress in continual learning. In European Conference on Computer Vision.
Rendell, P. (2011). A universal turing machine in Conway's game of life. International Conference on High Performance Computing & Simulation.
Ring, M. B. (1994). Continual learning in reinforcement environments. PhD thesis, The University of Texas at Austin.
Sajid, N., Ball, P. J., Parr, T., and Friston, K. J. (2021). Active inference: Demystified and compared. Neural Computation, 33:674-712.
Schmidhuber, J. (1991). Curious model model-building control systems. In International Joint Conference on Neural Networks.
Schmidhuber, J. (2010). Formal theory of creativity, fun, and intrinsic motivation (1990-2010). IEEE Transactions on Aulonomous Menial Development, 2(3):230-247.
Shalizi, R., Shalizi, L., and Haslinger, R. (2004). Quantifying oeff-organization with optimal predictors. Physical review letters, 93(1 11111111
Solomonoff, J. J. (1964). A formal theory of inductive inference. Part I. Information and Control, 7:1-22.
Still, S. and Precup. D. (2012). An cefformation-theorette approach to curiosity-driven reinforcement learning. Theory in Biosciences, 131:139-148.
Storck, J., Hochreiter. S., and Schmidhuber, J. (1995). Reinforcement driven information acquisition in non-deterministic environments. In Proceedings of the International Conference on Artificial Neural Networks, Paris, volume 2, pages 1559-164. EC2 & Cie.
Sutton, R. S. (1984), Temporal credit assignment in reinforcement learning. PhD thesis, University of Massachusetts Amherst.
Sutton, R. S. (1988). Learning to predict by the methods of temporal differences. Machine learning. 3:9 44.
Sutton, R. S.,, Koop, A., and Silver, D. (2007). On the role of tracking in stationary environments. In International Conference Machine Learning.
13

---

Thrun, S. (1998). Lifelong learning algorithms. In Learning to Learn, pages 181-209. Springer.
Turing, A. M. (1937). On computable numbers, with an application to the Entscheidungsproblem.. Proceedings of the London Mathematical Society, 42(1):230-265.
Veeriah, V., Zhang, S., and Sutton, R. S. (2017). Crossprop: Learning representations by stochastic meta-gradient descent in neural networks. In Machine Learning and Knowledge Discovery in Databases.
Veness, J., Ng. K. S., Hutter, M., Uther, W. T. B., and Silver, D. (2011). A monte-carlo AIXI approximation. J. Artif. Intell. Res., 40:95-142.
Vereshehagin, N. and Vitányi, P. M. (2010). Rate distortion and denoising of individual data using kolmogorov complexity. IEEE Transactions on Information Theory, 56:3438-3454
Verwimp, E., Aljundi, R., Ben-David, S., Bethge, M., Cossu, A., Gepperth, A., Hayes, T. L., Hüllermeier, E., Kanan, C., Kudithipudi, D., Lampert, C. H., Mundt, M., Pascanu, R., Popescu,
A.. Tolias, A. S., Weijer, J. d., Liu, B., Lomonaco, V., Tuytelaars, T., and Ven, G. M. v. d. (2024). Continual learning: Applications and the road forward. Transactions on Machine Learning Research.
14

---

A Experimental Details for Behavioural Self-Prediction
The code for the experiments can be found at: http://ggtthbbooom//eooowwwwwo/g
interactivity
The problem that we consider involves value function predicting a policy's actions, where the policy is trained to maximize interactivity. Specifically, the policy is trained to produce actions which have large prediction errors for the current static value function but which have low prediction errors for dynamic value function that is continually learned. We consider policy that maps its previous action new action, meaning that there is no external environment providing observations.
The value function, which we restrict to be linear, is tasked with predicting the future behaviour of the policy iteratively and online. At the first timestep, we randomly initialize the parameters of the policy 9g ~ p(0) and of the value function, Wo ~ p(W), using standard distributions for neural network initialization. We then randomly sample the initial action, b0 N 1/d), where d 1000 denotes the dimensionality of the action, b E R The policy, ne, is then trained to maximize its interactivity whereas the value function Vw is trained to predict the policy using TD(0).
The following steps are repeated at each timestep 1
A trajectory of T actions is produced by the policy, Te.-
A copy of the current value function is frozen, and we record the temporal difference errors incurred along this trajectory: { (We+1, 0t),..... S++r (W++7, 0.)). The sum of squared temporal difference errors provides measure of the unconditional algorithmic complexity, K (berlc) = > (W,,,
A copy of the current value function is updated dynamically along the trajec- tory, and record the temporal difference errors incurred along this trajectory: (We+1 ........ S,4r(W (Wirr::)) ()}. Where each Wi+ corresponds to the updated parameters of the value function. The sum of squared temporal difference errors pro- vides measure of the conditional algorithmic complexity, (0(
Σ (W.+.
We update the policy using single step from a gradient- optimizer, maximizing interactivity, but written here minimizing negative interactivity.
((0)
Σ O) 86+4 ( Witt: 0).
We take action using the updated policy, b,41 Oz+1
We update the value function with single step of TD(0) using the temporal difference error, ó, bet1 + 70(bet W.) - v(b.. W.).
A.1 Interpreting Interactivity Maximization As A Continual Learning Benchmark
Our theoretical and experimental results show that maximizing interactivity requires both fast adapta- tion to increase complexity with higher prediction errors and stability to sustain adaptation over time. That is, maximizing interactivity involves the canonical plasticity-stability trade-off of continual learning (Grossberg and Grossberg 1982] Parisi et al.) 2019). Our empirical results demonstrate that deep nonlinear baselines fail at striking this balance, whereas deep linear networks appear to naturally achieve this balance. This suggests that this synthetic benchmark isolates the key challenge in continual learning, while also not requiring outside data or environments. This is significant because few environments are designed specifically to evaluate continual adaptation. Thus, it is suboptimal to stop learning in this setting, regardless of the capacity of the algorithm or function approximator.
A.2 Limitations of Experiments
Our experiments used relatively shallow networks, with a maximum depth of D However, with the meta-gradient calculation over a finite horizon of T 10, the effective depth of the networks
15

---

during auto cooo-d-ffreentiation T = 40. Meta- Meta-gradient methods for deep networks can exhibit more pathological learning dynamics due increased curvature, leading to instability that could partially explain the discrepancy between linear and nonlinear networks. Understanding how to control curvature using only first-order methods is key for effective meta-gradient descent this setting.
The meta-gradient method poses several limitations in scaling. Ideally, would prefer scale both the horizon and the capacity of the function approximator. However, because mela-gradients involve a second-order term (the hessian) and because the effective depth is multiplicative the horizon and the depth of the network, this makes simultaneously scaling both costly. A more promising direction involves bootstrapping meta-gradient (Flennerhag et al. 2022). other first-order approximation NNichol et al. 2018), or more effective regularizers (Lewandowski et al. 2025a).
Experimental evaluation in this setting also requires special consideration. Holding the agent fixed for evaluation, as is commonly done machine learning, is not appropriate given that interactivity is defined as online objective. In addition, standard approaches to hyperparameter tuning may be feasible for evaluating the long-term performance of a continual learning agent (Mesbahi et al. 2025). Overcoming these obstacles more fairly assess dependence hyperparameters would require re-evaluation of several components of empirical practice in machine learning.
B Proofs
Proof of Proposition Let
M
be Turing machine where:
Q is the finite set of states
V is the input alphabet
P is the tape alphabet with Σ' CT
8 Q x Q (L, R} is the transition function
go E Q is the initial state
D' E r is the blank symbol
F S Q is the set of final states
Our proof constructs an algorithmic Markov process, & = (2,, E, Specifically, it involves showing how the Turing machine can be represented on state-space Ω with its transition function represented in the Markov transition function, T.
Constructing the state-space (?))
Let = 7 denote the integers for tape positions, Σ ((QU((") x ( where D is the Markov blank symbol. Then each w E Ω represents a complete Turing machine configuration by encoding the tape contents each position, the current state and head position.
Specifically, for a TM configuration with state q, head at position h, and tape contents ...a- jagd]..... we define:
(g. (O",a) ae)
if h (head position) if E / h and ag A O otherwise
w(E)
Constructing the transition function (T)
The Markov transition T(w) simulates one step of the Turing machine. It first finds the head position where w(h) = (g, a) for some E Q, a E Т. It then applies the Turing machine transition: 8(g.a) a) (d' a', d) where d R). Lastly, we construct w/ by:
* Setting w'(h) (L", a') (write new symbol)
16

---

Setting wh(h (h + offset(d)) = (q', b) where
b = c
if (h + offset(d)) = (D".c) for some e E
if wh + offset(d)) 0
and offset( L) offset(())))) R)
Leaving all other positions unchanged: w' w(E) for & (h, + offset(d))
At initialization, have that the initial tape contents is finite and thus |w/| co. At each step, the state remains finite, |w'| < oc, because each step changes at most 2 positions. Note also that T is computable in (ppoly[[=()); finding the head and updating positions requires linear scan and constant updates.
Proof of Proposition We prove each part in sequence.
Part 1: The automaton is equivalent to k-horizon boundaried Markov process.
Given that (+)= X, the k-step transition dynamics the internal state space Ul depends only on the current internal state and the current observation.
We define two k-horizon boundaried Markov process. First, for the internal statel, have: Ele = (St Xxx ) where (0,,)) = u(z;0). Next, for the policy, we have: Ely = (2) xue,, T where (y, 0, == π (x;
That is, both the policy, т, and the internal state update function, u, is simulated by the k-step composition of the environment's transition function. By the definition of uniform locality and the condition (+)) X, the step transition on fi is fully determined by the current internal state E 0 and the boundary z E f This establishes the equivalence.
Part 2: The automaton's environment is a partially observable Markov decision process.
For the automaton specifically, the environment consists of:
State space:
Action space: The output space 2/
Observation space: The input space 2|x
Transition function: Given the current environment state, the automaton's 's action y E 2ly, the next environment state follows from T
Observation function: The automaton observes x E Ω| from the current environment state
Since the automaton only observes Q|x and not the full environment state Ω this constitutes partial observability. The Markov property holds for the underlying environment state transitions via T.
Part 3: The automaton's interaction is equivalent
stateful policy acting the environment.
The automaton maintains an internal state E Ule and produces actions via the output function 22x x Rl 02y. This defines stateful policy, π (2;; 0), where the internal state is updated according to:
0++1 u(x;; 1.-1).
This is precisely the definition of stateful policy in partially observable environments, where the policy maintains internal memory (the substate f) and conditions its actions on both observations and this internal state.
Proof of Proposition An embedded automaton has finite number of states, which upper bounded by the size of its internal state space, |e). This upper bounds the number of unique
17

---

configurations that the internal state space can take, which thus upper bounds the capacity of the automaton.
Thus, the automaton's 's capacity is constrained to be upper bounded by number of states that is less than (0), which is finite.
Forthermore, an embedded automaton is only capable a limited form of computation relative to the partially observable Markov decision process. An embedded automaton is equivalent to finite-state machine. This means that the automaton only capable of recognizing a regular language. The partially observable Markov decision process that it faces, however, is computationally universal and equivalent in power to a Turing machine (by Proposition 1). This means that the environment swursively-enmmeratee
can, in general, generate implicitly computationally constrained, because of the separation between finite-state automata and the turing-complete environment in the Chomsky hierarchy (Chomsky) 1959).
language. The embedded automaton is thus
Thus, for sufficiently long behaviour sequence, the automaton must eventually return to a previous state (i.e., I' >> (0) by the pigeonhole principle. Any behavioural sequence with period longer than O cannot be represented by the automaton.
Thus, an embedded automaton simulated in universal-locee environment is implicitly constrained: there exist onput-output behaviours that it cannot realize.
See also:
Proof of Theorem 7
We denote the capacity of the automaton as C(A), and denote the maximum achievable T -hhorizon interactivity for given automaton as,
max (AA bo:t 1)-
interactivity is determined by the dependence between the past and future behaviour of the automaton. This behaviour is determined by a substate-space that grows with the horizon (T). Specifically, the future behaviour of an embedded automaton is determined by (i) the universal- local environment's ss transition function, (ii) the embedded automaton's 's initial internal state, and (iii) sobstate-space of the environment that grows with the horizon of behaviour considered. If an embedded automaton's 's past behaviour were predictive of its future behaviour of given horizon, then would also imply that its past behaviour predictive of a mubstate-space growing with that horizon. For large enough horizon, the size of this substate-space will eventually be larger than the capacity of the automaton. An embedded automaton with a given capacity cannot maximize interactivity beyond given horizon, meaning that it actively faces an implicit capacity constraint.
Intuition:
Formally: automaton with sufficiently high interactivity will produce behaviour with high unconditional Kolmogorov complexity, IK (bbb+T--i) + 0(1) > C(AA), where O(1) is a constant independent of the automaton. Because the behaviour is generated by the automaton, we know that the Kolmogorov complexity is also upper bounded by the capacity, C(A) + 0(1) > K(bes4T-1).
Thus, can upper bounded interactivity in terms of the unconditional complexity.
Iy (Al2,, bu.t-1) (K(baatT-1) K(bra4r-11 bu:
< K(bearr-1)
Which uses the fact that the conditional algorithmic complexity is positive, K(batt--1 boa-1) > 0. Next we use the fact that the Kolmogorov complexity of a sequence produced by an automaton is upper bounded by its capacity, which implics that,
max (Als, boa-1) S K(bbatt-1) (CA)) O(1) A
Lower Bounding Interactivity By Capacity
For the lower bound, we provide constructive proof in which we show how an automaton can scale a lower bound on its interactivity proportional to its capacity.
18

---

In particular, the automaton will use brute-force method which simulates a much smaller automaton along with a stored history. That is, a subroutine will simulate an automaton with capacity (A(.). where a < 1. The automatinn will use its remaining capacity to store on the order of (1 - (A) of the previous input-output pairs. It then runs an enumeration strategy as subroutine, which simulates the smaller automaton with capacity (A)) Specifically, the subroutine enumerates over all possible T-horiion futures and selects the next output that maximizes the resulting T' horizon unconditional complexity and minimizes the T'horizon conditional complexity with respect to the stored history of length (1 - ar) ()A) While this is computationally expensive, we can choose a to be small enough that this is possible. The interactivity achieved in this setting is thus,aC(AA) O(I)
Putting these together, we have the lower and upper bounds of:
- < max (r)aa,, S ((b (C(A))
A
Proof Theorem 2 We provide a proof for each of the two desiderata
(i) The first property follows from argument that is similar to Theorem I1 but adapted to learning agent, A. with some bounded capacity C((A). We are interested in what interactivity the best such agent can achieve, m 1ly (AAx,, bu:t-1).
bounded agent that maximizes its interactivity will have non-zero unconditional relatt-ela complexity. (be > 0 (otherwise, its interactivity would be zero). This implies that the unconditional Kolmogorov complexity of its behaviour is on the order of the the capacity of the agent, ((b.:e+--))) 2 C(A) O(1), where O(1) is a constant independent of the agent. Because the behaviour generated by the automaton, we know that the Kolmogorov complexity also upper bounded in terms of the capacity, C(A) O(1) 2 K(bb.TT-1)-
Such an agent will also have low conditional agent-relativized complexity (otherwise, its inter- activity would be low), An optimal learning agent that minimizes the agent-relativized com- O, has conditional Kolmogorov complexity is strictly less than the capacity of the agent, ((bbestT-lbbo---
plexity, (b
< C(A). In fact, we have, for a < 1, that (bbbarr-1 b) S aC(A). This is because the agent can only use fraction of its capacity on predicting its future behaviour (in addition to making predictions, an agent selects actions, and updates its substate).
Taken together, we have that the performance of an interactivity-seekingg agent interactivity is upper and lower bounded by capacity,
(1 a)CA) - 0(1 < max IT (Al <
An agent with a given capacity cannot maximize its interactivity without increasing its capacity. Thus, a bounded agent that seeks to maximize its interactivity through learning is limited by its finite capacity constraint.
(ii) For the second property, we demonstrate the necessity of continual adaptation for maximizing interactivity, by considering the role of the embedded agent's 's transition function.
Continual Adaptation in Automata
First we consider the finite-state automaton, A, and how its substate transition function, u, encodes its learning. An automaton agent that has stopped lcarning is thus equivalent to one that stops updating its internal state. In this case, the automaton's 's internal state remains constant zy 2 for all t' > t. A finite-state automaton has a capacity on the order of C(A) E O(poly(AA)). But, a finite-state automaton that does not update its internal state, denoted by A-, has a reduction in its capacity. In particular, the capacity is reduced to C(A-) = 0(12)x 1). because the terms needed to encode the transition function no longer needed for automaton that does not use the transition function. Using the upper bounds on interactivity from the Theorem 1, we conclude that an agent that stops learning reduces its future output complexity from O(1 A|ll|||loggg log (ll) O(IAa)). Thus, is suboptimal to stop learning.
Continual Adaptation in Reinforcement Learning Agents
19

---

Value parameters: If the parameters of the value function stop being updated. the interactivity objective immediately collapses 0.
Policy parameters: Suppose the policy's parameters stop being updated, meaning that the policy becomes fixed. Then the sequence of actions taken by the fixed policy becomes Markov process, which is predictable. Under the Markovian dynamics induced by fixed policy, the value function could converge an optimal static prediction of the future behaviour. This would lower both the unconditional Kolmogorov complexity and interactivity. Thus, an agent maximizing interactivity is suboptimal it stops updating its policy parameters.
C
Additional Background and Related Work
C.1 Additional constraints embedded agents
There are two additional ways in which embedded automaton is implicitly constrained:
1. Minimum size:
The size of embedded automaton, including the size of its input and output spaces, cannot be arbitrarily small, and thus there exists a minimum size. This implies that the automaton cannot read and write to arbitrarily small parts of the environment, constraining its observation and action spaces.
2. Simulation time: Simulating embedded automaton in universal- environment may also incur a simulation overhead. This constrains the automaton by the fact that several transitions in the environment may be necessary simulate single transition for the automaton.
While the embedded automaton is computationally constrained relative to its environment, these two additional constraints limit the information made available to the automaton about the environment. Specifically, an automaton generally cannot observe, process and output information at the same granularity, or at the same timescale, as the environment because of constraints on its size and its simulation time.
C.2 Algorithmic complexity
The Kolmogorov complexity (Kolmogorov 1965 Solomonoff 1964 Chaitin 1966) of an object (encoded as a binary string) is the length of the shortest program that computes and halts. Unlike traditional information theory, it measures the complexity of an individual object without depending on a stochastic source or ensemble.
The Kolmogorov complexity of a string depends on the choice of a universal Turing machine. However, since any universal Turing machine can simulate another (e.g., via a compiler), the choice of the machine affects the Kolmogorov complexity by, at most, an additive constant independent of the specific string (Li and Vitányi 2019).
Kolmogorov complexity is closely tied to compression, where the shortest description represents the efficient compression for the given universal Turing machine. Although Kolmogorov complexity is uncomputable, it is possible to compute improving upper bounds by searching over all possible programs parallel and tracking the shortest candidate that generates the target string (Li and Vitányi
2019
C.3 AIXI
AIXI defines general Bayes-optimal reinforcement learning agent in an unknown computable environment (Hutter 2005). In this framework, the environment represented by Turing machine with unidirectional input and output tapes, and bidirectional working/internal tapes. The agent's s actions are received by the environment on its input tape, based on which can write a computable history-basee based reward and observation on its output tape.
20

---

The AIXI agent acts in a Bayes-optimis manner by planning based on posterior estimate over all computable environments, using Solomonoff's universal prior as starting point (Solomonolf) 1964). This prior assigns higher probability 'simpler' environments-those with lower Kolmogorov complexity. However, both Solomonoff's prior and AIXI are incomputable, making the development of practical approximations within this framework key area of interest (Veness et al. 2011).
C.4 Connections to intrinsic motivation and the free energy principle
Previous work has explored several intrinsic drives that can guide agent behaviour without the need for explicit external rewards (Schmidhuber 2010 Barto 2013). Many approaches to intrinsic motivation are developed within the framework of traditional RL, where the agents are not constrained relative to the environment. As result, these approaches may not be well-suited to big world. Nevertheless, interactivity shares connections ideas such as mutual information maximization in intrinsic motivation.
The information gain of a dynamics model can serve as intrinsic or auxiliary reward, promoting curious exploration (Storck et al. 1995 Houthooft et al. (016) Unlike curiosity driven by information gain, the goal of interactivity
learn an accurate model of the world.
Another related concept is Empowerment (Klyubin et al. 2005), where an agent seeks to maximize its control over its environment. Emnpowerment-seeking agents aim to maximize the mutual information between their actions and future states. Such agents avoid states where their actions have low influence and prefer states that allow for wide range of controllable outcomes. This objective can also be used to learn a set of behaviours (or options) that lead to different final states (Mohamed and Jimenez Rezende 2015 Gregor al. (016). As discussed earlier, agents produce complex yet predictable behaviour, which is not directly tied to the concept of control. Furthermore, unlike objectives grounded in traditional (Shannon) information theory, interactivity relies on asymmetric algorithmic mutual information between previous inputs and future outputs.
Active inference describes agentic behavior in partially observable environments the minimization of free energy (Friston et al,, 2010;; Sajid et al. (02I). Free-energy minimization prefers selecting actions that lead to highly predictable states-inputs that unsurprising to the agent's model. In contrast to free-energy minimization, maximizing interactivity actively discourages low-complexity predictable states.
C.5 Relationship to other notions of boundaries and Markov processes
The boundaried Markov process that we define is also similar to other frameworks which introduce explicit boundaries. Active inference, for example, considers Markov blanket that separates probabilistic nodes directed acyclic graph as a way of separating the agent from its environment (Kirchhoff et al., al.],221. 2018). Open Markov processes have also been defined which have explicit boundary states from which probability can flow in and out of (Baez et al. 2016). Our work applies similar ideas specifically in the computational setting that consider.
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: the discussion, the limitations of an efficient algorithm for maximizing ineractivity discussed.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
22

---

Justification:
Yes, in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Yes, in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
23

---

Answer:
[NA]
Justification:
Not currently in the supplementary material, but we plan to open source it.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /pipps.cc/pullc//uuui wwwiii/gguie///eeeeeeoeic CoodeSubeiiie ssi wsionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: In the appendix and supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Shaded error bars are provided, but no statistical p-test.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: No, only a local cluster was used which did not log computational resources, but they can be replicated modern GPU in less than 24 hours.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: https://neurips http:///wwr....cpaaaaacccccceeea
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: does not, as it is purely theoretical investigation.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
25

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: None of these were used.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: Not used.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
26

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
27

---

Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [No]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
28


Reviews:
[{"review_id": "ifK7TJBeBW", "reviewer": "Reviewer_X3Zz", "summary": "Authors define a class of environments, \"universal Markov environments\" equivalent to universal Turing machines, and a \"locality\" condition. Authors then formalize agents/automata within these environments, and define interactivity as a complexity-theoretic measurement of the ability to adapt future behavior to past experience. Authors further define agent-relativized complexity and show they can approximate this with a value function trained with RL TD learning. Authors prove that agents with the goal of maximize interactivity necessarily employ continual learning; stopping learning is necessarily suboptimal. Authors implement this method on an environment.", "questions": "- Which definitions have already been defined in the literature, and which parts are novel contributions?\n- Section 1 states that \"Interactivity is similar to previously considered intrinsic motivation objectives 70 (Chentanez et al., 2004; Schmidhuber, 2010), and specifically predictive information (Bialek et al., 71 2001; Still and Precup, 2012). However, interactivity differs because of its formulation in terms 72 of behaviours using Kolmogorov complexity. This makes interactivity better suited to sequential 73 decision making in the constrained and partially observable setting that we consider.\" Is there a reason predictive information is less-well suited to sequential decision making? I would have thought that interactivity being defined based on Kolmogorov complexity would make it _worse_ for decision making settings.\n- I would explicitly define \"capacity\".\n- Is RL the most natural technique to learn in these environments?", "limitations": "- Interactivity can only be measured through an approximation, the utility of which is unclear.\n- Experiments showing the usefulness of these measures are not robust.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The idea of universal-local environments is interesting, and I like the example of Conway's Game of Life. I like the idea of having a general computational framework that can describe agency in terms of complexity.\n\nWeaknesses\n- I'm unsure if Kolmogorov complexity is the right complexity measure to use to describe agency- it may be, but it is also very general and uncomputable. It's unclear if the approximation the authors define is useful for applications.\n- I don't think \"implicitly constrained\" is defined sufficiently.\n- I'm not sure the authors explain why interactivity is a measure that should be optimized, beyond that it is a measure that requires continual learning by Theorem 2.\n- Weak experiments: There is just one set of experiments in Figure 4, and they are not described in Section 6 in sufficient detail. For example, the nature of the environment is not described.", "was_revised": true, "final_justification": "The authors addressed my questions about the use of Kolmogorov complexity and interactivity, as well as my concern about the experiment. Because of this, I will raise my rating to 4.", "rebuttal": "We are glad to hear that the reviewer found our submission interesting, and we thank them for going through our paper in detail. We address your individual questions below. Please also see our shared reply for more details regarding our experiments.\n\n\n>I'm unsure if Kolmogorov complexity is the right complexity measure to use to describe agency- it may be, but it is also very general and uncomputable. It's unclear if the approximation the authors define is useful for applications.\n\nThanks for the opportunity to clarify. To be clear, the idea behind interactivity is to characterize agency in terms of future behaviour that is predictable from past behaviour. We use Komogorov complexity as a tool to measure the predictability of an agent’s behaviour sequence. You’re correct to point out that this is a general approach, like previous work at the intersection of algorithmic information theory and AI (AIXI), and we see this generality as a strength. We also would like to emphasize that Kolmogorov complexity and interactivity is computable for an embedded automaton, and for a bounded agent. Crucially, we show that an agent can approximate this quantity using reinforcement learning. \n\n>I don't think \"implicitly constrained\" is defined sufficiently.\n\nThanks for raising this point. We will include an explicit discussion of “implicitly constrained” in the paper. Briefly, implicit constraints refers to constraints that are not explicitly imposed in the agent's objective (e.g., autonomous vehicles routing passengers have a constraint in their objective to follow traffic rules). Rather, these constraints emerge between the agent and its relationship to the environment. For example, a robot with a broken sensor is implicitly constrained by that broken sensor. This constraint is not reflected in its objective or algorithm, but can be detected by the agent through its now limited ability to sense the world.\n\n>I'm not sure the authors explain why interactivity is a measure that should be optimized, beyond that it is a measure that requires continual learning by Theorem 2.\n\nWe first motivated interactivity as a measure of an agent’s ability to learn from experience: \n\n[line 199-200]: An agent’s capability for learning can be characterized by its ability to adapt its future behaviour using its past experience. We propose interactivity to measure an embedded agent’s intrinsic ability to adapt its future behaviour, towards higher complexity, conditioned on its past behaviour.\n\nAgents with high interactivity are those that use their past experience to predict and then adapt their future behaviour. We position this as a continual learning task, but  incentivizing this type of adaptive behaviour could be useful for designing reinforcement learning agents that interact with their environment to discover what can and cannot be predicted or controlled. Our current work is the first step in understanding the challenges in this objective, and we are excited at the prospect of interactivity as an RL auxiliary objective in future work.\n\n>Weak experiments: There is just one set of experiments in Figure 4, and they are not described in Section 6 in sufficient detail. For example, the nature of the environment is not described.\n\nWe would like to point out that our experiments are in a highly novel task that combines online learning, reinforcement learning, meta learning and continual learning. In fact, Reviewer sAho commended us for generating results at all. Moreover, additional details regarding the experiments were included in Appendix B. \n\nWe have also added additional results which you can find under [EXP1] (Due to space, it is in another comment).\n\n>Which definitions have already been defined in the literature, and which parts are novel contributions?\n\nWe will make the following more clear in our submission: Definitions 1 and 2 have been defined in the literature, and the remaining are novel contributions. Definitions 3,4 and 5 develop the key tools for characterizing the universal-local environment that we consider. Definition 6 is similar to the standard automaton, but defined on our universal-local environment. Definition 7 is similar to the standard conditional Kolmogorov complexity, but adapted to the automaton embedded in the universal-local environment.\n\n>Section 1 states that \"Interactivity is similar to previously considered intrinsic motivation objectives 70 (Chentanez et al., 2004; Schmidhuber, 2010), and specifically predictive information (Bialek et al., 71 2001; Still and Precup, 2012). However, interactivity differs because of its formulation in terms 72 of behaviours using Kolmogorov complexity. This makes interactivity better suited to sequential 73 decision making in the constrained and partially observable setting that we consider.\" Is there a reason predictive information is less-well suited to sequential decision making? I would have thought that interactivity being defined based on Kolmogorov complexity would make it worse for decision making settings.\n\nThis is a great question, and we appreciate the opportunity to elaborate. Predictive information, and other notions from Shannon entropy, are defined for stationary probability distributions. In our setting, we do not assume any stationary probability distribution, as this is not always well-defined in a computable environment [1]. Kolmogorov complexity, and other tools from algorithmic information theory, are better suited to this setting as they are defined for sequences, rather than probability distributions. There is a long history of using this approach for understanding the limits of AI agents [2].\n\n>I would explicitly define \"capacity\"\n\nThank you for the suggestion! In our computational framework, capacity is measured by the size of the automaton’s state-space. We will clarify this in our submission, as this is an important point. The size of an automaton’s state-space fundamentally bounds the complexity of the behaviour that can be produced.\n\n>Is RL the most natural technique to learn in these environments?\n\nThere are three components that make reinforcement learning a natural fit: 1) the environment is a partially-observable Markov process, 2) the agent’s objective involves a long-term prediction, like a value function, 3) the agent’s performance depends on its behaviour sequence, meaning that it needs to explore and learn through trial-and-error. For these reasons, reinforcement learning provides the right problem characterization, as well as algorithms as we demonstrate in our approximation.\n\n>Interactivity can only be measured through an approximation, the utility of which is unclear.\n\nWe want to be clear that this is largely true for several other quantities in machine learning, such as optimal value functions and variational lower bounds. Interactivity is a value function, and we generate Monte-Carlo estimates in our experiments just as is done in calculating the return in policy gradient. In addition, our approximation maximizes a lower bound, which is a theoretically sound approach to optimization, like in variational lower bounds.\n\n>Experiments showing the usefulness of these measures are not robust.\n\nWe want to highlight that our results are not about measures being robust, as our results show the performance of conventional algorithms on our proposed task (maximizing interactivity). Our results simply highlight the difficulty of applying standard learning algorithms, showing that they are unable to sustain learning continually.\n\n\n[1] Müller, Markus. \"Stationary algorithmic probability.\" Theoretical Computer Science 411.1 (2010).\n\n[2] Hutter, Marcus. \"A theory of universal artificial intelligence based on algorithmic complexity.\" arXiv preprint cs/0004001 (2000)."}, {"review_id": "W9qUHhVygy", "reviewer": "Reviewer_sAho", "summary": "In \"The World Is Bigger: A Computationally-Embedded Perspective on the Big World Hypothesis\" the authors propose a new general problem setting for studying (a version of) the continual learning problem. This is achieved first by defining what the author's call a \"universal-local environment\" into which an agent may be embedded. The embedded agent is explicitly constrained by construction and is shown to be representable as a POMDP. Furthermore, an intrinsic new measure is proposed for assessing the agents ability to adapt to its future environment, and that maximizing this measure is structurally a continual RL problem.", "questions": "1. Any idea why \"(linear methods) ... always lead to performance collapse\"?\n2. Interactivity as defined appears to be one sensible measure, were others considered and rejected?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n* The paper presents what I would consider to be a bold contribution to the continual learning area\n* The paper presents a valuable extension (in spirit at least) to AIXI, which was an important conceptual contribution to the field\n* The formalism for much of the work in the continual learning set up is ad hoc, and this is a contribution towards placing those efforts on more stable grounds\n* The paper's motivation and writing are clear (if perhaps its technical presentation might be improved slightly) \n* The authors are to be commended for generating *results* from their construction (i.e. presenting an end-to-end utilization of the setup) with all that that entails\n\n\nWeaknesses:\n* Beyond an abstract theoretical construction it is not immediately clear to me if this will be of practical use to the community. Beyond the recovery of the \"common desideratum of the continual learning problem\"(which indeed is likely by explicit construction) it's not clear that studying agents/algorithms in this setting will provide insight to real-world systems\n* There are a lot of contributions here: the idea of \"universal-local\" environments, the definition of boundaries Markov processes, how to embed agents therein, demonstrating that this embedded construction has the desired properties and representations, the introduction of a suitable objective measure, and how that may be solved with TD methods etc., but with all that said, the empirical results feel almost incidental, and indeed weakly supported. \n* Minor typos here and there:\n> typo: line 76: \"Interactivity (as) viewed...\" -or- \"Interactivity (when) ~can be~ viewed from...\"\n> typo: line 325 \"... algorithms that stops learning...\"\n> type: line 327 \"We trained two a linear network and a non-linear network...\" (trained two what?)\n> typo: line 352 \"... is not be appropriate...\"", "was_revised": true, "final_justification": "The authors have improved the strength of the paper and clarified some important issues in their rebuttal. The rebuttal responses improve the clarity and justification for some of the choices made in the paper, and improved the experimental coverage to a level more suitable for a theoretical contribution. I'm increasing my score from a 4-boarderline, to a 5-accept.", "rebuttal": "We would like to thank the reviewer for their insightful comments and questions. We particularly appreciate you referring to our work as a bold contribution, and your recognition of how our work builds on and expands the foundation for continual learning. We have addressed your concerns below. And, we also use some of this rebuttal for additional details regarding our experiments.\n\n>Beyond an abstract theoretical construction it is not immediately clear to me if this will be of practical use to the community. Beyond the recovery of the \"common desideratum of the continual learning problem\"(which indeed is likely by explicit construction) it's not clear that studying agents/algorithms in this setting will provide insight to real-world systems\n\nWhile our approach is more on the abstract side, the behavioural self-prediction task provides a new way to evaluate an algorithm’s capability for continual learning. That is, rather than the current standard practice in continual learning where non-stationarities are designed, our proposed task evaluates a learning algorithm's ability to create its own nonstationarity. This is significant because it captures an important aspect of real world data, which  is often nonstationary yet predictable.\n\n>There are a lot of contributions here: the idea of \"universal-local\" environments, the definition of boundaries Markov processes, how to embed agents therein, demonstrating that this embedded construction has the desired properties and representations, the introduction of a suitable objective measure, and how that may be solved with TD methods etc., but with all that said, the empirical results feel almost incidental, and indeed weakly supported.\n\nPlease see our shared reply on the experiments, including a description of new results.\n\n>Minor typos here and there:\n\n\nThank you for catching these!\n\n> Any idea why \"(linear methods) ... always lead to performance collapse\"?\n\nThanks for bringing this up, it is a subtle point that we want to discuss further. The fact that linear methods collapse in performance is surprising compared to the stability of linear methods in reinforcement learning and continual learning. One explanation is that learning with meta-gradients and a linear network is similar to learning with gradients and a deep nonlinear network. In our shared reply we discuss this point further, and strategies we found effective in stabilizing learning.\n\n> Interactivity as defined appears to be one sensible measure, were others considered and rejected?\n\nThere are three levels to this question: \n- Our starting point was to measure the “predictable complexity” of future behaviour, and the motivation behind this was to characterize adaptive behaviour.\n- Kolmogorov complexity-based interactivity for finite automata is one representation of this idea. An alternative that we considered is algorithmic/Solomonoff probability of a given sequence, which can be defined on the environment as the log of the number of environment configurations that produce that sequence. The advantage of this approach is that, once defined with respect to our environment, it provides better intuition and can be visualized. The disadvantage of this approach is that it is not as well-known as Kolmogorov complexity, and would require more space for elaboration.\n- Finally, in the approximation to interactivity using reinforcement learning, we used an average reward formulation. However, we also considered a discounted approach. The advantage of discounting is that it is more familiar to RL researchers, and there are more well-known algorithms for the discounted settings. The disadvantage is that discounting would introduce more approximation, given that interactivity was defined without discounting.\n\n\n### [EXP1] We also included additional results with activation functions that have been found to be stable for continual learning:\n\nWe found that ReLU activations struggle to sustain their interactivity. While linear activations are not able to achieve as high interactivity, they are relatively stable. CReLU and Tanh seem to balance stability and performance, whereas a sinusoid is the least stable and was the only activation function to diverge.\n\n| Method | Iteration 2500 | Iteration 5000 | Iteration 7500 | Iteration 10000 |\n|---|---|---|---|---|\n| deep linear | 0.017 (0.002) | 0.016 (0.003) | 0.014 (0.002) | 0.019 (0.004) |\n| relu | 0.012 (0.003) | 0.017 (0.005) | 0.012 (0.003) | 0.008 (0.002) |\n| leaky | 0.015 (0.004) | 0.024 (0.007) | 0.030 (0.008) | 0.010 (0.003) |\n| sin | 0.017 (0.008) | 0.029 (0.009) | 0.016 (0.006) | 0.007 (0.006) |\n| crelu | 0.012 (0.003) | 0.010 (0.002) | 0.011 (0.002) | 0.019 (0.005) |\n| tanh | 0.017 (0.003) | 0.021 (0.005) | 0.021 (0.005) | 0.022 (0.006) |\n\nThe following results include double the number of iterations with layer norm. We found that higher interactivity could be achieved with layer norm. In continual learning, layer norm is helpful in ensuring that activations stay active throughout training. However, nonstationarity with layer norm can also have the effect of slowly lowering the effective learning rate and thus slowing learning. You can see that initial performance decreases over time for most nonlinear activation functions, indicating that the initial benefit of layer norm diminishes due to the nonstationarity.\n\n| Method | Iteration 5000 | Iteration 10000 | Iteration 15000 | Iteration 20000 |\n|---|---|---|---|---|\n| deep linear + LN | 0.057 (0.012) | 0.047 (0.010) | 0.034 (0.008) | 0.055 (0.015) |\n| relu + LN | 0.062 (0.010) | 0.046 (0.009) | 0.028 (0.006) | 0.033 (0.008) |\n| leaky + LN| 0.071 (0.012) | 0.050 (0.009) | 0.038 (0.007) | 0.039 (0.007) |\n| sin + LN | 0.062 (0.010) | 0.025 (0.005) |\n| crelu + LN| 0.077 (0.013) | 0.047 (0.010) | 0.030 (0.006) | 0.032 (0.006) |\n| tanh + LN| 0.109 (0.020) | 0.055 (0.012) | 0.045 (0.011) | 0.060 (0.014) |"}, {"review_id": "XKL72sNJ82", "reviewer": "Reviewer_CJca", "summary": "The paper proposes a framework to think about agent/environment design by considering how the agent is embedded into the environment, and how the agent’s capabilities of computation are inherently limited based on how the agent is embedded in the environment. It proposes an intrinsic measure of interactivity which determines what the agent should be optimizing to learn more about its environment.", "questions": "Is the main idea the following: we treat the environment as a computing machine, which contains the agent (automaton), which is also a computing machine. Then since the agent is embedded in the environment, its computation abilities are upper bounded by what the environment allows and what it presents to the agent (partial observability). And then finally, the goal is for the agent to maximize interactivity, which is basically about learning about a future that is maximally complex (since more to learn about) but also you want your past to reduce complexity of future (since it tells us that the past behaviors were “useful”.", "limitations": "Yes the paper acknowledges the computational limits of the algorithm to maximize interactivity.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- Very unique paper and brings valuable insights.\n- The paper is systematic and I think the ideas presented in this paper are deep. It would be a nice addition to the conference.\n- I like that the experiments use self-prediction as a loss since it is aligned with intrinsic motivation losses.\n- The relaxation to measure complexity conditioned on some horizon H is clever to make this metric more practically useful (Section 5.3)\n- I appreciate the measure of interactivity is based on the undiscounted average reward setting, which is also an underappreciated/less studied setting.\n\nWeaknesses\n- The empirical results seem a bit rushed. I understand the focus does not have to be on a full empirical analysis, but I think some of the discussion from Appendix B2 should be moved up and the discussion should relate the results to the main thesis of the paper better.\n- The surprising finding of instability of linear methods is also not discussed as much, and deserves some more attention.", "was_revised": true, "final_justification": "This paper is unique and introduces a topic/discussion that I think will bring value to the community. It allows us to step back and think about the problem generally rather than trying to beat SOTA every time.", "rebuttal": "Thank you for your review! We appreciate you referring to the ideas that we develop as deep, as well as your summarization of the main narrative of our paper. We address your questions below:\n\n\n>The empirical results seem a bit rushed. I understand the focus does not have to be on a full empirical analysis, but I think some of the discussion from Appendix B2 should be moved up and the discussion should relate the results to the main thesis of the paper better.\n\nThanks, we agree that more detail in the main paper would improve clarity. The goal of our paper was to characterize a problem setting that requires continual adaptation. Our characterization was theoretical, and the experiments that we generated were in a fairly novel setting that combines online learning, reinforcement learning, meta learning and continual learning. The space constraint made it challenging to include all the details. In fact, Reviewer sAho commended us for generating results at all.\n\nMoreover, we report additional results under the section titled [EXP1] in our reply to sAho. \n\n>The surprising finding of instability of linear methods is also not discussed as much, and deserves some more attention. \n\nWe agree that this is an interesting detail that can use further elaboration. The fact that linear methods collapse in performance is surprising, but one explanation is that even a linear network effectively becomes a deep nonlinear network when learning with meta-gradients. In our updated experiments, we show that learning can be stabilized.\n\n>Is the main idea the following: we treat the environment as a computing machine, which contains the agent (automaton), which is also a computing machine. Then since the agent is embedded in the environment, its computation abilities are upper bounded by what the environment allows and what it presents to the agent (partial observability). And then finally, the goal is for the agent to maximize interactivity, which is basically about learning about a future that is maximally complex (since more to learn about) but also you want your past to reduce complexity of future (since it tells us that the past behaviors were “useful”.\n\nYes, that is a great summary of the primary narrative in our submission! The three key ideas are the characterization of the universal-local environment, the embedded agent and the relationship between them (the interactivity objective). We also go one step further by taking this characterization and developing a reinforcement learning approach to maximizing interactivity."}, {"review_id": "YIGUdECTKT", "reviewer": "Reviewer_Hb59", "summary": "This paper introduces a theoretical framework for continual learning based on the big world hypothesis, where agents are implicitly constrained by being embedded within a computationally universal and local environment. The authors formalize such agents as embedded automata and define a new objective called interactivity, which uses Kolmogorov complexity to quantify how much an agent’s future behavior can be both complex and predictable from its past. They prove that any finite-capacity agent maximizing interactivity must continually adapt, as stopping learning is provably suboptimal. To operationalize this, they develop an RL algorithm that approximates interactivity via prediction error and evaluate it on a synthetic behavioral self-prediction benchmark, where an agent learns from its own nonstationary experience stream. The work is mostly theoretical but provides a novel, general perspective on continual adaptation without requiring explicit task boundaries or external rewards.", "questions": "1. Your use of universal-local environments (e.g., Conway’s Game of Life) is well-motivated as a constructive proof that embedded agents can exist. However, it’s not entirely clear why locality is essential beyond enabling the embedding. Could you clarify whether locality plays any further role in shaping the agent’s adaptation dynamics or in bounding interactivity?\n2. The proposed interactivity measure uses Kolmogorov complexity and is approximated via agent-relative prediction error. How general is this framework in practice? For instance, would interactivity remain a meaningful or tractable objective in high-dimensional or real-world sensory domains (e.g., vision, language)? What kinds of practical approximations might be required?\n3. Your behavioral self-prediction benchmark is clean and well-motivated, but it lacks comparisons to continual learning baselines. Can you elaborate on why existing baselines (e.g., EWC, replay buffers) were not included, and what challenges prevent comparison?\n4. Your learning algorithm for interactivity involves a form of bi-level optimization (meta-gradients), which is known to be expensive and unstable. Could you clarify whether this is essential to your formulation, or whether simpler approximations (e.g., first-order variants, bootstrapped objectives) might suffice?\n5. Your current experiments only include 2-layer networks. What's the rationale behind this choice, and how does the method extend to deeper networks?", "limitations": "- Practical Scalability:\nThe paper proposes an elegant but computationally heavy optimization procedure. While the authors mention second-order complexity and meta-gradients, they do not discuss the practical infeasibility of scaling to larger models. A clearer discussion of how the method might break down or require approximation in such settings would be valuable.\n- Limited Empirical Validation:\nThe synthetic benchmark is theoretically motivated but very narrow in scope. The authors should discuss whether their current results demonstrate efficacy beyond toy settings, and that future work is needed to bridge this gap.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Originality:\nThe paper presents a novel perspective on continual learning grounded in implicit constraints through computational embedding, rather than explicit resource limitations. The formalization of a universal-local environment and the use of Kolmogorov complexity to define the agent’s objective (interactivity) is highly original and conceptually deep.\n- Significance:\nBy framing continual learning in terms of interactivity, the paper offers a general and theoretically motivated setting in which any non-adaptive agent is provably suboptimal. This challenges standard assumptions in RL and provides a new foundation for studying continual adaptation without reliance on task segmentation or explicit forgetting.\n- Theoretical Rigor (Quality):\nThe paper is mathematically precise and includes formal definitions and proofs for all key claims, deferred to a comprehensive appendix. Notably, the results show that interactivity is upper bounded by agent capacity (Theorem 1) and that agents that stop learning are suboptimal (Theorem 2).\n- Clarity of Core Ideas:\nDespite the abstract nature of the concepts, the paper clearly communicates its main constructions—universal-local environments, embedded automata, and interactivity—with helpful analogies (e.g., Conway’s Game of Life) and visual aids. The contrast with traditional RL and AIXI is particularly helpful for positioning the contribution.\n\nWeaknesses:\n- Experiments (Quality / Significance):\nThe only experiment is a synthetic benchmark (behavioral self-prediction) without comparison to existing continual learning algorithms. While the experiment supports the theoretical claims, its simplicity (max 2 layers) limits practical insight into the applicability or scalability of the framework.\n- Clarity of Implementation Details:\nAlthough the theoretical setup is well presented, the reinforcement learning algorithm for maximizing interactivity is described somewhat abstractly. Important aspects like how the inner/outer learning loops interact, and the concrete form of predictions and TD errors, are difficult to follow without significant effort.\n- Limited Practical Connection:\nThe paper is mostly theoretical, and the benchmark does not involve realistic tasks or environments. This makes it unclear how the interactivity framework might inform or improve existing continual learning methods in practice, especially in high-dimensional domains.\n- Heavy Theoretical Overhead:\nThe reliance on Kolmogorov complexity, while elegant, leads to uncomputability in general and requires approximations that introduce complexity and potential instability (as discussed in the limitations). The practical utility of interactivity as a training signal may thus be limited without further simplification.", "was_revised": true, "final_justification": "Thanks for the detailed response. The explanations and justifications answer my questions/concerns well and I have increased the score,", "rebuttal": "We appreciate your thorough review of our submission. We particularly appreciate you finding the core ideas clear, the overall originality/significance and your attention to detail regarding the implications of our task on scaling.\n\n>Experiments (Quality / Significance): While the experiment supports the theoretical claims, its simplicity (max 2 layers) limits practical insight into the applicability or scalability of the framework.+ Practical Scalability: The paper proposes an elegant but computationally heavy optimization procedure.\n\nWe understand that evaluating scalability is a concern of the reviewer and we agree that it is important.\nWe would like to point out that our experiments are in a highly novel task that combines online learning, reinforcement learning, meta learning and continual learning. In fact, Reviewer sAho commended us for generating results at all. \n\nIn our additional experiments, we found that there is a performance benefit to scaling width and depth of the network. But our proposed task is such that the complexity of the task scales with the agent. This is important from the perspective of continual learning (for if the environment did not have this property, a non-adaptive learner could out-scale it). It does, however, challenge the conventional approach to scaling, as there is a cost: a scaled up agent faces a harder task. We hope that future empirical investigations will map out efficient approaches to scaling using interactivity maximization as a key task for evaluation.\n\nLastly, we would like to note that the computational scalability of this problem is a feature, not a bug. While it is true that meta-gradients scale particularly poorly, they provide the ground truth Monte Carlo estimates of the dynamics. We anticipate that effective algorithms will need to scale well, and this task particularly stresses the scalability of algorithms to maximize their interactivity. \n\n\n>Clarity of Implementation Details: ... how the inner/outer learning loops interact, and the concrete form of predictions and TD errors\n\nThank you for bringing up this point. Appendix B included additional implementation details. However, we plan to improve Section 6 to include how it all fits together. The setup is as follows: there is a (meta-) policy and a value function. They are both parameterized with the same architecture (depth/width), and all of their input and output spaces are the same. The value function is updated with TD0 to learn successor features from its experience. This experience is generated by the (meta-)policy in a feed-forward and recursive way ($b_{t+1} = \\pi(b | b_t)$). The policy is updated to maximize the difference between (temporal difference errors of the value function while it is learning) and (temporal difference errors of the frozen value function). The meta-gradient comes in because the policy is optimizing TD errors from a value function that is also learning. Thus, TD learning with the value function is the inner loop and the meta-policy maximizing interactivity is the outer loop.\n\n>Limited Practical Connection: The paper is mostly theoretical, and the benchmark does not involve realistic tasks or environments. This makes it unclear how the interactivity framework might inform or improve existing continual learning methods in practice, especially in high-dimensional domains.\n\nThe empirical contribution in our paper is: (1) interactivity maximization as an evaluation task for continual learning and (2) the meta reinforcement learning approach to maximizing interactivity. Our experiments serve to demonstrate that maximizing interactivity is a difficult task for current deep learning algorithms.. Our additional results (see shared reply) demonstrate that methods designed to help with continual learning also help in this task, thus providing additional evidence of its utility as a novel continual learning task.\n\n>Heavy Theoretical Overhead: The reliance on Kolmogorov complexity, while elegant, leads to uncomputability in general and requires approximations that introduce complexity and potential instability (as discussed in the limitations). The practical utility of interactivity as a training signal may thus be limited without further simplification.\n\nWe use Komogorov complexity as a tool to measure the predictability of an agent’s behaviour sequence. However, we emphasize that Kolmogorov complexity and interactivity are computable for an embedded automaton, and for a bounded agent. Crucially, we show that an agent can approximate this quantity using reinforcement learning. \n \n\n>Your use of universal-local environments (e.g., Conway’s Game of Life) is well-motivated as a constructive proof that embedded agents can exist. However, it’s not entirely clear why locality is essential beyond enabling the embedding. Could you clarify whether locality plays any further role in shaping the agent’s adaptation dynamics or in bounding interactivity?\n\nThanks for this great question! \n\nFirst, we emphasize that locality is common to most models of computation, such as the head movement of a Turing machine, and not just the rules of cellular automata. \n\nLocality plays two crucial roles.You are correct about the first role: it is used to define the boundary between the agent and the environment. You also hint at the second role: locality is needed to bound the interactivity objective. Intuitively, locality ensures that short-term dynamics depend on a small portion of the state-space. Without locality, short-term dynamics may depend on arbitrarily larger portions of the state-space, meaning that even a short-term future behaviour sequence can depend on a large portion of the state space. The implication of this is that the Kolmogorov complexity of short behaviour sequences can be arbitrarily large.\n\n>The proposed interactivity measure uses Kolmogorov complexity and is approximated via agent-relative prediction error. How general is this framework in practice? For instance, would interactivity remain a meaningful or tractable objective in high-dimensional or real-world sensory domains (e.g., vision, language)? What kinds of practical approximations might be required?\n\nThe reinforcement learning approximation for interactivity can be applied to any agent that learns to make predictions with temporal difference learning, regardless of the environment it is interacting with. We understand that high-dimensional observations can be more difficult to predict than latent states. However, the approximation involves the difference between two future temporal difference errors (one where the agent learns, and one where the agent does not learn). Thus, even if the environment provides high-dimensional observations that are more difficult to predict, the objective rewards any relative improvements in predictability. \n\n>Can you elaborate on why existing baselines (e.g., EWC, replay buffers) were not included, and what challenges prevent comparison?\n\nOur current set of experiments are set up primarily to evaluate the optimization problem underlying maximizing interactivity. While maintaining memory of the past will be important to make further improvements on interactivity, we found that loss of plasticity and general instability to be of far greater importance. In particular, EWC and replay buffers are not well suited for maximizing interactivity. For EWC, there are no discrete tasks: at every timestep the agent updates its policy and creates nonstationarity. And, because of this nonstationarity, old data is not useful for learning. Thus, replay buffers are not effective here as they are in other reinforcement and continual learning experiments.\n\n>Your learning algorithm for interactivity involves a form of bi-level optimization (meta-gradients)...\n\nWhile meta-gradients is the approach that we take, this is motivated by the fact that meta-gradients provide a Monte Carlo approximation to our objective. More scalable approaches, like first-order gradients, may be important for larger networks, but the full meta-gradient provides an important first step in understanding the dynamics of an agent maximizing interactivity. More sophisticated approaches could work, such as bootstrapped meta-gradients. Viewing interactivity as a value function opens many more sophisticated value approximation algorithms that may improve over Monte Carlo. We anticipate that such progress can be made in future work.\n\n> Your current experiments only include 2-layer networks. What's the rationale behind this choice, and how does the method extend to deeper networks?\n\nWhile the base network only has 2 layers, the meta-learner has a much deeper effective network size. This is because the meta-gradient for the meta-learner involves a composition as deep as the horizon. That is, the meta-learner has an effective depth of 2*H. This could be better represented by a recurrent architecture, but this would include yet more complexity that we seek to address in future work.\n\n\n>Limited Empirical Validation: The synthetic benchmark is theoretically motivated but very narrow in scope. The authors should discuss whether their current results demonstrate efficacy beyond toy settings, and that future work is needed to bridge this gap.\n\nThe behavioural self-prediction task that we introduce may seem toy, but its complexity scales with the function approximator. It can be applied to any learning algorithm that supports an input space equal to its output space. More generally, it could be used as an intrinsic motivation objective but this will require the development of scalable meta-learning algorithms."}]

Author rebuttal:

Meta-review: The reviewers agree that this work introduces a novel framework for continual learning through universal-local environments and the use of interactivity as a measure. This formalism embeds agents with computational limits and shows that maximizing interactivity naturally leads to continual learning. Reviewers view this as a useful extension of prior work like AIXI, providing a more principled foundation for studying agent-environment interaction.

Strengths noted include the clarity of motivation, systematic treatment of the problem, and an end-to-end demonstration with experiments. The use of Conway’s Game of Life, practical relaxations of complexity measures, and alignment with intrinsic motivation methods were highlighted as novel. I therefore recommend acceptance of this work to NeurIPS and look forward to seeing further research that builds on it.
Decision: Accept (spotlight)