On the Undecidability of Probabilistic Planning and Infinite-Horizon Partially Observable Markov Decision Problems

AAAI 1999

TL;DR

This paper proves that fundamental problems in probabilistic planning and infinite-horizon partially observable Markov decision processes (POMDPs) are undecidable. This means there's no general algorithm that can solve these problems for all possible inputs, even with unlimited computational resources, shattering hopes for universally applicable planning and decision-making systems in these domains.

What Problem Does This Paper Address?

The paper tackles the computability of decision-making under uncertainty, specifically in two related areas:

  1. Probabilistic Planning: Imagine a robot needing to achieve a goal in an uncertain environment. Actions don't always have predictable outcomes; they might lead to different states with certain probabilities. The goal is to find a sequence of actions (a plan) that guarantees reaching a desired state with a certain probability of success. This is crucial for applications where reliability is paramount.
  2. Partially Observable Markov Decision Processes (POMDPs): This is a more general framework where an agent doesn't know the exact state of the world. Instead, it receives observations that provide clues about the state. The agent needs to devise a strategy (a policy) to act optimally over time, maximizing some notion of reward (e.g., total discounted reward, average reward) or minimizing risk, even with incomplete information.

While researchers had made progress on finite-horizon or fully observable versions of these problems, the infinite-horizon and partially observable cases, especially for probabilistic planning, remained open questions regarding their fundamental computability. The authors aimed to settle whether these complex decision-making problems are solvable in principle.

Methods

The core of the paper's argument relies on a clever reduction from the string-existence problem for Probabilistic Finite Automata (PFAs) to the planning and POMDP problems.

  • Probabilistic Finite Automata (PFAs): These are like regular finite automata but with probabilistic transitions between states. The key problem here is the "string-existence" or "emptiness" problem: given a PFA and a threshold probability, does there exist any input string that the PFA accepts with a probability exceeding that threshold? This problem was already known to be undecidable.
  • Reduction Technique: The authors leverage a known reduction (from Condon & Lipton, 1989) that shows how to construct a PFA from a Turing Machine. This reduction has specific properties: if the Turing Machine accepts the empty string, the PFA accepts certain strings with high probability; otherwise, it accepts all strings with very low probability.
  • Modeling: The paper demonstrates how probabilistic planning problems and various POMDP optimality criteria (undiscounted total reward, average reward, discounted reward) can be precisely modeled using PFAs. This means that if you could solve a planning or POMDP problem, you could also solve the PFA string-existence problem.
  • Undecidability Transfer: Since the PFA string-existence problem is undecidable, and the planning/POMDP problems can perfectly mimic it, these more complex problems must also be undecidable.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The "No Free Lunch" Theorem for Planning: The paper's most significant insight is that for complex, realistic scenarios involving uncertainty and partial observability over infinite horizons, there is no universal algorithm that can find an optimal plan or policy. This is a fundamental theoretical limit.
  • PFA as a Universal Model: The paper highlights the surprising power of PFAs as a modeling tool. They can effectively capture the essence of probabilistic planning and various POMDP objectives, serving as a bridge to transfer undecidability results.
  • Undecidability of Approximations: Even the problem of finding an approximately optimal plan (within a certain additive or multiplicative factor of the true optimum) is also undecidable for PFAs and, by extension, for the planning and POMDP problems. This is a particularly strong result, as approximation algorithms are often sought when exact solutions are intractable.
  • Threshold Isolation is Undecidable: The problem of determining if a probability threshold is "isolated" (meaning there's a clear gap between the highest probability below the threshold and the lowest probability above it) for a PFA is also undecidable. This has implications for understanding the expressive power of PFAs.

Key Results

The paper establishes the undecidability of several key problems:

  • Probabilistic Planning: The problem of determining if a plan exists that achieves a success probability exceeding a given threshold is undecidable.
  • POMDP Policy Existence: For infinite-horizon POMDPs, the problem of determining if a policy exists that achieves a value greater than a threshold is undecidable for:
  • Positive-bounded models under total undiscounted reward.
  • Average reward criterion.
  • Discounted reward criterion.
  • State-oriented negative criteria (minimizing probability of entering bad states).
  • Approximation Problems: Problems related to finding approximate solutions (within an additive or multiplicative factor) are also undecidable.
  • Threshold Isolation: The problem of determining if a threshold is isolated for a PFA is undecidable.

Limitations and Future Work

  • Theoretical vs. Practical: The results are theoretical and establish fundamental limits. They don't preclude the existence of efficient algorithms for specific subclasses of problems or for practical approximations in many real-world scenarios.
  • Focus on Infinite Horizon: The paper primarily focuses on infinite-horizon problems. While finite-horizon POMDPs have known complexity bounds (often PSPACE-complete), the infinite horizon presents unique challenges.
  • Future Directions: The authors suggest that future work should focus on exploring alternative problem formulations and restrictions that might make these problems tractable. This could involve limiting the system dynamics, the agent's sensing capabilities, or the structure of the reward functions. They also hint that while optimal solutions might be impossible, finding good enough solutions might still be achievable through careful problem design.

Summary updated

BibTeX
@inproceedings{1999undecidability,
  title = {{On the Undecidability of Probabilistic Planning and Infinite-Horizon Partially Observable Markov Decision Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure