多人博弈中的相关学习
本文提出了一种新的算法方法来解决优化一些目标(如社会福利)的相关均衡问题,并且给出了一种适用于所有紧凑表示的足够条件,同时利用该算法方法将最优 CE 问题转化为调整偏差的社会福利问题,这个框架可以识别出新的类别的博弈,其中包括基于树图的图形多项式博弈。同样使用类似的方法,我们导出了一种足够的条件来处理最优粗糙相关均衡问题,并使用其证明了单例拥塞博弈的可跟踪性。
Sep, 2011
本文提出了第一种高效算法用于学习通过较粗的相关均衡 (CCE) 和相关均衡 (CE) 合理化行为的多智能体学习,这些算法的样本复杂度与所有问题参数(包括玩家数量)的多项式成正比,同时还开发了一种新的高效算法来找到一个合理化的行动规划(不一定是均衡),该算法的样本复杂度显著优于现有结果。算法采用了几种新技术来同时保证理性和无择性遗憾,包括相关探索方案和自适应学习速率。
Oct, 2022
通过适应性算法的考虑以确保比修改行为所能达到的结果更好,我们可以基于相关学习动态产生新的博弈理论分析,这样做比基于平衡策略算法更加有效,因为前者可以处理非零和多人博弈问题。我们重新审视了博弈理论中的中介均衡和偏差类型,证明了没有可行的概念包含所有其他类型,并引出了一个追溯与规避策略算法的平衡类别的定义。
Dec, 2020
研究了针对不同类型的协同均衡的最优相关策略问题,提出了相关 DAG 表示方法和双面列生成算法来计算最优策略并探讨其复杂性分析,探究了一些新的基准博弈。
Mar, 2022
本文研究了在完备回忆且 n 个玩家泛化和值和的博弈中,如何从简单无耦合的后悔最小化学习动力学中导出 EFCE。研究结果提供了第一个收敛于 EFCE 的无耦合动力学,为该领域解决了开放性问题。
Apr, 2021
提出了用于训练 n 人,广义和形博弈的 Joint Policy-Space Response Oracles (JPSRO) 算法,并建议一种有前途的元解算程序 -- 相关均衡 (correlated equilibria),并提出了最大基尼相关均衡 (MGCE) 的新解决方案概念。通过使用 CE 元解决程序对 JPSRO 进行多次实验,证明了在 n 人,广义和游戏中的收敛性。
Jun, 2021
本文提出一种针对不完全信息的博弈模式下具有更快学习速度的学习动态方案,并对其进行实验验证。其中,主要技术贡献为通过预测实现加速 Phi-regret 最小化,并通过对于有结构的马尔科夫链的细致扰动分析,表征与之相关的 fixed points 的稳定性。
Feb, 2022
本文探讨了多人博弈中学习的样本复杂性问题,并设计算法在样本复杂度多项式级别下,求解多人一般和马尔可夫博弈的粗略关联均衡和关联均衡,同时提出了针对特定条件下的学习算法,显著提高了现有算法的效率和精度。
Oct, 2021
我们研究了在 n 个玩家一般和游戏中寻找均衡的计算方法,特别是适用于复杂的视觉运动技能。我们展示了现有方法在此场景下要么计算上困难,要么在理论上受限。接着,我们介绍了 NeuPL-JPSRO 算法,一种神经人口学习算法,通过技能的迁移学习,并最终收敛于游戏的粗糙相关均衡 (CCE)。我们在一系列 OpenSpiel 游戏中展示了实证的收敛性,并经由精确的游戏求解器严格验证。然后,我们将 NeuPL-JPSRO 应用于复杂领域,在 MuJoCo 控制领域实现了自适应协调和技能迁移。我们的工作表明,收敛于均衡的人口学习可以在规模上和广泛性上实施,为解决异质玩家和混合动机的现实世界游戏铺平了道路。
Jan, 2024