Body: <p>I've been trying to read Sutton &amp; 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)</p>
  
  <p>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.</p>
  
  <p><a href="https://i.sstatic.net/MAJZ8.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/MAJZ8.png" alt="enter image description here"></a></p>
  
  <ul>
  <li>My setting is a 4x4 gridworld where reward is always -1. </li>
  <li>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. </li>
  <li>Discount rate will be 1.0 (no discounting). </li>
  <li><p>Terminal states should be two of them, (0,0) and (3,3) at the corners.</p>
  
  <ol>
  <li><p>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.</p></li>
  <li><p>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. </p></li>
  <li><p>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 )]</p></li>
  <li><p>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...</p></li>
  <li><p>G can be updated as described in pseudocode.</p></li>
  <li><p>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.</p></li>
  <li><p>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???</p></li>
  </ol></li>
  </ul>
  
  <p>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.</p>
  
  <p>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) )</p>
  
  <p>I will also post my python code thusfar.</p>
  
  <pre><code>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)
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-12T17:25:45.473Z
Comments.Text: See: https://ai.stackexchange.com/a/10818/2444. Maybe this is a duplicate of it.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-12T17:44:08.163Z
Comments.Text: 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???
Comments.UserDisplayName: Late347
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-12T17:45:57.500Z
Comments.Text: 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?
Comments.UserDisplayName: Late347
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-12T17:55:27.503Z
Comments.Text: 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)
Comments.UserDisplayName: Late347
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-12T19:43:36.897Z
Comments.Text: 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?
Comments.UserDisplayName: Late347
Tags: <reinforcement-learning><monte-carlo-methods><policy-evaluation>
Title: Difficulty understanding Monte Carlo policy evaluation (state-value) for gridworld
UserDisplayName: Late347
ThreadText: # Difficulty understanding Monte Carlo policy evaluation (state-value) for gridworld
  
  (Asked by: username_0 on 2019-04-12)
  
  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.
  
  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.
  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. 
  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 )]
  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...
  G can be updated as described in pseudocode.
  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.
  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)
  
  **Tags:** reinforcement-learning, monte-carlo-methods, policy-evaluation
  > **Comments:**
  > **username_1**: See: https://ai.stackexchange.com/a/10818/2444. Maybe this is a duplicate of it.  
  > **username_0**: 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???  
  > **username_0**: 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?  
  > **username_0**: 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)  
  > **username_0**: 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?  
  
  ---
  
  ## 0 answers
  
  