Online bandit learning against an adaptive adversary: from regret to policy regret

Online learning algorithms are designed to learn even when their input is generated by an adversary. The widely-accepted formal definition of an online algorithm’s ability to learn is the game-theoretic notion of regret. We argue that the standard definition of re-gret becomes inadequate if the adversary is allowed to adapt to the online algorithm’s ac-tions. We define the alternative notion of pol-icy regret, which attempts to provide a more meaningful way to measure an online algo-rithm’s performance against adaptive adver-saries. Focusing on the online bandit set-ting, we show that no bandit algorithm can guarantee a sublinear policy regret against an adaptive adversary with unbounded mem-ory. On the other hand, if the adversary’s memory is bounded, we present a general technique that converts any bandit algorithm with a sublinear regret bound into an algo-rithm with a sublinear policy regret bound. We extend this result to other variants of re-gret, such as switching regret, internal regret, and swap regret. 1