# samplingbased_belief_revision__13eba587.pdf

Sampling-Based Belief Revision

Michael Thielscher University of New South Wales, Australia

mit@unsw.edu.au

Model sampling has proved to be a practically viable method for decision-making under uncertainty, for example in imperfect-information games with large state spaces. In this paper, we examine the logical foundations of sampling-based belief revision. We show that it satisfies six of the standard AGM postulates but not Vacuity nor Subexpansion. We provide a corresponding representation theorem that generalises the standard result from a single to a family of faithful assignments for a given belief set. We also provide a formal axiomatisation of sampling-based belief revision in the Situation Calculus as an alternative way of reasoning about actions, sensing, and beliefs.

1 Introduction Model sampling is a viable approach to automated decisionmaking under uncertainty in a variety of domains; examples include the control of autonomous robots [Fox et al., 1999; Hollinger and Sukhatme, 2014] and computer game playing, where sampling is the method of choice to cope with highly incomplete knowledge of the game state in most imperfectinformation games [Frank and Basin, 1998; Ginsberg, 2001; Richards and Amir, 2012]. In all of these applications, agents base their decisions on a small set of samples from the set of all complete models that are consistent with their observations. When further information is acquired, models that turn out to be inconsistent with the new observations are resampled in order to maintain both consistency as well as a uniform size of the sample set [Frank and Basin, 1998; Edelkamp et al., 2012; Schofield et al., 2012].

From a logical perspective, when agents base their decisions on model sampling then they can be said to believe that the world is fully characterised by the samples. If, for instance, all models randomly sampled by a Bridge-playing agent [Ginsberg, 2001] happen to assume that their partner carries at least one card of each suit, then the agent concludes that the player will have to follow suit on any lead card. However, rational agents operating with beliefs (rather than knowledge) ought to take into account the possibility that their beliefs may be wrong, for example when a subsequent observation implies that a player does in fact not have a card

of a specific suit. When this happens, the agent needs to resample inconsistent models [Frank and Basin, 1998], thereby causing him to revise his beliefs in the light of new information.

In this paper, we study the formal properties of this kind of belief revision operators that follow from the sampling-based approach to handling incomplete information. The purpose of this study is two-fold:

1. A formal analysis of how model sampling affects the be-

liefs of an agent provides for a deeper understanding of the formal properties of an approach that has proved successful in a range of applications including robot control and computer game playing. 2. A formalisation of model sampling as a general princi-

ple for belief revision enriches the suite of traditional operators based on the AGM postulates [Alchourr on et al., 1985], especially since it promises to be a viable method for applications with large state spaces for which classical Belief Revision operators are not practical. Our investigation into the logical foundations for samplingbased belief revision will show that it satisfies six of the eight standard AGM postulates but not Vacuity nor Subexpansion. The intuitive reason is that when some but not all sampled models are consistent with new observation φ, then those that contradict φ get resampled. These new models may then invalidate previously held beliefs despite the fact that the presence of other samples that are consistent with φ imply that the new observation is consistent with the agent s original beliefs.

As a simple example, consider a situation in an unspecified card game where there are the 6 outstanding cards |2, 2, |3, ~3, }3, }4, and suppose that an agent has randomly generated the following two samples for the belief about the remaining hand (consisting of two cards) of another player: K = {{|3, }3}, {|2, ~3}}. Suppose further that the player is observed not to follow suit when hearts is played. This observation, which we shall write φ = ~, renders the second model inconsistent (but not the first). If we assume that resampling this model results in the new sample set K φ = {{|3, }3}, { 2, }4}}, then the following can be said about the beliefs of the agent before and after observing φ:

1. In K, the agent believes that the player has a |-card. 2. K is consistent with φ = ~.

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16)

(AGM-1) K φ = Cn(K φ) (Closure) (AGM-2) φ 2 K φ (Success) (AGM-3) K φ K + φ (Inclusion) (AGM-4) If φ 62 K then K φ K + φ (Vacuity) (AGM-5) If φ is consistent, then K φ is consistent (Consistency) (AGM-6) If φ , then K φ = K (Extensionality) (AGM-7) K (φ ) (K φ) + (Superexpansion) (AGM-8) If 62 (K φ), then K (φ ) (K φ) + (Subexpansion)

Figure 1: The eight AGM postulates.

3. In K φ, the agent no longer believes that the player has

These three properties together violate the Vacuity postulate, which satipulates that if φ is consistent with K, then every belief in K should also be a belief in K φ. We will show that for a similar reason, the Subexpansion postulate is not satisfied either.

We will provide a representation theorem for belief revision operators that satisfy all but these two AGM postulates. The result will be a generalisation of the classical representation theorem [G ardenfors and Makinson, 1988] from single to a family of faithful assignments for a given belief set.

The remainder of the paper is organised as follows. In the next section, we recall the necessary notions and notations for belief revision and logical reasoning about actions. In the section that follows, we define and analyse model sampling for belief revision in the context of the AGM framework. Thereafter, we state and prove the representation result. Finally, we apply our general concept of model sampling for belief revision to develop a variant of the classical Situation Calculus for reasoning about actions, sensing and beliefs based on (re-)sampling.

2 Background

We will formulate and analyse sampling-based belief revision in the context of the classical AGM-based approach and assuming a logic language L generated from a finite set P of propositions. By Cn(φ) we denote all classical logical consequences of a sentence, or a set of sentences, φ. K + φ stands for Cn(K [ {φ}). As usual, a propositional interpretation (world) is a mapping from P to {>, ?}. The set of all interpretations is denoted by W. If an interpretation w truthfunctionally maps a sentence, or a set of sentences, φ to >, then w is called a model of φ (denoted by w |= φ). Mods(φ) denotes the set of all models of φ, and the latter is consistent iff Mods(φ) 6= ;. Formulas, or sets of formulas, φ and are equivalent, written φ , iff Mods(φ) = Mods( ).

AGM Postulates Let the beliefs of an agent be represented by a set of sentences K in L. Any new evidence is a sentence φ in L, and the result of revising K with φ, denoted by K φ, is also a belief set over L. Alchourr on et al. [1985] put forward eight postulates for belief revision operators, which are given in Figure 1. Readers are referred to G ardenfors and Makinson [1988] for a detailed discussion of the motivation and interpretation of these postulates.

A Representation Theorem The classical representation theorem [G ardenfors and Makinson, 1988] characterises belief revision operators that satisfy the AGM postulates with the help of preference relations over worlds (i.e. models). A total pre-order (possibly indexed) is a reflexive, transitive binary relation such that either β or β holds for any , β. The strict part of is denoted by <, that is, < β iff β and β 6 . As usual, = β abbreviates β and β . Given any total pre-order over a set S, by min(S, ) we denote the set { 2 S : β for all β 2 S}. Definition 1 A function that maps each belief set K to a total pre-order K on W is called a faithful assignment if it satisfies the following conditions.

If w1, w2 |= K, then w1 =K w2. If w1 |= K and w2 6|= K, then w1 <K w2. If J K, then J= K. The intuitive meaning of w1 K w2 is that w1 is at least as plausible as w2 from the viewpoint of the agent who possesses the belief set K. The classical representation theorem says that belief revision operators that satisfy the AGM postulates can be characterised with the help of faithful assignments and vice versa. Theorem 1 A revision operator satisfies Postulates (AGM-1) (AGM-8) iff there is a faithful assignment that maps a belief set K to a total pre-order K such that

Mods(K φ) = min(Mods(φ), K)

Reasoning About Actions Model-sampling has been successfully used as a general technique for agents that act and sense in a dynamic environment which they cannot fully observe. This includes the control of autonomous robots [Fox et al., 1999; Hollinger and Sukhatme, 2014] and computer players for imperfect-information games [Frank and Basin, 1998; Ginsberg, 2001; Richards and Amir, 2012]. Action calculi for knowledge representation provide the logical foundations for reasoning about actions, with the Situation Calculus being the classical one [Mc Carthy, 1963]. We briefly recapitulate the basic concepts of this calculus in a variant that uses a special fluent to represent the knowledge of agents [Scherl and Levesque, 2003].The Situation Calculus is a predicate logic with a few pre-defined language elements:

constant s0, which denotes the initial situation, along

with constructor DO(A, S) to denote the situation resulting from doing action A in situation S;

predicate HOLDS(F, S), which denotes that fluent F

(i.e., an atomic state feature) is true in situation S; predicate POSS(A, S), which denotes that action A is

possible in situation S. For example, a fluent Has Card(P, C, V ) may be used to indicate that player P holds a card of suit C and value V . The effect of playing a specific card, represented by the action Play(P, C, V ), on all cards being held could then be axiomatised by the following so-called successor state axiom [Reiter, 1991] (free variables are assumed to be universally quantified):

POSS(A, S) !

( HOLDS(Has Card(P, C, V ), DO(A, S)) $

HOLDS(Has Card(P, C, V ), S) A 6= Play(P, C, V ) )

Put in words, all cards held in situation S will also be held in the situation after doing action A in S except for the card that happens to have been played.

Scherl and Levesque [2003] use the special fluent K(S0, S) to be read as: situation S0 is accessible from situation S in order to formally represent, and reason about, the knowledge of an agent within the Situation Calculus:

KNOWS(Φ, S)

def= 8S0. K(S0, S) ! Φ[S0] (1)

Here, Φ is a reified formula in which fluents are used as predicates (without situation argument); and Φ[S0] is Φ with all fluents F replaced by HOLDS(F, S0). For example,

KNOWS(8X. Has Card(p, ~, X), s0)

is 8S0. K(S0, s0) ! 8X. HOLDS(Has Card(p, ~, X), S0), meaning that the agent knows player p has no ~-card in the initial situation as this is true for all s0-accessible situations.

The effects of actions, including sensing, on the knowledge state of an agent are defined by the successor state axiom for the special fluent K [Scherl and Levesque, 2003]:

POSS(A, S) !

K(S00, DO(A, S)) $

9A0, S0. S00 = DO(A0, S0) K(S0, S)

8P. SENSE(P, A, S) $ SENSE(P, A0, S0)

Put in words, S00 is a possible situation after action A in S if, and only if, S00 is obtained by doing A in a situation S0 that was conceivable in S; and the agent s sensing result for A0, S0 is equivalent to his sensing result for the actual A, S.1

3 Model Sampling for Belief Revision In sampling-based approaches to decision making under uncertainty, agents approximate their incomplete knowledge about the state of a system with the help of a fixed, and typically small, number of sampled models that are consistent with given observations. At any point in time, the current collection of samples can be viewed as the agent s belief about the current state. New observations act as filters through which only those samples are kept that are consistent with

1SENSE(P, A, S) means that P, the encoding of a potential sensing result, is indeed perceived after doing action A in situation S.

the new information. Since the accuracy of the belief usually decreases with a shrinking number of samples, it is important that models which have been filtered out are being resampled, that is, get replaced by new and consistent samples. The belief of the agent thus gets revised. In the following, we will formalise this very general concept of (re-)sampling in the context of belief revision in order to analyse its underlying properties.

Various strategies have been used for the actual process of generating a set of models that are consistent with given observations. They vary from be highly domain-specific [Ginsberg, 2001] to domain-independent but according to a specific process [Richards and Amir, 2012; Schofield et al., 2012] to purely random resampling [Fox et al., 1999]. To accommodate these different types of strategies in our systematic analysis of how resampling changes the beliefs of an agent, we assume that models are generated in an arbitrary but fixed order, which may have been obtained by a purely random process. Example 1 Suppose the beliefs about the remaining two cards of a player are generated from 6 outstanding cards according to some, possibly purely random, sampling strategy in the order shown in Figure 2. Let us assume an agent who maintains a sample set S of size 2, then the initial set of samples without further information would consist of the first two in the series of generated models, that is,

S = {w1, w2} = {{|3, }3}, {|2, ~3}} (3) Now, consider two examples of new observations.

First, suppose we learn that the player whose hand we sample does not have a ~-card. The first model, w1, is consistent with this new information and hence will be retained, whereas the second sample, w2, is not. Resampling the inconsistent model means to consider the next world in the sequence of generated samples that is consistent with ~, which is w4. This results in the new sample set2

S / ( ~) = {w1, w4} = {{|3, }3}, { 2, }4}} (4) Second, suppose we make the more specific observation that the player does not own a ~-card and that one of his cards is }3. Again, w1 is consistent and remains in the sample set while the second sample is replaced by the next model in sequence after w2 and consistent with the new information ~ }3, which is w6. This results in the new sample set

S / ( ~ }3) = {w1, w6} = {{|3, }3}, {}3, }4}} (5) The beliefs of an agent who approximates the state of a system by a set of samples are all the logical consequences of the sample models. Definition 2 The belief set determined by a finite set of samples S = {w1, . . . , wn} W is given by

K|S = { : wi |= for all wi 2 S} (6) Recall, for instance, the initial sample set S given by (3) in Example 1. It follows that ~ 62 K|S but (|2 _ |3) 2 K|S.

We are now in a position to formalise the concept of resampling in belief revision, based on an arbitrary but fixed strategy for the generation of sample models.

2The notation S / φ below is used to denote the result of resampling a set of models S upon making a new observation expressed by sentence φ.

