Jun, 2024

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

PDF
TL;DR我们研究了不完全信息博弈中分布式学习近似相关均衡的迭代复杂度，我们证明了在广义形式博弈中，假设 PPAD 不属于 TIME (n^polylog (n))，任何多项式时间学习算法至少需要 2^log_2^{1-o (1)}(|I|) 次迭代才能收敛于 ε- 近似相关均衡集合，同时我们给出了无耦合动态的方法，在对数次迭代中达到 ε- 近似相关均衡的贝叶斯博弈，无需考虑类型的数量。
decentralized learningcorrelated equilibriaincomplete information gamesextensive-form gamesbayesian game
发现论文，激发创造
  • 寻找任何非平凡的粗糙相关均衡是困难的

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

    Apr, 2015

  • 具有不完全信息的广义博弈的近最优学习

    本文提出两种新算法：平衡在线镜像下降和平衡对策后悔最小化，通过整合平衡探索策略到它们的经典对应物算法，解决学习不完美信息的广义零和游戏的近似 Nash 均衡问题。同时，将结果推广到学习多人游戏的粗略相关均衡。

    Feb, 2022

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

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

    Feb, 2022

  • 相关均衡的查询复杂度

    该论文研究了在一个允许算法在纯策略配置上查询玩家收益的模型中寻找 $n$ 个玩家博弈的相关均衡的复杂性，结果表明随机规避后悔的动态算法可以高效地得出近似相关均衡，但确切相关均衡需要更多的回报查询（随机算法瓶颈）并无法使用高效的确定性算法（因为查询次数下限）。

    May, 2013

  • 紧凑博弈中计算最优相关均衡的通用框架

    本文提出了一种新的算法方法来解决优化一些目标（如社会福利）的相关均衡问题，并且给出了一种适用于所有紧凑表示的足够条件，同时利用该算法方法将最优 CE 问题转化为调整偏差的社会福利问题，这个框架可以识别出新的类别的博弈，其中包括基于树图的图形多项式博弈。同样使用类似的方法，我们导出了一种足够的条件来处理最优粗糙相关均衡问题，并使用其证明了单例拥塞博弈的可跟踪性。

    Sep, 2011

  • 多人随机博弈中的学习

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

    Oct, 2022

  • 广义和马尔可夫博弈中相关均衡的近最优策略优化

    我们研究了多人广义和 Markov 游戏中计算相关均衡的政策优化算法，以往结果在收敛速率上达到了 $O (T^{-1/2})$ 的相关均衡和 $O (T^{-3/4})$ 的粗糙相关均衡的加速收敛速率，本文提出了一种通过组合平滑值更新和乐观正则化领导者算法与对数障碍正则器的两个主要因素构建的解耦政策优化算法，达到了计算相关均衡的几乎最优 $ ilde {O}(T^{-1})$ 的收敛速率。

    Jan, 2024

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

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

    Feb, 2024

  • 马尔可夫博弈中独立学习和稀疏均衡计算的难度

    本文研究了去中心化多智能体强化学习问题中的不后悔算法，并探讨了自主学习能否在标准 Markov 博弈框架中实现无后悔学习。结果表明，无论是已知还是未知的博弈，该问题都无法以多项式时间实现无后悔学习，该文贡献了理论证明支持，提出了基于集聚方法的创新性应用，并发现了 SparseCCE 问题的下限，从而说明了近年来学者对于该问题的研究成果，并对博弈理论和强化学习算法研究方向提出了新的思考。

    Mar, 2023

  • 不完全回忆博弈：均衡概念及其复杂性

    通过研究不完全记忆下的最优决策问题，我们分析了广义形式博弈中多个解概念（纳什均衡、基于证据决策理论的多个自体以及基于因果决策理论的多个自体）下，在多人情景中寻找均衡的计算复杂性，同时关注精确和近似解的计算。我们将单人游戏、两人零和游戏与最小最大值以及没有外在随机性（几率节点）的游戏作为特例，并将这些问题与复杂性类 P、PPAD、PLS、Σ₂ᴾ、∃R 和∃∀R 联系起来。

    Jun, 2024