Omega-Regular Objectives in Model-Free Reinforcement Learning
Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi, Ashutosh Trivedi, Dominik Wojtczak.
TACAS, 2019
Paper (PDF) arXiv Publisher BibTeX
Abstract
We provide the first solution for model-free reinforcement learning of omega-regular objectives for Markov decision processes (MDPs). We present a constructive reduction from the almost-sure satisfaction of omega-regular objectives to an almost- sure reachability problem and extend this technique to learning how to control an unknown model so that the chance of satisfying the objective is maximized. A key feature of our technique is the compilation of omega-regular properties into limit- deterministic Buechi automata instead of the traditional Rabin automata; this choice sidesteps difficulties that have marred previous proposals. Our approach allows us to apply model-free, off-the-shelf reinforcement learning algorithms to compute optimal strategies from the observations of the MDP. We present an experimental evaluation of our technique on benchmark learning problems.