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

arXiv: https://arxiv.org/abs/2503.00206 · HTML: https://mlsanity.com/paper/2503.00206/

## Key facts

- Cited by 1 papers 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.

## Placed in

- Deep reinforcement learning methods / [Deep RL algorithms and representations](https://mlsanity.com/deeprl/deep-rl-algorithms-and-representations/)

## Builds on (most cited first, 19 of 19)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Reinforcement Learning with Augmented Data](https://mlsanity.com/paper/2004.14990/) (2020)
- [Causal Discovery with Reinforcement Learning](https://mlsanity.com/paper/1906.04477/) (2019)
- [Discovering contemporaneous and lagged causal relations in autocorrelated nonlinear time series datasets](https://mlsanity.com/paper/2003.03685/) (2020)
- [When Is Partially Observable Reinforcement Learning Not Scary?](https://mlsanity.com/paper/2204.08967/) (2022)
- [Robust Reinforcement Learning using Offline Data](https://mlsanity.com/paper/2208.05129/) (2022)
- [Partially Observable Markov Decision Processes in Robotics: A Survey](https://mlsanity.com/paper/2209.10342/) (2022)
- [Reinforcement Learning with Perturbed Rewards](https://mlsanity.com/paper/1810.01032/) (2018)
- [A Survey on Causal Reinforcement Learning](https://mlsanity.com/paper/2302.05209/) (2023)
- [Can Increasing Input Dimensionality Improve Deep Reinforcement Learning?](https://mlsanity.com/paper/2003.01629/) (2020)
- [Does the Markov Decision Process Fit the Data: Testing for the Markov Property in Sequential Decision Making](https://mlsanity.com/paper/2002.01751/) (2020)
- [MURAL: Meta-Learning Uncertainty-Aware Rewards for Outcome-Driven Reinforcement Learning](https://mlsanity.com/paper/2107.07184/) (2021)
- [Action Noise in Off-Policy Deep Reinforcement Learning: Impact on Exploration and Performance](https://mlsanity.com/paper/2206.03787/) (2022)
- [Robust Reinforcement Learning in POMDPs with Incomplete and Noisy Observations](https://mlsanity.com/paper/1902.05795/) (2019)
- [Colored Noise in PPO: Improved Exploration and Performance through Correlated Action Sampling](https://mlsanity.com/paper/2312.11091/) (2023)
- [Two-way Deconfounder for Off-policy Evaluation in Causal Reinforcement Learning](https://mlsanity.com/paper/2412.05783/) (2024)
- [Benchmarking Deep Reinforcement Learning for Navigation in Denied Sensor Environments](https://mlsanity.com/paper/2410.14616/) (2024)

## Built on by (most cited first, 1 of 1)

- [Prediction-Based Markov Violation Scores for Detecting Non-Markovian Observations in Reinforcement Learning](https://mlsanity.com/paper/2603.27389/) (2026)

## 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).