# No-Regret Learning in Network Stochastic Zero-Sum Games

arXiv: https://arxiv.org/abs/2205.14662 · HTML: https://mlsanity.com/paper/2205.14662/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2022.

## Built on by (most cited first, 1 of 1)

- [O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/2504.19375/) (2025)

## Abstract (arXiv)

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 include uncertainty. Such a game model can be found in security games, when a group of inspectors work together to detect a group of evaders. In this paper, we propose a distributed stochastic mirror descent (D-SMD) method, and establish the regret bounds O(√T) and O(log T) in the expected sense for convex-concave and strongly convex-strongly concave costs, respectively. Our bounds match those of the best known first-order online optimization algorithms. We then prove the convergence of the time-averaged iterates of D-SMD to the set of Nash equilibria. Finally, we show that the actual iterates of D-SMD almost surely converge to the Nash equilibrium in the strictly convex-strictly concave setting.