# Counting Reward Automata: Sample Efficient Reinforcement Learning Through the Exploitation of Reward Function Structure

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 27 references that are in the map.
- First posted on arXiv 18 Dec 2023.

## Builds on (most cited first, 11 of 11)

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Diversity is All You Need: Learning Skills without a Reward Function](https://mlsanity.com/paper/1802.06070/) (2018)
- [QT-Opt: Scalable Deep Reinforcement Learning for Vision-Based Robotic Manipulation](https://mlsanity.com/paper/1806.10293/) (2018)
- [Agent57: Outperforming the Atari Human Benchmark](https://mlsanity.com/paper/2003.13350/) (2020)
- [Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation](https://mlsanity.com/paper/1604.06057/) (2016)
- [The Next Decade in AI: Four Steps Towards Robust Artificial Intelligence](https://mlsanity.com/paper/2002.06177/) (2020)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [RUDDER: Return Decomposition for Delayed Rewards](https://mlsanity.com/paper/1806.07857/) (2018)
- [Reinforcement Learning With Temporal Logic Rewards](https://mlsanity.com/paper/1612.03471/) (2016)
- [Environment-Independent Task Specifications via GLTL](https://mlsanity.com/paper/1704.04341/) (2017)
- [The Option Keyboard: Combining Skills in Reinforcement Learning](https://mlsanity.com/paper/2106.13105/) (2021)

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

- [FORM: Learning Expressive and Transferable First-Order Logic Reward Machines](https://mlsanity.com/paper/2501.00364/) (2024)
- [Pushdown Reward Machines for Reinforcement Learning](https://mlsanity.com/paper/2508.06894/) (2025)
- [Beyond Sliding Windows: Learning to Manage Memory in Non-Markovian Environments](https://mlsanity.com/paper/2512.19154/) (2025)
- [Expressive Reward Synthesis with the Runtime Monitoring Language](https://mlsanity.com/paper/2510.16185/) (2025)
- [Expressive Temporal Specifications for Reward Monitoring](https://mlsanity.com/paper/2511.12808/) (2025)
- [Reinforcement Learning with Symbolic Reward Machines](https://mlsanity.com/paper/2603.03068/) (2026)

## Abstract (arXiv)

We present counting reward automata-a finite state machine variant capable of modelling any reward function expressible as a formal language. Unlike previous approaches, which are limited to the expression of tasks as regular languages, our framework allows for tasks described by unrestricted grammars. We prove that an agent equipped with such an abstract machine is able to solve a larger set of tasks than those utilising current approaches. We show that this increase in expressive power does not come at the cost of increased automaton complexity. A selection of learning algorithms are presented which exploit automaton structure to improve sample efficiency. We show that the state machines required in our formulation can be specified from natural language task descriptions using large language models. Empirical results demonstrate that our method outperforms competing approaches in terms of sample efficiency, automaton complexity, and task completion.