On the computational complexity of stochastic controller optimization in POMDPs

Nikos Vlassis, Michael L. Littman, David Barber

Abstract

While Partially Observable Markov Decision Processes (POMDPs) provide a robust framework for decision-making under uncertainty, finding optimal policies is often computationally prohibitive. This paper investigates the complexity of optimizing "blind" controllers—the simplest class of policies that ignore history and state. We demonstrate a significant "stochasticity paradox": while finding optimal deterministic blind controllers is computationally efficient, finding optimal stochastic blind controllers is NP-hard and SQRT-SUM-hard. This result establishes a fundamental computational cliff in controller optimization and links the problem to long-standing open questions in computational complexity theory.

Introduction

In the study of Artificial Intelligence and control theory, Partially Observable Markov Decision Processes (POMDPs) are the standard for modeling agents operating with imperfect information. Because solving POMDPs exactly is often impossible, researchers frequently turn to simplified "controllers." A blind controller represents the most basic policy: it selects actions based on a fixed rule without regard for the current state, observation history, or time.

Intuitively, one might expect that such a restricted policy class would be easy to optimize. However, this research reveals that the introduction of randomization—allowing the agent to choose actions based on a probability distribution rather than a single fixed action—fundamentally alters the complexity of the problem. This paper categorizes the computational difficulty of finding the optimal probability distribution for these stochastic blind controllers.

The Complexity of Stochasticity

The core contribution of this work is the proof that optimizing a stochastic blind controller is significantly more difficult than optimizing a deterministic one. In the deterministic case, where the agent always picks the same action (e.g., "always move North"), the problem is in P (polynomial time). However, moving to a stochastic rule (e.g., "move North with 30% probability") pushes the problem into the realm of NP-hardness.

Reductions and Proofs

The authors establish these complexity bounds through two primary theoretical reductions:

  1. Reduction from Independent-Set: By applying the Motzkin-Straus theorem, which relates graph theory to the optimization of quadratic forms over a simplex, the authors show that solving the stochastic-blind-policy problem is at least as hard as finding the largest independent set in a graph—a classic NP-hard problem.
  2. The SQRT-SUM Connection: The problem is further identified as SQRT-SUM-hard. The SQRT-SUM problem (determining if the sum of square roots of integers is less than a specific value) is a notoriously difficult problem in the PSPACE category. This connection suggests that even verifying whether a proposed stochastic controller is "good enough" is a mathematically deep challenge that may sit outside of NP.

The Stochasticity Paradox and Bilinear Programming

In many areas of computer science, randomization is used to simplify algorithms or bypass deterministic bottlenecks. Here, the opposite occurs. This "Stochasticity Paradox" arises because the optimization of these controllers results in a jointly constrained bilinear program. In these programs, the variables—specifically the occupancy distributions and the action probabilities—are multiplied together in both the objective function and the constraints. This creates a non-convex landscape that is notoriously difficult for optimizers to navigate.

Because a blind controller is a special case of more complex POMDP controllers, these results have broad implications: they prove that stochastic controller optimization in POMDPs is NP-hard in general, regardless of the controller's complexity.

Identifying Tractable Subclasses

Despite the general hardness results, the authors identify a specific mathematical "green zone" where the problem becomes tractable. Through convex analysis, they prove that if the transition matrices are symmetric (doubly stochastic) and the costs follow a specific structure, the optimization function becomes convex.

In this specific case:

  • An optimal controller is guaranteed to be deterministic.
  • The global optimum can be found in $O(kn^3)$ time, where $k$ is the number of actions and $n$ is the number of states.

Conclusion and Future Work

This research establishes that the simplicity of a controller's structure does not guarantee ease of optimization. The jump from deterministic to stochastic policies introduces a computational cliff that links POMDPs to the SQRT-SUM problem.

Future research is needed to address the limitations of this study, particularly regarding approximation algorithms. While finding the exact global optimum is NP-hard, it remains to be seen if efficient algorithms can find near-optimal solutions. Additionally, while this work focuses on infinite-horizon problems, the complexity of finite-horizon or average-reward scenarios remains an open area for investigation.

Summary updated

Abstract

We show that the problem of finding an optimal stochastic blind controller in a Markov decision process is an NP-hard problem. The corresponding decision problem is NP-hard in PSPACE and sqrt-sum-hard, hence placing it in NP would imply breakthroughs in long-standing open problems in computer science. Our result establishes that the more general problem of stochastic controller optimization in POMDPs is also NP-hard. Nonetheless, we outline a special case that is convex and admits efficient global solutions.
BibTeX
@article{vlassis2011computational,
  author = {Nikos Vlassis and Michael L. Littman and David Barber},
  title = {{On the computational complexity of stochastic controller optimization in POMDPs}},
  journal = {ACM Trans. Comput. Theory},
  year = {2011},
  doi = {10.1145/2382559.2382563},
}
Figure