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

马尔可夫链在促进许多现代创新方面发挥了关键作用，例如通过PageRank算法进行互联网搜索或使用强化学习实现机器人移动，因此马尔可夫链是一种重要的、通用的建模和分析工具。马尔可夫链的另一个应用实例包括推荐引擎中的算法、使用蒙特卡洛方法模拟复杂系统、使用随机行走进行社交网络中的社区检测之类的推理、以及分析复杂系统的配置(例如社交网络中的意见传播程度)。这个项目的目标是利用马尔可夫链的扰动来开发更容易分析和模拟的新的基础性结果，最终结果是更好地理解原始的马尔可夫链，并为应用开发新的高效算法，例如在强化学习和其他人工智能范例中。项目活动的中心是开发数学工具来分析关键性质，如收敛到平稳分布和使用马尔可夫链的扰动进行混合，并使用这些理论进步来开发具有可证明的性能保证的新估计算法，用于PageRank估计和强化学习。具体目标分为三个推进。第一部分将研究原始链在扰动链中保留的性质，以及马尔可夫链用于推理和优化问题的任何伴随含义。第二部分将研究PageRank马尔可夫链和个性化PageRank马尔可夫链的第一推力的一般结果的含义，重点是准确但低复杂性的估计。利用PageRank估计和强化学习之间的联系，第三个推动力将为一般折扣成本问题开发有效的政策评估和政策迭代方法。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.