# Learning Symbolic Representations for Reinforcement Learning of Non-Markovian Behavior

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 24 references that are in the map.
- First posted on arXiv 8 Jan 2023.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Reinforcement Learning for Temporal Logic Control Synthesis with Probabilistic Satisfaction Guarantees](https://mlsanity.com/paper/1909.05304/) (2019)
- [Environment-Independent Task Specifications via GLTL](https://mlsanity.com/paper/1704.04341/) (2017)
- [Joint Inference of Reward Machines and Policies for Reinforcement Learning](https://mlsanity.com/paper/1909.05912/) (2019)
- [Logically-Constrained Reinforcement Learning](https://mlsanity.com/paper/1801.08099/) (2018)
- [Reinforcement Learning with Non-Markovian Rewards](https://mlsanity.com/paper/1912.02552/) (2019)
- [Learning Finite State Representations of Recurrent Policy Networks](https://mlsanity.com/paper/1811.12530/) (2018)
- [A Policy Search Method For Temporal Logic Specified Reinforcement Learning Tasks](https://mlsanity.com/paper/1709.09611/) (2017)
- [Interpretable Sequence Classification via Discrete Optimization](https://mlsanity.com/paper/2010.02819/) (2020)

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

- [Detecting Hidden Triggers: Mapping Non-Markov Reward Functions to Markov](https://mlsanity.com/paper/2401.11325/) (2024)
- [Ground-Compose-Reinforce: Grounding Language in Agentic Behaviours using Limited Data](https://mlsanity.com/paper/2507.10741/) (2025)
- [Learning Reward Machines in Cooperative Multi-Agent Tasks](https://mlsanity.com/paper/2303.14061/) (2023)
- [Unifying Agent Interaction and World Information for Multi-agent Coordination](https://mlsanity.com/paper/2509.25550/) (2025)

## Abstract (arXiv)

Many real-world reinforcement learning (RL) problems necessitate learning complex, temporally extended behavior that may only receive reward signal when the behavior is completed. If the reward-worthy behavior is known, it can be specified in terms of a non-Markovian reward function - a function that depends on aspects of the state-action history, rather than just the current state and action. Such reward functions yield sparse rewards, necessitating an inordinate number of experiences to find a policy that captures the reward-worthy pattern of behavior. Recent work has leveraged Knowledge Representation (KR) to provide a symbolic abstraction of aspects of the state that summarize reward-relevant properties of the state-action history and support learning a Markovian decomposition of the problem in terms of an automaton over the KR. Providing such a decomposition has been shown to vastly improve learning rates, especially when coupled with algorithms that exploit automaton structure. Nevertheless, such techniques rely on a priori knowledge of the KR. In this work, we explore how to automatically discover useful state abstractions that support learning automata over the state-action history. The result is an end-to-end algorithm that can learn optimal policies with significantly fewer environment samples than state-of-the-art RL on simple non-Markovian domains.