2
$\begingroup$

In the book Reinforcement Learning: An Introduction (Sutton & 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?

$\endgroup$
  • 2
    $\begingroup$ You do know that if you complete a chapter's questions in self-study, and send to the author, that he will reply with the official answers? I have done so - it took a few weeks, but I got a reply. $\endgroup$ – Neil Slater Oct 18 '18 at 14:05
  • $\begingroup$ Nice :D. Is there a collection for the answers? I do not want to bother the authors with all my trivial questions :D. They did such a great job in writing this book and releasing it for free on the internet. But I will consider writing them if I fail to find a good answer. BTW is there an IRC chat for RL? $\endgroup$ – MrYouMath Oct 18 '18 at 14:13
  • 2
    $\begingroup$ There are collection of code exercises e.g. at github.com/ShangtongZhang/… (not sure how official that is), but as far as I know, not published answers for the maths & text-based questions. I am not sure, but one likely scenario is that he does not want collections of answers easily available online, because it encourages students to think less and take the easy route. If you complete a whole chapter and send your answers, this is not trivial, and supports the way the author has requested here: incompleteideas.net/book/solutions-2nd.html $\endgroup$ – Neil Slater Oct 18 '18 at 15:03
  • $\begingroup$ I have found something (fumblog.um.ac.ir/gallery/839/…), but the answer does not convince me. $\endgroup$ – MrYouMath Oct 18 '18 at 16:18
  • $\begingroup$ His answer is technically correct but not very interesting (since a vector is inherently not optimisable without a metric - and the metric would be your reward), and there are other areas worth discussing, such as your thoughts around partial information. $\endgroup$ – Neil Slater Oct 18 '18 at 16:25
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.