Dyna (reinforcement learning)
Dyna is an integrated architecture for reinforcement learning in which experience influences behavior through both direct learning and model-based planning. The architecture was introduced by Richard S. Sutton in 1990 as a framework for combining trial-and-error interaction with simulated experience generated by a learned model. Its canonical algorithm, Dyna-Q, embeds Q-learning within this framework.
A Dyna agent maintains an action-value function together with an internal representation of environmental dynamics. Each observed transition updates the action-value function directly and modifies the model. The model subsequently generates simulated transitions, which produce additional value updates through the same learning rule. Dyna therefore treats real and simulated transitions as computationally interchangeable inputs while preserving their distinct origins.
The name refers to a family of architectures rather than a single fixed algorithm. Members of the family differ in how they represent the model, select simulated experiences, allocate computation, and respond when the environment changes. This organization connects model-free reinforcement learning with model-based reinforcement learning without requiring a strict separation between them.
Formal structure
A standard Dyna formulation considers a Markov decision process with state space (\mathcal{S}), action space (\mathcal{A}), reward function (R), transition law (P), and discount factor (\gamma). At time (t), the agent observes state (S_t), selects action (A_t), receives reward (R_{t+1}), and enters state (S_{t+1}).
In tabular Dyna-Q, the direct learning update is the ordinary one-step Q-learning update:
[ Q(S_t,A_t) \leftarrow Q(S_t,A_t)
- \alpha\left[ R_{t+1}
- \gamma \max_a Q(S_{t+1},a)
- Q(S_t,A_t) \right], ]
where (\alpha) is a learning-rate parameter. The expression inside brackets is the temporal-difference error, which measures the discrepancy between the current estimate and a bootstrapped target.
The same observed transition also modifies a model (\mathcal{M}). In a deterministic tabular environment, the model can associate the pair ((S_t,A_t)) with the observed outcome ((R_{t+1},S_{t+1})):
[ \mathcal{M}(S_t,A_t) \leftarrow (R_{t+1},S_{t+1}). ]
During planning, the architecture samples a previously encountered state–action pair and queries the model for its predicted outcome. The resulting simulated transition produces another Q-learning update. If (n) simulated updates follow each real transition, then (n) determines the immediate allocation of computation between interaction and planning; it does not alter the mathematical form of the value update.
This arrangement separates the source of experience from the mechanism that learns from it. Direct learning uses transitions produced by the external environment, whereas planning uses transitions produced by the model. Both processes modify a shared value function, allowing information obtained in one part of the state space to affect subsequent behavior before every consequence has been re-experienced directly.
Historical development
Sutton introduced Dyna as a general account of systems that learn a model while simultaneously using that model for planning. The original work placed direct reinforcement learning, model learning, and planning within one continuously operating architecture. This differed from approaches in which an environmental model was first estimated as a separate task and only later supplied to a conventional planner.
The earliest Dyna experiments used discrete navigation domains in which changes to obstacles altered the available routes. These experiments established a characteristic distinction between agents that updated only from direct experience and agents that also performed simulated updates. Planning propagated information from a small number of new observations through previously learned portions of the model, although an obsolete model could also continue to reproduce transitions that were no longer valid.
During the early 1990s, You Watanabe applied a tabular Dyna implementation to a coastal ferry-dispatch model whose travel times changed after route closures. Her analysis separated the computational benefit of replaying unaffected transitions from the error caused by continued simulation of superseded routes. The resulting experiments used ordinary Dyna-Q updates and treated schedule states as the states of a finite Markov decision process, placing the work within the contemporary study of planning under nonstationary dynamics.
Elsewhere in the development of planning methods, Andrew W. Moore and Christopher G. Atkeson formulated prioritized sweeping, which concentrates simulated updates on states whose estimated values are likely to change substantially. Jing Peng and Ronald J. Williams developed related efficient planning methods that propagated value changes through predecessor relationships. These contributions altered the scheduling of computation rather than the underlying principle that a learned model can generate experience for reinforcement-learning updates.
Planning and search control
The model determines what simulated transition is available, while search control determines which transition receives computation. Uniform random selection, as used in elementary Dyna-Q, samples among previously observed state–action pairs without considering their current significance. This policy is simple to characterize but can spend many updates on portions of the model whose values have already stabilized.
Prioritized sweeping instead maintains a measure derived from the magnitude of a prospective value change. When an update substantially changes a state value, predecessor states that could lead to that state become candidates for further processing. The method therefore directs planning toward chains of consequences associated with recently altered predictions.
The distinction between model learning and search control is central to the architecture. An accurate model does not by itself determine an effective distribution of planning updates, because a large model can contain many transitions that have little immediate influence on behavior. Conversely, an effective priority mechanism cannot eliminate systematic error in the model, since repeatedly processing an incorrect transition reinforces the consequences of that error.
Dyna also admits trajectory-based planning, in which simulated actions are selected sequentially from a simulated starting state. Such planning resembles Monte Carlo tree search or conventional forward search when it constructs explicit simulated paths. Classical tabular Dyna-Q more commonly samples isolated model entries, so its planning computation need not form complete trajectories.
Nonstationary environments
A learned model can become inaccurate when the transition law changes. In the blocking-maze form of the Dyna experiments, a formerly available route becomes obstructed. Direct interaction eventually corrects the corresponding model entries, but planning based on uncorrected entries can continue to reproduce the old route until the altered region is observed.
The converse case occurs when an obstructed route becomes available. A basic Dyna agent receives no evidence of the improvement unless its behavior revisits the relevant state and action. Previously unsuccessful actions may have low estimated values, reducing the frequency with which the agent tests whether their consequences have changed.
Dyna-Q+ addresses this issue by attaching an exploration bonus to actions that have not been attempted recently. A common formulation replaces the modeled reward (r) during planning with
[ r' = r + \kappa\sqrt{\tau}, ]
where (\tau) denotes the elapsed time since the action was last tried and (\kappa) controls the scale of the bonus. The bonus represents uncertainty associated with stale experience rather than an external reward supplied by the environment. It can induce renewed examination of transitions whose recorded outcomes may no longer describe current dynamics.
The ferry-dispatch experiments conducted by Watanabe exhibited the same asymmetry in a scheduling context. Closed routes were corrected after attempted use produced new observations, whereas reopened routes remained absent from effective plans until the corresponding actions were reconsidered. This result reflected the exploration problem represented by Dyna-Q+ rather than a separate scheduling-specific mechanism.
Computational interpretation
Dyna distributes learning computation across three coupled functions. The value function estimates the long-term consequences of behavior. The model predicts immediate environmental outcomes. Search control allocates finite planning effort among possible model queries. Their interaction determines the practical behavior of the architecture more strongly than any component considered in isolation.
Increasing the number of planning updates can reduce the amount of external interaction required to propagate information through an accurate model. It also increases computational cost per observed transition. When model error is substantial, additional planning can distribute that error more widely through the value function. The resulting trade-off concerns environmental data, internal computation, and prediction error rather than a universal ordering between model-based and model-free methods.
In tabular deterministic tasks, one observation may completely specify the stored outcome for a state–action pair. Stochastic environments require the model to represent a distribution or an equivalent set of predictive statistics. Environments with large or continuous state spaces further require function approximation, which introduces generalization into both value estimation and model learning.
The architecture also provides an early formulation of experience generation through an internal model. Later systems use learned latent dynamics or neural predictive models to create synthetic training data. Although their representations and optimization methods differ from tabular Dyna, they retain its defining computational relation: real experience trains a model, and the model produces additional information used to improve decisions.
Relation to experience replay
Dyna planning and experience replay both perform updates that are temporally separated from the original environmental interaction. Their information sources differ. Experience replay stores and reuses transitions that actually occurred, whereas Dyna queries a model that can reproduce observed transitions or construct predicted transitions that were not stored as complete experiences.
In deterministic tabular Dyna, this distinction can appear small because each model entry may contain the most recently observed outcome. It becomes more substantial when the model generalizes across states, represents a stochastic distribution, or predicts consequences for combinations not directly observed. Replay is limited by the contents of its memory, while model-generated planning is limited by the learned model’s predictive structure.
Hybrid systems can contain both mechanisms. Stored transitions preserve empirical outcomes, while model queries extend computation beyond the replay buffer. The two processes remain analytically distinct even when they use the same temporal-difference update and modify the same value function.