Dec, 2023

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

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

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

    Sep, 2020

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

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

    Dec, 2023

  • 关于回合制零和马尔可夫博弈的强化学习

    本文提出了一种基于强化学习的方法，结合 “探索，策略改进和监督学习”，以找到与纳什均衡相关的价值函数和策略。通过实验证明了该方法在特定情况下可以在近似值方面找到纳什均衡。

    Feb, 2020

  • 使用函数逼近和相关均衡学习零和同时行动马尔可夫博弈

    本研究针对具有线性结构的两人零和有限马尔可夫博弈提出了一种基于乐观价值迭代的增强学习算法，该算法通过构建价值函数的上下置信区间，并用 Coarse Correlated Equilibrium 求解泛化和纳什均衡问题，实现了性能的总时间平方根复杂度的上限。

    Feb, 2020

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

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

    Dec, 2023

  • 针对两人零和线性混合马尔可夫游戏的近乎最优算法

    文章介绍了一种基于乐观不确定性的算法 Nash-UCRL，在找到粗略相关均衡的情况下，可以有效地找到两个玩家的纳什均衡，并证明了其上界和下界的一致性，提出了一种解决有限状态下博弈问题的方法。

    Feb, 2021

  • 在马尔科夫博弈中我们能以线性速率找到纳什均衡吗？

    研究了两个玩家的零和博弈下去中心化学习问题，提出了一种名为 Homotopy-PO 的元算法，通过交替使用本地快速算法和全局缓慢算法，使得机器人之间的政策收敛到了较稳健的纳什均衡状态，同时深入分析了算法的收敛性和性能。

    Mar, 2023

  • 在零和游戏中发现局部纳什均衡（仅限局部纳什均衡）

    本文提出了一种名为 local symplectic surgery 的算法，用于在二人零和博弈中寻找局部纳什均衡，并在两个数值案例中验证其有效性。

    Jan, 2019

  • 多人随机博弈中的学习

    本文研究多人随机博弈中同时学习的问题，通过生成算法获得相关均衡，包括 extensive-form correlated equilibrium 和普通 coarse correlated equilbrium，并提供了一些能够多项式时间内解决的特殊情况。

    Oct, 2022

  • 通用和随机博弈纳什均衡学习的去中心化策略梯度

    研究了一种具有未知转移概率密度函数的一般和随机游戏的纳什平衡学习。介绍一种加权渐近纳什均衡的概念，并提出了两种算法，一种是针对精确伪梯度的，另一种是针对未知伪梯度的。

    Oct, 2022