A Survey of solution techniques for the partially observed Markov decision process <s> Approximating Hv <s> Abstract : The problem considered is the monitoring of a discrete-state Markov process through a noisy channel with associated costs. Dynamic programming techniques are used to establish the optimal monitoring decision policies for both transient and steady-state situations. Examples are included. <s> BIB001 </s> A Survey of solution techniques for the partially observed Markov decision process <s> Approximating Hv <s> A fluorescence spectrophotometer having a beam splitter placed between an exit slit of an excitation monochromator and a specimen. Part of the excitation radiation is conducted to a first light quantum meter by said beam splitter and a reference photomultiplier is provided for receiving fluorescence from said first light quantum meter. A second light quantum meter is placed at the position normally occupied by a specimen cell and first and second absorbing cells are disposed in front of said first and second light quantum meters, respectively. <s> BIB002 </s> A Survey of solution techniques for the partially observed Markov decision process <s> Approximating Hv <s> A partially observed Markov decision process (POMDP) is a sequential decision problem where information concerning parameters of interest is incomplete, and possible actions include sampling, surveying, or otherwise collecting additional information. Such problems can theoretically be solved as dynamic programs, but the relevant state space is infinite, which inhibits algorithmic solution. This paper explains how to approximate the state space by a finite grid of points, and use that grid to construct upper and lower value function bounds, generate approximate nonstationary and stationary policies, and bound the value loss relative to optimal for using these policies in the decision problem. A numerical example illustrates the methodology. <s> BIB003
We have noted earlier that a real-valued function v, having the uncountably infinite space X as its domain, has a finite representation if v is pwl&c; i.e. there exists a finite set of vectors G such that v(x) = max {x~,: ~,~ F}. This fact was a key element in the development of the SS algorithm and its variants. The impressive numerical results reported in the previous section enhance the usefulness of the SS algorithm. However, two facts constrain the ultimate usefulness of any SS-type algorithm. First, the finite representation of the optimal value function requires computationally expensive reconstruction at each iteration. (We note that this representation is equivalent to a finite partition of X.) Second, the cardinality of the finite representation can grow geometrically as a function of stage; recall that #G = #A(#F ** #Z). Consider the following alternative approach, which we will call the fixed grid approach. Assume that X' is a finite subset of X, that an expected value function is determined for all x" ~ X', and that these values are used to determine the value of this expected value function for all x ~ X. The expected value function is invariably an approximation of the optimal value function. However, both of the aforementioned constraints of the SS algorithm are avoided. Kakalik BIB001 and Eckles  both used a linear interpolation method between fixed points in X in order to determine an approximation of the optimal value function. Bounds on the quality of the Eckles' approximation are presented in Sondik BIB002 . Sondik and Mendelssohn  used a grid of points that represents only those points in X that can be visited by a specified policy. Lovejoy BIB003 presented a procedure for approximating X by a finite grid of points. He used this grid to construct upper and lower bounds, generate suboptimal nonstationary and stationary policies, and determine a bound on the value loss, relative to optimal, for using these policies. We now briefly discuss Lovejoy's approach for determining the bounds and the suboptimal design. Lovejoy constructed the lower bound functions {v~} as follows. Let ~ be such that vZ,(x) = max {x)': ~ F,Z}. Analogous to our discussion of the SS algorithm, and state x'. This process is repeated for all x' ~ X'. Importantly, observe that #Fn z < #X' for all n. It is straightforward to show that v. z < vn for all n. Lovejoy also showed that the obvious strategy resulting from this lower bound generates expected value functions bounded below by {v.Z}. With respect to an operations count analysis for determining F.Z+ ~ given F. z, we note that: #X'#Z #A#F~ US operations (multiplications and additions) are required to determine x'P(z, a)yfor all "y~ F~, z ~ Z, x" ~ X', and a ~ A, where we assume that for all z, x', and a, flx'P(z, a) is constructed a priori (requiring #X'#Z #A(#S) 2 operations). Once upper and lower bounds are known, then action elimination can be used to identify an optimal action at as many points in X as possible. Impressive numerical results are presented in BIB003 . The following completely observed MDP appears to capture much of the process presented by Lovejoy for constructing an upper bound on v*. 