Optimal Rates for Feasible Payoff Set Estimation in Games Annalisa Barbara, Riccardo Poiani, Martino Bernasconi, Andrea Celli Abstract We study a setting in which two players play a (possibly approximate) Nash equilibrium of a bimatrix game, while a learner observes only their actions and has no knowledge of the equilibrium or the underlying game. A natural question is whether the learner can rationalize the observed behavior by inferring the players’ payoff functions. Rather than producing a single payoff estimate, inverse game theory aims to identify the entire set of payoffs consistent with observed behavior, enabling downstream use in, e.g. , counterfactual analysis and mechanism design across applications like auctions, pricing, and security games. We focus on the problem of estimating the set of feasible payoffs with high probability and up to precision ϵ \epsilon on the Hausdorff metric. We provide the first minimax-optimal rates for both exact and approximate equilibrium play, in zero-sum as well as general-sum games. Our results provide learning-theoretic foundations for set-valued payoff inference in multi-agent environments. 1 Introduction The central question in inverse game theory is the following ( Waugh et al. 2011 ; Kuleshov and Schrijvers 2015 ) : given observed equilibrium behavior, what utility functions could have generated it? We study the problem of recovering the entire set of possible payoffs compatible with the players’ observed behavior, given action samples generated by their strategies. We are interested in the minimax sample complexity of approximately identifying such a set. Even when equilibrium behavior is observed exactly (let alone through samples), the problem of inferring an agent’s utilities from behavior is inherently underdetermined, as multiple payoff functions can rationalize the same observed play ( Ng and Russell 2000 ; Waugh et al. 2011 ) . This issue is often referred to as unidentifiability . For example, the zero payoff matrix is compatible with any equilibrium. This ambiguity is usually addressed by imposing additional structure, such as restricting attention to parametrized low-dimensional payoff families ( Waugh et al. 2011 ; Kuleshov and Schrijvers 2015 ) , or by choosing a priori a selection principle such as maximum entropy ( Vorobeychik et al. 2007 ; Waugh et al. 2011 ) , or bounded-rationality models (such as quantal response) ( Yu et al. 2022 ) . Rather than imposing additional modeling assumptions or fixing an a priori selection principle, we focus on identifying the entire set of payoff functions consistent with the observed strategies, i.e. , the feasible payoff set. The idea of this approach is to defer the selection of a particular payoff to a later stage, thereby making the entire process modular and more adaptable to the requirements of the application at hand. For example, given the entire set of possible equilibria, one may select equilibria according to a maximum-entropy criterion ( Waugh et al. 2011 ) , add additional structural constraints to the set ( e.g. , if we know that the game is symmetric or has a potential-game structure), or choose a robust representative such as the incenter solution ( Cui et al. 2025 ) . This set-valued perspective is standard in structural econometrics and inverse game theory (see, among others, Brown and Matzkin 1996 ; Manski 2003 ; Tamer 2010 ; Waugh et al. 2011 ). However, the corresponding learning problem remains poorly understood from a theoretical standpoint, and even in the simplest multi-agent settings, we lack a sharp characterization of the statistical difficulty of such set-valued identification. In this work, we address this gap by providing minimax-optimal sample complexity guarantees for the problem of recovering the feasible payoff set from the observed behavior of two players in an unknown bimatrix game playing a Nash equilibrium. In particular, we consider two players repeatedly interacting in an unknown n -dimensional normal-form bimatrix game with payoff matrices (A,B) . The players play a (possibly approximate) Nash equilibrium (x,y) of the game, and the learner observes i.i.d. action pairs (X_{t},Y_{t}) sampled from the product distribution x\times y . The learner’s goal is to infer the feasible payoff set : the set of all payoff matrices (A^{\prime},B^{\prime}) for which the strategies (x,y) constitute a Nash equilibrium (or an \alpha -Nash equilibrium) of (A^{\prime},B^{\prime}) . The goal of the paper is to answer the following question: How many equilibrium samples are required to estimate the feasible payoff set up to Hausdorff error \epsilon with probability at least 1-\delta ? Our main contribution is the first minimax-optimal characterization of this question. Our results cover both general-sum and zero-sum games, and both approximate and exact Nash equilibria. Technical challenges An important technical ingredient in our analysis is the correspondence (a set-valued function) that maps equilibrium strategies to the feasible payoff sets that rationalize them. Regarding the lower bounds, we first show that, when observing exact equilibria ( i.e. , \alpha=0 ), the strong discontinuity of such correspondence makes the problem unlearnable. Therefore, we relax the learning requirement and provide minimax-optimal rates when the strategy profiles have a minimum probability of playing each action that is bounded away from 0 . Conversely, when \alpha>0 , we can show that such discontinuities are somewhat mitigated. Interestingly, our results reveal that small values of \alpha can substantially degrade the rates through an unavoidable dependence on \alpha^{-1} . Informally, the cause is that when (x,y) play some actions with probability \propto\alpha , small changes in the strategy profiles lead to large changes in the payoff sets. For the upper bounds, the major technical obstacle in obtaining tight rates is establishing this \alpha^{-1} dependence in the approximate-equilibrium case. To this end, focusing on a term that depends only on the x -player, we first show that the Hausdorff error scales with \mathcal{O}(\alpha^{-1}(\hat{x}-x)^{\top}Ay) , where \hat{x} is the empirical mean of x after m samples and A is any feasible payoff for (x,y) (an analogous argument holds for the y -player). Hence, to get a tight rate, we need to show that the empirical value of the game \hat{x}^{\top}Ay converges to the true value x^{\top}Ay as {\mathcal{O}}(\sqrt{\alpha(n+\log(1/\delta))/m}) , where m is the number of samples (while standard concentration of \hat{x} to x would only yield {\mathcal{O}}(\sqrt{n+\log(1/\delta)/m}) ). We argue that such rates are achievable by studying a fractional knapsack problem that arises in controlling the error. 1.1 Related Works Early empirical work on payoff learning treats utilities as regression targets when realized utilities are observed for sampled strategy profiles, enabling supervised payoff approximation ( Vorobeychik et al. 2007 ) . Closer in spirit to our setting, Kuleshov and Schrijvers 2015 introduced inverse game theory in the context of succinctly-representable games and studied the computational problem of finding utilities that rationalize an observed equilibrium (primarily via feasibility of linear/convex programs under structural restrictions). Waugh et al. 2011 study an inverse equilibrium problem (for correlated equilibria) in a parametrized setting, and recover a polytope of compatible payoff functions used to compute the maximum-entropy equilibrium. Recently, Goktas et al. 2024 studied how to recover a single payoff-parameter/Nash-equilibrium pair consistent with observed behavior, relying on some form of oracle access to payoffs during the inverse optimization. This is fundamentally different from our setting, where we aim to recover the feasible set of payoff matrices from i.i.d. equilibrium action samples alone. A related line of works focus on learning adversary models in Stackelberg games, with the main goal of enabling behavioral modeling of attackers in security games ( Haghtalab et al. 2016 ; Sinha et al. 2016 ; Wu et al. 2022 ) . This problem differs from ours in the fact that the learner can probe the adversary ( i.e. , the player with unknown payoffs) by observing their responses to ad hoc strategies. In the context of sponsored search auctions, Nekipelov et al. 2015 studies how to estimate players’ valuations from observed contextual data, by assuming each player places bids following a no-regret algorithm. Finally, Ling et al. 2018 attempts to fit parametric games end-to-end by replacing Nash equilibrium with differentiable fixed points, such as quantal response equilibrium, enabling gradient-based estimation of game parameters. Related to our work is the single-agent version of our problem, usually studied in inverse reinforcement learning (IRL). In IRL, the objective is to infer rewards for which a demonstrated policy is optimal ( Abbeel and Ng 2004 ) . It is well known that even in single-agent settings, the problem is fundamentally ill-posed , as multiple reward functions may be compatible with the observed behavior ( Ng and Russell 2000 ) . Analogously to the game theory setting, there have been several attempts to resolve this ambiguity by focusing on specific selection criteria such as maximum margin, maximum entropy, and minimum Hessian eigenvalue ( Ratliff et al. 2006 ; Metelli et al. 2017 ; Zeng et al. 2022 ) . In this work, we take inspiration from an alternative recent line of research that attempts to overcome the ambiguity issue by estimating the feasible reward set , i.e. , the entire set of reward functions compatible with the observed data ( Metelli et al. 2021 ; Lindner et al. 2022 ; Metelli et al. 2023 ; Poiani et al. 2024 ) . Remarkably, this approach captures the inherent ambiguity of the problem, supports robust prediction and counterfactual reasoning, and avoids committing to arbitrary equilibrium-selection or regularization choices. There are many works that extend the single-agent IRL problem to the multi-agent IRL problem (MAIRL), including, e.g. , ( Natarajan et al. 2010 ; Yu et al. 2019 ; Fu et al. 2021 ; Reddy et al. 2012 ; Zhang et al. 2019 ) . As in inverse game theory, most MAIRL approaches resolve the inherent ambiguity through a priori selection principles or additional modeling assumptions. There are recent exceptions that study the learning problem of returning the entire set of feasible rewards ( Freihaut and Ramponi 2024 ; Tang et al. 2024 ) . However, unlike what happens in game-theoretic applications such as mechanism design, auctions, and pricing, the primary goal of (MA)IRL is to serve as a preprocessing step within a larger pipeline: the learned model and payoff are subsequently used to train multi-agent policies, which are then evaluated in the true environment. As noted by Freihaut and Ramponi 2024 , in strategic settings this pipeline lacks guarantees without further restrictions (such as uniqueness of equilibria or structural assumptions that enforce it, e.g. , entropy-regularized Markov games), since the new learned equilibria for the approximated payoffs might perform arbitrarily bad in the original setting. Finally, a closely related area is revealed preference analysis, which asks whether observed price/purchase observations can be rationalized by utility maximization and constructs utility representations consistent with the available observations ( Samuelson 1948 ; Afriat 1967 ; Varian 1982 ) . There is a related line of works studying the sample complexity of learning to predict optimal bundles of items for a buyer with an unknown demand function from some specific class (e.g., linear, separable piecewise-linear concave, and Leontief) from observed choices ( Beigman and Vohra 2006 ; Zadimoghaddam and Roth 2012 ; Balcan et al. 2014 ) . 2 Preliminaries Mathematical notation For n\in\mathbb{N} , we denote by \Delta_{n} the n -dimensional simplex. Furthermore, [n] denotes the set \{1,\dots,n\} . We also denote by e_{i} the i -th standard basis vector of \mathbb{R}^{n} . For any x\in\Delta_{n} , we denote by \textup{supp}(x)=\{i\in[n]:x_{i}>0\} . Let \mathcal{X}_{1} , \mathcal{X}_{2} be two non-empty subsets of a metric space (\mathcal{X},d) . Then, the Hausdorff distance ( Rockafellar and Wets 2017 ) H_{d}(\mathcal{X}_{1},\mathcal{X}_{2}) is: \displaystyle\max\left\{\sup_{x_{1}\in\mathcal{X}_{1}}\inf_{x_{2}\in\mathcal{X}_{2}}d(x_{1},x_{2}),\sup_{x_{2}\in\mathcal{X}_{2}}\inf_{x_{1}\in\mathcal{X}_{1}}d(x_{1},x_{2})\right\}. We note that H_{d} is defined based on the metric d . In this work, we will be primarily interested in the case where d is the \ell_{\infty} -norm between (subsets of) Euclidean spaces. From now on, we will drop the dependency on d . General-Sum Games and Nash-Equilibrium A general-sum game (GSG) is specified by two matrices A,B\in[-1,1]^{n\times n} . For mixed strategies x,y\in\Delta_{n} , the expected losses incurred by the two players are x^{\top}Ay and x^{\top}By , respectively. Each player seeks to choose a mixed strategy that minimizes their own expected loss. Given \alpha\geq 0 , we say that a pair of strategies x,y is an \alpha -Nash equilibrium for \mathcal{G} if the following conditions are met: x^{\top}Ay\leq e_{i}Ay+\alpha for all i\in[n] , and x^{\top}By\leq x^{\top}Be_{j}+\alpha for all j\in[n] . For any x,y we denote by \mathcal{G}_{\alpha}(x,y) the set of all matrices for which x,y is an \alpha -Nash equilibrium, that is, the set of matrices A,B that verify the following constraints for all indices i,j\in[n]^{2} : \displaystyle x^{\top}Ay\leq e_{i}^{\top}Ay+\alpha\quad\textnormal{ and }\quad x^{\top}By\leq x^{\top}Be_{j}+\alpha. Formally, we can define the following sets: \displaystyle\mathcal{G}^{x}_{\alpha}(x,y)=\{A\in[-1,1]^{n\times n}:x^{\top}Ay\leq e_{i}^{\top}Ay+\alpha~~\forall i\} \displaystyle\mathcal{G}^{y}_{\alpha}(x,y)=\{B\in[-1,1]^{n\times n}:x^{\top}By\leq x^{\top}Be_{j}+\alpha~~\forall j\}, so that we can write \mathcal{G}_{\alpha}(x,y)=\mathcal{G}^{x}_{\alpha}(x,y)\times\mathcal{G}^{y}_{\alpha}(x,y) . Zero-Sum Games and Nash-Equilibrium A zero-sum game (ZSG), instead, is specified by a single matrix A\in[-1,1]^{n\times n} . In this case, x,y\in\Delta_{n}\times\Delta_{n} is an \alpha -Nash equilibrium if x^{\top}Ae_{j}-\alpha\leq x^{\top}Ay\leq e_{i}^{\top}Ay+\alpha holds for every i,j\in[n]^{2} . For any pair of mixed strategies x,y , we denote by \mathcal{Z}_{\alpha}(x,y) the set of all matrices for which x,y is an \alpha -Nash equilibrium, that is: \displaystyle\mathcal{Z}_{\alpha}(x,y)= \displaystyle\left\{A\in[-1,1]^{n\times n}:x^{\top}Ae_{j}-\alpha\leq x^{\top}Ay\right. \displaystyle\hskip 5.69046pt\textnormal{and }\left.x^{\top}Ay\leq e_{i}^{\top}Ay+\alpha,\quad\forall i,j\in[n]^{2}\right\}. Note that \mathcal{Z}_{\alpha}(x,y)\subseteq\mathcal{G}_{\alpha}(x,y) . Indeed, it is sufficient to slice \mathcal{G}_{\alpha}(x,y) on the hyperplane where A=-B . Remark 2.1 . When \alpha is not specified, we refer to the exact equilibrium case. There, we will simply write e.g. , \mathcal{G}(x,y) and \mathcal{Z}(x,y) instead of \mathcal{G}_{\alpha}(x,y) and \mathcal{Z}_{\alpha}(x,y) . Learning Framework We consider a setting in which two players follow a pair of mixed strategies x,y\in\Delta_{n}\times\Delta_{n} that constitute an \alpha -Nash equilibrium of an unknown general-sum game. The objective of the agent is to recover the feasible payoff set \mathcal{G}_{\alpha}(x,y) of matrices for which (x,y) is an \alpha -Nash equilibrium. In particular, the interaction framework is as follows: during each round t\in\mathbb{N} , the learner only observes X_{t},Y_{t}\sim x,y . The learning algorithm takes in input a precision level \epsilon>0 together with a maximum risk parameter \delta\in(0,1) and the parameter \alpha\in[0,1) and is composed of (i) a stopping rule \tau_{\delta} that controls the end of the data acquisition phase, and (ii) a recommendation rule, which we express as a function f that takes in input a pair of matrices A,B and returns 1 if the agent believes that (A,B) belongs to \mathcal{G}_{\alpha}(x,y) and 0 otherwise. We note that f uniquely describes a set \hat{\mathcal{G}}_{\alpha}=\{(A,B):f((A,B))=1\} , which denotes the guess of the agent for all the pair of matrices belonging to \mathcal{G}_{\alpha}(x,y) . Hence, in the following, we will refer to \hat{\mathcal{G}}_{\alpha} as the recommendation rule (similarly, \hat{\mathcal{Z}}_{\alpha} is the guess of the agent for the set \mathcal{Z}_{\alpha}(x,y) ). Among the possible learning algorithms, we are interested in those that are (\epsilon,\delta) -correct w.r.t. the Hausdorff distance. More precisely, the algorithm has to guarantee that: \displaystyle\mathbb{P}(H(\mathcal{G}_{\alpha}(x,y),\hat{\mathcal{G}}_{\alpha})\geq\epsilon)\leq\delta in the general-sum case, with an analogous requirement for \mathcal{Z}_{\alpha} in the zero-sum setting. We make a remark that distinguishes the two learning objectives. At first, one might think that the problem of learning \mathcal{Z}_{\alpha}(x,y) could be easily solved once we have a set \hat{\mathcal{G}}_{\alpha} that approximates \mathcal{G}_{\alpha}(x,y) . Nonetheless, we did not find any trivial way to slice a generic set \hat{\mathcal{G}}_{\alpha} so that it approximates \mathcal{Z}_{\alpha}(x,y) . On one hand, one might be tempted to obtain \hat{\mathcal{Z}}_{\alpha} by slicing \hat{\mathcal{G}}_{\alpha} on A=-B . However, this only ensures one direction of the Hausdorff distance. 1 1 1 Note that, in principle, the resulting set could even be empty. Similarly, one could think of slicing \hat{\mathcal{G}}_{\alpha} by taking all the pair of matrices (A,B) which are almost zero-sum, e.g. , \|A-(-B)\|_{\infty}\leq\epsilon . However, this set might be too large and could fail to satisfy the other direction of the Hausdorff distance. For these reasons, we study zero-sum and general-sum games as separate problems, providing minimax rates for both these settings. 3 Sample Complexity Lower Bound a_{11} a_{21} -1 1 -1 1 P^{*} a_{11} a_{21} -1 1 -1 1 P^{*} a_{11} a_{21} -1 1 -1 1 \mathcal{G}^{x}(x^{0},y^{0}) \mathcal{G}^{x}(x^{1},y^{1}) P^{*} Figure 1 : Visual representations of payoff sets \mathcal{G}^{x}_{\alpha}(\cdot,\cdot) for several pairs of instances (x^{0},y^{0}) (striped red region) and (x^{1},y^{1}) (solid green region). In each figure, a point P^{*} is used to illustrate the Hausdorff distance between the two areas. The y vector is (1,0) in all problems. ( Left ): we set \alpha=0 , x^{0}=(0,1) , x^{1}=(\pi,1-\pi) for any \pi\in(0,1) ; ( Center ): \alpha=0.2 , x^{0}=(0,1) , and x^{1}=(\pi,1-\pi) for \pi=0.05 ; ( Right ): \alpha=0.1 , \epsilon=0.1 , x^{0}=(\tfrac{\alpha}{2},1-\tfrac{\alpha}{2}) and x^{1}=(\tfrac{\alpha(1+3\epsilon)}{2},1-\tfrac{\alpha(1+3\epsilon)}{2}) . In this section, we study the sample complexity of any (\epsilon,\delta) -correct algorithm that learns, with high probability, the set of payoffs induced by an unknown strategy profile (x,y) . In Section 3.1 we discuss the case of \alpha=0 , and in Section 3.2 we discuss the case when \alpha>0 . 3.1 On Exact Equilibria We begin by highlighting a fundamental challenge in learning the feasible sets \mathcal{G}(x,y) and \mathcal{Z}(x,y) from data generated by an exact equilibrium. To build intuition for the problem, we first consider a simple general-sum example. Let n=2 and consider two strategy profiles (x^{0},y^{0}) and (x^{1},y^{1}) such that y^{0}=y^{1}=(1,0) , x^{0}=(0,1) , and x^{1}=(\pi,1-\pi) for some \pi . 2 2 2 We use exactly this construction to prove Theorem 3.1 . Then, it is easy to see that a matrix A belongs to \mathcal{G}^{x}(x^{0},y^{0}) if and only if a_{21}\leq a_{11} , while A belongs to \mathcal{G}^{x}(x^{1},y^{1}) if and only if a_{21}=a_{11} . Hence, as \pi\to 0 , we have a pair of instances that are statistically indistinguishable ( i.e. , the KL divergence between the two instances approaches 0 as \pi\to 0 ) while the Hausdorff between the payoff sets is constant and much larger than \epsilon . This behavior is illustrated in Figure 1 ( left ): for example, the payoff matrix with a_{21}=-1 and a_{11}=1 (marked with P^{\ast} in the figure) belongs to \mathcal{G}(x^{0},y^{0}) but lies at a constant distance from every point on the line a_{21}=a_{11} . Consequently, when x is unknown and must be learned from samples, one cannot distinguish between (x^{0},y^{0}) or (x^{1},y^{1}) , and therefore cannot output an \epsilon -correct estimate of the feasible set. In general, we have the following result. Theorem 3.1 . Let \alpha=0 and \epsilon<1 . Then, there exists a problem instance (x,y)\in\Delta_{n}^{2} such that, for any \pi\in(0,1) and (\epsilon,\delta) -correct algorithm, it holds that: \displaystyle\mathbb{E}_{x,y}[\tau_{\delta}]\geq\Omega\left(\nicefrac{{\log\left(\frac{1}{\delta}\right)}}{{\log\left(\frac{1}{1-\pi}\right)}}\right). (1) This holds both for General and Zero-Sum Games. These results show that there exists an instance in which learning \mathcal{G}(x,y) and/or \mathcal{Z}(x,y) is essentially impossible when \alpha=0 . Indeed, taking the limit of Equation 1 for \pi\to 0 leads to an infinite complexity lower bound. The cause of this phenomenon is intrinsic in the definition of an exact Nash equilibrium. Indeed, the condition for A\in\mathcal{G}^{x}(x,y) , 3 3 3 Similar reasoning holds for \mathcal{G}^{y}(x,y) and \mathcal{Z}(x,y) as well. i.e. , x^{\top}Ay\leq e_{i}^{\top}Ay~\forall i\in[n] , can equivalently be rewritten as follows: 4 4 4 This is a well-known result, e.g. , Gintis 2000 . For completeness, we report a formal statement in Lemma D.8 . \displaystyle x^{\top}Ay=e_{i}^{\top}Ay\quad\forall i:x_{i}>0 (2a) \displaystyle x^{\top}Ay\leq e_{i}^{\top}Ay\quad\forall i:x_{i}=0. (2b) This explains the strong discontinuity of \mathcal{G}^{x}(\cdot,y) when the strategy profile of the x -player changes support, as we observed in the example. To mitigate this issue, a natural assumption is to restrict attention to problem instances in which each action is played with probability bounded away from zero. This is exactly what was done in the IRL problem ( Metelli et al. 2023 ) , where the authors have found a similar phenomenon for the inverse reinforcement learning problem. Specifically, for any x,y , let \pi_{\min}(x,y)\in(0,\tfrac{1}{n}] as: \displaystyle\pi_{\min}(x,y)=\min\left\{\min_{i:x_{i}>0}x_{i},\min_{j:y_{j}>0}y_{j}\right\}. Then, we assume that the agent is dealing with a set of instances such that \pi_{\min}(x,y)\geq\pi_{\min} for some \pi_{\min}>0 . In this case, we derive the following lower bound. Theorem 3.2 . Let \alpha=0 , {\pi}_{\min}>0 , and \epsilon<1/384 . Then, there exists a problem instance (x,y) such that, for any (\epsilon,\delta) -correct algorithm, the following holds: \displaystyle\mathbb{E}_{x,y}[\tau_{\delta}]\geq\Omega\left(\frac{\log\left(\frac{1}{\delta}\right)}{\log\left(\frac{1}{1-\pi_{\min}}\right)}+\frac{n+\log\left(\frac{1}{\delta}\right)}{\epsilon^{2}}\right). (3) This result holds both for General and Zero-Sum Games. We can interpret the first term as the worst-case complexity of learning the support of (x,y) . The second term, instead, arises from the fact that, even after the support is identified, the strategies (x,y) must still be estimated accurately in order to return an (\epsilon,\delta) -correct set in the Hausdorff metric. 3.2 On Approximate Equilibria In this section we provide a lower bound for the case in which players are playing an \alpha -approximate Nash equilibrium. A natural question is whether the difficulty of learning the support of the equilibrium strategies again leads to an infinite sample-complexity bound. We argue that, in this setting, the answer is no . The presence of \alpha in the definitions of \mathcal{G}_{\alpha}(x,y) and \mathcal{Z}_{\alpha}(x,y) prevents these sets from having a representation analogous to Equation 2 . Intuitively, this removes the strong discontinuity exhibited by \mathcal{G}(x,y) and \mathcal{Z}(x,y) when (x,y) vary across strategy profiles with different supports. Informally, the parameter \alpha acts as a tolerance that absorbs the error contributed by actions that are played with small probability. To have an intuitive picture of this phenomenon, it is instructive to consider the simple instance that we analyzed for the \alpha=0 setting. We recall that y=y^{0}=y^{1}=(1,0) , x^{0}=(0,1) , and x^{1}=(\pi,1-\pi) for some \pi . Let \Delta_{A}=a_{21}-a_{11} . Then, we have that \displaystyle A\in\mathcal{G}^{x}_{\alpha}(x^{0},y^{0})\Leftrightarrow-2\leq\Delta_{A}\leq\alpha; \displaystyle A\in\mathcal{G}^{x}_{\alpha}(x^{1},y^{1})\Leftrightarrow\Delta_{A}\in[\max\{-2,-\tfrac{\alpha}{\pi}\},\min\{2,\tfrac{\alpha}{1-\pi}]\}. As \pi\to 0 (or, equivalently, as \pi\ll\alpha ), the two sets collapse. Thus, \alpha is absorbing the error of actions that are played rarely. These sets are depicted in Figure 1 ( center ). While this discussion is reassuring, an important question remains: what is the worst-case dependence of the lower bound on the parameter \alpha ? One can anticipate that, as \alpha\to 0 , the sample complexity must diverge, since actions played with vanishing probability increasingly influence the geometry of the feasible sets. To address this question, we establish the following result. Theorem 3.3 . Let \alpha\in(0,1/4) and \epsilon\leq 1/128 . Then, there exists a problem instance (x,y) such that, for any (\epsilon,\delta) -correct algorithm, the following holds: \displaystyle\mathbb{E}_{x,y}[\tau_{\delta}]\geq\Omega\!\left(\frac{n+\log(\frac{1}{\delta})}{\epsilon^{2}\,\alpha}\right). (4) This result holds both for General and Zero-Sum Games. An important aspect of this result is that the factor \alpha^{-1} multiplies all the other terms in the bound. To understand why this happens, we provide some intuition on how we obtained the term \log(\delta^{-1})/\epsilon^{2}\alpha . 5 5 5 The term n/(\epsilon^{2}\alpha) follows from a related but more involved argument, which we defer to Appendix A.3 . Consider two instances with n=2 such that y^{1}=y^{0}=(1,0) , x^{0}=(\tfrac{\alpha}{2},1-\tfrac{\alpha}{2}) , and x^{1}=(\tfrac{\alpha+3\alpha\epsilon}{2},1-\tfrac{\alpha+3\alpha\epsilon}{2}) . Again, let \Delta_{A}=a_{21}-a_{11} . One can verify that, for \alpha and \epsilon sufficiently small, it holds \displaystyle A\in\mathcal{G}^{x}_{\alpha}(x^{0},y^{0})\implies\Delta_{A}\geq-2; \displaystyle A\in\mathcal{G}^{x}_{\alpha}(x^{1},y^{1})\implies\Delta_{A}\geq-\tfrac{2\alpha}{\alpha+3\alpha\epsilon}>-2. These sets are depicted in Figure 1 ( right ). With some algebraic manipulations, one can show that the distance between these sets is at least 2\epsilon and, therefore, it is important for any algorithm to distinguish (x^{0},y^{0}) and (x^{1},y^{1}) to be (\epsilon,\delta) -correct. However, for \epsilon and \alpha small, the two instances are very similar as the KL divergence between the two is at most \epsilon^{2}\alpha . Therefore, using change-of-measure arguments, we can obtain the term \log(\delta^{-1})/\epsilon^{2}\alpha . This shows that, while \alpha provides a form of protection against the adverse geometry encountered when learning from exact equilibria, its effect is limited since all the other parameter the defines the instance are badly impacted by a small \alpha . 4 Algorithm Procedure 1 0: Number of samples m\in\mathbb{N} , \alpha,\epsilon,\delta\in\mathbb{R}_{\geq 0} 1: while t\in\{1,\dots,m\} do 2: Observe X_{t},Y_{t}\sim x,y and update \hat{x}(t),\hat{y}(t) 3: end while 4: Return \mathcal{G}_{\alpha}(\hat{x}(m),\hat{y}(m)) or \mathcal{Z}_{\alpha}(\hat{x}(m),\hat{y}(m)) The algorithm we developed and analyzed to attain minimax optimality is simple, and its pseudocode can be found in Procedure 1 . It takes as input the parameter of the problem, i.e. , \alpha,\epsilon and \delta , and an additional parameter m\in\mathbb{N} , that denotes the number of samples to collect. Then it simply gathers m observations for the two players x and y , and it stops by returning all the matrices that are an ( \alpha -)Nash equilibrium for the empirical strategy profiles. In other words, the recommendation rule is \mathcal{G}_{\alpha}(\hat{x}(m),\hat{y}(m)) for general-sum games and \mathcal{Z}_{\alpha}(\hat{x}(m),\hat{y}(m)) for zero sum games, where \hat{x}(m) and \hat{y}(m) are the maximum likelihood estimators of x and y after m samples ( i.e. , empirical means). In the following, we drop the dependency on m in \hat{x}(m) and \hat{y}(m) , and we simply write \hat{x} and \hat{y} . In the rest of this section, we show that, by properly choosing the parameter m , Procedure 1 is (\epsilon,\delta) -correct and, furthermore, this choice of m attains the same rate that we presented in the lower bound section. Specifically, in Section 4.1 we discuss our results for the exact equilibrium case and in Section 4.2 for the approximate one. Representation of \mathcal{G}_{\alpha}(\hat{x},\hat{y}) and \mathcal{Z}_{\alpha}(\hat{x},\hat{y}) In the introductory section, we noted that the recommendation rule is in one-to-one correspondence with a set of matrices. Here, we note that the sets produced by our procedure can be represented as linear feasibility problems. Indeed, given \hat{x} and \hat{y} , the set \mathcal{G}_{\alpha}(\hat{x},\hat{y}) and \mathcal{Z}_{\alpha}(\hat{x},\hat{y}) can be described by collections of linear inequalities. 4.1 Optimal Rates for Exact Equilibria As discussed in Section 3.1 , when \alpha=0 the problem of learning the payoff sets is in general ill-posed, as the sample complexity may be infinite. Therefore, we adopt the same assumption of Theorem 3.2 and restrict our attention to instances in which \pi_{\min}(x,y)\geq\pi_{\min}>0 . In this setting, we can show the following. Theorem 4.1 . Consider \alpha=0 and let m\in\widetilde{\mathcal{O}}\left(\frac{\log\left(\frac{1}{\delta}\right)}{\log\left(\frac{1}{1-\pi_{\min}}\right)}+\frac{n+\log\left(\frac{1}{\delta}\right)}{\epsilon^{2}}\right). Then, Procedure 1 is (\epsilon,\delta) -correct and its sample complexity \tau_{\delta} is given by m , both for general and zero-sum games. 6 6 6 \widetilde{O}(\cdot) hides multiplicative constants and \log(n) factors. Theorem 4.1 shows the same rate of the lower bound of Theorem 3.2 , thus showing minimax optimality. As discussed in the proof sketch below, the first term can be interpreted as the number of samples required to learn the support of (x,y) , while the second one, is the number of samples needed for the Hausdorff distance between \mathcal{G}(x,y) and \mathcal{G}(\hat{x},\hat{y}) to be bounded by \epsilon , once the support has been identified. We now present a proof sketch of Theorem 4.1 for the general-sum game problem. Then, we will discuss how to extend this reasoning to the zero-sum setting. Proof sketch of Theorem 4.1 (General-Sum Games) The proof works as follows. We fix a generic m\in\mathbb{N} , and we derive a high-probability upper bound on the Hausdorff distance between \mathcal{G}(x,y) and \mathcal{G}(\hat{x},\hat{y}) . Then, m is chosen so that this upper bound is below \epsilon . The line that we follow to derive this upper bound is inspired by the lower bound of Section 3 . In particular, we know that the support of (x,y) and (\hat{x},\hat{y}) should match in order to avoid the degenerate behavior that we identified. Hence, we start with the assumption that (x,y) and (\hat{x},\hat{y}) are such that \textup{supp}(x)=\textup{supp}(\hat{x}) and \textup{supp}(y)=\textup{supp}(\hat{y}) , and we later discuss how to guarantee that this holds in high probability once m is large enough. Under the assumption that \textup{supp}(x)=\textup{supp}(\hat{x}) and \textup{supp}(y)=\textup{supp}(\hat{y}) , we upper bound H(\mathcal{G}(x,y),\mathcal{G}(\hat{x},\hat{y})) by showing that for any (A,B)\in\mathcal{G}(x,y) there exists (\hat{A},\hat{B})\in\mathcal{G}(\hat{x},\hat{y}) such that: 7 7 7 We also show that the symmetric claim is true, since we need both directions to upper bound the Hausdorff distance. \displaystyle\|A-\hat{A}\|_{\infty}\leq 4\|y-\hat{y}\|_{1},\,\|B-\hat{B}\|_{\infty}\leq 4\|x-\hat{x}\|_{1}. (5) Note that this directly gives us an upper bound on the Hausdorff distance of 4(\|x-\hat{x}\|_{1}+\|y-\hat{y}\|_{1}) . In other words, the error scales linearly with the \ell_{1} -distance between the true strategy profile and the empirical one. Now, we discuss how to obtain Equation 5 (we do that for A , and the construction for B follows from a similar reasoning). Starting from A\in\mathcal{G}^{x}(x,y) (and assuming equal support), we know that if \hat{A}\in\mathcal{G}^{x}(\hat{x},\hat{y}) , then for all i\in\textup{supp}(x) , \hat{x}^{\top}\hat{A}\hat{y}=e_{i}^{\top}\hat{A}\hat{y} . Then, since we want to construct \hat{A} close to A , our goal is to "redistribute" the payoffs of A according to the shift of \hat{x} and \hat{y} so that, in all the rows in \textup{supp}(\hat{x}) , the value obtained by the x-player is left unchanged. To this end, for any i\in\textup{supp}(\hat{x}) , we first define the following quantity: \displaystyle\textstyle\Delta_{i}=\max_{k\in\textup{supp}(\hat{x})}\sum_{j\in[n]}\hat{y}_{j}A_{kj}-\sum_{j\in[n]}\hat{y}_{j}A_{ij}. (6) Here, \Delta_{i}\in[0,2\|y-\hat{y}\|_{1}] represents the maximum payoff difference (for the x -player) in playing the pure strategy i w.r.t. playing any other strategy k\in\textup{supp}(\hat{x}) . Intuitively, this is the shift, for actions in \textup{supp}(\hat{x}) , that \hat{A} should meet so that \hat{A}\in\mathcal{G}^{x}(\hat{x},\hat{y}) . Instead, for all the rows that do not belong to \textup{supp}(\hat{x}) , we only need to ensure that their value remains greater than those of actions in \textup{supp}(\hat{x}) . Given these intuitions, we define \hat{A} as follows: \hat{A}_{ij}:=\begin{cases}\dfrac{A_{ij}}{1+2\|y-\hat{y}\|_{1}},&\text{if }i\in S^{\star}_{\hat{x}},\\[12.0pt] \dfrac{A_{ij}+\Delta_{i}^{x}}{1+2\|y-\hat{y}\|_{1}},&\text{if }i\in\textup{supp}(\hat{x})\setminus S^{\star}_{\hat{x}},\\[12.0pt] \dfrac{A_{ij}+2\|y-\hat{y}\|_{1}}{1+2\|y-\hat{y}\|_{1}},&\text{if }i\notin\textup{supp}(\hat{x}),\end{cases} (7) where S^{\star}_{\hat{x}}=\operatornamewithlimits{argmax}_{k\in\textup{supp}(\hat{x})}\sum_{j\in[n]}\hat{y}_{j}A_{kj} . Ignoring the denominator, which is simply a rescaling to guarantee that \hat{A} remains in [-1,1]^{n\times n} , we observe that the construction does not modify values in S^{\star}_{\hat{x}} , but it increases the values of other actions played in \hat{x} so that any action in \textup{supp}(\hat{x}) yields the same value. Moreover, this construction increases the value of all the actions which are not played by \hat{x} , so that they do not obtain values which are better than actions that are actually played by \hat{x} . It is then possible to verify that \hat{A} belongs to \mathcal{G}^{x}(\hat{x},\hat{y}) , and that \|A-\hat{A}\|_{\infty}\leq 4\|y-\hat{y}\|_{1} . Finally, to conclude the proof, it is sufficient to upper bound with high-probability \|x-\hat{x}\|_{1} and \|y-\hat{y}\|_{1} , and to guarantee that the support of (x,y) aligns with that of (\hat{x},\hat{y}) . Standard concentration tools yield \mathcal{O}(\sqrt{(n+\log(\delta^{-1})/m}) for the former and \widetilde{\mathcal{O}}(\log(\delta^{-1})/\log((1-\pi_{\min})^{-1})) for the latter. Putting everything together this gives Theorem 4.1 . What changes in Zero-Sum Games The proof for the zero-sum game problem follows from a similar argument; however, there is an important difference in how to upper bound the Hausdorff distance once the support of (x,y) and (\hat{x},\hat{y}) matches. Specifically, constructing \hat{A}\in\mathcal{Z}(\hat{x},\hat{y}) is more challenging as now \hat{A} should satisfy the constraints for both players simultaneously. In particular, we show in Section B.2 that a matrix \hat{A} constructed as in Equation 7 fails to meet the constraints for the y -player. To solve this issue ( i.e. , building a matrix that accounts at the same time for changes in x and y ), we show that we can upper bound H(\mathcal{Z}(x,y),\mathcal{Z}(\hat{x},\hat{y})) as: \displaystyle H(\mathcal{Z}(x,y),\mathcal{Z}(\hat{x},y))+H(\mathcal{Z}(\hat{x},y),\mathcal{Z}(\hat{x},\hat{y})). This error decomposition allows us to apply the technique for general-sum games even in the zero-sum setting. 4.2 Optimal Rates for Approximate Equilibria Next, we present the results for the case in which the two players are playing an approximate Nash equilibrium. The following result summarizes our findings. Theorem 4.2 . Consider \alpha>0 and let \displaystyle m\in{\mathcal{O}}\left(\frac{n+\log\left(\frac{1}{\delta}\right)}{\epsilon^{2}\alpha}+\frac{\sqrt{n}\log\left(\frac{1}{\delta}\right)}{\epsilon\alpha}\right). Then Procedure 1 is (\epsilon,\delta) -correct and its sample complexity \tau_{\delta} is given by m , both for general-sum and zero-sum games. For \epsilon sufficiently small, i.e. , \epsilon\lesssim n^{-1/2} , Theorem 4.2 matches the rate of Theorem 3.3 . Hence, Procedure 1 is minimax optimal in the relevant regime of small \epsilon . Proof sketch of Theorem 4.2 (General-Sum Games) As for Theorem 4.1 , we fix a generic m\in\mathbb{N} and derive a high probability upper bound on the Hausdorff distance between the two sets as a function of m . Then, we choose m so that this upper bound is below \epsilon . We start by employing the same decomposition that we used for zero-sum games and \alpha=0 in order to upper bound H(\mathcal{G}_{\alpha}(x,y),\mathcal{G}_{\alpha}(\hat{x},\hat{y})) with \displaystyle H(\mathcal{G}_{\alpha}(x,y),\mathcal{G}_{\alpha}(\hat{x},y))+H(\mathcal{G}_{\alpha}(\hat{x},y),\mathcal{G}_{\alpha}(\hat{x},\hat{y})). This allows us to study only the error components that arise from one of the two strategy profiles, x or y . For clarity of exposition, we explain how to upper bound H(\mathcal{G}_{\alpha}(x,y),\mathcal{G}_{\alpha}(\hat{x},y)) , and in particular we focus on the component corresponding to the first player, namely the sets \mathcal{G}_{\alpha}^{x}(\cdot,\cdot) (as for \mathcal{G}_{\alpha}^{y}(\cdot,\cdot) we have specular arguments). Thus, we start by considering any A\in\mathcal{G}^{x}_{\alpha}(x,y) and construct \hat{A}\in\mathcal{G}^{x}_{\alpha}(\hat{x},y) which is close to A . To this end, we follow a reasoning that is similar to the above, i.e. , we first quantify A ’s constraint violation of \mathcal{G}_{\alpha}^{x}(\hat{x},y) and we try to correct that error with an appropriate construction. Specifically, let us denote by g_{A} the following quantity \displaystyle g_{A}\coloneqq\max_{i\in[n]}\left(\hat{x}^{\top}Ay-e_{i}^{\top}Ay\right). If g_{A}\leq\alpha , then A\in\mathcal{G}^{x}_{\alpha}(\hat{x},y) as \alpha is absorbing the error that arises from \hat{x}\neq x . If g_{A}\geq\alpha , instead, we construct \hat{A} as \hat{A}=\frac{\alpha}{g_{A}}A . This multiplicative construction ensures that \hat{A}\in\mathcal{G}_{\alpha}(\hat{x},y) since, for all i\in[n] , we have that: \displaystyle\hat{x}^{\top}\hat{A}y-e_{i}^{\top}\hat{A}y=\frac{\alpha}{g_{A}}(\hat{x}^{\top}Ay-e_{i}^{\top}Ay)\leq\alpha. The difference between A and \hat{A} is then given by: \displaystyle\|A-\hat{A}\|_{\infty}=\mathcal{O}\left(\frac{g_{A}-\alpha}{g_{A}}\right)\leq\mathcal{O}\left(\frac{(\hat{x}-x)^{\top}Ay}{\alpha}\right), where the second step follows from g_{A}\geq\alpha and the fact that A\in\mathcal{G}_{\alpha}^{x}(x,y) . 8 8 8 We add and subtract x^{\top}Ay . Then we use x^{\top}Ay-e_{i}^{\top}Ay\leq\alpha . Hence, to control the Hausdorff distance related to \mathcal{G}_{\alpha}^{x}(x,y) and \mathcal{G}_{\alpha}^{x}(\hat{x},y) , we need to control: \displaystyle\frac{1}{\alpha}\sup_{A\in\mathcal{G}_{\alpha}^{x}(x,y)}{(\hat{x}-x)^{\top}Ay}{}. (8) At first, one might be tempted to bound (\hat{x}-x)^{\top}Ay with 2\|x-\hat{x}\|_{1} . However, this naive argument yields sub-optimal rates. Since with high probability \|x-\hat{x}\|_{1}\leq\sqrt{(n+\log(\delta^{-1})/m} , the number of samples to ensure that Equation 8 is below \epsilon would roughly be (n+\log(\delta^{-1}))/{\epsilon^{2}\alpha^{2}} , which does not match the lower bound of Theorem 3.3 . The difficulty is that the bound (\hat{x}-x)^{\top}Ay\leq 2\|x-\hat{x}\|_{1} fails to exploit the fact that A\in\mathcal{G}_{\alpha}^{x}(x,y) and does not leverage its geometric structure. In the following, we show how to obtain better rates by exploiting the structure of \mathcal{G}_{\alpha}^{x}(x,y) . Indeed, the properties of \mathcal{G}_{\alpha}^{x}(x,y) will ensure that the variance of (\hat{x}-x)^{\top}Ay is small, thus leading to faster high-probability concentration. To this end, we need to manipulate appropriately Equation 8 . First of all, we bound Equation 8 as follows \displaystyle\sup_{A\in\mathcal{G}_{\alpha}^{x}(x,y)}\frac{\sum_{i:x_{i}>0}(\hat{x}_{i}-x_{i})(Ay)_{i}}{\alpha}+\frac{2\sum_{i:x_{i}=0}\hat{x}_{i}}{\alpha}, (9) to get rid of the components where x_{i}=0 in the optimization problem. Let us ignore the second term for now, and focus on the remaining optimization over A (we return to the second term later in the proof sketch). We will show that this remaining optimization problem presents a hidden fractional knapsack structure. First, let us introduce some notation. For any A\in\mathcal{G}_{\alpha}^{x}(x,y) , let \star\in[n] be any row that belongs to \operatornamewithlimits{argmin}_{i\in[n]}e_{i}^{\top}Ay . Then, let c_{i}=x_{i}[(Ay)_{i}-(Ay)_{\star}] . Then, we can rewrite that optimization problem as: \displaystyle\frac{1}{\alpha}\sup_{c:c_{i}\in[0,2x_{i}]}\sum_{i:x_{i}>0}\frac{\hat{x}_{i}-x_{i}}{x_{i}}c_{i}\quad\text{s.t.~}\sum_{i\in[n]}c_{i}\leq\alpha. (10) This problem is well-known to be solved by a greedy algorithm that sorts the indexes i ’s according to their value ( i.e. , \frac{\hat{x}_{i}-x_{i}}{x_{i}} ) and allocates the maximum value of c_{i} ( i.e. , c_{i}=2x_{i} ), according to this order until the budget is fully depleted, i.e. , is stops once \sum_{i:x_{i}>0}c_{i}>\alpha . Equation 10 can be rewritten as (exact steps in Section C.1 ): \displaystyle\frac{1}{\alpha}\sup_{S\in\mathcal{S}_{\alpha}(x)}\sum_{i\in S}(\hat{x}_{i}-x_{i}), where \mathcal{S}_{\alpha}(x) is given by \displaystyle\textstyle\mathcal{S}_{\alpha}(x)\coloneqq\{S\subseteq[n]:x_{i}>0~\forall i\in S\land\sum_{i\in S}x_{i}\leq\alpha/2\}. Now, the main point is that each set S\in\mathcal{S}_{\alpha}(x) is such that \sum_{i\in{S}}x_{i}\leq\alpha/2 . Hence, we can treat \sum_{i\in S}(\hat{x}_{i}-x_{i}) as a Bernoulli random variable with mean bounded by \alpha/2 (and variance bounded by \alpha/2 ). Using Bernstein’s inequality, we have that \sum_{i\in S}(\hat{x}_{i}-x_{i}) concentrates as \mathcal{O}(\sqrt{\alpha\log(\delta^{-1})/m}) . Taking an union bound over all the possible subsets S\in\mathcal{S}_{\alpha}(x) , we obtain a rate of \mathcal{O}(\sqrt{\alpha(n+\log(\delta^{-1})/m)} . Plugging this result in Equation 9 , we have that only \mathcal{O}(\frac{n+\log(\delta^{-1})}{\epsilon^{2}\alpha}) samples are needed to have the first error term below \epsilon . Now, we still need to control the second term of Equation 9 . It is easy to see that this term is 0 . Indeed, given that \hat{x}_{i} is the empirical mean of x_{i} , x_{i}=0\implies\hat{x}_{i}=0 . However, this only holds for one direction of the argument, i.e. , when we are finding matrices \hat{A}\in\mathcal{G}^{x}_{\alpha}(\hat{x},y) which are close to A\in\mathcal{G}_{\alpha}^{x}(x,y) . In the opposite case, we obtain 2\sum_{i:\hat{x}_{i}=0}x_{i} , which is commonly referred to as missing mass ( McAllester and Ortiz 2003 ) and is not equal to 0 . 9 9 9 There is another asymmetry in bounding that direction of the Hausdorff distance. Specifically, when constructing A\in\mathcal{G}_{\alpha}(x,y) close to some \hat{A}\in\mathcal{G}_{\alpha}(\hat{x},y) , the set \mathcal{S}_{\alpha}(\hat{x}) is stochastic. In the proof, we show that we can reduce it to \mathcal{S}_{2\alpha}(x) by only paying a minor order term in the sample complexity. However, Rajaraman et al. 2020 has shown that this term concentrates around its expectation fast w.r.t. to the number of samples, i.e. , it decays as \frac{\sqrt{n}\log(\delta^{-1})}{m} and hence only \sqrt{n}\log(\delta^{-1})/\epsilon\alpha samples are needed to have that term below \epsilon . 10 10 10 Furthermore, the expectation decays also as \mathcal{O}({m}^{-1}) ). In this way, we concluded the proof of Theorem 4.2 . What changes in Zero-Sum Games For the zero-sum game problem, we follow an analogous argument. The main difference is that we define g_{A} as: \displaystyle g_{A}\coloneqq\max\left\{\max_{i\in[n]}\hat{x}^{\top}Ay-e_{i}^{\top}Ay,\max_{j\in[n]}\hat{x}^{\top}Ae_{j}-\hat{x}^{\top}Ay\right\}. This is due to the fact that the matrix \hat{A} now needs to satisfy a larger set of constraints. We show that the errors introduced by this modification are bounded as in the general-sum case. The challenges for \alpha>0 We conclude by highlighting the challenges introduced by the case \alpha>0 . The main difficulty lies in the fact that when the players are playing an approximate equilibrium, we cannot rely on strong characterizations of their behavior, i.e. , Equation 2 , as we did for the \alpha=0 case. Furthermore, Theorem 3.3 shows that the dependence in \alpha is complex, as it multiplies all the parameters of the problem due to geometric arguments that impact how much the Hausdorff distance changes when the strategy profiles have values around \alpha . 5 Conclusions In this paper, we study the problem of learning from demonstrations the payoff sets that are compatible with an unknown, possibly approximate, equilibrium. We derived tight minimax rates by providing matching lower and upper bounds. As we highlighted, these results required careful considerations on the geometry of the set of feasible payoffs. Our work paves the way for several promising directions for future research. For instance, it would be interesting to extend these results beyond the notion of approximate Nash equilibrium to broader solution concepts, such as correlated equilibria. Furthermore, in this work, we assumed that the strategy profiles (x,y) are fixed. Future research should focus on the case where strategy profiles are evolving, and players are learning the game through regret minimization. Finally, we note that our analysis is instance-independent. In the future, it would be exciting to develop instance-dependent lower and upper bounds that directly depend on the unknown strategy profiles (x,y) . Here, one could take inspiration from the optimal instance-dependent results available in the bandit literature, see, e.g. , Garivier and Kaufmann 2016 . Impact Statement This paper presents work aimed at advancing the field of machine learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here. Appendix Content Table 1 : Table of Symbols Symbol Description n Number of actions per player [n] Set \{1,\dots,n\} \Delta_{n} Probability simplex over [n] e_{i} i -th canonical basis vector \textup{supp}(x) Support of x\in\Delta_{n} A,B Payoff matrices of a general-sum bimatrix game x,y Mixed strategies of the two players \alpha Approximation parameter for \alpha -Nash equilibrium \mathcal{G}_{\alpha}(x,y) Set of payoff matrices (A,B) for which (x,y) is an \alpha -Nash equilibrium \mathcal{G}^{x}_{\alpha}(x,y) Player-1 feasible payoff matrices \mathcal{G}^{y}_{\alpha}(x,y) Player-2 feasible payoff matrices \mathcal{Z}_{\alpha}(x,y) Zero-sum payoff matrices for which (x,y) is an \alpha -Nash equilibrium \hat{\mathcal{G}}_{\alpha},\hat{\mathcal{Z}}_{\alpha} Learner’s estimate of the feasible payoff set (X_{t},Y_{t}) Actions observed at round t , sampled from x\times y \hat{x},\hat{y} Empirical estimates of strategies m Number of observed samples \tau_{\delta} Stopping time of the learning algorithm H(\cdot,\cdot) Hausdorff distance (w.r.t. \ell_{\infty} norm) \|\cdot\|_{1},\|\cdot\|_{\infty} \ell_{1} and \ell_{\infty} norms \epsilon Target Hausdorff accuracy \delta Failure probability \pi_{\min}(x,y) Minimum positive probability in supports of x and y \pi_{\min} Known lower bound on \pi_{\min}(x,y) Appendix A Proof of the lower bounds A.1 Proof of Theorem 3.1 Proof. The proof is split into several steps. Step 1: Instance Construction To prove the result, we consider the case where n=2 . Then, we consider two different instances where the unknown strategy profiles (x^{0},y^{0}) and (x^{1},y^{1}) are defined as follows: \displaystyle x^{0}=(0,1),y^{0}=(1,0) \displaystyle x^{1}=(\pi,1-\pi),y^{1}=(1,0) where \pi is any number in (0,1) . Step 2: Haussdorff Distance Next, we analyze the distances H(\mathcal{G}(x^{0},y^{0}),\mathcal{G}(x^{1},y^{1})) and H(\mathcal{Z}(x^{0},y^{0}),\mathcal{Z}(x^{1},y^{1})) . In particular, we will provide lower bounds on these quantities. We start from H(\mathcal{G}(x^{0},y^{0}),\mathcal{G}(x^{1},y^{1})) . First of all, we note that: \displaystyle H(\mathcal{G}(x^{0},y^{0}),\mathcal{G}(x^{1},y^{1}))\geq\max_{A\in\mathcal{G}^{x}(x^{0},y^{0})}\min_{A^{\prime}\in\mathcal{G}^{x}(x^{1},y^{1})}\|A-A^{\prime}\|_{\infty}. (11) Next, we analyze this lower bound in our simplified case. For any matrix A=\begin{bmatrix}a_{11}&a_{12}\\ a_{21}&a_{22}\end{bmatrix}\in[-1,1]^{2\times 2} , using the definition of \mathcal{G}^{x}(x,y) , we have that: \displaystyle\text{(i) }A\in\mathcal{G}^{x}(x^{0},y^{0})\iff a_{21}\leq a_{11}\text{ and }a_{21}\leq a_{21}\iff a_{21}\leq a_{11}; \displaystyle\text{(ii) }A\in\mathcal{G}^{x}(x^{1},y^{1})\iff\pi a_{11}+(1-\pi)a_{21}\leq\min\{a_{11},a_{21}\}\iff a_{21}\leq a_{11}\text{ and }a_{11}\leq a_{21}\iff a_{21}=a_{11}. We now use this result to further lower bound the r.h.s. of Equation 11 . In particular, we have that: \displaystyle\max_{A\in\mathcal{G}^{x}(x^{0},y^{0})}\min_{A^{\prime}\in\mathcal{G}^{x}(x^{1},y^{1})}\|A-A^{\prime}\|_{\infty} \displaystyle=\max_{a_{11},a_{21}\in[-1,1]^{2}:a_{11}\geq a_{21}}\min_{t\in[-1,1]}\max\{|a_{11}-t|,|a_{21}-t|\} \displaystyle\geq\min_{t\in[-1,1]}\max\{|1-t|,|1+t|\} \displaystyle=1, where the first equality is justified by points (i) and (ii) above, together with the fact that for any A\in\mathcal{G}(x^{0},y^{0}) we can pick A^{\prime}\in\mathcal{G}(x^{1},y^{1}) such that a_{22}=a^{\prime}_{22} and a_{12}=a^{\prime}_{12} , and the inequality follows by setting a_{11}=1 and a_{21}=-1 . Similarly we can analyze H(\mathcal{Z}(x^{0},y^{0}),\mathcal{Z}(x^{1},y^{1})) . In this case, we have: \displaystyle\text{(i) }A\in\mathcal{Z}(x^{0},y^{0})\iff a_{22}\leq a_{21}\leq a_{11}; \displaystyle\text{(ii) }A\in\mathcal{Z}(x^{1},y^{1})\iff\pi a_{21}+(1-\pi)a_{22}\leq\pi a_{11}+(1-\pi)a_{21}\leq\min\{a_{11},a_{21}\}. Hence, we have that: \displaystyle H(\mathcal{Z}(x^{0},y^{0}),\mathcal{Z}(x^{1},y^{1})) \displaystyle\geq\max_{A\in\mathcal{Z}(x^{0},y^{0})}\min_{A^{\prime}\in\mathcal{Z}(x^{1},y^{1})}\|A-A^{\prime}\|_{\infty} \displaystyle\geq\min_{A^{\prime}\in\mathcal{Z}(x^{1},y^{1})}\max\{|1-a^{\prime}_{11}|,|-1-a^{\prime}_{21}|\} (Pick A\in\mathcal{Z}(x^{0},y^{0}):a_{11}=1,a_{21}=-1 ) \displaystyle\geq\min_{t\in[-1,1]}\max\{|1-t|,|1+t|\} ( A^{\prime}\in\mathcal{Z}(x^{1},y^{1})\implies a^{\prime}_{11}=a^{\prime}_{22} ) \displaystyle=1. Therefore, the following holds: \displaystyle H(\mathcal{G}(x^{0},y^{0}),\mathcal{G}(x^{1},y^{1}))\geq 1 (12) \displaystyle H(\mathcal{Z}(x^{0},y^{0}),\mathcal{Z}(x^{1},y^{1}))\geq 1. (13) Step 3: Change of measure We first set some notation. For any x,y\in\Delta_{n} , we have that \mathbb{P}_{x,y}=\prod_{t=1}^{\tau_{\delta}}p_{x}(X_{t})p_{y}(Y_{t}) , where p_{q}(\cdot) denotes the density function of q\in\Delta_{n} . Then, since Equations 12 and 13 hold (and since \epsilon<1 ), we can apply Lemma D.6 . Thus for any (\epsilon,\delta) -correct algorithm, for both GSGs and ZSGs we obtain \displaystyle\delta\geq\frac{1}{4}\exp\left(-\text{KL}(\mathbb{P}_{x^{0},y^{0}},\mathbb{P}_{x^{1},y^{1}})\right). We proceed by analyzing the r.h.s. of this equation. In the case we are considering we have set n=2 . Hence, x,y are Bernoulli distributions, and we obtain that: \displaystyle\text{KL}\left(\mathbb{P}_{x^{0},y^{0}},\mathbb{P}_{x^{1},y^{1}}\right) \displaystyle=\mathbb{E}_{x^{0},y^{0}}\left[\sum_{t=1}^{\tau_{\delta}}\text{KL}(p_{x^{0}}(X_{t}),p_{x^{1}}(X_{t}))\right] (Since y^{0}=y^{1} ) \displaystyle=\mathbb{E}_{x^{0},y^{0}}\left[\tau_{\delta}\right]\text{KL}(p_{x^{0}},p_{x^{1}}) (Wald’s identity) \displaystyle=\mathbb{E}_{x^{0},y^{0}}\left[\tau_{\delta}\right]\log\left(\frac{1}{1-\pi}\right). (By definition of x^{0} , x^{1} ) Then, we obtained that: \displaystyle\delta\geq\frac{1}{4}\exp\left(-\mathbb{E}_{x^{0},y^{0}}\left[\tau_{\delta}\right]\log\left(\frac{1}{1-\pi}\right)\right), which yields: \displaystyle\mathbb{E}_{x^{0},y^{0}}\left[\tau_{\delta}\right]\geq\frac{\log\left(\frac{1}{4\delta}\right)}{\log\left(\frac{1}{1-\pi}\right)}, thus concluding the proof. ∎ A.2 Proof Theorem 3.2 Proof outline Theorem 3.2 is obtained as a combination of three distinct lower bounds, i.e. , Theorems A.1 , A.2 and A.3 . In these theorems, we prove that there exists instances where the sample complexity of any (\epsilon,\delta) -correct algorithm is lower bounded by: \displaystyle\text{(i)}\,\,\frac{\log(\frac{1}{\delta})}{\log\left(\frac{1}{1-\pi_{\min}}\right)},\,\,\text{ (ii)}\,\,\frac{\log\left(\frac{1}{\delta}\right)}{\epsilon^{2}},\,\,\text{ and (iii)}\,\,\frac{n}{\epsilon^{2}}, respectively (here, we neglected the exact multiplicative constants, which are listed below). Importantly, these results hold both for General-Sum and Zero-Sum Games. Then, Theorem 3.2 follows by the following argument. Proof of Theorem 3.2 . It is sufficient to consider the instances presented in Theorems A.1 , A.2 and A.3 . The results then follows from applying \max\{a,b,c\}\geq\frac{1}{3}(a+b+c) . ∎ Now, we proceed by proving Theorems A.1 , A.2 and A.3 . We start from Theorem A.1 , which is a simple corollary of Theorem 3.1 . Theorem A.1 . Let \alpha=0 and \epsilon<1 . Then, there exists a problem instance such that, for any (\epsilon,\delta) -correct algorithm, the following holds: \displaystyle\mathbb{E}[\tau_{\delta}]\geq\frac{\log(\frac{1}{4\delta})}{\log\left(\frac{1}{1-\pi_{\min}}\right)}. This holds for both Zero-Sum and General-Sum Games. Proof. The results follow from applying Theorem 3.1 with \pi=\pi_{\min} . ∎ We now continue with Theorem A.2 . Theorem A.2 . Let \alpha=0 and \epsilon<\tfrac{1}{\sqrt{32}} . Then, there exists a problem instance such that, for any (\epsilon,\delta) -correct algorithm, it holds that \displaystyle\mathbb{E}[\tau_{\delta}]\geq\frac{\log\left(\frac{1}{4\delta}\right)}{16\epsilon^{2}}. This holds both for Zero-Sum and General-Sum Games. Proof. The proof is split into three steps Step 1: Instance Construction We consider the setting with n=2 . Then, we consider two different instances where the unknown strategy profiles (x^{0},y^{0}) and (x^{1},y^{1}) are defined as follows: \displaystyle x^{0}=\left(\frac{1}{2},\frac{1}{2}\right),~y^{0}=\left(\frac{1}{2},\frac{1}{2}\right) \displaystyle x^{1}=\left(\frac{1}{2}+\gamma,\frac{1}{2}-\gamma\right),~y^{1}=\left(\frac{1}{2},\frac{1}{2}\right), where \gamma\in(0,1/2) is a real number that will specified later in the proof. Step 2: Haussdorff Distance Next, we analyze the distances H(\mathcal{G}(x^{0},y^{0}),\mathcal{G}(x^{1},y^{1})) and H(\mathcal{Z}(x^{0},y^{0}),\mathcal{Z}(x^{1},y^{1})) . In particular, we will provide lower bounds on these quantities. We start from H(\mathcal{G}(x^{0},y^{0}),\mathcal{G}(x^{1},y^{1})) . We have that: \displaystyle H(\mathcal{G}(x^{0},y^{0}),\mathcal{G}(x^{1},y^{1})) \displaystyle\geq\max_{B\in\mathcal{G}^{y}(x^{0},y^{0})}\min_{B^{\prime}\in\mathcal{G}^{y}(x^{1},y^{1})}\|B-B^{\prime}\|_{\infty} \displaystyle\geq\min_{B^{\prime}\in\mathcal{G}^{y}(x^{1},y^{1})}\max\{|1-b^{\prime}_{11}|,|b^{\prime}_{12}|,|b^{\prime}_{21}|,|1-b^{\prime}_{22}|\}, where, in the second step, we have set B=\begin{bmatrix}1&0\\ 0&1\end{bmatrix}\in\mathcal{G}^{y}(x^{0},y^{0}) and B^{\prime}=\begin{bmatrix}b^{\prime}_{11}&b^{\prime}_{12}\\ b^{\prime}_{21}&b^{\prime}_{22}\end{bmatrix} . 11 11 11 Indeed, (x^{0})^{\top}By^{0}=\frac{1}{2} and (x^{0})^{\top}Be_{j}=\frac{1}{2} for all j\in[n] . Hence, all the constraints of \mathcal{G}^{y}(x^{0},y^{0}) are satisfied for such B . Now, using the values of (x^{1},y^{1}) , we can rewrite the last optimization problem as follows: \displaystyle\min_{B^{\prime}}\max\{|1-b^{\prime}_{11}|,|b^{\prime}_{12}|,|b^{\prime}_{21}|,|1-b^{\prime}_{22}|\} \displaystyle\text{s.t.\quad}b^{\prime}_{ij}\in[-1,1]\quad\forall i,j\in[n] \displaystyle\phantom{\text{s.t.}\quad}\tfrac{1}{2}\Bigl((\tfrac{1}{2}+\gamma)(b^{\prime}_{11}+b^{\prime}_{12})+(\tfrac{1}{2}-\gamma)(b^{\prime}_{21}+b^{\prime}_{22})\Bigr)\leq b^{\prime}_{11}(\tfrac{1}{2}+\gamma)+b^{\prime}_{21}(\tfrac{1}{2}-\gamma), \displaystyle\phantom{\text{s.t.}\quad}\tfrac{1}{2}\Bigl((\tfrac{1}{2}+\gamma)(b^{\prime}_{11}+b^{\prime}_{12})+(\tfrac{1}{2}-\gamma)(b^{\prime}_{21}+b^{\prime}_{22})\Bigr)\leq b^{\prime}_{12}(\tfrac{1}{2}+\gamma)+b^{\prime}_{22}(\tfrac{1}{2}-\gamma). Introducing an additional variable t\coloneqq\|B-B^{\prime}\|_{\infty}\geq 0 and simplifying the constraints, we can rewrite this optimization problem as follows: \displaystyle\min_{B^{\prime}\in[-1,1]^{2\times 2},t\geq 0}t (14) \displaystyle\text{s.t.\quad}|1-b^{\prime}_{11}|\leq t,~~~|b^{\prime}_{12}|\leq t,~~~|b^{\prime}_{21}|\leq t,~~~|1-b^{\prime}_{22}|\leq t \displaystyle(b^{\prime}_{11}-b^{\prime}_{12})(\tfrac{1}{2}+\gamma)+(b^{\prime}_{21}-b^{\prime}_{22})(\tfrac{1}{2}-\gamma)=0. Let t(B^{\prime}) be the optimal value of Problem ( 14 ) for any feasible matrix B^{\prime} . In the following, we will prove that t(B^{\prime})\geq\gamma for any feasible matrix B^{\prime} . To this end, let us introduce the following vector g^{\top}=[(\tfrac{1}{2}+\gamma),(-\tfrac{1}{2}-\gamma),(\tfrac{1}{2}-\gamma),(-\tfrac{1}{2}+\gamma)] . Then, the last linear constraints in ( 14 ) can be rewritten as g^{\top}z(B^{\prime})=0 , where z(B^{\prime}) denotes the flattened version of matrix B^{\prime} , i.e., z(B^{\prime})=(b^{\prime}_{11},b^{\prime}_{12},b^{\prime}_{21},b^{\prime}_{22}) . Next, let z_{0}=(1,0,0,1) . Note that g^{\top}z_{0}=2\gamma . Thus, for any feasible B^{\prime} , g^{\top}(z(B^{\prime})-z_{0})=-2\gamma . Therefore, \displaystyle 2\gamma \displaystyle=|g^{\top}(z(B^{\prime})-z_{0})| \displaystyle\leq\|g\|_{1}\|z(B^{\prime})-z_{0}\|_{\infty} (Hölder’s inequality) \displaystyle=\|g\|_{1}t(B^{\prime}) (Since z_{0}=z(B) and t(B^{\prime})=\|B^{\prime}-B\|_{\infty} ) \displaystyle=2t(B^{\prime}) (Definition of g for \gamma\in(0,\tfrac{1}{2}) ) Thus, we obtained that, for any feasible matrix B^{\prime} , t(B^{\prime})\geq\gamma . Choosing \gamma=2\epsilon , 12 12 12 This choice is valid since \gamma\in(0,\tfrac{1}{2}) and \epsilon<1/4 by assumption. we obtained that \displaystyle H(\mathcal{G}(x^{0},y^{0}),\mathcal{G}(x^{1},y^{1}))\geq 2\epsilon. (15) Next, we analyze H(\mathcal{Z}(x^{0},y^{0}),\mathcal{Z}(x^{1},y^{1})) . We have that: \displaystyle H(\mathcal{Z}(x^{0},y^{0}),\mathcal{Z}(x^{1},y^{1})) \displaystyle\geq\max_{A\in\mathcal{Z}(x^{0},y^{0})}\min_{A^{\prime}\in\mathcal{Z}(x^{1},y^{1})}\|A-A^{\prime}\|_{\infty} \displaystyle\geq\min_{A^{\prime}\in\mathcal{Z}(x^{1},y^{1})}\max\bigl\{|1-a^{\prime}_{11}|,\ |a^{\prime}_{12}|,\ |a^{\prime}_{21}|,\ |1-a^{\prime}_{22}|\bigr\}, where, in the second step, we have set A=\begin{bmatrix}1&0\\ 0&1\end{bmatrix}\in\mathcal{Z}(x^{0},y^{0}). Now, using the values of (x^{1},y^{1}) , we can rewrite the last optimization problem as follows: \displaystyle\min_{A^{\prime}}\max\{|1-a^{\prime}_{11}|,\ |a^{\prime}_{12}|,\ |a^{\prime}_{21}|,\ |1-a^{\prime}_{22}|\} \displaystyle\text{s.t.\quad}a^{\prime}_{ij}\in[-1,1]\quad\forall i,j\in\{1,2\} \displaystyle\phantom{\text{s.t.}\quad}(\tfrac{1}{2}+\gamma)a^{\prime}_{11}+(\tfrac{1}{2}-\gamma)a^{\prime}_{21}\leq\tfrac{1}{2}\Bigl((\tfrac{1}{2}+\gamma)(a^{\prime}_{11}+a^{\prime}_{12})+(\tfrac{1}{2}-\gamma)(a^{\prime}_{21}+a^{\prime}_{22})\Bigr) \displaystyle\phantom{\text{s.t.}\quad}(\tfrac{1}{2}+\gamma)a^{\prime}_{12}+(\tfrac{1}{2}-\gamma)a^{\prime}_{22}\leq\tfrac{1}{2}\Bigl((\tfrac{1}{2}+\gamma)(a^{\prime}_{11}+a^{\prime}_{12})+(\tfrac{1}{2}-\gamma)(a^{\prime}_{21}+a^{\prime}_{22})\Bigr) \displaystyle\phantom{\text{s.t.}\quad}\tfrac{1}{2}\Bigl((\tfrac{1}{2}+\gamma)(a^{\prime}_{11}+a^{\prime}_{12})+(\tfrac{1}{2}-\gamma)(a^{\prime}_{21}+a^{\prime}_{22})\Bigr)\leq\tfrac{1}{2}(a^{\prime}_{11}+a^{\prime}_{12}) \displaystyle\phantom{\text{s.t.}\quad}\tfrac{1}{2}\Bigl((\tfrac{1}{2}+\gamma)(a^{\prime}_{11}+a^{\prime}_{12})+(\tfrac{1}{2}-\gamma)(a^{\prime}_{21}+a^{\prime}_{22})\Bigr)\leq\tfrac{1}{2}(a^{\prime}_{21}+a^{\prime}_{22}). Introducing the additional variable t\coloneqq\|A-A^{\prime}\|_{\infty}\geq 0 and simplifying the constraints, we can rewrite the above minimization as the following optimization problem: \displaystyle\min_{A^{\prime}\in[-1,1]^{2\times 2},~t\geq 0}\quad t (16) \displaystyle\text{s.t.}\quad|1-a^{\prime}_{11}|\leq t,\quad|a^{\prime}_{12}|\leq t,\quad|a^{\prime}_{21}|\leq t,\quad|1-a^{\prime}_{22}|\leq t, \displaystyle(\tfrac{1}{2}+\gamma)(a^{\prime}_{11}-a^{\prime}_{12})+(\tfrac{1}{2}-\gamma)(a^{\prime}_{21}-a^{\prime}_{22})=0, \displaystyle\tfrac{1}{2}\Bigl((\tfrac{1}{2}+\gamma)(a^{\prime}_{11}+a^{\prime}_{12})+(\tfrac{1}{2}-\gamma)(a^{\prime}_{21}+a^{\prime}_{22})\Bigr)\leq\tfrac{1}{2}(a^{\prime}_{11}+a^{\prime}_{12}) \displaystyle\tfrac{1}{2}\Bigl((\tfrac{1}{2}+\gamma)(a^{\prime}_{11}+a^{\prime}_{12})+(\tfrac{1}{2}-\gamma)(a^{\prime}_{21}+a^{\prime}_{22})\Bigr)\leq\tfrac{1}{2}(a^{\prime}_{21}+a^{\prime}_{22}). Now, as we did for General-Sum Games, let t(A^{\prime}) be the optimal value of Problem ( 16 ) for any feasible matrix A^{\prime} . In the following, we will prove that t(A^{\prime})\geq\gamma for any feasible matrix A^{\prime} . To this end, let us introduce the following vector g^{\top}=[(\tfrac{1}{2}+\gamma),(-\tfrac{1}{2}-\gamma),(\tfrac{1}{2}-\gamma),(-\tfrac{1}{2}+\gamma)] . Then, the second constraint in ( 16 ) can be rewritten as g^{\top}z(A^{\prime})=0 , where z(A^{\prime}) denotes the flattened version of matrix A^{\prime} , i.e., z(A^{\prime})=(a^{\prime}_{11},a^{\prime}_{12},a^{\prime}_{21},a^{\prime}_{22}) . Next, let z_{0}=(1,0,0,1) . Note that g^{\top}z_{0}=2\gamma . Thus, for any feasible A^{\prime} , g^{\top}(z(A^{\prime})-z_{0})=-2\gamma . Therefore, \displaystyle 2\gamma \displaystyle=|g^{\top}(z(A^{\prime})-z_{0})| \displaystyle\leq\|g\|_{1}\|z(A^{\prime})-z_{0}\|_{\infty} (Hölder’s inequality) \displaystyle=\|g\|_{1}t(A^{\prime}) (Since z_{0}=z(A) and t(A^{\prime})=\|A^{\prime}-A\|_{\infty} ) \displaystyle=2t(A^{\prime}). (Definition of g for \gamma\in(0,\tfrac{1}{2}) ) Thus, we obtained that, for any feasible matrix A^{\prime} , t(A^{\prime})\geq\gamma . Choosing \gamma=2\epsilon , 14 14 14 This choice is valid since \gamma\in(0,\tfrac{1}{2}) and \epsilon<1/4 by assumption. we obtained that \displaystyle H(\mathcal{Z}(x^{0},y^{0}),\mathcal{Z}(x^{1},y^{1}))\geq 2\epsilon. (17) Step 3: Change of measure For any x,y\in\Delta_{n} , let \mathbb{P}_{x,y}=\prod_{t=1}^{\tau_{\delta}}p_{x}(X_{t})p_{y}(Y_{t}) , where p_{q}(\cdot) denotes the density function of q\in\Delta_{n} . Then, since Equations 15 and 17 holds, we can apply Lemma D.6 . Thus, both for GSGs and ZSGs, we have that: \displaystyle\delta\geq\frac{1}{4}\exp\left(-\text{KL}(\mathbb{P}_{x^{0},y^{0}},\mathbb{P}_{x^{1},y^{1}})\right). We proceed by analyzing the r.h.s. of this equation. In the case we are considering we have set n=2 . Hence, x,y are Bernoulli distributions, and we obtain that: \displaystyle\text{KL}\left(\mathbb{P}_{x^{0},y^{0}},\mathbb{P}_{x^{1},y^{1}}\right) \displaystyle=\mathbb{E}_{x^{0},y^{0}}\left[\sum_{t=1}^{\tau_{\delta}}\text{KL}(p_{x^{0}}(X_{t}),p_{x^{1}}(X_{t})\right] (Since y^{0}=y^{1} ) \displaystyle=\mathbb{E}_{x^{0},y^{0}}\left[\tau_{\delta}\right]\text{KL}(p_{x^{0}},p_{x^{1}}) (Wald’s identity) \displaystyle=\frac{1}{2}\mathbb{E}_{x^{0},y^{0}}\left[\tau_{\delta}\right]\log\!\left(\frac{1}{1-16\epsilon^{2}}\right) (By def. of x^{0},x^{1} and setting \gamma=2\epsilon ) \displaystyle\leq\mathbb{E}_{x^{0},y^{0}}\left[\tau_{\delta}\right]\frac{8\epsilon^{2}}{1-16\epsilon^{2}} ( -\log(1-x)\leq\frac{x}{1-x} for x\leq 1 ) \displaystyle\leq 16\mathbb{E}_{x^{0},y^{0}}\left[\tau_{\delta}\right]\epsilon^{2} ( \epsilon\leq\sqrt{\tfrac{1}{32}}\implies(1-16\epsilon^{2})\geq\tfrac{1}{2} ) Hence, we obtained that: \displaystyle\delta\geq\frac{1}{4}\exp\left(-16\mathbb{E}_{x^{0},y^{0}}\left[\tau_{\delta}\right]\epsilon^{2}\right) Rearranging the terms yields: \displaystyle\mathbb{E}_{x^{0},y^{0}}\left[\tau_{\delta}\right]\geq\frac{\log\left(\frac{1}{4\delta}\right)}{16\epsilon^{2}}, which concludes the proof. ∎ Finally, we prove Theorem A.3 . Theorem A.3 . Let \alpha=0 , n\geq 20 , n\mod 16=0 and \epsilon\leq\frac{1}{384} . Then, there exists a problem instance such that, for any (\epsilon,\delta) -correct algorithm, the following holds: \displaystyle\mathbb{E}[\tau_{\delta}]\geq\frac{\log(2)n}{40(192)^{2}\epsilon^{2}}. This holds both for Zero-Sum and General-Sum Games. Proof. As before, the proof is split into three main steps. Step 1: Instance Construction In the following, taking inspiration from the work of Jin et al. 2020 , we construct a set of different n -dimensional instances. We assume that n\geq 16 and that n\mod 16=0 . These instances are parameterized with an n -dimensional vector v\in\{-1,1\}^{n} such that \sum_{k=1}^{n}v_{k}=0 and are constructed as follows. We denote by \mathcal{V} the set of vectors that satisfies these two requirements. Now, let \gamma\in(0,\tfrac{1}{2}) ; we define (x^{v},y^{v}) as follows: \displaystyle x^{v}=(1,0,\dots 0)\text{ and }y^{v}=\left(\frac{1+\gamma v_{1}}{n},\frac{1+\gamma v_{2}}{n},\dots,\frac{1+\gamma v_{n}}{n}\right). Observe that n\geq 2,\gamma\in(0,\tfrac{1}{2}),\text{and~}v\in\{-1,1\}^{n} . Therefore, by construction, we have that y^{v}\in\Delta_{n} . In the rest of the proof, we restrict our attention to vectors v belonging to a subset \bar{\mathcal{V}} of \mathcal{V} . In particular, consider a pair v,w\in\bar{\mathcal{V}} and let \displaystyle D^{+}_{v,w}=\{k\in[n]:v_{k}=1\text{ and }w_{k}=-1\}\quad\quad D^{-}_{v,w}=\{k\in[n]:v_{k}=-1\text{ and }w_{k}=1\}, where we will drop the explicit dependence on v,w when clear from context. Then, we require that for any pair v,w\in\bar{\mathcal{V}} it holds \displaystyle|D^{+}_{v,w}|=|D^{-}_{v,w}|\geq\frac{n}{64}. (18) It is easy to see that |D^{+}_{v,w}|=|D^{-}_{v,w}| is granted for any pair v,w\in\mathcal{V} . The requirement that, e.g. , |D^{+}_{v,w}|\geq\tfrac{n}{64} , is instead equivalent to impose that \sum_{k=1}^{n}|v_{k}-w_{k}|\geq\tfrac{n}{16} . Thanks to Lemma D.12 , we know that: \displaystyle\exists\bar{\mathcal{V}}\subseteq\mathcal{V}\,\text{ s.t. }\,\forall v,w\in\bar{\mathcal{V}},\quad\sum_{k=1}^{n}|v_{k}-w_{k}|\geq\frac{n}{16}\text{~and~}|\bar{\mathcal{V}}|>2^{\frac{n}{5}}. (19) In the following step, we will consider two generic profiles (x^{v},y^{v}) and (x^{w},y^{w}) such that v,w\in\bar{\mathcal{V}} . Step 2: Haussdorff Distance We analyze the distances H(\mathcal{G}(x^{v},y^{v}),\mathcal{G}(x^{w},y^{w})) and H(\mathcal{Z}(x^{v},y^{v}),\mathcal{Z}(x^{w},y^{w})) . In particular, we will provide lower bounds on these quantities. We start from H(\mathcal{G}(x^{v},y^{v}),\mathcal{G}(x^{w},y^{w})) . We have that: \displaystyle H(\mathcal{G}(x^{v},y^{v}),\mathcal{G}(x^{w},y^{w})) \displaystyle\geq\max_{A\in\mathcal{G}^{x}(x^{v},y^{v})}\min_{A^{\prime}\in\mathcal{G}^{x}(x^{w},y^{w})}\|A-A^{\prime}\|_{\infty} \displaystyle\geq\min_{A^{\prime}\in\mathcal{G}^{x}(x^{w},y^{w})}\|A-A^{\prime}\|_{\infty}, where we define the matrix A\in\mathcal{G}(x^{v},y^{v}) as A_{ij}:=\begin{cases}0,&i=1,j\in[n]\\[2.0pt] \tfrac{1}{3},&i>1,j\in D^{+},\\[2.0pt] -\tfrac{1}{3}\kappa,&i>1,j\in D^{-},\\[2.0pt] 0,&i>1,j\in[n]\setminus(D^{+}\cup D^{-}),\end{cases}\qquad\text{where}\qquad\kappa\coloneqq\frac{\sum_{j\in D^{+}}y^{v}_{j}}{\sum_{j\in D^{-}}y^{v}_{j}}. (20) Before continuing, we prove that A constructed as in Equation 20 satisfies A\in\mathcal{G}(x^{v},y^{v}) . To this end, we first verify that A\in[-1,1]^{n\times n} . It suffices to check that \kappa\leq 3 . With some simple manipulations, we have that: \displaystyle\kappa=\frac{\sum_{j\in D^{+}}y^{v}_{j}}{\sum_{j\in D^{-}}y^{v}_{j}}=\frac{\frac{|D^{+}|(1+\gamma)}{n}}{\frac{|D^{-}|(1-\gamma)}{n}}=\frac{1+\gamma}{1-\gamma}\leq 3, where the second equality is due to Equation 18 and the last step is due to \gamma\in(0,\tfrac{1}{2}) . Next, we verify that A satisfies the Nash constraints. Since x^{v}=e_{1} , those constraints are equivalent to (e_{1}-e_{i})^{\top}Ay^{v}\leq 0 for all i\in[n] . Using the definition of A and y^{v} we have that: \displaystyle(e_{1}-e_{i})^{\top}Ay^{v} \displaystyle=\sum_{j=1}^{n}y_{j}^{v}(A_{1j}-A_{ij}) \displaystyle=-\sum_{j=1}^{n}y_{j}^{v}A_{ij} ( A_{1j}=0 for all j\in[n] ) \displaystyle=-\frac{1}{3}\left(\sum_{j\in D^{+}}y_{j}^{v}-\kappa\sum_{j\in D^{-}}y_{j}^{v}\right) (Definition of A ) \displaystyle=0. (Definition of \kappa ) Hence, all constraints are tight and A\in\mathcal{G}^{x}(x^{v},y^{v}) . We can now continue by lower bounding \min_{A^{\prime}\in\mathcal{G}^{x}(x^{w},y^{w})}\|A-A^{\prime}\|_{\infty} . In the following, we will prove that: \displaystyle\min_{A^{\prime}\in\mathcal{G}^{x}(x^{w},y^{w})}\|A-A^{\prime}\|_{\infty}\geq\frac{2|D^{+}|\gamma}{3n(1-\gamma)}. (21) To this end, consider any matrix A^{\prime}\in\mathcal{G}^{x}(x^{w},y^{w}) . Let \Delta(A^{\prime})=A^{\prime}-A so that A^{\prime}=\Delta(A^{\prime})+A . Since x^{w}=e_{1} , then A^{\prime} satisfies (e_{1}-e_{i})^{\top}A^{\prime}y^{w}\leq 0 for all i\in[n] . Moreover, for all A^{\prime}\in\mathcal{G}^{x}(x^{w},y^{w}) it holds that: \displaystyle(e_{1}-e_{i})^{\top}A^{\prime}y^{w} \displaystyle=(e_{1}-e_{i})^{\top}(\Delta(A^{\prime})+A)y^{w} \displaystyle=(e_{1}-e_{i})^{\top}\Delta(A^{\prime})y^{w}+(e_{1}-e_{i})^{\top}Ay^{w} \displaystyle=(e_{1}-e_{i})^{\top}\Delta(A^{\prime})y^{w}-\sum_{j=1}^{n}y^{w}_{j}A_{ij} ( A_{1j}=0 for all j\in[n] ) \displaystyle=(e_{1}-e_{i})^{\top}\Delta(A^{\prime})y^{w}-\frac{1}{3}\left(\frac{|D^{+}|(1-\gamma)}{n}-\kappa\frac{|D^{-}|(1+\gamma)}{n}\right) (Def. of A,y^{w},D^{+} and D^{-} .) \displaystyle=(e_{1}-e_{i})^{\top}\Delta(A^{\prime})y^{w}-\frac{1}{3}\left(\frac{|D^{+}|(1-\gamma)}{n}-\frac{|D^{+}|(1+\gamma)^{2}}{n(1-\gamma)}\right) (Def. of \kappa ) \displaystyle=(e_{1}-e_{i})^{\top}\Delta(A^{\prime})y^{w}+\frac{4|D^{+}|\gamma}{3n(1-\gamma)} \displaystyle\leq 0 ( A^{\prime}\in\mathcal{G}^{x}(x^{w},y^{w}) ) Then, it follows that any feasible A^{\prime}\in\mathcal{G}^{x}(x^{w},y^{w}) satisfies (e_{i}-e_{1})^{\top}\Delta(A^{\prime})y^{w}\geq\frac{4|D^{+}|\gamma}{3n(1-\gamma)} . This yields the following: \displaystyle\frac{4|D^{+}|\gamma}{3n(1-\gamma)} \displaystyle\leq(e_{i}-e_{1})^{\top}\Delta(A^{\prime})y^{w} \displaystyle\leq\sum_{j=1}^{n}y^{w}_{j}\left(|\Delta(A^{\prime})_{ij}|+|\Delta(A^{\prime})_{1j}|\right) \displaystyle\leq 2\sum_{j=1}^{n}y^{w}_{j}\|\Delta(A^{\prime})\|_{\infty} \displaystyle=2\|A-A^{\prime}\|_{\infty}, which proves Equation 21 . Combining this result with Equation 18 gives H(\mathcal{G}(x^{v},y^{v}),\mathcal{G}(x^{w},y^{w}))\geq\frac{\gamma}{96} . Picking \gamma=192\epsilon , 15 15 15 This choice is valid. Indeed, \epsilon\leq\frac{1}{384} by assumption and we imposed \gamma<\frac{1}{2} . we obtained \displaystyle H(\mathcal{G}(x^{v},y^{v}),\mathcal{G}(x^{w},y^{w}))\geq 2\epsilon. (22) Next we analyze H\!\left(\mathcal{Z}(x^{v},y^{v}),\mathcal{Z}(x^{w},y^{w})\right) . We have that: \displaystyle H\!\left(\mathcal{Z}(x^{v},y^{v}),\mathcal{Z}(x^{w},y^{w})\right) \displaystyle\geq\max_{A\in\mathcal{Z}(x^{v},y^{v})}\min_{A^{\prime}\in\mathcal{Z}(x^{w},y^{w})}\|A-A^{\prime}\|_{\infty} \displaystyle\geq\min_{A^{\prime}\in\mathcal{Z}(x^{w},y^{w})}\|A-A^{\prime}\|_{\infty}, where the matrix A\in\mathcal{Z}(x^{v},y^{v}) is defined as in Equation 20 . We already proved above that A\in[-1,1]^{n\times n} . It remains to prove that it satisfies the Nash constraints for zero-sum games, i.e. , that A satisfies: \displaystyle e_{1}^{\top}Ae_{j}\leq e_{1}^{\top}Ay^{v}\leq e_{i}^{\top}Ay^{v}\quad\forall i,j\in[n]. We already proved above that e_{1}^{\top}Ay^{v}\leq e_{i}^{\top}Ay^{v} holds for all i\in[n] . We only need to check that e_{1}^{\top}Ae_{j}\leq e_{1}^{\top}Ay^{v} holds for all j\in[n] . Since A_{1j}=0 for all j\in[n] , we have that: \displaystyle e_{1}^{\top}Ae_{j}=A_{1j}=0=\sum_{j\in[n]}y^{v}_{j}A_{1j}=e_{1}^{\top}Ay^{v}, thus showing that A\in\mathcal{Z}(x^{v},y^{v}) . We now continue by lower bounding \min_{A^{\prime}\in\mathcal{Z}(x^{w},y^{w})}\|A-A^{\prime}\|_{\infty} . We can follow the same reasoning that we used for General-Sum Games to prove that: \displaystyle H(\mathcal{Z}(x^{v},y^{v}),\mathcal{Z}(x^{w},y^{w}))\geq 2\epsilon. (23) Step 3: Change of measure For any x,y\in\Delta_{n} , let \mathbb{P}_{x,y}=\prod_{t=1}^{\tau_{\delta}}p_{x}(X_{t})p_{y}(Y_{t}) , where p_{q}(\cdot) denotes the density function of q\in\Delta_{n} . Then, since Equations 22 and 23 holds, we can apply Lemma D.7 using the set of instances \{(x^{v},y^{v})\}_{v\in\bar{\mathcal{V}}} and (x^{0},y^{0})=\!(e_{1},(\tfrac{1}{n},\dots\tfrac{1}{n})\!) as base instance. Thus, for both GSGs and ZSGs we have that for any (\epsilon,\delta) -correct algorithm it holds \displaystyle\delta\geq 1-\frac{1}{\log(|\bar{\mathcal{V}}|)}\left(\frac{1}{|\bar{\mathcal{V}}|}\sum_{v\in\bar{\mathcal{V}}}\textup{KL}(\mathbb{P}_{x^{v},y^{v}},\mathbb{P}_{x^{0},y^{0}})+\log 2\right). We proceed by analyzing the kl-divergence term in the r.h.s. of this equation. Specifically, we have that: \displaystyle\textup{KL}(\mathbb{P}_{x^{v},y^{v}},\mathbb{P}_{x^{0},y^{0}}) \displaystyle=\mathbb{E}_{(x^{v},y^{v})}\left[\sum_{t=1}^{\tau_{\delta}}\text{KL}(p_{y^{v}}(Y_{t}),p_{y^{0}}(Y_{t}))\right] (Since x^{v}=x^{0} ) \displaystyle=\mathbb{E}_{(x^{v},y^{v})}\left[\tau_{\delta}\right]\text{KL}(p_{y^{v}},p_{y^{0}}) (Wald’s identity) \displaystyle\leq 2(192^{2})\epsilon^{2}\mathbb{E}_{(x^{v},y^{v})}\left[\tau_{\delta}\right]. ( Lemma D.4 ) Plugging this result in the previous equation and rearranging the terms, we obtain: \displaystyle\frac{1}{|\bar{\mathcal{V}}|}\sum_{v\in\bar{\mathcal{V}}}\mathbb{E}_{(x^{v},y^{v})}\left[\tau_{\delta}\right]\geq\frac{(1-\delta)\log(|\bar{\mathcal{V}}|)+\log 2}{2(192)^{2}\epsilon^{2}}. Since \mathbb{E}_{(x^{v},y^{v})}\left[\tau_{\delta}\right]\leq\max_{w\in\bar{\mathcal{V}}}\mathbb{E}_{(x^{w},y^{w})}\left[\tau_{\delta}\right] for all v\in\bar{\mathcal{V}} , the last equation implies that there exists \bar{w}\in\bar{\mathcal{V}} such that: \displaystyle\mathbb{E}_{(x^{\bar{w}},y^{\bar{w}})}\left[\tau_{\delta}\right]\geq\frac{(1-\delta)\log(|\bar{\mathcal{V}}|)+\log 2}{2(192)^{2}\epsilon^{2}} Finally, we have \displaystyle\mathbb{E}_{(x^{\bar{w}},y^{\bar{w}})}\left[\tau_{\delta}\right] \displaystyle\geq\frac{(1-\delta)\log(|\bar{\mathcal{V}}|)+\log 2}{2(192)^{2}\epsilon^{2}} \displaystyle\geq\frac{\log(2)((1-\delta)\frac{n}{5}+1)}{2(192)^{2}\epsilon^{2}} ( Equation 19 ) \displaystyle\geq\frac{\log(2)n}{40(192)^{2}\epsilon^{2}}, ( \delta\leq\tfrac{1}{2} and n\geq 20 ) which concludes the proof. ∎ A.3 Proof of Theorem 3.3 Similarly to Theorem 3.2 , the proof of Theorem 3.3 is obtained by combining two distinct lower bounds, i.e. , Theorems A.4 and A.5 . In these theorems, we prove that there exist instances where the sample complexity of any (\epsilon,\delta) -correct algorithm is lower bounded by: \displaystyle\text{ (i)}\,\,\frac{\log\left(\frac{1}{\delta}\right)}{\epsilon^{2}\alpha},\,\,\text{ and (ii)}\,\,\frac{n}{\epsilon^{2}\alpha}, here, we only dropped the multiplicative constants. These results hold both for General-Sum Games and Zero-Sum Games. Theorem 3.3 follows by the following argument. Proof of Theorem 3.3 . It is sufficient to consider the case where the agent observes the instances presented in Theorems A.4 and A.5 with probability (\tfrac{1}{2},\tfrac{1}{2}) . The result is then straightforward. ∎ We now proceed by proving Theorems A.4 and A.5 . Theorem A.4 . Let \alpha\in(0,\tfrac{1}{4}) and \epsilon\leq\tfrac{1}{8} . Then, there exists a problem instance such that, for any (\epsilon,\delta) -correct algorithm, the following holds: \mathbb{E}[\tau_{\delta}]\geq\frac{\log(\frac{1}{4\delta})}{18\epsilon^{2}\,\alpha}. This holds for both Zero-Sum Games and General-Sum Games. Proof. The proof is divided into three steps. Step 1: Instance Construction To prove the result, we consider the case in which n=2 , and we have two different instances where the unknown strategy profiles (x^{0},y^{0}) and (x^{1},y^{1}) are defined as follows: \displaystyle x^{0}=\left(\tfrac{\alpha}{2},1-\tfrac{\alpha}{2}\right),~y^{0}=\left(1,0\right) \displaystyle x^{1}=\left(\tfrac{\alpha}{2}+\tfrac{\beta}{2},1-\tfrac{\alpha}{2}-\tfrac{\beta}{2}\right),~y^{1}=\left(1,0\right), where \beta\in(0,\tfrac{1}{4}) is a parameter that will be tuned later on. Since \alpha\in(0,\tfrac{1}{4}) and \beta\in(0,\tfrac{1}{4}) , x^{0} and x^{1} both belong to the simplex. Step 2: Haussdorff Distance Next, we lower bound H(\mathcal{G}_{\alpha}(x^{0},y^{0}),\mathcal{G}_{\alpha}(x^{1},y^{1})) and H(\mathcal{Z}_{\alpha}(x^{0},y^{0}),\mathcal{Z}_{\alpha}(x^{1},y^{1})) . We start from H(\mathcal{G}_{\alpha}(x^{0},y^{0}),\mathcal{G}_{\alpha}(x^{1},y^{1})) . We have that: \displaystyle H(\mathcal{G}_{\alpha}(x^{0},y^{0}),\mathcal{G}_{\alpha}(x^{1},y^{1})) \displaystyle\geq\max_{A\in\mathcal{G}_{\alpha}^{x}(x^{0},y^{0})}\min_{A^{\prime}\in\mathcal{G}_{\alpha}^{x}(x^{1},y^{1})}\|A-A^{\prime}\|_{\infty} \displaystyle\geq\min_{A^{\prime}\in\mathcal{G}_{\alpha}(x^{1},y^{1})}\max\{|1-a^{\prime}_{11}|,|1+a^{\prime}_{12}|,|1+a^{\prime}_{21}|,|1+a^{\prime}_{22}|\}, where, in the second step, we have set A=\begin{bmatrix}1&-1\\ -1&-1\end{bmatrix}\in\mathcal{G}_{\alpha}^{x}(x^{0},y^{0}) . 16 16 16 Indeed, (x^{0})^{\top}Ay^{0}=-1+\alpha , e_{1}^{\top}Ay^{0}=\tfrac{\alpha}{2} and e_{2}^{\top}Ay^{0}=-1 . Hence, (x^{0})^{\top}Ay^{0}\leq e_{i}^{\top}Ay^{0}+\alpha for all i\in\{1,2\} . Now, using the values of x^{1} and y^{1} , we are interested in solving the following problem: \displaystyle\min_{A^{\prime}\in[-1,1]^{2\times 2}}\max \displaystyle\{|1-a^{\prime}_{11}|,|1+a^{\prime}_{12}|,|1+a^{\prime}_{21}|,|1+a^{\prime}_{22}|\} \displaystyle\text{s.t.~} \displaystyle(\tfrac{\alpha}{2}+\tfrac{\beta}{2})a^{\prime}_{11}+(1-\tfrac{\alpha}{2}-\tfrac{\beta}{2})a^{\prime}_{21}\leq a^{\prime}_{11}+\alpha \displaystyle(\tfrac{\alpha}{2}+\tfrac{\beta}{2})a^{\prime}_{11}+(1-\tfrac{\alpha}{2}-\tfrac{\beta}{2})a^{\prime}_{21}\leq a^{\prime}_{21}+\alpha. Simplifying the constraints we can rewrite this optimization problem as follows: \displaystyle\min_{A^{\prime}\in[-1,1]^{2\times 2}} \displaystyle\max\,\,\{|1-a^{\prime}_{11}|,|1+a^{\prime}_{21}|\}\ (24) \displaystyle\text{s.t.~} \displaystyle a^{\prime}_{21}-a^{\prime}_{11}\leq\tfrac{2\alpha}{2-\alpha-\beta} \displaystyle a^{\prime}_{11}-a^{\prime}_{21}\leq\tfrac{2\alpha}{\alpha+\beta}. Now, we note that: \displaystyle\max\{|1-a^{\prime}_{11}|,|1+a^{\prime}_{21}|\} \displaystyle\geq\frac{1}{2}\left(|1-a^{\prime}_{11}|+|1+a^{\prime}_{21}|\right) ( \max\{a,b\}\geq\tfrac{1}{2}(a+b) ) \displaystyle\geq\frac{1}{2}|2-(a^{\prime}_{11}-a^{\prime}_{21})|. (Triangular inequality) Let \Delta=a^{\prime}_{11}-a^{\prime}_{21} and observe that \Delta\in[-2,2] . We can then lower bound the value of Problem ( 24 ) with the value of the following optimization problem: \displaystyle\min_{\Delta\in[-2,2]} \displaystyle\frac{1}{2}|2-\Delta|\ (25) \displaystyle\text{s.t.~} \displaystyle-\frac{2\alpha}{2-\alpha-\beta}\leq\Delta\leq\frac{2\alpha}{\alpha+\beta}. This can be easily solved in closed form, yielding \Delta^{\star}=2\frac{\alpha}{\alpha+\beta} . Consequently, we have obtained the following lower bound on the Hausdorff distance: H(\mathcal{G}_{\alpha}(x^{0},y^{0}),\mathcal{G}_{\alpha}(x^{1},y^{1}))\geq\frac{\beta}{\alpha+\beta} . Set \beta=\tfrac{8}{3}\epsilon\alpha . We have obtained that: 17 17 17 In this step, we make use of \epsilon<\tfrac{1}{8} . \displaystyle H(\mathcal{G}_{\alpha}(x^{0},y^{0}),\mathcal{G}_{\alpha}(x^{1},y^{1}))\geq 2\epsilon. (26) We continue by lower bounding H(\mathcal{Z}_{\alpha}(x^{0},y^{0}),\mathcal{Z}_{\alpha}(x^{1},y^{1})) . We have that: \displaystyle H(\mathcal{Z}_{\alpha}(x^{0},y^{0}),\mathcal{Z}_{\alpha}(x^{1},y^{1})) \displaystyle\geq\max_{A\in\mathcal{Z}_{\alpha}(x^{0},y^{0})}\min_{A^{\prime}\in\mathcal{Z}_{\alpha}(x^{1},y^{1})}\|A-A^{\prime}\|_{\infty} \displaystyle\geq\min_{A^{\prime}\in\mathcal{Z}_{\alpha}(x^{1},y^{1})}\max\{|1-a^{\prime}_{11}|,|1+a^{\prime}_{12}|,|1+a^{\prime}_{21}|,|1+a^{\prime}_{22}|\}, where, in the second step, we have set A=\begin{bmatrix}1&-1\\ -1&-1\end{bmatrix}\in\mathcal{Z}_{\alpha}(x^{0},y^{0}) . Indeed, we already proved above that A satisfies -1+\alpha=(x^{0})^{\top}Ay^{0}\leq e_{i}^{\top}Ay^{0}+\alpha for all i\in\{1,2\} . It is also easy to see that (x^{0})^{\top}Ae_{1}=-1+\alpha and (x^{0})^{\top}Ae_{2}=-1 for all j\in\{1,2\} . Hence, we obtained A\in\mathcal{Z}_{\alpha}(x^{0},y^{0}) . Then, one can proceed as above to obtain: 18 18 18 It is sufficient to drop all the constraints that arise from (x^{1})^{\top}A^{\prime}y^{1}\geq(x^{1})^{\top}A^{\prime}e_{j}-\alpha in the optimization problems. \displaystyle H(\mathcal{Z}_{\alpha}(x^{0},y^{0}),\mathcal{Z}_{\alpha}(x^{1},y^{1}))\geq 2\epsilon. (27) Step 3: Change of measure For any x,y\in\Delta_{n} , let \mathbb{P}_{x,y}=\prod_{t=1}^{\tau_{\delta}}p_{x}(X_{t})p_{y}(Y_{t}) , where p_{q}(\cdot) denotes the density function of q\in\Delta_{n} . Then, since Equations 26 and 27 hold, we can apply Lemma D.6 . For both GSGs and ZSGs we have \displaystyle\delta\geq\frac{1}{4}\exp\left(-\text{KL}(\mathbb{P}_{x^{0},y^{0}},\mathbb{P}_{x^{1},y^{1}})\right). We proceed by analyzing the r.h.s. of this equation. In the case we are considering we have set n=2 . Hence, x,y are Bernoulli distributions, and we obtain that: \displaystyle\text{KL}\left(\mathbb{P}_{x^{0},y^{0}},\mathbb{P}_{x^{1},y^{1}}\right) \displaystyle=\mathbb{E}_{x^{0},y^{0}}\left[\sum_{t=1}^{\tau_{\delta}}\text{KL}(p_{x^{0}}(X_{t}),p_{x^{1}}(X_{t}))\right] (Since y^{0}=y^{1} ) \displaystyle=\mathbb{E}_{x^{0},y^{0}}\left[\tau_{\delta}\right]\text{KL}(p_{x^{0}},p_{x^{1}}) (Wald’s identity) \displaystyle\leq 2\mathbb{E}_{x^{0},y^{0}}\left[\tau_{\delta}\right]\frac{\text{TV}(p_{x^{0}},p_{x^{1}})^{2}}{\alpha} (Reverse Pinsker’s Inequality) \displaystyle\leq 2\mathbb{E}_{x^{0},y^{0}}\left[\tau_{\delta}\right]\frac{(\tfrac{8}{3}\epsilon\alpha)^{2}}{\alpha} \displaystyle\leq 18\mathbb{E}_{x^{0},y^{0}}\left[\tau_{\delta}\right]{\alpha\epsilon^{2}}. Hence, we obtained that: \displaystyle\delta\geq\frac{1}{4}\exp\left(-18\mathbb{E}_{x^{0},y^{0}}\left[\tau_{\delta}\right]\alpha\epsilon^{2}\right). Rearranging the terms yields: \displaystyle\mathbb{E}_{x^{0},y^{0}}\left[\tau_{\delta}\right]\geq\frac{\log\left(\frac{1}{4\delta}\right)}{18\alpha\epsilon^{2}}. which concludes the proof. ∎ Finally, it remains to prove the last result that composes Theorem 3.3 . Theorem A.5 . Let \alpha\in(0,\tfrac{1}{2}) and \epsilon\leq\tfrac{1}{128} . Then, there exists a problem instance such that, for any (\epsilon,\delta) -correct algorithm, the following holds: \mathbb{E}[\tau_{\delta}]\geq\frac{\log(2)n}{20(128)^{2}\alpha\epsilon^{2}}. This holds for both Zero-Sum Games and General-Sum Games. Proof. The proof is split into three main steps. Step 1: Instance Construction Similar to Theorem A.3 , we construct a large set of different n -dimensional instances. We assume that n\geq 22 and that n-1\mod 16=0 . These instances are parameterized with an n-1 -dimensional vector v\in\{-1,1\}^{n-1} such that \sum_{k=1}^{n-1}v_{k}=0 and are constructed as follows. We denote by \mathcal{V} the set of vectors that satisfies these two requirements. Now, let \gamma\in(0,\alpha) ; we define (x^{v},y^{v}) as follows: \displaystyle y^{v}=(1,0,\dots 0)\text{ and }x^{v}=\left(\frac{\alpha+\gamma v_{1}}{n-1},\frac{\alpha+\gamma v_{2}}{n-1},\dots,\frac{\alpha+\gamma v_{n-1}}{n-1},1-\alpha\right). Observe that n-1\geq 16,\gamma\in(0,\alpha),\alpha\in(0,\tfrac{1}{2})~\text{and~}v\in\{-1,1\}^{n-1}\implies x^{v}\in[0,1] . Furthermore \sum_{k=1}^{n-1}v_{k}=0\implies\sum_{j=1}^{n}x^{v}_{k}=1 . Therefore, we have that x^{v}\in\Delta_{n} . In the rest of the proof, we restrict our attention to vectors belonging to a subset \bar{\mathcal{V}} of \mathcal{V} . Precisely, consider any pair v,w\in\bar{\mathcal{V}} and let \displaystyle D^{+}_{v,w}=\{k\in[n-1]:v_{k}=1\text{ and }w_{k}=-1\}\quad\quad D^{-}_{v,w}=\{k\in[n-1]:v_{k}=-1\text{ and }w_{k}=1\}, where we will drop the explicit dependence on v,w when clear from context. Then, we require that for any v,w\in\bar{\mathcal{V}} it holds \displaystyle|D^{+}_{v,w}|=|D^{-}_{v,w}|\geq\frac{n-1}{16}. (28) It is easy to see that |D^{+}_{v,w}|=|D^{-}_{v,w}| is satisfied for any pair v,w\in\mathcal{V} . The requirement that, e.g. , |D^{+}|\geq\tfrac{n-1}{16} , is instead equivalent to imposing that \sum_{k=1}^{n-1}|v_{k}-w_{k}|\geq\tfrac{n-1}{16} . Thanks to Lemma D.12 , we know that: \displaystyle\exists\bar{\mathcal{V}}\subseteq\mathcal{V}:\forall v,w\in\bar{\mathcal{V}},\quad\sum_{k=1}^{n-1}|v_{k}-w_{k}|\geq\frac{n-1}{16}\text{~and~}|\bar{\mathcal{V}}|>2^{\frac{n-1}{5}}. (29) In the following step, we will consider two generic profiles (x^{v},y^{v}) and (x^{w},y^{w}) such that v,w\in\bar{\mathcal{V}} . Step 2: Hausdorff Distance We analyze the distances H(\mathcal{G}_{\alpha}(x^{v},y^{v}),\mathcal{G}_{\alpha}(x^{w},y^{w})) and H(\mathcal{Z}_{\alpha}(x^{v},y^{v}),\mathcal{Z}_{\alpha}(x^{w},y^{w})) . In particular, we will provide lower bounds on these quantities. We start from H(\mathcal{G}_{\alpha}(x^{v},y^{v}),\mathcal{G}_{\alpha}(x^{w},y^{w})) . We have that: \displaystyle H(\mathcal{G}_{\alpha}(x^{v},y^{v}),\mathcal{G}_{\alpha}(x^{w},y^{w})) \displaystyle\geq\max_{A\in\mathcal{G}_{\alpha}^{x}(x^{v},y^{v})}\min_{A^{\prime}\in\mathcal{G}_{\alpha}^{x}(x^{w},y^{w})}\|A-A^{\prime}\|_{\infty} \displaystyle\geq\min_{A^{\prime}\in\mathcal{G}_{\alpha}^{x}(x^{w},y^{w})}\|A-A^{\prime}\|_{\infty}, where the matrix A\in\mathcal{G}^{x}_{\alpha}(x^{v},y^{v}) that we used in the second inequality is constructed as follows: A_{ij}:=\begin{cases}-1&i\in[n],j>1,\\[2.0pt] -\kappa&i\in D^{+},j=1,\\[2.0pt] 1&i\in D^{-},j=1,\\[2.0pt] 0&i\in[n-1]\setminus(D^{+}\cup D^{-}),j=1,\\ -1&i=n,j=1.\end{cases}\qquad\text{where}\qquad\kappa\coloneqq\frac{\sum_{j\in D^{-}}x^{v}_{j}}{\sum_{i\in D^{+}}x^{v}_{i}}. (30) Before continuing, we prove that A constructed as in Equation 30 satisfies A\in\mathcal{G}^{x}_{\alpha}(x^{v},y^{v}) . To this end, we first verify that A\in[-1,1]^{n\times n} . It suffices to check |\kappa|\leq 1 . With some simple manipulations, we have that: \displaystyle|\kappa|=\frac{\sum_{j\in D^{-}}x^{v}_{j}}{\sum_{i\in D^{+}}x^{v}_{i}}=\frac{\frac{|D^{-}|(\alpha-\gamma)}{n-1}}{\frac{|D^{+}|(\alpha+\gamma)}{n-1}}=\frac{\alpha-\gamma}{\alpha+\gamma}\leq 1, where the second equality is due to Equation 28 and the definition of x^{v} . Next, we verify that A satisfy the \alpha -Nash constraints. To this end, we need to verify that (x^{v})^{\top}Ay\leq-1+\alpha . We note that: \displaystyle(x^{v})^{\top}Ay \displaystyle=\sum_{i\in D^{+}}x^{v}_{i}A_{i1}+\sum_{i\in D^{-}}x_{i}^{v}A_{i1}+x_{n}A_{n1} \displaystyle=-\kappa\sum_{i\in D^{+}}x^{v}_{i}+\sum_{i\in D^{-}}x_{i}^{v}+(\alpha-1) (Def. of A and x^{v} ) \displaystyle=-1+\alpha. (Def. of \kappa ) Hence, all constraints are satisfied and A\in\mathcal{G}_{\alpha}^{x}(x^{v},y^{v}) . We can now continue by lower bounding \min_{A^{\prime}\in\mathcal{G}_{\alpha}^{x}(x^{w},y^{w})}\|A-A^{\prime}\|_{\infty} . Specifically, let us introduce the auxiliary variable t=\|A-A^{\prime}\|_{\infty} . Then, using the definition of y^{w} , we can rewrite this optimization problem as follows: \displaystyle\min_{A^{\prime}\in[-1,1]^{n\times n},t\geq 0} \displaystyle t (31) \displaystyle\text{s.t.\quad} \displaystyle|A^{\prime}_{ij}-A^{\prime}_{ij}|\leq t,~\forall i,j\in[n]^{2} \displaystyle\sum_{i\in[n]}x^{w}_{i}A^{\prime}_{i1}\leq\min_{i\in[n]}A^{\prime}_{i1}+\alpha. Consider any feasible matrix A^{\prime} . Then, it must hold that: \displaystyle A^{\prime}_{1n}+\alpha \displaystyle\geq(x^{w})^{\top}A^{\prime}y (Last constraint of Equation 31 ) \displaystyle=\sum_{i\neq n}x^{w}_{i}A^{\prime}_{i1}+(1-\alpha)A^{\prime}_{n1} (Def. of x^{w} ) \displaystyle=\sum_{i\neq n}x^{w}_{i}A_{i1}+\sum_{i\neq n}(x_{i}^{w}(A^{\prime}_{i1}-A_{i1}))+(1-\alpha)A^{\prime}_{n1} \displaystyle\geq\sum_{i\neq n}x^{w}_{i}A_{i1}-t\alpha+(1-\alpha)A^{\prime}_{n1} ( |A^{\prime}_{ij}-A_{ij}|\leq t and \sum_{i\neq n}x^{w}_{i}=\alpha ) \displaystyle=\sum_{i\neq n}(x^{w}_{i}-x^{v}_{i})A_{i1}-t\alpha+(1-\alpha)A^{\prime}_{n1} ( \sum_{i\neq n}x_{i}^{v}A_{i1}=0 ) \displaystyle=\frac{2\kappa|D^{+}|\gamma}{n-1}+\frac{2|D^{-}|\gamma}{n-1}-t\alpha+(1-\alpha)A^{\prime}_{n1} (Def. of x and A ) \displaystyle=\frac{4|D^{+}|\gamma}{n-1}\left(\frac{\alpha}{\alpha+\gamma}\right)-t\alpha+(1-\alpha)A^{\prime}_{n1} (Def. of \kappa ) \displaystyle\geq\frac{\gamma\alpha}{16(\alpha+\gamma)}-t\alpha+(1-\alpha)A^{\prime}_{n1}. ( Equation 28 ) Hence, rearranging the terms, and manipulating the equations, we obtain that any feasible A^{\prime} satisfies: \displaystyle\frac{\gamma\alpha}{16(\alpha+\gamma)} \displaystyle\leq\alpha(1+A^{\prime}_{n1})+t\alpha \displaystyle\leq 2t\alpha ( |A_{n1}-A^{\prime}_{n1}|=|1+A^{\prime}_{n1}|\leq t ) Therefore, we arrived at H(\mathcal{G}_{\alpha}(x^{v},y^{v}),\mathcal{G}_{\alpha}(x^{w},y^{w}))\geq\frac{\gamma}{32(\alpha+\gamma)} . Picking \gamma=128\alpha\epsilon , we obtained that: 19 19 19 In this step, we used that \epsilon\leq\tfrac{1}{128} . \displaystyle H(\mathcal{G}_{\alpha}(x^{v},y^{v}),\mathcal{G}_{\alpha}(x^{w},y^{w}))\geq 2\epsilon. (32) Next we analyze H\!\left(\mathcal{Z}_{\alpha}(x^{v},y^{v}),\mathcal{Z}_{\alpha}(x^{w},y^{w})\right) . We have that: \displaystyle H\!\left(\mathcal{Z}_{\alpha}(x^{v},y^{v}),\mathcal{Z}_{\alpha}(x^{w},y^{w})\right) \displaystyle\geq\max_{A\in\mathcal{Z}_{\alpha}(x^{v},y^{v})}\min_{A^{\prime}\in\mathcal{Z}_{\alpha}(x^{w},y^{w})}\|A-A^{\prime}\|_{\infty} \displaystyle\geq\min_{A^{\prime}\in\mathcal{Z}_{\alpha}(x^{w},y^{w})}\|A-A^{\prime}\|_{\infty}, where the matrix A\in\mathcal{Z}_{\alpha}(x^{v},y^{v}) is defined as in Equation 30 . We already proved above that A\in[-1,1]^{n\times n} . It remains to prove that it satisfies the \alpha -Nash constraints for zero-sum games, i.e. , that A satisfies: \displaystyle(x^{v})^{\top}Ae_{j}-\alpha\leq(x^{v})^{\top}Ay\leq e_{i}^{\top}Ay+\alpha,\quad\forall i,j\in[n]^{2}. Above, we have shown that -1+\alpha=(x^{v})^{\top}Ay\leq e_{i}^{\top}Ay+\alpha,\quad\forall i,j\in[n]^{2} . Now, it is sufficient to note that (x^{v})^{\top}Ae_{1}=(x^{v})^{\top}Ay and (x^{v})^{\top}Ae_{j}=-1 for all j>1 . Hence, A\in\mathcal{Z}_{\alpha}(x^{v},y^{v}) . Then, one can proceed as above to obtain: \displaystyle H(\mathcal{Z}_{\alpha}(x^{v},y^{v}),\mathcal{Z}_{\alpha}(x^{w},y^{w}))\geq 2\epsilon. (33) Step 3: Change of measure For any x,y\in\Delta_{n} , let \mathbb{P}_{x,y}=\prod_{t=1}^{\tau_{\delta}}p_{x}(X_{t})p_{y}(Y_{t}) , where p_{q}(\cdot) denotes the density function of q\in\Delta_{n} . Then, since Equations 33 and 33 holds, we can apply Lemma D.7 using the set of instances \{(x^{v},y^{v})\}_{v\in\bar{\mathcal{V}}} and (x^{0},y^{0})=\!((\tfrac{\alpha}{n-1},\dots\tfrac{\alpha}{n-1},1-\alpha),e_{1}\!) as base instance. Thus, both for GSGs and ZSGs, we have that, for any (\epsilon,\delta) -correct algorithm, it holds that: \displaystyle\delta\geq 1-\frac{1}{\log(|\bar{\mathcal{V}}|)}\left(\frac{1}{|\bar{\mathcal{V}}|}\sum_{v\in\bar{\mathcal{V}}}\textup{KL}(\mathbb{P}_{x^{v},y^{v}},\mathbb{P}_{x^{0},y^{0}})+\log 2\right). We proceed by analyzing the kl-divergence term in the r.h.s. of this equation. Specifically, we have that: \displaystyle\textup{KL}(\mathbb{P}_{x^{v},y^{v}},\mathbb{P}_{x^{0},y^{0}}) \displaystyle=\mathbb{E}_{(x^{v},y^{v})}\left[\sum_{t=1}^{\tau_{\delta}}\text{KL}(p_{x^{v}}(X_{t}),p_{x^{0}}(X_{t}))\right] (Since y^{v}=y^{0} ) \displaystyle=\mathbb{E}_{(x^{v},y^{v})}\left[\tau_{\delta}\right]\text{KL}(p_{x^{v}},p_{x^{0}}) (Wald’s identity) \displaystyle\leq 2(128^{2})\alpha\epsilon^{2}\mathbb{E}_{(x^{v},y^{v})}\left[\tau_{\delta}\right]. ( Lemma D.4 ) Plugging this result in the previous equation and rearranging the terms, we obtain: \displaystyle\frac{1}{|\bar{\mathcal{V}}|}\sum_{v\in\bar{\mathcal{V}}}\mathbb{E}_{(x^{v},y^{v})}\left[\tau_{\delta}\right]\geq\frac{(1-\delta)\log(|\bar{\mathcal{V}}|)+\log 2}{2(128)^{2}\alpha\epsilon^{2}}. Since \mathbb{E}_{(x^{v},y^{v})}\left[\tau_{\delta}\right]\leq\max_{w\in\bar{\mathcal{V}}}\mathbb{E}_{(x^{w},y^{w})}\left[\tau_{\delta}\right] for all v\in\bar{\mathcal{V}} , the last equation implies that there exists \bar{w}\in\bar{\mathcal{V}} such that: \displaystyle\mathbb{E}_{(x^{\bar{w}},y^{\bar{w}})}\left[\tau_{\delta}\right]\geq\frac{(1-\delta)\log(|\bar{\mathcal{V}}|)+\log 2}{2(128^{2})\alpha\epsilon^{2}} With some final algebraic steps, we can now conclude the proof: \displaystyle\mathbb{E}_{(x^{\bar{w}},y^{\bar{w}})}\left[\tau_{\delta}\right] \displaystyle\geq\frac{(1-\delta)\log(|\bar{\mathcal{V}}|)+\log 2}{2(128)^{2}\epsilon^{2}} \displaystyle\geq\frac{\log(2)((1-\delta)\frac{(n-1)}{5}+1)}{2(128)^{2}\alpha\epsilon^{2}} ( Equation 29 ) \displaystyle\geq\frac{\log(2)n}{20(128)^{2}\alpha\epsilon^{2}}, ( \delta\leq\tfrac{1}{2} and n\geq 22 ) This concludes the proof. ∎ Appendix B Proof of Theorem 4.1 This section is structured as follows: • In Section B.1 we prove the result for the inverse GSG problem ( Theorem B.4 ) • In Section B.2 , we prove the result of the inverse ZSG problem ( Theorem B.7 ) The proof of Theorem 4.1 then follows directly by combining Theorems B.4 and B.7 . B.1 Proof of Theorem B.4 ( \alpha=0 , General-Sum Games) Proof Outline First, in Lemma B.1 , we show that, for any pair of strategies (x,y) and (\hat{x},\hat{y}) such that \textup{supp}(x)=\textup{supp}(\hat{x}) and \textup{supp}(y)=\textup{supp}(\hat{y}) , then \mathcal{G}(x,y) is close to \mathcal{G}(\hat{x},\hat{y}) by construction. Specifically, for any point (A,B)\in\mathcal{G}(x,y) , there exist (\hat{A},\hat{B})\in\mathcal{G}(\hat{x},\hat{y}) such that A\approx\hat{A} and B\approx\hat{B} . Importantly the approximation errors scale linearly with \|x-\hat{x}\|_{1} and \|y-\hat{y}\|_{1} . Then, in Lemma B.2 , we show how Lemma B.1 implies that the Hausdorff distance between the two sets is directly proportional to \|x-\hat{x}\|_{1} and \|y-\hat{y}\|_{1} . In Lemma B.3 we combine this result together with probabilistic argument. In this way, we are able to provide an high probability error upper bound on H(\mathcal{G}(x,y),\mathcal{G}(\hat{x},\hat{y})) that is explicitly related to the number of data m collected by Algorithm 1 . Finally, to prove Theorem B.4 we only need to select m appropriately to guarantee that the final error of Algorithm 1 is bounded by \epsilon with high probability. We start with Lemma B.1 . Note that here, x,y,\hat{x},\hat{y} are any strategy on the simplex. Lemma B.1 (Alternative Matrix Construction; \alpha=0 and General-Sum Games) . Let \alpha=0 , x,y,\hat{x},\hat{y}\in\Delta_{n} . A\in\mathcal{G}^{x}(x,y) and B\in\mathcal{G}^{y}(x,y) and \hat{x},\hat{y}\in\Delta_{n} . Then if \textup{supp}(x)=\textup{supp}(\hat{x}) then there exists \hat{A}\in\mathcal{G}^{x}(\hat{x},\hat{y}) such that \displaystyle\|A-\hat{A}\|_{\infty}\leq 4\|y-\hat{y}\|_{1}, (34) and similarly, if \textup{supp}(y)=\textup{supp}(\hat{y}) then there exists \hat{B}\in\mathcal{G}^{y}(\hat{x},\hat{y}) such that \displaystyle\|B-\hat{B}\|_{\infty}\leq 4\|x-\hat{x}\|_{1}. (35) Furthermore, \hat{A} and \hat{B} are defined as: \hat{A}_{ij}:=\begin{cases}\dfrac{A_{ij}}{1+2\|y-\hat{y}\|_{1}},&\text{if }i\in\operatornamewithlimits{argmax}_{k\in\textup{supp}(x)}\sum_{j\in[n]}\hat{y}_{j}A_{kj},\\[12.0pt] \dfrac{A_{ij}+\Delta_{i}^{x}}{1+2\|y-\hat{y}\|_{1}},&\text{if }i\in\textup{supp}(x)\setminus\operatornamewithlimits{argmax}_{k\in\textup{supp}(x)}\sum_{j\in[n]}\hat{y}_{j}A_{kj},\\[12.0pt] \dfrac{A_{ij}+2\|y-\hat{y}\|_{1}}{1+2\|y-\hat{y}\|_{1}},&\text{if }i\notin\textup{supp}(x)\end{cases} \hat{B}_{ij}:=\begin{cases}\dfrac{B_{ij}}{1+2\|x-\hat{x}\|_{1}},&\text{if }j\in\operatornamewithlimits{argmax}_{k\in\textup{supp}(y)}\sum_{i\in[n]}\hat{x}_{i}B_{ik},\\[12.0pt] \dfrac{B_{ij}+\Delta_{i}^{y}}{1+2\|x-\hat{x}\|_{1}},&\text{if }j\in\textup{supp}(y)\setminus\operatornamewithlimits{argmax}_{k\in\textup{supp}(y)}\sum_{i\in[n]}\hat{x}_{i}B_{ik},\\[12.0pt] \dfrac{B_{ij}+2\|x-\hat{x}\|_{1}}{1+2\|x-\hat{x}\|_{1}},&\text{if }j\notin\textup{supp}(y),\end{cases} where, for all i\in\textup{supp}(x) and all j\in\textup{supp}(y) , \Delta_{i}^{x} and \Delta_{j}^{y} are defines as follows: \displaystyle\Delta_{i}^{x}=\max_{k\in\textup{supp}(x)}\sum_{j\in[n]}\hat{y}_{j}A_{kj}-\sum_{j\in[n]}\hat{y}_{j}A_{ij} \displaystyle\Delta_{j}^{y}=\max_{k\in\textup{supp}(y)}\sum_{i\in[n]}\hat{x}_{i}B_{ik}-\sum_{i\in[n]}\hat{x}_{i}B_{ij}. Proof. We first prove Equation 34 by construction. For brevity, let S_{x}:=\textup{supp}(x)\subseteq[n] and define the set of maximizers of \sum_{j\in[n]}\hat{y}_{j}A_{ij} over the different rows of the support of x as S^{\star}_{x} , namely S^{\star}_{x}\coloneqq\operatornamewithlimits{argmax}_{k\in S_{x}}\sum_{j\in[n]}\hat{y}_{j}A_{kj} . Note that, since A_{ij}\in[-1,1] and \hat{y}\in\Delta_{n} , we have that \Delta_{i}^{x}\in[0,2] . Furthermore, for all i\in S_{x} \displaystyle\Delta_{i}^{x} \displaystyle=\max_{k\in S_{x}}\sum_{j\in[n]}\hat{y}_{j}A_{kj}-\sum_{j\in[n]}\hat{y}_{j}A_{ij} \displaystyle=\sum_{j\in[n]}\hat{y}_{j}(A_{kj}-A_{ij}) (For any k\in S^{\star}_{x} ) \displaystyle=\sum_{j\in[n]}y_{j}(A_{kj}-A_{ij})+\sum_{j\in[n]}(\hat{y}_{j}-y_{j})(A_{kj}-A_{ij}) \displaystyle=\sum_{j\in[n]}(\hat{y}_{j}-y_{j})(A_{kj}-A_{ij}) ( Lemma D.8 and i,k\in S_{x} ) \displaystyle\leq 2\|y-\hat{y}\|_{1} ( -1\leq A\leq 1 ) \displaystyle\coloneqq\Delta, where in the last step we have introduced \Delta\coloneqq 2\|y-\hat{y}\|_{1} . Now, we are ready to define a matrix \hat{A} that we will use to prove Equation 34 . Specifically, \hat{A} is defined as follows: \hat{A}_{ij}:=\begin{cases}\dfrac{A_{ij}}{1+\Delta},&\text{if }i\in S^{\star}_{x},\\ \dfrac{A_{ij}+\Delta_{i}^{x}}{1+\Delta},&\text{if }i\in S_{x}\setminus S^{\star}_{x},\\ \dfrac{A_{ij}+\Delta}{1+\Delta},&\text{if }i\notin S_{x}.\end{cases} First of all, note that since A\in[-1,1]^{n\times n} and \Delta_{i}^{x}\leq\Delta , we have that \hat{A}\in[-1,1]^{n\times n} . At this point, we continue by showing that \hat{A}\in\mathcal{G}^{x}(\hat{x},\hat{y}) . To this end, since \alpha=0 and \textup{supp}(x)=\textup{supp}(\hat{x})=S_{x} , due to Lemma D.8 we only need to show that \displaystyle e_{i}^{\top}\hat{A}\hat{y} \displaystyle=e_{j}^{\top}\hat{A}\hat{y}\quad\forall\,i,j\in S_{x}, (36a) \displaystyle e_{i}^{\top}\hat{A}\hat{y} \displaystyle\leq e_{j}^{\top}\hat{A}\hat{y}\quad\forall\,i\in S_{x},\ j\notin S_{x}. (36b) Condition ( 36a ) To prove that Condition ( 36a ) holds, we first show that for any i_{1},i_{2}\in S^{*}_{x} , we have e_{i_{1}}^{\top}\hat{A}\hat{y}=e_{i_{2}}^{\top}\hat{A}\hat{y} . Specifically, let i_{1},i_{2}\in S^{\star}_{x} . Then, \displaystyle e_{i_{1}}^{\top}\hat{A}\hat{y} \displaystyle=\frac{1}{1+\Delta}\sum_{j\in[n]}A_{i_{1}j}\hat{y}_{j} \displaystyle=\frac{1}{1+\Delta}\sum_{j\in[n]}A_{i_{2}j}\hat{y}_{j} ( S^{\star}_{x}=\operatornamewithlimits{argmax}_{i\in S_{x}}\sum_{j\in[n]}\hat{y}_{j}A_{ij} and i_{1},i_{2}\in S^{\star}_{x} ) \displaystyle=e_{i_{2}}^{\top}\hat{A}\hat{y}. To conclude the proof of Condition ( 36a ), we need to consider i_{1}\in S^{\star}_{x} , and i_{2}\in S_{x}\setminus S^{\star}_{x} and prove that e_{i_{1}}^{\top}\hat{A}\hat{y}=e_{i_{2}}^{\top}\hat{A}\hat{y} . Using the definition of \hat{A} , we have that: \displaystyle e_{i_{1}}^{\top}\hat{A}\hat{y}=e_{i_{2}}^{\top}\hat{A}\hat{y}\iff\sum_{j\in[n]}\hat{y}_{j}A_{i_{1}j}=\sum_{j\in[n]}\hat{y}_{j}A_{i_{2}j}+\Delta_{i_{2}}^{x}. However, by definition of \Delta_{i_{2}}^{x} , we have that, \displaystyle\Delta_{i_{2}}^{x}=\max_{k\in S}\sum_{j\in[n]}\hat{y}_{j}A_{kj}-\sum_{k\in[n]}\hat{y}_{j}A_{i_{2}k}=\sum_{j\in[n]}\hat{y}_{j}A_{i_{1}j}-\sum_{k\in[n]}\hat{y}_{j}A_{i_{2}k}, hence, \sum_{j\in[n]}\hat{y}_{j}A_{i_{1}j}=\sum_{j\in[n]}\hat{y}_{j}A_{i_{2}j}+\Delta_{i_{2}} holds, and e_{i_{1}}^{\top}\hat{A}\hat{y}=e_{i_{2}}^{\top}\hat{A}\hat{y} holds as well. Finally, we note that the above argument also covers the case where i_{1},i_{2}\in S_{x}\setminus S_{x}^{\star} . Indeed, for any i\in S_{x}\setminus S_{x}^{\star} , we have e_{i}^{\top}\hat{A}\hat{y}=e_{i^{\star}}^{\top}\hat{A}\hat{y} for any i^{\star}\in S_{x}^{\star} . Therefore, for any i_{1},i_{2}\in S_{x}\setminus S_{x}^{\star} , e_{i_{1}}^{\top}\hat{A}\hat{y}=e_{i^{\star}}^{\top}\hat{A}\hat{y}=e_{i_{2}}^{\top}\hat{A}\hat{y}, which shows that Condition ( 36a ) holds for all pairs i_{1},i_{2}\in S_{x} . Condition ( 36b ). To prove that Condition ( 36b ) holds, since we already proven Condition ( 36a ), it is sufficient to show that, for i_{1}\in S^{\star}_{x} and i_{2}\notin S_{x} , we have that e_{i_{1}}^{\top}\hat{A}\hat{y}\leq e_{i_{2}}^{\top}\hat{A}\hat{y} . Consider the following inequalities: \displaystyle e_{i_{1}}^{\top}\hat{A}\hat{y} \displaystyle=\frac{1}{1+\Delta}\left(\sum_{j\in[n]}\hat{y}_{j}A_{i_{1}j}\right) \displaystyle=\frac{1}{1+\Delta}\left(\sum_{j\in[n]}y_{j}A_{i_{1}j}+\sum_{j\in[n]}(\hat{y}_{j}-y_{j})A_{i_{1}j}\right) \displaystyle\leq\frac{1}{1+\Delta}\left(\sum_{j\in[n]}y_{j}A_{i_{2}j}+\sum_{j\in[n]}(\hat{y}_{j}-y_{j})A_{i_{1}j}\right) (Due to A\in\mathcal{G}^{x}(x,y) and Lemma D.8 ) \displaystyle=\frac{1}{1+\Delta}\left(\sum_{j\in[n]}\hat{y}_{j}A_{i_{2}j}+\sum_{j\in[n]}(\hat{y}_{j}-y_{j})(A_{i_{1}j}-A_{i_{2}j})\right) \displaystyle\leq\frac{1}{1+\Delta}\left(\sum_{j\in[n]}\hat{y}_{j}A_{i_{2}j}+2\|y-\hat{y}\|_{1})\right) \displaystyle=e_{i_{2}}^{\top}\hat{A}\hat{y}. Hence, we proved that \hat{A}\in\mathcal{G}^{x}(\hat{x},\hat{y}) . Finally, to conclude the proof of Equation 34 , it remains to bound \|A-\hat{A}\|_{\infty} . Fix any pair of i,j\in[n] . Then, if i\in S^{\star}_{x} , we have that: |A_{ij}-\hat{A}_{ij}|=\left|A_{ij}-\frac{A_{ij}}{1+\Delta}\right|=|A_{ij}|\,\frac{\Delta}{1+\Delta}\leq\frac{\Delta}{1+\Delta}\leq 2\Delta. If, instead, i\in S_{x}\setminus S^{\star}_{x} : |A_{ij}-\hat{A}_{ij}|=\left|A_{ij}-\frac{A_{ij}+\Delta_{i}^{x}}{1+\Delta}\right|=\frac{|\,\Delta A_{ij}-\Delta_{i}^{x}\,|}{1+\Delta}\leq\frac{|A_{ij}|\Delta+\Delta_{i}^{x}}{1+\Delta}\leq\frac{2\Delta}{1+\Delta}\leq 2\Delta, Finally, if i\notin S_{x} , we have that: |A_{ij}-\hat{A}_{ij}|=\left|A_{ij}-\frac{A_{ij}+\Delta}{1+\Delta}\right|=\frac{\Delta|1-A_{ij}|}{1+\Delta}\leq\frac{2\Delta}{1+\Delta}\leq 2\Delta. Hence, \|A-\hat{A}\|_{\infty}\leq 2\Delta , thus concluding the proof of Equation 34 . We continue by proving Equation 35 . In particular, the proof of Equation 35 follows from arguments that are symmetrical to the ones that we presented above. More precisely, consider B\in\mathcal{G}^{y}(x,y) . Let S_{y}\coloneqq\textup{supp}(y) and for all j\in[n] and define: \Delta_{j}^{y}=\max_{k\in S_{y}}\sum_{i\in[n]}\hat{x}_{i}B_{ik}-\sum_{i\in[n]}\hat{x}_{i}B_{ij}. Furthermore, let S^{\star}_{y}=\operatornamewithlimits{argmax}_{j\in[n]}\sum_{i\in[n]}\hat{x}_{i}B_{ij} . Then, we define \hat{B} as follows: \hat{B}_{ij}:=\begin{cases}\dfrac{B_{ij}}{1+\Delta},&\text{if }j\in S^{\star}_{y},\\ \dfrac{B_{ij}+\Delta_{i}^{x}}{1+\Delta},&\text{if }j\in S_{y}\setminus S^{\star}_{y},\\ \dfrac{B_{ij}+\Delta}{1+\Delta},&\text{if }j\notin S_{y}.\end{cases} where \Delta=2\|x-\hat{x}\|_{1} . The proof of the results than follows from arguments that are analogous to the ones that we presented for Equation 34 . ∎ We now leverage Lemma B.1 to provide an upper bound on the Hausdorfff distance. Lemma B.2 (Matrix Construction \to Hausdorfff Distance) . Let \alpha=0 , x,y,\hat{x},\hat{y}\in\Delta_{n} . Suppose that \textup{supp}(x)=\textup{supp}(\hat{x}) and \textup{supp}(y)=\textup{supp}(\hat{y}) . Then, it holds that: \displaystyle H(\mathcal{G}(x,y),\mathcal{G}(\hat{x},\hat{y}))\leq 4(\|x-\hat{x}\|_{1}+\|y-\hat{y}\|_{1}). Proof. The proof is a direct application of Lemma B.1 . Precisely: \displaystyle H(\mathcal{G}(x,y),\mathcal{G}(\hat{x},\hat{y})) \displaystyle=\max\Bigg\{\max_{(A,B)\in\mathcal{G}(x,y)}\min_{(\hat{A},\hat{B})\in\mathcal{G}(\hat{x},\hat{y})}\max\{\|A-\hat{A}\|_{\infty},\|B-\hat{B}\|_{\infty}, \displaystyle\hskip 56.9055pt\max_{(\hat{A},\hat{B})\in\mathcal{G}(\hat{x},\hat{y})}\min_{(A,B)\in\mathcal{G}(x,y)}\max\{\|A-\hat{A}\|_{\infty},\|B-\hat{B}\|_{\infty}\Bigg\} \displaystyle\leq 4\max\left\{\|x-\hat{x}\|_{1},\|y-\hat{y}\|_{1}\right\} ( Lemma B.1 ) \displaystyle\leq 4(\|x-\hat{x}\|_{1}+\|y-\hat{y}\|_{1}). which concludes the proof. Here, we simply remark that, in order to apply Lemma B.1 in the first inequality, it is important to recall that \mathcal{G}(x,y)=\mathcal{G}^{x}(x,y)\times\mathcal{G}^{y}(x,y) . ∎ At this point, we can combine Lemma B.2 with probabilistic arguments to obtain a high probability error bound on the Hausdorff distance that is directly related to the number of samples observed by our algorithm. Lemma B.3 (High-Probability Hausdorff Bound) . Let \alpha=0 and \hat{x},\hat{y}\in\Delta_{n} be the maximum likelihood estimators of x,y after m samples. Suppose that m satisfies: \displaystyle m\geq\frac{\log\left(\frac{4n}{\delta}\right)}{\log\left(\frac{1}{1-\pi_{\min}}\right)}, (37) then, with probability at least 1-\delta , it holds that: \displaystyle H(\mathcal{G}(x,y),\mathcal{G}(\hat{x},\hat{y})\leq 8\sqrt{\frac{2\log\left(\frac{4}{\delta}\right)+2n\log(6m)}{m}}. Proof. We first define the following good event \mathcal{E} and shows that it holds with probability at least 1-\delta . We define \mathcal{E}=\mathcal{E}_{1}\cap\mathcal{E}_{2} , where \displaystyle\mathcal{E}_{1}=\left\{\|x-\hat{x}\|_{1}\leq\sqrt{\frac{2\log\left(\frac{4}{\delta}\right)+2n\log(6m)}{m}}\right\}\cap\left\{\|y-\hat{y}\|_{1}\leq\sqrt{\frac{2\log\left(\frac{4}{\delta}\right)+2n\log(6m)}{m}}\right\} \displaystyle\mathcal{E}_{2}=\{\textup{supp}(x)=\textup{supp}(\hat{x})\}\cap\{\textup{supp}(y)=\textup{supp}(\hat{y})\}. Then, we have that \mathbb{P}(\mathcal{E})=1-\mathbb{P}(\mathcal{E}^{\complement})\geq 1-(\mathbb{P}(\mathcal{E}_{1}^{\complement})+\mathbb{P}(\mathcal{E}^{\complement}_{2})) . Hence, we simply upper bound \mathbb{P}(\mathcal{E}_{1}^{\complement}) and \mathbb{P}(\mathcal{E}^{\complement}_{2}) . \displaystyle\mathbb{P}(\mathcal{E}_{1}^{\complement}) \displaystyle\leq\mathbb{P}\left(\|x-\hat{x}\|_{1}>\sqrt{\frac{2\log\left(\frac{4}{\delta}\right)+2n\log(6m)}{m}}\right)+\mathbb{P}\left(\|y-\hat{y}\|_{1}>\sqrt{\frac{2\log\left(\frac{4}{\delta}\right)+2n\log(6m)}{m}}\right) \displaystyle\leq\frac{\delta}{2}. ( Lemma D.3 ) Furthermore, \displaystyle\mathbb{P}(\mathcal{E}_{2}^{\complement}) \displaystyle\leq\mathbb{P}(\textup{supp}(x)\neq\textup{supp}(\hat{x}))+\mathbb{P}(\textup{supp}(y)\neq\textup{supp}(\hat{y})) \displaystyle\leq\frac{\delta}{2}. ( Equation 37 and Lemma D.1 ) Thus, we obtained that \mathbb{P}(\mathcal{E})\geq 1-\delta . Therefore, due to the definition of \mathcal{E} and by using Lemma B.2 , we have that, with probability at least 1-\delta : \displaystyle H(\mathcal{G}(x,y),\mathcal{G}(\hat{x},\hat{y})) \displaystyle\leq 4(\|x-\hat{x}\|_{1}+\|y-\hat{y}\|_{1}) \displaystyle\leq 8\sqrt{\frac{2\log\left(\frac{4}{\delta}\right)+2n\log(6m)}{m}}, which concludes the proof. ∎ We are now ready to show that Algorithm 1 is an (\epsilon,\delta) -correct method for learning \mathcal{G}(x,y) with minimax optimal sample complexity. Theorem B.4 . Consider \alpha=0 and let m\in\widetilde{\mathcal{O}}\left(\frac{\log\left(\frac{1}{\delta}\right)}{\log(1/(1-\pi_{\min}))}+\frac{n+\log\left(\frac{1}{\delta}\right)}{\epsilon^{2}}\right). Then Algorithm 1 is (\epsilon,\delta) -correct for General-Sum Games and its sample complexity \tau_{\delta} is given by m . Proof. First, we give a precise expression of the number of samples m needed by Algorithm 1 . \displaystyle m \displaystyle=\max\left\{\frac{\log\left(\frac{4n}{\delta}\right)}{\log\left(\frac{1}{1-\pi_{\min}}\right)},2\left(2+\frac{4\log(4/\delta)}{(\epsilon/\sqrt{128})^{2}}+\frac{4n}{(\epsilon/\sqrt{128})^{2}}\log\left(\frac{12n}{(\epsilon/\sqrt{128})^{2}}\right)\right)\right\} (38) \displaystyle\in\widetilde{\mathcal{O}}\left(\frac{\log\left(\frac{1}{\delta}\right)}{\log\left(\frac{1}{1-\pi_{\min}}\right)}+\frac{\log\left(\frac{1}{\delta}\right)+n}{\epsilon^{2}}\right). (39) Now, since m\geq\frac{\log\left(\frac{4n}{\delta}\right)}{\log\left(\frac{1}{1-\pi_{\min}}\right)} , by Lemma B.3 , we have that, with probability at least 1-\delta : \displaystyle H(\mathcal{G}(x,y),\mathcal{G}(\hat{x},\hat{y}) \displaystyle\leq 8\sqrt{\frac{2\log\left(\frac{4}{\delta}\right)+2n\log(6m)}{m}} Thus, we need to show that, for m chosen as in Equation 38 , 8\sqrt{\frac{2\log\left(\frac{4}{\delta}\right)+2n\log(6m)}{m}}\leq\epsilon . That holds if and only if \displaystyle\frac{\log\left(\frac{4}{\delta}\right)+n\log(6m)}{m}\leq\left(\frac{\epsilon}{\sqrt{128}}\right)^{2}. This, however, is granted by the definition of m . To this end, it is sufficient to apply Lemma D.9 with c_{1}=4,c_{2}=6,K=(\epsilon/\sqrt{128}) . Hence, after m samples, Algorithm 1 is (\epsilon,\delta) -correct for \alpha=0 and General-Sum Games. ∎ B.2 Proof of Theorem B.7 ( \alpha=0 , Zero-Sum Games) Proof outline The proof of Theorem B.7 is similar in spirit to the one that we presented for Theorem B.4 . There are, however, a couple of important differences that complicate the analysis. Importantly, these differences arise from the additional constraints that are present in the definition of \mathcal{Z}(x,y) , which require a single matrix to verify constraints both for the x and the y players. Consider, indeed, any pair of strategies (x,y) and (\hat{x},\hat{y}) such that \textup{supp}(x)=\textup{supp}(\hat{x}) and \textup{supp}(y)=\textup{supp}(\hat{y}) . Then, for any A\in\mathcal{Z}(x,y) , the construction of \hat{A} that we provided in Lemma B.1 for general-sum games fails to satisfy the constraints of \mathcal{Z}(\hat{x},\hat{y}) . To this end, consider the following simple numerical example. Let: \displaystyle A=\begin{pmatrix}1&-1\\ -1&1\end{pmatrix}\quad x=y=(0.5,0.5),\quad\hat{x}=(0.6,0.4),\hat{y}=(0.4,0.6) In this case, Lemma B.1 yields: \displaystyle\hat{A}=\begin{pmatrix}1&-0.42857143\\ -0.71428571&0.71428571\end{pmatrix}. \displaystyle\hat{A}\approx\begin{pmatrix}1&-0.43\\ -0.71&0.71\end{pmatrix}. Since \hat{A}\notin\mathcal{Z}(\hat{x},\hat{y}) , we cannot rely on the previous argument for this more complicated case. More generally, we found particularly challenging building analytically a matrix \hat{A} that takes into account variations both in x and y strategy profiles. To this end, however, we developed a trick to take into account the single variations of the x and the y vector. Specifically, we start our analysis with Corollary D.11 which states that \displaystyle H(\mathcal{Z}(x,y),\mathcal{Z}(\hat{x},\hat{y}))\leq H(\mathcal{Z}(x,y),\mathcal{Z}(\hat{x},y))+H(\mathcal{Z}(\hat{x},y),\mathcal{Z}(\hat{x},\hat{y})). This result allows us to construct matrices to upper bound the Hausdorff distance again by construction. Specifically, we can fix two matrices A_{1}\in\mathcal{Z}(x,y) and A_{2}\in\mathcal{Z}(\hat{x},y) and find two matrices A_{3}\in\mathcal{Z}(\hat{x},y) and A_{4}\in\mathcal{Z}(\hat{x},\hat{y}) such that A_{1}\approx A_{3} and A_{2}\approx A_{4} ( Lemma B.5 and Lemma B.6 ). Importantly, note that A_{1} and A_{3} belong to sets that “vary only across the x player’s strategy” ( i.e. , y is fixed), while A_{2} and A_{4} belong to sets that “vary only across the y player’s strategy” ( i.e. , \hat{x} is fixed). Importantly the approximation errors of both matrices scale linearly with \|x-\hat{x}\|_{1} and \|y-\hat{y}\|_{1} . Then, once this is done, we proceed identically to Theorem B.4 . We are now ready to start the proof of Theorem B.7 . As anticipated, given Corollary D.11 , we start by fixing the x -vector and, for any matrix A\in\mathcal{Z}(x,y) we build an alternative matrix \hat{A}\in\mathcal{Z}(x,\hat{y}) . A careful reader might note that the matrix constructed in the following lemma is similar to the one presented in Lemma B.1 for general-sum games. However, here both the statement and the proofs are different. Indeed, (i) to construct \hat{A} we require that the support of y and \hat{y} coincide and (ii) we need to ensure that our construction satisfies a larger number of constraints. We remark that in the following lemma, x,y,\hat{y} are generic strategies on the simplex. Lemma B.5 (Alternative Matrix Construction (fix x); \alpha=0 ; Zero-Sum Games) . Let \alpha=0 , and x,y,\hat{y}\in\Delta_{n} . Let A\in\mathcal{Z}(x,y) . It holds that: \displaystyle\textup{supp}(y)=\textup{supp}(\hat{y})\implies\exists\hat{A}\in\mathcal{Z}(x,\hat{y}):\|A-\hat{A}\|_{\infty}\leq 4\|y-\hat{y}\|_{1} Furthermore, \hat{A} is defined as follows: \hat{A}_{ij}:=\begin{cases}\dfrac{A_{ij}}{1+2\|y-\hat{y}\|_{1}},&\text{if }i\in\operatornamewithlimits{argmax}_{k\in\textup{supp}(x)}\sum_{j\in[n]}\hat{y}_{j}A_{kj},\\[12.0pt] \dfrac{A_{ij}+\Delta_{i}}{1+2\|y-\hat{y}\|_{1}},&\text{if }i\in\textup{supp}(x)\setminus\operatornamewithlimits{argmax}_{k\in\textup{supp}(x)}\sum_{j\in[n]}\hat{y}_{j}A_{kj},\\[12.0pt] \dfrac{A_{ij}+2\|y-\hat{y}\|_{1}}{1+2\|y-\hat{y}\|_{1}},&\text{if }i\notin\textup{supp}(x),\end{cases} where, for all i\in\textup{supp}(x) , \Delta_{i} is given by \displaystyle\Delta_{i}=\max_{k\in\textup{supp}(x)}\sum_{j\in[n]}\hat{y}_{j}A_{kj}-\sum_{j\in[n]}\hat{y}_{j}A_{ij} Proof. Given the definition of \hat{A} , we already know from Lemma B.1 that all the following statements are true: \displaystyle\text{(i)}~\|A-\hat{A}\|_{\infty}\leq 4\|y-\hat{y}\|_{1} \displaystyle\text{(ii)}~e_{i}^{\top}\hat{A}\hat{y}=e_{j}^{\top}\hat{A}\hat{y}\quad\quad\quad\quad~\forall i,j\in\textup{supp}(x) \displaystyle\text{(iii)}~e_{i}^{\top}\hat{A}\hat{y}\leq e_{j}^{\top}\hat{A}\hat{y}\quad\quad\quad\quad\forall i\in\textup{supp}(x),\forall j\notin\textup{supp}(x). Hence, from Lemma D.8 it only remains to verify that \hat{A} satisfies: \displaystyle x^{\top}\hat{A}e_{j}=x^{\top}\hat{A}\hat{y}~\quad\forall j\in\textup{supp}(\hat{y}) (40a) \displaystyle x^{\top}\hat{A}e_{j}\leq x^{\top}\hat{A}\hat{y}~\quad\forall j\notin\textup{supp}(\hat{y}). (40b) Before proving Equations 40a and 40b we make some preliminary considerations. First, we recall from Lemma D.8 that, since A\in\mathcal{Z}(x,y) , it holds that: \displaystyle x^{\top}Ay=x^{\top}Ae_{j}=e_{i}^{T}Ay,\quad\forall\,i\in\textup{supp}(x),j\in\textup{supp}(y), (41) \displaystyle x^{\top}Ae_{j}\leq x^{\top}Ay\leq e_{i}^{\top}Ay,\quad\forall\,i\notin\textup{supp}(x),\ \forall\,j\notin\textup{supp}(y). (42) Now, let \Delta=2\|y-\hat{y}\|_{1} and let j\in[n] . Then, we have that: \displaystyle x^{\top}\hat{A}e_{j} \displaystyle=\sum_{i\in[n]}x_{i}\hat{A}_{ij} \displaystyle=\frac{1}{1+\Delta}\left(x^{\top}Ae_{j}+\sum_{i:x_{i}>0}x_{i}\Delta_{i}\right). (Definition of \hat{A} ) Now, let us focus in detail on the term \sum_{i:x_{i}>0}x_{i}\Delta_{i} . We have that: \displaystyle\sum_{i:x_{i}>0}x_{i}\Delta_{i} \displaystyle=\sum_{i:x_{i}>0}x_{i}\sum_{j\in[n]}\hat{y}_{j}(A_{kj}-A_{ij}) (Definition of \Delta_{i} and k\in\operatornamewithlimits{argmax}_{\star\in\textup{supp}(x)}\sum_{j\in[n]}\hat{y}_{j}A_{\star,j} ) \displaystyle=\sum_{j\in[n]}\hat{y}_{j}\left(A_{kj}-\sum_{i:x_{i}>0}x_{i}A_{ij}\right) \displaystyle=\sum_{j\in[n]}\hat{y}_{j}\left(A_{kj}-x^{\top}Ae_{j}\right) \displaystyle=\sum_{j\in[n]}\hat{y}_{j}A_{kj}-\sum_{j:y_{j}>0}\hat{y}_{j}(x^{\top}Ae_{j}) ( \textup{supp}(y)=\textup{supp}(\hat{y}) ) \displaystyle=\sum_{j\in[n]}\hat{y}_{j}A_{kj}-x^{\top}Ay ( Equation 41 ) Hence, we obtained that, for all j\in[n] : \displaystyle x^{\top}\hat{A}e_{j}=\frac{1}{1+\Delta}\left(x^{\top}Ae_{j}-x^{\top}Ay+\max_{k\in\textup{supp}(x)}e_{k}^{\top}A\hat{y}\right) (43) We are now ready to conclude the proof. Consider j_{1},j_{2}\in[n] such that y_{j_{1}}>0 and y_{j_{2}}=0 . Then, combining Equations 41 and 43 , we have that: \displaystyle x^{\top}\hat{A}e_{j_{1}}=\frac{\max_{k\in\textup{supp}(x)}e_{k}^{\top}A\hat{y}}{1+\Delta} \displaystyle x^{\top}\hat{A}e_{j_{2}}\leq\frac{\max_{k\in\textup{supp}(x)}e_{k}^{\top}A\hat{y}}{1+\Delta}, thus proving Conditions ( 40a ) and ( 40b ). Hence, \hat{A}\in\mathcal{Z}(x,\hat{y}) . ∎ We now fix (x,y) and for A\in\mathcal{Z}(x,y) , we build \hat{A}\in\mathcal{Z}(\hat{x},y) . The proof of the following lemma is similar to that of Lemma B.5 , and the proof is reported mainly for the sake of completeness. Here, x,\hat{x},y are again generic strategies on the simplex. Lemma B.6 (Alternative Matrix Construction (fix y); \alpha=0 ; Zero-Sum Games) . Let \alpha=0 , A\in\mathcal{Z}(x,y) . It holds that: \displaystyle\textup{supp}(x)=\textup{supp}(\hat{x})\implies\exists\hat{A}\in\mathcal{Z}(\hat{x},y):\|A-\hat{A}\|_{\infty}\leq 4\|x-\hat{x}\|_{1} Furthermore, \hat{A} is defined as follows: \hat{A}_{ij}:=\begin{cases}\dfrac{A_{ij}}{1+2\|x-\hat{x}\|_{1}},&\text{if }j\in\operatornamewithlimits{argmax}_{k\in\textup{supp}(y)}\sum_{i\in[n]}\hat{x}_{i}A_{ik},\\[12.0pt] \dfrac{A_{ij}+\Delta_{j}}{1+2\|x-\hat{x}\|_{1}},&\text{if }j\in\textup{supp}(y)\setminus\operatornamewithlimits{argmax}_{k\in\textup{supp}(y)}\sum_{i\in[n]}\hat{x}_{i}A_{ik},\\[12.0pt] \dfrac{A_{ij}-2\|x-\hat{x}\|_{1}}{1+2\|x-\hat{x}\|_{1}},&\text{if }j\notin\textup{supp}(y),\end{cases} where, for all j\in\textup{supp}(x) , \Delta_{j} is defined as \displaystyle\Delta_{j}=\max_{k\in\textup{supp}(y)}\sum_{i\in[n]}\hat{x}_{i}A_{ik}-\sum_{i\in[n]}\hat{x}_{i}A_{ij}. Proof. First, as in Lemma B.1 , one can trivially verify that, since A\in[-1,1]^{n\times n} , \hat{A}\in[-1,1]^{n\times n} as well. Furthermore, by following analogous arguments, it is also easy to see that \|A-\hat{A}\|_{\infty}\leq 4\|x-\hat{x}\|_{1} By applying Lemma D.8 it thus remains to verify that: \displaystyle\hat{x}^{\top}\hat{A}e_{i}=\hat{x}^{\top}\hat{A}e_{j},\quad\forall i,j\in\textup{supp}(y) (44a) \displaystyle\hat{x}^{\top}\hat{A}e_{i}\geq\hat{x}^{\top}\hat{A}e_{j},\quad\forall i\in\textup{supp}(y),j\notin\textup{supp}(y) (44b) \displaystyle e_{i}^{\top}\hat{A}y=e_{i}^{\top}\hat{A}e_{j},\quad\forall i,j\in\textup{supp}(x) (44c) \displaystyle e_{i}^{\top}\hat{A}y\leq e_{j}^{\top}\hat{A}y,\quad\forall i\in\textup{supp}(x),j\notin\textup{supp}(x). (44d) Before continuing, we introduce some additional notation for the sake of brevity. Let \Delta=2\|x-\hat{x}\|_{1} and define S=\textup{supp}(y) and S^{\star}_{y}=\operatornamewithlimits{argmax}_{k\in\textup{supp}(y)}\sum_{i\in[n]}\hat{x}_{i}A_{ik} . Conditions ( 44a ) and ( 44b ) Given the expression of \hat{A} , Equation 44a is a direct consequence of Lemma B.1 . We now prove Equation 44b . Since Equation 44a holds, we only need to consider j_{1}\in\textup{supp}(y) and j_{2}\notin\textup{supp}(y) and show that \hat{x}^{\top}\hat{A}e_{j_{1}}\geq\hat{x}^{\top}\hat{A}e_{j_{2}} . Specifically, we consider j_{1}\in S^{\star}_{y} . Then, it holds that: \displaystyle\hat{x}^{\top}\hat{A}e_{j_{1}} \displaystyle=\frac{1}{1+\Delta}\sum_{i\in[n]}\hat{x}_{i}A_{ij_{1}} \displaystyle=\frac{1}{1+\Delta}\left(x^{\top}Ae_{j_{1}}+\sum_{i\in[n]}(\hat{x}_{i}-x_{i})A_{ij_{1}}\right) \displaystyle\geq\frac{1}{1+\Delta}\left(x^{\top}Ae_{j_{2}}+\sum_{i\in[n]}(\hat{x}_{i}-x_{i})A_{ij_{1}}\right) ( A\in\mathcal{Z}(x,y) , Lemma D.8 and j_{1}\in\textup{supp}(y) ) \displaystyle=\frac{1}{1+\Delta}\left(\sum_{i\in[n]}\hat{x}_{i}A_{ij_{2}}+\sum_{i\in[n]}(\hat{x}_{i}-x_{i})(A_{ij_{1}}-A_{ij_{2}})\right) \displaystyle\geq\frac{1}{1+\Delta}\left(\sum_{i\in[n]}\hat{x}_{i}A_{ij_{2}}-2\|x-\hat{x}\|_{1}\right) \displaystyle=\hat{x}^{\top}\hat{A}e_{j_{2}}, which concludes the proof. Conditions ( 44c ) and ( 44d ) Here, we proceed in a way that is analogous to Lemma B.5 . Specifically, consider any i\in[n] . Then, it holds that: \displaystyle e_{i}^{\top}\hat{A}y \displaystyle=\sum_{j\in[n]}y_{j}\hat{A}_{ij} \displaystyle=\frac{1}{1+\Delta}\left(e_{i}^{\top}Ay+\sum_{j:y_{j}>0}y_{j}\Delta_{j}\right). (Definition of \hat{A} ) Let us focus on \sum_{j:y_{j}>0}y_{j}\Delta_{j} . We have that: \displaystyle\sum_{j:y_{j}>0}y_{j}\Delta_{j} \displaystyle=\sum_{j:y_{j}>0}y_{j}\sum_{i\in[n]}\hat{x}_{i}(A_{ik}-A_{ij}) (Definition of \Delta_{j} and k\in\operatornamewithlimits{argmax}_{\star\in\textup{supp}(y)}\sum_{i\in[n]}\hat{x}_{i}A_{i\star} ) \displaystyle=\sum_{i\in[n]}\hat{x}_{i}\left(A_{ik}-\sum_{j:y_{j}>0}y_{j}A_{ij}\right) \displaystyle=\sum_{i\in[n]}\hat{x}_{i}(A_{ik}-e_{i}^{\top}Ay) \displaystyle=\sum_{i\in[n]}\hat{x}_{i}A_{ik}-\sum_{i:x_{i}>0}\hat{x}_{i}(e_{i}^{\top}Ay)) ( \textup{supp}(x)=\textup{supp}(\hat{x}) ) \displaystyle=\sum_{i\in[n]}\hat{x}_{i}A_{ik}-x^{\top}Ay ( A\in\mathcal{Z}(x,y) ) Therefore, we obtained that, for all i\in[n] : \displaystyle e_{i}^{\top}\hat{A}y=\frac{1}{1+\Delta}\left(e_{i}^{\top}Ay-x^{\top}Ay+\max_{k\in\textup{supp}(y)}\hat{x}^{\top}Ae_{k}\right). Now, let i_{1}\in\textup{supp}(\hat{x}) and i_{2}\notin\textup{supp}(\hat{x}) . We have that: \displaystyle e_{i_{1}}^{\top}\hat{A}y=\frac{1}{1+\Delta}\max_{k\in\textup{supp}(y)}\hat{x}^{\top}Ae_{k} \displaystyle e_{i_{2}}^{\top}\hat{A}y\geq\frac{1}{1+\Delta}\max_{k\in\textup{supp}(y)}\hat{x}^{\top}Ae_{k} which proves ( 44c ) and ( 44d ), thus showing that \hat{A}\in\mathcal{Z}(\hat{x},y) . ∎ Combining Lemmas B.5 and B.6 with Corollary D.11 , we have that, whenever \textup{supp}(x)=\textup{supp}(\hat{x}) and \textup{supp}(y)=\textup{supp}(\hat{y}) , then: \displaystyle H(\mathcal{Z}(x,y),\mathcal{Z}(\hat{x},\hat{y}))\leq 8(\|x-\hat{x}\|_{1}+\|y-\hat{y}\|_{1}) (45) Hence, following arguments that are identical to the ones presented for Theorem B.4 , we obtain the following result. Theorem B.7 . Consider \alpha=0 and let m\in\widetilde{\mathcal{O}}\left(\frac{\log\left(\frac{1}{\delta}\right)}{\log(1/(1-\pi_{\min}))}+\frac{n+\log\left(\frac{1}{\delta}\right)}{\epsilon^{2}}\right). Then Algorithm 1 is (\epsilon,\delta) -correct for Zero-Sum Games and its sample complexity \tau_{\delta} is given by m . Proof. Use Equation 45 . Then, the proof follows from the same arguments of Theorem B.4 . ∎ Appendix C Proof of Theorem 4.2 This section is structured as follows: • In Section C.1 we prove the result for the inverse GSG problem ( Theorem C.5 ) • In Section C.2 , we prove the result of the inverse ZSG problem ( Theorem C.8 ) The proof of Theorem 4.2 then follows directly by combining Theorems C.5 and C.8 . C.1 Proof of Theorem C.5 ( \alpha>0 , General-Sum Games) Proof outline We begin our proof by considering two pair of strategies (x,y) and (\hat{x},\hat{y}) and, for any pair of matrix (A,B)\in\mathcal{G}_{\alpha}(x,y) we construct: • (\hat{A},\hat{B})\in\mathcal{G}_{\alpha}(\hat{x},y) and \mathcal{G}_{\alpha}(x,\hat{y}) such that \hat{A}\approx A and \hat{B}\approx B • (\hat{A},\hat{B})\in\mathcal{G}_{\alpha}(x,\hat{y}) and \mathcal{G}_{\alpha}(x,\hat{y}) such that \hat{A}\approx A and \hat{B}\approx B This first result is presented in Lemma C.1 . In Lemma C.2 , we discuss how well these matrices that we constructed approximate the original pair of matrices (A,B) . This lemma is the key result that we discussed in Section 4.2 . Specifically, it shows how these errors scales as, e.g. ,: \displaystyle\mathcal{O}\left(\frac{1}{\alpha}\sup_{S\in\mathcal{S}(\alpha)}\sum_{i\in S}(\hat{x}_{i}-x_{i})+\frac{1}{\alpha}\sum_{i:\hat{x}_{i}=0}x_{i}\right). Next, using Corollary D.11 , we will use this result to formally upper bound, with high probability, the Hausdorff distance between \mathcal{G}_{\alpha}(x,y) and \mathcal{G}_{\alpha}(\hat{x},\hat{y}) . This is done in Lemmas C.3 and C.4 . Finally, Theorem C.5 simply follows by selecting the number of samples in a way such that the high-probability Hausdorff distance upper bound is below \epsilon . We now start with matrix construction argument. Note that in the following lemma x,y,\hat{x},\hat{y} are generic strategies on the simplex. Lemma C.1 (Matrix construction, \alpha>0 , General-Sum Games) . Let \alpha>0 and x,y,\hat{x},\hat{y}\in\Delta_{n} . Consider (A,B)\in\mathcal{G}_{\alpha}(x,y) . It holds that: \displaystyle\exists(\hat{A},\hat{B})\in\mathcal{G}_{\alpha}(\hat{x},y):\|A-\hat{A}\|_{\infty}\leq 2\left(\frac{(\hat{x}-x)^{\top}Ay}{\alpha}\right)_{+}\textup{ and }\|B-\hat{B}\|_{\infty}\leq 2\left(\frac{\max_{j\in[n]}(\hat{x}-x)^{\top}B(y-e_{j})}{\alpha}\right)_{+} (46) \displaystyle\exists(\hat{A},\hat{B})\in\mathcal{G}_{\alpha}(x,\hat{y}):\|A-\hat{A}\|_{\infty}\leq 2\left(\frac{\max_{i\in[n]}(x-e_{i})^{\top}A(\hat{y}-y)}{\alpha}\right)_{+}\textup{ and }\|B-\hat{B}\|_{\infty}\leq 2\left(\frac{x^{\top}B(\hat{y}-y)}{\alpha}\right)_{+}. (47) Proof. We first prove Equation 46 . Specifically, for (A,B)\in\mathcal{G}_{\alpha}(x,y) we define (\hat{A},\hat{B}) as (\hat{A},\hat{B})=(\lambda_{A}A,\lambda_{B}B) , where \lambda_{A},\lambda_{B}\in\mathbb{R} are defined as follows \displaystyle\lambda_{A}=\min\left\{1,\frac{\alpha}{\max_{i\in[n]}\hat{x}^{\top}Ay-e_{i}^{\top}Ay}\right\},\quad\lambda_{B}=\min\left\{1,\frac{\alpha}{\max_{j\in[n]}\hat{x}By-\hat{x}Be_{j}}\right\}. From now on, w.l.o.g., we asume that \lambda_{A},\lambda_{B}>0 . Otherwise, we could simply pick \hat{A}=A and \hat{B}=B and all the Nash constraints are verified. Next, we verify that (A,B)\in\mathcal{G}_{\alpha}(\hat{x},y) . First, under the assumption that \lambda_{A},\lambda_{B}>0 , it follows that \lambda_{A},\lambda_{B}\in(0,1] , and hence \hat{A},\hat{B}\in[-1,1]^{n\times n} . Secondly, for any i\in[n] : \displaystyle\hat{x}^{\top}\hat{A}y-e_{i}^{\top}\hat{A}y \displaystyle=\lambda_{A}\left(\hat{x}^{\top}Ay-e_{i}^{\top}Ay\right) \displaystyle=\min\left\{1,\frac{\alpha}{\max_{i\in[n]}\hat{x}^{\top}Ay-e_{i}^{\top}Ay}\right\}\left(\hat{x}^{\top}Ay-e_{i}^{\top}Ay\right) \displaystyle\leq\alpha, where, (i) if \lambda_{A}<1 , the last step is trivial, and (ii) if \lambda_{A}=1 , then, \alpha>\max_{i\in[n]}\hat{x}^{\top}Ay-e_{i}^{\top}Ay . Thus, we have proved that \hat{A}\in\mathcal{G}^{x}_{\alpha}(\hat{x},y) . The proof for showing that \hat{B}\in\mathcal{G}^{y}_{\alpha}(\hat{x},y) is equivalent. Next, we proceed by analyzing \|A-\hat{A}\|_{\infty} . We consider the case where \lambda_{A}<1 , otherwise A=\hat{A} and Equation 46 is trivial. We have that: \displaystyle\|A-\hat{A}\|_{\infty} \displaystyle\leq(1-\lambda_{A})\|A\|_{\infty} \displaystyle\leq 2(1-\lambda_{A}) \displaystyle\leq 2\frac{\max_{i\in[n]}\hat{x}^{\top}Ay-e_{i}^{\top}Ay-\alpha}{\alpha} \displaystyle=2\frac{(\hat{x}-x)^{\top}Ay+x^{\top}Ay-\min_{i\in[n]}e_{i}^{\top}Ay-\alpha}{\alpha} \displaystyle\leq 2\frac{(\hat{x}-x)^{\top}Ay}{\alpha}, ( A\in\mathcal{G}_{\alpha}^{x}(x,y) ) which proves the first part of Equation 46 . One can follow the same steps to prove the second part of Equation 46 . The proof of Equation 47 follows from analogous argument. It is indeed sufficient to define (\hat{A},\hat{B})=(\tilde{\lambda}_{A}A,\tilde{\lambda}_{B}B) where: \displaystyle\tilde{\lambda}_{A}=\min\left\{1,\frac{\alpha}{\max_{i\in[n]}x^{\top}A\hat{y}-e_{i}^{\top}A\hat{y}}\right\},\quad\tilde{\lambda}_{B}=\min\left\{1,\frac{\alpha}{\max_{j\in[n]}x^{\top}B\hat{y}-x^{\top}Be_{j}}\right\}. The proof is thus concluded. ∎ Next, the following lemma shows how to upper bound the terms that appeared in Lemma C.1 . We briefly recall that, for any p\in\Delta^{n} , \mathcal{S}_{\alpha}(p) is defined as \displaystyle\mathcal{S}_{\alpha}(p)=\left\{S\subseteq[n]:\forall i\in S~p_{i}>0\text{ and }\sum_{i\in S}p_{i}\leq\frac{\alpha}{2}\right\}. Also in the following lemma, x,y,\hat{x},\hat{y} are generic strategies on the simplex. Lemma C.2 (Key Intermediate Step) . Let \alpha>0 and x,y,\hat{x},\hat{y}\in\Delta_{n} . The following holds: \displaystyle\sup_{A\in\mathcal{G}_{\alpha}^{x}(x,y)}\left((\hat{x}-x)^{\top}Ay\right)_{+}\leq 4\sup_{S\in\mathcal{S}_{\alpha}(x)}\sum_{i\in S}(\hat{x}_{i}-x_{i})+2\sum_{i:x_{i}=0}\hat{x}_{i} (48) \displaystyle\sup_{B\in\mathcal{G}_{\alpha}^{y}(x,y)}\left(\max_{j\in[n]}(\hat{x}-x)^{\top}B(y-e_{j})\right)_{+}\leq 4\sup_{S\in\mathcal{S}_{\alpha}(x)}\sum_{i\in S}(\hat{x}_{i}-x_{i})+2\sum_{i:x_{i}=0}\hat{x}_{i} (49) \displaystyle\sup_{A\in\mathcal{G}_{\alpha}^{x}(x,y)}\left(\max_{i\in[n]}(x-e_{i})^{\top}A(\hat{y}-y)\right)_{+}\leq 4\sup_{S\in\mathcal{S}_{\alpha}(y)}\sum_{j\in S}(\hat{y}_{j}-y_{j})+2\sum_{j:y_{j}=0}\hat{y}_{j} (50) \displaystyle\sup_{B\in\mathcal{G}_{\alpha}^{y}(x,y)}\left(x^{\top}B(\hat{y}-y)\right)_{+}\leq 4\sup_{S\in\mathcal{S}_{\alpha}(y)}\sum_{j\in S}(\hat{y}_{j}-y_{j})+2\sum_{j:y_{j}=0}\hat{y}_{j}. (51) Proof. First, we observe that, due to symmetry, once Equation 48 and Equation 49 hold, Equation 50 and Equation 51 hold as well. We now start by proving Equation 48 . We assume w.l.o.g. that the supremum is positive. Furthermore, for any A\in\mathcal{G}_{\alpha}(x,y) , denote by \star\in[n] any index that attains the argmin in \min_{i\in[n]}(Ay)_{i} . Then, we have that: \displaystyle\sup_{A\in\mathcal{G}_{\alpha}^{x}(x,y)}\left((\hat{x}-x)^{\top}Ay\right)_{+} \displaystyle=\sup_{A\in\mathcal{G}_{\alpha}^{x}(x,y)}\sum_{i\in[n]}(\hat{x}_{i}-x_{i})[(Ay)_{i}-(Ay)_{\star}] ( \hat{x},x\in\Delta_{n} ) \displaystyle\leq\left(\sup_{A\in\mathcal{G}_{\alpha}^{x}(x,y)}\sum_{i:x_{i}>0}(\hat{x}_{i}-x_{i})[(Ay)_{i}-(Ay)_{\star}]\right)+2\sum_{i:x_{i}=0}\hat{x}_{i}\>. Let us focus on the remaining optimization problem over A . We are interested in solving: 20 20 20 The sup is attained since it is an optimization problem over a compact domain of a continuous function. \displaystyle\max_{A\in[-1,1]^{n\times n}}\sum_{i:x_{i}>0}(\hat{x}_{i}-x_{i})[(Ay)_{i}-(Ay)_{\star}] (52) \displaystyle\text{s.t.~}\sum_{i:x_{i}>0}x_{i}[(Ay)_{i}-(Ay)_{\star}]\leq\alpha. Let us introduce the following auxiliary variable c_{i}=x_{i}[(Ay)_{i}-(Ay)_{\star}]\in[0,2x_{i}] . Then, ( 52 ) is upper bounded by: \displaystyle\max_{(c_{1},\dots,c_{n})}\sum_{i:x_{i}>0}c_{i}\frac{(\hat{x}_{i}-x_{i})}{x_{i}} (53) \displaystyle\text{s.t.~}\sum_{i:x_{i}>0}c_{i}\leq\alpha\text{ and }c_{i}\in[0,2x_{i}]. This is a fractional knapsack problem. It is well-known that such problems can be solved by a greedy algorithm that sorts the indexes i ’s according to their value ( i.e. , \frac{\hat{x}_{i}-x_{i}}{x_{i}} ) and allocates the maximum value of c_{i} according to this order until all the budget ( i.e. , \sum_{i:x_{i}>0}c_{i}\leq\alpha ) expires. More formally, any optimal solution c^{\star} of ( 53 ) has the following shape. Let S\subseteq\{i\in[n]:x_{i}>0\} be any subset such that \min_{i\in S}\frac{\hat{x}_{i}-x_{i}}{x_{i}}\geq\max_{i\in S^{\complement}}\frac{\hat{x}_{i}-x_{i}}{x_{i}}, where S^{\complement}=\{i\in[n]:x_{i}>0\}\setminus S . Then c^{\star}_{i}=2x_{i} for all i\in S . Furthermore, there exists at most one j\in S^{\complement} such that c^{\star}_{j}\in[0,2x_{j}] . For all the remaining elements, we have that c^{\star}_{i}=0 . Hence, the optimal value of ( 53 ) can be written (and upper bounded) as follows: \displaystyle 2\sum_{i\in S}(\hat{x}_{i}-x_{i})+\frac{\hat{x}_{j}-x_{j}}{x_{j}}c^{\star}_{j} \displaystyle\leq 4\sum_{i\in S}(\hat{x}_{i}-x_{i}) \displaystyle\leq 4\sup_{S\in\mathcal{S}_{\alpha}(x)}\sum_{i\in S}(\hat{x}_{i}-x_{i}). (Def. of \mathcal{S}_{\alpha}(x) ) where the first inequality step follows from the fact that, for j\in S^{\complement} it holds that c_{j}\frac{\hat{x}_{j}-x_{j}}{x_{j}}\leq c_{i}\frac{\hat{x}_{i}-x_{i}}{x_{i}} for any i\in S . This concludes the proof of Equation 48 . Next, we continue by proving Equation 49 . Again, we assume w.l.o.g. that the sup is greater or equal than 0 . Then, we have that: \displaystyle\sup_{B\in\mathcal{G}_{\alpha}^{y}(x,y)}\left(\max_{j\in[n]}(\hat{x}-x)^{\top}B(y-e_{j})\right)_{+} \displaystyle=\max_{B\in\mathcal{G}_{\alpha}^{y}(x,y)}\max_{\star\in[n]}\sum_{i\in[n]}(\hat{x}_{i}-x_{i})\left[\sum_{j\in[n]}y_{j}B_{ij}-B_{i\star}\right] \displaystyle\leq\max_{B\in\mathcal{G}_{\alpha}^{y}(x,y)}\max_{\star\in[n]}\sum_{i:x_{i}>0}(\hat{x}_{i}-x_{i})\left[\sum_{j\in[n]}y_{j}B_{ij}-B_{i\star}\right]+2\sum_{i:x_{i}=0}\hat{x}_{i} \displaystyle=\max_{\star\in[n]}\max_{\begin{subarray}{c}B\in\mathcal{G}_{\alpha}(x,y)\\ \star\in\operatornamewithlimits{argmax}(\hat{x}-x)^{\top}B(y-e_{\star})\end{subarray}}\sum_{i:x_{i}>0}(\hat{x}_{i}-x_{i})\left[\sum_{j\in[n]}y_{j}B_{ij}-B_{i\star}\right]+2\sum_{i:x_{i}=0}\hat{x}_{i} \displaystyle\leq\max_{\star\in[n]}\max_{\begin{subarray}{c}B\in\mathcal{G}_{\alpha}(x,y)\end{subarray}}\sum_{i:x_{i}>0}(\hat{x}_{i}-x_{i})\left[\sum_{j\in[n]}y_{j}B_{ij}-B_{i\star}\right]+2\sum_{i:x_{i}=0}\hat{x}_{i}\>. Hence, fix any \star\in[n] in the outer maximization problem, and restrict our attention to the maximization problem over B , that is \displaystyle\max_{B\in[-1,1]^{n\times n}}\sum_{i:x_{i}>0}(\hat{x}_{i}-x_{i})\left[\sum_{j\in[n]}y_{j}B_{ij}-B_{i\star}\right] (54) \displaystyle\text{s.t.~}\sum_{i:x_{i}>0}x_{i}\left[\sum_{j\in[n]}y_{j}B_{ij}-B_{ik}\right]\leq\alpha\quad\forall k\in[n]. Since the \alpha -Nash constraint holds for all k\in[n] , it holds also for \star . Hence, we can upper bound ( 54 ) with the following problem: \displaystyle\max_{B\in[-1,1]^{n\times n}}\sum_{i:x_{i}>0}(\hat{x}_{i}-x_{i})\left[\sum_{j\in[n]}y_{j}B_{ij}-B_{i\star}\right] (55) \displaystyle\text{s.t.~}\sum_{i:x_{i}>0}x_{i}\left[\sum_{j\in[n]}y_{j}B_{ij}-B_{i\star}\right]\leq\alpha Introducing the variable c_{i}=x_{i}\left[\sum_{j\in[n]}y_{j}B_{ij}-B_{i\star}\right] and rewriting the objective function as \sum_{i:x_{i}>0}c_{i}\frac{\hat{x}_{i}-x_{i}}{x_{i}} , we obtain again a fractional knapsack problem that can be solved in closed form, as we presented above. Following the same steps as above, the proof is concluded. ∎ Here, we show how to exploit the previous results to upper bound the Hausdorff distance. Here, we will use the fact that \hat{x} and \hat{y} are the empirical mean of x and y after m samples. Lemma C.3 (Matrix Construction \to Hausdorff Distance) . Let \alpha>0 and x,y,\hat{x},\hat{y}\in\Delta_{n} . Specifically, \hat{x} and \hat{y} are the maximum likelihood estimators of x,y after m samples. Let f_{\alpha}(x,\hat{x}) and f_{\alpha}(y,\hat{y}) be defined as: \displaystyle f_{\alpha}(x,\hat{x})=\frac{16}{\alpha}\left(\sup_{S\in\mathcal{S}_{\alpha}(x)}\sum_{i\in S}(\hat{x}_{i}-x_{i})+\sup_{S\in\mathcal{S}_{\alpha}(\hat{x})}\sum_{i\in S}(x_{i}-\hat{x}_{i})+\sum_{i:\hat{x}_{i}=0}x_{i}\right) \displaystyle f_{\alpha}(y,\hat{y})=\frac{16}{\alpha}\left(\sup_{S\in\mathcal{S}_{\alpha}(y)}\sum_{j\in S}(\hat{y}_{j}-y_{j})+\sup_{S\in\mathcal{S}_{\alpha}(\hat{y})}\sum_{j\in S}(y_{j}-\hat{y}_{j})+\sum_{j:\hat{y}_{j}=0}y_{j}\right). It holds that: \displaystyle H(\mathcal{G}_{\alpha}(x,y),\mathcal{G}_{\alpha}(\hat{x},\hat{y})\leq f_{\alpha}(x,\hat{x})+f_{\alpha}(y,\hat{y}). Proof. From Corollary D.11 , we have that: \displaystyle H(\mathcal{G}_{\alpha}(x,y),\mathcal{G}_{\alpha}(\hat{x},\hat{y}) \displaystyle\leq H(\mathcal{G}_{\alpha}(x,y),\mathcal{G}_{\alpha}(\hat{x},y)+H(\mathcal{G}_{\alpha}(\hat{x},y),\mathcal{G}_{\alpha}(\hat{x},\hat{y}) Let us focus on the fist term. From Lemma C.1 , we have that: \displaystyle H(\mathcal{G}_{\alpha}(x,y),\mathcal{G}_{\alpha}(\hat{x},y)\leq 2\sup_{A\in\mathcal{G}^{x}_{\alpha}(x,y)}\left(\frac{(\hat{x}-x)^{\top}Ay}{\alpha}\right)_{+} \displaystyle+2\sup_{A\in\mathcal{G}^{x}_{\alpha}(\hat{x},y)}\left(\frac{(x-\hat{x})^{\top}Ay}{\alpha}\right)_{+}+ \displaystyle+\sup_{A\in\mathcal{G}^{y}_{\alpha}(x,y)}2\left(\frac{\max_{j\in[n]}(\hat{x}-x)^{\top}B(y-e_{j})}{\alpha}\right)_{+}+ \displaystyle+\sup_{A\in\mathcal{G}^{y}_{\alpha}(\hat{x},y)}2\left(\frac{\max_{j\in[n]}(x-\hat{x})^{\top}B(y-e_{j})}{\alpha}\right)_{+} This, in turn, can be upper bounded using Lemma C.2 . We thus obtain: \displaystyle H(\mathcal{G}_{\alpha}(x,y),\mathcal{G}_{\alpha}(\hat{x},y)\leq\frac{16}{\alpha}\left(\sup_{S\in\mathcal{S}_{\alpha}(x)}\sum_{i\in S}(\hat{x}_{i}-x_{i})+\sup_{S\in\mathcal{S}_{\alpha}(\hat{x})}\sum_{i\in S}(x_{i}-\hat{x}_{i})+\sum_{i:\hat{x}_{i}=0}x_{i}\right), where we used the fact that \sum_{x_{i}=0}\hat{x}_{i}=0 . Similarly, for H(\mathcal{G}_{\alpha}(\hat{x},y),\mathcal{G}_{\alpha}(\hat{x},\hat{y}) , we obtain: \displaystyle H(\mathcal{G}_{\alpha}(\hat{x},y),\mathcal{G}_{\alpha}(\hat{x},\hat{y})\leq\frac{16}{\alpha}\left(\sup_{S\in\mathcal{S}_{\alpha}(y)}\sum_{j\in S}(\hat{y}_{j}-y_{j})+\sup_{S\in\mathcal{S}_{\alpha}(\hat{y})}\sum_{j\in S}(y_{j}-\hat{y}_{j})+\sum_{j:\hat{y}_{j}=0}y_{j}\right), thus concluding the proof. ∎ The following lemma shows how to upper bound with probabilistic argument the terms that appeared in the previous lemma. Lemma C.4 (Haussdorf High-Probability upper bound) . Let m be such that: \displaystyle m\geq 1+\frac{4\left(n+\log\left(\frac{24}{\delta}\right)\right)}{\alpha}. (56) With probability at least 1-\delta it holds that: \displaystyle H(\mathcal{G}_{\alpha}(x,y),\mathcal{G}_{\alpha}(\hat{x},\hat{y})\leq\frac{64}{\alpha}\left(\sqrt{\frac{4\alpha\left(n+\log\left(\frac{6}{\delta}\right)\right)}{m}}+\frac{5(n+\log\left(\frac{6}{\delta}\right))}{m}+\frac{3\sqrt{n}\log\left(\frac{6}{\delta}\right)}{m}\right). Proof. We first fix any m\geq 1 and we consider the following good event \mathcal{E}=\mathcal{E}_{\textup{miss}}\cap\mathcal{E}_{\textup{set}}\cap\mathcal{E}_{\text{err},x}\cap\mathcal{E}_{\text{err},y} where these events are defined as: \displaystyle\mathcal{E}_{\text{miss}}=\left\{\sum_{i:\hat{x}_{i}=0}x_{i}-\mathbb{E}\left[\sum_{i:\hat{x}_{i}=0}x_{i}\right]\leq\frac{3\sqrt{n}\log\left(\frac{6}{\delta}\right)}{m}\right\}\bigcap\left\{\sum_{j:\hat{y}_{j}=0}y_{j}-\mathbb{E}\left[\sum_{j:\hat{y}_{j}=0}y_{j}\right]\leq\frac{3\sqrt{n}\log\left(\frac{6}{\delta}\right)}{m}\right\} \displaystyle\mathcal{E}_{\text{set},x}=\bigcap_{S\subseteq[n]}\left\{\Bigg|\sum_{i\in S}(\hat{x}_{i}-x_{i})\Bigg|\leq\sqrt{\frac{2\sum_{i\in S}\hat{x}_{i}\left(n+\log(\frac{24}{\delta})\right)}{m}}+\frac{4(n+\log(\frac{24}{\delta}))}{m-1}\right\} \displaystyle\mathcal{E}_{\text{set},y}=\bigcap_{S\subseteq[n]}\left\{\Bigg|\sum_{j\in S}(\hat{y}_{j}-y_{j})\Bigg|\leq\sqrt{\frac{2\sum_{j\in S}\hat{y}_{j}\left(n+\log(\frac{24}{\delta})\right)}{m}}+\frac{4(n+\log(\frac{24}{\delta}))}{m-1}\right\} \displaystyle\mathcal{E}_{\text{err},x}=\bigcap_{S\in\mathcal{S}_{2\alpha}(x)}\left\{\Bigg|\sum_{i\in S}(\hat{x}_{i}-x_{i})\Bigg|\leq\sqrt{\frac{4\alpha\left(n+\log\left(\frac{6}{\delta}\right)\right)}{m}}+\frac{4(n+\log\left(\frac{6}{\delta}\right))}{m}\right\} \displaystyle\mathcal{E}_{\text{err},y}=\bigcap_{S\in\mathcal{S}_{2\alpha}(y)}\left\{\Bigg|\sum_{j\in S}(\hat{y}_{j}-y_{j})\Bigg|\leq\sqrt{\frac{4\alpha\left(n+\log\left(\frac{6}{\delta}\right)\right)}{m}}+\frac{4(n+\log\left(\frac{6}{\delta}\right))}{m}\right\} We now continue by showing that \mathbb{P}(\mathcal{E})\geq 1-\delta . In particular, using a union bound, we obtain that \mathbb{P}(\mathcal{E})=1-\mathbb{P}(\mathcal{E}^{\complement})\geq 1-\left(\mathbb{P}\left(\mathcal{E}_{\text{miss}}^{\complement}\right)+\mathbb{P}\left(\mathcal{E}_{\text{set},x}^{\complement}\right)+\mathbb{P}\left(\mathcal{E}_{\text{set},y}^{\complement}\right)+\mathbb{P}\left(\mathcal{E}_{\text{err},x}^{\complement}\right)+\mathbb{P}\left(\mathcal{E}_{\text{err},y}^{\complement}\right)\right) . Hence, we continue by upper bounding the complement of each event that compose \mathcal{E} . We start from \mathbb{P}(\mathcal{E}^{\complement}_{\text{miss}}) . We have that: \displaystyle\mathbb{P}(\mathcal{E}^{\complement}_{\text{miss}})\leq\mathbb{P}\left(\sum_{i:\hat{x}_{i}=0}x_{i}-\mathbb{E}\left[\sum_{i:\hat{x}_{i}=0}x_{i}\right]\geq\frac{\sqrt{n}\log\left(\frac{6}{\delta}\right)}{m}\right)+\mathbb{P}\left(\sum_{i:\hat{y}_{i}=0}y_{i}-\mathbb{E}\left[\sum_{i:\hat{y}_{i}=0}y_{i}\right]\geq\frac{\sqrt{n}\log\left(\frac{6}{\delta}\right)}{m}\right)\leq\frac{\delta}{3}. where the last inequality is a direct application of concentration results for the missing mass, i.e. , Lemma D.2 . Next, we analyze \mathbb{P}(\mathcal{E}_{\text{set},x}^{\complement}) and \mathbb{P}(\mathcal{E}_{\text{set},y}^{\complement}) . Using Lemma D.5 , we have that: \displaystyle\mathbb{P}(\mathcal{E}_{\text{set},x}^{\complement})=\mathbb{P}\left(\exists S\subseteq[n]:\Bigg|\sum_{i\in S}(\hat{x}_{i}-x_{i})\Bigg|>\sqrt{\frac{2\sum_{i\in S}\hat{x}_{i}\left(n+\log(\frac{24}{\delta})\right)}{m}}+\frac{4(n+\log(\frac{24}{\delta}))}{m-1}\right)\leq\frac{\delta}{6}. Finally, it remains to analyze \mathbb{P}(\mathcal{E}_{\text{err},x}^{\complement}) and \mathbb{P}(\mathcal{E}_{\text{err},y}^{\complement}) . We present our argument for \mathbb{P}(\mathcal{E}_{\text{err},x}^{\complement}) and the computations for \mathbb{P}(\mathcal{E}_{\text{err},y}^{\complement}) follows from analogous arguments. Specifically, using Lemma D.5 , we have that: \displaystyle\mathbb{P}(\mathcal{E}_{\text{err},x}^{\complement})=\mathbb{P}\left(\exists S\in\mathcal{S}(2\alpha):\Bigg|\sum_{i\in S}(\hat{x}_{i}-x_{i})\Bigg|\geq\sqrt{\frac{4\alpha\left(n+\log\left(\frac{6}{\delta}\right)\right)}{m}}+\frac{4(n+\log\left(\frac{6}{\delta}\right))}{m}\right)\leq\frac{\delta}{6}. Hence, we obtained that \mathbb{P}(\mathcal{E})\geq 1-\delta . At this point, we proceed by upper bounding the Hausdorff distance under the good event \mathcal{E} . We start by applying Lemma C.3 and we analyze f_{\alpha}(x,\hat{x}) . 21 21 21 The arguments for upper bounding f_{\alpha}(y,\hat{y}) are symmetric. We recall that: \displaystyle f_{\alpha}(x,\hat{x}) \displaystyle=\frac{16}{\alpha}\left(\sup_{S\in\mathcal{S}_{\alpha}(x)}\sum_{i\in S}(\hat{x}_{i}-x_{i})+\sup_{S\in\mathcal{S}_{\alpha}(\hat{x})}\sum_{i\in S}(x_{i}-\hat{x}_{i})+\sum_{i:\hat{x}_{i}=0}x_{i}\right) At this point, let us focus on \mathcal{S}_{\alpha}(\hat{x}) . With probability at least 1-\delta it holds that: \displaystyle\mathcal{S}_{\alpha}(\hat{x}) \displaystyle=\{S\subseteq[n]:\hat{x}_{i}>0~\forall i\in S\text{ and }\sum_{i\in S}\hat{x}_{i}\leq\tfrac{\alpha}{2}\} \displaystyle\subseteq\{S\subseteq[n]:x_{i}>0~\forall i\in S\text{ and }\sum_{i\in S}\hat{x}_{i}\leq\tfrac{\alpha}{2}\} ( \hat{x}_{i}>0\implies x_{i}>0 ) \displaystyle=\left\{S\subseteq[n]:x_{i}>0~\forall i\in S\text{ and }\sum_{i\in S}\hat{x}_{i}\leq\tfrac{\alpha}{2}\text{ and }\sum_{i\in S}x_{i}\leq\tfrac{\alpha}{2}+\Big|\sum_{i\in S}x_{i}-\hat{x}_{i}\Big|\right\} \displaystyle\subseteq\left\{S\subseteq[n]:x_{i}>0~\forall i\in S\text{ and }\sum_{i\in S}\hat{x}_{i}\leq\tfrac{\alpha}{2}\text{ and }\sum_{i\in S}x_{i}\leq\tfrac{\alpha}{2}+\sqrt{\frac{2\sum_{i\in S}\hat{x}_{i}(n+\log(\frac{24}{\delta}))}{m}}+\frac{4(n+\log(\frac{24}{\delta}))}{m-1}\right\} \displaystyle=\left\{S\subseteq[n]:x_{i}>0~\forall i\in S\text{ and }\sum_{i\in S}\hat{x}_{i}\leq\tfrac{\alpha}{2}\text{ and }\sum_{i\in S}x_{i}\leq\tfrac{\alpha}{2}+\sqrt{\frac{\alpha(n+\log(\frac{24}{\delta}))}{m}}+\frac{4(n+\log(\frac{24}{\delta}))}{m-1}\right\} \displaystyle\subseteq\left\{S\subseteq[n]:x_{i}>0~\forall i\in S\text{ and }\sum_{i\in S}x_{i}\leq\tfrac{\alpha}{2}+\sqrt{\frac{\alpha(n+\log(\frac{24}{\delta}))}{m}}+\frac{4(n+\log(\frac{24}{\delta}))}{m-1}\right\} \displaystyle\subseteq\{S\subseteq[n]:x_{i}>0~\forall i\in S\text{ and }\sum_{i\in S}x_{i}\leq\alpha\} ( Equation 56 ) \displaystyle=S_{2\alpha}(x). where (i) the equality steps in the middle of these arguments follows from the fact that, with high probability, \sum_{i\in S}\hat{x}_{i}\leq\frac{\alpha}{2} implies the additional conditions that are mentioned in the formula, and (ii) the last \subseteq step follows rom the fact that, if m satisfies Equation 56 , then: \displaystyle\sqrt{\frac{\alpha(n+\log(\frac{24}{\delta})}{m}}+\frac{4\log(\frac{24}{\delta})}{m-1}\leq\frac{\alpha}{2}. Plugging this result within f_{\alpha}(x,\hat{x}) , we have that, with probability at least 1-\delta , \displaystyle f_{\alpha}(x,\hat{x}) \displaystyle\leq\frac{32}{\alpha}\left(\sup_{S\in\mathcal{S}_{2\alpha}(x)}\Bigg|\sum_{i\in S}\hat{x}_{i}-x_{i}\Bigg|+\sum_{i:\hat{x}_{i}=0}x_{i}\right) \displaystyle\leq\frac{32}{\alpha}\left(\sqrt{\frac{4\alpha\left(n+\log\left(\frac{6}{\delta}\right)\right)}{m}}+\frac{4(n+\log\left(\frac{6}{\delta}\right))}{m}+\sum_{i:\hat{x}_{i}=0}x_{i}\right) (Def. of \mathcal{E} ) \displaystyle\leq\frac{32}{\alpha}\left(\sqrt{\frac{4\alpha\left(n+\log\left(\frac{6}{\delta}\right)\right)}{m}}+\frac{4(n+\log\left(\frac{6}{\delta}\right))}{m}+\frac{3\sqrt{n}\log\left(\frac{6}{\delta}\right)}{m}+\mathbb{E}\left[\sum_{i:\hat{x}_{i}=0}x_{i}\right]\right). (Def. of \mathcal{E} ) It thus remains to control \mathbb{E}[\sum_{i:\hat{x}_{i}=0}x_{i}] . It holds that: \displaystyle\mathbb{E}\left[\sum_{i:\hat{x}_{i}=0}x_{i}\right]=\sum_{i\in[n]}x_{i}\mathbb{P}[\hat{x}_{i}=0]=\sum_{i\in[n]}x_{i}(1-x_{i})^{m}\leq n\max_{p\in[0,1]}p(1-p)^{m}\leq\frac{n}{m}. Following similar steps, we arrived at the following high-probability bound: \displaystyle H(G_{\alpha}(x,y),\mathcal{G}_{\alpha}(\hat{x},\hat{y}) \displaystyle\leq f_{\alpha}(x,\hat{x})+f_{\alpha}(y,\hat{y}) \displaystyle\leq\frac{64}{\alpha}\left(\sqrt{\frac{4\alpha\left(n+\log\left(\frac{6}{\delta}\right)\right)}{m}}+\frac{5(n+\log\left(\frac{6}{\delta}\right))}{m}+\frac{3\sqrt{n}\log\left(\frac{6}{\delta}\right)}{m}\right), which concludes the proof. ∎ We are now ready to prove Theorem C.5 . Theorem C.5 . Let \alpha>0 and let m\in{\mathcal{O}}\left(\frac{n+\log(\frac{1}{\delta})}{\alpha\epsilon^{2}}+\frac{\sqrt{n}\log\left(\frac{1}{\delta}\right)}{\alpha\epsilon}\right). Then, Algorithm 1 is (\epsilon,\delta) -correct for General-Sum Games and its sample complexity \tau_{\delta} is given by m . Proof. Let m_{1},m_{2},m_{3},m_{4} be defined as follows: \displaystyle m_{1}=1+\frac{4\left(n+\log\left(\frac{24}{\delta}\right)\right)}{\alpha} \displaystyle m_{2}=\frac{16(192)^{2}(n+\log(6/\delta))}{\alpha\epsilon^{2}} \displaystyle m_{3}=\frac{960(n+\log(6/\delta))}{\alpha\epsilon} \displaystyle m_{4}=\frac{576\sqrt{n}\log(6/\delta)}{\epsilon\alpha}. Finally, let m=\lceil\max\{m_{1},m_{2},m_{3},m_{4}\}\rceil . Since m\geq m_{1} , we can apply Lemma C.4 , and using the definition of m , one can verify that, with probability at least 1-\delta , 22 22 22 Here, we note that m\geq m_{i} imposes that the i+1 -th error term in the statement of Lemma C.4 is bounded by \tfrac{\epsilon}{3} . \displaystyle H(\mathcal{G}_{\alpha}(x,y),\mathcal{G}_{\alpha}(\hat{x},\hat{y}))\leq\epsilon. thus concluding the proof. ∎ C.2 Proof of Theorem C.8 ( \alpha>0 , Zero-Sum Games) Proof outline The proof of Theorem C.8 is in the same spirit as that of Theorem C.5 . Specifically, first, for any pair of strategies (x,y) and (\hat{x},\hat{y}) , we fix a matrix A\in\mathcal{Z}_{\alpha}(x,y) and we construct a pair of matrices (\hat{A}_{1},\hat{A}_{2})\in\mathcal{Z}_{\alpha}(\hat{x},y)\times\mathcal{Z}_{\alpha}(x,\hat{y}) ( Lemma C.6 ). Remarkably, \hat{A}_{1}\approx A and \hat{A}_{2}\approx A with error rates that are similar to those that we presented for the General-Sum Setting. Then, in Lemma C.7 , we upper bound these errors by heavily exploiting the key intermediate step that we presented for GSG’s ( i.e. , Lemma C.2 ). Once this result is obtained, one can follow the same exact proof for General-Sum as for Zero-Sum Games. Lemma C.6 (Matrix construction, \alpha>0 , Zero-Sum Games) . Let \alpha>0 and x,y,\hat{x},\hat{y}\in\Delta_{n} . Consider A\in\mathcal{Z}_{\alpha}(x,y) . It holds that: \displaystyle\exists\hat{A}\in\mathcal{Z}_{\alpha}(\hat{x},y):\|A-\hat{A}\|_{\infty}\leq 2\left(\max\left\{\frac{(\hat{x}-x)^{\top}Ay}{\alpha},\frac{\max_{j\in[n]}(\hat{x}-x)^{\top}A(e_{j}-y)}{\alpha}\right\}\right)_{+} (57) \displaystyle\exists\hat{A}\in\mathcal{Z}_{\alpha}(x,\hat{y}):\|A-\hat{A}\|_{\infty}\leq 2\left(\max\left\{\frac{\max_{i\in[n]}(x-e_{i})^{\top}A(\hat{y}-y)}{\alpha},\frac{x^{\top}A(y-\hat{y})}{\alpha}\right\}\right)_{+}. (58) Proof. We first prove Equation 57 . Let A\in\mathcal{Z}_{\alpha}(x,y) . We define \hat{A}=\lambda A where \lambda\in\mathbb{R} is given by: \displaystyle\lambda=\min\left\{1,\frac{\alpha}{\max\{\max_{i\in[n]}\hat{x}^{\top}Ay-e_{i}^{\top}Ay,\max_{j\in[n]}\hat{x}^{\top}Ae_{j}-\hat{x}^{\top}Ay\}}\right\}. In the following, we assume w.l.o.g., that \lambda\geq 0 . If \lambda<0 , one could pick \hat{A}=A and all the equilibrium constraints would be satisfied. Now, we verify that A\in\mathcal{Z}_{\alpha}(\hat{x},y) . First, since \lambda\in(0,1] , we have that \hat{A}\in[-1,1]^{n\times n} . Secondly, for all i\in[n] it holds that: \displaystyle\hat{x}^{\top}\hat{A}y-e_{i}^{\top}\hat{A}y \displaystyle=\lambda(\hat{x}^{\top}Ay-e_{i}^{\top}Ay) \displaystyle=\min\left\{1,\frac{\alpha}{\max\{\max_{i\in[n]}\hat{x}^{\top}Ay-e_{i}^{\top}Ay,\max_{j\in[n]}\hat{x}^{\top}Ae_{j}-\hat{x}^{\top}Ay\}}\right\}(\hat{x}^{\top}Ay-e_{i}^{\top}Ay) \displaystyle\leq\alpha, where, (i) if \lambda=1 , we have that \max_{i\in[n]}\hat{x}^{\top}Ay-e_{i}^{\top}Ay\leq\alpha , and (ii) if \lambda<1 , the last step is trivial. Following similar arguments, one can prove that \hat{x}^{\top}\hat{A}e_{j}-\hat{x}^{\top}\hat{A}y\leq\alpha for all j\in[n] . Hence, \hat{A}\in\mathcal{Z}_{\alpha}(\hat{x},y) . Next, we proceed by analyzing \|A-\hat{A}\|_{\infty} . We consider the case where \lambda<1 , otherwise A=\hat{A} and Equation 57 is direct. We have that: \displaystyle\|A-\hat{A}\|_{\infty} \displaystyle\leq(1-\lambda)\|A\|_{\infty} \displaystyle\leq 2(1-\lambda) \displaystyle\leq 2\frac{\max\{\max_{i\in[n]}\hat{x}^{\top}Ay-e_{i}^{\top}Ay,\max_{j\in[n]}\hat{x}^{\top}Ae_{j}-\hat{x}^{\top}Ay\}-\alpha}{\alpha} \displaystyle\leq 2\max\left\{\frac{\max_{i\in[n]}\hat{x}^{\top}Ay-e_{i}^{\top}Ay-\alpha}{\alpha},\frac{\max_{j\in[n]}\hat{x}^{\top}Ae_{j}-\hat{x}^{\top}Ay-\alpha}{\alpha}\right\} \displaystyle\leq 2\max\left\{\frac{(\hat{x}-x)^{\top}Ay}{\alpha},\frac{\max_{j\in[n]}(\hat{x}-x)^{\top}A(e_{j}-y)}{\alpha}\right\}, ( A\in\mathcal{Z}_{\alpha}(x,y) ) thus concluding the proof of Equation 57 . The proof of Equation 58 follows from analogous arguments. One has simply to define \hat{A}=\tilde{\lambda}A where \tilde{\lambda} is given by: \displaystyle\tilde{\lambda}=\min\left\{1,\frac{\alpha}{\max\{\max_{i\in[n]}x^{\top}A\hat{y}-e_{i}^{\top}A\hat{y},\max_{j\in[n]}x^{\top}Ae_{j}-x^{\top}A\hat{y}\}}\right\}. ∎ The following results extend the key intermediate that we presented for General-Sum Games ( i.e. , Lemma C.2 ) to the Zero-Sum Games problem. The proof exploits a connection between the quantities that arise in Lemma C.6 and those that we already upper-bounded in Lemma C.2 . Lemma C.7 (Key Intermediate Step (Zero-Sum Games)) . Let \alpha>0 and x,y,\hat{x},\hat{y}\in\Delta_{n} . The following holds: \displaystyle\sup_{A\in\mathcal{Z}_{\alpha}(x,y)}(\hat{x}-x)^{\top}Ay\leq 4\sup_{S\in\mathcal{S}_{\alpha}(x)}\sum_{i\in S}(\hat{x}_{i}-x_{i})+2\sum_{i:x_{i}=0}\hat{x}_{i} (59) \displaystyle\sup_{A\in\mathcal{Z}_{\alpha}(x,y)}\max_{j\in[n]}(\hat{x}-x)^{\top}A(e_{j}-y)\leq 4\sup_{S\in\mathcal{S}_{\alpha}(x)}\sum_{i\in S}(\hat{x}_{i}-x_{i})+2\sum_{i:x_{i}=0}\hat{x}_{i} (60) \displaystyle\sup_{A\in\mathcal{Z}_{\alpha}(x,y)}{\max_{i\in[n]}(x-e_{i})^{\top}A(\hat{y}-y)}\leq 4\sup_{S\in\mathcal{S}_{\alpha}(y)}\sum_{j\in S}(\hat{y}_{j}-y_{j})+2\sum_{j:y_{j}=0}\hat{y}_{j} (61) \displaystyle\sup_{A\in\mathcal{Z}_{\alpha}(x,y)}x^{\top}A(y-\hat{y})\leq 4\sup_{S\in\mathcal{S}_{\alpha}(y)}\sum_{j\in S}(\hat{y}_{j}-y_{j})+2\sum_{j:y_{j}=0}\hat{y}_{j} (62) Proof. We start by proving Equation 59 . Specifically, we have that: \displaystyle\sup_{A\in\mathcal{Z}_{\alpha}(x,y)}(\hat{x}-x)^{\top}Ay \displaystyle\leq\sup_{A\in\mathcal{G}^{x}_{\alpha}(x,y)}(\hat{x}-x)^{\top}Ay \displaystyle\leq 4\sup_{S\in\mathcal{S}_{\alpha}(x)}\sum_{i\in S}(\hat{x}_{i}-x_{i})+2\sum_{i:x_{i}=0}\hat{x}_{i}, ( Lemma C.2 ) where in the first inequality we have simply dropped the constraints x^{\top}Ae_{j}-x^{\top}Ay\leq\alpha for all j\in[n] . We can follow the same argument ( i.e. , simply drop the constraints) also for proving Equation 61 . Next, we continue with Equation 60 . We have that: \displaystyle\sup_{A\in\mathcal{Z}_{\alpha}(x,y)}\max_{j\in[n]}(\hat{x}-x)^{\top}A(e_{j}-y)\leq\sup_{B\in\mathcal{G}_{\alpha}^{y}(x,y)}\max_{j\in[n]}(\hat{x}-x)^{\top}B(y-e_{j}) \displaystyle\sup_{S\in\mathcal{S}_{\alpha}(x)}\sum_{i\in S}(\hat{x}_{i}-x_{i})+2\sum_{i:x_{i}=0}\hat{x}_{i}, ( Lemma C.2 ) where, in the first step, we have dropped the constraints x^{\top}Ay-e_{i}^{\top}Ay\leq\alpha and we applied a change of variable B=-A . We can use the same argument ( i.e. , dropping constraints and change of variable) also for proving Equation 62 . ∎ We can now prove Theorem C.8 Theorem C.8 . Let \alpha>0 and let m\in{\mathcal{O}}\left(\frac{n+\log\left(\frac{1}{\delta}\right)}{\alpha\epsilon^{2}}+\frac{\sqrt{n}\log\left(\frac{1}{\delta}\right)}{\alpha\epsilon}\right). Then, Algorithm 1 is (\epsilon,\delta) -correct for Zero-Sum Games, and its sample complexity \tau_{\delta} is given by m . Proof. Combining Lemma C.6 and Lemma C.7 , we can upper bound the Hausdorff distance H(\mathcal{Z}_{\alpha}(x,y),\mathcal{Z}_{\alpha}(\hat{x},\hat{y})) with the same quantities that we obtained in General Sum Games ( i.e. , those appearing in Lemma C.3 ). Hence, we can proceed as in the proof of General-Sum Games, and we obtain the same result. ∎ Appendix D Auxiliary Lemmas In this section, we provide statements of auxiliary lemma that are used throughout our analysis. D.1 Concentrations and Probabilities Lemma D.1 . Consider D\in\mathbb{N}_{>0} and p\in\Delta_{D} . Let \hat{p}_{m} be the maximum likelihood estimate of p obtained with m\geq 1 samples. Consider a threshold level \beta>0 and let \mathcal{I}(\beta)=\{i\in[D]:x_{i}\geq\beta\} . If m\geq\frac{\log\left(\frac{D}{\delta}\right)}{\log\left(\frac{1}{1-\beta}\right)} , then, with probability at least 1-\delta , it holds that: \displaystyle\forall i\in\mathcal{I}(\beta),N_{i}(m)\geq 1. As a corollary, let p_{\min}\in\mathbb{R} as any real number that satisfies p_{\min}>0 and p_{\min}\leq\min_{i\in[D]:p_{i}>0}p_{i} . Then, if m\geq\frac{\log\left(\frac{D}{\delta}\right)}{\log\left(\frac{1}{1-p_{\min}}\right)} it holds that \displaystyle\mathbb{P}\left(\textup{supp}(p)\neq\textup{supp}(\hat{p}_{m})\right)\leq\delta. Proof. With probabilistic arguments, we have that: \displaystyle\mathbb{P}\left(\exists i\in\mathcal{I}(\beta):N_{i}(m)=0\right) \displaystyle\leq\sum_{i\in\mathcal{I}(\beta)}\mathbb{P}(N_{i}(m)=0) (Boole’s inequality) \displaystyle\leq\sum_{i:x_{i}\geq\beta}(1-x_{i})^{m} \displaystyle\leq D(1-\beta)^{m} \displaystyle\leq\delta, ( m\geq\frac{\log\left(\frac{D}{\delta}\right)}{\log\left(\frac{1}{1-\beta}\right)} ) where, in the second inequality, we have used the fact that, for any i , N_{i}(m)=0 if and only if, for all the samples m , the outcome i is never observed. The corollary is a direct application of this claim by setting \beta=p_{\min} . ∎ Lemma D.2 (Theorem A.2 in Rajaraman et al. 2020 ) . Consider D\in\mathbb{N}_{>0} and a distribution p\in\Delta_{D} . Consider a sequence P_{1},\dots,P_{m} of i.i.d. samples drawn from p . For all i\in[D] , let N_{i}(p)=\sum_{t=1}^{m}\bm{1}\left\{P_{t}=i\right\} . Then, for \delta\in(0,1) , it holds that: \displaystyle\mathbb{P}\left(\sum_{i\in[D]}p_{i}\bm{1}\left\{N_{i}(m)=0\right\}-\mathbb{E}\left[\sum_{i\in[D]}p_{i}\bm{1}\left\{N_{i}(m)=0\right\}\right]\geq\frac{{3\sqrt{D}\log\left(\frac{1}{\delta}\right)}}{n}\right)\leq\delta. Lemma D.3 . Consider D\in\mathbb{N}_{>0} and p\in\Delta_{D} . Let \hat{p} be the maximum likelihood estimator of p after m i.i.d. samples. Then, for any \delta\in(0,1] , it holds that: \displaystyle\mathbb{P}\left(\|p-\hat{p}_{m}\|_{1}>\sqrt{\frac{2\log(1/\delta)+2D\log(6m)}{m}}\right)\leq\delta. Proof. By Pinsker’s inequality we have: \|\hat{p}_{m}-p\|_{1}\leq\sqrt{2\textup{KL}(\hat{p}_{m},p)} where \textup{KL}(p_{1},p_{2}) denotes the Kullback–Leibler divergence between distributions p_{1} and p_{2} . Now, applying Proposition 1 in Jonsson et al. 2020 , we obtain \mathbb{P}\left[\forall m\in\mathbb{N}^{*},\>m\textup{KL}(\hat{p}_{m},p)\leq\log\left(\frac{1}{\delta}\right)+(D-1)\log\left(e\left(1+\frac{m}{D-1}\right)\right)\right]\geq 1-\delta. Thus, we obtained that: \mathbb{P}\left[\|\hat{p}_{m}-p\|_{1}\leq\sqrt{\frac{2}{m}\left(\log\left(\frac{1}{\delta}\right)+(D-1)\log\left(e\left(1+\frac{m}{D-1}\right)\right)\right)}\right]\geq 1-\delta. At this point, we observe that: \sqrt{\frac{2}{m}\left(\log\left(\frac{1}{\delta}\right)+(n-1)\log\left(e\left(1+\frac{m}{D-1}\right)\right)\right)}\leq\sqrt{\frac{2\log(1/\delta)+2D\log(6m)}{m}} Thus concluding the proof. ∎ Lemma D.4 . Let n>1 and v\in\{-1,1\}^{n-1} such that \sum_{k=1}^{n-1}v_{k}=0 . Furthermore, let \tfrac{1}{2}>\beta>\gamma>0 , \mathbb{P}=\left(\frac{\beta+\gamma\beta v_{1}}{n-1},\dots,\frac{\beta+\gamma\beta v_{n-1}}{n-1},1-\beta\right) , and \mathbb{Q}=\left(\frac{\beta}{n-1},\dots,\frac{\beta}{n-1},1-\beta\right) . Then, it holds that: \displaystyle\textup{KL}(\mathbb{P},\mathbb{Q})\leq 2\beta\gamma^{2}. Proof. We have that: \displaystyle\textup{KL}(\mathbb{P},\mathbb{Q}) \displaystyle=\sum_{i\in[n-1]:v_{i}=1}\frac{\beta+\gamma\beta}{n-1}\log\left(1+\gamma\right)+\sum_{i\in[n-1]:v_{i}=-1}\frac{\beta-\gamma\beta}{n-1}\log\left(1-\gamma\right) \displaystyle=\frac{1}{2}\beta(1+\gamma)\log(1+\gamma)+\frac{1}{2}\beta(1-\gamma)\log(1-\gamma) \displaystyle=\frac{\beta}{2}\left(\log(1-\gamma^{2})+\gamma\log(1+\gamma)-\gamma\log(1-\gamma)\right) \displaystyle\leq\frac{\beta}{2}\left(\gamma\log(1+\gamma)-\gamma\log(1-\gamma)\right) ( \log(1-\gamma^{2})\leq 0 ) \displaystyle\leq\frac{\beta}{2}\left(\gamma^{2}+\gamma\left(\frac{1}{1-\gamma}-1\right)\right) ( \log(1+x)\leq x and -\log(1-x)\leq\frac{1}{1-x}-1 for x\in(0,1) ) \displaystyle\leq 2\beta\gamma^{2}. This concludes the proof. ∎ Lemma D.5 (Variance Aware Error Control) . Let D\in\mathbb{N}_{>0} and p\in\Delta_{D} . Let \hat{p} be the maximum likelihood estimator of p after m i.i.d. samples where m>2 . Let \beta\in(0,1) and let \mathcal{S}(\beta)=\{S\subseteq[D]:\forall i\in S,p_{i}>0\text{ and}\sum_{i\in S}p_{i}\leq\beta\} . Then, for \delta\in(0,1) it holds that: \displaystyle\mathbb{P}\left(\exists S\in\mathcal{S}(\beta):\Bigg|\sum_{i\in S}(p_{i}-\hat{p}_{i})\Bigg|>\sqrt{\frac{4\beta\left(D+\log\left(\frac{1}{\delta}\right)\right)}{m}}+\frac{4(D+\log\left(\frac{1}{\delta}\right))}{m}\right)\leq\delta. (63) Furthermore, for \delta\in(0,1) it holds that: \displaystyle\mathbb{P}\left(\exists S\subseteq[n]>\sqrt{\frac{2\sum_{i\in S}\hat{p}_{i}\left(D+\log(\frac{4}{\delta})\right)}{m}}+\frac{4(D+\log(\frac{4}{\delta})}{m-1}\right)\leq\delta. (64) Proof. We start by proving Equation 63 . Fix a set S\in\mathcal{S}(\beta) , then \sum_{i\in S}\hat{p}_{i} is the empirical mean of a Bernoulli r.v. with mean \mu=\sum_{i\in S}p_{i} . Hence, for \delta^{\prime}\in(0,1) , a standard application of Bernstein’s inequality [ Boucheron et al. 2003 ] yields \displaystyle\mathbb{P}\left(\Bigg|\sum_{i\in S}(p_{i}-\hat{p}_{i})\Bigg|>\sqrt{\frac{4\beta\log\left(\frac{1}{\delta^{\prime}}\right)}{m}}+\frac{4\log\left(\frac{1}{\delta^{\prime}}\right)}{m}\right)\leq\delta^{\prime}, where we have used that \mathbb{V}\mathrm{ar}(\sum_{i\in S}p_{i})\leq\sum_{i\in S}p_{i}\leq\beta . Now, for any value of \beta , the cardinality of \mathcal{S}(\beta) is bounded by 2^{D} . Hence, for any \delta^{\prime}\in(0,1) we have that: \displaystyle\mathbb{P}\left(\exists S\in\mathcal{S}(\beta):\Bigg|\sum_{i\in S}(p_{i}-\hat{p}_{i})\Bigg|>\sqrt{\frac{4\beta\log\left(\frac{1}{\delta^{\prime}}\right)}{m}}+\frac{4\log\left(\frac{1}{\delta^{\prime}}\right)}{m}\right)\leq 2^{D}\delta^{\prime}. Picking \delta^{\prime}=\frac{\delta}{2^{D}} concludes the proof. Equation 64 follows from similar arguments, but we replaced Bernstein’s inequality with its empirical version [ Maurer and Pontil 2009 ] . In particular, the empirical Bernstein’s inequality, replace the variance in the Bernstein inequality with the sample variance. In the following, we show how the sample variance of a Bernoulli r.v. with mean q can be upper bouded with 2\hat{q} . Let Denote by Z_{1},\dots,Z_{m}\sim q the m independent samples from q . Then: \displaystyle\hat{\mathbb{V}\mathrm{ar}}(\hat{q}) \displaystyle=\frac{1}{m(m-1)}\sum_{i0 for k\in\textup{supp}(x) and each e_{k}^{\top}Ay\geq x^{\top}Ay (by assumption), it must follows that e_{k}^{\top}Ay=x^{\top}Ay for all k\in\textup{supp}(x) . Hence, we have proved the first condition of (ii) and it remains to prove that for all j\notin\textup{supp}(x) and all i\in\textup{supp}(x) , we have that e_{i}^{\top}Ay\leq e_{j}^{\top}Ay . Fix any j\notin\textup{supp}(x) . By assumption (i), we have x^{\top}Ay\leq e_{j}^{\top}Ay . Combining this with the equality e_{i}^{\top}Ay=x^{\top}Ay for all i\in\textup{supp}(x) , we obtain e_{i}^{\top}Ay\leq e_{j}^{\top}Ay\qquad\forall\,i\in\textup{supp}(x),\ \forall\,j\notin\textup{supp}(x), which concludes the proof of (i)\Rightarrow(ii) . We conclude the proof by showing that (ii) \Rightarrow (i). Assume (ii) holds. Let c denote the common value e_{i}^{\top}Ay for i\in\textup{supp}(x) . Then: x^{\top}Ay=\sum_{i\in\textup{supp}(x)}x_{i}\,\left(e_{i}^{\top}Ay\right)=\sum_{i\in S}x_{i}\,c=c. Hence, x^{\top}Ay\leq e_{i}^{\top}Ay for all i\in\textup{supp}(x) . For any j\notin\textup{supp}(x) , (ii) gives e_{j}^{\top}Ay\geq c=x^{\top}Ay , which concludes the proof. ∎ Lemma D.9 . Let c_{1},c_{2},K\in\mathbb{R}_{>0} and consider \bar{T}=\inf\left\{t\in\mathbb{N}:\frac{\log(c_{1}/\delta)+n\log(c_{2}t)}{t}\leq K^{2}\right\}. Then: \displaystyle\bar{T}\leq 2\left(2+\frac{4\log(c_{1}/\delta)}{K^{2}}+\frac{4n}{K^{2}}\log\left(\frac{2nc_{2}}{K^{2}}\right)\right). Proof. First, it is easy to see that: \displaystyle\bar{T} \displaystyle\leq\max\left\{\inf\left\{t\in\mathbb{N}:\frac{\log(c_{1}/\delta)}{t}\leq\frac{K^{2}}{2}\right\},\inf\left\{t\in\mathbb{N}:\frac{n\log(c_{2}t)}{t}\leq\frac{K^{2}}{2}\right\}\right\} \displaystyle\leq 2\left(\inf\left\{t\in\mathbb{N}:\frac{\log(c_{1}/\delta)}{t}\leq\frac{K^{2}}{2}\right\}+\inf\left\{t\in\mathbb{N}:\frac{n\log(c_{2}t)}{t}\leq\frac{K^{2}}{2}\right\}\right) \displaystyle\leq 2\left(1+\frac{4\log(c_{1}/\delta)}{K^{2}}+\inf\left\{t\in\mathbb{N}:\frac{n\log(c_{2}t)}{t}\leq\frac{K^{2}}{2}\right\}\right) \displaystyle\coloneqq 2\left(1+\frac{4\log(c_{1}/\delta)}{K^{2}}+\tilde{T}\right). It remains to analyze the term: \tilde{T}=\inf\left\{t\in\mathbb{N}:\frac{n\log(c_{2}t)}{t}\leq\frac{K^{2}}{2}\right\}=\left\{t\in\mathbb{N}:t\geq\frac{2n\log(c_{2}t)}{K^{2}}\right\}. By definition, for \tilde{T}-1 , we have that: \displaystyle\tilde{T}-1<\frac{2n\log(c_{2}(\tilde{T}-1))}{K^{2}}. (69) Since \log(x)\leq\sqrt{x} , we have that: \displaystyle\sqrt{\tilde{T}-1}<\frac{2n\sqrt{c_{2}}}{K^{2}}, which leads to: \displaystyle\tilde{T}-1<\left(\frac{2n\sqrt{c_{2}}}{K^{2}}\right)^{2}. Plugging this result within Equation 69 , we obtain: \displaystyle\tilde{T}<\frac{4n}{K^{2}}\log\left(\frac{2nc_{2}}{K^{2}}\right)+1, which leads to the desired result. ∎ Lemma D.10 (General Decomposition Error) . Let (\mathcal{Y},d) be a metric space and let \mathcal{X} be any set. Consider a compact-valued correspondence F:\mathcal{X}\times\mathcal{X}\mathchoice{\mathrel{\vbox{\vbox{\halign{#\cr$\displaystyle\mapstochar\varrightarrow$\cr$\displaystyle\mapstochar\varrightarrow$\cr}}}}}{\mathrel{\vbox{\vbox{\halign{#\cr$\textstyle\mapstochar\varrightarrow$\cr$\textstyle\mapstochar\varrightarrow$\cr}}}}}{\mathrel{\vbox{\vbox{\halign{#\cr$\scriptstyle\mapstochar\varrightarrow$\cr$\scriptstyle\mapstochar\varrightarrow$\cr}}}}}{\mathrel{\vbox{\vbox{\halign{#\cr$\scriptscriptstyle\mapstochar\varrightarrow$\cr$\scriptscriptstyle\mapstochar\varrightarrow$\cr}}}}}\mathcal{Y} , and let x_{1},x_{2},\hat{x}_{1},\hat{x}_{2}\in\mathcal{X} . It holds that: \displaystyle H_{d}(F(x_{1},x_{2}),F(\hat{x}_{1},\hat{x}_{2}))\leq H_{d}(F(x_{1},x_{2}),F(\hat{x}_{1},x_{2}))+H_{d}(F(\hat{x}_{1},x_{2}),F(\hat{x}_{1},\hat{x}_{2})). Proof. For any y\in\mathcal{Y} , let c(y)\in\operatornamewithlimits{argmin}_{c\in F(\hat{x}_{1},x_{2})}d(y,c) . Note that, by Heine-Cantor, this minimum is attained since d(y,\cdot) is a continuous function and F is compact-valued. Then, recall that: \displaystyle H_{d}(F(x_{1},x_{2}),F(\hat{x}_{1},\hat{x}_{2}) \displaystyle=\max\left\{\sup_{y\in F(x_{1},x_{2})}\inf_{\hat{y}\in F(\hat{x}_{1},\hat{x}_{2})}d(y,\hat{y}),\sup_{\hat{y}\in F(\hat{x}_{1},\hat{x}_{2})}\inf_{y\in F(x_{1},x_{2})}d(y,\hat{y})\right\} (70) Now, focus on the first term. We have that: \displaystyle\sup_{y\in F(x_{1},x_{2})}\inf_{\hat{y}\in F(\hat{x}_{1},\hat{x}_{2})}d(y,\hat{y}) \displaystyle\leq\sup_{y\in F(x_{1},x_{2})}\inf_{\hat{y}\in F(\hat{x}_{1},\hat{x}_{2})}\left(d(y,c(y))+d(c(y),\hat{y})\right) (Triangular inequality) \displaystyle=\sup_{y\in F(x_{1},x_{2})}\left(d(y,c(y))+\inf_{\hat{y}\in F(\hat{x}_{1},\hat{x}_{2})}d(c(y),\hat{y})\right) \displaystyle\leq\sup_{y\in F(x_{1},x_{2})}d(y,c(y))+\sup_{y\in F(x_{1},x_{2})}\inf_{\hat{y}\in F(\hat{x}_{1},\hat{x}_{2})}d(c(y),\hat{y}) \displaystyle\leq H_{d}(F(x_{1},x_{2}),F(\hat{x}_{1},x_{2}))+\sup_{y\in F(x_{1},x_{2})}\inf_{\hat{y}\in F(\hat{x}_{1},\hat{x}_{2})}d(c(y),\hat{y}) (Def. of c(y) ) \displaystyle\leq H_{d}(F(x_{1},x_{2}),F(\hat{x}_{1},x_{2}))+H_{d}(F(\hat{x}_{1},x_{2}),F(\hat{x}_{1},\hat{x}_{2})) ( c(y)\in F(\hat{x}_{1},x_{2}) ) Similarly, by using the triangular inequality with c(\hat{y}) , one has that: \displaystyle\sup_{\hat{y}\in F(\hat{x}_{1},\hat{x}_{2})}\inf_{y\in F(x_{1},x_{2})}d(y,\hat{y})\leq H_{d}(F(x_{1},x_{2}),F(\hat{x}_{1},x_{2}))+H_{d}(F(\hat{x}_{1},x_{2}),F(\hat{x}_{1},\hat{x}_{2})). Plugging these results within Equation 70 , concludes the proof. ∎ Corollary D.11 (Decomposition Error in Inverse Game Theory) . Let x,y,\hat{x},\hat{y}\in\Delta_{n} . Then, for \alpha\geq 0 , it holds that: \displaystyle H(\mathcal{G}_{\alpha}(x,y),\mathcal{G}_{\alpha}(\hat{x},\hat{y}))\leq H(\mathcal{G}_{\alpha}(x,y),\mathcal{G}_{\alpha}(\hat{x},y))+H(\mathcal{G}_{\alpha}(\hat{x},y),\mathcal{G}_{\alpha}(\hat{x},\hat{y})) \displaystyle H(\mathcal{Z}_{\alpha}(x,y),\mathcal{Z}_{\alpha}(\hat{x},\hat{y}))\leq H(\mathcal{Z}_{\alpha}(x,y),\mathcal{Z}_{\alpha}(\hat{x},y))+H(\mathcal{Z}_{\alpha}(\hat{x},y),\mathcal{Z}_{\alpha}(\hat{x},\hat{y})) Proof. This is a direct application of Lemma D.10 . ∎ Lemma D.12 (Packing argument [ Metelli et al. 2023 ] , Lemma E.6) . Let \mathcal{V}\;=\;\Bigl\{v\in\{-1,1\}^{D}:\sum_{j=1}^{D}v_{j}=0\Bigr\}. Then the \tfrac{D}{16} -packing number of \mathcal{V} with respect to the metric d(v,v^{\prime})\;=\;\sum_{j=1}^{D}\lvert v_{j}-v^{\prime}_{j}\rvert is lower bounded by 2^{D/5} .