# Learning in structured MDPs with convex cost functions: Improved regret bounds for inventory management

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 May 2019.

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

- [Hindsight Learning for MDPs with Exogenous Inputs](https://mlsanity.com/paper/2207.06272/) (2022)
- [Optimistic Q-learning for average reward and episodic reinforcement learning](https://mlsanity.com/paper/2407.13743/) (2024)
- [Learning and Information in Stochastic Networks and Queues](https://mlsanity.com/paper/2105.08769/) (2021)
- [VC Theory for Inventory Policies](https://mlsanity.com/paper/2404.11509/) (2024)
- [Stateful Offline Contextual Policy Evaluation and Learning](https://mlsanity.com/paper/2110.10081/) (2021)
- [Deep Policy Iteration with Integer Programming for Inventory Management](https://mlsanity.com/paper/2112.02215/) (2021)
- [Learning to Order for Inventory Systems with Lost Sales and Uncertain Supplies](https://mlsanity.com/paper/2207.04550/) (2022)
- [Non-stationary Reinforcement Learning under General Function Approximation](https://mlsanity.com/paper/2306.00861/) (2023)
- [Understanding the Training and Generalization of Pretrained Transformer for Sequential Decision Making](https://mlsanity.com/paper/2405.14219/) (2024)
- [Learning-based Optimal Admission Control in a Single Server Queuing System](https://mlsanity.com/paper/2212.11316/) (2022)
- [Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning](https://mlsanity.com/paper/2409.14557/) (2024)
- [ICNN-enhanced 2SP: Leveraging input convex neural networks for solving two-stage stochastic programming](https://mlsanity.com/paper/2505.05261/) (2025)
- [Restarted Bayesian Online Change-point Detection for Non-Stationary Markov Decision Processes](https://mlsanity.com/paper/2304.00232/) (2023)
- [Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space](https://mlsanity.com/paper/2306.02574/) (2023)
- [Deep Optimal Timing Strategies for Time Series](https://mlsanity.com/paper/2310.05479/) (2023)
- [Learning to Admit Optimally in an M/M/k/k+N Queueing System with Unknown Service Rate](https://mlsanity.com/paper/2202.02419/) (2022)
- [Thompson Sampling for Repeated Newsvendor](https://mlsanity.com/paper/2502.09900/) (2025)
- [Zero-shot Generalization in Inventory Management: Train, then Estimate and Decide](https://mlsanity.com/paper/2411.00515/) (2024)
- [DAL: A Practical Prior-Free Black-Box Framework for Piecewise Stationary Bandits](https://mlsanity.com/paper/2501.19401/) (2025)
- [Adaptive Bounded Exploration and Intermediate Actions for Data Debiasing](https://mlsanity.com/paper/2504.08151/) (2025)
- [Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation?](https://mlsanity.com/paper/2601.20694/) (2026)
- [DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees](https://mlsanity.com/paper/2604.16684/) (2026)

## Abstract (arXiv)

We consider a stochastic inventory control problem under censored demands, lost sales, and positive lead times. This is a fundamental problem in inventory management, with significant literature establishing near-optimality of a simple class of policies called ``base-stock policies'' for the underlying Markov Decision Process (MDP), as well as convexity of long run average-cost under those policies. We consider the relatively less studied problem of designing a learning algorithm for this problem when the underlying demand distribution is unknown. The goal is to bound regret of the algorithm when compared to the best base-stock policy. We utilize the convexity properties and a newly derived bound on bias of base-stock policies to establish a connection to stochastic convex bandit optimization. Our main contribution is a learning algorithm with a regret bound of tildeO(L√T+D) for the inventory control problem. Here L is the fixed and known lead time, and D is an unknown parameter of the demand distribution described roughly as the number of time steps needed to generate enough demand for depleting one unit of inventory. Notably, even though the state space of the underlying MDP is continuous and L-dimensional, our regret bounds depend linearly on L. Our results significantly improve the previously best known regret bounds for this problem where the dependence on L was exponential and many further assumptions on demand distribution were required. The techniques presented here may be of independent interest for other settings that involve large structured MDPs but with convex cost functions.