# Q table not converging for an arbitrary experiment

This is an experiment in order to understand the working of Q table and Q learning.

I have the states as

states = [0,1,2,3]

I have an arbitrary value for each of these states as shown below (assume index-based mapping) -

arbitrary_values_for_states = [39.9,47.52,32.92,37.6]

I want to find the minimum of the state which will give me the minimum value. So I have complimented the values to 50-arbitrary value.

inverse_values_for_states = [50-x for x in arbitrary_values_for_states]

Therefore, I defined reward function as -

def reward(s,a,s_dash):
if inverse_values_for_states[s]<inverse_values_for_states[s_dash]:
return 1
elif inverse_values_for_states[s]>inverse_values_for_states[s_dash]:
return -1
else:
return 0


Q table is initialized as - Q = np.zeros((4,4)) (np is numpy)

The learning is carried out as -

episodes = 5
steps = 10
for episode in range(episodes):
s = np.random.randint(0,4)
alpha0 = 0.05
decay = 0.005
gamma = 0.6
for step in range(steps):
a = np.random.randint(0,4)
action.append(a)
s_dash = a
alpha = alpha0/(1+step*decay)
Q[s][a] = (1-alpha)*Q[s][a]+alpha*(reward(s,a,s_dash)+gamma*np.max(Q[s_dash]))

s = s_dash


The problem is, the table doesn't converge.

Example. For the above scenario -

np.argmax(Q[0]) gives 3
np.argmax(Q[1]) gives 2
np.argmax(Q[2]) gives 2
np.argmax(Q[3]) gives 2


All of the states should give argmax as 2 (which is actually the index[state] of the minimum value).

Another example,

when I increase steps to 1000 and episodes to 50,

np.argmax(Q[0]) gives 3
np.argmax(Q[1]) gives 0
np.argmax(Q[2]) gives 1
np.argmax(Q[3]) gives 2


More, steps and episodes should assure convergence, but this is not visible.

I need help where I am going wrong.

PS: This little experiment is needed to make Q-learning applicable to a larger combinatorial problem. Unless I understand this, I don't think I will be able to do that right. Also, there is no terminal state because this is an optimization problem. (And I have heard that Q-learning doesn't necessarily needs a terminal state)

• for episode in range(episodes): doesn't it should be for steps in range(episodes) ? Sorry, I'm a C++ guy, it's a bit daunting to me... :P May 6, 2020 at 8:50
• @abhas_RewCie range() is like a vector of integers. episodes specify the stop value for generating the integers. episode is like a candidate element (i) of that vector. So, it will loosely translate as for(int episode=0; episode<episodes.size();episode++) May 6, 2020 at 14:45
• if you don't mind writing the algorithm.... May 6, 2020 at 14:50

If your intention is to learn make the agent learn which has the min arbitrary value, then you would need to modify your rewards a bit.

The current reward structure provides the incentive to just move to a stage where it gets a reward.

For example, if it is at state 0, it gets the same reward to go to either state 2 or state 3, since both of them have a higher inverse value.

To make the agent learn to move to state 2, you would have to provide it with more incentives to go to state 2.

def reward(s,a,s_dash):
if s_dash == 2:
return 5
elif inverse_values_for_states[s]<inverse_values_for_states[s_dash]:
return 1
elif inverse_values_for_states[s]>inverse_values_for_states[s_dash]:
return -1
else:
return 0


I tried using this and it converges to 2. This is a hard-coded version, but I guess you get the idea.

• It's worse than you suggest. The OP's reward structure encourages the smallest possible incremental improvement on each action, because then it is possible for it to receive maximum rewards before finishing. It is better to score $[1,1,1,-1,1,1,1,-1....]$ starting from the worst state than score $[1,0,0...]$ and this is shown by the OP's converged values. Feb 11, 2022 at 8:25