# Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Sep 2018.

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

- [Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions](https://mlsanity.com/paper/2210.07996/) (2022)
- [Dynamic Budget Throttling in Repeated Second-Price Auctions](https://mlsanity.com/paper/2207.04690/) (2022)
- [Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions](https://mlsanity.com/paper/2401.01077/) (2024)
- [Constrained Online Two-stage Stochastic Optimization: Near Optimal Algorithms via Adversarial Learning](https://mlsanity.com/paper/2302.00997/) (2023)
- [Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates](https://mlsanity.com/paper/2607.02150/) (2026)
- [Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints](https://mlsanity.com/paper/2608.11383/) (2026)

## Abstract (arXiv)

We study a dynamic and stochastic knapsack problem in which a decision maker is sequentially presented with items arriving according to a Bernoulli process over n discrete time periods. Items have equal rewards and independent weights that are drawn from a known non-negative continuous distribution F. The decision maker seeks to maximize the expected total reward of the items that she includes in the knapsack while satisfying a capacity constraint and while making terminal decisions as soon as each item weight is revealed. Under mild regularity conditions on the weight distribution F, we prove that the regret---the expected difference between the performance of the best sequential algorithm and that of a prophet who sees all of the weights before making any decision---is, at most, logarithmic in n. Our proof is constructive. We devise a reoptimized heuristic that achieves this regret bound.