Dyna-Q is an algorithm developed by Rich Sutton
intended to speed up learning or model convergence for Q learning.
Remember that Q learning is model free.
Meaning that it does not rely on T or R.
T being, our transition matrix and
R being our reward function, it doesn't know it.
Q learning does not know T or R.
Dyna ends up becoming a blend of model free and model based methods.
Here's how it works.
So let's first consider plain old Q learning.
Dyna is really in addition to Q learning.
So let's start with the regular Q learning and
then look at how we add Dyna into it.
So we initialize our Q table and then we begin iterating.
We observe s, we execute action a and
then we have observe our new state s prime and our reward R
within updater our Q table with this experience tubal and repeat.
And we do that over and over and over again, interacting with the world and
our Q table becomes better and better.
So when we augment Q learning with Dyna-Q.
We had three new components, the first is that we
add some logic that enables us to learn models of T and
R then for lack of a better term we halucinate an experience.
So rather than interacting with the real world like we do appear with
the Q learning part and this is expensive by the way.
We hallucinate these experiences, update our queue table and
repeat this many times, maybe hundreds of times.
This operation is very cheap compared to interacting with the real world.
So we can leverage the experience we gain here
from an interaction with the real world, but then update our model
more completely before we step out and interact with the real world again.
After we've iterated enough times down here maybe 100 maybe 200 times.
Then we return back up here and resume our interaction with the real world.
The key thing here is that for each experience with the real world,
we have maybe 100 or 200 updates of our model here.
Let's look at each of these components in a little more detail now.
So in this part where we update our model.
What we really want to do is find new values for T and R.
The point where we update our model includes the following.
We want to update T, so I'm calling it T prime for the moment, which
represents our transition matrix and we want to update our reward function.
Now, remember that T is the probability that if we
are in state s and we take action a will end up in s prime.
And r is our expected reward if we are in state s and we take action a.
I'm going to show you in a moment how we'll update T and
R Here's how we hallucinate an experience.
First, we randomly select an s, second, we randomly select an a,
so our state and action are chosen totally at random.
Then we infer our new state s prime, by looking at T.
And we infer a reward, our immediate reward R by looking at big R or R table.
So, now we've got s, a, s prime and r.
Or a complete experience tuple and we can update our Q table using that.
So, the Q table update is our final step and
this is really all there is to die in a queue.
We've added these three sections and what's missing and I'll get to in just
a moment is how do we update our model of t and our model of r?