Minimax Rates for Online Convex Optimization with Limited Decision Changes

Abstract

Online convex optimization has rececently received substantial attention due to its elegant theory and many practical applications. It is well-known that when the player receives either fullinformation feedback or partial-information (bandit) feedback, the minimax rate for expected regret is Θ(√T), where T is the number of iterations in the game. However, real world constraints often limit the player from making many decision changes. We analyze the setting where the player is limited to S ≤ T switches between actions, and give a complete characterization of the minimax rate. When the player receives bandit feedback, we prove the minimax rate is Θ( ˜ T/√S) up to a logarithmic factor in T. When the player receives full-information feedback, the minimax rate is known to be Θ(√T) for S = Ω(√T); we complete the story by proving the minimax rate is Θ( TS) for S = O(√T). Our lower bound proofs are information theoretic in nature, whereas our upper bounds are shown by presenting algorithms which provably achieve the optimal minimax rate.