mlsanityData to 7 Oct 2026

Reinforcement Learning with Non-Markovian Rewards

arXiv 1912.02552 ↗First posted 5 Dec 2019cs.AIcited by 45

On the map: World models → Latent dynamics models and model-based RL

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.

Key facts. Cited by 45 papers in the map (data through 7 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.

Builds on

0 of 25 references.

No references here yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 8; 2023: 7; 2024: 9; 2025: 8; 2026: 6.

45 papers.

Sort:

By area:

  1. 2021A Survey on Interpretable Reinforcement Learningcited by 70
  2. 2021Universal Trading for Order Execution with Oracle Policy Distillationcited by 29
  3. 2021Learning Reward Machines: A Study in Partially Observable Reinforcement Learningcited by 16
  4. 2024Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methodscited by 15
  5. 2021A First-Occupancy Representation for Reinforcement Learningcited by 14
  6. 2021Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learningcited by 13
  7. 2022Markov Abstractions for PAC Reinforcement Learning in Non-Markov Decision Processescited by 10
  8. 2022Noisy Symbolic Abstractions for Deep RL: A case study with Reward Machinescited by 10
  9. 2022Automata Learning meets Shieldingcited by 9
  10. 2023Consistent Aggregation of Objectives with Diverse Time Preferences Requires Non-Markovian Rewardscited by 8
  11. 2024DeepDFA: Automata Learning through Neural Probabilistic Relaxationscited by 8
  12. 2022Learning Task Automata for Reinforcement Learning using Hidden Markov Modelscited by 7
33 more
  1. 2025Reinforcement Learning with Stochastic Reward Machinescited by 7
  2. 2022Model-Free Reinforcement Learning for Symbolic Automata-encoded Objectivescited by 6
  3. 2024Neural Reward Machinescited by 6
  4. 2021Non-Markovian Reinforcement Learning using Fractional Dynamicscited by 5
  5. 2024Detecting Hidden Triggers: Mapping Non-Markov Reward Functions to Markovcited by 5
  6. 2022Hierarchies of Reward Machinescited by 4
  7. 2022Reinforcement Learning under Partial Observability Guided by Learned Environment Modelscited by 4
  8. 2023Learning Symbolic Representations for Reinforcement Learning of Non-Markovian Behaviorcited by 4
  9. 2024FORM: Learning Expressive and Transferable First-Order Logic Reward Machinescited by 4
  10. 2023A State Representation for Diminishing Rewardscited by 3
  11. 2024Multi-Agent Reinforcement Learning with a Hierarchy of Reward Machinescited by 3
  12. 2021Reinforcement Learning with Formal Performance Metrics for Quadcopter Attitude Control under Non-nominal Contextscited by 2
  13. 2023Learning Reward Machines in Cooperative Multi-Agent Taskscited by 2
  14. 2023Omega-Regular Reward Machinescited by 2
  15. 2022Automata Cascades: Expressivity and Sample Complexitycited by 1
  16. 2024AIGB: Generative Auto-bidding via Conditional Diffusion Modelingcited by 1
  17. 2025Constructing Non-Markovian Decision Process via History Aggregatorcited by 1
  18. 2025Synthetic POMDPs to Challenge Memory-Augmented RL: Memory Demand Structure Modelingcited by 1
  19. 2025Fully Learnable Neural Reward Machinescited by 1
  20. 2025Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processescited by 1
  21. 2023Policy Dispersion in Non-Markovian Environmentcited by 0
  22. 2023Learning Environment Models with Continuous Stochastic Dynamicscited by 0
  23. 2024Reinforcement Learning from Bagged Rewardcited by 0
  24. 2024Learning Quantitative Automata Modulo Theoriescited by 0
  25. 2025Average Reward Reinforcement Learning for Omega-Regular and Mean-Payoff Objectivescited by 0
  26. 2025Inferring Reward Machines and Transition Machines from Partially Observable Markov Decision Processescited by 0
  27. 2025Lattice Annotated Temporal (LAT) Logic for Non-Markovian Reasoningcited by 0
  28. 2026DeepDFA: Injecting Temporal Logic in Deep Learning for Sequential Subsymbolic Applicationscited by 0
  29. 2026Ergodicity in reinforcement learningcited by 0
  30. 2026Agentic-Kube: A Graph-Enhanced Multi-Agent Reinforcement Learning Framework for Multi-Objective Kubernetes Schedulingcited by 0
  31. 2026SatQNet: Satellite-assisted Quantum Network Entanglement Routing Using Directed Line Graph Neural Networkscited by 0
  32. 2026Smart Transportation Without Neurons -- Fair Metro Network Expansion with Tabular Reinforcement Learningcited by 0
  33. 2026Theoretical Foundations of max@k Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2020Learning Non-Markovian Reward Models in MDPs
  2. 2025Statistical and Algorithmic Foundations of Reinforcement Learning
  3. 2024Beyond Simple Sum of Delayed Rewards: Non-Markovian Reward Modeling for Reinforcement Learning
  4. 2025RLAF: Reinforcement Learning from Automaton Feedback
  5. 2024Tractable Offline Learning of Regular Decision Processes
  6. 2020Online Learning of Non-Markovian Reward Models
  7. 2023Is RLHF More Difficult than Standard RL?
  8. 2021Reinforcement Learning in Reward-Mixing MDPs