Don’t Follow Reinforcement Learning Blindly: Lower Sample Complexity of Learning Optimal Inventory Control Policies with Fixed Ordering Cost

Abstract

We study the sample complexity of offline learning for a class of structured Markov decision processes (MDPs) describing the inventory control system with fixed ordering cost/setup cost, a fundamental problem in supply chains. We find that a naive plug-in sampling-based approach applied to the inventory MDPs leads to strictly lower sample complexity bounds compared to the optimal bounds recently obtained for the general MDPs. More specifically, in the infinite-horizon discounted cost setting, we obtain an $\tilde{O}(min\{\frac{(\overline{S}-\underset{\_}{s}{)}^2}{(1-\gamma {)}^2{ϵ}^2},\frac{1}{(1-\gamma {)}^4{ϵ}^2}\})$ sample complexity bound, where ${(\overline{S}-\underset{\_}{s})}^2$ corresponds to the number of state-action pairs in a generic MDP with state space $\mathcal{S}$ and action space $\mathcal{A}$ . As such, $\tilde{O}\left(\frac{(\overline{S}-\underset{\_}{s}{)}^2}{(1-\gamma {)}^2{ϵ}^2}\right)$ improves on the optimal generic reinforcement learning (RL) bound $\tilde{\mathrm{\Theta }}\left(\frac{(\overline{S}-\underset{\_}{s}{)}^2}{(1-\gamma {)}^3{ϵ}^2}\right)$ (when directly applying $\tilde{\mathrm{\Theta }}\left(\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma {)}^3{ϵ}^2}\right)$ here) by a factor of $(1-\gamma {)}^{-1}$ , and $\tilde{O}\left(\frac{1}{(1-\gamma {)}^4{ϵ}^2}\right)$ is able to completely remove the dependence on state and action cardinality. In the infinite-horizon average cost setting, we obtain an $\tilde{O}\left(\frac{(\overline{S}-\underset{\_}{s}{)}^2}{{ϵ}^2}\right)$ bound, improving on the generic optimal RL bound $\tilde{\mathrm{\Theta }}\left(\frac{(\overline{S}-\underset{\_}{s}{)}^2{t}_{mix}}{{ϵ}^2}\right)$ (when directly applying $\tilde{\mathrm{\Theta }}\left(\frac{|\mathcal{S}||\mathcal{A}|t_{mix}}{{ϵ}^2}\right)$ here) by a factor of $t_{mix}$ , and hence removing the mixing time dependence. By carefully leveraging the structural properties of the inventory dynamics in various settings, we are able to improve on those “best-possible” bounds developed in the RL literature. Our results demonstrate the drawbacks one could face by blindly following RL algorithms and the necessity of designing sample efficient algorithms that properly incorporate the special structures of the inventory systems.