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 \colon \mathbb{ Q}^d\rightarrow \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$.
Categories: cs.DM cs.LO math.DS