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

Naveen Mysore · 2025

Read Quantifying First-Order Markov Violations in Noisy Reinforcement Learning: A Causal Discovery Approach by Naveen Mysore (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-00206.txt.

Introduction

Naveen Mysore measures breaks in the Markov assumption inside noisy reinforcement learning in this 2025 paper. Learning agents assume each observation fully shows the state. Sensor noise and missing variables break that promise quietly. His method pairs a causal discovery algorithm with a new score for multi step dependence.

Three classic control tasks serve as test beds. Added noise sometimes left little trace in the score, even at high levels. Dropping key variables hurt both returns and the score sharply. Removing angular velocity from two tasks was especially damaging. Other dropped dimensions mattered far less. The score tells engineers which sensors to protect first, rather than treating all noise alike.

Catalog record

CREATORNaveen Mysore
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE25 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-00206

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantifying First-Order Markov Violations in Noisy Reinforcement Learning: A Causal Discovery Approach Naveen Mysore Abstract 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. The present 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 ). 1 Introduction Reinforcement learning (RL) conventionally assumes that each observation completely encodes the environment’s state, thereby guaranteeing single-step (Markov) transitions ( Sutton & Barto 1998 ) . In practical scenarios, however, partial observability or sensor inaccuracies frequently violate this assumption ( Wisniewski et al. 2024 ) , leading to multi-step correlations and weakened training outcomes. Although numerous RL methods can withstand mild noise, moderate or poorly structured perturbations tend to disrupt Markovian structure and erode policy performance. A principal difficulty is in identifying the precise circumstances under which the Markov property fails. Standard benchmarks (e.g., final returns) do not indicate whether an environment is effectively “non-Markovian” from the learning agent’s standpoint. To address this, the current study introduces a Markov Violation Score (MVS), leveraging partial correlation tests via PCMCI ( Runge 2022 ) . This metric highlights significant lag-2-and-beyond correlations that point to multi-step processes beyond first-order assumptions. A thorough examination explores how particular distortions affect both learning performance and MVS in three classic control tasks: CartPole-v1 , Pendulum-v1 , and Acrobot-v1 . • Noise Injection. Gaussian noise and autoregressive processes are injected into observation streams at various magnitudes, revealing which components are indispensable for stable operation. • Dimension Dropping. Specific observation dimensions are removed entirely, compelling agents to learn in the presence of incomplete states. While some omissions lead to modest performance reductions, others trigger severe instability and elevated MVS. • Markov Violation Analysis. For each manipulation, PCMCI detects higher-order correlations (lags of 2 or more). Notable surges in multi-step links typically align with abrupt performance drops, indicating that single-step Markov assumptions no longer hold. The outcomes show that different state components do not uniformly maintain Markovian structure. Altering or omitting a crucial variable can lead to strong multi-lag dependencies and dramatic policy breakdowns, while discarding less essential parts can have minimal impact. Moreover, each task exhibits distinct thresholds of resilience: certain environments degrade under moderate noise, whereas others (e.g., Acrobot) accommodate multi-lag interactions without catastrophic failure. Paper Organization. Sections 2 – 3.2 provide background on partial observability and causal discovery, then present the Markov property, PCMCI, and the introduced MVS. Section 5 outlines the experimental procedure (baseline runs, noise perturbations, dimension dropping) and reports empirical findings on policy performance alongside Markov consistency. Section 6 discusses constraints and outlines possible future directions, and Section 7 offers concluding remarks. 2 Related Works Real-world reinforcement learning (RL) often faces partial observability and noisy signals that undercut the strict Markov property ( wie 2012 ) . In the domain of robust RL , a variety of works address disturbances in observations or transitions ( Panaganti et al. 2022 ; Liu et al. 2022b ) , employing adversarial training ( Pinto et al. 2017 ) or domain randomization ( Wang et al. 2019 ; Li et al. 2021 ; Wang et al. 2020 ) to tackle noisy sensing. Some investigations incorporate noise directly into states or actions ( Hollenstein et al. 2024 ; Hollenstein et al. ; Igl et al. 2019 ) , yet their evaluations frequently rely on final-return measures and overlook a principled way to detect multi-step dependencies arising from the breakdown of Markov assumptions. Another area of partially observable RL examines how unobserved factors degrade Markovian structure ( Lauri et al. 2023 ) . Within POMDPs and similar formalisms, latent variables ( Liu et al. 2022a ) often characterize environment dynamics ( Zhu et al. 2020 ; Yu et al. ; Shi et al. 2020 ) . While such techniques can handle certain forms of noise (e.g., Gaussian or autoregressive), few methods pinpoint which dimensions or temporal segments are crucial for sustaining or undermining first-order dynamics. Moreover, a single, cohesive metric for quantifying multi-lag correlations remains elusive. In contrast, some studies ( Ota et al. 2020 ) expand input dimensionality to boost sample efficiency and final returns, highlighting the importance of retaining essential state information in larger feature spaces. However, these works do not clarify which dimensions are strictly necessary for preserving a Markovian environment. To address such gaps, the present study applies PCMCI’s causal discovery approach ( Runge 2022 ) to expose higher-lag partial correlations and measure departures from the Markov property. Building on robust RL’s focus on noisy observations and partial-observability research on hidden variables, this paper introduces a Markov Violation Score (MVS) that consolidates multi-step influences exceeding first-order transitions. Unlike previous causal-discovery research ( Zeng et al. 2023 ) and partial-observation studies, the MVS offers a single, interpretable metric reflecting how strongly the Markov assumption is broken under dimension removal or other perturbations. Consequently, this perspective surpasses reliance on final-return metrics to identify precisely which dropped variables or noise processes most severely compromise first-order RL learning. 3 Preliminaries 3.1 Markov Property and Markov Decision Processes A discrete-time stochastic process \{X_{t}\}_{t=0}^{\infty} satisfies the Markov property if, at every time step t , the future state X_{t+1} is conditionally independent of all prior states \{X_{0},X_{1},\ldots,X_{t-1}\} given the current state X_{t} . Formally, P\bigl(X_{t+1}\mid X_{t},X_{t-1},\ldots,X_{0}\bigr)\;=\;P\bigl(X_{t+1}\mid X_{t}\bigr). Intuitively, this means the present state fully encapsulates all relevant information from the past. In a reinforcement learning (RL) context, we typically apply the Markov property to a state variable S_{t} . If the environment truly satisfies this property, then P\bigl(S_{t+1}=s^{\prime},R_{t+1}=r\,\mid\,S_{t}=s,A_{t}=a,\ldots,S_{0},A_{0}\bigr)\;=\;P\bigl(S_{t+1}=s^{\prime},R_{t+1}=r\,\mid\,S_{t}=s,A_{t}=a\bigr), which ensures that only the current state S_{t} and action A_{t} determine the distribution over next states S_{t+1} and rewards R_{t+1} . However, if noise or partial observability reduce the completeness of S_{t} , higher-order (multi-lag) dependencies may arise. This violates the first-order Markov assumption and can complicate RL methods that rely on single-step dynamics. 3.1.1 Conditional Independence and the PCMCI Framework Two variables X and Y are said to be conditionally independent given a set of variables Z if P(X\,\mid\,Y,Z)\;=\;P(X\,\mid\,Z). In an ideal Markov process, once the current state S_{t} is known, the future state

Read the complete text