Adaptive game playing using multiplicative weights

摘要: Abstract We present a simple algorithm for playing repeated game. show that player using this suffers average loss is guaranteed to come close the minimum achievable by any fixed strategy. Our bounds are nonasymptotic and hold opponent. The algorithm, which uses multiplicative-weight methods of Littlestone Warmuth, analyzed Kullback–Liebler divergence. This analysis yields new, proof min–max theorem, as well provable method approximately solving A variant our game-playing proved be optimal in very strong sense. Journal Economic Literature Classification Numbers: C44, C70, D83.