Deep Learning for Markov Chains: Lyapunov Functions, Poisson's Equation, and Stationary Distributions

• URL: http://arxiv.org/abs/2508.16737v1
• Date: Fri, 22 Aug 2025 18:24:43 GMT
• Title: Deep Learning for Markov Chains: Lyapunov Functions, Poisson's Equation, and Stationary Distributions
• Abstract summary: We show that deep learning can automate the construction of Lyapunov functions by training neural networks to satisfy integral equations.<n>Our approach can be adapted to solve Poisson's equation and estimate stationary distributions.
• Score: 1.7699991125484107
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Lyapunov functions are fundamental to establishing the stability of Markovian models, yet their construction typically demands substantial creativity and analytical effort. In this paper, we show that deep learning can automate this process by training neural networks to satisfy integral equations derived from first-transition analysis. Beyond stability analysis, our approach can be adapted to solve Poisson's equation and estimate stationary distributions. While neural networks are inherently function approximators on compact domains, it turns out that our approach remains effective when applied to Markov chains on non-compact state spaces. We demonstrate the effectiveness of this methodology through several examples from queueing theory and beyond.

Related papers

• Learning Ergodic Dynamical Systems from a Finite Trajectory [10.59816347247158]
  We study discrete-time autonomous systems defining time-homogeneous Markov processes.<n>We first focus on estimating the optimal one-step prediction function by nonlinear least squares.<n>We extend the framework to higher-order systems and finite-state spaces.
  arXiv  Detail & Related papers  (2026-07-24T15:21:51Z)
• Interpretable Neural Approximation of Stochastic Reaction Dynamics with Guaranteed Reliability [4.736119820998459]
  We introduce DeepSKA, a neural framework that achieves interpretability, guaranteed reliability, and substantial computational gains.<n>DeepSKA yields mathematically transparent representations that generalise across states, times, and output functions, and it integrates this structure with a small number of simulations to produce unbiased, provably convergent, and dramatically lower-magnitude estimates than classical Monte Carlo.
  arXiv  Detail & Related papers  (2025-12-06T04:45:31Z)
• Latent Guided Sampling for Combinatorial Optimization [3.636090511738153]
  Recent Combinatorial Optimization methods leverage deep learning to learn solution strategies, trained via Supervised or Reinforcement Learning (RL)<n>While promising, these approaches often rely on task-specific augmentations, perform poorly on out-of-distribution instances, and lack robust inference mechanisms.<n>In this work, we propose LGS-Net, a novel latent space model that conditions on efficient problem instances, and introduce an efficient Neural inference method, Latent Guided Sampling (LGS)
  arXiv  Detail & Related papers  (2025-06-04T08:02:59Z)
• Uncertainty quantification for Markov chains with application to temporal difference learning [63.49764856675643]
  We develop novel high-dimensional concentration inequalities and Berry-Esseen bounds for vector- and matrix-valued functions of Markov chains.<n>We analyze the TD learning algorithm, a widely used method for policy evaluation in reinforcement learning.
  arXiv  Detail & Related papers  (2025-02-19T15:33:55Z)
• Stochastic Process Learning via Operator Flow Matching [12.275587079383603]
  We develop operator flow matching (OFM) for learning process priors on function spaces.<n>OFM provides the probability density of the values of any collection of points.<n>Our method outperforms state-of-the-art models in process learning, functional regression, and prior learning.
  arXiv  Detail & Related papers  (2025-01-07T20:12:56Z)
• Symplectic Neural Flows for Modeling and Discovery [9.786274281068815]
  SympFlow is a time-dependent symplectic neural network designed using parameterized Hamiltonian flow maps.<n>It allows for backward error analysis and ensures the preservation of the symplectic structure.<n>We demonstrate the effectiveness of SympFlow on diverse problems, including chaotic and dissipative systems.
  arXiv  Detail & Related papers  (2024-12-21T22:02:00Z)
• Distributionally Robust Model-based Reinforcement Learning with Large State Spaces [55.14361269378122]
  Three major challenges in reinforcement learning are the complex dynamical systems with large state spaces, the costly data acquisition processes, and the deviation of real-world dynamics from the training environment deployment. We study distributionally robust Markov decision processes with continuous state spaces under the widely used Kullback-Leibler, chi-square, and total variation uncertainty sets. We propose a model-based approach that utilizes Gaussian Processes and the maximum variance reduction algorithm to efficiently learn multi-output nominal transition dynamics.
  arXiv  Detail & Related papers  (2023-09-05T13:42:11Z)
• Value-Distributional Model-Based Reinforcement Learning [59.758009422067]
  Quantifying uncertainty about a policy's long-term performance is important to solve sequential decision-making tasks. We study the problem from a model-based Bayesian reinforcement learning perspective. We propose Epistemic Quantile-Regression (EQR), a model-based algorithm that learns a value distribution function.
  arXiv  Detail & Related papers  (2023-08-12T14:59:19Z)
• MARS: Meta-Learning as Score Matching in the Function Space [79.73213540203389]
  We present a novel approach to extracting inductive biases from a set of related datasets. We use functional Bayesian neural network inference, which views the prior as a process and performs inference in the function space. Our approach can seamlessly acquire and represent complex prior knowledge by metalearning the score function of the data-generating process.
  arXiv  Detail & Related papers  (2022-10-24T15:14:26Z)
• Reachability analysis in stochastic directed graphs by reinforcement learning [67.87998628083218]
  We show that the dynamics of the transition probabilities in a Markov digraph can be modeled via a difference inclusion. We offer a methodology to design reward functions to provide upper and lower bounds on the reachability probabilities of a set of nodes.
  arXiv  Detail & Related papers  (2022-02-25T08:20:43Z)
• Variational Inference for Continuous-Time Switching Dynamical Systems [29.984955043675157]
  We present a model based on an Markov jump process modulating a subordinated diffusion process. We develop a new continuous-time variational inference algorithm. We extensively evaluate our algorithm under the model assumption and for real-world examples.
  arXiv  Detail & Related papers  (2021-09-29T15:19:51Z)
• ImitationFlow: Learning Deep Stable Stochastic Dynamic Systems by Normalizing Flows [29.310742141970394]
  We introduce ImitationFlow, a novel Deep generative model that allows learning complex globally stable, nonlinear dynamics. We show the effectiveness of our method with both standard datasets and a real robot experiment.
  arXiv  Detail & Related papers  (2020-10-25T14:49:46Z)
• Multiplicative noise and heavy tails in stochastic optimization [62.993432503309485]
  empirical optimization is central to modern machine learning, but its role in its success is still unclear. We show that it commonly arises in parameters of discrete multiplicative noise due to variance. A detailed analysis is conducted in which we describe on key factors, including recent step size, and data, all exhibit similar results on state-of-the-art neural network models.
  arXiv  Detail & Related papers  (2020-06-11T09:58:01Z)
• A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms [67.67377846416106]
  We present a distributional approach to theoretical analyses of reinforcement learning algorithms for constant step-sizes. We show that value-based methods such as TD($lambda$) and $Q$-Learning have update rules which are contractive in the space of distributions of functions.
  arXiv  Detail & Related papers  (2020-03-27T05:13:29Z)
• Formal Synthesis of Lyapunov Neural Networks [61.79595926825511]
  We propose an automatic and formally sound method for synthesising Lyapunov functions. We employ a counterexample-guided approach where a numerical learner and a symbolic verifier interact to construct provably correct Lyapunov neural networks. Our method synthesises Lyapunov functions faster and over wider spatial domains than the alternatives, yet providing stronger or equal guarantees.
  arXiv  Detail & Related papers  (2020-03-19T17:21:02Z)

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.