Abstract
In inventory management, the transition from model-based to model-free approaches has highlighted a critical need for theoretical guarantees on policy performance. This paper applies Vapnik-Chervonenkis (VC) theory to provide the first near-tight generalization guarantees for classical inventory policies like base-stock and $(s, S)$. We demonstrate that non-stationary base-stock policies exhibit "horizon-free" estimation error—error that does not grow with the time horizon $T$. This result challenges the conventional wisdom that longer planning horizons necessarily require significantly more data for effective learning.
Introduction
Inventory management practitioners traditionally rely on a two-step "model-based" approach: estimating demand distributions from historical data and then solving a dynamic program (DP). However, this method often falters under model misspecification or temporal demand correlation. Recent shifts toward Reinforcement Learning (RL) offer "model-free" alternatives but often result in "black box" policies that are unstable with limited data.
This paper explores a hybrid approach: constrained Empirical Risk Minimization (ERM). By restricting the policy space to well-structured, interpretable classes (e.g., base-stock), we investigate the fundamental question: How much data is required to ensure these policies perform well on unseen demand?
Methodology
The authors utilize tools from statistical learning theory—specifically VC-dimension, Pseudo-dimension, and Fat-shattering (Pseudo-$\gamma$) dimension—to bound the Generalization Error (GE). The GE represents the gap between a policy's performance on training data versus its real-world performance.
Key technical components include:
- Trajectory-based ERM: Optimizing policies directly over $N$ historical demand sequences rather than estimating distributions.
- Dual-class Analysis: Analyzing the sensitivity of inventory state transitions to policy parameters.
- Pseudo-$\gamma$ Dimension: Employing a refined margin-based complexity measure for non-stationary policies to achieve tighter bounds.
Theoretical Insights
The "Horizon-Free" Surprise
A non-stationary base-stock policy ($S^t$) involves $T$ distinct parameters. Intuitively, one might expect the complexity to scale with $T$. However, the authors prove the estimation error is $\Theta(\sqrt{1/N})$, independent of the time horizon $T$. The inherent structure of the inventory problem limits overfitting, regardless of the number of periods.
Structure vs. Parameter Count
Interestingly, the stationary $(s, S)$ policy, which has only two parameters, possesses a higher complexity bound ($O(\sqrt{\log T / N})$) than the $T$-parameter base-stock policy. This underscores that the mathematical structure of the policy class is a more significant driver of complexity than the raw number of variables.
"Learning Less is More"
In data-scarce environments, simpler policy classes (like stationary base-stock) often outperform more flexible ones. While flexible classes may have lower approximation error, their higher estimation error can lead to significant overfitting and poor real-world performance.
Key Results
The paper provides nearly-tight characterizations of the expected Generalization Error across different policy classes. A comparison with existing literature highlights the significance of the "horizon-free" result.
Numerical simulations validate these rates. For $S^t$ policies, the regret relative to the optimal policy increased by only approximately 8% as the horizon $T$ grew from 1 to 100, confirming the theoretical $T$-independence.
Limitations and Future Work
While these results provide a strong foundation, several areas remain for future exploration:
- Lead Times and Backlogging: The current analysis assumes deterministic lead times and backlogged demand. Extending this to lost-sales models or stochastic lead times is a key challenge.
- Censored Demand: The model assumes full visibility of historical demand, whereas real-world data is often "censored" (limited to sales data).
- Fixed Costs: The horizon-free result for non-stationary policies assumes no fixed ordering costs ($K=0$). When $K > 0$, complexity may indeed scale with $T$, suggesting that fixed costs fundamentally alter the learning landscape.
Summary updated