Minimizing Regret on Reflexive Banach Spaces and Nash Equilibria in Continuous Zero-Sum Games
We study a general adversarial online learning problem, in which we are given a decision set X in a reflexive Banach space X and a sequence of reward vectors in the dual space of X. At each iteration, we choose an action from X , based on the observed sequence of previous rewards. Our goal is to minimize regret. Using results from infinite dimensional convex analysis, we generalize the method of Dual Averaging to our setting and obtain upper bounds on the worst-case regret that generalize many previous results. Under the assumption of uniformly continuous rewards, we obtain explicit regret bounds in a setting where the decision set is the set of probability distributions on a compact metric space S. Importantly, we make no convexity assumptions on either S or the reward functions. We also prove a general lower bound on the worst-case regret for any online algorithm. We then apply these results to the problem of learning in repeated two-player zero-sum games on compact metric spaces. In doing so, we first prove that if both players play a Hannan-consistent strategy, then with probability 1 the empirical distributions of play weakly converge to the set of Nash equilibria of the game. We then show that, under mild assumptions, Dual Averaging on the (infinite-dimensional) space of probability distributions indeed achieves Hannan-consistency.
results in the literature, including algorithms for online learning on finite sets (Arora et al., 2012) and finite-dimensional online convex optimization (Hazan et al., 2007).
Given a convex subset X of a reflexive Banach space X, the generalized Dual Averaging (DA) method maximizes, at each iteration, the cumulative past rewards (which are elements of X * , the dual space of X) minus a regularization term h. We show that under certain conditions, the maximizer in the DA update is the Fréchet gradient Dh * of the regularizer's conjugate function. In doing so, we develop a novel characterization of the duality between essential strong convexity of h and essential Fréchet differentiability of h * in reflexive Banach spaces, which is of independent interest.
We apply these general results to the problem of minimizing regret when the rewards are uniformly continuous functions over a compact metric space S. Importantly, we do not assume convexity of either S or the rewards, and show that it is possible to achieve sublinear regret under a mild geometric condition on S (namely, the existence of a locally Q-regular Borel measure). We provide explicit bounds for a class of regularizers, which guarantee sublinear worst-case regret. We also prove a general lower bound on the regret for any online algorithm and show that DA asymptotically achieves this bound up to a √ log t factor.
Our results are related to work by Lehrer (2003) and Sridharan and Tewari (2010); Srebro et al. (2011). Lehrer (2003) gives necessary geometric conditions for Blackwell approachability in infinitedimensional spaces, but no implementable algorithm guaranteeing Hannan-consistency. Sridharan and Tewari (2010) derive general regret bounds for Mirror Descent (MD) under the assumption that the strategy set is uniformly bounded in the norm of the Banach space. We do not make such an assumption here. In fact, this assumption does not hold in general for our applications in Section 3.
The paper is organized as follows: In Section 2 we introduce and provide a general analysis of Dual Averaging in reflexive Banach spaces. In Section 3 we apply these results to obtain explicit regret bounds on compact metric spaces with uniformly continuous reward functions. We use these results in Section 4 in the context of learning Nash equilibria in continuous two-player zero sum games, and provide a numerical example in Section 4. All proofs are given in the supplementary material.
The paper considers the problem of regret minimization in reflexive Banach spaces, and the main contribution is showing that properly tuned variants of dual averaging/FTRL can guarantee sublinear regret bounds in this setting. This result is then applied to the special case of regret minimization in compact metric spaces, where the authors are able to show explicit near-optimal rates that hold uniformly for all comparators. Finally, the authors apply their techniques for proposing algorithms for finding epsilon-Nash equilibria in continuous zero-sum games. The results are illustrated with several simple experiments and examples. 
POST-REBUTTAL COMMENTS  Thanks for the replies. I've found the example of X=L2(R) and \cal{X} = \Delta(X) to be convincing enough, so I understand now how the results are more general than those of Sridharan and Tewari (2010).  =============================  The paper is very technical and offers a rather demanding reading experience: the main paper is essentially a densely compressed collection of definitions and theorems for a number of different problem settings. The paper is made complete by a tremendous 17-page appendix that not only includes the full proofs, but adds several simulations, illustrative examples and technical results that are interesting in their own right. This structure itself is my main concern about the paper: I am not sure that NIPS is a suitable venue for such enormous papers with so much to say. Splitting papers so that the main file includes the main result and the supplement presents the proofs is considered normal by now; this current paper goes way beyond.  Despite my above comments, if the reader is familiar with the underlying concepts, the logic of the paper is reasonably easy to follow. The proofs are clean and appear to be correct. The techniques themselves are not very original: notably, the proof of the key result (Theorem 3) closely follows the analysis of Kwon and Mertikopoulos (2014). Other proof techniques are also familiar from related work. That said, I do appreciate the clarity and the generality of the new results in the current paper.  There is room for improvement in discussing the related literature. In particular, the authors write off the result of Sridharan and Tewari (COLT 2010) as being weaker than the new results because their bounds require a uniformly bounded strategy set. However, the results in the current paper also seem to make a similar assumption (Assumption S.2 in the appendix that seems to be necessary for proving all the results in the paper!), so I wouldn't consider this to be a serious distinction. Also, the authors fail to mention the follow-up work by Srebro, Sridharan and Tewari (NIPS 2011) who prove even more general results. I realize that some of the results in that work are way beyond the scope of this paper, but still, a short discussion would be useful to have. A discussion about how the bound of Corollary 3 relates to other results about continuous exponential weights would be even more useful.  Overall, while I'm not sure that the structure of the paper is really suitable for NIPS, I think that this is a solid technical paper that may warrant some interest.  Detailed comments ================= 020: Is Audibert and Bubeck (2009) really the best reference to illustrate this point? Maybe Cesa-Bianchi and Lugosi (2006) and Shalev-Shwartz (2011) are better references. 049: "existence" -> "existence of" 076: This is a strange way to define worst-case regret; worst-case is usually defined by taking the supremum over the sequence of losses, not the comparator.  086: "w.r.t. to" -> "w.r.t."; this occurs several times in the paper. 110: "strictly convex" was not defined formally, the notation A^{-1} for sets A likewise. Perhaps it would be good to give a reference to a convex analysis textbook for interested readers. 140: This theorem seems to require Assumption S.2 to hold. If so, please state this assumption in the main text. 149: Regret bounds that depend on the comparator x are sometimes the best one can hope for; see, e.g., McMahan and Orabona (COLT 2014). In particular, for the case of unbounded decision sets, it may not be reasonable to expect a bound that holds simultaneously for all x. 222: Also note that this choice of regularizer coincides with the entropic barrier of Bubeck and Eldan (COLT 2015) for Euclidean spaces. 237: "w is any function with modulus of continuity"---does the sequence depend on w? If so, please make it clear in the statement of the theorem. Appendix: 254, Eq. (13): Inconsistent notation for inner products in the first term. 256, display: shouldn't the inequality be an equality instead? 268, display: what is "d\tau"?