Adversarial Combinatorial Bandits with Switching Costs
Yanyan Dong Vincent Y. F. Tan
We study the problem of adversarial combinatorial bandit with a switching
cost $\lambda$ for a switch of each selected arm in each round, considering
both the bandit feedback and semi-bandit feedback settings. In the oblivious
adversarial case with $K$ base arms and time horizon $T$, we derive lower
bounds for the minimax regret and design algorithms to approach them. To prove
these lower bounds, we design stochastic loss sequences for both feedback
settings, building on an idea from previous work in Dekel et al. (2014). The
lower bound for bandit feedback is $ \tilde{\Omega}\big( (\lambda
K)^{\frac{1}{3}} (TI)^{\frac{2}{3}}\big)$ while that for semi-bandit feedback
is $ \tilde{\Omega}\big( (\lambda K I)^{\frac{1}{3}} T^{\frac{2}{3}}\big)$
where $I$ is the number of base arms in the combinatorial arm played in each
round. To approach these lower bounds, we design algorithms that operate in
batches by dividing the time horizon into batches to restrict the number of
switches between actions. For the bandit feedback setting, where only the total
loss of the combinatorial arm is observed, we introduce the Batched-Exp2
algorithm which achieves a regret upper bound of $\tilde{O}\big((\lambda
K)^{\frac{1}{3}}T^{\frac{2}{3}}I^{\frac{4}{3}}\big)$ as $T$ tends to infinity.
In the semi-bandit feedback setting, where all losses for the combinatorial arm
are observed, we propose the Batched-BROAD algorithm which achieves a regret
upper bound of $\tilde{O}\big( (\lambda K)^{\frac{1}{3}}
(TI)^{\frac{2}{3}}\big)$.