On Decision-Theoretic Foundations for Defaults

1 Preliminaries

1.1 Decision Theory

We start by reviewing the basic setting of decision the­ ory. (For more details, see [Luce and Raiffa, 1957].) Decision theory deals with decisions in the face of uncertainty. A decision-theoretic context is a tuple (S, 0, A, Pr, U), where S is a set of possible states of the world before the decision is made; 0 is a set of pos­ sible outcomes of actions, i.e. , states of the world after the decision is made and carried out; A is a set of pos­ sible actions, each one is a function from S to 0; Pr is a probability measure overS that captures (subjective) likelihood of each state; and U is a utility function that maps outcomes in 0 to real numbers, that quantify the desirability of outcomes. In the following discussion, we usually assume that S, 0 and A are fixed, and do not mention them explicitly.

In a fixed decision-theoretic context the expected utility of an action a given evidence E ~ S is defined as

where Pr(sJE) is the conditional probability of s given the evidence E. Classical decision theory prescribes that given our assessment of a probability and utility measures and given evidence E, we should choose an action that maximizes expected utility, i.e., an action a such that EU(Pr,u)(aJE) = maxa'EA EU(Pr,u)(a'JE) . We denote by MEU(Pr,u)(E) the expected utility of the best action given E, i.e., maxa'EA EU(Pr,U) (a'JE), and by mEU(Pr,U) (E) the expected utility of the worst action, i.e., mina'EA EU(Pr,U) (a'JE). (From here on we omit the subscript (Pr, U) whenever it is clear from the context.)

We note that decision theory is only interested in the relative ordering of actions, given E , i.e., the relations between EU(aiE) and EU(a'IE). Since using a utility measure U'(-) = c1 · U(·) + c2, for some c1 > 0 and c2, leads to the exact same conclusions, decision theory treats U and U' as equivalent.

Decision theory usually does not deal explicitly with how we describe events or actions. However, in our dis­ cussion of defaults we describe events using a logical lan­ guage. We assume that there is a language £ that is closed under the usual propositional connectives and a truth-assignment 1r that assigns to each state s E S a subset of£. Intuitively, 1r(s) is the set of sentences that are true at s. We require that the following conditions hold:

• cp E 1r(s) if and only if ·cp 'f. 1r(s).
• cp 1\ 'ljJ E 1r(s) if and only if cp E 1r(s) and 'ljJ E 1r(s).

From now on we will use Pr( cp) as an abbreviation of Pr({slcp E 1r(s)}).

1.2 Defaults

The study of default statements has a long tradition in artificial intelligence (see [Ginsberg, 1987; Gabbay et al., 1993] for overviews). We denote by cp -+ 'ljJ the statement "if cp then by default '1/J". A typical ex­ ample is the following statements: Bird -+ Flies and Bird 1\ Penguin-+ ·Flies. These two defaults state that birds typically fly, but penguins are exceptional and typ­ ically do not fly: default statements differ from material implication in that they allow for exceptions. Defaults are intuitively appealing and seem to provide a natural language for specifying common-sense knowledge. For­ mal understanding of defaults turns out to be quite elu­ sive; there has been a great deal of discussion in the lit­ erature as to what the appropriate semantics of defaults should be. While there is little consensus on the seman­ tics of defaults, there has been some consensus on reason­ able "core" properties defaults. This core was suggested by Kraus, Lehmann and Magidor (1990) and consists of the following properties:

REF. cp-+ cp (Reflexivity).

LLE. If cp = cp', then from cp -+ 'ljJ infer cp' -+ 'ljJ (Left Logical Equivalence).

RW. If 'ljJ ~ '1/J', then from cp -+ 'ljJ infer cp -+ '1/J' (Right Weakening).

CUT. From cp -+ 1/!1 and cp 1\ 1/!1 -+ 'ljJ2 infer cp -+ 1/!2.

CM. From cp -+ 1/!1 and cp -+ 1/!2 infer cp 1\ 1/!1 -+ 1/!2 (Cautious Monotonicity).

OR. From cp1 -+ 'ljJ and cp2 -+ 'ljJ infer cp1 V cp2 -+ '1/J.

REF states that cp is always a default conclusion of cp. LLE states that the syntactic form of the antecedent is irrelevant: logically equivalent antecedents have the same consequences. RW describes a similar property of the consequent: If 'ljJ (logically) entails '1/J', then we can deduce cp -+ '1/J' from cp -+ '1/J. This allows us to combine default and logical reasoning. CM and CUT state that if 1/!1 is a default conclusion of cp, then 'ljJ2 is a default conclusion of cp if and only if it is a default conclusion of cp 1\ 1/!1: Discovering that 'ljJ1 holds (as would be expected, given the default) should not cause us to retract or add other default conclusions. OR states that we are allowed to reason by cases: If the same default conclusion follows from each of two antecedents, then it also follows from their disjunction.

Kraus, Lehmann and Magidor focus on consequence relations. A consequence relation captures a particular way we make assumptions. Given a pair of formulas <p and '1/J, this relation determines whether we are willing to assume 'ljJ given the knowledge cp. Formally, they define a consequence relation Cn to be the set of defaults, such that cp -+ 'ljJ E Cn if 'ljJ is among the consequences of <p. Kraus, Lehmann and Magidor characterize cumulative reasoning by system C, composed of REF, LLE, RW, CM, and CUT, and preferential reasoning by system P that contains system C and OR. A consequence rela­ tion is cumulative (resp. preferential) if it satisfies sys­ tem C (resp. system P), i.e., the set of defaults is closed under applications of these rules. They suggest that a "reasonable" consequence relation should be preferen­ tial. Furthermore they provide representation theorems for cumulative and preferential consequence relations us­ ing order relations over worlds. While we do not go into the motivation for these rules, they are accepted as rea­ sonable "core" properties that nonmonotonic reasoning should satisfy.

Surprisingly, Pearl (1989) describes a probabilistic no­ tion of defaults, t:-semantics, that leads to preferential consequence relations. Intuitively, t:-semantics accepts a default cp -+ 'ljJ if Pr(·'I/Jicp) is very small. Formally, to model "very small", t:-semantics examines behavior in the limit. A parameterized probability distribution 1 PPD is a family = {Prn I n > 0}. Given a PPD, PP, the induced consequence relation is

