# Reinforcement Learning with Non-Markovian Rewards

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

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- Placed in Latent dynamics models and model-based RL, one of 11 directions in World models.
- Builds on 0 of its 25 references that are in the map.
- First posted on arXiv 5 Dec 2019.

## Placed in

- World models / [Latent dynamics models and model-based RL](https://mlsanity.com/wm/latent-dynamics-models-and-model-based-rl/)

## Built on by (most cited first, 30 of 45)

- [A Survey on Interpretable Reinforcement Learning](https://mlsanity.com/paper/2112.13112/) (2021)
- [Universal Trading for Order Execution with Oracle Policy Distillation](https://mlsanity.com/paper/2103.10860/) (2021)
- [Learning Reward Machines: A Study in Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2112.09477/) (2021)
- [Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methods](https://mlsanity.com/paper/2407.09905/) (2024)
- [A First-Occupancy Representation for Reinforcement Learning](https://mlsanity.com/paper/2109.13863/) (2021)
- [Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learning](https://mlsanity.com/paper/2107.04633/) (2021)
- [Markov Abstractions for PAC Reinforcement Learning in Non-Markov Decision Processes](https://mlsanity.com/paper/2205.01053/) (2022)
- [Noisy Symbolic Abstractions for Deep RL: A case study with Reward Machines](https://mlsanity.com/paper/2211.10902/) (2022)
- [Automata Learning meets Shielding](https://mlsanity.com/paper/2212.01838/) (2022)
- [Consistent Aggregation of Objectives with Diverse Time Preferences Requires Non-Markovian Rewards](https://mlsanity.com/paper/2310.00435/) (2023)
- [DeepDFA: Automata Learning through Neural Probabilistic Relaxations](https://mlsanity.com/paper/2408.08622/) (2024)
- [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)
- [Reinforcement Learning with Stochastic Reward Machines](https://mlsanity.com/paper/2510.14837/) (2025)
- [Model-Free Reinforcement Learning for Symbolic Automata-encoded Objectives](https://mlsanity.com/paper/2202.02404/) (2022)
- [Non-Markovian Reinforcement Learning using Fractional Dynamics](https://mlsanity.com/paper/2107.13790/) (2021)
- [Detecting Hidden Triggers: Mapping Non-Markov Reward Functions to Markov](https://mlsanity.com/paper/2401.11325/) (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)
- [Learning Symbolic Representations for Reinforcement Learning of Non-Markovian Behavior](https://mlsanity.com/paper/2301.02952/) (2023)
- [FORM: Learning Expressive and Transferable First-Order Logic Reward Machines](https://mlsanity.com/paper/2501.00364/) (2024)
- [Reinforcement Learning with Formal Performance Metrics for Quadcopter Attitude Control under Non-nominal Contexts](https://mlsanity.com/paper/2107.12942/) (2021)
- [A State Representation for Diminishing Rewards](https://mlsanity.com/paper/2309.03710/) (2023)
- [Multi-Agent Reinforcement Learning with a Hierarchy of Reward Machines](https://mlsanity.com/paper/2403.07005/) (2024)
- [Learning Reward Machines in Cooperative Multi-Agent Tasks](https://mlsanity.com/paper/2303.14061/) (2023)
- [Omega-Regular Reward Machines](https://mlsanity.com/paper/2308.07469/) (2023)
- [AIGB: Generative Auto-bidding via Conditional Diffusion Modeling](https://mlsanity.com/paper/2405.16141/) (2024)
- [Automata Cascades: Expressivity and Sample Complexity](https://mlsanity.com/paper/2211.14028/) (2022)
- [Constructing Non-Markovian Decision Process via History Aggregator](https://mlsanity.com/paper/2506.24026/) (2025)
- [Synthetic POMDPs to Challenge Memory-Augmented RL: Memory Demand Structure Modeling](https://mlsanity.com/paper/2508.04282/) (2025)

## Abstract (arXiv)

The standard RL world model is that of a Markov Decision Process (MDP). A basic premise of MDPs is that the rewards depend on the last state and action only. Yet, many real-world rewards are non-Markovian. For example, a reward for bringing coffee only if requested earlier and not yet served, is non-Markovian if the state only records current requests and deliveries. Past work considered the problem of modeling and solving MDPs with non-Markovian rewards (NMR), but we know of no principled approaches for RL with NMR. Here, we address the problem of policy learning from experience with such rewards. We describe and evaluate empirically four combinations of the classical RL algorithm Q-learning and R-max with automata learning algorithms to obtain new RL algorithms for domains with NMR. We also prove that some of these variants converge to an optimal policy in the limit.