通过离线贪心算法在线学习：在市场设计和优化中的应用-研究论文

受时变组合环境中在线决策的启发，我们研究了将离线算法转换为在线算法的问题。 我们专注于离线组合问题，这些问题可以使用对局部错误具有鲁棒性的贪婪算法进行常数因子逼近。 对于此类问题，我们提供了一个通用框架，该框架使用 Blackwell 可接近性将离线鲁棒贪婪算法有效地转换为在线算法。 我们表明，在完整信息设置下，由此产生的在线算法有 O(T^{1/2})（近似）遗憾。 我们进一步介绍了 Blackwell 可接近性的强盗扩展，我们称之为 Bandit Blackwell 可接近性。 我们利用这个概念将贪婪的鲁棒离线算法转换为强盗设置中的 O(T^{2/3})（近似）遗憾。 为了展示我们框架的灵活性，我们将离线到在线转换应用于收益管理、市场设计和在线优化交叉点的几个问题，包括在线平台中的产品排名优化、拍卖中的底价优化和子模块最大化. 我们表明，当我们的转换应用于这些应用程序时，会导致新的遗憾界限或改进当前已知的界限。