# Pushdown Reward Machines for Reinforcement Learning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Interpretable and logic-guided RL, one of 15 directions in Deep reinforcement learning methods.
- Builds on 6 of its 24 references that are in the map.
- First posted on arXiv 9 Aug 2025.

## Placed in

- Deep reinforcement learning methods / [Interpretable and logic-guided RL](https://mlsanity.com/deeprl/interpretable-and-logic-guided-rl/)

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [A Composable Specification Language for Reinforcement Learning Tasks](https://mlsanity.com/paper/2008.09293/) (2020)
- [Learning Reward Machines: A Study in Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2112.09477/) (2021)
- [Counting Reward Automata: Sample Efficient Reinforcement Learning Through the Exploitation of Reward Function Structure](https://mlsanity.com/paper/2312.11364/) (2023)
- [FORM: Learning Expressive and Transferable First-Order Logic Reward Machines](https://mlsanity.com/paper/2501.00364/) (2024)

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

- [ARM-FM: Automated Reward Machines via Foundation Models for Compositional Reinforcement Learning](https://mlsanity.com/paper/2510.14176/) (2025)
- [Expressive Reward Synthesis with the Runtime Monitoring Language](https://mlsanity.com/paper/2510.16185/) (2025)
- [Reinforcement Learning with Symbolic Reward Machines](https://mlsanity.com/paper/2603.03068/) (2026)
- [Exact Distinguishability in Non-Markovian Decision Processes](https://mlsanity.com/paper/2610.01527/) (2026)

## Abstract (arXiv)

Reward machines (RMs) are automata structures that encode (non-Markovian) reward functions for reinforcement learning (RL). RMs can reward any behaviour representable in regular languages and, when paired with RL algorithms that exploit RM structure, have been shown to significantly improve sample efficiency in many domains. In this work, we present pushdown reward machines (pdRMs), an extension of reward machines based on deterministic pushdown automata. pdRMs can recognise and reward temporally extended behaviours representable in deterministic context-free languages, making them more expressive than reward machines. We introduce two variants of pdRM-based policies, one which has access to the entire stack of the pdRM, and one which can only access the top k symbols (for a given constant k) of the stack. We propose a procedure to check when the two kinds of policies (for a given environment, pdRM, and constant k) achieve the same optimal state values. We then provide theoretical results establishing the expressive power of pdRMs, and space complexity results for the proposed learning problems. Lastly, we propose an approach for off-policy RL algorithms that exploits counterfactual experiences with pdRMs. We conclude by providing experimental results showing how agents can be trained to perform tasks representable in deterministic context-free languages using pdRMs.