This chapter will present a series of work related to the issue of search performance in competitive coevolutionary learning. We start with an introduction on performance analysis in competitive coevolution and discuss why the notion of generalization from Machine Learning is useful and relevant. The next section will present this generalization performance framework in competitive coevolutionary learning for problem that can be framed in the context of game-play. We will formally show how this framework is developed and then demonstrate through a series of controlled computational studies its applications towards rigorous quantitative analysis of coevolutionary search performance. The following section describes how these statistical estimators of generalization performance defined as average game outcomes can be improved by exploiting the near-Gaussian nature of those averages and provide tighter bounds via parametric testing. The last section will close the chapter with brief remarks on the issue of the relationship between generalization and diversity in coevolutionary learning.