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

TL;DR

This paper introduces Online Conversion with Switching Costs (OCS), a new framework for online decision-making where players must buy or sell assets over time while facing penalties for changing their conversion rates. The authors develop RORO (Ramp-On Ramp-Off), a provably optimal deterministic algorithm, and RO-Advice, a learning-augmented version that integrates machine learning predictions to achieve superior average-case performance without sacrificing worst-case safety.

What Problem Does This Paper Address?

In classic "online conversion" problems, you try to buy or sell an asset (like currency or electricity) over a fixed time window without knowing future prices. However, real-world systems—especially in sustainable energy—face switching costs. For example, 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 either handle deadlines without switching costs (like one-way trading) or handle switching costs without hard deadlines (like convex function chasing). 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 a "smooth" operation.

Methods

The authors propose two primary algorithmic contributions:

  1. RORO (Ramp-On Ramp-Off): A novel framework that handles continuous decision spaces. At each time step, it solves two "pseudo-cost" optimization problems—one assuming the conversion rate increases and one assuming it decreases. It then selects the decision that minimizes a balanced cost function. The authors prove that RORO achieves the optimal competitive ratio for this problem class.
  2. RO-Advice: A "learning-augmented" meta-algorithm. It takes "black-box" advice (e.g., a time-series prediction from an ML model) and blends it with the robust RORO decision. A hyperparameter $\epsilon$ allows users to tune the trade-off between consistency (how well it performs if the ML advice is perfect) and robustness (how well it performs if the ML advice is totally wrong).

Datasets

The algorithms were evaluated using a carbon-aware EV charging case study with the following data:

  • ACN-Data: A dataset of ~16,000 real EV charging sessions (arrival/departure times and energy demand).
  • CAISO Data: Historical marginal carbon intensity traces from the California Independent System Operator.
  • NSRDB: Solar irradiation data used to simulate local solar generation at charging sites.
  • CarbonCast: An "off-the-shelf" CNN-LSTM model used to provide the ML-based carbon intensity forecasts for the RO-Advice algorithm.

Key Insights and Ideas

  • The "Smoothing" Requirement: Switching costs fundamentally change the optimal strategy. Instead of waiting for a single "best" price, the algorithm must "ramp" its activity to avoid the high penalties associated with sudden changes.
  • Advice Complexity: The authors prove a significant theoretical result: to achieve perfect performance (1-consistency), an algorithm needs advice that grows linearly with the length of the time horizon. Simple "best price" predictions are insufficient for OCS because they don't provide enough information to manage the temporal switching costs.
  • Continuous vs. Binary: While previous work handled binary "pause and resume" decisions, OCS requires continuous decisions (e.g., charging at 4.5kW vs 5kW). This makes traditional "double threshold" approaches fail, necessitating the optimization-based RORO approach.

Key Results

  • Theoretical Optimality: RORO is proven to be the best possible deterministic online algorithm for OCS, matching the information-theoretic lower bound.
  • Empirical Gains: In EV charging simulations, RORO improved the average empirical competitive ratio by 57.3% over carbon-agnostic methods and 12.1% over standard one-way trading.
  • ML Boost: When augmented with ML predictions (RO-Advice), the performance improved by an additional 33.4% over the robust RORO algorithm.
  • Safety Guaranteed: Even when the ML predictions were intentionally manipulated to be adversarial, RO-Advice maintained a competitive ratio bounded by a safe worst-case limit.

Limitations and Future Work

  • Multidimensionality: The current model is one-dimensional (buying/selling one asset). The authors suggest that future work should explore multidimensional settings, such as shifting workloads across both time and different geographic data center locations.
  • Pareto-Optimality: While the paper provides a consistency-robustness trade-off, it remains an open question whether this specific trade-off is "Pareto-optimal" (the absolute best possible balance) for the OCS problem.
  • Complex Advice Models: Since linear advice is required for 1-consistency, exploring more efficient ways to compress or provide "just enough" advice for complex online metrics remains a promising research path.

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

Loading related content...

Figure