Abstract: We revisit one of most classic questions in game theory and online learning. How do standard learning dynamics such as Multiplicative Weights Update or Gradient Descent behave in zero-sum games? The standard textbook answer to this question is that these dynamics "converge" in a time-average sense to Nash equilibria. We will provide a tutorial on some recent results that analyze the day-to-day behavior and show how dynamics in zero-sum games have formal connections to the physics of closed systems. As in the case of e.g. pendulums, the time-average position and speed of these systems may agree with their equilibrium values but these time-averages do not tell the full story.

The continuous-time analogues of these dynamics (e.g. replicator dynamics/MWU) are Poincaré recurrent. Informally, the trajectories are "cycles" of constant distance from the Nash equilibrium which lies at the center of the "cycle". In fact, the dynamics conserve a hidden energy function that remains constant on all trajectories. These results extend in a natural way to multiplayer generalizations of zero-sum games. In discrete-time, the classical online algorithms such as MWU, move tangentially to these cycles and as a result they diverge chaotically away from Nash equilibria, contradicting the paradigm of zero-sum games as an archetype of game theoretic stability. Multiple new questions and directions emerge.

Bio: Dr. Piliouras is an Assistant Professor at the Singapore University of Technology and Design (SUTD). He received his PhD in Computer Science from Cornell University in 2010. He has held postdoc positions at the Georgia Institute of Technology (GaTech, ECE Dept.) and California Institute of Technology (Caltech, Dept. of Computing and Mathematical Sciences). He has held visiting positions at UC Berkeley and DeepMind and is a collaborator of the Ethereum Foundation. He is the recipient of a Singapore NRF Fellowship (2018) and a Simons/UC Berkeley Fellowship (2015).

Abstract: One of the biggest promises of machine learning is the automation of decision making in many application domains such as business, healthcare and law. However, most of decision making involves making interventions and understanding the effects of such interventions. This requires understanding causal relationships among the variables in your data, which is at odds with most of machine learning techniques, which primarily target the identification of correlations and produce purely predictive, as opposed to causal models. Techniques from econometrics and causal inference can help mitigate this problem. I will survey several such techniques such as, inverse propensity scoring, double machine learning, instrumental variables, regression discontinuity designs and synthetic controls. I will outline how such techniques can be blended with machine learning approaches so as to remove the limited modeling ability of traditional econometrics and get the best of both worlds.

Bio: Vasilis Syrgkanis is a Principal Researcher at Microsoft Research, New England, where he is co-leading the project on Automated Learning and Intelligence for Causation and Economics (ALICE). He received his Ph.D. in Computer Science from Cornell University in 2014, under the supervision of Prof. Eva Tardos and spent two years in Microsoft Research, New York as a postdoctoral researcher. His research addresses problems at the intersection of theoretical computer science, machine learning and economics. His work received best paper awards at the 2015 ACM Conference on Economics and Computation (EC’15), the 2015 Annual Conference on Neural Information Processing Systems (NIPS’15) and the Conference on Learning Theory (COLT’19).