Dynamic Regret in Online Convex Optimization with Indicator Switching Costs

We study dynamic regret in online convex optimization with an indicator switching cost: a fixed penalty incurred whenever two consecutive decisions differ. This captures startup overheads such as server activation, model deployment, and cache updates, and on a bounded domain it recovers norm-based movement costs as a special case. Existing guarantees for indicator costs handle only static comparators. We show that a direct extension of these techniques to dynamic regret provably fails, motivating a different approach. We propose a meta-learning framework: a set of randomized lazy FTRL base learners restarted at dyadic time scales, aggregated by a movement-aware master that mixes their proposal densities and samples actions via maximal coupling of consecutive mixtures. The resulting algorithm satisfies, in expectation, R1T ≤ tildeO(min√T(ST+1),T2/3(PT+1)1/3), where R1T is the dynamic regret plus the cumulative indicator switching cost, ST counts comparator switches, and PT is the comparator path length. The bound holds simultaneously for all sequences and requires no prior knowledge of ST or PT: it is minimax-optimal (up to logarithmic factors) for tracking piecewise-constant comparators, and also captures frequently moving comparators with small total path length.