Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning
Open accessThe DOI matches its Crossref record; 16 of the 16 references it cites were found in a registry or an index.
Abstract
Reinforcement learning (RL) methods usually treat reward functions as black boxes. As such, these methods must extensively interact with the environment in order to discover rewards and optimal policies. In most RL applications, however, users have to program the reward function and, hence, there is the opportunity to make the reward function visible – to show the reward function’s code to the RL agent so it can exploit the function’s internal structure to learn optimal policies in a more sample efficient manner. In this paper, we show how to accomplish this idea in two steps. First, we propose reward machines, a type of finite state machine that supports the specification of reward functions while exposing reward function structure. We then describe different methodologies to exploit this structure to support learning, including automated reward shaping, task decomposition, and counterfactual reasoning with off-policy learning. Experiments on tabular and continuous domains, across different tasks and RL agents, show the benefits of exploiting reward structure with respect to sample efficiency and the quality of resultant policies. Finally, by virtue of being a form of finite state machine, reward machines have the expressive power of a regular language and as such support loops, sequences and conditionals, as well as the expression of temporally extended properties typical of linear temporal logic and non-Markovian reward specification.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Human-level control through deep reinforcement learning
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al. (2015) · Nature · doi:10.1038/nature14236 · Cited by 30,357
Reinforcement Learning: An Introduction
Sutton, R. S., & Barto, A. G. (1998) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.1998.712192 · Cited by 27,225
Continuous control with deep reinforcement learning
Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., & Wierstra, D. (2015) · arXiv · doi:10.48550/arxiv.1509.02971 · Cited by 10,782
Deep Reinforcement Learning with Double Q-Learning
Van Hasselt, H., Guez, A., & Silver, D. (2016) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v30i1.10295 · Cited by 3,318
A survey of robot learning from demonstration
Argall, B. D., Chernova, S., Veloso, M., & Browning, B. (2009) · Robotics and Autonomous Systems · doi:10.1016/j.robot.2008.10.024 · Cited by 3,227
Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning
Sutton, R. S., Precup, D., & Singh, S. (1999) · Artificial Intelligence · doi:10.1016/s0004-3702(99)00052-1 · Cited by 3,119
CLEVR: A Diagnostic Dataset for Compositional Language and Elementary Visual Reasoning
Johnson, J., Hariharan, B., van der Maaten, L., Fei-Fei, L., Zitnick, C. L., & Girshick, R. (2017) · 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2017.215 · Cited by 1,781
Concrete Problems in AI Safety
Amodei, D., Olah, C., Steinhardt, J., Christiano, P., Schulman, J., & Mané, D. (2016) · arXiv · doi:10.48550/arxiv.1606.06565 · Cited by 1,314 · cited 1×
“More generally, the agent may find unintended ways to maximize reward (Amodei et al., 2016).”
BackgroundDeep reinforcement learning from human preferences
Christiano, P., Leike, J., Brown, T. B., Martic, M., Legg, S., & Amodei, D. (2017) · arXiv · doi:10.48550/arxiv.1706.03741 · Cited by 1,058 · cited 1×
“…are demonstrations (e.g., Ng & Russell, 2000; Abbeel & Ng, 2004; Ziebart et al., 2008; Fu et al., 2018), positive and negative feedback (e.g., Thomaz et al., 2006; Knox & Stone, 2008; MacGlashan et al., 2017), and trajectory preferences (e.g., Akrour et al., 2012; Christiano et al., 2017).”
BackgroundModular Multitask Reinforcement Learning with Policy Sketches
Andreas, J., Klein, D., & Levine, S. (2016) · arXiv · doi:10.48550/arxiv.1611.01796 · Cited by 274 · cited 2×
“The same idea was exploited by policy sketches (Andreas et al., 2017) but without the need for an external signal when a sub-goal is reached.”
BackgroundLTL and Beyond: Formal Languages for Reward Function Specification in Reinforcement Learning
Camacho, A., Toro Icarte, R., Klassen, T. Q., Valenzano, R., & McIlraith, S. A. (2019) · Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2019/840 · Cited by 157 · cited 9×
“This paper also covers an approach for automated reward shaping from a given reward machine that we later introduced (Camacho et al., 2019).”
BackgroundMethodInfluentialSelf-citationHadfield-Menell, D., Milli, S., Abbeel, P., Russell, S., & Dragan, A. (2017) · arXiv · doi:10.48550/arxiv.1711.02827 · Cited by 125
TAMER: Training an Agent Manually via Evaluative Reinforcement
Bradley Knox, W., & Stone, P. (2008) · 2008 7th IEEE International Conference on Development and Learning · doi:10.1109/devlrn.2008.4640845 · Cited by 117 · cited 1×
“…are demonstrations (e.g., Ng & Russell, 2000; Abbeel & Ng, 2004; Ziebart et al., 2008; Fu et al., 2018), positive and negative feedback (e.g., Thomaz et al., 2006; Knox & Stone, 2008; MacGlashan et al., 2017), and trajectory preferences (e.g., Akrour et al., 2012; Christiano et al., 2017).”
BackgroundAPRIL: Active Preference Learning-Based Reinforcement Learning
Akrour, R., Schoenauer, M., & Sebag, M. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-33486-3_8 · Cited by 95
Reward Machines for Cooperative Multi-Agent Reinforcement Learning
Neary, C., Xu, Z., Wu, B., & Topcu, U. (2021) · International Joint Conference on Autonomous Agents and Multiagent Systems · doi:10.65109/fzbc2933 · Cited by 28
Counterfactual Data Augmentation using Locally Factored Dynamics
Pitis, S., Creager, E., & Garg, A. (2020) · arXiv · doi:10.48550/arxiv.2007.02863 · Cited by 26
Cited by
LTL2Action: Generalizing LTL Instructions for Multi-Task RL
Vaezipoor, P., Li, A., Icarte, R. T., & McIlraith, S. (2021) · arXiv · doi:10.48550/arxiv.2102.06858 · Cited by 19
Self-citationFormal Methods for Autonomous Systems
Wongpiromsarn, T., Ghasemi, M., Cubuktepe, M., Bakirtzis, G., Carr, S., Karabag, M. O., Neary, C., Gohari, P., & Topcu, U. (2023) · Foundations and Trends® in Systems and Control · doi:10.1561/2600000029 · Cited by 17
Parsafar, P. (2025) · The Journal of Supercomputing · doi:10.1007/s11227-024-06510-1 · Cited by 9
Metadata
- Authors
- Toro Icarte, R., Klassen, T. Q., Valenzano, R., & McIlraith, S. A.
- Venue
- Journal of Artificial Intelligence Research
- Publisher
- AI Access Foundation
- Published
- 2022-01-11
- Volume
- 73
- Pages
- 173-208
- ISSN
- 1076-9757 (ISSN-L)
- OpenAlex
- W3092156990
- Cited by
- 188
- References
- 16
- FWCI
- 12.93
- Type
- journal article
- Language
- en
- Open access
- diamond
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.