In Richard Sutton's book on RL (2nd edition), he presents the Dyna-Q algorithm, which combines planning and learning.

In the planning part of the algorithm, the Dyna-agent randomly samples n state-action pairs $(s, a)$ previously seen by the agent, feeds this pair into its model of the environment and gets a sampled next state $s'$ and reward $r$. It then uses this set $(s,a,r,s')$ to perform its usual Q-learning update.

In a deterministic environment, the reward and next state are always the same for a given state-action pair $(s_t,a_t)\to(r_{t+1},s_{t+1}')$. In his chapter on Dyna-Q, Sutton does not refer to this process as being a form of experience replay, and only introduces the latter concept much later in the book. However I can't really see the distinction (if there is one) between those two processes.

Is it correct to say that in a deterministic environment, planning in Tabular Dyna-Q is a form of experience replay ?

Tabular Dyna-Q from Sutton's book, sectionn 8.2


2 Answers 2


Is it correct to say that in a deterministic environment, planning in Tabular Dyna-Q is a form of experience replay ?

I would say that it's not entirely correct to say this, only because the terms "Experience Replay" and "Dyna-Q" are well-understood as referring to specific implementations. It is true that in the specific situation you describe (tabular RL in deterministic environments), they end up doing similar things. However, they still do these similar things using different implementations, which may create subtle differences in practice. For example, the two ideas probably have different memory requirements. For this reason, I don't think it's ever correct to use one term when the other is meant, even though they are very close to each other in this situation.

The following is a quote from the Conclusion of "Reinforcement Learning for Robots Using Neural Networks" (1993), Long-Ji Lin's dissertation. This is one of the first sources of Experience Replay. Throughout the entire document, Experience Replay and Dyna are consistently treated as different ideas, but indeed with many similarities:

This dissertation proposed a technique called experience replay. This technique in effect takes advantage of a model, but does not have the difficult problem of building a model, because the model is simply the collection of past experiences.

So the important distinction really isn't in what they accomplish, but how they do it. Once you move beyond the setting you described (Function Approximation instead of tabular, and/or nondeterministic instead of deterministic), you'll see more apparant differences.


In some papers the two concepts are considered the same, e.g.: Krueger, Paul, Thomas Griffiths, and Stuart J. Russell. "Shaping Model-Free Reinforcement Learning with Model-Based Pseudorewards." (2017).

However, there may be a difference in the way the update is done. Dyna uses the value function and the prediction error directly. It can thus use one single simulated step update.

Using replay may be more similar to use montecarlo updates that consider the cumulative reward over a sequence of actions and do not use the value function or the prediction error in the update.

Z. Feldman and C. Domshlak, “Monte-Carlo tree search: To MC or to DP?,” in ECAI 2014: 21st European Conference on Artificial Intelligence, 2014, vol. 263, p. 321


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.