5.10 Hitting problems with applications in single-item inventory control
5.10 Hitting problems with applications in single-item inventory control
In a single-item inventory under period review and controlled by an \((s,S)\) policy, every time the inventory position becomes \(s\) or lower, a replenishment up to state \(S\) is placed at cost \(K.\)1If you don’t like challenges, you can skip this section. When the position is at \(x > s,\) the inventory cost is \(L(x),\) see (5.9.1). Typically, we are interested in the long-run average cost when the position starts at \(S\) and stops when getting at or below \(s.\) By the renewal reward theorem, it suffices to compute the expected cost \(v(s,S)\) and expected time \(T(s,S)\) of one cycle that starts at \(S\) and stops at \(x\leq s.\) The long-run average cost is then given by \(v(s,S)/T(s,S).\)
Both \(v(s,S)\) and \(T(s,S)\) can be found as the solution of a hitting problem. The stopping set is \(x \leq s.\) When in state \(x>s,\) the continuation (or running) cost for \(v\) is, as said, \(L(x),\) and \(1\) for \(T,\) because it costs 1 period to stay 1 period in state \(x.\) The stopping cost for \(v\) is the ordering cost \(K,\) and it is \(0\) for \(T,\) because once stopped, time no longer progresses.
Below we discuss a general algorithm to numerically solve such hitting problems.
A bit of theory helps to set up this algorithm. We start with a discrete Markov chain \(X = \set{X_k, k \geq 0}\) with a reasonably small state space, e.g., at most several thousand states.2Otherwise we should resort to other numerical methods. The state space is split into two disjoint sets \(C\) and \(D.\) When \(X_k \in C,\) the process continues, while if \(X_k \in D,\) it stops. Define the stopping time \(\tau = \inf\set{ k : X_k \in D},\) and assume that the transition probabilities \(P(x,y)\) of \(X\) are such that the chain gets absorbed in \(D\) in finite expected time, that is, \(\EE{x}{\tau} < \infty\) for all possible initial states \(x.\) We write \(\tilde L(x) = L(x) \1{x\in C} + K \1{x\in D}\) for the cost associated with spending a period or stopping in state \(x.\) The interesting question is to ask: What is the expected cost until the process stops?3For suitable conditions on \(c,\) see for instance, Dynkin and Yushkevich 1968.
Focus first on some state \(y,\) then, when starting in \(x,\) \(\EE{x}{\sum_{t=0}^{\tau} \1{X_{t} = y} \tilde L(y)}\) is the expected cost for spending time in, or hitting, state \(y.\) With this, we write the total cost until stopping as
\begin{align*} v(x) = \sum_{y} \EE{x}{\sum_{t=0}^{\tau} \1{X_{t} = y} \tilde L(y)}. \end{align*}By splitting the expectation and taking the summation over \(t\) out of the expectation we obtain a very useful expression for \(v\):
\begin{align*} v(x) &= \sum_{y} g(x, y) \tilde L(y), \end{align*}where \(g,\) known as Green’s kernel, is given by
\begin{align*} g(x, y) = \sum_{t=0}^{\infty} \EE{x}{\1{X_{t} = y, t \leq \tau}}. \end{align*}It represents the expected number of visits to \(y\) until absorption when the chain starts at \(x.\) In terms of probabilities, \(g\) can be written as4Use that \(\E{\1{A}} = \P A\) for an indicator event \(A.\)
\begin{align*} g(x, y) &= \sum_{t=0}^{\infty} \PP{x}{X_{t} = y, t \leq \tau}. \tag{5.10.1} \end{align*}Finally, if \(X\) can start at some state \(x\) with probability \(\mu_x,\) the expected number of visits to \(y\) becomes
\begin{align*} g(y) = \sum_x \mu_x g(x,y). \tag{5.10.2} \end{align*}The following seemingly simple, and certainly short, algorithm computes \(g\) as defined in (5.10.2).
\begin{algorithm}
\caption{Compute expected visits to states before absorption.}
\begin{algorithmic}[1]
\State \textbf{Input:} a map of initial probabilities \(\mu,\) transitions \(P(x),\) a stopping rule \(\pr{stop?},\) cutoff \(\varepsilon\).
\State \textbf{Output:} expected visits \(g\).
\Function{Green}{\(\mu,\, P,\, \pr{stop?},\, \varepsilon\)}
\State \(g\gets\pr{Map}()\)
\While{\(\pr{Keys}(\mu)\neq\emptyset\)}
\State \(\var{states}\gets\pr{Keys}(\mu)\)
\For{\(x\in\var{states}\)}
\State \(p\gets\mu(x)\)
\State \(g(x)\xleftarrow{+}p\)
\State \(\mu(x)\gets0\)
\If{\(\neg\pr{stop?}(x)\)}
\For{\((y,\, p_{xy})\in P(x)\)}
\State \(\mu(y)\xleftarrow{+}p\cdot p_{xy}\)
\EndFor
\EndIf
\EndFor
\State \(\mu\gets\pr{FilterValues}\rb{\mu,\, \lambdafun{p}{p>\varepsilon}}\)
\EndWhile
\Return \(g\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Before explaining how this works, we discuss this function’s arguments. The input map \(\mu\) maps a state \(x\) to the initial probability \(\mu(x)\) of that state. For instance, when the process starts (almost) surely at \(X_0=x,\) we set \(\mu(x)\gets1.\) Next, \(P(x)\) returns a list of pairs \((y,p_{xy}),\) where \(y\) is a state to which \(X\) can move from \(x\) and \(p_{xy}\) is the probability of that transition. The rule \(\pr{stop?}(x)\) is true when the chain should stop (is absorbed) at \(x,\) and false otherwise. Finally, \(\varepsilon\) is a small number that prevents keeping states that have negligible probability of being accessed.
So, intuitively speaking, how does this algorithm work? As long as not all probability mass has been absorbed5That is, \(\pr{Keys}(\mu)\) is not yet empty., a for loop cycles over the states \(x\) currently in the map. The map \(g\) counts the expected number of visits to a state \(x\) and is updated in every round of the loop. We fix the range of the for loop by storing \(\pr{Keys}(\mu)\) in \(\var{states},\) because the keys of \(\mu\) can change in the body of the loop. When \(x\) is processed, \(\mu(x)\) is the probability mass waiting to be processed at \(x.\) In accordance with (5.10.1), we add this probability to the expected total number of visits \(g(x)\) and assign it to \(p\) for ease.
We set \(\mu(x)\gets0\) for two reasons. When the chain is absorbed (stopped) at \(x,\) we continue with the next state to be checked in the for loop. In this case, the total probability mass should decrease by the absorption probability \(p,\) which is indeed achieved by setting \(\mu(x)\gets0.\) If the chain does not stop at \(x,\) the probability \(p\) should be distributed over all states \(y\) to which \(X\) can transition. If \(y\neq x,\) then \(\mu(y)\xleftarrow{+}p\cdot p_{xy},\) because \(y\) could have been accessed from other states too. When \(y=x,\) the probability of staying in \(x\) is \(p\cdot p_{xy}.\)6Recall that the expected number of consecutive periods to stay in state \(x\) is \(\sim \Geo{p_x}.\) Since we earlier set \(\mu(x)\gets0,\) we can also use \(\mu(x)\xleftarrow{+}p\cdot p_{xx}\) for state \(x.\) In other words, the same update works for all next states, without singling out \(x.\)
Once the for loop completes, \(\mu\) is replaced by a map containing only states with probability greater than \(\varepsilon.\)
There remains, however, a fundamental question: why is it allowed to change \(\mu\) in the for loop itself, and does it really converge to the Green kernel we discussed above?
To really understand why the \(\pr{Green}\) function works, we need to discuss some further ideas of discrete Markov chains. Recall the interpretation of the Green kernel \(g(x,y)\) as the expected number of times \(y\) will be visited up to absorption and when starting in \(X_{0}=x.\) For the stopped process, set \(P(x,y)=0\) whenever \(x\in D.\) Thus a stopping state contributes one visit but has no outgoing transitions. Clearly, using the Markov property, \(g\) should satisfy the recursive expression
\begin{align*} g(x,y) &= \EE{x}{\1{X_{0}=y}} + \EE{x}{g(X_{1}, y)} \\ &\stackrel{1}= \1{x=y} + \sum_{z}\EE{x}{\1{X_{1}=z}} g(z, y) \\ &\stackrel{2}= \1{x=y} + \sum_{z} P(x, z) g(z, y); \end{align*}in 1 we use that \(g(z, y)\) is a constant, hence can be taken out of the expectation, in 2 that \(\EE{x}{\1{X_1=z}} = P(x,z).\) Casting this in matrix format makes this structure clearer:
\begin{align*} G = I + P G. \tag{5.10.3} \end{align*}Then, by using this recursive structure, and noting that \(X\) will be absorbed in some set \(D\) in expected finite time and \(P\) is finite so that \(P^t\) converges geometrically fast to \(0\) elementwise as \(t\to\infty,\)
\begin{align*} G = I + P G = I + P(I + P G) = I + P + P^{2} G = \sum_{t=0}^{n} P^{t} + P^{n+1}G \to \sum_{t=0}^{\infty} P^{t}. \end{align*}And, if we define recursively \(\mu^{t} = \mu^{t-1} P = \mu P^{t},\) so that \(\mu_{y}^{t} = \sum_{x} \mu_{x} P^{t}(x,y),\)
\begin{align*} g(y) = \sum_{x} \mu_{x} \sum_{t=0}^{\infty} P^{t}(x, y) =\sum_{t=0}^{\infty} \mu_{y}^{t}. \end{align*}The advantage of this algorithm over solving \(G = I + PG\) with matrix methods is as follows. The latter is a matrix equation for which we need to specify the size of \(G.\) However, the states that have a reasonable probability of being visited are not yet known. Thus, solving \(G=I+PG\) may include many more or less superfluous states, which is numerically wasteful.
Let us develop a few intermediate algorithms that apply the above ideas to compute \(g(y).\) Note that \(\mu\) is the starting distribution of \(X_0.\) The key part updates \(g\) and \(\mu\) as \(g^{k+1} = g^{k} + \mu^{k},\) and \(\mu^{k+1} \leftarrow \mu^{k} P.\) Thus, after \(k\) iterations, \(g\) equals \(\sum_{t=0}^{k-1} \mu^{t}\) and \(\mu\) equals \(\mu^k.\) In the update of \(\mu\) we prune on too small events. As \(\mu^k\) becomes smaller and smaller as \(k\) increases, eventually, all elements of \(\mu\) become less than \(\varepsilon,\) and the while loop terminates.
\begin{algorithm}
\caption{Compute expected visits by updating visits and probability mass separately.}
\begin{algorithmic}[1]
\State \textbf{Input:} initial probability map \(\mu,\) transitions \(P(x),\) stopping rule \(\pr{stop?},\) cutoff \(\varepsilon\).
\State \textbf{Output:} expected visits \(g\).
\Function{GreenTwoPass}{\(\mu,\, P,\, \pr{stop?},\, \varepsilon\)}
\State \(g\gets\pr{Map}()\)
\While{\(\pr{Keys}(\mu)\neq\emptyset\)}
\For{\(x\in\pr{Keys}(\mu)\)} \Comment{Compute \(g^{t+1}=g^t+\mu^t.\)}
\State \(g(x)\xleftarrow{+}\mu(x)\)
\EndFor
\State \(\var{next}\gets\pr{Map}()\)
\For{\(x\in\pr{Keys}(\mu)\)} \Comment{Compute \(\var{next}=\mu^t P.\)}
\If{\(\neg\pr{stop?}(x)\)}
\For{\((y,\, p_{xy})\in P(x)\)}
\State \(\var{next}(y)\xleftarrow{+}\mu(x)\cdot p_{xy}\)
\EndFor
\EndIf
\EndFor
\State \(\mu\gets\pr{FilterValues}\rb{\var{next},\, \lambdafun{p}{p>\varepsilon}}\) \Comment{Retain mass for \(\mu^{t+1}.\)}
\EndWhile
\Return \(g\)
\EndFunction
\end{algorithmic}
\end{algorithm}
We can combine the updating of \(g\) and \(\var{next}\) in one for loop because these maps do not affect each other in the for loop. Observe that the assignment \(p\gets\mu(x)\) avoids looking up \(\mu(x)\) twice.
\begin{algorithm}
\caption{Compute expected visits with one loop for both updates.}
\begin{algorithmic}[1]
\State \textbf{Input:} initial probability map \(\mu,\) transitions \(P(x),\) stopping rule \(\pr{stop?},\) cutoff \(\varepsilon\).
\State \textbf{Output:} expected visits \(g\).
\Function{GreenCombined}{\(\mu,\, P,\, \pr{stop?},\, \varepsilon\)}
\State \(g\gets\pr{Map}()\)
\While{\(\pr{Keys}(\mu)\neq\emptyset\)}
\State \(\var{next}\gets\pr{Map}()\)
\For{\(x\in\pr{Keys}(\mu)\)}
\State \(p\gets\mu(x)\)
\State \(g(x)\xleftarrow{+}p\) \Comment{Update \(g^{t+1}.\)}
\If{\(\neg\pr{stop?}(x)\)}
\For{\((y,\, p_{xy})\in P(x)\)} \Comment{Accumulate \(\mu^tP\) in \(\var{next}.\)}
\State \(\var{next}(y)\xleftarrow{+}p\cdot p_{xy}\)
\EndFor
\EndIf
\EndFor
\State \(\mu\gets\pr{FilterValues}\rb{\var{next},\, \lambdafun{p}{p>\varepsilon}}\) \Comment{Retain mass for \(\mu^{t+1}.\)}
\EndWhile
\Return \(g\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Observe that in these two algorithms, the while loop first updates \(g^{t+1} = g^{t} + \mu^{t},\) and then computes \(\mu^{t} P\) and prunes small entries to obtain \(\mu^{t+1}.\) In other words, the entire vector \(\mu^{t+1}\) is computed before adding it to \(g^{t+1}\) in the next pass of the while loop.
The next phase in the analysis of \(\pr{Green}\) is to see why it is allowed to update \(\mu\) within the for loop, that is, why \(\pr{Green}\) gives the same value for \(g(y)\) as the above two algorithms. The next theorem answers this.
Theorem 5.10.1.
Let \(P\) be a matrix such that \(G(I - P) = I\) has a solution \(G,\) compare (5.10.3). Assume \(\varepsilon=0,\) so no positive probability mass is pruned. Here \(k\) counts individual state updates, rather than passes through the while loop. If \(g^0=0\) and \(\mu^0 = \mu,\) then \(g^k \to \mu G\) when the update rules of \(\pr{Green}\)
\begin{align*} p &= \mu_{x}^{k}, & g^{k+1} &= g^k + p \delta_x, & \mu^{k+1} &= \mu^k - p \delta_x + p \delta_x P, \end{align*}are applied sequentially for all \(x\) in the support of \(\mu^k.\)
Proof
We first show that the quantity \(H^{k} = g^{k} + \mu^{k}G\) remains the same for all \(k\geq 0\) under the update rules. Using substitution of the update rules,
\begin{align*} H^{k+1} &=g^{k+1} + \mu^{k+1} G &= g^k + p \delta_x + \bigl(\mu^k - p \delta_x + p \delta_x P\bigr) G \\ &= g^k + p \delta_x + \mu^k G - p \delta_x (I - P) G \\ &= g^k + \mu^k G = H^{k}, \end{align*}because \((I - P)G = I,\) cf. (5.10.3). Then, by recursion, \(g^k + \mu^k G = g^0 + \mu^0 G = \mu G\) since \(g^0 = 0\) and \(\mu^0=\mu.\) Since the stopped chain is transient and every state with pending mass is eventually processed, \(\mu^k\to0.\) The invariant \(g^k+\mu^kG=\mu G\) then gives \(g^k\to\mu G.\)
Without pruning, \(\pr{Green}\) gives the same Green kernel as the other algorithms. With \(\varepsilon>0,\) it gives an approximation.
We have some final remarks.
- The advantage of \(\pr{Green}\) is that we do not have to make a guess of the states that will be visited by \(X\) with reasonable probability. When using matrix methods to compute \(G\) such that \(G(I-P) = I,\) we need to expand \(P\) to many states that are irrelevant (up to \(\varepsilon\)).
- In inventory control, the update over \(P\) is often a fixed list. In such cases, it is quite a bit faster to update \(\mu(x-i)\xleftarrow{+}p\cdot\P{D=i}\) for each demand value \(i\) than to pass \(P.\)
- The difference between the, say, regular approaches and \(\pr{Green}\) can be compared to a Jacobi versus Gauss-Seidel updating scheme. In my experiments with inventory control, the \(\pr{Green}\) algorithm converges in about half the time of the other schemes.
Let us demonstrate the \(\pr{Green}\) algorithm for the \((s,S)\) inventory control algorithm, see Alg. 5.10.4. It obtains the Lighthouse Company data from Alg. 2.5.4, constructs the running cost \(L(x),\) and sets \(\mu^0(S)=1\) and zero elsewhere. It then defines the stopping and transition rules and calls \(\pr{Green}.\) The expected visits \(g(x)\) give the cycle length, cycle cost, and average cost.
\begin{algorithm}
\caption{Compute the average cost of an \((s,S)\) policy using \(\pr{Green}.\)}
\begin{algorithmic}[1]
\State \textbf{Input:} reorder level \(s,\) order-up-to level \(S,\) cutoff \(\varepsilon\).
\State \textbf{Output:} average cost \(\var{averageCost}\).
\State \((p_D,\, \leadtime,\, h,\, b,\, K)\gets\pr{LighthouseData}()\)
\State \(p_X\gets\pr{Convolution}(p_D,\, \leadtime)\)
\State \(c\gets\lambdafun{z}{b\cdot z^-+h\cdot z^+}\)
\State \(L\gets\lambdafun{x}{\pr{Expectation}\rb{p_X,\, \lambdafun{u}{c(x-u)}}}\)
\State \(\mu\gets\pr{Constant}(S)\)
\State \(\pr{stop?}\gets\lambdafun{x}{x\le s}\)
\State \(P\gets\lambdafun{x}{\qb{(x-i,\, p_D(i)):i\in\pr{Keys}(p_D)}}\)
\State \(g\gets\pr{Green}(\mu,\, P,\, \pr{stop?},\, \varepsilon)\)
\State \(T(s,\, S)\gets\sum_{x>s}g(x)\)
\State \(v(s,\, S)\gets\sum_{x>s}g(x)\cdot L(x)+K\cdot\sum_{x\le s}g(x)\)
\State \(\var{averageCost}\gets v(s,\, S)/T(s,\, S)\)
\end{algorithmic}
\end{algorithm}
In a second example, we consider an inventory system that accepts returns. These returns can be seen as negative demand. In that case, the regular algorithm to compute the average cost under an \((s,S)\) policy no longer works, but \(\pr{Green}\) has no problems with such cases. The return probabilities below are the normalized values of the weights used in the reproducibility code. We reuse the stopping rule and start with a fresh point mass at \(S.\)
\begin{algorithm}
\caption{Compute the average cost when customers may return items.}
\begin{algorithmic}[1]
\State \textbf{Input:} \(p_D,\, s,\, S,\, c,\, K,\, \varepsilon,\, \pr{stop?}\) from the previous example.
\State \textbf{Output:} average cost with returns \(\var{averageCostReturns}\).
\State \(p_R\gets\pr{Map}()\)
\State \(p_R(0)\gets8/25,\quad p_R(1)\gets8/25\)
\State \(p_R(2)\gets6/25,\quad p_R(3)\gets3/25\)
\State \(p_{D-R}\gets\pr{Subtract}(p_D,\, p_R)\)
\State \(p_{X'}\gets\pr{Convolution}(p_{D-R},\, 2)\)
\State \(L'\gets\lambdafun{x}{\pr{Expectation}\rb{p_{X'},\, \lambdafun{u}{c(x-u)}}}\)
\State \(P'\gets\lambdafun{x}{\qb{(x-i,\, p_{D-R}(i)):i\in\pr{Keys}(p_{D-R})}}\)
\State \(\mu\gets\pr{Constant}(S)\)
\State \(g'\gets\pr{Green}(\mu,\, P',\, \pr{stop?},\, \varepsilon)\)
\State \(T'\gets\sum_{x>s}g'(x)\)
\State \(v'\gets\sum_{x>s}g'(x)\cdot L'(x)+K\cdot\sum_{x\le s}g'(x)\)
\State \(\var{averageCostReturns}\gets v'/T'\)
\end{algorithmic}
\end{algorithm}
Opt 1.
In the pruning step of \(\pr{Green},\) why not retain a state \(x\) whenever \(\mu(x)>\varepsilon\) or \(\pr{stop?}(x)\) is false?
Hint
How do we handle states at which \(\pr{stop?}(x)\) is true earlier in the algorithm?
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
When a state \(x\) is in the stopping set, it has been visited once. If \(\mu(x)\le\varepsilon,\) the proposed rule discards its mass before this visit is counted. We need to count this visit because there can be a cost associated with stopping at this \(x.\)