Paper deep dive

Diagnosing Non-Markovian Observations in Reinforcement Learning via Prediction-Based Violation Scoring

Naveen Mysore

Year: 2026Venue: arXiv preprintArea: cs.LGType: PreprintEmbeddings: 43

Intelligence

Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 94%

Last extracted: 3/31/2026, 2:04:05 AM

Summary

The paper introduces a prediction-based scoring method to diagnose non-Markovian observations in reinforcement learning. By using a two-stage pipeline—a random forest to remove Markov-compliant dynamics followed by ridge regression to test for historical predictive signals—the method quantifies Markov violations. The approach is evaluated across six environments and three algorithms, demonstrating that while it effectively detects violations in high-dimensional tasks, it faces an 'inversion phenomenon' in low-dimensional settings where the random forest absorbs the noise signal.

Entities (5)

Reinforcement Learning · field · 99%Markov Violation Score · method · 98%AR(1) Noise · phenomenon · 95%Random Forest · algorithm · 95%Ridge Regression · algorithm · 95%

Relation Signals (3)

Markov Violation Score → quantifies → Non-Markovian structure

confidence 95% · This paper introduces a prediction-based scoring method that quantifies non-Markovian structure in observation trajectories.

Random Forest → removes → Markov-compliant dynamics

confidence 92% · A random forest first removes nonlinear Markov-compliant dynamics

AR(1) Noise → induces → Markov violation

