Resolute Choice in Sequential Decision Problems with Multiple Priors

1 Introduction

In many sequential decision problems, agents must act under uncertainty. This issue arises in several applications of artificial intelligence (AI), e.g. medical diagnosis (sequence of medical treatments/tests), troubleshooting under uncertainty (sequence of observations/repairs), poker-playing program (sequence of raise/call/fold). Decision theory provides useful tools to deal with uncertainty in decision problems. A decision under uncertainty is classically viewed as a function that maps states of the word to consequences - denoting Θ the set of states, X the set of consequences, D = {f : Θ ↦→X} is the set of potential acts. Following the theory of expected utility [von Neuman and Morgenstern, 1947], a probability P can model the uncertainty about the state of the world, and a utility function u : X ↦→U ⊂ R will capture the utility of the consequences. Then each decision f can be evaluated by its expected utility EUP,u(f) = Σθ∈Θ u(f(θ)) . P(θ) and compared to other decision. The best decision should be the one that maximizes expected utility.

However, it has been shown that expected utility cannot always capture the behaviour of rational decision makers. Ellsberg's counter example [1961] is the following: let U be an urn containing 13 of red balls and 23 of black or yellow balls.

One ball will be drawn and guessing the right color leads to a gain of 1 (0 otherwise). The decision to bet on red (resp. black) is denoted by fR (resp. fB). The decision to bet on "red or yellow" (resp. "black or yellow") is denoted by fRY (resp. fBY ).Most of people prefer fR to fB and fBY to fRY . But there exist no probability measure P and no utility function u such that EUP,u(fR) > EUP,u(fB) and EUP,u(fBY ) > EUP,u(fRY ). The point is that the knowledge about the world is ambiguous: the underlying probability measure could be any probability in the set

Gilboa and Schmeidler [1989] have then shown that most decision makers do use the expected utility model, but on the basis of the whole set of priors: they maximize the min, over P, of the possible values of the expected utility. In Ellsberg's example, for instance, the probability of {black} belongs to [0, 23 ]: the minimum value of EU for act fB is thus 0; for act fR, P ({red}) = 13 , hence the expected utility is 13 in any case: fR is preferred to fB. The probability of P({red, yellow}) varies between 13 and 1, hence the min expected utility of act fRY is 13 (it is possible that there is no yellow ball). Probability P({black, yellow}) is equal to 23 , hence the expected utility of act fBY is 23 in any case: fBY is preferred to fRY .

The topic of this paper is to study how to optimize min expected utility in problems of sequential decision making under uncertainty involving multiple priors. More precisely, we tackle the problem of optimizing this criterion in a tree endowed with multiple priors. The choice of decision trees as the basic way of representing sequential problems is motivated by its generality: no linearity assumption on utility under certainty is indeed made, and even the Markov property is not required. Note that the algorithms proposed here can nevertheless be used to "solve" an influence diagram by "unfolding" the decision diagram in a decision tree, and then selecting an optimal strategy in this tree. This approach is suitable for small or medium size decision problems.

The question of selecting a strategy in a decision tree endowed with imprecise probabilities has received little attention in the literature. It raises two types of issues: decisiontheoretic ones [Jaffray and Jeleva, 2007; Jaffray, 1999], i.e. the suitability -from the normative point of view- of various decision criteria under imprecise probability in a sequential decision setting, and algorithmic ones [Kikuti et al., 2011;

Huntley and Troffaes, 2008], i.e. the effective computation of an optimal strategy. In this paper, we are more concerned with the algorithmic issues.

