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.