在不确定性优化中，随机优化是一种广泛应用的方法，其中不确定的输入参数被建模为随机变量。尽管已经为多个基本问题提出了精确或近似算法，但这一方法的一个显著限制是需要对基础概率分布有完全的了解。本文探讨了在未知分布的情况下，算法如何通过重复交互学习这些分布，并且能否仍然获得良好的近似算法。
我们为一类“单调”随机问题提供了一种通用的在线学习算法，其相对最佳近似算法的遗憾为 $\sqrt{T\log T}$。值得注意的是，我们的在线算法适用于半带式设置，即在每个周期中，算法仅观察实际探测的随机变量的样本。此外，我们的结果还扩展到有审查和二元反馈的设置，在这些情况下，策略仅观察探测变量的截断或阈值版本。
我们的框架适用于多个基本问题，包括先知不等式、潘多拉盒子、随机背包、单资源收益管理和序列定价等。