Every-Visit MC Prediction

The algorithm of every-visit MC prediction is given as follows:

1. Let total_return(s) be the sum of the return of a state across several episodes and N(s) be the counter, that is, the number of times a state is visited across several episodes. Initialize total_return(s) and N(s) as zero for all the states. The policy is given as input.
2. For M number of iterations:
   1. Generate an episode using the policy
   2. Store all the rewards obtained in the episode in the list called rewards
   3. For each step t in the episode:
      1. Compute the return of the state s_t as R(s_t) = sum(rewards[t:])
      2. Update the total return of the state s_t as total_return(s_t) = total_return(s_t) + R(s_t)
      3. Update the counter as N(s_t) = N(s_t) + 1
3. Compute the value of a state by just taking the average, that is: