# revising_beliefs_and_intentions_in_stochastic_environments__d9c29901.pdf Revising Beliefs and Intentions in Stochastic Environments Nima Motamed1 , Natasha Alechina2,1 , Mehdi Dastani1 and Dragan Doder1 1Utrecht University, The Netherlands 2Open University, The Netherlands {n.motamed, n.a.alechina, m.m.dastani, d.doder}@uu.nl The development of autonomous agents operating in dynamic and stochastic environments requires theories and models of how beliefs and intentions are revised while taking their interplay into account. In this paper, we initiate the study of belief and intention revision in stochastic environments, where an agent s beliefs and intentions are specified in a decidable probabilistic temporal logic. We then provide general Katsuno & Mendelzon-style representation theorems for both belief and intention revision, giving clear semantic characterizations of revision methods. 1 Introduction Autonomous agents operating in dynamic environments need a method for keeping track of their beliefs, updating these as new information is received. But an agent also carries intentions they are committed to bring about, and these also need to be updated on the basis of new information or deliberation. While there is an enormous amount of literature on the former topic of belief revision, the topic of intention revision received, in comparison, less attention [Cohen and Levesque, 1990; Wooldridge, 2000; van der Hoek et al., 2007; Castelfranchi and Paglieri, 2007; Lorini and Herzig, 2008; Shoham, 2009; Grant et al., 2010; Icard et al., 2010; van Ditmarsch et al., 2011; Shapiro et al., 2012; van Zee and Doder, 2016; van Zee et al., 2020]. As observed by many of the aforementioned authors, intention and beliefs are deeply intertwined, and their revisions need to be studied together. For instance, for an agent to be able to intend something, it does not suffice if it is merely the case that their beliefs and the intention are separately consistent on their own: they need to cohere together, in the sense that the agent s beliefs should be consistent with the achievement of the intention [van Zee et al., 2020]. In prior work on intention revision, such interactions between belief and intention have only been studied for agents acting in deterministic environments. But for many practical applications, agents act in stochastic environments, where their actions have uncertain outcomes. In this paper, we present the first framework for the joint revision of beliefs and intentions in stochastic environments. We define beliefs and intentions in a decidable probabilistic temporal logic interpreted on Markov Decision Processes (MDPs), giving the ability to express beliefs about the uncertainty in actions outcomes, as well as complex temporal intentions. We propose a set of rationality postulates for revision operators in this logic. Using these rationality postulates, we also obtain semantic understanding of revision through Katsuno & Mendelzon-style representation theorems [Katsuno and Mendelzon, 1991]. Working with stochastic environments and highly expressive beliefs and intentions about probability and time brings new challenges compared to prior work in the field, both technical and conceptual. In terms of technical challenges, giving a representation theorem is complicated by the fact that in general, there are infinitely many MDPs satisfying certain beliefs, due to the presence of probability, and that we have no general guarantees on the expressibility of sets of MDPs. These features are vital to the original theorems of [Katsuno and Mendelzon, 1991]. To overcome this challenge, we employ results and methods from [Falakh et al., 2023] to still obtain representation theorems. But to make our work more practically applicable, we go further by defining two novel postulates which additionally provide representation theorems for a specific class of operators that are conceptually simple and generally computable, properties which are not guaranteed by the results of [Falakh et al., 2023]. In terms of conceptual challenges, stochastic environments also require more nuanced approaches to the interplay between beliefs and intentions than is considered in prior work. Let us illustrate this with the following example (which we will frequently revisit throughout this paper). Consider an agent named Theo, who intends to attend an obscure, underground concert tomorrow. He only has $5, and admission costs precisely $5. He believes that if he goes to the ticket office today, he can almost certainly buy a ticket since no one knows the band and they are therefore unlikely to be sold out. Theo is also aware that the concert venue sometimes sends out free tickets for concerts in the mail, as a promotion. So Theo also believes that if he stays at home, he may receive tickets, albeit with a small probability. Now, for simplicity assume that Theo s favorite brand of beer costs $5, both at shops and at the concert venue. How would Theo revise his intentions with the new intention to also buy a drink tomorrow? His beliefs do in one sense support the Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) possibility of achieving both intentions, since he could luck out and get free tickets, attend the concert, and buy the drink there. So perhaps the revision should just be adding the new intention on top of his original one. But should rational agents make decisions based on unlikely outcomes? It would be more reasonable to say that an agent s intentions are coherent only if they can achieve them with reasonably high probability, with the definition of being reasonably high as a choice to be made. So it may be more reasonable that when revising with this new intention, Theo drops his old intention of attending the concert. To see how the nuance of probabilities also influences the interplay between beliefs and intentions, note that accepting intentions should revise the agent s beliefs: if he intends to attend the concert, Theo should also believe he no longer has $5 after the concert, as the only way to be reasonably sure about his attendance is to spend it on tickets. Similarly, revising beliefs should also be able to trigger intention revision. Say Theo gets a call from his friend Stan, who tells him that the band, which Theo thought to be obscure, has suddenly become an international sensation overnight. Theo revises his beliefs about him being able to buy tickets at the ticket office, as they are now highly likely to be sold out. And since it so unlikely to get tickets, no matter what he does, it may be reasonable to drop his intention of attending the concert. An agent s beliefs and intentions naturally concern themselves with probability ( I believe speeding is likely to be dangerous ) and time ( I intend to apply for jobs until I succeed ). Therefore we choose to express beliefs and intentions in an appropriate probabilistic temporal logic. We choose to work with an extended version of the Probabilistic Logic of Bounded Policies (PLBP), introduced by [Motamed et al., 2023]. We refer to this extension as PLBP+. We now explain the syntax and semantics of the logic. We fix a countably infinite set Prop of propositional variables and a finite set A of actions throughout the paper. To each action a A we associate a precondition prea, which is a conjunction of literals over Prop, and a finite nonempty list Posta of possible postconditions, which are also conjunctions of literals. Intuitively, the precondition of an action is precisely what must be satisfied so that the action can be executed, and a postcondition of an action is one of its possible outcomes, i.e. that which is made true after executing the action. We refer to the ith postcondition of a as posta,i. Before we can define the stochastic environments that serve as models of the logic, some notation is required. We write f : X Y to denote that f is a partial function from X to Y , and write f(x) to denote that f is defined on input x X. Given a set X, some x X and n 0, we write Xn x for the set of all sequences in X of length n starting with x (i.e. with X0 x = and X1 x = {x}), and we write X n x = Sn k=0 Xk x. Finally, we write (X) for the set of all finitely supported (discrete) probability distributions on X, i.e. those probability distributions D : X [0, 1] such that D(x) > 0 for only finitely many x. Definition 1 (MDP). A Markov decision process (MDP) over A is a tuple M = (S, P, V ), where S is the set of states, P : S A (S) is the partial probabilistic transition function, and V : S 2Prop is the valuation. We often abbreviate P(s, a) by Ps,a. These are required to satisfy the following conditions. First, for all s S, there is some a A such that s prea, where here is the standard propositional satisfaction relation. Second, Ps,a iff s prea. And third, given Ps,a , we have that (i) for all t S such that Ps,a(t) > 0, there is a unique posta,i in Posta such that t posta,i, and (ii) for all posta,i in Posta there is at most one t such that Ps,a(t) > 0 and t posta,i. A pointed MDP (p MDP) is a pair P = (M, s) where M is an MDP, and s is a state in M. We denote the set of all p MDPs P by p MDP. A key feature of PLBP+ is the ability to reason about n-step policies, which specify how the agent will act for n time steps. Definition 2 (n-step policies). Given a p MDP P = (M, s) and n 0, an n-step P-policy is a function π: S n s A such that sk preπ(s1 sk) for all s1 sk S n s . Given n-step π with n 1 and t S, define the pushforward of π to t to be the (n 1)-step (M, t)-policy πt given by putting πt(t) = π(st). We will drop P when the p MDP is clear from context, speaking just of n-step policies. Or conversely, when the n is not relevant within some context, we just speak of P-policies. Definition 3 (Paths and path distributions). For an n-step policy π, we define Paths(π) as the set of all paths s0 sn Sn+1 such that s0 = s, and P(sk, π(s0 sk))(sk+1) > 0 for all 0 k < n. Given an n-step policy π, its path distribution is the probability distribution µπ (Paths(π)) defined as µπ(s0 sn) = Q 0 k, <} by appropriate abbreviations, e.g. Pr>rΦ := Pr rΦ. Note that we can also define more complicated (bounded) temporal operators, such as the bounded until Φ Un Ψ := W 0 k n(XkΨ V 0 ℓrΦ expresses the intention to keep executing a until a point from which Φ will hold with probability > r, for a maximum of n steps. Note that this gives us a very rich notion of intention, going far beyond the atomic action intentions ( I intend to perform a at time t ) of [Shoham, 2009; van Zee et al., 2020]. Example 1 (Running example). Coming back to our example from Section 1 about Theo and the concert, we can rewrite the beliefs and intentions therein as PLBP+ formulas (fixing some probabilities for the terms likely and unlikely ). The relevant propositional variables are Prop = {five, conc}, with the former denoting Theo having $5, and the latter denoting Theo being at the concert. The example concerns the actions stay of staying at home, go Tick of going to the ticket office to buy a ticket, and buy Dr of buying his favorite drink. The relevant preconditions are prego Tick = five (it costs $5 to buy tickets), and prebuy Dr = five (Theo needs to have $5 to buy drinks). The relevant postconditions are Postgo Tick = {conc five, conc five} (Theo either gets to attend and spends $5, or he doesn t and keeps it), Poststay = {conc five, conc five} (whether he gets a ticket or not, he keeps his money), and Postbuy Dr = { five} (buying a drink is deterministic: Theo pays $5). His original beliefs are modelled by the state formula φ1 = five ((dogo Tick dostay) dogo Tick Pr .9Xconc dostay Pr .01Xconc), i.e. Theo has $5, can try to buy a ticket or stay at home, and with probability at least 90% the former gets him to the concert, while at most 1% the latter does. The intentions of attending the concert and buying drinks are respectively Φ1 = Xconc and Φ2 = Xdobuy Dr. The statement that the band has become popular (i.e. tickets are likely to be sold out) is φ2 = (dogo Tick Pr 0.01Xconc) (there s only a 1% chance Theo gets to buy tickets). 3 Coherence and Beliefs In this section, we introduce our proposal for defining the coherence of beliefs and intentions, as well as what it means to believe something on the basis of certain intentions. Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) As mentioned in Section 1, it is not sufficient that an agent s beliefs and intentions are separately consistent: we need joint consistency. This joint consistency between beliefs and intentions is what has been referred to as coherence by [van Zee et al., 2020]. What we want, is a requirement on beliefs and intentions, stating that the agent s beliefs should somehow be consistent with the possible achievement of their intentions. Note that this is effectively the Strong Consistency Principle proposed by [Bratman, 1987] in his influential theory of intentions. Coherence is defined in prior work as stating that there exists some model of the agent s beliefs, in which the agent has a policy which achieves the intention. Translating this definition to our setting, we are asking given a belief φ and an intention Φ, whether there exists some P JφK, and a P-policy π, such that π achieves Φ. What does it mean that π achieves Φ? Contrary to the prior work, in our setting actions have uncertain outcomes: some of the paths produced by π may satisfy Φ, while others do not. It is sensible to define the notion of achievement with regards to the probability with which these paths satisfy Φ, i.e. µπ([Φ]π). We therefore propose to take a parametric, applicationdependent approach to coherence, in which we take some value 0 θ < 1 with the intuition being that the agent only considers policies that achieve intentions with probability greater than θ. The value of θ will depend on the specific problem domain or type of agent we are considering at the time. Definition 6 (θ-coherence). Let 0 θ < 1 be a rational number. A state formula φ and path formula Φ are θ-coherent if there exists a p MDP P JφK and a P-policy π such that µπ([Φ]π) > θ. Note that this definition is equivalent to stating that the formula φ Pr>θΦ is satisfiable. Therefore, by Theorem 1 we get that it is actually decidable whether beliefs and intentions are θ-coherent. Example 2 (Running example, continued). Our discussion in Section 1 effectively observed that Theo s strong beliefs φ1 and intentions Φ1 Φ2 are 0-coherent (where Φ1 = Xconc and Φ2 = Xdobuy Dr), due the possibility of choosing the action stay. But note that this combined intention is not e.g. 0.05coherent with φ1, since in any model of φ1, any policy will assign at most probability 0.01 to Φ1 Φ2. We do have that Φ1 alone is 0.05-coherent with φ1 - the same holds for Φ2. While beliefs as we have discussed them so far have been about what the environment looks like, independent of how the agent actually chooses to act, an essential part of a theory of belief and intention is that since an agent is committed to performing intentions, they actually in some sense believe that the outcomes of those intentions will hold. To model this, [van der Hoek et al., 2007] propose to separate so-called strong beliefs from weak beliefs. The former are what we have considered so far: independent of how the agent actually acts. The latter are believed on the assumption the agent performs their intentions. The separation prevents scenarios like the Little Nell Problem [Mc Dermott, 1982]. Since weak beliefs are contingent on the performance of intentions, we propose to consider these to be path formulas as well: we weakly believe certain properties (like outcomes of intended actions) will hold throughout time. This is similar to the approach to weak beliefs of [van Zee et al., 2020]. Trying to use their approach naively, we could choose to define the weak beliefs obtained from our beliefs φ and intentions Φ to be those path formulas Ψ such that for all P JφK and Ppolicies π, we have for all w Paths(π) that if M, π, w Φ, then also M, π, w Ψ. But this approach is problematic, as our running example of Theo and the concert shows. By our naive definition of weak beliefs, Theo will not weakly believe that he will have $0 tomorrow, because of the existence of the policy in which he stays at home today. One could certainly argue that it is more practical and rational that Theo should in fact believe that, assuming he manages to attend the concert, he will be out of money. The problem here, as with coherence, is that the policy of staying at home achieves the intention with too low a probability. Therefore, we also parameterize the definition of weak beliefs by the same θ stating when a policy should be considered as achieving an intention, removing from consideration policies which only achieve the intention by sheer luck. Definition 7 (θ-weak beliefs). Let 0 θ < 1 be a rational number. Given a state formula φ and path formula Φ, the set WBθ(φ, Φ) of θ-weak beliefs of φ and Φ is defined as the set of all path formulas Ψ such that for all P JφK and P-policies π such that µπ([Φ]π) > θ, it holds for all w Paths(π) that if M, π, w Φ, then M, π, w Ψ. Note that Ψ WBθ(φ, Φ) if and only if φ Pr>θΦ Φ Ψ, which is again if and only if φ (Pr>θΦ Pr=1(Φ Ψ)). By Theorem 1, we can therefore decide whether a given formula Ψ is in WBθ(φ, Φ). Example 3 (Running example, continued). We have that indeed X five WB0(φ1, Φ1), while X five WB0.05(φ1, Φ1) and XX five WB0.05(φ1, Φ2): Theo 0.05weakly believes he will not have his money tomorrow if he intends to attend the concert tomorrow. And he also 0.05weakly believes he will not have his money the day after tomorrow if he intends to buy a drink tomorrow. We see directly from the definitions that the satisfiability of weak beliefs is equivalent to the coherence of the corresponding strong beliefs and intentions. 4 Representation for Revision Operators We now move our attention to the revision of beliefs and intentions. Similar to prior work [van Zee et al., 2020], we follow the approach of revising an agent s strong beliefs φ and intentions Φ with new strong beliefs ψ and intentions Ψ, by first revising the strong beliefs independently of the intentions, and afterwards revising the intentions in a way that takes the revised strong beliefs into account. We explore this joint revision in Section 4.3. We will start by discussing belief revision operators, and providing a representation theorem for them. By virtue of our setup, we will afterwards see that almost all of the machinery we develop here will also apply to intention revision operators. We conclude this section by discussing what our setup tells us about the interplay between belief and intention. Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) Throughout this section, we write Bel for the set of state formulas, and Int for the set of path formulas. 4.1 Belief Revision Definition 8 (Belief revision operator). A belief revision operator is a function : Bel Bel Bel, with φ ψ being read as the result of revising φ by ψ. Conceptually, we wish for belief revision operators to satisfy the intuition that they are revising φ by ψ by minimally changing φ until ψ can be added without problems. But the original approach of [Katsuno and Mendelzon, 1991] with finite-signature propositional logic does not apply to our setting: there are infinitely many p MDPs due to e.g. the presence of probability in our models, and generally speaking, there exists no formula φ that expresses even a single p MDP P (i.e. such that JφK = {P}), since we could always consider p MDPs which differ from P only at times which are outside the scope of φ. Luckily, the approach of [Falakh et al., 2023] still allows us to obtain a representation theorem by adding some requirements on the semantic side, which they refer to a min-completeness and min-expressibility. First some preliminaries on orders are required. A relation X X is a total preorder if it is reflexive, transitive and connected (i.e. x y or y x for all x, y X). We write x y iff x y and y x. We say x U X is -minimal in U if x y for all y U, and write min(U, ) for the set of all such -minimal elements in U. Definition 9 (p MDP assignments). A p MDP assignment is a function ( ) : Bel 2p MDP p MDP such that φ is a total preorder for all φ. The assignment is faithful if the following three conditions hold: (i) If P φ and P φ, then P φ P and P φ P. (ii) If P φ and P φ, then P φ P . (iii) If φ ψ, then φ = ψ. The assignment is min-complete if min(JψK, φ) = for all φ and ψ with JψK = . It is min-expressible if for all φ and ψ there exists ψ ,φ Bel such that Jψ ,φK = min(JψK, φ). The rationality postulates used by [Falakh et al., 2023] are precisely those of [Katsuno and Mendelzon, 1991], and are equivalent to the original presentation of the AGM postulates by [Alchourr on et al., 1985]. Though Katsuno & Mendelzon s work was concerned with finite-signature propositional logic, we emphasize that the rationality postulates are applicable in much more general settings: citing [Segerberg, 1999], AGM is not really logic; it is a theory about theories . The postulates are as follows. (B1) φ ψ ψ. (B2) If φ ψ is satisfiable, then φ ψ φ ψ. (B3) If ψ is satisfiable, then φ ψ is satisfiable. (B4) If φ1 φ2 and ψ1 ψ2, then φ1 ψ1 φ2 ψ2. (B5) (φ ψ) χ φ (ψ χ). (B6) If (φ ψ) χ is satisfiable, then it holds that φ (ψ χ) (φ ψ) χ. The postulate (B1) expresses the success of revision: the new information must be incorporated by the revision. The postulate (B2) expresses that when the new information is consistent with our beliefs, revision should be the same as just adding the new information. The postulate (B3) expresses that we maintain consistency whenever we add consistent information to our beliefs, and the postulate (B4) expresses that revision should not care about syntax. Finally, the postulates (B5) and (B6) ensure that revision can be thought of as based on a notion of minimal change, with the outcome of revision φ ψ giving those models of ψ that are closest to models of φ. Given such a interpretation, we would naturally have that a model of ψ which is closest to φ and satisfies χ is automatically also the model of ψ χ closest to φ, which is exactly what (B5) states. And similarly, we would never have that there exist models M, N Jψ χK such that M is closest to φ amongst Jψ χK but N is strictly closer to φ than M amongst JψK, which is exactly what (B6) rules out. Example 4 (Running example, continued). Consider Theo s original strong beliefs φ1 and the new piece of information φ2 = (dogo Tick Pr 0.01Xconc) (which he gains by learning the band is actually popular). Then the postulates tell us already several things about how the revision φ1 φ2 will look, for any belief revision operator satisfying them. For example, (B3) tells us that φ1 φ2 must be satisfiable, since φ2 clearly is. We get that φ1 φ2 cannot be equivalent to φ1 φ2, as that formula is not satisfiable: Theo has to drop some beliefs. But whatever he drops, (B1) tells us that φ1 φ2 φ2: he comes to believe that if he goes to the ticket office, the probability that tickets are available is at most 1%. The following general representation result, Theorem 2, expresses that belief revision minimally changes beliefs to accommodate new information. Theorem 2 (General representation for PLBP+). The following statements hold: For every min-complete, min-expressible and faithful p MDP assignment ( ) there exists a belief revision operator satisfying (B1)-(B6) such that Jφ ψK = min(JψK, φ). For every belief revision operator satisfying (B1)- (B6) there exists a min-complete, min-expressible and faithful p MDP assignment ( ) such that Jφ ψK = min(JψK, φ). Proof. This follows from the results of [Falakh et al., 2023], as we now explain. Consider PLBP+ state formulas as what they refer to as a base logic: PLBP+ state formulas are the sentences, p MDPs are the worlds, the satisfaction relation is used, the bases are the singletons {φ} of state formulas, and the abstract union of {φ} and {ψ} is {φ ψ}. Then what they refer to as base change operators, are precisely what we refer to as belief revision operators. [Delgrande et al., 2018] introduce a postulate (Acyc), which (applied to PLBP+ state formulas as a base logic) states the following: For any φ and ψ0, . . . , ψn with Jψi (φ ψ(i+1) mod (n+1))K = for all i, it holds that Jψ0 (φ ψn)K = . By Theorem 10.13 of [Falakh et al., 2023], we get that the following statements hold: Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) For every min-complete, min-expressible and faithful p MDP assignment ( ), there exists a belief revision operator satisfying (B1)-(B6) and (Acyc) such that Jφ ψK = min(JψK, φ). For every belief revision operator satisfying (B1)-(B6) and (Acyc), there exists a min-complete, min-expressible and faithful p MDP assignment ( ) such that Jφ ψK = min(JψK, φ). We see that in fact, PLBP+ state formulas form what they call a disjunctive base logic, since PLBP+ state formulas contain disjunctions. Therefore, their Corollary 10.17 applies and tells us that any belief revision operator satisfying (B1)- (B6) also automatically satisfies (Acyc), which completes our proof. While Theorem 2 gives us a representation theorem for belief revision operators, it does not give us much in the way of practical belief revision. It is not clear from the start how we can come up with min-complete and min-expressible p MDP assignments. And even if we find such assignments, we have no guarantee in general that the resulting belief revision operator is actually computable. Therefore we propose finitely expressible p MDP assignments, which are a more specific class of p MDP assignments that are both easily understood from an intuitive, conceptual point of view, as well as computable under very mild assumptions. We start with some technical preliminaries. Definition 10 (Finitariness). A total preorder on a (possibly infinite) set X is finitary if the set {[x] | x X} is finite, where [x] = {y X | x y and y x}. Given a finitary total preorder and x X, we write level (x) := |{[y] | y X and y x}|. Writing height( ) := |{[x] | x X}|, we define the level sets X ,1, . . . , X ,height( ) by putting X ,k := {x X | level (x) = k}. The idea is that a finitary total preorder may be defined on an infinite set, but it divides the set into finitely many levels of equivalent elements. Definition 11 (FEF p MDP assignments). A p MDP assignment ( ) is finitely expressible if φ is finitary for all φ Bel, and for all φ there exist φ1, . . . , φheight( φ) Bel such that Jφk K = p MDP φ,k, i.e. the k-th level set of p MDP according to φ. We refer to finitely expressible and faithful p MDP assignments as FEF p MDP assignments for short. Finitely expressible p MDP assignments divide the space of p MDPs into finitely many levels for every φ, with every level expressible by formulas of PLBP+. And indeed, finite expressibility implies both min-completeness and min-expressibility. FEF p MDP assignments are conceptually simple, because they are in fact the same as specifying for every φ a finite sequence of weakenings of φ, which corresponds intuitively to the idea that in revision we keep removing information step-by-step from our beliefs until they can accommodate the new information. We make this correspondence precise in Proposition 1. Definition 12 (Belief weakening maps). A belief weakening map is a function : Bel Bel+ (where we write Bel+ to denote the set of all non-empty finite sequences of φ Bel) assigning to all φ Bel a finite sequence φ 1 φ n, such that φ 1 φ. Proposition 1. The following statements hold: For every FEF p MDP assignment ( ) there exists a belief weakening map such that | φ | = height( φ ) + 1 and J φ k K = S 1 ℓ k p MDP φ,ℓfor all φ and k. For every belief weakening map , there exists an FEF p MDP assignment ( ) such that height( φ) | φ | + 1 and J φ k K = S 1 ℓ k p MDP φ,ℓfor all φ and k. Proof. Take an FEF p MDP assignment ( ). Since it is finitely expressible, we have that for all φ there exist φ1, . . . , φheight( φ) such that Jφk K = p MDP φ,k. Defining the belief weakening map by putting φ 1 := φ and φ k+1 := W 1 ℓ k φℓfor 1 k height( φ), we indeed get the required property. Now take a belief weakening map . Given φ and P, write φ, P := min{1 ℓ | φ | | P φ ℓ} if P W φ otherwise , i.e. the number of the first weakening of φ that P satisfies if possible, and otherwise . We define the p MDP assignment by putting P φ P iff φ, P φ, P . It is immediate that this assignment produces total preorders, since it is defined by comparing numbers. Faithfulness follows from the observations that (i) φ, P = 1 if P φ, (ii) φ, P > 1 if P φ, and (iii) the definition being completely syntax-invariant. Finitariness follows from φ, P taking at most | φ | + 1 values. If we do not have φ k φ ℓfor any k = ℓ(i.e. the weakenings are semantically distinct), if W φ is not a tautology (i.e. the value φ, P = can appear), and if φ is satisfiable, then height( φ) = | φ | + 1. If any of those assumptions do not hold (e.g. if W φ is a tautology), then the height may be lower, though never higher. To see that the assignment is finitely expressible, we recursively define for 1 k height( φ) the formulas φk by putting φk := φ max{ℓ; φ ℓ W 1 m θ. The set of θbundles in P is denoted Bunθ(P). For φ Bel, we write Bunθ(φ) = S P JφK Bunθ(P). Now, for a θ-bundle B = (M, π, W) and Φ Int, we define B Φ iff M, π, w Φ for all w W. The seemingly odd notation is justified by the following observation: Ψ WBθ(φ, Φ) iff for all B Bunθ(φ) it holds that B Φ implies B Ψ. In other words, we can think of our earlier entailment relation θ φ of path formulas (defined as Φ θ φ Ψ iff Ψ WBθ(φ, Φ)) as actually being derived in the standard way from the satisfaction relation Bunθ(φ) Int. This means that, fixing φ Bel, PLBP+ path formulas Ψ Int and θ-bundles B Bunθ(φ) form an instance of base logics in the sense of [Falakh et al., 2023], in which θ-coherence w.r.t. φ is the notion of satisfiability. We can utilize this powerful fact to give definitions and a representation theorem that fully mirror those we gave for belief revision: the definitions and theorems here are the same as in Section 4.1, in which occurences of are replaced by θ φ and p MDPs are replaced by θ-bundles B Bunθ(φ). In the following, we write [Φ]θ φ for the set of all B Bunθ(φ) such that B Φ. Definition 15 (θ-bundle assignments). A θ-bundle assignment is a Bel-indexed family ( , ) of functions φ,( ) : Int 2Bunθ(φ) Bunθ(φ) such that φ,Φ is a total preorder for all Φ. The assignment is faithful if: (i) If B Φ and B Φ, then B φ,Φ B and B φ,Φ B. (ii) If B Φ and B Φ, then B φ,Φ B . (iii) If Φ =θ φ Ψ, then φ,Φ = φ,Ψ. The assignment is finitely expressible if φ,Φ is finitary for all φ and Φ, and for all φ and Φ there exist Φφ,1, . . . , Φφ,height( φ,Ψ) Int such that [Φφ,k]θ φ = (Bunθ(φ)) φ,Φ,k, i.e. the k-th level set of Bunθ(φ) according to φ,Φ. We refer to finitely expressible and faithful θ-bundle assignments as FEF θ-bundle assignments for short. We have an analogue of Proposition 1, showing how FEF θ-bundle assignments are precisely θ-intention weakening maps, assigning to every φ and Φ a sequence of path formulas Φ φ 1 θ φ θ φ Φ φ n such that Φ φ 1 =θ φ Φ. And using a new postulate (Iω), we can give a representation theorem for FEF θ-bundle assignments. In the following, a θ-intention partition for φ is a sequence Φ1, . . . , Φn Int such that (i) Φ1 Φn is a tautology w.r.t. θ φ, (ii) φ and Φk are θcoherent for all k, and (iii) φ and Φk Φℓare not θ-coherent for all k = ℓ. (Iω) For all φ and Φ there exists a θ-intention partition Φ1, . . . , Φn w.r.t. φ, such that for all Ψ, there exists k with Φ φ Ψ =θ φ Ψ Φk. Theorem 4 (Representation for intention revision). The following statements hold: Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) For every FEF θ-bundle assignment ( , ) there exists an intention revision operator satisfying (I1)-(I6) and (Iω), such that [Φ φ Ψ]θ φ = min([Ψ]θ φ, φ,Φ). For every intention revision operator satisfying (I1)- (I6) and (Iω) there exists an FEF θ-bundle assignment ( , ) such that [Φ φ Ψ]θ φ = min([Ψ]θ φ, φ,Φ). Proof sketch. The proof is identical to that of Theorem 3: for every φ, we now consider path formulas with the entailment relation θ φ to form a base logic in the sense of [Falakh et al., 2023], interpreted over θ-bundles in Bunθ(φ). We conclude this section by stating that intention revision operators satisfying (I1)-(I6) and (Iω) are computable if the underlying θ-intention weakening maps are computable, by a conceptually identical algorithm as for belief operators. To compute Φ φ Ψ, first check if φ and Ψ are θ-coherent: if not, output . Then compute Φ φ 1 , . . . , Φ φ n, and iterate over 1 k n, checking whether φ and Ψ Φ φ k are θ-coherent. For the first such k, output Ψ Φ φ k. If no such k exists, output Ψ. 4.3 Joint Revision of Beliefs and Intentions In this section, we present the fundamental interaction between beliefs and intentions that motivates the current work: revision of beliefs may trigger revision of intentions, and vice-versa. We capture this interaction through the following definition in which joint revision proceeds by first revising strong beliefs, and then revising intentions w.r.t. the revised strong beliefs. Definition 16 (Belief-intention revision operator). Given a belief revision operator and an intention revision operator , their belief-intention revision operator is the function : (Bel Int)2 Bel Int defined as (φ, Φ) (ψ, Ψ) := (φ ψ, Φ φ ψ Ψ). Note that we define the joint revision operator through independent belief and intention revision operators. We could have taken joint revision operators as primitive and provided postulates for them capturing the desired interplay, but the definition above simplifies presentation and follows earlier lines of work [van Zee et al., 2020]. In joint revision, belief revision may trigger intention revision, since the intention revision s notion of coherence depends on the new strong belief φ ψ. And vice-versa, intention revision triggers belief revision, though key is the separation between strong and weak beliefs: only the latter depend on intentions, as seen in Definition 7. As argued earlier, intention revision should not change strong beliefs. The postulates for belief and intention revision tell us certain properties of these joint belief-intention revision operators, which we illustrate through our running example. Example 6 (Running example, continued). First, note that intention revision changes weak beliefs. We saw in Example 3 that X five WB0.05(φ1, Φ1): when intending to attend the concert, Theo 0.05-weakly believes he will be out of money tomorrow. Now consider the revision (φ1, Φ1) ( , Φ2) = (φ1, Φ3) (i.e. we just wish to revise with the intention to buy a drink). By the postulates for intention revision, we get that Xfive WB0.05(φ1, Φ3), since Φ3 0.05 φ Φ2 0.05 φ Xfive. So after revision, we weakly believe that Theo does have $5 tomorrow: otherwise, he could not buy a drink tomorrow. Now, note that belief revision actually changes intentions. Consider the revision (φ1, Φ1) (φ2, ) = (φ1 φ2, Φ1 φ1 φ2 ). We know that since φ2 is satisfiable, φ1 φ2 must also be by our belief revision postulates. So we have that is 0.05-coherent w.r.t. φ1 φ2 ( always is as long as the strong beliefs are satisfiable). We can derive by our intention revision postulates that Φ1 φ1 φ2 must also be 0.05-coherent w.r.t. φ1 φ2. But we know that φ2 and Φ1 are not 0.05-coherent. Therefore, it cannot be that Φ1 φ1 φ2 0.05 φ1 Φ1. This means that by revising with the belief that the band is popular, Theo is forced to abandon his intention to attend the concert. 5 Conclusion We have initiated the study of belief and intention revision in stochastic environments, expressed in an appropriate probabilistic temporal logic. We give rationality postulates for revision, and prove representation theorems both for revision operators in general, as well for operators that are generally computable using the novel postulates (Bω) and (Iω). In future work, we plan to extend our framework to allow for iterated revision, a la [Darwiche and Pearl, 1997]. We also wish to develop a representation theorem with a modified version of (I1), which would allow success of revision only given coherent new intentions, as is also the case in the work of [van Zee et al., 2020]. Such revision could follow the approach as taken in the consistent AGM revision of [Hansson, 2023a; Hansson, 2023b], where revision with inconsistent statements maintains the original beliefs, or the more nuanced approach of [Konieczny et al., 2010], in which revision by a formula does not need to immediately entail it, but instead only increase its plausibility every time it is revised with. References [Alchourr on et al., 1985] Carlos E. Alchourr on, Peter G ardenfors, and David Makinson. On the logic of theory change: Partial meet contraction and revision functions. The Journal of Symbolic Logic, 50(2):510 530, 1985. [Bratman, 1987] Michael Bratman. Intention, Plans, and Practical Reason. Cambridge, MA: Harvard University Press, Cambridge, 1987. [Canny, 1988] John Canny. Some algebraic and geometric computations in PSPACE. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing STOC 88, page 460 467. ACM, 1988. [Castelfranchi and Paglieri, 2007] Cristiano Castelfranchi and Fabio Paglieri. The role of beliefs in goal dynamics: prolegomena to a constructive theory of intentions. Synthese, 155(2):237 263, 2007. [Chang and Keisler, 2012] Chen Chung Chang and Howard Jerome Keisler. Model Theory. Dover Publications, 3 edition, 2012. [Cohen and Levesque, 1990] Philip R Cohen and Hector J Levesque. Intention is choice with commitment. Artificial intelligence, 1990. Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) [Darwiche and Pearl, 1997] Adnan Darwiche and Judea Pearl. On the logic of iterated belief revision. Artificial Intelligence, 89(1):1 29, 1997. [De Giacomo and Vardi, 2013] Giuseppe De Giacomo and Moshe Y. Vardi. Linear temporal logic and linear dynamic logic on finite traces. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI 13, page 854 860. AAAI Press, 2013. [Delgrande et al., 2018] James P. Delgrande, Pavlos Peppas, and Stefan Woltran. General belief revision. J. ACM, 65(5), sep 2018. [Falakh et al., 2023] Faiq Miftakhul Falakh, Sebastian Rudolph, and Kai Sauerwald. AGM belief revision, semantically, 2023. ar Xiv:2112.13557. [Grant et al., 2010] John Grant, Sarit Kraus, Donald Perlis, and Michael J. Wooldridge. Postulates for revising BDI structures. Synth., 175(Supplement-1):39 62, 2010. [Hansson, 2023a] Sven Ove Hansson. A basis for AGM revision in bayesian probability revision. J. Philos. Log., 52(6):1535 1559, 2023. [Hansson, 2023b] Sven Ove Hansson. Iterated AGM revision based on probability revision. J. Log. Lang. Inf., 32(4):657 675, 2023. [Icard et al., 2010] Thomas Icard, Eric Pacuit, and Yoav Shoham. Joint revision of belief and intention. In Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning, KR 10, page 572 574. AAAI Press, 2010. [Katsuno and Mendelzon, 1991] Hirofumi Katsuno and Alberto O. Mendelzon. Propositional knowledge base revision and minimal change. Artificial Intelligence, 52(3):263 294, 1991. [Khan and Lesp erance, 2012] Shakil M. Khan and Yves Lesp erance. Logical foundations for a rational BDI agent programming language (extended version). In Louise A. Dennis, Olivier Boissier, and Rafael H. Bordini, editors, Programming Multi-Agent Systems - 9th International Workshop, Pro MAS 2011, volume 7217 of Lecture Notes in Computer Science, pages 3 21. Springer, 2012. [Konieczny et al., 2010] S ebastien Konieczny, Mattia Medina Grespan, and Ram on Pino P erez. Taxonomy of improvement operators and the problem of minimal change. In Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning, KR 10, page 161 170. AAAI Press, 2010. [Leask, 2021] Sam Leask. GROVE - a computationally grounded model for rational intention revision in BDI agents. Ph D thesis, University of Nottingham, UK, 2021. [Lorini and Herzig, 2008] Emiliano Lorini and Andreas Herzig. A logic of intention and attempt. Synthese, 163(1):45 77, 2008. [Mc Dermott, 1982] Drew Mc Dermott. A temporal logic for reasoning about processes and plans. Cognitive Science, 6(2):101 155, 1982. [Motamed et al., 2023] Nima Motamed, Natasha Alechina, Mehdi Dastani, Dragan Doder, and Brian Logan. Probabilistic temporal logic for reasoning about bounded policies. In Edith Elkind, editor, Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI23), pages 3296 3303, August 2023. Main Track. [Rao and Georgeff, 1991] Anand S. Rao and Michael P. Georgeff. Modeling rational agents within a bdiarchitecture. In Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning (KR 91), pages 473 484, 1991. [Segerberg, 1999] Krister Segerberg. Two Traditions in the Logic of Belief: Bringing them Together, pages 135 147. Springer Netherlands, Dordrecht, 1999. [Shapiro et al., 2012] Steven Shapiro, Sebastian Sardi na, John Thangarajah, Lawrence Cavedon, and Lin Padgham. Revising conflicting intention sets in BDI agents. In Wiebe van der Hoek, Lin Padgham, Vincent Conitzer, and Michael Winikoff, editors, International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2012, pages 1081 1088, 2012. [Shoham, 2009] Yoav Shoham. Logical theories of intention and the database perspective. Journal of Philosophical Logic, 38(6):633 647, 2009. [van der Hoek et al., 2007] Wiebe van der Hoek, Wojciech Jamroga, and Michael Wooldridge. Towards a theory of intention revision. Synthese, 155(2):265 290, 2007. [van Ditmarsch et al., 2011] Hans van Ditmarsch, Tiago de Lima, and Emiliano Lorini. Intention change via local assignments. In Mehdi Dastani, Amal El Fallah Seghrouchni, Jomi H ubner, and Jo ao Leite, editors, Languages, Methodologies, and Development Tools for Multi-Agent Systems, pages 136 151, Berlin, Heidelberg, 2011. Springer. [van Zee and Doder, 2016] Marc van Zee and Dragan Doder. Agm-style revision of beliefs and intentions. In ECAI, volume 285 of Frontiers in Artificial Intelligence and Applications, pages 1511 1519. IOS Press, 2016. [van Zee et al., 2020] Marc van Zee, Dragan Doder, Leendert van der Torre, Mehdi Dastani, Thomas Icard, and Eric Pacuit. Intention as commitment toward time. Artificial Intelligence, 283, 2020. [Wooldridge, 2000] Michael John Wooldridge. Reasoning about Rational Agents. MIT Press, 2000. Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)