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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mrow> <mml:mover> <mml:mi>O</mml:mi> <mml:mo stretchy="false">~</mml:mo> </mml:mover> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mo form="prefix" movablelimits="true">min</mml:mo> <mml:mrow> <mml:mo>{</mml:mo> <mml:mfrac> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mover> <mml:mi>S</mml:mi> <mml:mo accent="false">¯</mml:mo> </mml:mover> <mml:mo>−</mml:mo> <mml:munder> <mml:mi>s</mml:mi> <mml:mo>_</mml:mo> </mml:munder> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>−</mml:mo> <mml:mi>γ</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mn>2</mml:mn> </mml:msup> <mml:msup> <mml:mi>ϵ</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> </mml:mfrac> <mml:mo>,</mml:mo> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>−</mml:mo> <mml:mi>γ</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mn>4</mml:mn> </mml:msup> <mml:msup> <mml:mi>ϵ</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> </mml:mfrac> <mml:mo>}</mml:mo> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> sample complexity bound, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mover> <mml:mi>S</mml:mi> <mml:mo accent="false">¯</mml:mo> </mml:mover> <mml:mo>−</mml:mo> <mml:munder> <mml:mi>s</mml:mi> <mml:mo>_</mml:mo> </mml:munder> <mml:mo>)</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:msup> </mml:math> corresponds to the number of state-action pairs in a generic MDP with state space <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mrow> <mml:mi mathvariant="script">S</mml:mi> </mml:mrow> </mml:math> and action space <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mrow> <mml:mi mathvariant="script">A</mml:mi> </mml:mrow> </mml:math> . As such, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mrow> <mml:mover> <mml:mi>O</mml:mi> <mml:mo stretchy="false">~</mml:mo> </mml:mover> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mfrac> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mover> <mml:mi>S</mml:mi> <mml:mo accent="false">¯</mml:mo> </mml:mover> <mml:mo>−</mml:mo> <mml:munder> <mml:mi>s</mml:mi> <mml:mo>_</mml:mo> </mml:munder> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>−</mml:mo> <mml:mi>γ</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mn>2</mml:mn> </mml:msup> <mml:msup> <mml:mi>ϵ</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> </mml:mfrac> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> improves on the optimal generic reinforcement learning (RL) bound <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mrow> <mml:mover> <mml:mi mathvariant="normal">Θ</mml:mi> <mml:mo stretchy="false">~</mml:mo> </mml:mover> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mfrac> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mover> <mml:mi>S</mml:mi> <mml:mo accent="false">¯</mml:mo> </mml:mover> <mml:mo>−</mml:mo> <mml:munder> <mml:mi>s</mml:mi> <mml:mo>_</mml:mo> </mml:munder> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>−</mml:mo> <mml:mi>γ</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mn>3</mml:mn> </mml:msup> <mml:msup> <mml:mi>