# DeepSynth: Automata Synthesis for Automatic Task Segmentation in Deep Reinforcement Learning

arXiv: https://arxiv.org/abs/1911.10244 · HTML: https://mlsanity.com/paper/1911.10244/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Nov 2019.

## Built on by (most cited first, 9 of 9)

- [Modular Deep Reinforcement Learning for Continuous Motion Planning with Temporal Logic](https://mlsanity.com/paper/2102.12855/) (2021)
- [Overcoming Exploration: Deep Reinforcement Learning for Continuous Control in Cluttered Environments from Temporal Logic Specifications](https://mlsanity.com/paper/2201.12231/) (2022)
- [LCRL: Certified Policy Synthesis via Logically-Constrained Reinforcement Learning](https://mlsanity.com/paper/2209.10341/) (2022)
- [Program Synthesis Guided Reinforcement Learning for Partially Observed Environments](https://mlsanity.com/paper/2102.11137/) (2021)
- [Mission-driven Exploration for Accelerated Deep Reinforcement Learning with Temporal Logic Task Specifications](https://mlsanity.com/paper/2311.17059/) (2023)
- [System III: Learning with Domain Knowledge for Safety Constraints](https://mlsanity.com/paper/2304.11593/) (2023)
- [Safeguarded Progress in Reinforcement Learning: Safe Bayesian Exploration for Control Policy Synthesis](https://mlsanity.com/paper/2312.11314/) (2023)
- [Progressive Safeguards for Safe and Model-Agnostic Reinforcement Learning](https://mlsanity.com/paper/2410.24096/) (2024)
- [Structured Representation Learning with Locally Linear Embeddings and Adaptive Feature Fusion](https://mlsanity.com/paper/2606.18469/) (2026)

## Abstract (arXiv)

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.