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.

enter image description here

  • 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


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
        elif act == 1: ##right
        elif act == 2: ## down
        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
for r in range(4):
    for c in range(4):

#"""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
        elif act == 1: ##right
        elif act == 2: ## down
        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
            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!
  • 1
    $\begingroup$ See: ai.stackexchange.com/a/10818/2444. Maybe this is a duplicate of it. $\endgroup$
    – nbro
    Apr 12, 2019 at 17:25
  • $\begingroup$ 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??? $\endgroup$
    – Late347
    Apr 12, 2019 at 17:44
  • $\begingroup$ 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? $\endgroup$
    – Late347
    Apr 12, 2019 at 17:45
  • $\begingroup$ 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) $\endgroup$
    – Late347
    Apr 12, 2019 at 17:55
  • $\begingroup$ 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? $\endgroup$
    – Late347
    Apr 12, 2019 at 19:43


You must log in to answer this question.