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

本文研究了预测中的不同类型自适应（非固定的）对手的强度，使用新概念的策略遗憾去衡量玩家的表现，特别关注记忆和切换成本的自适应对手，具有均摊2/3次幂的速率且强度显著较弱。

具有切换成本和其他自适应对手的在线学习