In a decision tree endowed with clear probabilities, it is well-known that an optimal strategy can be recovered in linear time by rolling back the decision tree, i.e. computing a strategy recursively in a dynamic programming manner. Nevertheless, this approach is not valid anymore when optimizing min expected utility in a decision tree with multiple priors, since Bellman's principle of optimality does not hold anymore. From this point, two research directions can be explored. The first one, followed by Kikuti et al. [2011] is to add an assumption of dynamic feasibility, which amounts at seeking the strategy returned by rolling back the decision tree. This strategy will be preferred by a consequentialist decision maker, i.e. a decision maker whose present decision does not depend on the past nor on what she plan to do when making her first decision. Though appealing from an algorithmic viewpoint, this approach does not necessarily prevent the decision maker from selecting a strategy that could be "dominated" in some sense [Hammond, 1988]. The alternative way, proposed by [McClennen, 1990], is the resolute choice approach, where the decision maker commits to an optimal strategy viewed from the root of the decision tree, and never deviates from it later. It raises a challenging algorithmic problem, provided the combinatorial number of potential strategies. Huntley and Troffaes [2008] have adressed this issue by proposing a very generic method to compute the set of non-dominated strategies (to be defined later), but without entering into computational considerations: they do not study the computational complexity of the problem, and the method they provide is not implementable as it stands.

The paper is organized as follows. After introducing the framework (Section 2), we show that evaluating a strategy according to min expected utility is NP-hard (Section 3) and we study how linear programming can be used to automatize this evaluation. We then provide operational algorithms to compute an optimal strategy (Section 4), and conclude by reporting the results of numerical tests (Section 5).

2 Decision Trees withMultiple Priors

In multistage decision making, one studies problems where one has to make a sequence of decisions conditionally to events. Decision trees provides a simple and explicit representation of a sequential decision problem under uncertainty. A decision tree T involves three kinds of nodes: a set ND of decision nodes (represented by squares), a set NC of chance nodes (represented by circles) and a set NU of utility nodes (leaves of the tree). A decision node can be seen as a decision variable, the domain of which corresponds to the labels of the branches starting from that node. A random variable X is assigned to each chance node, and there is one outgoing branch for each possible value x ∈ D(X), where D(X) is the domain of X. These branches are labelled by the probabilities of the corresponding events. The values indicated at the leaves correspond to the utilities of the consequences. For illustration, we now present an example of a decision tree representing a sequential problem involving an Ellsberg's urn.

Example 1 Consider a game beginning with a toss coin, before a ball is drawn in an Ellsberg's urn (the same as in the introduction). Depending on whether the coin comes up heads or tails (random variable X1, with D(X1) = {H, T} for heads and tails), the decision maker is asked to bet on red or black (decision D1), or red or yellow (decision D2). The color of the ball is a random variable X2, with D(X2) = {R, B, Y } for red, black or yellow. If the decision maker bets on red (fR) and a red ball is drawn, it yields a gain of 1 - ε (with ε > 0). If she bets on black or yellow (fB or fY ) and the guess is correct, it yields a gain of 1. The overall game can be represented by the decision tree of Figure 1. Note that random variable X2 appears several times in the decision tree since the draw can be made in several contexts (the coin comes up heads and the decision maker chooses red, the coin comes up heads and the decision maker chooses black, etc.).

When crisp probabilities are known, the joint probability measure over the random variables Xi is not given in extenso, but through the labelling on the tree by conditional probabilities : each branch starting from a chance node Xj i represent an event Xi = x and is endowed with a number, that represents the probability P(Xi = x|past(Xj i )), where past(Xj i ) denotes all the value assignments to random and decision variables on the path from the root to Xj i . Furthermore, in this paper, we assume that P(Xi = x|past(Xj i )) only depends on the random variables in past(Xj i ). In the case of multiple priors, the joint probability is imprecise and it is not possible to represent it by a labeling of the edges with numbers. In the present paper, we propose to label them by variables representing the (ill-known) possible values of the conditional probabilities. Each branch starting from a chance node Xj i represents an event Xi = x and is labelled by a variable pi,j,x (for P(Xi = x|past(Xj i ))).

The joint imprecise probability should be expressed explicitly, by a set of joint probability measures, but it is not always feasible, e.g. when random variables have an infinite range of possible values. In this paper, we consider the case where the set of measures are represented by probability intervals P(Xi ∈ E|past(Xj i )) on events E, where E ⊆ D(Xi). Formally, we have sets of linear constraints C j i locally defined over subsets of variables pi,j,x at each chance node Xj i . A

