Acting Optimally in Partially Observable Stochastic Domains

Anthony R. Cassandra, Leslie Pack Kaelbling, Michael L. Littman

Abstract

This paper addresses the challenge of decision-making in environments characterized by partial observability and stochastic transitions. By framing the Partially Observable Markov Decision Process (POMDP) as a "Belief MDP," the authors introduce the Witness algorithm—a computationally efficient method for value iteration that leverages linear programming. The approach is validated on several benchmark problems, demonstrating significant improvements in solving complex planning tasks where agents must manage uncertainty about their current state.

Introduction

In a standard Markov Decision Process (MDP), an agent possesses perfect knowledge of its state at all times. However, real-world applications, such as robotics and autonomous navigation, often involve noisy sensors and limited visibility. The POMDP framework, established in the 1960s, provides a mathematical foundation for these scenarios but has historically suffered from extreme computational inefficiency. This paper bridges the gap between theoretical operations research and practical AI planning by introducing more efficient algorithms for finding optimal control strategies in these uncertain environments.

The POMDP Framework

The authors treat the POMDP as a "Belief MDP," where the state is represented not as a single discrete location, but as a belief state—a probability distribution over all possible underlying states. To act optimally, the agent must maintain this distribution based on its history of actions and observations.

POMDP control architecture featuring a state estimator (SE) and policy (\pi).

As shown in the architecture above, the system consists of two primary components: a state estimator (SE) that updates the belief state $b$ based on observations $o$, and a policy $\pi$ that maps the current belief state to an optimal action $a$.

The Witness Algorithm

The core innovation of this work is the Witness Algorithm. Previous exact solution methods for POMDPs often generated an excessive number of vectors to represent the value function, leading to a computational explosion. The Witness algorithm adopts a more surgical approach:

  1. It initializes with a minimal set of vectors.
  2. It employs linear programming to identify a "witness"—a specific belief state where the current value function representation is sub-optimal.
  3. Upon finding a witness, it adds only the specific vector required to resolve that gap.

This method allows the agent to handle a continuum of belief states using a finite set of linear segments. Furthermore, these complex mathematical policies can be compiled into a Policy Graph—a finite-state controller that allows for efficient execution without real-time heavy computation.

Experimental Evaluation

The algorithm was evaluated on several benchmark "toy" environments that were considered challenging at the time:

  • Simple 4-state Environment: A linear track where the agent must reach a goal but only receives location information at the goal itself.
  • 4x4 Unobservable Grid: A 16-state navigation task where all cells appear identical to the agent's sensors.
  • The Tiger Problem: A classic benchmark where an agent must decide whether to open one of two doors or "listen" to gain more information at a cost.
A 4x4 unobservable grid environment and its corresponding optimal policy graph.

In the 4x4 grid task (illustrated above), the agent successfully learns a policy graph that navigates to the goal despite the lack of direct state observations. In the Tiger Problem, the algorithm identifies a "listen until sure" strategy, demonstrating that the model naturally treats information-gathering as a valuable action.

Key Results and Insights

The Witness algorithm demonstrated empirical superiority over previous methods like Sondik’s or Monahan’s algorithms. Notably, it solved a 23-state problem—considered large for the era—in under 30 minutes.

A key insight of this work is that information-gathering is integrated directly into the reward structure. The agent learns to "pay" for information (e.g., by taking a sensing action) if that information is expected to increase long-term rewards. This allows the agent to behave optimally across varying levels of uncertainty, from being "completely lost" to "highly certain."

Conclusion and Future Work

While the Witness algorithm significantly improved the state of the art, the authors noted that POMDPs remain subject to the "curse of dimensionality." As the state space grows, the number of required vectors can still increase exponentially. Future work suggested moving toward approximate solutions for massive real-world problems and exploring Policy Iteration as a potentially faster alternative to Value Iteration. Nonetheless, this paper remains a foundational contribution to the field of automated planning under uncertainty.

Summary updated

Abstract

In this paper, we describe the partially observable Markov decision process (POMDP) approach to finding optimal or near-optimal control strategies for partially observable stochastic environments, given a complete model of the environment. The POMDP approach was originally developed in the operations research community and provides a formal basis for planning problems that have been of interest to the AI community. We found the existing algorithms for computing optimal control strategies to be highly computationally inefficient and have developed a new algorithm that is empirically more efficient. We sketch this algorithm and present preliminary results on several small problems that illustrate important properties of the POMDP approach.
BibTeX
@inproceedings{cassandra1994acting,
  author = {Anthony R. Cassandra and Leslie Pack Kaelbling and Michael L. Littman},
  title = {{Acting Optimally in Partially Observable Stochastic Domains}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure