Speaker：邓小铁 北京大学
部分图源来自北京大学人工智能学院发布文章
背景
马尔科夫博弈又称随机博弈游戏（也称为Stochastic Game）为多智能体强化学习和顺序智能体交互的研究奠定了基础。我们研究折扣通用和有限状态随机博弈中（近似）马尔科夫完美均衡的计算复杂度，并证明其为PPAD完备问题。这为开发多智能体强化学习算法以与普通纳什均衡计算方式相同地处理通用和有限状态随机博弈开辟了可能性。
其次需要解释一下什么是PPAD？
计算无处不在，任何一门成熟的学科都涉及一些计算问题，在经济学中，这样的概念尤其多。以经济学中的最基本概念“纳什均衡”以及“市场均衡“的计算为例，它们与传统计算机科学中所研究的计算问题存在很大区别：它们不是判定问题，纳什均衡点的存在性是有纳什定理直接保证的；它们也不是优化问题，因为没有一个优化的目标。
从本质上讲，它们是一类不动点的计算问题，所以从传统的NP-Complete（non-deterministic polynomial，非确定多项式完全问题）角度来研究他们的计算复杂度并不合适。为此，美国加州大学伯克利分校的克里斯托斯·帕帕迪米特里欧(Christos Papadimitriou) 教授定义了PPAD（polynomial parityarguments on directed graphs，有向图的多项式校验参数）计算复杂类来描述这类问题，并与其合作者一起证明了在4 人及以上的博弈中，纳什均衡的计算是属于PPAD-Complete 的。哥大的陈汐教授和北大的邓小铁教授把结果加强到二人博弈的纳什均衡的计算也是属于PPAD-Complete 的。（——摘自百度百科）
Main Problem
What is the exact computational complexity to solve Stohcastic Game ?
以下截取了部分讲座的截图，但是其中很多部分我都是浅尝。
该部分介绍了随机博弈游戏的起源在1953年，旨在描述多玩家之间的动态互动。
PPAD具体的背景上面已经提到，是相对NP-hard问题的不同版本。
综述
对于马尔可夫过程的具体理解，还需要多去了解一下。但多智能体博弈这件事情我觉得未来一定也是解决AI学习应用的重要风口。
