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. – Shifat E Arman 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_*$$.
• 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. – Swakshar Deb Nov 29 '20 at 17:09