First-Visit MC Prediction

The algorithm of first-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 rewards obtained in the episode in a list called rewards
   3. For each step t in the episode:

   If the state s_t is occurring for the first time 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: