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.

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

Cited by in corpus (27)

• Online Learning: A Modern Introduction Using Convex Optimization
• Learning Prices for Repeated Auctions with Strategic Buyers
• Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits
• Online Learning with Switching Costs and Other Adaptive Adversaries
• Logarithmic Regret for Adversarial Online Control
• Multi-Player Bandits: The Adversarial Case
• Deterministic MDPs with Adversarial Rewards and Bandit Feedback
• Non-stationary Online Learning with Memory and Non-stochastic Control
• Locally Differentially Private (Contextual) Bandits Learning
• Proximal Online Gradient is Optimum for Dynamic Regret
• Making Non-Stochastic Control (Almost) as Easy as Stochastic
• Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transition
• 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
• Multi-Armed Bandits for Correlated Markovian Environments with Smoothed Reward Feedback
• An Algorithm for Stochastic and Adversarial Bandits with Switching Costs
• On No-Sensing Adversarial Multi-player Multi-armed Bandits with Collision Communications
• Online Markov Decision Processes with Non-oblivious Strategic Adversary
• Lazy OCO: Online Convex Optimization on a Switching Budget
• Bandits with Feedback Graphs and Switching Costs
• Distributed No-Regret Learning in Multi-Agent Systems
• How to gamble with non-stationary $\mathcal{X}$-armed bandits and have no regrets
• Multi-token Markov Game with Switching Costs
• Dynamic First Price Auctions Robust to Heterogeneous Buyers
• Online Learning with Composite Loss Functions