Feb, 2024

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

HTML
PDF
TL;DR使用乐观跟随正则化领导者算法结合适当的价值更新过程，在全信息一般和马尔可夫博弈中找到近似于O(T^-1)粗糙相关均衡。
发现论文，激发创造
  • 零和博弈中快速且强烈学习：在非消失步长时消失后悔

    我们展示了一种称为"Fast and Furious"的学习方法，使得在二人零和博弈中时间平均遗憾减少且步长不为零成为可能，此学习方法为最小化-最大化优化和多智能体系统中的研究提供了新的标杆，即使是在最简单的情况下，我们的研究证明该方法的遗憾界限为$\Theta(\sqrt{T})$，在学习率固定的情况下也会稳定收敛于确切的纳什均衡价值。

    May, 2019

  • 使用函数逼近和相关均衡学习零和同时行动马尔可夫博弈

    本研究针对具有线性结构的两人零和有限马尔可夫博弈提出了一种基于乐观价值迭代的增强学习算法，该算法通过构建价值函数的上下置信区间，并用 Coarse Correlated Equilibrium 求解泛化和纳什均衡问题，实现了性能的总时间平方根复杂度的上限。

    Feb, 2020

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

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

    Apr, 2021

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

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

    Oct, 2021

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

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

    Nov, 2021

  • 一般和式马尔可夫博弈的遗憾最小化和均衡收敛

    简而言之，本文提出了一种针对广义和博弈的、分散、计算高效的算法，其保证所有代理都使用时可以提供次线性遗憾保证，并且不需要代理之间的通信。该算法的主要观察结果是，通过马尔可夫游戏的在线学习基本上可以归结为一种加权遗憾最小化。

    Jul, 2022

  • $O(T^{-1})$ 乐观正则化领导者策略在双人零和马尔科夫博弈中的收敛性

    证明了在Markov博弈中，基于乐观的Follow-the-Regularized-Leader (OFTRL)算法的平滑值更新，可在T次迭代中找到$O(T^{-1})$的近似Nash均衡，该算法的关键改进是通过紧化OFTRL权重的代数不等式，使竞争者的遗憾之和大致是非负的，使得学习动态的二阶路径长度被限制，最终实现了$O(T^{-1})$的收敛速率提高。

    Sep, 2022

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

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

    Mar, 2023

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

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

    Jan, 2024

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

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

    Nov, 2024