Then it can be shown that:

Lemma 1.1: [Goldszmidt et al., 1993] Cn is a prefer­ ential consequence relation if and only if there is a PPD PP such that Cn = Cn,(PP).

2 Decision-Theoretic Defaults

Our approach is based on the following idea: Given an appropriate measure of a set of states importance in the decision-making process, we can ignore those states of negligible importance. Thus, we will accept the default cp -+ 'ljJ if the "importance" of cp 1\ ·'1/J is very small in comparison to the importance of cp. In what follows, we investigate two definitions that try to capture this idea.

2.1 Basic Definition

One natural candidate is the maximal expected utility of a set. Suppose we know that we are in the set cp. Then we can write

Thus, Pr( ·'1/Jicp) MEU( cp 1\ ·'1/J) is an upper bound on the contribution of ·'1/J to the value of actions in cp. However, this may be misleading. For example, the expected util­ ity of all actions on cp 1\ ·'l/J might be the same high value. Intuitively, in this case ·'1/J plays no role in determining what action is best on cp, yet MEU(cp 1\ ·'l/J) is large. Moreover, as we noted above, any positive linear trans­ formation of utilities (i.e., define U'(-) = c1 · U(·) + c2 for some constants c1 and c2 , s.t., c1 > 0) should not change our conclusions. Yet, we can use such a trans­ formation to blow up the maximum expected utility on sets. Therefore, instead of using MEU as the estimate, we use the following "normalized" measure:

1 0ur presentation follows the formulation of [Goldszmidt et al., 1993].

2 To handle cases where Prn(cp) = 0, we define Prn(·?/Jirp) to be 0 when Prn(cp) = 0.

(Again, we omit (Pr, U) when it is clear from the con­ text.) We call G(A) the gain of A, since it measures how much can be gained if we choose a good action instead of a bad one on A. It is easy to check that Pr(·'I/Jicp) · G(cp 1\ ·'l/J) bounds the potential loss incurred by ignoring ·'1/J in the computation of expected utilities of actions:

However, we should remember that this error is relative to G(cp), since we cannot do worse than mEU(cp) nor better than MEU(cp). This suggests that when we are willing to tolerate an error ratio of E we can ignore ·'1/J when we know cp if

That is, Pr('l/Jicp) · EU(alcp 1\ '1/J) is E close to the actual expected utility on a when we know cp.

However, we usually do not want to fix an arbitrary E. We overcome this problem by examining what happens in the limit when our threshold approaches 0. A param­ eterized decision-theoretic context (PDC) is a sequence {(Prn, Un)ln 2: 0} of decision-theoretic contexts. Such a sequence describes our assessment of the decision prob­ lem when we successively lower the size of "ignorable" · quantity. We define our first notion of defaults, which we will call "weak" for reasons that will become apparent below.

Definition 2.1: A PDC P = {(Prn, Un) In 2: 0} (weakly) satisfies the default cp --t 'lj;, denoted P Fw cp-+ '1/J, if

where Gn is an abbreviation for G(Prn,Un)· 3 I We define the consequence relation Cnw ( P) = { cp -+ 'lj; I p Pw cp --t '1/J}.

Note that, according to this definition, we ignore ·'1/J if the product of Pr( ·'1/Jicp) and the gain of cp 1\ ·'l/J is small.