{|3, }3} {|2, ~3} {~3, }4} { 2, }4} { 2, ~3} {}3, }4} . . . {~3, }3} w1 w2 w3 w4 w5 w6 . . . w15

Figure 2: A random sequence of samples for a 2-card hand generated from the 6 outstanding cards |2, 2, |3, ~3, }3, }4.

Definition 3 Let S be a given sample set of size n > 0. Consider an arbitrary but fixed order w1 <S w2 <S w3 <S . . . on W \ S in which further samples are generated. Let φ be a sentence, then resampling S for φ results in the set of worlds

S / φ = (S \ Mods(φ)) [ mink(Mods(φ), <S) (7)

k = n |S \ Mods(φ)| mink(Mods(φ), <S) are the m smallest worlds in

w1 <S w2 <S w3 < . . . that are models of φ but not in S, where m = min(k, |Mods(φ)|).3

Put in words, all samples consistent with φ are retained, and all other models are replaced by the next m generated worlds that are consistent with φ and different from any of the retained samples. If φ admits a sufficient number of models, then the sample size n is retained (case m = k), otherwise it is reduced to the number of remaining consistent models.

Example 2 Recall Example 1. It is easy to see that for sample size n = 2, (4) and (5) satisfy the conditions of Definition 3 wrt. the sampling order given in Figure 2. It is also easy to see that there is only one world that satisfies | }, hence S / ( | }) = {{ 2, ~3}} must result in a set smaller than the original sample size of 2. Resampling for an observation that has no model results in the empty set, e.g. S / (|3 |3) = ;.

As the main result in this section, we show that samplingbased belief revision satisfies six of the eight classical AGM postulates but not Vacuity nor Subexpansion (cf. Figure 1). Theorem 2 Let K|S be a belief set determined by a sample set S of size n > 0 and / the operation of resampling wrt. any given order for generating samples. The corresponding belief revision operator defined by

K|S φ = K|S/φ (8)

satisfies (AGM-1) (AGM-3) and (AGM-5) (AGM-7). Proof: We prove each postulate in turn.

(AGM-1) follows by Definition 2, equation (6). (AGM-2) holds by Definition 3, equation (7), which im-

plies that S /φ Mods(φ), hence φ 2 K|S/φ according to equation (6). For (AGM-3) we observe that if 2 K|S φ then w |=

for all w 2 S / φ according to (8), hence w |= for all w 2 S \ Mods(φ) according to (7). It follows that 2 K|S + φ according to (6). (AGM-5) holds since Mods(φ) 6= ; implies S / φ 6= ;

according to (7); hence, if φ is consistent then by (8), K|S φ is consistent too.

3If |Mods(φ)| = 0 then S = ;, i.e., no consistent sample exists.

(AGM-6) follows from Definition 3, equation (7), since

φ implies Mods(φ) = Mods( ), hence S / φ = S / , which implies K|S φ = K|S by (8). For (AGM-7), recall Definition 3, equation (7), and con-

sider any sample w 2 S / φ that satisfies not only φ but also . By Definition 3 and because the same sampling strategy <S is used when constructing S / (φ ), it follows that w is either among the samples in S that satisfy φ , or is among the first m generated samples that satisfy φ , where m is given as in Definition 3. Hence, w 2 S/(φ ). Therefore, (S/φ)\Mods( ) S / (φ ). This implies that K|S/φ + K|S/(φ ), hence K|S (φ ) (K|S φ) + according to (8).

