|
Article Excerpt
1. Introduction
The main goal of this paper is to propose a new multistage Monte Carlo (MMC) method for solving influence diagrams using local computation. Influence diagrams are a compact representation of Bayesian decision problems that were initially proposed as a front end for decision trees (Howard and Matheson 1984). Later, Olmsted (1983) and Shachter (1986) devised a method for solving influence diagrams directly, i.e., without first transforming them to decision trees. The direct influence diagram solution technique uses local computation to obtain the conditionals and an optimal strategy. Smith et al. (1993) have proposed modifications to the influence diagram technique for representing and solving asymmetric decision problems.
Most of the research on representing and solving decision problems assume that all chance and decision variables have discrete state spaces. For problems in which some of the decision and/or chance variables are continuous, several approximation methods have been proposed. The traditional approach is to partition the state space of each continuous variable into a few discrete states (e.g., Miller and Rice 1983, Keefer 1994). A related approach is to summarize continuous distributions by their first few moments, summarize continous utility functions by their first few derivatives, and then use either the moments, the derivatives, or both to obtain a solution (Howard 1971, Smith 1993). Another approach is to deal directly with continuous variables without discretizations. For example, Shachter and Kenley (1989) have studied influence diagram methodology for decision problems in which the probability model is multivariate Gaussian, and Poland (1994) has developed influence diagrams that use Gaussian mixtures to approximate arbitrary continuous distributions.
For the general case of a decision problem consisting of a mixture of discrete and continuous variables, Jenzarli (1995) has investigated the use of Gibbs sampling for solving such decision problems using local computation. Gibbs sampling is one member of a class of techniques called Markov chain Monte Carlo that draw dependent samples from a distribution that in the long run approaches the target joint distribution (e.g., see Gilks et al. 1996). Bielza et al. (1999) explore the problem of using Markov chain Monte Carlo methods to solve a single-stage decision problem with continuous decision and chance nodes.
The MMC sampling technique proposed here draws independent and identically distributed observations to solve multiple-stage decision problems. Monte Carlo methods that have been proposed in this spirit sample from the entire distribution (e.g., see Hertz 1964, and Shachter and Peot 1990 for Bayesian networks, which are influence diagrams without decision and value nodes). However, when the number of variables is large, the combined state space of all variables is exponentially large, and the sample size required for precise estimates is too large to be practical. The MMC method generates samples at each stage from a small set of variables in the influence diagram. We use methods developed for exact solution of influence diagrams to limit the number of variables sampled at any time. Because influence diagrams model each chance variable with a conditional probability distribution, the MMC solution method lends itself well to influence diagram representations.
In [section]2, we provide a statement of the oil wildcatter with secondary recovery (OWSR) problem as an example. In [section]3, we describe an influence diagram representation of the OWSR problem using the Smith et al. (1993) distribution tree technique. In [section]4, we describe our MMC method for solving influence diagrams using local computation and illustrate it using the OWSR problem. In [section]5, we describe an application of our method to pricing Bermudan put options. Finally, in [section]6, we conclude with a summary and some issues for further research. The online appendix (mansci.pubs.informs.org/ecompanion.html) elaborates on the statistical properties of the MMC method.
2. Oil Wildcatter with Secondary Recovery (OWSR) Problem
The OWSR problem is an adaptation of a problem described by Raiffa (1968). An oil wildcatter must decide whether or not to drill a well at a particular location. He is uncertain whether the well will be dry, wet (some oil), or soaking (lots of oil). The cost of drilling is $70,000. The expected net revenue (exclusive of drilling cost) resulting from primary recovery of oil from a dry well is $0, from a wet well is $120,000 and from a soaking well is $270,000. The wildcatter's subjective probabilities for the state of the well are 0.5 for dry, 0.3 for wet, and 0.2 for soaking.
Before making the decision whether or not to drill, the wildcatter can have a seismic test done to investigate the underground structure of the drill site. The cost of the seismic test is $10,000 to classify the site as having either no structure (ns), open structure (os), or closed structure (cs). The underground structure is related to the amount of oil as follows. If the well is dry, the conditional probabilities of ns, os, and cs are 0.6, 0.3, and 0.1, respectively. If the well is wet, the corresponding probabilities are 0.3, 0.4, and 0.3. Finally, if the well is soaking, the corresponding probabilities are 0.1, 0.4, and 0.5.
After drilling, striking oil, and extracting an optimal amount using primary recovery techniques, the wildcatter has the option of extracting more oil using secondary recovery techniques at an additional cost of $20,000. Secondary recovery will result in no recovery (nr) with associated revenues of $0, low recovery (lr) with associated revenues of $30,000 or high recovery (hr) with associated revenue of $50,000. The amount of secondary recovery depends on the state of the well. If the well is wet, the conditional probabilities of nr, lr, and hr are 0.5, 0.4, and 0.1, respectively. If the well is soaking, the corresponding probabilities are 0.3, 0.5 and 0.2.
3. Influence Diagram Representation
A mathematical representation of a Bayesian decision problem can be broken into four parts: (1) alternatives--the set of alternatives available to the decision maker, (2) uncertainty model--a probability model of the uncertainties faced by the decision maker, (3) preferences for outcomes--a utility function model of the preferences of the decision maker for all possible outcomes, and (4) information constraints--a set of restrictions on the information available to the decision maker each time he or she must make a decision.
An influence diagram representation of a decision problem is specified at two levels: graphical and numerical. At the graphical level, we have an acyclic directed graph with three different types of nodes--chance, decision, and utility--and two different types of directed edges--domain and pure information. At the numerical level, we have a distribution tree for each node in the graph. Figure 1 shows an influence diagram representation of the OWSR problem at the graphical level. Figures 2 and 3 show the influence diagram representation at the numerical level.
In Figure 1, T (seismic test), D (drill), and S (secondary recovery) are rectangular decision nodes representing decision variables; R (seismic test results), O (amount of oil), and SR (secondary oil recovered), are circular chance nodes representing chance variables; and [v.sub.1], [v.sub.2], and [v.sub.3] are diamond-shaped value nodes representing additive factors of the joint utility function.
The solid arrows pointing to a decision variable indicate the domain of the conditional for the decision variable, which is the subset of variables included in the conditional. In the OWSR problem, the domain for the conditional for T is {T}, which we write as Dom([[chi].sub.T]) = {T}, where [[chi].sub.T] denotes the conditional for T. Also, Dom([[chi].sub.D]) = {D} and Dom([[chi].sub.S]) = {D, O, S}.
[FIGURE 1 OMITTED]
[FIGURE 2 OMITTED]
A conditional for a decision variable constrains the set of possible alternatives available to the decision maker at that variable. Because there are no constraints on the choices at the decision variables T and D, Dom([[chi].sub.T]) = {T} and Dom([[chi].sub.D]) = {D}. Because the choices available at S depend on the choice made at D and the realized value of O, Dom([[chi].sub.S]) = {D, O, S}. In general, the domain of the variable X consists of the set of variables at the tails of the solid arrows pointing to X and X itself. Solid arrows pointing to decision nodes are also interpreted as information constraints in the sense that if there is a solid arrow from node X (either chance or decision) to decision node A, then the true state of X will be known to the decision maker at the time he or she has to choose an alternative at A. Dashed arrows pointing to decision nodes indicate information constraints only. A dashed arrow from a node X to a decision node A means that the decision maker knows the true value of X at the time he or she has to make a choice at A. This is in contrast to a solid arrow, which indicates both a conditional and an information constraint.
[FIGURE 3 OMITTED]
The influence diagram literature usually assumes a "no-forgetting" condition, which specifies that if there is a directed path from a node X (chance or decision) to decision node A via other decision nodes only, then this implies that the decision maker knows the value of X at the time he or she has to make a choice at A. Optionally,...
|
