Online Calibrated Forecasts. Efficiency versus Universality for Learning in Games

Professor Jeff Shamma

University of California - Los Angeles

Mechanical and Aerospace Engineering Department

Abstract -- We provide 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 play 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.

Bio: Jeff Shamma is a Professor of Mechanical and Aerospace Engineering at UCLA. He received a PhD in Systems Science and Engineering in 1988 from the Massachusetts Institute of Technology, Department of Mechanical Engineering. He previously held faculty positions at the University of Minnesota, Minneapolis, and the University of Texas, Austin, before joining UCLA in 1999. He is a past recipient of the American Automatic Control Council Eckman Award and a Fellow of The IEEE. His research interest is feedback control and systems theory.

Friday, February 17, 2006

3:30 – 4:30 p.m.

1500 EECS