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) gives 3 np.argmax(Q) gives 2 np.argmax(Q) gives 2 np.argmax(Q) gives 2
All of the states should give argmax as 2 (which is actually the index[state] of the minimum value).
when I increase steps to 1000 and episodes to 50,
np.argmax(Q) gives 3 np.argmax(Q) gives 0 np.argmax(Q) gives 1 np.argmax(Q) 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 $\endgroup$
episodesspecify the stop value for generating the integers.
episodeis like a candidate element (i) of that vector. So, it will loosely translate as
for(int episode=0; episode<episodes.size();episode++)$\endgroup$