Online Stochastic Allocation of Reusable Resources

In the online optimization framework, information is revealed sequentially in time. The decisions are made without knowledge of the future information, but they can depend on past observations. In this work, we study online optimization algorithms in reusable resource allocation applications, where a resource unit is returned to the system after a period of usage duration, and can be further assigned to another customer. The decision-maker (DM) assigns limited inventories of reusable resources to sequentially arriving customers. In each time step, the DM’s decision leads to a set of allocation outcomes, consisting of the amounts of rewards earned, the amounts of resources consumed and the usage durations of the assigned resources. Our model captures a diversity of real-life applications include hotel booking, rental of cars and fashion items and cloud computing services. Our problem instance incorporates the following features:

1. 1.

   Multiple objectives. The DM’s goal is to maximize multiple types of rewards.

2. 2.

   Customer heterogeneity. The customers are associated with different customer types.

3. 3.

   Online setting. In each time step, the arriving customer’s type is drawn independently and identically from an unknown probability distribution.

4. 4.

   Reusability. Each type of resource is endowed with a stochastic usage duration, whose probability distribution is known to the DM. However, the DM does not know the the realized usage duration of an allocation before the resource is returned.

Features 1-3 are shared by both non-reusable and reusable resource allocation problems, while feature 4 is a distinct feature of reusable resource allocation problems. Without considering feature 4, our problem reduces to the non-reusable setting as in [1]. On feature 3, we remark that in many applications, given a customer type, its mean allocation outcome is accessible by machine learning (ML) approaches in a data-efficient manner ([2, 3, 4]). In many existing resource allocation research ([21, 5, 6, 7, 8]), the mean allocation outcomes are assumed to be prior-knowledge acquired through ML models. However, in applications where customer types are represented as high-dimensional feature vectors, the number of types can be exponential in the dimension of the feature vectors or even unbounded. Such a curse of dimensionality hinders the estimation on the proportion of each customer type. Therefore, we treat the probability distribution of each customer type as the unknown object. We further remark on feature 4 that our usage duration is defined in the same manner as [6] and [9], which are recent works on offline reusable resource allocation problems. We highlight that the probability distribution of each usage duration can be arbitrarily defined, which means our result does not depend on specific structures of certain usage distributions, such as the exponential distribution.

Traditional resource allocation problems [10, 11] concern the allocation of non-reusable resources. Online algorithms for allocating non-reusable resources have been extensively studied in [12, 13, 14, 1, 15, 16, 17]. These algorithms involve adaptive weighing processes that balance the trade-off between the rewards earned and the resources consumed. Most of their analysis largely depend on the monotonically-decreasing inventories. However, in our reusable model, the effect of an allocation may be different for each future time step, contingent on whether the allocated resources are returned, causing fluctuating resource consumption amount across consecutive time steps.

To our knowledge, this is the first paper to address reusable resource allocation problems in an online stochastic setting and demonstrate a near-optimal performance guarantee. Some studies focus on assortment planning problems in adversarial settings ([20, 18, 19]), and achieve non-trivial competitive ratios. Offline pricing and assortment planning problems have been studied in [6, 9, 20], where near-optimality is achieved in the form of approximation ratios under full model certainty. The main contribution of our paper can be summarized as follows.

• •

  Model generality. We propose a general reusable resource allocation model which allows for various decision settings (such as admission control, matching, pricing and assortment planning), multiple objectives (such as revenue, market share and service level), and large numbers of customer types or allocation types (the algorithm’s performance is independent of these sizes).

• •

  Near-optimal algorithm performance. We develop an adaptive weighing algorithm that trades-off among not only the resources occupied and the rewards earned, but also the usage durations. In the regime where each usage duration is short compared with the length of the planning horizon, our algorithm achieves matching near-optimal performance as the online non-reusable resource setting ([1]), as well as the the state-of-art offline reusable setting ([20]).

The remainder of paper is organized as follows. In Section II, we present our model and highlight some of its applications. An online algorithm and the corresponding performance analysis are proposed in Section III. In Section IV, numerical experiments are provided.

Notation. The reward types and the resource types are respectively indexed by two finite sets $\mathcal{I}_{r}$ and $\mathcal{I}_{c}$. A generic reward type or resource type is denoted as $i$. For each $i\in\mathcal{I}_{c}$, the DM has $c_{i}\in\mathbb{R}_{>0}$ units of resource $i$ for allocation. Each customer is associated with a customer type $j\in\mathcal{J}$, which reflects the customer’s features. We denote the set of possible allocation actions as $\mathcal{K}$, and each element $k\in\mathcal{K}$ as an action. The action set can model a broad range of decisions, which is elaborate in the end of Section II.

The DM allocates the resources in $T$ discrete time steps. In time step $t\in\{1,\ldots,T\}$, at most one customer arrives. We denote the customer type of the arrival at time $t$ as $j(t)$. In particular, we designate the type $j_{\textsf{null}}\in\mathcal{J}$ to represent the case of no arrival. We assume that $j(1),\ldots,j(T)$ are independently and identically distributed (i.i.d.) random variables over $\mathcal{J}$. We denote $p_{j}=\Pr(j(1)=j)$, and $\mathbf{p}=\{p_{j}\}_{j\in\mathcal{J}}$.

When a customer (denote his type as $j$) arrives, the DM chooses an action $k\in\mathcal{K}$. The choice leads to an array of stochastic outcomes, consisting of the amount of rewards earned $W_{jk}=(W_{ijk})_{i\in\mathcal{I}_{r}}$, the amount of resources occupied $A_{jk}=(A_{ijk})_{i\in\mathcal{I}_{c}}$, and the usage durations $\{D_{i}\}_{i\in\mathcal{I}_{c}}$. For the no arrival customer type $j_{\textsf{null}}$, we stipulate that $\Pr(W_{i^{\prime},j_{\textsf{null}},k}=A_{i,j_{\textsf{null}},k}=0)=1$ for all $i^{\prime}\in\mathcal{I}_{r},i\in\mathcal{I}_{c},k\in\mathcal{K}$, since there should be no reward earned and no resource occupied in the case of no arrival. To ensure feasibility in our resource constrained model, we assume that there exists a null action $k_{\textsf{null}}\in\mathcal{K}$ that satisfies $\Pr(W_{i^{\prime},j,k_{\textsf{null}}}=A_{i,j,k_{\textsf{null}}}=0)=1$ for all $i^{\prime}\in\mathcal{I}_{r},i\in\mathcal{I}_{c},j\in\mathcal{J}$. Selecting the null action is equivalent to rejecting a customer.

For each $j,k$, the stochastic outcomes follow the joint distribution $\mathcal{O}_{jk}$, namely $(W_{jk},A_{jk})\sim\mathcal{O}_{jk}$. We allow $W_{jk},A_{jk}$ to be arbitrarily correlated. For each $i\in\mathcal{I}_{c}$, the random usage duration $D_{i}$ is independent of $W_{jk},A_{jk}$. This assumption is also made in related works on offline reusable resource allocation, such as [6] and [9], since the usage duration reflects more of a customer’s intrinsic needs on each resource. We assume that $W_{ijk}\in[0,w_{\max}]$ for each $i\in\mathcal{I}_{r},j\in\mathcal{J},k\in\mathcal{K}$, $A_{ijk}\in[0,a_{\max}]$ almost surely for each $i\in\mathcal{I}_{c},j\in\mathcal{J},k\in\mathcal{K}$, and $D_{i}\in\{0,1,\ldots,d_{\max}\}$ almost surely for each $i\in\mathcal{I}_{c}$. Additionally, we denote $w_{ijk}=\mathbb{E}[W_{ijk}]$, $a_{ijk}=\mathbb{E}[A_{ijk}]$, and $d_{i}=\mathbb{E}[D_{i}]$.

