Omega-Regular Objectives in Model-Free Reinforcement Learning

Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi, Ashutosh Trivedi, University Liverpool

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Citations (Scopus)
104 Downloads (Pure)


We provide the first solution for model-free reinforcement learning of ω -regular objectives for Markov decision processes (MDPs). We present a 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. We compile ω -regular properties into limit-deterministic Büchi 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.
Original languageEnglish
Title of host publicationTACAS: International Conference on Tools and Algorithms for the Construction and Analysis of Systems
PublisherSpringer Lecture Notes in Computer Science (LNCS)
Publication statusPublished - 04 Apr 2019

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Omega-Regular Objectives in Model-Free Reinforcement Learning'. Together they form a unique fingerprint.

Cite this