Reinforcement Learning for Matrix Computations: PageRank as an Example
This work addresses the need for efficient, distributed matrix computations in web ranking, though it appears incremental as it adapts existing reinforcement learning techniques to a specific application.
The authors tackled the problem of computing PageRank by proposing a reinforcement learning algorithm that is model-free and easily distributed, achieving convergence and demonstrating performance through numerical experiments.
Reinforcement learning has gained wide popularity as a technique for simulation-driven approximate dynamic programming. A less known aspect is that the very reasons that make it effective in dynamic programming can also be leveraged for using it for distributed schemes for certain matrix computations involving non-negative matrices. In this spirit, we propose a reinforcement learning algorithm for PageRank computation that is fashioned after analogous schemes for approximate dynamic programming. The algorithm has the advantage of ease of distributed implementation and more importantly, of being model-free, i.e., not dependent on any specific assumptions about the transition probabilities in the random web-surfer model. We analyze its convergence and finite time behavior and present some supporting numerical experiments.