DeepSynth swMATH ID: 43034 Software Authors: Hasanbeig, Mohammadhosein; Jeppu, Natasha Yogananda; Abate, Alessandro; Melham, Tom; Kroening, Daniel Description: DeepSynth: Automata Synthesis for Automatic Task Segmentation in Deep Reinforcement Learning. This paper proposes DeepSynth, a method for effective training of deep Reinforcement Learning (RL) agents when the reward is sparse and non-Markovian, but at the same time progress towards the reward requires achieving an unknown sequence of high-level objectives. Our method employs a novel algorithm for synthesis of compact automata to uncover this sequential structure automatically. We synthesise a human-interpretable automaton from trace data collected by exploring the environment. The state space of the environment is then enriched with the synthesised automaton so that the generation of a control policy by deep RL is guided by the discovered structure encoded in the automaton. The proposed approach is able to cope with both high-dimensional, low-level features and unknown sparse non-Markovian rewards. We have evaluated DeepSynth’s performance in a set of experiments that includes the Atari game Montezuma’s Revenge. Compared to existing approaches, we obtain a reduction of two orders of magnitude in the number of iterations required for policy synthesis, and also a significant improvement in scalability. Homepage: https://arxiv.org/abs/1911.10244 Source Code: https://github.com/grockious/deepsynth Dependencies: Python Related Software: Tabu search; Baselines; Adam; Gurobi; Uppaal Stratego; StocHy; AMYTISS; MoChiBA; PRISM; FAUST2; Lang2LTL; OpenAI Gym; AlphaZero; REINFORCEjs Cited in: 4 Documents all top 5 Cited by 13 Authors 2 Klassen, Toryn Qwyllyn 2 McIlraith, Sheila A. 2 Toro Icarte, Rodrigo 2 Valenzano, Richard 1 Abate, Alessandro 1 Castro, Margarita Paz 1 den Hengst, Floris 1 François-Lavet, Vincent 1 Hasanbeig, Hosein 1 Hoogendoorn, Mark 1 Kröning, Daniel 1 van Harmelen, Frank 1 Waldie, Ethan Cited in 3 Serials 2 Artificial Intelligence 1 Machine Learning 1 The Journal of Artificial Intelligence Research (JAIR) Cited in 2 Fields 4 Computer science (68-XX) 1 Operations research, mathematical programming (90-XX) Citations by Year