# 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 – RewCie May 6 '20 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++) – Prabal Dev May 6 '20 at 14:45
• if you don't mind writing the algorithm.... – RewCie May 6 '20 at 14:50

## 1 Answer

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.