Linking PageRank, Time Reversal, and Policy Evaluation

1. Problem Statement

The paper addresses the computational bottleneck of Policy Evaluation in Markov Decision Processes (MDPs). Given a fixed policy $\pi$, the goal is to compute the value function $v_\pi$, which represents the expected cumulative discounted reward starting from each state.

• Current Challenge: In large-scale problems, the state space is massive, and the transition matrix is often sparse and non-symmetric. Solving the Bellman equation (a linear system) using standard methods (e.g., Gauss-Seidel, prioritized sweeping) can be computationally expensive.
• Parallel Field: In network science, PageRank is a highly optimized method for computing stationary distributions of random walks with restarts on massive graphs.
• Core Question: Can the problem of policy evaluation be mathematically mapped to PageRank computation, thereby allowing the use of efficient PageRank solvers for MDPs?

2. Methodology

The authors establish a rigorous mathematical correspondence between the value function of a discounted MDP and the PageRank vector of a time-reversed Markov chain.

A. Irreducible MDPs (The Core Correspondence)

For an irreducible policy-induced Markov chain with transition matrix $P_\pi$, stationary distribution $\mu$, discount factor $\gamma$, and reward vector $r$:

1. Time Reversal: The authors define the time-reversed transition matrix $P^*_\pi = D^{-1} P_\pi^\top D$, where $D = \text{diag}(\mu)$.
2. Mapping Parameters:
   • The discount factor $\gamma$ in the MDP corresponds to the teleportation parameter (restart probability) in PageRank.
   • The reward vector $r$ determines the restart distribution $u$ for the PageRank problem, defined as $u(s) \propto r(s)\mu(s)$.
3. Result: The value function $v_\pi(s)$ is proportional to the PageRank vector $w(s)$ of the time-reversed chain:
   $$v_\pi(s) = \frac{\langle r \rangle_\mu}{1 - \gamma} \frac{w(s)}{\mu(s)}$$
   where $\langle r \rangle_\mu$ is the expected reward under the stationary distribution.

B. General MDPs (Decomposition Theorem)

Real-world MDPs often have reducible chains with transient and recurrent classes. The authors prove a decomposition theorem:

• Recurrent Classes: The value function is computed exactly as in the irreducible case using the stationary distribution.
• Transient Classes: Since transient chains do not have a stationary distribution, the authors utilize Quasi-Stationary Distributions (QSD) and Doob $h$-transforms.
  • They transform the substochastic transition matrix of a transient class into a stochastic matrix via the Doob transform.
  • The value function on transient states is expressed as a PageRank problem on the time-reversed Doob-transformed chain, where the teleportation parameter becomes $\gamma \lambda$ (with $\lambda$ being the spectral radius of the transient submatrix).

C. Undiscounted MDPs

The framework extends to undiscounted MDPs ($\gamma=1$) with terminal (absorbing) states. In this limit, the PageRank formulation remains valid, with the teleportation parameter determined by the spectral properties of the transient dynamics.

3. Key Contributions

1. Theoretical Unification: The paper establishes a formal duality between policy evaluation (solving $(I - \gamma P)v = r$) and PageRank (solving $w = \gamma w P^* + (1-\gamma)u$) via time reversal.
2. General Decomposition: It provides a general theorem reducing policy evaluation for arbitrary finite MDPs (including reducible and transient cases) to a collection of independent PageRank problems on communicating classes.
3. Algorithmic Repurposing: It demonstrates that the vast library of scalable PageRank algorithms (e.g., Power Iteration, Coordinate Updates, Monte Carlo) can be directly applied to solve Bellman equations.
4. Numerical Validation: The authors implement the RLGL (Red-Light-Green-Light) algorithm—a state-of-the-art coordinate-update PageRank solver—to solve policy evaluation problems.

4. Results

The authors conducted numerical experiments on a "sticky random walk" control problem on large graphs (Preferential Attachment, Erdős–Rényi, and 2D Grids with $10^5$ nodes).

• Comparison: They compared the RLGL PageRank solver against standard policy evaluation methods: Gauss-Seidel and Prioritized Sweeping.
• Performance:
  • The RLGL-GSD (Green-Light-Red-Light with GSD heuristic) algorithm consistently reduced the Bellman residual faster than the other methods when measured by normalized iterations (cumulative edges processed).
  • In reversible settings (where time reversal is trivial), the policy evaluation problem reduced to a single PageRank computation, showing significant efficiency gains.
• Conclusion: PageRank-based coordinate solvers are highly effective Bellman solvers, particularly for large-scale, sparse, and reversible systems.

5. Significance and Implications

• Computational Efficiency: By reframing policy evaluation as a PageRank problem, researchers can leverage decades of optimization in network analysis to accelerate dynamic programming and reinforcement learning.
• Scalability: This approach is particularly promising for massive state spaces where traditional linear solvers struggle with memory or convergence speed.
• New Research Directions: The paper opens several avenues for future work:
  • Applying these methods to irreversible MDPs (where time reversal is non-trivial).
  • Integrating PageRank-inspired coordinate methods into modern Deep Reinforcement Learning frameworks.
  • Investigating whether RL agents can learn time-reversed dynamics to guide exploration and policy improvement.

In summary, the paper provides a profound theoretical link between two distinct fields (MDPs and Network Analysis) and offers a practical, high-performance alternative for solving one of the fundamental subroutines in reinforcement learning.