Competing Against Equilibria in Zero-Sum Games with Evolving Payoffs
  We study the problem of repeated play in a zero-sum game in which the payoff
matrix may change, in a possibly adversarial fashion, on each round; we call
these Online Matrix Games. Finding the Nash Equilibrium (NE) of a two player
zero-sum game is core to many problems in statistics, optimization, and
economics, and for a fixed game matrix this can be easily reduced to solving a
linear program. But when the payoff matrix evolves over time our goal is to
find a sequential algorithm that can compete with, in a certain sense, the NE
of the long-term-averaged payoff matrix. We design an algorithm with small NE
regret--that is, we ensure that the long-term payoff of both players is close
to minimax optimum in hindsight. Our algorithm achieves near-optimal dependence
with respect to the number of rounds and depends poly-logarithmically on the
number of available actions of the players. Additionally, we show that the
naive reduction, where each player simply minimizes its own regret, fails to
achieve the stated objective regardless of which algorithm is used. We also
consider the so-called bandit setting, where the feedback is significantly
limited, and we provide an algorithm with small NE regret using one-point
estimates of each payoff matrix.
