Consider the following snake and ladders game as depicted in the figure below

Problem 1 : Markov Reward Process
Consider the following snake and ladders game as depicted in the figure below.
• Initial state is S and a fair four sided die is used to decide the next state at each time
• Player must land exactly on state W to win
• Die throws that take you further than state W leave the state unchanged
(a) Identify the states, transition matrix of this Markov process. (1 point)
(b) Construct a suitable reward function, discount factor and use the Bellman equation for the
Markov reward process to compute how long does it take “on average” (the expected number
of die throws) to reach the state W from any other state. (4 points)
Problem 2 : Markov Decision Process
A production facility has N machines. If a machine starts up correctly in the morning, it renders
a daily revenue of 1$. A machine that does not start up correctly, needs to be repaired. A
visit by a repair man costs N
2
$ per day and he repairs all broken machines on the same day.
The repair cost is a lump-sum amount and does not depend on the number of machines that
is repaired. A machine that has been repaired always starts up correctly the next day. The
number of machines that start up correctly the next day depends on the number of properly
working machines at present day and is governed by the probability distribution given in the
table below, where m stands for the number of (presently) working machines and n stands for
the number of ones that would start up correctly the next day. The goal for the facility manager
Assignment № 1 Page 1