# Active Finite Reward Automaton Inference and Reinforcement Learning Using Queries and Counterexamples

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2020.

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

- [Learning Reward Machines: A Study in Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2112.09477/) (2021)
- [Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learning](https://mlsanity.com/paper/2107.04633/) (2021)
- [Reward Machines for Deep RL in Noisy and Uncertain Environments](https://mlsanity.com/paper/2406.00120/) (2024)
- [Noisy Symbolic Abstractions for Deep RL: A case study with Reward Machines](https://mlsanity.com/paper/2211.10902/) (2022)
- [Learning Task Automata for Reinforcement Learning using Hidden Markov Models](https://mlsanity.com/paper/2208.11838/) (2022)
- [Neural Reward Machines](https://mlsanity.com/paper/2408.08677/) (2024)
- [Hierarchies of Reward Machines](https://mlsanity.com/paper/2205.15752/) (2022)
- [Reinforcement Learning under Partial Observability Guided by Learned Environment Models](https://mlsanity.com/paper/2206.11708/) (2022)
- [Multi-Agent Reinforcement Learning with a Hierarchy of Reward Machines](https://mlsanity.com/paper/2403.07005/) (2024)
- [Learning Reward Machines from Partially Observed Policies](https://mlsanity.com/paper/2502.03762/) (2025)
- [Reinforcement Learning with Temporal-Logic-Based Causal Diagrams](https://mlsanity.com/paper/2306.13732/) (2023)
- [Bayesian Inverse Reinforcement Learning for Non-Markovian Rewards](https://mlsanity.com/paper/2406.13991/) (2024)
- [Learning Hidden Subgoals under Temporal Ordering Constraints in Reinforcement Learning](https://mlsanity.com/paper/2411.01425/) (2024)
- [Fully Learnable Neural Reward Machines](https://mlsanity.com/paper/2509.19017/) (2025)
- [Reinforcement Learning With Reward Machines in Stochastic Games](https://mlsanity.com/paper/2305.17372/) (2023)
- [Learning Environment Models with Continuous Stochastic Dynamics](https://mlsanity.com/paper/2306.17204/) (2023)
- [Learning Quantitative Automata Modulo Theories](https://mlsanity.com/paper/2411.10601/) (2024)
- [Average Reward Reinforcement Learning for Omega-Regular and Mean-Payoff Objectives](https://mlsanity.com/paper/2505.15693/) (2025)
- [Inferring Reward Machines and Transition Machines from Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2508.01947/) (2025)
- [Physics-Informed Reward Machines](https://mlsanity.com/paper/2508.14093/) (2025)
- [DeepDFA: Injecting Temporal Logic in Deep Learning for Sequential Subsymbolic Applications](https://mlsanity.com/paper/2602.03486/) (2026)
- [Active Reward Machine Inference From Raw State Trajectories](https://mlsanity.com/paper/2604.07480/) (2026)
- [Temporal-Causal Inference for Reinforcement Learning via Automata Learning](https://mlsanity.com/paper/2609.07461/) (2026)

## Abstract (arXiv)

Despite the fact that deep reinforcement learning (RL) has surpassed human-level performances in various tasks, it still has several fundamental challenges. First, most RL methods require intensive data from the exploration of the environment to achieve satisfactory performance. Second, the use of neural networks in RL renders it hard to interpret the internals of the system in a way that humans can understand. To address these two challenges, we propose a framework that enables an RL agent to reason over its exploration process and distill high-level knowledge for effectively guiding its future explorations. Specifically, we propose a novel RL algorithm that learns high-level knowledge in the form of a finite reward automaton by using the L* learning algorithm. We prove that in episodic RL, a finite reward automaton can express any non-Markovian bounded reward functions with finitely many reward values and approximate any non-Markovian bounded reward function (with infinitely many reward values) with arbitrary precision. We also provide a lower bound for the episode length such that the proposed RL approach almost surely converges to an optimal policy in the limit. We test this approach on two RL environments with non-Markovian reward functions, choosing a variety of tasks with increasing complexity for each environment. We compare our algorithm with the state-of-the-art RL algorithms for non-Markovian reward functions, such as Joint Inference of Reward machines and Policies for RL (JIRP), Learning Reward Machine (LRM), and Proximal Policy Optimization (PPO2). Our results show that our algorithm converges to an optimal policy faster than other baseline methods.