3 In order to handle defaults in situations where Gn (A) = 0 in a reasonable manner, we use throughout the paper the following definition: ; = 0 whenever x = y = 0, and ; is infinitely large, i.e., unbounded, when x > y = 0.

In line with our intuitions, this definition weighs both the probability of the set, and the utility of actions on states in the set. It is also easy to see that this definition generalizes E-semantics. If we choose utilities such that Gn(A) = c, for some constant c, for all non-empty sets A, then (2) becomes limn--too Prn(·'I/Jicp) = 0, which is equivalent to the definition of defaults in E-semantics. 4 Thus, under certain choices of the utility function our definition becomes equivalent to €-semantics.

Proposition 2.2: There is a utility function Ue, such that for each PPD PP = {Prn In 2: 0}, the PDC Ppp = {(Prn,Ue) 12: 0} is such that Cne(PP) = Cnw(Ppp).

Above we stated the desideratum that defaults should not affect the quality of our decisions. Intuitively, an ac­ tion is approximately optimal if, in the limit, its expected utility over E is almost as good as MEUn(E). Formally, we say that an action a is approximately optimal on a set E with respect to a PDC P, if

Again, we must normalize by Gn(E) to avoid being sen­ sitive to positive linear transformations. We say that a default cp -+ 'ljJ is approximation safe (with respect toP) if every approximately optimal action on cp 1\ 'ljJ is also approximately optimal on cp. This implies that choosing a good action on cp 1\ 'ljJ leads to a good action on cp.

Theorem 2.3: If P f=w cp-+ 'lj;, then cp-+ 'lj; is approx­ imation safe w. r. t. P.

Definition 2.1 satisfies our stated criteria of approxi­ mation. However, the induced consequence relations, in general, are not cumulative. In particular, RW does not hold. Consider the following example, where we have two propositions p and q, and four equiprobable states. Utilities (for any n) of two actions a1 and a2 are defined according to this table:

It is easy to check that true --t ·P is satisfied according to Definition 2.1, simply because G(p) = 0. However, true --t (·pV·q) is not satisfied since G(pl\q) = 10. RW is violated because the gain of a set might be small, while the gain of (some of) its subsets might be very high. This phenomena occurs because of "canceling out", i.e., ac­ tions that are good on one subset are bad on another, and vice versa. In our example, a1 and a2 "cancel out" on p. When we examine the whole set, this phenomenon is undetectable, since we only examine the expected util­ ities of actions. It is easy to construct similar counterex­ amples to CUT, CM and OR.

This example shows that Definition 2.1 is quite weak. Before we discuss this issue, we examine what properties are satisfied by this definition. We define the following weak variant of RW:

4 In fact, it suffices to require that Un is such that for all non-empty sets A, 0 < c :S Gn(A) :S d for some constants c, d. This implies that P f=w cp -+ 1/J if and only if {Prn} f=. cp-+ 1/J .

RW w. If 'l/J1 => 'l/J2, then from <p -+ 'l/;1 and <p -+ ( 'l/;2 => 'l/;1) infer <p -+ 'l/J2 .

To understand the nature of this rule, we need to ex­ amine properties of G. As we noted above, if B c A, then G(A) does not necessarily provide an upper bound on G(B). This is an artifact of "canceling out", i.e., a big difference in the expected utility of actions on B is canceled out by their expected utility on G(A \B) . But this implies that if G(B) is much bigger than G(A), then G(A \B) must also be big. In fact we can show that if G(A) is "small", then G(B) and G(A \B) must be of the same magnitude. Using this insight we can understand RW w : From <p -+ 'l/;1 we infer that G ( <p 1\ ·'l/Jl) is small. The formulae <p 1\ ·'l/;1 1\ ·'l/;2 and <p 1\ ·'l/;1 1\ 'l/;2 form a disjoint partition of <p 1\ ·'l/;1; if one of them is small, then the other is also. From <p -+ ( 'l/;2 => 'lj;l) we conclude that G( <pi\ · 'l/;1/\ 'l/;2) is small, hence G( <pi\ · 'l/;1/\ ·'l/;2) is small. But, this is exactly the desired conclusion.