2 Notably, the fact that sampling-based belief revision satisfies (AGM-3) and (AGM-7) guarantees that arbitrary new beliefs, i.e. which do not follow from K + φ or (K φ) + , are not introduced when revising a sample set. On the other hand, it is easy to construct counterexamples to show that neither Vacuity (AGM-4) nor Subexpansion (AGM-8) are satisfied. Example 3 Recall S as defined in (3). For Vacuity, note, e.g., that (|2 _ |3) 2 K|S and that φ = ~ is consistent with K|S. However, according to (4), (|2 _ |3) 62 K|S φ.

For Subexpansion, observe first that }3 is consistent with S / ~ according to (4), hence }3 62 K ( ~). From (4) we can also see that |3 2 (K ( ~)) + }3. However, (5) implies that |3 62 K ( ~ }3).

4 A Representation Theorem The classical representation theorem for AGM-based belief revision states that any revision operator that satisfies all classical postulates can be equivalently characterised as faithful assignments of every belief set to a specific preference relation over worlds (cf. Definition 1 and Theorem 1). We have seen that sampling-based belief revision satisfies all but two of the postulates. This begs the question whether the classical representation theorem can be generalised so as to characterise belief revision operators that comply with the standard postulates minus Vacuity and Subexpansion.

It turns out that indeed a suitably extended representation theorem can be given based on the same concept of faithful assignments and preference orderings. The necessary weakening of the conditions of Theorem 1 is obtained by allowing for multiple total pre-orders for a given belief set. This can be intuitively explained as follows: Different possible worlds may be characterised by different underlying assumptions, which then lead to different preference orderings among alternative worlds upon revision. When revising a set of preferred worlds in the light of a family of faithful assignments, the resulting set is obtained as the combined set of minimal worlds from all preference relations.

Definition 4 A mapping from belief sets K to collections of total pre-orders 1

K, . . . , n

K (n 1) on W is a weakly faithful assignment if it satisfies the following conditions.

If w1 |= K then there is a k 2 {1, . . . , n} such that

K w2 for all w2. If w2 6|= K then for all k 2 {1, . . . , n} there is some

w1 |= K such that w1 <k

K w2. If J K, then 1

J, . . . , n

K, . . . , n

K. Put in words, every K-world is most preferred in at least one ordering (but may be even less preferred than a non-K world in others) while non-K worlds are never most preferred. It is easy to verify that all faithful assignments according to Definition 1 are also weakly faithful (with n = 1). As a generalisation of the classical representation theorem, revision with a weakly faithful assignment can be shown to characterise exactly the belief revision operators that satisfy all AGM-postulates except Vacuity and Subexpansion. Theorem 3 A revision operator satisfies Postulates (AGM-1) (AGM-3) and (AGM-5) (AGM-7) iff there is a weakly faithful assignment 1

K, . . . , n

K such that

Mods(K φ) =

