Skip to content

MDP Practice – Waterslide

You’ve decided to take a trip with your friends to the grid-world water park. Yay! The grid-world water park is not the most exciting thing in the world - there is a single waterslide that is composed of two ladder squares and two slide squares (marked with vertical bars and squiggly lines respectively). In this water park, you can move from any square to any neighboring square, unless the current square is a slide in which case it must move forward one square along the slide. The actions are denoted by arrows between squares on the map and all deterministically move the agent in the given direction. The agent cannot stand still: it must move on each time step. Rewards are also shown below: it’s super fun to go down the water slide (+2), kind of hard to climb the rungs of the ladder (-1), and neutral (+0) otherwise. The time horizon is infinite; this MDP goes on forever.

+--------+--------+--------+--------+--------+--------+
|        | Ladder | Ladder | Slide  | Slide  |        |
|       0↔-1     0↔-1      →+2      →+2      →0       |
| [C]0   | [D]    | [E]    | [F]    | [G]    |    0   |
+----↕---+-----------------------------------+----↕---+
|    0   |                                   |    0   |
|        |                                   |        |
| [B]0   |                                   |    0   |
+----↕---+-----------------------------------+----↕---+
|    0   |        |        |        |        |    0   |
|       0↔0      0↔0      0↔0      0↔0      0↔0       |
| [A]    |        |        |        |        |        |
+--------+--------+--------+--------+--------+--------+

(a) How many (deterministic) policies 𝜋 are possible for this MDP? (think of how many actions can be taken from each state and how many states there are).

2 Slide States: 1 action possible 1 Corner State: 1 action possible 2 Ladder States: 2 actions possible 9 Other States: 2 actions possible

slide = 2
corner = 1
ladder = 2
other = 9

total_policy = 1^(slide + corner) * 2^(ladder + other)

(b) Fill in the blank cells of this table with values that are correct for the corresponding function, discount, and state. Hint: You should not need to do substantial calculation here. (Note: Vt(s) is the time-limited value of state s, if our MDP were to terminate after t timesteps.)

\(\gamma\) \(s = A\) \(s = E\)
\(V_{3}(s)\) 1.0 0 +4
\(V_{10}(s)\) 1.0 +2 +4
\(V_{10}(s)\) 0.1 0 +2.2
\(Q_{1}(s, west)\) 1.0 N/A 0
\(Q_{10}(s, west)\) 1.0 N/A +3
\(V^{*}(s)\) 1.0 \(+ \infty\) \(+ \infty\) (Maximizes use of slide, infinite rewards)
\(V^{*}(s)\) 0.1 0 \(<+2.2\) (Uses slide initially, rewards diminish substantially)