Online Learning with Switching Costs and Other Adaptive Adversaries

Nicolo Cesa-Bianchi; Ofer Dekel; Ohad Shamir

Source-linked AI summary

Online Learning with Switching Costs and Other Adaptive Adversaries

Nicolo Cesa-Bianchi, Ofer Dekel, Ohad Shamir

arXiv:1302.4387v2Feb 18, 2013cs.LGstat.ML

TL;DR

The paper asks how regret behaves against adaptive adversaries, for which the usual regret measure is inadequate. It establishes upper and lower bounds for constrained adversaries under full-information and bandit feedback. The results show that switching costs are harder with bandit feedback, while bounded-memory adversaries are harder than switching costs under full information.

Problem
The usual regret definition is inadequate for measuring performance against adaptive adversaries, so the paper asks how regret scales against weaker, constrained adversaries.
Source: §1 · pp. 2–3
Method
The paper proves upper and lower bounds on policy regret across adversary types and both feedback models.
Source: §1.2 · p. 4, §4 · p. 8
Results
Switching costs are harder with bandit feedback than full information, and bounded-memory adversaries are harder than switching costs under full information.
Source: §1.2 · p. 4, §4 · p. 8
Takeaways & Limitations
The results distinguish the difficulty of controlling switching costs from that of handling general bounded-memory adversaries.
Source: §4 · p. 8
The studied adversaries are constrained: switching-cost losses add a charge for changing actions, while bounded-memory losses depend on the player’s m most recent actions.
Source: §1 · pp. 2–3

Abstract

