May, 2023

单调博弈中学习的弹弓方法

PDF
TL;DR本文提出了一种新的针对噪声问题的计算均衡的框架，包含现有的付款规范算法，并具有最后迭代收敛性质。主要思想是扰动或规范化游戏的支付或效用。这种扰动可以将当前策略拉到固定点，称为滑轮策略。通过周期性更新滑轮策略，我们演示了最后迭代的收敛。最后，我们展示了基于此框架的算法在实证中具有更快的收敛。
equilibriamonotone gamesfollow the regularized leader algorithmconvergenceslingshot strategy
发现论文，激发创造
  • 从庞加莱回归到不完全信息博弈的收敛：通过正则化寻找均衡

    研究了在顺序不完美信息游戏中遵循规则的领导者动态，推广了 Poincaré 循环结果，并探讨了通过调整奖励来建立收敛保证的技术，进而构建了精确收敛到 Nash 平衡的算法，为零和二人不完美信息游戏的无模型算法提供了新思路。

    Feb, 2020

  • 学习控制未知强单调博弈

    我们提出了一种简单的算法，通过在线调整受控系数来学习将博弈的纳什均衡点转移到符合线性约束，而不需要知道奖励函数或行动集，从而提供具有概率 1 保证的收敛性以满足目标线性约束的纳什均衡集合，并为该算法提供了均方收敛速度为 O (t^{-1/4}) 的界限。我们演示了该算法在全局二次代价优化和资源分配博弈中实现负载平衡的应用场景的模拟结果。

    Jun, 2024

  • 连续对局中的最小信息学习

    通过引入一种随机学习过程 - 阻尼梯度逼近，我们在本文中为具有连续行动集的博弈设计了一种学习过程，它是基于收益的，因此不需要玩家有策略上的认知或关于游戏的知识，我们还证明了在大部分博弈中玩家可以收敛于 Nash 均衡点。

    Jun, 2018

  • 斯塔克贝格博弈中的学习动态收敛

    本文研究了斯塔克伯格博弈中学习动态的收敛性，并提出了一种基于梯度的学习更新规则，用于训练生成对抗网络。

    Jun, 2019

  • 正则化学习下游戏中动态稳定性和战略稳定性的等效性

    通过研究正则化的无悔学习方法在有限游戏中的长期行为，我们发现玩家的实际策略如何随时间演变的理解非常有限，同时发现只有严格纳什均衡是稳定吸引的，进而揭示了玩家的日常对策的集合有理性的特性。我们进一步刻画了相应集合的稳定和收敛速率，并表明基于熵正则化的方法以几何速度收敛，而基于投影的方法在有限次迭代内收敛，即使是在带有被动反馈的并发奖励的情况下。

    Nov, 2023

  • 零和马尔可夫博弈中政策优化的更快收敛

    本文提出了一种基于 OMWU 方法的单环路政策优化算法，并在二人零和马尔可夫博弈中，通过控制正则化的程度，实现了有限时间的最后一次线性收敛到达量子响应均衡点，并在全信息离散设置中实现了收敛结果。

    Oct, 2022

  • 关于零和博弈的收敛策略探讨

    本文研究了学习动态的最后迭代收敛问题，并提供了新的结果和技术，其中包括一类游戏模型及其动态下的结果，以及通过遗憾分析得到的性质，证明了具有有界二阶路径长度，而且无论玩家使用不同算法和预测机制，也能实现 O（1 /sqrt（T））的速率和最优 O（1）的后悔界。同时证明了 OMD 要么接近纳什均衡，要么在效率上优于强韧价格，最后，对一般和连续的游戏模型也进行了探讨。

    Mar, 2022

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

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

    Feb, 2024

  • 连续博弈中的自适应学习：最优遗憾边界和纳什均衡收敛

    本文提出了一种基于乐观的镜像下降的无悔策略算法，可以在非稳态环境下实现 O (sqrt (T)) 的后悔度，并可在变分稳定游戏中收敛到纳什均衡。

    Apr, 2021

  • 正则化学习在博弈中的快速收敛

    通过采用具有一种新颖形式的经验回忆的正则化学习算法，我们表明，在多人博弈的普通形式中，该类自适应算法能够实现更快的收敛速率，并实现对近似效率和粗略相关均衡的收敛，并且，对这种类型算法应用的每个玩家，他们的个体后悔降至 $O (T^{-3/4})$，而其效用之和则以 $O (T^{-1})$ 的速度趋于近似最优，在与该类算法相对应的算法维持更快的速率的同时，我们还表明了该类中的任何算法均可通过黑匣子降至 $ ilde {O}(T^{-1/2})$ 的速率来抵抗对手。

    Jul, 2015