Online calibrated forecasts: Memory efficiency versus universality for learning in games

Shie Mannor, Jeff S. Shamma, Gürdal Arslan

Research output: Contribution to journalArticlepeer-review

Abstract

We provide a simple learning process that enables an agent to forecast a sequence of outcomes. Our 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 memory requirements. We show that if the sequence of outcomes has certain properties-it has some internal (hidden) state that does not change too rapidly-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 a tracking forecast, while the other player 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 actual play of the other players. We further show that if both players use tracking forecast, then under certain conditions on the game matrix, convergence to a Nash equilibrium is possible with positive probability for a larger class of games than the class of games for which smooth fictitious play converges to a Nash equilibrium.

Original languageEnglish (US)
Pages (from-to)77-115
Number of pages39
JournalMachine Learning
Volume67
Issue number1-2
DOIs
StatePublished - May 2007
Externally publishedYes

Keywords

  • Calibration
  • Fictitious play
  • Forecasting
  • Learning in games
  • Prediction of universal sequences
  • Stochastic approximation
  • The ODE method

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Online calibrated forecasts: Memory efficiency versus universality for learning in games'. Together they form a unique fingerprint.

Cite this