Online Learning with Switching Costs and Other Adaptive Adversaries

By Nicolò Cesa-Bianchi, Ofer Dekel, Ohad Shamir. 2013

133 citations recorded by the source corpus.

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 Θ(T2/3). Interestingly, this rate is significantly worse than the Θ(√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 ****Θ(T2/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.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Beyond Individual and Group Fairness (2020, methodology): “…an instance of the stochastic multi-armed bandit problem with switching costs, and arms corresponding to the states in the MDP, existing algorithms [Cesa-Bianchi et al., 2013, Simchi-Levi and Xu, 2019] achieving Õ( √ T ) have time complexity that depends on the number of arms which in our case is…”
Dealing with Non-Stationarity in MARL via Trust-Region Decomposition (2021, background): “Switching cost is a standard notion in the literature to measure the changing behavior of an single-agent RL algorithm (Cesa-Bianchi et al., 2013; Bai et al., 2019; Gao et al., 2021).”
L G ] 2 6 M ay 2 01 9 Phase Transitions and Cyclic Phenomena in Bandits with Switching Constraints (2019, methodology): “In particular, while the algorithm in Cesa-Bianchi et al. (2013) developed for the “switching penalty” model can achieve Õ( √ T ) (distribution-free) regret with O(log logT ) switches, if the learner wants a policy that always incurs finite switching cost independent of T , then prior literature…”
Minimax Bounds on Stochastic Batched Convex Optimization (2018, background): “More recent work in the statistical learning theory literature focuses on so-called “switching bandits,” in which an algorithm plays a certain strategy and pays a penalty for switching between strategies (Cesa-Bianchi et al., 2013a,b).”
Contextual Slate GLM Bandits with Limited Adaptivity (2026, unknown): “In the multi-armed bandit setting, several works have studied the advantages of batching [CBDS13, PRCS15, GHRZ19], Subsequently, [RYZ21] proposed batched algorithms for contextual linear bandits, by introducing distributional optimal designs, and using them to guide and determine policy updates.”