Jan, 2024

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

PDF
TL;DR我们研究了多人广义和 Markov 游戏中计算相关均衡的政策优化算法，以往结果在收敛速率上达到了 $O (T^{-1/2})$ 的相关均衡和 $O (T^{-3/4})$ 的粗糙相关均衡的加速收敛速率，本文提出了一种通过组合平滑值更新和乐观正则化领导者算法与对数障碍正则器的两个主要因素构建的解耦政策优化算法，达到了计算相关均衡的几乎最优 $ ilde {O}(T^{-1})$ 的收敛速率。
policy optimization algorithmscorrelated equilibriamulti-player general-sum markov gamesconvergence ratecoarse correlated equilibrium
发现论文，激发创造
  • $\widetilde {O}(T^{-1})$ 在全信息 General-Sum Markov Games 中收敛到（粗糙）相关均衡

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

    Feb, 2024

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

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

    Feb, 2020

  • 针对两人零和线性混合马尔可夫游戏的近乎最优算法

    文章介绍了一种基于乐观不确定性的算法 Nash-UCRL，在找到粗略相关均衡的情况下，可以有效地找到两个玩家的纳什均衡，并证明了其上界和下界的一致性，提出了一种解决有限状态下博弈问题的方法。

    Feb, 2021

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

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

    Jul, 2022

  • 马尔科夫博弈中的离线学习和一般函数逼近

    研究离线多智体强化学习在马尔科夫博弈中学习近似均衡，提供适用于一般函数逼近的新框架以处理所有三种均衡，此框架利用 Bellman 一致压缩和数据覆盖条件，与之前的算法框架相比，其保证更好且能够处理更广泛的情况。

    Feb, 2023

  • 零和马尔可夫博弈中政策优化的更快收敛

    本文提出了一种基于 OMWU 方法的单环路政策优化算法，并在二人零和马尔可夫博弈中，通过控制正则化的程度，实现了有限时间的最后一次线性收敛到达量子响应均衡点，并在全信息离散设置中实现了收敛结果。

    Oct, 2022

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

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

    Sep, 2011

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

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

    Sep, 2022

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

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

    Nov, 2021

  • 具有单一控制器的多人马尔可夫博弈中的乐观策略梯度：超越 Minty 属性的收敛

    在这篇论文中，我们提出了一个新的框架来描述多人 Markov 游戏中的乐观策略梯度方法，在单个控制器下收敛到稳定的 ε-NE，其收敛速度为 O (1/ε^2) 次迭代，该框架基于对经典 Minty 性质的自然推广，我们相信它在 Markov 游戏之外也有进一步的应用。

    Dec, 2023