Timezone: »

 
Poster
Online Learning in Periodic Zero-Sum Games
Tanner Fiez · Ryann Sim · Stratis Skoulakis · Georgios Piliouras · Lillian Ratliff

Wed Dec 08 04:30 PM -- 06:00 PM (PST) @
in Poster Session 4 »

A seminal result in game theory is von Neumann's minmax theorem, which states that zero-sum games admit an essentially unique equilibrium solution. Classical learning results build on this theorem to show that online no-regret dynamics converge to an equilibrium in a time-average sense in zero-sum games. In the past several years, a key research direction has focused on characterizing the transient behavior of such dynamics. General results in this direction show that broad classes of online learning dynamics are cyclic, and formally Poincar\'{e} recurrent, in zero-sum games. We analyze the robustness of these online learning behaviors in the case of periodic zero-sum games with a time-invariant equilibrium. This model generalizes the usual repeated game formulation while also being a realistic and natural model of a repeated competition between players that depends on exogenous environmental variations such as time-of-day effects, week-to-week trends, and seasonality. Interestingly, time-average convergence may fail even in the simplest such settings, in spite of the equilibrium being fixed. In contrast, using novel analysis methods, we show that Poincar\'{e} recurrence provably generalizes despite the complex, non-autonomous nature of these dynamical systems.

Keywords: Theory · Robustness · Online Learning

Author Information

Tanner Fiez (University of Washington)
Ryann Sim (Singapore University of Technology and Design)
Stratis Skoulakis (Singapore University of Technology and Design)
Georgios Piliouras (Singapore University of Technology and Design)
Lillian Ratliff (University of Washington)

More from the Same Authors