<p>You have a simple mistake in your TD Error function:</p>

<pre><code>TD_error = reward + gamma * max(Q[next_state]) - Q[state][action]
</code></pre>

<p>You have made <code>Q[next_state]</code> a Python <code>dict</code>, so this will take the maximum <em>key</em> 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 <code>1.0</code> when stepping from adjacent grid points to the positive terminal state.</p>

<p>The correct code is:</p>

<pre><code>TD_error = reward + gamma * max(Q[next_state].values()) - Q[state][action]
</code></pre>

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

CC BY-SA 4.0
2020-01-22T15:29:48.123Z
2020-01-22T15:29:48.123Z
Neil Slater
<p>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. </p>

<p><a href="https://i.sstatic.net/NITn0.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/NITn0.png" alt="enter image description here"></a></p>

<p>The code that I am running is shown below:</p>

<pre><code># 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) &lt; 0:
            return (state, grid[row][col])

    if action == 1: # down

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

    if action == 2: # left

        if (col - 1 &lt; 0):
            return (state, grid[row][col])

    if action == 3: # right

        if (col + 1 &gt; 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 &lt; 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])
</code></pre>

<p>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. </p>

<p>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. </p>

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

<p>(0,0): {0: 2.0, 1: 2.9, 2: 2.9, 3: 2.9}</p>

<p>(0,1): {0: 2.9, 1: 2.0, 2: 2.9, 3: 2.9}</p>

<p>(2,0): {0: 2.9, 1: 2.9, 2: 2.9, 3: 2.9}</p>

<p>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. </p>

<p>Would anyone be able to help ? Thank you so much !</p>

CC BY-SA 4.0
2020-01-22T15:19:08.227Z
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 ?.
Brale
CC BY-SA 4.0
2020-01-22T15:22:23.327Z
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) ?
calveeen
CC BY-SA 4.0
2020-01-22T15:24:31.630Z
max considers keys of dict not values. You are taking max action, it returns number 3 every time instead of a Q value.
Brale
<reinforcement-learning><q-learning>
Q-learning problem wrong policy
calveeen
# Q-learning problem wrong policy

(Asked by: username_0 on 2020-01-22)

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 !

**Tags:** reinforcement-learning, q-learning

> **Comments:**
> **username_1**: 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 ?.  
> **username_0**: 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) ?  
> **username_1**: max considers keys of dict not values. You are taking max action, it returns number 3 every time instead of a Q value.  

---

## 1 answers

### Answer by username_2 on 2020-01-22. Score: 1 | Accepted answer

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.


---

