跳到正文
arXiv cs.AI· Maurizio d'Andrea (TSE-R), Fabien Gensbittel (TSE-R), J\'er\^ome Renault (TSE-R)·· 10 小时前AI 评分18

指数权重算法在重复博弈中的末次迭代收敛性研究

Games played by Exponential Weights Algorithms

AI 导读

论文研究恒定学习率下指数权重算法的末次迭代收敛性,证明只要存在严格 Nash 均衡,下一阶段选择该均衡的概率几乎必然收敛至 0 或 1。算法产生的混合动作序列极限若存在,必属于"收益均等 Nash 均衡"集合;在强协调博弈中,该序列几乎必然收敛到某个严格 Nash 均衡。成果已发表于 Mathematics of Operations Research。

正文 · AI 翻译

查看 PDF HTML(实验性)

摘要:本文研究固定学习率的指数权重算法的末次迭代收敛性质。我们考虑离散时间下的重复交互,其中每个参与者使用由初始混合动作和固定学习率刻画的指数权重算法,使得在第 $t$ 阶段所采用的混合动作剖面 $p^t$ 服从齐次马尔可夫链。首先,我们证明只要存在严格纳什均衡,则在下一阶段采用严格纳什均衡的概率几乎必然收敛到 0 或 1。其次,我们证明 $p^t$ 的极限(只要存在)属于“收益均等的纳什均衡”集合。第三,我们证明在强协调博弈中(参与者的收益在对角线上为正、在其他位置为 0),$p^t$ 几乎必然收敛到某个严格纳什均衡。最后我们提出了一些开放问题。
评论: 发表于 Mathematics of Operations Research。修订版包含少量更正和表述改进
主题: 人工智能(cs.AI);概率论(math.PR)
MSC 分类: 91A25, 60J05
引用为: arXiv:2407.06676 [cs.AI]
  (或 arXiv:2407.06676v2 [cs.AI] 用于此版本)
  https://doi.org/10.48550/arXiv.2407.06676

由 DataCite 颁发的 arXiv DOI

期刊 参考: Mathematics of Operations Research (2026), Articles in Advance
相关 DOI: https://doi.org/10.1287/moor.2025.1310

链接到相关资源的 DOI

提交历史

来自:Maurizio D'Andrea [查看电子邮件] [通过 CCSD 代理]
[v1] 2024年7月9日星期二 08:49:51 UTC(32 KB)
[v2] 2026年11月18日星期三 05:13:42 UTC(30 KB)

来源:arXiv cs.AI · arxiv.org