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

Abstract

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. Focusing on the online bandit setting, we show that no bandit algorithm can guarantee a sublinear policy regret against an adaptive adversary with unbounded memory. 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 algorithm with a sublinear policy regret bound. We extend this result to other variants of regret, such as switching regret, internal regret, and swap regret.

Appears in Proceedings of the 29th International Conference on Machine Learning (ICML 2012)

Cited by in corpus (14)

• Multi-Player Bandits: The Adversarial Case
• Deterministic MDPs with Adversarial Rewards and Bandit Feedback
• Making Non-Stochastic Control (Almost) as Easy as Stochastic
• Decentralized Learning in Online Queuing Systems
• Survey of Self-Play in Reinforcement Learning
• Stochastic Bandits with Delay-Dependent Payoffs
• A survey on multi-player bandits
• Online Markov Decision Processes with Non-oblivious Strategic Adversary
• An Algorithm for Stochastic and Adversarial Bandits with Switching Costs
• On No-Sensing Adversarial Multi-player Multi-armed Bandits with Collision Communications
• Multi-token Markov Game with Switching Costs
• Distributed No-Regret Learning in Multi-Agent Systems
• Dynamic First Price Auctions Robust to Heterogeneous Buyers
• Online Learning with Composite Loss Functions