Answers.Body: <p>Q-learning is an off-policy learning algorithm. We are following the behaviour policy, <span class="math-container">$b$</span>, which is <span class="math-container">$\epsilon-$</span>greedy. This behaviour policy need not be an optimal policy rather it is a more explorable policy. But we are learning the target policy, <span class="math-container">$\pi$</span>, which is argmax of state action value <span class="math-container">$(Q(s,a))$</span>. This target policy is by definition optimal policy.</p>
  <p>From the <span class="math-container">$\epsilon$</span>-greedy policy improvement theorem we can show that for any <span class="math-container">$\epsilon$</span>-greedy policy (I think you are referring to this as a non-optimal policy) we are still making progress towards the optimal policy and when <span class="math-container">$\pi^{'}$</span> = <span class="math-container">$\pi$</span> that is our optimal policy (Rich Sutton's book Chapter-5). Here <span class="math-container">$\pi^{'}$</span> is the new policy and <span class="math-container">$\pi$</span> is the previous policy.
  <a href="https://i.sstatic.net/fzhlj.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/fzhlj.png" alt="enter image description here" /></a></p>
  <p>Think of this diagram, where we are selecting action based on <span class="math-container">$\epsilon$</span>-greedy policy but still making progress towards the optimal policy <span class="math-container">$\pi_*$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-29T16:45:36.493Z
Answers.Text: This does not answer the question why, if we use a non-optimal policy, Q-learning converges to an optimal policy.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-29T17:09:37.087Z
Answers.Text: I think the op denoted $\epsilon$-greedy policy as sub-optimal policy. But from $\epsilon$-greedy policy improvement theorem we can show that the $\epsilon$-greedy policy converges to optimal policy.
Answers.UserDisplayName: Swakshar Deb
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-29T17:38:22.620Z
Answers.Text: You may want to include the usual diagram, which I think is quite insightful.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-29T17:57:26.550Z
Answers.Text: Where did you get this diagram from? Which version of the book are you specifically referring to? Can you provide the link? Isn't this diagram applied to generalized policy iteration and the policy shouldn't be greedy?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-29T18:02:59.500Z
Answers.Text: I took this diagram from David silver lecture slide (model-free control). Yes, this diagram applied to generalized policy iteration.
Answers.UserDisplayName: Swakshar Deb
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-29T16:13:45.230Z
Answers.LastActivityDate: 2020-11-29T17:51:17.687Z
Answers.LastEditDate: 2020-11-29T17:51:17.687Z
Answers.UserDisplayName: Swakshar Deb
Body: <p>In Q-learning, during training, it doesn't matter how the agent selects actions. The algorithm always converges to the optimal policy. Why does this happen? What's the intuition?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-11-18T01:38:47.577Z
Comments.Text: You can find a proof of the convergence of the Q-learning algorithm in the paper [Convergence of Q-learning: A Simple Proof](http://users.isr.ist.utl.pt/~mtjspaan/readingGroup/ProofQlearning.pdf) by Francisco S. Melo.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-11-18T01:40:40.503Z
Comments.Text: Your statement "it doesn’t matter how I select actions" is not really true. Q-learning "requires that all state-action pairs be visited infinitely often", as it's mentioned in the paper I linked you to above and e.g. in the book RL: An Introduction by Barto and Sutton.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-11-18T01:41:50.150Z
Comments.Text: So, what is your real question? Are you looking for a proof? If yes, then you can find it in the paper above. Or are you looking for an intuition behind the convergence of Q-learning?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-11-20T14:45:51.123Z
Comments.Text: I am actually looking for an intuition behind this.
Comments.UserDisplayName: Shifat E Arman
Tags: <reinforcement-learning><q-learning><proofs><convergence>
Title: Why does Q-learning converge to the optimal policy, even if the agent acts sub-optimally?
UserDisplayName: Shifat E Arman
ThreadText: # Why does Q-learning converge to the optimal policy, even if the agent acts sub-optimally?
  
  (Asked by: username_0 on 2018-11-17)
  
  In Q-learning, during training, it doesn't matter how the agent selects actions. The algorithm always converges to the optimal policy. Why does this happen? What's the intuition?
  
  **Tags:** reinforcement-learning, q-learning, proofs, convergence
  
  > **Comments:**
  > **username_1**: You can find a proof of the convergence of the Q-learning algorithm in the paper [Convergence of Q-learning: A Simple Proof](http://users.isr.ist.utl.pt/~mtjspaan/readingGroup/ProofQlearning.pdf) by Francisco S. Melo.  
  > **username_1**: Your statement "it doesn’t matter how I select actions" is not really true. Q-learning "requires that all state-action pairs be visited infinitely often", as it's mentioned in the paper I linked you to above and e.g. in the book RL: An Introduction by Barto and Sutton.  
  > **username_1**: So, what is your real question? Are you looking for a proof? If yes, then you can find it in the paper above. Or are you looking for an intuition behind the convergence of Q-learning?  
  > **username_0**: I am actually looking for an intuition behind this.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-11-29. Score: 1
  
  Q-learning is an off-policy learning algorithm. We are following the behaviour policy, $b$, which is $\epsilon-$greedy. This behaviour policy need not be an optimal policy rather it is a more explorable policy. But we are learning the target policy, $\pi$, which is argmax of state action value $(Q(s,a))$. This target policy is by definition optimal policy.
  
  From the $\epsilon$-greedy policy improvement theorem we can show that for any $\epsilon$-greedy policy (I think you are referring to this as a non-optimal policy) we are still making progress towards the optimal policy and when $\pi^{'}$ = $\pi$ that is our optimal policy (Rich Sutton's book Chapter-5). Here $\pi^{'}$ is the new policy and $\pi$ is the previous policy.
  [![enter image description here](https://i.sstatic.net/fzhlj.png)](https://i.sstatic.net/fzhlj.png)
  
  Think of this diagram, where we are selecting action based on $\epsilon$-greedy policy but still making progress towards the optimal policy $\pi\_\*$.
  
  > **Comments:**
  > **username_1**: This does not answer the question why, if we use a non-optimal policy, Q-learning converges to an optimal policy.  
  > **username_2**: I think the op denoted $\epsilon$-greedy policy as sub-optimal policy. But from $\epsilon$-greedy policy improvement theorem we can show that the $\epsilon$-greedy policy converges to optimal policy.  
  > **username_1**: You may want to include the usual diagram, which I think is quite insightful.  
  > **username_1**: Where did you get this diagram from? Which version of the book are you specifically referring to? Can you provide the link? Isn't this diagram applied to generalized policy iteration and the policy shouldn't be greedy?  
  > **username_2**: I took this diagram from David silver lecture slide (model-free control). Yes, this diagram applied to generalized policy iteration.  
  
  ---
  
  