Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 37 ยท Q-learning and SARSA

Dyna-Q: Learning and Planning

Learn Dyna-Q: combine real experience with a learned model to plan in the background, and see how planning steps speed up learning on a maze with runnable Python code.

Everything so far has been model-free: the agent learns values straight from experience and throws each transition away after one update. That wastes information. If you have already walked through a door once, you know where it leads; you do not need to walk through it 50 more times to propagate that fact through your Q-table.

Dyna-Q fixes this by adding a model: a memory of what happened after each state-action pair. Between real steps, the agent replays imagined transitions from the model and updates Q from them. This is planning, and it multiplies the learning that each real step buys.

Learning, planning, acting

Dyna interleaves these activities in one loop:

  1. Act in the real environment and observe (s, a, r, s').
  2. Learn directly: apply the ordinary Q-learning update to that transition.
  3. Model-learn: store model[(s, a)] = (r, s').
  4. Plan: repeat n times: pick a previously seen (s, a) at random, look up (r, s') in the model and apply the same Q-learning update to it.
flowchart LR
    E["Real environment"] -->|"experience"| Q["Q-table"]
    E -->|"experience"| M["Model"]
    M -->|"simulated experience (n planning steps)"| Q
    Q -->|"epsilon-greedy action"| E

Real steps are expensive; simulated steps are nearly free. Dyna turns computation into learning.

With n = 0 you get plain Q-learning. With n = 30 each real step triggers 30 extra updates. The cost is computation, not environment interaction, which matters a lot when real interaction is slow, costly or risky (a robot, a patient, a real market).

Dyna-Q on a maze

Here is a small maze: # is a wall, S the start and G the goal (reward +1, everything else 0). We count how many steps each episode takes and compare n = 0 (plain Q-learning) with n = 10 and n = 30 planning steps. Every row is an average over three seeds.

Python Dyna-Q with 0, 10 and 30 planning steps

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read each row left to right: it is the number of steps episode 1, 2, 3 ... needed. The shortest route is 14 steps. Plain Q-learning (n = 0) improves slowly, while the planning agents settle on a short route within a few episodes. The agent did not see more of the world; it extracted far more from each observation.

Why it works, and where it breaks

Without planning, reward information travels backwards one step per visit. After the agent first reaches the goal, only the last state before the goal changes. Planning lets the information ripple through the whole remembered path within one episode, because replayed transitions update predecessor states too. You can watch this directly: after one successful episode, how many states already know a direction to the goal?

Python How far does one success spread?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The grids show max Q scaled to a digit (higher means closer to the goal as the agent currently believes). With n = 0 only the state next to the goal lights up; with planning, positive digits spread back along the path the agent took.

This relies on the model being correct. The tabular model above is exactly right for a deterministic environment. If the world is stochastic, store counts or sample outcomes. If the world changes, the model becomes wrong, and planning with it confidently chases a goal that has moved.

Dyna-Q+ and changing worlds

Dyna-Q+ adds an exploration bonus for state-action pairs that have not been tried for a long time: during planning, use the reward r + kappa * sqrt(tau), where tau is the number of steps since that pair was last really tried and kappa is small (around 0.001 to 0.01). When a shortcut opens somewhere the agent has not looked for a long time, the bonus makes planning curious enough to re-test it. If kappa is too large, the agent keeps wandering instead of using what it knows.

Prioritized sweeping (a short note)

Uniform random replay wastes effort on states whose values would not change. Prioritized sweeping keeps a priority queue ordered by the size of the expected value change, and updates the biggest ones first, then pushes the predecessors of changed states. It reaches the same solution with far fewer updates on large problems. Its spirit lives on in prioritized experience replay in deep Q-networks.

Common mistakes

  • Sampling planning updates from state-action pairs never visited (the model has no data there).
  • Storing only s' and not the terminal flag, so planning bootstraps past the end of an episode.
  • Treating a stochastic environment as deterministic in the model.
  • Cranking n up with no limit: planning time per step grows linearly.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the model in Dyna-Q store?

    The model predicts (r, s') for a pair (s, a) from past experience; planning samples from it.
  2. 2. What is Dyna-Q with n = 0 planning steps?

    With no simulated updates the agent only applies the real-experience Q-learning update.
  3. 3. Why do planning steps speed up learning?

    Replaying stored transitions updates many states per real step.
  4. 4. What problem does Dyna-Q+ address?

    Its bonus for long-untried state-action pairs encourages re-checking parts of the world that may have changed.

Summary

  • Dyna-Q learns a model of the environment from real experience and plans by replaying simulated transitions.
  • Each real step triggers n extra Q-updates, so learning needs far fewer real episodes.
  • It depends on an accurate model; a changed environment makes planning go stale.
  • Dyna-Q+ adds a curiosity bonus for pairs not tried recently; prioritized sweeping chooses which updates to replay.
  • Model-based ideas return later in environments and applications.

Next: Function Approximation: Why Tables Run Out