Difficulty understanding Monte Carlo policy evaluation (state-value) for gridworld

Question

I've been trying to read Sutton & Barto book chapter 5.1, but I'm still a bit confused about the procedure of using Monte Carlo policy evaluation (p.92), and now I just cant proceed anymore coding a python solution, because I feel like I don't fully understand how the algorithm works, so that the pseudocode example in the book doesn't seem to make much sense to me anymore. (the orange part)

I've done the chapter 4 examples with the algorithms coded already, so I'm not totally unfamiliar with these, but somehow I must have misunderstood the Monte Carlo prediction algorithm from chapter 5.

• My setting is a 4x4 gridworld where reward is always -1.
• Policy is currently equiprobable randomwalk. If an action would take the newState (s') into outside the grid, then you simply stay in place, but action will have been taken, and reward will have been rewarded.
• Discount rate will be 1.0 (no discounting).

• Terminal states should be two of them, (0,0) and (3,3) at the corners.

  1. On page 92 it shows the algorithm pseudocode and I feel as though I coded my episode generating function correctly thusfar. I have it such that, the results are that I always start in the same starting state (1,1) coords in the gridworld.

  2. Currently, I have it so that if you started always in state (1,1), then a possible randomly generate episode could be as follows (in this case also optimal walk). Note that I currently have the episodes in form of list of tuple (s, a, r). Where s will also be a tuple (row,column), but a = string such as "U" for up, and r is reward always -1.

  3. so that a possible episode could be like: [( (1,1), "U", -1 ), ( (0,1), "L", -1 )] So that the terminal state is always excluded, so that the last state in episode will be the state immediately close to terminal state. Just like the pseudocode describes that you should exclude the terminal state S_T. But, the random episode could have been one where there are repeating states such as [( (1,1), "U", -1), ( (0,1), "U", -1 ), ( (0,1), "U", -1 ), ( (0,1), "L", -1 )]

  4. I made the loop for each step of episode, such as follows: once you have the episodeList of tuples, iterate for each tuple, in reversed order. I think this should give the correct amount of iterations there...

  5. G can be updated as described in pseudocode.

  6. currently the Returns(S_t) datastructure that I have, will be a dictionary where the keys are state tuples (row,col), and the values are empty lists in the beginning.

  7. I have a feeling that I'm calculating the average into V(S_t) incorrectly because I origianlly thought that you could even omit the V(S_t) step totally from the algorithm, and only afterwards compute for a separate 2D array V[r,c] for each state get the sum of the appropriate list elements (accessed from the dict), and divide that sum by the amount of episodes that you ran???

But I don't suddently know how to implement the first visit check in the algorithm. Like, I literally don't understand what it is actually checking for.

And furthermore I don't understand how the empirical mean is now supposed to be calculates in the monte carlo algorithm where there is the V(s_t) = average( Returns(S_t) )

I will also post my python code thusfar.

import numpy as np
import numpy.linalg as LA
import random

# YOUR CODE



rows_count = 4
columns_count = 4
V = np.zeros((rows_count, columns_count))
reward = -1 #probably not needed
directions = ['up', 'right', 'down', 'left'] #probably not needed
maxiters = 10000
eps = 0.0000001
k = 0 # "memory counter" of iterations inside the for loop, note that for loop i-variable is regular loop variable

rows = 4
cols = 4

#stepsMatrix = np.zeros((rows_count, columns_count)) 





def isTerminal(r,c):      #helper function to check if terminal state or regular state
    global rows_count, columns_count
    if r == 0 and c == 0: #im a bit too lazy to check otherwise the iteration boundaries        
        return True       #so that this helper function is a quick way to exclude computations
    if r == rows_count-1 and c == columns_count-1:
        return True
    return False

def getValue(row, col):    #helper func, get state value
    global V
    if row == -1: row =0   #if you bump into wall, you bounce back
    elif row == 4: row = 3
    if col == -1: col = 0
    elif col == 4: col =3

    return V[row,col]

def getState(row,col):
    if row == -1: row =0   #helper func for the exercise:1
    elif row == 4: row = 3
    if col == -1: col = 0
    elif col == 4: col =3
    return row, col


def makeEpisode(r,c):  #helper func for the exercise:1
## return the count of steps ??
#by definition, you should always start from non-terminal state, so
#by minimum, you need at least one action to get to terminal state
    stateWasTerm = False
    stepsTaken = 0
    curR = r
    curC = c
    while not stateWasTerm:

        act = random.randint(0,3)
        if act == 0: ##up
            curR-=1
        elif act == 1: ##right
            curC+=1
        elif act == 2: ## down
            curR+=1
        else:##left
            curC-=1
        stepsTaken +=1
        curR,curC = getState(curR,curC)
        stateWasTerm = isTerminal(curR,curC)
    return stepsTaken


V = np.zeros((rows_count, columns_count))
episodeCount = 100
reward = -1
y = 1.0 #the gamma discount rate


#use dictionary where key is stateTuple, 
#and value is stateReturnsList
#after algorithm for monte carlo policy eval is done, 
#we can update the dict into good format for printing
#and use numpy matrix
returnsDict={} 
for r in range(4):
    for c in range(4):
        returnsDict[(r,c)]=[]





#"""first-visit montecarlo episode generation returns the episodelist"""
def firstMCEpisode(r,c):
    global reward
    stateWasTerm = False
    stepsTaken = 0
    curR = r
    curC = c
    episodeList=[  ]

    while not stateWasTerm:

        act = random.randint(0,3)
        if act == 0: ##up
            r-=1
            act="U"
        elif act == 1: ##right
            c+=1
            act="R"
        elif act == 2: ## down
            r+=1
            act="D"
        else:##left
            c-=1
            act="L"
        stepsTaken +=1

        r,c = getState(r,c)
        stateWasTerm = isTerminal(r,c)
        episodeList.append( ((curR,curC), act, reward) )
        if not stateWasTerm:

            curR = r
            curC = c


    return episodeList


kakka=0 #for debug breakpoints only!
#first-visit Monte Carlo with fixed starting state in the s(1,1) state
for n in range(1, episodeCount+1):

    epList = firstMCEpisode(1,1)
    G = 0
    for t in reversed( range( len(epList) )):
        G = y*G + reward #NOTE! reward is always same -1
        S_t = epList[t][0] #get the state only, from tuple

        willAppend = True
        for j in range(t-1):
            tmp = epList[j][0]
            if( tmp == S_t ):
                willAppend =False
                break
        if(willAppend):
            returnsDict[S_t].append(G)
            t_r = S_t[0] #tempRow from S_t
            t_c =S_t[1] #tempCol from S_t
            V[t_r, t_c] = sum( returnsDict[S_t] ) / n


kakka = 3 #for debug breakpoints only!
print(V)