Does the environment pay the bonus?

No; it is added internally during planning.

Does a simulated visit reset the clock?

No; the clock concerns real trials.

Is Dyna-Q+ guaranteed to discover every improvement quickly?

No; accessibility, exploration and modeling choices still matter.

AI Glossary / Reinforcement learning and robotics / Advanced

Dyna-Q with exploration bonus (Dyna-Q+)

Definition

Dyna-Q with exploration bonus, usually called Dyna-Q+, extends Dyna-Q by encouraging the agent to revisit state-action pairs that have gone untried for a long time. During planning, it adds a bonus based on elapsed real interaction time to the modeled reward. The purpose is to encourage exploration that can reveal changes or missing information in the environment model.

What it means

A model may describe what happened previously without reflecting what is possible now. An agent that only exploits familiar routes can miss a newly opened shortcut because its old model still says that the route is blocked. Dyna-Q+ makes long-untried choices increasingly attractive through planning updates.
The bonus is an exploration incentive, not an observed environmental reward or proof that an action has improved. Trying a stale action can reveal an opportunity, confirm the old model or incur an exploration cost.

How it works

Dyna-Q+ retains Dyna-Q's combination of direct learning, model updates and planning. For each state-action pair, it tracks tau, the number of real time steps since that pair was last tried. A planning update uses modeled reward r plus kappa times the square root of tau, where kappa controls the bonus scale.
The resulting target also includes the usual discounted next-state value for a nonterminal modeled transition. Real interaction updates use the reward actually observed. Simulated planning visits do not count as new real trials for resetting the elapsed-time record.
The textbook's Dyna-Q+ setup also permits planning over actions not yet tried in an observed state. Their initial model predicts a return to that same state with reward zero.

Three practical examples

Changing navigation: an agent has reason to recheck a previously blocked direction after the environment may have changed.
Simulator experiments: researchers compare adaptation with and without the bonus while separately measuring exploration costs and observed returns.
Model maintenance: a team examines how long each accessible state-action pair has gone without a real trial, distinguishing stale evidence from frequent simulated reuse.

Think of it this way

Imagine a reminder to revisit an old assumption. The longer it has gone unchecked, the stronger the reminder becomes. The reminder does not establish that the assumption is false; only a new observation can do that. Re-reading the old note is not the same as checking the situation again.

Worked example

Consider an original planning calculation for two modeled actions, A and B. Both have modeled reward zero, and both lead to successor states whose current maximum action values are zero. Let alpha = 0.5, gamma = 0.9 and kappa = 0.1. Initially, Q(A) = 0.3 and Q(B) = 0.1.
Suppose A was last tried 4 real time steps ago, while B was last tried 100 steps ago. Their bonuses are 0.1 times square root of 4 = 0.2 and 0.1 times square root of 100 = 1.0. Because the successor values are zero, these are also their planning targets.
One planning update for A gives 0.3 + 0.5 times (0.2 - 0.3) = 0.25. One planning update for B gives 0.1 + 0.5 times (1.0 - 0.1) = 0.55. Before these updates, A had the larger estimate. After them, B does. The preference changed because of the exploration bonus, not because a new environmental reward was observed.
For comparison, ordinary Dyna-Q updates under the same zero modeled rewards and zero successor values would give Q(A) = 0.15 and Q(B) = 0.05. A would remain preferred.
Now suppose the agent actually tries B. It receives reward zero and reaches a successor whose maximum estimated value is still zero. The direct Q-learning update moves Q(B) from 0.55 to 0.275. At that real trial, B's elapsed-time clock is reset; a subsequent planning calculation with tau = 0 has no bonus. Under the same successor-value assumption, another update would move its estimate to 0.1375.
The age clock matters. If the agent merely planned about B ten times without trying it, those simulated repetitions would not constitute ten fresh observations. Nor should they reset its clock as if the environment had been checked. The clock advances according to real interaction steps, not the number of planning updates.
The square root also makes the bonus grow less than proportionally with age. Increasing tau from 100 to 400 doubles the bonus from 1 to 2; it does not quadruple it. These illustrative numbers show the mechanism, not a recommended parameter setting or a measured adaptation benefit.

Illustrative case study

Fictional company Cedar Routes studies a simulator in which an unused passage can become available. Its team records environmental rewards, planning bonuses and elapsed-time counters separately. It checks whether agents actually revisit the passage rather than simply increasing its modeled value.
The analysts compare discovery time with the cost of extra exploratory moves. If the passage never changes, those checks may provide little benefit. The team therefore evaluates both changing and unchanged scenarios. This fictional study reports no measured result or operational recommendation.

Common misconceptions and mistakes

The bonus is not evidence that an action is rewarding. It deliberately encourages checking possibilities that may be stale or unexplored. Resetting tau during simulated planning would confuse computation with observation and weaken that purpose.
Another mistake is adding the bonus only to action selection and calling it the same algorithm. That is a different variant from modifying planning targets. The bonus scale also interacts with the environment's reward scale: a value appropriate in one task need not be suitable in another. Finally, the model's handling of never-tried actions must be specified alongside the bonus rule.

Business use

Dyna-Q+ illustrates how a learning system can devote effort to checking assumptions when conditions change. In simulated evaluations, teams should report actual rewards separately from exploration incentives and measure the costs of repeated testing. The relevant comparison includes both adaptation after changes and behavior when no useful change occurs.

Check your understanding

Why did B's planning target exceed A's?

Answer: B had gone longer without a real trial.

Why did trying B reduce its estimate in the example?

Answer: Its observed target was zero rather than the bonus-enhanced target.

Why did quadrupling age only double the bonus?

Answer: The formula uses the square root of age.

Related terms

Dyna-Q
Exploration bonus
Model-based reinforcement learning
Nonstationary environment
Planning update
Exploration-exploitation trade-off
Model staleness

Learn next

Vary kappa and compare bonus-driven estimates with observed return, keeping real and simulated time separate.

Sources

Sutton and Barto, Reinforcement Learning: An Introduction, second edition, Section 8.3, including the Dyna-Q+ footnote: https://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf . The planning calculations and company scenario are original illustrations.

Previous: Dyna-Q Next: Dynamic backtracking