多人游戏中通过多重矩阵可分解性保证自我对弈
本文介绍了一种可推广的终端到终端学习方法,结合了虚构自游戏和深度强化学习来学习近似Nash均衡。在Leduc扑克和真实规模的Limit Texas Holdem游戏中,NFSP相比于传统强化学习方法,接近甚至超过了基于领域知识经验的超级算法。
Mar, 2016
本文基于博弈论原理研究了一种基于人口统计的培训体系——策略空间响应神谕(PSRO),并将其扩展到广义和多人游戏中。通过使用另一种解决方案概念 $\alpha$-Rank,在一些游戏分类中建立了收敛保证,并确定了 Nash 平衡和 $\alpha$-Rank 之间的联系。实验结果表明,基于 $\alpha$-Rank 的 PSRO 可以在很多游戏中实现比近似 Nash Solver 更快的收敛速度。
Sep, 2019
研究自博弈算法在Markov游戏中的应用,提出了Value Iteration with Upper/Lower Confidence Bound (VI-ULCB)算法和探索-开采算法,并证明了其在策略最佳化中的有效性和高样本利用率。
Feb, 2020
本文提出了楽观的Nash Q-learning算法,并使用了新的Nash V-learning算法,解决了在马尔可夫博弈环境中的奖励学习优化问题,且这个算法的采样复杂度比现有算法还要低.
Jun, 2020
本文研究了no-regret动力学中最常被考虑的动态系统之一 - Follow-the-regularized-leader的行为,证明了非严格的纳什均衡对于no-regret学习是不稳定的且不能吸引该动态系统的稳定状态,因此只有严格的纳什均衡是no-regret动力学的稳定限制点。
Oct, 2020
本文研究了去中心化多智能体强化学习问题中的不后悔算法,并探讨了自主学习能否在标准Markov博弈框架中实现无后悔学习。结果表明,无论是已知还是未知的博弈,该问题都无法以多项式时间实现无后悔学习,该文贡献了理论证明支持,提出了基于集聚方法的创新性应用,并发现了SparseCCE问题的下限,从而说明了近年来学者对于该问题的研究成果,并对博弈理论和强化学习算法研究方向提出了新的思考。
Mar, 2023
通过研究正则化的无悔学习方法在有限游戏中的长期行为,我们发现玩家的实际策略如何随时间演变的理解非常有限,同时发现只有严格纳什均衡是稳定吸引的,进而揭示了玩家的日常对策的集合有理性的特性。我们进一步刻画了相应集合的稳定和收敛速率,并表明基于熵正则化的方法以几何速度收敛,而基于投影的方法在有限次迭代内收敛,即使是在带有被动反馈的并发奖励的情况下。
Nov, 2023
该研究介绍了Off-FSP,这是第一个面向竞技游戏的实用无模型离线RL算法。通过调整固定数据集的权重以重要性采样的方式与各种对手进行模拟交互,学习最佳响应以及应用离线自我对弈学习框架,并进一步实现虚构自我对弈(FSP)以近似纳什均衡(NE),在部分覆盖的真实世界数据集中,我们的方法显示出通过融合任何单代理离线RL方法接近NE的潜力。在Leduc Hold'em Poker的实验证明了我们的方法与最先进的基准算法相比显著提高性能。
Feb, 2024
本文研究了两人零和矩阵博弈和随机博弈,通过收益驱动的学习动态实现了收敛且对称的学习过程。我们首次进行了有限样本分析,结果表明在矩阵博弈中找到纳什分布的样本复杂度为$O(\epsilon^{-1})$,而找到纳什均衡的样本复杂度为$O(\epsilon^{-8})$,具有重要的理论和实践意义。
Sep, 2024
本研究解决了两玩家零和矩阵和随机博弈中的学习动力学问题,提出了一种基于收益的收敛性学习方法。该方法首次提供了具有最后迭代收敛保证的有限样本分析,发现矩阵博弈寻找纳什分布的样本复杂度为$O(\epsilon^{-1})$,而寻求纳什均衡的复杂度为$O(\epsilon^{-8})$。此工作为随机近似算法的收敛行为提供了新的视角。
Sep, 2024