WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment

Without transfer, more episodes of exploration are needed to collect experience to build a good world model.

“Without transfer, more episodes of exploration are needed to collect experience to build a good world model.”

After front-loading 400k LLM tokens (about $15), WorldCoder can issue as many actions as needed without subsequent LLM queries.

“Our approach has different asymptotics: after front-loading 400k LLM tokens (about $15), it can issue as many actions as needed without subsequent LLM queries (Fig. 3C).”

Each replay buffer data set D can be represented by its mutually independent data subset D⊥⊥T×R from the perspective of finding the correct world model.

“Lemma α: Each replay buffer data set, D, can be represented by its mutually independent data subset, D ⊥ ⊥T ×R , from the perspective of finding the correct world model, i.e.,”

Agents that use the extra optimism under uncertainty objective can correct the imagined world model given the newly collected data after the efficient exploration.

“• and correct the imagined world model given the newly collected data after the efficient exploration.”

Random exploration needs exponentially more actions to find this counter-example in the worst case.

“Random exploration needs exponentially more number of actions to find this counter-example in the worst case.”

• AssumptionThe authors state this as an assumption: The environment is an episodic MDP (S, A, T, R, γ).
• AssumptionThe authors state this as an assumption: The agent does not have free reset to all possible states, so it must go through trajectories from the initial state to each target state.
• AssumptionThe authors state this as an assumption: The environments are deterministic and have sparse rewards.

WorldCoder is more compute-efficient compared to ReAct-style agents.

“more compute-efficient compared to ReAct-style agents”

• Also stated in: § 1 Introduction · plain

  “also more compute-efficient than prior LLM agents.”

• Also stated in: § 3 Experimental Results · plain

  “ReAct-style architectures [29, 78, 41, i.a.], also require expensive LLM calls at every action, and so asymptotically their cost grows linearly with the number of actions taken.”

• cites [29]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites [78]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites [41]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

PPO failed to gain enough positive-reward supervision signals after 3 × 10^8 actions in UnlockPickup.

“PPO failed to gain enough positive-reward supervision signals after 3 × 10 8 actions as shown in Figure 6.”

PPO is much more sample inefficient than our method.

“As shown in Figure 6, PPO is much more sample inefficient than ours.”

Our method has different asymptotic LLM cost compared to prior LLM agents.

“Our method has different asymptotic LLM cost compared to prior LLM agents, which consume LLM calls/tokens at every action.”

• AssumptionRests on an assumption: Prior LLM agents consume LLM calls/tokens at every action.

The counter-example d′ is mutually independent to the replay buffer D(t) because there is a model (T(t), R(t)) such that (T(t), R(t)) does not entail d′ and (T(t), R(t)) entails D(t).

