On the Complexity of Iterative Tropical Computation with Applications to Markov Decision Processes

Nikhil Balaji, Stefan Kiefer, Petr Novotný, Guillermo A. Pérez, Mahsa ShirmohammadiarXiv 2018 · OpenReview

Introduction

For decades, Value Iteration (VI) has served as a fundamental algorithmic tool for solving Markov Decision Processes (MDPs). Despite its ubiquity in artificial intelligence and robotics, its exact computational complexity remained an open question for over 30 years. This paper settles the debate, proving that computing an optimal policy for a finite horizon $H$ (encoded in binary) is EXPTIME-complete. This result suggests that the exponential-time iterative process typically employed is likely optimal, as no polynomial-space "shortcut" exists.

The Problem: Value Iteration and the Horizon Gap

MDPs provide a mathematical framework for decision-making under uncertainty. Value Iteration finds the optimal payoff over a horizon $H$ by repeatedly applying a recurrence equation. The complexity of this task hinges on the representation of $H$:

  1. If $H$ is small (unary), the problem is P-complete.
  2. If $H$ is large (binary), the algorithm runs for an exponential number of steps.

Since the seminal work of Papadimitriou and Tsitsiklis in 1987, researchers have wondered if a PSPACE algorithm could bypass these iterations. This work confirms that the problem is inherently hard, requiring exponential time.

Methodology: The Reduction Chain

The authors establish EXPTIME-hardness through a sophisticated chain of reductions, transforming a known hard problem into Value Iteration.

The reduction chain from EXPTIME-bounded Turing Machine termination to Value Iteration.

The process begins with the termination problem for an exponential-time Turing Machine and proceeds through several intermediate steps:

  • Counter Programs: Reducing the TM problem to the bounded termination of simple counter programs.
  • Straight-Line Programs (SLPs): Simulating counter programs by iterating functions represented as SLPs (sequences of $max$ and $+$ operations).
  • MDP Reachability: Mapping the SLP "powering problem" (calculating results after $H$ iterations) onto MDP state reachability.

Key Insights: Bitsize Explosion and Max-Plus Logic

A critical insight involves the "bitsize trap." While an MDP might be small, the number of bits required to represent values can grow exponentially during iteration (e.g., values halving at each step). This prevents simple space-saving techniques from reducing the problem to PSPACE.

An example MDP and its corresponding value iteration recurrence equations.

Furthermore, the paper demonstrates that iterating simple "max-plus" functions—using only $max$ and addition—is sufficient to simulate a full Turing machine. This has significant implications for arithmetic circuit theory beyond just MDPs.

Key Results

  • EXPTIME-Completeness: Determining if a specific action is optimal for a binary-encoded horizon $H$ is EXPTIME-complete.
  • Finite-Horizon Reachability: Maximizing the probability of reaching a target state in $H$ steps is also EXPTIME-complete.
  • SLP Powering: The paper establishes that comparing SLP outputs after $H$ iterations is EXPTIME-complete, solving a major question in the study of arithmetic circuits.

Conclusion and Future Work

This work provides a definitive complexity bound for exact Value Iteration. Future research may explore whether approximate value iteration—finding a "near-optimal" policy—shares this same extreme complexity. Additionally, a variant regarding the existence of any policy achieving a reward threshold remains a formal open question in the theory.

Summary updated

BibTeX
@misc{balaji2018complexity,
  author = {Nikhil Balaji and Stefan Kiefer and Petr Novotný and Guillermo A. Pérez and Mahsa Shirmohammadi},
  title = {{On the Complexity of Iterative Tropical Computation with Applications to Markov Decision Processes}},
  year = {2018},
  url = {https://openreview.net/forum?id=AvnbbXa6spP},
}
Figure