💻 computer science

On Piecewise Affine Reachability with Bellman Operators

This paper establishes the decidability of the reachability problem for Bellman operators arising from Markov decision processes under specific conditions in any dimension and for arbitrary inputs in two dimensions, contrasting with the known undecidability of reachability for general piecewise affine maps.

Original authors: Anton Varonka, Kazuki Watanabe

Published 2026-01-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Anton Varonka, Kazuki Watanabe

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a video game where you are trying to guide a character from a starting point (let's call it Start) to a specific treasure chest (Target).

In this game, the world is governed by a set of rules called a Bellman Operator. Think of this operator as a very smart, slightly chaotic GPS. Every time you take a step, the GPS looks at your current location and tells you where you will end up next. However, this GPS has a twist: it doesn't just give you one direction. It looks at several possible paths (some are "best case," some are "worst case") and picks the one that fits the current situation best.

The big question the paper asks is: If you keep following this GPS, will you ever land exactly on the treasure chest?

The Problem: A Chaotic Maze

In the world of mathematics, this is called a "Piecewise Affine Map." Imagine a map that is divided into different zones. In Zone A, the rules are simple (like walking in a straight line). In Zone B, the rules change slightly. In Zone C, they change again.

For general maps like this, mathematicians have known for a long time that the answer to "Will I reach the treasure?" is impossible to know. It's like trying to predict the exact path of a leaf in a hurricane; the system is too complex and unpredictable. Even in a simple 2D world (like a flat piece of paper), this problem is usually unsolvable.

The Solution: The "Smart" GPS

The authors of this paper decided to look at a specific, special type of GPS used in Markov Decision Processes (MDPs). In real life, these are used to model systems with uncertainty, like a robot navigating a room or a game AI making decisions.

These special GPSs (Bellman Operators) have a unique superpower: they always try to find the optimal path. They are designed to converge toward a single, perfect destination called the Fixed Point. Think of this Fixed Point as the "True North" of the system. No matter where you start, if you keep following the rules, you will eventually get very, very close to True North.

The paper asks: Can we mathematically prove whether we will ever hit the target exactly, or just get close to it?

The Three Scenarios

The authors broke the problem down into three scenarios, like checking different conditions before starting a journey:

1. The Target is NOT the "True North"
If the treasure chest you are looking for is not the system's natural destination (the Fixed Point), the answer is easy.

The Analogy: Imagine the GPS is pulling you toward True North. If your target is a random spot on the map that isn't True North, the GPS will eventually pull you past it.
The Result: The authors proved that if the target isn't the natural destination, we can calculate a "deadline." If you haven't reached the target by that deadline, you never will. It's a "Yes" or "No" answer that can be found quickly.

2. The Target IS "True North," and you are already on the right side
If your target is the natural destination, and you start either "above" it or "below" it (in a mathematical sense), the path is predictable.

The Analogy: Imagine you are sliding down a hill toward a valley. If you start on the left side of the hill, you will slide down the left side. You won't suddenly jump to the right side.
The Result: The authors showed that in this case, the system eventually settles into a simple pattern where it only uses the "best" moves. We can track this pattern easily and determine if you will land exactly on the target.

3. The Target IS "True North," but you are "off-center"
This is the hardest case. You want to reach the natural destination, but you start in a weird spot where you are "above" the target in some ways and "below" it in others.

The Analogy: Imagine trying to balance a ball on a wobbly table. You are pushing it from a weird angle. It might bounce around unpredictably before settling.
The Result: For a 2D world (a flat surface), the authors found a clever trick. They realized that even though the ball bounces, the "lines" it bounces off of have a specific order. By analyzing these lines, they proved that either the ball hits the target within two bounces, or it will never hit it. This solves the puzzle for 2D.

Why This Matters

The paper's main achievement is finding a "safe zone" within a chaotic world.

General Maps: Unpredictable and unsolvable (like a hurricane).
Bellman Operators (MDPs): Predictable and solvable (like a guided tour).

The authors proved that for these specific "smart" maps, we can always answer the question: "Will we reach the target?"

If the target isn't the natural destination, we can check a short list of steps.
If the target is the natural destination and we start "straight," we can check the pattern.
If we are in 2D and start "crooked," we can check the geometry of the bounces.

The Bottom Line

The paper doesn't claim this solves every math problem in the universe. It specifically solves the "reachability" problem for a very important class of maps used in computer science and AI (Bellman Operators).

They showed that while the general version of this problem is a nightmare (undecidable), the version used in decision-making systems is actually manageable. They provided the "instruction manual" to determine if a system will ever hit a specific goal, turning an impossible question into a solvable one for these specific cases.

In short: They took a chaotic, unpredictable maze and showed that if the maze is built by a "smart" decision-maker, we can always figure out if the exit is reachable.

Technical Summary: On Piecewise Affine Reachability with Bellman Operators

1. Problem Statement

The paper investigates the reachability problem for Piecewise Affine Maps (PAMs), specifically focusing on a subclass known as Bellman operators arising from Markov Decision Processes (MDPs).

The general reachability problem asks: Given a map $f: \mathbb{Q}^d \to \mathbb{Q}^d$ and two vectors $s, t \in \mathbb{Q}^d$ , does there exist an integer $n \in \mathbb{N}$ such that $f^n(s) = t$ ?

Context: For general affine maps, this problem is decidable (Kannan and Lipton). However, for general PAMs, the problem is undecidable even in dimension $d=2$ (Koiran et al.).
Specific Focus: The authors restrict the domain to Bellman operators $\Phi: [0, 1]^d \to [0, 1]^d$ derived from MDPs without end components. These operators represent the optimal reachability probabilities (maximum or minimum) to a target state. The problem is formalized as Bellman Operator Reachability (BOR): Given $s, t \in [0, 1]^d \cap \mathbb{Q}^d$ and a Bellman operator $\Phi$ , does $\Phi^n(s) = t$ for some $n$ ?

2. Methodology and Approach

The authors adopt an approach that restricts the structure of the PAM (Bellman operators) rather than the dimension or the number of pieces. Their methodology relies on the convergence properties of Bellman operators and the analysis of "tight" versus "leaking" actions.

Key Concepts

Convergence: Under the assumption of no end components, the sequence $\langle \Phi^n(s) \rangle$ converges to a unique fixed point $\mu_\Phi$ (the vector of optimal reachability probabilities) from any initial vector $s$ .
Tight vs. Leaking Actions:
- An action is tight at a state $i$ if it preserves the fixed point value (i.e., $L_\alpha(\mu_\Phi) = (\mu_\Phi)_i$ ).
- An action is leaking if it does not preserve the fixed point value.
Sign Abstraction: The authors define a sign vector $f(x) \in \{-1, 0, 1\}^d$ based on the componentwise comparison of $x$ with the target $t$ (where $t = \mu_\Phi$ ).
Reduction to Matrix Semigroups: For the case where only tight actions are eventually chosen, the problem is reduced to the Product Family Reachability (PFR) problem. This involves determining if a sequence of matrix multiplications (from a semigroup generated by substochastic matrices) maps a vector $\epsilon = s - \mu_\Phi$ to zero.

3. Key Contributions and Results

The paper establishes decidability for the BOR problem under specific conditions and for specific dimensions.

A. Arbitrary Dimensions ( $d \geq 1$ )

The authors prove decidability for arbitrary dimensions under two distinct conditions:

Target is not the Fixed Point ( $t \neq \mu_\Phi$ ):
- Result: Decidable.
- Method: Since the sequence converges to $\mu_\Phi$ , the distance $\|\Phi^n(s) - \mu_\Phi\|$ eventually becomes smaller than $\|t - \mu_\Phi\|$ . The authors compute an effective bound $N$ such that if $t$ is reachable, it must be reached within $N$ steps.
Target is the Fixed Point ( $t = \mu_\Phi$ ) and Vectors are Comparable:
- Condition: The initial vector $s$ is comparable to $t$ (i.e., $s \leq t$ or $s \geq t$ componentwise).
- Result: Decidable.
- Method:
  - Phase 1 (Leaking Actions): The authors show that after a computable number of steps, the Bellman operator only selects tight actions.
  - Phase 2 (Sign Abstraction): Once only tight actions are active, the evolution of the sign vector $f(\Phi^n(s))$ becomes deterministic and depends only on the previous sign vector, not the exact values. Since the space of sign vectors is finite ( $2^d$ ), the sequence either reaches the zero vector (indicating $t$ is reached) or enters a cycle without reaching zero.

B. Two-Dimensional Case ( $d = 2$ )

The authors address the remaining difficult case where $t = \mu_\Phi$ and $s$ is incomparable to $t$ (i.e., $s \triangleright \triangleleft t$ ).

Result: The BOR problem is decidable for $d=2$ for both max- and min-Bellman operators.
Method:
- The problem is reduced to the PFR problem in 2D.
- The authors exploit the existence of a total order on the lines induced by the actions (based on the angle of their kernel lines).
- They prove a structural lemma (Lemma 4.2/4.5): For any vector $\epsilon$ incomparable to 0, the sequence $\epsilon, F(\epsilon), F^2(\epsilon), \dots$ either reaches a vector comparable to 0 within two steps, or it never reaches 0.
- This property allows the algorithm to terminate: if the sequence does not become comparable to 0 quickly, the answer is "no."

C. Summary of Decidability

General PAMs: Undecidable in $d=2$ .
Bellman Operators:
- Decidable for all $d$ if $t \neq \mu_\Phi$ .
- Decidable for all $d$ if $s$ is comparable to $t = \mu_\Phi$ .
- Decidable for $d=2$ even if $s$ is incomparable to $t = \mu_\Phi$ .

4. Significance and Claims

The paper claims to provide the first reasonably large class of PAMs for which the reachability problem is decidable in the two-dimensional case, contrasting sharply with the known undecidability of general PAMs in the same dimension.

Extension of Previous Work: This work extends the authors' previous research (which focused on max-Bellman operators) to include min-Bellman operators, requiring new definitions and proof techniques to handle the minimum objective uniformly.
Theoretical Contribution: The paper highlights that while the general vector reachability problem for matrix semigroups is undecidable, the specific structure of Bellman operators (non-negative coefficients, substochastic matrices, and the specific geometry of 2D kernels) allows for decidability in $d=2$ .
Mortality Problem: The authors note that their results imply the decidability of the mortality problem (whether $\Phi^n(s) = t$ for all $s$ ) for Bellman operators in any dimension, as this reduces to checking the BOR problem for $s=0$ and $s=1$ .

The authors remain modest regarding higher dimensions ( $d > 2$ ) with incomparable vectors, noting that the decidability remains open due to the complexity of the dynamics of the product family semigroup in higher dimensions, which does not admit the simple total ordering argument used for $d=2$ .