General agents need world models
Authors: Jonathan Richens
Tom Everitt
David Abel
Venue: ICML 2025 poster (2025)
Keywords: Agents
world models
reinforcement learning
goal-conditioned reinforcement learning
causality
generalization
Primary area: theory->reinforcement_learning_and_planning
TL;DR: We prove that any agent capable of  flexible goal-directed behaviour must have learned a world model, and provide algorithms for recovering this world model from the agent.

Abstract: Are world models a necessary ingredient for flexible, goal-directed behaviour, or is model-free learning sufficient?
We provide a formal answer to this question, showing that any agent capable of generalizing to multi-step goal-directed tasks must have learned a predictive model of its environment.
We show that this model can be extracted from the agent's policy, and that increasing the agents performance or the complexity of the goals it can achieve requires learning increasingly accurate world models.
This has a number of consequences: from developing safe and general agents, to bounding agent capabilities in complex environments, and providing new algorithms for eliciting world models from agents.

General agents need world models
Jonathan Richens'
Tom Everitt
David Abel'
Abstract
Are world models necessary ingredient for flex- ible, goal-directed behaviour, or is model-free learning sufficient? We provide formal answer to this question, showing that any agent capable of generalizing to multi-step goal-directed tasks must have learned a predictive model of its en- vironment. We show that this model can be ex- tracted from the agent's policy, and that increasing the agents performance or the complexity of the goals it can achieve requires learning increasingly accurate world models. This has number of consequences: from developing safe and general agents, to bounding agent capabilities in complex environments, and providing new algorithms for eliciting world models from agents.
RL. Planning
our result
p IRL/ inverse planning
π
Figure 1: Our result complements previous insights from planning and inverse RL. While planning uses world model and goal to determine policy, and IRL and in- verse planning use an agent's 's policy and a world model to identify its goal, our result uses an agent's policy and its goal to identify a world model
1. Introduction
hallmark of human intelligence is the ability to perform novel tasks with minimal supervision, formalised by few- shot and zero-shot learning (Lake et al., (017). With the emergence of these capabilities in language models (Brown al. 2020), focus has shifted to developing general agents systems capable of performing long horizon goal-oriented tasks in complex, real-world environments (Yao et al., [2022 Hao et al. 2023). In humans this kind of flexible goal- directed behaviour relies heavily on rich mental representa- tions of the world, i.e. world models (Johnson-Laird) 1983 Ha & Schmidhuber 2018). which are used to set abstract goals beyond immediate sensory inputs (Locke & Latham 2013). and to deliberatively and proactively plan actions (Bratman 1987). Whether world models are necessary for achieving human-level Al has long been debated, pitting the challenges of learning models against the potential benefits they confer (Huang 2020).
2023 Wang et al. 2023 LeCun 2022 Raad et al. 2024 and having direct access to the agent's 's world model has benefits like being able to apply formal planning methods (Sutton 2018), predicting the agent's 's behaviour in safety- critical domains (Amodei al.) 2016 Dalrymple 2024}, reducing sample complexity (Hafner et al. 2019)
al.
and supporting transfer learning (Chua et al.) 2018 8 Zhu et al. 2023). However, learning accurate models of real- world systems can be extremely challenging (Dulac-Arnold ct al. 2019), and the performance of model-based agents is fundamentally limited by their model's fidelity.
In "Intelligence without representation", Brooks famously proposed that the world is its own best model, and that all intelligent behaviours can emerge in model-free agents in- teracting through action-percepee to learn explicit representations the world (Brooks 1991). This view has largely been borne out by the development of model-fre frre agents capable of generalizing across a wide
loops, without needing
Explicitly model-based agents have achieved impressive performance across many tasks and domains (Hatner al.
range of tasks and environments (Reed al. 2022 Brohan
et al. 2023 Driess et al. [023] Black et al. 2024 Schrit
'Google DeepMind. Correspondence to: Jonathan Richens <jonrichens@e @ googlc.com>.
twieser et al. 2020). This model-free paradigm aims to achieve truly general agents while side-stepping the chal- lenges inherent in learning a world model. However, there is mounting evidence that model-fre agents may in fact learn implicit world models (Li et al., 2022), and may even
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

General agents need world models
learn implicit planning algorithms (Hou al.
2023
Bush
2.2. Environment
al. 2025
We assume the environment is a controlled Markov pro- cess (cMP) [Puterman| 2014] Sutton 2018), which is Markov decision process without a specified reward func- tion or discount factor. Formally, cMP consists of a set of states S, a set of actions A, and a transition function Paer (a) = P(S = s' A = a, = =). We refer to a sequence of state-action pairs over time as a trajectory,
This raises fundamental question: is there a model shortcut to human-level AI? Or is learning a world model necessary, with all the complexity this entails? And if so, just how accurate and comprehensive do world models need to be to support given level of capability? We provide a formal answer to these questions, showing that,
T = (so: ao. $1, $1.01....) and a finite prefix of T as a history, h2 = (s0, a0,-.., 8t).
any agent that satisfies a regret bound for a suf- ficiently diverse set of simple goal- goal-directed tasks must have learned an accurate predictive model of its environment.
Definition (Controlled Markov process). A controlled
Markov process (cMP) is a Markov decision process (MDP) without specified reward function or discount factor. is defined by the tuple (S, A, Pas (a)( where S is the state space, A is the action space, and (a) P(S s' A 01 S = 8) is the transition function.
Specifically, we consider environments described by a fully observed Markov processes, and propose a minimalist def- inition of general agents goal-conditioned policies (Liu et al., (022) that satisfy a regret bound for large set of simple goal-directed tasks (such as steering the environment into a desired state). We derive an algorithm that returns an approximation of the environment transition function (a world model) given the policy of any such agent, and show that the error in this approximation decreases as we increase the agent's 's performance or the complexity of the goals it can achieve. In other words, general agents are world models, with all the information required to simulate the environ- ment encoded in their policy. Importantly, we prove this for any agent that satisfies a regret bound, regardless of the details of its training and architecture and without imposing rationality assumptions.
To derive our results we make the standard assumptions that the environment is finite, irreducible, and stationary, mean- ing every state is reachable from every other state under some finite sequence of actions, and transition probabilities do not change over time. Furthermore we assume |A|| 2 2 so that the environment can support non- non-trivial policies.
Assumption 1. We assume the environment is described by an irreducible, stationary, finite, controlled Markov process (Def. 7 with at least two actions.
For further discussion of these standard assumptions see Puterman 2014 Sutton 2018
2.3. Goals
The necessity of learning world model has profound con- sequences for how we develop general AI systems, how capable these systems can ultimately be, and how we can ensure agents are safe and interpretable. We explore these consequences and others in Section + A more immediate consequence that in proving our result we derive new algorithms for extracting world models from general agents. We demonstrate this in Section [.1] and show that our algo- rithms can recover accurate world models even when the agent strongly violates our competence assumptions. In Section 5 we then discuss related work, including inverse reinforcement learning and mechanistic interpretability.
Our aim is not to provide complete definition of goal- directed behaviour, but to define a simple and intuitive class of goals we might reasonably expect an agent to be capa- ble of. In many settings including planning (Ghallab et al. 2004), goal-conditioned reinforcement learning (Liu et al. 2022), and control theory (Aström & Murray, 2021 l), the simplest goals are desirable states of the world (goal states), and goal is achieved by the agent steering the environ- ment into one of these goal states. More generally, goal- directed behaviour can involve sequence of sub-goals to be achieved in particular order, and may include desirable actions as well as environment states. This class includes instruction following, which is the type of goal-directed behaviour we typically desire of Al agents.
2. Setup
2.1. Notation
To describe these sequences of sub-goals (sequential goals) use Linear Temporal Logic (LTL) (Pnueli 1977 Baier &
Capital letters denote random variables X and lower case
letters denoting a value or state X = x. Bold letters denote sets of variables X = X2..,, }m and æ denotes the joint state [2,,,2,... Fm }. Square brackets denote a proposition, e.g. [X = z] is True if X = x and False otherwise.
Katoen 2008). which is commonly used to specify tasks and
temporal objectives for agents (Littman et al. 2017 Li et al.
2017 Hasanbeig et al.] 2019 Dzifeak et al.
2009 Ding
et al. 2014) including more recently for cooll-onditioned
reinforcement learning agents (Vaezipoor et al.
2021 Quu
2

---

General agents need world models
Jackermeier & Abate 2024). An LTL express-- sion op assigns a truth value to each trajectory (denoted = s), which is true iff' satisfies the LTL expression. Concretely, we define goal as pair (O.g) where is a set of goal states and O is a temporal operator specifying a time horizon within which the goal states should be reached. For our results will be sufficient to restrict our attention to two temporal operators; Eventually (0), where the goal state must be reached at any future time, and Next (O), where the next state must be goal state, e.g. to capture the immediate consequences of an agent's ' actions. In the absence of a temporal operator, the goal condition must in the current time step, which we refer to as Now and rep- resent with the trivial (True) operator T. We denote goals as op := ([(ss, a) gl). For example, & = ([S s)) specifies that state s must eventually be reached. See Ap- pendix A.3 for further discussion.
al. 2023
V
Environment
0.9
0.7
Agent
0.4
World model
Figure 2: The agent-environment system. Agents are maps from states 8t (or histories) and goals & to actions a, The dashed line represents Algorithm [ which recovers the environment transition probabilities from this agent map.
Example: A maintenance robot given the task of fix- ing a faulty machine, finding an engineer and alerting them that the machine is broken. Fixing the machine re- quires performing a sequence of predetermined actions 01, a2....,, aN and each time attaining the desired out- come 81, .,...., 8N. which can be represented as the se- quential goal ti = (4P1, PP.,,,,....,.. (NN = [A = a S = $1] A O(AA .1.5 = s1] O(...) (using simplified notation for as),a) E g)). Finding and alerting the engi- neer requires the robot to navigate to an engineer S Beng and alerting them A = a', 1/2 = Q Seng, A = a')). The robot's 's goal can be represented as the composite goal v = the V 2/2.
Definition (Goals). A goal yp is an LTL expression of the form 9 = ([((s,) a) E g]) where,
g is a set of goal-states, a sub-set of the joint states of the environment-agee agent system (s,a) E S x A.
O is a temporal operator specifying the time horizon for reaching g. We restrict to O E {O,0, T} where O = Next, C
Eventually, T Now.
we can construct composite goals of increasing complexity by either combining goals in sequence (where goal A must be achieved before goal (PB) or in parallel (where satisfying either goal Aa or goal yB is sufficient). We use vi = (. (n,) to denote a sequence of sub-goals, where the agent must satisfy 인 before moving on to (22, and so on. Here & is also an LTL expression, which we provide a formula for in Appendix A.. We refer to n as the depth of v/, i.e. the number of sub-goals the agent must satisfy to satisfy v (also known as the temporal height, Demri & [Schnoebelen (2002)) Parallel composition is achieved by taking the disjunction (OR) of two or more (sequential) goals, i.e. for w/ = 2h V 4/2, T F= a// is true iff th or 1/2 are satisfied by r. Finally, & denotes the set of all composite goals for given environment, and It, to denote the set of all compositions of goals (Def. 3) of depth at most n.
Using Def. wee
2.4. Agents
Our aim is to formulate a minimalist definition of an agent capable of achieving a range of goals in its environment. To this end we focus on goal-conditioeed agents (Liu et al., 2022 [chhull et al. 2015), which are policies π that map histories and goals to actions, : he; 1 ++ ag (Figure 2 Note this does not restrict to agents that can condition their actions on the full history of the environment, as any policy (e.g. a Markov policy) can be represented in this way. For simplicity, we assume that the environment is fully observed by the agent, and that the agent follows a deterministic policy. This leads to a natural definition of an optimal goal-conditioned agent for a given environment and set of goals V which is policy that maximizes the probability that v is achieved, for all vi E V.
Definition 3 (Composite goals). A sequential goal to is an ordered sequence of sub-gouls (Def. 2) vo = (. .n)). where the agent must achieve sub- sub-goal ips before pi+1. The depth of sequential goal is the number of sub-goals depth(() ()- = n. A composite goal is disjunction of one or more sequential goals 1/2 = - Vi, i.e. the agent must achieve any sub-goal vi to achieve sb. The depth of a composite goal is the max depth of its sub-goals depth(()= = maxe, depth((x)). In is the set of all com- posite goals s with depth(w) S n.
Definition 4 (optimal coal-conditioned agent). For a given set of goals Tp (Def. 3 an optimal agent is a goal- conditioned policy n² (at h133)) where T² is deterministic and satisfies.
n" = arg max P(r s n, 30)
(I)
7
V 80 S.t. P(so) > O. where so the initial state of the
3

---

General agents need world models
2018), which in Markovian environments are sufficient to Real agents are rarely optimal, especially when operating in complex environments and for tasks that require coor- dinating many sub-goals over long time horizons. Hence, we relax Def. 4 to define a bounded agent that is capable of achieving goals of some maximum goal depth v, with failure rate that is bounded relative to the optimal agent. Bounded agents are defined by two parameters; a failure rate ò [0, 1], which places lower bound on the proba- bility that the agent achieves a goal compared an optimal agent (analogous to regret), and ii) a maximum goal depth n, such that this regret bound holds only for goals with a depth less than or equal to n. This naturally captures the type of agents we are interested in those which have some capability (parameterised by 5) for achieving goals of some maximum complexity n.
environment L 0, and V o/ v.
predict the evolution of the environment under arbitrary policies. We define world model as any approximation Pes (a) of the transition function of the environment (Def. | Pas (a) = P(S = s' A, = a. St = 8), with bounded error (a) (a) S E.
3. Results
Our main result is a proof by reduction- we assume the agent is bounded goal-conditioned agent (Def. 5 i.e. it has some (lower bounded) competency at goal-directed tasks of some finite depth n (Def. 3 We then prove that an approximation of the environment's transition function (a world model) is determined by the agent's policy alone, with bounded error. Hence, learning such a goal-conditioned policy is informationally equivalent to learning accurate world model.
Definition 5 (bounded goal-conditioned agent). A bounded goal-conditioned agent is a goal-conditioned policy т T(a hy: +) satisfying.
Theorem 1. Let (a) = P(S++1= = - - = be the transition probabilities of an environment satisfying Assumption | Let be goal-conditioned agent (Def. 3 with a maximum failure rate 5 for all goals x/ E v,, where Vn is the set of all composite goals with maximum goal depth n > 1. T fully determines a model for the environment transition probabilities Per (a) with errors satisfying
P(T - db (T) 2 max P(r F F st) 8)
(2)
V E Vn where is the maximum goal depth and su is the initial state of the environment at t.- 0.
Importantly, Def. 5 only assumes a level of competence for the agent. We do not, for example, impose any ratio- nality assumptions on the agent as in (Von Neumann & Morgensterm/ 2007: Savage 1972), which are not satisfied by current agents (Raman al. 2024b).
2P (Ps (a))
(ax (a) S
(n-1)(1- 5)
for any n, 6, and for 8 << 1, >> 1 the error scales as,
Example: Following the previous example, the perfor- mance of the maintenance robot is measured by the proba- bility that it either fixes the machine or alerts an engineer, i.e. P(T F sP Vip2 ,, 80). This intuitively involves weighing up the two possible courses of action; if the repair is difficult then directly attempting it could lead to failure, and finding an engineer is the better course of action. Or if the proba- bility of finding an engineer is very low, attempting to fix the machine may be the best strategy. Whatever the agent chooses to do, we can measure its performance relative to the probability that the optimal agent will solve the task, P(T F P1 V P2 π sp).
(a) - (a)) ~ 0 (8/vm) + O(1/))
Proof in Appendix A.6
In Appendix A.5 we give simplified overview of the proof of Theorem We derive an algorithm that queries the goal-conditioned policy with different goals ei E V n which correspond to either-or decisions between two incompatible sub-goals vé via V tha As the agent satisfies a regret bound, its choice of action encodes information about which of the sub-goals has higher maximum probability of being satisfied, and this information can be used to estimate the transition probabilities (a). We then prove that this estimate satisfies the error bounds stated in Theorem Note that while the statement of Theorem I assumes the agent has a maximum failure rate (regret bound) for all & Rn. in fact our proof only requires the agent satisfies this regret bound for small subset of Vr, consisting of n composite goals (see discussion of emergent capabilities in Section 4.
2.5. World models
We are interested in the role of world models in goal- directed behaviour. Hence we focus on predictive world models, which can be used by agents to plan. This fol- lows the definition of world models used in reinforcement learning (RL), as opposed to the use of the term to de- scribe representations of the environment state alone (c.g. in Li et al.) (2022); Gurnee & Tegmark (2023b)). For model-based RL agents, explicit world models are usu- ally one-step predictors of the environment state (Sutton
Our algorithm for recovering a bounded-error world model from a bounded soal-conditioned agent (Algorithm [ is detailed in Appendix C It is universal, meaning the same
4

---

General agents need world models
algorithm works for all agents satisfying Def. 3 all envi- ronments satisfying Assumption T It is also unsupervised; the only input to the algorithm is the agent's 's policy The existence of this algorithm, which converts π into a bounded error world model, implies the world model is encoded in the agent's policy, and learning such policy is information- ally equivalent to learning a world model. Formally, the approximate world model (a) is identifiable given the agent's policy and our assumptions (see for example BBarein boom et al. ().22)) ). In Section we compare Algorithm and its assumptions to methods for recovering world models in mechanistic interpretability, which similarly use the exis- tence of a recovery map establish that an agent has learned a world model.
0175
-0280W 4.91
0.375
y- 0.212 Steth + 1
0.39
0.23-
0.125
8
0.10-
0.000
0075
0073
0050-
0.030
25
120 125
150
175
5.023
Newdl51 11:.51=000000 +0,00)
5500
b)
Figure 3: a) shows the mean error in the world model re- covered by Algorithm 2 (c), decrease as the agent learns to generalize to higher depth goals. Nmax(()) = 0.04) is the maximum goal depth such that the agent achieves a mean regret & 0.04. The scaling is O(n 1/2), with the scaling between the worst-case error e and worst-case re- gret 5 in Theorem | b) shows the mean error scaling with (8(m = 50)), the mean regret the agent achieves for depth n = 50 goals. For both figures, error bars show 95% confi- dence intervals for the mean over 10 experiments where we re- re-trained the agents with different experience trajectories of the same length.
Properties of the world model. The accuracy of the world model recovered from the agent in Theorem I increases as the agent approaches optimality (6 - 0), and/or as the depth of sequential goals it can achieve increases. A key consequence of the derived error bounds is that for any 5 < we can recover an arbitrarily accurate world model if we can make n sufficiently large. Therefore, in order to achieve long horizon goals even with a high failure rate 5 d~ 1, the agent must have learned a highly accurate world model. The error bounds also depend on the transition probabilities, and dividing both sides of the bound by (a) shows that the relative error (a)) Pa. (a) can become very large for (a) << 1. This means that for any d > 0 and/or finite n, there can exist low probability transitions that the agent is not required to learn This matches the intuition that sub-optimal finite-horizon agents need only learn relatively sparse world models covering the more common transitions, but achieving goals with higher success rate or longer horizons requires higher resolution world models.
even partially determine the transition probabilities from the policy of a myopic agent. In the proof of Theorem 2 we show this by explicitly construct a myopic agent that is optimal for any choice of Pas E [o. 1], and so the policy of such an agent can only impart trivial bounds on the transition probabilities. Therefore, learning world model with is not necessary for myopic ggents-wordd models only become necessary for agents pursuing goals with multiple sub-goals and over multi-step horizons.
Theorem | impprts only a trivial error bound on the world model we can extract from agents whose maximum goal depth is n 1. It is not immediately clear if this means that agents that only optimize for immediate outcomes (myopic agents) do not need to learn a world model, or if Theorem | simply fails to capture this class of agents. To resolve this we derive a result for myopic agents, which satisfy a regret bound for n = 1 and only a trivial regret bound (6 = 1) for any n > 1.
3.1. Experiments
We demonstrate our procedure for recovering a world model from an agent, and how the accuracy of the model increases as the agent learns to generalize to more tasks (longer hori- zon goals). We also investigate if our algorithm can re- cover the transition function when the agent strongly vi- olates our assumptions (Def. 5). Specifically,
realistic agent could be highly competent (ò ~ 0) for some depth-n goals but completely fail for others (6 = 1). This agent would violate any non-trivial regret bound as in Def. 5 resulting in trivial model-error bounds in Theorem [ To explore this case we relax Def. 5 consider agents where the regret bound holds only on average over some set of goals V, i.c. (8) S k where (6) is the average value of P(T F so ग. su)/ max, P(r }= &b IT, so) over all v E V. We then determine empirically how the average er- ror (<) in the world model recovered by Algorithm I scales with the agent's 's average regret (6) (Figure 3 b)), where e c: | (a) - P.o (a)) and (e) is mean value of over all transitions (8. a, a')")
Theorem 2. Let the set of myopic goals L myopic be the subset of depth-I composite goals 1 such that the goal state(s) must be attained immediately after the agents first action, Pp = Ol(s, a) E g)- We define an optimal myopic agent as a policy (at h)) that is optimal for all & e I myopic- For an environment sattisfyng Assumption] 7 any bounds on the transition probabilities (asx(a)- Pss (a) $ than can be determined from π² are trivial 1) and
tight. Proof in Appendix B
Theorem 2 implies that there exists no procedure that can
5

---

General agents need world models
The environment used to test our algorithms is a randomly generated cMP satisfying Assumption I comprising of 20 states and 5 actions with sparse transition function. We train our agent using trajectories sampled from the environ- ment under a random policy, and we increase the compe- lency of our agent by increasing the length of the trajectory is trained on, Nasmples. See Appendix D for further de- tails on the agent and experimental setup. We recover the world model using Algorithm 2 simplified version of Algorithm D
implicit world models have been proposed an explana- tion for emergent capabilities in foundation models (Brown et al. 2020 Li et al. 2022; Abdou et al. 202I). Our results support this hypothesis by revealing a mechanism by which implicit world models could emerge during training. To minimize regret across a variety of training tasks, agents are required to learn an implicit world model, which in turn could support generalization to a wide range of tasks the agent was never explicitly trained on. Note that for simplic- ity we have stated Theorem [ with the assumption that the agent can generalize to any depth-n composite goal w.. but this is not the strongest statement of the result. In the proof (Appendix A the agent is required to generalize only to small subset of Vn, comprising of n simple composite goals (see also Algorithm [ There are likely many such choices of subsets of L n (e.g. a different sufficient set is used in Algorithm [ Appendix C and there are likely other tasks beyond achieving composite goals (Def. 3 that are sufficient to derive the result. Our findings therefore point to the existence of sets of simple tasks, where learning to perform these tasks implies sufficient world knowledge to (in principle) generalize to any task.
As we increase Nsamples we observe the agent can generalize to longer horizon goals, captured by (()) = k) which is the maximum goal depth n such that the agent achieves an average regret (6) = for goals of depth n. We find that for all Nasmples tested, and for all goal deptsh n, our agent agent achieved a worst-case regret å = for some goals, i.e. the agent violates any non-trivial regret bound of the form Def. 5 Nevertheless, we find that Algorithm 2 recovers the transition function with a low average error (Figure 3 b)), which scales as ~ O(n (n22) like the error bound Theorem]] [ Hence, in spite of the agent violating our assumptions and achieving maximal regret for some goals, the average error has similar decay with the goal depth as when the worst-case regret bound (Def. 5 is satis- fied. Therefore, we can still accurately recover the transition function from the agent as long as it achieves a relatively low average regret for long horizon goals.
Beyond planning, world models support domain adaptation CCha et al. 2018), reasoning about uncertainty (Lockwood & Si 2022) and social cognition (Rabinowitz et al. 2018).
With additional structural assumptions, they can also sup- port causal reasoning (Pearl 2018), simulating counterfac- tual trajectories and imagination (Racanière et al., 2017).
4. Discussion
and reasoning about intent (Ward al., 2024) and attribu- tion (Chockler & Halpern 2004). Theorem | provides simple explanation for how this wide range of cognitive abilities, associated primarily with human-level intelligence Tomasello 2022), can emerge from simple goal- goal-directed behaviour. This could explain away several prominent theo- ries for how these capabilities arose in nature, which propose specific environmental factors such as resource uncertainty Hiills et al. (215)) and social complexity (Dunbar) 1998) as the driving force for their emergence. The composite goals used in the proof of Theorem |
We now discuss the consequences of Theorem I and its limitations.
No model-free path to general agents. Theorem D iimplies that any agent that satisfies a regret bound as in Def. 5 must have learned an implicit world model, and the accuracy of the model increases as the regret 8 decreases or the maxi- mum goal depth n increases. In other words, there is no way to train agent capable of generalizing to long horizon tasks without learning a world model, and the fidelity of the model bounds the agent's 's capabilities. This removes a key motivation for model free approaches, as learning a world model cannot be avoided. On the other hand, it mo- tivates explicitly model-based architectures (LeCun, 2022 Hafner et al., 2023; Schrittwieser et al., (2020), which can directly attack the model learning problem, and can exploit their benefits in terms of sample efficiency (Hafner et al.
describe simple either-or navigation tasks in single-agent environment. If an agent was required to solve these tasks without repeated attempts (zero-shot), perhaps due to risk of death, this would require the agent to satisfy a regret bound as in Def. 5 and hence learn world model capable of supporting these capabilities. without needing to invoke novel environmental social factors
2019), planning (Sutton 2018), interpretability (Glanois et al.
Safety, Several proposals for AI safety and alignment re- quire an accurate predictive model of the agent- environment system to verify the safety of plans (Bengio et al. 2024] Dairymple et al. 2024), safely explore (Brunke et al. 2022). predict human responses (Leike et al. 2018)0)) avoid prob- lematic incentives (Farquhar et al.) 2022h. and incorporate model-based concepts into decision making such as intent
2024) and safety (Amodei et al., 2016).
Emergent capabilities. An accurate world model is a pow- erful tool it can be used to determine low-regret policies for any well-defined objective, without requiring further in- teraction with the environment or task-specific data. Hence,
6

---

General agents need world models
Ward et al.
2024), deception (Wadd et al.
2023 and harm
stronger in more realistic environments which incorporate partially observed states or non-Markovian dynamics.
(Richens et al. 2022 Bengio et al. 2024). Other proposals
focus on passive oracles (essentially world models), avoid- ing agents altogether due to their inherent safety issues (Bengio et al. 2025 Armstrong & O' O'Rorke (017))
Limitations. The proof of Theorem I considers only fully observed environments. It is not clear what an agent op- erating in a partially observed environment would have to learn about latent variables in order to achieve the same level of behavioural flexibility. It is important to clarify that Theorem proves the existence of a world model encoded in the agent's 's policy, not its specific use (e.g. for planning), nor can we make deeper epistemological claims about what the agent knows about its environment (Fagin et al. 2004).
One major impediment to these approaches is the reasonable expectation that the capabilities of model-free agents will outpace our ability learn accurate predictive models of complex real-world environments. There are already sev- eral examples of Al systems that can solve prediction tasks in domains we cannot yet model (Abramson et al., [024] Merchant et al., 2023), ) and it is intuitively hard to inter- pret, audit and correct the behaviour of black-box agents operating in environments we do not understand, or where the agent has superior world knowledge than the supervi- sor (Christiano et al.] 202T). Our results point to solution, providing a theoretical guarantee that we can extract an accurate world model from any sufficiently capable model- free agent. Importantly, the fidelity of this model increases with the agent's capabilities, especially as agent gets better at achieving goals over long time horizons- prrciels-preeisell the regime where safety concerns such as reward hacking be- come important (Farquhar al., 2025). Future work should explore developing scalable algorithms for cliciting these world models and using them to improve agent safety,
5. Related work
Inverse reinforcement learning (IRL) Ng et al. 2000 and inverse planning (Baker et al.) 2007) involve determin- ing an agents reward function (or goal) given the transition function and the optimal policy. Similarly, planning is the process of determining an optimal policy given the tran- sition function and a goal (reward). Our result fills in the remaining direction, recovering the transition function given the agent's s goal and their regret-bounded policy. IRL the reward function can only be fully determined if we know the optimal policy across multiple environments (Amin & Singh (016), and likewise we find that to fully determine the environment transition function we must know the opti- mal policy for multiple goals. Figure shows how our result relates to planning and IRL, where for each process takes as input two elements from (environment, goal, policy). and determines the missing third element.
Limits on strong AI. Our ability to learn accurate models of the world is fundamentally limited by the openness of real-world systems, their complexity and unpredictability, confounding, limited data, and the curse of dimensionality (Box& & Draper 1987). Theorem [ implies that training agent capable of generalizing to wide range of tasks in the real world is extremely hard- at least as hard (and possibly much harder) than learning an accurate model of the world. While 'thinking slow' (Kahneman 201T) deliberative plan- ning and reasoning is not necessary (or even desirable) in every situation-ffe example, humans also generalize to novel tasks through 'thinking fast' heuristics (Tversky& & Kahneman 1974) and similarity-basee generalization (Shep- ard 1987) our results establish that for any agent, natural or artificial, their ability to generalize is ultimately bounded by their ability to learn how the world works.
Mechanistic Interpretability (MI) aims to uncover implicit world models within model-free agents (Abdou et al. 2021
Li et al. 2022 Gurnee & Tegmark 2023a Karvonen 2024
Hou et al. 2023 Bush et al. 2025). This typically involves learning a map from a policy network's activations to fea- tures representing states S (e.g. the board states of a game (Li et al. 2022)). The state-space (ontology) S is either probing/Alain
assumed (as in supervised probing (Alain & Bengio (2016) or identified through unsupervised learning (as with SAFS Bricken et al. (2023)). The causal role of these features in the agent's 's decision making is established by intervening on their representations and observing the policy changes consistently, as if the world state had changed.
One consequence is that regret-bounded agents (Def. 5) are effectively limited domains that are 'solvable', i.c. where we can feasibly learn model of the underlying dynamics and use it to plan over long horizons. In domains where this is infeasible, there can be no guarantee the agent will generalize (satisfy a non-trivial regret bound 8 < 1) for long horizon tasks (n > 1). Therefore, some amount of online learning will be necessary, which is limited by the speed of interaction with the environment. Note that our results are derived for the simplest non-trivial environments (Assumption]] D. and it is likely these constraints will be even
Our work also establishes an agent has learned a world model by the existence of a recovery map, but crucially this map is from the agent's is policy rather than its activations. This is strictly weaker (as the policy is a function of the activations), and so Algorithm [[ can be used even when activations are inaccessible (e.g. private weights). This also allows us to tie the existence of a world model to agent capabilities (regret bounds as in Def. 5) rather than the specifics of the agent architecture, and Algorithm [ apppies
7

---

General agents need world models
to all agents satisfying Def. Def.15land and environments satisfying Assumption 1 By comparison, probes SAEs are fit given agent-enviroommnt system, and may require retraining if either changes (e.g. through distributional shifts or weight updates). Also Algorithm|| is unsupervised, whereas MI methods are at least partially supervised, which can lead to ambiguity as to where the world model is encoded (in the agent, the probe, or jointly).
whereas domain generalization does. That said, in the cMP setring the transition function does encode a degree of causal information, and we leave it to future work to determine precisely what causal knowledge is required for an agent satisfying Def. This hints at an agential version of Pearl's causal hierarchy (Bareinboim et al., 2022), where differ- ent agent capabilities (like domain or task generalization) provably require different degrees of causal knowledge.
Another key difference is that recover a predictive world model P... (a) capturing environment dynamics, rather than simply a state space representation S. However, our aim is to prove the agent has learned the actual environment dynamics up to an error bound, not to recover the subjective world model used by the agent to generate its actions. As discussed in the paragraph 'representation theorems' below, if we introduce additional consistency assumptions similar to those used M we can recover the agent's 's subjective world model. One drawback is that we may underestimate what an agent knows about its environment-e.g agents could learn a world model but strongly violate Def. (c.g. due to errors in planning), so Algorithm[Tisn' guaranteed to recover this world knowledge whereas methods like probing may succeed. However, Section 3.1 shows that least in simple environments, our procedure can work well even when the regret bound is trivialised (8 = 1).
LTL goal-conditioned agents. LTL is the natural choice for expressing instructions, goals and safety constraints in reinforcement learning and planning (Camacho et al. 2019).
Recently, there have been several implementations of goal- conditioned agents that generalize zero-shot to arbitrary L.TI. goals (Qiu et al. 2023 Jackermeier Abate [025] Vaezipoor et al. 2021 Kuo et al., 2020). This maps pre- cisely onto the setting we study, and future work could ex- plore using Algorithm | variants to recover world models from these agents, and use them to debug agent behaviour.
Representation theorems such as SSavage 1972) and Halpern & Piermont (2024), establish that agents satisfying certain rationality axioms behave as if they are maximiz- ing the expected value of a utility function with respect to world model. For example. [Savage (9722) can be used to 'fit' a world model to agent's 's behaviour, determining a unique utility function U(s') and set of beliefs (a world model (a)) such that the policy that maximizes [U] is identical to the agents policy. However, this says nothing about what (if anything) the agent has learned about the true environment dynamics. For example, we may be able to assign a specific world model and utility function a purely random policy T(a s) = 1/| but this clearly does not imply that learning a world model is necessary to gener- ate a random policy. Instead of attempting to recover an agent's 's subjective world model, we aim to recover the true underlying dynamics of the environment from the policy of the agent. In doing so, we show that learning such a policy implies learning these dynamics, and so the learnability of these dynamics bounds agent capabilities. Further, Theo- rem 2 establishes that an optimal myopic agent does not need to learn the transition probabilities Par (4), and repre- sentation theorems typically focus on the myopic regime.
Causal world models. (Richens& & Everitt 2024) provides a similar result to Theorem I showing that an agent capable of adapting to a sufficiently large set of distributional shifts must have learned a causal world model. Our work has a different focus: we study an agents ability to generalize to new goals (task generalization) rather than adapting to new environments (domain generalization). A surprising consequence of our result combined with Richens & Everitt (2024) is that domain generalization requires strictly more knowledge of the environment than task generalization. To see this, consider a setting where the state comprises two variables 5 = X x Y and X + Y. We can construct optimal goal-conditioned agent (Def. 4 given the transi- tion function Peo (a) = P(X++1 = x', Ye+1 = s A, = a, X, = x, Yt = y), as an optimal goal-conditioned policy can be determined by planning on this model. However, the causal relation between X - Y is non-identifiable from Pxs (a), i.c. almost all distributions (a) are com- patible with both X + Y and X + Y. Therefore, task generalization does not require knowledge of the causal re- lation between concurrent environment variables X, and Y;
We can recover something like the agent's ss subjective world model by changing Def. 5o the assumption that the agent is 6-optimal with respect to its own world model M,
PM(T }= & ग., 50) Z max PM }= &b π,, (0) 5)
x
'Consistency in MI requires the agent adapts their behaviour following interventions their world model. This amounts to assuming regret-boundes behavior under interventions, which is tantamount to assuming the agent has a causal world model to begin with (Richens& & Everiti 20024). Hence, using this kind of interventional consistency to establish that an agent has world model risks circular reasoning.
(3)
This amounts to assuming the agent has world model, and that its behaviour is highly consistent with this world model (with consistency given by 6), but stops short of as- suming the agent is optimal with respect to its own beliefs. For example, 8 > 0 could represent a sub-optimal planner. For this altered Def. 5 Theorem is unchanged and Algo-
8

---

General agents need world models
rithm reeturns the agents subjective world model M with bounded error. This may be appealing as a representation theorem as it has much weaker assumptions than Savage (1972), e.g. we only assume the agent follows a policy that is imperfectly consistent with its beliefs, whereas Savagee (1972) requires the agent specifies a preference order over all actions (whereas a policy specifies only the most pre- ferred action(s)), and makes strong rationality assumptions which not satisfied by most current systems (Raman et al. 2024a).
this relation between agents and environments has long been hypothesised, we have sought to formalise and prove it. We have shown that any agent capable of generalizing to a suffi- ciently wide range of simple goal-directed tasks, must have learned an accurate model of it's environment. Essentially, all the information required to accurately simulate the en- vironment is contained in the agent's policy. This implies that learning a world model not only beneficial, but neces- sary for general agents. Consequently, efforts to create truly general Al cannot sidestep the challenge of world modeling, and instead should embrace it to unlock further capabilities and address critical issues in safety and interpretability.
Good regulator theorem. This influential theorem attempts to establish a similar result to ours, than any agent capable of controlling a system is in some sense a model of that system (Conant& & Ross Ashby 1970). However, as pointed out in /Wentoorhh 2021), what the theorem actually shows is that, under several strong assumptions, agent that minimizes the entropy of its environment must have a deterministic policy. This deterministic policy is then interpreted as a model of the environment, with the actions assigned to different states corresponding to a state representation. This in spite of the fact that the policy (and hence the world model) could be a constant function, assigning the same action every state. We do not consider an agent having deterministic policy to be meaningful evidence that the agent has a model of its environment, and our theorem less ambiguously demonstrates that a world model capable of predicting the evolution of the environment has been Iearned by the agent.
Future work could extend our analysis to different classes of goals beyond Def. 3] and identify sets of simple 'univer- sal' tasks that are sufficient to imply an agent has learned a world model. These tasks may then be useful for training general agents. Our results also point to new methods for inferring an agent's beliefs from their goals and behaviour without making strong rationality assumptions. Future work could build on Algorithm T to develop algorithms for recov- ering world models that are more scalable or apply to more general environments, and using these to improve agent safety and interpretability. On the more foundational level, Theorem gives theoretical support to work in mechanistic interpretability looking to uncover implicit world models- for any agent capable of sufficiently general goal-directed behavior, the world model must be in there. Future work could use this necessity to derive new fundamental bounds on agent capabilities from the learnability of world models.
Theories of agency. That agents have world models foundational assumption for several prominent theories in psychology and neuroscience; from constructivist theories of perception (Gregory) 1980) to active inference (Friston 2010) and theories of consciousness (Safron 2020). Like representation theorems, these theories aim to provide ex- planatory models of natural agents, rather than proving that agents necessarily conform their assumptions. Our results offer strong theoretical justification for these frameworks by demonstrating that goal-directed agents must acquire world models to achieve degree of behavioural flexibility. Moreover, our findings remove the need to assume agents have world models a priori. Instead, we can assume a level of competency which implies their existence axisualce-aruuably a more defensible position as competence can be measured,
Impact statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
6. Conclusion
The idea that the microstructure of an agent reflects the macrostructure of its environment is not new, It can be traced as far back as Democritus, who claimed that "man is a microcosm" a miniature reflection of the cosmos (Allers) 1944)- and persists in contemporary scientific thinking- for example, Friston's assertion that "an agent does not have model of it's world-it it is a model" (Friston 2013). While
9

