Answers.Body: <p>Your implementation of Monte Carlo Exploring Starts algorithm appears to be working as designed. This is a problem that can occur with some deterministic policies in the gridworld environment. </p>
  
  <p>It is possible for your policy improvement step to generate such a policy, and there is no recovery from this built into the algorithm. First visit and every visit variants will converge differently to the true action values, however neither offers an improvement here. It is most likely that your loops are occurring via state/action pairs that did not occur in the first episode, so the value estimates are default 0, which then looks like the best choice when creating the deterministic policy*.</p>
  
  <p>In Sutton &amp; Barto to demonstrate Monte Carlo ES, the authors choose an environment where such loops are impossible (a simplified Blackjack game). They then quickly move on to removing the need for exploring starts by using <span class="math-container">$\epsilon$</span>-greedy policies. So this issue is not covered in detail, although there are assertions in a couple of places that it must be possible to complete episodes.</p>
  
  <p>To resolve this whilst still using Monte Carlo ES, you will need to alter the environment so that such loops are not possible. The simplest change is to terminate the episode if it gets too long. This is hacky, because done simply on the gridworld it violates the Markov property (because now the time step should technically be part of the state if you want to predict value). However, it will get you out of the immediate problem, and provided you set the termination point high enough - e.g. 100 steps for your small gridworld - the agent should still discover the optimal policy and associated action values.</p>
  
  <p>This "timeout" patch is also used by many OpenAI Gym environments, because although most other algorithms can find their way out of infinite loops like this, they can still suffer slow learning from over-long episodes as a result.</p>
  
  <hr>
  
  <p>* This leads to a possible fix of initialising your Q values pessimistically - e.g. with -50 starting value. That should help the first deterministic policy join up to the terminal state - although if you make it <em>strictly</em> deterministic and resolve value ties deterministically too, then even this may not be enough. You might want to give that a try to verify what I am saying here, although I would recommend the timeout hack instead, as that is a more general solution. Pessimistic start values are bad for exploration when using other algorithms.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-19T09:35:40.990Z
