Bayes相关均衡和无悔动态
本文研究了no-regret动力学中最常被考虑的动态系统之一 - Follow-the-regularized-leader的行为,证明了非严格的纳什均衡对于no-regret学习是不稳定的且不能吸引该动态系统的稳定状态,因此只有严格的纳什均衡是no-regret动力学的稳定限制点。
Oct, 2020
本文研究了在完备回忆且n个玩家泛化和值和的博弈中,如何从简单无耦合的后悔最小化学习动力学中导出EFCE。研究结果提供了第一个收敛于EFCE的无耦合动力学,为该领域解决了开放性问题。
Apr, 2021
提出了新的技术,将DFG的技术用于解决内部遗憾和交换遗憾,从而使得多人游戏中的学习动态能够收敛到近似相关均衡,同时分析了Blum和Mansour算法中的近似最优遗憾保证。
Nov, 2021
研究了针对不同类型的协同均衡的最优相关策略问题,提出了相关DAG表示方法和双面列生成算法来计算最优策略并探讨其复杂性分析,探究了一些新的基准博弈。
Mar, 2022
本文提出了一个简单而计算高效的算法,能够在多项对数轮内获得ε T-swap遗憾,这在与现有算法相比的超线性轮次要求下,是一种指数级的改进,并解决了“Blum and Mansour 2007”中的主要未解决问题。同时该算法对ε有指数级依赖,但我们证明了一个新的,相匹配的下界。
Oct, 2023
使用乐观跟随正则化领导者算法结合适当的价值更新过程,在全信息一般和马尔可夫博弈中找到近似于O(T^-1)粗糙相关均衡。
Feb, 2024
我们研究了不完全信息博弈中分布式学习近似相关均衡的迭代复杂度,我们证明了在广义形式博弈中,假设PPAD不属于TIME(n^polylog(n)),任何多项式时间学习算法至少需要2^log_2^{1-o(1)}(|I|)次迭代才能收敛于ε-近似相关均衡集合,同时我们给出了无耦合动态的方法,在对数次迭代中达到ε-近似相关均衡的贝叶斯博弈,无需考虑类型的数量。
Jun, 2024
本研究探讨了在正规形式博弈中,缩小后悔的迭代次数以达到相关均衡(CE)的问题。作者提出了现有学习算法(如乘法权重更新)接近最优的证据,并证明了计算均匀混合的T个产品分布的CE的下界,这些结果为基于算法的后悔最小化方案提供了重要限制,可能影响相关算法的设计与优化。
Nov, 2024
本研究针对在无悔学习中如何达到均衡的问题,提出了对两人(一般总和)博弈中计算下界的首次探讨,强调了所需迭代次数。研究者通过证明计算近似最优 $T$ 稀疏协调均衡的下界,从而限制了无悔学习的迭代复杂性,并表明最大团的不可近似性阻碍了在多项式时间内实现任何非平凡稀疏化的可能性。
Nov, 2024