mlsanityData to 14 Oct 2026

Quantifying First-Order Markov Violations in Noisy Reinforcement Learning: A Causal Discovery Approach

arXiv 2503.00206 ↗First posted 28 Feb 2025cs.LG cs.AI stat.MLcited by 1

On the map: Deep reinforcement learning methods → Deep RL algorithms and representations

Abstract (arXiv)

Reinforcement learning (RL) methods frequently assume that each new observation completely reflects the environment's state, thereby guaranteeing Markovian (one-step) transitions. In practice, partial observability or sensor/actuator noise often invalidates this assumption. This paper proposes a systematic methodology for detecting such violations, combining a partial correlation-based causal discovery process (PCMCI) with a novel Markov Violation score (MVS). The MVS measures multi-step dependencies that emerge when noise or incomplete state information disrupts the Markov property. Classic control tasks (CartPole, Pendulum, Acrobot) serve as examples to illustrate how targeted noise and dimension omissions affect both RL performance and measured Markov consistency. Surprisingly, even substantial observation noise sometimes fails to induce strong multi-lag dependencies in certain domains (e.g., Acrobot). In contrast, dimension-dropping investigations show that excluding some state variables (e.g., angular velocities in CartPole and Pendulum) significantly reduces returns and increases MVS, while removing other dimensions has minimal impact. These findings emphasize the importance of locating and safeguarding the most causally essential dimensions in order to preserve effective single-step learning. By integrating partial correlation tests with RL performance outcomes, the proposed approach precisely identifies when and where the Markov assumption is violated. This framework offers a principled mechanism for developing robust policies, informing representation learning, and addressing partial observability in real-world RL scenarios. All code and experimental logs are accessible for reproducibility (https://github.com/ucsb/markovianess).

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods. Builds on 19 of its 25 references that are in the map. First posted on arXiv 28 Feb 2025.

Builds on

19 of 25 references.

References · 19

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  3. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  4. 2020Reinforcement Learning with Augmented Datacited by 468
  5. 2019Causal Discovery with Reinforcement Learningcited by 145
  6. 2020Discovering contemporaneous and lagged causal relations in autocorrelated nonlinear time series datasetscited by 137
  7. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  8. 2022Robust Reinforcement Learning using Offline Datacited by 96
  9. 2022Partially Observable Markov Decision Processes in Robotics: A Surveycited by 86
  10. 2018Reinforcement Learning with Perturbed Rewardscited by 79
  11. 2023A Survey on Causal Reinforcement Learningcited by 45
  12. 2020Can Increasing Input Dimensionality Improve Deep Reinforcement Learning?cited by 37
7 more
  1. 2020Does the Markov Decision Process Fit the Data: Testing for the Markov Property in Sequential Decision Makingcited by 30
  2. 2021MURAL: Meta-Learning Uncertainty-Aware Rewards for Outcome-Driven Reinforcement Learningcited by 24
  3. 2022Action Noise in Off-Policy Deep Reinforcement Learning: Impact on Exploration and Performancecited by 22
  4. 2019Robust Reinforcement Learning in POMDPs with Incomplete and Noisy Observationscited by 10
  5. 2023Colored Noise in PPO: Improved Exploration and Performance through Correlated Action Samplingcited by 8
  6. 2024Two-way Deconfounder for Off-policy Evaluation in Causal Reinforcement Learningcited by 5
  7. 2024Benchmarking Deep Reinforcement Learning for Navigation in Denied Sensor Environmentscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Prediction-Based Markov Violation Scores for Detecting Non-Markovian Observations in Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Rethinking State Disentanglement in Causal Reinforcement Learning
  2. 2024Mitigating Partial Observability in Sequential Decision Processes via the Lambda Discrepancy
  3. 2025Model-Based Reinforcement Learning Under Confounding
  4. 2025Learning Causal States Under Partial Observability and Perturbation
  5. 2025Dynamic Sparsity: Challenging Common Sparsity Assumptions for Learning World Models in Robotic Reinforcement Learning Benchmarks
  6. 2025Learning Nonlinear Causal Reductions to Explain Reinforcement Learning Policies
  7. 2023Can Active Sampling Reduce Causal Confusion in Offline Reinforcement Learning?
  8. 2026From Causal Graphs to Markovian States: Multi-Order State Exposure for Deep RL