Aug, 2022

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

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

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

    Feb, 2020

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

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

    Feb, 2021

  • 零和马尔可夫博弈中通用的函数逼近

    本文主要研究带有参数化的一般函数类的两人零和有限时间跨度马尔科夫博弈，在研究中提出了可行的算法，包括基于模型的算法和无模型算法，并且在状态-动作对数$d$线性特征的情况下取得了比现有算法更好的效果，同时提出了最小极小规模的模型维度等概念来解决抽样复杂度的问题，最终得出了在模型上算法抽样复杂度可以通过将见证人等级推广到马尔科夫博弈来边界化。

    Jul, 2021

  • 多人零和游戏中相关均衡的几乎最优无悔学习

    提出了新的技术，将DFG的技术用于解决内部遗憾和交换遗憾，从而使得多人游戏中的学习动态能够收敛到近似相关均衡，同时分析了Blum和Mansour算法中的近似最优遗憾保证。

    Nov, 2021

  • 动态定价中n人马尔可夫博弈的近似纳什均衡学习

    本文研究了具有竞争性的马尔可夫游戏中的Nash均衡学习，使用了一种新的无模型方法找到近似Nash均衡，其中策略 - ε对应性和状态至ε-最小策略是用神经网络表示的。在动态价格领域，可以学习到近似的Nash均衡。

    Jul, 2022

  • 马尔科夫博弈中的离线学习和一般函数逼近

    研究离线多智体强化学习在马尔科夫博弈中学习近似均衡，提供适用于一般函数逼近的新框架以处理所有三种均衡，此框架利用 Bellman 一致压缩和数据覆盖条件，与之前的算法框架相比，其保证更好且能够处理更广泛的情况。

    Feb, 2023

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

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

    Dec, 2023

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

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

    Dec, 2023

  • $\widetilde{O}(T^{-1})$ 在全信息General-Sum Markov Games中收敛到（粗糙）相关均衡

    使用乐观跟随正则化领导者算法结合适当的价值更新过程，在全信息一般和马尔可夫博弈中找到近似于O(T^-1)粗糙相关均衡。

    Feb, 2024

  • 正规形式博弈中后悔最小化的计算下界

    本研究探讨了在正规形式博弈中，缩小后悔的迭代次数以达到相关均衡（CE）的问题。作者提出了现有学习算法（如乘法权重更新）接近最优的证据，并证明了计算均匀混合的T个产品分布的CE的下界，这些结果为基于算法的后悔最小化方案提供了重要限制，可能影响相关算法的设计与优化。

    Nov, 2024