Improved Approximation Guarantees for Periodic-Review Stochastic Inventory Control
Abstract
In periodic-review stochastic inventory control, replenishment policies must balance holding and backlogging costs while responding to uncertain demands and evolving forecasts that may be arbitrarily correlated and nonstationary. In this general information setting, Levi, P{á}l, Roundy, and Shmoys (Mathematics of Operations Research 2007) established that the fully adaptive optimum can be approximated within factor $2$, which had remained the best-known performance guarantee since then. Their marginal cost accounting and dual-balancing framework made this comparison possible without computing optimal decisions across future trajectories, opening a broad research program on approximation algorithms for stochastic inventory systems. We break this long-standing barrier for periodic-review stochastic inventory control, showing how to compete against the fully adaptive benchmark within factor ( e )/( e−1 ) ≈ 1.582 while retaining general demand correlations and evolving forecasts. We attain these advances by discovering a structural connection between marginal inventory accounting and weighted stopping problems, where each unit's conditional holding charge forms a supermartingale, while postponing its order incurs a history-dependent backlog charge. To leverage the random thresholding approach of Ma and Tzamos (ICML 2023) in this context, we develop a potential-function analysis, leading to an ( e )/( e−1 )-approximation with respect to any unit's stopping problem. Subsequently, our common-threshold policy coordinates these marginal decisions into a global replenishment policy without additional loss.
Related
- Periodic measures for time-inhomogeneous stochastic differential equations driven by multiplicative α-stable processes: Existence, uniqueness and numerical approximation
- Improved Guarantees for Langevin Monte Carlo with Average Smoothness
- Towards Optimal Inventory Control under Censored Demand: A Biased Sample-Average Approximation Approach
- Diffusion Flow Matching: Dimension-Improved KL Bounds and Wasserstein Guarantees
- Learning Representations through Token Prediction: Geometry, Approximation, and Downstream Guarantees
BibTeX
@misc{segev2026improved,
title = {{Improved Approximation Guarantees for Periodic-Review Stochastic Inventory Control}},
author = {Danny Segev},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41475},
eprint = {2610.41475},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41475},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Improved Approximation Guarantees for Periodic-Review Stochastic Inventory Control
AU - Danny Segev
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41475
UR - https://arxiv.org/abs/2610.41475
AB - In periodic-review stochastic inventory control, replenishment policies must balance holding and backlogging costs while responding to uncertain demands and evolving forecasts that may be arbitrarily correlated and nonstationary. In this general information setting, Levi, P{á}l, Roundy, and Shmoys (Mathematics of Operations Research 2007) established that the fully adaptive optimum can be approximated within factor $2$, which had remained the best-known performance guarantee since then. Their marginal cost accounting and dual-balancing framework made this comparison possible without computing optimal decisions across future trajectories, opening a broad research program on approximation algorithms for stochastic inventory systems. We break this long-standing barrier for periodic-review stochastic inventory control, showing how to compete against the fully adaptive benchmark within factor ( e )/( e−1 ) ≈ 1.582 while retaining general demand correlations and evolving forecasts. We attain these advances by discovering a structural connection between marginal inventory accounting and weighted stopping problems, where each unit's conditional holding charge forms a supermartingale, while postponing its order incurs a history-dependent backlog charge. To leverage the random thresholding approach of Ma and Tzamos (ICML 2023) in this context, we develop a potential-function analysis, leading to an ( e )/( e−1 )-approximation with respect to any unit's stopping problem. Subsequently, our common-threshold policy coordinates these marginal decisions into a global replenishment policy without additional loss.
ER -