# Contextual Decision-Making with Knapsacks Beyond the Worst Case

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 43 references that are in the map.
- First posted on arXiv 25 Nov 2022.

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

- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Practical Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/1803.01088/) (2018)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Resourceful Contextual Bandits](https://mlsanity.com/paper/1402.6779/) (2014)
- [An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives](https://mlsanity.com/paper/1506.03374/) (2015)
- [Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds](https://mlsanity.com/paper/1909.05499/) (2019)
- [Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression](https://mlsanity.com/paper/2211.07484/) (2022)
- [Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits](https://mlsanity.com/paper/1504.06937/) (2015)
- [Uniformly bounded regret in the multi-secretary problem](https://mlsanity.com/paper/1710.07719/) (2017)
- [A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management](https://mlsanity.com/paper/1802.06192/) (2018)
- [Online Allocation and Pricing: Constant Regret via Bellman Inequalities](https://mlsanity.com/paper/1906.06361/) (2019)
- [The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks](https://mlsanity.com/paper/2102.06385/) (2021)
- [Structured Linear Contextual Bandits: A Sharp and Geometric Smoothed Analysis](https://mlsanity.com/paper/2002.11332/) (2020)
- [The Bayesian Prophet: A Low-Regret Framework for Online Decision Making](https://mlsanity.com/paper/1901.05028/) (2019)
- [An Improved Analysis of LP-based Control for Revenue Management](https://mlsanity.com/paper/2101.11092/) (2021)
- [Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions](https://mlsanity.com/paper/2210.07996/) (2022)
- [Online Contextual Decision-Making with a Smart Predict-then-Optimize Method](https://mlsanity.com/paper/2206.07316/) (2022)
- [Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oracles](https://mlsanity.com/paper/2210.11834/) (2022)
- [Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations](https://mlsanity.com/paper/1912.08917/) (2019)
- [Logarithmic regret bounds for Bandits with Knapsacks](https://mlsanity.com/paper/1510.01800/) (2015)
- [Bandits with Knapsacks beyond the Worst-Case](https://mlsanity.com/paper/2002.00253/) (2020)
- [Best of Many Worlds Guarantees for Online Learning with Knapsacks](https://mlsanity.com/paper/2202.13710/) (2022)

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

- [Learning to Price with Resource Constraints: From Full Information to Machine-Learned Prices](https://mlsanity.com/paper/2501.14155/) (2025)
- [Small Total-Cost Constraints in Contextual Bandits with Knapsacks, with Application to Fairness](https://mlsanity.com/paper/2305.15807/) (2023)
- [Episodic Contextual Bandits with Knapsacks under Conversion Models](https://mlsanity.com/paper/2507.06859/) (2025)

## Abstract (arXiv)

We study the framework of a dynamic decision-making scenario with resource constraints. In this framework, an agent, whose target is to maximize the total reward under the initial inventory, selects an action in each round upon observing a random request, leading to a reward and resource consumptions that are further associated with an unknown random external factor. While previous research has already established an widetildeO(√T) worst-case regret for this problem, this work offers two results that go beyond the worst-case perspective: one for the worst-case gap between benchmarks and another for logarithmic regret rates. We first show that an Omega(√T) distance between the commonly used fluid benchmark and the online optimum is unavoidable when the former has a degenerate optimal solution. On the algorithmic side, we merge the re-solving heuristic with distribution estimation skills and propose an algorithm that achieves an widetildeO(1) regret as long as the fluid LP has a unique and non-degenerate solution. Furthermore, we prove that our algorithm maintains a near-optimal widetildeO(√T) regret even in the worst cases and extend these results to the setting where the request and external factor are continuous. Regarding information structure, our regret results are obtained under two feedback models, respectively, where the algorithm accesses the external factor at the end of each round and at the end of a round only when a non-null action is executed.