In the ideal world of Reinforcement Learning (RL), an agent operates within a Markov Decision Process (MDP). This framework relies on the Markov property: the assumption that the current state provides all the information necessary to predict the future, making the history of past observations and actions irrelevant.
However, as Jangwon Kim and Soohee Han point out in Belief Projection-Based Reinforcement Learning for Environments with Delayed Feedback, real-world systems rarely satisfy this property. Whether due to communication delays in robotics or the need to satisfy complex temporal goals, the "best" action often depends on what happened several steps ago. To use standard RL tools in these non-Markovian settings, researchers employ state augmentation—the process of folding historical data into the current state representation to restore the Markov property.
The Mechanism of Augmentation
State augmentation works by expanding the agent's view of "now" to include relevant pieces of "then." The specific variables added depend on the source of the non-Markovian behavior:
- Feedback Delays: When there is a lag between taking an action and seeing its result, the agent must track "in-flight" actions. Baiming Chen and colleagues in Delay-Aware Multi-Agent Reinforcement Learning demonstrate this by augmenting the state with a buffer of pending actions, effectively turning a delayed system into a delay-free one.
- Risk and Safety: Standard RL maximizes the sum of rewards, but safety-critical tasks often require tracking a "cost budget." Hao Jiang and Tien Mai show in Solving Constrained Reinforcement Learning through Augmented State and Reward Penalties that by adding the "cost spent so far" to the state, agents can learn to stay within safety thresholds.
- Non-Additive Objectives: If a goal is to maximize the minimum reward (for safety) or the Sharpe ratio (for finance), the objective is no longer a simple sum. Yuting Tang and Masashi Sugiyama describe this in Recursive Reward Aggregation as adding running statistics to the state to make these complex targets solvable.
The Curse of Dimensionality
While augmentation theoretically solves the problem, it introduces a massive practical hurdle: the state space explosion. By adding history to the state, the number of possible configurations the agent must explore grows rapidly.
Craig Boutilier, Adam J. Grove, and Fahiem Bacchus noted as early as 1996 in Rewarding Behaviors that incorporating temporal logic into the state space leads to exponential growth. This "curse of dimensionality" makes traditional tabular RL computationally prohibitive.
In modern deep RL, this manifests as high sample complexity. Pierre Liotet and Marcello Restelli argue in Delayed Reinforcement Learning by Imitation that as the delay length increases, the augmented state becomes so high-dimensional that neural networks struggle to converge on an optimal policy within a reasonable number of training steps.
Scaling Challenges Across Domains
The difficulty of state augmentation scales differently depending on the task's requirements:
- Temporal Logic: For missions with complex constraints (e.g., "Visit A, then B, but only after C"), Derya Aksaray explains in Tractable Reinforcement Learning of Signal Temporal Logic Objectives that tracking the full history of states is often infeasible. Instead, researchers use compact "flags" to track progress, attempting to turn an exponential explosion into a manageable polynomial one.
- Submodularity: In tasks like exploration where rewards have diminishing returns, Manish Prajapat and Mojmir Mutny show in Submodular Reinforcement Learning that the state must be augmented with the entire trajectory of visited locations, making traditional methods computationally intractable.
- Risk-Awareness: In Planning and Learning in Risk-Aware Restless Multi-Arm Bandit Problem, Erick Delage and colleagues highlight that tracking accumulated rewards to manage risk (like Value at Risk) significantly increases overhead, limiting the ability to scale to many independent processes.
Beyond Brute-Force Augmentation
Because of the computational cost, recent work focuses on alternatives that avoid "bloating" the state space. Esther Derman and Gal Dalal prove in Acting in Delayed Environments with Non-Stationary Markov Policies that one can sometimes use non-stationary policies and forward models to predict the future rather than explicitly storing the past. Similarly, Simon Ramstedt and Christopher J. Pal propose Delay-Correcting Actor-Critic, which uses hindsight trajectory resampling to handle delays without requiring the neural network to process a massive, linear-growth action buffer.
In summary, state augmentation is the standard "bridge" that allows non-Markovian problems to be solved by Markovian algorithms. While it provides a mathematically sound path to optimality, its primary challenge is the trade-off between the completeness of the history and the tractability of the resulting search space.