2024

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

Tang, Hao, Key, Darren, Ellis, Kevin

Understand

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

The world model tries to explain its interactions, while also being optimistic about what reward it can achieve.
We define this optimism as a logical constraint between a program and a planner.
We study our agent on gridworlds, and on task planning, finding our approach is more sample-efficient compared to deep RL, more compute-efficient compared to ReAct-style agents, and that it can transfer its knowledge across environments by editing its code.

Built on

Introduction and removal of reward, and maze performance in rats
Edward Chace Tolman and Charles H Honzik · 1930
Earlier work this paper cites.
Mind in society: The development of higher psychological processes
Lev Semenovich Vygotsky · 1980
Earlier work this paper cites.
Integrated architectures for learning, planning, and reacting based on approximating dynamic programming
Richard S Sutton · 1990
Earlier work this paper cites.
Information retrieval on the web
Mei Kobayashi and Koichi Takeda · 2000
Earlier work this paper cites.
Using confidence bounds for exploitation-exploration trade-offs
Peter Auer · 2002
Earlier work this paper cites.
Efficient selectivity and backup operators in monte-carlo tree search
Rémi Coulom · 2006
Earlier work this paper cites.
Bandit based monte-carlo planning
Levente Kocsis and Csaba Szepesvári · 2006
Earlier work this paper cites.
Problog: a probabilistic prolog and its application in link discovery
Luc De Raedt, Angelika Kimmig, and Hannu Toivonen · 2007
Earlier work this paper cites.
An object-oriented representation for efficient reinforcement learning
Carlos Diuk, Andre Cohen, and Michael L Littman · 2008
Earlier work this paper cites.
Church: a language for generative models
Noah D. Goodman, Vikash K. Mansinghka, Daniel Roy, Keith Bonawitz, and Joshua B. Tenenbaum · 2008
Earlier work this paper cites.
Introduction to information retrieval
Christopher D Manning, Prabhakar Raghavan, and Hinrich Schütze · 2008
Earlier work this paper cites.
The probabilistic relevance framework: Bm25 and beyond
Stephen Robertson, Hugo Zaragoza, et al · 2009
Earlier work this paper cites.
ALFWorld: Aligning Text and Embodied Environments for Interactive Learning
Original
Mohit Shridhar, Xingdi Yuan, Marc-Alexandre Côté, Yonatan Bisk, Adam Trischler, and Matthew Hausknecht · 2010
Earlier work this paper cites.
Hierarchical task and motion planning in the now
Leslie Pack Kaelbling and Tomás Lozano-Pérez · 2011
Earlier work this paper cites.
A survey of monte carlo tree search methods
Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter I Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton · 2012
Earlier work this paper cites.
Contextual markov decision processes
Original
Assaf Hallak, Dotan Di Castro, and Shie Mannor · 2015
Earlier work this paper cites.
Artificial intelligence: a modern approach
Stuart J Russell and Peter Norvig · 2016
Earlier work this paper cites.
Mastering the game of go with deep neural networks and tree search
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al · 2016
Earlier work this paper cites.
Minimax regret bounds for reinforcement learning
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos · 2017
Earlier work this paper cites.
Minimalistic gridworld environment for openai gym
Maxime Chevalier-Boisvert, Lucas Willems, and Suman Pal · 2018
Earlier work this paper cites.
Recurrent world models facilitate policy evolution
David Ha and Jürgen Schmidhuber · 2018
Earlier work this paper cites.
From skills to symbols: Learning symbolic representations for abstract high-level planning
George Konidaris, Leslie Pack Kaelbling, and Tomas Lozano-Perez · 2018
Earlier work this paper cites.
gym-sokoban
Max-Philipp B. Schrader · 2018
Earlier work this paper cites.
Reinforcement learning: An introduction
Richard S Sutton and Andrew G Barto · 2018
Earlier work this paper cites.
Programmatically interpretable reinforcement learning
Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri · 2018
Earlier work this paper cites.
Adaptive discretization for episodic reinforcement learning in metric spaces
Sean R Sinclair, Siddhartha Banerjee, and Christina Lee Yu · 2019
Earlier work this paper cites.

Similar

Imitation-projected programmatic reinforcement learning
Abhinav Verma, Hoang Le, Yisong Yue, and Swarat Chaudhuri · 2019
Cited alongside, same era.
A novel automated curriculum strategy to solve hard sokoban planning instances
Dieqiao Feng, Carla P Gomes, and Bart Selman · 2020
Cited alongside, same era.
Integrated task and motion planning, 2020
Caelan Reed Garrett, Rohan Chitnis, Rachel Holladay, Beomjoon Kim, Tom Silver, Leslie Pack Kaelbling, and Tomás Lozano-Pérez · 2020
Cited alongside, same era.
Provably efficient reinforcement learning with linear function approximation
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan · 2020
Cited alongside, same era.
Dense passage retrieval for open-domain question answering
Original
Vladimir Karpukhin, Barlas Oğuz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih · 2020
Cited alongside, same era.
Rl baselines3 zoo
Antonin Raffin · 2020
Cited alongside, same era.
Mastering atari, go, chess and shogi by planning with a learned model
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al · 2020
Cited alongside, same era.
Pddlgym: Gym environments from pddl problems
Tom Silver and Rohan Chitnis · 2020
Cited alongside, same era.
Neurosymbolic programming
Swarat Chaudhuri, Kevin Ellis, Oleksandr Polozov, Rishabh Singh, Armando Solar-Lezama, Yisong Yue, et al · 2021
Cited alongside, same era.
Making sense of raw input
Richard Evans, Matko Bošnjak, Lars Buesing, Kevin Ellis, David Pfau, Pushmeet Kohli, and Marek Sergot · 2021
Cited alongside, same era.
Neural production systems: Learning rule-governed visual dynamics
Original
Anirudh Goyal, Aniket Didolkar, Nan Rosemary Ke, Charles Blundell, Philippe Beaudoin, Nicolas Heess, Michael Mozer, and Yoshua Bengio · 2021
Cited alongside, same era.
Mastering atari with discrete world models
Danijar Hafner, Timothy Lillicrap, Mohammad Norouzi, and Jimmy Ba · 2021
Cited alongside, same era.

