a course of patient management, the decision-maker must carefully evaluate the costs and benefits of both current and future choices, as well as their interaction and ordering.  Other decision problems with similar characteristics - complex temporal cost-benefit tradeoffs, stochasticity, and partial observability of the underlying controlled process - include robot navigation, target tracking, machine mantainance and replacement, and the like.

Sequential decision problems can be modeled as Markov decision processes (MDPs)
(Bellman, 1957; Howard, 1960; Puterman, 1994; Boutilier, Dean, & Hanks, 1999) and their extensions. The model of choice for problems similar to patient management is the partially observable Markov decision process (POMDP) (Drake, 1962; Astrom, 1965; Sondik, 1971; Lovejoy, 1991b). The POMDP represents two sources of uncertainty: stochasticity of the underlying controlled process (e.g. disease dynamics in the patient management problem),
and imperfect observability of its states via a set of noisy observations (e.g. symptoms, findings, results of tests). In addition, it lets us model in a uniform way both control and information-gathering (investigative) actions, as well as their effects and cost-benefit tradeoffs. Partial observability and the ability to model and reason with information-gathering actions are the main features that distinguish the POMDP from the widely known fully observable Markov decision process (Bellman, 1957; Howard, 1960).

Although useful from the modeling perspective, POMDPs have the disadvantage of being hard to solve (Papadimitriou & Tsitsiklis, 1987; Littman, 1996; Mundhenk, Goldsmith, Lusena, & Allender, 1997; Madani, Hanks, & Condon, 1999), and optimal or e-optimal solutions can be obtained in practice only for problems of low complexity. A challenging goal in this research area is to exploit additional structural properties of the domain and/or suitable approximations (heuristics) that can be used to obtain good solutions more efficiently.

We focus here on heuristic approximation methods, in particular approximations based on value functions. Important research issues in this area are the design of new and efficient algorithms, as well as a better understanding of the existing techniques and their relations, advantages and disadvantages. In this paper we address both of these issues. First, we survey various value-function approximations, analyze their properties and relations and provide some insights into their differences. Second, we present a number of new methods and novel refinements of existing techniques. The theoretical results and findings are also supported empirically on a problem from the agent navigation domain.

## 2. Partially Observable Markov Decision Processes

A partially observable Markov decision process (POMDP) describes a stochastic control process with partially observable (hidden) states.  Formally, it corresponds to a tuple
(S, A, O, T, O, R) where S is a set of states, A is a set of actions, O is a set of observations, T : S × A × S → [0,1] is a set of transition probabilities that describe the dynamic behavior of the modeled environment, O : S × A × Θ → [0, 1] is a set of observation probabilities that describe the relationships among observations, states and actions, and R : S × A × S → R denotes a reward model that assigns rewards to state transitions and models payoffs associated with such transitions. In some instances the definition of a POMDP also includes an a priori probability distribution over the set of initial states S.