When are Q values calculated in experience replay?

Question

In experience replay, the update rule follows the loss:

$$ L_i(\theta_i) = \mathbb{E}_{(s_t, a_t, r_t, s_{t+1}) \sim U(D)} \left[ \left(r_t + \gamma \max_{a_{t+1}} Q(s_{t+1}, a_{t+1}; \theta_i^-) - Q(s_t, a_t; \theta_i)\right)^2 \right] $$

I can't get my head around the order of calculation of the terms in that equation:

An experience element is

$(s_t, a_t, r_t, s_{t+1} )$

where

$s_t$ is the state at time $t$

$a_t$ is the action taken from $s_t$ at time $t$

$r_t$ is the reward received by taking that action from $s_t$ at time $t$

$s_{t+1}$ is the next state

In the on policy case, as I understand it, Q of the equation above is the same Q, which is the only approximator.

As I understand the algorithm, at time $t$ we save an experience

$(s_t, a_t, r_t, s_{t+1} )$.

Then, later, at time $t+x$, we attempt to learn from that experience.

However, at the time of saving the experience, $Q(s_t,a_t)$ was something different than at the time of attempting to learn from that experience, because the parameters $\theta$ of $Q$ have since changed. This could actually be written as

$Q_t(s_t, a_t) \neq Q_{t+x}(s_t,a_t)$

Because the Q value is different, I don't see how the reward signal at time $t$ is of any relevance for $Q_{t+x}(s_t,a_t)$ at $t+x$, the time of learning.

Also, it is likely that following a policy that is derived from $Q_t$ would lead to $a_{t}$, whereas following a policy that is derived from $Q_{t+x}$ would not.

I don't see in the experience replay algorithm that the Q value $Q_t(s_t, a_t)$ is saved, so I must assume that is not.

Why does calculating the Q value again at a later time make sense FOR THE SAME SAVED REWARD AND ACTION?

Answer 1

Because the Q value is different, I don't see how the reward signal at time $t$ is of any relevance for $Q_{t+x}(s_t,a_t)$ at $t+x$, the time of learning.

The $r_t$ value for any single step is not dependent on $Q$ or the current policy. It is purely dependent on $(s_t,a_t)$. That means you can use the Q update equation to use it to calculate new TD targets, by combining your knowledge of the old reward signal and the value functions of the latest policy.

The value $r_t + \gamma \max_{a_{t+1}} Q(s_{t+1}, a_{t+1}; \theta_i^-)$ is the TD target in the loss function you show. There are many possible variations to calculate the TD target value in RL, with different properties. The one you are using is biased towards initial random values unrelated to the problem, and also deliberately biased towards older Q values to prevent runaway feedback. It is also low variance compared to other possibilities, and simpler to calculate.

Also, it is likely that following a policy which is derived from $Q_t$ would lead to $a_{t}$, whereas following a policy which is derived from $Q_{t+x}$ would not.

Yes that is correct. However, you don't care about that for a single step, you just care about calculating a better estimate for $Q(s,a)$ regardless of whether you would choose $a$ in state $s$ with the current policy. That is what an action value measures - the utility of taking action $a$ in state $s$ and thereafter following a given policy.

This is a strength of experience replay, that you are constantly refining your estimates of off-policy action values to determine which is the best.

This does become more of an issue when you want to use longer trajectories in the update step (which you may want to do to reduce bias of your TD target estimate). A series of steps in history $s_t,a_t,r_t ... s_{t+1}, a_{t+1},r_{t+1}...s_{t+n}$ may not have the same chance of occurring under the latest policy as it did when it was stored in memory. For the first step $s_t,a_t$ again you don't care if it is one you would currently take because the point is to refine your estimate of that action value. However, if you want to use $r_{t+1}, r_{t+2}$ etc plus $s_{t+n}$ to create a TD target, then you have to care whether your current policy and the one used to populate the history table would be different.

It is a problem if you want to use more sophisticated estimates of TD target that use multiple sample steps along with experience replay. There are some approaches you can take to allow for this, such as importance sampling. For a single step update mechanism you don't need to worry about it.

I don't see in the experience replay algorithm that the Q value $Q_t(s_t, a_t)$ is saved, so I must assume that is is not.

This is correct. You must re-calculate the TD target from a more up-to-date policy to get better estimates of the action value. With experience replay, you are not interested in collecting a history of values of Q. Instead you are interested in the history of state transitions and rewards.

Why does calculating the Q value again at a later time make sense FOR THE SAME SAVED REWARD AND ACTION?

Because it will change, due to the learning process summarising effects of state transitions.

As a toy example, consider a maze solver with traps (negative rewards) and treasures (positive rewards). At one point in history, the agent finds itself in a location and its policy told it to move into a trap on the next step. The agent would initially score location and steps leading up to it with negative Q values. Later it discovers through exploration that there is also some treasure if it takes a different turning towards the end of the the same series of steps. With experience replay, and re-calculating Q values each time, it can figure out which section of that path should be converted to high scores because they lead to treasure as well as the trap and now the agent has a better policy for the end of the path it has better estimates of value there.

Answer 2

Once the algorithm reaches a point where a reward (or penalty) is gained, then a slowly decaying amount of that reward is given to the Q-value of whichever action was derived from a particular state for each time step back through the game (or however far back you want to apply that reward). You will have stored the state and Q-values for each time step during the game, allowing you to update the appropriate Q-values with the new reward. These state / updated Q-values (from many runs) become your training data for the next iteration of your training algorithm.