行为到稀疏图游戏:均衡状态的高效恢复
考虑从严格的行为数据中学习线性影响博弈 (LIGs) 的结构和参数,通过纯策略 Nash 平衡的最大似然估计 (MLE) 将学习问题转化为生成模型的估计,在控制平衡数量的同时捕捉数据中的均衡行为。该方法可以应用于识别大型 (社交) 网络中最有影响力的个体,并支持决策分析和其他普适性的图形游戏。
Jun, 2012
这篇研究论文探讨了具有噪声的两人零和矩阵博弈中,识别纯策略纳什均衡(PSNE)的样本复杂度。研究人员设计了一个接近最优的算法,其样本复杂度与已知的下界相匹配,同时解决了纯探索问题和 dueling bandits 问题,且结果与最优边界相匹配。
Oct, 2023
通过发展更高效和可扩展的算法,使用稀疏迭代方法的行为扰动来解决不完全信息博弈中的纳什均衡问题,从而实现最优均衡,但不排除博弈树中未到达的子树中存在次优策略。 通过使用平滑方法,能够计算出一个近似的 extensive-form 完美均衡,以解决经典的纳什均衡算法中存在的精度问题。
May, 2017
我们提出了一种简单的算法,通过在线调整受控系数来学习将博弈的纳什均衡点转移到符合线性约束,而不需要知道奖励函数或行动集,从而提供具有概率 1 保证的收敛性以满足目标线性约束的纳什均衡集合,并为该算法提供了均方收敛速度为 O (t^{-1/4}) 的界限。我们演示了该算法在全局二次代价优化和资源分配博弈中实现负载平衡的应用场景的模拟结果。
Jun, 2024
研究了一种具有未知转移概率密度函数的一般和随机游戏的纳什平衡学习。介绍一种加权渐近纳什均衡的概念,并提出了两种算法,一种是针对精确伪梯度的,另一种是针对未知伪梯度的。
Oct, 2022
本文研究了基于局部知识来学习研究各种类型的博弈及其均衡求解的复杂度,探讨了计算学习模型和对于各种博弈的查询复杂度,着重研究了对称网络拥塞博弈,并通过仅查询少量的纯策略来学习成本函数。
Feb, 2013
通过研究正则化的无悔学习方法在有限游戏中的长期行为,我们发现玩家的实际策略如何随时间演变的理解非常有限,同时发现只有严格纳什均衡是稳定吸引的,进而揭示了玩家的日常对策的集合有理性的特性。我们进一步刻画了相应集合的稳定和收敛速率,并表明基于熵正则化的方法以几何速度收敛,而基于投影的方法在有限次迭代内收敛,即使是在带有被动反馈的并发奖励的情况下。
Nov, 2023
在一种类别的随机博弈中,利用自治的镜面下降算法通过占用测量和置信区间技术提出了一种学习算法,以构建稳定的 ε-NE 策略集合,并证明了其多项式时间收敛性。
Dec, 2023
该文提供了第一个完全多项式时间的近似混合策略纳什均衡算法,用于计算树形图多超矩阵博弈中的纳什均衡,并证明当操作数量受到限制时,该算法适用于树状多项式博弈和树形图博弈,并引出了拟多项式时间的近似算法。
Feb, 2016
研究引入相对熵正则化对 General-Sum $N$-agent games 的 Nash Equilibria 的影响,揭示了该类游戏的 NE 符合线性高斯策略。此外,本文提出了符合熵正则化充分条件的 NE 唯一性,并证明了在 Policy Optimization 算法中线性收敛性,该算法在熵正则化充分条件下能达到 NE。此外,在熵正则化不足的情况下,我们还提出了一种 δ 增强技术,可实现游戏中的 ε-NE。
Mar, 2024