A Survey of solution techniques for the partially observed Markov decision process <s> Introduction <s> In the first few years of an ongoing survey of applications of Markov decision processes where the results have been implemented or have had some influence on decisions, few applications have been identified where the results have been implemented but there appears to be an increasing effort to model many phenomena as Markov decision processes. <s> BIB001 </s> A Survey of solution techniques for the partially observed Markov decision process <s> Introduction <s> This paper extends an earlier paper [White 1985] on real applications of Markov decision processes in which the results of the studies have been implemented, have had some influence on the actual decisions, or in which the analyses are based on real data. <s> BIB002 </s> A Survey of solution techniques for the partially observed Markov decision process <s> Introduction <s> Abstract A review is given of an optimization model of discrete-stage, sequential decision making in a stochastic environment, called the Markov decision process (MDP). This review presents an overview of theoretical and computational results, applications, several generalizations of the standard MDP problem formulation, and future directions for research. The reference list contains seminal papers, key texts, and surveys for the interested reader. <s> BIB003 </s> A Survey of solution techniques for the partially observed Markov decision process <s> Introduction <s> Abstract We consider discrete-time, partially observable stochastic control systems x t + 1 = F ( x t , u t , v t ), t = 0,1,…, y t = G ( u t − 1 , x t , w t ), t = 1,2,…, y 0 = G 0 ( x 0 , w 0 ), where x t , u t , and y t are, respectively, the state, control, and observation at time t , and the state and observation disturbance processes { v t } and { w t } are sequences of i.i.d. random elements with distributions ν and μ, respectively. We study the non-parametric adaptive control problem of maximizing the infinite-horizon discounted reward criterion when ν and μ are unknown and determine conditions for several adaptive policies to be asymptotically optimal and for almost-surely uniform approximations of the optimal reward function. Our approach combines convergence results for empirical processes and recent results on parameter-adaptive stochastic control problems. <s> BIB004
This paper presents a survey of computational algorithms for the partially observed Markov decision process (POMDP) having finite state, action, and observation sets. Emphasis is placed on algorithmic developments that have occurred since the publication of Monahan's survey of the POMDP  . The (completely observed) Markov decision process (MDP) is a well-studied model of sequential decision making under uncertainty that has been applied in a variety of significant real-world settings; see BIB003 for a recent survey of the MDP, and BIB002 BIB001 for surveys of its application. By completely observed, we mean that the decision maker has access to the exact value of the current state of the system without charge. Many situations exist, however, where such an assumption is invalid. For example, portions of the state value may be inaccessible (e.g. the state of a machine might be comprised of the state of various internal and unobservable components of the machine), sensors used to measure the state may give noisecorrupted readings, and/or exact state observations may be costly. The POMDP generalizes the MDP to include such situations, making the POMDP a particularly robust modeling tool for the control of a variety of discrete event dynamic systems. The applicability of the POMDP is limited in two ways. First, the POMDP is very data intensive. White and White BIB003 survey adaptive control techniques for the MDP and techniques for dealing with MDPs having parameter values described *This research was supported by NSF Grant ECS-8708183 and ARO Contract DAAG-29-85-K0089. by set inclusion. Such techniques, extended to the POMDP, are likely to mollify this limitation (see also BIB004 ). The second limitation is that the solution of the POMDP model of most realistic problems can require substantial computational effort. This limitation, and the potential modeling applicability of the POMDP model, serve as the motivation for the study of numerical solution techniques for the POMDP and hence for this survey. This survey is organized as follows. Section 2 presents the formulation of the POMDP that will be of interest throughout the paper. Sections 3 and 4 present optimality equations for two different sufficient statistics for the POMDP. Properties of an important operator associated with the second sufficient statistic are listed in section 5. The Smallwood-Sondik (SS) algorithm is described in section 6. We present a computationally attractive variant of the SS algorithm and a procedure to accelerate the Monahan variant of the SS algorithm. In section 7, we present three variants of the SS algorithm that have been shown to significantly accelerate its convergence. These variants are based on convergence-enhancing techniques that have proven useful for the MDP. Approximation schemes are discussed in section 8, primarily a recently developed approximation procedure due to Lovejoy. Section 9 considers a finite-memory suboptimal design technique, the development of which was inspired by results due to Platzman. The use of artificial intelligence concepts found in the heuristic search literature provides directions for research discussed in section 10. We present conclusions in section 11.