Similar reasoning leads to the following weak versions of CUT and CM:

CUTw. From <p-+ 'l/;1, <p-+ 'l/J1 V 'l/J2 and <p 1\ 'l/J1 -+ 'l/J2, infer <p -+ 'l/J2 .

CMw. From <p -+ 'l/J1, <p -+ 'l/J1 V 'l/J2 and <p -+ 'l/J2, infer <p 1\ '1/Jl -+ 'l/;2 °

Let system Cw be the system containing REF, LLE, RW w, CUT w and CMw. We can then show:

Theorem 2.4: If P is a PDC, then Cnw(P) satisfies system Cw.

It is unclear to us at this stage whether system Cw is complete, or whether there are other rules that hold for this definition. Notice that From CUT w and RW we can derive CUT, and from CMw and RW we can derive CM. Thus, the main difference between system Cw and system C is the weaker version of right weakening.

These results show that the most natural definition of defaults that satisfies our decision-theoretic desiderata (i.e., being approximation safe) has very weak proper­ ties. We consider the failure to satisfy properties of cu­ mulative reasoning to be a serious one. Two properties of cumulative reasoning are especially important. The first is the AND property:

This property is derived from system C (see [Kraus et al., 1990]) . This property deals with modularity of as­ sumptions. It states that if we can safely assume 'l/;1 and also safely assume 'l/;2, then we should be able to assume both. This property, however, is not guaranteed by Defi­ nition 2.1. The other property is CM. It states that if we happen to learn that some of our assumptions are true, we do not retract our previous assumptions. Suppose, for example, that I assume by default that my car will start, and that it is a sunny day. If, I then learn that the day is sunny, it seems intuitive that I should not need to retract my conclusions about the car. Again, this property is not guaranteed by Definition 2.1.

In general, we believe that properties of cumulative reasoning are indeed basic properties of any notion of de­ faults; if we do not satisfy cumulative reasoning, we must reexamine our assumptions whenever we have additional information, even if this information is consistent with our previous default conclusions. Such behavior seems undesirable. Thus, we would like to add the additional desideratum that accepted defaults are cumulative. This leads us to ask: is there a natural definition of decision­ theoretic defaults that satisfy both desiderata?

2.2 Strong Definition

We have seen that our definition of defaults is "almost" cumulative, except that it does not satisfy RW. The problem was that even if G(A) is small, it might be that G(B), for some subset B of A, is very large. In other words, the measure G(A) is not informative about the behavior of actions on subsets of A. To overcome this problem we introduce a more cautious measure of sets. We define

for non-empty A, and define t.{Pr,U) (0) = 0. (Again, we, omit the subscript when it is clear from the context.) It is easy to check that if B ~ A, then Pr(BIA) · t.(B) ~ t.(A) . Thus, t.(A) is more informative about the be­ havior of subsets of A than G(A). In particular, if for some t,

then we can conclude that

for all '1/J' such that 'ljJ => 'l/J'. This suggests that the following definition satisfies our desiderata.

Definition 2.5 : A PDC P = {(Prn, Un) I n ~ 0} (strongly) satisfies the default <p -+ 'lj;, denoted P f=. <p-+ '1/J, if

where 6.n is an abbreviation for t.(Prn,Un)· I

We define the (strong) consequence relation of P as Cns(P) =clef {<p-+ 'l/JIP F s <p-+ '1/J}. It is easy to verify that this definition of defaults is indeed more restrictive than Definition 2.1.

