The foundational bedrock of reinforcement learning (RL) is the Markov property: the assumption that the future depends only on the current state and action. This assumption allows us to write clean Bellman equations, design elegant algorithms, and guarantee convergence.
However, real-world applications frequently break this assumption, forcing agents to look backward into their history to make optimal decisions. Historical dependencies emerge from several distinct physical and mathematical constraints:
- Feedback and Execution Delays: In physical systems, there is often a lag between choosing an action and observing its effect, or between an event occurring and the agent receiving the observation Liotet et al..
- Non-Markovian Rewards: Tasks involving complex logic, temporal constraints, or diminishing returns mean that a reward depends on the entire sequence of past actions, not just the immediate transition Prajapat et al..
- Risk and Safety Constraints: Optimizing for risk metrics like Conditional Value-at-Risk (CVaR) or hitting specific performance targets requires tracking cumulative costs or rewards over time Chow et al..
The naive solution to handle a non-Markovian environment is state augmentation. If the environment's transitions or rewards depend on a history window of length $d$, we can redefine the state space by concatenating the current state with the history of the last $d$ actions and observations. While mathematically sound, this approach triggers a combinatorial explosion known as the curse of history.
The Mechanism of State Space Explosion
To understand why state augmentation fails, consider an agent operating in an environment with a base state space $\mathcal{S}$ and an action space $\mathcal{A}$. If there is an execution delay of $d$ steps, the agent cannot simply act on $s_t$; it must account for the queue of $d$ pending actions that have already been committed to but have not yet taken effect.
The augmented state space must therefore encompass every possible combination of the current state and the pending action sequence:
$$\mathcal{S}_{\text{augmented}} = \mathcal{S} \times \mathcal{A}^d$$
As the delay $d$ or history window grows, the size of this state space scales exponentially.
Without History: [ State s ] ---> Dim: |S|
With History (d=3): [ State s ] x [ Action a_1 ] x [ Action a_2 ] x [ Action a_3 ] ---> Dim: |S| * |A|^3
In tabular RL, this exponential growth makes exact solutions computationally intractable due to memory limits. In deep RL, it creates a massive dimensionality overhead. The agent must explore an exponentially larger space of state-action combinations, leading to extreme sample inefficiency and slow convergence Chen et al..
How the Curse Manifests Across Domains
The curse of history is a shared mathematical bottleneck appearing across seemingly unrelated RL subfields.
Delayed Environments
When actions have execution or observation delays, brute-force state expansion scales poorly Derman et al.. For multi-agent systems, Qiu notes that this explosion compounds further as the number of agents or the duration of actions increases, making long-horizon decentralized tasks prohibitive.
Risk-Sensitive Control
To optimize for tail-end risks or safety budgets, agents must track their accumulated costs. Osogami et al. show that risk-constrained problems are inherently time-inconsistent; a choice that seems optimal at the start of an episode may no longer seem optimal halfway through. Resolving this inconsistency via history tracking introduces a severe dimensionality explosion Wang et al.. Similarly, Xu et al. note that tracking cumulative rewards to meet specific goals scales proportionally with the range and precision of reward discretization, rendering high-precision solutions intractable.
History-Dependent Rewards
In tasks with submodular rewards (where exploration yields diminishing returns) or logical specifications, the state must be augmented with the entire trajectory of visited locations or past events Prajapat et al., Rens et al.. This causes the state space to grow exponentially with the length of the temporal horizon.
Bypassing the Explosion: Structural Solutions
To make these problems tractable, recent research focuses on bypassing explicit state augmentation by exploiting the underlying structure of decision processes.
Forward Models and Non-Stationary Policies
Instead of expanding the state space with a queue of pending actions, Derman et al. and Valensi et al. demonstrate that optimal control under delays can be achieved using non-stationary Markov policies combined with a forward model. By using the forward model to predict future states through the delay queue, the agent can make optimal decisions while keeping the state representation compact.
Exploiting Underlying MDP Structure
Rather than treating the history-augmented space as a generic large MDP, Chen et al. prove that one can achieve near-optimal regret bounds that depend strictly on the original system's size, completely avoiding the exponential sample-efficiency penalty of the curse of history.
Decoupling via Imitation and Auxiliary Tasks
Liotet et al. decouple the problem by training an expert in an undelayed environment and using imitation learning to teach the delayed agent. This bypasses direct reinforcement learning over the exploded state space entirely. Similarly, Wu et al. use short-delay auxiliary tasks to bootstrap learning for long-delay environments, improving sample efficiency.
Automata and Predictive Representations
For history-dependent objectives, instead of storing raw trajectories, researchers compress history into minimal finite representations. This can be achieved using automata learning to bridge the gap between non-Markovian history and standard Markovian solvers Ronca et al., or by leveraging predictive representations that focus on future outcomes rather than past paths Rafols et al..