# Q-learning problem wrong policy

I am coding out a simple 4x4 grid game whereby the agent starts at a particular state and his aim is to reach the terminal state. The agent is supposed to avoid traps along the way and reach the end goal with high reward. The below picture illustrates the environment.

The code that I am running is shown below:

# 4x4 Grid
import random

gamma = 1
grid = [[-0.1 for i in range(4)] for j in range(4)]
episodes = 500000
epsilon = 1 # start greedy
decay = 0.999
min_epsilon = 0.1
alpha = 0.65
# set terminal states
grid[1][0] = -1
grid[2][2] = -1
grid[0][3] = 1

# Set up Q tables
# 0: up, 1: down, 2: left, 3: right
# Q = {(0,0): {0: z, 1: x, 2: c, 3: v}, ... }}
Q = {}

# 4 rows
for row in range(4):
# 4 columns
for column in range(4):
Q[(row,column)] = {}
# 4 actions
for k in range(4):
Q[(row,column)][k] = 0

def isTerminal(state):
if state == (1,0) or state == (2,2) or state == (0,3):
return True
return False

def get_next_state_reward(state, action):

row = state[0]
col = state[1]
#print(row, col)
if action == 0: # up
# out of grid
if (row - 1) < 0:
return (state, grid[row][col])

if action == 1: # down

# out of grid
if (row + 1) > len(grid) - 1:
return (state, grid[row][col])

if action == 2: # left

if (col - 1 < 0):
return (state, grid[row][col])

if action == 3: # right

if (col + 1 > len(grid[row]) - 1):
return (state, grid[row][col])

if action == 0:

row -= 1
return ((row,col), grid[row][col])

if action == 1:

row += 1
return ((row,col), grid[row][col])

if action == 2:

col -= 1
return ((row,col), grid[row][col])

if action == 3:

col += 1
return ((row,col), grid[row][col])

state_visit = {}
for row in range(4):
# 4 columns
for column in range(4):
state_visit[(row,column)] = 0

for episode in range(episodes):

# let agent start at start state
state = (3,0)

while not isTerminal(state):

r = random.uniform(0,1)

if r < epsilon:
action = random.randint(0,3)
else:
action = max(Q[state], key=lambda key: Q[state][key])

next_state, reward = get_next_state_reward(state, action)

TD_error = reward + gamma * max(Q[next_state]) - Q[state][action]

Q[state][action] = Q[state][action] + alpha * TD_error

state = next_state

state_visit[next_state] += 1
epsilon = max(min_epsilon, epsilon*decay)

#input()

policy = {}
# get optimal policies for each state
for states in Q:
policy[states] = max(Q[states], key=lambda key: Q[states][key])


When I finish running the algorithm however, I am unable to achieve the optimal policy no matter how many tweaks I do to the number of episodes, or epsilon decay, or the alpha value.

Particularly, the Q values that I attain for state (2,0), (0,1) and (0,0) have Q values that are equal values for three directions except for the last direction which brings the agent to the terminal state.

For example, these are the Q-values that I get for state (0,0), (0,1) and (2,0) respectively.

(0,0): {0: 2.0, 1: 2.9, 2: 2.9, 3: 2.9}

(0,1): {0: 2.9, 1: 2.0, 2: 2.9, 3: 2.9}

(2,0): {0: 2.9, 1: 2.9, 2: 2.9, 3: 2.9}

I am not sure why the Q-values for the 3 directions should be the same because each extra step that the agent takes incurs a negative reward.

Would anyone be able to help ? Thank you so much !

• what does max(Q[next_state]) do ?. Q[next_state] returns a dict with actions as keys and Q values as values. So you are taking max action (3) every time instead of a Q value ?. Jan 22 '20 at 15:19
• yes, Q[next_state] returns a dictionary that maps each action to it's q value for that state. I am taking the highest possible Q value for the next state in the update equation. Why does it return action (3) ? Jan 22 '20 at 15:22
• max considers keys of dict not values. You are taking max action, it returns number 3 every time instead of a Q value. Jan 22 '20 at 15:24

You have a simple mistake in your TD Error function:

TD_error = reward + gamma * max(Q[next_state]) - Q[state][action]


You have made Q[next_state] a Python dict, so this will take the maximum key which is 3 for all your Q table entries. This is why you end up with values very close to 3 at the end, which is impossible for your problem, the maximum return will be 1.0 when stepping from adjacent grid points to the positive terminal state.

The correct code is:

TD_error = reward + gamma * max(Q[next_state].values()) - Q[state][action]


Alternatively, since your actions are all numeric, you could use a list instead of a dict in your Q table.