Answers.Body: <p>You have a simple mistake in your TD Error function:</p>
  
  <pre><code>TD_error = reward + gamma * max(Q[next_state]) - Q[state][action]
  </code></pre>
  
  <p>You have made <code>Q[next_state]</code> a Python <code>dict</code>, so this will take the maximum <em>key</em> which is 3 for all your Q table entries. This is why you end up with values very close to 3 at the end, which is impossible for your problem, the maximum return will be <code>1.0</code> when stepping from adjacent grid points to the positive terminal state.</p>
  
  <p>The correct code is:</p>
  
  <pre><code>TD_error = reward + gamma * max(Q[next_state].values()) - Q[state][action]
  </code></pre>
  
  <p>Alternatively, since your actions are all numeric, you could use a <code>list</code> instead of a <code>dict</code> in your Q table.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-22T15:29:48.123Z
Answers.LastActivityDate: 2020-01-22T15:29:48.123Z
Answers.UserDisplayName: Neil Slater
Body: <p>I am coding out a simple 4x4 grid game whereby the agent starts at a particular state and his aim is to reach the terminal state. The agent is supposed to avoid traps along the way and reach the end goal with high reward. The below picture illustrates the environment. </p>
  
  <p><a href="https://i.sstatic.net/NITn0.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/NITn0.png" alt="enter image description here"></a></p>
  
  <p>The code that I am running is shown below:</p>
  
  <pre><code># 4x4 Grid
  import random
  
  
  gamma = 1
  grid = [[-0.1 for i in range(4)] for j in range(4)]
  episodes = 500000
  epsilon = 1 # start greedy
  decay = 0.999
  min_epsilon = 0.1
  alpha = 0.65
  # set terminal states
  grid[1][0] = -1
  grid[2][2] = -1
  grid[0][3] = 1
  
  # Set up Q tables
  # 0: up, 1: down, 2: left, 3: right
  # Q = {(0,0): {0: z, 1: x, 2: c, 3: v}, ... }}
  Q = {}
  
  # 4 rows
  for row in range(4):
      # 4 columns
      for column in range(4):
          Q[(row,column)] = {}
          # 4 actions
          for k in range(4):
              Q[(row,column)][k] = 0
  
  
  def isTerminal(state):
      if state == (1,0) or state == (2,2) or state == (0,3):
          return True
      return False
  
  def get_next_state_reward(state, action):
  
      row = state[0]
      col = state[1]
      #print(row, col)
      if action == 0: # up
          # out of grid
          if (row - 1) &lt; 0:
              return (state, grid[row][col])
  
      if action == 1: # down
  
          # out of grid
          if (row + 1) &gt; len(grid) - 1:
              return (state, grid[row][col])
  
      if action == 2: # left
  
          if (col - 1 &lt; 0):
              return (state, grid[row][col])
  
      if action == 3: # right
  
          if (col + 1 &gt; len(grid[row]) - 1):
              return (state, grid[row][col])
  
      if action == 0:
  
          row -= 1
          return ((row,col), grid[row][col])
  
      if action == 1:
  
          row += 1
          return ((row,col), grid[row][col])
  
      if action == 2:
  
          col -= 1
          return ((row,col), grid[row][col])
  
      if action == 3:
  
          col += 1
          return ((row,col), grid[row][col])
  
  state_visit = {}
  for row in range(4):
      # 4 columns
      for column in range(4):
          state_visit[(row,column)] = 0
  
  for episode in range(episodes):
  
      # let agent start at start state
      state = (3,0)
  
      while not isTerminal(state):
  
          r = random.uniform(0,1)
  
          if r &lt; epsilon:
              action = random.randint(0,3)
          else:
              action = max(Q[state], key=lambda key: Q[state][key])
  
  
          next_state, reward = get_next_state_reward(state, action)
  
          TD_error = reward + gamma * max(Q[next_state]) - Q[state][action]
  
          Q[state][action] = Q[state][action] + alpha * TD_error
  
          state = next_state
  
          state_visit[next_state] += 1
          epsilon = max(min_epsilon, epsilon*decay)
  
          #input()
  
  
  policy = {}
  # get optimal policies for each state
  for states in Q:
      policy[states] = max(Q[states], key=lambda key: Q[states][key])
  </code></pre>
  
  <p>When I finish running the algorithm however, I am unable to achieve the optimal policy no matter how many tweaks I do to the number of episodes, or epsilon decay, or the alpha value. </p>
  
  <p>Particularly, the Q values that I attain for state (2,0), (0,1) and (0,0) have Q values that are equal values for three directions except for the last direction which brings the agent to the terminal state. </p>
  
  <p>For example, these are the Q-values that I get for state (0,0), (0,1) and (2,0) respectively.</p>
  
  <p>(0,0): {0: 2.0, 1: 2.9, 2: 2.9, 3: 2.9}</p>
  
  <p>(0,1): {0: 2.9, 1: 2.0, 2: 2.9, 3: 2.9}</p>
  
  <p>(2,0): {0: 2.9, 1: 2.9, 2: 2.9, 3: 2.9}</p>
  
  <p>I am not sure why the Q-values for the 3 directions should be the same because each extra step that the agent takes incurs a negative reward. </p>
  
  <p>Would anyone be able to help ? Thank you so much !</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-01-22T15:19:08.227Z
