Timezone: »

Repeated Games against Budgeted Adversaries
Jacob D Abernethy · Manfred K. Warmuth

Mon Dec 06 12:00 AM -- 12:00 AM (PST) @

We study repeated zero-sum games against an adversary on a budget. Given that an adversary has some constraint on the sequence of actions that he plays, we consider what ought to be the player's best mixed strategy with knowledge of this budget. We show that, for a general class of normal-form games, the minimax strategy is indeed efficiently computable and relies on a "random playout" technique. We give three diverse applications of this algorithmic template: a cost-sensitive "Hedge" setting, a particular problem in Metrical Task Systems, and the design of combinatorial prediction markets.

Author Information

Jacob D Abernethy (University of Michigan)
Manfred K. Warmuth (Google Brain)

More from the Same Authors