Markov Models

Follow this topic Ask about this topic

Momentum

6 papers in the last four weeks, up 100% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 76

Oct 6, 2026stat.ML

Learning Transition Kernels of Jump-Diffusion Processes with Conditional Diffusion Models

We study the problem of learning transition kernels for time-homogeneous jump-diffusion processes using conditional diffusion models, with the goal of generating new sample paths from training data consisting of N independent trajectories observed on a high-frequency discrete time grid. On the theoretical side, we establish non-asymptotic bounds for the conditional score estimation error and for the KL divergence between the laws of the true and generated discretely observed paths. On the numerical side, we first evaluate our method on synthetic data to assess the theoretical findings and benchmark its performance against the approach of Gao et al. (2025). We then apply our method to real-world data and investigate its performance on a probabilistic forecasting task.

Yuzhen Zhao, Yating Liu, Quentin Guibert

CEREMADE, CNRS, Universite Paris-Dauphine, PSL, 75016 Paris, France

Stochastic Differential Equations Conditional Distribution Estimation Conditional Diffusion Models Markov Models

Oct 5, 2026cs.LG

Conditional Flow Matching for Transport Between Markov Processes

Motivated by sequence-to-sequence transport in the context time-series domain adaptation, we study the problem of transportation between trajectories of Markov processes. Given a limited number of trajectories from source distribution and the target distribution, we formulate a flow matching based algorithm which learns a transport map from the source to target trajectory distribution, while preserving the Markov structure. We show that this is consistent in the population limit and derive finite-sample error bounds under mixing time assumptions, following the analysis of classical statistical problems including regression (Nagaraj et al., 2020), principal component analysis (Kumar and Sarkar, 2023), and matrix concentration (Neeman et al., 2024) in the Markov setting. We complement that with a lower-bound construction showing that a mixing-time dependent sample complexity is unavoidable even with regular Gaussian conditional transitions. We evaluate on synthetic and real-world data. For image retrieval from electroencephalography (EEG) on THINGS-EEG2 (Gifford et al., 2022), the task is to identify the viewed image from EEG signals captured from human subjects, which suffers from high inter subject variability. We augment the ENIGMA decoder (Kneeland et al., 2026) with a conditional flow before its subject-specific temporal map. This improves mean top-5 retrieval accuracy from 43.87% to 49.05%, an 11.82% relative improvement.

Syamantak Kumar, Dheeraj Nagaraj, Saptarshi Roy +1

The University of Texas at Austin, Department of Computer Science · Google Deepmind · Mohamed bin Zayed University of Artificial Intelligence, CMS Division +1

Conditional Flow Matching Domain Adaptation Markov Models Optimal Transport

Sep 22, 2026cs.LG

Marginal Log-Likelihood Increments under Dirichlet-Smoothed Markov Estimation

For a Dirichlet-smoothed transition model, the effect of adding one workflow trace to the training archive is an exact change in reference-weighted log likelihood. We derive that change and show that it is a weighted reduction of Kullback--Leibler divergence between the reference conditionals and the model. From this form we obtain an upper bound on the gain available to any acquisition, which expresses a millinat difference as a share of what is attainable, an exact covariance identity for the effect of the reference weighting, and a sign criterion for the interaction between two candidates, from which the batch objective is neither submodular nor supermodular. A case study on the BPI Challenge 2012 loan-application log measures all three and finds a positive selection result in one of the four combinations of reference weighting and budget unit. There, of two regressors fitted to identical descriptors and identical labels, the one that predicts individual increments far more accurately, median

R^2

0.87 against 0.62, realizes the smaller share of the attainable gain, 61 against 69 per cent, so ranking accuracy for individual traces is neither necessary nor sufficient for batch quality.

Levin David Schwab

Markov Models Process Mining Training Data Selection Conditional Distribution Estimation

Sep 15, 2026physics.comp-ph

Machine learning kinetics from molecular dynamics data

Most molecular transitions occur on timescales far beyond direct molecular dynamics simulations. The committor, the probability that a configuration reaches a product state before a reactant state, is a central kinetic statistic, providing a mechanism-independent reaction coordinate and a foundation for transition path theory and the calculation of rates. This review surveys modern approaches for estimating the committor and related kinetic statistics from molecular simulations, with an emphasis on self-supervised methods that learn solutions of their defining dynamical equations rather than relying on labeled shooting data. We develop a common operator viewpoint connecting generator-based partial differential equations, variational principles, Markov state models, dynamical Galerkin approximation, and neural networks. Empirical and theoretical evidence points to the efficiency of these methods. We provide theoretical and practical guidance for realizing their full potential in applications, including strategies for treating non-Markovian effects and for sampling. We conclude by identifying opportunities for further research, including connections to reinforcement learning and generative modeling.

Jonathan Weare, Aaron R. Dinner

Courant Institute School of Mathematics, Computing, and Data Science, New York University, New York, New York 10012, United States · Department of Chemistry and James Franck Institute, University of Chicago, Chicago, Illinois 60637, United States

Markov Models Molecular Dynamics Simulation

Sep 15, 2026cs.LG

High-Performance Tensor Formulation of the Viterbi Algorithm for Hidden Semi-Markov Models

