Timezone: »

 
Poster
Online Learning with Switching Costs and Other Adaptive Adversaries
Nicolò Cesa-Bianchi · Ofer Dekel · Ohad Shamir

Sun Dec 08 02:00 PM -- 06:00 PM (PST) @ Harrah's Special Events Center, 2nd Floor
in Poster Session »
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 $T^{2/3}$. Interestingly, this rate is significantly worse than the $\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 $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.
[ PDF] 

Author Information

Nicolò Cesa-Bianchi (Università degli Studi di Milano, Italy)
Ofer Dekel (Microsoft Research)
Ohad Shamir (Weizmann Institute of Science)

More from the Same Authors