研究了基于遗憾匹配(RM+)及其变种的算法在求解大规模两人零和博弈中的最优策略时的迭代收敛性,并通过数值实验证明了部分实际变种算法在简单的 3×3 游戏中无法保证迭代收敛。进一步证明了基于平滑技术的最新变种算法,如 extragradient RM+ 和 smooth Predictive RM+ 在最优策略上存在渐进收敛以及 1/√t 的最优策略收敛。最后,引入了重启变种算法,并证明它们在最优策略上可达到线性级别的收敛速度。
Nov, 2023
本文研究了学习动态的最后迭代收敛问题,并提供了新的结果和技术,其中包括一类游戏模型及其动态下的结果,以及通过遗憾分析得到的性质,证明了具有有界二阶路径长度,而且无论玩家使用不同算法和预测机制,也能实现 O(1 /sqrt(T))的速率和最优 O(1)的后悔界。同时证明了 OMD 要么接近纳什均衡,要么在效率上优于强韧价格,最后,对一般和连续的游戏模型也进行了探讨。
Mar, 2022
通过分析梯度方法在达到纳什均衡时的线性收敛特性,证明了变异梯度方法在双线性博弈和强单调性博弈中的各种表现,并发现了这些方法在极端情况下收敛机制的差异。同时证明了变异梯度可以在任意外推次数的情况下实现优化率,一个广泛算法类别的最佳值
Jun, 2019
研究无穷时间折扣二人零和马尔可夫博弈,开发了一种分散算法,自我对弈时能够收敛到 Nash 均衡点。
Feb, 2021
本文研究了基于遗憾的算法在连续游戏中寻找近似的纳什均衡,针对反事实遗憾最小化(CFR)算法存在的表示收敛的缺陷,提出了一些基于树形复合结构的乐观遗憾最小化算法,并给出了实验证明其在求解连续游戏时的有效性。
Jun, 2021
通过转换问题为一系列凸凹优化问题, ' 无悔算法 ' 在学习纳什均衡中取得竞争性表现,在离散时间反馈设置下实现最后迭代收敛。
Aug, 2023
通过在线学习的自我对弈是解决大规模两人零和游戏的主要方法之一,尤其流行的算法包括乐观的乘积权重更新(OMWU)和乐观的梯度下降 - 梯度上升(OGDA),本文证明了 OMWU 存在潜在的较慢的最后迭代收敛问题。
Jun, 2024
本研究解决了开放性问题,证明了用切向残差作为潜势函数的 extragradient 算法(或乐观梯度上升下降算法)在任意凸可行域上具有极致的收敛速率,其简单的表达为 $O (1/√T)$ 。
Apr, 2022
本研究通过对二人博弈中多智能体学习策略的分析,提出了一个令人惊讶的结论 —— 不论策略是否收敛,智能体的平均收益都会收敛于纳什均衡,在电子商务和拍卖中具有一定的适用性。
Jan, 2013
本文研究了凸凹零和博弈问题,并提出了一种遵循在线学习框架的近似算法 Optimistic Multiplicative-Weights Update,在本地范围内表现出最后收敛性。
Feb, 2020