An Anytime Algorithm for Reachability on Uncountable MDP

Kush Grover, Jan Kretínský, Tobias Meggendorfer, Maximilian Weininger

Abstract

We consider the problem of approximating the reachability probabilities in Markov decision processes (MDP) with uncountable (continuous) state and action spaces. While there are algorithms that, for special classes of such MDP, provide a sequence of approximations converging to the true value in the limit, our aim is to obtain an algorithm with guarantees on the precision of the approximation. As this problem is undecidable in general, assumptions on the MDP are necessary. Our main contribution is to identify sufficient assumptions that are as weak as possible, thus approaching the "boundary" of which systems can be correctly and reliably analyzed. To this end, we also argue why each of our assumptions is necessary for algorithms based on processing finitely many observations. We present two solution variants. The first one provides converging lower bounds under weaker assumptions than typical ones from previous works concerned with guarantees. The second one then utilizes stronger assumptions to additionally provide converging upper bounds. Altogether, we obtain an anytime algorithm, i.e. yielding a sequence of approximants with known and iteratively improving precision, converging to the true value in the limit. Besides, due to the generality of our assumptions, our algorithms are very general templates, readily allowing for various heuristics from literature in contrast to, e.g., a specific discretization algorithm. Our theoretical contribution thus paves the way for future practical improvements without sacrificing correctness guarantees.

Introduction

In automated verification, Markov Decision Processes (MDPs) serve as the fundamental framework for modeling systems characterized by both stochastic behavior and non-deterministic choice. While robust tools exist for finite MDPs—where states and actions are discrete—many critical real-world applications, such as robotics and power grid management, operate within uncountable (continuous) state and action spaces.

Analyzing these continuous systems is notoriously difficult. The general reachability problem in this context is undecidable, leading many current approaches to rely on "best effort" reinforcement learning or fixed-grid discretization. These methods often lack formal guarantees or a way to measure the distance between an approximation and the ground truth. This research seeks to define the "boundary" of what is computable by identifying the minimal assumptions required to calculate reachability probabilities with provable, iteratively improving error bounds.

Methodology

The authors introduce two algorithmic templates that adapt classic finite-state techniques to the continuous domain:

  1. Asynchronous Value Iteration (AVI): Traditionally used to establish lower bounds, this variant stores values for a finite set of sampled state-action pairs.
  2. Bounded Real-Time Dynamic Programming (BRTDP): This serves as the core "anytime" algorithm, maintaining both lower and upper bounds to provide a clear window of precision.

The Role of Lipschitz Continuity

To bridge the gap between a finite number of observations and an infinite state space, the algorithm assumes the Value Function is Lipschitz continuous. This assumption implies that if two states are spatially close, their reachability probabilities are also similar. By leveraging this property, the algorithm can "smear" information from a sampled point to its neighbors, creating a symbolic "envelope" of possible values across the entire continuous space. Notably, the authors argue that assuming the continuity of the value function is a weaker, and thus more broadly applicable, requirement than assuming the continuity of the transition function itself.

The Absorption Requirement

To ensure that upper bounds converge, the authors introduce an Absorption assumption. This requires that under any strategy, the system eventually terminates in either a target state (success) or a "sink" state (failure). This prevents the algorithm from becoming trapped in infinite loops that avoid the goal without ever reaching a terminal state, which would otherwise lead to non-converging upper bounds.

Experimental Evaluation

The proposed framework was implemented in a Java prototype and evaluated on two newly designed benchmarks:

  • 1D Navigation Model: A point moving on a line influenced by gravity and thrust, with the risk of entering a sink state during emergency maneuvers.
  • 2D Navigation Model: A robot navigating a unit square $[0, 1]^2$ toward a target corner while avoiding a central sink region.

Key Results

The experiments confirmed that the algorithm successfully produces converging lower and upper bounds, providing a verifiable "precision window."

  • Performance: In the 1D model, the tool achieved a precision of $\epsilon = 0.05$ in approximately 9 seconds. The more complex 2D model reached a precision of $\epsilon = 0.1$ in 620 seconds, requiring roughly 3GB of RAM.
  • Qualitative Mapping: The algorithm successfully distinguished between "safe" and "dangerous" regions. For example, in the 1D model, it correctly identified states where the proximity to a sink made escape impossible regardless of the action taken.
  • Heuristic Flexibility: As a template-based approach, the algorithm can incorporate various sampling heuristics (such as simulation-based sampling) without sacrificing formal correctness.

Limitations and Future Work

While this work establishes a new standard for provable reachability in continuous MDPs, several challenges remain. The algorithm currently requires the Lipschitz constant to be known a priori, which can be difficult to calculate for complex systems. Additionally, the Absorption assumption, while theoretically necessary for convergence, may be difficult to verify in practice.

Future research will focus on handling discontinuities—areas where small state changes lead to drastically different outcomes—by partitioning the state space into Lipschitz-continuous segments. Furthermore, addressing the "curse of dimensionality" in high-dimensional systems (e.g., multi-jointed robotics) remains a primary goal for scaling these formal guarantees to more complex real-world scenarios.

Summary updated

Abstract

We consider the problem of approximating the reachability probabilities in Markov decision processes (MDP) with uncountable (continuous) state and action spaces. While there are algorithms that, for special classes of such MDP, provide a sequence of approximations converging to the true value in the limit, our aim is to obtain an algorithm with guarantees on the precision of the approximation. As this problem is undecidable in general, assumptions on the MDP are necessary. Our main contribution is to identify sufficient assumptions that are as weak as possible, thus approaching the "boundary" of which systems can be correctly and reliably analyzed. To this end, we also argue why each of our assumptions is necessary for algorithms based on processing finitely many observations. We present two solution variants. The first one provides converging lower bounds under weaker assumptions than typical ones from previous works concerned with guarantees. The second one then utilizes stronger assumptions to additionally provide converging upper bounds. Altogether, we obtain an anytime algorithm, i.e. yielding a sequence of approximants with known and iteratively improving precision, converging to the true value in the limit. Besides, due to the generality of our assumptions, our algorithms are very general templates, readily allowing for various heuristics from literature in contrast to, e.g., a specific discretization algorithm. Our theoretical contribution thus paves the way for future practical improvements without sacrificing correctness guarantees.
BibTeX
@inproceedings{grover2022anytime,
  author = {Kush Grover and Jan Kretínský and Tobias Meggendorfer and Maximilian Weininger},
  title = {{An Anytime Algorithm for Reachability on Uncountable MDP}},
  booktitle = {CONCUR},
  year = {2022},
  doi = {10.4230/lipics.concur.2022.11},
}
Figure