Hidden Semi-Markov Models (HSMMs) are fundamental probabilistic models widely adopted across diverse domains, from computational biology to finance and signal processing. The Viterbi algorithm decodes the most likely state sequence given an HSMM and can be applied iteratively for ab initio model learning. However, existing Viterbi implementations remain sequential, and GPU-accelerated solutions are entirely absent, making HSMM decoding impractical for large-scale workloads. We present a tensor-based formulation of the Viterbi algorithm for HSMMs, restructuring the inner loops into tensor operations that naturally map onto SIMD units and massively parallel architectures. Building on this formulation, we provide optimized implementations spanning single- and multi-core CPUs, and, for the first time, GPU. Experimental evaluation demonstrates speedups of up to 14x on a single core, over 200x with multi-core, and over 570x on GPU over the state-of-the-art sequential baseline, establishing a new performance baseline for large-scale HSMM decoding.

Lorenzo Piarulli, Elia Belli, Daniele De Sensi

Department of Computer Science Sapienza University of Rome

Markov Models High-Performance Computing Hidden Markov Models

Sep 14, 2026cs.DS

Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering

Finding policies for Markov Decision Processes (MDPs) is a central problem in areas such as Reinforcement Learning and Operations Research. Here, we have to repeatedly choose an action that should be performed by an agent. Depending on the action and the current state of the agent, the agent collects a reward and randomly transitions into a new state. The goal is to maximize the reward in expectation over a finite time horizon of length

H

. We consider a recently introduced variant that generalizes the traditionally additive reward function in the model to a monotone submodular one, which allows for capturing a range of interesting applications. Without the stochastic component, this problem is equivalent to the Submodular Orienteering problem, where the goal is to find an

s

-

t

walk in a directed graph maximizing a monotone submodular function under a length constraint. We present a novel LP-based algorithm for Submodular Orienteering using ideas from the Sherali-Adams hierarchy and Round-or-Cut. Our guarantees are comparable to the known quasi-polynomial time logarithmic approximation for Submodular Orienteering, but also extend to the setting of Submodular Markov Decision Processes. In the polynomial time regime, we present an

O(n^{\varepsilon})

-approximation (and

O(H^{\varepsilon})

for Submodular MDPs) for every

\varepsilon >0

, where

n

is the number of vertices, which was unknown even for Submodular Orienteering. Prior to our work, the best known approximation guarantee for Submodular MDPs had an approximation ratio linear in

H

. Beyond these algorithmic results, our methods reveal a trade-off between the approximation guarantee and the number of previously visited vertices on which an agent conditions its decision.

Lars Rohwedder, Rico Zenklusen

University of Southern Denmark, Odense, Denmark · ETH Zurich, Zurich, Switzerland

Submodular Optimization Markov Decision Processes Markov Models Approximation Algorithms

Sep 14, 2026cs.LO

Supermartingale Certificates for Parametric MDPs

We consider the problems of formal verification and synthesis in parametric Markov decision processes (MDPs) with general measurable state and action spaces. The heart of our approach is a parameter flattening transformation, which allows us to transform parametric MDPs into semantically equivalent non-parametric MDPs. Building on this transformation, we introduce the novel notion of parametric supermartingale certificates, which generalize the traditional supermartingale certificates---used for non-parametric MDPs---to the parametric setting. We use our parametric supermartingale certificates to design algorithms for verification and approximate synthesis in polynomial arithmetic parametric MDPs. This leads to the first verification and synthesis algorithms for parametric MDPs with general state and action spaces. We implement our algorithms and experimentally evaluate them on several continuous parametric random walk benchmarks.

Kaushik Mallik, \DHorj̣e Žikelić

IMDEA Software Institute, Madrid, Spain

Robust Markov Decision Processes Markov Decision Processes Markov Models Program Synthesis Formal Verification

Sep 12, 2026cs.AI

Windowed A-K-MDP

Markov decision processes (MDPs) are used to support decision-making in conservation of biodiversity, but policies, even over small state spaces, can be difficult to interpret for conservation managers. K-MDP methods address this problem by building simpler MDPs with at most K abstract states. We show that the previously proposed A-K-MDP algorithm that relies on selecting a discretisation divisor using binary search can skip better abstract states. To fix this issue, we propose Windowed A-K-MDP, an algorithm that generates every distinct feasible partition induced within a declared divisor window and evaluates candidates until reaching the ideal value loss (J = 0) or exhausting the family of candidates. Across 33 K-MDP instances, Windowed improved 25 and tied 8.

Xiangwen Yang, Frankie Cho, Iadine Chades

Monash University Melbourne, Australia

Markov Decision Processes Markov Models State Abstraction

Sep 1, 2026cs.SD

Artificial Rosetta Stone: Constrained Maximum A Posteriori (MAP) Reconstruction of Symbolic Raga Sequences via Order-k Markov Models

Reconstructing a damaged musical fragment is an inverse problem: the observed sequence contains partial information, while a raga encodes constraints limiting allowable completions. This paper formalizes a mathematical framework for this, proposing the Artificial Rosetta Stone (ARS). We separate three claims often conflated: a symbolic sequence can be reconstructed probabilistically; a sequence can be consistent with an explicit grammar; and a historical performance can be authenticated. We only support the first two. We model a raga via a finite alphabet and constraint system, using an order-k Markov model for melodic probabilities. A symmetric Dirichlet prior yields a tractable posterior. We pose missing-note reconstruction as a constrained MAP problem. For fixed-length sequences and finite-order constraints, optimization admits an exact dynamic-programming solution with worst-case time complexity

O(TN^{k+1})

. We derive the parameter count

N^k(N - 1)

, prove a concentration bound under explicit mixing assumptions, and analyze estimation error propagation. A reproducible synthetic experiment uses six raga-inspired alphabets, orders

k \in \{1, 2, 3\}

, and masking rates up to 50%. This is a proof of concept, not historical reconstruction. A real-audio feasibility pilot evaluates 30 usable sequences from 42 Yaman clips via automated pitch extraction, segmentation, and quantization. Lacking documented provenance and relying on automated transcription, this is not expert-validated archival reconstruction. Claims are tied to stated conditions, not universal properties of Hindustani music. Code: https://github.com/mathacker23/ArtificialRosettaStone.

Saanvi Raghavendran, Abhishek Bhattacharjee

Abstract Math Institute

Markov Models Sequence Modeling

Sep 1, 2026cs.LG

When Metropolis and Hastings Meet Bradley and Terry: Exact MCMC From Preference Voting

Sampling from distributions conditioned on desired semantic properties is an emerging challenge in modern generative modeling. Metropolis-Hastings (MH) provides a principled route to conditional sampling, but requires access to exact pointwise target-density evaluations, which are not available in generative settings. Meanwhile, pairwise comparisons by humans or model "judge" are highly accessible and have proved valuable across diverse applications. We introduce Pref-MH, a general exact MH sampler for judge-induced conditional distributions using only stochastic binary pairwise comparisons. Our key observation is that the MH unnormalized density ratio matches the preference odds of the Bradley-Terry (BT) choice model. The central challenge is that while MH requires precise ratio computation, BT judges provide only sampled binary feedback. To this end, we develop a valid accept/reject rule whose resulting Markov chain provably converges to the target distribution. We further show that, for a fixed proposal kernel and budget, Pref-MH is optimal in the Peskun-Tierney sense among this class of exact reversible acceptance rules. Experiments on text generation and molecular design with LLM judges, as well as image generation with VLM judges, demonstrate that Pref-MH provides a practical and flexible approach to conditional sampling when comparative feedback is relatively easy to obtain.

Ariel Smogorghevski, Nir Rosenfeld, Yaniv Romano

Department of Data and Decision Sciences, Technion – Israel Institute of Technology · Department of Computer Science, Technion – Israel Institute of Technology · Department of Electrical and Computer Engineering, Technion – Israel Institute of Technology

Markov Chain Monte Carlo Markov Models Conditional Generative Modeling

Aug 31, 2026stat.ML

Exact Global MCMC with Denoising Diffusion

This work shows that diffusion models learned with standard denoising loss can provide effective global MCMC proposals for complex high-dimensional target densities. The method is motivated by the observation that sequentially applying a forward and reverse diffusion process defines a Markov chain with a target stationary distribution for an ideal denoiser trained on samples of the target distribution. This observation can be made exact for any denoiser by applying a Metropolis-Hastings step whose acceptance ratio includes the density of the forward and reverse paths of a discrete time SDE approximation. We therefore propose to train denoising diffusion models on locally convergent MALA samples to learn global MCMC proposals. We call the composition of the global denoiser-based path sampler and a local MALA sampler Denoising Diffusion Monte Carlo (DDMC). Experiments show that DDMC can provide global proposals with high acceptance across a variety of complex target densities. Our results offer preliminary evidence that the established scaling behavior of standard diffusion training transfers directly to exact sampling from high-dimensional unnormalized densities.

Mitch Hill

Markov Chain Monte Carlo Markov Models Diffusion Models

Aug 7, 2026cs.LG

From Optimal Actions to World Models: Identifiability of Transition Kernels in Discounted MDPs

We study what can be recovered about the transition probabilities of a Markov decision process from optimal actions alone. This is closely related to the inverse problem considered by Letcher et al., who ask when the dynamics can be recovered from numerical

Q

-values. Here the numerical values themselves are not observed; only the optimal actions are known, for every reward in a given class. For state-action rewards

r(s,a)

, knowing the optimal actions for every reward also tells us how much better one action is than another when each is followed by the same fixed policy. This is still not enough to determine the transition probabilities uniquely. We prove that two kernels give the same optimal actions for every reward exactly when

Q_{s,a} = \Bigl(P_{s,a}+\tfrac1γe_s^{\mathsf T}(L-I)\Bigr)L^{-1}

for one invertible matrix

L

satisfying

L\mathbf 1=\mathbf 1

. Near a kernel with strictly positive entries, there is an

n(n-1)

-dimensional family of different kernels with this property. The result is unchanged if we consider only rewards having a unique optimal action at every state. We then compare this with rewards of the forms

r(s)

and

r(s,a,s')

. Rewards that depend on the next state can usually recover the transition kernel itself: every row at a state with at least two actions is determined, and we describe exactly when a row at a state with one action can remain hidden. State rewards reveal less: two kernels give the same optimal actions exactly when every deterministic policy is optimal for the same set of rewards. The results show how the form of the reward affects what can be learned about the dynamics from optimal actions alone.

Neal Batra

Dovetail Research · University of Warwick

Markov Decision Processes Markov Models

Aug 6, 2026cs.LG

Newton-Schulz Retraction-Based Inference Enables Hidden Quantum Markov Models to Outperform Classical HMMs

Hidden Markov models (HMMs) are widely used probabilistic models for discrete sequential data but can be limited when hidden dynamics are complex. Hidden quantum Markov models (HQMMs) generalize HMMs by replacing probability vectors with density matrices and stochastic transitions with quantum operations, enabling richer latent representations. However, existing HQMM learning methods have not consistently outperformed Expectation--Maximization (EM)-trained HMMs on data not generated by quantum processes, limiting their practical applicability. We introduce NS-RIS, Newton--Schulz Retraction-based Inference on the Stiefel manifold, a scalable algorithm for learning trace-preserving HQMMs. NS-RIS uses Newton--Schulz orthogonalization to compute a polar-factor search direction while preserving Stiefel-manifold feasibility, avoiding costly matrix decompositions. We further establish a finite-time stationarity guarantee under standard assumptions on smoothness, stochastic gradients, and finite Newton--Schulz accuracy. Empirically, NS-RIS provides the first benchmark evidence that an HQMM can significantly outperform an EM-trained HMM on data not generated by a quantum model. On synthetic HMM-generated benchmarks, NS-RIS outperforms both EM and the state-of-the-art HQMM method COSM, improving the evaluation metric by an average of 38.5% and by up to 50.6%. On a synthetic HQMM benchmark, it improves the test metric over COSM by 18.9% while reducing runtime by 12.0%. On the real-world Splice classification benchmark, NS-RIS also surpasses both EM and COSM in higher-dimensional latent regimes, reducing mean classification error by 17.9% for latent dimension 6 and 14.9% for latent dimension 8 relative to COSM. These results move HQMMs beyond a theoretical generalization of HMMs and establish them as practical and expressive models for scientific sequence data.

Ning Ning

Department of Statistics, Texas A&M University College Station, Texas, USA

Newton-Schulz Iteration Markov Models Second-Order Optimization Hidden Markov Models

Aug 6, 2026cs.LG

Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty. We study how many samples are necessary and sufficient to learn an

\varepsilon

-optimal robust policy under the average-reward criterion. A generative model provides samples from the nominal transition kernel, whereas policy performance is evaluated over

(s,a)

-rectangular total-variation uncertainty sets of radius at most

σ

. Let

H_0

and

H_σ

denote the nominal and robust optimal bias spans, respectively. We identify

σH_0

as the perturbation scale separating high- and low-tolerance regimes. Our matching upper and lower bounds show that, up to logarithmic factors, the minimax total sample complexity is

NSA \asymp \frac{SA}{\varepsilon^2}\begin{cases} \min\{H_0,H_σ\}, & \varepsilon\gtrsimσH_0,\\ \min\{H_0,H_σ\}+σH_σ^2, & \varepsilon\lesssimσH_0. \end{cases}

Here

S

and

A

are the numbers of states and actions, and

N

is the number of samples per state-action pair. The sample complexity consists of a linear-span term that resembles the nominal AMDP results and a robustness-specific term that appears only in the low-tolerance regime. We attain these rates using reduction-based plug-in procedures that select the reduction---nominal or robust---and its discount factor: a span-informed procedure that makes these choices using known span parameters, and a span-agnostic procedure that calibrates both choices from data.

Yuepeng Yang, Yuxin Chen, Yuejie Chi

*Department of Statistics and Data Science, Yale University. · †Department of Statistics and Data Science, the Wharton School, University of Pennsylvania.

Robust Markov Decision Processes Average-Reward RL Markov Models Minimax Estimation Distributionally Robust RL Sample-Efficient RL

Aug 6, 2026cs.CL

MACRO: Markov Chain Routing of Transformer Layers

Standard Large Language Models (LLMs) execute layers sequentially. Dynamic layer routing, i.e. search for a different execution path through layers involving layer repetitions, skips and other moves, can improve performance. Existing routing approaches often require updating model weights, running expensive search loops per test instance, or demand ground-truth labels during inference. In this work, we propose Markov Chain Routing of Transformer Layers (MACRO), a framework that learns task-specific routes over LLM architectures without modifying underlying parameters. MACRO models layer routing as a context-dependent Markov policy conditioned on layer indices, computation budget phases, directional displacements, and operator context, supporting skip, repeat, and residual hidden-state addition operations. The Markov route distribution is updated via feedback on training data and decoded using a top-k Viterbi algorithm to isolate high-probability candidate programs. We evaluate MACRO across diverse reasoning and knowledge benchmarks on multiple open-weight LLMs. MACRO achieves a +5.0% average accuracy improvement over the unrouted baselines, with largest gains on small models. We outperform the best dynamic routing approach Dr. LLM by +7.2%, while reducing route-search time 9.4x (from 14.8 to 1.6 hours). Our code is publicly available at https://github.com/Batorskq/MACRO.

Paweł Batorski, Abtin Pourhadi, Akylgali Aitaza +2

Heinrich Heine University Düsseldorf · Jagiellonian University · IDEAS Research Institute

Markov Models LLM Inference Acceleration LLM Routing

Aug 3, 2026cs.AI

PAC Approximation and DIRECT Optimization for Parametric Markov Models

In this paper, we consider the parameter synthesis and optimization problem for parametric Markov decision processes (pMDPs), the extension of classical MDPs where exact probability values are replaced by parametric expressions. Computing the rational function

f_{\lsf}

that maps parameter valuations to the satisfaction value of a PRCTL property

\lsf

is a computationally expensive task, particularly for pMDPs where the optimal policy may vary across the parameter space. We adopt the \emph{scenario approach} to efficiently synthesize a probably approximately correct (PAC) approximation

\ApproxFunOfProperty{f}

of

f_{\lsf}

: by sampling parameter configurations and solving a linear program, we obtain a polynomial approximation whose error margin

\margin

is guaranteed, with prescribed confidence, for all but an

\errorRate

-fraction of the parameter domain under the sampling distribution. We further show how this PAC framework can be combined with statistical model checking (SMC), enabling the analysis of black-box parametric models. Building on the PAC approximation, we integrate the DIRECT (DIviding RECTangles) algorithm for derivative-free global optimization over the parameter space. We establish conditional optimality-gap guarantees: under explicit Lipschitz and PAC-good-set assumptions, the difference between the true optimum

f_{\lsf}(\parameters^{*})

and the value found by DIRECT is bounded by a partition-diameter term and, in the PAC case, an additional approximation-error term. An empirical evaluation on 2997 benchmarks focuses on the new DIRECT-based optimization component. The results show that DIRECT variants solve fewer instances than the scenario optimizer, but on their common successful instances they often return slightly better objective values and usually run faster, while remaining close to the scenario values within the PAC margin.

Zhiming Chi, Ying Liu, Andrea Turrini +2

Key Laboratory of System Software (Chinese Academy of Sciences), Beijing, China · Institute of Software, Chinese Academy of Sciences, Beijing, China · University of Chinese Academy of Sciences, Beijing, China +2

Robust Markov Decision Processes Markov Decision Processes Markov Models Formal Verification

Aug 1, 2026cs.LO

Tensor Probabilistic Model Checking of Finite-Horizon Markov Chains (Extended Version)

We reexamine the problem of verifying Markov chains with respect to step-bounded reachability probabilities. Prevailing approaches rely on encoding the state-transition matrix using either explicit or symbolic representations. While these approaches are effective for sparse transition dynamics, they scale less favorably in the dense regime. Our insight is to cast probabilistic model checking of Markov chains as computations over dense tensors. This methodology enables the use of off-the-shelf compiler toolchains for optimized execution of these tensor computations on hardware accelerators. We prove the soundness of the methodology of mapping probabilistic model checking to tensor computations. We implement our approach in a tool called Tessa . Empirical evaluation shows that Tessa unlocks massive speedups over state-of-theart methods on selected benchmarks from the literature.

Jianlin Li, Nick Guo, Peter Ye +1

David R. Cheriton School of Computer Science University of Waterloo, Canada

Reachability Analysis Markov Models Formal Verification

Jul 29, 2026cs.LG

Minimal Markovization via Stable Quotients in Holonomy-Cover Decision Processes

An agent acting under partial observability must retain a recursively updateable statistic of history that restores the Markov property, but the smallest such statistic is generally unknown. We characterize this minimal Markov sufficient statistic for holonomy-cover decision processes, a structured POMDP class in which the visible dynamics are Markov and every realized visible transition applies a fixed permutation to a hidden mode. In particular, we construct the stable quotient, the coarsest observation-wise abstraction preserving one-step rewards and quotient successors, and prove that the pair of the current observation and stable class forms an exact finite Markov state. When the current class is correctly initialized, exact class tracking requires exactly the minimal memory symbols, in the sense that under reachability and pairwise decision separation at a maximizing observation, no arbitrary finite-memory controller can use fewer. Under resettable diagnostics, nearest-prototype class inference has exponentially decaying error, and a calibrate-then-restart reduction transfers finite-MDP guarantees to the recovered state. The results enable \emph{Holonomy Memory Reinforcement Learning}. It represents memory by the current stable class, updates it through ordered edge transports, identifies local class coordinates when diagnostics are available, and applies a standard finite-MDP RL backbone after synchronization. Experiments recover an exact compression from raw states to quotient states and achieve perfect paired-order accuracy with three decision-time memory states, matching the quotient oracle and outperforming the non-oracle baselines.

Zuyuan Zhang, Yongshan Chen, Mahdi Imani +1

Department of Electrical and Computer Engineering, The George Washington University · Department of Electrical and Computer Engineering, Northeastern University

Markov Decision Processes Partially Observable RL Markov Models State Abstraction State Tracking Partially Observable Markov Decision Processes+1

Jul 29, 2026cs.AI

Property-driven Causal Abstractions for Markov Decision Processes

Markov Decision Processes (MDPs) are widely used as decision-making models, commonly specified over factored state spaces through state variables and their valuations. The exponential blowup in the number of states renders many reasoning tasks in MDPs challenging. Abstractions are promising techniques to reduce MDPs and thus mitigate scalability issues. In this work, we introduce a notion of causality on factored MDPs and a novel property-driven causal abstraction technique that retains many characteristics of the original MDP model. For this, we rely on causal relations over state variable predicates and identify those states that share the same reasons for fulfilling or violating a given abstraction property. We theoretically and empirically compare various causal MDP abstractions using different model types such as MDPs, interval MDPs, or stochastic games. Our evaluation demonstrates the potential of our approach: For several standard benchmarks, we obtain small abstractions that allow us to compute near-optimal policies for the original MDP. Furthermore, our causal abstractions often generalize to related large-scale MDP models.

Jule Schmidt, Maximilian Weininger, Clemens Dubslaff +2

Ruhr-University Bochum, Germany · Eindhoven University of Technology, The Netherlands · Oxford University, UK +1

Markov Decision Processes Markov Models State Abstraction Causal Abstraction

Jul 28, 2026cs.AI

dtControl2+ $\varepsilon$ : Trading Optimality for Explainability in MDPs via Decision Trees

Over the past decade, decision trees have been used to represent controllers (a.k.a. policies) in an explainable way, with dtControl2 as a current state-of-the-art tool. However, for systems that are large or have many corner cases, even such representations tend to be too complex and not human-comprehensible. Unfortunately, reducing the size of the decision tree is not straightforward, as missing just a single crucial case might result in an incorrect controller. We tackle this issue in the setting of Markov decision processes, extending dtControl2 by "

\varepsilon

" functionality: Given an allowed imprecision

\varepsilon \geq 0

, we construct a smaller decision tree, distilling the essence of the controller, while still guaranteeing its

\varepsilon

-optimality. This enables us to provide tunably simpler explanations, omitting a controllable amount of detail. Our tool constructs decision trees that are orders of magnitude smaller than the state of the art.

Tereza Kinská, Jan Křetínský, Tobias Meggendorfer +2

Masaryk University, Brno, Czech Republic · Technical University of Munich, Munich, Germany · Lancaster University Leipzig, Leipzig, Germany +1

Markov Decision Processes Markov Models Decision Tree Learning Interpretability in RL

Jul 26, 2026stat.ME

A Characterization of the Orthocomplement of the Tangent Space of Semiparametric Markov Models

Graphical models are ubiquitous in social and empirical science as they are intuitive and easy to use. These models belong to the broader class of Markov models, defined using solely conditional independence (CI) restrictions. In order to estimate finite-dimensional target parameters in such models efficiently, semi-parametric theory provides a principled framework for constructing regular and asymptotically linear estimators via influence functions (IFs). These estimators are asymptotically normal and root-

n

consistent. Characterizing the class of all influence functions for a target parameter is crucial for statistically efficient inference in these models. For models that are Markov relative to directed acyclic graphs (DAGs), the orthogonal complement of the tangent space is known, implying that for any target the class of all influence functions can be derived once an influence function is obtained. On the other hand, for Markov models not equivalent to a DAG model -- such as ordinary Markov models associated with undirected graphs, chain graphs, or acyclic directed mixed graphs -- the orthogonal complement has not been characterized, impeding semi-parametric inference in these models. We derive closed form expressions for the orthogonal complement of the tangent space for general Markov models and illustrate our results by characterizing the class of influence functions for the conditional mean parameter in several graphical models.

Trung Phung, Ilya Shpitser

Computer Science Department, Johns Hopkins University, Baltimore, Maryland, USA

Semiparametric Inference Markov Models Influence Functions

Jul 24, 2026stat.ML

Learning Ergodic Dynamical Systems from a Finite Trajectory

We consider the problem of learning from a single finite trajectory of an ergodic stochastic dynamical system. More precisely, we study discrete-time autonomous stochastic systems defining time-homogeneous Markov processes. We first focus on estimating the optimal one-step prediction function by nonlinear least squares, and derive high-probability guarantees measured with respect to the invariant measure of the process. These results make explicit how the non-independent and non-identically distributed nature of trajectory data modifies the classical statistical learning analysis. We then extend the framework to higher-order systems and finite-state spaces. Finally, we show that the same least squares and concentration arguments naturally extend to learning Koopman operators. Our approach combines tools from statistical learning theory and quantitative ergodic theory for Markov chains. It relies, in particular, on a concentration inequality for Hilbert-space-valued additive functionals of uniformly geometrically ergodic Markov chains.

Oleksii Kachaiev, Silvia Villa, Lorenzo Rosasco

MaLGa center, DIMA, Università degli Studi di Genova, Genoa, Italy · Istituto Italiano di Tecnologia, Genoa, Italy · MaLGa center, DIBRIS, Università degli Studi di Genova, Genoa, Italy

Koopman Operator Learning Markov Models Nonlinear System Identification System Identification Statistical Learning Theory

Jul 23, 2026cs.LG

Mean-to-Score Discrete Diffusion: Posterior-Mean Denoisers for Score Entropy

Score Entropy Discrete Diffusion (SEDD) parameterizes discrete reverse processes with unconstrained positive score ratios. While positivity guarantees nonnegative reverse jump rates, it does not ensure Bayes realizability: ratios at a noisy state need not be jointly induced by any clean-token posterior under the forward kernel. The score-entropy loss has the correct population optimum but does not enforce this constraint away from it. In a trained pure-uniform SEDD checkpoint, roughly one quarter of complete score vectors violate the coordinate box, while more than half lie inside it yet remain materially incompatible with any valid posterior. Such violations can produce negative pre-normalization weights in finite-step sampling. Projecting raw scores onto the bridge polytope removes all observed negative weights and improves external generative PPL from

203.6

to

175.1

without changing the sampler. We introduce \emph{mean-to-score} (M2S), which predicts a clean-token posterior mean and converts it to the score through an exact kernel-dependent linear map. The construction applies to any known coordinate-wise continuous-time Markov chain (CTMC) satisfying a mild support condition. For uniform corruption, it maps the probability simplex onto the bridge polytope; for absorbing-mask corruption, the resulting objective recovers MD4 exactly. In a controlled 28.4M-parameter CIFAR-10 comparison, M2S lowers test BPD from

3.173

to

3.129

and FID-50k from

\CifarSEDDFID

to

\CifarMtwoSFID

. A 170M-parameter M2S model trained on about 262B OpenWebText token slots outperforms the evaluated pure-uniform SEDD, GIDD, and Neural CTMC checkpoints at every tested sampling budget, reaching generative PPL

143.3

at 128 steps versus

183.6

for the strongest pure-uniform baseline.

Jingyuan Li, Xiaoyi Jiang, Yixuan Jiang +4

Tsinghua University · Beijing Institute of Mathematical Sciences and Applications · Wuhan University +1

Constrained Generative Modeling Markov Models Diffusion Language Models Diffusion Models

Jul 21, 2026cs.LG

Parallel Noising in Neural Markov Logic Networks

Neural Markov Logic Networks (NMLNs) are a flexible neurosymbolic relational model. Previous work has shown that, although NMLNs achieve strong performance as generative models for small relational structures, they underperform diffusion-based generative graph models on larger structures. In this paper, we strengthen NMLNs along two main dimensions: (i) we increase the expressive capacity of their potential functions using graph neural networks, and (ii) we develop a new training and inference algorithm inspired by parallel-tempering Markov chain Monte Carlo methods, which we name parallel noising. Together, these enhancements enable NMLNs to attain strong performance in graph generation relative to general diffusion-based generative graph models. Furthermore, they allow NMLNs to match the performance of specialized text-based recurrent models when generating small molecular structures.

Peter Jung, Giuseppe Marra, Ondrej Kuzelka

Czech Technical University, Prague, Czech Republic · Department of Computer Science, KU Leuven, Leuven, Belgium

Markov Chain Monte Carlo Graph Generation Markov Models Molecular Generation Parallel Tempering

Jul 21, 2026cs.SD

End-to-End Markov State Sequence Learning for Auditory Attention Decoding

Auditory attention decoding (AAD) identifies the speaker a listener attends to from neural responses like electroencephalography (EEG), making it a key algorithm in neuro-steered hearing aids. However, most neural AAD models are trained as independent short-window classifiers, despite auditory attention being a temporally persistent cognitive state and short-window EEG--audio evidence often being noisy and ambiguous. We propose an end-to-end Markov AAD framework based on conditional random field (CRF) that trains window-level neural emissions under a two-state attention prior. The framework treats the logits of any AAD backbone as Markov emissions, learns the transition rate from a standard HMM initialization, and jointly optimizes cross-entropy and CRF objectives, allowing temporal continuity to guide representation learning rather than merely smoothing predictions after training. We also introduce ESCNet, an EEG--speech correlation backbone that preserves time-aligned features and converts the difference between two mean Pearson correlations into state logits. We evaluate the framework with four emission backbones spanning correlation-based, convolutional, recurrent, and attention-based designs. On the dynamic AVGC dataset, CRF training generally outperforms post-hoc HMM smoothing; with ESCNet, it achieves

86.5\%

causal and

92.4\%

non-causal accuracy using

1

s windows. On the static KUL and USTC datasets, it improves causal decoding over fixed-rate post-hoc HMM baselines by

5.6\%

and

2.0\%

, respectively, showing the superiority of learning AAD as attention state sequence over isolated-window classification.

Yushan Yashengjiang, Jie Zhang, Miao Sun +3

NERC-SLIP, University of Science and Technology of China (USTC), Hefei 230027, China · School of Information and Communication Engineering, Guangzhou Maritime University, Guangzhou 510725, China · Artificial Intelligence Research Institute, iFLYTEK Company, Ltd., Hefei 230088, China +1

Markov Models Neural Decoding EEG Decoding Sequence Modeling

Jul 14, 2026cs.LG

Concurrent Image Understanding and Generation: Self-Correcting Coupled Markov Jump Processes

Human cognition does not separate understanding and generation. A teacher at a whiteboard speaks and draws

\textit{together}

, each modality reshapes the other. In this paper, we bring this coupled loop to artificial systems. Masked Diffusion Models (MDMs) are ideally suited to this task, yet existing samplers either decode text and image interleavedly or independently update them in parallel branches that share only previous-step history, but not the other modality's latest decisions

\textit{within}

the same step; combined with MDMs' inability to remask, cross-modal contradictions are neither detected nor repaired. We introduce

\textbf{Self-Correcting Coupled Markov Jump Processes (SC-CMJP)}

, a framework in which one modality's transition rates are functionals of the other modality's confidence score, as weighted by cross-modal attention. Furthermore, a remasking jump retracts commitments the moment cross-modal evidence turns against them. In conjunction with SC-CMJP, we introduce

\texttt{CO}_\texttt{2}\texttt{Jump}

(Self-

\underline{\text{CO}}

rrecting

\underline{\text{CO}}

upled

\underline{\text{Jump}}

), a novel training-free single-pass sampler for joint multimodal geneneration. For training and evaluation purposes, we have created and will release three large-scale joint multimodal generation corpora:

\text{JEdit-1M}

,

\text{JMaze-200K}

,

\text{JNono-200K}

, with matching in- and out-of-distribution benchmarks.

\texttt{CO}_\texttt{2}\texttt{Jump}

achieves best joint performance for image understanding and editing as well as visual reasoning (maze and nonogram solving). The performance of the sampler scales monotonically with the number of denoising steps, evidence that the benefits of cross-modal coupling

\textit{compound}

across the trajectory. Project page: https://coupled-jump.github.io

Minh-Quan Le, Armand Comas, Alexandros Lattas +7

Google · Stony Brook University · Google DeepMind

Masked Diffusion Models Markov Models Cross-Modal Alignment Multimodal Generation Multimodal Learning

Jul 10, 2026cs.LG

Risk-Aware General-Utility Markov Decision Processes

We study general-utility Markov decision processes (GUMDPs) with risk-aware objectives. In this framework, an agent aims to optimize a risk measure of the distribution of objective values, where the objective function depends on the frequency of visitation of states induced by the agent's policy. First, we motivate, propose, and formalize risk-aware GUMDPs, which enable agents and decision makers to trade off expected performance by risk aversion while benefiting from the rich set of objectives that can be cast under the framework of GUMDPs. We focus our attention on the entropic risk measure (ERM). Second, we show how we can solve risk-aware GUMDPs with ERM objectives by resorting to online planning techniques. In particular, we propose an approach based on Monte Carlo Tree Search (MCTS) to provably solve risk-aware GUMDPs up to any desired accuracy. Third, we provide a set of experimental results showcasing that our approach is successful when optimizing for a spectrum of risk-aware behaviors in the context of GUMDPs under diverse tasks (standard MDPs, maximum state entropy exploration, imitation learning, and multi-objective MDPs).

Pedro P. Santos, Fábio Vital, Alberto Sardinha +1

INESC-ID · Instituto Superior Técnico, University of Lisbon · Pontifical Catholic University of Rio de Janeiro

Markov Decision Processes Markov Models Risk-Sensitive RL Interval Markov Decision Processes

Jul 6, 2026cs.LG

What Does a Discrete Diffusion Model Learn?

What does a discrete diffusion model learn: a denoiser, a score ratio, or a bridge plug-in predictor? At the level of jump rates, these are one object in different coordinates, and reading a neural network in the wrong coordinate changes the process being trained and sampled. Starting with a rigorous derivation of the continuous-time Markov chain (CTMC) ELBO for any noising process, boundary terms included, we prove the \emph{Oracle Distance} theorem: the negative ELBO is exactly equal to the data entropy plus the path KL from the oracle reverse process to the learned one, not merely a bound. Its unique optimizer is therefore the conditional expectation of the true reverse jump rate given the current noisy state, and its irreducible cost is the rate at which the forward process

Z_t

destroys information about the clean data

Z_0

,

-\tfrac{d}{dt}I(Z_0; Z_t)

, so every noising process shares the same best achievable negative ELBO: the data entropy. For sequences with token-factorizing noise, the oracle projection yields three exact coordinates for the optimizer: denoiser, cavity (bridge plug-in), and score, with closed-form conversions among them. This framework identifies which law each loss in the literature actually optimizes, recovering MDM, UDM, SEDD, and GIDD as special cases; explains why denoiser and cavity coincide for masked diffusion but not for uniform diffusion; proves that a denoiser parameterization makes the uniform ELBO diverge at initialization while the bridge plug-in stays finite; and calibrates ELBO implementations exactly at initialization. Every identity is verified numerically, without approximation, on an exactly solvable model.

Rodrigo Casado Noguerales, Bernhard Schölkopf, Thomas Hofmann +1

1ETH Zurich · 2Max Planck Institute for Intelligent Systems, Tübingen · 3ELLIS Institute Tübingen

Markov Models Variational Inference Diffusion Models

Jul 6, 2026stat.ML

Non-Asymptotic Error Bounds for SMC with Biased Proposals: Application to Conditional Diffusion Sampling

Sequential Monte Carlo (SMC) methods are a natural tool for post-hoc conditioning of pretrained generative models, but in many applications the mutation kernels used by the particle system are biased approximations of an ideal Feynman--Kac flow. This paper develops a non-asymptotic error analysis for such SMC samplers. Under forward-smoothing forgetting conditions, we decompose the total error into a kernel bias, measuring the effect of replacing the ideal transition kernels by approximate ones, and a finite-particle Monte Carlo error. Our approach relies on extending local Doeblin-type conditions and Lyapunov drift arguments for Markov kernels to conditional distributions, thereby enabling a principled control of the bias. We then instantiate this general framework for conditional sampling with score-based diffusion models, and derive the first non-asymptotic error bound that jointly controls initialization error, time discretization, and score approximation in the reverse diffusion dynamics as well as finite-particle Monte Carlo error.

Stanislas Strasman, Gabriel Victorino Cardoso, Sylvain Le Corff +2

SU, LPSM · Sorbonne Université and Université Paris Cité, CNRS, LPSM, F-75005 Paris, France · LPSM +2

Markov Chain Monte Carlo Markov Models Diffusion Sampling Convergence Analysis Score-Based Generative Modeling

Jun 29, 2026cs.AI

Sample-Efficient Learning of Probabilistic Causes for Reachability in Markov Decision Processes with Probabilistic Guarantees

Probabilistic model checking for Markov decision processes (MDPs) provides quantitative guarantees, but often offers limited insight into why undesired outcomes occur. Probability-raising (PR) causality addresses this by identifying states whose visitation increases the probability of reaching designated states. Existing PR-cause identification methods, however, use MDP modifications not well-suited for learning: the gap between conditional and unconditional reachability probabilities can be hard to detect from transition samples, and construction requires reachability probabilities of the MDP, which are unavailable when transition probabilities are unknown. We study unknown MDPs and propose a learning approach with probabilistic guarantees for PR-cause identification. Our key ingredient is a restart-based MDP modification that reduces PR-cause checking to two conditional reachability queries without using reachability values of the original MDP. We prove correctness, establish sample-complexity bounds, and develop an anytime learning-and-checking algorithm based on two-sided value iteration that progressively classifies states as causal, non-causal, or undecided. Experiments on two benchmarks demonstrate reliable and fast identification of PR causes.

Ryohei Oura, Georgios Fainekos, Hideki Okamoto +1

Toyota Research Institute of North America, Toyota Motor North America · Frontier Research Center, Toyota Motor Corporation

Reachability Analysis Markov Decision Processes Markov Models Causal Reasoning Causal Inference