The Price of Simplicity: Analyzing Decoupled Policies for Multi-Location Inventory Control Yohan John*, Vade Shah*, James A. Preiss, Mahnoosh Alizadeh, Jason R. Marden Abstract What is the performance cost of using simple, decoupled control policies in inherently coupled systems? Motivated by industrial refrigeration systems, where centralized compressors exhibit economies of scale yet traditional control employs decoupled room-by-room temperature regulation, we address this question through the lens of multi-location inventory control. Here, a planner manages multiple inventories to meet stochastic demand while minimizing costs that are coupled through nonlinear ordering functions reflecting economies of scale. Our main contributions are: (i) a surprising equivalence result showing that optimal stationary base-stock levels for individual locations remain unchanged despite the coupling when restricting attention to decoupled strategies; (ii) tight performance bounds for simple decoupled policies relative to optimal coupled policies, revealing that the worst-case ratio depends primarily on the degree of nonlinearity in the cost function and scales with the number of locations for systems with fixed costs; and (iii) analysis of practical online algorithms that achieve competitive performance without solving complex dynamic programs. Numerical simulations demonstrate that while decoupled policies significantly outperform their worst-case guarantees in typical scenarios, they still exhibit meaningful suboptimality compared to fully coordinated strategies. These results provide actionable guidance for system operators navigating the trade-off between control complexity and operational efficiency in coupled systems. I Introduction Industrial refrigeration poses significant control challenges, particularly in cold storage facilities where multiple rooms must be maintained below critical temperature thresholds to preserve perishable goods. These systems use evaporators in each room that absorb heat from storage spaces and a centralized set of compressors—the dominant energy consumers—to meet the aggregate cooling load. Conventional control approaches rely on simple temperature setpoints that determine whether individual evaporators are on or off, creating a decoupled system where evaporator operation depends solely on conditions within each room [ 13 , 24 , 9 ] . However, cooling multiple rooms simultaneously could be more energy efficient because compressors operate most efficiently at maximum capacity [ 19 , 21 ] . Although technologies now exist to enable such coordinated control strategies [ 5 ] , it is crucial to determine whether the resulting efficiency gains would justify the implementation costs. Cold storage facilities can be thought of as multi-location inventory control systems [ 15 , 2 , 10 ] , a model from operations research where a planner manages multiple inventories of an item that is depleted by a random demand process over time; the core challenge is to balance the competing costs of holding excess inventory, incurring backlogs when demand exceeds the current inventory level, and placing orders for additional inventory. In this framework, cooling capacity corresponds to the ‘inventory level’ and heat loads represent ‘demands’ that deplete this inventory. The ‘thermal battery’ concept, i.e., intentionally overcooling products below required thresholds, parallels holding excess stock in traditional inventory systems, insufficient cooling is akin to backlogs, and the energy consumed by cooling operations represents ordering. When multi-location inventory systems are decoupled with independent demands and costs, they reduce to separate single-location systems, and decoupled control policies (like the setpoint control approaches used in refrigeration systems) are often effective. However, when the systems are coupled through their costs, as in refrigeration systems where compressor efficiency creates interdependencies, the problem and its optimal solutions may become more complex. Inventory control provides a well-established framework for studying coupling in these kinds of systems. Decades of research on the problem have focused on characterizing optimal policies under various assumptions on the demand process and cost functions for both single-location and multi-location systems. The key insight from this literature is that for typical single-location problems, simple control policies such as base-stock policies (order up to a specific threshold S if inventory falls below S ) or (s,S) policies (order up to S if inventory falls below s ) are provably optimal [ 1 , 22 ] . The multi-location inventory problem generalizes the standard problem to multiple locations. When the systems are decoupled, one can achieve optimal or near-optimal performance with decoupled policies [ 1 , 15 ] . However, in coupled systems where the cost in one location depends on another, such as when per-unit costs decrease with larger order quantities [ 20 , 3 ] , the problem is no longer decomposable, and simple decoupled policies may be significantly suboptimal. Several works have characterized optimal [ 2 , 15 , 7 , 8 , 18 ] or near-optimal [ 12 , 10 , 11 ] policies for various kinds of coupled multi-location systems. Importantly, these policies can be complex and difficult to implement in practice. The focus of this work is to study how well simple, decoupled policies perform in coupled multi-location inventory systems like the refrigeration example above. In particular, we focus on systems where demand and holding/backlog costs are independent across locations, but ordering costs are a nonlinear function of the cumulative order quantity across all locations in each period. Our results are summarized as follows: (i) Our first contribution given in Theorem 1 demonstrates that the optimal stationary base-stock policy for a particular location in a multi-location inventory control problem is equivalent to the optimal stationary base-stock policy for that location in isolation. In other words, despite the coupling through nonlinear ordering costs, the existence of other locations does not influence the optimal base-stock level for a given location. This result significantly simplifies the process of finding optimal stationary base-stock policies, as it allows us to solve separate single-location problems rather than a joint multi-location problem. (ii) Our second contribution given in Theorem 2 provides tight bounds on the performance gap between the optimal policy and the optimal decoupled base-stock and (s,S) policies in multi-location inventory control problems. Specifically, for sector-bounded ordering costs, we show that this ratio depends only on the degree of nonlinearity of the ordering cost function, while for affine-bounded ordering costs, it also scales with the number of locations. These bounds precisely quantify the trade-off between policy simplicity and performance across different system structures, providing guidance on when decoupled base-stock policies are nearly optimal and when more complex coupled policies may be necessary. (iii) Our third contribution extends our analysis to a simple online policy as an alternative to optimal decoupled base-stock or (s,S) policies, which are structurally simple but can be computationally difficult to identify, especially in the case where demands are correlated over time [ 6 ] . In Proposition 3 , we analyze the randomized cost-balancing policy [ 17 ] , an efficiently computable heuristic that balances ordering, holding, and backlog costs. We prove that this algorithm achieves competitive ratios that scale predictably with our bounds for optimal decoupled policies, thereby demonstrating that effective inventory control is possible even with online decision rules. These results are particularly valuable for practical applications where computational resources are limited or real-time decisions are required. We validate these theoretical results through numerical simulations which reveal that while simple decoupled policies and online algorithms outperform their worst-case bounds in practice, they still exhibit significant suboptimality compared to optimal coupled policies. Although our motivation stems from industrial refrigeration systems, we recognize that real refrigeration dynamics involve additional complexities not captured in our model. However, our purpose is not to accurately model refrigeration systems but rather to provide a first-order understanding of how decoupled control policies perform in inherently coupled environments. The fundamental insight of this paper is a precise characterization of the performance guarantees achievable with structurally simple control policies like setpoint control. These findings provide practical guidance for system operators facing the trade-off between control complexity and operational efficiency across various domains with similar coupling structures. II Multi-Location Inventory Problem In the multi-location inventory problem, one seeks to meet stochastic demand while balancing ordering costs, holding costs, and backlog costs across multiple locations. The system is described by the M -dimensional linear dynamics x_{k+1}=x_{k}+u_{k}-w_{k}, (1) where x_{k}\in\mathbb{R}^{M} is the inventory level at each location at stage k , u_{k}\in\mathbb{R}_{\geq 0}^{M} is the control input (ordering), and w_{k} is an M -dimensional random variable that represents stochastic demand. We assume that each w_{k}^{i} is finite-mean, independent, nonnegative, and has bounded support, where we use the superscript i\in\{1,...,M\} to index the relevant quantity for the i th location. At each stage, we face two competing costs: the cost of ordering, which we represent as c:\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0} , and the cost of holding inventory or experiencing backlogged demand, which we represent as r:\mathbb{R}^{M}\to\mathbb{R}_{\geq 0} . We assume that c is a function of the total order quantity across all the individual locations 1 1 1 We assume that the cost is an unweighted sum of the order amount at each location, but all of our results extend to the setting where the ordering cost is c(\sum_{i=1}^{M}\alpha^{i}z^{i}) for some \alpha>0 . , i.e., c(z) is a shorthand notation for c(\sum_{i=1}^{M}z^{i}) , and that c is locally bounded and lower semicontinuous. Additionally, we assume that the holding/backlog costs are additively separable, i.e., r(z)=\sum_{i=1}^{M}r^{i}(z^{i}) , where r^{i}:\mathbb{R}\to\mathbb{R}_{\geq 0} is locally bounded, radially unbounded, and convex. The average costs over an N -period horizon are given by \mathbb{E}\left[\frac{1}{N}\sum_{k=0}^{N-1}\left(c(u_{k})+r(x_{k}+u_{k}-w_{k})\right)\right]. (2) For the infinite-horizon setting, we follow the approach of [ 23 ] and average costs by taking the limit superior of ( 2 ) as N\to\infty . We adopt the notation P=(c,r,W) to completely describe a multi-location inventory problem, where the dimension of W , an M -by- N random variable whose (i,k) -th element is w_{k-1}^{i} , indicates the number of inventories and the length of the horizon, and we use \mathcal{P}^{M} to denote the set of all M -location inventory problems with finite or infinite horizon that meet the above assumptions on c , r , and W . We define a policy \pi=\{\mu_{k}\}_{k\,\geq\,0} as a sequence of functions \mu_{k}:\mathbb{R}^{M}\to\Delta(\mathbb{R}^{M}_{\geq 0}) that map a state x_{k} to a probability distribution over feasible controls u_{k}^{i}\geq 0 for all i ; if \mu_{k}=\mu for all k , then \pi is said to be stationary . The expected cost for a given policy \pi from initial condition x_{0} is given by J_{\pi}(x_{0}\,|\,P) , which is defined as \mathbb{E}\left[\frac{1}{N}\sum_{k=0}^{N-1}\left(c(\mu_{k}(x_{k}))+r(x_{k}+\mu_{k}(x_{k})-w_{k})\right)\right] (3) with appropriate modifications for the infinite-horizon setting. An optimal policy \pi_{*} for a given problem P is one which incurs expected cost less than or equal to all other policies for all initial conditions, i.e., \pi_{*}\in\argmin_{\pi\in\Pi^{M}}J_{\pi}(x_{0}\,|\,P),\quad\forall\ x_{0}\in\mathbb{R}^{M} (4) where \Pi^{M} is the set of all M -dimensional policies; our assumptions on c , r , and W guarantee the existence of \pi_{*} for both finite [ 4 , Ch. 3] and infinite-horizon problems [ 23 ] . A policy \pi is said to be decoupled if \mu_{k} is component-wise separable for all k , i.e., \mu_{k}(z_{k})=\{\mu_{k}^{1}(z_{k}^{1}),...,\mu_{k}^{M}(z_{k}^{M})\} ; otherwise, it is coupled . We occasionally abuse notation and write a decoupled policy as \pi=\{\pi^{1},...,\pi^{M}\} , where \pi^{i}=\{\mu_{k}^{i}\}_{k\geq 0} . II-A Motivating Examples Fig. 1 contains some numerical examples that illustrate optimal policies under linear and nonlinear ordering costs and motivate our study of the suboptimality of decoupled policies. We define linear ordering costs as functions of the form c(z)=mz where m\geq 0 is the per-unit cost. Fig. 1 (a) shows the optimal policy for a 2-location problem with ordering cost c(z)=2z and has two notable features. First, because the multi-location inventory problem ( 2 ) is coupled only through the ordering cost function, for linear ordering costs the problem decouples into M independent single-location problems. As a result, the optimal policy in this case is also decoupled. Second, it is well-known in the inventory control literature that for single-location problems with linear ordering costs, so-called base-stock policies are optimal [ 1 ] . Definition 1 . A policy \pi\in\Pi^{1} is a base-stock policy if \mu_{k}(x_{k})=\max\{S_{k}-x_{k},0\} (5) for some S_{k}\in\mathbb{R} for all k\geq 0 . Fig. 1 (a) shows that the optimal policy for each location at time k=0 is a base-stock policy where S_{0}=1 . Fig. 1 (b) shows that the optimal policy for a nonlinear ordering cost, in this case c(z)=\begin{cases}2z,\quad&z\in\{0,1\}\\ 4z,\quad&z\in\{2,3,4\},\end{cases} (6) can be coupled and have quite general structure. Note that in the x_{0}^{1}=x_{0}^{2}=0 state it is optimal to order 1 unit in either location (but not both) so the two locations are indistinguishable, i.e., there is symmetry about the anti-diagonal. For this particular nonlinear ordering cost function ( 6 ), the best (decoupled) base-stock policy also happens to be the one shown in Fig. 1 (a). Fig. 1 (c) shows the increase in expected cost associated with using the policy from Fig. 1 (a) instead of the optimal policy from Fig. 1 (b). To characterize the suboptimality in cases like this, our main results provide bounds on the worst-case cost increase of using decoupled single-location policies for multi-location problems for broad classes of nonlinear ordering cost functions. Fig. 1: We consider M=2 inventories, integer-valued parameters, a finite horizon N=2 , holding/backlog cost r(z)=\max\{0,z\}+10\max\{0,-z\} , and stochastic demand w_{k} that takes values zero or one with equal probability. (a) shows the optimal policy for the linear ordering cost c(z)=2z . (b) shows the optimal policy for the nonlinear ordering cost function ( 6 ). (c) shows the expected cost from each initial condition for the nonlinear ordering cost function ( 6 ) under the policies in (a),(b). III Policy Comparison In this section, we compare the performance of optimal and decoupled policies in the multi-location inventory problem ( 3 ) for various ordering cost functions. Our results in this section focus specifically on the infinite horizon setting, i.e., N=\infty . III-A Stationary Base-Stock Policies The motivating examples in the previous section highlight that complex, coupled policies may perform better than simple, decoupled ones. In this section, we momentarily disregard questions of policy complexity and ask instead about the effects of coupling within an extremely simple class of policies. Consider the class of decoupled stationary base-stock policies \Pi_{\textup{Y}}^{M}\subset\Pi^{M} , where a decoupled policy \pi=\{\pi^{1},...,\pi^{M}\} is said to be a decoupled stationary base-stock policy if \pi^{i} is a stationary base-stock policy for all i . Our first result demonstrates that when optimizing within this class for infinite horizon problems, coupling can be neglected, i.e., there is no difference between solving for optimal base-stock policies jointly over \Pi_{\textup{Y}}^{M} or individually over \Pi_{\textup{Y}}^{1} . Theorem 1 (Equivalence of stationary base-stock policies) . Consider an infinite horizon M -location inventory problem P=(c,r,W)\in\mathcal{P}^{M} with initial condition x_{0}\in\mathbb{R}^{M} . The jointly-optimized stationary base-stock policy \pi_{\star}\in\argmin_{\pi\in\Pi_{\textup{Y}}^{M}}J_{\pi}(x_{0}\,|\,P) (7) and the individually-optimized stationary base-stock policy \pi_{\circ}=\{\pi_{\circ}^{1},...,\pi_{\circ}^{M}\} , where P^{i}=(c,r^{i},W^{i}) and \pi_{\circ}^{i}\in\argmin_{\pi\in\Pi_{\textup{Y}}^{1}}J_{\pi}(x_{0}^{i}\,|\,P^{i}), (8) exist and satisfy J_{\pi_{\circ}}(x_{0}\,|\,P)=J_{\pi_{\star}}(x_{0}\,|\,P) . Theorem 1 highlights a key property of stationary base-stock policies in infinite-horizon problems: within this class, solving for policies independently is optimal. Importantly, this means that the coupling in the ordering cost can and should be disregarded, as one cannot achieve better performance by taking it into consideration. Furthermore, this result is quite general, as it holds for any locally bounded, nonnegative, and lower semicontinuous ordering cost function. Proof. Let S^{i} denote the base-stock level in inventory i defined by \pi_{\star} , and assume without loss of generality that S^{i}\geq 0 for all i . Given that the support of the demand w_{k}^{i} is nonnegative, we can write the objective function in ( 7 ) with the initial condition x_{0}^{i}=0 for all i as \limsup_{N\to\infty}\frac{1}{N}\mathbb{E}\Bigg[\sum_{k=0}^{N}\Bigg(c\left(\sum_{i=1}^{M}(S^{i}-x_{k}^{i})\right)+\sum_{i=1}^{M}r^{i}(S^{i}-w_{k}^{i})\Bigg)\Bigg]. From ( 1 ) and ( 5 ), we have that for all k\geq 1 , \displaystyle u_{k}^{i}=S^{i}-x_{k}^{i} \displaystyle=S^{i}-(x_{k-1}^{i}+u_{k-1}^{i}-w_{k-1}^{i}) \displaystyle=S^{i}-(x_{k-1}^{i}+S^{i}-x_{k-1}^{i}-w_{k-1}^{i})=w_{k-1}^{i}, so we can separate the k=0 terms and rewrite the optimization problem as \displaystyle\min_{S\in\mathbb{R}^{M}}\limsup_{N\to\infty}\frac{1}{N}\mathbb{E}\Bigg[c\left(\sum_{i=1}^{M}(S^{i}-x_{0}^{i})\right)+\sum_{i=1}^{M}r^{i}(S^{i}-w_{0}^{i}) \displaystyle+\sum_{k=1}^{N}\left(c\left(\sum_{i=1}^{M}w_{k-1}^{i}\right)+\sum_{i=1}^{M}r^{i}(S^{i}-w_{k}^{i})\right)\Bigg]. The expected ordering cost terms are a fixed constant for all k\geq 1 , and since c and r are locally bounded, the total cost incurred in the first period is finite. Hence, we can equivalently rewrite the problem as \displaystyle\min_{S\in\mathbb{R}^{M}}\limsup_{N\to\infty}\frac{1}{N}\mathbb{E}\left[\sum_{k=1}^{N}\sum_{i=1}^{M}r^{i}(S^{i}-w_{k}^{i})\right]. This problem can be decomposed into M independent single-location inventory control problems, and the same analysis can be applied to verify that the single-inventory problem corresponding to location i is precisely problem ( 8 ), meaning that the expected costs of \pi_{\star} and \pi_{\circ} from the zero initial condition are identical. The existence of both \pi_{\star} and \pi_{\circ}^{i} follows from the fact that the limit superior of the objective exists and is a nonnegative, radially unbounded, and proper function in S , so it has an infimum; furthermore, the infimum can be achieved because it is also lower semicontinuous. We extend the analysis to nonzero initial conditions as follows. For any initial condition where x_{0}^{i}<0 , a stationary threshold policy orders up to S^{i} in one period, so by the same argument as above, these costs are finite and negligible. For any initial condition where x_{0}^{i}>0 , we consider two cases: if \sum_{k=1}^{\infty}\mathbb{E}[w_{k}^{i}]=\infty , then x_{k}^{i}\leq S^{i} for some k<\infty with probability 1, and the finite costs associated with these periods can be eliminated in a similar fashion. Otherwise, if \sum_{k=1}^{\infty}\mathbb{E}[w_{k}^{i}]<\infty , S^{i}=0 is trivially optimal for both the individually- and jointly-optimized problems. ∎ III-B Base-Stock and (s,S) Policies Unfortunately, the results of the previous section are specific to stationary base-stock policies in infinite horizon problems. It is not difficult to show that when one allows for more general policies or when one considers a finite horizon, coupling cannot always be neglected without some performance degradation. Hence, in this section, we study both complexity and coupling as we quantify the performance gap between optimal coupled and simple decoupled policies. We focus specifically on the classes of decoupled base-stock and decoupled (s,S) policies \Pi_{\textup{B}}^{M}\subset\Pi^{M} and \Pi_{\textup{S}}^{M}\subset\Pi^{M} , respectively; a policy \pi=\{\pi^{1},...,\pi^{M}\} is a decoupled base-stock (resp., (s,S) ) policy if \pi^{i} is a base-stock (resp., (s,S) ) policy for all i . Definition 2 . A policy \pi\in\Pi^{1} is an (s,S) policy if \mu_{k}(x_{k})=\begin{cases}S_{k}-x_{k}&x_{k}0 and 0 otherwise [ 22 ] . We refer to such ordering cost functions as affine . The results in this section focus on two broad classes of nonlinear ordering cost functions: Definition 3 . A function c:\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0} is sector-bounded if lz\leq c(z)\leq hz for some h\geq l>0 . Definition 4 . A function c:\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0} is affine-bounded if K_{l}\mbox{1}(z)+lz\leq c(z)\leq K_{h}\mbox{1}(z)+hz for some h\geq l>0 and K_{h}\geq K_{l}>0 . Our main result establishes bounds on the worst-case performance of decoupled base-stock policies for infinite horizon problems 2 2 2 Note that in the finite horizon setting, ( 11 ) still holds; however, ( 10 ) holds as an upper bound rather than as an equality. with sector-bounded ordering costs and decoupled (s,S) policies for problems with affine-bounded ordering costs. Theorem 2 (Suboptimality of base-stock and (s,S) policies) . 1. Let \mathcal{P}_{\textup{SB}}^{M}\subset\mathcal{P}^{M} denote the set of all M -location inventory problems where the ordering cost is sector-bounded with h\geq l>0 . We have that \sup_{x_{0}\in\mathbb{R}^{M},P\in\mathcal{P}_{\textup{SB}}^{M}}\min_{\pi\in\Pi_{\textup{B}}^{M}}\frac{J_{\pi}(x_{0}\,|\,P)}{J_{\pi_{*}}(x_{0}\,|\,P)}=\frac{h}{l}. (10) 2. Let \mathcal{P}_{\textup{AB}}^{M}\subset\mathcal{P}^{M} denote the set of all M -location inventory problems where the ordering cost is affine-bounded with h\geq l>0 and K_{h}\geq K_{l}>0 . We have that \sup_{x_{0}\in\mathbb{R}^{M},P\in\mathcal{P}_{\textup{AB}}^{M}}\min_{\pi\in\Pi_{\textup{S}}^{M}}\frac{J_{\pi}(x_{0}\,|\,P)}{J_{\pi_{*}}(x_{0}\,|\,P)}\leq M{\max}\left\{\frac{K_{h}}{K_{l}}{,}\frac{h}{l}\right\}. (11) Theorem 2 establishes several interesting properties of optimal decoupled base-stock policies for problems with sector-bounded ordering costs. First, observe that the ratio ( 10 ) grows with the ratio h/l , indicating that optimal decoupled policies may perform worse with ‘more nonlinear’ functions; note that when the ordering cost is linear, h/l=1 . Second, the proof is constructive, meaning that one can identify a decoupled base-stock policy that achieves this bound by solving only M single-location problems with identical linear ordering costs. Third, the tightness of the result means that no base-stock policy achieves a ratio strictly less than h/l for all problem instances, implying that this policy is not only reasonable to implement but also optimal (with respect to worst-case performance) among base-stock policies. Theorem 2 also establishes important properties of optimal decoupled (s,S) policies for problems with affine-bounded ordering costs. Here, the bound ( 11 ) also grows with the ratios h/l and K_{h}/K_{l} , indicating that the degree of nonlinearity affects worst-case performance similarly, and the proof is also constructive. However, the key distinction between the two is that the upper bound in ( 11 ) scales with the number of locations. This suggests that for systems with several locations and fixed costs—such as cold storage facilities, where there may be several rooms and compressors typically have minimum operating thresholds [ 21 ] —decoupled policies may perform especially poorly 3 3 3 That said, we acknowledge that this bound is not tight, and we leave it to future work to show that this ratio is also lower-bounded by an increasing function of M . . Proof. We first establish ( 10 ). We proceed constructively. Taking c_{l}(z)=lz , let \pi_{\text{\framebox{\rule{0.0pt}{3.01389pt}\rule{3.01389pt}{0.0pt}}}} denote the (optimal) decoupled base-stock policy for the multi-location problem P_{l}=(c_{l},r,W) . We have that \displaystyle\frac{J_{\pi_{\text{\framebox{\rule{0.0pt}{2.15277pt}\rule{2.15277pt}{0.0pt}}}}}(x_{0}\,|\,P)}{J_{\pi_{*}}(x_{0}\,|\,P)}\mathrel{\overset{\textrm{(i)}}{\vphantom{\leq}{\leq}}}\frac{J_{\pi_{\text{\framebox{\rule{0.0pt}{2.15277pt}\rule{2.15277pt}{0.0pt}}}}}(x_{0}\,|\,P)}{J_{\pi_{\text{\framebox{\rule{0.0pt}{2.15277pt}\rule{2.15277pt}{0.0pt}}}}}(x_{0}\,|\,P_{l})}\leq\frac{J_{\pi_{\text{\framebox{\rule{0.0pt}{2.15277pt}\rule{2.15277pt}{0.0pt}}}}}(x_{0}\,|\,P_{h})}{J_{\pi_{\text{\framebox{\rule{0.0pt}{2.15277pt}\rule{2.15277pt}{0.0pt}}}}}(x_{0}\,|\,P_{l})}\mathrel{\overset{\textrm{(ii)}}{\vphantom{\leq}{\leq}}}\frac{h}{l} where P_{h}=(c_{h},r,W) with c_{h}(z)=hz . Here, (i) holds because the costs under P are greater than or equal to the costs under P_{l} , and (ii) follows from the fact that since the same policy \pi_{\text{\framebox{\rule{0.0pt}{3.01389pt}\rule{3.01389pt}{0.0pt}}}} is enacted on both P_{l} and P_{h} , the only differences in their overall costs must result from differences in their ordering costs which are bounded by the sector. Because these inequalities hold for any x_{0} and P with sector-bounded ordering cost, they hold for the supremum over x_{0} and P . To establish equality, we provide an example of a generic infinite horizon M -location inventory problem in Appendix -B such that for any \varepsilon>0 , the expected cost of any base-stock policy is at least \frac{h}{l+\varepsilon} greater than the expected cost of the optimal policy for some initial condition. Taking the limit as \varepsilon\to 0 yields that the supremum exists and is \frac{h}{l} . To show ( 11 ), we first consider the setting where K_{l}=K_{h} and l=h (i.e., the function is affine). Let \pi_{\diamond} denote the decoupled (s,S) policy \{\pi_{\diamond}^{1},...,\pi_{\diamond}^{M}\} where \pi_{\diamond}^{i} is optimal for P^{i}=(c,r^{i},W^{i}) . Let j\in\argmax_{i\in\{1,...,M\}}\ J_{\pi_{\diamond}^{i}}(x_{0}\,|\,P^{i}) denote the single location that incurs the maximum expected cost under \pi_{\diamond} for the initial condition x_{0} . Then, we have that \frac{J_{\pi_{\diamond}}(x_{0}\,|\,P)}{J_{\pi_{*}}(x_{0}\,|\,P)}\mathrel{\overset{\textrm{(iii)}}{\vphantom{\leq}{\leq}}}\frac{J_{\pi_{\diamond}}(x_{0}\,|\,P)}{J_{\pi_{\diamond}^{j}}(x_{0}\,|\,P^{j})}\leq\frac{MJ_{\pi_{\diamond}^{j}}(x_{0}\,|\,P^{j})}{J_{\pi_{\diamond}^{j}}(x_{0}\,|\,P^{j})}=M (12) where we have (iii) because adding additional locations cannot decrease the expected cost. We now consider the general setting. Define c_{l}(z)=K_{l}\mbox{1}(z)+lz and c_{h}(z)=K_{h}\mbox{1}(z)+hz , and let \pi_{\diamond} instead denote the decoupled policy \{\pi_{\diamond}^{1},...,\pi_{\diamond}^{M}\} where \pi_{\diamond}^{i} is optimal for P^{i}=(c_{h},r^{i},W^{i}) . Let \pi_{l} , \pi_{*} , and \pi_{h} denote the optimal policies for the problems P_{l}=(c_{l},r,W) , P , and P_{h}=(c_{h},r,W) , respectively. First, we apply some trivial bounds on the ratio of the expected costs between \pi_{\diamond} and \pi_{*} : \displaystyle\frac{J_{\pi_{\diamond}}(x_{0}\,|\,P)}{J_{\pi_{*}}(x_{0}\,|\,P)}\leq\frac{J_{\pi_{\diamond}}(x_{0}\,|\,P)}{J_{\pi_{l}}(x_{0}\,|\,P_{l})}\leq\frac{J_{\pi_{\diamond}}(x_{0}\,|\,P_{h})}{J_{\pi_{l}}(x_{0}\,|\,P_{l})}. We further bound the last expression by \displaystyle\frac{J_{\pi_{\diamond}}(x_{0}\,|\,P_{h})}{J_{\pi_{l}}(x_{0}\,|\,P_{l})}\mathrel{\overset{\textrm{(iv)}}{\vphantom{\leq}{\leq}}}\frac{MJ_{\pi_{h}}(x_{0}\,|\,P_{h})}{J_{\pi_{l}}(x_{0}\,|\,P_{l})}\mathrel{\overset{\textrm{(v)}}{\vphantom{\leq}{\leq}}}\frac{MJ_{\pi_{l}}(x_{0}\,|\,P_{h})}{J_{\pi_{l}}(x_{0}\,|\,P_{l})} where (iv) follows from ( 12 ) and (v) follows from the fact that \pi_{l} is suboptimal for P_{h} . All that remains is to bound the difference in costs between the problems P_{l} and P_{h} when \pi_{l} is applied. Consider performing the cost transformation described in Appendix -A on P_{l} and P_{h} . We can use ( 21 ) to write \frac{J_{\pi_{l}}(x_{0}\,|\,P_{h})}{J_{\pi_{l}}(x_{0}\,|\,P_{l})}=\frac{J_{\pi_{l}}(x_{0}\,|\,\hat{P}_{h})+h\gamma}{J_{\pi_{l}}(x_{0}\,|\,\hat{P}_{l})+l\gamma}=\frac{\alpha+K_{h}\beta+h\gamma}{\alpha+K_{l}\beta+l\gamma} where \alpha\geq 0 represents expected holding/backlog costs, \beta=\frac{1}{N}\sum_{k=0}^{N-1}\mbox{1}(\sum_{i=1}^{M}u_{k}^{i})\geq 0 represents fixed ordering costs, and \gamma=\mathbb{E}\left[\frac{1}{N}\sum_{k=0}^{N-1}\sum_{i=1}^{M}w_{k}^{i}\right]\geq 0 represents unit ordering costs (with appropriate limits for the infinite horizon setting). We proceed by considering two cases: 1. If K_{l}h\leq K_{h}l , then one can show that \frac{\alpha+K_{h}\beta+h\gamma}{\alpha+K_{l}\beta+l\gamma}\leq\frac{K_{h}}{K_{l}} . 2. If K_{l}h>K_{h}l , then it can similarly be shown that \frac{\alpha+K_{h}\beta+h\gamma}{\alpha+K_{l}\beta+l\gamma}<\frac{h}{l} . Thus, in either case the ratio is less than \max\left\{K_{h}/K_{l},h/l\right\} 4 4 4 Note that for the case of h=l=0 , the upper bound is MK_{h}/K_{l} by the same argument. . Once again, all of the inequalities hold for any x_{0} and P with the appropriate ordering cost function. Therefore, they hold for the supremum over x_{0} and P . ∎ IV Online Algorithm Computing an optimal policy for an inventory control problem can be challenging even in the single-location setting. For example, in the case of demand structures with correlation over time, the problem of solving for optimal policies can suffer from the curse of dimensionality [ 6 ] . However, for single-location finite-horizon problems with linear or affine ordering costs, there exists an efficient online algorithm that achieves constant-factor competitive ratios relative to optimal policies, even with correlated demands [ 16 , 17 ] . Here the term online algorithm refers to policies that do not require pre-computation and can be efficiently implemented online. In this section, we analyze the application of this algorithm to multi-location problems with nonlinear ordering costs. IV-A Randomized Cost-Balancing Policy In [ 17 ] , the authors propose the randomized cost-balancing policy \pi_{\vartriangle} which is an online algorithm for single-location inventory control problems with linear or affine ordering costs and holding/backlog costs of the form r(x)=a(\max\{0,x\})+b(\max\{0,-x\}) where a,b\geq 0 . We define \mathcal{Q}^{M}\subset\mathcal{P}^{M} as the set of all M -location finite-horizon inventory problems with ordering costs assumptions as in Section II and holding/backlog costs as above. Under \pi_{\vartriangle} , at each time step one employs the following probabilistic ordering rule to balance in expectation the holding, backlog, and fixed cost K : \mu_{\vartriangle}=\begin{cases}\hat{u}_{k},\quad&\theta_{k}\geq K,\ \textup{w.p.}\ 1\\ \tilde{u}_{k},\quad&\theta_{k}0 . We have that \sup_{x_{0}\in\mathbb{R}^{M},Q\in\mathcal{Q}_{\textup{SB}}^{M}}\frac{J_{\pi_{\vartriangle}}(x_{0}\,|\,Q)}{J_{\pi_{*}}(x_{0}\,|\,Q)}\leq\frac{2h}{l}. (16) 2. Let \mathcal{Q}_{\textup{AB}}^{M}\subset\mathcal{Q}^{M} denote the set of all M -location inventory problems where the ordering cost is affine-bounded with h\geq l>0 and K_{h}\geq K_{l}>0 . We have that \sup_{x_{0}\in\mathbb{R}^{M},Q\in\mathcal{Q}_{\textup{AB}}^{M}}\frac{J_{\pi_{\vartriangle}}(x_{0}\,|\,Q)}{J_{\pi_{*}}(x_{0}\,|\,Q)}\leq 3M\max\left\{\frac{K_{h}}{K_{l}},\frac{h}{l}\right\}. (17) Proof. We begin with ( 16 ). The proof is handled in two steps. First, we have the following bound when comparing \pi_{\vartriangle} with \pi_{\text{\framebox{\rule{0.0pt}{3.01389pt}\rule{3.01389pt}{0.0pt}}}} , the optimal (decoupled) policy for the problem Q_{l}=(c_{l},r,W) with c_{l}(z)=lz : \frac{\frac{1}{2}J_{\pi_{\vartriangle}}(x_{0}\,|\,Q_{h})}{J_{\pi_{\text{\framebox{\rule{0.0pt}{2.15277pt}\rule{2.15277pt}{0.0pt}}}}}(x_{0}\,|\,Q_{l})}\mathrel{\overset{\textrm{(vi)}}{\vphantom{\leq}{\leq}}}\frac{J_{\pi_{\text{\framebox{\rule{0.0pt}{2.15277pt}\rule{2.15277pt}{0.0pt}}}}}(x_{0}\,|\,Q_{h})}{J_{\pi_{\text{\framebox{\rule{0.0pt}{2.15277pt}\rule{2.15277pt}{0.0pt}}}}}(x_{0}\,|\,Q_{l})}\leq\frac{h}{l}, where Q_{h}=(c_{h},r,W) with c_{h}(z)=hz , and we use ( 14 ) for (vi). The second step is straightforward: \frac{\frac{1}{2}J_{\pi_{\vartriangle}}(x_{0}\,|\,Q)}{J_{\pi_{*}}(x_{0}\,|\,Q)}\leq\frac{\frac{1}{2}J_{\pi_{\vartriangle}}(x_{0}\,|\,Q)}{J_{\pi_{\text{\framebox{\rule{0.0pt}{2.15277pt}\rule{2.15277pt}{0.0pt}}}}}(x_{0}\,|\,Q_{l})}\leq\frac{\frac{1}{2}J_{\pi_{\vartriangle}}(x_{0}\,|\,Q_{h})}{J_{\pi_{\text{\framebox{\rule{0.0pt}{2.15277pt}\rule{2.15277pt}{0.0pt}}}}}(x_{0}\,|\,Q_{l})}. Now we move to showing ( 17 ). We will need the following bound for affine ordering costs that uses the decoupled (s,S) policy \pi_{\diamond}=\{\pi_{\diamond}^{1},\dots,\pi_{\diamond}^{M}\} where \pi_{\diamond}^{i} is optimal for Q^{i}=(c,r^{i},W^{i}) with c(z)=K\mbox{1}(z)+mz : \frac{\frac{1}{3}J_{\pi_{\vartriangle}}(x_{0}\,|\,Q)}{J_{\pi_{*}}(x_{0}\,|\,Q)}\mathrel{\overset{\textrm{(vii)}}{\vphantom{\leq}{\leq}}}\frac{J_{\pi_{\diamond}}(x_{0}\,|\,Q)}{J_{\pi_{*}}(x_{0}\,|\,Q)}\mathrel{\overset{\textrm{(viii)}}{\vphantom{\leq}{\leq}}}M. (18) We use ( 15 ) for (vii) and (viii) follows from the proof of Theorem 2 . Now we can proceed as before. The proof is similar to that of ( 16 ), so we only show the first stage that compares \pi_{\vartriangle} with \pi_{l} , the optimal policy for Q_{l}=(c_{l},r,W) with c_{l}(z)=K_{l}\mbox{1}(z)+lz : \frac{\frac{1}{3M}J_{\pi_{\vartriangle}}(x_{0}\,|\,Q_{h})}{J_{\pi_{l}}(x_{0}\,|\,Q_{l})}\mathrel{\overset{\textrm{(ix)}}{\vphantom{\leq}{\leq}}}\frac{J_{\pi_{l}}(x_{0}\,|\,Q_{h})}{J_{\pi_{l}}(x_{0}\,|\,Q_{l})}\leq\max\left\{\frac{K_{h}}{K_{l}},\frac{h}{l}\right\}, where Q_{h}=(c_{h},r,W) with c_{h}(z)=K_{h}\mbox{1}(z)+hz , and we use ( 18 ) for (ix). All of the inequalities hold for any x_{0} and Q with the appropriate ordering cost function. Therefore, they hold for the supremum over x_{0} and Q . ∎ Proposition 3 establishes that one can apply the online policy \pi_{\vartriangle} to multi-location inventory problems with a variety of ordering cost functions and achieve bounded suboptimality. While these policies may be far from optimal in general, we show in the following section that they perform reasonably well for representative numerical examples, suggesting that one need not solve a dynamic program to achieve good performance in multi-location settings with nonlinear costs. V Simulations In this section we evaluate the suboptimality of the proposed decoupled policies and online algorithms via numerical simulation. We use the sector-bounded ordering cost function c(z)=\begin{cases}4z,\quad&z\leq 6\\ 2z+12,\quad&z>6\end{cases} (19) and the affine-bounded ordering cost function c(z)=\begin{cases}4\mbox{1}(z)+2z,\quad&z\leq 6\\ 4\mbox{1}(z)+z+6,\quad&z>6\end{cases} (20) Both these functions exhibit economies of scale where the per-unit cost decreases as larger quantities are ordered. We perform 1000 Monte Carlo simulations from each possible initial condition to compare decoupled dynamic programming-based policies and online algorithms with the optimal policy. Fig. 2 (a) shows a heatmap of the average cost ratios J_{\pi_{\text{\framebox{\rule{0.0pt}{2.15277pt}\rule{2.15277pt}{0.0pt}}}}}(x_{0}\,|\,Q)/J_{\pi_{*}}(x_{0}\,|\,Q) and J_{\pi_{\vartriangle}}(x_{0}\,|\,Q)/J_{\pi_{*}}(x_{0}\,|\,Q) under the ordering cost ( 19 ) where \pi_{\text{\framebox{\rule{0.0pt}{3.01389pt}\rule{3.01389pt}{0.0pt}}}} is the decoupled base-stock policy that is optimal for the problem P_{l}=(c_{l},r,W) with c_{l}(z)=lz . For the decoupled policy, the mean ratio is 1.13 and the max ratio is 1.18. For the online algorithm, the mean ratio is 1.15 and the max ratio is 1.21. Our worst-case bounds are h/l=4/2=2 for the decoupled policy and 2h/l=4 for the online algorithm. While the empirical performance is far from the worst-case bounds, we do see substantially increased cost. Interestingly, for this choice of parameters, the online algorithm performs nearly as well as the decoupled policy. Fig. 2 (b) shows a heatmap of the average cost ratios J_{\pi_{\diamond}}(x_{0}\,|\,Q)/J_{\pi_{*}}(x_{0}\,|\,Q) , J_{\pi_{\vartriangle}}(x_{0}\,|\,Q)/J_{\pi_{*}}(x_{0}\,|\,Q) under ( 20 ) where \pi_{\diamond} is the decoupled (s,S) policy that is optimal for each single-location problem P_{h}^{i}=(c_{h},r^{i},W^{i}) with c_{h}(z)=K_{h}\mbox{1}(z)+hz . For the decoupled policy, the mean ratio is 1.14 and the max ratio is 1.22. For the online algorithm, the mean ratio is 1.47 and the max ratio is 1.56. Our (optimized) worst-case bounds are M\max\{K_{h}/K_{l},h/l\}=2\max\{(16/3)/4,(4/3)/1\}=8/3 and 3M\max\{K_{h}/K_{l},h/l\}=8 , respectively. Once again the empirical performance does not attain the worst-case bounds; however, the suboptimality of both policies is evident. Fig. 2: For all simulations we consider M=2 inventories, state space x\in[-2,8] , discretization \Delta x=0.5 , a finite horizon N=20 , and stochastic demand w_{k}\in\{0,0.5,1,1.5\} where w_{k}\sim\mathrm{Bin}(3,0.5) . (a) shows average cost ratios for the decoupled policy \pi_{\text{\framebox{\rule{0.0pt}{3.01389pt}\rule{3.01389pt}{0.0pt}}}} and online policy \pi_{\vartriangle} from each initial state under sector-bounded ordering cost. We set holding/backlog cost r(z)=0.1\max\{0,z\}+10\max\{0,-z\} . (b) shows average cost ratios for the decoupled policy \pi_{s} and online policy \pi_{\vartriangle} from each initial state under affine-bounded ordering cost. We set holding/backlog cost r(z)=0.2\max\{0,z\}+10\max\{0,-z\} . VI Conclusion In this work, we evaluated the performance of simple decoupled policies in multi-location inventory control problems coupled through a nonlinear ordering cost function. For sector-bounded nonlinearities, we demonstrated that a collection of base-stock policies could achieve a tight bound parameterized by the nonlinearity of the function, while for affine-bounded nonlinearities, we demonstrated that a collection of (s,S) policies could achieve a bound parameterized by the nonlinearity of the function and the number of inventories. We also showed that online algorithms from the literature could be used as a simpler alternative to dynamic programming in these settings. Numerical simulations indicate that for many problem instances there is additional structure that leads to better performance than our worst-case bounds . Future work includes deriving corresponding lower bounds for the performance of the decoupled policies as well as identifying particular problem classes that could admit tighter bounds. -A Cost Transformation Here we recap a useful cost transformation from the inventory control literature [ 16 , 14 ] . Consider rewriting the ordering cost c(u_{k}) as c(x_{k+1}-x_{k}+w_{k}) using the dynamics ( 1 ). For stationary ordering cost functions c with a linear term m\sum_{i=1}^{M}u_{k}^{i} , the transformed cost \hat{c} that neglects the linear term, i.e., sets m=0 , can be seen to neglect a cost of m\sum_{k=0}^{N-1}\sum_{i=1}^{M}w_{k}^{i} which is only a function of the stochastic demand. Therefore, we have the following relationship between the expected cost of a given policy \pi under the original costs P=(c,r,W) and the transformed costs \hat{P}=(\hat{c},r,W) : J_{\pi}(x_{0}\,|\,P){=}J_{\pi}(x_{0}\,|\,\hat{P})+m\mathbb{E}\left[\frac{1}{N}\sum\nolimits_{k=0}^{N-1}\sum\nolimits_{i=1}^{M}w_{k}^{i}\right]. (21) -B Tightness Example for Theorem 2 Proof. Consider an M -location infinite horizon problem P with demand w_{k}^{i}\sim\mathrm{Unif}(1,1+\delta) for all i,k and holding/backlog cost r^{i}(z_{k}^{i})=\delta\max\{0,z_{k}^{i}\}+p\max\{0,-z_{k}^{i}\} where \delta=\frac{\varepsilon}{l+2} . We define the set V=\{M,M(1+\delta)\} . The ordering cost is c(z)=lz for z\in V , and c(z)=hz otherwise; we assume p\gg h . We begin by deriving a lower bound on the expected cost of a decoupled base-stock policy \pi_{b}\in\Pi_{\textup{B}}^{M} from the initial condition where x_{0}^{i}=0 for all i . The policy is arbitrary aside from the assumption that \sum_{k=0}^{n}S_{k}^{i}\geq n+1 (equivalently, \sum_{k=0}^{n}u_{k}^{i}\geq n+1 ) for all i and for all n\geq 0 ; it is easily verifiable that any policy that does not satisfy this condition is suboptimal since it incurs backlog costs with probability 1 . We can rewrite the dynamics as x_{k+1}^{i}=\begin{cases}S_{k}^{i}-w_{k}^{i}&x_{k}^{i}