Deep Learning for Markov Chains: Lyapunov Functions, Poisson’s Equation, and Stationary Distributions
Yanlin Qu, Jose Blanchet, Peter Glynn · 2025
Read Deep Learning for Markov Chains: Lyapunov Functions, Poisson’s Equation, and Stationary Distributions by Yanlin Qu, Jose Blanchet, Peter Glynn (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-2508-16737.txt.
Introduction
Yanlin Qu, Jose Blanchet, and Peter Glynn present a 2025 paper on deep learning for Markov chains. Markov chains model systems that jump between states, from queues to inventories. Lyapunov functions prove such systems stable, but crafting one takes creativity and effort. The authors train neural networks to satisfy equations drawn from first-step analysis. The networks learn the stability certificate directly. The same machinery then solves Poisson's equation and estimates long-run state frequencies.
A worry is that networks only fit bounded regions, yet the method works on unbounded state spaces too. Queueing examples and others demonstrate the reach. Operations researchers get an automated route to proofs that once needed bespoke insight. Stability certificates gate everything else in queue design, from staffing to buffer sizes. A learner that proposes them, with equations to verify the result, pairs machine search with human-checkable math. That pairing is the paper's real contribution.
Catalog record
| CREATOR | Yanlin Qu, Jose Blanchet, Peter Glynn |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-16737
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Deep Learning for Markov Chains: Lyapunov Functions, Poisson’s Equation, and Stationary Distributions Yanlin Qu, Jose Blanchet, Peter Glynn 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. MSC Classification]60J05 keywords Markov chains, deep learning, Lyapunov functions, Poisson’s equation, stationary distributions, first-transition analysis pacs [ 1 Introduction The use of Lyapunov functions to settle stability questions in the setting of Markovian queues has become a standard tool within the research community. However, the construction of appropriate Lyapunov functions to determine the stability of many models remains challenging, and settling stability questions via the use of this method requires great creativity and insight in order to build suitable Lyapunov functions; see, for example, Chapter 16.4 of Meyn and Tweedie 2012 and Chapter 3.2 of Dai and Harrison 2020 . In this paper, we show how deep learning can be used to numerically compute Lyapunov functions. In particular, given a Markov chain X=(X_{n}:n\geq 0) living on state space \mathcal{S}\subseteq\mathbb{R}^{d} with one-step transition kernel P=(P(x,dy):x,y\in\mathcal{S}) , the typical Lyapunov function used to settle stability involves a non-negative function v=(v(x):x\in\mathcal{S}) satisfying the inequality (Pv)(x)\leq v(x)-1, (1.1) for x\in A^{c} and some suitable set A , where (Ph)(x)=\int_{\mathcal{S}}h(y)P(x,dy) for a generic function h ; see Chapter 11.3 of Meyn and Tweedie 2012 . The function v is then known to provide an upper bound on \mathbb{E}_{x}T_{A} , where \mathbb{E}_{x} is the expectation on the path-space of X conditioned on X_{0}=x , and T_{A}=\inf\{n\geq 0:X_{n}\in A\} . In fact, our deep learning algorithm computes the minimal non-negative function v satisfying ( 1.1 ), namely the function v^{*}(x)=\mathbb{E}_{x}T_{A} that satisfies ( 1.1 ) with equality. More generally, we leverage deep learning to globally compute expectation functions of the form u^{*}(x)=\mathbb{E}_{x}\left[\sum_{k=0}^{T}\exp\left(-\sum_{j=0}^{k-1}\beta(X_{j})\right)r(X_{k})\right], (1.2) for r\geq 0 and x\in C , where T=\inf\{n\geq 0:X_{n}\in C^{c}\} . Note that expected hitting times, exit probabilities, and infinite horizon expected discounted rewards (obtained by making C^{c} the empty set) are all special cases of ( 1.2 ). By conditioning on the first transition of the Markov chain (i.e. using first-transition analysis (FTA)), these functions can be characterized by integral equations. We train neural networks to satisfy these equations by minimizing the integrated squared residual error with respect to the network parameters using stochastic gradient descent (SGD). To obtain an unbiased gradient estimator, we use the double-sampling trick that utilizes two independent and identically distributed (i.i.d.) copies of the first transition; see Goda and Kitade 2023 . We have used this idea in related work of ours on computing rates of convergence to equilibrium for Markov chains; see Qu et al. 2024 . This idea has also been used to compute splitting probabilities and to predict rare events without simulating long sample paths, thereby achieving great efficiency; see Strahan et al. 2023 ; Cheng and Weare 2024 and the references therein. In the context of reinforcement learning, the same idea can be used to perform policy evaluation, leading to the residual gradient algorithm ; see Baird 1995 ; Baird and Moore 1998 ; Sutton and Barto 2018 (Chapter 11.5). Our main contribution in this paper is to expose the use of deep learning to the queueing and applied probability communities, as a means of solving the linear integral equations that arise from Markov chain models. In the course of explaining these ideas, we describe how deep learning can be applied to compute global approximations to the solution of FTA equations arising within the general setting of ( 1.2 ). As far as we are aware, this generalization is new. In particular, as explained above, our proposed approach therefore provides a vehicle for deep-learning-based numerical construction of Lyapunov functions. Hence, deep learning can potentially play a role in settling the types of stability questions that often arise in Markov chain modeling applications. In addition to the integral equations that arise within the setting of FTA expectations and probabilities, this paper also contributes suitable deep-learning-based algorithms for solving the integral equations that arise within the context of stationary distribution computation and also that of Poisson’s equation. To be specific, when X is positive recurrent with a unique stationary distribution \pi , Poisson’s equation involves computing the solution u^{*} to the linear integral equation given by u(x)-(Pu)(x)=r(x)-\pi r, (1.3) for x\in\mathcal{S} , where \pi r=\int_{\mathcal{S}}r(y)\pi(dy) is the centering constant. Since this constant is typically unknown, the approach used to solve ( 1.2 ) must be adapted to address this issue; this contribution is also new. We further note that the unknown probability measure \pi arising in the setting of stationary distribution computation is a measure rather than a function (as in ( 1.2 )) and hence the deep learning algorithm for computing \pi also requires a slight modification to the FTA deep learning approach we propose. Poisson’s equation plays a key role in the central limit theorem for Markov chains, and in other calculations related to additive functionals of Markov chains; see, for example, Maigret 1978 and Kurtz 1981 . The theory and practice of deep-learning-based function approximation requires that the domain of the functions being approximated be compact. We show how the deep learning method can be applied to Markov chains on non-compact state spaces, despite the fact that neural networks are inherently function approximators on compact domains. An additional contribution of this paper is our careful analysis of the sample complexity for the deep learning approximations to the solutions to the equations arising in the computation of FTA expectations and probabilities. In particular, Theorem 3 shows that, if the target function u^{*} on K\subseteq\mathbb{R}^{d} is s -Hölder continuous, then the mean squared error of the empirical risk minimizer (ERM) over clipped ReLU networks scales as n^{-\frac{2s}{2s+d}} up to logarithmic factors, with an explicit conditioning factor reflecting the implicit fixed-point contraction associated with the linear integral equation arising in FTA settings. This connects the smoothness s and dimension d of the problem to the number of samples required to achieve a prescribed accuracy. This paper is organized as follows: In Section 2 , we apply deep learning to compute FTA-type quantities ( 1.2 ), including Lyapunov functions. In Section 3 , we develop the corresponding finite-sample guarantee. In Section 4 , we apply deep learning to solve Poisson’s equation ( 1.3 ), without computing the centering constant. In Section 5 , we apply deep learning to estimate stationary distributions. In Section 6 , we extend our approach to non-compact state spaces. In Section 7 , we demonstrate the effectiveness of our approach through several examples from queueing theory and beyond. 2 First-transition analysis via deep learning We start by observing that the expectation u^{*}(x) defined by ( 1.2 ) can be expressed