Strategy Synthesis in Markov Decision Processes Under Limited Sampling Access

Christel BaierChristel Baier, Clemens DubslaffClemens Dubslaff, Patrick WienhöftPatrick Wienhöft, Stefan J. KiebelStefan J. Kiebel

DOI Link

Christel Baier, Clemens Dubslaff, Patrick Wienhöft, Stefan J. Kiebel
Strategy Synthesis in Markov Decision Processes Under Limited Sampling Access
In Rozier, Kristin Yvonne and Chaudhuri, Swarat, eds., NASA Formal Methods, 86--103, 2023. Springer Nature Switzerland

Details
Bibtex

KurzfassungAbstract
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.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

@inproceedings{BDWK2023,
  author    = {Christel Baier and Clemens Dubslaff and Patrick Wienh{\"{o}}ft
               and Stefan J. Kiebel},
  title     = {Strategy Synthesis in Markov Decision Processes Under Limited
               Sampling Access},
  editor    = {Rozier and Kristin Yvonne\n               and Chaudhuri and
               Swarat},
  booktitle = {NASA Formal Methods},
  publisher = {Springer Nature Switzerland},
  year      = {2023},
  pages     = {86--103},
  doi       = {10.1007/978-3-031-33170-1_6}
}