Why is an average of all returns used to update the value in the first-visit MC control?

Question

In Sutton & Barto's Reinforcement Learning: An Introduction, in page 83 (101 of the pdf), there is a description of first-visit MC control. In the phase where they update $Q(s, a)$, they do an average of all the returns $G$ for that state-action pair.

Why don't they just update the value with a weight for the value from previous episodes $\alpha$ and a weight $1- \alpha$ for the new episode return as it is done in TD-Learning?

I have also seen other books (for example, Algorithms for RL (page 22) where they update it using $\alpha$. What is the difference?

Answer 1

Why don't they just update the value with a weight for the value from previous episodes $\alpha$ and a weight $1- \alpha$ for the new episode return as it is done in TD-Learning?

In my opinion, this is a mistake in the book. I went back and checked that this is still the same in the finished second edition, and it is still there.

Keeping all returns and taking averages works fine in a prediction scenario with a fixed policy, and it is somewhat simpler and more intuitive to explain as "this is the mean value" (efficiency can come later, after comprehension). However, the pseudo-code is incorrect for a control scenario where older returns (that you still refer in the list) will not reflect the current policy, so will be biased.

In practice, no-one really uses the MC Control algorithms as written. Nearly always a learning rate parameter, $\alpha$ is used to update estimates.

What is the difference?

In a prediction scenario, where you want to evaluate a fixed policy, it would be slightly more efficient to use a count of samples for each $s,a$ pair and variable $\alpha = \frac{1}{N(s,a)}$ which is mathematically identical to keeping a list and taking the average as needed.

In a control scenario using a list of old return values is not only memory inefficient, it is also sample inefficient as you would need samples from each improved policy to outnumber the older samples in order to remove sampling bias due to using returns from initial worse policies. A fixed, or slowly decaying $\alpha$ is a simple and efficient way of "forgetting" the old return values as they become less relevant to the task.

Another way to achieve similar forgetting may be to have a maximum size for each $Returns(s,a)$ list. However, that is not mentioned in the MC Control pseudocode.

Perhaps I am missing something, as the book has been through significant review process. However, it may be that this detail is overlooked because the basic MC Control scenarios are not as interesting as all the extensions and combinations with TD, where you will find the book does use a learning rate $\alpha$ - including when making comparison charts of MC vs TD approaches etc. The explicit list of returns and averaging over them for control only occurs in a couple of places in the text in this pseudocode, and is not mentioned again.