3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ there's no difference it's the same thing. Incremental update is more appropriate because you don't have to save returns in the memory . $\endgroup$ – Brale Jun 6 '19 at 18:16
  • $\begingroup$ @Brale_ Thanks for your comment. Can you mathematically show why it is the same in an answer? $\endgroup$ – Miguel Saraiva Jun 6 '19 at 18:43
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.