When is the Markov decision process not adequate for goal-directed learning tasks?

Question

In the book Reinforcement Learning: An Introduction (Sutton and Barto, 2018). The authors ask

Exercise 3.2: Is the MDP framework adequate to usefully represent all goal-directed learning tasks? Can you think of any clear exceptions?

I thought maybe a card game would be an example if the state does not contain any pieces of information on previously played cards. But that would mean that the chosen state leads to a system that is not fully observable. Hence, if I track all cards and append it to the state (state vector with changing dimension) the problem should have the Markov Property (no information on the past states is needed). This would not be possible if the state is postulated as invariant in MDP.

If the previous procedure is allowed, then it seems to me that there are no examples where the MDP is not appropriate.

I would be glad if someone could say if my reasoning is right or wrong. What would be an appropriate answer to this question?

Answer 1

Background

The Markov Decision Process is an extension of Andrey Markov's action sequence that visualize action-result sequence possibilities as a directed acyclic graph. One path through the acyclic graph, if it satisfies the Markov Property is called a Markov Chain.

The Markov Property requires that the probability distribution of future states at any point within the acyclic graph be evaluated solely on the basis of the present state.

Markov Chains are thus a stochastic model theoretically representing one of the set of possible paths. And the action-result sequence is a list of state transitions corresponding to actions chosen solely by each action's previous state and the expectations that the expected subsequent state will most probably lead to the desired outcome.

Andrey Markov based his work on Gustav Kirchhoff's work on spanning trees, which is based on Euler's initial directed graph work.

The Exercise

Exercise 3.2 was given with two parts.

Is the MDP framework adequate to usefully represent all goal-directed learning tasks?

Can you think of any clear exceptions?

The first question is subjective in that it inquires about usefulness but does not define what it means. If "useful" means the MDP will improve the chances of achieving a goal over a random selection of action at each state, then except in no win scenarios or the most contrived case where all actions have equal distribution of probable results, then the MDP is useful.

If "useful" means optimal, then there are other approaches, with additional complexity and requiring additional computing resources that will improve odds of goal achievement. These other approaches overcome one or more of the limitations of pure MDP.

Advancements and Alternatives

Advancements made to MDP and alternatives to MDP, which number in the hundreds, include these.

• Logical detection of the infeasibility of goal achievement (no win scenario)
• Calculation of probabilities when only partial information is available about the current state
• Invocation of the decision at any point (continuous MDP used in real time systems)
• Probabilities are not known and must be learned from past experience where simple Q-learning is employed
• Past experience is used by statistically relating action-state details to generalizations derived from past action-result sequences or such information acquired or shared
• The action-state decisions, made within the context of an unknown system of changing or not reliably applied rules, can be used to tune a set of fuzzy rules in a fuzzy logic container and utilize fuzzy inference in the decisions
• Bluff and fraud detection

Card Games

Game play for a typical card game could make use of MDP, so MDP would be strictly useful, however not optimal. Some of the above decisioning features would be more optimal, particularly those that deals with unknowns and employ rules, since the card game has them.

Random or Decoupled

Two obvious cases are (a) a truly randomized action-result world where goal achievement has equal probability no matter the sequence of moves or (b) a scenario where goal achievement is entirely decoupled from actions the actor can take. In those cases, nothing will be useful with regard to the particular objective chosen.

Challenge

The way to best learn from the exercise, though, is to find a scenario where MDP would be useless and one of the above listed Advancements and Alternatives would be required rather than simply preferred. If you look at the list, there will be some cases that will eventually come to mind. I suggest you think it through, since the goal is to learn from the book.

Answer 2

According to http://tianlinliu.com/files/notes_exercise_RL.pdf, MDP may not be feasible to multi-target tasks.

In contrast, EA-based methods like NSGA-II, NSGA-III, can solve the multi-target tasks.

And also, tasks that need more than one state to predict the next action are also not suitable to use MDP. For example, when we predict the next action a stranger who just meets you at a party will do, we need to consider all the behaviors he did in the past minutes. It will be more suitable than using the MDP way, which will simply label the stranger is a "good" guy or "bad" guy (or a continuous number between good or bad).