Sampling-Based Belief Revision

Michael ThielscherIJCAI 2016

Abstract

In complex environments such as imperfect-information games or autonomous robotics, agents often cannot represent every possible state. Instead, they rely on sampling—maintaining a small set of possible worlds consistent with observations. This paper provides the first formal logical foundation for this practice, evaluating it against the classic AGM postulates for rational belief change. The analysis reveals that while sampling-based revision is robust, satisfying six of the eight requirements, the resampling process inherently leads to the violation of Vacuity and Subexpansion.

Introduction

In domains like Poker or Bridge, the state space is too vast for exhaustive logical reasoning. Agents typically maintain a set of "samples" (models) that represent their current beliefs. When new evidence contradicts these samples, the agent must revise its beliefs by discarding inconsistent models and generating new ones. While effective in practice, the formal rationality of this "resampling" heuristic remained unexamined until now. This research investigates whether the heuristic of resampling is actually "rational" in a formal sense by testing it against the established logical standards of belief revision.

The AGM Framework and Postulate Testing

The "gold standard" for belief revision is defined by the eight AGM postulates (Alchourrón, Gärdenfors, and Makinson). These axioms describe how a rational agent should update its knowledge base upon receiving new information.

The eight AGM postulates for rational belief revision.

The author systematically tests a formalized sampling operator against these postulates. The results show that sampling-based revision is surprisingly robust, satisfying six of the eight postulates: Closure (AGM-1), Success (AGM-2), Inclusion (AGM-3), Consistency (AGM-5), Extensionality (AGM-6), and Superexpansion (AGM-7).

The Failure of Vacuity and Subexpansion

The most significant finding is the inherent failure of Vacuity (AGM-4) and Subexpansion (AGM-8). In classical logic, Vacuity states that if a new observation $\phi$ is consistent with current beliefs $K$, the agent should not lose any existing knowledge.

In sampling, however, even if $\phi$ is consistent with the overall belief set, it might contradict specific samples. Replacing these "dead" samples with new ones can lead to the loss of a previously held belief simply because the new samples do not happen to support it. This highlights a fundamental difference between logical preservation and the maintenance of a constant sample size; resampling introduces new models to maintain diversity, which behaves differently than traditional logical operators that prioritize keeping as much of the old knowledge as possible.

Logical Representation: Multiple Systems of Spheres

To capture this behavior logically, the author generalizes the standard "system of spheres" model. Instead of a single preference ordering over worlds, sampling-based revision requires a family of orderings—one for each sample. This reflects the diversity of hypotheses an agent maintains.

Multiple systems of spheres representing a collection of rankings for different samples.

Theorem 3 in the paper proves that a revision operator satisfies the six "sampling-friendly" postulates if and only if it can be represented by such a "weakly faithful assignment" to a collection of total pre-orders. This provides a rigorous mathematical bridge between the heuristic of sampling and formal belief revision theory.

Conclusion

This research bridges the gap between heuristic AI techniques and formal logic. By identifying exactly where sampling deviates from classical rationality, it provides a framework for more predictable and robust agent design. The paper also extends this into the Situation Calculus, providing a formal axiomatization for agents to reason about their own sampling processes. Future work will address iterated revision, exploring how repeated resampling might cause belief "drift" over long sequences of observations.

Summary updated

BibTeX
@inproceedings{thielscher2016sampling,
  author = {Michael Thielscher},
  title = {{Sampling-Based Belief Revision}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure