用于两人零和马尔科夫博弈的正则化梯度下降 / 上升算法
本文提出了一种用于计算竞争性双人游戏纳什均衡的新算法,该算法基于正则化双线性局部逼近的纳什均衡,避免了交替梯度下降中出现的振荡和发散,而且在达到指数级 (局部) 收敛性的同时,其收敛和稳定性的性质对于玩家之间的强交互是稳健的,具有更快的收敛速度。
May, 2019
本文研究一种梯度方案对两个玩家的随机博弈进行求解,并在模拟中显示该方案确实收敛到 Nash 均衡解。但如果只在目标函数的全局最小值处才能达到最优解,当渐近接近时仅能到达局部极小值,本文阐明了梯度方案收敛于广义和随机游戏中纳什均衡的重要必要条件。
Jul, 2015
本文研究了竞争性游戏的均衡计算问题,提出了一种通过熵正则化实现的解法,可以在线性速率下找到量子反应均衡,并且可以实现分散式迭代更新,同时还可以在亚线性速率下找到非正则矩阵博弈的纳什均衡和解决零和 MDP。
May, 2021
通过使用策略近似来减少学习零和随机博弈的纳什均衡的计算成本,我们提出了一种新的 Q-learning 类型算法,该算法使用一系列经过熵正则化的软策略来近似 Q 函数更新期间的纳什策略。我们证明, 在某些条件下,通过更新正则化的 Q 函数,该算法收敛于纳什平衡,并演示了该算法快速适应新环境的能力。提供一种动态超参数调度方案来进一步加快收敛速度。 应用于多个随机游戏的实证结果验证了所提出的算法收敛于纳什平衡,同时展现了比现有算法更快的加速效果。
Sep, 2020
本研究提出了一个广泛适用于多智能体领域的竞争性基于梯度的学习模型,并使用动态系统理论对其进行了分析,对于有限和无限游戏,我们表征了一组非常小的局部纳什均衡,这组均衡将被激活,如果每个智能体采用基于梯度的学习算法。同时研究了基于算法自身构建的不属于纳什均衡的收敛策略在有限和无限游戏中的存在性,这可能解释了在零和游戏中,应用相关算法时出现的困难。最后,为了验证理论贡献,我们给出了一个示例验证。
Apr, 2018
本文研究了一类非凸非凹的极小极大博弈,应用于生成对抗网络中。作者从优化理论、博弈理论和动态系统的角度展开分析,证明了针对特定的问题实例,梯度下降升力动力学可能表现出多种不收敛至极小极大解的行为,包括周期性和波恩卡雷复发。
Oct, 2019
研究了一种具有未知转移概率密度函数的一般和随机游戏的纳什平衡学习。介绍一种加权渐近纳什均衡的概念,并提出了两种算法,一种是针对精确伪梯度的,另一种是针对未知伪梯度的。
Oct, 2022
本文研究如何扰动由两个玩家组成的零和马尔可夫博弈的奖励来诱导期望的纳什均衡。提出了一种反向传播方案,用于在给定奖励函数下求解纳什均衡,并通过黑盒求解器展示了框架的收敛性和在两种多智能体强化学习环境中的成功应用。
Feb, 2023
研究内容涵盖电子竞技中的机器学习,多代理生成对抗网络的表现力,以及两队博弈中的优化问题和 Nash 均衡解的解决方案。通过考虑全信息反馈下的游戏,对在线学习算法的能力进行了讨论,并提出了一个基于控制论技术的一阶方法用于解决该类问题,该方法能够在某些条件下享有局部收敛性。
Nov, 2021