Model uncertainty and dynamics. We assume that the DM knows the horizon length $T$, the values of $w_{\max}$, $a_{\max}$, $d_{\max}$, as well as $\Pr(D_{i}\geq t)$ for every $i\in\mathcal{I}_{c},t\in\{1,\ldots,T\}$. However, the DM does not know the probability distribution $\mathbf{p}$ over customer types. At each time step $t\in\{1,\ldots,T\}$, the DM observes the type $j(t)\sim\mathbf{p}$ of the arriving customer, and the mean outcomes $\{(w_{j(t),k},a_{j(t),k})\}_{k\in\mathcal{K}}$ specific to the type $j(t)$. Then, the DM chooses an action $k(t)\in\mathcal{K}$, and observes the stochastic outcomes of rewards $\{W_{i,j(t),k(t)}(t)\}_{i\in\mathcal{I}_{r}}$ and resources $\{A_{i,j(t),k(t)}(t)\}_{i\in\mathcal{I}_{c}}$ at time $t$. Our model uncertainty scenario included the case when the DM knows the mean outcomes $a_{ijk},w_{ijk}$ in advance. For example, the DM could have estimates on $a_{ijk},w_{ijk},\Pr(D_{i}\geq t)$ by constructing supervised learning models [2, 3, 4] on a pool of customer demand data.

An integer programming formulation. We let binary decision variables $X^{\pi}_{k}(t)$ be the DM’s decision under a non-anticipatory algorithm $\pi$, where $X^{\pi}_{k}(t)=1$ if action $k$ is taken at time $t$, and $X^{\pi}_{k}(t)=0$ otherwise. Under a non-anticiaptory algorithm, $\{X^{\pi}_{k}(t)\}_{k\in\mathcal{K}}$ depends on historical observations $\{j(s)\}^{t}_{s=1}\cup\{W_{i,j(s),k(s)}(s)\}_{i\in\mathcal{I}_{r},1\leq s\leq t-1}\cup\{A_{i,j(s),k(s)}(s)\}_{i\in\mathcal{I}_{c},1\leq s\leq t-1}$. The DM aims to maximize $\mathbb{E}[\min_{i\in\mathcal{I}_{r}}\sum^{T}_{t=1}\sum_{k\in\mathcal{K}}W_{i,j(t),k}(t)X^{\pi}_{k}(t)]$, which achieves the simultaneous maximization of all the reward types by ensuring max-min fairness. Here we maximize the rewards to keep in line with the resource allocation literature instead of minimize the regret as in the classical online convex optimization literature, but we remark that they are essentially eqivalent. For each $i\in\mathcal{I}_{c}$ and $t\in\{1,\ldots,T\}$, we require that the resource constraint

holds with certainty. The left hand side in (1) represents the amount of type $i$ resources occupied at time step $t$. Our goal can be formulated as the following binary integer program

We remark that the term $\mathbf{1}(D_{i}(\tau)\geq t-\tau+1)$ induces non-stationarity in resource consumption, since even when a DM selects the same action $k$ at $\tau_{1}<\tau_{2}$, their amounts of resource consumption $\mathbf{1}(D_{i}(\tau_{1})\geq t-\tau_{1}+1)A_{i,j(\tau_{1}),k}(\tau_{1}),\mathbf{1}(D_{i}(\tau_{2})\geq t-\tau_{2}+1)A_{i,j(\tau_{2}),k}(\tau_{2})$ at time $t$ are differently distributed. Existing works on non-reusable resources crucially hinges on model stationarity, which does not hold true in our setting.

A tractable benchmark. The goal of constructing a non-anticipatory algorithm that achieves the optimal value of (IP-C) is analytically intractable due to the curse of dimensionality. The intractability motivates us to consider an alternative linear program (LP), dubbed (LP-E), where the realization of the customer arrivals, their usage duration and outcomes exactly follow the expectation:

Define the optimal objective value of (LP-E) to be $\lambda^{*}$, and let the optimal objective of (IP-C) be $\hat{\lambda}^{*}$. The following lemma shows that $\lambda^{*}$ is a tractable upper bound for the expected reward of any online algorithms.

For the algorithm design, we further introduce a “steady state” benchmark, assuming the decision variables are invariant across time:

We denote an optimal solution of (LP-SS) as $x^{*}_{jk}$, and the optimal value of (LP-SS) as $\tilde{\lambda}^{*}$. We further define

This assumption indicates that our algorithm does not apply to large $D_{i}$, say for non-reusable resources where $D_{i}=T$ with certainty. In the next lemma, we show that $\tilde{\lambda}^{*}$ is close to $\lambda^{*}$.

We remark that under a wide range of usage durations, we can use (LP-SS) as a benchmark to gauge the performance of our algorithm. For instance, for light tailed $D_{i}$ (for example, there exists $u>0$ such that $\lim_{t\rightarrow\infty}\Pr(D_{i}\geq t)t^{u}=0$), we can take $\delta=\epsilon/T$, $\bar{d}(\delta)=d_{max}\log(d_{\max}T/\epsilon)$. If $D_{i}$ has bounded support, i.e. $D_{i}\in[0,d_{\text{UB}}]$ almost surely, we can take $\delta=0$ and let $\bar{d}(\delta)=d_{\text{UB}}$.

Applications. Before proceeding to our algorithm development, we highlight the generality of our model by discussing some of its applications, where the reward type set $\mathcal{I}_{r}$, the customer type set $\mathcal{J}$ and the action set $\mathcal{K}$ can be chosen to model a variety of decisions.

• •

  Admission control. In this setting, the DM is to either admit or reject each arriving customer [21]. Real life examples include patient inflow control in an emergency department or an ICU. The admission control setting can be modeled by letting action set $\mathcal{K}=\{\text{accept},\text{reject}\}$. The reward of a resource is fixed at $r_{i}$ for $i\in\mathcal{I}_{c}$. Upon taking an action $k$ for a type $j$ customer, an array of stochastic demands $\{A_{ijk}\}_{i\in\mathcal{I}_{c}}$ is generated. Our model captures different reward settings. We list some of the examples: for simultaneously maximizing the revenue/social welfare for each type of resource, define $\mathcal{I}_{r}=\mathcal{I}_{c}$ and $W_{ijk}=r_{i}A_{ijk}$. For maximizing the total revenue/social welfare of all resources, let $\mathcal{I}_{r}=\{1\}$ be a singleton, and define $W_{1jk}=\sum_{i\in\mathcal{I}_{c}}r_{i}A_{ijk}$. For maximizing the service level of each resource, we define $\mathcal{I}_{r}=\mathcal{I}_{c}$ and $W_{ijk}=A_{ijk}$. We remark that multiple kinds of rewards can be modeled simultaneously.

• •

  Assortment Planning. In assortment planning problems, one unit of resource $i$ is associated with a fixed price $r_{i}$. The DM influences the customers’ demands through offering different assortments of resources. Real life assortment planning examples with reusable resources include renting of fashion items and vehicles. Contingent upon the arrival of a customer, say of type $j$, the DM decides the assortment $k\in\mathcal{K}$ to display, where $\mathcal{K}$ is a collection of subsets of $\mathcal{I}_{c}$ ([9, 22]). Let $q_{ijk}$ denote the probability for customer type $j$ to choose product $i$ in assortment $k$. In the revenue management literature, the probability $q_{ijk}$ is modeled by a random utility choice model. The assortment planning problem (simultaneously maximizing revenue of each resource) can be incorporated in our model by setting $\mathcal{I}_{r}=\mathcal{I}_{c}$, setting $A_{ijk}$ to be the Bernoulli random variable with mean $q_{ijk}$, and setting $W_{ijk}=r_{i}A_{ijk}$.

Main results. In this section, we propose a multi-stage adaptive weighing algorithm (dubbed Algorithm $A$ as in “Adaptive”, and displayed in Algorithm 1). We first provide our main results. We assume there exists $\epsilon$ satisfying $\gamma=\Omega(\log(|\mathcal{I}|T/\epsilon)/\epsilon^{2})$, where $\mathcal{I}=\mathcal{I}_{c}\cup\mathcal{I}_{r}$. Let

denote the type $i\in\mathcal{I}_{r}$ reward achieved by Algorithm $A$, our main result is shown in the following theorem.

We remark that if $D_{i}$ has bounded support, i.e. $D_{i}\in[0,d_{\text{UB}}]$ almost surely for all $i\in\mathcal{I}_{c}$, then the above reward can be simplified as $\sum^{T}_{t=1}W_{i}(t)\geq T\lambda^{*}(1-O(\epsilon))-d_{\text{UB}}\tilde{O}(\epsilon)$ for every $i\in\mathcal{I}_{r}$ with probability at least $1-\epsilon$. In the case when $\delta\leq\log(|\mathcal{I}|T)/\epsilon$ and $\bar{d}(\delta)=o(T)$, our algorithm achieves a reward at least $T\lambda^{*}(1-O(\epsilon))$. This result nearly matches the [1] in studying an online non-reusable resource allocation problem, as well as [20] in the state-of-art work on the offline assortment planning with reusable resources.

The assumption $\gamma=\Omega(\log(|\mathcal{I}|T/\epsilon)/\epsilon^{2})$ means that the amount of resource $c_{i}$ for each $i$ is sufficiently large, and the planning horizon $T$ is sufficiently long. Crucially, the performance guarantee in Theorem 1 does not deteriorate even when $|\mathcal{J}|$ or $|\mathcal{K}|$ grows. Consequently, our Algorithm $A$ is applicable to complex scenarios when $|\mathcal{J}|>T$.

High-level description and comparison against [1]. Our Algorithm $A$ extends [1]’s idea of adaptive weighing from the non-reusable setting to the reusable setting. [1] proposes a multi-stage adaptive weighing algorithm to trade-off between the rewards and the resources. For each reward and resource constraint of a fluid LP (corresponding to our (LP-E)), a penalty weight is defined. The weight on each constraint progressively gets larger as the reward generated or the resource consumed gets closer to their total capacity (the capacity of each reward is approximated). [1] does not apply to the reusable setting, as their penalty weights and algorithm design depend on the monotonic-decreasing resources.

Somewhat surprisingly, we can still utilize their adaptive weighing idea. we approximate (LP-E) with a knapsack-constrained (LP-SS), and define penalty weights that incorporates the usage duration as well as the resource consumption. In a series of Lemmas that eventually leads to Theorem 1, we show that our algorithm effectively capitalizes the reusability of the resources to maximize the total rewards. We overcome the technical difficulty in non-monotonic and time-correlated resource levels, by achieving near-optimal performance. Nevertheless, we remark that the closeness of (LP-E) and (LP-SS) builds upon Assumption 1, and hence our algorithm is not applicable to the non-reusable setting.

A multistage online algorithm. In Algorithm 1, we divide the time horizon into $l$ stages $\{-1,0,1,\ldots,l-1\}$ where $l$ satisfies $\epsilon 2^{l}=1$ for some $\epsilon\in[\bar{d}(\delta)/T,1/2]$. Stage $-1$ consists of $t^{(-1)}=\epsilon T$ time periods. This stage is solely for exploration on the latent $\{p_{j}\}_{j\in\mathcal{J}}$, and the first $\epsilon T$ customers are served with random actions. Stage $r\in\{0,\ldots,l-1\}$ consists of $t^{(r)}=\epsilon T2^{r}$ time periods. The assumption $\epsilon\in[\bar{d}(\delta)/T,1/2]$ ensures that $l\geq 1$ (there is at least 1 stage) and $\epsilon T\geq\bar{d}(\delta)$ (each stage consists of at least $\bar{d}(\delta)$ time periods). We denote $j^{(r)}(s)$ as the type of the customer who arrives at the $s$-th time step in stage $r$ (where $s\in\{1,\ldots,t^{(r)}\}$), meaning that $j^{(r)}(s)=j(t^{(r)}+s)$.

In each stage $r\geq 0$, Algorithm $A$ consists of two steps. In Step 1, we estimate the optimum of (LP-SS). In Step 2, we define “penalty weights” on constraints of (LP-SS), and choose the action that balances between each constraint.

Step 1: Estimate the value of $\tilde{\lambda}^{*}$ (Line 3 of Algorithm 1). We first derive $\mu^{(r)*}$, which is the optimal objective value of the linear program $\text{(LP-RSS)}^{(r)}:$

