How do I know when a Q-learning algorithm converges?

Question

I am currently trying to implement the Q-learning algorithm. After reading enough to have a good understanding of how it works, I am now wondering how to know when the algorithm actually reaches convergence. Say, I have a Q-table generated as in this example, how do I know the job is done, i.e, the algorithm has converged?

Thanks!

Answer 1

In practice, a reinforcement learning algorithm is considered to converge when the learning curve gets flat and no longer increases.

However, other elements should be taken into account since it depends on your use case and your setup. In theory, Q-Learning has been proven to converge towards the optimal solution. However, in this section of (Sutton and Barto, 1998), since the exploration parameter $\varepsilon$ parameter is not gradually increased, Q-Learning converges in a premature fashion (before reaching the optimal policy).

To my experience, it is not always obvious to make the $\varepsilon$ and the learning rate $\alpha$ decrease in a way that ensures convergence and most of the time, there is some tuning involved here (when moving these parameters, your Q-Learning curve will stabilize in different levels).

Finally, don't forget that Q-Learning has been propose in 1989 by Watkins, which is a little bit outdated. It is well suited when you learn about reinforcement learning but not that much when implementing real learning agents. I would recommend exploring more state-of-the-art techniques.

Answer 2

1. Do a fixed number of episodes/iterations. Simplest approach which will give you near-optimal solution.
2. Evaluate on N number of episodes and take an average. For example rollout 5 episodes, take average return $ G $ and compare that with best possible $ G_{max} $(if that info is available) or with 2-3 previous results with something like RMSE.
3. UPD. This one was incorrect. Due to randomness involved in an algorithm you cannot do that. This will work only for value iteration. Track Q-function updates. Once it becomes smaller than some small number e you can stop running episodes/iterations.

    e = 0.001  # some small number
    while True:  # improving our Q
        delta = 0  # track updates

        while True:  # running episode
            old_Q = Q[s, a]
            new_Q = Q[s, a] + alpha * (r + gamma*max_a(Q[s', a']) - Q[s, a])
            delta = max(delta, old_Q-new_Q)

        if delta < e:
            # Assuming Q has been converged, no major updates
            # while running an episode (max update was less
            # than small `e`)
            break

^^ apply the code only for value iteration.

Also check this question for more information.