# Online Contextual Decision-Making with a Smart Predict-then-Optimize Method

arXiv: https://arxiv.org/abs/2206.07316 · HTML: https://mlsanity.com/paper/2206.07316/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 29 references that are in the map.
- First posted on arXiv 15 Jun 2022.

## Builds on (most cited first, 17 of 17)

- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [From Predictive to Prescriptive Analytics](https://mlsanity.com/paper/1402.5481/) (2014)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Stochastic Bandits with Linear Constraints](https://mlsanity.com/paper/2006.10185/) (2020)
- [Adaptive Algorithms for Online Convex Optimization with Long-term Constraints](https://mlsanity.com/paper/1512.07422/) (2015)
- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [Generalization Bounds in the Predict-then-Optimize Framework](https://mlsanity.com/paper/1905.11488/) (2019)
- [Resourceful Contextual Bandits](https://mlsanity.com/paper/1402.6779/) (2014)
- [Fast Rates for Contextual Linear Optimization](https://mlsanity.com/paper/2011.03030/) (2020)
- [Fast Algorithms for Online Stochastic Convex Programming](https://mlsanity.com/paper/1410.7596/) (2014)
- [Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds](https://mlsanity.com/paper/1909.05499/) (2019)
- [Risk Bounds and Calibration for a Smart Predict-then-Optimize Method](https://mlsanity.com/paper/2108.08887/) (2021)
- [Risk Guarantees for End-to-End Prediction and Optimization Processes](https://mlsanity.com/paper/2012.15046/) (2020)
- [Joint Online Learning and Decision-making via Dual Mirror Descent](https://mlsanity.com/paper/2104.09750/) (2021)

## Built on by (most cited first, 12 of 12)

- [Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oracles](https://mlsanity.com/paper/2210.11834/) (2022)
- [Dissecting the Impact of Model Misspecification in Data-driven Optimization](https://mlsanity.com/paper/2503.00626/) (2025)
- [Contextual Decision-Making with Knapsacks Beyond the Worst Case](https://mlsanity.com/paper/2211.13952/) (2022)
- [Learning to Price with Resource Constraints: From Full Information to Machine-Learned Prices](https://mlsanity.com/paper/2501.14155/) (2025)
- [Efficient End-to-End Learning for Decision-Making: A Meta-Optimization Approach](https://mlsanity.com/paper/2505.11360/) (2025)
- [The Bias-Variance Tradeoff in Data-Driven Optimization: A Local Misspecification Perspective](https://mlsanity.com/paper/2510.18215/) (2025)
- [Dynamic Budget Throttling in Repeated Second-Price Auctions](https://mlsanity.com/paper/2207.04690/) (2022)
- [Learning Decision-Sufficient Representations for Linear Optimization](https://mlsanity.com/paper/2603.18551/) (2026)
- [Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback](https://mlsanity.com/paper/2606.01081/) (2026)
- [Decision-Focused Learning: When and Why Traditional Prediction Models Fail](https://mlsanity.com/paper/2606.21773/) (2026)
- [BOCO: Bayesian Online Contextual Optimization for Decision-Focused Online Learning](https://mlsanity.com/paper/2511.20413/) (2025)
- [The Value of Information in Resource-Constrained Pricing](https://mlsanity.com/paper/2603.24974/) (2026)

## Abstract (arXiv)

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 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.