# SCaLE: Switching Cost aware Learning and Exploration

arXiv: https://arxiv.org/abs/2601.09042 · HTML: https://mlsanity.com/paper/2601.09042/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 33 of its 95 references that are in the map.
- First posted on arXiv 14 Jan 2026.

## Builds on (most cited first, 30 of 33)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Improper Learning for Non-Stochastic Control](https://mlsanity.com/paper/2001.09254/) (2020)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics](https://mlsanity.com/paper/1605.00353/) (2016)
- [Non-stationary Online Learning with Memory and Non-stochastic Control](https://mlsanity.com/paper/2102.03758/) (2021)
- [Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization](https://mlsanity.com/paper/1905.12776/) (2019)
- [Online Algorithms for Weighted Paging with Predictions](https://mlsanity.com/paper/2006.09509/) (2020)
- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Smoothed Online Optimization for Regression and Control](https://mlsanity.com/paper/1810.10132/) (2018)
- [Perturbation-based Regret Analysis of Predictive Control in Linear Time Varying Systems](https://mlsanity.com/paper/2106.10497/) (2021)
- [Operator splitting for a homogeneous embedding of the linear complementarity problem](https://mlsanity.com/paper/2004.02177/) (2020)
- [Exact and Stable Covariance Estimation from Quadratic Sampling via Convex Programming](https://mlsanity.com/paper/1310.0807/) (2013)
- [An optimal algorithm for bandit convex optimization](https://mlsanity.com/paper/1603.04350/) (2016)
- [ROP: Matrix recovery via rank-one projections](https://mlsanity.com/paper/1310.5791/) (2013)
- [Chasing Convex Bodies Optimally](https://mlsanity.com/paper/1905.11968/) (2019)
- [Chasing Convex Bodies with Linear Competitive Ratio](https://mlsanity.com/paper/1905.11877/) (2019)
- [Better Best of Both Worlds Bounds for Bandits with Switching Costs](https://mlsanity.com/paper/2206.03098/) (2022)
- [Bandit Linear Control](https://mlsanity.com/paper/2007.00759/) (2020)
- [In-Trajectory Inverse Reinforcement Learning: Learn Incrementally Before An Ongoing Trajectory Terminates](https://mlsanity.com/paper/2410.15612/) (2024)
- [Finite-time System Identification and Adaptive Control in Autoregressive Exogenous Systems](https://mlsanity.com/paper/2108.11959/) (2021)
- [Decentralized Online Convex Optimization in Networked Systems](https://mlsanity.com/paper/2207.05950/) (2022)
- [Online Learning for Predictive Control with Provable Regret Guarantees](https://mlsanity.com/paper/2111.15041/) (2021)
- [Online Linear Quadratic Tracking with Regret Guarantees](https://mlsanity.com/paper/2303.10260/) (2023)
- [Online Convex Optimization with Switching Cost and Delayed Gradients](https://mlsanity.com/paper/2310.11880/) (2023)
- [Inverse reinforcement learning by expert imitation for the stochastic linear-quadratic optimal control problem](https://mlsanity.com/paper/2405.17085/) (2024)
- [Algorithms for Right-Sizing Heterogeneous Data Centers](https://mlsanity.com/paper/2107.14692/) (2021)
- [Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization](https://mlsanity.com/paper/2311.00181/) (2023)
- [Tight Rates for Bandit Control Beyond Quadratics](https://mlsanity.com/paper/2410.00993/) (2024)
- [Regret Analysis of Learning-Based Linear Quadratic Gaussian Control with Additive Exploration](https://mlsanity.com/paper/2311.02679/) (2023)
- [Optimal Decentralized Smoothed Online Convex Optimization](https://mlsanity.com/paper/2411.08355/) (2024)

## Abstract (arXiv)

This work addresses the fundamental problem of unbounded metric movement costs in bandit online convex optimization, by considering high-dimensional dynamic quadratic hitting costs and ℓ2-norm switching costs in a noisy bandit feedback model. For a general class of stochastic environments, we provide the first algorithm SCaLE that provably achieves a distribution-agnostic sub-linear dynamic regret, without the knowledge of hitting cost structure. En-route, we present a novel spectral regret analysis that separately quantifies eigenvalue-error driven regret and eigenbasis-perturbation driven regret. Extensive numerical experiments, against online-learning baselines, corroborate our claims, and highlight statistical consistency of our algorithm.