No-Regret Learning in Network Stochastic Zero-Sum Games
简介：No-regret learning has been widely used to compute a Nash equilibrium in two-person zero-sum games.However,there is still a lack of regret analysis for network stochastic zero-sum games,where players competing in two subnetworks only have access to some local information,and the cost functions are subject to stochastic uncertainty.Such a game model can be found in network interdiction problems,when a group of inspectors work together to detect a group of evaders.In this paper,the authors propose a distributed stochastic mirror descent(D-SMD)method,and establish the regret bounds O(√T)and O(logT)in the expected sense for convex-concave and strongly convex-strongly concave costs,respectively.The proposed bounds match those of the best known first-order online optimization algorithms.The authors then prove the convergence of the time-averaged iterates of D-SMD to the set of Nash equilibria.Finally,the authors show that the actual iterates of D-SMD almost surely converge to the Nash equilibrium in the strictly convex-strictly concave setting.展开
学者：HuangShijieLEIJinlongHONGYiguang
关键词：Distributed mirror descentnetwork zero-sum gamesno-regret learningstochastic
在线出版日期：2026-05-14 （网站首发日期）
