Dyna-Q planning

Why Planning Needs Exploration

Dyna-Q planning uses a learned model to create simulated experiences. This can make an agent efficient because it can plan from what it already knows. However, that efficiency can create a blind spot: if planning repeatedly uses familiar transitions, the agent may spend too little effort checking actions that have been ignored for a long time. Dyna-Q+ addresses this problem by using elapsed time since the last real trial as an exploration signal.

Tracking Elapsed Time

For each state-action pair, Dyna-Q+ considers how much time has elapsed since that pair was last tried in real experience. Call this elapsed-time count τ. The count is not itself a reward. Instead, it supplies information about how neglected the pair has become. As τ becomes larger, the pair receives stronger encouragement during simulated planning.

Adding the Exploration Bonus

The planning backup in Dyna-Q+ adds the bonus κ √τ to the modeled reward. Here, τ represents the elapsed time since the state-action pair was last tried, and κ controls the strength of this exploration encouragement. The important relationship is that the bonus grows with τ. Consequently, a transition that has remained untested for longer becomes more attractive in simulated planning.

Including Never-Tried Actions

Dyna-Q+ extends exploration further than rewarding recently neglected actions. An action that has never been tried from a particular state is still allowed to enter the planning step. It is not excluded merely because no real transition has yet been observed for it.

For such a never-tried action, Dyna-Q+ begins with a deliberately simple model: the action is assumed to return the agent to the same state and produce reward zero. This initial same-state, zero-reward model gives the action a modeled transition that can participate in planning. The action can therefore receive an exploratory value rather than remaining completely absent from the planning process.

Planning Versus Exploration

Ordinary modeled planning uses the learned model to generate simulated experiences from transitions the agent has already represented. Dyna-Q+ keeps that model-based planning idea but adds an exploration signal based on elapsed time. The difference is not simply that Dyna-Q+ plans more; it changes which simulated experiences receive extra encouragement.

Mistakes About Dyna-Q+

• Treating the exploration bonus as an observed environmental reward

  The bonus is added during the planning backup to make a long-untried modeled transition more attractive.

  Fix: Treat κ √τ as an exploration signal used by planning.

• Assuming only previously tried actions can be planned

  Dyna-Q+ allows a never-tried action to enter planning through an initial same-state, zero-reward model.

  Fix: Include the initial model for the never-tried action.

• Giving the same bonus to every transition

  The bonus depends on τ, and a larger elapsed-time count produces a larger bonus.

  Fix: Compare elapsed-time counts when determining which transition receives more encouragement.

• Confusing efficient planning with sufficient exploration

  Planning can become efficient while still creating a blind spot around actions that have been ignored for a long time.

  Fix: Use the elapsed-time signal to direct additional planning attention toward long-untried transitions.

Check Your Understanding

Key Takeaways

1. Dyna-Q+ uses elapsed time since the last real trial as an exploration signal.
2. Its planning backup adds the bonus κ √τ to the modeled reward.
3. The bonus becomes larger when a state-action pair has remained untested for longer.
4. An action that has never been tried can still participate in planning through an initial same-state, zero-reward model.
5. The distinctive exploration mechanism is the use of elapsed time to make neglected modeled experiences more attractive during planning.