In Sutton/Barto's book on Introduction to Reinforcement Learning, they introduced the idea of MDP and its advantages to Reinforcement Learning early on.
My questions are:
I would like to ask your insights and intuition on this. Thanks
The concepts of states, actions, state transitions and rewards all seem kind of necessary, I don't see how Reinforcement Learning can really make sense without those (though there is some room for simplification, e.g. an RL problem with only a single state could be viewed as a Multi-Armed Bandit problem).
So, when you say "non-MDP" in your question, I'll assume that to mean that the Markov assumption is violated. This basically means that the current state does not provide sufficient information for determining an optimal policy / history is important / the entire sequence of all past states and actions are relevant / there is partial observability. Under that assumption:
- We still CAN do RL on a system that is non-MDP, right?
Yes, but you will for example lose theoretical guarantees for certain algorithms to converge to optimal solutions. In practice you'll probably want to take extra steps in your algorithms to improve performance. For example, you may want to add some memory to your algorithm by replacing your state observations with a concatenation of the last $n$ state observations, instead of just a single state observation.
- What advantages can there be if a task can be described by MDP vs non MDP?
The advantage of knowing that your task can be described as an MDP is that you can afford to use simpler algorithms / have theoretical proofs telling you that your solution will eventually converge to an optimal solution. The advantage of a non-MDP is... well, you can describe problems which can otherwise not be described because they don't fit in the MDP framework (for example an environment with partial observability, which can for example be the case if you have a robot with a first-person view from its camera, as opposed to a top-down view of the entire environment).
- How will I know if a task can be described by an MDP? Is there a statistical test to know this?
Not really. It will probably often be obvious if it mostly fits the general framework (can you define States, Actions, Rewards, do you have discrete time-steps which correspond to decision-points for your agent?). Though sometimes this also may not be obvious, sometimes there's not an obvious direct translation, but it's still possible if you're clever about your formulation.
On top of that, the Markov property is very important for the problem to truly be an MDP. Does a single observation of the state tell you everything you need to know? If yes, the Markov property is satisfied. Otherwise, it's violated (for example if you can't see everything that's relevant due to camera angle, or if you can't see the velocity/direction in which an object is moving because you're only observing a single frame).
