a way that at least partially eliminates their disadvantages. The idea is based on the fact that the two techniques work on the solution from two different sides (one forward and the other backward) and the complexity for each of them worsens gradually.  Then the solution is to compute the complete k th value function using dynamic programming (value iteration)
and cover the remaining steps by forward decision-tree expansion.

Various modifications of the above idea are possible. For example, one can often replace exact dynamic programming with two more efficient approximations providing upper and lower bounds of the value function. Then the decision tree must be expanded only when the bounds are not sufficient to determine the optimal action oice. A number of search techniques developed in the AI literature (Korf, 1985) combined with branch-and-bound pruning (Satia & Lave, 1973) can be applied to this type of problem. Several researchers have experimented with them to solve POMDPs (Washington, 1996; Hauskrecht, 1997; Hansen, 1998b).  Other methods applicable to this problem are based on Monte-Carlo sampling (Kearns, Mansour, & Ng, 1999; McAllester & Singh, 1999) and real-time dynamic programming (Barto, Bradtke, & Singh, 1995; Dearden & Boutilier, 1997; Bonet & Geffner, 1998).

## 2.7.2 Classical Planning Framework

POMDP problems with fixed initial belief states and their solutions are closely related to work in classical planning and its extensions to handle stochastic and partially observable domains, particularly the work on BURIDAN and C-BURIDAN planners (Kushmerick, Hanks, & Weld, 1995; Draper, Hanks, & Weld, 1994). The objective of these planners is to maximize the probability of reaching some goal state. However, this task is similar to the discounted reward task in terms of complexity, since a discounted reward model can be converted into a goal-achievement model by introducing an absorbing state (Condon, 1992).

## 3. Heuristic Approximations

The key obstacle to wider application of the POMDP framework is the computational complexity of POMDP problems. In particular, finding the optimal solution for the finitehorizon case is PSPA CE-hard (Papadimitriou & Tsitsiklis, 1987) and the discounted infinitehorizon case may not even be computable (Madani et al., 1999).  One approach to such problems is to approximate the solution to some c-precision. Unfortunately, even this remains intractable and in general POMDPs cannot be approximated efficiently (Burago, Rougemont, & Slissenko, 1996; Lusena, Goldsmith, & Mundhenk, 1998; Madani et al., 199). This is also the reason why only very simple problems can be solved optimally or nar optimally in practice.

To alleviate the complexity problem, research in the POMDP area has focused on various heuristic methods (or approximations without the error parameter) that are more efficient. 11 Heuristic methods are also our focus here.  Thus, when referring to approximations, we mean heuristics, unless specifically stated otherwise.