Online Learning with Switching Costs and Other Adaptive Adversaries

Abstract

We study the power of different types of adaptive (nonoblivious) adversaries in the setting of prediction with expert advice, under both full-information and bandit feedback. We measure the player's performance using a new notion of regret, also known as policy regret, which better captures the adversary's adaptiveness to the player's behavior. In a setting where losses are allowed to drift, we characterize ---in a nearly complete manner--- the power of adaptive adversaries with bounded memories and switching costs. In particular, we show that with switching costs, the attainable rate with bandit feedback is $\tilde{\Theta }(T^{2/3})$. Interestingly, this rate is significantly worse than the $\Theta (\sqrt{T})$ rate attainable with switching costs in the full-information case. Via a novel reduction from experts to bandits, we also show that a bounded memory adversary can force $\tilde{\Theta }(T^{2/3})$ regret even in the full information case, proving that switching costs are easier to control than bounded memory adversaries. Our lower bounds rely on a new stochastic adversary strategy that generates loss processes with strong dependencies.

References in corpus (2)

• Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret
• On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization

Cited by in corpus (17)

• Batched bandit problems
• Batched Multi-armed Bandits Problem
• Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transition
• Diffusion Approximations for Thompson Sampling in the Small Gap Regime
• Improved Path-length Regret Bounds for Bandits
• Double Explore-then-Commit: Asymptotic Optimality and Beyond
• Collaborative Top Distribution Identifications with Limited Interaction
• Stochastic Bandits with Delay-Dependent Payoffs
• Revisiting Smoothed Online Learning
• Beyond Individual and Group Fairness
• Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design
• Gaussian Process Bandit Optimization with Few Batches
• Lazy OCO: Online Convex Optimization on a Switching Budget
• Competitive ratio versus regret minimization: achieving the best of both worlds
• Bandits with Feedback Graphs and Switching Costs
• Online Learning with Composite Loss Functions
• Bandit problems with fidelity rewards