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

CIF：AF：小：研究中心性、混合和强化学习的扰动马尔可夫链方法

• 批准号: 2008130
• 负责人: Vijay Subramanian
• 金额: $ 35.06万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-01 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2008130&HistoricalAwards=false
• 关键词: CIF; AF; Small; Perturbed; Markov

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.

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

项目成果

A Strong Duality Result for Cooperative Decentralized Constrained POMDPs

合作分散约束 POMDP 的强对偶结果

• 发表时间: 2023-12
• 期刊: Proceedings of the IEEE Conference on Decision Control
• 作者: Nouman Khan and Vijay Subramanian

On the Benefits of Being Constrained When Receiving Signals

关于接收信号时受到约束的好处

• DOI: 10.1007/978-3-030-94676-0_10
• 发表时间: 2022-01
• 期刊: Web and Internet Economics. WINE 2021. Lecture Notes in Computer Science(
• 作者: Su, ST.;Kempe, D.;Subramanian, V.G.
• 通讯作者: Subramanian, V.G.

Common Information based Approximate State Representations in Multi-Agent Reinforcement Learning

多智能体强化学习中基于公共信息的近似状态表示

• 发表时间: 2022-01
• 期刊: Spain. PMLR
• 作者: Kao, Hsu;Subramanian;Vijay
• 通讯作者: Vijay

Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space

可数无限状态空间马尔可夫决策过程中最优策略的贝叶斯学习

• 发表时间: 2023-12
• 期刊: Advances in Neural Information Processing Systems 36 (NeurIPS 2023
• 作者: Saghar Adler;Vijay Subramanian
• 通讯作者: Vijay Subramanian

Private Information Compression in Dynamic Games among Teams

团队动态博弈中的私有信息压缩

• DOI: 10.1109/cdc45484.2021.9683479
• 发表时间: 2021-01
• 期刊: 2021 60th IEEE Conference on Decision and Control (CDC
• 作者: Tang, Dengwang;Tavafoghi, Hamidreza;Subramanian, Vijay;Nayyar, Ashutosh;Teneketzis, Demosthenis
• 通讯作者: Teneketzis, Demosthenis