Answers.Body: <p>I was able to solve the problem.</p>
  <p>The main issue for non-convergence was that I was not decaying the learning rate appropriately. I put a decay rate of <span class="math-container">$-0.00005$</span> on the learning rate <code>lr</code>, and subsequently Q-Learning also converged to the same value as value iteration.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-15T08:49:42.723Z
Answers.Text: You may also have been able to work with a lower fixed learning rate of e.g. 0.01 - that should be low enough to converge to an optimal policy, and result in close enough to true Q values that you could easily see the similarity with the dynamic programming approaches.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-01T16:51:22.540Z
Answers.Text: Feel free to accept your own answer by clicking on the checkmark sign.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-15T00:56:09.393Z
Answers.LastActivityDate: 2020-11-01T16:51:03.593Z
Answers.LastEditDate: 2020-11-01T16:51:03.593Z
Answers.UserDisplayName: abkds
Body: <p>I am trying to learn tabular Q learning by using a table of states and actions (i.e. no neural networks). I was trying it out on the <a href="https://gym.openai.com/envs/FrozenLake-v0/" rel="nofollow noreferrer">FrozenLake</a> environment. It's a very simple environment, where the task is to reach a <code>G</code> starting from a source <code>S</code> avoiding holes <code>H</code> and just following the frozen path which is <code>F</code>. The <span class="math-container">$4 \times 4$</span> FrozenLake grid looks like this</p>
  <pre><code>SFFF
  FHFH
  FFFH
  HFFG
  </code></pre>
  <p>I am working with the slippery version, where the agent, if it takes a step, has an equal probability of either going in the direction it intends or slipping sideways perpendicular to the original direction (if that position is in the grid). Holes are terminal states and a goal is a terminal state.</p>
  <p>Now I first tried <em>value iteration</em> which converges to the following set of values for the states</p>
  <pre><code>[0.0688909  0.06141457 0.07440976 0.05580732 0.09185454 0. 0.11220821 0.         0.14543635 0.24749695 0.29961759 0. 0.         0.3799359  0.63902015 0.        ]
  </code></pre>
  <p>I also coded <em>policy iteration</em>, and it also gives me the same result. So I am pretty confident that this value function is correct.</p>
  <p>Now, I tried to code the Q learning algorithm, here is my code for the Q learning algorithm</p>
  <pre><code>def get_action(Q_table, state, epsilon):
      &quot;&quot;&quot;
      Uses e-greedy to policy to return an action corresponding to state
      
      Args:
          Q_table: numpy array containing the q values
          state: current state
          epsilon: value of epsilon in epsilon greedy strategy
          env: OpenAI gym environment 
      &quot;&quot;&quot;
      return env.action_space.sample() if np.random.random() &lt; epsilon else np.argmax(Q_table[state]) 
  
  
  def tabular_Q_learning(env):
      &quot;&quot;&quot;
      Returns the optimal policy by using tabular Q learning
      
      Args:
          env: OpenAI gym environment
          
      Returns:
          (policy, Q function, V function) 
      &quot;&quot;&quot;
      
      # initialize the Q table
      # 
      # Implementation detail: 
      # A numpy array of |x| * |a| values
      
      Q_table = np.zeros((env.nS, env.nA))
      
      # hyperparameters
      epsilon = 0.9
      episodes = 500000
      lr = 0.81
  
      
      for _ in tqdm_notebook(range(episodes)):
          # initialize the state
          state = env.reset()
          
          if episodes / 1000 &gt; 21:
              epsilon = 0.1
          
          t = 0
          while True: # for each step of the episode
              # env.render()
              # print(observation)
           
              # choose a from s using policy derived from Q 
              action = get_action(Q_table, state, epsilon) 
              
              # take action a, observe r, s_dash
              s_dash, r, done, info = env.step(action)
              
              # Q table update 
              Q_table[state][action] += lr * (r + gamma * np.max(Q_table[s_dash]) - Q_table[state][action])
              
              state = s_dash
              
              t += 1
              
              if done:
                  # print(&quot;Episode finished after {} timesteps&quot;.format(t+1))
                  break
          # print(Q_table)
      
      policy = np.argmax(Q_table, axis=1)
      V = np.max(Q_table, axis=1)
      
      return policy, Q_table, V
  </code></pre>
  <p>I tried running it and it converges to a different set of values which is following <code>[0.26426802 0.03656142 0.12557195 0.03075882 0.35018374 0. 0.02584052 0.         0.37657211 0.59209091 0.15439031 0. 0.         0.60367728 0.79768863 0.        ]</code></p>
  <p>I am not getting, what is going wrong. The implementation of Q learning is pretty straightforward. I checked my code, it seems right.</p>
  <p>Any pointers would be helpful.</p>
  