where $\hat{p}^{(r)}_{j}=\frac{1}{t^{(r-1)}}\sum^{t^{(r-1)}}_{t=1}\mathbf{1}(j^{(r-1)}(t)=j)$, denoting the empirical customer distribution based on customer arrivals in stage $r-1$. $\text{(LP-RSS)}^{(r)}$ is a sample average approximation (SAA) of (LP-SS). It is worth mentioning that both (LP-SS) and $\text{(LP-RSS)}^{(r)}$ are highly tractable, even in assortment planning application when $|\mathcal{K}|$ is exponential in $|\mathcal{I}_{c}|$ ([23]). In addition, the knapsack-type constraints in $\text{(LP-RSS)}^{(r)}$ allows us to apply the adaptive weighing in Step 2 in a similar manner to the non-reusable setting. Given that $\mu^{(r)*}$ is easily obtained in Step 1, we define $\lambda^{(r)}$ in the following lemma, and show it is a progressively more accurate estimate of $\tilde{\lambda}^{*}$ as $r$ grows.

Step 2: Run an online algorithm given $\lambda^{(r)}$ (Line 4 - Line 10 of Algorithm 1). With slight abuse of notation, we write $A_{i,j(t^{(r)}+s),k}(t^{(r)}+s)$ as $A^{(r)}_{i,j^{(r)}(s),k}(s)$, $W_{i,j(t^{(r)}+s),k}(t^{(r)}+s)$ as $W^{(r)}_{i,j^{(r)}(s),k}(s)$, and $D_{i,j(t^{(r)}+s),k}(t^{(r)}+s)$ as $D^{(r)}_{i}(s)$. In addition, we denote $X^{(r)}_{j(t^{(r)}+s),k}(t^{(r)}+s)$ as $X^{(r)}_{j^{(r)}(s),k}(s)$. Define, at time $t$ in stage $r$, $Y^{(r)}_{i\tau t}=\sum_{k\in\mathcal{K}}\mathbf{1}(D^{(r)}_{i}(\tau)\geq t-\tau+1)A^{(r)}_{i,j^{(r)}(\tau),k}(\tau)X^{(r)}_{j^{(r)}(\tau),k}(\tau)$ and $Z^{(r)}_{it}=\sum_{k\in\mathcal{K}}W^{(r)}_{i,j^{(r)}(t),k}(t)X^{(r)}_{j^{(r)}(t),k}(t)$ respectively as resource $i$ consumed by customer $\tau$, and reward $i$ earned.

At the $s$-th time step of stage $r$, after observing the customer type $j^{(r)}(s)$ we take action $k^{(r)}(s)$ according to Line 7. The parameter $\phi^{(r)}_{i,s,t}$ represents a “penalty weight” for the resource constraint $i\in\mathcal{I}_{c}$ in (LP-SS). If the allocation decisions during $1,\ldots,s-1$ in stage $r$ leads to a high amount of resource $i$ occupation at time $t$, the penalty $\phi^{(r)}_{i,s,t}$ would also be high. Similarly, a lower amount of accrued reward type $i\in\mathcal{I}_{r}$ during $1,\ldots,s-1$ in stage $r$ leads to a higher value of the weight $\psi^{(r)}_{i,s}$. Both weights quantify the DM’s emphasis on resources and rewards.

Performance guarantee of Algorithm $A$. Our analysis involves bounding the total probability of violating each constraint in (LP-C) in all time steps. Each violation leads to unserved customers and lost rewards. We show that under Algorithm $A$, all constraints of (LP-C) are satisfied with high probability. To understand the choice of $k^{(r)}(s+1)$ in Line 7 of Algorithm 1, we introduce an auxiliary offline static algorithm (dubbed Algorithm $S$ as in “Static”). Algorithm $S$ requires knowing $x^{*}=\{x^{*}_{jk}\}_{jk}$, an optimal solution to (LP-SS), and a tuning parameter $\epsilon\in(0,1)$ for preserving capacities in anticipation of any constraint violation. At a time $t$, if a customer of type $j$ arrives, the DM selects action $k\in\mathcal{K}\setminus k_{\text{null}}$ with probability $\frac{x_{jk}^{*}}{1+\epsilon}$, and selects the null action $k_{\text{null}}$ with probability $\frac{\epsilon}{1+\epsilon}+\frac{x_{j,k_{\text{null}}}^{*}}{1+\epsilon}$. We denote $X^{S}_{j(t^{(r)}+s),k}(t^{(r)}+s)$ as $\tilde{X}^{(r)}_{j^{(r)}(s),k}(s)$. Define $\tilde{Y}^{(r)}_{i\tau t}=\sum_{k\in\mathcal{K}}\mathbf{1}(D^{(r)}_{i}(\tau)\geq t-\tau+1)A^{(r)}_{i,j^{(r)}(\tau),k}(\tau)\tilde{X}^{(r)}_{j^{(r)}(\tau)k,r}(\tau)$ and $\tilde{Z}^{(r)}_{it}=\sum_{k\in\mathcal{K}}W^{(r)}_{i,j^{(r)}(t),k}(t)\tilde{X}^{(r)}_{j^{(r)}(t),k}(t)$ where $\Pr(\tilde{X}^{(r)}_{j^{(r)}(\tau),k}(\tau)=1)=\frac{x^{*}_{jk}}{1+\epsilon}$ for each $\tau$ in stage $r$. A performance guarantee of Algorithm $S$ is provided in the following lemma.