“Lemma γ: This counter example, d ′ , is mutually independent to the replay buffer, D (t) , because there is a model ( T t) . (t) , R(t) ) such that ( T (t) , R(t) ) ⊬ d ′ ∧ ( T (t) , R(t) ) ⊢ D (”

The saturating formulation of the term frequency in BM25 significantly outperforms its linear variant in TF-IDF.

“One interesting finding in our preliminary experiments is that the saturating formulation of the term frequency, nτ •(k1+1) nτ +k1•(1-b+b•|τ |/l D ) , in BM25 significantly outperforms its linear variant in TF-IDF.”

In comparison with agents that only use the traditional data-consistency objective (φ1) and rely on random exploration, agents that use the extra optimism under uncertainty objective can imagine the functionality of actions and their interactions with necessary tools to achieve the goal without any real interactions with the environment.

“In comparison with agents that only use the traditional data-consistency objective (ϕ 1 ), which merely relies on random exploration to gain new knowledge of the world through new data, agents that use the extra optimism under uncertainty objective can • imagine the functionality of actions and their interactions with the necessary tools, in order to achieve the goal, without any real interactions”

WorldCoder can transfer its knowledge across environments by editing its code.

“it can transfer its knowledge across environments by editing its code.”

• Also stated in: § 1 Introduction · plain

  “finding that code can be quickly adapted to new world dynamics within grid-world and robot task planning domains.”

Optimism is necessary for zero-shot generalization to new goals in Minigrid.

“Optimism is also necessary for zero-shot generalization to new goals (Fig. 4B, env 3).”

PPO cannot solve the UnlockPickup environment even in 3 × 10^8 steps.

“It cannot solve the UnlockPickup environment even in 3 × 10 8 steps.”

WorldCoder is much more sample and compute efficient than baselines in the paper's experiments.

“We show that WorldCoder is much more sample and compute efficient in our methods than baselines.”

• Also stated in: § Additional information · boosted

  “our method significantly outperforms the baselines in the sample efficiency and the compute efficiency in our experiments.”

Transfer is especially helpful in quickly solving new Minigrid environments.

“Transfer is especially helpful in quickly solving new environments (Fig. 4B).”

WorldCoder with the optimism objective learned the correct world model from scratch with no more than 100 actions in UnlockPickup.

“Nevertheless, our method with the optimism objective learned the correct world model from scratch with no more than 100 actions due to its better sample efficiency in exploration.”

WorldCoder is more sample-efficient compared to deep RL.

“finding our approach is more sample-efficient compared to deep RL”

• Also stated in: § 1 Introduction · boosted

  “dramatically more sample-efficient compared to deep RL”

• Also stated in: § 3 Experimental Results · plain

  “both model-based and model-free deep RL require millions of experiences to solve basic levels (Fig. 3D).”

After learning how the world works, WorldCoder can receive natural language instructions and begin following them immediately without further learning from environmental interactions.

“After learning how the world works, our agent should be able to receive natural language instructions and begin following them immediately without further learning from environmental interactions.”

• Also stated in: § Minigrid. · plain

  “Our agent can follow these natural-language instructions by enforcing optimism under uncertainty (ϕ 2 ).”

• AssumptionThe authors state this as an assumption: The LLM possesses fuzzy prior knowledge of how the world might be, together with programming skill to code and debug a transition function.

PPO needs 10^4 to 10^5 steps to learn valid policies (not perfect) in most environments.

“It needs 10 4 -10 5 steps to learn valid policies (not perfect though) in most environments.”

For deterministic environments, the number of actions to find a counter-example with a world model that satisfies φ1 ∧ φ2 is guaranteed to be smaller than the diameter of the state space, D_S, when equipped with an optimal planner.

“For deterministic environments, the number of actions to find a counter-example with a world model that satisfies ϕ 1 ∧ ϕ 2 is guaranteed to be smaller than the diameter of the state space, D S , when equipped with an optimal planner (by definition).”

• AssumptionThe authors state this as an assumption: The environment is an episodic MDP (S, A, T, R, γ).
• AssumptionThe authors state this as an assumption: The agent acts according to an optimal planner operating over a world model (T, R) ∈ T × R satisfying ϕ1 ∧ ϕ2.
• AssumptionThe authors state this as an assumption: The agent does not have free reset to all possible states, so it must go through trajectories from the initial state to each target state.
• AssumptionThe authors state this as an assumption: The environments are deterministic and have sparse rewards.

Agents that use the extra optimism under uncertainty objective can explore much more efficiently guided by the imagined world model.

“• explore much more efficiently guided by the imagined world model;”

ReAct cannot effectively play the game.

“ReAct has the same pretrained knowledge of Sokoban but cannot effectively play the game.”

Assume an episodic MDP (S, A, T, R, γ), an agent acting according to an optimal planner over a world model (T, R) ∈ T × R satisfying φ1 ∧ φ2, and that the true MDP is in the agent's model class. Then the maximum number of actions needed to achieve the goal (exit with positive reward) is D_S,A,T × (K_T×R + 1).

“Theorem A.4. Assume an episodic MDP (S, A, T, R, γ).Assume an agent acting according to an optimal planner operating over world model ( T , R) ∈ T × R satisfying ϕ 1 ∧ ϕ 2 , and that the true MDP is in the agent's model class: T ∈ T and R ∈ R. Then the maximum number of actions needed to achieve the goal (exit with positive reward) is D S,A,T × (K T ×R + 1).”

• AssumptionThe authors state this as an assumption: The environment is an episodic MDP (S, A, T, R, γ).
• AssumptionThe authors state this as an assumption: The agent acts according to an optimal planner operating over a world model (T, R) ∈ T × R satisfying ϕ1 ∧ ϕ2.
• AssumptionThe authors state this as an assumption: The true MDP is in the agent's model class: T ∈ T and R ∈ R.
• AssumptionThe authors state this as an assumption: The agent does not have free reset to all possible states, so it must go through trajectories from the initial state to each target state.

BM25 works significantly well in our experiments.

“We focus on the symbolic ones for efficiency issues and find BM25 [50], a state-ofthe-art algorithm for web-scale information retrieval, works significantly well in our experiments.”

• cites [50]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

The optimism under uncertainty objective is necessary for nonzero performance on all AlfWorld tasks.

“and that the optimism under uncertainty objective is necessary for nonzero performance on all of these tasks.”

The maximum number of actions to learn or find a good-enough world model is polynomial with respect to intrinsic properties of the state space and model space.

“More formally, we show that the maximum number of actions to learn/find a good-enough world model is polynomial w.r.t.intrinsic properties of the state space and model space:”

• AssumptionThe authors state this as an assumption: The environment is an episodic MDP (S, A, T, R, γ).
• AssumptionThe authors state this as an assumption: The agent acts according to an optimal planner operating over a world model (T, R) ∈ T × R satisfying ϕ1 ∧ ϕ2.
• AssumptionThe authors state this as an assumption: The agent does not have free reset to all possible states, so it must go through trajectories from the initial state to each target state.

Using GPT-4 and refinement, WorldCoder can generate world models with 250+ lines of code.

“Using this technique and this LLM we can generate world models with 250+ lines of code.”

• Also stated in: § Minigrid. · plain

  “We find that we can synthesize a world model containing 250+ lines of code, which serves as an adequate model of how AlfWorld works (Appendix E)”

ReAct succeeds on only 15% ± 8% of basic Sokoban levels.

“Quantitatively, ReAct succeeds on only 15% ± 8% of basic levels, showing that pretrained knowledge of Sokoban does not, by itself, allow strong play.”

Only through counter-examples that cannot be explained by the current world model can the size of the set of potentially correct world models become smaller and smaller, eventually leading to a set that only contains good-enough world models that guide the agent towards the goal.

“Only through the counter-examples which cannot be explained by the current world model, the size of the set of the potentially correct world models can become smaller and smaller, which eventually leads to a set that only contains the good-enough world models that guide the agent towards the goal.”

ReAct has the same pretrained knowledge of Sokoban.

“ReAct has the same pretrained knowledge of Sokoban but cannot effectively play the game.”

Counter-examples are precious because, when searching for the correct world model, each interaction data (s, a, s′, r, d) in the replay buffer implies a constraint to satisfy for the potentially correct world models in the space of world models.

“Counter-example are precious because, when in search of the correct world model, each interaction data (s, a, s ′ , r, d) in the replay buffer implies a constraint to satisfy for the potentially correct world models in the space of world models.”

WorldCoder builds a Python program representing its knowledge of the world based on its interactions with the environment.

“We give a model-based agent that builds a Python program representing its knowledge of the world based on its interactions with the environment.”

• Also stated in: § 1 Introduction · plain

  “Our proposed solution is an architecture that synthesizes a Python program to model its past experiences with the world, effectively learning the transition function, and which takes actions by planning using that world model.”

Assuming the low-data regime, preferring an optimistic world model guarantees that the agent can at least start making progress toward the goal, even if it later has to update its beliefs because they turned out to be too optimistic.

“Assuming the low-data regime, there will be multiple world models consistent with the data: preferring an optimistic one guarantees that the agent can at least start making progress toward the goal, even if it later has to update its beliefs because they turned out to be too optimistic.”

• AssumptionThe authors state this as an assumption: The low-data regime holds, so there will be multiple world models consistent with the data.

Curriculum learning allows transfer of knowledge across environments, making combinatorial program synthesis more tractable by reusing successful pieces of old programs.

“we show how curriculum learning can allow transfer of knowledge across environments, making combinatorial program synthesis more tractable by reusing successful pieces of old programs.”

WorldCoder can interoperate with different kinds of planners.

“This shows that our framework can interoperate with different kinds of planners.”

WorldCoder uses a new learning objective that prefers world models which a planner thinks lead to rewarding states, particularly when the agent is uncertain as to where the rewards are.

“To address the challenge of efficient exploration, we introduce a new learning objective that prefers world models which a planner thinks lead to rewarding states, particularly when the agent is uncertain as to where the rewards are.”

The optimism under uncertainty objective is much more sample efficient at getting valuable counterexamples than random exploration.

“The optimism under uncertainty objective is much more sample efficient to get those valuable counterexamples than random exploration.”

Collecting data that can be explained by all potentially correct world models is useless because it implies no stricter constraints than the current ones.

“Collecting data that can be explained by all potentially correct world models is useless because it implies no stricter constraints than the current ones.”

The optimism objective is necessary for any non-zero performance.

“Optimism objective is necessary for any non-zero performance.”

The optimism objective enables more efficient exploration.

“We show that the optimism objective enables more efficient exploration.”

Zero-shot generalization to new goals occurs as a consequence of enforcing optimism under uncertainty (φ2).

“This zero-shot generalization to new goals occurs as a consequence of enforcing optimism under uncertainty (ϕ 2 in Eq. 2).”

If the world model after D_S × (K⊥⊥T×R + 1) steps is still incorrect, then building a mutually independent data set with size larger than K⊥⊥T×R is contradictory to its definition.

“Assume the world model after D S × (K ⊥ ⊥T ×R + 1) steps is still incorrect, we then build a mutually independent data set, D (D S ×(K ⊥ ⊥T ×R +1) ⊥ ⊥T ×R , with size larger than K ⊥ ⊥T ×R , which is contradictory to its definition.”

Before ever receiving reward, φ2 forces the agent to invent a reward function that it believes it could achieve but has not already achieved.

“Before ever receiving reward, ϕ 2 forces the agent to invent a reward function.This reward function will be something that the agent believes it could achieve, but has not already achieved: roughly, something within its 'zone of proximal development' [71].”

• cites [71]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Because there is no randomness and no partial rewards in the environments, roll-outs are not cost-effective in the usage of simulations.

“Noticing that there is no randomness and no partial rewards in the environments, roll-outs are not cost-effective in the usage of simulations.”

• AssumptionRests on an assumption: The environments have no randomness and no partial rewards.

In WorldCoder, the LLM does not simulate the world, but instead builds a simulation of the world.

“In our setup, the LLM does not simulate the world, but instead builds a simulation of the world.”

We do not need to run a trajectory multiple times to estimate its expectations of returns.

“We do not need to run a trajectory multiple times to estimate its expectations of returns.”

• AssumptionRests on an assumption: The environments have no randomness and no partial rewards.

The learned world model should explain the observed data by correctly predicting the observed state transitions and rewards.

“Clearly, the learned world model should explain the observed data by correctly predicting the observed state transitions and rewards.This is a standard training objective within model-based RL [62].”

• cites [62]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

A good-enough world model is guaranteed to be discovered in time that is polynomial in the diameter of the true MDP and the logical dimensionality of the model space.

“We prove that a good-enough world model is guaranteed to be discovered in time that is polynomial in several key quantities, defined below.”

• Also stated in: § 2.3 Understanding optimism under uncertainty · plain

  “Then the maximum number of actions needed to achieve the goal (exit with positive reward) is D S,A,T × (K T ×R + 1).”

• AssumptionThe authors state this as an assumption: The MDP is episodic with the current episode terminating upon reaching the goal.
• AssumptionThe authors state this as an assumption: The true MDP is in the agent's model class (T ∈ T and R ∈ R).
• AssumptionThe authors state this as an assumption: An optimal planner operates over the world model.