Strategy Synthesis in Markov Decision Processes Under Limited Sampling Access
This work addresses strategy synthesis for agents in partially unknown environments, relevant to control theory, AI, and formal methods, but it appears incremental as it builds on existing gray-box MDP and reinforcement learning frameworks with specific algorithmic improvements.
The paper tackles the problem of synthesizing reward-maximizing strategies in gray-box Markov decision processes (MDPs) with limited sampling access, by developing a reinforcement learning algorithm that uses interval MDPs as an internal model and incorporates lower confidence bound exploration and action scoping to enhance learning efficiency.
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.