The potential growth of the size of the linear function set is not the only bad news. As remarked earlier, a piecewise linear convex value function is usually less complex than the worst case because many linear functions can be pruned away during updates. However, it turned out that the task of identifying all useful linear functions is computationally intractable as well (Littman, 1996). This means that one faces not only the potential sssseeerrrroooowww of the number of useful linear functions, but also inefficiencies related to the identification of such vectors. This is a significant drawback that makes the exact methods applicable only to relatively simple problems.

The above analysis suggests that solving a POMDP problem is an intrinsically hard task. Indeed, finding the optimal solution for the finite-horizon problem is PSPACE-hard
(Papadimitriou & Tsitsiklis, 1987). Finding the optimal solution for the discounted infinitehorizon criterion is even harder.  The corresponding decision problem has been shown to be undecidable (Madani et al., 1999), and thus the optimal solution may not be computable.

## 2.4.4 Structural Refinements Of The Basic Algorithm

The standard POMDP model uses a flat state space and full transition and reward matrices.

However, in practice, problems often exhibit more structure and can be represented more compactly, for example, using graphical models (Pearl, 1988; Lauritzen, 1996), most often dynamic belief networks (Dean & Kanazawa, 1989; Kjaerulff, 1992) or dynamic influence diagrams (Howard & Matheson, 1984; Tatman & Schachter, 1990). 5 There are many ways to take advantage of the problem structure to modify and improve exact algorithms. For example, a refinement of the basic Monahan algorithm to compact transition and reward models has been studied by Boutilier and Poole (1996). A hybrid framework that combines MDP problem-solving techniques to take advantage of perfectly and partially observable components of the model and the subsequent value function decomposition was proposed by Hauskrecht (1997, 1998, 2000). A similar approach with perfect information about a region (subset of states) containing the actual underlying state was discussed by Zhang and Liu (1997b, 1997a).  Finally, Castañon (1997) and Yost (1998) explore techniques for solving large POMDPs that consist of a set of smaller, resource-coupled but otherwise independent POMDPs.

## 2.5 Extracting Control Strategy

Value iteration allow us to compute an ith approximation of the value function Vi. However, our ulimate goal is to find the optimal control strategy µ* : I → A or its close approximation. Thus our focus here is on the problem of extraction of control strategies from the results of value iteration.

## 2.5.1 Lookahead Design

The simplest way to define the control function µ : I → A from the value function Vi is via greedy one-step lookahead:

$$\mu\left(b\right)=\arg\max_{a\in A}\left\{\sum_{t\in S}\rho\left(s,a\right)b(s)+\gamma\sum_{a\in\Theta}P\left(a|b,a\right)V_{t}\left(\tau\left(b,\,o,a\right)\right)\right\}\,.$$
