On Piecewise Affine Reachability with Bellman Operators

Abstract

We study the following reachability problem for piecewise affine maps: Given two vectors $\mathbf{s},\mathbf{t}\in {\mathbb{Q}}^d$ and a piecewise affine map $f:{\mathbb{Q}}^d\to {\mathbb{Q}}^d$, does there exist $n\in \mathbb{N}$ such that $f^n(\mathbf{s})=\mathbf{t}$? In this work, we focus on this reachability problem for a subclass of piecewise affine maps -- Bellman operators arising from Markov decision processes. We prove that the reachability problem for $\max$- and $\min$-Bellman operators is decidable in any dimension under either of the following conditions: (i) the target vector $\mathbf{t}$ is not the fixed point of the operator $f$; or (ii) the initial and target vectors $\mathbf{s}$ and $\mathbf{t}$ are comparable with respect to the componentwise order. Furthermore, we show that in the two-dimensional case, the reachability problem for Bellman operators is decidable for arbitrary $\mathbf{s},\mathbf{t}\in {\mathbb{Q}}^2$. This stands in sharp contrast to the known undecidability of reachability for general piecewise affine maps in dimension $d=2$.

includes a study of Bellman operators under the minimisation objective and a refined proof of the decidability for the two-dimensional case, now for both min and max objectives