Detailed Instructions: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
Problem:<lb>We study a general version of the adversarial online learning problem. We are given a decision<lb>set X in a reflexive Banach space X and a sequence of reward vectors in the dual space of X . At<lb>each iteration, we choose an action from X , based on the observed sequence of previous rewards.<lb>Our goal is to minimize regret, defined as the gap between the realized reward and the reward<lb>of the best fixed action in hindsight. Using results from infinite dimensional convex analysis, we<lb>generalize the method of Dual Averaging (or Follow the Regularized Leader) to our setting and<lb>obtain general upper bounds on the worst-case regret that subsume a wide range of results from the<lb>literature. Under the assumption of uniformly continuous rewards, we obtain explicit anytime regret<lb>bounds in a setting where the decision set is the set of probability distributions on a compact metric<lb>space S whose Radon-Nikodym derivatives are elements of L(S) for some p > 1. Importantly,<lb>we make no convexity assumptions on either the set S or the reward functions. We also prove<lb>a general lower bound on the worst-case regret for any online algorithm. We then apply these<lb>results to the problem of learning in repeated continuous two-player zero-sum games, in which<lb>players' strategy sets are compact metric spaces. In doing so, we first prove that if both players<lb>play a Hannan-consistent strategy, then with probability 1 the empirical distributions of play weakly<lb>converge to the set of Nash equilibria of the game. We then show that, under mild assumptions,<lb>Dual Averaging on the (infinite-dimensional) space of probability distributions indeed achieves<lb>Hannan-consistency. Finally, we illustrate our results through numerical examples.<lb>
Solution:
Minimizing Regret on Reflexive Banach Spaces and Learning Nash Equilibria in Continuous Zero-Sum Games