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.

本文研究了随机鞍点问题的经验鞍点解的泛化界，证明了在具有 Lipschitz 连续和强凸强凹的目标函数的情况下，可以使用统一稳定性论证来建立一个 O（1/n）的泛化界，并在没有强凸性和没有有界域的情况下提供了泛化界。在马尔可夫决策过程中的批量策略学习和用于随机博弈的混合策略纳什均衡估计的两个示例中，我们展示了正则化 ESP 解具有接近最优样本复杂度。