pith. sign in

arxiv: 2605.00532 · v1 · submitted 2026-05-01 · 🧮 math.OC · cs.NA· math.NA· math.PR

Linking PageRank, Time Reversal, and Policy Evaluation

Konstantin Avrachenkov , Lorenzo Gregoris , Nelly Litvak This is my paper

Pith reviewed 2026-05-09 19:13 UTC · model grok-4.3

classification 🧮 math.OC cs.NAmath.NAmath.PR
keywords PageRankMarkov decision processpolicy evaluationtime reversalquasi-stationary distributionsDoob h-transformvalue functiondiscounted rewards
0
0 comments X

The pith

The value function of a discounted MDP equals a rescaled PageRank vector on the policy's time-reversed Markov chain.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper establishes a direct link between policy evaluation in Markov decision processes and the computation of PageRank vectors in network analysis. For any fixed policy, the expected discounted rewards that define the value function can be recovered from the PageRank vector of a time-reversed version of the policy's Markov chain, after a simple rescaling. The discount factor in the MDP plays exactly the role of the teleportation probability in PageRank, and the reward function shapes the restart distribution used in the PageRank computation. This correspondence extends to general finite MDPs through a decomposition that handles recurrent and transient states separately via quasi-stationary distributions. The unification suggests that computational tools developed for one domain can be repurposed for the other.

Core claim

