The Value of Observation for Monitoring Dynamic Systems

1 Introduction

known state given the past observations. The goal is to maintain (i.e. track) a belief state, a distribution over the states; in many applications this is the first step towards even more challenging tasks such as learning and planning. Often the dynamics of the system is not perfectly known but an approximate model is available. When the model and initial state are perfectly known then state monitoring reduces to Bayesian inference. However, if there is modelling error (e.g. the transition model is slightly incorrect), then the belief states in the approximate model may diverge from the true (Bayesian) belief state. The implications of such a divergence might be dire.

The most popular dynamic models for monitoring some unknown state are the Hidden Markov Model (HMM) [Rabiner & Juang, 1986] and extensions such as Partially Observable Markov Decision Process [Puterman, 1994], Kalman Filters [Kalman, 1960] and Dynamic Bayesian Networks [Dean

∗Supported in part by a grant from ISF and BSF.

& Kanazawa, 1989] - all of which share the Markov assumption. Naturally, one would like to provide conditions as to when monitoring is possible when modelling errors are present. Such conditions can be made on either the dynamics of the system (i.e. the transition between the states) or on the observability of the system. While the true model of the transition dynamics usually depends on the application itself, the observations often depend on the user, e.g. one might be able to obtain better observations by adding more sensors or just more accurate sensors. In this paper our main interest is in quantifying when the observations become useful and how it effects the monitoring problem.

Before we define our proposed measure, we give an illustrative example of an HMM, where the value of information can vary in a parametric manner. Consider an HMM in which at every state the observation reveals the true state with probability 1 - ϵ and with probability ϵ gives a random state. This can be thought of as having a noisy sensor. Intuitively, as the parameter ϵ varies from zero to one, the state monitoring become harder.

We introduce a parameter which characterizes how informative the observations are in helping to disambiguate what the underlying hidden state is. We coin this parameter the value of observation. Our value of observation criterion tries to quantify that different belief states should have different observation distributions. More formally, the L1 distance between any two belief states and their related observation distributions is maintained up to a multiplicative factor (which is at least the value of observation parameter).

In this paper we use as an update rule a variant of the Bayesian update. First we perform a Bayesian update given our (inaccurate) model, and then we add some noise (in particular, we mix the resulting belief state with the uniform distribution). Adding noise is crucial to our algorithm as it ensures the beliefs do not become incorrectly overly confident, thus preventing the belief state from adapting fast enough to new informative information.

Our main results show that if the model is only approximate then our modified Bayesian updates guarantee that the true belief state and our belief state will not diverge - assuming the value of observation is not negligible. More specifically, we show that if the initial state is approximately accurate, then the expected KL-divergence between our belief state and the true belief state remains small. We also show that if we have an uninformative initial state (e.g., arbitrary initial belief state) we will converge to a belief state whose expected KL-divergence from the true belief state is small and will remain as such from then on. Finally, we extend our results to the setting considered in [Boyen & Koller, 1998], where the goal is to compactly represent the belief state. The precision and rate of convergence depends on the value of observation.

One natural setting with an inaccurate model is when the underlying environment is not precisely Markovian. For example, it might be that the transition model is slightly influenced by some other extrinsic random variables. Given these extrinsic variables, the true transition model of the environment is only a slightly different model each time step. This is a case where we might like to model the environment as Markovian, even at the cost of introducing some error, due to the fact that transition model is not entirely Markovian. Our results apply also to this setting. This is an encouraging result, since in many cases the Markovian assumption is more of an abstraction of the environment, then the a precise description.

Related Work. The work most closely related to ours is that of Boyen and Koller (1998), where they considered monitoring in a Hidden Markov Model. In their setting, the environment is (exactly) known and the agent wants to keep a compact factored representation of the belief state (which may not exactly have a factored form). Their main assumption is that the environment is mixing rapidly, i.e the error contract by geometric factor after each time we apply the transition matrix operator. In contrast, we are interested in monitoring when we have only an approximate environment model. Both our work and theirs assume some form of contraction where beliefs tend to move closer to the truth under the Bayesian updates - ours is through an assumption about the value of observation while their is through assumption about the transition matrix. The main advantage of our method is that in many applications one can improve the quality of its observations, by adding more and better sensors. However, the mixing assumption used by Boyan and Koller may not be alterable. Furthermore, in the final Section, we explicitly consider their assumption in our setting and show how a belief state can be compactly maintained when both the model is approximate and when additional error accumulates from maintaining a compact factored representation.

