Q table not converging for an arbitrary experiment

Question

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)

Answer 1

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.