Linking PageRank, Time Reversal, and Policy Evaluation

Konstantin Avrachenkov, Lorenzo Gregoris, Nelly Litvak

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 discount…