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

• URL: http://arxiv.org/abs/2503.00206v2
• Date: Sun, 01 Jun 2025 18:06:22 GMT
• Title: Quantifying First-Order Markov Violations in Noisy Reinforcement Learning: A Causal Discovery Approach
• Abstract summary: Reinforcement learning (RL) methods assume that each new observation completely reflects the environment's state.<n>In practice, partial observability or sensor/actuator noise often invalidates this assumption.<n>This paper proposes a systematic methodology for detecting such violations with a novel Markov Violation score (MVS)<n>MVS measures multi-step dependencies that emerge when noise or incomplete state information disrupts the Markov property.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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. 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).

Related papers

• Path-dependent Discrete Amortized Inference [7.20046890493201]
  We consider the problem of sampling compositional and discrete objects from a given unnormalized posterior distribution.<n>We show that the Markovian assumption can both hamper signal propagation during training and catastrophically reduce the learned sampler's expressivity.<n>We propose lifting the MDP with a learnable latent dynamical system that allows the underlying policy to depend on the entire past trajectory.
  arXiv  Detail & Related papers  (2026-08-09T11:35:05Z)
• GAMR: Geometric-Aware Manifold Regularization with Virtual Outlier Synthesis for Learning with Noisy Labels [7.09131557837911]
  Deep neural networks (DNNs) experience significant performance degradation when processing noisy labels.<n>Current mainstream approaches attempt to mitigate this issue by passively filtering clean samples during training.<n>We highlight for the first time the fundamental importance of actively reshaping feature space geometry for learning from noisy data.
  arXiv  Detail & Related papers  (2026-05-20T05:24:43Z)
• Diagnosing Non-Markovian Observations in Reinforcement Learning via Prediction-Based Violation Scoring [0.0]
  Reinforcement learning algorithms assume that observations satisfy the Markov property.<n>Real-world sensors frequently violate this assumption through correlated noise, latency, or partial observability.<n>This paper introduces a prediction-based scoring method that quantifies non-Markovian structure in observation trajectories.
  arXiv  Detail & Related papers  (2026-03-28T19:42:27Z)
• Variational Rectification Inference for Learning with Noisy Labels [74.85528327499662]
  We propose variational rectification inference (VRI) to formulate the adaptive rectification for loss functions.<n>VRI is constructed as a hierarchical Bayes by treating the rectifying vector as a latent variable.<n>By introducing the variational term in VRI, the conditional posterior is estimated accurately and avoids collapsing to a Dirac delta function.
  arXiv  Detail & Related papers  (2026-03-18T01:25:08Z)
• Beyond Raw Detection Scores: Markov-Informed Calibration for Boosting Machine-Generated Text Detection [105.14032334647932]
  Machine-generated texts (MGTs) pose risks such as disinformation and phishing, highlighting the need for reliable detection.<n> Metric-based methods, which extract statistically distinguishable features of MGTs, are often more practical than complex model-based methods that are prone to overfitting.<n>We propose a Markov-informed score calibration strategy that models two relationships of context detection scores that may aid calibration.
  arXiv  Detail & Related papers  (2026-02-08T16:06:12Z)
• When Sharpening Becomes Collapse: Sampling Bias and Semantic Coupling in RL with Verifiable Rewards [20.896576101848655]
  We study whetherReinforcement Learning with Verifiable Rewards elicits novel capabilities or merely sharpens the distribution over existing knowledge.<n>We propose inverse-success advantage calibration to prioritize difficult queries and distribution-level calibration to diversify sampling via a memory network.
  arXiv  Detail & Related papers  (2026-01-22T03:15:57Z)
• Noise-Adaptive Regularization for Robust Multi-Label Remote Sensing Image Classification [5.658568324275769]
  We propose NAR, a noise-adaptive regularization method that distinguishes between additive and subtractive noise.<n> NAR consistently improves robustness compared with existing methods.<n>Performance improvements are most pronounced under subtractive and mixed noise.
  arXiv  Detail & Related papers  (2026-01-13T11:16:45Z)
• Learning Causal States Under Partial Observability and Perturbation [29.533770208192845]
  Existing methods fail to mitigate perturbations while addressing partial observability.<n>We propose textitCausal State Representation under Asynchronous Diffusion Model (CaDiff)<n>CaDiff is the first framework that approximates causal states using diffusion models with both theoretical rigor and practicality.
  arXiv  Detail & Related papers  (2025-11-29T06:56:03Z)
• Anomalous Decision Discovery using Inverse Reinforcement Learning [3.3675535571071746]
  Anomaly detection plays a critical role in Autonomous Vehicles (AVs) by identifying unusual behaviors through perception systems.<n>Current approaches, which often rely on predefined thresholds or supervised learning paradigms, exhibit reduced efficacy when confronted with unseen scenarios.<n>We present Trajectory-Reward Guided Adaptive Pre-training (TRAP), a novel IRL framework for anomaly detection.
  arXiv  Detail & Related papers  (2025-07-06T17:01:02Z)
• Automatically Identify and Rectify: Robust Deep Contrastive Multi-view Clustering in Noisy Scenarios [76.02688769599686]
  We propose a novel multi-view clustering framework for the automatic identification and rectification of noisy data, termed AIRMVC.<n>Specifically, we reformulate noisy identification as an anomaly identification problem using GMM.<n>We then design a hybrid rectification strategy to mitigate the adverse effects of noisy data based on the identification results.
  arXiv  Detail & Related papers  (2025-05-27T16:16:54Z)
