论文标题
使用不完美的预测平滑在线组合优化
Smoothed Online Combinatorial Optimization Using Imperfect Predictions
论文作者
论文摘要
平滑的在线组合优化考虑了一个学习者，他反复选择了组合决定，以最大程度地减少不知情的变化成本功能，并在连续回合中进行惩罚。当有不完美的预测模型可用时，我们研究平滑的在线组合优化问题，该模型可以在此预测未确定的未来成本功能。我们表明，使用预测计划有限的时间范围会导致后悔取决于总预测性不确定性和额外的切换成本。该观察结果表明，选择一个合适的计划窗口来平衡不确定性和切换成本之间，这导致了在线算法，并保证了累积遗憾的上和下限。从经验上讲，与合成在线分布式流媒体问题中的其他基线相比，我们的算法在累积后悔方面显示出显着改善。
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.
