Limit reachability for model-free reinforcement learning of ω-regular objectives
Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi, Ashutosh Trivedi, Dominik Wojtczak · 2019
We have recently solved the model-free reinforcement learning of ω-regular objectives for Markov decision processes. We outline our constructive reduction from the almost-sure satisfaction of ω-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 ω-regular properties into limit-deterministic Büchi automata, which sidesteps difficulties associated with the traditional Rabin automata. Our approach allows us to apply model-free, off-the-shelf reinforcement learning algorithms to compute optimal strategies from the observations of the Markov decision process.