Answers.Body: <p>Your Q learning update expression looks correct. The <code>Total Reward</code> will not be the same at the end of each episode because the starting position of taxi is different in each episode so the number of steps necessary to reach the final destination will be different in each episode. The graph that you posted shows that the algorithm converged after short amount of episodes so 100000 episodes might be too much. Since the environment is simple try manually calculating optimal policy for some starting specific position and then see if the algorithm does the same sequence of actions.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-14T11:01:22.993Z
Answers.LastActivityDate: 2020-02-14T11:01:22.993Z
Answers.UserDisplayName: Brale
Answers.Body: <p>Great answer by @Brale. I want to point out another thing. The plateau in a graph ---like the one you shared--- indicates convergence, and the converged value may not always be <em>zero</em>. In general, you need to verify the learned behavior by your algorithm. For instance, if you are using Gym's LunarLander environment, you should also double-check what is it that your algorithm has learned <em>after</em> converging. Put another way, your algorithm might converge, but not to the desired behavior.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-28T12:04:35.277Z
Answers.LastActivityDate: 2022-10-28T12:04:35.277Z
Answers.UserDisplayName: jigz
Body: <p>I started learning about Q table from this blog post <a href="https://www.oreilly.com/radar/introduction-to-reinforcement-learning-and-openai-gym/" rel="nofollow noreferrer">Introduction to reinforcement learning and OpenAI Gym, by Justin Francis</a>, which has a line as below -</p>
  <blockquote>
  <p>After so many episodes, the algorithm will converge and determine the optimal action for every state using the Q table, ensuring the highest possible reward. We now consider the environment problem solved.</p>
  </blockquote>
  <p>The Q table was updated by Q-learning formula
  <code>Q[state,action] += alpha * (reward + np.max(Q[state2]) - Q[state,action])</code></p>
  <p>I ran 100000 episodes of which I got the following -</p>
  <pre><code>Episode 99250 Total Reward: 9
  Episode 99300 Total Reward: 7
  Episode 99350 Total Reward: 6
  Episode 99400 Total Reward: 14
  Episode 99450 Total Reward: 10
  Episode 99500 Total Reward: 10
  Episode 99550 Total Reward: 9
  Episode 99600 Total Reward: 14
  Episode 99650 Total Reward: 5
  Episode 99700 Total Reward: 7
  Episode 99750 Total Reward: 3
  Episode 99800 Total Reward: 5
  </code></pre>
  <p>I don't know what the highest reward is. It does not look like it has converged. Yet, the following graph</p>
  <p><a href="https://i.sstatic.net/NBS9v.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/NBS9v.png" alt="enter image description here" /></a></p>
  <p>shows a trend in convergence but it was plotted for a larger scale.</p>
  <p>What should be the sequence of actions to be taken when the game is reset() but the &quot;learned&quot; Q table is available? How do we know that and the reward in that case?</p>
  
Tags: <reinforcement-learning><q-learning><rewards><convergence>
Title: How do we know that the algorithm has converged and ensures the highest possible reward?
UserDisplayName: Prabal Dev
ThreadText: # How do we know that the algorithm has converged and ensures the highest possible reward?
  
  (Asked by: username_0 on 2020-02-14)
  
  I started learning about Q table from this blog post [Introduction to reinforcement learning and OpenAI Gym, by Justin Francis](https://www.oreilly.com/radar/introduction-to-reinforcement-learning-and-openai-gym/), which has a line as below -
  
  > After so many episodes, the algorithm will converge and determine the optimal action for every state using the Q table, ensuring the highest possible reward. We now consider the environment problem solved.
  
  The Q table was updated by Q-learning formula
  `Q[state,action] += alpha * (reward + np.max(Q[state2]) - Q[state,action])`
  
  I ran 100000 episodes of which I got the following -
  
  ```
  Episode 99250 Total Reward: 9
  Episode 99300 Total Reward: 7
  Episode 99350 Total Reward: 6
  Episode 99400 Total Reward: 14
  Episode 99450 Total Reward: 10
  Episode 99500 Total Reward: 10
  Episode 99550 Total Reward: 9
  Episode 99600 Total Reward: 14
  Episode 99650 Total Reward: 5
  Episode 99700 Total Reward: 7
  Episode 99750 Total Reward: 3
  Episode 99800 Total Reward: 5
  
  ```
  
  I don't know what the highest reward is. It does not look like it has converged. Yet, the following graph
  
  [![enter image description here](https://i.sstatic.net/NBS9v.png)](https://i.sstatic.net/NBS9v.png)
  
  shows a trend in convergence but it was plotted for a larger scale.
  
  What should be the sequence of actions to be taken when the game is reset() but the "learned" Q table is available? How do we know that and the reward in that case?
  
  **Tags:** reinforcement-learning, q-learning, rewards, convergence
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2020-02-14. Score: 2 | Accepted answer
  
  Your Q learning update expression looks correct. The `Total Reward` will not be the same at the end of each episode because the starting position of taxi is different in each episode so the number of steps necessary to reach the final destination will be different in each episode. The graph that you posted shows that the algorithm converged after short amount of episodes so 100000 episodes might be too much. Since the environment is simple try manually calculating optimal policy for some starting specific position and then see if the algorithm does the same sequence of actions.
  
  
  ---
  
  ### Answer by username_2 on 2022-10-28. Score: 1
  
  Great answer by @username_1. I want to point out another thing. The plateau in a graph ---like the one you shared--- indicates convergence, and the converged value may not always be *zero*. In general, you need to verify the learned behavior by your algorithm. For instance, if you are using Gym's LunarLander environment, you should also double-check what is it that your algorithm has learned *after* converging. Put another way, your algorithm might converge, but not to the desired behavior.
  
  
  ---
  
  