1
$\begingroup$

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)

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ – RewCie May 6 '20 at 8:50
  • $\begingroup$ @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++) $\endgroup$ – Prabal Dev May 6 '20 at 14:45
  • $\begingroup$ if you don't mind writing the algorithm.... $\endgroup$ – RewCie May 6 '20 at 14:50
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.