Non-Markovian Reinforcement Learning

Definition

Non-Markovian reinforcement learning studies decision problems where rewards, task validity, or constraints depend on the history of observations/events, not only the current environment state.

Why It Matters

Many tasks are order-sensitive: collect a key before opening a door, visit waypoints in sequence, avoid a forbidden prefix, or satisfy a temporal specification. Treating these as ordinary Markov rewards can erase the structure needed for exploration, explanation, and safety.

Formalism / Key Objects

• A common formalization is an NMRDP

$$M=(S,s_0,A,P,AP,L,R),$$

where L:S -> 2^{AP} labels states with propositions and R:(2^{AP})^* -> {0,1} maps traces to rewards.

• The trace reward can be encoded by a DFA

$$A=(Q,\Sigma ,\delta ,q_0,F),\Sigma =2^{AP}.$$

A trajectory is accepted if the induced automaton run ends in F.

• The product M x A makes the history-dependent reward Markovian by augmenting environment state with automaton state.
• A Reward Machines view makes the reward/task automaton explicit:

$$M=⟨U,P,\varphi ,r,u_0,U^A,U^R⟩,$$

where phi labels transitions with event formulas and r assigns rewards to progress in the automaton.

• In Toro Icarte et al.’s MDPRM formulation, augmenting environment state s with RM state u makes a history-dependent reward Markovian over S x U.

Connections

• Reward Machines provide a finite-state reward-language interface for non-Markovian rewards.
• Reward Machine Learning Methods records how CRM, HRM, and reward shaping exploit this augmented state structure.
• Automata Learning becomes important when the reward automaton is unknown or incomplete.
• Linear Temporal Logic and reward machines provide compact ways to specify temporal objectives.
• Safe Reinforcement Learning uses non-Markovian structure when safety depends on sequences, not isolated states.
• Alinejad2026 - Dynamic Automaton Refinement and Planning for Non-Markovian RL studies online refinement of the task automaton during policy learning.
• Furelos-Blanco2023 - Hierarchies of Reward Machines studies compositional reuse of reward machines through hierarchical calls.
• Compositional Reinforcement Learning handles a different decomposition axis: explicit subsystem entry/exit interfaces and probabilistic subtask success targets.
• Dynamic Automaton Refinement captures the confidence-triggered automaton update and product-MDP maintenance details.
• Hierarchical Reward Machine Semantics captures the HRM traversal and flat-equivalence formalism.

Common Confusions

• Non-Markovian reward does not mean the environment dynamics are necessarily non-Markovian; the history dependence may live only in the task/reward layer.
• Building a product MDP can recover Markov structure, but it may enlarge the state space substantially.
• Learning the policy and learning the automaton are separate problems even when they are interleaved.

Key Sources

• Toro Icarte2022 - Reward Machines
• Alinejad2026 - Dynamic Automaton Refinement and Planning for Non-Markovian RL
• Furelos-Blanco2023 - Hierarchies of Reward Machines