Fenchel 博弈中的无悔动态:算法凸优化的统一框架
本论文研究了如何利用在线学习动态算法来求解具有 Nash 均衡约束的凸凹博弈问题,通过引入乐观学习机制使得该方法求解速度得到了显著提升,同时还证明了在强凸平滑函数的情况下该方法的加速收敛性。
Jul, 2018
本文提出了一种基于乐观的镜像下降的无悔策略算法,可以在非稳态环境下实现 O (sqrt (T)) 的后悔度,并可在变分稳定游戏中收敛到纳什均衡。
Apr, 2021
本文提出了一种新的在线学习方法,用于在大型 extensive-form 游戏中最小化后悔。该方法通过在线学习函数逼近器来估计选择特定行动的后悔值,并使用无悔算法根据这些估计值来定义一系列策略。我们证明了该方法的正确性,并证明了只要逼近函数能够实现后悔值,方法就能自我学习并收敛到纳什均衡。我们的技术可以被理解为现有大型游戏中抽象工作的原则性推广;在我们的工作中,抽象和均衡都是在自我博弈中学习的。我们在实验中展示了该方法可以在相同资源条件下实现比最先进的抽象技术更高质量的策略。
Nov, 2014
本文提出了一种称为 “laminar regret decomposition” 的新框架,该框架扩展了 CFR 算法,并使 regret minimization 能够适用于更广泛的决策点模型和损失函数模型。该框架适用于多种问题类型,例如:序贯决策制定、纳什均衡及其近似解、以及普遍化量子反应均衡。实验证明,该框架所开发的算法与 counterfactual regret minimization 相比,在计算纳什均衡时具有可比性,并且该方法是计算极大规模游戏中的量子反应均衡的第一个算法。此外,我们还展示了一种新类型的可伸缩对手利用方法。
Sep, 2018
研究一种基于连续时间的在线优化策略族,证明其能够达到无遗憾学习。从传统的离散时间角度来看,这种方法可导出大量离散时间算法(包括一些经典遗憾分析算法)的无遗憾性质,并统一了许多经典的遗憾上界,得到了一个无需借助于倍增技巧即可保证 $O (n^{-1/2})$ 遗憾上界的学习策略类。
Jan, 2014
我们研究了重复的一阶售价拍卖和一般重复贝叶斯博弈的情况,在这种情况下,一个参与者(学习者)采用了一个无悔学习算法,而另一个参与者(优化者)在了解学习者的算法的情况下,策略化地追求自己的效用最大化。 对于一类被称为基于均值的无悔学习算法,我们证明:(i)在标准(即完全信息)的一阶售价拍卖中,优化者不能获得超过 Stackelberg 效用的效用 -- 这是文献中的标准基准,但是(ii)在贝叶斯一阶售价拍卖中,存在优化者可以获得远高于 Stackelberg 效用的实例。 另一方面,Mansour 等人(2022)证明了一类更复杂的算法,称为无多面体交换后悔算法可以将优化者的效用限制在任意重复贝叶斯博弈(包括贝叶斯一阶售价拍卖)的 Stackelberg 效用上,并提出是否有必要使用无多面体交换后悔算法来限制优化者的效用。对于一般的贝叶斯博弈,在一个合理且必要的条件下,我们证明了无多面体交换后悔算法确实是将优化者的效用限制在 Stackelberg 效用上的必要条件,从而回答了他们的开放性问题。对于贝叶斯一阶售价拍卖,我们通过利用贝叶斯一阶售价拍卖的结构给出了一个简单的改进标准算法来最小化多面体交换后悔。
Feb, 2024
本文提出了针对分散式场景中双方零和博弈问题的算法,提供了最佳的诚实遗憾和对抗遗憾率,解决了收敛到游戏价值的对数项的开放问题,并通过乐观的镜像下降算法与鲁棒的乐观镜像下降算法的信号传递方案相结合,实现了最佳结果。
Feb, 2018
本研究主要探讨了潜在博弈、马尔可夫潜在博弈和 Frank-Wolfe 算法在随机成本和强盗反馈下的应用,提出了一种具有足够探索性和递归梯度估计的变种算法,能证明收敛于纳什均衡并对每个参与者实现亚线性遗憾。该算法同时在潜在博弈中实现了纳什遗憾和 $O (T^{4/5})$ 的遗憾上界,匹配了现有最佳结果,无需额外的投影步骤。通过精确平衡过去样本的重复使用和新样本的探索,我们将结果扩展到了马尔可夫潜在博弈中,将现有最佳纳什遗憾从 $O (T^{5/6})$ 改进至 $O (T^{4/5})$。此外,我们的算法不需要了解游戏的任何信息,如分布误差系数,这提供了更灵活的实际实施。实验结果证实了我们的理论发现,并强调了我们方法的实际有效性。
Apr, 2024
使用 CFR 框架开发算法以解决行为约束的 extensive-form games,同时计算近似 Nash 平衡改进。比标准算法更好,收敛速率与最先进的 Nash 平衡计算算法相当。
Nov, 2017