解决博弈中的高效收敛算法
通过在线学习的自我对弈是解决大规模两人零和游戏的主要方法之一,尤其流行的算法包括乐观的乘积权重更新(OMWU)和乐观的梯度下降 - 梯度上升(OGDA),本文证明了 OMWU 存在潜在的较慢的最后迭代收敛问题。
Jun, 2024
本文研究了基于遗憾的算法在连续游戏中寻找近似的纳什均衡,针对反事实遗憾最小化(CFR)算法存在的表示收敛的缺陷,提出了一些基于树形复合结构的乐观遗憾最小化算法,并给出了实验证明其在求解连续游戏时的有效性。
Jun, 2021
研究了基于遗憾匹配(RM+)及其变种的算法在求解大规模两人零和博弈中的最优策略时的迭代收敛性,并通过数值实验证明了部分实际变种算法在简单的 3×3 游戏中无法保证迭代收敛。进一步证明了基于平滑技术的最新变种算法,如 extragradient RM+ 和 smooth Predictive RM+ 在最优策略上存在渐进收敛以及 1/√t 的最优策略收敛。最后,引入了重启变种算法,并证明它们在最优策略上可达到线性级别的收敛速度。
Nov, 2023
本文研究了一种叫做 OMWU 的算法,该算法在约束的 min-max 最优化问题中表现出优秀的收敛性以及稳定性。该算法与先前的梯度下降法及其他学习算法不同,且需要使用新的技术和思路。
Jul, 2018
本文研究了凸凹零和博弈问题,并提出了一种遵循在线学习框架的近似算法 Optimistic Multiplicative-Weights Update,在本地范围内表现出最后收敛性。
Feb, 2020
本文研究了学习动态的最后迭代收敛问题,并提供了新的结果和技术,其中包括一类游戏模型及其动态下的结果,以及通过遗憾分析得到的性质,证明了具有有界二阶路径长度,而且无论玩家使用不同算法和预测机制,也能实现 O(1 /sqrt(T))的速率和最优 O(1)的后悔界。同时证明了 OMD 要么接近纳什均衡,要么在效率上优于强韧价格,最后,对一般和连续的游戏模型也进行了探讨。
Mar, 2022
本文提出了针对分散式场景中双方零和博弈问题的算法,提供了最佳的诚实遗憾和对抗遗憾率,解决了收敛到游戏价值的对数项的开放问题,并通过乐观的镜像下降算法与鲁棒的乐观镜像下降算法的信号传递方案相结合,实现了最佳结果。
Feb, 2018
提出了新的技术,将 DFG 的技术用于解决内部遗憾和交换遗憾,从而使得多人游戏中的学习动态能够收敛到近似相关均衡,同时分析了 Blum 和 Mansour 算法中的近似最优遗憾保证。
Nov, 2021
本文提出了一种基于乐观的镜像下降的无悔策略算法,可以在非稳态环境下实现 O (sqrt (T)) 的后悔度,并可在变分稳定游戏中收敛到纳什均衡。
Apr, 2021
本研究对 OGDA 和 OMWU 在约束优化问题中的后迭代收敛性进行了显著扩展,提出了一种足够条件来保证 OGDA 在多面体上的双线性博弈问题中展现出线性的后迭代收敛性,并且没有唯一均衡假设,同时在强凸 - 强凹函数上也保持收敛性,这种条件也适用于多个一般目标和可行集合的约束下的 OGDA 算法,并通过实验结果验证了理论。
Jun, 2020