Regret minimization under partial monitoring

• 成果类型: Article
• 署名作者: Cesa-Bianchi, Nicolo; Lugosi, Gabor; Stoltz, Gilles
• 署名单位: University of Milan; Pompeu Fabra University; ICREA; Pompeu Fabra University; Universite PSL; Ecole Normale Superieure (ENS); Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1060.0206
• 发表日期: 2006
• 页码: 562-580
• 关键词: universal prediction; minimizing regret; online

摘要

We consider repeated games in which the player, instead of observing the action chosen by the opponent in each game round, receives a feedback generated by the combined choice of the two players. We study Hannan-consistent players for these games, that is, randomized playing strategies whose per-round regret vanishes with probability one as the number n of game rounds goes to infinity. We prove a general lower bound of Omega(n(-1/3)) for the convergence rate of the regret, and exhibit a specific strategy that attains this rate for any game for which a Hannan-consistent player exists.