Intellectual and Cognitive History › AI Planning and Model-Based Learning

The third tradition eventually made model acquisition an algorithmic problem. It began, however, with hand-written symbolic models: engineers specified states and operators, and programs searched over their consequences. Model-based reinforcement learning later replaced much of that specification with models learned from interaction. This changed validation as well as construction. A hand-written model can be inspected symbol by symbol; a learned model must be tested statistically, especially where experience is sparse. The lineage therefore runs from explicit symbolic planning to learned latent dynamics, and it connects directly to the model-based reinforcement learning chapters of Part II.

The first AI programs to "think ahead" did so over symbolic state spaces. Allen Newell, Clifford Shaw, and Herbert Simon demonstrated Logic Theorist in 1956 as a heuristic proof-search program. Their General Problem Solver, begun in 1957, introduced means-ends analysis: detect a difference between the current state and the goal, choose an operator that can reduce it, and recursively solve the preconditions for applying that operator. The procedure is recognizably a planning loop: evaluate the gap, imagine an action closing part of it, recurse. Here the world model is explicit: states, operators with preconditions and effects, and a search procedure that simulates operator application. Nothing is hidden; "imagination" is the application of an operator to a symbolic description to see what results.

Richard Fikes and Nils Nilsson's STRIPS (1971) gave this paradigm its durable formal shape: actions described by precondition, add, and delete lists, enabling planners that reason over action schemas rather than enumerating states. Under the usual blocks-world conventions, where variables bind to distinct movable blocks and the table is treated as a distinguished always-clear constant, a correct schema can write Move(X, Z, Y) with preconditions On(X,Z), Clear(X), and Clear(Y); add effects On(X,Y) and Clear(Z); and delete effects On(X,Z) and Clear(Y). Deleting On(X,Z) keeps one block recorded on at most one support; recording the old support Z as an argument allows the add effect to restore Clear(Z), freeing it for later moves. Moves that originate on the table require either admitting the table constant as Z under compatible predicates or adding a companion schema. This compression is the symbolic ancestor of a problem we will study in depth: how to represent dynamics compactly enough to plan over. The planning tradition matured into a deep field covering heuristic search, partial-order planning, and temporal and probabilistic planning. Under their stated assumptions, particular algorithms can guarantee completeness, return optimal plans, or make plans independently verifiable. Purely learned approaches do not generally provide the same guarantees, although hybrid systems can inherit them from a symbolic component. We will cover classical planning and optimal control in detail in Part II.

Two limitations of the symbolic tradition shaped what came next. First, the models were given, hand-written by engineers, which works for logistics and blocks worlds but not for a robot facing the physical world. Nobody can enumerate every precondition and effect of "grasp the cup" in a kitchen; the effects depend on friction, deformability, lighting, and contents. Second, crisp symbolic states can be brittle under noise: one wrong precondition may invalidate a plan. Classical planners did develop execution monitoring, plan repair, and replanning, so recovery was not absent, but these mechanisms still depended on a hand-specified symbolic interface that represented the relevant deviation. Learning models from data and making planning robust to model error became central problems.

Arthur Samuel's checkers program (1959) is remembered for self-play learning, but its more relevant innovation for us is the forward-looking backup: Samuel evaluated a position by simulating the game tree and propagating values backward. Richard Sutton later identified this as an early instance of temporal-difference learning, which he formalized in 1988: update a prediction of a future outcome toward the prediction that follows it. In finite tabular policy-evaluation problems where the behavior process visits every relevant state infinitely often and the step sizes satisfy the Robbins-Monro conditions, TD and Monte Carlo methods target the same policy value function, although their finite-sample updates differ. Constant step sizes typically bring the iterates to a bounded neighborhood of the target and leave them fluctuating within it, rather than producing almost-sure convergence to one value. With linear function approximation, Tsitsiklis and Van Roy (1997) characterize the on-policy TD fixed point as a projected solution. The combination of bootstrapping, function approximation, and off-policy data does not inherit that guarantee and can diverge; Baird (1995) gives classical linear counterexamples. Nonlinear approximation has additional failure modes, but they are not attributed to Baird's construction here. TD's practical advantage is that it uses intermediate transitions rather than waiting for a final return. It therefore underlies much of Part II and fits naturally wherever an agent learns chained predictions.

Sutton's Dyna architecture is the historical hinge between model-free and model-based reinforcement learning, and it is simple enough to state in one paragraph. An agent interacts with the real environment, storing each experienced transition in a learned model. Between real steps, it plans by sampling stored or imagined transitions and applying the same learning update it would apply to real experience. Real experience improves both the policy and the model; the model then turns each piece of real experience into additional simulated updates. The first conference account appeared in 1990, followed by the 1991 SIGART article linked here. The architecture dissolves what had seemed like a fundamental dichotomy. Model-free methods learn directly from experience; model-based methods learn a model and then plan. Dyna shows that interleaving direct and simulated updates can be effective; it does not claim that one fixed interleaving schedule is universally optimal.