constraint c ∈ C j i takes the form p-c ≤ ∑x∈Dc pi,j,x ≤ p+c , where Dc = {x : pi,j,x is in the scope of c} ⊆ D(Xi) and p-c , p+c are reals (if p-c = p+c the interval is said degenerated). In Figure 1, these constraints are defined as follows:

Obviously, if the probabilities are precisely known at node Xj i , then C j i simply assigns a value to each pi,j,x.

Furthermore, some independencies can be taken into account by explicitly adding a set Ce of equality constraints over the pi,j,x. In the example, since X1 and X2 are independent, we have p2,1,x=p2,2,x=p2,3,x=p2,4,x for all x. We denote by PT the set of possible probabilitymeasures over decision tree T that are compatible with constraints C = (⋃i,j C j i ) ∪ Ce.

In a decision tree T , a strategy consists in setting a value to every decision node, i.e. to every decision variable conditionally to the past. The decision tree in Figure 1 includes 4 feasible strategies, among which for instance strategy s = (D1 = fB,D2 = fY ). In our setting, a strategy can be associated to a compound lottery over the utilities, where the probabilities of the involved events are ambigous. For instance, strategy s corresponds to the compound lottery pictured in Figure 2. Comparing strategies amounts therefore to compare compound lotteries. The evaluation of a strategy (more precisely, of the corresponding compound lottery) according to min expected utility depends on the multi-prior set PT . In this setting, we denote by EU(s) = minP∈PT EU(P, s) the min expected utility of strategy s, where EU(P, s) is the expected utility of s for probability measure P . A strategy s is preferred to s′ if EU(s) > EU(s′ ). We show in the next section that the evaluation of a strategy is a combinatorial problem in itself due to the combinatorial nature of PT .

3 Evaluating a Strategy

We now prove that evaluating a strategy according to its min expected utility is an NP-hard problem, where the size of an instance is the number of involved chance nodes.

Proposition 1 Evaluating a strategy according to its min expected utility is an NP-hard problem, even if all nondegenerated probability intervals are [0, 1].

Proof. The proof relies on a polynomial reduction from problem 3-SAT, which can be stated as follows: given a set X of boolean variables and a collection C of clauses on X such that |c| = 3 for every clause c ∈ C, does there exist an assignment of truth values to the boolean variables of X that satisfies simultaneously all the clauses of C ?

evaluating a strategy amounts to evaluating a compound lottery. One associates a random variable Xi to every booolean variable xi, with domain {true, false}. The polynomial generation of a compound lottery from an instance of 3-SAT is performed as follows. One generates a subtree Tk for each clause ck ∈ C. The indices of the boolean variables appearing in clause ck are denoted uk, vk,wk. For instance, for clause c2 = x1 ∨ x3 ∨ x4, u2 = 1, v2 = 3 and w2 = 4. Subtree Tk is a complete binary tree such that:

• the root (depth 0) is a chance node labeled by Xuk ,
• nodes of depth 1 are chance nodes labeled by Xvk ,
• nodes of depth 2 are chance nodes labeled by Xwk ,
• nodes of depth 3 are utility nodes.

Each chance node Xj i has two outgoing branches:

• one corresponding to Xi = true and labelled by pi ∈ [0, 1],
• one corresponding to Xi = false and labelled by 1 - pi.

Finally, the value of a utility node is 1 if it is on the path making false all the literals of ck, otherwise its value is 0.

Once all subtrees Tk have been generated, a unique root node X0 is generated, which is parent of all subtrees Tk. A probability 1/m is assigned to each branch from X0. This concludes the reduction. Clearly, the generated tree can be computed in polynomial time. As an illustration, in Figure 3, we give the compound lottery generated from the following instance of 3-SAT: (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x3 ∨ x4).

