acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 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. Causal 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.

Primary area:
reinforcement learning
Keywords:
Causal DAG, Minimal Markovian State, End-to-End State Selection, Controlled Redundancy

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_udsjOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The authors use a longitudinal causal graph to construct a minimal state, then introduce MOSE to select useful observations from the available history. Synthetic environments and two Atari games evaluate the effect of this selection on learning

Critical strengths

The paper addresses a useful question: how much information should a learning algorithm retain? The observation that a minimal state can train poorly motivates a careful study of the tradeoff between state size and learning performance.

Critical weaknesses
  1. The minimality result conflicts with Definition 3.7. Consider independent X_t, rewards R_t=X_t, and isolated actions; an empty state is Markov and preserves every optimal action, yet Algorithm G.1 retains X_t. This contradicts Theorems 4.1 + 4.2.

  2. Causal MOSE receives an additional gradient update, and synthetic returns vary by orders of magnitude. Matched updates and normalized per-instance returns are needed to establish the contribution of state selection.

Questions for authors
  1. Suppose X_t is independent across time, R_t = X_t, and actions affect neither states nor rewards. Every action is equally optimal, so an empty state is Markov and preserves optimal actions under Definition 3.7. However, Algorithm G.1 retains X_t. How is this consistent with the claimed minimality?

  2. Do MOSE’s gains remain when all methods receive the same total number of gradient updates? Please also normalize returns within each task before averaging, so reward scale does not determine the aggregate result, and compare against a recurrent model given the same observation history.

Reviewer_JvPPOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to construct reinforcement-learning states from sequential observations when the current observation alone may not be Markovian. Given a known longitudinal causal DAG, the authors propose a backward procedure that retains historical variables already present in the next state, adds observed reward parents, and includes the past parents needed for the next state after accounting for within-time dependencies. Under the stated causal assumptions, they claim that the resulting state sequence is Markovian, preserves optimal actions, and cannot be reduced by deleting variables without losing validity for at least one model compatible with the graph. The main linear experiments cover orders 5 and 10 and episode horizons 25 and 30, with curves averaged over 18 instances. MOSE is also added to an R2D2-based agent on BattleZone and Krull; after 2 million environment interactions, the reported mean-score improvements are 25.8% and 34.7%, respectively. Causal MOSE is not evaluated on Atari because the causal graphs are unavailable. The central empirical message is that a compact state designed to preserve Markovian sufficiency need not be the easiest representation for a neural value function to learn, and that combining causal structure with learned retention of redundant history can improve performance.

Critical strengths
  1. The research question is worthwhile. Constructing usable RL states from graph structure and understanding the role of beneficial redundancy in statistical learning are both questions that merit explicit investigation. The gap between theoretically constructed states and neural-network learning performance is also a useful empirical observation.

  2. The experiments include structural comparisons. Figure 4 on p. 9 compares the window state, DAG state, MOSE, and Causal MOSE across 18 linear DGP instances. The appendix also includes gating comparisons and nonlinear experiments. Experiments with 2M interactions on two Atari tasks provide preliminary evidence that MOSE can be applied to recurrent representations.

Critical weaknesses
  1. The minimality and necessity claims do not follow from the paper's own definition of a valid state. The optimality requirement in Definition 3.7 on p. 5 is only argmaxₐQ*(s,a)=argmaxₐQ*(z,a). However, Theorem 4.1 requires all parents of the reward to be included in the state, and Theorem 4.2 on p. 6 claims that deleting any variable must invalidate the state for some compatible model. The proof on p. 19 uses equality of Q-values for all actions as its induction target, which is stronger than preserving optimal actions.
  2. The experimental gains cannot be clearly attributed to causal sufficiency or beneficial redundancy. The description on p. 8 and Algorithms G.3–G.4 on pp. 23–24 show that Causal MOSE adds a Q-network update using only the DAG state. However, the paper lacks a control with the same number of gradient steps and does not separate the effects of fixed gates and the additional update.
  3. Missing relevant reference. The related-work discussion omits Patil, Mahajan, and Precup (2024), “On learning history-based policies for controlling Markov decision processes,” which is directly relevant to the motivation for constructing history-based state representations. The authors should cite this work and clarify its relationship to the problem formulation and motivation of MOSE. Direct counterexample.
  4. The experiments demonstrate improved returns, but do not establish that the representations learned by MOSE satisfy the Markov property. The state-selection error rates in Figures H.4–H.5 measure agreement with the DAG-derived state rather than Markovianity, and Appendix H.5 presents asymptotic recovery only as a conjecture.
  5. The discussion in Sections 4.2 and 5.1—that historical redundancy can benefit learning even after a Markov-sufficient state has been constructed—is closely related to the earlier work Beyond Markov Assumption: Improving Sample Efficiency in MDPs by Historical Augmentation. Please discuss this connection and clarify the distinct contributions of MOSE/Causal-MOSE in causal state construction and history selection. https://openreview.net/forum?id=v9GwGQoOG5
Questions for authors
  1. Do the conclusions hold when the effects of fixed DAG gates and the additional Q-network update are separated under an equal gradient-update budget?
Reviewer_vYxhOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Online reinforcement learning typically assumes a Markov procedure but deciding which past observations to include is not a trivial task. Leaving out too much information can break the Markov property and including too many unnecessary inputs can reduce efficiency. This paper proposes a procedure for identifying a minimal set of historical observations from a known causal graph. Although this set is intended to contain enough information for optimal decisions, the authors find that RL agents sometimes learn better with additional inputs. To take advantage of this, the authors propose MOSE, an attention-based selector that learns which historical observations to keep and which to drop. The authors evaluate the methods in synthetic environments and on two Atari games.

Critical strengths
  1. Using causal structure to guide state selection is a strength of the paper. Causal-MOSE keeps the variables identified through the causal graph and learns which additional inputs to retain.

  2. The comparison with larger observation windows is another strength. Although the minimal causal state contains enough information for optimal decisions, the authors find that neural RL agents sometimes learn better with additional inputs. MOSE takes advantage of this observation by using an attention-based selector to learn which historical inputs to retain.

Critical weaknesses
  1. Causal-MOSE uses an extra training update based only on the graph-derived state. It is unclear whether the gains come from retaining causal variables, the extra update, or both.

  2. The paper does not compare MOSE with existing methods that learn which inputs to select. Such a comparison would help determine whether its attention-based selector performs better than other selection methods.

  3. The paper reports that additional inputs can improve performance but offers limited analysis of which redundant inputs help or why. Removing selected redundant inputs and measuring the change in performance would help explain what the selector has learned.

Questions for authors
  1. Could the authors test retaining the graph-derived variables and adding the DAG-only update separately, while keeping the number of optimization steps the same across methods?
  2. Which variables and time steps does the selector tend to keep? Beyond the false-positive and false-negative rates, are there patterns in these selection choices? Does removing selected inputs outside the graph-derived state hurt performance?
  3. In the LSTM experiments, the selected features do not directly correspond to observed variables. How can we interpret what MOSE keeps or drops?
  4. Could the authors add existing feature-selection or gating methods for comparison.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.