当前位置:首页> AI教程> 马尔科夫博弈与PPAD计算复杂度解析

马尔科夫博弈与PPAD计算复杂度解析

释放双眼,带上耳机,听听看~!
本文介绍了马尔科夫博弈及其与PPAD计算复杂度的关系,探讨了多智能体强化学习的应用前景,是AI学习和应用的重要领域之一。

Speaker:邓小铁 北京大学

部分图源来自北京大学人工智能学院发布文章

背景

马尔科夫博弈又称随机博弈游戏(也称为Stochastic Game)为多智能体强化学习和顺序智能体交互的研究奠定了基础。我们研究折扣通用和有限状态随机博弈中(近似)马尔科夫完美均衡的计算复杂度,并证明其为PPAD完备问题。这为开发多智能体强化学习算法以与普通纳什均衡计算方式相同地处理通用和有限状态随机博弈开辟了可能性。

马尔科夫博弈与PPAD计算复杂度解析

其次需要解释一下什么是PPAD?

计算无处不在,任何一门成熟的学科都涉及一些计算问题,在经济学中,这样的概念尤其多。以经济学中的最基本概念“纳什均衡”以及“市场均衡“的计算为例,它们与传统计算机科学中所研究的计算问题存在很大区别:它们不是判定问题,纳什均衡点的存在性是有纳什定理直接保证的;它们也不是优化问题,因为没有一个优化的目标。

马尔科夫博弈与PPAD计算复杂度解析

从本质上讲,它们是一类不动点的计算问题,所以从传统的NP-Complete(non-deterministic polynomial,非确定多项式完全问题)角度来研究他们的计算复杂度并不合适。为此,美国加州大学伯克利分校的克里斯托斯·帕帕迪米特里欧(Christos Papadimitriou) 教授定义了PPAD(polynomial parityarguments on directed graphs,有向图的多项式校验参数)计算复杂类来描述这类问题,并与其合作者一起证明了在4 人及以上的博弈中,纳什均衡的计算是属于PPAD-Complete 的。哥大的陈汐教授和北大的邓小铁教授把结果加强到二人博弈的纳什均衡的计算也是属于PPAD-Complete 的。(——摘自百度百科)

马尔科夫博弈与PPAD计算复杂度解析

Main Problem

What is the exact computational complexity to solve Stohcastic Game ?
以下截取了部分讲座的截图,但是其中很多部分我都是浅尝。

马尔科夫博弈与PPAD计算复杂度解析
该部分介绍了随机博弈游戏的起源在1953年,旨在描述多玩家之间的动态互动。

马尔科夫博弈与PPAD计算复杂度解析
PPAD具体的背景上面已经提到,是相对NP-hard问题的不同版本。

马尔科夫博弈与PPAD计算复杂度解析

马尔科夫博弈与PPAD计算复杂度解析

综述

对于马尔可夫过程的具体理解,还需要多去了解一下。但多智能体博弈这件事情我觉得未来一定也是解决AI学习应用的重要风口。

本网站的内容主要来自互联网上的各种资源,仅供参考和信息分享之用,不代表本网站拥有相关版权或知识产权。如您认为内容侵犯您的权益,请联系我们,我们将尽快采取行动,包括删除或更正。
AI教程

昇腾 auto tune 操作指南

2023-12-15 15:06:14

AI教程

使用PaddleNLP和Hugging Face Space训练模型并上传至Huggingface

2023-12-15 15:23:14

个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索