Certifying ε-equilibria in stochastic games with limited data availability

We focus on stochastic generalized Nash equilibrium problems (SGNEPs) to establish probabilistic guarantees on the quality of the solution produced by a data-driven version of the extragradient (EG) algorithm for stochastic generalized Nash equilibrium (SGNE) seeking. Specifically, we consider a setting where the distribution of the random variable influencing the multi-agent process is unknown, and only a finite number of realizations is available for its characterization. While convergence to a SGNE should not be expected with finite data, we leverage a sample average-based approximation of the game mapping to derive distribution-free certificates bounding the distance between the true SGNE and the solution produced by the data-driven EG method. Consistently, the proposed bound shrinks as the number of samples grows to infinite.