Q-learning problem wrong policy

Question

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 !

Answer 1

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.