Standard Reinforcement Learning (RL) relies on the Markov property: the assumption that the current observation provides all the information necessary to choose an optimal action. In this view, the future is independent of the past, given the present.
However, most complex human goals are inherently non-Markovian. If a robot is told to "pick up the mail and then bring it to the office, but only if the door was previously unlocked," its optimal action at the office depends entirely on whether it visited the mailbox and whether the door was unlocked earlier. To a standard RL agent, the "state" of being at the office looks the same regardless of history, leading to a failure to learn.
The research direction across these papers describes a unified solution: State Augmentation. By enriching the agent's observation with a formal representation of task progress, we can transform history-dependent problems into standard Markovian ones.
The Product MDP: Markovianizing History
The core mechanism used by researchers like Alberto Camacho and Sheila A. McIlraith is the construction of a Product Markov Decision Process (Product MDP).
Instead of forcing the agent to learn a policy based solely on the environment state $S$, we define a task using a formal structure—typically a Finite State Automaton (FSA) or a Reward Machine (RM). This automaton acts as a "task monitor." As the agent moves through the environment, the monitor transitions between its own internal states ($U$) based on high-level events (e.g., "picked up key").
By defining the agent’s state as the pair $(S, U)$, the history is "collapsed" into the current value of $U$. As Maor Gaon and Ronen I. Brafman demonstrate in Reinforcement Learning with Non-Markovian Rewards, this transformation allows us to use off-the-shelf RL algorithms like Q-learning or PPO without any internal modifications to the learner itself. The agent doesn't need a "memory" (like an LSTM); it simply needs to know its current position on the "task map."
Formal Languages as Task Maps
To build these task maps, researchers use temporal logics to specify behavior. Michael L. Littman and colleagues introduced Geometric Linear Temporal Logic (GLTL) in Environment-Independent Task Specifications via GLTL to provide a robust way of defining these sequences.
Other frameworks focus on different facets of the problem:
- Safety and Constraints: Arun Raman uses automata to "supervise" agents, ensuring they obey non-Markovian action constraints even while learning.
- Fairness: Parand Alizadeh Alamdari applies this to fairness, augmenting states with "counterfactual memories" to ensure agents don't just achieve a fair outcome, but follow a fair process.
- Counting: Benjamin Rosman extends the idea to Counting Reward Automata, allowing agents to solve tasks that require tracking quantities (e.g., "collect exactly five samples") by adding counter variables to the state.
Inferring the Map from Experience
A major challenge is that we don't always have a pre-written logical formula for a task. In these cases, the research shifts toward Automata Synthesis.
The DeepSynth framework, developed by Hosein Hasanbeig and Alessandro Abate, uses SAT-based synthesis to automatically "distill" an agent's exploration data into a symbolic automaton. In Symbolic Task Inference in Deep Reinforcement Learning, they show that by inferring this structure, an agent can solve sparse-reward games like Montezuma’s Revenge up to 100 times faster.
Similarly, Rodrigo Toro Icarte explores Learning Reward Machines directly from experience, treating the automaton as a structured external memory that helps the agent navigate partially observable environments.
Why It Works: Stationary Objectives
Beyond just providing memory, state augmentation solves a subtle optimization problem: non-stationarity.
In Improving Intrinsic Exploration by Creating Stationary Objectives, Roger Creus Castanyer argues that many RL failures occur because the agent's goals change over time (e.g., a novelty bonus that disappears once a state is visited). By feeding the statistics of these rewards back into the state, the objective becomes stationary.
Whether the "history" being tracked is a logical sequence of sub-tasks, a safety constraint, or a count of items collected, the intuition remains the same: If the reward depends on the past, make the past part of the present. By offloading temporal reasoning to a formal symbolic structure, we allow the neural network to focus on what it does best—mapping the current (augmented) state to the best possible action.