Online Learning with Switching Costs and Other Adaptive Adversaries
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 � Θ(T 2/3 ). Interestingly, this rate is significantly worse than the Θ( √ 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 � Θ(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.
This paper studies the problem of prediction with 
      expert advice and finds matching upper and lower bounds on regret in terms 
      of T (of T^{2/3}) in a number of settings: bandit feedback with 
      adversaries of the form (bounded memory, size-1 memory, and imposing 
      switching costs) and full-information feedback with adversaries with 
      bounded memory. This is a fundamental question, and it's nice to 
      see progress here. There are a couple of unusual things to note 
      about the setting: - The definition of expected regret is not the 
      usual one. Traditionally, one looks at the expected difference between the 
      costs of the selected actions and the performance of the best fixed action 
      in hindsight (meaning given the actual history of play). Instead, they 
      look at the expected value of the difference between the actual 
      performance and that of the best fixed action (not taking the actual 
      history into account, but rather assuming that the fixed action had been 
      played all along). This difference is salient because they consider 
      adaptive adversaries who e.g. take into account a limited history when 
      selecting their cost functions. The regret definition used here ("policy 
      regret") seems to be the right one for these settings, and the paper 
      mostly does a good job of making this distinction. But since this is a 
      potential source of confusion, I would have preferred if the paper had 
      been more explicit with references to the cases where similar results are 
      known under the standard expected regret. Also, it's strange that Table 1 
      summarizing results doesn't provide standard references for the results in 
      prior work. - The results require a weakening of the usual assumption 
      of bounded loss values (and hence the reproving of the corresponding upper 
      bounds, which the paper does do). I still think the results are 
      interesting, but of course it would be nicer to have results in the 
      standard model. The paper gives a thorough treatment, with nice 
      proof sketches of the main results in the main body of the paper, and a 
      nice discussion of open questions.