A Survey of solution techniques for the partially observed Markov decision process <s> Finite-memory suboptimal design <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> BIB001 </s> A Survey of solution techniques for the partially observed Markov decision process <s> Finite-memory suboptimal design <s> We develop bounds on the value function and a suboptimal design for the partially observed Markov decision process. These bounds and suboptimal design are based on the M most recent observations and actions. An a priori measure of the quality of these bounds is given. We show that larger M implies tighter bounds. An operations count analysis indicates that ( # A # Z ) M +1 ( # S ) multiplications and additions are required per successive approximations iteration of the suboptimal design algorithm, where A , Z , and S are the action, observation, and state spaces, respectively, suggesting the algorithm is of potential use for problems with large state spaces. A preliminary numerical study indicates that the quality of the suboptimal design can be excellent. <s> BIB002 </s> A Survey of solution techniques for the partially observed Markov decision process <s> Finite-memory suboptimal design <s> A finite-input, finite-state, finite-output stochastic control problem with imperfect state observation and classical information pattern is shown to be meaningful as the horizon increases without bound and the discount rate approaches unity. The plant model, a finite probabilistic system, includes the Markov decision and partially-observed Markov decision problems as special cases. Under conditions resembling controllability and observability in linear systems we show that: an optimal strategy exists, it may be realized by a stationary policy on the state estimate, its performance does not depend on the initial state distribution, and convergence rates for its finite-horizon and discounted performances are readily established. <s> BIB003
Assume that there is a process {OI, t = 0, 1 .... } such that an optimal strategy can be obtained which is dependent on the data process only through {0 l, t = 0, 1 .... }. That is, assume it is sufficient for optimality for a(t) to depend only on 0lid(t)]. Then, 19 I sufficiently summarizes the information useful for action selection that is contained in d(t). We refer to such a process { 19 I, t = 0, 1 .... } as a sufficient statistic (a more formal treatment of which can be found in  ). We seek sufficient statistics for two reasons. First, a sufficient statistic can accommodate optimality. Second, the sufficient statistic may represent the information contained in the data process that is useful for action selection in a computationally desirable manner. We remark that the data process is trivially a sufficient statistic, and we recall that the information process is a sufficient statistic possessing some numerically appealing features (e.g. the state space of the information process is stage invariant, whereas the state space of the data process grows geometrically in stage). Platzman  BIB003 and White and Scherer BIB002 have considered a third sufficient statistic in the development of bounds and a suboptimal design for the POMDP. This third sufficient statistic { y(t), t = 0, 1 .... } combines the data and information processes in the following manner: Thus, since {x(t), t = 0, 1 .... } can be constructed from {y(t), t = 0, 1 .... }, {y(t), t = 0, 1 .... } is a sufficient statistic. We now present the development found in BIB002 . for all x ~ X. (2) A sufficient condition for these bounds to bc tight. If P (z 'n, a m) has rank 1 for all (z 'n, a m) ~ Z" x A m for some m < M, then for all n, rn < n < M, and (z n, a n) ~ Z n x A n, ln(z n, a n) = un(z n, an). BIB001 A guarantee that larger M produces tighter bounds. An operations count analysis shows that determination of LMv, given v, requires #S((#A #Z) ** (M + 1)) operations. Therefore, on the basis of operations per iteration, we conclude that for small action and observation spaces and large state spaces, use of the L M operator for suboptimal design determination is preferred to the use of the Lovejoy lower bound procedure, and that for large action and observation spaces and small state spaces, we should prefer use of the Lovejoy lower bound procedure to use of the L M operator.