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?