Does it make sense to do experience replay when using Monte Carlo method (ex. on-policy first-visit MC control as in chapter 5.4 of Sutton and Barto 2018). Will experience replay help in the context of Monte Carlo control at all? If so, how to implement it? Store $(s_t, a_t, G_t)$ where $G_t=R_{t+1}+R_{t+2}+...+R_{T}$ and sample them later for updating $Q$?
1 Answer
$\begingroup$
$\endgroup$
Does it make sense to do experience replay when using Monte Carlo method (ex. on-policy first-visit MC control as in chapter 5.4 of Sutton and Barto 2018).
Experience replay is inherently off-policy when used for a control problem. When the replay memory recalls a specific experience that happened in the agent's past, the agent will very likely have updated its policy in the intervening steps. Which means that the policy that generated the experience is different to the policy that you wish to update the estimated values for.
This means that you cannot just use the stored Monte Carlo return $G_t$ using your idea of storing $(s_t, a_t, G_t)$.
Instead, you need to store enough data to correct the sampling bias from the mismatched policies. That means for each step, you need to store $(s_t, a_t, \pi_t(a_t | s_t), r_{t+1}, s_{t+1})$, where $\pi_t(a_t | s_t)$ is the probability that the agent chose that action under the policy in effect at the time.
With this you can then re-create trajectories and values of $G_t$ for the current policy using importance sampling. This is fiddly and will involve either storing the original data as complete trajectories, or constructing possible trajectories by looking up replay memory based on $s_t$ to get steps in turn (it is OK to mix and match policies in a single trajectory, provided you know $\pi_t(a_t | s_t)$ and therefore can get the correct weighting to apply.
If you are dealing with long trajectories, a large experience replay table, and you want to target the current guess at an optimal policy for updates, then the whole thing is likely to be very inefficient, as many updates for early state, action pairs will end up having zero relevant information in the replay memory to allow you to calculate the importance sampled return. You only get to find that out by performing the calculation, so in some scenarios you could spend a lot of computing power achieving very little.
Unfortunately, the recalculation of trajectory probabilities in order to perform importance sampling makes this method far more cumbersome than when the same idea of experience replay is applied to single-step TD methods, such a Q learning. Singe-step Q learning still needs to re-calculate a sampled expected return (the TD target) from a given state, action pair - however it only evaluates this using data from a single step and does not actually look at any policy decisions that affect the outcome of that step (the first action $a_t$ does not count as it is the one being re-evaluated, and the second action $a_{t+1}$ does not count because Q-learning takes a $\text{max}$ over all choices, ignoring polciy choice). So single-step Q learning does not need to know what the behaviour policy actually was, and can perform calculations based on just one row from experience replay table.
Moving the idea of experience replay to an approach that works with longer trajectories than a single step is not easy, or it involves some kind of compromise. For example, in the "Rainbow" DQN paper, the authors use n-step returns whilst ignoring the need for importance sampling, and it still makes an improvement to Atari benchmarks even though it gains bias due to not handling off-policy of historical data correctly. That is a risk that offsets reduced bias from longer trajectories against increased bias from off-policy sampling, affected by things such as the size of replay memory and the speed at which policy can change and exploratory moves are taken.
