Smoothed Online Combinatorial Optimization Using Imperfect Predictions
This work addresses online decision-making problems with switching penalties for applications like resource allocation, but it appears incremental as it builds on existing smoothed optimization frameworks by integrating predictions.
The paper tackles smoothed online combinatorial optimization by incorporating imperfect predictions of future cost functions, resulting in an algorithm that balances predictive uncertainty and switching costs to achieve improved cumulative regret bounds. Empirical results show significant improvement over baselines in synthetic online distributed streaming problems.
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.