For a fixed policy, the value function of a discounted Markov decision process can be obtained, up to an explicit rescaling, from the PageRank vector of a suitably defined time-reversed Markov chain. In this correspondence, the discount factor plays the role of the teleportation parameter, while rewards induce the restart distribution. Beyond the irreducible case, invoking quasi-stationary distributions and Doob h-transforms, a general decomposition theorem shows that policy evaluation for arbitrary finite MDPs reduces to a collection of PageRank problems on the recurrent and transient components of the policy-induced Markov chain. The framework also covers undiscounted MDPs with terminal (i

What carries the argument

The time-reversed Markov chain built from the policy transition matrix, with its PageRank vector (damped by the discount factor) yielding the value function after rescaling.

If this is right

  • Policy evaluation for undiscounted MDPs with absorbing terminal states reduces to the same PageRank construction.
  • Transition-dependent rewards are incorporated simply by redefining the restart distribution in the reversed chain.
  • The general finite-MDP case decomposes into independent PageRank computations, one per recurrent class plus one for transients.
  • Existing fast PageRank solvers on graphs can be applied directly to compute value functions on large state spaces.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Fast PageRank approximation methods such as Monte Carlo sampling or matrix sketching become immediate candidates for approximate policy evaluation in large MDPs.
  • The time-reversal duality may yield new dual formulations or symmetry-based bounds for convergence rates in reinforcement learning.
  • Centrality scores in networks can be reinterpreted as expected discounted cumulative rewards under suitably chosen reward functions.

Load-bearing premise

The policy-induced chain admits a unique stationary distribution when irreducible, or that quasi-stationary distributions exist on recurrent classes together with a valid Doob h-transform construction.

What would settle it

Take any small irreducible finite MDP, solve the linear Bellman system for the exact value function, build the corresponding time-reversed chain, compute its PageRank vector with teleportation equal to the discount, rescale, and check whether the vectors match exactly.

Figures

Figures reproduced from arXiv: 2605.00532 by Konstantin Avrachenkov, Lorenzo Gregoris, Nelly Litvak.

Figure 1
Figure 1. Figure 1: Policy Iteration (left column) / Policy Evaluation (right column) experiments (all runs: γ = 0.90, κ = 0.1; initial stickiness αx ∼ Unif[0.1, 0.9]; results averaged over 20 seeds). Left column: average value vs normalized iterations (cumulative edges processed / total edges). Right column: Bellman residual vs normalized iterations. Stopping tolerance 10−10 . 12 view at source ↗
read the original abstract

We establish a connection between policy evaluation in Markov decision processes and PageRank in network analysis. For a fixed policy, we show that the value function of a discounted Markov decision process can be obtained, up to an explicit rescaling, from the PageRank vector of a suitably defined time-reversed Markov chain. In this correspondence, the discount factor plays the role of the teleportation parameter, while rewards induce the restart distribution. Beyond the irreducible case, invoking quasi-stationary distributions and Doob $h$-transforms, we prove a general decomposition theorem showing that policy evaluation for arbitrary finite MDPs reduces to a collection of PageRank problems on the recurrent and transient components of the policy-induced Markov chain. This framework naturally extends to undiscounted MDPs with terminal states and to transition-dependent rewards. We conclude by showing efficiency of our approach on a numerical example of a sticky random walk on large deterministic and random graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript claims to link policy evaluation in discounted Markov decision processes to PageRank computation via time reversal of the policy-induced chain. The value function is recovered from the PageRank vector up to rescaling, with the discount factor as the teleportation parameter and rewards inducing the restart distribution. A general decomposition theorem for finite MDPs is presented using quasi-stationary distributions for recurrent classes and Doob h-transforms for transients. Extensions to undiscounted cases with terminal states and transition-dependent rewards are included, with a numerical illustration on sticky random walks on large graphs.

Significance. If the derivations hold, this provides a significant exact algebraic bridge between policy evaluation in RL and PageRank in network analysis, grounded in standard Markov chain theory with no free parameters. The decomposition theorem for general MDPs is a key strength, reducing the problem to independent PageRank instances while preserving the Bellman structure. The approach extends naturally to related settings and the numerical example indicates practical efficiency, potentially enabling cross-field algorithmic transfers.

minor comments (2)
  1. [Abstract] The abstract states that the value function is obtained 'up to an explicit rescaling' but does not preview the form of the rescaling factor; stating it explicitly in the introduction or the irreducible-case section would improve readability.
  2. In the numerical example section, the description of the sticky random walk and the graphs would benefit from explicit parameter values (e.g., stickiness probability, graph sizes, and exact PageRank solver used) to support reproducibility.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, including the recognition of the exact algebraic bridge between policy evaluation and PageRank, the strength of the decomposition theorem, and the natural extensions to related settings. We are pleased that the recommendation is to accept.

Circularity Check

0 steps flagged

No significant circularity; algebraic equivalence via standard Markov chain identities

full rationale

The central claim derives the discounted value function directly from the stationary distribution of a time-reversed chain whose teleportation parameter is set to the discount factor and whose restart distribution is induced by the reward vector. This is an exact linear-algebra identity obtained by substituting the time-reversal construction into the standard stationary-distribution equation; the Bellman equation V = r + γPV is recovered without any auxiliary fitting, ansatz, or self-referential definition. The extension to general finite MDPs decomposes the chain into recurrent classes (handled by quasi-stationary distributions) and transient states (handled by Doob h-transforms), each of which reduces to an independent PageRank problem with an explicit rescaling factor. Both quasi-stationary distributions and h-transforms are standard, externally established tools in Markov-chain theory and do not rely on results from the present authors. No load-bearing step reduces the claimed correspondence to its own inputs by construction, and no self-citation is invoked to justify uniqueness or the core construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard properties of finite Markov chains and MDPs without introducing new free parameters or postulated entities.

axioms (2)
  • standard math Finite-state Markov chains admit unique stationary distributions when irreducible and aperiodic.
    Invoked for the basic PageRank-value function equivalence.
  • standard math Quasi-stationary distributions exist and are unique on recurrent classes of finite chains.
    Used in the decomposition theorem for transient and recurrent components.

pith-pipeline@v0.9.0 · 5463 in / 1246 out tokens · 54510 ms · 2026-05-09T19:13:41.281288+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 2 canonical work pages

  1. [1]

    Adaptive on-line page importance computation

    Serge Abiteboul, Mihai Preda, and Gregory Cobena. “Adaptive on-line page importance computation”. In:Proceedings of the 12th international conference on World Wide Web. 2003, pp. 280–290

    2003

  2. [2]

    Generalized prioritized sweeping

    David Andre, Nir Friedman, and Ronald Parr. “Generalized prioritized sweeping”. In: Advances in neural information processing systems10 (1997)

    1997

  3. [3]

    Red Light Green Light Method for Solving Large Markov Chains

    Konstantin Avrachenkov, Patrick Brown, and Nelly Litvak. “Red Light Green Light Method for Solving Large Markov Chains”. In:Journal of Scientific Computing93.1 (Oct. 2022), p. 18.issn: 0885-7474, 1573-7691.doi: 10 . 1007 / s10915 - 022 - 01976 - 8.url: https://link.springer.com/10.1007/s10915-022-01976-8

    work page doi:10.1007/s10915-022-01976-8 2022

  4. [4]

    Computing Stationary Distribution via Dirichlet-Energy Minimization by Coordinate Descent

    Konstantin Avrachenkov, Lorenzo Gregoris, and Nelly Litvak. “Computing Stationary Distribution via Dirichlet-Energy Minimization by Coordinate Descent”. In:50th Woud- schoten Conference. Lecture Notes in Computational Science and Engineering. Springer, 2026, pp. 123–456

    2026

  5. [5]

    Monte Carlo methods in PageRank computation: When one iteration is sufficient

    Konstantin Avrachenkov et al. “Monte Carlo methods in PageRank computation: When one iteration is sufficient”. In:SIAM Journal on Numerical Analysis45.2 (2007), pp. 890–904

    2007

  6. [6]

    Generic rank-one corrections for value iteration in Markovian decision problems

    Dimitri P. Bertsekas. “Generic rank-one corrections for value iteration in Markovian decision problems”. In:Operations Research Letters18.2 (1995), pp. 67–71

    1995

  7. [7]

    The anatomy of a large-scale hypertextual web search engine

    Sergey Brin and Lawrence Page. “The anatomy of a large-scale hypertextual web search engine”. In:Computer networks and ISDN systems30.1-7 (1998), pp. 107–117

    1998

  8. [8]

    Fan Chung and Olivia Simpson.Computing Heat Kernel Pagerank and a Local Clustering Algorithm. 2016. arXiv: 1503 . 03155 [cs.DS].url: https : / / arxiv . org / abs / 1503 . 03155

    2016

  9. [9]

    Conditional Brownian motion and the boundary limits of harmonic functions

    J. L. Doob. “Conditional Brownian motion and the boundary limits of harmonic functions”. In:Bulletin de la Société Mathématique de France85 (1957), pp. 431–458.doi:10.24033/ bsmf.1494

    1957

  10. [10]

    Scaling personalized web search

    Glen Jeh and Jennifer Widom. “Scaling personalized web search”. In:Proceedings of the 12th international conference on World Wide Web. 2003, pp. 271–279

    2003

  11. [11]

    Andrey Kolobov et al.Planning with Markov decision processes: An AI perspective. Vol. 17. Morgan & Claypool Publishers, 2012

    2012

  12. [12]

    David A Levin and Yuval Peres.Markov chains and mixing times. Vol. 107. American Mathematical Soc., 2017

    2017

  13. [13]

    A uniform approach to accelerated PageRank computation

    Frank McSherry. “A uniform approach to accelerated PageRank computation”. In:Pro- ceedings of the 14th international conference on World Wide Web - WWW ’05. the 14th international conference. Chiba, Japan: ACM Press, 2005, p. 575.isbn: 978-1-59593-046-0. doi: 10.1145/1060745.1060829.url: http://portal.acm.org/citation.cfm?doid= 1060745.1060829(visited on ...

    work page doi:10.1145/1060745.1060829.url: 2005

  14. [14]

    Prioritized Sweeping: Reinforcement Learning with Less Data and Less Real Time

    Andrew W. Moore and Christopher G. Atkeson. “Prioritized Sweeping: Reinforcement Learning with Less Data and Less Real Time”. In:Machine Learning13.1 (1993), pp. 103– 130

    1993

  15. [15]

    Policy invariance under reward transformations: Theory and application to reward shaping

    Andrew Y Ng, Daishi Harada, and Stuart Russell. “Policy invariance under reward transformations: Theory and application to reward shaping”. In:Icml. Vol. 99. Citeseer. 1999, pp. 278–287

    1999

  16. [16]

    John Wiley & Sons, 2014

    Martin L Puterman.Markov decision processes: Discrete stochastic dynamic programming. John Wiley & Sons, 2014. 13

    2014

  17. [17]

    Walter Rudin.Functional Analysis. 2nd. International Series in Pure and Applied Mathe- matics.NewYork,NY:McGraw-HillScience/Engineering/Math,1991.isbn:978-0070542365

    1991

  18. [18]

    On quasi-stationary distributions in discrete-time Markov chains with a denumerable infinity of states

    Eugene Seneta and David Vere-Jones. “On quasi-stationary distributions in discrete-time Markov chains with a denumerable infinity of states”. In:Journal of Applied Probability 3.2 (1966), pp. 403–434

    1966

  19. [19]

    MIT Press, 1998

    Richard S Sutton and Andrew G Barto.Reinforcement learning: An introduction. MIT Press, 1998

    1998

  20. [20]

    Remco Van Der Hofstad.Random graphs and complex networks. Vol. 2. Cambridge university press, 2024. 14

    2024