For analysis sake, we consider a hybrid Algorithm $A_{s}S_{t^{(r)}-s}$ in each stage $r$. For Algorithm $A_{s}S_{t^{(r)}-s}$, the DM makes allocation decisions based on Algorithm $A$ in time step $\{1,\ldots,s\}$, and based on Algorithm $S$ in time step $\{s+1,\ldots,t^{(r)}\}$. We show that $A_{s+1}S_{t^{(r)}-s-1}$ outperforms $A_{s}S_{t^{(r)}-s}$, which inductively leads to the conclusion that the performance of the online adaptive Algorithm $A$ is no worse than the offline static Algorithm $S$ (see Lemma 4). This induction technique is introduced in [1] on the non-reusable setting. We need more refined techniques to disentangle the time-correlation between the resources constraints at each time step, and finally prove the following lemma.

Putting Lemmas 2 and 5 together, we have Theorem 1.

We consider an assortment planning problem. One unit of resource $i$ is associated with a fixed price $r_{i}$. Contingent upon the arrival of a customer, say of type $j$, the DM decides the assortment $k\in\mathcal{K}$ to display, where $\mathcal{K}$ is a collection of subsets of $\mathcal{I}_{c}$. Let $q_{ijk}$ denote the probability for customer type $j$ to choose product $i$ in assortment $k$. Therefore, the assortment planning problem (simultaneously maximizing the revenue of each resource) can be incorporated in our model by setting $\mathcal{I}_{r}=\mathcal{I}_{c}$, setting $A_{ijk}$ to be the Bernoulli random variable with mean $q_{ijk}$, and setting $W_{ijk}=r_{i}A_{ijk}$. In our test, the probability $q_{ijk}$ is modeled by the multinomial logit (MNL) choice model. Each resource $i\in\mathcal{I}_{c}$ is associated with a feature vector $\boldsymbol{f}_{i}\in\mathbb{R}^{m}$, and each customer type $j\in\mathcal{J}$ is associated with a set of feature vectors $\{\boldsymbol{b}_{ij}\}_{i\in\mathcal{I}_{c}}$, where $\boldsymbol{b}_{ij}\in\mathbb{R}^{m}$ for each $i\in\mathcal{I}_{c}$. The feature vector $\boldsymbol{f}_{i}$ could involve the fixed price $r_{i}$, and $q_{ijk}=\frac{\exp(\boldsymbol{b}_{ij}^{\top}\boldsymbol{f}_{i})}{1+\sum_{\ell\in k}\exp(\boldsymbol{b}_{\ell j}^{\top}\boldsymbol{f}_{\ell})}$ if $i\in k$, and $q_{ijk}=0$ if $i\not\in k$. In complement, the probability of no purchase is $\frac{1}{1+\sum_{\ell\in k}\exp(\boldsymbol{b}_{\ell j}^{\top}\boldsymbol{f}_{\ell})}.$ Notice that the size of the action set $\mathcal{K}$ scales exponentially with the number of products. Nevertheless, for the MNL models, $k^{(r)}(t)$ can be computed efficiently by solving a simple LP whose computational time is polynomial in $|\mathcal{I}_{c}|$ [24].