On the Signiicance of Markov Decision Processes
Formulating the problem facing an intelligent agent as a Markov decision process (MDP) is increasingly common in artiicial intelligence , reinforcement learning, artiicial life, and artiicial neural networks. In this short paper we examine some of the reasons for the appeal of this framework. Foremost among these are its generality, simplicity, and emphasis on goal-directed interaction between the agent and its environment. MDPs may be becoming a common focal point for diierent approaches to understanding the mind. Finally, we speculate that this focus may be an enduring one insofar as many of the eeorts to extend the MDP framework end up bringing a wider class of problems back within it. Sometimes the establishment of a problem is a major step in the development of a eld, more important than discovery of solution methods. For example, the problem of supervised learning has played a central role as it has developed through pattern recognition, statistics, machine learning and artiicial neural networks. Regulation of linear systems has practically deened the eld of control theory for decades. To understand what has happened in these and other elds it is essential to track the origins, development, and range of acceptance of particular problem classes. Major points of change are marked sometimes by a new solution to an existing problem, but just as often by the promulgation and recognition of the signiicance of a new problem. Now may be one such time of transition in the study of mental processes, with Markov decision processes being the newly accepted problem. Markov decision processes (MDPs) originated in the study of stochastic optimal control (Bellman, 1957) and have remained the key problem in that area ever since. In the 1980s and 1990s, incompletely known MDPs were gradually recognized as a natural problem formulation for reinforcement learning (e. Recognizing the common problem led to the discovery of a wealth of common algorithmic ideas and theoretical analyses. MDPs have also come to be widely studied within AI as a new, particularly suitable kind of planning problem, e.g., as in decision-theoretic planning (e.g., Dean et al., 1995), and in conjunction with structured Bayes nets (e.g., Boutilier et al., 1995). In robotics, artiicial life, and evolutionary methods it is less common to use the language and mathematics of MDPs, but again the problems considered are well expressed in MDP terms. Recognition of this