# Prediction-Based Markov Violation Scores for Detecting Non-Markovian Observations in Reinforcement Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 16 of its 23 references that are in the map.
- First posted on arXiv 28 Mar 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [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)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Detecting causal associations in large nonlinear time series datasets](https://mlsanity.com/paper/1702.07007/) (2017)
- [Discovering contemporaneous and lagged causal relations in autocorrelated nonlinear time series datasets](https://mlsanity.com/paper/2003.03685/) (2020)
- [Generalization in Reinforcement Learning with Selective Noise Injection and Information Bottleneck](https://mlsanity.com/paper/1910.12911/) (2019)
- [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)
- [Does the Markov Decision Process Fit the Data: Testing for the Markov Property in Sequential Decision Making](https://mlsanity.com/paper/2002.01751/) (2020)
- [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)
- [Mitigating Partial Observability in Sequential Decision Processes via the Lambda Discrepancy](https://mlsanity.com/paper/2407.07333/) (2024)
- [Benchmarking Deep Reinforcement Learning for Navigation in Denied Sensor Environments](https://mlsanity.com/paper/2410.14616/) (2024)
- [Quantifying First-Order Markov Violations in Noisy Reinforcement Learning: A Causal Discovery Approach](https://mlsanity.com/paper/2503.00206/) (2025)

## Abstract (arXiv)

Reinforcement learning algorithms assume that observations satisfy the Markov property, yet real-world sensors frequently violate this assumption through correlated noise, latency, or partial observability. Standard performance metrics conflate Markov breakdowns with other sources of suboptimality, leaving practitioners without tools to detect such violations. This paper introduces a prediction-based Markov Violation Score (MVS) that quantifies non-Markovian structure in observation trajectories. A random forest first removes nonlinear Markov-compliant dynamics; ridge regression then tests whether historical observations reduce prediction error on the residuals beyond what the current observation provides. The resulting score is bounded in [0, 1] and requires no causal graph construction. Evaluation spans six environments (CartPole, Pendulum, Acrobot, HalfCheetah, Hopper, Walker2d), three algorithms (PPO, A2C, SAC), controlled AR(1) noise at six intensity levels, and 10 seeds per condition. In post-hoc detection, 7 of 16 environment-algorithm pairs, primarily high-dimensional locomotion tasks, show significant positive monotonicity between noise intensity and MVS (Spearman rho up to 0.78, confirmed under repeated-measures analysis); under training-time noise, 13 of 16 pairs exhibit statistically significant reward degradation. An inversion phenomenon is documented in low-dimensional environments where the random forest absorbs the noise signal, causing MVS to decrease as true violations grow, a failure mode analyzed in detail. A practical utility experiment demonstrates that MVS correctly identifies partial observability and guides architecture selection, fully recovering performance lost to non-Markovian observations. Source code to reproduce all results is available at https://github.com/NAVEENMN/Markovianes.