Understand Dynamic Regret with Switching Cost for Online Decision Making

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

Introduction

In real-world online decision-making scenarios, such as managing data center resources or optimizing stock portfolios, the cost of a decision is not limited to the immediate "operating cost." A significant factor often overlooked is the switching cost: the penalty incurred when changing decisions between consecutive rounds. For instance, migrating a virtual machine between physical servers or adjusting the output level of a power plant involves substantial computational or physical overhead.

This paper investigates how these switching costs influence the fundamental difficulty of online learning, measured through dynamic regret. Dynamic regret compares an algorithm's cumulative cost against the best possible sequence of decisions made with perfect hindsight. The central question addressed is whether the addition of a movement penalty fundamentally alters the regret bounds of online decision-making.

Problem Formulation and Settings

The authors analyze two classic online learning paradigms using a unified Online Mirror Descent (OMD) framework. The primary distinction between these settings lies in the information available to the agent at the time of decision-making.

Comparison of Online Algorithms (OA) and Online Convex Optimization (OCO) settings.
  1. Online Algorithms (OA): In this setting, the agent observes the current loss function $f_t$ before committing to a decision $x_t$. This "look-ahead" allows for a direct trade-off between operating and switching costs.
  2. Online Convex Optimization (OCO): Here, the agent must commit to a decision $x_t$ before the loss function $f_t$ is revealed. This is a more challenging, adversarial setting where the agent is effectively "blind" to the immediate consequences of their choice.

A key innovation in this work is the introduction of a generalized switching cost formulation. Rather than relying solely on standard distance metrics ($\|x_{t+1} - x_t\|$), the authors use a power $\sigma$ (where $1 \le \sigma \le 2$). This parameterization allows the model to capture various penalty types, from those sensitive to minor adjustments ($\sigma=1$) to those that disproportionately penalize large shifts ($\sigma=2$).

Theoretical Insights: The Information Gap

The research reveals a striking asymmetry in how switching costs affect these two settings. The impact of movement penalties is entirely dependent on the timing of information revelation.

  • Sensitivity in OA: In the OA setting, where information about the loss is plentiful, the switching cost becomes the primary bottleneck. The agent can precisely calculate the optimal trade-off, and thus the switching cost directly dictates the achievable regret bound.
  • Immunity in OCO: Conversely, in the OCO setting, the bottleneck is information rather than movement. Because the agent must act before seeing the loss, the inherent difficulty of predicting an adversarial environment is so high that the additional switching cost does not fundamentally increase the problem's complexity. The regret bound remains dominated by the uncertainty of the loss function.

Main Results

The authors provide rigorous dynamic regret bounds for both settings:

  • OA Bound: For the OA setting, they prove a bound of $O(T^{\frac{1}{\sigma+1}} D^{\frac{\sigma}{\sigma+1}})$, where $D$ represents the "path length" (the total movement of the optimal decisions). At $\sigma=1$, this matches the state-of-the-art $O(\sqrt{TD})$.
  • OCO Bound: For the OCO setting, they achieve a bound of $O(\sqrt{TD} + \sqrt{T})$.
  • Optimality: The authors establish a lower bound of $\Omega(\sqrt{TD} + \sqrt{T})$ for OCO, demonstrating that their algorithm is optimal and confirming that switching costs do not increase the asymptotic complexity of OCO.

Empirical Evaluation

The theoretical findings were validated using binary classification tasks (logistic regression) on three real-world datasets characterized by "concept drift": usenet1, usenet2, and spam (from the UCI repository). These datasets provide dynamic environments where the optimal decision boundary shifts over time.

The experiments confirmed that while OCO methods generally suffer higher total loss than OA methods due to the lack of look-ahead, the marginal loss attributed to switching costs in OCO is relatively stable. In contrast, OA methods can optimize for switching costs much more aggressively, reflecting their sensitivity to movement penalties.

Conclusion and Future Work

This work clarifies the role of switching costs in online decision-making, showing that their impact is contingent on the information structure of the problem. Future research directions include developing parameter-free algorithms that can adapt to the path length $D$ without prior knowledge. Additionally, extending the framework to more general distance measures, such as Bregman divergence, and exploring these dynamics in discrete "expert" settings remain promising avenues for further study.

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},
}
Figure