不完全信息博弈中近似（粗糙）相关均衡的复杂性
内容提要
本文探讨了粗略相关均衡的研究，提出了新算法以解决多人博弈中的近似Nash均衡问题，并分析了不完全信息博弈的学习动态。研究发现，随机算法在复杂性上存在瓶颈，而无后悔学习在多智能体强化学习中无法实现多项式时间的收敛。
延伸解读
近似相关均衡的算法进展
文章梳理了求解近似相关均衡的多种算法。平衡在线镜像下降和平衡对策后悔最小化通过整合平衡探索策略，解决了广义零和博弈的近似Nash均衡问题，并推广到多人博弈的粗略相关均衡。此外，解耦政策优化算法结合平滑值更新与乐观正则化领导者算法，在马尔可夫博弈中达到了几乎最优的收敛速率。这些进展表明，针对不同博弈结构设计专门算法是提升效率的关键。
精确与近似均衡的查询复杂度差异
在允许查询纯策略收益的模型中，随机规避后悔的动态算法能高效得到近似相关均衡，但精确相关均衡需要更多查询，且不存在高效确定性算法，因为查询次数存在下限。这揭示了近似与精确求解在计算复杂度上的本质区别，也说明随机算法在精确求解上存在瓶颈。对于大量玩家的二元行动博弈，查询复杂度与ε-支持纳什均衡的关系是指数级的，导致自适应动态收敛速度指数级下降。
无后悔学习在去中心化多智能体强化学习中的局限
文章指出，在去中心化多智能体强化学习中，无后悔学习无法在多项式时间内实现。无论是已知还是未知的博弈，在标准马尔可夫博弈框架下，该问题均无法以多项式时间实现无后悔学习。这一结论基于理论证明，并发现了SparseCCE问题的下限。这意味着，尽管无后悔学习在单智能体场景中有效，但在多智能体去中心化设定下，其计算复杂性构成了根本性障碍，需要新的算法思路。
最优相关均衡的算法框架与可跟踪性
文章提出了一种新的算法方法来解决优化社会福利等目标的相关均衡问题，并给出了适用于所有紧凑表示的足够条件。该框架将最优CE问题转化为调整偏差的社会福利问题，能识别出新的博弈类别，包括基于树图的图形多项式博弈。类似方法也用于处理最优粗糙相关均衡问题，并证明了单例拥塞博弈的可跟踪性。这为在特定博弈中高效计算最优均衡提供了理论工具。
Q&A
什么是粗略相关均衡？
粗略相关均衡是一种博弈理论中的均衡概念，适用于不完全信息的博弈，允许玩家在不完全了解其他玩家策略的情况下进行决策。
本文提出了哪些新算法来解决近似Nash均衡问题？
本文提出了平衡在线镜像下降和平衡对策后悔最小化两种新算法，旨在解决不完美信息的广义零和游戏中的近似Nash均衡问题。
不完全信息博弈的学习动态有什么新发现？
研究发现，随机算法在复杂性上存在瓶颈，而无后悔学习在多智能体强化学习中无法实现多项式时间的收敛。
如何优化社会福利的相关均衡问题？
通过提出一种新的算法方法，将最优相关均衡问题转化为调整偏差的社会福利问题，从而优化社会福利。
在多人随机博弈中，如何同时学习相关均衡？
通过生成算法，可以在多人随机博弈中获得相关均衡，包括广泛形式的相关均衡和普通粗略相关均衡。
去中心化多智能体强化学习中的不后悔算法有什么限制？
研究表明，无论是已知还是未知的博弈，去中心化多智能体强化学习中的不后悔学习无法以多项式时间实现。