Comments.Text: what does `max(Q[next_state])` do ?. `Q[next_state]` returns a dict with actions as keys and Q values as values. So you are taking max action (3) every time instead of a Q value ?.
Comments.UserDisplayName: Brale
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-01-22T15:22:23.327Z
Comments.Text: yes, Q[next_state] returns a dictionary that maps each action to it's q value for that state. I am taking the highest possible Q value for the next state in the update equation. Why does it return action (3) ?
Comments.UserDisplayName: calveeen
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-01-22T15:24:31.630Z
Comments.Text: max considers keys of dict not values. You are taking max action, it returns number 3 every time instead of a Q value.
Comments.UserDisplayName: Brale
Tags: <reinforcement-learning><q-learning>
Title: Q-learning problem wrong policy
UserDisplayName: calveeen
ThreadText: # Q-learning problem wrong policy
  
  (Asked by: username_0 on 2020-01-22)
  
  I am coding out a simple 4x4 grid game whereby the agent starts at a particular state and his aim is to reach the terminal state. The agent is supposed to avoid traps along the way and reach the end goal with high reward. The below picture illustrates the environment.
  
  [![enter image description here](https://i.sstatic.net/NITn0.png)](https://i.sstatic.net/NITn0.png)
  
  The code that I am running is shown below:
  
  ```
  # 4x4 Grid
  import random
  
  gamma = 1
  grid = [[-0.1 for i in range(4)] for j in range(4)]
  episodes = 500000
  epsilon = 1 # start greedy
  decay = 0.999
  min_epsilon = 0.1
  alpha = 0.65
  # set terminal states
  grid[1][0] = -1
  grid[2][2] = -1
  grid[0][3] = 1
  
  # Set up Q tables
  # 0: up, 1: down, 2: left, 3: right
  # Q = {(0,0): {0: z, 1: x, 2: c, 3: v}, ... }}
  Q = {}
  
  # 4 rows
  for row in range(4):
      # 4 columns
      for column in range(4):
          Q[(row,column)] = {}
          # 4 actions
          for k in range(4):
              Q[(row,column)][k] = 0
  
  def isTerminal(state):
      if state == (1,0) or state == (2,2) or state == (0,3):
          return True
      return False
  
  def get_next_state_reward(state, action):
  
      row = state[0]
      col = state[1]
      #print(row, col)
      if action == 0: # up
          # out of grid
          if (row - 1) < 0:
              return (state, grid[row][col])
  
      if action == 1: # down
  
          # out of grid
          if (row + 1) > len(grid) - 1:
              return (state, grid[row][col])
  
      if action == 2: # left
  
          if (col - 1 < 0):
              return (state, grid[row][col])
  
      if action == 3: # right
  
          if (col + 1 > len(grid[row]) - 1):
              return (state, grid[row][col])
  
      if action == 0:
  
          row -= 1
          return ((row,col), grid[row][col])
  
      if action == 1:
  
          row += 1
          return ((row,col), grid[row][col])
  
      if action == 2:
  
          col -= 1
          return ((row,col), grid[row][col])
  
      if action == 3:
  
          col += 1
          return ((row,col), grid[row][col])
  
  state_visit = {}
  for row in range(4):
      # 4 columns
      for column in range(4):
          state_visit[(row,column)] = 0
  
  for episode in range(episodes):
  
      # let agent start at start state
      state = (3,0)
  
      while not isTerminal(state):
  
          r = random.uniform(0,1)
  
          if r < epsilon:
              action = random.randint(0,3)
          else:
              action = max(Q[state], key=lambda key: Q[state][key])
  
          next_state, reward = get_next_state_reward(state, action)
  
          TD_error = reward + gamma * max(Q[next_state]) - Q[state][action]
  
          Q[state][action] = Q[state][action] + alpha * TD_error
  
          state = next_state
  
          state_visit[next_state] += 1
          epsilon = max(min_epsilon, epsilon*decay)
  
          #input()
  
  policy = {}
  # get optimal policies for each state
  for states in Q:
      policy[states] = max(Q[states], key=lambda key: Q[states][key])
  
  ```
  
  When I finish running the algorithm however, I am unable to achieve the optimal policy no matter how many tweaks I do to the number of episodes, or epsilon decay, or the alpha value.
  
  Particularly, the Q values that I attain for state (2,0), (0,1) and (0,0) have Q values that are equal values for three directions except for the last direction which brings the agent to the terminal state.
  
  For example, these are the Q-values that I get for state (0,0), (0,1) and (2,0) respectively.
  
  (0,0): {0: 2.0, 1: 2.9, 2: 2.9, 3: 2.9}
  
  (0,1): {0: 2.9, 1: 2.0, 2: 2.9, 3: 2.9}
  
  (2,0): {0: 2.9, 1: 2.9, 2: 2.9, 3: 2.9}
  
  I am not sure why the Q-values for the 3 directions should be the same because each extra step that the agent takes incurs a negative reward.
  
  Would anyone be able to help ? Thank you so much !
  
  **Tags:** reinforcement-learning, q-learning
  
  > **Comments:**
  > **username_1**: what does `max(Q[next_state])` do ?. `Q[next_state]` returns a dict with actions as keys and Q values as values. So you are taking max action (3) every time instead of a Q value ?.  
  > **username_0**: yes, Q[next_state] returns a dictionary that maps each action to it's q value for that state. I am taking the highest possible Q value for the next state in the update equation. Why does it return action (3) ?  
  > **username_1**: max considers keys of dict not values. You are taking max action, it returns number 3 every time instead of a Q value.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-01-22. Score: 1 | Accepted answer
  
  You have a simple mistake in your TD Error function:
  
  ```
  TD_error = reward + gamma * max(Q[next_state]) - Q[state][action]
  
  ```
  
  You have made `Q[next_state]` a Python `dict`, so this will take the maximum *key* which is 3 for all your Q table entries. This is why you end up with values very close to 3 at the end, which is impossible for your problem, the maximum return will be `1.0` when stepping from adjacent grid points to the positive terminal state.
  
  The correct code is:
  
  ```
  TD_error = reward + gamma * max(Q[next_state].values()) - Q[state][action]
  
  ```
  
  Alternatively, since your actions are all numeric, you could use a `list` instead of a `dict` in your Q table.
  
  
  ---
  
  