应用人工障碍实现自适应学习得到常规博弈的纳什均衡
本文提出了一个几何框架来制定零和博弈中的智能体目标,以构建产生开放式学习的自适应目标序列,从而产生比现有算法更强的智能体集合。我们将PSRO_rN应用于两个高度非传递性的资源分配游戏,并发现PSRO_rN始终优于现有替代方案。
Jan, 2019
研究线性二次游戏中政策优化寻找纳什均衡的全局收敛性,开发了三种投影嵌套-梯度方法并给出了满意的收敛性证明和模拟结果,是对零和Markov博弈政策优化强化学习算法理论方面的探索。
May, 2019
通过使用策略近似来减少学习零和随机博弈的纳什均衡的计算成本,我们提出了一种新的Q-learning类型算法,该算法使用一系列经过熵正则化的软策略来近似Q函数更新期间的纳什策略。我们证明, 在某些条件下,通过更新正则化的Q函数,该算法收敛于纳什平衡,并演示了该算法快速适应新环境的能力。提供一种动态超参数调度方案来进一步加快收敛速度。 应用于多个随机游戏的实证结果验证了所提出的算法收敛于纳什平衡,同时展现了比现有算法更快的加速效果。
Sep, 2020
本文研究了no-regret动力学中最常被考虑的动态系统之一 - Follow-the-regularized-leader的行为,证明了非严格的纳什均衡对于no-regret学习是不稳定的且不能吸引该动态系统的稳定状态,因此只有严格的纳什均衡是no-regret动力学的稳定限制点。
Oct, 2020
本文提出了一种基于乐观的镜像下降的无悔策略算法,可以在非稳态环境下实现O(sqrt(T))的后悔度,并可在变分稳定游戏中收敛到纳什均衡。
Apr, 2021
本文提出一种基于零阶优化技术、结合平滑梯度估计器和均衡查找动态的方法来解决没有梯度信息的连续行动博弈问题,采用神经网络建模玩家策略,特别是采用随机策略网络来建模混合策略。实验表明,该方法可以快速找到高质量的近似均衡。此外,研究表明,输入噪声的维度对方法的性能至关重要。这是第一篇在未知任何梯度信息的情况下解决了不受限制的连续行动博弈的研究。
Nov, 2022
研究了两个玩家的零和博弈下去中心化学习问题,提出了一种名为Homotopy-PO的元算法,通过交替使用本地快速算法和全局缓慢算法,使得机器人之间的政策收敛到了较稳健的纳什均衡状态,同时深入分析了算法的收敛性和性能。
Mar, 2023
AI在数学领域以一种建设性的方式处理数学问题,使推理自动化、减少劳动力和降低错误率。本研究首次提供了一个自动化方法,用于理论计算机科学中一个经过深入研究的问题:计算两人博弈中的近似纳什均衡。我们观察到,这样的算法可以被重新表述为搜索混合范式,其中包括搜索阶段和混合阶段。通过这样做,我们能够完全自动化设计和分析混合阶段的过程。例如,我们演示了如何使用我们的方法来分析文献中所有算法的近似界限。这些近似界限是无需任何手写证明计算的。我们的自动化方法严重依赖近似纳什均衡中的LP松弛结构。由于许多近似算法和在线算法采用了LP松弛,我们的方法可能被扩展用于自动化分析其他算法。
Oct, 2023
在一种类别的随机博弈中,利用自治的镜面下降算法通过占用测量和置信区间技术提出了一种学习算法,以构建稳定的ε-NE策略集合,并证明了其多项式时间收敛性。
Dec, 2023
通过利用Tsallis熵正则化的值迭代方法,我们提出了一种合理且收敛的算法,在弱条件下以无耦合和单时间尺度算法的方式高效地实现了近似纳什均衡。该算法在多项式时间内学习近似纳什均衡,仅需要存在一个诱导不可约和非周期性马尔可夫链的策略对,从而明显减弱了过去的假设。我们的分析利用了负漂移不等式,并引入了Tsallis熵的新特性,这些特性具有独立的研究价值。
Dec, 2023