# Is my understanding of the differences between MDP, Semi MDP and POMDP correct?

I just wanted to confirm that my understanding of the different Markov Decision Processes are correct, because they are the fundamentals of reinforcement learning. Also, I read a few literature sources, and some are not consistent with each other. What makes the most sense to me is listed below.

### Markov Decision Process

All the states of the environment are known, so the agent has all the information required to make the optimal decision in every state. We can basically assume that the current state has all information about the current state and all the previous states (i.e., the Markov property)

### Semi Markov Decision Process

The agent has enough information to make decisions based on the current state. However, the actions of the agent may take a long time to complete, and may not be completed in the next time step. Therefore, the feedback and learning portion should wait until the action is completed before being evaluated. Because the action takes many time steps, "mini rewards" obtained from those time steps should also be summed up.

Example: Boiling water

• State 1: water is at 23 °C
• Action 1: agent sets the stovetop at 200 °C
• Reward (30 seconds after, when water started to boil):
• +1 for the fact that water boiled in the end, but -0.1 reward for each second it took for the water to start boiling.
• So, the total reward was -1.9 (-2.9 because the water did not boil for 29 seconds, then +1 for water boiling on 30th second)

### Partially Observable Markov Decision Process

The agent does not have all information regarding the current state, and has only an observation, which is a subset of all the information in a given state. Therefore, it is impossible for the agent to truly behave optimally because of a lack of information. One way to solve this is to use belief states, or to use RNNs to try to remember previous states to make better judgements on future actions (i.e., we may need states from the previous 10 time steps to know exactly what's going on currently).

Example

We are in a room that is pitch black. At any time instant, we do not know exactly where we are, and if we only take our current state, we would have no idea. However, if we remember that we took 3 steps forward already, we have a much better idea of where we are.

Are my above explanations correct? And if so, isn't it possible to also have Partially Observable Semi Markov Decision Processes?

• Yes that all seems pretty much correct. Of course, your descriptions are somewhat informal, so there might be minor details to nitpick about... but the core differences between the three as you described them are fine. – Dennis Soemers Oct 30 '18 at 16:44
• Thanks for the reply Dennis! So in theory, it is possible to have a partially observable semi markov decision process? Also, do you by any chance know any good textbooks/references I can refer to, to ensure my descriptions are 100% correct. Thanks again! – Rui Nian Oct 30 '18 at 18:06
• Correct, that would be possible. As for POMDPs.. don't know any particular reference by heart, but they're all over really, they're everywhere. As for SMPDs, I believe one of the "original" references for them is: papers.nips.cc/paper/… . Another good one is: sciencedirect.com/science/article/pii/S0004370299000521 (the latter actually proposes an "Options framework", which is more general than SMDPs, but much more popular these days). – Dennis Soemers Oct 30 '18 at 18:50