文件名称：好先知知道末日临近-研究论文
文件大小：1.24MB
文件格式：PDF
更新时间：2024-06-29 10:54:11
online stochastic decision-making
我们考虑一类具有可交换动作的在线决策问题，其中在每个周期中，控制器都会收到来自某个随机到达过程的输入类型，并且必须选择一个动作，最终目标仅取决于类型动作计数的总和. 这样的框架封装了许多常见优化问题的在线随机变体，例如背包、装箱和广义分配作为规范示例。 在这种情况下，我们研究了一种自然模型预测控制算法，该算法在每个时期都基于更新的确定性等价优化问题贪婪地行动。 我们引入了一个简单但通用的条件，在该条件下，与具有完整到达知识的最佳解决方案相比，该算法获得均匀的附加损失（独立于地平线）。 我们的条件建立在 Vera 和 Banerjee (2019) 的补偿耦合技术之上，提供了一个统一的观点，即作为基础决策问题的几何结构的结果如何产生均匀的附加损失。我们的特征使我们能够推导出均匀损失算法几个新的设置，包括第一个这样的在线随机装箱算法。 它还让我们可以研究其他建模假设的影响，包括范围的选择、批量决策和有限的计算。 特别是，我们表明，当时间范围的结束在结束前足够长的时间已知时，上述问题满足了我们的条件。 相比之下，如果在后期阶段，时间范围的结束仍然存在不确定性，我们表明这种统一的损失保证是不可能实现的。 我们通过对真实和合成数据的大规模实验证明了我们算法的性能。