On Piecewise Affine Reachability with Bellman Operators
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911397930074112 |
|---|---|
| author | Varonka, Anton Watanabe, Kazuki |
| author_facet | Varonka, Anton Watanabe, Kazuki |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_19923 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Piecewise Affine Reachability with Bellman Operators Varonka, Anton Watanabe, Kazuki Discrete Mathematics Logic in Computer Science Dynamical Systems 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$. |
| title | On Piecewise Affine Reachability with Bellman Operators |
| topic | Discrete Mathematics Logic in Computer Science Dynamical Systems |
| url | https://arxiv.org/abs/2502.19923 |