State Space Augmentation for Non-Markovian Decision Processes

48 concepts36 papers1 proposal

The bedrock of reinforcement learning (RL) is the Markov assumption: the belief that the future depends only on the current state, not on the history of how the agent arrived there. This assumption enables the use of Bellman equations, dynamic programming, and standard value iteration.

However, many real-world objectives are inherently non-Markovian. Consider an autonomous vehicle tasked with minimizing the variance of its travel time, a financial agent trying to hit a specific target profit, or a robot executing a complex sequence of instructions like "pick up the key before opening the door." In all these cases, the optimal action depends heavily on past events.

Instead of abandoning standard Markovian tools to solve these problems, a powerful and elegant alternative exists: State Space Augmentation. By expanding the environment's physical state space with a compact summary of historical context, we can transform a non-Markovian decision process into a standard, solvable Markov Decision Process (MDP).

The Core Mechanism: Restoring Memorylessness

To understand why state space augmentation works, consider a decision process where the reward or transition dynamics depend on the entire history of states and actions, $H_t = (s_0, a_0, s_1, a_1, \dots, s_t)$.

Directly planning over histories causes the state space to grow exponentially with time, leading to the curse of dimensionality. State space augmentation circumvents this by finding a sufficient statistic or auxiliary variable $z_t = f(H_t)$ that captures all necessary historical information. We then construct an augmented state:

$$\bar{s}_t = (s_t, z_t)$$

For this transformation to restore the Markov property, the auxiliary variable must update in a memoryless fashion: $z_{t+1} = g(z_t, s_t, a_t)$. If this condition is met, the transitions between augmented states depend solely on the current augmented state and action:

$$P(\bar{s}_{t+1} \mid \bar{s}_t, a_t) = P(s_{t+1} \mid s_t, a_t) \cdot P(z_{t+1} \mid z_t, s_t, a_t)$$

As early work by Boutilier et al. and Gretton et al. demonstrated, an optimal policy derived over this expanded state space is mathematically equivalent to the optimal policy of the original non-Markovian problem. This allows practitioners to deploy off-the-shelf RL and planning algorithms without altering their internal optimization mechanics.

Tracking Cumulative Rewards for Risk and Goals

One major failure mode of standard MDPs is their inherent risk-neutrality; they maximize expected cumulative rewards but ignore the distribution of those rewards. True risk-sensitive objectives—such as minimizing variance or maximizing the probability of hitting a performance target—are non-Markovian because the value of a future reward depends on how much reward has already been accumulated.

To resolve this, Mannor et al. and Xu et al. proposed augmenting the state space with a running tally of the cumulative reward earned during an episode.

Standard State:  [ Physical State (s) ] -> Cannot evaluate risk or targets
Augmented State: [ Physical State (s) , Cumulative Reward (∑R) ] -> Restores Markov property

When the agent knows exactly how much reward it has accumulated relative to its target, its remaining strategy can be optimized using standard dynamic programming. This foundational concept underpins modern risk-sensitive frameworks:

  • Distributional RL: Chen et al. leverage reward-augmented states to propagate probability distributions through environments under general function approximation.
  • Continuous Discretization: To maintain computational feasibility when tracking continuous rewards, algorithms proposed by Bastani et al. discretize the accumulated reward component while preserving provable regret bounds.
  • Inverse RL: When learning from human demonstrations, Lazzati et al. utilize reward augmentation to explicitly model and infer the non-Markovian risk attitudes of human operators.

Automata and Product MDPs for Temporal Logic

When an agent's task involves complex, temporally extended constraints (e.g., "visit A, then B, and never touch C"), the history is best summarized using formal languages like Linear Temporal Logic (LTL). Here, state space augmentation takes the form of a Product MDP.

Instead of tracking raw history, the temporal specification is compiled into a finite-state machine or a "Reward Machine," as detailed by Toro Icarte et al. and Brafman et al.. The environment state space is crossed with the internal states of this automaton.

Environment State Space (S)  ×  Automaton States (Q)  =  Product MDP Space (S × Q)

As the agent moves through the physical world, it triggers transitions within the automaton. The current automaton state acts as an explicit symbolic memory of task progress.

This framework has been widely adopted to scale deep reinforcement learning to long-horizon tasks. For instance, the DeepSynth framework (Hasanbeig et al.; Hasanbeig et al.; Hasanbeig et al.) automatically synthesizes these automata from exploration data, transforming sparse, non-Markovian environments into structured sub-tasks.

By embedding the automaton state directly into the agent's observation space, standard model-free algorithms can solve sequential objectives without requiring internal recurrent memory architectures. This mechanism has been successfully extended to multi-agent stochastic games (Hu et al.), inverse reinforcement learning (Memarian et al.), and planning under uncertain human specifications (Shah et al.).

Auxiliary Variables for Complex Dynamics

The utility of state augmentation extends beyond tracking rewards and automata; it can stabilize any decision process where the objective depends on trajectory-wide statistics or changing environment properties.

Balancing Diverse Time Horizons

When an agent must balance multiple objectives with different discount factors, simply summing the rewards leads to time-inconsistent behavior. To resolve this, Pitis proved that multi-objective consistency requires non-Markovian rewards. By augmenting the state space with auxiliary variables that track the accumulated relative discount of each goal, standard RL algorithms can maintain consistent planning across diverse time horizons.

Tracking Trajectory Extremes

In safety-critical applications, goals often depend on the worst penalty or best reward encountered so far. Sharpless et al. address this by expanding the state space with variables that track historical performance extrema, allowing Hamilton-Jacobi-Bellman formulations to handle non-Markovian safety boundaries.

Stabilizing Intrinsic Exploration

Intrinsic rewards (like novelty bonuses) change constantly as an agent explores, creating a non-stationary objective that confuses standard RL solvers. Castanyer demonstrates that augmenting the agent's state with the underlying statistics of these intrinsic rewards transforms a non-stationary exploration task into a stationary MDP, significantly boosting exploration efficiency.

Why the Idea Works

State space augmentation works because it shifts the burden of memory from the learning algorithm to the state representation.

Instead of forcing an RL agent to learn complex temporal dependencies using recurrent neural networks (which can suffer from vanishing gradients and training instability), augmentation structures the state space so that the immediate transition and reward functions become memoryless again. Whether through tracking cumulative rewards, synthesizing finite-state automata, or maintaining auxiliary statistics, enriching the state space ensures that the classical Bellman optimality equations remain perfectly valid.

Key Foundational Work

Rewarding Behaviors (1996) — contributed 3 concept elements to this direction.
Mean-Variance Optimization in Markov Decision Processes (2011) — contributed 1 concept elements to this direction.
Probabilistic Goal Markov Decision Processes (2011) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_state_space_augmentation_reward_augmente_b25b473c,
  title = {state space augmentation (reward-augmented state representation)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/state-space-augmentation-reward-augmented-state-representation/rdr_b25b473cb75747e08d587c804cd33868},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_state_space_augmentation_reward_augmente_b25b473c_v1,
  title = {state space augmentation (reward-augmented state representation)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/state-space-augmentation-reward-augmented-state-representation/rdr_b25b473cb75747e08d587c804cd33868/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake