TL;DR本文研究如何以在线学习问题的形式购买信息来帮助随机优化问题，提出了一个 $2$-competitive 算法和一个 $e/(e-1)$-competitive 随机化算法，特别应用于 Min-Sum Set Cover 优化问题。
Abstract
stochastic optimization is one of the central problems in Machine Learning
and Theoretical Computer Science. In the standard model, the algorithm is given
a fixed distribution known in advance. In practice though
通过提供一种具有与最佳近似算法（在已知分布下）相对于平方根的 T 乘以 log T 束缚的通用在线学习算法，在半探测器环境中解决了在一大类 “单调” 随机问题中对于未知分布是否能够获得良好（近似）算法进行学习的问题。我们的框架适用于随机优化的若干基本问题，如先知不等式、潘多拉盒、随机背包、随机匹配和随机次模优化。