Papers › A Pseudo-Gradient Approach for Model-free Markov Chain Optimization
A Pseudo-Gradient Approach for Model-free Markov Chain Optimization
Nanne A. Dieleman, Joost Berkhout, Bernd Heidergott
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We develop a first-order (pseudo-)gradient approach for optimizing functions over the stationary distribution of discrete-time Markov chains (DTMC). We give insights into why solving this optimization problem is challenging and show how transformations can be used to circumvent the hard constraints inherent in the optimization problem. The optimization framework is model-free since no explicit model of the interdependence of the row elements of the Markov chain transition matrix is required. Upon the transformation we build an extension of Simultaneous Perturbation Stochastic Approximation (SPSA) algorithm, called stochastic matrix SPSA (SM-SPSA) to solve the optimization problem. The performance of the SM-SPSA gradient search is compared with a benchmark commercial solver. Numerical examples show that SM-SPSA scales better which makes it the preferred solution method for large problem instances. We also apply the algorithm to the maximization of web-page rankings in web-graphs based on a real-life data set. As we explain in the paper, when applying a first-order gradient search one typically encounters a phenomenon which we call ``infliction points," that is, jumps in the optimization trajectories between periods of almost stationary behavior that slow down the optimization. We propose a heuristic for avoiding such infliction points and present a metastudy on a wide range of networks showing the positive effect of our heuristic on the convergence properties of SM-SPSA gradient search.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections