# How to get P and R values for a Markov Decision Process grid world problem?

Take the canonical 3x4 grid world example below. What would the P and R matrices look like for this problem? I know that P would be AxSxS, and R would be AxS, but I'm having a lot of trouble thinking about how exactly this works.

P should be 4 12x12 matrices if I'm not mistaken, one for each action (up, down,left,right). R should be a 4x12 matrix, but I'm not totally sure why...aren't there only 12 possible cells for which there is a reward?

I've tried a bunch of different values trying to figure this out using MDPToolbox, but I keep running into exceptions or math errors, so I'm clearly not understanding something.

Here's some example code:

# P = 4 12x12 matrices where each row's sum is 1.0
# R = 4x12 matrix where one cell has a reward of 1.0 and one a reward of -1.0
pi = mdptoolbox.PolicyIteration(P ,R, 0.9)
pi.run()
print(pi.policy)


This gives me a math domain error, so something is not right.

What exactly should the P and R matrices look like for this grid world problem?

• Yes, there should be a transition matrix for each action. The problem doesn't make sense other wise. – Math1000 May 17 '18 at 20:34

I started looking at that the Python MDPToolbar tonight, so someone correct me if I get any of this wrong. What you have written sounds more or less correct to me. Maybe you just have a simple bug or something. But here is how I went about it:

You have four actions that can be taken in each cell: left, right, forward, and back. In your case I guess technically its 3 actions, but you can just give the back action 0.0 probability.

P would have shape (4, 12, 12). Each P[action_index, :, :] grid would have rows that sum to 1.0. Each row represents being in one of the twelve states/cells. Each element in each row represents the transition probability of moving from the current row to a new row.

For example, consider this toy P[0, :, :] transition matrix for some action-A:

[[ 0.5, 0.5, 0.0], [ 0.1, 0.9, 0.0], [ 0.0, 0.0, 1.0]]

Looking at the second row, that indicates that I am currently in state #2 and after I execute action-A, I will end up in state #2 again with 0.9 probability or move to state #1 with 0.1 probability. See how to interpret that?

I wrote this function to generate a grid-world like your example and return the P and R matrices. (Hopefully no bugs....)

def run(func):
func()
return func

def grid_world_example(grid_size=(3, 4),
black_cells=[(1,1)],
white_cell_reward=-0.02,
green_cell_loc=(0,3),
red_cell_loc=(1,3),
green_cell_reward=1.0,
red_cell_reward=-1.0,
action_lrfb_prob=(.1, .1, .8, 0.),
start_loc=(0, 0)
):
num_states = grid_size[0] * grid_size[1]
num_actions = 4
P = np.zeros((num_actions, num_states, num_states))
R = np.zeros((num_states, num_actions))

@run
def fill_in_probs():
# helpers
to_2d = lambda x: np.unravel_index(x, grid_size)
to_1d = lambda x: np.ravel_multi_index(x, grid_size)

def hit_wall(cell):
if cell in black_cells:
return True
try: # ...good enough...
to_1d(cell)
except ValueError as e:
return True
return False

# make probs for each action
a_up = [action_lrfb_prob[i] for i in (0, 1, 2, 3)]
a_down = [action_lrfb_prob[i] for i in (1, 0, 3, 2)]
a_left = [action_lrfb_prob[i] for i in (2, 3, 1, 0)]
a_right = [action_lrfb_prob[i] for i in (3, 2, 0, 1)]
actions = [a_up, a_down, a_left, a_right]
for i, a in enumerate(actions):
actions[i] = {'up':a[2], 'down':a[3], 'left':a[0], 'right':a[1]}

# work in terms of the 2d grid representation

def update_P_and_R(cell, new_cell, a_index, a_prob):
if cell == green_cell_loc:
P[a_index, to_1d(cell), to_1d(cell)] = 1.0
R[to_1d(cell), a_index] = green_cell_reward

elif cell == red_cell_loc:
P[a_index, to_1d(cell), to_1d(cell)] = 1.0
R[to_1d(cell), a_index] = red_cell_reward

elif hit_wall(new_cell):  # add prob to current cell
P[a_index, to_1d(cell), to_1d(cell)] += a_prob
R[to_1d(cell), a_index] = white_cell_reward

else:
P[a_index, to_1d(cell), to_1d(new_cell)] = a_prob
R[to_1d(cell), a_index] = white_cell_reward

for a_index, action in enumerate(actions):
for cell in np.ndindex(grid_size):
# up
new_cell = (cell[0]-1, cell[1])
update_P_and_R(cell, new_cell, a_index, action['up'])

# down
new_cell = (cell[0]+1, cell[1])
update_P_and_R(cell, new_cell, a_index, action['down'])

# left
new_cell = (cell[0], cell[1]-1)
update_P_and_R(cell, new_cell, a_index, action['left'])

# right
new_cell = (cell[0], cell[1]+1)
update_P_and_R(cell, new_cell, a_index, action['right'])

return P, R


