Strategy Synthesis in Markov Decision Processes Under Limited Sampling Access

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

Abstract

A central task in control theory, artificial intelligence, and formal methods is to synthesize reward-maximizing strategies for agents that operate in partially unknown environments. In environments modeled by gray-box Markov decision processes (MDPs), the impact of the agents’ actions are known in terms of successor states but not the stochastics involved. In this paper, we devise a strategy synthesis algorithm for gray-box MDPs via reinforcement learning that utilizes interval MDPs as internal model. To compete with limited sampling access in reinforcement learning, we incorporate two novel concepts into our algorithm, focusing on rapid and successful learning rather than on stochastic guarantees and optimality: lower confidence bound exploration reinforces variants of already learned practical strategies and action scoping reduces the learning action space to promising actions. We illustrate benefits of our algorithms by means of a prototypical implementation applied on examples from the AI and formal methods communities.

Details

OriginalspracheEnglisch
TitelNASA Formal Methods
Redakteure/-innenKristin Yvonne Rozier, Swarat Chaudhuri
Herausgeber (Verlag)Springer, Cham
Seiten86-103
Seitenumfang18
ISBN (elektronisch)978-3-031-33170-1
ISBN (Print)978-3-031-33169-5
PublikationsstatusVeröffentlicht - 3 Juni 2023
Peer-Review-StatusJa

Publikationsreihe

ReiheLecture Notes in Computer Science
Band13903
ISSN0302-9743

Konferenz

TitelNASA Formal Methods Symposium 2023
KurztitelNFM 2023
Veranstaltungsnummer2023
Dauer16 - 18 Mai 2023
Webseite
BekanntheitsgradInternationale Veranstaltung
OrtUniversity of Clear Lake
StadtHouston
LandUSA/Vereinigte Staaten

Externe IDs

dblp conf/nfm/BaierDWK23
Scopus 85163947741
ORCID /0000-0002-5321-9343/work/142236785
ORCID /0000-0001-8047-4094/work/143075253

Schlagworte