Omega-Regular Objectives in Model-Free Reinforcement Learning

Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi, Ashutosh Trivedi, Ashutosh Trivedi*, Dominik Wojtczak

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

16 Citations (Scopus)
8 Downloads (Pure)

Abstract

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 publicationTools and Algorithms for the Construction and Analysis of Systems
Subtitle of host publication25th International Conference, TACAS 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Prague, Czech Republic, April 6–11, 2019, Proceedings
EditorsTomáš Vojnar, Lijun Zhang
Place of PublicationCham
PublisherSpringer
Pages395-412
VolumePart I
ISBN (Electronic)978-3-030-17462-0
ISBN (Print)978-3-030-17461-3
DOIs
Publication statusPublished - 2019
Event25th International Conference on Tools and Algorithms for the Construction and Analysis of Systems conference series, TACAS 2019 - Charles University, Prague, Czech Republic
Duration: 6 Apr 201911 Apr 2019
Conference number: 25

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11427
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th International Conference on Tools and Algorithms for the Construction and Analysis of Systems conference series, TACAS 2019
Abbreviated titleTACAS 2019
CountryCzech Republic
CityPrague
Period6/04/1911/04/19
Otherheld as part of the 22nd European Joint Conferences on Theory and Practice of Software, ETAPS 2019

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

Cite this