Dyna: learn a model of the world, then practise in it

The Q-learning post moved one cell of the table a fraction of the way towards a target after each real step. Ten days of trading gave ten updates, and a cell the learner did not visit did not move. That is slow, and in a market it is also expensive: every real step means a position held for a day with real money on it. Dyna is Sutton and Barto’s answer to the question “can the learner get more than one update out of one real day?”. The answer is yes, if it keeps a record of what it has seen and practises on the record. This post builds that record from the same ten days of SPY in January 2023, runs one practice update by hand, and then looks at the ways the record can lie.

A model is a table of what followed what

Sutton and Barto’s definition is deliberately plain: a model of the environment is “anything that an agent can use to predict how the environment will respond to its actions” (section 8.1). Given a state and an action, it predicts the next state and the reward. They draw one distinction inside that. A distribution model lists every possible outcome with its probability; a sample model produces one outcome, drawn with the right probability. Their example is the sum of a dozen dice: writing a program that rolls them and returns the sum is easy, listing every sum with its probability is harder, so sample models are often the ones you can actually build.

The model in Dyna-Q, their simplest version, is a table with one row per state–action pair the learner has actually experienced. After each real step the row for that state and action is overwritten with the reward and next state just observed (section 8.2). Table 1 has the ten real steps of the January 2023 episode. The state is what SPY did the day before, up or down, and the action every day is “go long”, because the learner was long throughout:

After these ten steps the Dyna-Q model has two rows (Table 2), because only two state–action pairs were ever tried:

Two of the table’s four cells have a model row; “go cash” was never tried from either state, so the model knows nothing about it. That matters for the next step, because the book is explicit that planning “randomly samples only from state–action pairs that have previously been experienced”, so the model is never asked about a pair it has no information on (section 8.2).

Every real step is used twice

Sutton and Barto name the two uses (section 8.2). Real experience can improve the value table directly, which they call direct reinforcement learning, and it can improve the model, which they call model-learning. The model then produces simulated experience, and running the learning rule on simulated experience is planning. Their Dyna-Q loop is the Q-learning loop with two steps added: after the real update, record the transition in the model; then, n times, pick a remembered state and a remembered action from it, ask the model for the reward and next state, and apply the identical Q-update. Leave out those two steps and “the remaining algorithm would be one-step tabular Q-learning”.

The identical update is the point. Here it is with the model’s prediction in place of the fresh observation:

Q, the cell being updated; α, the learning rate; γ, the discount factorR, the reward the model remembers for the pair; S′, the next state it remembers

Table 3 is a made-up starting table like the one in the Q-learning post, with the states named to match the model. Rows are states, columns actions, cells in percent of the position:

The real step on day 1: state yesterday down, action go long, reward $\good{-0.42\%}$, next state yesterday down. The best entry in the next state’s row is 0.30, so the target is $-0.42 + 0.9 \times 0.30 = \good{-0.15}$, the error is $-0.15 - 0.30 = \risk{-0.45}$, and at a learning rate of 0.2 the cell goes from 0.30 to $\key{0.21}$. That is the update from the Q-learning post, nothing new.

Now a planning step. After day 3 the model has a row for both pairs. To keep the arithmetic easy to compare, the step below still uses the starting table, not the table after three real updates. The learner draws one at random, say the pair “yesterday up, go long”, and the model returns what it recorded on day 3: reward $\good{-1.14\%}$, next state yesterday down. The target is $-1.14 + 0.9 \times 0.30 = \good{-0.87}$, the error is $-0.87 - 0.50 = \risk{-1.37}$, and at 0.2 the cell goes from 0.50 to $\key{0.23}$. Same formula, same learning rate, same discount. The one difference is that no market was consulted: the reward and the next state came from a table in memory. Sutton and Barto call the learning rule the “final common path” for both kinds of experience, with learning and planning “differing only in the source of their experience” (section 8.2).

One real step, n practice steps, one rule. Planning is Q-learning run on remembered transitions instead of fresh ones; the model is the memory it runs on.

What n buys, and what it costs

The parameter $n$ is how many planning updates follow each real step. With ten real days the table receives ten updates at $n = 0$, which is plain Q-learning, sixty at $n = 5$, and 510 at $n = 50$. The real steps are the same ten in every case. What changes is how much of the table each one is allowed to touch (Figure 1, first panel).

Sutton and Barto’s maze experiment (Example 8.1) shows what the extra updates do. Their agent without planning took about 25 episodes to find the shortest route; with five planning steps per real step it took about five, with fifty about three. Their figure 8.3 explains why. Without planning, each episode teaches the agent one more step of the route, the last one, because the value of reaching the goal has to travel backwards one cell per visit, as in the Q-learning post. With planning, the same backward travel happens in memory between real steps, so by halfway through the second episode the agent has a route almost all the way back to the start while it is “still wandering near the start state”.

The price is compute. Sutton and Barto put it as indirect methods making “fuller use of a limited amount of experience” and so reaching a better policy “with fewer environmental interactions”, while direct methods are “much simpler and are not affected by biases in the design of the model” (section 8.2). When real steps are cheap, as in a video game, the trade hardly matters. When each real step is a day of market exposure, it is the whole case for building a model, and the second half of their sentence is the warning.

