|
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. |
