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

Question

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?

Answer 1

Yes, the core differences between the different categories of problems are correct as you've described them.

For SMDPs, I'd like to remark that the water boiling example is maybe not the best. That looks more like an example of "delayed rewards", but not one of "durative actions": when the agent takes that action to raise the temperature, it takes some time before the reward comes in, but the agent's action itself doesn't take that much time. The agent could maybe do something else in the meantime. Delayed rewards are not restricted to SMDPs, they can also show up in regular MDPs (you just have to make sure to include some data in the state representation to indicate the time since the temperature was set or something like that, such that the Markov property is not violated).

A typical example of an SMDP with durative actions would be a grid with rooms, split by walls but connected by smaller doors inside those walls. A single "primitive" action would just take a single step in the larger grid, but longer-duration "macro-actions" would make the agent navigate from somewhere within a room to one of the doors "on auto-pilot". This would still take as much time as it would to navigate explicitly in multiple smaller actions, but the larger more complex behaviour being encapsulated in a single "macro-action" can speed up learning.