Proposition 2.6: Let P be a PDC. If P Fs <p -+ 1/J, then P Fw <p-+ '1/J.

An immediate corollary is that if <p -+ 'ljJ is strongly satisfied by P then it is approximation safe with respect to P. Moreover, we can show that this notion of defaults satisfies cumulative reasoning.

Theorem 2.7: If P is a PDC, then Cns(P) satisfies system C .

We conjecture that system C is complete with respect to the class of all PDCs, i.e., a consequence relation Cn is cumulative if and only if there exists a PDC P , such that Cn = Cns(P).

This result shows that Definition 2.5 satisfies our desiderata using a natural decision-theoretic construc­ tion. It might seem that our definition of t. is somewhat arbitrary. Indeed, as we show in the full version of this paper, similar properties are satisfied by other measures as well. Roughly, we show that 1:1 1 satisfies Proposi­ tion 2.6 if and only if D.~ (A) provides an upper bound, in a certain precise sense, on G n (A) , and 1:1 1 satisfies The­ orem 2.7 if and only if D.(A) provides an upper-bound on Pr(BIA) · D.(B) for B ~ A. We claim that D. is the most natural member of this family.

2.3 The OR Rule

The last section showed how to obtain cumulative rea­ soning in our framework. Recall that preferential reason­ ing is defined to be cumulative reasoning combined with the OR rule. Most accepted semantics of defaults, in particular preferential structures and ~:-semantics, lead to preferential consequence relations. Is OR satisfied in the two approaches we described? As the following ex­ ample shows, this is not necessarily the case.

Example 2.8: Consider the following scenario. The agent is contemplating two possible investments. He can either buy the stocks of company A, an oil producer, or those of company B, a plastic manufacturer. The success of either investment is greatly dependent on changes in the price of oil. If oil prices rise, company A's profits will increase. However, since plastic is an oil by-product, the cost of raw material for company B will rise, and its profits will decline. On the other hand, if oil prices decline, company A's profits will decline, and company B's profits will increase. This situation is complicated by news of a technological break-through in oil refinement . This technology is expected to decrease the cost of oil refinement, reducing the costs for both companies. But it will have a more dramatic effect on company B by improving the quality of its raw material. However, this technology is still in early stages of development, and is not likely to have any effect on the market in the next few years.

These considerations are captured by the following (parameterized) decision theoretic setting.

Suppose the agent knows that oil prices will rise. Then, he can ignore the possible emergence of new technologies. To see this, G( o+) = 2 + 1/n, and G( o+ 1\ T) = 3/n, thus we would accept o+ -t --, T. Similar consideration show that if the agent knows that oil prices will fall, he can also ignore the new technology, i.e., o- -t --, T. What happens when the agent does not know whether oil price will rise or fall? In that case, he cannot ignore the possibility of new technology. Without knowledge about the direction of oil prices, investing in A or in B is more or less the same, except when the new technology arrives. In that situation the plastic industry is clearly a better choice. This type of consideration, which is secondary when the agent has more knowledge, becomes a ma­ jor consideration in the decision without that knowledge. Technically, we have that G(O+ v o-) = G(T) = 10/n, thus we cannot accept the default o+ V o- -t --, T. And if the agent accepts this default, he is likely to make the wrong choice, i.e., buy into the oil company. I

In retrospect, it is not too surprising that OR is not satisfied in our system. The essence of OR is reasoning by cases: If when <p1 holds we can assume '1/J, and when <p2 holds we can assume '1/J, then we should also assume '1/J when we know that one of these cases is true. However, as noticed by Kraus, Lehmann and Magidor, this rule might be inappropriate when we read the antecedent of the default as "I only know <p" (which is basically how we interpret this default): "I only know <p" is not equivalent to "I only know <p 1\ '1/J" or "I only know <p 1\ ·'1/J."

3 Poole's decision-theoretic defaults

Poole (1992) introduces a semantics for defaults that is also based on decision theory. His motivation is similar to our own, yet his proposal is very different. We now briefly review his semantics. A default in Poole's system has the form <p '"'-'+ a, and reads "Given evidence <p, do action a". This default caches information about the best action to perform when we get evidence <p. Such a default is accepted in a decision-theoretic context (Pr, U) if a maximizes the expected utility over <p, that is

