广义和粗糙相关均衡的更快无悔学习动态

AAAIFeb, 2022

广义和粗糙相关均衡的更快无悔学习动态

Faster No-Regret Learning Dynamics for Extensive-Form Correlated and Coarse Correlated Equilibria

Ioannis Anagnostides, Gabriele Farina, Christian Kroer, Andrea Celli, Tuomas Sandholm

TL;DR本文提出一种针对不完全信息的博弈模式下具有更快学习速度的学习动态方案，并对其进行实验验证。其中，主要技术贡献为通过预测实现加速 Phi-regret 最小化，并通过对于有结构的马尔科夫链的细致扰动分析，表征与之相关的 fixed points 的稳定性。

Abstract

A recent emerging trend in the literature on learning in games has been concerned with providing faster learning dynamics for correlated and coarse correlated equilibria in normal-form games. Much less is known about the significantly more challenging setting of extensive-form games, which can capture both sequential and simultaneous moves, as well as imperf

extensive-form correlated equilibria imperfect-information games phi-regret minimization trigger deviation functions coarse correlated equilibrium

发现论文，激发创造

广义博弈中简单非耦合无悔学习动态

本文研究了在完备回忆且 n 个玩家泛化和值和的博弈中，如何从简单无耦合的后悔最小化学习动力学中导出 EFCE。研究结果提供了第一个收敛于 EFCE 的无耦合动力学，为该领域解决了开放性问题。

Apr, 2021

博弈论中的粗略相关性

本文通过介绍粗糙相关性和其在博弈理论中的应用，着重研究了粗糙相关性在博弈模型中的实际意义，并提出了一种新的算法，使得博弈模型的求解更加高效。

Aug, 2019

广义型博弈中的相关性：鞍点公式和基准模型

本文提出了一种新的算法来计算具有广泛相关性平衡的解，该算法基于一个新的双线性鞍点问题的解。此外，我们还介绍了两个基准游戏，探究冲突解决和协商领域中的广泛相关性平衡的质量特征。

May, 2019

广义积和博弈中的最优相关均衡：固定参数算法，难度和双向列生成

研究了针对不同类型的协同均衡的最优相关策略问题，提出了相关 DAG 表示方法和双面列生成算法来计算最优策略并探讨其复杂性分析，探究了一些新的基准博弈。

Mar, 2022

多人随机博弈中的学习

本文研究多人随机博弈中同时学习的问题，通过生成算法获得相关均衡，包括 extensive-form correlated equilibrium 和普通 coarse correlated equilbrium，并提供了一些能够多项式时间内解决的特殊情况。

Oct, 2022

$\widetilde {O}(T^{-1})$ 在全信息 General-Sum Markov Games 中收敛到（粗糙）相关均衡

使用乐观跟随正则化领导者算法结合适当的价值更新过程，在全信息一般和马尔可夫博弈中找到近似于 O (T^-1) 粗糙相关均衡。

Feb, 2024

多人零和游戏中相关均衡的几乎最优无悔学习

提出了新的技术，将 DFG 的技术用于解决内部遗憾和交换遗憾，从而使得多人游戏中的学习动态能够收敛到近似相关均衡，同时分析了 Blum 和 Mansour 算法中的近似最优遗憾保证。

Nov, 2021

不完全信息博弈中近似（粗糙）相关均衡的复杂性

我们研究了不完全信息博弈中分布式学习近似相关均衡的迭代复杂度，我们证明了在广义形式博弈中，假设 PPAD 不属于 TIME (n^polylog (n))，任何多项式时间学习算法至少需要 2^log_2^{1-o (1)}(|I|) 次迭代才能收敛于 ε- 近似相关均衡集合，同时我们给出了无耦合动态的方法，在对数次迭代中达到 ε- 近似相关均衡的贝叶斯博弈，无需考虑类型的数量。

Jun, 2024

多人博弈中的相关学习

该论文研究了多人游戏中，玩家间某种形式的通信建模的解概念，着重探讨了顺序博弈中的粗糙相关均衡（CCEs）并提出了 CFR 及其变体算法，其中 CFR-Jr 的效率比 CFR-S 和当前最先进的计算 CCEs 算法都要快且可行。

Oct, 2019

寻找任何非平凡的粗糙相关均衡是困难的

本文介绍了关于粗略相关均衡的研究，讨论了算法和动态模型在多人博弈中的适用性，并给出了相应的数学模型和贡献。

Apr, 2015