Why does Q-learning converge to the optimal policy, even if the agent acts sub-optimally?

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?

• You can find a proof of the convergence of the Q-learning algorithm in the paper Convergence of Q-learning: A Simple Proof by Francisco S. Melo.
– nbro
Nov 18 '18 at 1:38
• 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.
– nbro
Nov 18 '18 at 1:40
• 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?
– nbro
Nov 18 '18 at 1:41
• I am actually looking for an intuition behind this. Nov 20 '18 at 14:45

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. Think of this diagram, where we are selecting action based on $$\epsilon$$-greedy policy but still making progress towards the optimal policy $$\pi_*$$.

• This does not answer the question why, if we use a non-optimal policy, Q-learning converges to an optimal policy.
– nbro
Nov 29 '20 at 16:45
• 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. Nov 29 '20 at 17:09
• You may want to include the usual diagram, which I think is quite insightful.
– nbro
Nov 29 '20 at 17:38
• 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?
– nbro
Nov 29 '20 at 17:57
• I took this diagram from David silver lecture slide (model-free control). Yes, this diagram applied to generalized policy iteration. Nov 29 '20 at 18:02