Answers.Text: I managed to make "a hacky fix". The issue appears to have resolved itself in usual cases if I let the algorithm explore the gridworld in the beginning with equiprobable randomwalk. Then, after having run some 500 first iterations, then only I start updating the  policy. So the early iterations are still gathering data into the returnsDict and Qdict, but the algorithm is delaying the updating of the policy until it has explored a bit in the beginning, with the randomwalk policy. It seems to get it "over the hump", because there is guaranteed iterations for all state-action pairs being visited
Answers.UserDisplayName: Late347
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-19T09:41:33.487Z
Answers.Text: @Late347: Yes I expect that will work well. It may still be possible to estimate values that result in a loop that way (such as an infinite to-and-fro between two states), but I would guess even if it is possible, that it is very unlikely.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-19T19:30:24.177Z
Answers.Text: Neil, if you feel a need to edit the question to make the Q&A more useful, please feel free.
Answers.UserDisplayName: DukeZhou
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-19T08:55:33.980Z
Answers.LastActivityDate: 2019-04-19T09:13:26.187Z
Answers.LastEditDate: 2019-04-19T09:13:26.187Z
Answers.UserDisplayName: Neil Slater
Body: <p>I've been trying to implement policy improvement for Q(s,a) function as per Sutton&amp;Barto reinforcement learning book. The original algorithm with first-visit MonteCarlo is pictured below.</p>
  
  <p><a href="https://i.sstatic.net/ODu0o.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ODu0o.png" alt="enter image description here"></a></p>
  
  <p>I remember the book earlier mentioning that the every-visit variation simply omits the first-visit check "unless the pair blah,blah..." but otherwise the algorithms should be the same (???)</p>
  
  <p>Initial policy in the very first iteration (first episode), should be equiprobable randomwalk. In general terms, if action takes you outside the border of the gridworld (4x4), then you simply bounce back into where you started from, but reward will have been given, and action will have been taken.</p>
  
  <p>I have verified that my code gets stuck (sometimes) in the episode generation portion of my code in foreverloop for some reason, early on in the code (iterations amount in the outerloop is small). Even though, I thought I followed the pseudocode rather well, but it's really annoying that sometimes the code gets stuck in foreverloop.</p>
  
  <p>The reason must be that for some reason my code updates from the equiprobable randomwalk policy => into deterministic policy but in a wrong way, such that it can create foreverloops in the episode generation after the first episode has ran (it must have ran the entire first episode with equiprobable randomwalk). The below picture shows that if you get into any state in the marked box, you cannot get out from there and get stuck in episode generation...
  <a href="https://i.sstatic.net/ID7Qn.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ID7Qn.png" alt="enter image description here"></a></p>
  
  <p>If the random generator seed it lucky, then it can usually get "over the hump" and proceed to make the required number of iterations in the outerloop, and output an optimal policy for the gridworld.</p>
  
  <p>Here is the python code (from my experience I ran it in debugger and had to restart it a couple of times, but usually it will show quite fast that it gets stuck into the episode generation, and cannot proceed in the iterations in outerloop.</p>
  
  <pre><code>import numpy as np
  import numpy.linalg as LA
  import random
  from datetime import datetime
  
  random.seed(datetime.now())
  rows_count = 4
  columns_count = 4
  
  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
  
  
  maxiters = 100000
  reward = -1
  actions = ["U", "R", "D", "L"]
  V = np.zeros((rows_count, columns_count))
  returnsDict={}
  QDict={}
  actDict={0:"U",1:"R",2:"D",3:"L"}
  policies = np.array([ ['T','A','A','A'],
                       ['A','A','A','A'],
                       ['A','A','A','A'],
                       ['A','A','A','T'] ])
  
  
  
  
  
  """returnsDict, for each state-action pair, maintain (mean,visitedCount)"""
  for r in range(rows_count):
      for c in range(columns_count):
          if not isTerminal(r, c):
              for act in actions:
                  returnsDict[ ((r, c), act) ] = [0, 0] ## Maintain Mean, and VisitedCount for each state-action pair
  
  
  
  """ Qfunc, we maintain the action-value for each state-action pair"""
  for r in range(rows_count):
      for c in range(columns_count):
          if not isTerminal(r, c):
              for act in actions:
                  QDict[ ((r,c), act) ] = -9999  ## Maintain Q function value for each state-action pair
  
  
  
  
  
  
  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 getRandomStartState():
      illegalState = True
  
      while illegalState:
          r = random.randint(0, 3)
          c = random.randint(0, 3)
          if (r == 0 and c == 0) or (r == 3 and c == 3):
              illegalState = True
          else:
              illegalState = False
      return r, c
  
  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 getRandomAction():
      global actDict
      return actDict[random.randint(0, 3)]
  
  
  def getMeanFromReturns(oldMean, n, curVal):
      newMean = 0
      if n == 0:
          raise Exception('Exception, incrementalMeanFunc, n should not be less than 1')
      elif n == 1:
          return curVal
      elif n &gt;= 2:
          newMean = (float) ( oldMean + (1.0 / n) * (curVal - oldMean) )
          return newMean
  
  
  """get the best action 
  returns string action
  parameter is state tuple (r,c)"""
  def getArgmaxActQ(S_t):
      global QDict
      qvalList = []
      saList = []
  
      """for example get together
      s1a1, s1a2, s1a3, s1a4
      find which is the maxValue, and get the action which caused it"""
      sa1 = (S_t, "U")
      sa2 = (S_t, "R")
      sa3 = (S_t, "D")
      sa4 = (S_t, "L")
      saList.append(sa1)
      saList.append(sa2)
      saList.append(sa3)
      saList.append(sa4)
  
      q1 = QDict[sa1]
      q2 = QDict[sa2]
      q3 = QDict[sa3]
      q4 = QDict[sa4]
      qvalList.append(q1)
      qvalList.append(q2)
      qvalList.append(q3)
      qvalList.append(q4)
  
      maxQ = max(qvalList)
      ind_maxQ = qvalList.index(maxQ)  # gets the maxQ value and the index which caused it
  
      """when we have index of maxQval, then we know which sa-pair
      gave that maxQval =&gt; we can access that action from the correct sa-pair"""
      argmaxAct = saList[ind_maxQ][1]
      return argmaxAct
  
  """QEpisode generation func
  returns episodeList
  parameters are starting state, starting action"""
  def QEpisode(r, c, act):
      global reward
      global policies
  
      """NOTE! r,c will both be local variables inside this func
      they denote the nextState (s') in this func"""
      stateWasTerm = False
      stepsTaken = 0
      curR = r
      curC = c
      episodeList = [ ((r, c), act, reward) ]  # add the starting (s,a) immediately
  
      if act == "U":  ##up
          r -= 1
      elif act == "R":  ##right
          c += 1
      elif act == "D":  ## down
          r += 1
      else:  ##left
          c -= 1
      stepsTaken += 1
      r, c = getState(r, c)  ## check status of the newState (s')
      stateWasTerm = isTerminal(r, c)  ## if status was terminal stop iteration, else keep going into loop
  
      if not stateWasTerm:
          curR = r
          curC = c
  
      while not stateWasTerm:
          if policies[curR, curC] == "A":
              act = getRandomAction()  ## """get the random action from policy"""
          else:
              act = policies[curR, curC]  ## """get the deterministic action from policy"""
  
          if act == "U":  ## up
              r -= 1
          elif act == "R":  ## right
              c += 1
          elif act == "D":  ## down
              r += 1
          else:  ## left
              c -= 1
          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
  
  
  
  
  print("montecarlo program starting...\n")
  """ MOnte Carlo Q-function, exploring starts, every-visit, estimating Pi ~~ Pi* """
  for iteration in range(1, maxiters+1): ## for all episodes
  
      print("curIter == ", iteration)
      print("\n")
      if iteration % 20 == 0: ## get random seed periodically to improve randomness performance
          random.seed(datetime.now())
  
  
  
      for r in range(4):
          for c in range(4):
              if not isTerminal(r,c):
                  startR = r
                  startC = c
                  startAct = getRandomAction()
  
  
     ## startR, startC = getRandomStartState() ## get random starting-state, and starting action equiprobably
    ##  startAct = getRandomAction()
                  sequence = QEpisode(startR, startC, startAct)  ## generate Q-sequence following policy Pi, until terminal-state (excluding terminal)
                  G = 0
  
                  for t in reversed(range(len(sequence))): ## iterate through the timesteps in reversed order
                      S_t = sequence[t][0] ## use temp variables as helpers
                      A_t = sequence[t][1]
                      R_t = sequence[t][2]
                      G += R_t ## increment G with reward, NOTE! the gamma discount factor == 1.0
                      visitedCount = returnsDict[S_t, A_t][1] ## use temp visitedcount
                      visitedCount += 1
  
                      if visitedCount == 1: ## special case in iterative mean algorithm, the first visit to any state-action pair
                          curMean = 9999
                          curMean = getMeanFromReturns(curMean, visitedCount, G)
                          returnsDict[S_t, A_t][0] = curMean ## update mean
                          returnsDict[S_t, A_t][1] = visitedCount ## update visitedcount
                      else:
                          curMean = returnsDict[S_t, A_t][0] ## get temp mean from returnsDict
                          curMean = getMeanFromReturns(curMean, visitedCount, G) ## get the new temp mean iteratively
                          returnsDict[S_t, A_t][1] = visitedCount ## update visitedcount
                          returnsDict[S_t, A_t][0] = curMean ## update mean
  
  
                      QDict[S_t, A_t] = returnsDict[S_t, A_t][0] ## update the Qfunction with the new mean value
                      tempR = S_t[0] ## temp variables simply to disassemble the tuple into row,col
                      tempC = S_t[1]
                      policies[tempR, tempC] = getArgmaxActQ(S_t) ## update policy based on argmax_a[Q(S_t)]
  
  
  print("optimal policy with Monte-Carlo, every visit was \n")
  print("\n")
  print(policies)
  </code></pre>
  
  <p>Here is the updated "hacky fix" code that seems to get the algorithm "over the hump" without getting stuck into foreverloop with deterministic policy. My teacher had recommended that you don't need to update policy at every step in this kind of Monte Carlo, so you could have made the policy updates at periodic intervals using python's modulo operator on the iterationsCount or something.
  Also, I had the bright idea that the Sutton&amp;Barto book described that all state-action pairs must be visited, very large amount of times, for the exploring starts pre-condition of the algorithm to be fulfilled.</p>
  
  <p>So, I then decided to enforce the algorithm to have run at least once for all state-action pairs so you start from each state-action pair deterministically one-by-one (for each episode actually). This would still be run with the old randomwalk policy in this early exploration phase, where we are gathering data into the returnsDict, and Qdict, but not yet improving deterministic policy.</p>
  
  <pre><code>import numpy as np
  import numpy.linalg as LA
  import random
  from datetime import datetime
  
  random.seed(datetime.now())
  rows_count = 4
  columns_count = 4
  
  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
  
  
  
  """NOTE about maxiters!!!
  the Monte-Carlo every visit algorithm implements total amount of iterations with formula
  totalIters = maxiters * nonTerminalStates * possibleActions
  totalIters = 5000 * 14 * 4
  totalIters = 280000
  
  in other words, there will be 5k iterations per each state-action pair
  in other words there will be an early exploration phase where policy willnot be updated,
  but the gridworld will be explored with randomwalk policy, gathering Qfunc information, 
  and returnDict information.
  
  in early phase there will be about 27 iterations for each state-action pair during,
  non-policy-updating exploration 
  (maxiters * explorationFactor) / (stateACtionPairs) = 7500 *0.2 /56
  
  after that early exploring with randomwalk,
  then we act greedily w.r.t. the Q-function, 
  for the rest of the iterations to get the optimal deterministic policy
  """
  maxiters = 7500
  explorationFactor = 0.2 ## explore that percentage of the first maxiters rounds, try to increase it, if you get stuck in foreverloop, in QEpisode function
  reward = -1
  actions = ["U", "R", "D", "L"]
  V = np.zeros((rows_count, columns_count))
  returnsDict={}
  QDict={}
  actDict={0:"U",1:"R",2:"D",3:"L"}
  policies = np.array([ ['T','A','A','A'],
                       ['A','A','A','A'],
                       ['A','A','A','A'],
                       ['A','A','A','T'] ])
  
  
  
  
  
  """returnsDict, for each state-action pair, maintain (mean,visitedCount)"""
  for r in range(rows_count):
      for c in range(columns_count):
          if not isTerminal(r, c):
              for act in actions:
                  returnsDict[ ((r, c), act) ] = [0, 0] ## Maintain Mean, and VisitedCount for each state-action pair
  
  
  
  """ Qfunc, we maintain the action-value for each state-action pair"""
  for r in range(rows_count):
      for c in range(columns_count):
          if not isTerminal(r, c):
              for act in actions:
                  QDict[ ((r,c), act) ] = -9999  ## Maintain Q function value for each state-action pair
  
  
  
  
  
  
  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 getRandomStartState():
      illegalState = True
  
      while illegalState:
          r = random.randint(0, 3)
          c = random.randint(0, 3)
          if (r == 0 and c == 0) or (r == 3 and c == 3):
              illegalState = True
          else:
              illegalState = False
      return r, c
  
  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 getRandomAction():
      global actDict
      return actDict[random.randint(0, 3)]
  
  
  def getMeanFromReturns(oldMean, n, curVal):
      newMean = 0
      if n == 0:
          raise Exception('Exception, incrementalMeanFunc, n should not be less than 1\n')
      elif n == 1:
          return curVal
      elif n &gt;= 2:
          newMean = (float) ( oldMean + (1.0 / n) * (curVal - oldMean) )
          return newMean
  
  
  """get the best action 
  returns string action
  parameter is state tuple (r,c)"""
  def getArgmaxActQ(S_t):
      global QDict
      qvalList = []
      saList = []
  
      """for example get together
      s1a1, s1a2, s1a3, s1a4
      find which is the maxValue, and get the action which caused it"""
      sa1 = (S_t, "U")
      sa2 = (S_t, "R")
      sa3 = (S_t, "D")
      sa4 = (S_t, "L")
      saList.append(sa1)
      saList.append(sa2)
      saList.append(sa3)
      saList.append(sa4)
  
      q1 = QDict[sa1]
      q2 = QDict[sa2]
      q3 = QDict[sa3]
      q4 = QDict[sa4]
      qvalList.append(q1)
      qvalList.append(q2)
      qvalList.append(q3)
      qvalList.append(q4)
  
      maxQ = max(qvalList)
      ind_maxQ = qvalList.index(maxQ)  # gets the maxQ value and the index which caused it
  
      """when we have index of maxQval, then we know which sa-pair
      gave that maxQval =&gt; we can access that action from the correct sa-pair"""
      argmaxAct = saList[ind_maxQ][1]
      return argmaxAct
  
  
  
  
  """QEpisode generation func
  returns episodeList
  parameters are starting state, starting action"""
  def QEpisode(r, c, act):
  
      """ideally, we should not get stuck in the gridworld...but,
      but sometiems when policy transitions from the first episode's policy == randomwalk,
      then, on second episode sometimes we get stuck in foreverloop in episode generation
      usually the only choice then seems to restart the entire policy into randomwalk ??? """
  
      global reward
      global policies
  
      """NOTE! r,c will both be local variables inside this func
      they denote the nextState (s') in this func"""
      stepsTaken = 0
      curR = r
      curC = c
      episodeList = [ ((r, c), act, reward) ]  # add the starting (s,a) immediately
  
      if act == "U":  ##up
          r -= 1
      elif act == "R":  ##right
          c += 1
      elif act == "D":  ## down
          r += 1
      elif act == "L":  ##left
          c -= 1
      stepsTaken += 1
      r, c = getState(r, c)  ## check status of the newState (s')
      stateWasTerm = isTerminal(r, c)  ## if status was terminal stop iteration, else keep going into loop
  
      if not stateWasTerm:
          curR = r
          curC = c
  
      while not stateWasTerm:
          if policies[curR, curC] == "A":
              act = getRandomAction()  ## """get the random action from policy"""
          else:
              act = policies[curR, curC]  ## """get the deterministic action from policy"""
  
          if act == "U":  ## up
              r -= 1
          elif act == "R":  ## right
              c += 1
          elif act == "D":  ## down
              r += 1
          else:  ## left
              c -= 1
          stepsTaken += 1
  
          r, c = getState(r, c)
          stateWasTerm = isTerminal(r, c)
          episodeList.append( ((curR, curC), act, reward) )
          if not stateWasTerm:
              curR = r
              curC = c
          if stepsTaken &gt;= 100000:
              raise Exception("Exception raised, because program got stuck in MC Qepisode generation...\n")
  
  
      return episodeList
  
  
  
  
  print("montecarlo program starting...\n")
  """ MOnte Carlo Q-function, exploring starts, every-visit, estimating Pi ~~ Pi* """
  
  """It appears that the Qfunction apparently can be unreliable in the early episodes rounds, so we can avoid getting 
  stuck in foreverloop because of unreliable early episodes, BUT...
  
  we gotta delay updating the policy, until we have explored enough for a little bit...
  so our Qfunction has reliable info inside of it, to base the decision on, later..."""
  Q_function_is_reliable = False ## variable shows if we are currently updating the policy, or just improving Q-function and exploring
  
  
  for iteration in range(1, maxiters+1): ## for all episodes
  
      print("curIter == ", iteration, ", QfunctionIsReliable == ", Q_function_is_reliable )
      print("\n")
      if iteration % 20 == 0: ## get random seed periodically to improve randomness performance
          random.seed(datetime.now())
  
      for r in range(4):  ## for every non-terminal-state
          for c in range(4):
              if not isTerminal(r,c):
                  startR = r
                  startC = c
                  for act in actions: ## for every action possible
                      startAct = act
                      sequence = QEpisode(startR, startC, startAct)  ## generate Q-sequence following policy Pi, until terminal-state (excluding terminal)
                      G = 0
  
                      for t in reversed(range(len(sequence))): ## iterate through the timesteps in reversed order
                          S_t = sequence[t][0] ## use temp variables as helpers
                          A_t = sequence[t][1]
                          R_t = sequence[t][2]
                          G += R_t ## increment G with reward, gamma discount factor is zero
                          visitedCount = returnsDict[S_t, A_t][1]
                          visitedCount += 1
  
                         ## if (S_t, A_t, -1) not in sequence[:t]: ## This is how you COULD have done the first-visit MC, but we do every-visit now...
                          if visitedCount == 1: ## special case in iterative mean algorithm, the first visit to any state-action pair
                              curMean = 9999
                              curMean = getMeanFromReturns(curMean, visitedCount, G)
                              returnsDict[S_t, A_t][0] = curMean ## update mean
                              returnsDict[S_t, A_t][1] = visitedCount ## update visitedcount
                          else:
                              curMean = returnsDict[S_t, A_t][0] ## get temp mean from returnsDict
                              curMean = getMeanFromReturns(curMean, visitedCount, G) ## get the new temp mean iteratively
                              returnsDict[S_t, A_t][1] = visitedCount ## update visitedcount
                              returnsDict[S_t, A_t][0] = curMean ## update mean
  
  
                          QDict[S_t, A_t] = returnsDict[S_t, A_t][0] ## update the Qfunction with the new mean value
                          tempR = S_t[0] ## temp variables simply to disassemble the tuple into row,col
                          tempC = S_t[1]
  
                          if iteration &gt;= round(maxiters * explorationFactor): ## ONLY START UPDATING POLICY when we have reliable estimates for Qfunction, that is when iteration &gt; maxiter/10
                              Q_function_is_reliable = True
                              policies[tempR, tempC] = getArgmaxActQ(S_t) ## update policy based on argmax_a[Q(S_t)]
  
  
  print("optimal policy with Monte-Carlo, every visit was \n")
  print("\n")
  print(policies)
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-19T08:38:56.980Z
Comments.Text: Actually here I don't think we need the code - perhaps you could link it from the question. That's because the algorithm is performing as designed. You *might* have errors or bugs in your code, but they are not related to this problem.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-19T09:44:53.687Z
Comments.Text: You have added even more code? I recommend (1) Not having the code here, but linking it. (2) Don't edit the question to post a solution into it, because it invalidates other answers (i.e. mine in this case). If you want to post your own answer with how you resolved the problem, please do so.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-19T19:29:37.917Z
Comments.Text: Welcome to SE:AI.  I highly recommend taking Neil's advice.  (I'm leaving the question open provisionally, but I have to advise you that without edits, it will likely be closed by the community.)
Comments.UserDisplayName: DukeZhou
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-20T10:50:47.513Z
Comments.Text: I could put the two code snippets as Github GISTs, and link them - also make the update into a community Wiki answer. Late347, it would be better if you did this, but if you cannot be bothered, then is it OK if I do so?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-20T11:46:02.310Z
Comments.Text: Im fine with putting the code snippets to somewhere where people can access them. I was initially confused about this "hostile response" for my post ! sorry if I made a mistake... I've gotten used to the the idea that especially on stack overflow you definitely are allowed to post code in-line. And I remembered from some other stack exchange that you were supposed to edit your own answer rather than make a new answer, if you wanted to highlight something or add more information. I remembered from math stack exchange that you were allowed to ask multiple things in the same question post.
Comments.UserDisplayName: Late347
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-20T20:59:03.723Z
Comments.Text: Sorry I am not trying to be hostile, just trying to get the question into a form suitable for the site. You have misunderstood some things. Especially regarding editing the question. It is OK to add clarifying details, and in fact desirable. It is not OK to answer a question inside the question, and considered bad form to change the question radically after receiving a suitable answer. There is a separate Answer section for answering, and you are welcome to answer your own question there. Regarding the code, it is not adding anything to this specific question and IMO gets in the way.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-03T16:38:55.097Z
Comments.Text: excuse me, I have a naive question for this code. Actually I need to change the matrix you use to a one dimensional array, and when the agent reach the target, it will get a additional reward like 10 or 20. Could you please tell me how can I make the adjustment based on your code? That will help me a lot!
Comments.UserDisplayName: may
Tags: <python><monte-carlo-methods>
Title: Monte-Carlo, every-visit gridworld, exploring starts, python code gets stuck in foreverloop in episode generation
UserDisplayName: Late347
ThreadText: # Monte-Carlo, every-visit gridworld, exploring starts, python code gets stuck in foreverloop in episode generation
  
  (Asked by: username_0 on 2019-04-18)
  
  I've been trying to implement policy improvement for Q(s,a) function as per Sutton&Barto reinforcement learning book. The original algorithm with first-visit MonteCarlo is pictured below.
  
  I remember the book earlier mentioning that the every-visit variation simply omits the first-visit check "unless the pair blah,blah..." but otherwise the algorithms should be the same (???)
  Initial policy in the very first iteration (first episode), should be equiprobable randomwalk. In general terms, if action takes you outside the border of the gridworld (4x4), then you simply bounce back into where you started from, but reward will have been given, and action will have been taken.
  I have verified that my code gets stuck (sometimes) in the episode generation portion of my code in foreverloop for some reason, early on in the code (iterations amount in the outerloop is small). Even though, I thought I followed the pseudocode rather well, but it's really annoying that sometimes the code gets stuck in foreverloop.
  The reason must be that for some reason my code updates from the equiprobable randomwalk policy => into deterministic policy but in a wrong way, such that it can create foreverloops in the episode generation after the first episode has ran (it must have ran the entire first episode with equiprobable randomwalk). The below picture shows that if you get into any state in the marked box, you cannot get out from there and get stuck in episode generation...
  
  If the random generator seed it lucky, then it can usually get "over the hump" and proceed to make the required number of iterations in the outerloop, and output an optimal policy for the gridworld.
  Here is the python code (from my experience I ran it in debugger and had to restart it a couple of times, but usually it will show quite fast that it gets stuck into the episode generation, and cannot proceed in the iterations in outerloop.
  import numpy as np
  import numpy.linalg as LA
  import random
  from datetime import datetime
  
  random.seed(datetime.now())
  rows_count = 4
  columns_count = 4
  
  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
  
  
  maxiters = 100000
  reward = -1
  actions = ["U", "R", "D", "L"]
  V = np.zeros((rows_count, columns_count))
  returnsDict={}
  QDict={}
  actDict={0:"U",1:"R",2:"D",3:"L"}
  policies = np.array([ ['T','A','A','A'],
                       ['A','A','A','A'],
                       ['A','A','A','A'],
                       ['A','A','A','T'] ])
  
  
  
  
  
  """returnsDict, for each state-action pair, maintain (mean,visitedCount)"""
  for r in range(rows_count):
      for c in range(columns_count):
          if not isTerminal(r, c):
              for act in actions:
                  returnsDict[ ((r, c), act) ] = [0, 0] ## Maintain Mean, and VisitedCount for each state-action pair
  
  
  
  """ Qfunc, we maintain the action-value for each state-action pair"""
  for r in range(rows_count):
      for c in range(columns_count):
          if not isTerminal(r, c):
              for act in actions:
                  QDict[ ((r,c), act) ] = -9999  ## Maintain Q function value for each state-action pair
  
  
  
  
  
  
  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 getRandomStartState():
      illegalState = True
  
      while illegalState:
          r = random.randint(0, 3)
          c = random.randint(0, 3)
          if (r == 0 and c == 0) or (r == 3 and c == 3):
              illegalState = True
          else:
              illegalState = False
      return r, c
  
  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 getRandomAction():
      global actDict
      return actDict[random.randint(0, 3)]
  
  
  def getMeanFromReturns(oldMean, n, curVal):
      newMean = 0
      if n == 0:
          raise Exception('Exception, incrementalMeanFunc, n should not be less than 1')
      elif n == 1:
          return curVal
      elif n >= 2:
          newMean = (float) ( oldMean + (1.0 / n) * (curVal - oldMean) )
          return newMean
  
  
  """get the best action 
  returns string action
  parameter is state tuple (r,c)"""
  def getArgmaxActQ(S_t):
      global QDict
      qvalList = []
      saList = []
  
      """for example get together
      s1a1, s1a2, s1a3, s1a4
      find which is the maxValue, and get the action which caused it"""
      sa1 = (S_t, "U")
      sa2 = (S_t, "R")
      sa3 = (S_t, "D")
      sa4 = (S_t, "L")
      saList.append(sa1)
      saList.append(sa2)
      saList.append(sa3)
      saList.append(sa4)
  
      q1 = QDict[sa1]
      q2 = QDict[sa2]
      q3 = QDict[sa3]
      q4 = QDict[sa4]
      qvalList.append(q1)
      qvalList.append(q2)
      qvalList.append(q3)
      qvalList.append(q4)
  
      maxQ = max(qvalList)
      ind_maxQ = qvalList.index(maxQ)  # gets the maxQ value and the index which caused it
  
      """when we have index of maxQval, then we know which sa-pair
      gave that maxQval => we can access that action from the correct sa-pair"""
      argmaxAct = saList[ind_maxQ][1]
      return argmaxAct
  
  """QEpisode generation func
  returns episodeList
  parameters are starting state, starting action"""
  def QEpisode(r, c, act):
      global reward
      global policies
  
      """NOTE! r,c will both be local variables inside this func
      they denote the nextState (s') in this func"""
      stateWasTerm = False
      stepsTaken = 0
      curR = r
      curC = c
      episodeList = [ ((r, c), act, reward) ]  # add the starting (s,a) immediately
  
      if act == "U":  ##up
          r -= 1
      elif act == "R":  ##right
          c += 1
      elif act == "D":  ## down
          r += 1
      else:  ##left
          c -= 1
      stepsTaken += 1
      r, c = getState(r, c)  ## check status of the newState (s')
      stateWasTerm = isTerminal(r, c)  ## if status was terminal stop iteration, else keep going into loop
  
      if not stateWasTerm:
          curR = r
          curC = c
  
      while not stateWasTerm:
          if policies[curR, curC] == "A":
              act = getRandomAction()  ## """get the random action from policy"""
          else:
              act = policies[curR, curC]  ## """get the deterministic action from policy"""
  
          if act == "U":  ## up
              r -= 1
          elif act == "R":  ## right
              c += 1
          elif act == "D":  ## down
              r += 1
          else:  ## left
              c -= 1
          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
  
  
  
  
  print("montecarlo program starting...\n")
  """ MOnte Carlo Q-function, exploring starts, every-visit, estimating Pi ~~ Pi* """
  for iteration in range(1, maxiters+1): ## for all episodes
  
      print("curIter == ", iteration)
      print("\n")
      if iteration % 20 == 0: ## get random seed periodically to improve randomness performance
          random.seed(datetime.now())
  
  
  
      for r in range(4):
          for c in range(4):
              if not isTerminal(r,c):
                  startR = r
                  startC = c
                  startAct = getRandomAction()
  
  
     ## startR, startC = getRandomStartState() ## get random starting-state, and starting action equiprobably
    ##  startAct = getRandomAction()
                  sequence = QEpisode(startR, startC, startAct)  ## generate Q-sequence following policy Pi, until terminal-state (excluding terminal)
                  G = 0
  
                  for t in reversed(range(len(sequence))): ## iterate through the timesteps in reversed order
                      S_t = sequence[t][0] ## use temp variables as helpers
                      A_t = sequence[t][1]
                      R_t = sequence[t][2]
                      G += R_t ## increment G with reward, NOTE! the gamma discount factor == 1.0
                      visitedCount = returnsDict[S_t, A_t][1] ## use temp visitedcount
                      visitedCount += 1
  
                      if visitedCount == 1: ## special case in iterative mean algorithm, the first visit to any state-action pair
                          curMean = 9999
                          curMean = getMeanFromReturns(curMean, visitedCount, G)
                          returnsDict[S_t, A_t][0] = curMean ## update mean
                          returnsDict[S_t, A_t][1] = visitedCount ## update visitedcount
                      else:
                          curMean = returnsDict[S_t, A_t][0] ## get temp mean from returnsDict
                          curMean = getMeanFromReturns(curMean, visitedCount, G) ## get the new temp mean iteratively
                          returnsDict[S_t, A_t][1] = visitedCount ## update visitedcount
                          returnsDict[S_t, A_t][0] = curMean ## update mean
  
  
                      QDict[S_t, A_t] = returnsDict[S_t, A_t][0] ## update the Qfunction with the new mean value
                      tempR = S_t[0] ## temp variables simply to disassemble the tuple into row,col
                      tempC = S_t[1]
                      policies[tempR, tempC] = getArgmaxActQ(S_t) ## update policy based on argmax_a[Q(S_t)]
  
  
  print("optimal policy with Monte-Carlo, every visit was \n")
  print("\n")
  print(policies)
  
  Here is the updated "hacky fix" code that seems to get the algorithm "over the hump" without getting stuck into foreverloop with deterministic policy. My teacher had recommended that you don't need to update policy at every step in this kind of Monte Carlo, so you could have made the policy updates at periodic intervals using python's modulo operator on the iterationsCount or something.
  Also, I had the bright idea that the Sutton&Barto book described that all state-action pairs must be visited, very large amount of times, for the exploring starts pre-condition of the algorithm to be fulfilled.
  So, I then decided to enforce the algorithm to have run at least once for all state-action pairs so you start from each state-action pair deterministically one-by-one (for each episode actually). This would still be run with the old randomwalk policy in this early exploration phase, where we are gathering data into the returnsDict, and Qdict, but not yet improving deterministic policy.
  import numpy as np
  import numpy.linalg as LA
  import random
  from datetime import datetime
  
  random.seed(datetime.now())
  rows_count = 4
  columns_count = 4
  
  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
  
  
  
  """NOTE about maxiters!!!
  the Monte-Carlo every visit algorithm implements total amount of iterations with formula
  totalIters = maxiters * nonTerminalStates * possibleActions
  totalIters = 5000 * 14 * 4
  totalIters = 280000
  
  in other words, there will be 5k iterations per each state-action pair
  in other words there will be an early exploration phase where policy willnot be updated,
  but the gridworld will be explored with randomwalk policy, gathering Qfunc information, 
  and returnDict information.
  
  in early phase there will be about 27 iterations for each state-action pair during,
  non-policy-updating exploration 
  (maxiters * explorationFactor) / (stateACtionPairs) = 7500 *0.2 /56
  
  after that early exploring with randomwalk,
  then we act greedily w.r.t. the Q-function, 
  for the rest of the iterations to get the optimal deterministic policy
  """
  maxiters = 7500
  explorationFactor = 0.2 ## explore that percentage of the first maxiters rounds, try to increase it, if you get stuck in foreverloop, in QEpisode function
  reward = -1
  actions = ["U", "R", "D", "L"]
  V = np.zeros((rows_count, columns_count))
  returnsDict={}
  QDict={}
  actDict={0:"U",1:"R",2:"D",3:"L"}
  policies = np.array([ ['T','A','A','A'],
                       ['A','A','A','A'],
                       ['A','A','A','A'],
                       ['A','A','A','T'] ])
  
  
  
  
  
  """returnsDict, for each state-action pair, maintain (mean,visitedCount)"""
  for r in range(rows_count):
      for c in range(columns_count):
          if not isTerminal(r, c):
              for act in actions:
                  returnsDict[ ((r, c), act) ] = [0, 0] ## Maintain Mean, and VisitedCount for each state-action pair
  
  
  
  """ Qfunc, we maintain the action-value for each state-action pair"""
  for r in range(rows_count):
      for c in range(columns_count):
          if not isTerminal(r, c):
              for act in actions:
                  QDict[ ((r,c), act) ] = -9999  ## Maintain Q function value for each state-action pair
  
  
  
  
  
  
  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 getRandomStartState():
      illegalState = True
  
      while illegalState:
          r = random.randint(0, 3)
          c = random.randint(0, 3)
          if (r == 0 and c == 0) or (r == 3 and c == 3):
              illegalState = True
          else:
              illegalState = False
      return r, c
  
  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 getRandomAction():
      global actDict
      return actDict[random.randint(0, 3)]
  
  
  def getMeanFromReturns(oldMean, n, curVal):
      newMean = 0
      if n == 0:
          raise Exception('Exception, incrementalMeanFunc, n should not be less than 1\n')
      elif n == 1:
          return curVal
      elif n >= 2:
          newMean = (float) ( oldMean + (1.0 / n) * (curVal - oldMean) )
          return newMean
  
  
  """get the best action 
  returns string action
  parameter is state tuple (r,c)"""
  def getArgmaxActQ(S_t):
      global QDict
      qvalList = []
      saList = []
  
      """for example get together
      s1a1, s1a2, s1a3, s1a4
      find which is the maxValue, and get the action which caused it"""
      sa1 = (S_t, "U")
      sa2 = (S_t, "R")
      sa3 = (S_t, "D")
      sa4 = (S_t, "L")
      saList.append(sa1)
      saList.append(sa2)
      saList.append(sa3)
      saList.append(sa4)
  
      q1 = QDict[sa1]
      q2 = QDict[sa2]
      q3 = QDict[sa3]
      q4 = QDict[sa4]
      qvalList.append(q1)
      qvalList.append(q2)
      qvalList.append(q3)
      qvalList.append(q4)
  
      maxQ = max(qvalList)
      ind_maxQ = qvalList.index(maxQ)  # gets the maxQ value and the index which caused it
  
      """when we have index of maxQval, then we know which sa-pair
      gave that maxQval => we can access that action from the correct sa-pair"""
      argmaxAct = saList[ind_maxQ][1]
      return argmaxAct
  
  
  
  
  """QEpisode generation func
  returns episodeList
  parameters are starting state, starting action"""
  def QEpisode(r, c, act):
  
      """ideally, we should not get stuck in the gridworld...but,
      but sometiems when policy transitions from the first episode's policy == randomwalk,
      then, on second episode sometimes we get stuck in foreverloop in episode generation
      usually the only choice then seems to restart the entire policy into randomwalk ??? """
  
      global reward
      global policies
  
      """NOTE! r,c will both be local variables inside this func
      they denote the nextState (s') in this func"""
      stepsTaken = 0
      curR = r
      curC = c
      episodeList = [ ((r, c), act, reward) ]  # add the starting (s,a) immediately
  
      if act == "U":  ##up
          r -= 1
      elif act == "R":  ##right
          c += 1
      elif act == "D":  ## down
          r += 1
      elif act == "L":  ##left
          c -= 1
      stepsTaken += 1
      r, c = getState(r, c)  ## check status of the newState (s')
      stateWasTerm = isTerminal(r, c)  ## if status was terminal stop iteration, else keep going into loop
  
      if not stateWasTerm:
          curR = r
          curC = c
  
      while not stateWasTerm:
          if policies[curR, curC] == "A":
              act = getRandomAction()  ## """get the random action from policy"""
          else:
              act = policies[curR, curC]  ## """get the deterministic action from policy"""
  
          if act == "U":  ## up
              r -= 1
          elif act == "R":  ## right
              c += 1
          elif act == "D":  ## down
              r += 1
          else:  ## left
              c -= 1
          stepsTaken += 1
  
          r, c = getState(r, c)
          stateWasTerm = isTerminal(r, c)
          episodeList.append( ((curR, curC), act, reward) )
          if not stateWasTerm:
              curR = r
              curC = c
          if stepsTaken >= 100000:
              raise Exception("Exception raised, because program got stuck in MC Qepisode generation...\n")
  
  
      return episodeList
  
  
  
  
  print("montecarlo program starting...\n")
  """ MOnte Carlo Q-function, exploring starts, every-visit, estimating Pi ~~ Pi* """
  
  """It appears that the Qfunction apparently can be unreliable in the early episodes rounds, so we can avoid getting 
  stuck in foreverloop because of unreliable early episodes, BUT...
  
  we gotta delay updating the policy, until we have explored enough for a little bit...
  so our Qfunction has reliable info inside of it, to base the decision on, later..."""
  Q_function_is_reliable = False ## variable shows if we are currently updating the policy, or just improving Q-function and exploring
  
  
  for iteration in range(1, maxiters+1): ## for all episodes
  
      print("curIter == ", iteration, ", QfunctionIsReliable == ", Q_function_is_reliable )
      print("\n")
      if iteration % 20 == 0: ## get random seed periodically to improve randomness performance
          random.seed(datetime.now())
  
      for r in range(4):  ## for every non-terminal-state
          for c in range(4):
              if not isTerminal(r,c):
                  startR = r
                  startC = c
                  for act in actions: ## for every action possible
                      startAct = act
                      sequence = QEpisode(startR, startC, startAct)  ## generate Q-sequence following policy Pi, until terminal-state (excluding terminal)
                      G = 0
  
                      for t in reversed(range(len(sequence))): ## iterate through the timesteps in reversed order
                          S_t = sequence[t][0] ## use temp variables as helpers
                          A_t = sequence[t][1]
                          R_t = sequence[t][2]
                          G += R_t ## increment G with reward, gamma discount factor is zero
                          visitedCount = returnsDict[S_t, A_t][1]
                          visitedCount += 1
  
                         ## if (S_t, A_t, -1) not in sequence[:t]: ## This is how you COULD have done the first-visit MC, but we do every-visit now...
                          if visitedCount == 1: ## special case in iterative mean algorithm, the first visit to any state-action pair
                              curMean = 9999
                              curMean = getMeanFromReturns(curMean, visitedCount, G)
                              returnsDict[S_t, A_t][0] = curMean ## update mean
                              returnsDict[S_t, A_t][1] = visitedCount ## update visitedcount
                          else:
                              curMean = returnsDict[S_t, A_t][0] ## get temp mean from returnsDict
                              curMean = getMeanFromReturns(curMean, visitedCount, G) ## get the new temp mean iteratively
                              returnsDict[S_t, A_t][1] = visitedCount ## update visitedcount
                              returnsDict[S_t, A_t][0] = curMean ## update mean
  
  
                          QDict[S_t, A_t] = returnsDict[S_t, A_t][0] ## update the Qfunction with the new mean value
                          tempR = S_t[0] ## temp variables simply to disassemble the tuple into row,col
                          tempC = S_t[1]
  
                          if iteration >= round(maxiters * explorationFactor): ## ONLY START UPDATING POLICY when we have reliable estimates for Qfunction, that is when iteration > maxiter/10
                              Q_function_is_reliable = True
                              policies[tempR, tempC] = getArgmaxActQ(S_t) ## update policy based on argmax_a[Q(S_t)]
  
  
  print("optimal policy with Monte-Carlo, every visit was \n")
  print("\n")
  print(policies)
  
  **Tags:** python, monte-carlo-methods
  > **Comments:**
  > **username_1**: Actually here I don't think we need the code - perhaps you could link it from the question. That's because the algorithm is performing as designed. You *might* have errors or bugs in your code, but they are not related to this problem.  
  > **username_1**: You have added even more code? I recommend (1) Not having the code here, but linking it. (2) Don't edit the question to post a solution into it, because it invalidates other answers (i.e. mine in this case). If you want to post your own answer with how you resolved the problem, please do so.  
  > **username_2**: Welcome to SE:AI.  I highly recommend taking Neil's advice.  (I'm leaving the question open provisionally, but I have to advise you that without edits, it will likely be closed by the community.)  
  > **username_1**: I could put the two code snippets as Github GISTs, and link them - also make the update into a community Wiki answer. Late347, it would be better if you did this, but if you cannot be bothered, then is it OK if I do so?  
  > **username_0**: Im fine with putting the code snippets to somewhere where people can access them. I was initially confused about this "hostile response" for my post ! sorry if I made a mistake... I've gotten used to the the idea that especially on stack overflow you definitely are allowed to post code in-line. And I remembered from some other stack exchange that you were supposed to edit your own answer rather than make a new answer, if you wanted to highlight something or add more information. I remembered from math stack exchange that you were allowed to ask multiple things in the same question post.  
  > **username_1**: Sorry I am not trying to be hostile, just trying to get the question into a form suitable for the site. You have misunderstood some things. Especially regarding editing the question. It is OK to add clarifying details, and in fact desirable. It is not OK to answer a question inside the question, and considered bad form to change the question radically after receiving a suitable answer. There is a separate Answer section for answering, and you are welcome to answer your own question there. Regarding the code, it is not adding anything to this specific question and IMO gets in the way.  
  > **username_3**: excuse me, I have a naive question for this code. Actually I need to change the matrix you use to a one dimensional array, and when the agent reach the target, it will get a additional reward like 10 or 20. Could you please tell me how can I make the adjustment based on your code? That will help me a lot!  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-04-19. Score: 3
  
  Your implementation of Monte Carlo Exploring Starts algorithm appears to be working as designed. This is a problem that can occur with some deterministic policies in the gridworld environment.
  
  It is possible for your policy improvement step to generate such a policy, and there is no recovery from this built into the algorithm. First visit and every visit variants will converge differently to the true action values, however neither offers an improvement here. It is most likely that your loops are occurring via state/action pairs that did not occur in the first episode, so the value estimates are default 0, which then looks like the best choice when creating the deterministic policy\*.
  
  In Sutton & Barto to demonstrate Monte Carlo ES, the authors choose an environment where such loops are impossible (a simplified Blackjack game). They then quickly move on to removing the need for exploring starts by using $\epsilon$-greedy policies. So this issue is not covered in detail, although there are assertions in a couple of places that it must be possible to complete episodes.
  
  To resolve this whilst still using Monte Carlo ES, you will need to alter the environment so that such loops are not possible. The simplest change is to terminate the episode if it gets too long. This is hacky, because done simply on the gridworld it violates the Markov property (because now the time step should technically be part of the state if you want to predict value). However, it will get you out of the immediate problem, and provided you set the termination point high enough - e.g. 100 steps for your small gridworld - the agent should still discover the optimal policy and associated action values.
  
  This "timeout" patch is also used by many OpenAI Gym environments, because although most other algorithms can find their way out of infinite loops like this, they can still suffer slow learning from over-long episodes as a result.
  
  ---
  
  \* This leads to a possible fix of initialising your Q values pessimistically - e.g. with -50 starting value. That should help the first deterministic policy join up to the terminal state - although if you make it *strictly* deterministic and resolve value ties deterministically too, then even this may not be enough. You might want to give that a try to verify what I am saying here, although I would recommend the timeout hack instead, as that is a more general solution. Pessimistic start values are bad for exploration when using other algorithms.
  
  > **Comments:**
  > **username_0**: I managed to make "a hacky fix". The issue appears to have resolved itself in usual cases if I let the algorithm explore the gridworld in the beginning with equiprobable randomwalk. Then, after having run some 500 first iterations, then only I start updating the  policy. So the early iterations are still gathering data into the returnsDict and Qdict, but the algorithm is delaying the updating of the policy until it has explored a bit in the beginning, with the randomwalk policy. It seems to get it "over the hump", because there is guaranteed iterations for all state-action pairs being visited  
  > **username_1**: @Late347: Yes I expect that will work well. It may still be possible to estimate values that result in a loop that way (such as an infinite to-and-fro between two states), but I would guess even if it is possible, that it is very unlikely.  
  > **username_2**: Neil, if you feel a need to edit the question to make the Q&A more useful, please feel free.  
  
  ---
  
  