Dyna's significance is not just architectural. It crystallized the trade-off that defines model-based reinforcement learning: real experience is expensive but trustworthy, simulated experience is cheap but only as good as the model. Moore and Atkeson's prioritized sweeping (1993) sharpened the point by propagating updates backward from transitions with large value changes, concentrating planning where updates can matter most. The biological echo is suggestive, although the chronology runs the other way: Wilson and McNaughton reported sleep reactivation in 1994, a few years after Dyna, and Foster and Wilson reported awake reverse replay in 2006. Later studies, including Singer and Frank (2009), found replay content related to reward and recent experience. These observations resemble prioritized simulated updates, but they do not establish that hippocampal replay implements Dyna or performs the same value update.

The Q-learning update at Dyna's core is worth writing down, since we will use it in the experiment below:

$$Q(s, a) \leftarrow Q(s, a) + \alpha \left[ r + \gamma \max_{a'} Q(s', a') - Q(s, a) \right],$$

where $\alpha$ is a learning rate and $\gamma$ a discount factor. When $s'$ is terminal, the bootstrap term $\gamma \max_{a'} Q(s',a')$ is taken as zero. Read the update as a prediction-correction pair: the term $r + \gamma \max_{a'} Q(s', a')$ is a fresh estimate of the value of $(s,a)$ based on the observed successor for a real transition or the model-sampled successor for an imagined transition, and the bracket measures how wrong the old estimate was. The update nudges the estimate toward the fresher one by a fraction $\alpha$. In Dyna, this update runs both on real transitions $(s, a, r, s')$ and on transitions $(s, a, r, s')$ sampled from the learned model, and nothing in the update distinguishes the two cases.

For many years after Dyna, model-based reinforcement learning remained comparatively marginal in mainstream reinforcement learning, despite substantial work in planning, adaptive control, and probabilistic robotics. A persistent obstacle was model bias, which Part VI and Part XII treat in depth. If a learned model is wrong in a region the policy can visit, an optimizer may actively seek the error because it looks like an opportunity. A false shortcut or false prediction of safety can therefore produce confident failure. The 2010s brought methods that made this problem more manageable and model-based learning more competitive.

Marc Deisenroth and Carl Edward Rasmussen's PILCO (2011) attacked model bias with probabilistic models. Its Gaussian-process dynamics model propagated predictive uncertainty through imagined trajectories, and that uncertainty affected expected cost through moment matching rather than through a separate hand-added penalty. PILCO solved several benchmark control tasks from scratch with tens of seconds of interaction, a striking sample-efficiency result relative to contemporary model-free baselines. Guided policy search, introduced by Sergey Levine and Vladlen Koltun in 2013 and extended in work with Nolan Wagener, Pieter Abbeel, Chelsea Finn, and others, used model-based trajectory optimization to supervise reactive policies. The model could plan locally where it was valid, while the deployed policy acted without online model-based optimization.

The deep-learning era then collapsed the distinction between "model" and "perception." Two threads converged in the methods that followed.

• Learning in latent space. Rather than predicting every raw detail, learn a compressed latent state and model its dynamics. The World Models paper by David Ha and Jürgen Schmidhuber (2018) combined a variational-autoencoder-style vision model, a recurrent mixture-density network for latent dynamics, and a small controller trained inside the model's "dream." Those dream episodes were bounded, and the controller was evaluated in the real environment, because cheap simulation does not remove model bias or make arbitrarily long rollouts reliable.
• Planning with learned models at scale. MuZero (Julian Schrittwieser and colleagues, published in Nature in 2020) achieved superhuman play in Go, chess, and shogi, and strong Atari performance with a latent dynamics model that predicted rewards, values, policies, and planning-relevant transitions but did not reconstruct observations. It therefore showed that observation reconstruction was unnecessary for these tasks; stronger claims that reconstruction is generally harmful require a specified baseline and setting. AlphaZero, first released as a 2017 preprint and published in Science in 2018, planned over perfect game states. MuZero instead learned its own latent states and predicted only what planning consumed.

Meanwhile the Dreamer line (Danijar Hafner and colleagues: PlaNet 2019, Dreamer 2020, and DreamerV3, first released as a preprint in 2023 and published at ICLR 2024) made latent imagination practical for continuous control. The revised DreamerV3 paper reports one hyperparameter configuration across many domains and learning to collect diamonds in Minecraft without human demonstrations or a task-specific curriculum. This reduced dependence on per-task tuning; it did not eliminate every implementation or compute choice. Dreamer's recurrent state-space model, which Part V develops, combines an encoder-decoder, a stochastic forward model, and learning from imagined rollouts.