Online Calibrated Forecasts: Efficiency versus Universality for Learning in Games

Abstract: We present a simple learning process that enables an agent to forecast a sequence of outcomes. The forecasting scheme, termed tracking forecast, is based on tracking the past observations while emphasizing recent outcomes. As opposed to other forecasting schemes, we sacrifice universality in favor of a significantly reduced computational burden. We show that if the sequence of outcomes has certain properties---it has some internal (hidden) state that does not change too fast---then the tracking forecast is "weakly calibrated" so that the forecast appears to be correct most of the time. For binary outcomes, this result holds without any internal state assumptions. We consider learning in a repeated strategic game where each player attempts to compute some forecast of the opponent actions and plays a best response to it. We show that if one of the players uses tracking forecast, while the other players uses a standard learning algorithm (such as exponential regret matching or smooth fictitious play), then the player using the tracking forecast obtains the best response to the acttual play of the other players. We further show that if both players use a tracking forecast, then under certain conditions on the game matrix, a convergence to a Nash equilibrium is possible with positive probability for a larger class of games than smooth fictitious play.

This is joint work with S. Mannor and G. Arslan

Paper: Click to view.


Biography: Jeff Shamma received a BS from the Georgia Institute of Technology in 1983 and a PhD from the Massachusetts Institute of Technology in 1988, both in Mechanical Engineering. He has held faculty positions at the University of Minnesota, Minneapolis, the University of Texas at Austin, and University of California, Los Angeles. Jeff returned to Georgia Tech in 2007, where he is a Professor of Electrical and Computer Engineering and Julian T. Hightower Chair of Systems and Controls.

Jeff Shamma