Then

Thinker: Learning to plan and act
Stephen Chung, Ivan Anokhin, and David Krueger · 2023
Later among the works it cites.
Combining functional and automata synthesis to discover causal reactive programs
Ria Das, Joshua B. Tenenbaum, Armando Solar-Lezama, and Zenna Tavares · 2023
Later among the works it cites.
Dreamcoder: growing generalizable, interpretable knowledge with wake–sleep bayesian program learning
Kevin Ellis, Lionel Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lore Anaya Pozo, Luke Hewitt, Armando Solar-Lezama, and Joshua B Tenenbaum · 2023
Later among the works it cites.
Lilo: Learning interpretable libraries by compressing and documenting code, 2023
Gabriel Grand, Lionel Wong, Matthew Bowers, Theo X. Olausson, Muxin Liu, Joshua B. Tenenbaum, and Jacob Andreas · 2023
Later among the works it cites.
Leveraging pre-trained large language models to construct and utilize world models for model-based task planning
Lin Guan, Karthik Valmeekam, Sarath Sreedharan, and Subbarao Kambhampati · 2023
Later among the works it cites.
Mastering diverse domains through world models, 2023
Danijar Hafner, Jurgis Pasukonis, Jimmy Ba, and Timothy Lillicrap · 2023
Later among the works it cites.
Reasoning with language model is planning with world model
Original
Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu · 2023
Later among the works it cites.
Look before you leap: Unveiling the power of gpt-4v in robotic vision-language planning
Original
Yingdong Hu, Fanqi Lin, Tong Zhang, Li Yi, and Yang Gao · 2023
Later among the works it cites.
Hybrid search for efficient planning with completeness guarantees
Kalle Kujanpää, Joni Pajarinen, and Alexander Ilin · 2023
Later among the works it cites.
Emergent world representations: Exploring a sequence model trained on a synthetic task
Kenneth Li, Aspen K Hopkins, David Bau, Fernanda Viégas, Hanspeter Pfister, and Martin Wattenberg · 2023
Later among the works it cites.
Eureka: Human-level reward design via coding large language models
Yecheng Jason Ma, William Liang, Guanzhi Wang, De-An Huang, Osbert Bastani, Dinesh Jayaraman, Yuke Zhu, Linxi Fan, and Anima Anandkumar · 2023
Later among the works it cites.
Transformers are sample-efficient world models
Vincent Micheli, Eloi Alonso, and François Fleuret · 2023
Later among the works it cites.
Do Embodied Agents Dream of Pixelated Sheep: Embodied Decision Making using Language Guided World Modelling
Kolby Nottingham, Prithviraj Ammanabrolu, Alane Suhr, Yejin Choi, Hannaneh Hajishirzi, Sameer Singh, and Roy Fox · 2023
Later among the works it cites.
Is self-repair a silver bullet for code generation?, 2023
Theo X. Olausson, Jeevana Priya Inala, Chenglong Wang, Jianfeng Gao, and Armando Solar-Lezama · 2023
Later among the works it cites.
Rlang: A declarative language for describing partial world knowledge to reinforcement learning agents, 2023
Rafael Rodriguez-Sanchez, Benjamin A. Spiegel, Jennifer Wang, Roma Patel, Stefanie Tellex, and George Konidaris · 2023
Later among the works it cites.
Neurosymbolic grounding for compositional world models, 2023
Atharva Sehgal, Arya Grayeli, Jennifer J. Sun, and Swarat Chaudhuri · 2023
Later among the works it cites.
Adaplanner: Adaptive planning from feedback with language models
Haotian Sun, Yuchen Zhuang, Lingkai Kong, Bo Dai, and Chao Zhang · 2023
Later among the works it cites.
From perception to programs: Regularize, overparameterize, and amortize
Hao Tang and Kevin Ellis · 2023
Later among the works it cites.
On the planning abilities of large language models - a critical investigation
Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati · 2023
Later among the works it cites.
Learning adaptive planning representations with natural language guidance, 2023
Lionel Wong, Jiayuan Mao, Pratyusha Sharma, Zachary S. Siegel, Jiahai Feng, Noa Korneev, Joshua B. Tenenbaum, and Jacob Andreas · 2023
Later among the works it cites.
Language models meet world models: Embodied experiences enhance language models
Jiannan Xiang, Tianhua Tao, Yi Gu, Tianmin Shu, Zirui Wang, Zichao Yang, and Zhiting Hu · 2023
Later among the works it cites.
Large language models as commonsense knowledge for large-scale task planning
Zirui Zhao, Wee Sun Lee, and David Hsu · 2023
Later among the works it cites.
Large language models for information retrieval: A survey
Original
Yutao Zhu, Huaying Yuan, Shuting Wang, Jiongnan Liu, Wenhan Liu, Chenlong Deng, Zhicheng Dou, and Ji-Rong Wen · 2023
Later among the works it cites.
Code repair with llms gives an exploration-exploitation tradeoff
Hao Tang, Keya Hu, Jin Peng Zhou, Sicheng Zhong, Wei-Long Zheng, Xujie Si, and Kevin Ellis · 2024
Closest in time.
Bootstrapping cognitive agents with a large language model
Feiyu Zhu and Reid Simmons · 2024
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…