Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret

Understand

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 regret becomes inadequate if the adversary is allowed to adapt to the online algorithm's actions.
• We define the alternative notion of policy regret, which attempts to provide a more meaningful way to measure an online algorithm's performance against adaptive adversaries.