Formulate a MDP for a problem given below

Question

Can someone help me to formulate an MDP for the below problem ?.

Problem Definition

Bunny wakes up in a strange room with 2 doors; one on the left, and one on the right. In front of him is a map of the building, laying out clearly what lies behind each door. Behind one of the doors is a room with the way outside, and behind the other one a room with a hungry tiger. Bunny does not like tigers. Especially hungry ones.

• Consider the control problem where the current state is specified by the current room Bunny is in, and the actions Bunny can take are to move through a door to another room. Assume that there are 2 doors in the starting room, each leading to its own room, and that one of these other rooms (specifically the one on the left) has a single door that leads to the exit, while the other one (specifically the one on the right) has a tiger in it. Moreover, assume that Bunny has full knowledge of these details but that there is a 10% chance that when trying to move through one of the doors, he gets confused and goes through the other door instead. Lastly, assume that the episode does not end when Bunny enters the room with the tiger.

Questions

• Formulate a Markov Decision Process (MDP) for the problem of con- trolling Bunny’s actions in order to avoid the tiger and exit the building. (Give the transition and reward functions in tabular format, or give the transition graph with rewards).

I would like to know, is there any procedures or rules, that needs to be considered before formulating an MDP for a problem

What i have done so far

• State A - Starting room

• State B - Room with an exit door

• State C - Room that has a tiger in it

I don't know how to proceed further.

Answer 1

I would like to know, is there any procedures or rules, that needs to be considered before formulating an MDP for a problem

For a simple problem like this, I would do the following:

• List the states.
  • You have missed a state - the terminal state of leaving the building
• Mark terminal states
  • In this case, only exiting the building is a terminal state. The hungry tiger doesn't actually do anything to Bunny, the problem states that the MDP should just continue.
• List the actions possible in each state.
  • In your starting diagram, you do not show actions, and this is already limiting your ability to express the MDP.

• List the possible transitions and probabilities of them

  • For most action choices in the example, there are two possible outcomes from each action. The problem doesn't actually describe what happens when there is only one door, for the room with the tiger, but it seems reasonably safe to say that it is not possible for Bunny to get confused when there is only one door, so exiting the room with the tiger is one exception.

• Assign rewards. Rewards should relate to the goals stated in the problem definition. Negative rewards for things to avoid happening (or in general to avoid time wasting). Positive rewards for reaching desired targets.

  • In your case you have two goals - avoid tiger and exit building. There does not appear to be any time constraint.

Typically you would show action choices as labelled arrows going from states to an action node (usually just a small solid circle) where the state transitions then take effect, with further arrows labelled with probabilities going to states. So State A should have two arrows going out "choose left door" and "choose right door", then these choices will branch again - "choose left door" will go to state B with p=0.9 and state C with p=0.1.

You have some free choices over where to put reward labels, and there are a few different standard approaches. In this case, I would put the non-zero rewards on the state transitions that lead to goal-affecting states. E.g. maybe a +1 reward on the state transition from B taking the exit door and ending up outside. Note that for both the exit and the room with the tiger, that there are two possible ways to get to them due to the random transitions (thanks to Bunny getting confused).

Note there are no actions, and no possibility of different transitions, where Bunny starts in state C and ends up in state C on the next timestep. I think you are confusing state C as being a terminal state - although this is understandable as some encounters with hungry tigers in the real world could well be terminal, the problem clearly states that everything just carries on for Bunny if he encounters the tiger. It is just something he wants to avoid. If he ends up in state C, then he still has an action he can take to go through the door. When he takes this action, he cannot "get confused" and pick the wrong door, so should always end up in state B with p=1.0.

If you decide to draw a transition diagram, you have free choice of layout. There is no fixed approach for this, and for many MDPs it may not be possible to draw a nice 2D diagram. However, in your case, it is definitely possible to layout the states in a simple 2D arrangement. A good place to start would be to place the states in locations that correspond to the imaginary room map. Leave plenty of space initally, as the states do not link directly (as you have started), but link via action nodes which themselves branch to the next state.

I hope this enough guidance for you to complete the problem by yourself. Solving the remainder on your own will be much better for your learning than turning it into a worked example here.