min(Mods(φ), k

Proof (sketch): The only-if direction can be proved by constructing, for a given and K, assignments i

K, one for each wi 2 Mods(K), as follows:

K w0 for all w0 2 W \ {wi}.

K w00 if w0 2 Mods(K form(w0, w00)),4 for all w0, w00 2 W \ {wi}. (We note that this shows how to determine a corresponding system of spheres for an operator obtained from a given ordering of samples as per Definition 3.) Proving this to be weakly faithful is akin to the proof for a similarly constructed single assignment to be faithful in case of classical belief revision [Katsuno and Mendelzon, 1992].

For the if direction, we assume a revision operator given by (9) and prove that it satisfies each postulate in turn.

(AGM-1) follows from the definition of K φ as the set of formulas whose models are given by (9).

(AGM-2) follows from Mods(K φ) Mods(φ) by (9). (AGM-3): If w 2 Mods(K [ {φ}) then w 2 Mods(K) \ Mods(φ), hence w 2 min(Mods(K), k

K) \ Mods(φ) for some k 2 {1, . . . , n} by the first condition in Definition 4. Therefore, S

k min(Mods(φ), k

K) Mods(K [ {φ}), which implies K φ K + φ.

(AGM-5) holds since consistency of φ, i.e. Mods(φ) 6= ;, implies that min(Mods(φ), k

K) 6= ; for all 1 k n, hence Mods(K φ) 6= ;.

(AGM-6) follows from the fact that whenever φ then Mods(φ) = Mods( ), which for all 1 k n implies min(Mods(φ), k

K) = min(Mods( ), k

K). (AGM-7): To show that S

k min(Mods(φ), k

K)\Mods( ) is a subset of S

k min(Mods(φ ), k

K), consider an arbitrary world w 2 S

k min(Mods(φ), k

K) \ Mods( ), then

4form(w0, w00) denotes an arbitrary propositional formula whose only models are w0 and w00 [Katsuno and Mendelzon, 1992].

Figure 3: Revision with multiple systems of spheres [Grove, 1988]: If the three inner circles together are the models for the current belief, K, then the worlds in the shaded areas together are the models for the revised belief set K φ.

w 2 Mods(φ ). Suppose that for this world we have that w 62 S

k min(Mods(φ ), k

K), then for all 1 k n there must be a world w0

k 2 Mods(φ ) such that w0

K w, contradicting the assumption w 2 S

k min(Mods(φ), k

K). 2 The principle of combining the minimal φ-models from multiple systems of spheres is graphically illustrated in Figure 3: Even in case some K-worlds are consistent with the new observation (here, some of the most preferred worlds in 1

K), the revised set may include new models determined by an alternative preference relation (here, 2

K). This is the defining characteristic of operators that do not satisfy Vacuity or Subexpansion but all other AGM postulates.

A justification for the use of more than one faithful assignment can be that a belief may have been formed by considering alternative hypotheses, as in the following example. Example 4 We know that when John goes out for dinner, he always chooses between Asian (A) and Western (W) cuisine. He prefers to have the former in Thai Town (T) and the latter elsewhere ( T). We also know that he usually goes for dessert (D) in a Western but not in an Asian restaurant. There is a notable exception with one of his favourite Asian restaurants, however, where he usually does have dessert. This restaurant happens not to be in Thai Town.

Suppose John tells us that he went out for dinner last night, then we may represent uncertainty about his choice of cuisine by considering two hypotheses based on his preferred choices (A _ W): on the one hand, if he decided in favour of Asian food, then he would have gone to Thai Town and skipped dessert, so we believe in the conditional A ! T D; on the other hand, he could have had Western food elsewhere, including dessert, so we also believe in the conditional W ! T D. Altogether our belief is characterised by

(A T D) _ (W T D) (10) Now, suppose we subsequently learn that John had in fact dessert, then we may reconsider both principled hypotheses in turn: while the second (W) is consistent with the additional observation, the first (A) is not. Rather than dropping this hypothesis, however, we may choose to select the closest world according to John s preferences in case of Asian cuisine, which means to consider the possibility that he went to his preferred Asian restaurant that is not in Thai Town where he usually has dessert. Our revised belief will be (A T D) _ (W T D), which entails T D but not W, contrary to Vacuity applied to (10) 2 K, φ = D.

5 Axiomatising Model Sampling for Reasoning About Actions and Sensing

An interesting application of sampling-based logical reasoning about beliefs and how to revise them can be found in general theories of actions and sensing, aiming at a practically viable method to handle large domains in which agents have highly incomplete knowledge. A point in case are existing implementations of the Situation Calculus with sensing that attempt to maintain a complete description of the knowledge state, such as Reiter s [2001] use of prime implicants, which do not scale well due to the high theoretical complexity of executing knowledge-based plans [Lang and Zanuttini, 2012].

In the following, we develop a formal axiomatisation of model sampling in the Situation Calculus as an alternative way of reasoning about knowledge and akin to the modelling of classical belief revision in this calculus [Shapiro et al., 2000]. To this end, we replace Scherl and Levesque s [2003] special epistemic fluent K(S0, S) (to express that situation S0 is accessible from situation S) by an alternative fluent S(S0, S) whose intuitive meaning is that of situation S0 being a sample obtained for the actual situation S.

It is of course not always the case that the actual situation is among the sampled ones. In fact this is very unlikely in practice. Hence, the axiom of reflexivity 8S. K(S, S), which is a foundational axiom in the Situation Calculus with knowledge [Scherl and Levesque, 2003], does not translate into an axiom 8S. S(S, S). As a consequence, unlike fluent K which axiomatises knowledge (cf. (1)), fluent S axiomatises belief. This is reflected in the following definition:

def= 8S0. S(S0, S) ! Φ[S0] (11)

The adaptation of the successor state axiom for the knowledge fluent (cf. (2)) to the sampling fluent requires to axiomatise the concept of resampling. This can be formally captured by an auxiliary fluent SR(S00, S0, T) meaning that situation S00 is a sample of situation S0 obtained through resampling in situation T. The third argument is necessary because, for example, a situation s0

0 can be a valid sample for s0 when the agent is in that situation, but after sensing the agent may know enough to rule out that he could have been in s0

0 initially. The following axioms for S and SR formalise the relation among samples between successor situations:

POSS(A, S) !

S(S00, DO(A, S)) !

9A0, S0. S00 = DO(A0, S0) S(S0, S)

8P. SENSE(P, A, S) $ SENSE(P, A0, S0) _ SR(S00, DO(A0, S0), DO(A0, S0))

POSS(A, S) !

SR(S00, DO(A, S), T) !

9A0, S0. S00 = DO(A0, S0) SR(S0, S, T)

8P. SENSE(P, A, S) $ SENSE(P, A0, S0)

In words, a sample S00 must be

the result of updating a sample S0 from the previous sit-

uation such that the sensing result coincides with what is sensed in the actual situation S;

or the result of re-sampling in the resulting situa-

tion DO(A, S). Moreover, in order for a situation S00 to be the result of resampling situation DO(A, S) in situation T, S00 must be obtained from a sample S0 of S obtained through resampling in the same situation T.

We note that axioms (12) do not account for a specific sampling strategy; they rather define the range of all possible ways in which an agent can sample situations. Hence, (12) provides a mere schema from which actual successor state axioms (with the usual bi-implication [Reiter, 1991]) can be obtained by strengthening each right-hand side with a formula characterising a particular resampling strategy. This may include a limit on the sample size for each situation, e.g. to just two via the axiom S(S1, S) S(S2, S) S(S3, S) ! S1 = S2 _ S1 = S3 _ S2 = S3.

6 Conclusion Motivated by the success of sampling technique in different domains in which agents have to reason and make decisions under uncertainty, we have examined the logical foundations of sampling-based belief revision. It turned out that operators based on this principle satisfy six of the eight standard AGM postulates but not Vacuity nor Subexpansion. The reason is that resampling may result in new models that invalidate previously held beliefs even in cases where a new observation is consistent with the agent s original beliefs. Hence, even if new information is consistent with currently held beliefs, nonetheless some of these beliefs may get dropped. But our analysis also shows that arbitrary new beliefs (i.e., which do not follow from the previously held beliefs and the new information) can never be introduced through model resampling. A corresponding representation theorem adapts the classical result from single to multiple systems of spheres for a given belief set. As an application of our general framework for sampling-based belief revision, we have adapted a formal Situation Calculus axiomatisation to provide an alternative way of reasoning about actions and beliefs using (re-)sampling.

A practically viable method for belief revision, model sampling enriches the suite of traditional operators based on the AGM postulates, especially for domains where maintaing a full set of models (explicitly or implicitly represented) is practically impossible due to large information sets. These properties provide important insights into the side-effects of resampling on the beliefs of a decision-making agent that reasons based on sampled models. This insight follows from the analysis of resampling as single-step revision, which covers the essence of the operation performed by the agent when processing new information. Nonetheless for future work it would be interesting to formally investigate iterated revision in this context [Darwiche and Pearl, 1997]. We are also interested in looking at other applications of belief revision in which the sampling-based technique may provide an interesting alternative to classical operators. Another question for future work is to analyse the formal relation between our axiomatisation of sampling-based reasoning in the Situation Calculus and the existing axiomatisation of AGM-style belief revision in this calculus [Shapiro et al., 2000].

Acknowledgments

We thank the reviewers of an earlier version for their very helpful comments and suggestions. This research was supported by the Australian Research Council under grant no. DP150101351. The author is also affiliated with the University of Western Sydney.

References [Alchourr on et al., 1985] Carlos Alchourr on, Peter G ardenfors, and David Makinson. On the logic of theory change. Journal of Symbolic Logic, 50(2):510 530, 1985. [Darwiche and Pearl, 1997] Adnan Darwiche and Judea Pearl. On the logic of iterated belief revision. Artificial Intelligence, 89:1 29, 1997. [Edelkamp et al., 2012] Stefan Edelkamp, Tim Federholzner, and Peter Kissmann. Searching with partial belief states in general games with incomplete information. In B. Glimm and A. Kr uger, editors, Proceedings of the German Annual Conference on Artificial Intelligence (KI), volume 7526 of LNCS, pages 25 36, Saarbr ucken, Germany, September 2012. Springer. [Fox et al., 1999] Dieter Fox, Wolfram Burgard, Frank Del-

laert, and Sebastian Thrun. Monte Carlo localisation: Efficient position estimation for mobile robots. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 343 349, Orlando, August 1999. [Frank and Basin, 1998] Ian Frank and David Basin. Search

in games with incomplete information: A case study in using Bridge card play. Artificial Intelligence, 100(1 2):87 123, 1998. [G ardenfors and Makinson, 1988] Peter G ardenfors and David Makinson. Revisions of knowledge systems using epistemic entrenchment. In Proceedings of the Conference on Theoretical Aspects of Reasoning about Knowledge (TARK), pages 83 95, Pacific Grove, 1988. Morgan Kaufmann. [Ginsberg, 2001] Matthew Ginsberg. GIB: Imperfect infor-

mation in a computationally challenging game. Journal of Artificial Intelligence Research, 14:303 358, 2001. [Grove, 1988] Adam Grove. Two modellings for theory change. Journal of Philosophical Logic, 17(2):157 170, 1988. [Hollinger and Sukhatme, 2014] Geoffrey Hollinger and Gaurav Sukhatme. Sampling-based robotic information gathering algorithms. International Journal of Robotics Research, 39(9):1271 1287, 2014. [Katsuno and Mendelzon, 1992] Hirofumi Katsuno and Al-

berto Mendelzon. Propositional knowledge base revision and minimal change. Artificial Intelligence, 52(3):263 294, 1992. [Lang and Zanuttini, 2012] Jerˆome Lang and Bruno Zanut-

tini. Knowledge-based programs as plans the complexity of plan verification. In L. De Raedt, C. Bessi ere, D.

Dubois, P. Doherty, P. Frasconi, F. Heintz, and P. Lucas, editors, Proceedings of the European Conference on Artificial Intelligence (ECAI), pages 504 509, Montpellier, France, August 2012. IOS Press. [Mc Carthy, 1963] John Mc Carthy. Situations and Actions and Causal Laws. Stanford Artificial Intelligence Project, Memo 2, Stanford University, CA, 1963. [Reiter, 1991] Ray Reiter. The frame problem in the situa-

tion calculus: A simple solution (sometimes) and a completeness result for goal regression. In V. Lifschitz, editor, Artificial Intelligence and Mathematical Theory of Computation, pages 359 380. Academic Press, 1991. [Reiter, 2001] Ray Reiter. On knowledge-based programming with sensing in the situation calculus. ACM Transactions on Computational Logic, 2(4):433 457, 2001. [Richards and Amir, 2012] Mark Richards and Eyal Amir.

Information set generation in partially observable games. In Proceedings of the AAAI Conference on Artificial Intelligence, Toronto, 2012. [Scherl and Levesque, 2003] Richard Scherl and Hector Levesque. Knowledge, action, and the frame problem. Artificial Intelligence, 144(1):1 39, 2003. [Schofield et al., 2012] Michael Schofield, Timothy Cerexhe, and Michael Thielscher. Hyper Play: A solution to general game playing with imperfect information. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 1606 1612, Toronto, July 2012. AAAI Press. [Shapiro et al., 2000] Steven Shapiro, Maurice Pagnucco,

Yves Lesp erance, and Hector Levesque. Iterated belief change in the situation calculus. In A. Cohn, F. Giunchiglia, and B. Selman, editors, Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR), pages 527 538, Breckenridge, April 2000. Morgan Kaufmann.