Smoothed Online Combinatorial Optimization Using Imperfect Predictions

Authors

  • Kai Wang Harvard University
  • Zhao Song Adobe Research
  • Georgios Theocharous Adobe Research
  • Sridhar Mahadevan Adobe Research

DOI:

https://doi.org/10.1609/aaai.v37i10.26430

Keywords:

PRS: Planning Under Uncertainty

Abstract

Smoothed online combinatorial optimization considers a learner who repeatedly chooses a combinatorial decision to minimize an unknown changing cost function with a penalty on switching decisions in consecutive rounds. We study smoothed online combinatorial optimization problems when an imperfect predictive model is available, where the model can forecast the future cost functions with uncertainty. We show that using predictions to plan for a finite time horizon leads to regret dependent on the total predictive uncertainty and an additional switching cost. This observation suggests choosing a suitable planning window to balance between uncertainty and switching cost, which leads to an online algorithm with guarantees on the upper and lower bounds of the cumulative regret. Empirically, our algorithm shows a significant improvement in cumulative regret compared to other baselines in synthetic online distributed streaming problems.

Downloads

Published

2023-06-26

How to Cite

Wang, K., Song, Z., Theocharous, G., & Mahadevan, S. (2023). Smoothed Online Combinatorial Optimization Using Imperfect Predictions. Proceedings of the AAAI Conference on Artificial Intelligence, 37(10), 12130-12137. https://doi.org/10.1609/aaai.v37i10.26430

Issue

Section

AAAI Technical Track on Planning, Routing, and Scheduling