  This paper studies the generalization bounds for the empirical saddle point
(ESP) solution to stochastic saddle point (SSP) problems. For SSP with
Lipschitz continuous and strongly convex-strongly concave objective functions,
we establish an $\mathcal{O}(1/n)$ generalization bound by using a uniform
stability argument. We also provide generalization bounds under a variety of
assumptions, including the cases without strong convexity and without bounded
domains. We illustrate our results in two examples: batch policy learning in
Markov decision process, and mixed strategy Nash equilibrium estimation for
stochastic games. In each of these examples, we show that a regularized ESP
solution enjoys a near-optimal sample complexity. To the best of our knowledge,
this is the first set of results on the generalization theory of ESP.
