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

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)

• See: ai.stackexchange.com/a/10818/2444. Maybe this is a duplicate of it. – nbro Apr 12 '19 at 17:25
• apparently I calculated the value function average in a wrong way... apparently I am required to keep some kind of N(S_t) datastructure, maybe a dict where the key is the each particular state such as (row,col) and the value is the amount of times that state has been visited to overall across all episodes??? Or do I even need to have that N(S_t datastructure, can I just calculate the V(S_t) for each state such that I calculate the sumOfElements from each list of respective state, divided by that listAmountOfElements??? – Late347 Apr 12 '19 at 17:44
• because isnt it so... that if I have dictionary where key is (row,col) for each state, and the value is the list of returns for that state... then the amount of elements in each list, is the amount of times that each state was visited? – Late347 Apr 12 '19 at 17:45
• also, a new question, are you supposed to start always in the same fixed starting state in this Monte Carlo policy evaluation part? will it distort the algorithm from converging to the actual value function for that policy (equiprobable randomwalk), as long as you have run maybe 100k iterations ( iterations == episodes) – Late347 Apr 12 '19 at 17:55
• I got the every-visit Monte Carlo done, but I didn't fully understand how to make the checking for first-visit MC, and from what sequience exactly do you check the existence of currently iterated state S_t ??? what is the ending limit that is included in the first-visit check iteration? – Late347 Apr 12 '19 at 19:43