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

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 O ~ ( min { ( S ¯ − s _ ) 2 ( 1 − γ ) 2 ϵ 2 , 1 ( 1 − γ ) 4 ϵ 2 } ) sample complexity bound, where ( S ¯ − s _ ) 2 corresponds to the number of state-action pairs in a generic MDP with state space S and action space A . As such, O ~ ( ( S ¯ − s _ ) 2 ( 1 − γ ) 2 ϵ 2 ) improves on the optimal generic reinforcement learning (RL) bound Θ ~ ( ( S ¯ − s _ ) 2 ( 1 − γ ) 3