活动回顾 | 邓小铁教授：马尔科夫博弈的近似完美均衡

北京时间2023年4月28日，第八期 AIRS-TNSE 联合杰出讲座系列活动在线上成功举办。此次，我们有幸邀请到北京大学的邓小铁教授介绍基于马尔科夫博弈的近似完美均衡，并分享他在这个领域内的相关研究成果与有趣发现。

本次讲座由 AIRS 副院长兼群体智能中心主任、香港中文大学（深圳）协理副校长、校长讲座教授、IEEE TNSE 主编黄建伟教授担任执行主席和主持人。

马尔科夫博弈与马尔科夫决策过程相类似，支撑了许多人工智能和机器学习的相关研究，虽然其在概念上直截了当，并且不涉及不可信的威胁（比均衡属性更强），但是在马尔科夫博弈中寻找完美均衡仍然非常困难。现有的方法主要研究马尔科夫博弈的特殊情况，或是忽略其动态性质以将研究限制在较弱的纳什均衡概念。邓小铁教授及其合作者针对上述挑战，证明了马尔科夫博弈中近似完美均衡的计算等同于单一状态设置中的纳什均衡，并展示了其 PPAD 难的完备性。

邓小铁教授及其合作者首先在策略概况空间上构造了函数，使每个策略概况都是该函数的不动点，当且仅当它是马尔科夫博弈的完美均衡，通过函数的连续性证明及 Brouwer 不动点定理保证了不动点的存在。随后，通过对该函数的近似属性分析，将目标转换为寻找 Lipschitz 函数的近似不动点。最后，藉由 Papadimitriou 提出的定理证明完成该问题 PPAD 难的完备性。

邓小铁教授的精彩分享发人深思，在参与者与两位教授的积极讨论中，涌现了许多有趣的问题。例如，考虑具有连续动作或状态空间的马尔科夫强化学习；马尔科夫博弈与平均场博弈之间的区别与联系；博弈动态属性在具体场景中的应用等。

视频回顾

Recording

AIRS-TNSE 联合杰出讲座系列

AIRS-TNSE Joint Distinguished Seminar Series

AIRS-TNSE 联合杰出讲座系列由 IEEE TNSE 期刊和深圳市人工智能与机器人研究院（AIRS）联合主办，香港中文大学（深圳）、网络通信与经济学实验室（NCEL）、IEEE 联合支持。该系列活动旨在汇聚网络科学与工程领域的国际顶级专家学者分享前沿科技成果。

*特别鸣谢李想对本文的贡献

相关阅读

IEEE TNSE 杰出讲座系列第七期回顾

IEEE TNSE 杰出讲座系列第六期回顾

IEEE TNSE 杰出讲座系列第五期回顾