CIF: AF: Small: A Perturbed Markov Chains Approach to Studying Centrality, Mixing and Reinforcement Learning

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

By their key role in facilitating many modern innovations such as Internet search via the PageRank algorithm or enabling robot movement using reinforcement learning, Markov chains are an important and versatile modeling plus analysis tool. Further examples of applications of Markov chains include algorithms in recommendation engines, simulation of complex systems using Monte-Carlo methods, inference such as community detection in social networks using random walks, and in analyzing configurations for complex systems, such as extent of opinion spread in social networks. The goal of this project is to develop new foundational results on Markov chains using perturbations of them that are easier to analyze and to simulate, with the end result being both a better understanding of the original Markov chain and the development of novel and efficient algorithms for applications, such as in reinforcement learning and other artificial-intelligence paradigms. The project activities center around the development of mathematical tools to analyze key properties such as convergence to the stationary distribution and mixing of Markov chains using their perturbations, and the use these theoretical advances to develop novel estimation algorithms with provable performance guarantees for PageRank estimation and for reinforcement learning. The specific goals are divided into three thrusts. The first will study properties that are preserved in the perturbed chain from the original chain, and any accompanying implications on inference and optimization problems that Markov chains are used for. The second will study the implications of the general results from the first thrust on the PageRank Markov chain along with Personalized PageRank Markov chains, with the emphasis on accurate but low-complexity estimation. Drawing connections between PageRank estimation and reinforcement learning, the third thrust will develop efficient policy-evaluation and policy-iteration methods for general discounted-cost problems. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.