Sep, 2024

基于收益的独立学习在零和随机博弈中的最后迭代收敛性

HTML
PDF
TL;DR本研究解决了两玩家零和矩阵和随机博弈中的学习动力学问题，提出了一种基于收益的收敛性学习方法。该方法首次提供了具有最后迭代收敛保证的有限样本分析，发现矩阵博弈寻找纳什分布的样本复杂度为$O(\epsilon^{-1})$，而寻求纳什均衡的复杂度为$O(\epsilon^{-8})$。此工作为随机近似算法的收敛行为提供了新的视角。
发现论文，激发创造
  • 通过熵正则化的策略逼近学习零和随机博弈中的纳什均衡

    通过使用策略近似来减少学习零和随机博弈的纳什均衡的计算成本，我们提出了一种新的Q-learning类型算法，该算法使用一系列经过熵正则化的软策略来近似Q函数更新期间的纳什策略。我们证明， 在某些条件下，通过更新正则化的Q函数，该算法收敛于纳什平衡，并演示了该算法快速适应新环境的能力。提供一种动态超参数调度方案来进一步加快收敛速度。 应用于多个随机游戏的实证结果验证了所提出的算法收敛于纳什平衡，同时展现了比现有算法更快的加速效果。

    Sep, 2020

  • 无遗憾学习和混合纳什均衡：不能相互混合

    本文研究了no-regret动力学中最常被考虑的动态系统之一 - Follow-the-regularized-leader的行为，证明了非严格的纳什均衡对于no-regret学习是不稳定的且不能吸引该动态系统的稳定状态，因此只有严格的纳什均衡是no-regret动力学的稳定限制点。

    Oct, 2020

  • 随机博弈中的独立学习

    本综述介绍了一个新的独立学习动力学网络，其保证了在零和随机博弈中的收敛性，同时也回顾了其他算法，以期推动研究有关动态环境下博弈的独立和自然学习动力学。

    Nov, 2021

  • 学习双人混合马尔可夫博弈：核函数逼近和相关均衡

    本论文提出了一种基于优化原则的在线学习算法，通过在函数空间中最小化对偶差来寻找Nash均衡点，在马尔科夫博弈中进行非线性函数逼近，解决了高维函数空间中的探索问题，并扩展了几种算法，其中一个可以实现更紧的遗憾上界，另一个可以应用于神经网络函数逼近的模型错误说明。

    Aug, 2022

  • 未知独立链$n$-人随机博弈中纳什均衡策略的可扩展与独立学习

    在一种类别的随机博弈中，利用自治的镜面下降算法通过占用测量和置信区间技术提出了一种学习算法，以构建稳定的ε-NE策略集合，并证明了其多项式时间收敛性。

    Dec, 2023

  • 零和随机博弈中带有函数逼近的两时间尺度 Q-Learning

    我们提出了一种两时间尺度Q学习算法，采用函数逼近，以找到两个玩家之间公平、收敛、理性且对称的纳什均衡。我们的方法在线性函数逼近的特殊情况下，建立了无限采样边界，从而对这类随机博弈中收敛到纳什均衡所需的样本量提供了多项式的上界。

    Dec, 2023

  • 弱可达情况下的零和马尔可夫博弈纳什均衡学习

    通过利用Tsallis熵正则化的值迭代方法，我们提出了一种合理且收敛的算法，在弱条件下以无耦合和单时间尺度算法的方式高效地实现了近似纳什均衡。该算法在多项式时间内学习近似纳什均衡，仅需要存在一个诱导不可约和非周期性马尔可夫链的策略对，从而明显减弱了过去的假设。我们的分析利用了负漂移不等式，并引入了Tsallis熵的新特性，这些特性具有独立的研究价值。

    Dec, 2023

  • 受限周期性博弈中额外梯度法与乐观主义的最后收敛分离

    研究了乐观法和额外梯度法在受限周期游戏中的最终迭代行为，证明了与无限制周期游戏中的收敛性类似的分离结果。

    Jun, 2024

  • 快速学习游戏的最后迭代收敛需要健忘算法

    通过在线学习的自我对弈是解决大规模两人零和游戏的主要方法之一，尤其流行的算法包括乐观的乘积权重更新（OMWU）和乐观的梯度下降-梯度上升（OGDA），本文证明了OMWU存在潜在的较慢的最后迭代收敛问题。

    Jun, 2024

  • 基于收益的独立学习在零和随机博弈中的最后迭代收敛

    本文研究了两人零和矩阵博弈和随机博弈，通过收益驱动的学习动态实现了收敛且对称的学习过程。我们首次进行了有限样本分析，结果表明在矩阵博弈中找到纳什分布的样本复杂度为$O(\epsilon^{-1})$，而找到纳什均衡的样本复杂度为$O(\epsilon^{-8})$，具有重要的理论和实践意义。

    Sep, 2024