---

General agents need world models
A. Proof of Theorem 1
A.I. Notation
In the following we denote random variables as capital letters and lower case letters a denoting an event X = z
(equivalently, a value or state of X). We use bold letters denote sets of variables X X2, Xm } and æ denotes set of events {211, #2:...... ............... J. We use square brackets to denote proposition, e.g. [X = xr] returns True if X x and False otherwise. [(p) denotes an indicator function, which returns 1 if the proposition p is True and 0 if False.
A.2. Environments
Definition (Controlled Markov process). controlled Markov process (cMP) is a Markov decision process (MDP) without specified reward function or discounl factor. It is defined by the tuple (S, A, Pax((a) where S is the state space, A is the action space, and Pee (a) P(S = s' A o, S s) is the transition function.
First we assume the environment is described by a finite-dimensional, irreducible, controlled Markov process. For discussion of these standard assumptions see Puterman 2014 Sutton 2018
Assumption 1. We assume the environment is described by an irreducible, stationary, finite, controlled Markov process (Def. with at least two actions.
In the following we use S 8, and A = a₁ to denote the state of the environment and the agent's choice of action at time t. The sequence of successive environment states and actions are referred to as trajectory т = (So. ag. $1, a1....), with т denoting an infinite length trajectory and we introduce an index tijj = (si, ai...., St, ax) to denote a finite length trajectory between times i and j. In some settings we use ha: = (8t, ai,.... .x)) to denote a finite length trajectory that should be interpreted as history, i.e. a trajectory that has occurred, and which truncated at 8, (i.e. does not include a4).
A.3. Goals
Linear Temporal Logic (LTL) (Pnueli 1977 Baier & Katoen 2008 is a formalism widely used for expressing instructions,
goals and safety constraints for agents (Littman et al. 2017 et al. 2017 Hasanbeig et al., 2019 Dzifcak et al. 2009) Ding et al., 2014). LTL extends classical propositional logic by introducing operators for reasoning about sequences of states over time, primary among them being,
(Next): The property holds in the next state,
O (Eventually): The property will hold at some point in the future,
O (Always): The property holds every state from now on,
Ui (Until): One property holds until another becomes true,
which can be combined with standard logical connectives (AND A, OR V. NOT and material implication -) create complex goal specifications. The environment agent system is described by the joint states (st,ae) where 8; is the state of the environment and a, is the agent's action, at time t. Trajectories (paths) are sequence of these states which we denote (Su. 4u, $1, .). An LTL expression yp assigns truth value to given trajectory т, denoted T + pp, which is true if r satisfies yp and false otherwise, with evaluation beginning at L. = 0. For example, the trajectory of the environment-agent
system 5 = (sp = 0, ag = 0, $1 = 1, ag = O....) satisfies yp = [s = 0] ^ Ois = 1] as the agent is in state s = 0 initially (at time = 0) and in the next time step is state 8 =1. 1.
Our desire is to define a minimal class of goals that describe the simplest and most intuitive goal-directed behaviours. To this end we focus the most common definition of goals as being desirable states of the environment-agem system (Liu
et al. 2022). which must be achieved within some time horizon.
Definition 2 (Goals). A goal is an LTL expression of the form yp {[(ss a) E g]) where,
g is a set of gtalestates, a sub-set of the joint states of the environment-agen system (s, a) E A,
O a temporal operator specifying the time horizon for reaching g. We restrict to O E -1O,0 O. T} where O = Next, = Eventually, Now.
10

---

General agents need world models
Rather than considering time horizons the level of specific time indices I, which would require the agent be capable of a high degree of environment control (e.g. 'reach state S = 8 in precisely three time steps'), ) we focus two simple time horizons; goals that are achieved immediately (now, T), in the next time step (next, O), or at any time in the future (eventually. Q). Note that in LTL expressions the 'now' temporal operator is the identity, and we use T (True) to denote this.
As T[X = x)) = X = x we suppress
e.g. p = [(s, a) E g.). for ease of notation.
Example: consider the following goal for a cleaning robot: move eventually to the kitchen and in the next time step turn on the dish washer. This goal can be expressed as ip = O[S in kitchen| ^ O[A = turn on dishwasher)). trajectory т satisfies this goal (denoted т }= (p) 3 s.t. S. = in kitchen and A,+1 turn on dishwasher
Going beyond the simplest, one-step goal-directed tasks requires agent to achieve multiple sub-goals in particular order. Our aim is to define sequential goal 1/ in such a way that т |= 16 is true if and only if each sub-goal state 9: is reached by the agent in the correct order. Expressing these sequential goals in LTL can be cumbersome, so for notational neatness we define a sequential goal formula // (pI,..., (PL) which stands in for the more complex LTL expression, which is given by the the recursive formula in Def. 3 will not be necessary to define sequential goals general, as for our proofs we will focus on a simple class of sequential goals where the agent must reach a goal state either immediately or eventually.
Definition 6 (Sequential goals), & = (fI1, .P,,...,PPI) denotes the sequence of sub-goals (Def. 2 11,, P2.....,........................ Pa, where Pi = O,(((s, a) E gil). O E (0. T} and n = (e)) is the goal depth. sb can be expressed in linear temporal logic using the following recursive formula,
a(s, E gil a (pp....... =1=T O (1(s,a) Egi A (i)), O 0
(p1, il,,P2.... .2,...,. (PL)
(4)
a() & 9 E egl / (p2....... 0 =
where T = True and O = T denotes the Now (trivial) temporal operator, and the singleton (4) = 4p
By applying recursively we can convert any sequential goal into LTL expression. To understand 4 we can consider the simple case with two sub-goals v (fI1, (p2) and trajectory T (so, ao $1, (1,.1....... If O T, then ai is satisfied if (so, (8) E 91 and the trajectory starting from the next time step T = ($1, 01, 82, .., satisfies 422 For O = O the LTL expression we desire is (411,99 = [(s, a) $ gi [[[[s, a) E gi] A 9p2). To see this, consider the case where O2 = T, i.e. the agent's goal is to eventually reach gr. and then in the next time step to reach 92. If we attempt to express this goal as du = ([(ss,) a) E gı| A 4p2), note that r += v if 3 s.t. (s;, az) E gi and (St+1, d++1) E g2. This includes trajectories where the agent reaches 91 and then fails to transition to 92 in the next time step, arbitrarily many times, so long as eventually the agent achieves the desired transition. Our aim is express sequential goals where after satisfying sub-goal yo; the agent switches to pursuing the sub-goal (p+1 in the next time step, and if the agent fails to satisfy this sub-goal then it fails to satisfy the overall sequential goal. The expression [(s, a) & 9 [ a) gi] A 4p2) enforces the condition [(s, a) & gi] (the agent is not in goal-state 91) until they eventually reach 91 at some t, and their trajectory commencing t + satisfies 422, which captures the desired goal-switching behaviour.
Example: Consider the goal of transitioning eventually to S = s, then in the next time step transitioning to state S s' and then eventually returning to S s. This is captured by the sequential goal sb (P1, (2, P1) with sub- goals y = Og where 9I {(a, s) a E A} and ş 92 where 9i = {(a, V'Yaa E A)- Applying $ gives v = [(s, a) & gi]u[[(s, a) E gi) [[[s,, a) E g2] A ((((s,) a) E 91l)), which is satisfied by any 7 s.t. i) 3 t s.t. S. = and S₁r * s V t' < t, ii) S, = s' and ii) et > + 1 s.t. S., = s.
Finally, we consider the case where there are multiple sequential goals the agent could satisfy, each corresponding to a different course of action that would be sufficient to achieve an overall goal. For example, a doctor's 's goal of providing primary care to a patient can be satisfied by several mutually exclusive pathways, such as providing a primary diagnosis and prescription, referring to a specialist for diagnosis, and so on. Each of these is its own task described by a sequence of sub- -ob-lgaas (e.g. attempting primary diagnosis may involve question asking, performing an examination, etc), the outcome of which can inform the path the doctor takes (e.g. if an examination is inconclusive, they may refer to specialist). Each of these pathways therefore corresponds to a different sequential goal, and satisfying any of these sequential goals satisfies the overall goal of providing care to the patient.
To formalise this we consider goals that are disjunctions over multiple sequential goals. Let T denote the set of all composite goals, which includes all disjunctions over all sequential goals (Def. 6). i.e. dh, v E & = sb V v/ E V. For a conjunction

---

General agents need world models
over goals vi V v then agent satisfies vl" if its policy generates trajectory (80: 01 81, 02. that satisfies vi or v/.
Definition (Composite goals). A sequential goal db is an ordered sequence of sub-goals (Def. 2 vs (p)..... (i......P)),. where the agent must achieve sub-goal ip; before (fttI- The depth of a sequential goal the number of sub-goat depth( = n. composite goal is disjunction of one more sequential goals db V== 3, i.e. the agent must achieve any sub-goal ths achieve sb. The depth of a composite goal is the max depth of its sub-goals depth(<)) max depth( (v:). V is the set of all composite goals tp with depth(v) (1) S
Example: Consider the simple navigation task where a robot cleaner is required to clean the kitchen and the living room in any order, and then return to its charging station. There are two pathways that satisfy this; 1) clean the kitchen (eventually), then clean the living room (eventually), then return to the charging point (eventually). 2) the same as 1) but with the kitchen and living room swapped. Formally, the robot satisfies the overall goal if it generates a trajectory that satisfies the LTL expression & = ei V 2h where ز1 = (f1, :Pa), e = (122, PP, (P3),
O[[ss a) E {($1, a1 (1)H)) 422 = ([((s, a) E 92 = {(22, ()))),. Ps = O(s E 9s = (ss))) f)). $1 = in kitchen, $2 = in livingroom, $3 = at charging station
and 01 = clean.
A.4. Agents
We assume the environment is described by cMDP (Def. [ Due to the generally non-Markovian nature of sequential goals, we consider the most general definition of agents as maps from histories and goals to actions. goal conditioned agent is a policy <(a; he: ) where & is a (composite) goal. For simplicity we restrict our attention agents that follow deterministic policies. In general the environment may evolve non-deterministicallyy probability that - Val, which is determined by summing over the probabilities of all trajectories that could result from and that satisfy vb QQiu et al. 2024).
the objective is to maximise the
Definition 4 (optimal conl-condi agent). For a given set of goals (Def. an optimal agent is a goal-conditioned policy n² (ae 1)) where x²* is deterministic and satisfies,
π = arg max P(T n., 80)
(1)
V s.f. P(so) > O, where so is the initial state of the environment at L = O, and V 1h E w.
P(r += vb π. so) is the probability that the trajectory T generated by the agent under policy i satisfies the composite goal (LTL expression is given by Def. 3
p 50) >EPEpr P(T n. 80) F +))
(5)
In other words, an optimal goal-conditioned agent can achieve any composite goal va E v with the maximum probability of success attainable for every initial state Sy so that the agent could start in.
It is of course unreasonable assume that any realistic agent is capable of optimally satisfying any given composite goal & in its environment, and so we consider two relaxations of Def. 4 sub-optimal agents, and restricted the complexity of the goals the agent is capable of achieving.
Firstly, the most intuitive way to bound the agent's optimality carries over from regret bounds in reinforcement learning (Sutton 2018), but instead of providing a lower bound on the cumulative discounted reward compared to the optimal agent, we can lower bound on the probability that the agent achieves a given goal compared to the optimal agent. Secondly, achieving goals that involve larger number of sub-goals higher goal depth n. Def. 3 is more difficult than achieving short-term or myopic goals, and intuitively requires more knowledge of the environment. For example, if we restricted to one-step goals (O; = T and n = 1), simply knowing arg max, Pxxr (a) would be sufficient to identify an optimal policy, thus a full world model capable of simulating the environment is clearly not required. On the other hand, if an agent uses a world model to plan, effectively planning for longer sequences of sub- sub-goals requires an increasingly accurate model, as errors compound over time. Hence, in deriving our results it is natural to consider agents with some bounded maximum goal depth n, such that there is no guarantee that agent can satisfy the regret bound for sequential goals with depth greater than n.
12

---

General agents need world models
To this end, we propose the following definition of bounded goal-conditioned agent defined by two parameters; 8 (the lower bound the probability of achieving goal compared an optimal agent), and (the maximum goal depth for which the ó bound applies).
Definition 5 (bounded goal conditondd agent), bounded goal-conditioned agent a goal-conditoned policy x(a hy: v) satisfying,
P(T = & प., 80) 2 max P(T - 1 (1)
(2)
4 E V where is the maximum goal depth and so is the initial state of the environment 0.
A.5. Overview of proof of Theorem
At a high level, the proof of Theorem can be understood as deriving an algorithm that estimates Pas by querying the bounded agent's policy x (a, he, 1)) with different composite goals and observing how the agent's action choice changes. We consider composite goals where the agent is required to navigate (eventually) to specific state S = and take action A = transitioning to an outcome state, and then returns eventually to S (Figure D. We compare two goals, the first 2/2 (r, n) which is satisfied if the outcome state is S at most r times, out of a total of trials (taking action A = a in = 8), and the second (r, n) where the outcome is S = 8 at least r + times. An optimal agent can achieve the first
P
1-p
S
Figure 4: Figure illustrates the composite goal in the proof of Theorem
goal with a probability given by the cumulative binomial distribution Px S r) where X is the total number of 'successful" transitions (a, 8) + s', which occur with probability (a), and likewise the second goal can be achieved with probability Px(X > r). Hence, as we increase r from to n, an optimal agent will switch from pursuing the second goal to pursuing the first goal when reaches a value that exceeds the median number of successes, and we show is possible to identify this "oal switching" in the agent's policy <(a hes th (r, n) (22(,,))) The median is given by [Paa' (a)(n 1)J and we can bound P.r (a) with error that scales 1/n. For 5 >>> 0, the goal-switching behaviour of the agent cannot precisely determine the median, but bounds it within a region, and this allows us approximate Par (a) with error that depends on 5.
A.6. Proof of Theorem I
We now prove our main results.
Lemma 1. For a finite dimensional, stationary and irreducible cMPD (Assumption 7 there exists a deterministic Markovian policy Fz (a h (so, ao ..,, ST)) = Ty (a ST) that eventually reaches given state S = s' from any other state S 5 with probability 1.
Proof. Irreducibility states that for any s' * s there exists a finite sequence of actions that reaches any S = from any = 8 with non-zero probability. Therefore, for any S = s' we can construct a tree states by; i) starting with the root s' and defining the set Z S \ {s'}. ii) for each s" E Z, if 3 A a" s.t. (a") > then s" is a parent of s' in the tree and we remove s" from Z, iii) repeat for all parents of s' and on, until dimensional and irreducible, the resulting tree traverses the state space and is of finite depth, and by construction every state in the tree 8; has single child 8j and the tree contains no loops. For each we can associate an action a(s;) given by (s::) = arg max, P (a). Consider the Markovian policy 7(A = h = (So, Ao...., ST) ) = [a = a(sT)) )]. which attempts to move from the most recent state ST to s' by traversing the tree. For every state, there is a non-zero probability
0. As the cMDP is finite
that x succeeds in traversing the tree to the root S = s'. If the agent fails a given transition S, = s; + S = $,, the process of traversing the tree begins again from S,+1, and as the policy and environment are Markovian, each attempt to
13

---

General agents need world models
Traverse S = s' is independent. Hence, स attempts reach S s' with unbounded number of independent trials, each with non-zero probability of success, and hence eventually reaches 5 s' with probability
For s' the problem is identical except that the deterministic policy can take any action in S = Let S = $1 be the state that this transitions to. If $1 = then the policy has reached S = s. If 81 * s we follow the deterministic Markovian policy derived in the previous section which eventually reaches 5 = 8 with probability 1.
The following lemma allows us to simplify our analysis by letting us consider optimal policies in environments with extended action spaces, where determining optimal policies is easier.
Lemma Consider extending the action space of the environment cMDP with single action A ā, A' AU {a} where the extended transition functioo P' has (a) Pas (a) V a + ā, and Pa (ā) any valid conditional probability distribution. For any given composite goal the optimal policy for the extended action space A' achieves vp with probability greater or equal that for the optimal policy in the unextended action space A.
max P'(r == 8
πT, 80) 2 max P(r 1= 1/2 80)
Proof. Let P (a denote the new transition function in the extended environment. As P. (a) = Pas (a) Va ā, the probability of any π that does not take action A = a satisfying any given composite goal v is the same in the extended and unextended environments. As the optimal policy A over does not take action = ā (as à E A), then
P'( v I 5b) = P(T F | 80)
(6)
Therefore there exists a policy for the extended action space (namely ) that achieves with the same probability the optimal policy for the unextended action space. Therefore,
max (T 17
4 IT, s0) 2 max P(r } & TT, sp)
We now derive Lemmas that let us factor and simplify sequential goals.
Lemma 3. For vb = ..p.....,,11)) and a cMP obeying Assumption I if 91 = O(S = 89, A = agl) and T(a; (4)) =
(a, st) is stationary Markovian policy that eventually reaches S Sg and takes A 0g from Su su with probability
1, then,
P(T + (111, .2............ ... ...) T, 50)
P(T -= (p22, ................................ ,.L) TT)
Proof. Using Def. we can simplify (411, 12,,,,,,,,,1111. = 1S + s syl (1p2,... ... (t.)). If so Sg then yo is satisfied at t = 0 and ạ is trivialised, i.. P(r - (2., (PL) 8g) = P(T F (122 (122..... .,, (PL) TI, 8g). Therefore need only consider the case where So # 8g-
As ग reaches S = 8g from So = 8n with probability 1, every trajectory generated by π eventually reaches S = 8, by assumption, and at some > as so * sg. For a given J let T be the time step that r first reaches sg. Because π is deterministic and Markovian, and the environment Markovian, then for so # Sg we can express,
P(T so, T) II P(s: 8i-1, s1 (x:1) SS 8gy Tyy T' sg))
(8)
where n² is the policy for > 0, and as x' is stationary we have that P(Tr+1 Sr = 8y, n' R'(S, sy)) P(rr+1
14

---

General agents need world models
Sg. TT (8g)). Let bor be the trajectory up to ST &g. Using the LTL expression for ae from Def. 6 givees.
P(T + (0:.9p2.... (2.;)))).. 1 n, so) = Σ
P(hr 80: ④))
Σ P(Tr+1
| he,, ((r + [S + sy]u[[S - =8yl A (1p2...., ((L)))
Ar
1241
(9)
(10)
P(TTl | 80:
+ + snl) Σ
P( |T, (bbr)) T (p2,...,,
lvT
TP+1
(11)
Σ P(hr so: T) Σ P(Tr+1 | (g: (s))) + (p22....,($1))))
(12)
hT
T++1
Σ P(hrl 80: P( F (122..., | ST = 8g, A, = T((g))
(13)
hT
P(r F (122..., 8g. T))
(14)
where in the last line we have used Ene P(hT n, 80) = 1 by assumption (as π reaches S 8g from So = so with probability 1).
Lemma 4. For 1b = (f),, P2, Pa....,, PPL) and a cMP obeying Assumption 7 if = O(Is E gil) and 92 = O[S
$g. A ogl) and π is a deterministic, Markovian policy then
P(r L # s0. P(S1 91 so, (T) P(T - (P9 .......,... (P3.....,,P1.. 1 1.g. TT)
Proof. Using Def. and Tk (sk, ......) .) get,
P(T F vbl 80, T)
Σ P(Ti 90, 00 T(so)) E gi) A (1))))
(15)
Σ P(n 80, G0 = ( (P2, (p2....,,
(16)
P(si 50, 00 - ((0))) ( Σ P(T2 so, ao T(S)), = ((s))\(([T += (122................... (p2))),)))))))
(L)))
(17)
Σ P(1 | so, a0 = =<s))) Egi)) Σ P( | 01 = =<>)))][(( F (12..... (L)))
(18)
To
Σ P(si | 50, 00 = ( (g)))))))))))))))) = (12...., (p)) 81 u: = x(1))
(19)
Σ P(s so, 0n = = (T) (133,... ,pL) x)
20
$1
= P(S E 91 | so. P(T (p.....,.p)) | x))
(21)
where in line 20) we apply Lemma 3
Lemma 5. For vb (12,, ................................
... (L)
,L)) and cMP obeying Assumption 1 if = T([A =a)) and is deterministic
policy s.I. (s0))= then P(r }= vé | 80, T) P(T -= (12,....,
550 T)
Proof. This follows simply from Def. 6 and that the policy is deterministic,
P(T - /b 8p, T)
P(n | so, Go = <(s))) (Ao = a) ^
(22)
Σ P(n | su, Go = a - ((o))) = a))((I= +
(23)
P(7 }= (f2, .p))) 50, T)
(24)
15

