文件名称：贝叶斯先知：在线决策的低后悔框架-研究论文
文件大小：792KB
文件格式：PDF
更新时间：2024-06-29 08:05:36
Online Stochastic Optimization
我们开发了一个用于设计在线策略的新框架，允许访问提供有关离线基准的统计信息的预言机。 访问此类预测预言机可以实现简单而自然的贝叶斯选择策略，并提出了这些策略在不同环境中如何执行的问题。 我们的工作对这个问题做出了两个重要贡献：首先，我们开发了一种称为补偿耦合的通用技术，可用于推导出任何在线策略和离线基准的预期遗憾（即相对于基准的附加损失）的界限. 其次，使用这种技术，我们展示了一种自然贪婪策略，我们称之为贝叶斯选择器，对于我们称为在线分配的一大类问题，具有恒定的预期遗憾（即，与到达数量和资源水平无关）具有有限类型，其中包括广泛研究的在线包装和在线匹配问题。 我们的结果概括和简化了在线打包和在线匹配的几个现有结果，并为获得其他在线决策设置的预言机驱动策略提供了一条有前途的途径。