Particle Filtering [Doucet, 1998] is a different monitoring approach, in which one estimates the current belief state by making a clever sampling, where in the limit one observes the true belief state. The major drawback with this method is in the case of a large variance where it requires many samples. A combination of the former two methods was considered by [Ng et al., 2002].

Building on the work of [Boyen & Koller, 1998] and the trajectory tree of [Kearns et al., 2002], McAllester and Singh (1999) provides an approximate planning algorithm. Similar extensions using our algorithm may be possible.

Outline. The outline of the paper is as follows. In Section 2 we provide notation and definitions. Section 3 is the main section of the paper and deals with monitoring and is composed from several subsections; Subsection 3.1 describes the algorithm; Subsection 3.2 provides the main monitoring theorem; Subsection 3.3 proves the Theorem. In Section 4, we show how to extend the results into the dynamic Bayesian networks.

2 Preliminaries

An Hidden Markov Model (HMM) is 4-tuple, (S, P,Ob,O), where S is the set of states such that |S| = N, P is the transition probability form every state to every state, Ob is the observations set and O is the observation distribution in every state. A belief state b is a distribution over the states S such that b(i) is the probability of being at state si. The transition probabilities of the belief states are defined according to HMM transition and observation probability, using a Bayesian update.

For a belief state b(·), the probability of observing o is O(o|b), where

After observing an observation o in belief state b(·), the updated belief state is:

where U O o is defined to be the observation update operator. Also, we define the transition update operator T as,

We denote by bt the belief state at time t, where at time 0 it is b0. (We will discuss both the case that the initial belief state is known and the case where it is unknown.) After observing observation ot ∈ Ob, the inductive computation of the belief state for time t + 1 is:bt+1 = T P U O ot bt,

where we first update the belief state by the observation update operator according to the observation ot and then by the transition update operator. It is straightforward to consider a different update order. Therefore, bt+1 is the distribution over states conditioned on observing {o0, o1, . . . ot} and on the initial belief state being b0.

3 Approximate Monitoring

We are interested in monitoring the belief state in the case where either our model is inaccurate or we do not have the correct initial belief state (or both). Let us assume that an algorithm has access to a transition matrix ̂ P and an observation distribution ̂O, which have error with respect to the true models. The algorithm's goal is to accurately estimate the belief state at time t, which we denote by ˆbt.

For notational simplicity, we define Eo∼b = Eo∼O(·|b). When P and ̂ P are clear from the context, we define T to be T P and ̂ T to be T b P . When O and ̂O are clear from the context, we define Uo to be U O o and ̂ Uo to be U b O o .

Our main interest is the behavior of

where the expectation is taken with respect to observation sequences {o0, o1, . . . ot-1} drawn according to the true model, and bt and ˆbt are the belief states at time t, with respect to these observation sequences.

In order to quantify the accuracy of our state monitoring, we must assume some accuracy conditions on our approximate model. The KL-distance is the natural error measure. The assumptions that we make now on the accuracy of the model will later be reflected in the quality of the monitoring.

Assumption 3.1 (Accuracy) For a given HMM model (S, P,Ob,O), an (ϵT , ϵO) accurate model is an HMM (S, P, Ob, O), such that for all states s ∈ S,

Next we define the value of observation parameter.

Definition 3.1 Given an observation distribution O, let M O be the matrix such that its (o, s) entry is O(o|s). The Value of Observation, γ, is defined as infx:‖x‖1=1 ‖Mx‖1 and it is in [0, 1].

Note that if the value of observation is γ, then for any two belief states b1 and b2,

where the first inequality follows from simple algebra.

The parameter γ plays a critical rule in our analysis. At the extreme, when γ = 1 we have ‖b1 - b2‖1 = ‖O(·|b1) - O(·|b2)‖1. Note that this definition is very similar to definition of the Dobrushin coefficient, supb1,b2 ‖P (b1, ·) - P (b2, ·)‖1 and it is widely used in the filtering literature [Moral, 2004]. We now consider some examples.

Let γ be 1 and consider b1 having support on one state and b2 on another state. In this case ‖b1 - b2‖1 = 2 and therefore ‖O(·|b1) - O(·|b2)‖1 = 2, which implies that we have a different observations from the two states. Since this holds for any two states, it implies that given an observation we can uniquely recover the state. To illustrate the value observation characterization, in POMDP terminology for γ = 1 we have a fully observable MDP as no observation can appear with positive probability in two states. At the other extreme, for an unobservable MDP, we can not have a value of γ > 0 since ‖O(·|b1) -O(·|b2)‖1 = 0 for any two belief states b1 and b2.

Recall the example in the Introduction where at every state the observation reveals the true state with probability 1-ϵ and with probability ϵ gives a random state. Here, it is straightforward to show that γ is 1 -ϵ. Hence, as ϵ approaches 0, the value of observation approaches 1.

We now show that having a value of γ bounded away from zero is sufficient to ensure some guarantee on the monitoring quality, which improves as γ increases. Throughout, the paper we assume that γ > 0.

3.1 The Belief State Update

Now we present the belief state update. The naive approach is to just use the approximate transition matrix ˆ P and the approximate observation distribution ˆO. The problemwith this approach is that the approximate belief state might place negligible probability on a possible state and thus a mistake may be irreversible.

Consider the following update operator ˜ T. For each states s ∈ S,

where Uni is the uniformdistribution. Intuitively, this update operator ˜U mixes with the uniform distribution, with weight ϵU , and thus always keeps the probability of being in any state bounded away from zero. Unfortunately, the mixture with the uniform distribution is an additional source of inaccuracy in the belief state, which our analysis would latter have to account for.

The belief state update is as follows.

where ˆbt is our previous belief state.

3.2 Monitoring the belief state

In this subsection we present our main theorem, which relates the accuracy of the belief state to our main parameters: the quality of the approximate model, the value of observation, and the weight on the uniform distribution.

Theorem 3.2 At time t let ˆbt be the belief state updated according to equation (1), bt be the true belief state, Zt = E [KL(bt||ˆbt)], and γ be the value of observation. Then

where ϵ = ϵT + ϵU log N + 3γ√ϵO and α = γ 2 2 log2 N ϵU .

Furthermore, if ‖ˆb0 - b0‖1 ≤ √ ϵα then for all times t:

Also, for any initial belief states b0 and ˆb0, and δ > 0, there exists a time τ(δ) ≥ 1, such that for any t ≥ τ(δ) we have

The following corollary now completely specifies the algorithm by providing a choice for ϵU , the weight of the uniform distribution.

Corollary 3.3 Assume that ‖ˆb0 - b0‖1 ≤ √ ϵα and ϵU = ϵT log N . Then for all times t,

Proof: With the choice of ϵU , we have:

And,

which completes the proof.

□

3.3 The Analysis

We start by presenting two propositions useful in proving the theorem. These are proved later. The first provides a bound on the error accumulation.

Proposition 3.4 (Error Accumulation)For every belief states bt and ˆbt and updates bt+1 = TUot bt and ˆbt+1 = ˜ T ̂ Uot ˆbt, we have:

The next proposition lower bounds the last term in Proposition 3.4. This term, which depends in the value of observation, enables us to ensure that the two belief states will not diverge.

Proposition 3.5 (Value of Observation) Let γ be the value of observation, b1 and b2 be belief states such that b2(s) ≥ μ for all s. Then

Using these two propositions we can prove our main theorem, Theorem 3.2.

Proof of Theorem 3.2: Due to the fact that ˜U mixes with the uniform distribution, we can take μ = ϵU/N. Combining Propositions 3.4 and 3.5, and recalling the definition of ϵ, we

By taking expectation with respect to {o0, o1, . . . ot-1}, we have:

where the last line follows since, by convexity,

which proves the first claim in the theorem.

We proceed with the case where the initial belief state is good in the sense that ‖ˆb0 - b0‖1 ≤ √ ϵα . Then we have that Zt is always less than √ ϵα . The function Zt -αZ 2 t + ϵ has derivative 1 - 2Ztα, which is positive when Zt ≤ √ ϵα . Since Zt at √ ϵα is mapped to √ ϵα , then every Zt ≤ √ ϵα is mapped to a smaller value. Hence the Zt will always remain below √ ϵα .

We conclude with the subtle case of unknown initial belief state, and define the following random variable

Note that Z ′ t is a positive super-martingale and therefore converges with probability 1 to a random variable Z ′ . The expectation of Z ′ cannot be larger than √ ϵα , since whenever Z ′ is larger than √ ϵα its expectation in the next timestep is strictly less than its expected value. Since by definition Z ′ t ≥ Zt then, regardless the our initial knowledge on the belief state, the monitoring will be accurate and results in error less than √ ϵα . □

Error Accumulation Analysis

In this subsection we present a series of lemmas which prove Proposition 3.4. The lemmas bound the difference between the updates in the approximate and true model.

We start by proving the Lemma 3.8 provided at the beginning of the Subsection

Lemma 3.6 For every belief states b1 and b2,

Proof: Let us define the joint distributions p1(s′ , s) = P (s, s′ )b1(s) and p2(s′ , s) = ˆ P (s, s′ )b2(s). Throughout the proof we specifically denote s to be the (random) 'first' state, and s′ to be the (random) 'next' state. By the chain rule for relative entropy, we can write:

where the last line follows by Assumption 3.1.

Let p1(s|s′ ) and p2(s|s′ ) denote the distributions of the first state given the next state, under p1 and p2 respectively. Again, by the chain rule of conditional probabilities we have,

where the last line follows from the positivity of the relative entropy. Putting these two results together leads to the claim.

□The next lemma bounds the effect of mixing with uniform distribution.

Lemma 3.7 For every belief states b1 and b2

Proof: By convexity,

where the last line uses the fact that the relative entropy between any distribution and the uniform one is bounded by log N. □

Combining these two lemmas we obtain the following lemma on the transition model.

Lemma 3.8 For every belief states b1 and b2,

After dealing with transition model, we are left to deal with the observation model. We provide an analog lemma with regards to the observation model.

Lemma 3.9 For every belief states b1 and b2,

Proof: First let us fix an observation o. We have:

where the last line uses the fact that O(o|b1) and ̂O(o|b2) are constants (with respect to s).

Now let us take expectations. For the first term, we have:

where the last step uses the fact that ∑o O(o|s) = 1. Similarly, for the third term, it straightforward to show that:

For the second term,

directly from the definition of the relative entropy. The lemma follows from Assumption 3.1. □

Now we are ready to prove Proposition 3.4.

Proof of Proposition 3.4: Using the definitions of updates and the previous lemmas:

where the first inequality is by Lemma 3.8 and the second is by Lemma 3.9 This completes the proof of Proposition 3.4.□

Value of Observation Proposition - The Analysis

The following technical lemma is useful in the proof and it relates the L1 norm to the KL divergence.

Proof: Let A be the set of states where b is greater than ˆb, i.e. A = {s|b(s) ≥ ˆb(s)}. So

where we have used the concavity of the log function and that ∑s∈A(b(s) -ˆb(s)) = 12 ‖b-ˆb‖1. The claim now follows using the fact that μ < 12 . □

We are now ready to complete the proof. We will make use of Pinsker's inequality, which relates the KL divergence to the L1 norm. It states that for any two distributions p and q

Proof of Proposition 3.5: By Pinsker's inequality and Assumption 3.1, we have

for all states s ∈ S. Using the triangle inequality,

Therefore,

where we used ‖ ̂O(·|ˆb) - O(·|ˆb)‖1 ≤ maxs ‖O(·|s) O(·|s)‖1 and Pinsker's inequality to bound ‖ ̂O(·|ˆb) O(·|ˆb)‖1 ≤ √2KL( ̂O(·|ˆb)||O(·|ˆb)) .

-

-

Combing with Pinsker's inequality, we have

where the before last inequality follows from ‖b -ˆb‖1 ≤ 2 and the last inequality from Lemma 3.10. □

4 Extension to DBNs

In many application one of the main limitations is the representation of the state which can grow exponentially in the number of state variables. Dynamic Bayesian Networks [Dean & Kanazawa, 1989] have compact representation of the environment. However, the compact representation of the network does not guarantee that one can represent compactly the belief state.

The factored representation can be thought as having an update of the following form

where H projects the belief state into the closest point in the factored representation space. Next we adopt the following definition from [Boyen & Koller, 1998] regarding the quality of the factored representation.

Definition 4.1 An approximation ˜b of ˆb, incurs error ϵ if relative to true belief state b we have

Armed with these definitions one can prove an equivalent Theorem to Theorem 3.2 with respect to KL(˜bt||bt). Due to lack of space and the similarity to the previous results we omit them.

5 Conclusions and Open Problems

In this paper we presented a new parameter in HMM, which governs how much information the observation convey. We showed how one can do fairly good monitoring in absence of an accurate model/unknown starting state/compcat representation as long as the HMM' observations are valuable. An open question that remains is whether the characterization can be made weaker and still an agent would be able to track, for instance if in most states the observations are valuable but there are few in which they are not, can we still monitor the state? Another very important research direction is that of planning in POMDPs. Our results show that one can monitor the belief state of the agent, however this is not enough for the more challenging problem of planning, where one should also decide which actions to take. It is not clear whether our characterization can yield approximate planning as well. The major problem with planning is that of taking the best action w.r.t to a distribution over states can lead to disastrous state and one should look into the long term implications of her actions due to the uncertainty. We leave these interesting problems to future work.