Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms

Adam Lechowicz, Nicolas Christianson, Bo Sun, Noman Bashir, Mohammad Hajiesmaili, Adam Wierman, Prashant J. Shenoy

Abstract

We introduce and study online conversion with switching costs, a family of online problems that capture emerging problems at the intersection of energy and sustainability. In this problem, an online player attempts to purchase (alternatively, sell) fractional shares of an asset during a fixed time horizon with length $T$. At each time step, a cost function (alternatively, price function) is revealed, and the player must irrevocably decide an amount of asset to convert. The player also incurs a switching cost whenever their decision changes in consecutive time steps, i.e., when they increase or decrease their purchasing amount. We introduce competitive (robust) threshold-based algorithms for both the minimization and maximization variants of this problem, and show they are optimal among deterministic online algorithms. We then propose learning-augmented algorithms that take advantage of untrusted black-box advice (such as predictions from a machine learning model) to achieve significantly better average-case performance without sacrificing worst-case competitive guarantees. Finally, we empirically evaluate our proposed algorithms using a carbon-aware EV charging case study, showing that our algorithms substantially improve on baseline methods for this problem.

Introduction

In classic online conversion problems, a decision-maker seeks to buy or sell an asset over a fixed time window without knowledge of future prices. However, real-world systems—particularly in sustainable energy—face significant switching costs. For instance, rapidly fluctuating the charging rate of an electric vehicle (EV) can degrade the battery, and shifting massive data center workloads incurs operational overhead. Existing algorithms typically handle either deadlines without switching costs or switching costs without hard deadlines. This paper bridges that gap, specifically targeting "carbon-aware" problems where the goal is to time energy use to coincide with low-carbon intensity periods while maintaining smooth operation.

Switching costs fundamentally change the optimal strategy. Instead of waiting for a single "best" price, an algorithm must "ramp" its activity to avoid high penalties associated with sudden changes. Furthermore, while previous work handled binary "pause and resume" decisions, Online Conversion with Switching Costs (OCS) requires continuous decisions (e.g., charging at 4.5kW vs 5kW), rendering traditional double-threshold approaches insufficient.

The RORO and RO-Advice Algorithms

The authors propose two primary algorithmic contributions to address the OCS problem:

  1. RORO (Ramp-On Ramp-Off): This novel framework handles continuous decision spaces by solving two "pseudo-cost" optimization problems at each time step—one assuming the conversion rate increases (ramping-on) and one assuming it decreases (ramping-off). It then selects the decision that minimizes a balanced cost function. RORO is proven to achieve the optimal competitive ratio for this problem class.
Algorithm 1: The Online Ramp-On, Ramp-Off (RORO) framework.
  1. RO-Advice: A learning-augmented meta-algorithm that integrates "black-box" advice (e.g., time-series predictions from an ML model) with the robust RORO decision. A hyperparameter $\epsilon$ allows users to tune the trade-off between consistency (performance with perfect advice) and robustness (performance with adversarial advice).

A significant theoretical result of this work is that achieving perfect performance (1-consistency) requires advice that grows linearly with the length of the time horizon. Simple "best price" predictions are insufficient for OCS because they lack the information necessary to manage temporal switching costs.

Empirical Evaluation

The algorithms were evaluated using a carbon-aware EV charging case study. The study utilized the ACN-Data set of ~16,000 real EV charging sessions, historical marginal carbon intensity traces from CAISO, and solar irradiation data from NSRDB. ML-based carbon intensity forecasts were provided by CarbonCast, an off-the-shelf CNN-LSTM model.

Key results include:

  • Theoretical Optimality: RORO matches the information-theoretic lower bound for deterministic online algorithms.
  • Empirical Gains: In simulations, RORO improved the average empirical competitive ratio by 57.3% over carbon-agnostic methods and 12.1% over standard one-way trading.
  • ML Integration: RO-Advice improved performance by an additional 33.4% over the robust RORO algorithm.
  • Safety: Even with manipulated adversarial predictions, RO-Advice maintained a competitive ratio within a safe worst-case limit.

Conclusion and Future Work

This work establishes a robust framework for online conversion with switching costs. Future research may explore multidimensional settings, such as shifting workloads across both time and geographic locations. Additionally, determining the Pareto-optimality of the consistency-robustness trade-off and exploring more efficient advice compression models remain open challenges.

Summary updated

Abstract

We introduce and study online conversion with switching costs, a family of online problems that capture emerging problems at the intersection of energy and sustainability. In this problem, an online player attempts to purchase (alternatively, sell) fractional shares of an asset during a fixed time horizon with length $T$. At each time step, a cost function (alternatively, price function) is revealed, and the player must irrevocably decide an amount of asset to convert. The player also incurs a switching cost whenever their decision changes in consecutive time steps, i.e., when they increase or decrease their purchasing amount. We introduce competitive (robust) threshold-based algorithms for both the minimization and maximization variants of this problem, and show they are optimal among deterministic online algorithms. We then propose learning-augmented algorithms that take advantage of untrusted black-box advice (such as predictions from a machine learning model) to achieve significantly better average-case performance without sacrificing worst-case competitive guarantees. Finally, we empirically evaluate our proposed algorithms using a carbon-aware EV charging case study, showing that our algorithms substantially improve on baseline methods for this problem.
BibTeX
@inproceedings{lechowicz2024online,
  author = {Adam Lechowicz and Nicolas Christianson and Bo Sun and Noman Bashir and Mohammad Hajiesmaili and Adam Wierman and Prashant J. Shenoy},
  title = {{Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms}},
  booktitle = {SIGMETRICS/Performance (Abstracts)},
  year = {2024},
  doi = {10.1145/3652963.3655074},
}
Figure