# Online Linear Programming with Replenishment

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jan 2026.

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

- [Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving](https://mlsanity.com/paper/2609.28263/) (2026)

## Abstract (arXiv)

We study an online linear programming (OLP) model in which inventory is not provided upfront but instead arrives gradually through an exogenous stochastic replenishment process. This replenishment-based formulation captures operational settings, such as e-commerce fulfillment, perishable supply chains, and renewable-powered systems, where resources are accumulated gradually and initial inventories are small or zero. The introduction of dispersed, uncertain replenishment fundamentally alters the structure of classical OLPs, creating persistent stockout risk and eliminating advance knowledge of the total budget. We develop new algorithms and regret analyses for three major distributional regimes studied in the OLP literature: bounded distributions, finite-support distributions, and continuous-support distributions with a non-degeneracy condition. For bounded distributions, we design an algorithm that achieves widetildeO(√T) regret. For finite-support distributions with a non-degenerate induced LP, we obtain O(log T) regret, and we establish an Omega(√T) lower bound for degenerate instances, demonstrating a sharp separation from the classical setting where O(1) regret is achievable. For continuous-support, non-degenerate distributions, we develop a two-stage accumulate-then-convert algorithm that achieves O(log2 T) regret, comparable to the O(log T) regret in classical OLPs. Together, these results provide a near-complete characterization of the optimal regret achievable in OLP with replenishment. Finally, we empirically evaluate our algorithms and demonstrate their advantages over natural adaptations of classical OLP methods in the replenishment setting.