• Attention Reallocation: Towards Zero-cost and Controllable Hallucination Mitigation of MLLMs [62.9348974370985]
  We propose attention reallocation (AttnReal) to mitigate hallucinations with nearly zero extra cost. Our approach is motivated by the key observations that, MLLM's unreasonable attention distribution causes features to be dominated by historical output tokens. Based on the observations, AttnReal recycles excessive attention from output tokens and reallocates it to visual tokens, which reduces MLLM's reliance on language priors.
  arXiv  Detail & Related papers  (2025-03-11T11:52:37Z)
• Rethinking State Disentanglement in Causal Reinforcement Learning [78.12976579620165]
  Causality provides rigorous theoretical support for ensuring that the underlying states can be uniquely recovered through identifiability. We revisit this research line and find that incorporating RL-specific context can reduce unnecessary assumptions in previous identifiability analyses for latent states. We propose a novel approach for general partially observable Markov Decision Processes (POMDPs) by replacing the complicated structural constraints in previous methods with two simple constraints for transition and reward preservation.
  arXiv  Detail & Related papers  (2024-08-24T06:49:13Z)
• Robust Learning under Hybrid Noise [24.36707245704713]
  We propose a novel unified learning framework called "Feature and Label Recovery" (FLR) to combat the hybrid noise from the perspective of data recovery.
  arXiv  Detail & Related papers  (2024-07-04T16:13:25Z)
• Skeleton-Based Human Action Recognition with Noisy Labels [43.58994208412764]
  Label noise negatively affects the model's training, resulting in lower recognition quality. NoiseEraSAR integrates global sample selection, co-teaching, and Cross-Modal Mixture-of-Experts strategies. Our proposed approach demonstrates better performance on the established benchmark, setting new state-of-the-art standards.
  arXiv  Detail & Related papers  (2024-03-15T02:42:28Z)
• Undersampling and Cumulative Class Re-decision Methods to Improve Detection of Agitation in People with Dementia [16.949993123698345]
  Agitation is one of the most prevalent symptoms in people with dementia (PwD) In a previous study, we collected multimodal wearable sensor data from 17 participants for 600 days and developed machine learning models for detecting agitation in one-minute windows. In this paper, we first implemented different undersampling methods to eliminate the imbalance problem, and came to the conclusion that only 20% of normal behaviour data were adequate to train a competitive agitation detection model.
  arXiv  Detail & Related papers  (2023-02-07T03:14:00Z)
• GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond [101.5329678997916]
  We study sample efficient reinforcement learning (RL) under the general framework of interactive decision making. We propose a novel complexity measure, generalized eluder coefficient (GEC), which characterizes the fundamental tradeoff between exploration and exploitation. We show that RL problems with low GEC form a remarkably rich class, which subsumes low Bellman eluder dimension problems, bilinear class, low witness rank problems, PO-bilinear class, and generalized regular PSR.
  arXiv  Detail & Related papers  (2022-11-03T16:42:40Z)
• Finite-Time Analysis of Natural Actor-Critic for POMDPs [29.978816372127085]
  We consider the reinforcement learning problem for partially observed Markov decision processes (POMDPs) with large or even countably infinite state spaces. We consider a natural actor-critic method that employs a finite internal memory for policy parameterization. We show that this error can be made small in the case of sliding-block controllers by using larger block sizes.
  arXiv  Detail & Related papers  (2022-02-20T07:42:00Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  We study a new subclass of POMDPs, whose latent states can be decoded by the most recent history of a short length $m$. In particular, in the rich-observation setting, we develop new algorithms using a novel "moment matching" approach with a sample complexity that scales exponentially. Our results show that a short-term memory suffices for reinforcement learning in these environments.
  arXiv  Detail & Related papers  (2022-02-08T16:39:57Z)
• Provable RL with Exogenous Distractors via Multistep Inverse Dynamics [85.52408288789164]
  Real-world applications of reinforcement learning (RL) require the agent to deal with high-dimensional observations such as those generated from a megapixel camera. Prior work has addressed such problems with representation learning, through which the agent can provably extract endogenous, latent state information from raw observations. However, such approaches can fail in the presence of temporally correlated noise in the observations.
  arXiv  Detail & Related papers  (2021-10-17T15:21:27Z)
• Exploring the Training Robustness of Distributional Reinforcement Learning against Noisy State Observations [7.776010676090131]
  State observations that an agent observes may contain measurement errors or adversarial noises, misleading the agent to take suboptimal actions or even collapse while training. In this paper, we study the training robustness of distributional Reinforcement Learning (RL), a class of state-of-the-art methods that estimate the whole distribution, as opposed to only the expectation, of the total return.
  arXiv  Detail & Related papers  (2021-09-17T22:37:39Z)
• Attentional-Biased Stochastic Gradient Descent [74.49926199036481]
  We present a provable method (named ABSGD) for addressing the data imbalance or label noise problem in deep learning. Our method is a simple modification to momentum SGD where we assign an individual importance weight to each sample in the mini-batch. ABSGD is flexible enough to combine with other robust losses without any additional cost.
  arXiv  Detail & Related papers  (2020-12-13T03:41:52Z)
• Semi-Supervised Learning with Variational Bayesian Inference and Maximum Uncertainty Regularization [62.21716612888669]
  We propose two generic methods for improving semi-supervised learning (SSL) The first integrates weight perturbation (WP) into existing "consistency regularization" (CR) based methods. The second method proposes a novel consistency loss called "maximum uncertainty regularization" (MUR)
  arXiv  Detail & Related papers  (2020-12-03T09:49:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.