Regret minimization under partial monitoring

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.