Abstract | ||
---|---|---|
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 Ω(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. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1287/moor.1060.0206 | Mathematics of Operations Research |
Keywords | Field | DocType |
regret minimization,internal regret,hannan consistency,combined choice,hannan-consistent player,repeated games,randomized playing strategy,partial monitoring,game round,specific strategy,number n,convergence rate,imperfect monitoring,per-round regret,lower bound,pricing,feedback,repeated game,primary,yttrium,convergence | Convergence (routing),Mathematical economics,Mathematical optimization,Regret minimization,Regret,Upper and lower bounds,Infinity,Repeated game,Rate of convergence,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 3 | 0364-765X |
Citations | PageRank | References |
23 | 2.48 | 20 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Nicolò Cesa-Bianchi | 1 | 4609 | 590.83 |
GáBor Lugosi | 2 | 1092 | 195.02 |
Gilles Stoltz | 3 | 351 | 31.53 |