Constructing MDP Abstractions Using Data with Formal Guarantees
This paper is concerned with a data-driven technique for constructing finite Markov decision processes (MDPs) as finite abstractions of discrete-time stochastic control systems with unknown dynamics while providing formal closeness guarantees. The proposed scheme is based on notions of stochastic bisimulation functions (SBF) to capture the probabilistic distance between state trajectories of an unknown stochastic system and those of finite MDP. In our proposed setting, we first reformulate corresponding conditions of SBF as a robust convex program (RCP). We then propose a scenario convex program (SCP) associated to the original RCP by collecting a finite number of data from trajectories of the system. We ultimately construct an SBF between the data-driven finite MDP and the unknown stochastic system with a given confidence level by establishing a probabilistic relation between optimal values of the SCP and the RCP. We also propose two different approaches for the construction of finite MDPs from data. We illustrate the efficacy of our results over a nonlinear jet engine compressor with unknown dynamics. We construct a data-driven finite MDP as a suitable substitute of the original system to synthesize controllers maintaining the system in a safe set with some probability of satisfaction and a desirable confidence level.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Agile Temporal Discretization for Symbolic Optimal Control
As control systems grow in complexity, abstraction-based methods have become essential for designing controllers with formal guarantees. However, a key limitation of these methods is their reliance on discrete-time model…
Data-driven Construction of Finite Abstractions for Interconnected Systems: A Compositional Approach
Finite-state abstractions (a.k.a. symbolic models) present a promising avenue for the formal verification and synthesis of controllers in continuous-space control systems. These abstractions provide simplified models tha…
Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learning
The main focus of Hierarchical Reinforcement Learning (HRL) is studying how large Markov Decision Processes (MDPs) can be more efficiently solved when addressed in a modular way, by combining partial solutions computed f…
Hierarchical Reinforcement LearningNeural Abstractions
We present a novel method for the safety verification of nonlinear dynamical models that uses neural networks to represent abstractions of their dynamics. Neural networks have extensively been used before as approximator…
Guarantees for Sound Abstractions for Generalized Planning (Extended Paper)
Generalized planning is about finding plans that solve collections of planning instances, often infinite collections, rather than single instances. Recently it has been shown how to reduce the planning problem for genera…