Online Contextual Decision-Making with a Smart Predict-then-Optimize Method
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.