mlsanityData to 14 Oct 2026

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

arXiv 2603.27389 ↗First posted 28 Mar 2026cs.LG cs.AI stat.MLcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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.

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.

Builds on

16 of 23 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024Mitigating Partial Observability in Sequential Decision Processes via the Lambda Discrepancy10 Jul

Other references · 15

  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. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,258
  4. 2017Detecting causal associations in large nonlinear time series datasetscited by 244
  5. 2020Discovering contemporaneous and lagged causal relations in autocorrelated nonlinear time series datasetscited by 137
  6. 2019Generalization in Reinforcement Learning with Selective Noise Injection and Information Bottleneckcited by 101
  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. 2020Does the Markov Decision Process Fit the Data: Testing for the Markov Property in Sequential Decision Makingcited by 30
  11. 2022Action Noise in Off-Policy Deep Reinforcement Learning: Impact on Exploration and Performancecited by 22
  12. 2019Robust Reinforcement Learning in POMDPs with Incomplete and Noisy Observationscited by 10
3 more
  1. 2023Colored Noise in PPO: Improved Exploration and Performance through Correlated Action Samplingcited by 8
  2. 2024Benchmarking Deep Reinforcement Learning for Navigation in Denied Sensor Environmentscited by 4
  3. 2025Quantifying First-Order Markov Violations in Noisy Reinforcement Learning: A Causal Discovery Approachcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2022Structural Estimation of Markov Decision Processes in High-Dimensional State Space with Finite-Time Guarantees
  2. 2024Rethinking State Disentanglement in Causal Reinforcement Learning
  3. 2025Dynamic Sparsity: Challenging Common Sparsity Assumptions for Learning World Models in Robotic Reinforcement Learning Benchmarks
  4. 2025Model-Based Reinforcement Learning under Random Observation Delays
  5. 2026Safe Reinforcement Learning with Receding-Horizon Safety Critic and Differentiable Action Shields
  6. 2025Model-Based Exploration in Monitored Markov Decision Processes
  7. 2025Trajectory Entropy Reinforcement Learning for Robust Robot Motor Skill Learning
  8. 2021Proximal Reinforcement Learning: Efficient Off-Policy Evaluation in Partially Observed Markov Decision Processes