In this lecture we are going to discuss how to implement a replay memory or replay buffer efficiently
to understand why we would want to do this.
Let's first consider how we might implement a replay buffer using a naive programming approach.
Once we've done that we'll discuss why it's not ideal and then move on to a better version.
In essence a replay buffer is simply a python list.
Inside this list we are going to store tuples with five elements each SARS Prime and the Dunn flag.
So as our agent takes a step and encounters a new tuple it will just store this tuple in our list.
The buffer of course has a maximum size.
So once we've hit the size limit we're going to throw out the old its value.
How do we do that.
Well we can use the python function pop and passing the argument 0.
This means remove the element at index 0
next.
Let's consider how we will use the buffer during training.
What we would like to do is grab a batch of random samples from our buffer.
From this we can calculate input target pairs and then do one step of gradient descent.
Remember that the target will be calculated as our plus gamma times the mass over a prime of Q of vast
prime a prime and this only applies if as prime is not a terminal state.
Otherwise the target is just the reward by itself.
In other words we're going to do some kind of calculation over the batch of data we just sampled.
Here's how you might do this.
Start with an empty array of targets.
Then loop through each of the tuples you sampled for each iteration check whether the done flag is true
or not.
If it's true then the target is just ah.
Otherwise it's just the formula we saw previously.
Of course as you may know we don't like doing for loops in Python.
If we can avoid for loops we'll be slower than doing batch operations and num PI.
It's true that you could gather the batches together and cast them into an umpire race but that means
you still had to store a bunch of lists not ideal
here's another problem with continually appending a new tuples and popping old ones.
It may seem like this will take up only a constant amount of memory since the memory storing the old
removed values should be freed by the garbage constructed.
Unfortunately python will not do this and you will end up with a memory leak and a very slow computer.
This probably won't be an issue with a modestly sized dataset like the one we have but it's good to
be aware of the kinds of problems that may arise when you want to graduate to more advanced applications.
So what's the solution the solution is to implement your own replay buffer.
Here's a high level view of how it'll work.
First we're going to pre allocate the arrays we will use to store the states actions rewards and so
on.
So this will really take up a constant amount of RAM.
We will never allocate new arrays nor try to remove any arrays.
All we will do is populate our pre allocated arrays.
Second we'll use a pointer which will tell us the current insertion location of our transition tuples.
So every time we encounter a new tuple we'll store it in the next available location in the array.
Now what happens when the array is full.
While all this value is at the beginning.
So that means we can simply overwrite it in this way our buffer is circular.
When we get to the end we just go back to the beginning.
In this example you see here we can see that the pointer shows us the value at the current time t.
But before that we have the value at the previous time.
T minus 1.
This goes back to T minus 2 T minus 3.
But whereas T minus 4.
In fact it's at the end of the array because when we store the value for T minus 4 we were at the end.
So the next value T minus 3 would have been stored at the beginning since we had to circle back to replace
the all this value on the next step.
We would replace the current all this value which is at T minus nine
one small detail.
We have to think about is what happens when the array is not yet full.
In this case we will still need to keep track of the current size of our buffer.
For example the pre allocated array may be of size 10 but we will only have store 5 values than the
effective size of the buffer will be 5.
When we sample a batch from this buffer we can only sample values from zero up to 5
so that's it for this lecture instead of using the naive approach of storing our transitions in a list
then sampling from the list to get yet another list.
We will instead use a fixed size array and store transitions in this fixed size array in a circular
fashion.