Oct, 2022

多人游戏中学习可理性均衡

HTML
PDF
TL;DR本文提出了第一种高效算法用于学习通过较粗的相关均衡(CCE)和相关均衡(CE)合理化行为的多智能体学习，这些算法的样本复杂度与所有问题参数（包括玩家数量）的多项式成正比，同时还开发了一种新的高效算法来找到一个合理化的行动规划（不一定是均衡），该算法的样本复杂度显著优于现有结果。算法采用了几种新技术来同时保证理性和无择性遗憾，包括相关探索方案和自适应学习速率。
发现论文，激发创造
  • 多智能体竞赛中的探索-利用：有界理性下的收敛

    通过研究充分考虑游戏奖励和探索成本平衡的原型学习模型Q-learning，我们证明在使用积极探索率的具有异质性学习代理的权重零和多元矩阵游戏中，Q-learning总是收敛于唯一的量刑-反应均衡（QRE），这是有界理性下游戏的标准解决方案概念，并展示了 Q-learning 在竞争环境中的快速收敛性，而无需任何参数微调，在竞争多代理环境中的均衡选择问题提供了算法所需的保证。

    Jun, 2021

  • 何时才能高效学习具有多个玩家的广义和马尔可夫博弈？

    本文探讨了多人博弈中学习的样本复杂性问题, 并设计算法在样本复杂度多项式级别下, 求解多人一般和马尔可夫博弈的粗略关联均衡和关联均衡, 同时提出了针对特定条件下的学习算法, 显著提高了现有算法的效率和精度。

    Oct, 2021

  • 去中心化一般和马尔可夫博弈中具有可证明效率的强化学习

    本文提出了一种多智能体强化学习算法，可以在一般和马尔可夫博弈中学习到一个粗略的相关均衡策略，并且算法是完全分散的，智能体只有本地信息，并不知道其他智能体的存在。

    Oct, 2021

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

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

    Nov, 2021

  • 随机博弈中的马尔科夫均衡复杂性

    本文研究了Markov粗粒度关联均衡问题的计算复杂性及其在多智能体强化学习中的应用，发现当多智能体交互为回合制、折扣因子和粗略程度为常数时，计算近似的Markov粗粒度关联均衡策略属于NP难问题，但是提供了在多智能体中非稳定Markov CCE策略的学习解决方案。

    Apr, 2022

  • 多人随机博弈中的学习

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

    Oct, 2022

  • 学习马尔可夫博弈中基于密度相关均衡的策略

    本文提出了基于状态密度的相关均衡（DBCE），它是一种新的CE概念，可以更好地满足代理协调和实际应用的安全性和公平性的需求，并通过实验表明了其在状态密度问题场景下的优越性。

    Feb, 2023

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

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

    Feb, 2024

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

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

    Jun, 2024

  • 正规形式博弈中后悔最小化的计算下界

    本研究探讨了在正规形式博弈中，缩小后悔的迭代次数以达到相关均衡（CE）的问题。作者提出了现有学习算法（如乘法权重更新）接近最优的证据，并证明了计算均匀混合的T个产品分布的CE的下界，这些结果为基于算法的后悔最小化方案提供了重要限制，可能影响相关算法的设计与优化。

    Nov, 2024