On the Optimality of Uncertain MDP Abstractions
Ibón Gracia, Morteza Lahijanian · 2026
Read On the Optimality of Uncertain MDP Abstractions by Ibón Gracia, Morteza Lahijanian (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-13377.txt.
Introduction
Gracia and Lahijanian ask if refining uncertain MDP models can reach the best controller with no error left. Their method turns a nonlinear stochastic system into an uncertain MDP, builds a controller with guarantees by robust dynamic programming, then refines the model until it is near best. Theory gives a sufficient condition, vanishing ambiguity, that ensures the process reaches the best result in the limit and finishes in finite time. Set-valued MDP models meet it, while interval MDP models do not.
Catalog record
| CREATOR | Ibón Gracia, Morteza Lahijanian |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 87146 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.13377
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Optimality of Uncertain MDP Abstractions Ibón Gracia, Morteza Lahijanian Abstract We study the asymptotic optimality of abstraction-based control synthesis algorithms. Specifically, we consider uncertain MDP (UMDP) abstraction, and investigate whether refinement leads to optimal results, i.e., an optimal controller and zero error bound. Additionally, we study completeness of abstraction-refinement algorithms, i.e., that the algorithm produces near-optimal results in finite time. The focus is on nonlinear stochastic systems with general vector fields and temporal logic specifications. We present an algorithm that abstracts the system into a UMDP and synthesizes a controller with performance guarantees via robust dynamic programming. Then, the algorithm iteratively refines the abstraction until a near-optimality criterion is met. A thorough theoretical analysis reveals a sufficient condition, which we denote vanishing ambiguity , guaranteeing asymptotic optimality of the abstraction process and completeness of the algorithm. We show that set-valued MDP abstractions satisfy this criterion, whereas interval MDP abstractions lack such a guarantee. I Introduction Automatic control of safety-critical cyber-physical systems requires formal guarantees, but in practice these rely on approximations with quantified (and ideally tight) error bounds. This is particularly challenging for complex, nonlinear, and stochastic robotic systems, where loose bounds (e.g., an autonomous car with safety probability lower-bound 0.90 and upper-bound 1.0 ) are insufficient for deployment. Abstraction-based methods enable formal synthesis for such systems, and even for complex temporal logic specifications, by modeling the systems as finite-state uncertain MDPs (UMDPs). While these approaches provide sound probability bounds, they typically lack guarantees of asymptotic optimality, i.e., that refinement of the abstraction converges to the true satisfaction probability. Indeed, finer discretizations do not always improve bounds and can even degrade them [ 15 ] . This raises a fundamental question: “ under what conditions are UMDP abstraction-based methods asymptotically optimal? ” In this work, we aim to address it by identifying a sufficient condition under which asymptotic optimality is guaranteed and UMDP classes that satisfy this condition. When it comes to formal control via UMDP abstractions, work [ 1 ] focuses on stochastic hybrid systems with regular transition and reset kernels. It abstracts the continuous-state system as an MDP and then quantifies the error between the safety probabilities of the original system and the abstraction. The obtained error bound vanishes as the discretization becomes finer, meaning that the abstraction approach is asymptotically optimal. However, the obtained bounds are loose. In consequence, [ 19 ] proposes to soundly abstract the original system into a UMDP class named interval MDP (IMDP). This approach effectively embeds the discretization error into the ambiguous, i.e., not fixed, transitions of the abstraction. Such works obtain the tightest bounds on the transition probabilities under restrictive assumptions on the system’s dynamics, like additive Gaussian disturbances and/or linear dynamics [ 4 , 2 ] . In consequence, these abstraction processes are also asymptotically optimal. Additional works also obtain IMDP abstractions assuming additive and/or unimodal disturbances [ 8 , 18 , 24 ] . On the other hand, for general nonlinear dynamics, most works employ 1 -step reachable sets to obtain sound abstractions [ 12 , 21 , 22 , 13 ] . While these approaches yield correct bounds in the satisfaction probabilities, it is not clear if they are asymptotically optimal. Recent works [ 12 , 11 , 13 , 15 , 5 ] employ more general UMDP abstraction classes than IMDPs to account for additional, e.g., epistemic, uncertainties [ 12 , 11 ] , or to obtain tighter performance bounds [ 13 , 15 , 5 ] . Some works also propose heuristic abstraction-refinement algorithms [ 9 , 8 , 2 ] in order to improve the obtained guarantees. However, a discussion on asymptotic optimality is again missing in these works. In fact, to the best of our knowledge, no UMDP abstraction-based approach ensures asymptotic optimality when considering temporal logic specifications, as the value functions become discontinuous, making convergence analysis non-trivial [ 1 ] . In this work we lay the foundation for the general theory of asymptotic optimality in UMDP abstractions under specifications given as linear temporal logic over finite traces (LTL f ) [ 7 ] formulas. We considering a fully known system model and general rectangular UMDPs [ 16 ] . Our contributions are threefold: (i) we derive a sufficient condition on the abstraction procedure that guarantees its asymptotic optimality; (ii) we show that, for general nonlinear dynamics and when the abstraction is obtained via reach set computations, state-of-the-art set-valued MDP (SMDP) abstractions [ 13 ] , are indeed asymptotically optimal, while others, relying on the popular IMDP abstractions [ 22 ] , are not; (iii) we propose a general abstraction-refinement algorithm that synthesizes \varepsilon -optimal controllers and satisfaction probability bounds in finite time for any asymptotically optimal UMDP abstraction. II Basic Notation We let \mathbb{N}_{0}:=\mathbb{N}\cup\{0\} . Given a set A\subseteq X , we let \partial A denote the boundary of A and denote by \mathds{1}_{A}:X\mapsto\{0,1\} the indicator function of A , which returns \mathds{1}_{A}(x)=1 if x\in A and 0 otherwise. Given a subset A of a metric space (X,d) , we let \mathrm{diam}_{d}(A):=\sup_{x,x^{\prime}\in A}d(x,x^{\prime}) be the diameter of A . We also denote by B(0,\epsilon)\subset X the closed \epsilon -ball centered at 0 . Given subsets A,B\subset X , we denote by A\oplus B their Minkowski sum . Given a set X , we denote by \mathcal{F}(X) its Borel \sigma -algebra and by \mathcal{P}(X) the set of Borel probability distributions (measures) over X . Given a measurable space (X,\mathcal{F}(X)) , we denote by \mathcal{L} the Lebesgue measure . When the space is equipped with a metric d , we denote the Wasserstein distance between measures \gamma,\gamma^{\prime}\in\mathcal{P}(X) by \mathcal{W}(\gamma,\gamma^{\prime}):=\inf_{\pi\in\Pi(\gamma,\gamma^{\prime})}\int_{X^{2}}d(x,x^{\prime})d\pi(x,x^{\prime}) , where \Pi(\gamma,\gamma^{\prime})\in\mathcal{P}(X^{2}) is the set of probability measures on X^{2} with marginals \gamma and \gamma^{\prime} . Given a subset A of (X,d) , the measurable space (A,\mathcal{F}(A)) and the probability measure P\in\mathcal{P}(A) , with a slight abuse of notation, we also interpret this measure as an element of \mathcal{P}(X) , without formally defining its extension on (X,\mathcal{F}(X)) . In consequence, we sometimes write \int_{X}fdP:=\int_{A}f|_{A}dP for f:X\rightarrow\mathbb{R} , with f|_{A} being the restriction of f to A . III Problem Formulation We consider a discrete-time stochastic system of the form \displaystyle x_{t+1}=f(x_{t},u_{t},w_{t}), (1) with x_{t}\in X\subseteq\mathbb{R}^{n} being the state at time t\in\mathbb{N}_{0} , u_{t}\in U denoting the action where U is a finite set, and w_{t} is a random disturbance. We assume that \{w_{t}\}_{t\in\mathbb{N}_{0}} is an i.i.d. stochastic process taking values in a compact set W\subset\mathbb{R}^{d} , where w_{t}\sim P_{W} . Given x_{0},\ldots,x_{T}\in X , u_{0},\dots,u_{T-1}\in U , and T\in\mathbb{N}_{0} , we denote a finite trajectory of System ( 1 ) by \omega^{X}=x_{0}\xrightarrow{u_{0}}\ldots\xrightarrow{u_{T-1}}x_{T} . We let \Omega^{X}_{T} denote the set of all trajectories of length T\in\mathbb{N}_{0} . A time-varying controller \kappa:=(\kappa_{0},\dots,\kappa_{T-1}) is a set of functions indexed by time where each \kappa_{t} is a function \kappa_{t}:\omega_{t}^{X}\rightarrow U that maps the current trajectory to the next action u_{t}\in U . We denote by \mathcal{K} the set of all such controllers. The transition kernel of System ( 1 ) is a function \mathcal{T}:\mathcal{F}(X)\times X\times U\rightarrow[0,1] that, given current state x_{t} and action u_{t} , and the Borel set D , returns the probability that the successor state belongs to D , i.e., x_{t+1}\in D with