GLIE+MC control Algorithm:

enter image description here

My question is why does this algorithm use only a single Monte Carlo episode (during PE step) to compute the $Q(s,a)$? In my understanding this has the following drawbacks:

  • If we have multiple terminal states then we will only reach one (per Policy Iteration step PE+PI).
  • It is highly unlikely that we will visit all the states (during training), and a popular scheduling algorithm for exploration constant $\epsilon = 1/k$ where $k$ is apparently the episode number, ensures that exploration decays very very rapidly. This ensures that we may never visit a state during our entire training.

So why this algorithm uses single MC episode and why not multiple episodes in a single Policy Iteration step so that the agent gets a better feel of the environment?


I feel the general answer is that we want to be as efficient as possible in learning from experience.

Policy improvement here always produces an equivalent or better policy, so delaying the improvement step to gather more episodes will only slow down learning.

I would note too that often a different kind of Monte Carlo learning is used. Instead the speed of the update is typically controlled with a new hyper parameter $\alpha$, instead of keeping track of the visit counts. The Q estimate is then updated something like:

$$ Q \leftarrow Q + \alpha \left (G - Q \right) $$

The value of $\alpha$ then lets you tune how much evaluation vs improvement happens. This is called constant alpha Monte Carlo. Often this is used as a stepping stone to introduce TD methods, e.g., in 6.1 of the Sutton and Barto book.

  • $\begingroup$ Your answer makes point, but I think in David SIlver's Lec 5 he actually mentions it explicitly later that we can do incomplete PE's, but I do not think he mentions whether this algo is also incorporating incomplete PE. $\endgroup$
    – user9947
    Jul 11 '19 at 3:51
  • $\begingroup$ This is definitely incomplete (or truncated) policy iteration. Doing complete evaluation would mean running more episodes until the Q estimate converges to the exact Q for the current policy, then improving the policy with the state-by-state greedy action. $\endgroup$
    – tahsmith
    Jul 11 '19 at 12:19
  • $\begingroup$ you are correct, just checked it. Thanks! $\endgroup$
    – user9947
    Jul 11 '19 at 12:36

Your Answer

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