关于虚拟博弈收敛性问题的分解方法研究
研究了一种基于深度虚假博弈算法的高效工具,来寻找大型 N 玩家随机微分博弈的马尔可夫纳什平衡,并提出了一种新的游戏解耦方法,证明了算法的收敛性,并且在理论假设之外的情况下,提出了大人口游戏的数值结果。
Aug, 2020
Fictitious play, proposed by Brown and shown to converge by Robinson, may not converge at rate O(1/sqrt{t}) as conjectured by Karlin when the payoff matrix of the row player is the identity matrix, but instead may converge as slow as omega(t^-1/n).
Dec, 2014
本文研究了虚拟博弈在寻找二人博弈的纳什均衡时的表现,证明虚拟博弈无法找到一个加法近似保证显著优于 1/2 的解。我们的结论适用于 2 人游戏并且玩家的得分在 [0,1] 范围内。
Mar, 2011
本文提出了一种深度学习方法 —— 深度虚拟博弈,并应用于计算有限非零和随机微分博弈的纳什均衡,在每个阶段让各个博弈者优化自己的收益,用深度神经网络进行近似求解,基于虚拟博弈策略的深度学习算法具有可扩展性、并行性和模型无关性,并证明了在适当的假设下虚拟博弈收敛于开环纳什均衡。
Mar, 2019
该研究开发了一种新算法,名为 Fictitious Cross-Play(FXP),同时训练了基于自我博弈和交叉博弈的主策略和反应策略,并在矩阵游戏中证明了 FXP 能够收敛到全局纳什均衡点,而自我博弈方法则无法达到。
Oct, 2023
本文介绍了一种类似于虚构判断游戏的学习过程用于求解 Mean Field Game 系统,并证明了该方法在 Mean Field Game 系统为 potential 时的收敛性。
Jul, 2015
本文分析了连续时间虚拟博弈学习算法在各种有限状态均场博弈设置(有限时间,折扣率 γ)中的应用,提供了一个新的学习动态来解决平均场博弈模型中存在共同噪声的最优解问题。
Jul, 2020
我们介绍了一种简单的广义形式虚拟博弈算法,用于寻找二人零和游戏的均衡点,该算法实现等价于 Fictitious Play 的广义形式。与类似的广义形式虚拟博弈算法和反事实遗憾最小化算法相比,我们比较了其性能。这三种算法在减少存储需求和计算复杂度方面具有相同的优势,该新算法直观且容易实现,是寻求快速且简便的游戏求解工具的一个吸引人的选择。
Oct, 2023
通过策略初始化来减少虚拟博弈中的均衡近似误差,其中最具优势的方法是用 maximin 求解非凸二次规划,与传统方法相比,使用 5 种初始化的情况下,可以将近 75%的近似误差降低。
Mar, 2022
本文提出了一种名为 “Exploitability Descent” 的新算法,通过直接针对最坏情况的对手进行策略优化,计算具有不完全信息的两人零和博弈的近似均衡。我们证明,当遵循此优化时,玩家策略的可利用性会渐近地收敛于零,因此当两个玩家同时使用此优化时,联合策略会收敛于纳什均衡。与虚拟实现(XFP)和反事实后悔(CFR)不同,我们的收敛结果涉及到被优化的策略而不是平均策略。我们的实验在纸面上就达到了 XFP 和 CFR 相当的收敛速率,利用函数逼近,我们发现我们的算法在两个游戏中优于纸面情况,这是在此类算法中不完全信息游戏中的首个结果。
Mar, 2019