2019 · 152 citations · 19 references
ComputingComputer ScienceAlgorithmsArtificial IntelligenceMachine LearningPolicy LearningReinforcement LearningReinforcement Learning FoundationsValue FunctionsDeep Reinforcement LearningExposed StructureLearning From Sparse RewardsNormal Form RepresentationQ-learningReinforcement Learning TheorySample EfficiencySparse Reward Learning
In Reinforcement Learning (RL), an agent is guided by the rewards it receives from the reward function. Unfortunately, it may take many interactions with the environment to learn from sparse rewards, and it can be challenging to specify reward functions that reflect complex reward-worthy behavior. We propose using reward machines (RMs), which are automata-based representations that expose reward function structure, as a normal form representation for reward functions. We show how specifications of reward in various formal languages, including LTL and other regular languages, can be automatically translated into RMs, easing the burden of complex reward function specification. We then show how the exposed structure of the reward function can be exploited by tailored q-learning algorithms and automated reward shaping techniques in order to improve the sample efficiency of reinforcement learning methods. Experiments show that these RM-tailored techniques significantly outperform state-of-the-art (deep) RL algorithms, solving problems that otherwise cannot reasonably be solved by existing approaches.
19
Human-level control through deep reinforcement learning
Volodymyr Mnih, Koray Kavukcuoglu, David Silver et al. · Nature · 2015 · 30K citations
Reinforcement Learning: An Introduction
Jeffrey D. Johnson, Jinghong Li, Zengshi Chen · Neurocomputing · 2000 · 8.7K citations
Introduction to automata theory, languages, and computation
Computer Languages · 1980 · 6.9K citations
Deep Reinforcement Learning with Double Q-Learning
Hado van Hasselt, Arthur Guez, David Silver · 2016 · 6K citations · Full text
Tom Schaul, John Quan, Ioannis Antonoglou et al. · arXiv (Cornell University) · 2015 · 2K citations · Full text