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 $\t\theta(T^{2/3})$, thereby closing a fundamental gap in our understanding of learning with bandit feedback. Indeed, 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 one of the first concrete indications that learning with bandit feedback can be significantly harder than learning with full-information feedback (previous results only showed a different dependence on constants). One implication of our result is a new $\t\Omega(T^{2/3})$ lower bound on the (nondiscounted) minimax regret in the adversarial online MDP problem. Our constructions build on a novel stochastic process with a controllable dependency structure that may be of independent interest.

本文研究的是带有动作切换代价的敌对多臂赌博机问题，证明了在该问题下玩家T回合的最小極大后悔度为~Θ(T^2/3)，并研究了其他在线学习领域的开放问题，结果得到了一个多尺度随机游走的新随机化结构，该结构对如此困难的学习问题证明可能会有所帮助。

带切换成本的赌博机：T ^ {2/3} 遗憾