Let us show that the 3-SAT formula is satisfiable if and only if the min expected utility of the compound lottery is 0. If there is an instantiation {x1 = a1, x2 = a2, . . . , xn = an} that satisfies the 3-SAT formula, then the min expected utility of the compound lottery L is 0. Indeed, setting each variable pi to 1 if ai is equal to "true", and 0 otherwise, yields a min expected utility equal to 0. This is related to the fact that each utility node of value 1 is the terminal node of the unique path in Tk that makes false clause ck. As clause ck is made true by the instanciation, this utility node has probability 0 to be reached.

Conversely, if the min expected utility of L is 0, then the 3-SAT formula is satisfiable. Indeed, given an instantiation of parameters pi making zero the min expected utility of the lottery, the probability to reach a nonzero utility node is necessarily 0. This implies that, for every path to a nonzero utility node, at least one probability pi is 0 (label pi) or 1 (label 1 - pi). By setting value "true" (resp. "false") to xi if pi = 1 (resp. 0), the 3-SAT formula is satisfied. ■

We now describe a procedure to evaluate a strategy, based on a mathematical programming formulation. Before providing the formal expression of min expected utility EU(s) of a strategy s, we need to introduce some notations. We denote by X1, . . . , Xn the set of random variables appearing in a decision tree T , and by X = 〈X1, . . . ,Xn〉 the corresponding random vector. We denote by D(Y ) the domain of a random variable (or random vector) Y . Furthermore, given a subset I ⊆ {1, . . . , n} of indices, we denote by XI the random vector whose components are Xi (i ∈ I). Besides, given a node N, we denote by π(N) the set of indices of the random variables on the path from the root to N (random variable in N excluded if N ∈ NC). The complementary set is denoted by ¯π(N) = {1, . . . , n} \ π(N). Finally, we denote by x(N) the assignment vector of Xπ(N) that leads to node N. For instance, consider the decision tree of Figure 1. We have π(X1 2 ) = {1} since random variable X1 (node X1 1 ) appears on the path from X1 1 to X1 2 . Thus Xπ(X1 2 ) = 〈X1〉, and x(X1 2 ) = 〈H〉 since X1 = H on the considered path.

In a decision tree T , a strategy s is characterized by the subset Us ⊂ NU of utility nodes it enables to reach. The min expected utility EU(s) of s can thus be written as follows:

where P (Xπ(N) = x(N)) represents (in accordance with our notations) the probability to reach node N when following strategy s. For instance, strategy (D1 = fB,D2 = fY ) in Figure 1 yields the following formula:

Given the combinatorial nature of PT , we formulate a mathematical program to evaluate a strategy s. The main difficulty consists in characterizing the set of measures P ∈ PT . The fact that the crisp probabilities satisfies constraints C is indeed not sufficient to ensure the global consistency of the probability measure over T [Jeantet and Spanjaard, 2009], due to the possibility of several instances of the same random variable in T . For instance, assume that the probabilities P(X1), P(X2) and P(X2|X1) appear in the decision tree. Then, the total probability theorem should hold: P(X2) = ∑x∈D(X1) P(X2|X1 = x)P(X1 = x). In order to characterize set PT of "feasible" probability measures, we define constraints upon atomic probabilities P(X = x) instead of variables pi,j,x. Furthermore, we consider the probabilities P(X(N) = x(N)) to reach each of the nodes N of the tree, provided the node is compatible with the followed strategy. The variables used in our formulation are thus not the pi,j,x, and their number is exponential in n (number of distinct random variables), but the interest is that they are sufficient to both properly characterize a probability measure and insure its compatibility with C. So that Kolmogorov's axioms hold, it is necessary to satisfy the following constraint:

Besides, in order to link atomic probabilities P(X = x) to probabilities P(Xπ(N) = x(N)), we introduce the following linear constraints for all N ∈ N (there are some redundancies, but we do not elaborate here to save space):

Then, to insure that constraints C j i are satisfied, we introduce the following constraints for each chance node Xj i by using Bayes' rule: ∀c ∈ C j i ,

where Dc is the subdomain of Xi involved in constraint c (see Section 2), and Xπ(Xj i )∪{i} = (x, z) means that 2 , :

Finally, to insure that constraints Ce are satisfied, we need the following bilinear constraint, by using Bayes' rule:

