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>