Blog
About

25
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Minimizing Regret on Reflexive Banach Spaces and Learning Nash Equilibria in Continuous Zero-Sum Games

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We study a general version of the adversarial online learning problem. We are given a decision set \(\mathcal{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 \(\mathcal{X}\), based on the observed sequence of previous rewards. Our goal is to minimize regret, defined as the gap between the realized reward and the reward of the best fixed action in hindsight. Using results from infinite dimensional convex analysis, we generalize the method of Dual Averaging (or Follow the Regularized Leader) to our setting and obtain general upper bounds on the worst-case regret that subsume a wide range of results from the literature. Under the assumption of uniformly continuous rewards, we obtain explicit anytime regret bounds in a setting where the decision set is the set of probability distributions on a compact metric space \(S\) whose Radon-Nikodym derivatives are elements of \(L^p(S)\) for some \(p > 1\). Importantly, we make no convexity assumptions on either the set \(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 continuous two-player zero-sum games, in which players' strategy sets are 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. Finally, we illustrate our results through numerical examples.

          Related collections

          Author and article information

          Journal
          2016-06-03
          Article
          1606.01261

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          Custom metadata
          cs.LG

          Artificial intelligence

          Comments

          Comment on this article