Abstract
In the domain of online optimization, agents often face a dual-cost structure: a hitting cost associated with the current action's performance and a switching cost penalized by the magnitude of change between consecutive actions. While Smoothed Online Convex Optimization (SOCO) provides a framework for these problems, existing literature typically assumes the hitting cost functions are known. This paper introduces SCaLE (Switching Cost aware Learning and Exploration), the first algorithm to achieve sub-linear dynamic regret for unknown quadratic hitting costs under noisy bandit feedback. By strategically balancing an initial exploration phase with a robust exploitation phase, SCaLE overcomes the fundamental trade-off between moving to learn and remaining stationary to minimize costs, even in high-dimensional, rank-deficient environments.
1. Introduction
Real-world systems—ranging from data center thermal management to wind turbine control—operate under a "pay-as-you-go" reality. Every decision involves a hitting cost (how well the action meets demand) and a switching cost (the penalty for rapid state changes). Traditionally, these problems are modeled as Smoothed Online Convex Optimization (SOCO). However, in many practical scenarios, the underlying cost function is unknown, and the agent only receives "bandit feedback"—a single, noisy measurement of the total cost after an action is taken.
This lack of information introduces a significant challenge: to learn the system's curvature, the agent must explore diverse actions. Yet, in a SOCO framework, diverse actions necessitate large movements, which directly increase switching costs. This paper addresses this tension by providing a principled approach to learning and exploration in the presence of movement penalties.
2. Problem Formulation
The paper considers a system where an agent chooses an action $x_t$ at each time step $t$ and incurs a cost: $$C_t(x_t) = f_t(x_t) + \frac{1}{2}\|x_t - x_{t-1}\|^2$$
Here, $f_t$ is a quadratic hitting cost governed by an unknown matrix $A$. The agent does not observe $f_t$ or its gradient; instead, it receives a noisy observation $y_t = f_t(x_t) + \epsilon_t$. The goal is to minimize dynamic regret, the difference between the agent's total cost and the cost of the best sequence of actions in hindsight.
Two primary hurdles complicate this setting:
- The Fundamental Trade-off: Learning the $d \times d$ matrix $A$ requires exploration, but exploration triggers switching costs.
- Degeneracy in High Dimensions: In many real-world systems, $A$ is rank-deficient. In these "flat" regions, bandit feedback is dominated by noise, making it difficult to identify the system's curvature without incurring prohibitive movement costs.
3. The SCaLE Algorithm
The researchers propose a two-stage algorithm, SCaLE (Switching Cost aware Learning and Exploration), designed to manage the exploration-exploitation trade-off:
3.1 Exploration Phase
For an initial duration of $m$ rounds, the algorithm probes the environment by injecting Gaussian noise around a target state. This phase is a deliberate sacrifice; the agent intentionally incurs higher switching costs to gather the diverse data necessary for statistical consistency. This ensures that the estimate of the unknown matrix $A$ is sufficiently accurate for the subsequent phase.
3.2 Estimation and Exploitation
Following the exploration phase, the algorithm performs two steps:
- Estimation: It solves a convex trace-norm minimization problem to recover the unknown matrix $A$ from the noisy bandit feedback collected during exploration.
- Exploitation: Using the estimated matrix, the agent follows a Linear-Adaptive Interpolation (LAI) policy. LAI is known to be optimal for SOCO when the quadratic costs are known, as it balances the hitting cost against the switching cost by interpolating between the current state and the predicted minimizer.
Additionally, the authors introduce HySCaLE (Hybrid SCaLE), a heuristic variant that continues to refine the estimate of $A$ during the exploitation phase using projected gradient descent, allowing for continuous adaptation.
4. Theoretical Contributions
A core contribution of this work is a novel spectral regret analysis. The authors decompose the regret into two distinct components: errors in estimating the eigenvalues of $A$ and perturbations in the eigenbasis. This analytical framework allows them to prove that SCaLE remains stable even when the matrix $A$ is singular.
Key theoretical findings include:
- Regret Bounds: If $A$ is full-rank, SCaLE achieves $O(T^{1/2})$ regret, which is optimal. If $A$ is rank-deficient, it achieves $O(T^{2/3})$ regret.
- Exploration Necessity: The authors prove a lower bound showing that any algorithm that does not explicitly explore will suffer at least $\Omega(\sqrt{T})$ regret. Curvature cannot be learned "for free" in the presence of switching costs.
5. Experimental Results
As a theoretical advancement, the paper validates SCaLE through extensive numerical simulations across various noise distributions to test its "distribution-agnostic" claims. The algorithm was tested against three types of noise in the minimizer sequence:
- Light-tailed: IID and correlated Gaussian noise.
- Heavy-tailed: Laplace distribution.
- Fat-tailed: Cauchy distribution (where variance is undefined).
In these simulations, SCaLE and HySCaLE significantly outperformed standard baselines such as "Follow the Minimizer" (FTM) and "Passive Online Learners" (POL). Notably, the algorithm demonstrated remarkable stability against heavy-tailed disturbances that typically cause standard gradient-based learners to fail. Furthermore, sensitivity analysis indicated that the optimal exploration time $m$ is relatively constant across different noise levels, suggesting the algorithm is robust and easy to tune.
6. Conclusion and Future Work
SCaLE represents a significant step forward in online optimization by providing the first sub-linear dynamic regret guarantees for unknown quadratic costs with switching penalties. It proves that even with limited bandit feedback and high-dimensional, rank-deficient structures, effective learning is possible through structured exploration.
Future research directions include moving beyond the "explore-then-exploit" rigidity toward a formal "continuous learning" framework that maintains theoretical guarantees. Additionally, extending these methods to fully adversarial environments—where noise is not just random but potentially malicious—remains an open and promising challenge.
Summary updated