2
$\begingroup$

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?

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

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])
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.