I then ran the mpd.ValueIteration class on the matrices and got the following policy which seemed reasonable: (Note I converted the policy matrix from int's to strings to be interpretable.)

[['R', 'R', 'R', 'U'],
['U', 'U', 'U', 'U'],
['U', 'R', 'U', 'D']]


Finally, for reference here are what the actual P and R matrices could look like:

P:
array([[0.9, 0.1, 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. ],
[0.1, 0.8, 0.1, 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. ],
[0. , 0.1, 0.8, 0.1, 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. ],
[0. , 0. , 0. , 1. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. ],
[0.8, 0. , 0. , 0. , 0.2, 0. , 0. , 0. , 0. , 0. , 0. , 0. ],
[0. , 0.8, 0. , 0. , 0.1, 0. , 0.1, 0. , 0. , 0. , 0. , 0. ],
[0. , 0. , 0.8, 0. , 0. , 0. , 0.1, 0.1, 0. , 0. , 0. , 0. ],
[0. , 0. , 0. , 0. , 0. , 0. , 0. , 1. , 0. , 0. , 0. , 0. ],
[0. , 0. , 0. , 0. , 0.8, 0. , 0. , 0. , 0.1, 0.1, 0. , 0. ],
[0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0.1, 0.8, 0.1, 0. ],
[0. , 0. , 0. , 0. , 0. , 0. , 0.8, 0. , 0. , 0.1, 0. , 0.1],
[0. , 0. , 0. , 0. , 0. , 0. , 0. , 0.8, 0. , 0. , 0.1, 0.1]])
array([[0.1, 0.1, 0. , 0. , 0.8, 0. , 0. , 0. , 0. , 0. , 0. , 0. ],
[0.1, 0.8, 0.1, 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. ],
[0. , 0.1, 0. , 0.1, 0. , 0. , 0.8, 0. , 0. , 0. , 0. , 0. ],
[0. , 0. , 0. , 1. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. ],
[0. , 0. , 0. , 0. , 0.2, 0. , 0. , 0. , 0.8, 0. , 0. , 0. ],
[0. , 0. , 0. , 0. , 0.1, 0. , 0.1, 0. , 0. , 0.8, 0. , 0. ],
[0. , 0. , 0. , 0. , 0. , 0. , 0.1, 0.1, 0. , 0. , 0.8, 0. ],
[0. , 0. , 0. , 0. , 0. , 0. , 0. , 1. , 0. , 0. , 0. , 0. ],
[0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0.9, 0.1, 0. , 0. ],
[0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0.1, 0.8, 0.1, 0. ],
[0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0.1, 0.8, 0.1],
[0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0.1, 0.9]])
array([[0.9, 0. , 0. , 0. , 0.1, 0. , 0. , 0. , 0. , 0. , 0. , 0. ],
[0.8, 0.2, 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. ],
[0. , 0.8, 0.1, 0. , 0. , 0. , 0.1, 0. , 0. , 0. , 0. , 0. ],
[0. , 0. , 0. , 1. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. ],
[0.1, 0. , 0. , 0. , 0.8, 0. , 0. , 0. , 0.1, 0. , 0. , 0. ],
[0. , 0.1, 0. , 0. , 0.8, 0. , 0. , 0. , 0. , 0.1, 0. , 0. ],
[0. , 0. , 0.1, 0. , 0. , 0. , 0.8, 0. , 0. , 0. , 0.1, 0. ],
[0. , 0. , 0. , 0. , 0. , 0. , 0. , 1. , 0. , 0. , 0. , 0. ],
[0. , 0. , 0. , 0. , 0.1, 0. , 0. , 0. , 0.9, 0. , 0. , 0. ],
[0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0.8, 0.2, 0. , 0. ],
[0. , 0. , 0. , 0. , 0. , 0. , 0.1, 0. , 0. , 0.8, 0.1, 0. ],
[0. , 0. , 0. , 0. , 0. , 0. , 0. , 0.1, 0. , 0. , 0.8, 0.1]])
array([[0.1, 0.8, 0. , 0. , 0.1, 0. , 0. , 0. , 0. , 0. , 0. , 0. ],
[0. , 0.2, 0.8, 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. ],
[0. , 0. , 0.1, 0.8, 0. , 0. , 0.1, 0. , 0. , 0. , 0. , 0. ],
[0. , 0. , 0. , 1. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. ],
[0.1, 0. , 0. , 0. , 0.8, 0. , 0. , 0. , 0.1, 0. , 0. , 0. ],
[0. , 0.1, 0. , 0. , 0. , 0. , 0.8, 0. , 0. , 0.1, 0. , 0. ],
[0. , 0. , 0.1, 0. , 0. , 0. , 0. , 0.8, 0. , 0. , 0.1, 0. ],
[0. , 0. , 0. , 0. , 0. , 0. , 0. , 1. , 0. , 0. , 0. , 0. ],
[0. , 0. , 0. , 0. , 0.1, 0. , 0. , 0. , 0.1, 0.8, 0. , 0. ],
[0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0.2, 0.8, 0. ],
[0. , 0. , 0. , 0. , 0. , 0. , 0.1, 0. , 0. , 0. , 0.1, 0.8],
[0. , 0. , 0. , 0. , 0. , 0. , 0. , 0.1, 0. , 0. , 0. , 0.9]])

R:
array([-0.02, -0.02, -0.02,  1.  , -0.02, -0.02, -0.02, -1.  , -0.02,
-0.02, -0.02, -0.02])
array([-0.02, -0.02, -0.02,  1.  , -0.02, -0.02, -0.02, -1.  , -0.02,
-0.02, -0.02, -0.02])
array([-0.02, -0.02, -0.02,  1.  , -0.02, -0.02, -0.02, -1.  , -0.02,
-0.02, -0.02, -0.02])
array([-0.02, -0.02, -0.02,  1.  , -0.02, -0.02, -0.02, -1.  , -0.02,
-0.02, -0.02, -0.02])