Source-linked AI summary
Bandits with Switching Costs: T^{2/3} Regret
Ofer Dekel, Jian Ding, Tomer Koren, Yuval Peres
TL;DR
The paper addresses the unresolved minimax regret of adversarial bandits with switching costs under bounded losses. It constructs stochastic loss sequences and proves a matching lower bound, establishing a T^2/3 minimax rate and a gap from full-feedback learning as T grows.
Problem
For bounded-loss bandits with switching costs, the minimax rate was unresolved, and results allowing losses to grow left open whether the rate reflected that enlarged range.
Source: §1 · p. 4Method
The authors apply Yao’s minimax principle, constructing a stochastic loss sequence that forces high expected regret for every deterministic player.
Source: §1.1 · p. 4Results
The minimax regret is eΘ(k^1/3T^2/3), and the paper reports a clear asymptotic difficulty gap from full-feedback learning as T grows.
Source: §1.1 · p. 4Takeaways & Limitations
The result provides the first reported clear gap, even for constant k, between bandit and full-feedback learning in their asymptotic dependence on T.
Source: §1.1 · p. 4The stated game uses an oblivious adversary and losses bounded in [0,1].
Source: §1 · p. 3
Abstract
from arXiv · showhide
We study the adversarial multi-armed bandit problem in a setting where the player incurs a unit cost each time he switches actions. We prove that the player's $T$-round minimax regret in this setting is $\widetilde{\Theta}(T^{2/3})$, thereby closing a fundamental gap in our understanding of learning with bandit feedback. In the corresponding full-information version of the problem, the minimax regret is known to grow at a much slower rate of $\Theta(\sqrt{T})$. The difference between these two rates provides the \emph{first} indication that learning with bandit feedback can be significantly harder than learning with full-information feedback (previous results only showed a different dependence on the number of actions, but not on $T$.) In addition to characterizing the inherent difficulty of the multi-armed bandit problem with switching costs, our results also resolve several other open problems in online learning. One direct implication is that learning with bandit feedback against bounded-memory adaptive adversaries has a minimax regret of $\widetilde{\Theta}(T^{2/3})$. Another implication is that the minimax regret of online learning in adversarial Markov decision processes (MDPs) is $\widetilde{\Theta}(T^{2/3})$. The key to all of our results is a new randomized construction of a multi-scale random walk, which is of independent interest and likely to prove useful in additional settings.
1 Introduction
The introduction frames minimax regret with switching costs as an unresolved question for bounded-loss bandits, where the earlier matching full-information result did not extend to bandit feedback. The paper proves a matching lower bound for bandits and identifies further implications for online learning.
1 Introduction
- Switching costs charge a penalty whenever the chosen action changes, a constraint motivated by settings such as investment advice, web applications, and production lines.Source: §1 · p. 2
1.1 Our Results
- Theorem 1 establishes regret of eΩ(k^1/3T^2/3) for bandit strategies when k ≤ T, matching the prior upper bound and yielding minimax regret eΘ(k^1/3T^2/3).The result is for the standard setup with losses bounded in [0, 1].Source: §1.1 · p. 4
- This is the first reported clear gap, even for constant k, between the asymptotic difficulty of online learning with bandit and full feedback as T grows.Source: §1.1 · p. 4
- The authors use Yao’s minimax principle to construct a stochastic loss sequence that yields high regret for every deterministic player.Source: §1.1 · p. 4
- The paper extends its lower bound to arbitrary switching costs and shows that some bandit algorithms with O(√T) regret without switching costs can be forced to make eΩ(T) switches.Source: §1.1 · p. 4
- Because the switching-cost problem is a special case of online MDP learning with adversarial rewards and bandit feedback, the paper also obtains an eΩ(T^2/3) minimax-regret lower bound for that problem.Source: §1.1 · p. 4
2 Constructing the Loss Sequence
The construction hides a uniformly selected best action behind a stochastic loss process, then bounds losses by projection. Its dependence structure limits how much the player learns without switching, linking identification of the best action to switching costs.
2 Constructing the Loss Sequence
- The adversary selects a uniformly random best action χ, gives it a fixed ε loss advantage, and projects all intermediate losses into [0, 1].Every other action receives the same intermediate loss, W_t + 1/2; χ receives W_t + 1/2 − ε.Source: §2 · p. 5
- Unlike an i.i.d. process, the chosen dependence structure controls information about χ through the player's switches, making identification require frequent, costly switching.With i.i.d. losses, estimating each action's mean to within ε/2 would require O(σ^2/ε^2) samples per action and at most k − 1 switches.Source: §2 · p. 6
3 The Stochastic Process
The section defines a Gaussian process through a parent function, whose structure controls its depth and width. The Multi-scale Random Walk balances these properties, with both bounded logarithmically in T.
3 The Stochastic Process
- W_t is defined recursively from its parent value and an independent zero-mean Gaussian; changing the parent function yields processes from i.i.d. Gaussians to a simple Gaussian random walk.The parent function must assign each round an earlier round or zero.Source: §3 · p. 6
3.1 Depth and Width
- Depth is the maximum number of ancestors, while width is the maximum cut size; the simple Gaussian random walk has width 1, whereas i.i.d. Gaussians have width T.Small width limits information extracted per switch, while low depth is needed to keep the process bounded without shrinking its variance so much that it fails to mask the loss gap.Source: §3.1 · pp. 6–7
3.2 The Multi-scale Random Walk
- The MRW uses a parent rule that clears the lowest-order 1 in t's binary representation, and its values can also be represented as sums along binary-tree paths.In the tree view, each W_t sums the Gaussian variables on the path from the root to its leaf.Source: §3.2 · p. 8, Figure 2 · p. 8
- ⌊log2 T⌋+1 bounds both the MRW's depth and width, giving the process the two logarithmic properties needed for the lower-bound construction.The construction is designed to be neither too deep nor too wide.Source: §3.2 · p. 8
4 Analysis
The analysis proves a minimax-regret lower bound by linking how well the player can identify a better action to how often they switch. The proof uses this tradeoff to establish the bound for deterministic and randomized players.
4.2 Regret Lower Bound
- For T ≥ max {k, 6}, every deterministic player against the constructed stochastic losses has expected regret at least k^1/3T^2/3/(100 log^2 T).The result extends to randomized players through the oblivious-adversary argument, yielding the main lower bound.Source: §4 · p. 9, §4.2 · p. 14
4.1 Distinguishability Requires Switching
- The analysis bounds how well the player can identify whether action i is better by the total variation distance between observation distributions, in terms of switches to or from i and process width.The distance measures identification ability; the width w(ρ) controls the bound.Source: §4.1 · pp. 9–10
- If the player switches frequently, switching costs drive regret; if not, the observation distributions become difficult to distinguish, leaving the better action unidentified.The proof combines this dilemma with a lower bound on hypothetical regret and controls the difference from actual regret.Source: §4.1 · p. 10, §4.2 · p. 12
5 Extensions and Implications
The extensions show that the lower-bound construction accommodates binary losses and arbitrary switching costs, yields a loss–switch tradeoff, and applies to adversarial MDP settings.
5.1 Binary losses
- Replacing each real-valued loss with a biased coin outcome preserves the construction’s expected ε-gap, while additional noise further obscures feedback.The argument for the player’s inability to identify the best action still applies.Source: §5.1 · p. 15
5.2 Arbitrary Switching Cost
- With switch cost c and T > c · max {k, 6}, every randomized bandit strategy faces regret R = eΩ(c^1/3k^1/3T^2/3).The bound is tight in T, k, and c up to poly-logarithmic factors, in light of Arora et al. (2012).Source: §5.2 · p. 15
5.3 Tradeoff between Loss and Switches
- An algorithm guaranteeing expected regret eO(T^α) without switching costs can be forced to make eΩ(T^2(1−α)) switches.For EXP3, the stated implication is eΩ(T) switches.Source: §5.3 · p. 16
5.4 Lower Bound for Online Adversarial Markov Decision Processes
- The switching-cost bandit lower bound applies to online adversarial deterministic MDPs, whose undiscounted minimax regret is eΘ(T^2/3); it gives an eΩ(T^2/3) lower bound for general adversarial MDPs with bandit feedback.The general setting allows stochastic state transitions.Source: §5.4 · p. 16
6 Summary
The paper establishes a T^2/3 minimax-regret rate for bandit learning with switching costs, contrasting it with full-information learning. It identifies exploration costs as the source of difficulty and draws implications for bounded-memory adversaries.
6 Summary
- The k-action bandit problem with switching costs has minimax regret eΘ(k^1/3T^2/3), making it strictly harder in T than the corresponding full-information experts problem.The paper identifies this as the first such separation in the dependence on T.Source: §6 · p. 17
- The difficulty stems from paying to explore the quality of different actions; the same lower-bound rate applies to bandit learning against bounded-memory adaptive adversaries.The stated lower bound matches the upper bounds of Arora et al. (2012).Source: §6 · p. 17
- The paper presents its multi-scale random walk construction as a tool that may prove useful in additional settings.Source: §6 · p. 17