Poole argues that this definition naturally captures many real-life defaults. He gives examples of default statements that conclude what action to perform, such as "if you are in Vancouver in November, carry anum­ brella". He shows that his semantics satisfies several desirable criteria, such as non-monotonicity, specificity, and ignoring irrelevant information.

Poole would ultimately want his semantics to capture regular defaults, such as "birds typically fly." However, these defaults have formulas as their conclusions, not actions. Poole attempts to overcome this problem using the following idea: With each proposition p, he asso­ ciates three actions: pt, pf, pu. These actions stand for: assume that p is true, assume that p is false, and do not make assumptions on p, respectively. Poole then represents defaults such as "birds typically fly" as Bird '"'-'+ Flyt. He shows that under certain (rather strong) assumptions on the utility of these actions, he can give accepting conditions for defaults in terms of Pr and U. Poole's solution forces us to examine utilities of actions of a specific form - making assumptions. It seems to us that unless we have a good model of how making assumptions affects the choice of "real" actions (i.e., ac­ tions in the world), it is quite difficult to assess their utility. Moreover, it is unclear whether such a model will satisfy requirements of Poole's analysis. Our approach to defaults circumvents these problems by examining the utility of the actual actions available to us when we face the decision. We believe this approach is more natural. In any particular context we are facing a choice between several concrete decisions. The context describes the possible outcomes these decisions can lead to and their resulting utilities.

In spite of this criticism, we believe that defaults of the form <p '"'-'+ a are useful, and suggest that Poole's defaults can be combined with our notion of defaults. This leads to a system where we can state defaults about actions to perform, as well as assumptions that can be made. We now outline the synthesis of Poole's defaults and our system into a joint framework.

Recall that Poole's original semantics for <p '""'-+ a is that EU(ai<p) = MEU(<p). We want to define an similar definition in terms of PDCs. Instead of stating that a is the best action, given <p, we state that a is a safe approximation. Formally, a PDC P satisfies <p '""'-+ a if (3) holds. This definition is very much in the spirit of Poole's original one, and we can show that the same properties are satisfied. Moreover, there are interesting interactions between Poole's defaults and ours.

Theorem 3.1: The following rules of inference are valid for-+ and'""'-+:

• If <p = <p 1 , then from <p '""'-+ a infer <p 1 '""'-+ a.
• From <p 1\ 'lj; '""'-+ a and <p 1\ ·'l/! '""'-+ a infer <p '""'-+ a.
• From <p -+ 'lj; and <p 1\ 'lj; '""'-+ a infer <p '""'-+ a.
• From <p-+ 'lj; and <p '""'-+ a infer <p 1\ 'lj; '""'-+ a.
• From <p-+ false infer <p '""'-+ a.

This theorem shows that our definition of Poole's default satisfies the sure thing principle [Savage, 1954]: if a is a good action when I know <p 1\ 'lj;, and a good action when I know <p 1\ ·'l/!, then it is a good action when I just know <p. Moreover, the third and fourth properties show the direct relation between our defaults and approximately good actions: if <p-+ 'lj;, then a good action when I know <p is also good when I know <p 1\ 'lj;, and vice versa. We believe that the combination of both types of default is useful. In future work we intend to apply this logical framework in applications to reasoning about decisions and knowledge compilation.

4 Discussion

Our starting point was the thesis that knowledge repre­ sentation and reasoning methodologies are better under­ stood in terms of their role in determining the behavior of agents. Once we have establish this role, we can gain a better understanding of the methodology in question. We examined one particular role of default reasoning. Focusing on this role helped us to determine desider­ ata that defaults should satisfy and to derive decision­ theoretic semantics for defaults that meet these desider­ ata. Given this role, we can motivate what conclusions are entailed from a knowledge-base of defaults. But more importantly, providing a role for defaults is the first step toward understanding what defaults the knowledge-base should contain in the first place. As our approach sug­ gests, the content of the knowledge-base depends on the specific context of the agent: his beliefs (i.e., probabil­ ity) his goals (i.e., utility), and the actions available to him.

