Abstract-Vi anser syntes av kontrollpolicyer som maximerar sannolikheten för att uppfylla givna tidslogiska specifikationer i okända, stokastiska miljöer. Vi modellerar interaktionen mellan systemet och dess miljö som en Markov beslutsprocess (MDP) med initialt okända övergångssannolikheter. Den lösning vi utvecklar bygger på den så kallade modellbaserade troligen ungefär korrekta Markov-beslutsprocessen (PAC-MDP). Algoritmen uppnår en ε-ungefär optimal policy med sannolikhet 1 − δ med hjälp av prover (dvs. Observationer), tid och rum som växer polynomiskt med storleken på MDP, storleken på automaton som uttrycker tidslogik specifikation, och en ändlig tidshorisont. I detta tillvägagångssätt upprätthåller systemet en modell av den initialt okända MDP, och konstruerar en produkt MDP baserat på sin lärda modell och specifikationsautomaton som uttrycker tidslogiska begränsningar. Under genomförandet uppdateras policyn iterativt med hjälp av observation av de övergångar som gjorts av systemet. Iterationen avslutas i ändligt många steg. Med hög sannolikhet, den resulterande policyn är sådan att, för varje stat, skillnaden mellan sannolikheten för att uppfylla specifikationen enligt denna policy och den optimala en är inom en fördefinierad gräns.
Modellbaserade PAC-MDP-metoder kan användas för att syntetisera policyer som är ungefär optimala med hög sannolikhet REF.
Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraints
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}