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.
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
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.
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.