A Survey of solution techniques for the partially observed Markov decision process <s> Smallwood-Sondlk algorithm <s> This paper formulates the optimal control problem for a class of mathematical models in which the system to be controlled is characterized by a finite-state discrete-time Markov process. The states of this internal process are not directly observable by the controller; rather, he has available a set of observable outputs that are only probabilistically related to the internal state of the system. The formulation is illustrated by a simple machine-maintenance example, and other specific application areas are also discussed. The paper demonstrates that, if there are only a finite number of control intervals remaining, then the optimal payoff function is a piecewise-linear, convex function of the current state probabilities of the internal Markov process. In addition, an algorithm for utilizing this property to calculate the optimal control policy and payoff function for any finite horizon is outlined. These results are illustrated by a numerical example for the machine-maintenance problem. <s> BIB001 </s> A Survey of solution techniques for the partially observed Markov decision process <s> Smallwood-Sondlk algorithm <s> This paper treats the discounted cost, optimal control problem for Markov processes with incomplete state information. The optimization approach for these partially observable Markov processes is a generalization of the well-known policy iteration technique for finding optimal stationary policies for completely observable Markov processes. The state space for the problem is the space of state occupancy probability distributions the unit simplex. The development of the algorithm introduces several new ideas, including the class of finitely transient policies, which are shown to possess piecewise linear cost functions. The paper develops easily implemented approximations to stationary policies based on these finitely transient policies and shows that the concave hull of an approximation can be included in the well-known Howard policy improvement algorithm with subsequent convergence. The paper closes with a detailed example illustrating the application of the algorithm to the two-state partially observable Markov process. <s> BIB002
The Smallwood-Sondik (SS) algorithm BIB001 is a successive approximations approach for solving the POMDP and as such is based on determining Hv from v. See BIB002 for a related policy iteration algorithm for the infinite horizon case. The SS algorithm makes extensive use of the fact that H preserves pwl&c. Let F,, be such The fact that the function g is a function of x 6 X can significantly complicate the determination of F'. An approach to determining F' from F (which has been attributed to Monahan) that avoids dealing directly with the issue of determining the function g is as follows. First, determine the set However, G is a large set compared to F (#G = #A(#F ** #Z), where #G is the cardinality of the set G and A ** B = A B) and may contain many unnecessary elements. Second, eliminate as many elements in G as possible to obtain F'. A direct linear programming approach (see BIB001 for further discussion) can be used to reduce the number of elements in G. Consider the following sufficient condition for constructing F' from G" Choose ~ ~ G. If u* = 0, then add ~' to F', where u = maximum u subject to: u <x(~'-~) V~G,