confidence 90% · AR(1) noise induces dependence at all lags... introducing temporal dependence that grows with α.

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract: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 diagnostic tools for such violations. This paper introduces a prediction-based scoring method 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 the violation score (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 the score to decrease as true violations grow, a failure mode analyzed in detail. A practical utility experiment demonstrates that the proposed score correctly identifies partial observability and guides architecture selection, fully recovering performance lost to non-Markovian observations. Source code to reproduce all results is provided at this https URL.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

42,538 characters extracted from source content.

Expand or collapse full text

Diagnosing Non-Markovian Observations in Reinforcement Learning via Prediction-Based Violation Scoring Naveen Mysore 1,2 nmysore@ucsb.edu 1 Department of Electrical and Computer Engineering, University of California, Santa Barbara, USA 2 Dyssonance.ai Abstract Reinforcement learning algorithms assume that observations satisfy the Markov property, yet real- world sensors frequently violate this assumption through correlated noise, latency, or partial observabil- ity. Standard performance metrics conflate Markov breakdowns with other sources of suboptimality, leaving practitioners without diagnostic tools for such violations. This paper introduces a prediction- based scoring method that quantifies non-Markovian structure in observation trajectories. A random forest first removes nonlinear Markov-compliant dynamics; ridge regression then tests whether histori- cal 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 the violation score (Spearman ρ up to 0.78, confirmed under repeated-measures analysis); under training-time noise, 13 of 16 pairs exhibit sta- tistically significant reward degradation. An inversion phenomenon is documented in low-dimensional environments where the random forest absorbs the noise signal, causing the score to decrease as true violations grow—a failure mode analyzed in detail. A practical utility experiment demonstrates that the proposed score correctly identifies partial observability and guides architecture selection, fully recover- ing performance lost to non-Markovian observations. Source code to reproduce all results is provided at https://github.com/NAVEENMN/Markovianes. 1 Introduction Reinforcement learning (RL) algorithms overwhelmingly assume that observations satisfy the Markov prop- erty: the current observation, together with the current action, is sufficient to predict the distribution over next observations and rewards (Sutton and Barto, 1998). This assumption underpins convergence guaran- tees, the policy gradient theorem, and the design of virtually all model-free and model-based methods. In practice, though, real-world observations are routinely corrupted by sensor noise, communication delays, and partial observability (Wisniewski et al., 2024), any of which can introduce temporal correlations that break the Markov property. When that happens, value functions conditioned on the current state alone become systematically bi- ased, and policy gradients may point in wrong directions. The trouble is that standard evaluation metrics— episodic return, sample efficiency, convergence rate—cannot tell a practitioner why an agent is underper- forming. An agent struggling because its observations are non-Markovian looks identical, by these metrics, 1 arXiv:2603.27389v1 [cs.LG] 28 Mar 2026 to one struggling with reward sparsity or function approximation error. Despite the practical importance of this failure mode, the RL community lacks standard diagnostic tools for detecting Markov violations in observation trajectories. This paper proposes a prediction-based violation scoring framework to address this gap. The core idea is straightforward: first, a random forest captures whatever structure is predictable from the current state– action pair alone; then, ridge regression checks whether lagged observations carry additional predictive signal about the residuals. If they do, history matters and the Markov property is violated. The resulting score lies in [0, 1] and requires no causal graph construction. Three main contributions are made. First, the two-stage scoring pipeline is developed and evaluated across six Gymnasium environments (CartPole, Pendulum, Acrobot, HalfCheetah, Hopper, Walker2d), three algorithms (PPO, A2C, SAC), six AR(1) noise intensities, and 10 seeds per condition—960 runs in total (Sections 4 and 5). Second, in the 7 environment–algorithm pairs where the score correctly tracks violations (Spearman ρ up to 0.78), higher scores correspond to worse policy performance, and 13 of 16 pairs show statistically significant reward degradation under noise. However, an inversion phenomenon is also observed in low-dimensional environments where the random forest absorbs the noise signal rather than leaving it for the second stage (Section 5.3). This inversion was initially surprising, and its root cause is analyzed in detail, since understanding when the method fails is as important as demonstrating when it works. Third, the score is shown to be actionable: in a controlled partial-observability experiment on CartPole, a score- guided strategy that switches to a history-augmented policy when violations are detected fully recovers the lost performance (Section 5.6). The primary focus is diagnosis—giving practitioners a tool to answer “are my observations non-Markovian?”— rather than a complete remedy. That said, the utility experiment demonstrates that even a simple threshold on the violation score can drive architecture decisions with substantial impact on reward. Paper organization. Section 2 surveys related work. Section 3 introduces the Markov property and its connection to conditional independence. Section 4 defines the prediction-based scoring method. Section 5 presents experiments, including the utility demonstration. Section 6 discusses limitations, and Section 7 concludes. 2 Related Works Robust RL and observation noise. Real-world RL deployments frequently encounter noisy or corrupted observations. The robust RL literature addresses this through adversarial training (Pinto et al., 2017), model- based methods for incomplete or noisy observations (Wang et al., 2019), and distributionally robust formu- lations (Panaganti et al., 2022; Liu et al., 2022b). Separately, the effect of correlated action noise on explo- ration and performance has been studied in continuous control (Hollenstein et al., 2024; 2022), and selective noise injection has been proposed as a regularizer to improve generalization (Igl et al., 2019). These lines of work all evaluate robustness or exploration quality through downstream task performance; none of them tell a practitioner whether or how severely the Markov property has been violated. Partial observability and POMDPs. When the full state is not directly observable, the problem becomes a POMDP (Lauri et al., 2023). Solutions range from belief-state methods to identifying tractable POMDP subclasses with provable sample efficiency (Liu et al., 2022a). These methods can mitigate non-Markovian structure by maintaining history or exploiting structural assumptions, but they do not quantify how much history dependence is present in the first place. The present work is complementary: the proposed score diagnoses the violation; POMDP methods address it. 2 Conditional independence testing and Granger causality. The statistics literature provides many tools for testing conditional independence, from kernel-based tests (Zhang et al., 2011) to classifier-based ap- proaches. Granger causality (Granger, 1969) asks whether past values of one series improve prediction of another—closely related to the approach taken here. Nonlinear extensions via neural networks (Tank et al., 2022) or random forests handle richer dynamics than linear methods. Our approach builds on this tradition but targets the RL setting specifically, where the question reduces to whether any historical observation helps predict the next state beyond what the current state already provides. Markov property testing in RL. Directly testing the Markov property in RL trajectories has received limited attention. Shi et al. (2020) proposed a Forward-Backward Learning procedure that tests the Markov assumption in sequential decision making without parametric assumptions on the joint distribution, with theoretical validity guarantees. However, that test is designed for binary hypothesis testing (Markov or not) and does not produce a graded severity score. Constraint-based causal discovery methods such as PCMCI (Runge, 2022) can detect multi-lag dependencies; the framework supports both linear and nonlinear conditional independence tests, though the default partial-correlation test assumes linearity. Mysore (2025) applied PCMCI with partial correlation to quantify first-order Markov violations in noisy RL, demonstrating that such diagnostics are useful but inheriting the linearity constraints of that specific test. The prediction- based approach proposed here sidesteps these issues: the random forest first stage is nonparametric, and history dependence is tested directly through prediction error comparison rather than graph construction. Positioning. Robust RL assumes violations exist and builds defenses; causal discovery infers graphical structure. The proposed method sits between the two, providing a single scalar answer to a more focused question: does the current observation suffice, or does history help? For an RL practitioner, that question is often more actionable than a full causal graph, and the prediction-based formulation handles nonlinear dynamics naturally. 3 Background 3.1 Markov Property and Markov Decision Processes A discrete-time stochastic processX t ∞ t=0 satisfies the Markov property if the future state X t+1 is condi- tionally independent of all prior states given the current state: P X t+1 | X t ,X t−1 ,...,X 0 = P X t+1 | X t . In RL, this applies to the state variable S t . When the environment is Markov, P S t+1 = s ′ ,R t+1 = r | S t = s,A t = a,...,S 0 ,A 0 = P S t+1 = s ′ ,R t+1 = r | S t = s,A t = a , so only the current state S t and action A t determine what happens next. When noise or partial observability corrupts S t , the observed signal O t may no longer carry enough information, and higher-order dependencies can emerge in the observation stream—even though the un- derlying state dynamics remain Markov. Detecting such observation-level dependencies is the central goal of this work. Throughout, “Markov violation” refers to non-Markovian structure in observations, not a breakdown of the latent state dynamics. 3 3.2 Conditional Independence as a Test for Markov Structure Two random variables X and Y are conditionally independent given Z if P(X | Y,Z) = P(X | Z). The Markov property is exactly such a statement: S t+1 ⊥ S 0 ,...,S t−1 | S t . Whenever knowledge of past states improves prediction of the next state beyond what the current state provides, this independence is violated. This observation suggests a practical detection strategy. Rather than constructing a causal graph or com- puting partial correlations, one can directly test whether historical observations carry predictive information that the current observation misses. The next section formalizes this idea. 4 Prediction-Based Markov Violation Scoring This section describes the proposed violation score, a scalar that quantifies how much an observation trajec- tory departs from Markov. The method has two stages: first strip out whatever the current state can predict, then check whether past observations help explain what remains. 4.1 Stage 1: Nonlinear Markov Removal Given a trajectory of observations o 1 ,o 2 ,...,o T and actions a 1 ,a 2 ,...,a T , two sets of features are constructed. The Markov featuresx (M) t = [o t ,a t ] contain only the information that would suffice if the process were Markov. The history featuresx (H) t = [o t ,a t ,o t−1 ,a t−1 ,...,o t−k+1 ,a t−k+1 ] additionally include k− 1 lagged observation–action pairs. The target is always the next observation y t = o t+1 . In Stage 1, a random forest regressor predicts y t from the Markov features alone: ˆy RF t = f RF x (M) t . The forest uses 200 trees with max depth 10 and a minimum of 5 samples per leaf. To avoid information leakage, residuals are computed using out-of-bag (OOB) predictions: r t = y t − ˆy OOB t . After this stage, the residuals r t have been stripped of everything predictable from the current observa- tion and action. Whatever predictable structure remains must come from history—exactly the signal that indicates a Markov violation. 4.2 Stage 2: Ridge Comparison The residuals are split into training (first 70%) and test (last 30%) sets chronologically, and two ridge re- gressions are fit: Markov ridge model. g M predicts residuals from Markov features: ˆr (M) t = g M x (M) t . This baseline picks up any linear Markov structure that the random forest may have missed. 4 History ridge model. g H predicts residuals from history features: ˆr (H) t = g H x (H) t . If the process is truly Markov, g H should do no better than g M . Both models use RidgeCV with 20 regularization values α ∈ 10 −2 , 10 −1.6 ,..., 10 5 selected via leave-one-out cross-validation (LOO). LOO on sequential data can leak temporal information through shared lagged features; blocked or rolling cross-validation would provide a stricter guard against this, at the cost of less efficient use of the training set. Test-set errors are: MSE M = 1 n test X t∈T test r t − ˆr (M) t 2 ,MSE H = 1 n test X t∈T test r t − ˆr (H) t 2 . 4.3 Score Definition The Markov Violation Score (MVS) is the fractional reduction in prediction error from adding history: MVS = clip MSE M − MSE H MSE M , 0, 1 .(1) A few properties are worth noting. The score is bounded in [0, 1] by construction: negative values (where the history model performs worse, typically due to estimation noise in finite samples) are clipped to zero. When the process is Markov, the history model gains nothing and MVS ≈ 0. Intuitively, MVS measures the relative reduction in test-set prediction error from adding historical observations. The random forest first stage is important because it handles nonlinear-but-Markov dynamics (e.g., the trigonometric relationships in Pendulum) that would otherwise produce false positives. The ridge second stage, with cross-validated regularization, guards against overfitting to spurious history correlations in finite samples. Design choices. A history depth of k = 3 (two additional lags beyond the current) is used, along with a 70/30 train–test split and per-dimension scoring averaged across observation dimensions. AR(1) noise induces dependence at all lags (decaying as α ℓ ); k = 3 captures the strongest portion (lags 1–2) while keeping computation manageable. 4.4 AR(1) Noise as a Controlled Markov Violation To evaluate the score under violations of known severity, autoregressive noise is injected into observations. At each time step, each dimension i is corrupted: ̃o (i) t = o (i) t + z (i) t , z (i) t = α· z (i) t−1 + ε (i) t , ε (i) t ∼N(0, 1), where α ∈ [0, 1) controls the autocorrelation. When α = 0, the noise is i.i.d. and introduces no temporal correlation into the observation stream. (Strictly, even i.i.d. additive noise can make observations non- Markov in the hidden-Markov-model sense, since ̃o t is a noisy function of the latent state; however, no additional history dependence is created by the noise process itself, and the score is empirically near zero in this condition.) For α > 0, the noise process z t carries information from previous time steps into ̃o t , introducing temporal dependence that grows with α. An important distinction: the underlying environment dynamics remain Markov in the augmented state (S t ,z t ). However, because the noise process z t is hidden from the agent, the observation stream ̃o t is non-Markov—the current corrupted observation alone does not determine the conditional distribution of the next. The proposed score targets exactly this observation-level non-Markovity, which is what a practitioner encounters when working with sensor data. This setup gives two experimental phases: 5 1. Phase 1 (Post-hoc detection): Policies are trained on clean observations. AR(1) noise is injected into collected trajectories afterward, and the violation score is computed. This isolates detection capability from any policy adaptation effects. 2. Phase 2 (Training under noise): Policies are trained from scratch with AR(1) noise present through- out, measuring how Markov violations affect learning. 5 Experiments and Results The proposed score is evaluated across six RL environments, three algorithms, and six noise intensities. Phase 1 asks whether the score can detect controlled Markov violations in post-hoc trajectories; Phase 2 measures how those same violations affect policy learning. 5.1 Experimental Setup Environments. Table 1 summarizes the six environments, which span classic control and continuous lo- comotion from OpenAI Gymnasium (Towers et al., 2024). Table 1: Environment summary. Observation dimensionality ranges from 3 (Pendulum) to 17 (HalfCheetah, Walker2d). SAC is used only for continuous-action environments. EnvironmentObs. DimAction SpaceAlgorithmsTraining Steps CartPole-v14Discrete (2)PPO, A2C50k Pendulum-v13Continuous (1)PPO, A2C, SAC450k Acrobot-v16Discrete (3)PPO, A2C50k HalfCheetah-v417Continuous (6)PPO, A2C, SAC1M Hopper-v411Continuous (3)PPO, A2C, SAC1M Walker2d-v417Continuous (6)PPO, A2C, SAC1M Algorithms. PPO (Schulman et al., 2017) and A2C are used across all six environments, with SAC (Haarnoja et al., 2018) additionally applied to the four continuous-action environments. SAC is excluded from Cart- Pole and Acrobot because the stable-baselines3 (Raffin et al., 2021) SAC implementation requires continuous action spaces. All agents use two-hidden-layer MLP policies, giving 16 environment–algorithm pairs in total. Noise protocol. AR(1) noise (Section 4.4) is applied to all observation dimensions at six autocorrelation levels: α∈0.0, 0.1, 0.3, 0.5, 0.7, 0.9. The α = 0 condition is the clean baseline. Seeds and evaluation. Every condition is run with 10 independent seeds. Means with 95% confidence intervals are reported, and significance is assessed via Spearman rank correlation (Phase 1) and Welch’s t- test (Phase 2) at the p < 0.05 level. Because multiple environment–algorithm pairs are tested (16 in Phase 1, 15 in Phase 2), Benjamini–Hochberg false discovery rate (FDR) correction is applied; significance counts reported throughout refer to FDR-adjusted q-values. 6 5.2 Phase 1: Score Sensitivity to Noise Intensity Policies are first trained on clean observations. After training, trajectories are collected, AR(1) noise is injected post-hoc at each α level, and the violation score is computed. This design isolates detection from any confounding policy adaptation. Figure 1 plots MVS against α for all 16 pairs. Table 2 gives the Spearman correlations. 0.00.20.40.60.8 AR(1) alpha 0.02 0.00 0.02 0.04 0.06 0.08 0.10 0.12 MVS Acrobot-v1 A2C PPO 0.00.20.40.60.8 AR(1) alpha 0.000 0.025 0.050 0.075 0.100 0.125 0.150 0.175 MVS CartPole-v1 A2C PPO 0.00.20.40.60.8 AR(1) alpha 0.00 0.05 0.10 0.15 0.20 0.25 0.30 0.35 MVS HalfCheetah-v4 A2C PPO SAC 0.00.20.40.60.8 AR(1) alpha 0.02 0.00 0.02 0.04 0.06 0.08 0.10 0.12 MVS Hopper-v4 A2C PPO SAC 0.00.20.40.60.8 AR(1) alpha 0.000 0.025 0.050 0.075 0.100 0.125 0.150 0.175 MVS Pendulum-v1 A2C PPO SAC 0.00.20.40.60.8 AR(1) alpha 0.000 0.025 0.050 0.075 0.100 0.125 0.150 0.175 MVS Walker2d-v4 A2C PPO SAC MVS vs AR(1) Noise Level (Phase 1b) Figure 1: Phase 1: Violation score vs. noise intensity. Each panel shows one environment; lines represent different algorithms. Error bars are 95% CIs over 10 seeds. The score increases monotonically with α in HalfCheetah and CartPole. In Pendulum, Hopper (PPO/SAC), and Acrobot it decreases—the inversion phenomenon discussed in Section 5.3. Repeated-measures validation. Because Phase 1 injects six noise levels into the same trajectory per seed, the 60 points per pair are not independent. To verify that the pooled p-values are not artifacts, Spearman ρ was computed within each seed (across the 6 α values). For all 7 positive pairs, all 10 seeds show positive ρ (sign-test p = 0.002). Page’s L trend test—which directly tests ordered alternatives under repeated measures—confirms significance for all 7 (p < 10 −4 ), with within-seed median ρ from 0.54 to 0.83. Specificity check. The score was also computed on trajectories from random (untrained) policies under the same noise. Random-policy scores are near zero everywhere, confirming that the method does not fire on unstructured trajectories. The nonzero scores seen in trained-policy runs reflect a genuine interaction between the AR(1) noise and the structure that the learned policy imposes on trajectories. A stronger speci- ficity test—Markov but nonlinear dynamics with i.i.d. noise under trained policies—is left to future work. 5.3 Inverted Scores: When Detection Fails In eight of 16 pairs, the score moves in the wrong direction: it decreases as α increases (Table 2). This was initially surprising and prompted a detailed investigation. 7 Table 2: Phase 1 monotonicity. Spearman ρ between noise intensity α and violation score, pooled across seeds (n = 60 per pair). Seven pairs show the expected positive trend (HalfCheetah strongest at ρ = 0.78). Eight show significant inversion. See text for repeated-measures analysis that accounts for within-seed dependence. EnvironmentAlgorithmSpearman ρ p-valueDirection Positive monotonicity (7 pairs): HalfCheetah-v4PPO0.776 < 10 −12 ✓ HalfCheetah-v4SAC0.700 < 10 −9 ✓ HalfCheetah-v4A2C0.664 < 10 −8 ✓ CartPole-v1PPO0.554 < 10 −5 ✓ Hopper-v4A2C0.520 < 10 −4 ✓ Walker2d-v4A2C0.507 < 10 −4 ✓ CartPole-v1A2C0.447 < 10 −3 ✓ Inverted (8 pairs): Pendulum-v1PPO−0.760 < 10 −12 × Pendulum-v1SAC−0.756 < 10 −12 × Hopper-v4SAC−0.724 < 10 −10 × Hopper-v4PPO−0.643 < 10 −7 × Acrobot-v1PPO−0.497 < 10 −4 × Acrobot-v1A2C−0.466 < 10 −3 × Walker2d-v4SAC−0.3300.010 × Pendulum-v1A2C−0.2800.030 × Not significant (1 pair): Walker2d-v4PPO0.0700.596— 8 Root cause. The problem lies in Stage 1. In low-dimensional environments with highly regular trained- policy trajectories, the random forest is flexible enough to fit not just the true Markov dynamics but also the AR(1) noise pattern riding on top of them. Once the RF captures that noise structure, the residuals are scrubbed of the very signal Stage 2 needs. As α grows and the noise becomes a larger fraction of the total signal, the RF fits it more aggressively—hence the inverted relationship. When it happens. Two factors predict inversion: (1) low observation dimensionality, which gives the RF fewer features and makes noise patterns easier to memorize, and (2) highly structured clean-policy trajectories, which provide a regular backdrop against which AR(1) noise stands out. HalfCheetah, with 17 dimensions and noisier dynamics, is largely immune. Implications. This is a fundamental limitation of any two-stage design where the first stage is flexible enough to absorb the violation signal. Potential mitigations—restricting RF capacity, using a linear first stage in low-dimensional settings, ensemble strategies—are discussed in Section 6. 5.4 Phase 2: Impact of Markov Violations on Reward Phase 2 asks whether the violations the proposed score is designed to detect actually matter for learning. Agents are trained from scratch with AR(1) noise present throughout. Clean (α = 0) versus heavily noised (α = 0.9) final reward is compared using Welch’s t-test across 10 seeds. Figure 2 plots reward against α; Table 3 gives the statistical comparisons. 0.00.20.40.60.8 AR(1) alpha 400 350 300 250 200 150 100 50 Reward Acrobot-v1 A2C PPO 0.00.20.40.60.8 AR(1) alpha 100 200 300 400 500 Reward CartPole-v1 A2C PPO 0.00.20.40.60.8 AR(1) alpha 0 2000 4000 6000 8000 10000 Reward HalfCheetah-v4 A2C PPO SAC 0.00.20.40.60.8 AR(1) alpha 0 500 1000 1500 2000 2500 3000 Reward Hopper-v4 A2C PPO SAC 0.00.20.40.60.8 AR(1) alpha 1400 1200 1000 800 600 400 200 Reward Pendulum-v1 A2C PPO SAC 0.00.20.40.60.8 AR(1) alpha 0 1000 2000 3000 4000 Reward Walker2d-v4 A2C PPO SAC Reward vs AR(1) Noise Level (Phase 2) Figure 2: Phase 2: Reward vs. noise intensity. AR(1) noise during training degrades final performance across nearly all conditions. The worst collapses: HalfCheetah-SAC drops from 8920 to −42; Walker2d- SAC from 4244 to 318; CartPole-PPO from 500 to 53. The damage is substantial. The worst-hit condition, HalfCheetah-SAC, collapses from 8920 to−42— essentially complete failure. Walker2d-SAC drops 93% (4244 to 318), CartPole-PPO 89% (500 to 53). The 9 Table 3: Phase 2: Welch’s t-test. Clean (α = 0) vs. noised (α = 0.9) reward, 10 seeds. Thirteen of 16 pairs show significant degradation after Benjamini–Hochberg FDR correction (q < 0.05). Rewards rounded to integers. EnvironmentAlgorithmClean RewardNoised Reward t-statSignificant CartPole-v1PPO5005394.3Yes Pendulum-v1PPO−166−119157.4Yes Pendulum-v1SAC−133−113448.2Yes HalfCheetah-v4SAC8920−4222.1Yes Walker2d-v4SAC424431821.3Yes Walker2d-v4PPO258722710.2Yes HalfCheetah-v4PPO16543369.25Yes CartPole-v1A2C408509.24Yes Hopper-v4SAC25744327.53Yes Hopper-v4PPO24874187.24Yes Hopper-v4A2C169675.22Yes HalfCheetah-v4A2C8931934.70Yes Pendulum-v1A2C−901−12923.41Yes Acrobot-v1PPO−88−2172.31No (q = 0.053) Walker2d-v4A2C1861121.95No (q = 0.08) Acrobot-v1A2C−286−150 −2.09No (q = 0.07) three non-significant pairs after FDR correction are all borderline (q < 0.08) and involve either A2C in environments where it already performs modestly, or Acrobot where the absolute reward scale is small. A caveat: AR(1) noise with larger α has higher marginal variance, so part of the degradation may reflect noise power rather than temporal correlation per se. Matching marginal variance across α while varying only autocorrelation would isolate the non-Markov contribution; this more controlled design is left to future work. 5.5 Combined Analysis Phase 1 and Phase 2 independently establish two facts: the score tracks violation severity in high-dimensional environments (Spearman ρ up to 0.78, 60 observations per pair), and those same violations degrade reward (13 of 16 pairs significant after FDR correction). Figure 3 puts the two together by plotting Phase 1 violation scores against Phase 2 reward ratio for each condition. The scatter reveals a clear pattern: in environments where the score works correctly—primarily high- dimensional ones like HalfCheetah—points fan out to the right with increasing noise, and higher scores correspond to worse reward. In inverted environments, the score stays near zero regardless of noise level, so reward degrades without a corresponding signal. This is consistent with the inversion mechanism from Section 5.3. The qualitative takeaway is that the proposed method is most informative in environments where the random forest cannot easily memorize the noise—precisely the higher-dimensional settings where diagnosis is most needed. 5.6 Practical Utility: Score-Guided Architecture Selection The results so far show that the proposed score detects violations and that violations hurt reward. But can a practitioner actually use the score? This is tested with a simple architecture-selection experiment: choose between a standard memoryless policy and one that receives a window of recent observations. 10 0.000.050.100.150.200.250.30 MVS (Phase 1b) 0 2 4 6 8 Reward Ratio (vs clean baseline) MVS vs Reward Degradation Spearman rho=-0.350, p=0.0015 Acrobot-v1 CartPole-v1 HalfCheetah-v4 Hopper-v4 Pendulum-v1 Walker2d-v4 Figure 3: Combined: Violation score vs. reward ratio. Each point is one environment–algorithm–noise- level condition. In environments where the score correctly tracks violations (e.g., HalfCheetah, CartPole), higher scores correspond to lower reward. Inverted pairs cluster near score≈ 0 regardless of reward loss. Setup. CartPole-v1 is used under two observation conditions. In the full condition the agent sees all four state variables (position, velocity, angle, angular velocity). In the masked condition the two velocities are zeroed out, leaving only positions—a clean partial-observability setting where the current observation alone cannot determine the next state. For each condition, both a standard MLP policy and a history-augmented policy (current plus two prior observations concatenated) are trained. All runs use PPO, 100k steps, 5 seeds, 20 evaluation episodes. Detection results. Table 4 shows the violation score computed on trajectories from both random and trained policies. Table 4: Detection of partial observability. Masking velocities creates non-Markov observations. The score is near zero for full observations and rises to 0.42 under masking with a trained policy, correctly flagging the violation. ObservationRandom Policy ScoreTrained Policy Score Full (4D)0.0000.000 Masked (positions only)0.0020.421 The score correctly flags the masked condition (0.42) and confirms that full observations are Markov (0.00). Interestingly, the signal is much stronger under a trained policy than a random one (0.42 vs. 0.002), likely because a trained policy concentrates on a narrow region of state space where the missing velocity information matters more. Architecture selection. Table 5 shows what happens when the detection signal is acted upon. The takeaway is clear. When observations are Markov (score = 0), a standard policy suffices and adding 11 Table 5: Architecture selection results. Under full observations both policies hit 500. Under masking the standard policy collapses while the history-augmented policy fully recovers. PPO, 100k steps, 5 seeds, 20 evaluation episodes. ObservationPolicyMean RewardStd FullStandard500.00.0 FullHistory-augmented500.00.0 MaskedStandard43.11.2 MaskedHistory-augmented500.00.0 history buys nothing. When observations are non-Markov (score = 0.42), the standard policy collapses to reward 43—a 91% drop—while the history-augmented policy recovers fully to 500. A simple rule—use the standard architecture when the score is near zero, switch to history augmentation otherwise—gets optimal performance in both cases without adding unnecessary complexity. 6 Limitations and Future Directions Score inversion in low-dimensional environments. The most significant limitation is the inversion phe- nomenon documented in Section 5.3: in 8 of 16 environment–algorithm pairs, the violation score decreases as the true violation grows stronger. Because the random forest in Stage 1 is flexible enough to absorb the noise signal itself, the residuals end up cleaner than they should be—and Stage 2 finds nothing. This is not an implementation bug but a fundamental tension in any two-stage approach with a powerful first stage. Several directions seem worth exploring: restricting forest capacity (fewer trees, shallower depth) so it cannot latch onto temporal noise patterns; falling back to a linear first stage in low-dimensional settings where Markov dynamics are roughly linear anyway; ensembling across Stage 1 models of varying capac- ity; or collapsing to a single-stage direct comparison between Markov and history models, accepting higher false-positive rates in nonlinear-but-Markov systems. AR(1) noise as the sole violation type. The method has been tested exclusively against AR(1) observation noise. AR(1) provides a clean, parameterized violation whose severity is controlled, but real-world non- Markov structure comes from many sources: sensor latency, frame stacking artifacts, communication delays, and genuinely missing state dimensions. Whether the proposed approach generalizes to these settings is an open question. Frame stacking is especially interesting—it introduces a qualitatively different kind of history dependence that may be easier or harder to detect than smooth autocorrelation. From diagnosis to remedy. Section 5.6 shows that the violation score can guide architecture selection in a controlled setting, but fully closing the loop remains open. The score could potentially run as an online diagnostic during training, triggering adaptive responses—switching to a history-augmented architecture when the score crosses a threshold, adjusting learning rates, or informing sensor suite design by comparing scores across observation configurations. That said, the inversion problem must be resolved before the method can serve as a reliable online signal in all environments. Scalability. The pipeline requires collecting a trajectory, computing random forest predictions, and fitting ridge regressions. All steps scale linearly in trajectory length and polynomially in observation dimensional- ity. For the environments tested (up to 17 dimensions), computation is negligible next to RL training time. 12 Scaling to image observations would require a representation learning step before applying the scoring method, which introduces its own assumptions and potential failure modes. Algorithm coverage. PPO, A2C, and SAC—representative on-policy and off-policy methods—are evalu- ated here. How Markov violations interact with model-based RL, offline RL, or multi-agent settings remains unexplored. Model-based methods are particularly interesting: their explicit dynamics models could either amplify non-Markov noise or partially compensate for it. Cross-validation and noise design. Stage 2 selects ridge regularization via leave-one-out cross-validation. Because adjacent time points share lagged features, LOO can leak temporal information; blocked or rolling CV would provide a stricter protocol. Additionally, AR(1) noise with larger α has higher marginal variance, so Phase 2 reward degradation conflates temporal correlation with noise power. A design matching marginal variance across α while varying only autocorrelation would isolate the non-Markov contribution. Theoretical guarantees. The proposed score currently lacks formal statistical guarantees. The two-stage procedure creates dependencies between the residuals and the ridge models that complicate standard hypoth- esis testing. Establishing Type I and Type I error rates, or connecting the score to conditional independence tests with known power properties, would put the method on firmer theoretical ground. 7 Conclusion A prediction-based scoring framework is introduced that quantifies non-Markovian structure in RL obser- vation trajectories. The two-stage approach—random forest residualization followed by ridge regression comparison—yields a bounded, interpretable scalar: zero when the process is Markov, increasing with the severity of history dependence. Across six environments, three algorithms, and controlled AR(1) noise, the proposed method success- fully detects violations in 7 of 16 environment–algorithm pairs, with Spearman correlations up to ρ = 0.78 between noise intensity and the score. In these environments, higher scores correspond to worse policy performance. Phase 2 results confirm that these violations have real consequences: 13 of 16 pairs show statistically significant reward degradation under noise. In a practical utility experiment, the score is shown to guide architecture selection—when partial observability renders observations non-Markovian, it flags the problem and a history-augmented policy chosen accordingly recovers the lost performance entirely. At the same time, an inversion phenomenon in low-dimensional environments limits detection in nearly half the tested conditions, pointing to a fundamental tension between flexible first-stage modeling and preserving the signal that the second stage needs. The candid analysis of when the method works and when it does not is a contribution in its own right. Reliable detection of history dependence is a prerequisite for principled mitigation, and understanding why prediction-based approaches fail in certain regimes should inform the design of more robust diagnostics going forward. References C. W. J. Granger. Investigating Causal Relations by Econometric Models and Cross-spectral Methods. Econometrica, 37(3):424–438, 1969. doi: 10.2307/1912791. 13 Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor, August 2018. URL http://arxiv. org/abs/1801.01290. arXiv:1801.01290 [cs]. Jakob Hollenstein, Sayantan Auddy, Matteo Saveriano, Erwan Renaudo, and Justus Piater. Action Noise in Off-Policy Deep Reinforcement Learning: Impact on Exploration and Performance. Transactions on Machine Learning Research, June 2022. doi: 10.48550/arXiv.2206.03787. URL https://arxiv. org/abs/2206.03787. arXiv:2206.03787 [cs.LG]. Jakob Hollenstein, Georg Martius, and Justus Piater. Colored Noise in PPO: Improved Exploration and Performance through Correlated Action Sampling. Proceedings of the AAAI Conference on Artificial Intelligence, 38(11):12466–12472, March 2024. ISSN 2374-3468, 2159-5399. doi: 10.1609/aaai.v38i11. 29139. URL http://arxiv.org/abs/2312.11091. arXiv:2312.11091 [cs]. Maximilian Igl, Kamil Ciosek, Yingzhen Li, Sebastian Tschiatschek, Cheng Zhang, Sam Devlin, and Katja Hofmann. Generalization in Reinforcement Learning with Selective Noise Injection and Information Bottleneck. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. doi: 10.48550/arXiv.1910.12911. URL https://proceedings.neurips.c/paper/ 2019/hash/e2ccf95a7f2e1878fcafc8376649b6e8-Abstract.html. arXiv:1910.12911 [cs.LG]. Mikko Lauri, David Hsu, and Joni Pajarinen. Partially Observable Markov Decision Processes in Robotics: A Survey. IEEE Transactions on Robotics, 39(1):21–40, February 2023. ISSN 1552-3098, 1941- 0468. doi: 10.1109/TRO.2022.3200138. URL https://ieeexplore.ieee.org/document/ 9899480/. Qinghua Liu, Alan Chung, Csaba Szepesvari, and Chi Jin. When Is Partially Observable Reinforcement Learning Not Scary? In Proceedings of Thirty Fifth Conference on Learning Theory, pages 5175–5220. PMLR, June 2022a. URL https://proceedings.mlr.press/v178/liu22f.html. ISSN: 2640-3498. Zijian Liu, Qinxun Bai, Jose Blanchet, Perry Dong, Wei Xu, Zhengqing Zhou, and Zhengyuan Zhou. Dis- tributionally Robust $Q$-Learning. In Proceedings of the 39th International Conference on Machine Learning, pages 13623–13643. PMLR, June 2022b. URL https://proceedings.mlr.press/ v162/liu22a.html. ISSN: 2640-3498. Naveen Mysore. Quantifying first-order markov violations in noisy reinforcement learning: A causal dis- covery approach. arXiv preprint, arXiv:2503.00206, February 2025. doi: 10.48550/arXiv.2503.00206. URL https://arxiv.org/abs/2503.00206. Kishan Panaganti, Zaiyan Xu, Dileep Kalathil, and Mohammad Ghavamzadeh.Robust Reinforce- ment Learning using Offline Data, October 2022. URL http://arxiv.org/abs/2208.05129. arXiv:2208.05129 [cs]. Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust Adversarial Reinforcement Learning. In Proceedings of the 34th International Conference on Machine Learning, pages 2817–2826. PMLR, July 2017. URL https://proceedings.mlr.press/v70/pinto17a.html. ISSN: 2640-3498. Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dorber. Stable-Baselines3: Reliable reinforcement learning implementations. Journal of Machine Learning Re- search, 22(268):1–8, 2021. 14 Jakob Runge. Discovering contemporaneous and lagged causal relations in autocorrelated nonlinear time series datasets, January 2022. URL http://arxiv.org/abs/2003.03685. arXiv:2003.03685 [stat]. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.Proximal Pol- icy Optimization Algorithms, August 2017.URL http://arxiv.org/abs/1707.06347. arXiv:1707.06347 [cs]. Chengchun Shi, Runzhe Wan, Rui Song, Wenbin Lu, and Ling Leng. Does the Markov Decision Process Fit the Data: Testing for the Markov Property in Sequential Decision Making. In Proceedings of the 37th International Conference on Machine Learning, pages 8807–8817. PMLR, November 2020. URL https://proceedings.mlr.press/v119/shi20c.html. ISSN: 2640-3498. Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. The MIT Press, Cam- bridge, MA, 1998. Alex Tank, Ian Covert, Nicholas Foti, Ali Shojaie, and Emily B. Fox. Neural Granger Causality. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(8):4267–4279, August 2022. doi: 10. 1109/TPAMI.2021.3065601. Epub 2022 Jul 1. PMID: 33705309; PMCID: PMC9739174. Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U. Balis, Gianluca De Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Markus Krimmel, Arjun KG, Rodrigo Perez-Vicente, Andrea Pierré, Sander Schulhoff, Jun Jet Tai, Hannah Tan, and Omar G. Younis. Gymnasium: A Standard Inter- face for Reinforcement Learning Environments. arXiv preprint arXiv:2407.17032, July 2024. doi: 10.48550/arXiv.2407.17032. URL https://arxiv.org/abs/2407.17032. arXiv:2407.17032 [cs.LG]. Yuhui Wang, Hao He, and Xiaoyang Tan. Robust Reinforcement Learning in POMDPs with Incom- plete and Noisy Observations, February 2019.URL http://arxiv.org/abs/1902.05795. arXiv:1902.05795 [cs]. Mariusz Wisniewski, Paraskevas Chatzithanos, Weisi Guo, and Antonios Tsourdos. Benchmarking Deep Reinforcement Learning for Navigation in Denied Sensor Environments, October 2024. URL http: //arxiv.org/abs/2410.14616. arXiv:2410.14616 [cs]. Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kernel-based Conditional Indepen- dence Test and Application in Causal Discovery. In Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, pages 804–813, February 2011. doi: 10.48550/arXiv.1202.3775. URL https://arxiv.org/abs/1202.3775. arXiv:1202.3775 [cs.LG]. A Declaration of LLM Usage Large language models (GPT-4, Claude) were used during manuscript preparation for grammar correction and revising passive voice constructions. All scientific content, experimental design, implementation, and analysis are the sole work of the author. 15 B Implementation and Reproducibility Details All RL agents are trained using Stable-Baselines3 (Raffin et al., 2021) with default hyperparameters for each algorithm (PPO, A2C, SAC). The AR(1) noise wrapper, MVS computation pipeline, and analysis scripts are available in the supplementary source code. Random seeds are fixed for reproducibility; each condition is evaluated over 10 independent seeds. 16

Instant research discovery