What is a good convergence criterion for Q-learning in a stochastic environment?

Question

I have a stochastic environment and I'm implementing a Q-table for the learning that happens on the environment. The code is shown below. In short, there are ten states (0, 1, 2,...,9), and three actions: 0, 1, and 2. The action 0 does nothing, action 1 subtracts 1 with a probability of 0.7, and action 2 adds 1 with a probability of 0.7. We get a reward of 1 when we are in state 5, and 0 otherwise.

import numpy as np
import matplotlib.pyplot as plt

def reward(s_dash):
    if s_dash == 5:
        return 1
    else: 
        return 0
states = range(10)
Q = np.zeros((len(states),3))
Q_previous = np.zeros((len(states),3))
episodes = 2000
trials = 100
alpha = 0.1
decay = 0.995
gamma = 0.9
ls_av = []
ls = []
for episode in range(episodes):
    print(episode)
    s = np.random.choice(states)
    eps = 1
    for i in range(trials):
        eps *= decay
        p = np.random.random()
        if p < eps:
            a = np.random.randint(0,3)
        else:
            a = np.argmax(Q[s, :])

        if a == 0:
            s_dash = s
        elif a == 1:
            if p >= 0.7:
                s_dash = max(s-1, 0)
            else:
                s_dash = s
        else:
            if p >= 0.7:
                s_dash = min(s+1, 9)
            else:
                s_dash = s
        r = reward(s_dash)
        Q[s][a] = (1-alpha)*Q[s][a] + alpha*(r + gamma*np.max(Q[s_dash]))
        s = s_dash
    ls.append(np.max(abs(Q - Q_previous)))
    Q_previous = np.copy(Q)
print(Q)
for i in range(10):
    print(i, np.argmax(Q[i, :]))
plt.plot(ls)
plt.show()

When I plot the absolute value of the maximum change in the Q-table at the end of each episode, I get the following, which indicates that the Q-table is constantly being updated.

However, I see that when I print out the action with the max Q-value for each state, it shows what I expect to be the optimal policy. For each state, the best action is given as shown below:

(0, 2)
(1, 2)
(2, 2)
(3, 2)
(4, 2)
(5, 0)
(6, 1)
(7, 1)
(8, 1)
(9, 1)

My question is: why do I not have convergence in the Q-table? If I had a stochastic environment for which I didn't know before-hand what the optimal policy is, how will I be able to judge if I need to stop training when the Q-table isn't converging?

Answer 1

To obtain guarantees of convergence for Q table values, you need to decay the learning rate, $\alpha$, at a suitable rate. Too fast and convergence will be to inaccurate values. Too slow and convergence never happens.

For sticking with theoretical guarantees, the learning rate decay process should generally follow the rule that $\sum_t \alpha_t = \infty$ but $\sum_t \alpha_t^2 \ne \infty$ - an example of a learning rate schedule that does this is $\alpha_t = \frac{1}{t}$, although in practice that specific choice could lead to very slow convergence.

Choosing a good starting $\alpha$ and a good decay schedule will depend on the problem, and you may want to base it on experience with similar problems. However, it is not that common to need to gurantee convergence of action values in value-based reinforcement learning. In control problems you often care more about have finding an optimal policy than about perfectly accurate action values. Further to that, many interesting control problems are too complex to solve perfectly in tabular form, so you expect some approximation. It seems relatively common just to pick a learning rate for the problem and stick with it.

If you make your learning rate lower, the Q table will converge to more stable Q values, but possibly at the expense of taking longer to converge on the optimal policy.