Adaptive game playing using multiplicative weights
成果类型：
Article
署名作者：
Freund, Y; Schapire, RE
署名单位：
AT&T
刊物名称：
GAMES AND ECONOMIC BEHAVIOR
ISSN/ISSBN：
0899-8256
DOI：
10.1006/game.1999.0738
发表日期：
1999
页码：
79-103
关键词：
摘要：
We present a simple algorithm for playing a repeated game. We show that a player using this algorithm suffers average loss that is guaranteed to come close to the minimum loss achievable by any fixed strategy. Our bounds are nonasymptotic and hold for any opponent. The algorithm, which uses the multiplicative-weight methods of Littlestone and Warmuth, is analyzed using the Kullback-Liebler divergence. This analysis yields a new, simple proof of the min-max theorem, as well as a provable method of approximately solving a game. A variant of our game-playing algorithm is proved to be optimal in a very strong sense. Journal of Economic Literature Classification Numbers: C44, C70, D83. (C) 1999 Academic Press.
来源URL：