for each constraint pi,j,x = pi′ ,j ′ ,x′ in Ce. In Example 1, for constraint p2,1,R = p2,3,R, it writes: P(X1 = T) × P(X1 = H, X2 = R) = P (X1 = H) × P (X1 = T, X2 = R).

The characterization of PT thus requires O(|N|+|D(X)|) variables (representing the probabilities to reach each of the nodes, and the atomic probabilities) and O(|N| + |C|) constraints (the constraints to link the atomic probabilities to the probabilities to reach each of the nodes, and the constraints to insure compatibility with C). Clearly, |D(X)| (and hence n) appears to be a key parameter for the spatial (and time) efficiency of this formulation, and the numerical tests will confirm it. Now that PT is characterized, we are able to evaluate a strategy by using an off-the-shelf optimization software.

4 Selecting a Strategy

Due to their combinatorial number, the enumeration of all strategies is quickly cumbersome. Furthermore, when trying to maximize min expected utility in a decision tree, it is important to note that the optimality principle does not hold. For illustration, let us perform the rolling back procedure on the decision tree of Figure 1. In D1 and D2, the decision maker prefers decision fR, since it provides a min expected utility of (1 - ε)/3, while it is 0 for the other decision. The strategy returned by rolling back the decision tree is therefore s = (D1 = fR,D2 = fR). The min expected utility of s is (1 - ε)/3, while strategy (D1 = fB,D2 = fY ) yields 1/3. Hence, to compute a strategy optimizing min expected utility one cannot resort to standard dynamic programming in the general case. Nevertheless, there exist cases authorizing it. We describe one such case in the next paragraph.

Separable Decision Trees. For each chance node Xj i , we denote by P j i the set of conditional probability distributions over Xi|past(Xj i ) that satisfies constraints C j i . A decision tree T is called separable (or separately specified [Kikuti et al., 2011]) if PT = ∏Xj i ∈NC P j i . In such a tree, it is valid to use a rolling back procedure for maximizing min expected utility. In this procedure, comparing strategies s and s′ in a subtree amounts to compare the induced (ambiguous) lotteries Ls and Ls′ . The validity of the rolling back procedure is related to the fulfillment of the following property:

where λ ∈ [0, 1] and λLs + (1 - λ)Ls′ is the compound lottery that yields lottery Ls (resp. Ls′ ) with probability λ (resp. (1 - λ)). The fulfillment of this property directly follows from the separability assumption [Jeantet and Spanjaard, 2009]. The optimal min expected utility EU∗ (N) at node N is computed recursively by using the following formulas:

- At a decision node Di: EU∗ (Di) = max

d∈D(Di) EU∗ (Di = d).

where D(Di) is the domain of decision variable Di.

- At a chance node Xj i :

where Nx is the node reached if Xi = x.

The computation of EU∗ (Xj i ) according to the above formula requires the resolution of a linear program whose set of constraints is C j i (note that the separability assumption implies of course that Ce = ∅). The number of such (small size) linear programs solved during the running of the procedure is clearly linear in the number of chance nodes.

Non-separable Decision Trees. In the general (nonseparable) case, the rolling back method does not work when directly operating with min expected utility. However, one can use the following simple property: if a strategy s is dominated by another strategy s′ , i.e. EU(P, s) ≤ EU(P, s′ ) for all P ∈ PT , then EU(s) ≤ EU(s′ ). The main idea is therefore to compute the set of all non-dominated strategies (w.r.t. the asymetric part of the previous relation) in a first phase, and then, in a second phase, to recover the optimal one in this set according to min expected utility. The evaluation procedure of Section 3 can be used to determine the best strategies in the second phase. It has been proved that the set of non-dominated strategies can be computed by rolling back the decision tree [Huntley and Troffaes, 2008]. We provide here an operational approach to perform this procedure in our setting. The set S∗ (N) of non-dominated strategies at node N is computed recursively:

- At a decision node N: S∗ (N) = ND(⋃ki=1 S∗ (Ni)) where N1, . . . , Nk are the children of N and ND(S) returns the set of non-dominated strategies in S.

