From Causal Graphs to Markovian States: Multi-Order State Exposure for Deep RL

summary

The gist

The gist: MOSE consistently outperforms both minimal state construction and single-window policies on common benchmarks and synthetic datasets, establishing that controlled redundancy is necessary to

In short

The paper addresses how to create Markovian states from time-series causal graphs for reinforcement learning. It proposes MOSE, a method that exposes a single Q-function to multiple state orders simultaneously (1 through W), and Causal-MOSE, which combines this with a minimal state construction. Results show that controlled redundancy—combining the minimal Markovian core with MOSE—outperforms both methods alone, proving that simply using the minimal state is insufficient for deep RL performance.

Key concepts

Minimal Markovian State Construction: This process maps a known causal graph of observed variables to a set of states that strictly satisfy the Markov property. A state is considered minimal if removing any variable from it either breaks the Markov property or reduces the optimal value achievable in some consistent environment. This construction provides a provably valid, yet as small as possible, state representation.
Multi-Order State Exposure (MOSE): Instead of feeding only the minimal state to a deep learning model, MOSE feeds all orders of states from 1 up to W simultaneously. These lower-order inputs act like structured noise that helps reshape the learning process. This technique encourages the network to discover a more useful state representation by providing richer, albeit non-Markovian, historical context.
Controlled Redundancy: This is the core finding: combining the provably minimal Markovian state with MOSE allows for controlled redundancy. The minimal part ensures structural validity (the Markov property), while MOSE allows the model flexibility to incorporate extra variables that might be statistically useful for better value estimation, leading to superior overall performance.

Terminology used across episodes

Reinforcement Learning (RL) — explained in 25 episodes
Sample Complexity — explained in 18 episodes
Federated Learning — explained in 17 episodes
Retrieval-Augmented Generation (RAG) — explained in 16 episodes
Interpretability — explained in 15 episodes
Quantum Fisher Information (QFI) — explained in 15 episodes

This episode discusses

The paper

From Causal Graphs to Markovian States: Multi-Order State Exposure for Deep RL · Read on arXiv

Jiamin Xu, Jacqueline Maasch, Kyra Gan

Cornell Tech

Online reinforcement learning (RL) relies on the Markov property for guaranteed performance, but real-world applications often lack well-defined states given raw observed variables. While causal RL has attracted growing interest, existing work typically assumes Markovian states are provided and uses causality only to accelerate learning. This leaves a fundamental gap: given a longitudinal causal graph over observed variables, how does one construct MDP states that provably satisfy the Markov property? We provide a procedure that constructs a provably minimal such state. In deep RL, the minimal representation alone empirically fails to improve performance, indicating that neural networks cannot automatically exploit Markovian minimality. We therefore propose MOSE (Multi-Order State Exposure), which exposes a single shared Q-function to history-based state constructions of orders 1 through W simultaneously. An attention-based selection layer scores the dimensions of this combined input by their estimated relevance to value-function estimation and selects the high-scoring ones. Causal MOSE further constrains the selection layer to retain every variable of the minimal state, guaranteeing sufficiency while leaving the model free to admit useful redundancy. MOSE consistently outperforms both the minimal state construction and single-window policies on common benchmarks and synthetic datasets. Including the minimal representation alongside MOSE can further improve performance. Our results establish a core principle for causal deep RL: minimal sufficiency is not enough. Controlled redundancy gives the model flexibility to learn its state representation end-to-end. Causal state information provides structural guidance that can make this learning more efficient.

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "From Causal Graphs to Markovian States".

Jane: The gist: MOSE consistently outperforms both minimal state construction and single-window policies on common benchmarks and synthetic datasets,

Tom: First, who's behind it and why it matters.

Paper summary: Tom: So, we're talking about this paper, "From Causal Graphs to Markovian States: Multi-Order State Exposure for Deep RL". It starts by pointing out that online reinforcement learning needs the Markov property for guaranteed performance, but raw observed variables often don't provide well-defined states.

Jane: Right. The paper addresses the gap here: given a longitudinal causal graph over these observations, how do you construct MDP states that provably satisfy the Markov property?

Tom: They provide a procedure to construct this provably minimal state representation, and they also observe that just using the minimal representation alone doesn't improve performance in deep RL.

Lu: The authors address this by proposing MOSE, which feeds multi-order historical state constructions into the same Q-function simultaneously. This is a heuristic method for constructing states that doesn't require you to know the causal graph beforehand.

Jane: They use lower-order non-Markovian inputs as structured noise to reshape the loss landscape, creating a gradient from suboptimal to optimal representations. Then they use an attention layer to select dimensions based on relevance for value function estimation.

Meng: From an engineering standpoint, that sounds like it adds complexity to the training pipeline because you're feeding multiple historical windows at once into one Q-function. What does this add in terms of computational cost?

Tom: The paper notes that Causal-MOSE, which includes the minimal state with MOSE, performs as well or better than just MOSE, suggesting controlled redundancy is key.

Jane: So the core claim is that combining a principled Markovian core with this mechanism allows the agent to discover useful variables when they are beneficial for learning.

Lu: The resulting representation can serve as a foundation upon which existing causal RL techniques could be applied to potentially improve performance further.

Tom: Basically, they established a direct mapping from longitudinal causal graphs to minimal Markovian states and then proposed MOSE to make it usable in deep RL by letting the network figure out the best state structure.

Jane: It moves the focus from assuming you have a valid MDP already to asking whether the state we construct can actually improve learning.

Meng: If this works on synthetic data, that’s one thing. We need to know if it holds up when we move to real traffic where things get messy and noisy quickly.

Tom: That's the next hurdle they have to clear, Meng, but the paper points out that their results are based on synthetic data generating processes like Linear ANM and PNL models.

Conclusion: Tom: So looking at this paper, "From Causal Graphs to Markovian States: Multi-Order State Exposure for Deep RL", it seems the main achievement is formalizing the connection between causal graphs and MDP states.

Jane: They proved a graphical criterion for constructing a valid state space given a time series causal DAG, and they also gave you an algorithm to extract that minimal representation directly from the full time graph.

Lu: And then they propose MOSE as the practical way to make this usable in deep RL by exposing the network to multi-order inputs simultaneously.

Tom: The implication is that we shouldn't just rely on using the minimal state alone; you need that extra mechanism of controlled redundancy so the model can learn its own useful state representation.

Jane: So, instead of just picking a fixed set of variables, you give the network enough information to explore which ones are truly useful for learning in its specific context.

Lu: This gives us a way to build on existing causal RL techniques by providing a principled foundation for how to structure the state space from raw observations.

Tom: It’s about moving from just having a fixed representation to letting the learning process discover the right representation through that structured exposure of information.

More episodes

← Home