Online Submodular Minimization with Switching Costs

We consider online submodular minimization with switching costs against an oblivious adversary under full-information and bandit feedback. Our algorithms use shared-threshold rounding to control movement. For a ground set of size $n$, horizon $T$, losses in $[-M,M]$, and switching-cost weight $\lambda$, the minimax expected regret under full information is $\Theta (M\min T,\sqrt{(1+\lambda /M)nT})$. Under bandit feedback, a chain-traversal exploration scheme achieves $O(M\min T,n(1+\lambda /M{)}^{1/3}{T}^{2/3})$, matching our lower bound up to logarithmic factors when $\lambda \ge M$. To obtain high-probability guarantees, we establish a pathwise upper bound on the realized regret that isolates a cumulative movement the learner can monitor. Using this quantity to trigger a switching-budget restarting wrapper yields high-probability bounds under both feedback models with only logarithmic overhead.