---

General agents need world models
where 7k (8kr (g.-..)-
We now derive a family of composite goals for which the optimal policy satisfies the goal with a probability given by the cumulative binomial distribution for which the probability parameters is a specific transition probability. Lemma 6. Let (r, n) be the composite goal which is the disjunction over all sequential goals of the form
vb (P1: (P2, (P3, (P2, (P3. 122 1P3)
times
where the agent
i) takes action A b, 4p1 [A=
= b), and then transitions eventually to S and takes action a, 42 0[[S
8, A al),
ti) transitions next to a goal state which is either 43 = 5'1, or S 433 OiS + s/) =
iii) returns eventually to S = s and takes action A = a, and repeats the cycle ii)-iii) a total of n times, with the transition P = SS' = s) occurring r times and the transition 4 = |S + s'1 occurring n r times.
For + s', the optimal policy achieves this goal with probability,
n!
max P(r - (r, 8o) (n - r) Paw Pa)((a) Pa)(
(25)
v.. Each v involves specific ordering of the r sub-goals ips = |S = s] and the n r sub-goals 4 = [ # s'), hence they are mutually exclusive, i.e. Ar such that [r + vhl A = w/y for any the v in the disjunction s.t. db + e.y. and hence.
Proof. Let e = V,
P(r + n)) k, s0) P P(T - 4bs ग., sp)
(26)
First we evaluate max, P(T F (r,m) n., 80) in the environment with the extended action space (Lemma with A' = A U {a). (a) = AA 8" E S and Pa (a + a) = (a). L.e. we extend with the action A = ā which returns the agent to = from any state with probability 1. Note that until the agent has returned to = a total of n times, in order to satisfy any sequential goal ah; comprising the composite goal (0 n) the agent must take action A = at f = and A when it in S s. The only freedom left the agent how returns to S (to satisfy (22) from whatever state it transitions after taking A in S 8, and for the extended action space it can achieve this immediately with probability simply by taking action A a. Therefore, the following policy is optimal for satisfying vi(n,, r) with the extended action space,
[[[aa -]), t T([a' = a] ^ [st = +)) + I([a' = a [s+ # s)), 0
#* (A d' (so, ao .... 8t))
(27)
iee the agent first takes action (required to satisfy (Pi). and from then on takes action a 8 (required for PP and ( and otherwise, which returns the agent immediately S s. Applying Lemma 5 and Lemma allows us to eliminate the first y01 and yo2, giving
P'(T +
(2, P3, P....., P2, Sp'
|"
(28)
rXP2is9 and (n-r)xx2214)
where #" is #* for t > 0, which we denote म* from on for ease of notation, and can treat f* as a stationary policy. Repeatedly applying Lemma 4 to 28 gives.
P'(7 } tha x 80) = Pas((aa" (a) Pas (a))
(29)
16

---

General agents need world models
Applying (26 and noting (r - vi n², .8) = (T my 88) for all i,j for (rr,, n) V, th and the total number of sequential goals comprising (r, n) is given by the number of combinations of size from objects (n transitions, of which are > 8'), and so recover,
n! (n r)l!! Pee P (a)
max (T (5(r, n., nT
(30)
Finally, we construct a policy स in the original (unextended) environment, and show that this saturating the upper bound in (30) and so by Lemma is optimal, therefore Equation (25) holds. By Lemma] T there exists a deterministic Markovian policy oe 8) that transitions eventually to S = s from any state with probability Let,
I(la' - b]),
0
((a st)
(a st), t> 0 and +
(31)
[([a' = a)) t and 8; =
Note ग is identical to #* except that instead of taking action A = ä in S - (as this action does not exist) the agent follows Tea As is deterministic, stationary and Markovian, and eventually reaches S = s with probability from any S = s', so we can apply Lemma and Lemma 4 as before giving,
P(r - d; म. so) Pas (1) Pas (a))
(32)
hence क is optimal, and using nCr nl/((n r)rr!) we which saturates the upper bound implied by 30) and Lemma 2 recover (25).
We now in position prove main theorem.
Theorem 1. Let (a) P(S++1=s' = S. - s) be the transition probabilities of an environment satisfying Assumption I Let ı be goal-conditioned agent (Def. 55) with a maximum maiimufaailure rate 6 for all goals v E D, where L, the set of all composite goals with maximum goal depth 1. n fully determines model for the environment transition probabilities Per (a) with errors satisfying
2P (a)((()(1 Pas (a)) (n - 1)(1 5)
Perr (a) - Pao S
for any n, 8, and for 8 < 1, n >> the error scales as,
(a) (((5m))
Proof in Appendix
Proof. Let tha (ks, n) denote composite goal as Lemma which a disjunction over all sequential goals of the form
t = (pPo P1, P2. $1,
(33)
times
where the agent
i) takes action A = a (sp0 = [A=a)) and then transitions eventually to S = s and takes action A = a (pp O(S
s, A = a])),
ii) transitions next to goal state which is either S = s' (422 = O = s()) or S + s' (42 = Ols s().
iii) returns eventually to S = s and takes action A = a (f11), and repeats the cycle ii)- a total n times, with the transition S22 Ols' = occurring r times and the transition &/22 O(s + 8'] occurring n r times, for all S
17

---

General agents need world models
Lee. the agent's goal is to first take action A and then achieve the transition (a, 8 at most & times out of attempts. Note that n attempts corresponds to goal depth of 2n 1.
Consider the sequential goals tha (k, n) that is identical to Vi (k, n)) except that the first sub-goal i) takes action A = b instead of A = at time t = O, and in iii) we have r > k instead of r S k. Le. the agents goal is to first take action A = b and then to achieve the transition (a, 8) + s' more than &e times out of n attempts.
Consider the composite goal (k, (k, n) V (ko(k, m) for any pair of action a, b such that a # b (we assume there are at least two distinct action in Assumption D.
Note that dh (k, n) and (k, r²) are mutually exclusive, T - (k, = T F vo (A: rt) and vice versa, hence,
P(T F Va, (k, n)) | ,,, su) = P(T - (k, n)) T., 80) + P(T + Uh n)) ग,, 80)
(34)
and for any only one of the terms on the right hand side is non-zero. Hence we can evaluate max, P(r - (k, n)) T, s0)) and max, P(r FF (k,,k, m) nt, 8o) separately.
Consider a bounded goal-conditioned agent (Def. 5). As the policy is deterministic by assumption, the agent is can only choose one of two sub-goals to attempt to satisfy, via (a n) or (k, n), depending on its first action choice Ag. If (aa so) = I( = al) then the agent is pursuing Va (k: n). For Vaa (k; n) Vz ths all thi 3/ are mutually exclusive for w/s + 1ig. T F vi = T k 1 and vice versa, and hence,
P(T Va (a,k,, ) n. s0)
Σ P(T F abs JT, so)
(35)
and by Lemma 6 the maximum probability that this goal can be satisfied is given by,
h
max P(T Va n)) T. su) = Σ Pa(X -) = Pn k)
(36)
where
n!
rr) (n r)rr Pas (a)
(37)
is the binomial probability mass function and (x S k) is the cumulative distribution function.
Likewise if r so) = I[lao bl) the agent is pursuing (k, n)), which can be achieved with maximum probability,
max P(r = (k, 80)
Σ Pa(X= = P k) r=
(38)
Finally T(ao | so) = I[aa = d')) where a' & (a then the agent satisfies vha (k: n) with probability zero.
By assumption the agent's policy is deterministic, and max ( S k), Px(XX k)} > 0, so for any n, k the agent must take action A = A = b at = 0. Therefore for any given n, ls the agent's policy r(ao so; (k,s(k, selects either ao = or ag b, and the choice of Ao for a given & witnesses the following inequalities;
raan I s0: (k, n)) T(ao al) = Px < k) 2 Pa(x k)(1 5)
(39)
T(ao | so: (k, = [[ao b]) = Px(X R) 2 Px < 41 8)
(40)
For ease of notation we denote (a) = p. The median of the binomial distribution X m is an integer 0 S m S that satisfies npp 1 I m I np + 1. The proof proceeds by incrementing from 0 to n, increasing (, < k) while
decreasing (x > k), and finding the smallest value k* such that P.(XX > k² - 1) 2 Px < k- - 1)(1 - 5) and (X < k*) 2 Pa(X > (1)(1- ([[1-00 5). If the agent always chooses Ao = a we set k* = O, and if they always choose Ap = we set E. = n. This will turn out to be equivalent to a sparsity bias in the procedure for estimating (a), as it will result in us treating any transition probability below a given threshold value as O. or above a maximum value as
Note that Pn (X: > 0) = 1, P. I 0) = O. and P, > n) = O, (x S n) = 1, so for any 8 < there must
18

---

General agents need world models
exist 0 k* satisfying 39 and (4)). Using ( k) 1 (x s k), (x k - 1) Pr k) and
Px(X k - 1) (x k) these inequalities simplify
1 1 8
P(X
(41)
2
1-6
P(X2 2 2
(42)
Note that the median m satisfies (x 2 m) 2 1/2 and (x S m) 1/2, so for 6 we will recover the median exactly, and ò > 0 constitutes relaxation of the bounds on the median, which we will show results in k that has a bounded distance from the mean np.
We derive two bounds on k", first in the case where ò' is small and n is large. To derive this first bound we use Berry-Esseen theorem, which allows us to bound the distance of the (normalised) cumulative binomial distribution from the cumulative normal distribution,
X np np
Pr
< k - +(X S k)
SA
(43)
p)
where & is the cumulative normal distribution and A Cplvá where C constant satisfying C S 0.4748 and P (1 2p(1 p))/ vp(1 pp). For simplicity we relax this upper bound by taking.
(44)
2//p(11 p)
which is larger than Cp/Va. Defining Y = (X np)/ /np(11 p), and using PY 2 k) =1 P(Y 1 k 1),
42
and 41 become,
h- np Y
1 1- 8
$
A
(45)
v /np(11 (1 - p))
2
k* np 1
1 2
Y
+4
(46)
v /up(11 - p)
(47)
which can be rearranged to give,
k' - mp
1 1- 8
--1
2- A
(48)
npp(1 p))
bn - np -
< -1
2 +A
(49)
Vnp(L -p)
(50)
For 8 < 1 and A < 1 we can approximate the right hand side of 448 and 449
using the Taylor expansion of +
(yy at
= 1/2,
s - = + = eVTT =v2 (
+
<< 1
(51)
which is a valid approximation when ²² << 1. We therefore recover the bounds,
1
8
1
b*
2 mp 2~
2 - p)
+
A
(52)
2
1
8
mp S
22mmp(1 pp)
+
+
(53)
2
4
19

---

General agents need world models
Using 6 (h* 1/2)/n /n as our estimate of therefore satisfies
2xp(1 p)
5 A
1
10 2l V
+
+
4
2n
Tp(1 - p)
1
=
+
2
8n
n2
2
which is valid for 8² < 1 and - the approximation errors scales as ((6/vT) + (1/n))
11/(pp(1111m - pp) < 1 i.. up(1 - p) >> 1. We have therefore shown that in this regime
Finally, we derive an absolute error bound for the estimate P that is valid for all values of p. n, 6. Le. for * and/or np(1 - p) z k" can be relatively far from the median, and we require bound that is satisfied for the tails of the cumulative binomial distribution. To this end we apply the one-sided Chebyshev inequality,
Px 2 1 to) I 1+
(54)
where μ np and a /np(11 - p). Changing variables t (k* np) / in 54) yields,
1
P(X 2 k*) v
(55)
1 1+
(b* 2
mp(1 pp)
which combined with 42
yields,
np(1 1 p) 1- 5
|k - npl
(56)
Using p : k//n our estimate of the transition probability gives,
p(1 - p) n(1 - 8)
b pl - V
(57)
Finally, as attempting the transition n times corresponds to a goal depth of 2n + 1, we arrive at our final expression.
Note that the bound in Theorem asserts that we can identify p {0, with perfect precision. While this appears surprising first, note that the sparsity constraint we previously enforced when selecting k. means that we estimate all sufficiently small p Poo (a) 0 and similar for Psr (a) 1, hence for deterministic transition probabilities we do recover the exact value. This is also intuitive from the definition of the bounded goal-conditioned agent Def. 5 as for any
5 < 1 the agent will never choose sub-goal v if Pa (a) 0, and hence any such transition will always be assigned k.* = 0 which yields an estimate (a) = O.
B. Proof of Theorem 2
Theorem 2. Let the set of myopic goals Y myopie be the subset of depth-I composite goals T such that the goal state(s) must be attained immediately after the agents first uction, & Ol a) E g). We define optimal myopic agent policy nt a((a he, 1)) that is optimal for all 1 E L myopic. For an environment satisfying Assumption ] any bounds on the transition probabilities (a) Pas (a)) S c than can be determined from x² are trivial (c 1) and tight. Proof in Appendix B
Proof. We will prove this by contradiction, determining partial information of the environment transition function that is sufficient to construct optimal myopic agent, and showing that this partial information is insufficient to bound the transition probabilities (the trivial bound is tight). Hence, there can exist no procedure that bounds the transition probabilities given this partial information, and so no procedure that does so given the optimal myopic policy.
Any 2b E myopi is of the form P V P1 V ... V yo where si = O([(s, a) E g.). Using the transitivity of the Next operator, this can be simplified to = O(((s, E gil v.. V [(s, a) E 9k]), and using y = 9i Uga ... U gk we get
20

---

General agents need world models
[s1, a1) E yf where Y S is some arbitrary subset of S. For Ag the probability that di is satisfied is given by P(r v/ n., 80) P(s1 y a, 80)) The optimal agent therefore returns action
(ao 50; v) arg max P(s y 0, so)
(58)
Let a" ('(.. v) = arg max P( E y a, 50). We can construct optimal policy x² <'(ao Soi 15) given A (a"(so. y) so. Y S S,Y = y) as x (ao s0; 80; = T(ao = a a"0, y)l)- Next, we show that the set of transition functions that are compatible with any given A includes all values Per (a) E [0, 1] for any given transition, and so A' does not partially identify (a). This can be seen simply by choosing Pa. (a) Pas' (i.e. the transition probabilities the same for all actions). For any choice of Pa.' E [0; 1]. such transition function is compatible with all possible A'. Hence, for any given A the set of compatible values of Pas (a) is [0, 1). and knowing A"' provides no bound on the possible values of any given transition probability (a) (i.e. partial identification is impossible (Bellot 2023)). Hence, as T is function of A", x²" can provide no con-trivial bound on Par((a).
21

---

General agents need world models
C. Algorithms
First we present the pseudocode for the procedure Algorithm I used the proof of Theorem To derive error-bounded estimates of the transition probabilities (s)(() given the regret-bounded goal-conditioned policy x(a hy; vb). We then present Algorithm 2 an alternative algorithm for estimating P..((a) which has weaker errors bounds than Algorithm but significantly simplified implementation. Note that in both Algorithm [ and Algorithm 2 we employ linear search of k. but we can greatly reduce the complexity in practice e-g. by performing binary search over k E [0. rz). We use Algorithm 2 to generate our experimental results in Section 3.1 and Appendix D Note that by looping over all transitions (s, a, s') and
applying Algorithm we can recover the full transition function.
Algorithm Estimate Transition Probability Pas (a) from Policy
Require: Goal-conditioned policy =(ar/he: v))
Require: Choice of state s, action a, outcome
Require: Precision parameter N (related maximum goal depth 2n
Require: An alternative action b + 1: function ISTTIAATTRAASSTTTRRRRRLLLLTT s,
2: Initialize k* < n
3: for = to n do
4: Define base LTL components:
5:
4P0 + [Ao = a]
6:
Take action a
7:
% + -Ao b]
8:
Take action b
9:
+- O[A S = x]
10:
Transitions eventually to state and takes action a
11:
L2 + -+iS= s')
Transition Next to state
2 +OIS + s']
Transition Next any state other than s!
15:
Define composite goal:
16:
tho + (p1,42)
17:
Sequential goal labelled Fail
4
18:
1 + (42))92)
19:
Sequential goal labelled Success
(h, n) V sequences with r successes (pPo, (who or xn))
21:
thokk, n) + V sequenoos with r>> successes (1/6- (tho or (1))x)
LTL expressions calculated with Def. (k, vaa (kk,, n) V vby(ki n) ag T(agl 88; (k,,((k, n))
23:
24:
25:
Query the policy for the first action
26:
if 0g then
27:
b -
28:
break
29:
Found smallest s.t. where agent prefers goal involving S
successes
Estimate (a) + (k- 1/2)/n
31:
return Pa.((1. (a)
Algorithm requires the agent to generalize to simpler sequential goals than Algorithm
22

---

General agents need world models
Algorithm 2 Simplified method for estimating Transition Probability (as((a) from Policy a with weaker error bounds than Algorithm [
Require: Goal-conditioned policy (aa ((allhes v))
Require: Choice of state action a, outcome s'
Require: Precision parameter N (related maximum goal depth 2n +
Require: An alternative action b +
I: function
8, s',,,,,
2: Define base LTL components:
3: :Po f- [Ag = a)
4:
Take action a
5:
* + [Ap bl
6:
Take action b
7:
+ ([A = 0, S =
8:
Transitions eventually to state s and takes action a
4
9:
P22 <- O = s'
10:
Transition Next to state
2/ OiS s'] Transition Next any state other than 8
13:
Define sequential goals:
14:
Vo + (Po, 11, (P2)
15:
vo t (Po. $1. (91)92)
16:
aa. tha V 1/%
17:
ag + Taallsoite Va,b)
Query the policy for the first action
if ao then
20:
Witnessing Pas((a) 2 (a)) 5)
21:
Vaa < (Po, (11,,2))x)) 422)x))
22:
(s(k) + (Po, (1I, 2 for = 11=1ton do
23:
24:
(ka((k) t Vo V (b))
an + ma0o000; (k))
Query the policy for the first action
27:
if 00 then
28:
6* x k break
29:
30:
Estimate
P.x (a) + Solve(P" =
31:
return (a)
32:
else
vb (Po, (V1, (/2xxn dha (ba(k) t (Pou, (1/,, ; 2h22 xk) for 1: to do
34:
35:
36:
(k) - (k) V 1bb
37:
au + su: (k))
38:
b Query the policy for the first action
39:
[g then
40:
break
42:
Estimate P.r/ (a) +- Solve(Pk* -1/2 (1 P)))
43:
return (a.
23

---

General agents need world models
D. Experiments
Here we detail the experiment setup including the environment, agent and results.
Environment. Our environment is a cMP Def. [ comprising of 20 states and 5 actions, and satisfying Assumption | has randomly generated transition function with a sparsity constraint such that each state-action pair has at most outcomes that occur with non-zero probability, so as to ensure that navigating eventually to given goal-state is non-trivial (e.g. is not achieved by all deterministic policies).
Agent. The agent is model based, with the model learned from experienced generated by sampling state-action trajectories from the environment under the maximally random policy of a given number of time steps Neamples e (500, 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10, 000}. Note that Algorithm 2 does not have access to the agents internal world model (the algorithm takes as input only the agent's policy). Algorithm different composite goals of the form (n, m) and the agent determines the optimal policy with respect to its world model, which corresponds to I) at f 0 taking action A = if the agent believes (a)) (1 Pee' (a)) else A = b 2) identifying a deterministic policy that eventually reaches the target state S = from any other state, and taking action A = a in S 8.
the agent with
Experimental setup. We train 10 agents for each sample size Naamples with a different random seed for the experience trajectories, and take the average of the experimental results over the set of agents with the same sample size. For each agent we run Algorithm for different max goal depths N {10, 20, 50, 75, 100, 200, 300, 400, 500, 600), and record the regret ö for each input goal, which is 1 P(T += 2a,, P(T }= Vn.. x²) where P(T + dham IT) is the probability the agent achieves the goal agent's 's policy and P(T - &n.m x²) is the probability that the optimal policy achieves the goal. We then calculate the average regret (5) all goals the agent is queried with by Algorithm 2 and the average error (c) (averaged over all state-action-outton
tuples) for the estimated transition function returned by Algorithm 2
We determine
Nmax (()) = k) through least-squares regression of N (goal depth) v.s. (6) for a given agent.
Results.
Table 1: Mean Error and Standard Deviation for Different samples and Ndept Values
Naya
Nasppta
2000
4000
5000
7000
9000
10000
0.171
0.007
1.113
0:305
0.111
0.009
0,007
0.000
0.08%
01082
0.003
0.0015
0.004
0:075
0.304
0.072 + 0.005
0.066
0.305
20
0.160
0008
0.118
0.005
0.8N8
:: 0.005
0,073 2: 0,004
0.864 :: 0.002
(1009
00,033
0.054
0.005
0.052
4: 01003
0:049
0.303
0.047
:: 0.0022
0.344
0.003
50
0.157
+ 0.08
0.108
0.008
0.077
+ +.0.05
0.063
0.003
0.054 + 0.083
0.488
+ -0.000
0.044
0.005
0.041
+ +-0.03
0.039
0.303
0.037 +-0002
0.034 + 0.002
75
0.157 1 0.008
0.107
0.008
0,075 1 0.005
0.061 1 0.003
0,052 1 0.003
0.047 1 0.0002
0,042
0.002
0.040 1 1.0003
0.038
0.003
0.035 1 0.002
0.003 1 0,002
100
0.156
0L008
1.106
0:305
0.074
:: 0.004
0,000
0.003
0.051
= 0.0022
0.046 :: 01,02
0394
0.001
0.099
: 0.03
0.037
0.305
0.034 :: 0.002
01032 0.002
200
0.155
0.068
0.105
0:007
0.073 0.004
0.059
1::::0000 0.003
0.050 : 0.002
0.045
0.00
0.040
0.002
0.038
0.003
0.036 0.003
0.634 + 0.002
0.031 0.002
300
0.155
0.008
0.104
0.004
01058
0.002
0.044
0.040
0.03
0.0% 0.003
0.002
0.011 0.002
0.008
0.101
0.004
0.058
0.002
0,041
0,040
0.003
0.035 0.003
0.053
0,001
0.002
500
0.008 0.155
0.104=
0.307
0.004
0,05% 0,003
0.029 = 0.802
0.044 0.002
03940=
0.012
0L003
0:035 0.003
0.033
= 0.002
0,001 0.302
600
0.155
0.008
0.007
0.072 + 0.004
0.058 0.003
0.040 + 0 0.00
0.044 0.002
0.040
0.002
0.037 + 0.003
0.035 0.003
0.034 :1 0.002
0,031 0.002
References
Abdou, M., Kulmizev, A., Hershcovich, D., Frank, S., Pavlick, E., and Søgaard, A. Can language models encode perceptual structure without grounding? a case study in color. arXiv preprint arXiv:2109.0662 2021.
Abramson, J., Adler, J., Dunger, J., Evans, R., Green, T., Pritzel, A., Ronneberger, O., Willmore, L., Ballard, A. J., Bambrick. J., al. Accurate structure prediction of biomolecular interactions with alphafold 3. Nature, 630(8016):493-55333 2024.
Alain, G. and Bengio, Y. Understanding intermediate layers using linear classifier probes. arXiv preprint arXiv:1610.01644. 2016.
Allers, R. Microcosmus: From anaximandros to paracelsus. Traditio, pp. 319-407, 1944.
Amin, K. and Singh, S. Towards resolving unidentifiability in inverse reinforcement learning. arXiv preprint
1eXiv:6601.0656 2016.
Amodei, D., Olah, C., Steinhardt, J., Christiano, P., Schulman, J., and Mané, D. Concrete problems in ai safety. arXiv preprint /606. 06565, 2016.
24

---

General agents need world models
Armstrong, S. and O'Rorke, X. Good and safe uses of ai oracles. arXiv preprini 17X 2017.
Äström, K. J. and Murray, R. Feedback systems: an introduction for scientists and engineers. Princeton university press, 2021.
Baier, C. and Katoen, J.-P. Principles of model checking. MIT press, 2008.
Baker, C. L., Tenenbaum, J. B., and Saxe, R. R. Goal inference inverse planning. In Proceedings of the annual meeting of the cognitive science society, volume 29, 2007.
Bareinboim, E., Correa, D., Ibeling, D., and Icard, T. On pearl's hierarchy and the foundations of causal inference. In Probabilistic and causal inference: the works of judea pearl, pp. 507-556. 2022.
Bellot, A. Towards bounding causal effects under markov equivalence. arXiv preprini urXiv:2311.07255 2023.
Bengio, Y., Cohen, M. K., Malkin, N., MacDermott, M., Fornasiere, D., Greiner, P., and Kaddar, Y. Can a bayesian oracle prevent harm from an agent? arXiv preprint arXiv:2408. 052844 2024.
Bengio, Y., Cohen, M., Fornasiere, D., Ghosn, J., Greiner, P., MacDermott, M., Mindermann, S., Oberman, A., Richardson,
J., Richardson, O., et al. Superintelligent agents pose catastrophic risks: Can scientist ai offer a safer path? arXiv preprint arXiv:2502. 15657, 2025.
Black, K., Brown, N., Driess, D., Esmail, A., Equi, M., Finn, C., Fusai, N., Groom, L., Hausman, K., Ichter, B., et al. To A vision-language-action flow model for general robot control. arXiv preprint arXiv:2410.24164 2024.
Box, G. E. and Draper, N. R. Empirical model-building and response surfaces. John Wiley & Sons, 1987.
Bratman, M. Intention, plans, and practical reason, 1987.
Bricken, T., Templeton, A., Batson, J., Chen, B., Jermyn, A., Conerly, T., Turner, N., Anil, C., Denison, C., Askell, A., et al. Towards monosemanticity: Decomposing language models with dictionary learning. Transformer Circuits Thread, 2, 2023.
Brohan, A., Brown, N., Carbajal, J., Chebotar, Y., Chen, X., Choromanski, K., Ding, T., Driess, D., Dubey, A., Finn, C., et al.
Ri-2: Vision-languagc-action models transfer web knowledge to robotic control. arXiv preprint arXiv:2307.15878, 2023,
Brooks, R. A. Intelligence without representation. Artificial intelligence, 47(1-3):139-155 1991.
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Brunke, L., Greeff, M., Hall, A. W., Yuan, Z., Zhou, S., Panerati, J., and Schoellig, A. P. Safe learning in robotics: From learning-based control safe reinforcement learning. Annual Review of Control, Robotics, and Autonomous Systems, (1):411-444, 2022.
Bush, T. Chung, S., Anwar, U., Garriga-Alonso, A., and Krueger, D. Interpreting emergent planning in model-free reinforcement learning. The Thirteenth International Conference on Learning Representations, 2025.
Camacho, A., Icarte, R. T., Klassen, T. Q., Valenzano, R. A., and Mcllraith, S. A. Ld and beyond: Formal languages for reward function specification in reinforcement learning. In IJCAI, volume 19, pp. 6065-6073, 2019.
Chockler, H. and Halpern, J. Y. Responsibility and blame: A structural-model approach. Journal of Artificial Intelligence Research, 22:93- 115, 2004.
Christiano, P., Cotra, A., and Xu, M. Eliciting latent knowledge: How to tell if your eyes deceive you. Technical report, Alignment Research Center, 2021.
Chua, K., Calandra, R., McAllister, R., and Levine, S. Deep reinforcement learning handful of trials using probabilistic dynamics models. Advances neural information processing systems, 31, 2018.
Conant, R. C. and Ross Ashby, W. Every good regulator of a system must be a model of that system. International journal of systems science, 1(2):89-97, 1970.
25

---

General agents need world models
Dalrymple, D., Skalse, J., Bengio, Y., Russell, S., Tegmark, M., Seshia, S., Omohundro, S., Szegedy, C., Goldhaber, B., Ammann, N., et al. Towards guaranteed safe ai: A framework for ensuring robust and reliable ai systems. arXiv preprint MrXiv:2405.06624, 2024.
Demri, S. and Schnoebelen, P. The complexity of propositional linear temporal logics in simple cases. Information and Computation, 77((1):4-1033, 2002.
Ding, X., Smith, S. L., Belta, C., and Rus, D. Optimal control of markov decision processes with linear temporal logic constraints, IEEE Transactions Automatic Control, 5965)1244-1225,, 2014.
Driess, D., Xia, F., Sajjadi, M. S., Lynch, C., Chowdhery, A., Ichter, B., Wahid, A., Tompson, J., Vuong, Q. Yu, T., et al. Palm-e: An embodied multimodal language model. In International Conference on Machine Learning, pp. 8469-8488
PMLR, 2023.
Dulac-Arnold, G., Mankowitz, D., and Hester, T. Challenges of real-world reinforcement learning. arXiv preprint TrXiv:1904.12001 2019.
Dunbar, R. I. The social brain hypothesis. Evolutionary Authropology: Issues, News, and Reviews: Issues, News, and Reviews, 165) 1998.
Dzifcak, J., Scheutz, M., Baral, C., and Schermerhorn, P. directives into temporal and dynamic logic representation for goal management and action execution. In 2009 IEEE International Conference Robotics and Automation, pp. 4163-4168. IEEE, 2009.
What do and how do it: Translating natural language
Fagin, R., Halpern, J. Y., Moses, Y., and Vardi, M. Reasoning about knowledge. MIT press, 2004.
Farquhar, S., Carey, R., and Everitt, T. Path-specific objectives for safer agent incentives. Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 9529-9538, 2022.
Farquhar, S., Varma, V., Lindner, D., Elson, D., Biddulph, C., Goodfellow, I., and Shah, R. Mona: Myopic optimization with non-myopic approval can mitigate multi-step reward hacking, arXiv preprint arXiv:2501.13011, 2025.
Friston, K. The free-energy principle: a unified brain theory? Nature reviews neuroscience, 11(2):127-138, 2010.
Friston, K. Active inference and free energy. Behavioral and brain sciences, 36(3):212, 2013.
Ghallab, M., Nau, D., and Traverso, P. Automated Planning: theory and practice. Elsevier, 2004.
Glanois, C., Weng, P., Zimmer, M., Li, D., Yang. T., Hao, J., and Liu, W. A survey on interpretable reinforcement learning. Machine Learning, 1388))5847-5890, 2024.
Gregory, R. L. Perceptions hypotheses. Philosophical Transactions of the Royal Society of London. B, Biological Sciences, 290(1038):181-99, 1980.
Gurnee, W. and Tegmark, M. Language models represent space and time. arXiv preprint arXiv:2310.02207,
Gurnee, W. and Tegmark, M. Language models represent space and time. arXiv preprint arXiv:2310.02200) 2023b.
Ha, D. and Schmidhuber, J. World models. arXiv preprint
2018.
Hafner, D., Lillicrap, T., Fischer, I., Villegas, R., Ha, D., Lee, H., and Davidson, J. Learning latent dynamics for planning PMLR, 2019.
from pixels. In International conference on machine learning, pp.
Hafner, D., Pasukonis, J., Ba, J., and Lillicrap, T. Mastering diverse domains through world models. arXiv preprint arXiv:2301.04104 2023.
Halpern J. Y. and Piermont, E. Subjective causality, arXiv preprint arXiv:2401.10937 2024.
Hao, S., Gu, Y., Ma, H., Hong, J., Wang, Z., Wang, D. Z., and Hu, Z. Reasoning with language model is planning with world model. arXiv preprint arXiv:2305. /4992, 2023.
26

---

General agents need world models
Hasanbeig, M., Kantaros, Y., Abate, A., Kroening, D., Pappas, G. J., and Lee, I. Reinforcement learning for temporal logic control synthesis with probabilistic satisfaction guarantees. In 20/9 IEEE 58th conference decision and control (CDC), pp. 5338-5343. IEEE, 2019.
Hills, T. T., Todd, M., Lazer, D., Redish, A. D., and Couzin, I. D. Exploration versus exploitation in space, mind, and society. Trends in cognitive sciences, 19(1):46-55) 54, 2015.
Hou, Y., Li, J., Fei, Y., Stolfo, A., Zhou, W., Zeng, G., Bosselut, A., and Sachan, M. Towards mechanistic interpretation of multi-step reasoning capabilities of language models. arXiv preprint arXiv:2310. 14491, 2023.
Huang, Q. Model-based or model-free, a review of approaches in reinforcement learning. In 2020 International Conference on Computing and Data Science (CDS), pp. 219-221. IEEE, 2020.
Jackermeier, M. and Abate, A. Deepltl: Learning efficiently satisfy complex Itl specifications. International Conference Learning Representations (ICLR) 2025, 2024.
Jackermeier, M. and Abate, A. Deepltl: Learning to efficiently satisfy complex Itl specifications for multi-task rl. The Thirteenth International Conference on Learning Representations, 2025.
Johnson-Laird, P. Mental models: Towards cognitive science of language, inference, and consciousness. Number 6. Harvard University Press, 1983.
Kahneman, D. Thinking, fast and slow. macmillan, 2011.
Karvonen, Emergent world models and latent variable estimation in chess-playing language models. arXiv preprint arXiv:2403.15498, 2024.
Kuo, Y.-.,, Katz, B., and Barbu, A. Encoding formulas as deep networks: Reinforcement learning for zero-shot execution of formulas. 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1604-5610 IEFE, 2020.
Lake, B. M., Ullman, T. D., Tenenbaum, J. B., and Gershman, S. Building machines that learn and think like people. Behavioral and brain sciences, 40:e253, 2017.
LeCun, Y. A path towards autonomous machine intelligence version 0.9. 2, 2022-06-27. Open Review, 62(1):1-62, 2022. 2022.
Leike, J., Krueger, D., Everitt, T., Martic, M., Maini, V., and Legg. Scalable agent alignment via reward modeling: research direction. arXiv preprint 1..0711 2018.
Li, K., Hopkins, A. K., Bau, D., Viégas, F., Pfister, H., and Wattenberg, M. Emergent world representations: Exploring a sequence model trained on a synthetic task. arXiv preprint arXiv:2210.13388, 2022.
Li, X., Vasile, C.-l,, and Belta, C. Reinforcement learning with temporal logic rewards. In 2017 JEEE/RSJ International Conference Intelligent Robots and Systems (IROS), pp. 3834-3839. IEEE, 2017.
Littman, M. L., Topcu, U., Fu, J., Isbell, C., Wen, M., and MacGlashan, J. Cavironment-indeeeedden task specifications via gltl. arXiv preprint arXiv: 1704.04341, 2017.
Liu, M., Zhu, M., and Zhang, W. Goal-conditioned reinforcement learning: Problems and solutions. arXiv preprint arXiv:2201.08299 2022.
Locke, E. A. and Latham, G. P. Goal setting theory, 1990. 2013.
Lockwood, O. and Si, M. A review of uncertainty for deep reinforcement learning. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, volume 18, pp. 155-162, 2022.
Merchant, A., Batzner, S., Schoenholz, S. S., Aykol, M., Cheon, G., and Cubuk, E. D. Scaling deep learning for materials discovery. Nature, 624((990):80-85, 2023.
Ng, Y., Russell, S., et al. Algorithms for inverse reinforcement learning. leml, volume 1, pp. 2000.
27

---

General agents need world models
Pearl, J. Theoretical impediments machine learning with seven sparks from the causal revolution. arXiv preprint arXiv: 1801. 04016, 2018.
Pnueli, A. The temporal logic of programs. In 18th annual symposiun on foundations of computer science (sfes 1977), pp. 46-57. ieee, 1977.
Puterman, M. L. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Qiu, W., Mao, W., and Zhu, H. Instructing goal-conditioned reinforcement learning agents with temporal logic objectives. Advances in Neural Information Processing Systems, 36:39147-39175. 2023.
Qiu, W., Mao, W., and Zhu, H. Instructing goal-conditioned reinforcement learning agents with temporal logic objectives. Advances in Neural Information Processing Systems. 36, 2024.
Raad, M. A., Ahuja, A., Barros, C., Besse, F., Bolt, A., Bolton, A., Brownfield, B., Buttimore, G., Cant, M., Chakera, S., et al. Scaling instructable agents across many simulated worlds. arXiv preprint arXiv:2404.10179 2024.
Rabinowitz, N., Perbet, F., Song, F., Zhang, C., Eslami, S. A., and Botvinick, M. Machine theory of mind. International conference on machine learning, pp. 4218-4227, PMLR, 2018.
Racanière, S., Weber, T., Reichert, D., Buesing, L., Guez, A., Jimenez Rezende, D., Puigdomènech Badia, A., Vinyals, O., Heess, N., Li, Y., et al. Imagination-augmennta agents for deep reinforcement learning. Advances in neural information processing systems, 30, 2017.
Raman, N., Lundy, T., Amouyal, S., Levine, Y., Leyton-Brown, K., and Tennenholtz, M. Steer: Assessing the economic rationality of large language models. arXiv preprint arXiv:2402.09552 2024a.
Raman, N. K., Lundy, T., Amouyal, S. J., Levine, Y., Leyton-Brown, K., and Tennenholtz, M. Steer: Assessing the economic rationality of large language models. In Forty-first International Conference on Machine Learning, 2024b.
Reed, S., Zolna, K., Parisotto, E., Colmenarejo, S. G., Novikov, A., Barth-Maron, G., Gimenez, M., Sulsky, Y., Kay, J., Springenberg, J. T., et al. A generalist agent. arXiv preprint arXiv:2205.06115, 2022.
Richens, J. and Everitt, T. Robust agents learn causal world models. The Twelfth International Conference on Learning Representations, 2024.
Richens, Beard, R., and Thompson, D. H. Counterfactual harm. Advances in Neural Information Processing Systems, 35: 36350-3633 36365, 2022.
Safron, A. An integrated world modeling theory (iwmt) of consciousness: combining integrated information and global neuronal workspace theories with the free energy principle and active inference framework; toward solving the hard problem and characterizing agentic causation. Frontiers in artificial intelligence, 3:520574, 2020.
Savage, J. The foundations of statistics. Courier Corporation, 1972.
Schaul, T., Horgan, D., Gregor, K., and Silver, D. Universal value function approximators. In International conference on machine learning, pp. 1312-1320. PMLR, 2015.
Schrittwieser, J., Antonogiou, I., Hubert, T., Simonyan, K., Sifre, L., Schmitt, S., Guez, A., Lockhart, E., Hassabis, D., Graepel, T., et al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7839)888 2020.
Shepard, R. N. Toward a universal law of generalization for psychological science. Science, 237(4820)13117-133, 1987.
Sutton, R. S. Reinforcement learning: introduction. A Bradford Book, 2018.
Tomasello, M. The evolution of agency: Behavioral organization from lizards to humans. MIT Press, 2022.
Tversky, A. and Kahneman, D. Judgment under uncertainty: Heuristics and biases: Biases in judgments reveal some heuristies of thinking under uncertainty. science, 185(4157):1124-1111,, 1974.
28

---

General agents need world models
Vaezipoor, P., Li, A. C., Icarte, A. T., and Mcilraith, S. A. Lr12action: Generalizing Itl instructions for multi-task rl. In International Conference Machine Learning, pp- 10497-10508. PMLR, 2021.
Von Neumann, J. and Morgenstern, O. Theory of games and economic behavior: 60th anniversary commemorative edition. In Theory of games and economic behavior. Princeton university press, 2007.
Wang, G., Xie, Y., Jiang, Y., Mandlekar, A., Xiao, C., Zhu, Y., Fan, L.,, and Anandkumar, A. Voyager: An open-ended embodied agent with large language models. arXiv preprint arXiv:2305.16221, 2023.
Ward, F., Toni, F., Belardinelli, F., and Everitt, T. Honesty is the best policy: defining and mitigating ai deception. Advances in neural information processing systems, 36:2313-2341, 2023.
Ward, F. R., MacDermott M., Belardinelli, F,, Toni, F,, and Everitt, The reasons that agents act: Intention and instrumental goals. arXiv preprint arXiv:2402.07222,, 2024.
Wentworth, J. Fixing the good regulator theorem.
http://wwww.a.aenooooooooooorrr/ 2021. Accessed: 2023-10-17.
Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K., and Cao, Y. React: Synergizing reasoning and acting in language models. arXiv preprint
2022.
Zhu, Z., Lin, K., Jain, A. K., and Zhou, J. Transfer learning in deep reinforcement learning: A survey, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023.
29


Reviews:
[{"review_id": "KQswjRWtZf", "reviewer": "Reviewer_Xhe1", "summary": "The authors establish that an agent capable of generalizing across a sufficiently large number of goal-conditioned tasks within an environment must have learned an accurate approximation of the environment’s transition model. As a consequence of this result, their proof provides a method for extracting the transition model directly from the agent's policy.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for thoroughly reviewing our paper and for your helpful comments. In particular, the following comment on the need to clarify the size of the `universal’ set of goals, compared to the set of finite horizon trajectories.   \n\n**Reviewer:** _It not obvious that the set of 'universal' goal-directed tasks is small compared to the set of finite trajectories. I would be happy to raise my score if the authors provide insights on this aspect._\n\nYou correctly point out that we assume the agent can generalize to any composite goal of depth n (denoted $\\mathbf{\\Psi}_n$). What we failed to make clear in the paper is that the proof of Theorem 1 actually only requires that the agent can generalize to only a very small subset of $\\mathbf{\\Psi}_n$. This is what led us to comment on the existence of small `universal’ goal sets, which are sufficient for learning a world model and hence generalizing to more complex goals. \n\nPrecisely, the set of goals we require the agent to generalize to is $\\\\{ \\psi_{a, b}(k, n) \\\\}_{k=1}^{k=n}$ \n\nwhere $\\psi_{a, b}(k, n)$ are described at the start of the proofs of Lemma 5 and Theorem 1. The cardinality of this set is n, which is much smaller than $\\mathbf{\\Psi}_n$, and in general much smaller than the number of finite time trajectories, which scale as $\\mathcal{O}(|S|^T |A|^{T-1})$ for horizon $T$. We can interpret this as growing exponentially with the goal depth n, as satisfying our sequential goals of depth n requires trajectories at least of length $T \\geq n/2$ for these goals. \n\nWe have made this all clear in the paper, and thank the reviewer for pointing it out. \n\nTypo corrected on p.5. second sentence.", "claims_and_evidence": "The main claim is supported by the proof of Theorem 1, which appears to be correct to the best of my knowledge.\n\nHowever, the authors also claim that an agent trained on a small set of 'universal' goal-directed tasks can generalize to solve significantly more complex tasks. This claim raises concerns, as the proof requires the agent to successfully solve all composite goals up to a given maximum depth. It is unclear whether this set remains small relative to the set of all possible finite-time trajectories. Additionally, if the maximum depth constraint is reduced and model error increases, it is not evident how this would affect generalization performance beyond the training set.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I have carefully reviewed the proofs of the lemmas and the theorem, and to the best of my knowledge, they appear to be correct.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This paper extends the important findings of Richens (2024) to the sequential setting, albeit within a more restricted domain. Richens (2024) demonstrated that a robust agent must have learned a causal model, and this work builds upon that insight by considering goal-conditioned agents in sequential decision-making tasks. This line of research is particularly timely, as large goal-conditioned models are increasingly being deployed in real-world robotic applications.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths: The proofs are easy to read. Both the discussion and related work sections are insightful.\nWeakness: It not obvious that the set of 'universal' goal-directed tasks is small compared to the set of finite trajectories. I would be happy to raise my score if the authors provide insights on this aspect.", "other_comments_or_suggestions": "p.5 second sentence \"We compare two goals, the first ψ1(r, n) which is satisfied if the outcome state is S = s at most r times\" -> Shouldn't the outcome state be s'?", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zJlLgelpLt", "reviewer": "Reviewer_aY71", "summary": "This paper shows the insight that any agent capable of performing zero-shot generalization must have learned an accurate generative model as a world model of its environment. This paper provides a comprehensive theoretical analysis to support the claims.\n\n## update after rebuttal\nThanks to the authors for providing the rebuttal. I've read the author's response and comments from other reviewers. I have no further questions at this time. I will keep my original positive rating.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for you helpful comments. As noted by **Reviewer Xhe1**, our paper does propose a new method for eliciting world models from agents. However, this was quite unclear in the submitted draft, and we have included an explicit algorithm (below) in the manuscript to clarify this. \n\nFollowing you recommendation we have made the following changes to the paper; \n\n1. Explicit algorithms for recovering world models from agents (below)\n2. New experiments, validating these algorithms on real agents (details below). \n3. Discussion of real-world tasks where our results can be applied (for example [1] recently developed goal conditioned agents that can generalize zero-shot to arbitrary linear temporal logic goals). \n\n\n[1] Jackermeier et al. \"DeepLTL: Learning to Efficiently Satisfy Complex LTL Specifications for Multi-Task RL.\" ICLR 2025 (oral)\n\n\n### **New experiments**\n\nMotivation: can our algorithm for recovering an agent's world model (below) be applied to real-world agents that perhaps maximally violate our theoretical assumptions? Namely, the strict regret bound we assume in Theorem 1. \n\n**Experimental setup**\n\nOur experiment involves extracting a world model from a model-based language agent in 120 randomly generated cMDP environments using our algorithm (below). We show the agent strongly violates our assumptions, but nonetheless this algorithm can still recover the agent's world model.  \n\n1. 120 randomly generated environments described by cMPs, with between 5 and 40 states and 3 and 20 actions. \n2. Our goal-conditioned agent is an LLM (Gemini Flash 2.0), with an explicit, private world model. \n3. We then attempt to learn this private world model using Algorithm 1 (above) given only the agent's policy\n\nA figure of our results can be viewed at the following URL: https://imgur.com/a/1gNe15c\n\nWe also note that our paper is a theory paper, which as pointed out by reviewer Xhe1 significantly extends important recent theory work. We hope it can be judged on these merits, without requiring experiments that extend on the current state of the art empirical work (for example [1] trained LTL conditioned agents and was an oral at ICLR 2025, and used environments simpler than Atari). \n\n### **Algorithm 1: Estimate Transition Probability $\\hat{P}_{ss'}(a)$ from Policy $\\pi$**\n\n**Input:**\n* Goal-conditioned policy $\\pi(a_t | h_t; \\psi)$\n* Choice of state $s$, action $a$, outcome $s'$\n* Precision parameter $n \\in \\mathbb{N}$ (related to maximum goal depth $2n+1$)\n* An alternative action $b \\neq a$\n\n**Function:** EstimateTransitionProbability($\\pi, s, a, s', n, b$)\n\n1.  Initialize $k^* \\gets n$\n2.  For $k = 1$ to $n$:\n    * Define base LTL components:\n        * $\\varphi_0 \\gets [A_0=a]$  (*Take action $a$*)\n        * $\\varphi'_0 \\gets [A_0=b]$ (*Take action $b$*)\n        * $\\varphi_1 \\gets ◇ [A=a, S = s]$ (*Transitions eventually to state $s$ and takes action $a$*)\n        * $\\varphi_2 \\gets ○ [S=s']$ (*Transition Next to state $s'$*)\n        * $\\varphi'_2 \\gets ○ [S\\neq s']$ (*Transition Next to any state other than $s'$*)\n    * Define composite goal:\n        * $\\psi_0 \\gets \\langle\\varphi_1, \\varphi_2'\\rangle$ (*Sequential goal labelled Fail*)\n        * $\\psi_1 \\gets \\langle\\varphi_1, \\varphi_2\\rangle$ (*Sequential goal labelled Success*)\n        * $\\psi_a(k,n) \\gets \\bigvee_{\\text{sequences with } r \\le k \\text{ successes}} \\langle \\varphi_0, (\\psi_0 \\text{ or } \\psi_1)_{\\times n} \\rangle$\n        * $\\psi_a(k,n) \\gets \\bigvee_{\\text{sequences with } r > k \\text{ successes}} \\langle \\varphi_0', (\\psi_0 \\text{ or } \\psi_1)_{\\times n} \\rangle$\n    * $\\psi_{a,b}(k,n) \\gets \\psi_a(k,n) \\vee \\psi_b(k,n)$\n    * $a_0 \\gets \\pi(a_0 | s_0; \\psi_{a,b}(k,n))$ (*Query the policy for the first action*)\n    * If $a_0 = a$:\n        * $k^* \\gets k$\n        * **break** (*Found smallest $k$ s.t. where agent prefers goal involving $\\le k$ successes*)\n3.  Estimate $\\hat{P}_{ss'}(a) \\gets (k^*-1/2)/n$\n4.  **Return** $\\hat{P}_{ss'}(a)$", "claims_and_evidence": "This paper provides detailed theoretical proof to stand for the claims.", "methods_and_evaluation_criteria": "This paper only provides a theoretical framework but does not propose a new method and does not conduct experiments.", "theoretical_claims": "I have checked the main theoretical claims, but not in every detail.", "experimental_designs_or_analyses": "This paper does not provide any experiment.", "relation_to_broader_scientific_literature": "This paper provides a theoretical framework to claim that the world model is essential for zero-shot generalization.", "essential_references_not_discussed": "To the best of my knowledge, the references are sufficiently covered.", "other_strengths_and_weaknesses": "While this paper focuses on the theoretical part, some experiments, even in some simple environments like Atari, help readers connect the claims of this paper to real-world RL or robotics applications. Whether any tasks exist (e.g., robot navigation, manipulation) can this paper's claims be applied?", "other_comments_or_suggestions": "Please refer to the issues raised above.", "questions_for_authors": "Please refer to the issues raised above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5AksWfnP5E", "reviewer": "Reviewer_idip", "summary": "- This paper proves a bound on an agent's ability to achieve zero-shot generalization. \n- It studies a full-observable controlled Markov process, with standard simplifying environment assumptions.\n- They find a bound on the regret of an agent with a key term being an L1 distance between true and estimated transition probabilities.\n- This leads the paper to conclude that to do zero-shot generalization, agents must learn world models.\n- There is lengthy discussion on implications of this and how it connects to results in related areas such as causality and safety.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and thoughtful review and helpful comments. We hope to address your main concerns about the core claims of our paper, which we believe stem from a misunderstanding of theorem 1, and have implemented your suggestions for improving the paper.  \n\n**What do we actually show?**\nYour review notes that we _prove a bound on the agent's ability to achieve zero-shot generalization_ and from this conclude that to do zero-shot generalization, agents must learn world models. We agree that if this was our result, it would be highly questionable.\n\nWhat we actually do is _assume_ the agent satisfies this regret bound (rather than prove it does). I.e. we assume the agent has some minimal degree of competence at zero-shot learning. We then formally prove (as verified by reviewer Xhe1) that for any agent satisfying this assumption, a world model is encoded in the agent's policy. We derive an (unsupervised) algorithm for recovering this world model from the policy (similar to [4]), and prove an error bound on the accuracy of the world model recovered, which depends on the agent's regret. \n\nWe agree that this could be made clearer in the paper, and have done so by specifying the algorithm that recovers the world model outside of the proof of Theorem 1 (see Algorithm 1 in response to reviewer aY71) and re-writing the results section to improve clarity and discussion of our results. \n\n**Is this obvious?**\nThe question of whether or not AI systems have or need world models is hotly debated (see for example [1]), and the subject of significant empirical research [2,3]. A similar result to ours [4] was recently proven for domain generalization (rather than zero-shot learning) and received an award at ICLR 2024. \n\nWhile we agree it feels intuitive that agents should have a world model, there are many ways agents can can reach goal states without one; e.g. through numerous heuristics (schemas, similarity-based reasoning, ...), online learning, etc. Humans can switch between using model-based reasoning _or_ heuristics to generalize to new tasks, depending on the situation. And many biological agents that are thought to be purely model-free (`stimulus-response' agents [5]). It is unclear if general AI systems like LLMs have world models, or if they can generalize purely via heuristics. Before now, there was no formal result showing that world models are necessary for generalization. And indeed we show that for myopic tasks, where the agent is optimizing for immediate outcomes, world models are _not_ necessary.\n\nWe tackle this question by tying world models to a key capability---zero-shot learning. This has consequences for how we design agents (model-based v.s. model free) and reveals fundamental limitations on agent capabilities. Further, we show that this world model can be extracted, which has consequences for safety and interpretability.  \n\n**How have we improved the paper based on your feedback**\n\n1. We agree with your point that the paper lacks insights into theorem 1 and the procedure for extracting world models. We now give an explicit algorithm for recovering world models (see response to reviewer aY71), and have extended the discussion of theorem 1 and other results to 2 pages and reduced repetition.  \n\n2. We have included experiments demonstrating that our algorithm can be applied to real world agents (see response to reviewer aY71)\n\n3. We have introduced a new theorem which proves that learning a world model is _not necessary_ for myopic agents, which optimize for immediate outcomes to their actions (depth-1 goals). This relates to your question on if the need for a world model is obvious or not. Theorem and proof can be seen here https://imgur.com/a/QzrXt0W\n\n\n\n**Reviewer questions**\n\n1. _Why is it a generative model?_. The world model we recover can be used to simulate environment trajectories. This is opposed to the purely state-based world models often studied (e.g. in [2]). \n2. _Three temporal operators..._ Typo corrected. We were referring to the trivial (Now) operator, but have removed this. \n3. _Should eq. 2 rhs be $\\pi^*$_ We are taking the max over $\\pi$, which is equivalent. \n4. _What is $p$ in theorem 1_. Typo corrected. \n5. Comments on Brookes et. al. 2024, have removed. \n6. _Line 206 rh column, I don't see what this prob ratio refers to?_. This is the ratio of the estimated transition probability to the true value, i.e. the relative error. It is given by dividing the inequality in theorem 1 by $P_{ss'}(a)$\n\n\n\n\n[1] https://x.com/ylecun/status/1667947166764023808\n\n[2] Li, et al. \"Emergent world representations: Exploring a sequence model trained on a synthetic task.\" ICLR (2023) oral\n\n[3] Gurnee et. al. \"Language Models Represent Space and Time.\" ICLR (2024)\n\n[4] Richens et. al. \"Robust agents learn causal world models\". ICLR (2024) oral\n\n[5] Tomasello. The evolution of agency: Behavioral organization from lizards to humans. MIT Press, 2022.", "claims_and_evidence": "- While I don't disagree with the discovered bound, I'm unclear whether this by itself definitively supports some claims such as 'Theorem 1 shows that any bounded agent has learned a world model'. The implicit vs explicit distinction seems important detail to maintain in such claims.\n\n- Another key contribution of the paper is 'we can recover an approximation of the environment transition function (a world model) from the agents policy alone', but I found the explanation of how to do this (at least in the main paper) vague.", "methods_and_evaluation_criteria": "No experiments.", "theoretical_claims": "Assessing these proofs is a little out my comfort area. I can take a deeper dive if needed depending on other reviewer's expertise. For the first pass, I read the main paper carefully but only spot checked the proofs in the appendix.\n\nSo far the technical details appear well written and correct.", "experimental_designs_or_analyses": "No experiments.", "relation_to_broader_scientific_literature": "I am not particularly familiar with related work so withhold judgement.", "essential_references_not_discussed": "Fine.", "other_strengths_and_weaknesses": "- From one angle, the paper seems to be saying something quite obvious in a very complicated way -- that an agent must have an internal estimate of how its environment works in order to be good at reaching states within it. The better its internal estimates, the better the agent. I'm not familiar with the thought history on this, and I get lost in some of the nuances of the discussion, but to me this seems quite intuitive. From this angle I'm unclear how much impact the paper's result has.\n- I'm unfamiliar with the structure the paper uses -- lengthy set up, followed by a very short summary of the main theoretical result, and then long discussion of connections with other work. No experiments.\n- The paper takes just 7 pages, including a fair bit of repetition of text and definitions. Overall it feels a little empty. The heart of the contribution is section 3, which takes up less than a page.\n- The paper could use this spare space to do a much better job of giving insight into theorem 1's proof and the procedure for extracting the transition probabilities.", "other_comments_or_suggestions": "- In abstract, why is it specifically a _generative_ model that is learned?\n- 'three temporal operators', but seemed to only define two (is the later or operation included in this?)\n- Should eq 2 on rhs be $\\pi^*$?\n- What is $p$ in theorem 1? did I miss something?\n- 'While model-based agents explicitly learn world models (typically transformers (Brooks et al., 2024) or diffusion models (Janner et al., 2022))'. Why cite Brooks et al. here? They do not do model-based learning, they are doing video generation. (They also use diffusion.)\n- Line 206 rh column, I don't see what this prob ratio refers to?\n- The first few pages of the appendix repeat most of the main paper again. If there are important details in the appendix, move them to the main paper.", "questions_for_authors": "See review.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper establishes a theoretical result indicating that a reinforcement learning agent capable of generalising across a sufficiently large number of goal-conditioned tasks (where goals are LTL specifications) within an environment must necessarily have learned an accurate transition model of the environment. 

The paper's result appears sound and is relevant to discussions on whether AI agents must or do learn "world models". The result here indicates that, at least in this context, learning a world model is a necessary condition if an agent is to be considered general. The paper is purely theoretical, establishing its main result and then discussing the implications; however, reviewers were split on whether the result is indeed valuable and useful to the RL community, so a better discussion here would improve the paper.  During the rebuttal, the authors provided clarifications, a practical algorithm for extracting the transition model and experimental results that align with the theory, although perhaps even better would have been a simpler experiment on a small cMP demonstrating how the error in the transition function changes as an agent has learned to achieve more goals. 

Despite these shortcomings, the reviewers generally agree on acceptance, and authors are encouraged to incorporate the additional information provided during the rebuttal phase.
Decision: Accept (poster)