Standard reinforcement learning (RL) relies heavily on the Markov assumption: the next state of an environment depends solely on its current state and the immediate action taken. In the textbook formulation of a Markov Decision Process (MDP), time stands still while an agent selects an action, and the effects of that action manifest instantaneously.
In the real world, this assumption breaks down completely. Physical systems suffer from various forms of latency:
- Computation Delay: As noted by Pal et al., real-time systems do not pause for an agent to "think." By the time a neural network computes an action, the environment has already moved on.
- Actuator Lag: In heavy machinery or autonomous vehicles, commands take time to physically execute, creating a gap between control inputs and system responses (Lin et al.).
- Sensor and Communication Latency: Observations arriving from distant or underwater sensors are often stale, reflecting what happened several timesteps ago rather than what is happening now (Liotet et al.).
When these delays exist, a single snapshot observation is no longer a sufficient statistic for predicting the future. The system becomes non-Markovian, causing standard RL algorithms to fail or become highly unstable. History augmentation provides an elegant, model-free solution to this problem: by expanding the agent's state representation to include a structured window of recent observations and actions, we can mathematically recover the Markov property.
The Core Intuition: History as a State Proxy
How does adding past data fix a broken Markov property? The core insight is that the unobserved present is often a deterministic or highly predictable function of a known past combined with the intervening actions.
Instead of forcing a neural network to implicitly guess the hidden state of a delayed or partially observable environment, we explicitly construct a new, augmented state space. If the environment's true underlying state cannot be directly accessed, a finite sequence of recent interactions can serve as a perfect proxy. This transformation allows us to apply standard, computationally efficient MDP algorithms to environments that are inherently non-Markovian.
Compensating for Action and Execution Latency
Consider an environment with a fixed computation or execution delay. When an agent observes state $s_t$ and begins calculating an action, the action will not actually take effect until timestep $s_{t+1}$.
To reconcile this mismatch, Pal et al. propose augmenting the input state space with the action currently being executed by the agent. Because the ongoing action is already locked in and actively changing the environment during the computation window, treating it as a component of the current state restores a valid Markovian framework. For more complex robotic systems operating concurrently, Xiao et al. extend value-based architectures by incorporating concurrent execution data directly into the state, allowing the agent to reason about system delays as a known environmental feature rather than external noise.
Standard MDP: [ Observation ] --------------------------> (Action Selection)
|
Augmented MDP: [ Observation + Recent Action History ] ---------> (Action Selection)
When delays span multiple timesteps, a single action is not enough. Liotet et al. demonstrate that expanding the state representation to include a history buffer of all actions executed during the latency period provides the necessary context for the policy to account for pending commands.
This mechanism works because the agent's own action history bridges the temporal gap. If the controller knows the state of the world from $d$ steps ago, and it has a deterministic record of every action it has injected into the system since then, it possesses all the information required to project the system's trajectory forward to the present moment. This approach has been successfully applied to real-world challenges like urban traffic intersection control, where Salvato et al. utilize a buffer of pending actions to prevent gridlock caused by communication lag.
Resolving Partial Observability and Sensor Lag
History augmentation is equally powerful when dealing with partial observability (POMDPs) or delayed/missing sensor data. In an arbitrary POMDP, tracking the true state typically requires maintaining a complex probability distribution over all possible states (a belief state), which scales exponentially with the time horizon.
However, many real-world problems fall into a subclass known as $m$-step decodable POMDPs. As proven by Efroni et al., the hidden state of these systems can be completely recovered by simply concatenating a short, finite history of recent observation-action pairs into a single aggregate state. This technique, often implemented as frame-stacking, bypasses the need for explicit state reconstruction entirely.
[ Obs(t-2), Act(t-2) ] -> [ Obs(t-1), Act(t-1) ] -> [ Obs(t) ] ===> Combined Markov State
When observations are explicitly delayed or occasionally go missing, the agent can use a similar strategy to maintain a deterministic history. Chen et al. and Li et al. show that by expanding the state space to include the most recent confirmed observation along with the sequence of actions executed since that point, the agent can mathematically approximate the state transitions that occurred during the blind spot.
Similarly, Francois-Lavet et al. demonstrate that mapping a sequence of past observations and actions to a constructed state space effectively builds a fully observable MDP out of a partially observable process.
Why It Works: Practical Advantages Over Recurrent Models
While recurrent neural networks (like LSTMs or Transformers) can also track history, explicit history augmentation via state manipulation offers several distinct advantages:
- No Parametric Overhead: Instead of forcing a recurrent network to learn how to store and protect historical context in its latent weights, history augmentation uses simple, non-parametric structures like FIFO queues (Belardinelli et al.) or fixed temporal history buffers (Spinelli et al.). This makes the input representation lightweight and highly stable during training.
- Credit Assignment: By explicitly pairing delayed observations with the exact historical actions that caused them, the reward signal can be accurately mapped back to the responsible decisions. This prevents the performance collapse that occurs when standard RL agents misattribute the consequences of past actions to their current choices.
- Noise Filtering: In stochastic environments, a single snapshot cannot differentiate between a temporary measurement anomaly and a genuine environmental shift. A temporal history allows feedforward networks to identify trends, velocities, and patterns, enabling predictive rather than purely reactive control.
Key Foundational Work
Reinforcement Learning for Mixed Open-loop and Closed-loop Control (1996) — contributed 1 concept elements to this direction.
Information Set Generation in Partially Observable Games (2012) — contributed 1 concept elements to this direction.