Contextual Linear Optimization with Partial Feedback
Yichun Hu, Nathan Kallus, Xiaojie Mao, Yanchen Wu
情境线性优化(CLO)使用预测性上下文特征来降低目标中随机成本系数的不确定性,从而提高决策性能。 一个规范的例子是随机的最短路径问题,随机边缘成本(例如,旅行时间)和上下文特征(例如,滞后的交通,天气)。 虽然CLO的现有工作假设完全观察到的成本系数向量,但在许多应用中,决策者只观察到与历史上每个选择的决策相应的部分反馈。 在本文中,我们研究土匪反馈设置(例如,仅观察到每个历史路径的整体旅行时间)和半土匪反馈设置(例如,还观察到每个选定路径上各个段的旅行时间)。 我们提出了具有不同类型反馈的CLO的统一离线学习算法,遵循强大的诱导经验风险最小化(IERM)框架,该框架集成了估计和优化。 我们为 IERM 提供了一种新的快速后悔,允许错误指定的模型类和灵活的估计方法选择。 为了解决部分反馈的IERM,我们还量身定制了可计算处理的代理损失。 我们独立兴趣理论的一个副产品是IERM的快率遗憾,具有完整的反馈和错误指定的政策类。 我们使用模拟和真实数据上的随机最短路径示例,以数值方式比较不同方法的性能,并提供经验结果的实际见解。
Contextual linear optimization (CLO) uses predictive contextual features to reduce uncertainty in random cost coefficients in the objective and thereby improve decision-making performance. A canonical example is the stochastic shortest path problem with random edge costs (e.g., travel time) and contextual features (e.g., lagged traffic, weather). While existing work on CLO assumes fully observed cost coefficient vectors, in many applications the decision maker observes only partial feedback corr...