DeepSynth: Automata synthesis for automatic task segmentation in deep reinforcement learning

Conference item

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 humaninterpretable 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.

Authors: Hasanbeig, M; Yogananda Jeppu, N; Abate, A; Melham, TF; Kroening, D

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for the Advancement of Artificial Intelligence
• Journal: Proceedings of the AAAI Conference on Artificial Intelligence
• Volume: 35
• Issue: 9
• Pages: 7647-7656
• Publication date: 2021-05-18
• Acceptance date: 2020-12-02
• Event title: 35th AAAI Conference on Artificial Intelligence: AAAI 2021
• Event location: Virtual event
• Event website: https://aaai.org/Conferences/AAAI-21/
• Event start date: 2021-02-02
• Event end date: 2021-02-09
• Language: English
• Keywords: temporal planning; FFR; deep neural network algorithms; reinforcement learning; sequential decision making