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 corresponding to each chosen decision in the history. In this paper, we study both a bandit-feedback setting (e.g., only the overall travel time of each historical path is observed) and a semi-bandit-feedback setting (e.g., travel times of the individual segments on each chosen path are additionally observed). We propose a unified class of offline learning algorithms for CLO with different types of feedback, following a powerful induced empirical risk minimization (IERM) framework that integrates estimation and optimization. We provide a novel fast-rate regret bound for IERM that allows for misspecified model classes and flexible choices of estimation methods. To solve the partial-feedback IERM, we also tailor computationally tractable surrogate losses. A byproduct of our theory of independent interest is the fast-rate regret bound for IERM with full feedback and a misspecified policy class. We compare the performance of different methods numerically using stochastic shortest path examples on simulated and real data and provide practical insights from the empirical results.

翻译：情境线性优化（CLO）利用预测性情境特征来减少目标函数中随机成本系数的不确定性，从而提升决策性能。一个典型例子是带有随机边成本（如行程时间）和情境特征（如滞后交通量、天气）的随机最短路径问题。现有CLO研究通常假设成本系数向量可完全观测，但在许多实际应用中，决策者仅能观测到历史中每个选定决策对应的部分反馈。本文研究了两种反馈设置：老虎机反馈设置（例如仅观测每条历史路径的总行程时间）和半老虎机反馈设置（例如额外观测每条选定路径上各分段的行程时间）。我们提出了一类统一的离线学习算法，用于处理具有不同类型反馈的CLO问题，该算法遵循一个强大的诱导经验风险最小化（IERM）框架，该框架整合了估计与优化过程。我们为IERM提供了新颖的快速收敛遗憾界理论，该理论允许模型类别存在误设且支持灵活的估计方法选择。针对部分反馈的IERM问题，我们还设计了计算可行的代理损失函数。理论推导的一个独立副产品是：针对完全反馈与误设策略类别的IERM快速收敛遗憾界。我们通过随机最短路径案例在模拟数据与真实数据上的数值实验，比较了不同方法的性能，并从实证结果中提炼出具有实践指导意义的见解。