from arXiv · show

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 $\widetilde{\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 $\widetilde{\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.

1 Introduction

The paper studies regret against adaptive adversaries under full-information and bandit feedback, using a regret notion suited to losses that depend on the player’s past actions. It derives bounds for constrained adversaries, including switching costs and bounded memory, and compares how feedback and adversary strength affect attainable regret.

1 Introduction

The paper evaluates adaptive play using regret that compares cumulative realized loss with the best fixed action in hindsight.The authors note that the more common regret definition is inadequate for measuring performance against adaptive adversaries.Source: §1 · p. 2

1.1 The Current State of the Art

Earlier work focused mostly on oblivious adversaries, while prior bounded-memory results gave O(T^2/3) regret bounds.The paper seeks sublinear expected regret, since arbitrary adaptive adversaries can force linear regret.Source: §1 · p. 2, §1.1 · p. 3

1.2 Our Contribution

For switching costs with bandit feedback and stochastic i.i.d. losses, a distribution-free bound of O(√(T log log log T)) is attainable with O(log log T) switches.This result is stated for finite action sets.Source: §1.2 · p. 4
The paper’s lower bounds match existing upper bounds up to logarithmic factors in all but one of the settings considered.The remaining gap is for a unit-memory adaptive adversary under full-information feedback.Source: §1.2 · p. 4
With full information, switching costs permit Θ(√T) regret, while a bounded-memory adversary can force Ω(T^2/3) regret.The paper concludes that controlling switching costs is easier than handling a general bounded-memory adversary.Source: §1.2 · pp. 4–5

2 Lower Bounds

Section 2 proves regret lower bounds for constrained adversaries. It establishes a bound for bandit feedback with switching costs and extends the result to full-information feedback with bounded memory.

2.1 Ω(T 2/3) with Switching Costs and Bandit Feedback

Ω(T^2/3) regret is forced against a switching-cost adversary with bandit feedback, and a deterministic loss sequence with bounded drift attains the lower bound.The proof first uses a randomized loss process, then shows a deterministic sequence with bounded drift must exist.Source: §2.1 · pp. 5–6
Against this randomized loss sequence, any player has expected regret Ω(T^2/3): identifying the better action requires Ω(T^2/3) switches; with fewer, expected regret is Ω(T^-1/3) per round.While staying on one action, the player observes only a random walk and gets no further information; the gap between the losses each round is T^-1/3.Source: §2.1 · p. 6

2.2 Ω(T 2/3) with Bounded Memory and Full-Information Feedback

With full-information feedback, a bounded-memory adversary with memory size 2 can force Ω(T^2/3) regret using losses with range bounded by C = 2 and bounded drift.The reduction makes each round’s loss equal to the previous round’s loss in a bandit game with switching costs, for the same action sequence.Source: §2.2 · p. 6

3 Upper Bounds

The section extends regret upper bounds to losses with bounded range and drift, then gives reductions and algorithms for switching-cost and bounded-memory settings. The bounded-memory bandit result is an expected regret guarantee of eO(T^2/3).

3 Upper Bounds

Known upper bounds extend from bounded losses to losses with bounded range and bounded drift; remaining bounds follow by weakening the adversary or improving feedback.The section identifies these as extensions of known results and notes that some other bounds are trivial or follow by monotonicity.Source: §3 · p. 7

3.1 O(T) with Switching Costs and Full-Information Feedback

For switching costs with full-information feedback, the section extends the Follow the Lazy Leader guarantee to losses with bounded range and arbitrary drift.A reduction forms modified losses for FLL; the stated guarantee applies to the original loss sequence.Source: §3.1 · p. 7
For oblivious switching-cost losses with bandit feedback, a reduction based on modified losses yields a regret guarantee under bounded range and drift.The construction uses a fixed horizon and feeds losses computable from bandit feedback to Exp3.P.Source: T) with an Oblivious Adversary and… · p. 7

O(T 2/3) with Bounded Memory and Bandit Feedback

With bounded memory, bounded range, and bounded drift, the proposed strategy attains eO(T^2/3) expected regret in the bandit setting.The strategy uses exploration intervals for each action and runs Hedge across epochs.Source: O(T 2/3) with Bounded Memory and… · p. 8

4 Discussion

The discussion identifies an unresolved bounded-loss assumption and open questions about regret guarantees. It also points to other adversary classes, including deterministically adaptive adversaries.

4 Discussion

The results require relaxing the standard [0, 1] loss bound; proving similar lower bounds under that standard assumption remains open.The paper also asks whether expected regret bounds can be strengthened to high-probability bounds or generalized to shifting and swap regret.Source: §4 · p. 8
The attainable regret for oblivious adversaries with delayed feedback, especially under bandit feedback, is unclear in the discussion.The paper also identifies deterministically adaptive adversaries as an interesting class for future study.Source: §4 · pp. 8–9
Deterministically adaptive adversaries react to actions in a known deterministic way rather than through secret malicious adaptation.The paper notes that many real-world online prediction scenarios are deterministically adaptive.Source: §4 · p. 9

A Distribution-free regret bound for bandits with switching costs

This appendix gives a staged strategy for bandits with switching costs and an i.i.d. oblivious adversary. Its high-probability guarantee assumes subgaussian loss marginals.

A Distribution-free regret bound for bandits with switching costs

A deterministic strategy has a high-probability regret guarantee when each action's loss marginal is subgaussian.The theorem considers a finite action set and i.i.d. oblivious adversaries with switching costs.Source: A Distribution-free regret bound for… · p. 11
The strategy plays active actions in round-robin stages, estimates their losses from sample means, and narrows the active set across stages.The stage lengths grow with the known horizon, while the active sets are nested.Source: A Distribution-free regret bound for… · p. 11
The analysis establishes simultaneous high-probability control of the staged empirical estimates, supporting the active-action selection guarantee.The proof uses stagewise bounds and a union bound over stages.Source: A Distribution-free regret bound for… · pp. 11–12

B Proof of Thm. 1

The proof constructs a stochastic adversary with a small loss gap, first obtaining a regret lower bound and then extracting a deterministic strategy with bounded drift. The argument uses relative entropy to control how well the player can distinguish which action is better.

B Proof of Thm. 1

The proof bounds the information difference between the two adversary distributions by analyzing the loss observed after each action switch.When the player switches, the conditional Gaussian means differ by 2ε, giving relative entropy 2ε^2; without a switch, it is zero.Source: B Proof of Thm. 1 · p. 13
With ε=T^-1/3, the randomized adversary forces expected regret of at least T^2/3/10 against any deterministic player.The construction draws a hidden sign Z uniformly and uses independent standard Gaussian noise with the two actions separated by ε.Source: B Proof of Thm. 1 · pp. 13–14
To obtain the deterministic-player argument for randomized players, the proof caps switches at floor(T^2/3), which bounds regret by 2T^2/3 for every adversary realization.The capped strategy freezes on its current action after reaching the switch limit.Source: B Proof of Thm. 1 · p. 15
A randomized adversary yields expected regret of at least T^2/3/40 for some deterministic strategy while keeping drift at most 3 log(t)+16 for all t.The proof obtains both properties by showing that the high-regret and bounded-drift events have a nonempty intersection.Source: B Proof of Thm. 1 · p. 16

C Proof of Thm. 2

The proof constructs a randomized memory-2 adversary from a memory-1 strategy, then uses a reduction to derive a lower bound for players’ regret. It converts the randomized construction into a deterministic adversary with bounded loss drift.

C Proof of Thm. 2

The proof constructs a memory-2 randomized adversary from a memory-1 strategy by setting the first loss to zero and defining later losses from the memory-1 strategy.The construction is used for a game of T + 1 rounds.Source: C Proof of Thm. 2 · p. 16
The constructed player strategy can be simulated in the bandit-with-switching-costs setting using past actions and observable losses.The proof argues that the relevant loss quantities are observable in the bandit setting.Source: C Proof of Thm. 2 · p. 17
A contradiction with Eq. (17) establishes an expected-regret lower bound for the randomized adversary construction.The proof then substitutes T for T + 1 to express the bound for a T-round game.Source: C Proof of Thm. 2 · p. 17
The proof transfers the expected-regret guarantee to a deterministic adversary whose losses have bounded drift.It uses the intersection of a regret event and an event bounding drift by 3 log(t) + 18.Source: C Proof of Thm. 2 · p. 17

D Proofs of Upper Bounds

The upper-bound proofs use standard regret analyses where their loss assumptions permit them, and mini-batched Hedge with exploration to obtain oblivious loss estimates. The exploration adds per-epoch cost, and choosing the number of epochs completes the stated bound.

D Proofs of Upper Bounds

With switching costs, each loss is an oblivious loss plus an indicator for changing actions; the range of the underlying loss is reduced accordingly.The proof states that if the total loss range has size C, the underlying loss range has size C − 1.Source: D Proofs of Upper Bounds · p. 17
The proof invokes Exp3.P’s standard regret bound for losses that are not oblivious, and states that its analysis holds for the specified transformed losses in [0, 1].The bounded-range and drift assumptions are also used to place the transformed losses in [0, 1].Source: D Proofs of Upper Bounds · p. 18
Mini-batched Hedge plays one action throughout each epoch, with epochs of length T/J at least 2K(m + 1), and receives loss estimates at epoch end.The estimate randomness is independent of Hedge’s choice of epoch action.Source: D Proofs of Upper Bounds · pp. 18–19
For each action, separated exploration steps play a reference action and then that action; the two observed losses form an estimate.The exploration points are sampled with uniform marginals using a circular arrangement to avoid border effects.Source: D Proofs of Upper Bounds · p. 19
The resulting estimates do not depend on Hedge’s current or past actions, so Hedge is run on oblivious losses and its standard regret bound applies.The proof identifies the estimate as valid for each action.Source: D Proofs of Upper Bounds · p. 19
Choosing J of order T^2/3 completes the regret bound after accounting for exploration cost of 2(m + 1)CK per epoch.The proof adds this exploration cost to the regret bound before choosing J.Source: D Proofs of Upper Bounds · p. 20