When the model is wrong

The model above was built from a world that never changed and recorded exactly what happened. Sutton and Barto list three ways a model goes wrong (section 8.3): the environment is random and only a few samples have been seen; the model generalises imperfectly; or the environment has changed and the new behaviour has not been observed yet. The first and third are the market’s everyday condition.

Random outcomes. The last-outcome model answers “yesterday down, go long” with +0.70%, next state up, because that is what happened on day 6, the last down day. But that pair was seen four times, and the four rewards were $\bad{-0.42\%}$, $\good{+0.77\%}$, $\good{+2.29\%}$ and $\good{+0.70\%}$: an average of $\key{0.84\%}$ with a spread (standard deviation) of $\risk{0.97\%}$, and the next state was “up” three times out of four, not always (Figure 1, second panel). A model that keeps one outcome has collapsed that spread to a point, and every planning step that draws the pair replays the same point. Fifty planning steps a day do not add evidence; they repeat the one memory fifty times. The fix the book points to is a model that keeps counts of what followed each pair and samples from them, or uses all of them with their probabilities, which is the distribution model from the first section; prioritised sweeping for random environments does exactly this (section 8.4). On the “yesterday up” pair the gap is larger still: last outcome $\bad{-0.18\%}$, average over six visits $\good{+0.11\%}$.

A changed world. Their blocking-maze and shortcut-maze examples (8.2 and 8.3) separate two cases. When the world gets worse, the planned policy walks into the change and discovers it, because the model is optimistic and “the planned policy attempts to exploit these opportunities and in doing so discovers that they do not exist”. When the world gets better, nothing forces the discovery. In the shortcut maze a new, shorter path opened and the Dyna-Q agent “never realized that it existed. Its model said that there was no shortcut, so the more it planned, the less likely it was to step to the right and discover it.” Planning on a stale model does not merely fail to learn the change; it hardens the old answer, because each replay is another update towards it. The book’s remedy, Dyna-Q+, adds a bonus to the simulated reward of transitions that have not been tried for a long time, so that long-untested beliefs get checked against the real world again.

A model cannot contain what it has never seen. Replaying it more makes the learner more sure, not more right; only a real step can correct it.

The lesson reaches past Dyna. A backtest is a model of the market built from recorded transitions, and a strategy tuned on it is a learner planning on that model. Everything above applies: a single history is one sample path, not the distribution; a regime that has ended is a shortcut that closed; and the more times the same history is replayed, the more confident the result looks, for the same reason and with the same lack of new evidence.

Traps

Table 4 lists the usual misreadings.

The code

The snippet reproduces Table 2 and the one planning update. Its variables are in Table 5:

import pandas as pd

url = "https://raw.githubusercontent.com/ankurtrapasiya/examples/main/data/prices.csv"
px = pd.read_csv(url, index_col="date", parse_dates=True)["SPY"]
r = 100 * (px / px.shift(1) - 1).dropna()
i0 = r.index.get_loc(pd.Timestamp("2023-01-03"))
state = lambda ret: "yesterday up" if ret > 0 else "yesterday down"
steps = [(state(r.iloc[i0 + t - 1]), r.iloc[i0 + t], state(r.iloc[i0 + t])) for t in range(10)]

model = {}
for s, reward, s2 in steps:
    model[s] = (reward, s2)            # overwrite: the model keeps only the last outcome
for s, (reward, s2) in model.items():
    print(f"Model({s}, go long) = reward {reward:+.2f}%, next {s2}")

Q = pd.DataFrame({"go long": [0.50, 0.30], "go cash": [0.00, 0.10]}, index=["yesterday up", "yesterday down"])
reward, s2 = steps[2][1], steps[2][2]  # a planning step replaying the day-3 memory
target = reward + 0.9 * Q.loc[s2].max()
print(f"planning: 0.50 + 0.2 x ({target - 0.50:+.2f}) = {0.50 + 0.2 * (target - 0.50):.2f}")

It prints the two model rows, +0.70% then up for the down state and −0.18% then down for the up state, and then the planning update $0.50 + 0.2 \times (-1.37) = 0.23$. The model[s] = ... line inside the loop is the overwrite: Python dictionaries keep one value per key, which is exactly what a last-outcome model does.

Summary

Table 6 is the post in one line per idea.

References

• Sutton and Barto, Reinforcement Learning: An Introduction, 2nd edition (MIT Press, 2018). Section 8.1 for the definition of a model, distribution and sample models, the dice example, planning as a process from model to policy, and random-sample one-step tabular Q-planning; section 8.2 for direct reinforcement learning versus model-learning, the Dyna architecture (figure 8.1), search control, the tabular Dyna-Q algorithm with its deterministic last-outcome model and its restriction to previously experienced pairs, the comparison of direct and indirect methods, and the maze results (Example 8.1, Figures 8.2 and 8.3); section 8.3 for the three sources of model error, the blocking and shortcut mazes (Examples 8.2 and 8.3) and Dyna-Q+; section 8.4 for prioritised sweeping and the count-based model for stochastic environments.