Our semantics grounds defaults in decision-theoretic contexts. Intuitively, this is because we use well­ understood notions (i.e., probability and utility) instead of abstract ones (e.g., preferential structures). This choice allows us to relate defaults to other forms of knowledge. In this paper we examined one candidate, Poole's default actions. We believe that knowledge is not , in general, homogeneous. It is composed of various types of statements, and clearly there are interactions be­ tween these statements. Grounding these different types of statements in a common basis allows us to understand these interactions. In our case, the interactions between Poole's defaults and ours described in Theorem 3.1 are not arbitrary; they are a consequence of the semantics of both defaults in terms of decision-theoretic contexts.

Our definitions rely on PDCs - sequences of decision­ theoretic contexts. These structures, which may not ap­ pear intuitive at first sight, should be understood as a mathematical idealization. This idealization allows us to talk about very small quantities or very big quantities, and in particular, the quotient t, without committing to a particular value. This point highlights an important problem in nonmonotonic reasoning as well as probabilis­ tic reasoning: what is a an acceptable notion of approx­ imation? It is clear that setting a fixed threshold value is a crude way of defining approximation. Similarly, the use of limits is also quite crude. For example, we do not examine the rate of convergence nor do we provide a methodology for obtaining these sequences.

Of course, in real applications, we can often set a threshold value, below which things are considered small enough to be ignored. Once we fix this threshold we accept a default when the expression in (2) (or (5)) is smaller than this threshold. This definition approxi­ mates the notions we examined here. In particular, it does not satisfy the inference rules we describe. However, we can reason using these inference rules and get conclu­ sions that might violate the fixed error margin. This pro­ vides a way of getting "fast and dirty" conclusions. Such an approach has been applied in the in t-semantics liter­ ature, and recent work [Darwiche and Goldszmidt , 1994] indicate that such approximations might be quite useful. A possible avenue of future research is to use this method in knowledge-compilation of decision-theoretic informa­ tion [Henrion et al., 1991]. Roughly, in this method, off-line computation will generate a set of defaults us­ ing some parameter t. These defaults (and their logical consequences) will be used at run-time to ignore various possibilities, hence reducing the amount of time spent in evaluating possible actions. As with any type of ap­ proximation, there is a tradeoff between the quality of the inference made (decision in this case) and the time spent on making this inference. Decision-theoretic de­ faults can be viewed as summarizing the information en­ coded in the underlying decision-theoretic context and may allow for faster on-line computations.

Our analysis is based on static or "one-shot" decision theory. Recently, there has been much work on decision making in dynamic environments (e.g., Markov Decision Processes [Puterman, 1994]). The notion of expected utility in these models is somewhat more complicated. However, similar considerations of probability and util­ ity apply when attempt to ignore various possibilities, i.e., we would like to ignore a possibility if it has small impact on the quality of actions we later choose. We in­ tend to examine notions similar to default assumptions in the framework of Markov Decision Processes and to use these result to provide fast and approximately optimal planning in this setting.

Finally, we note that the approach we examine in this paper is not the only one for justifying defaults. In particular, several recent works [Pearl, 1993; Boutilier, 1994] examine approaches to qualitative decision theory. Roughly, these are analogues to decision theory where defaults play the role of probabilities, and analogues of utility, and expected utility (i.e., a combination rule) are suggested. All of these approaches are descriptive in that they espouse a particular procedure for decision-making. We believe that it is important to understand the nor­ mative foundations of such qualitative decision theory. This involves finding reasonable "rationality postulates" (in the sense of Savage's (1954) normative foundation for decision theory) that characterize these qualitative deci­ sion procedures. Initial results in this spirit appear in [Brafman and Tennenholtz, 1994], although in a some­ what different context. Such results should help us un­ derstand the consequences of adopting a specific repre­ sentation for decision making under uncertainty. This type of investigation, which we are currently undertak­ ing, should elucidate the tradeoffs between qualitative representations and quantitative representations.

Acknow ledgernents

The authors are grateful to Craig Boutilier, Jon Doyle, Hector Geffner, Moises Goldszmidt, James Kittock, Daphne Koller, Yoav Shoham, the anonymous referees and particularly Joe Halpern, for comments on drafts of this paper and useful discussions relating to this work. The first author was supported in part by ARPA grant AF F 49620-94-1-0090 and NSF grant IRI-9220645. The second author was supported in part by the Air Force Office of Scientific Research ( AFSC), under Contract F49620-91-C-0080.