Tags: <reinforcement-learning><q-learning><value-iteration><policy-iteration><frozen-lake>
Title: Why is my implementation of Q-learning not converging to the right values in the FrozenLake environment?
UserDisplayName: abkds
ThreadText: # Why is my implementation of Q-learning not converging to the right values in the FrozenLake environment?
  
  (Asked by: username_0 on 2019-10-14)
  
  I am trying to learn tabular Q learning by using a table of states and actions (i.e. no neural networks). I was trying it out on the [FrozenLake](https://gym.openai.com/envs/FrozenLake-v0/) environment. It's a very simple environment, where the task is to reach a `G` starting from a source `S` avoiding holes `H` and just following the frozen path which is `F`. The $4 \times 4$ FrozenLake grid looks like this
  
  ```
  SFFF
  FHFH
  FFFH
  HFFG
  
  ```
  
  I am working with the slippery version, where the agent, if it takes a step, has an equal probability of either going in the direction it intends or slipping sideways perpendicular to the original direction (if that position is in the grid). Holes are terminal states and a goal is a terminal state.
  
  Now I first tried *value iteration* which converges to the following set of values for the states
  
  ```
  [0.0688909  0.06141457 0.07440976 0.05580732 0.09185454 0. 0.11220821 0.         0.14543635 0.24749695 0.29961759 0. 0.         0.3799359  0.63902015 0.        ]
  
  ```
  
  I also coded *policy iteration*, and it also gives me the same result. So I am pretty confident that this value function is correct.
  
  Now, I tried to code the Q learning algorithm, here is my code for the Q learning algorithm
  
  ```
  def get_action(Q_table, state, epsilon):
      """
      Uses e-greedy to policy to return an action corresponding to state
      
      Args:
          Q_table: numpy array containing the q values
          state: current state
          epsilon: value of epsilon in epsilon greedy strategy
          env: OpenAI gym environment 
      """
      return env.action_space.sample() if np.random.random() < epsilon else np.argmax(Q_table[state]) 
  
  def tabular_Q_learning(env):
      """
      Returns the optimal policy by using tabular Q learning
      
      Args:
          env: OpenAI gym environment
          
      Returns:
          (policy, Q function, V function) 
      """
      
      # initialize the Q table
      # 
      # Implementation detail: 
      # A numpy array of |x| * |a| values
      
      Q_table = np.zeros((env.nS, env.nA))
      
      # hyperparameters
      epsilon = 0.9
      episodes = 500000
      lr = 0.81
  
      
      for _ in tqdm_notebook(range(episodes)):
          # initialize the state
          state = env.reset()
          
          if episodes / 1000 > 21:
              epsilon = 0.1
          
          t = 0
          while True: # for each step of the episode
              # env.render()
              # print(observation)
           
              # choose a from s using policy derived from Q 
              action = get_action(Q_table, state, epsilon) 
              
              # take action a, observe r, s_dash
              s_dash, r, done, info = env.step(action)
              
              # Q table update 
              Q_table[state][action] += lr * (r + gamma * np.max(Q_table[s_dash]) - Q_table[state][action])
              
              state = s_dash
              
              t += 1
              
              if done:
                  # print("Episode finished after {} timesteps".format(t+1))
                  break
          # print(Q_table)
      
      policy = np.argmax(Q_table, axis=1)
      V = np.max(Q_table, axis=1)
      
      return policy, Q_table, V
  
  ```
  
  I tried running it and it converges to a different set of values which is following `[0.26426802 0.03656142 0.12557195 0.03075882 0.35018374 0. 0.02584052 0. 0.37657211 0.59209091 0.15439031 0. 0. 0.60367728 0.79768863 0. ]`
  
  I am not getting, what is going wrong. The implementation of Q learning is pretty straightforward. I checked my code, it seems right.
  
  Any pointers would be helpful.
  
  **Tags:** reinforcement-learning, q-learning, value-iteration, policy-iteration, frozen-lake
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2019-10-15. Score: 4 | Accepted answer
  
  I was able to solve the problem.
  
  The main issue for non-convergence was that I was not decaying the learning rate appropriately. I put a decay rate of $-0.00005$ on the learning rate `lr`, and subsequently Q-Learning also converged to the same value as value iteration.
  
  > **Comments:**
  > **username_1**: You may also have been able to work with a lower fixed learning rate of e.g. 0.01 - that should be low enough to converge to an optimal policy, and result in close enough to true Q values that you could easily see the similarity with the dynamic programming approaches.  
  > **username_2**: Feel free to accept your own answer by clicking on the checkmark sign.  
  
  ---
  
  