9.6 Markovian Belief Revision

For the purposes of this section, I restrict attention to BCSs where the prior plausibility measures are algebraic, as defined in Section 3.9. As I observed in Section 6.10, in such systems, the notion of a Markovian plausibility measure on runs makes perfect sense. Not surprisingly, BCSs where the prior plausibility on runs is Markovian are called Markovian BCSs. To see the power of Markovian BCSs as a modeling tool, consider the following example:

Example 9.6.1

A car is parked with a nonempty fuel tank at time 0. The owner returns at time 2 to find his car still there. Not surprisingly, at this point he believes that the car has been there all along and still has a nonempty tank. He then observes that the fuel tank is empty. He considers two possible explanations: (a) that his wife borrowed the car to do some errands or (b) that the gas leaked. (Suppose that the "times" are sufficiently long and the tank is sufficiently small that it is possible that both doing some errands and a leak can result in an empty tank.)

To model this as a BCS, suppose that Φ_e consists of two primitive propositions: Parked (which is true if car is parked where the owner originally left it) and Empty (which is true if the tank is empty). The environment state is just a truth assignment to these two primitive propositions. This truth assignment clearly changes over time, so REV1 is violated. (It would be possible to instead use propositions of the form Parked_i—the car is parked at time i—which would allow REV1 to be maintained; for simplicity, I consider here only the case where there are two primitive propositions.) There are three environment states: s_pe, s_pe, and s_pe. In s_pe, Parked ∧ Empty is true; in s_pe, Parked ∧ Empty is true; and in s_pe, Parked ∧ Empty is true. For simplicity, assume that, in all runs in the system, Parked ∧ Empty is true at time 0 and Parked ∧ Empty is true at times 2 and 3. Further assume that in all runs the agent correctly observes Parked in round 2, and Empty in round 3, and makes no observations (i.e., observes true) in round 1.

I model this system using a Markovian plausibility on runs. The story suggests that the most likely transitions are the ones where no change occurs, which is why the agent believes at time 2—before he observes that the tank is empty—that the car has not moved and the tank is still not empty. Once he discovers that the tank is empty, the explanation he considers most likely will depend on his ranking of the transitions. This can be captured easily using ranking functions (which are algebraic plausibility measures). For example, the agent's belief that the most likely transitions are ones where no change occurs can be modeled by taking τ(s, s) = 0 and τ(s, s′)> 0 if s ≠ s′, for s, s′ ∈{s_pe, s_pe, s_pe}. This is already enough to make [s_pe, s_pe, s_pe]the most plausible 2-prefix. (Since, for each time m ∈{0, …, 3}, the agent's local state is the same at time m in all runs, I do not mention it in the global state.) Thus, when the agent returns at time 2 to find his car parked, he believes that it was parked all along and the tank is not empty.

How do the agent's beliefs change when he observes that the tank is empty at time 3? As I said earlier, I restrict attention to two explanations: his wife borrowed the car to do some errands, which corresponds to the runs with 2-prefix [s_pe, s_pe, s_pe], or the gas tanked leaked, which corresponds to the runs with 2-prefix [s_pe, s_pe, s_pe] and [s_pe, s_pe, s_pe] (depending on when the leak started). The relative likelihood of the explanations depends on the relative likelihood of the transitions. He considers it more likely that his wife borrowed the car if the transition from s_pe to s_pe is less likely than the sum of the transitions from s_pe to s_pe and from s_pe to s_pe, for example, if τ(s_pe, s_pe) = 3, τ(s_pe, s_pe) = 1, and τ(s_pe, s_pe) = 1. Applying the Markovian assumption and the fact that ⊗ is + for rankings, these choices make κ([s_pe, s_pe, s_pe]) = 2 and κ([s_pe, s_pe, s_pe]) = κ([s_pe, s_pe, s_pe]) = 3. By changing the likelihood of the transitions, it is clearly possible to make the two explanations equally likely or to make the gas leak the more likely explanation.

This example was simple because the agent's local state (i.e., the observations made by the agents) did not affect the likelihood of transition. In general, the observations the agent makes do affect the transitions. Using the Markovian assumption, it is possible to model the fact that an agent's observations are correlated with the state of the world (e.g., the agent's being more likely to observe p if both p and q are true than if p ∧ q is true) and to model unreliable observations that are still usually correct (e.g., the agent's being more likely to observe p if p is true than if p is false, or p being more likely to be true if the agent observes p than if the agent observes p; note that these are two quite different assumptions).

These examples show the flexibility of the Markovian assumption. While it can be difficult to decide how beliefs should change, this approach seems to localize the effort in what appears to be the right place: deciding the relative likelihood of various transitions. An obvious question now is whether making the Markovian assumption puts any constraints on BCSs. As the following result shows, the answer is no, at least as far as belief sets go:

Theorem 9.6.2

Given a BCS퓙, there is a Markovian BCS퓙′ such that the agent's local states are the same in both 퓙 and 퓙′ and, for all local states s_a, Bel(퓙, s_a) = Bel(퓙′, s_a).

Proof Suppose that 퓙 = (, , π). Let Pl be the prior on that determines . Although the agent's local state must be the same in 퓙 and 퓙′, there is no such requirement on the environment state. The idea is to define a set ′ of runs where the environment states have the form 〈g₀, …, g_m〉, for all possible initial sequences g₀, …, g_m of global states that arise in runs of . Then 퓙′ = (′, ′ π′), where π′(〈g₀, …, g_m〉) = π(g_m) and ′ is determined by a Markovian prior Pl′ on that simulates Pl. "Simulates" essentially means "is equal to" here; however, since Pl′ must be algebraic, equality cannot necessarily be assumed. It suffices that Pl′ ([〈g₀〉, 〈g₀, g₁ 〉,…, 〈g₀,…,g_m〉]) > Pl′ ([〈g′₀〉, 〈g′₀, g′₁ 〉,…, 〈g′₀,…,g′_m′〉]) iff Pl([g₀,…, g_m]) > Pl([g′₀,…, g′_m]). I leave the technical details to the reader (Exercise 9.20).