Omega-Regular Objectives in Model-Free Reinforcement Learning



Hahn, EM, Perez, Mateo, Schewe, S, Somenzi, Fabio, Trivedi, Ashutosh and Wojtczak, DK
(2019) Omega-Regular Objectives in Model-Free Reinforcement Learning. In: 25th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), 2019-4-6 - 2019-4-11, Prague, Czech Republic.

Access the full-text of this item by clicking on the Open Access link.
[thumbnail of tacas.pdf] Text
tacas.pdf - Author Accepted Manuscript

Download (427kB)

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 bjectives 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¨uchi 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.

Item Type: Conference or Workshop Item (Unspecified)
Uncontrolled Keywords: 46 Information and Computing Sciences, 4602 Artificial Intelligence, 4611 Machine Learning
Depositing User: Symplectic Admin
Date Deposited: 20 Feb 2019 14:58
Last Modified: 20 Jun 2024 20:24
DOI: 10.1007/978-3-030-17462-0_27
Open Access URL: https://link.springer.com/chapter/10.1007%2F978-3-...
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3033069