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?

  • 2
    $\begingroup$ 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. $\endgroup$ – nbro Nov 18 '18 at 1:38
  • 1
    $\begingroup$ 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. $\endgroup$ – nbro Nov 18 '18 at 1:40
  • 1
    $\begingroup$ 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? $\endgroup$ – nbro Nov 18 '18 at 1:41
  • $\begingroup$ I am actually looking for an intuition behind this. $\endgroup$ – 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. enter image description here

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.