Standard reinforcement learning (RL) typically relies on the Markov property: the assumption that the optimal action and the expected reward depend only on the current state and action. However, real-world tasks are rarely so self-contained. As Rens et al. illustrate, you don't receive the "reward" of a cake simply for putting a pan in the oven; the reward is contingent on a specific sequence of prior events, such as cracking eggs and mixing flour. When rewards depend on the past, the environment becomes non-Markovian, and standard agents often fail because they cannot distinguish between identical current observations that require different actions based on history.
The Challenge of Temporal Ambiguity
In non-Markovian settings, the agent faces a fundamental ambiguity. For example, in high-precision robotic tasks like peg insertion, Drolet et al. note that a single sensor snapshot cannot tell a robot if it is currently succeeding or encountering a mechanical jam; it must account for the history of interactions to resolve the state. Similarly, Jang et al. argue that manipulation tasks often involve occlusions where the agent must remember where an object was previously located to act correctly now.
Without a mechanism to track this history, the agent's policy is "memoryless." As Wen et al. explain, memoryless policies cannot distinguish between different stages of a long-term task, leading to sub-optimal behavior or total failure in multi-step sequences.
Restoring Markovianity via Reward Machines
To solve these problems, researchers have moved toward structured representations that explicitly track task progress. A central mechanism in this area is the Reward Machine (RM). As proposed by Toro Icarte et al., a Reward Machine is a finite-state automaton that represents the reward function. By augmenting the agent's state with the current state of the machine, the problem is effectively "Markovianized"—the history is compressed into a single discrete state.
Camacho et al. describe RMs as a "lingua franca" for RL, allowing complex tasks specified in formal logics to be converted into a format the agent can exploit. This structure provides several benefits:
- Decomposition: It breaks a long-term goal into manageable sub-tasks.
- Sample Efficiency: Agents can use the machine's transitions to understand why they received a reward, rather than treating the reward as a black box.
- Coordination: In multi-agent systems, Ardon et al. show that learning these machines allows agents to coordinate on sequential tasks without human-engineered structures.
Formal Logic as a Specification Tool
If Reward Machines provide the mechanism for memory, formal logics provide the language for defining it. Linear Temporal Logic (LTL) and Signal Temporal Logic (STL) allow researchers to specify complex requirements like "visit A, then B, but never enter C."
Aksaray et al. demonstrate that by remodeling a system as a history-dependent "$\tau$-MDP," agents can learn to satisfy STL specifications that require tracking history over a specific time horizon. Furthermore, Lennon et al. show that using LTL as "side information" helps agents overcome partial information gaps, allowing them to capture the true intent of human demonstrations that a simple state-based reward would miss.
Learning the Hidden Logic
A significant hurdle is that the underlying "rules" of a task are not always known upfront. Recent work focuses on inferring these non-Markovian structures from data.
- Active Learning: Xu et al. introduced the AFRAI-RL framework, where agents "interrogate" their environment to discover the underlying Finite Reward Automata.
- Iterative Inference: The JIRP framework, developed by Xu et al., allows agents to iteratively infer Reward Machines while simultaneously learning a policy, solving tasks where rewards are both sparse and non-Markovian.
- Symbolic Generalization: To handle environments with varying numbers of objects, Ardon et al. proposed First-Order Reward Machines (FORMs), which use first-order logic to create compact, human-readable task descriptions that transfer to new scenarios.
Sequence Modeling and Amortized Context
While automata provide discrete memory, neural architectures offer a continuous alternative for capturing history. Weaver et al. utilize Transformers to capture the non-Markovian stylistic patterns in human racing gameplay. To address the computational cost of long histories, Jang et al. (ContextVLA) propose compressing multi-frame video history into a single "context token," allowing robotic models to leverage temporal dependencies efficiently. Similarly, Jia et al. suggest that selective state-space models like Mamba can capture long-range temporal relationships more effectively than standard Transformers in data-scarce robotic tasks.
By integrating these memory mechanisms—whether through discrete automata, formal logic, or continuous sequence models—RL agents can move beyond the "here and now," enabling them to solve the complex, multi-stage challenges inherent in the real world.