# Value iteration does not converge when using Q learning

I have a simple game and want my agent to play it with a help of reinforcement learning. We have a board and a value in each cell. The goal is to go from start to finish point with the highest score (agent can go in 4 available directions: up, down, left, right) within given moves (distance from start to finish with no extra steps). The issue is that my extracted policy doesn't give me the correct result (green - starting point; red - finish cell) So I want to clarify all the parameters that I chose for my algorithm:

1. States space size (number of cells on the board): 4x4 = 16
2. Actions space size (one for each direction): 4
3. Probability of the next state (equal for each available next state): 1/4 = 0.25 (for central cells); 1/3 = 0.33 (for border cells); 1/2 = 0.5 (for corner cells)
4. Reward: value of the cell or -1 if we no longer can reach finish from that point.

But my value function does not want to converge (and it always has to), so probably the issue with values I provide to it. Help me figure out what major mistake did I miss.

The code for the value function calculation looks like this one

def value_iteration(states_space_size, game):
v = np.zeros(states_space_size)
max_iterations = 1000
eps = 1e-20
last_dif = float('inf')

for i in range(max_iterations):
prev_v = np.copy(v)  # last value function
for s in range(states_space_size):  # 16: size of the board
q_sa = []
for a in range(len(DIRECTIONS)):  # 4: up, down, left, right
next_states_rewards = []
for next_sr in get_available_states_from(s, a, game):
# (probability, next_state, reward) of the states you can go from (s,a)
p, s_, r = next_sr
next_states_rewards.append((p*(r + prev_v[s_])))
# store the sum of rewards for each pair (s,a)
q_sa.append(np.sum(next_states_rewards))
# choose the max reward of (s,a) pairs and put it on the actual value function for STATE s
v[s] = max(q_sa)

# check convergence
if np.abs(np.abs(np.sum(prev_v - v)) - last_dif) < eps:
print('Value-iteration converged at iteration %d' % (i+1))
break
last_dif = np.abs(np.sum(prev_v - v))
return v


In case you want to refer to the whole listing here is the link

• What is the "correct result"? According to the rewards that you have assigned, being in the states (2, 0), (2, 1), and (1, 1), is better than getting to the end state. So the policy will continue to stay in those states that have high reward. In order to get the desired result, try making each state (excluding the end state) have a non-positive reward. This way, the policy extracted from value iteration will not get stuck in an infinite loop. Dec 6, 2018 at 16:59
• You're missing a learning rate and a discount factor in your Q-learning update rule. Both are necessary for convergence. Dec 10, 2018 at 21:45
• I need a Bellman equation to maximize cumulative result for my rewards? Where should I apply it? Is it missing from the code above or it should be done on a policy extraction step? Dec 11, 2018 at 19:59
• Since all of the rewards are non-negative, you can convert all of the rewards r for each state s (excluding the "end" state) to r'(s) = -d/(r(s)+c) for positive constants c and d. For example, if c = d = 1 then r'(s) = -1/(r(s)+1). Dec 12, 2018 at 15:44
• This is being automatically flagged as low quality, probably because it is so short. At present it is more of a comment than an answer by our standards. Can you expand on it? You can also turn it into a comment. Dec 12, 2018 at 21:31

Ok, so I've slightly modified the initial example and the code below gives me working policy

states_space_size = 16  # 4x4 size of the board
actions_space_size = len(DIRECTIONS)
QSA = np.zeros(shape=(states_space_size, actions_space_size))
max_iterations = 80
gamma = 1  # discount factor
alpha = 0.9  # learning rate
eps = 0.99  # exploitation rate
s = 0  # initial state
for i in range(max_iterations):
# explore the world?
a = choose_an_action(actions_space_size)
# or not?
if random.random() > eps:
# which criterion on decreasing epsilon
a = np.argmax(QSA[s])

r, s_ = perform_action(s, a, game)
qsa = QSA[s][a]
qsa_ = np.argmax(QSA[s_])
QSA[s][a] = qsa + alpha*(r + gamma*qsa_ - qsa)

# change state
s = s_

# converge criterion instead of max iterations?
print(QSA)


I have introduced learning rate variable (how quickly to forget older results) and exploration/exploitation rate (choose random actions vs following existing policy) and seems like resulting policy gives the desired path

• SO is different from other online fora that you might have used in the past. Specifically, the answer box is reserved for answers, not additional questions or edits to your original question. If there are additional things that you would like to ask, you can ask a new question. Please see the help center for more information.
– Sycorax
Dec 12, 2018 at 21:14
• @Sycorax thanks, I've updated the answer to contain only working result Dec 12, 2018 at 21:24
• @MostWanted why is it qsa_ = np.argmax(QSA[s_]) instead of qsa_ = max(QSA[s_])? Mar 16, 2021 at 9:57