- At a chance node N:

S∗ (N) = ND({s1 ⊕ . . . ⊕ sk : si ∈ S∗ (Ni) ∀i}) where N1, . . . ,Nk are the children of N and ⊕ is the combination operation of substrategies.

The key primitive in this procedure is function ND(·). To compute the non-dominated elements of a set S, one performs pairwise comparisons of strategies in S. Such comparisons are called dominance test hereafter. A strategy s dominates a strategy s′ if there does not exist P ∈ PT (i.e., satisfying the constraints presented in Section 3) such that:

where Us is the subset of utility nodes that s reaches. The test thus amounts to solve a set of linear constraints.

5 Numerical Tests

The proposed algorithms have been implemented in C++, and the CPLEX solver has been used to solve the mathematical programs. The numerical tests have been performed on a Pentium IV 2.13GHz CPU computer with 3GB of RAM.

For the separable case, one considers decision trees of (even) depth h, where all chance (resp. decision) nodes have outdegree d (resp. 2). The utilities are real numbers randomly drawn in [0, 100]. To define the imprecise probability, or equivalently the constraints C j i , one generates d - 1 constraints of arity d - 1 (two constraints of arity 1 if d = 2). For each constraint c, one sets p+c - p-c = 0.1. The average execution times on 20 such random instances are reported in Table 1. Timeout was set to 100 sec., and symbol X appears as soon as the running time exceeded the timeout for at least one instance. Notice that our procedure was able to solve decision trees with up to 2m nodes and that, unsurprizingly, ambiguity degree d has a great impact on the resolution times.

For the non-separable case, one considers binary and complete decision trees of even depth h, with real utilities in [0, 100]. The binary assumption allows to consider a larger range of depths for the decision trees. To generate the constraints C j i on the imprecise probabilities, we first generate a crisp probability distribution P over n random variables. Then, for each chance node, a random variable is randomly assigned. At each chance node, following Bayes' rule, we compute the crisp conditional probabilities according to P. Finally, each conditional probability p on a branch is replaced by an interval [p-, p+] including p. The imprecision degree w = p+ - p- ranges in {0.01, 0.05, 0.1, 0.5} (one value for the whole tree). Furthermore, and importantly, one sets Ce = ∅ in all instances. This assumption prevents from the insertion of bilinear constraints, and the CPLEX solver can therefore safely be used for evaluating strategies and testing dominance. The average execution times over 20 random instances are reported in Table 2 (symbol "-" means that n is greater than the number of chance nodes). Line ND gives the average number of non-dominated strategies at the root. Timeout was set to 1000 seconds. The size of the tackled instances are of course smaller than in the separable case, since the procedure handles sets of non-dominated elements, which is computationally more demanding than simply rolling back single values. As the dominance test is an important primitive in the procedure, Table 3 gives the average execution times of such tests according to the number n of random variables. We report here only the cases when a dominance relation is actually detected (average over 50 positive cases), since it takes longer than when it does not exist. Consistently with our expectation, the times strongly increase with n, that appears to be a key parameter for the efficiency of the procedure.

6 Conclusion

The optimization of min expected utility in sequential decision problems with multiple priors is known to be difficult from the algorithmic point of view, since the usual principles of dynamic programming do not apply. We have shown in this paper that the problem is indeed intractable. Evaluating a given strategy is NP-hard, even in a simple variant where the distinct random variables are mutually independent. Facing this difficulty, we distinguished two cases: separable and nonseparable decision trees. For each case, we have proposed a dedicated procedure to tackle the problem. Our first experiments are promising, although classic improvements still have to be explored, e.g. column generation [Kikuti et al., 2011], use of bounds to prune the search, etc.

The model proposed here is nevertheless quite simple from the viewpoint of expressivity. In a more general setting, one should provide the user with a richer way of expressing her knowledge about the random variables, e.g. by a credal network. Clearly, the more expressive the setting, the higher the risk of an increase in complexity. The challenge is to balance expressivity of the model and algorithmic efficiency.