Online Contextual Decision-Making with a Smart Predict-then-Optimize Method
This work addresses decision-making under uncertainty for resource-constrained systems, offering a general framework that is incremental in extending SPO methods to online settings.
The paper tackles the online contextual decision-making problem with resource constraints by proposing an algorithm that combines Smart Predict-then-Optimize with mirror descent, achieving regret bounds with a convergence rate of O(T^{-1/2}) and demonstrating empirical improvements over traditional methods on knapsack and longest path instances.
We study an online contextual decision-making problem with resource constraints. At each time period, the decision-maker first predicts a reward vector and resource consumption matrix based on a given context vector and then solves a downstream optimization problem to make a decision. The final goal of the decision-maker is to maximize the summation of the reward and the utility from resource consumption, while satisfying the resource constraints. We propose an algorithm that mixes a prediction step based on the "Smart Predict-then-Optimize (SPO)" method with a dual update step based on mirror descent. We prove regret bounds and demonstrate that the overall convergence rate of our method depends on the $\mathcal{O}(T^{-1/2})$ convergence of online mirror descent as well as risk bounds of the surrogate loss function used to learn the prediction model. Our algorithm and regret bounds apply to a general convex feasible region for the resource constraints, including both hard and soft resource constraint cases, and they apply to a wide class of prediction models in contrast to the traditional settings of linear contextual models or finite policy spaces. We also conduct numerical experiments to empirically demonstrate the strength of our proposed SPO-type methods, as compared to traditional prediction-error-only methods, on multi-dimensional knapsack and longest path instances.