How do we know that the algorithm has converged and ensures the highest possible reward?

Question

I started learning about Q table from this blog post Introduction to reinforcement learning and OpenAI Gym, by Justin Francis, which has a line as below -

After so many episodes, the algorithm will converge and determine the optimal action for every state using the Q table, ensuring the highest possible reward. We now consider the environment problem solved.

The Q table was updated by Q-learning formula Q[state,action] += alpha * (reward + np.max(Q[state2]) - Q[state,action])

I ran 100000 episodes of which I got the following -

Episode 99250 Total Reward: 9
Episode 99300 Total Reward: 7
Episode 99350 Total Reward: 6
Episode 99400 Total Reward: 14
Episode 99450 Total Reward: 10
Episode 99500 Total Reward: 10
Episode 99550 Total Reward: 9
Episode 99600 Total Reward: 14
Episode 99650 Total Reward: 5
Episode 99700 Total Reward: 7
Episode 99750 Total Reward: 3
Episode 99800 Total Reward: 5

I don't know what the highest reward is. It does not look like it has converged. Yet, the following graph

shows a trend in convergence but it was plotted for a larger scale.

What should be the sequence of actions to be taken when the game is reset() but the "learned" Q table is available? How do we know that and the reward in that case?

Answer 1

Your Q learning update expression looks correct. The Total Reward will not be the same at the end of each episode because the starting position of taxi is different in each episode so the number of steps necessary to reach the final destination will be different in each episode. The graph that you posted shows that the algorithm converged after short amount of episodes so 100000 episodes might be too much. Since the environment is simple try manually calculating optimal policy for some starting specific position and then see if the algorithm does the same sequence of actions.

Answer 2

Great answer by @Brale. I want to point out another thing. The plateau in a graph ---like the one you shared--- indicates convergence, and the converged value may not always be zero. In general, you need to verify the learned behavior by your algorithm. For instance, if you are using Gym's LunarLander environment, you should also double-check what is it that your algorithm has learned after converging. Put another way, your algorithm might converge, but not to the desired behavior.