Linking PageRank, Time Reversal, and Policy Evaluation
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.
Related
- Policy Evaluation and Policy Gradient for Continuous-Time Markov Regime-Switching Systems
- Efficient Best-of-N policy evaluation for inference-time alignment
- Ancestral lineages under horizontal trait transfer: spinal decomposition and time reversal beyond stationarity
- Influence of Time Reversal Invariance Breaking on the Distribution of Off-Diagonal Scattering Matrix Elements and Cross Sections
- PageRank on Lubotzky--Phillips--Sarnak graphs
BibTeX
@misc{avrachenkov2026linking,
title = {{Linking PageRank, Time Reversal, and Policy Evaluation}},
author = {Konstantin Avrachenkov and Lorenzo Gregoris and Nelly Litvak},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.00532},
eprint = {2605.00532},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.00532},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Linking PageRank, Time Reversal, and Policy Evaluation
AU - Konstantin Avrachenkov
AU - Lorenzo Gregoris
AU - Nelly Litvak
PY - 2026
DA - 2026/09/19
PB - arXiv
DO - 10.48550/arxiv.2605.00532
UR - https://arxiv.org/abs/2605.00532
AB - 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.
ER -