Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraints

Abstract

We consider synthesis of control policies that maximize the probability of satisfying given temporal logic specifications in unknown, stochastic environments. We model the interaction between the system and its environment as a Markov decision process (MDP) with initially unknown transition probabilities. The solution we develop builds on the so-called model-based probably approximately correct Markov decision process (PAC-MDP) methodology. The algorithm attains an $\epsilon$-approximately optimal policy with probability $1-\delta$ using samples (i.e. observations), time and space that grow polynomially with the size of the MDP, the size of the automaton expressing the temporal logic specification, $\frac{1}{\epsilon }$, $\frac{1}{\delta }$ and a finite time horizon. In this approach, the system maintains a model of the initially unknown MDP, and constructs a product MDP based on its learned model and the specification automaton that expresses the temporal logic constraints. During execution, the policy is iteratively updated using observation of the transitions taken by the system. The iteration terminates in finitely many steps. With high probability, the resulting policy is such that, for any state, the difference between the probability of satisfying the specification under this policy and the optimal one is within a predefined bound.

9 pages, 5 figures, Accepted by 2014 Robotics: Science and Systems (RSS)

Cited by in corpus (20)

• A Review of Robot Learning for Manipulation: Challenges, Representations, and Algorithms
• Modular Deep Reinforcement Learning for Continuous Motion Planning with Temporal Logic
• Robust Control for Dynamical Systems With Non-Gaussian Noise via Formal Abstractions
• Sampling-Based Robust Control of Autonomous Systems with Non-Gaussian Noise
• Reinforcement Learning Based Temporal Logic Control with Maximum Probabilistic Satisfaction
• Modular Deep Reinforcement Learning with Temporal Logic Specifications
• Safe Reinforcement Learning via Probabilistic Shields
• Tractable Reinforcement Learning of Signal Temporal Logic Objectives
• Control Synthesis from Linear Temporal Logic Specifications using Model-Free Reinforcement Learning
• Safe Control under Uncertainty
• A Learning Based Optimal Human Robot Collaboration with Linear Temporal Logic Constraints
• Safety-Constrained Reinforcement Learning for MDPs
• Learning Optimal Strategies for Temporal Tasks in Stochastic Games
• Reinforcement Learning Based Temporal Logic Control with Soft Constraints Using Limit-deterministic Generalized Buchi Automata
• Statistical Verification of Autonomous Systems using Surrogate Models and Conformal Inference
• Synthesis of Discounted-Reward Optimal Policies for Markov Decision Processes Under Linear Temporal Logic Specifications
• PAC Model Checking of Black-Box Continuous-Time Dynamical Systems
• POMDP Model Learning for Human Robot Collaboration
• Statistically Model Checking PCTL Specifications on Markov Decision Processes via Reinforcement Learning
• Approximate Dynamic Programming with Probabilistic Temporal Logic Constraints