ProPS: Posterior Sampling for Programmatic World Models

Programmatic world models represent an environment’s dynamics as code that a language model synthesizes from observed transitions, and recent methods decompose this code into many small “laws”. We study how an agent can plan with such laws. Because each law states only part of what an action does, we compile laws into planning rules that each state an action’s whole effect. However, since a rule's context can stay partial, two uncertainties remain: 1) whether an action can run at all, and 2) which of the rival rules compiled for an action is right. We introduce Program Posterior Sampling (ProPS), a controller that keeps an availability posterior and a rule posterior over these two unknowns, plans under a sample from both, and updates both from each outcome. For a small library of complete programs, we prove that an exact version of ProPS is optimal under Bayes-adaptive dynamic programming, while a general version trades this guarantee for scale. On Crafter-OO, ProPS outperforms all baselines given the same laws, including a product of experts and an LLM agent that reads the laws as text.