Understand Dynamic Regret with Switching Cost for Online Decision Making

Yawei Zhao, Qian Zhao, Xingxing Zhang, En Zhu, Xinwang Liu, Jianping Yin

TL;DR

This paper investigates how "switching costs"—the penalty for changing decisions between rounds—affect the performance of online decision-making. The authors reveal a surprising asymmetry: while switching costs significantly degrade performance in settings where you see the loss function before acting (Online Algorithms), they have virtually no impact on the fundamental difficulty of settings where you must act before seeing the loss (Online Convex Optimization).

What Problem Does This Paper Address?

In real-world online decision-making (like managing data center resources or stock portfolios), you don't just care about the immediate "operating cost" of a choice. You also care about the switching cost: the price of changing your mind. For example, moving a virtual machine between servers or ramping up a power plant incurs physical or computational overhead.

Researchers typically measure performance using dynamic regret, which compares an algorithm's total cost against the best possible sequence of decisions made with perfect hindsight. While previous work established bounds for this regret, it wasn't clear how the switching cost specifically influenced the difficulty of the problem. The authors set out to answer: Does adding a movement penalty fundamentally change the "speed limit" (regret bound) of online learning?

Methods

The authors analyze two classic settings using a unified Online Mirror Descent (OMD) framework:

  1. Online Algorithms (OA): The agent observes the current loss function $f_t$ before making a decision $x_t$.
  2. Online Convex Optimization (OCO): The agent must commit to a decision $x_t$ before the loss function $f_t$ is revealed.

A key contribution is their generalized switching cost formulation. Instead of just looking at the distance between decisions ($\|x_{t+1} - x_t\|$), they use a power $\sigma$ (where $1 \le \sigma \le 2$). This allows the model to account for different types of penalties, such as those sensitive to small changes ($\sigma=1$) versus those that heavily penalize large jumps ($\sigma=2$).

Datasets

The authors evaluated their theoretical findings using binary classification tasks (logistic regression) on three real-world datasets characterized by "concept drift" (changing data distributions over time):

  • usenet1
  • usenet2
  • spam (from the UCI repository)

These datasets represent dynamic environments where the optimal decision is constantly shifting, making them ideal for testing dynamic regret.

Key Insights and Ideas

  • The Information Gap: The most striking insight is that the impact of switching cost depends entirely on when you see the loss.
  • OA is sensitive to movement: In the OA setting, knowing the loss function allows the agent to calculate a precise tradeoff between operating and switching costs. Here, the switching cost directly dictates the regret bound.
  • OCO is "immune" to movement: In the OCO setting, the environment can be adversarial. Because the agent is already "blind" to the current loss, the inherent difficulty of guessing the loss function is so high that the switching cost doesn't make the problem fundamentally harder. The regret bound remains $O(\sqrt{TD})$, the same as if there were no switching cost at all.
  • The "Aha!" Moment: Switching cost is "free" in OCO because the bottleneck is information, not movement. In OA, where information is plentiful, movement becomes the new bottleneck.

Key Results

  • OA Bound: For the OA setting, the authors proved a dynamic regret bound of $O(T^{\frac{1}{\sigma+1}} D^{\frac{\sigma}{\sigma+1}})$, where $D$ is the "path length" (how much the optimal decisions move). When $\sigma=1$, this matches the state-of-the-art $O(\sqrt{TD})$.
  • OCO Bound: For the OCO setting, they achieved $O(\sqrt{TD} + \sqrt{T})$.
  • Tightness: They provided a lower bound of $\Omega(\sqrt{TD} + \sqrt{T})$ for OCO, proving that their algorithm is optimal and that switching costs do not increase the complexity of the OCO problem.
  • Empirical Confirmation: Experiments showed that while OCO methods suffer much higher total loss than OA methods (due to the lack of look-ahead), the additional loss caused by switching costs in OCO is relatively stable, whereas in OA, it can be optimized much more aggressively.

Limitations and Future Work

  • Parameter Dependence: The current bounds depend on knowing the "budget of dynamics" ($D$) to tune the learning rate. The authors suggest that moving toward parameter-free settings—where the algorithm adapts to $D$ automatically—is a vital next step.
  • Distance Metrics: The study primarily uses standard norms for switching costs. The authors note that extending this to more general distance measures, like Bregman divergence or Mahalanobis distance, would make the framework even more robust for specialized applications.
  • Expert Settings: While this paper covers general convex optimization, the authors mention that exploring these switching cost dynamics in "expert" settings (discrete choices) remains an open question.

Summary updated

Abstract

As a metric to measure the performance of an online method, dynamic regret with switching cost has drawn much attention for online decision making problems. Although the sublinear regret has been provided in many previous researches, we still have little knowledge about the relation between the dynamic regret and the switching cost. In the paper, we investigate the relation for two classic online settings: Online Algorithms (OA) and Online Convex Optimization (OCO). We provide a new theoretical analysis framework, which shows an interesting observation, that is, the relation between the switching cost and the dynamic regret is different for settings of OA and OCO. Specifically, the switching cost has significant impact on the dynamic regret in the setting of OA. But, it does not have an impact on the dynamic regret in the setting of OCO. Furthermore, we provide a lower bound of regret for the setting of OCO, which is same with the lower bound in the case of no switching cost. It shows that the switching cost does not change the difficulty of online decision making problems in the setting of OCO.
BibTeX
@article{zhao2020understand,
  author = {Yawei Zhao and Qian Zhao and Xingxing Zhang and En Zhu and Xinwang Liu and Jianping Yin},
  title = {{Understand Dynamic Regret with Switching Cost for Online Decision Making}},
  journal = {ACM Trans. Intell. Syst. Technol.},
  year = {2020},
  url = {https://openreview.net/forum?id=xNqrW59HopT},
}

Loading related content...

Figure