Asymptotically Optimal Regret for Black-Box Predict-then-Optimize

本文考虑了预测后优化决策模型，该模型包括两个步骤：（1）从历史数据中训练监督学习模型，包括决策、背景和奖励；（2）使用该模型为新的背景进行二元决策，以最大化模型预测的奖励。这种方法在工业界很常见。过去的分析假设在所有历史背景下，所有行动的奖励都是已知的，这只适用于具有特殊结构的问题。本文针对广告定向和推荐系统中的新型黑盒预测后优化问题进行了研究，这些问题缺乏特殊结构，我们只能观察到所采取行动的奖励。我们提出了一种新的损失函数，称为经验软遗憾（ESR），该函数与传统的基于准确性的度量（如均方误差）相比，能够在训练时显著提高奖励。该损失函数针对采取次优决策时的遗憾进行优化；由于遗憾通常是不可微分的，因此我们提出了一个可微分的“软”遗憾项，使得可以使用神经网络和其他依赖于梯度训练的灵活机器学习模型。在特定的成对数据情况下，我们理论上证明了优化我们的损失函数将在监督学习模型类中达到渐近最优的遗憾。我们还展示了我们的方法在新闻推荐和个性化医疗方面的实际决策问题中明显优于基于上下文的贝叶斯方法和条件平均处理效应估计的基准算法。

黑盒预测优化问题，如何在缺乏特殊结构的情况下优化决策？

提出了一种新的损失函数Empirical Soft Regret（ESR），用于训练预测模型，并在预测-优化决策中使用。ESR针对次优决策的遗憾进行优化，通过可微的“软”遗憾项，使得神经网络等灵活的机器学习模型能够使用梯度下降进行训练。在成对数据的情况下，理论上优化ESR可以在监督学习模型类中实现渐近最优遗憾。

论文的实验表明，ESR方法在新闻推荐和个性化医疗决策等现实问题中，相比于基于上下文的强化学习和条件平均处理效果估计等基准方法，具有显著的性能优势。

相关研究包括上下文感知多臂老虎机问题和条件平均处理效果估计等。