Online Learning and Pricing for Network Revenue Management with Reusable Resources
Authors: Huiwen Jia
Cong Shi
Siqian Shen
Venue: NeurIPS 2022 Accept (2022)
Keywords: pricing
network
bandits
stochastic systems
queueing network
mixing times

Abstract: We consider a price-based network revenue management problem with multiple products and multiple reusable resources. Each randomly arriving customer requests a product (service) that needs to occupy a sequence of reusable resources (servers). We adopt an incomplete information setting where the firm does not know the price-demand function for each product and the goal is to dynamically set prices of all products to maximize the total expected revenue of serving customers. We propose novel batched bandit learning algorithms for finding near-optimal pricing policies, and show that they admit a near-optimal cumulative regret bound of $\tilde{O}(J\sqrt{XT})$, where $J$, $X$, and $T$ are the numbers of products, candidate prices, and service periods, respectively. As part of our regret analysis, we develop the first finite-time mixing time analysis of an open network queueing system (i.e., the celebrated Jackson Network), which could be of independent interest. Our numerical studies show that the proposed approaches perform consistently well.

Online Learning and Pricing for Network Revenue Management with Reusable Resources
Huiwen Jia
Cong Shi Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109 shi chicoonumicc ch. edu
Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48 18909 hwj
j ia@umichh edu
Siqian Shen
Industrial and Operations Engineering
University of Michigan Ann Arbor, MI 4814 18109 si siqinnuumi ch. edu
Abstract
We consider a price-based network revenue management problem with multiple products and multiple reusable resources. Each randomly arriving customer quests a product (service) that needs to occupy a sequence reusable resources (servers). We adopt incomplete information setting where the firm does not know the price-demand function for each product and the goal is to dynamically set prices of all products maximize the total expected revenue of serving customers. We propose novel batched bandit learning algorithms for finding near-optimal pricing policies, and show that they admit a near-optimal cumulative regret bound of OJVVTT), where J, X, and I' are the numbers of products, candidate prices, and service periods, respectively. As part of our regret analysis, we develop the first finite-time mixing time analysis of an open network queueing system (i.e., the celebrated Jackson Network), which could be of independent interest. Our numerical studies show that the proposed approaches perform consistently well.
Introduction
Network revenue management (NRM) (Gallego and Van Ryzin 1997) has attained remarkable results in wide range of applications including airline management, electricity pricing, retailing, healthcare, and leisure (see, e.g., Williamson 1992 Talluri and Van Ryzin 2006 Özer and Phillips 2012). The
bulk of existing literature focuses primarily on canonical settings with perishable resources which the product once sold is permanently removed from inventory (Besbes and Zeevi 2012] Ferreira al. 2018 Chen and Shi 2019). Little progress has been made for NRM with reusable resources. mainly due to the complexity of analyzing the underlying stochastic systems (typically manifested as stochastic queueing networks). In this paper, we develop easy-to-ing to-implement online learning and pricing policies for NRM with reusable resources shared by multiple products and analyze their theoretical and empirical performances.
1.1 Problem Description
A service-providing firm is endowed with multiple types of reusable resources, each having fixed capacity. The firm sells multiple types of products (services), each requiring the use of sequence
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

of different types of reusable resources (servers). (See, e.g., Figure 2 Customers randomly arrive according to price-dependent multivariate Poisson process to request products. Upon requesting one particular product, a customer enters the system by going through a sequence of product-specified reusable resources one by one. During the service process, if there is no available next type of resource upon finishing using the previous type in the sequence, she will join the queue in front of this next type of resource and wait until the next available unit. Both the mean demand rate of each product and the average usage time of each resource depend on the posted price vector. However, such dependence is unknown to the firm a priori. We note that under a fixed price vector, the service system can be reduced to the celebrated Jackson Network (Jackson 1963 (957). The main objective of this paper is to design a "learning-w while-doing" algorithm to dynamically post prices of different products, in order to maximize the expected total revenue collected over finite time horizon.
is evident that NRM with reusable resources finds many important real-world applications, including cloud computing, hospitality industry, project management, and leisure (Lei and Jasin 2020). For example, firms such as Amazon and Microsoft offer diverse cloud computing services, each requiring a different set of computational resources (virtual machines) for a certain duration of time to finish their computational jobs (see, e.g., Kaewpuang et al. 2013 Püschel et al. 2015).
1.2 Main Results and Contributions
We propose new batched bandit algorithms for NRM with reusable resources (RNRM). The per- formance measure is regret, which is the revenue difference between our learning algorithms and a clairvoyant optimal pricing policy under full information. We use J, T to denote the numbers of products, candidate prices, and service periods, respectively. We prove in Theorems and 2 that the cumulative regret is Ö(JvXT) which matches the lower bound along the dimensions of X and T up to a logarithmic factor. It remains open whether one could improve the dependence on J. Note that all prior studies on non-reusable settings (e.g.. MMio and Wang (02T) show polynomial dependence on J at best. We test diverse instances to show numerical performance of our approaches.
The main contribution of our work is three-fold:
(Modeling.) To the best of our knowledge, we are the first to consider the joint learning and optimization problem in NRM with reusable resources. Prior literature on reusable resources only focused on augle-product settings (seeJia et al. (2020 2022) and references therein). it considerably more challenging to model and analyze the network setting where multiple products share multiple resources (with finite capacities), mainly due to the sequential use of resources (to finish up a service) and the evolving nature of available capacities in real-time We establish a connection between our model and the celebrated Juckson Network (Jackson 1963 1957).
(A (Algorithm.) We first develop a linear programming (LP) upper bound on the optimal objective value given full information. The LP model provides a static pricing control policy. Therefore. we can cast our RNRM as a multi-armed bandits (MAB) problem where we select among candidate prices (analogs of arms) to minimize the cumulative regret. There are two key challenges. The first lies in the fact that whenever the system posts new price, the arrival processes change immediately while the system still contains "old" customers from the previously posted price. Therefore, is difficult to analyze the transient system performance and keep track of the cumulative revenue in a dynamic pricing scheme. We resolve this challenge by proposing batched algorithms. Our algorithms separate the time horizon into successive batches and select a price for each batch. We further divide each batch into two intervals. In the first interval, the system completes serving the previous customers and reaches the steady-state under the new price. In the second interval, the system maintains the stcady-state (cxploiting the new price). This batched framework not only allows for system stabilization (under new prices) but also allows for infrequent Olog T') price changes, which is more implementable in practical settings (see Cheung et al. 2017). The second challenge is more mathematical because we must ensure that the regret does not scale exponentially in the number of products or resources (given the combinatorial nature of the underlying graph).
(Regret Analysis.) To cope with the first challenge mentioned above, we bound the loss of nonstation- arity by bounding the length of the first interval of each batch. We prove that the system can reach the new steady-star state reasonably fast (see mixing times of Jackson Network in Propositions 3 and 4 To the best of our knowledge, this is the first result giving a finite-time bound on mixing times of Jackson Networks. To cope with the second challenge, we decompose the resulting Jackson Network into
2

---

topological layers and present a novel nested coupling argument (based on the layers). The coupling argument ofjii et al. 2020) in the single-resource single-produce setting cannot be directly applied to our network setting. First, in the network of M/M/c queues, the arrival and waiting processes depend on previously visited resources, which significantly more complex to analyze upon price changes. To resolve this challenge, we have to carefully construct virtual and alternative queues to explicitly account for such dependency. On a high level, the difficulty lies in that the original queues have a time-varying rate from initial rate to stable rate upon any price change. Given a carefully chosen time period т, we first construct alternative queues that start from zero initial rate and ramp up directly to the stable rate at timestamp before that the customer distribution matches the original queues in period т. We then construct virtual queues that could clear all previously arrived customers at a specific time T, and show that their mixing times provide upper bound on the alternative queues and consequently the original queues. Second, even ignoring the subtleties of time-varying rates (upon price changes), if one applies the coupling argument of Jia al. (2020) in brute-force way to every resource the network, the coupling probability would result in an undesirable exponential scaling in the number of products. We decompose the network into topological layers so that the resulting coupling probability only scales linearly in the number of products.
1.3 Literature Review
NRM with Reusable Resources and Demand Learning. Network, demand learning, and reusable resources three key elements of this study. We only review related literature that shares at least two of the three elements.
NRM with demand learning. Due to the easy accessibility of real-time sales data, there have been recent studies on developing learning and pricing algorithms with probably near-optimal regret bound for NRM (see, e.g., Besbes and Zeevi 2012, Chen et al. 2019 Chen and Shi 2019 BBadanidiyuru et al. 2018 Agrawal and Devanur 2016 Ferreira et al. 2018). All the aforementioned study considers the canonical settings (first defined by Gallego and Van Ryzin 1997), i.e., non-reusable resources.
NRM with reusable resources. The only existing studies on RNRM are Owen and Simchi-Levi (2018). Rusmevichientong et al. (2020) and and Jasin (2020). Lei and Jasin (2020) considered a determin- istic service time assumption. and developed an asymptotically near-optimal real-time pricing control algorithm. Owen and Simchi-Levis (2018) considered a joint assortment and pricing problem under a multi-resource setting and provided constant factor performance guarantees. Rusmevichientong et al.) (2020) considered a dynamic assortment and pricing problem with reusable products and proposed a provably near-optimal policy based on approximate dynamic programming.
Demand learning with reusable resources. The aforementioned literature on reusable resources all assumed known distributional information of the underlying model. There has been little work considering demand learning for service systems with reusable resources due to complex underlying system dynamics. The only studies that considered demand learning for reusable resources are Chen it al. (2020). Jia et al. (2020) 2022). and all considered only the single resource setting. Chen et al. (2020) proposed an online learning framework for a dynamic pricing and capacity sizing problem in a GI/GI/1 queue and Jia et al. (2020 2022) developed MAB-based algorithms for optimal dynamic pricing an M/M/c queue for the single product single resource setting.
To the best of our knowledge, we are the first to thoroughly study all three elements.
Transient Aalysis of Jackson Networks. Jackson Network has received much attention among the queueing networks because its steady-state distribution is particularly simple to compute as product-form solution [Jackson] 1963 1957). 'he queue lengths across the nodes in Jackson Networks, i.c., a network of M/M/c queues, during the transient state can be bounded via techniques of stochastic dominance (see Massey 1986 1984 1977). However, how the network reacts to system changes remains an open question (see, e.g. Mohamed et al. 2003 2005). Kelton and Law 1985) pointed out that queueing system needs to run "long-enough" for removing the effects brought by the initial starting point and then reach an ensured "steady-state portion of the run. The only work that explicitly developed finite-time bound mixing times of queueing system is recent paper by Dia et al. (200)). In contrast, our paper gives the first finite-time high probability bound on mixing times of Jackson Networks (a network consisting of M/M/c queues) upon action changes.
Batched Bandit Approaches. UCB2 (Auer al. 2002 and Improved-UCI. (Auer and Ortner 2010) were implicitly -bbtchh policies with M = Olog T)) Later, Perchet et al. (2016) studied batched
3

---

MAB in the two-armed case under static batch design and Gao et al. (2019) extended the algorithms the general multiple-anmn armed case and adaptively determined batch size. There is also rich literature focusing on batched MAB problems with switching cost. For example, and Xu (2019) treated the finite
Desa-Bianchi et al. (2013)
considered uniform switching cost in the objective and switching cost budget as a hard constraint. In contrast, we construct the batched action framework to control the loss of the nonstationarity (resulted from the transient time after each action change).
2 Problem Formulation
Consider a firm that manages I types of reusable resources to provide J types of products over a finite time horizon T. Denote the capacity of resource type i I as c₁. At the beginning of each period, the firm posts a price x = {z, j E J} for all products from a given price candidate set X' C. RI Let 1 [Z] J = JJ]. and X = | Each arriving customer requests one product j E J. which is processed through an ordered sequence of resources. Customers arrive following a price-dependent multivariate Poisson process with a total rate (x), which is unknown to the decision maker a priori. The service time of resource i follows an exponential distribution regardless of which product type it belongs to, which also depends on posted price x. If there is not enough capacity for the current resource, the customer will join the queue of this resource until being served. The resources are released to process the next customers upon finishing serving the current ones.
We consider two popular payment models, the lump sum payment model (presented in the main manuscript) and the service duration-dependent payment model (presented in Appendix
(Lump sum payment model.) A customer of product j E J pays lump sum Ty to the firm. More elaborately, if a customer chooses product j. then the customer will pay 2; to the firm regardless of how long the services over resources are. In our illustrative example, each product can be quoted fixed price (i.e., not service duration dependent), which could seen as preset "cloud solution package". The customers may prefer or benefit from this fixed price (contract) from their own accounting and cash flow management. Under this model, even though the customers are not sensitive to service durations, the cloud platform is nevertheless sensitive to service durations since they affect how many products/services can be completed within a finite horizon.
(Service duration dependent payment model.) A customer of product j E J pays the amount that is equal the per-unit-time æ., multiplied by the total service duration. This payment scheme is duration dependent, which is also ubiquitous, especially in cloud computing applications (e.g., how much time is spent using EC2 in our illustrative example). In the interest of space, the model and analytical details are presented in Appendix F
Consider a resource-consumption matrix A₁ı E R.x1, where element ays- = 1 indicates that service type j requires to processed on server type i. We use an T-dimensional vector, y E (0, 1,... ) to denote the number of customers across different types of resources. The firm aims at finding pricing policy as क : {(y, 1) : y E (0, 1,.., ,o)" : T) - X, where the firm selects price (y,t). t) X for period when there y customers in the system the beginning of period t, to maximize the expected cumulative revenue Y².
Assumption (fTurn-off" price.) For each product j E J, there exists a "turn-off" price Pj < oo such that the demand for this product is zero when the posted price is larger than this turn-off price.
Assumption is widely assumed in NRM studies (see, e.g., Lei and Jasin 2020). This turn-off price can be used effectively turn off the demand for undesired products whenever needed. Therefore, for each candidate price x E X. we can further decompose the products into turn-on product set Ton Jmm(x) and turn-off product set [at(x), where the latter can be empty.
A Assumption 2. There exists an order of server types I such that the processing sequence of servers i1, i2, in always has in < i2 <...< in for any product j E J.
One can understand Assumption 2 via viewing a network. Consider graph with resources as nodes and draw directed are from node to i' if any product requires successive processing on resources i and F. If the system satisfies Assumption [ then this graph acyclic, i.e., no cycles, and there exists at least one topologiaal order such that all arcs are from smaller index to a larger index. Without

---

loss of generality. we consider one such topological order when referring to resource i in the rest part of this paper. To better utilize this network representation, we also add a source node represent customers entering the system and a sink node I to represent customers exiting the system. Thus, the consumption matrix can be extended to Aji E Jx++2) and ajs = ajt = 1 for all products.
Assumption 3. (Product-form demand.) Any given price vector x induces a (Markovian) routing matrix P(x) where its (i, 1'tt entry pi represents the product demand portion who will consume resource i' next out of those who consume resource i. Then the demand rate for any product j E J, represented by a sequence of resources 8, i1, $1.82..... ........n........... i, is given by
a = ax Phi.22 ... Pin-i,
which means that the demand rute for product j is equal to the total demand rate a(x) times a sequence of rousing probabilities of P(x), under posted price vector x.
We use Figure Znn in the Appendix to demonstrate a concrete example. With Assumptions 2 and 3 the service system under any posted price E X can be reduced to Jackson Network consisting with 7 number of M/M/c queues (when the system only contains customers arriving under this price, i.e., after finishing serving other customers arriving under the previously posted prices). The main idea is that there exists a mapping x - axx), P(x) that gives rise to product demand pattern. Note that our assumptions are mild in the sense that this mapping can be nonparametrie. The decision maker does not know this underlying mapping and needs to learn it while maximizing revenue on the fly.
Given any price x. (i) one hand, this price affects the total demand (xx) entering the system. (ii) On the other hand, this price affects the internal competition between products, which is reflected in the server routing matrix P(x). As result, axx) and P(x) define Jackson Network well and the demand rate a (x) of each product type is also determined (use vector Tx E R to denote demand of products). We use (x) and μt; (x) to denote the demand and service rates of resource type i.
Assumption 4. (Stability.) The queueing system of each resource is stable under any price, i.e., (x/4(x)= > (x). Therefore, the Jackson Network is stable as well.
Assumption 4 Jnsures that the underlying Jackson Network is stable under any candidate price (i.e., the queue length will not grow indefinitely). This assumption can be readily satisfied by putting appropriate lower bounds on the price vector.
Assumption (Change of rates.) For any node, consider the arrival and service rates (A1, U1) and (A2, U2) under X1, E X where x1 2 X2, also denote the utilization factor by P1 = >1/11 and
P2 = X2/U2, μ2, respectively, then 1) \ - A2 S -3e 3ologgp
P1
and 2) if μn >> j12, then p 2 22
This assumption is used to justify Lemmas 3 and (used in the proof of Propositions 3 and 4 and the original proofs are in Dia et al. (2020). These conditions are mild and easy to validate in practice in the following sense. 1) The difference in arrival rates between two prices is bounded (by a large constant). This can be easily satisfied by interpolating intermediate prices in the candidate price set X. 2) If both the service and arrival rate under price is higher than or equal to another price, the utilization factor in the former case must be greater than the latter squared. A simple sufficient condition to guarantee P1 2 p is P1 2 P2, which reduces to \1 2 f1/ u2, and thus the practitioners only need validate that the ratio of change in arrival rates exceeds the ratio of change in service rates.
Assumption 6. We assume log T 2 (to ensure sufficient time for mixing).
3 Regret, Relaxed Regret, and Static Price Benchmark
Under the full information scenario, where the firm knows the underlying arrival rate axyx) of all products j E I under any candidate price x E X. We denote a state-dependent optimal policy as x", where π² = argmax, y and let Y = y* Therefore, the regret of any pricing policy x can be defined as Regret( x T) Y Y In short, we aim finding heuristic pricing policies that lead to small regret. However, finding the state- dete-deeendent optimal pricing policy x² is computationally intractable even under the full information scenario. Firstly, it requires solving a dynamic program with an infinite number of potential states, in the form of (y, (), which suffers from the curse of dimensionality. Moreover, the transient dynamics of a queueing network are complex and hard to analyze especially when the offered price changes over periods. Thus, it is impossible to obtain x²
5

---

and Y To tackle this problem, we develop an upper bound on the expected revenue achievable by the state-dependent optimal expected revenue (see similar approach in Jia et al. 2020).
An LP based upper bound. Consider continuous decision variables Tyt- Oyts and Yye for y E {0, ,,.., o0.' t= I..... T, and x E X. We formulate linear program (LP) as follows. We also discuss the sufficiency of using (y, 1) as the state variable Appendix C
ytp_ = mmaxx Y
Σ
Σ
RyeY
(la)
yE
1=1
Σ
Oyt = V4 = ,...., T
(1b)
Σ Tyt =1
Vy E {0, 10. oo)' == I....,,
(1c)
XEX
yt S
Σ
Tyl xxx x Vy 1o..,..... 00 Vt = I.....IT
(1d)
xEX
0 S Gyt S 1
Vy 10,1....,. oo)' Vt -M=1.... T Vy (0,1,.....0) VI =I V (1f)
(Ie)
0 0 .. 1
Proposition 1. The LP solution provides an upper bound on the optimal revenue, i.e, Y < Y and y = T og where x arg maxxex ax x.
Proof Sketch. Consider an arbitrary policy म. Let variable oy: take the value of probability that the system has y customers at the beginning of period for y E {0, 1,..., oo) and = 1,... T. Let variable zy: = if the policy á chooses price x at state (y: t), and otherwise. Let variable Yy take the value of expected revenue collected before the end of period T from the customers who arrive during period f, when the system has y customers at the beginning of period t. Then we can show that the decision variables (T,a, a, Y) associated with any admissible policy must satisfy the constraints of the linear program (T). and the expected revenue of this admissible policy is exactly the corresponding objective value in (1). We can readily check that T a is upper bound of LLP We can construct a solution which obtain this upper bound and thus YLP = T of X.
Definition 1. The relaxed regret is defined as Regret( T) YLP y
Based on Proposition] I we have for any policy æ, the corresponding relaxed regret is valid upper bound of its regret, i.c., Regret(T, n. T) 2 Regret(T,, T), and it suffices to bound the relaxed regret.
4 Batched Bandit Algorithms
The basis for implementing an Upper Confidence Bound (UCB) type of algorithm is identifying an upper confidence bound of the expected collected revenue of each candidate price. We start with the steady-state revenue rate. We can show that this steady-state revenue rate can be used to compute a lower bound of the expected revenue during consecutive periods (see proof of Theorem upper confidence bound of the steady-state revenue
[. Therefore, it is equivalent to deriving rate based on historical sales information. Jia et al. (2020) established a concentration bound of the steady-state revenue rate under the single product setting. Here we develop concentration bound for the multi-product multi-resource setting.
We use (x) to denote the number of arrived customers requesting product j under price x. We use (x) (x) to denote the observed time interval between the arrival time of customer k and the arrival time of customer k who are requesting product j under the price x. We use (x) to denote the
empirical mean of the inter-arrival time and thus d,(x) = [x)(x) (x))x)/n(xx), for j E J. Proposition 2. For any price X, if the number of arrival time observations for each turn-on product n (x) > 8log(J+T) for j E (x), then we have
PPG
ax x
Σ
Ij
dx(x) (x) 2 1
2 T
(x)
(x
(x)

---

The proof of Proposition is based on the concentration inequality for sub- sub-exponential random variables (see, e.g., Boucheron et al. 2013 Jia 2020) and is provided in Appendix C X x is the steady-State revenue rate and denote it by r(ax, x). Proposition says that with certain amount of arrival time observations of turn-on products under candidate price, we can derive valid upper bound of the steady-stae staat revenue rate with a high probability guarantee. Hence, we define the corresponding upper and lower confidence bounds of the stationary revenue rate associated with price by the end of period t follows.
Note that
Definition 2. Define Rad, (x) = EjEJm(x)) 3, s2
f,(x)) as the confidence radius by the end of period t. The upper and lower confidence bounds of the revenue rate associated with price x are:
Ux(x)= = Σ
jEJm((x dx(x) + (x),(x),
[x(x) = Σ
dx(x) -Rad((x).
(2)
jEIm((x)
4.1 RNRM-UCB
With Definition 2 we can leverage the idea of UCB to solve RNRM. We separate periods into two phases. The first phase is the Warm-up Phase, where offer each candidate price by one until collect 8 log(J++) number of arrival time intervals for each turn-on product Ton [x)(x) under each price. Therefore, the total length of this Warm-up Phase O(X log(J++))) After this Warm-up Phase, Proposition i valid to use. The second phase is the Learning Phase. The UCB algorithm cannot be directly used because in order to estimate the expected revenue when offering price, we have to wait until the system reaches the steady-state. The key idea is to reduce the number price changes and further reduce the intractable transient state performance. We separate the Learning Phase into M number of batches. Define I. 2 Vm = 1,..., M. Each batch m contains LT periods, where T = (log 2 and the number of layers defined in Definition Therefore, the batch size is exponentially increasing. We can then add m in the subscript of notation (Nmy (xx,, (x), (mn((x) Radm (x), Um (x), Lm (x)) to represent their values by the end of batch m. At the beginning of each batch m + 1, AARM-UCB chooses price x with the highest Um (x) and offers this price during batch 1. We present the algorithmic details in Algorithm
Algorithm 1 RNRM--UB.
1: Input: T, X. service network, turn-off prices.
2: Initialize: L, T, Ims M, m 0.
3: Warm-up Phase:
4: for x E X' do
5: Offer x, record inter-arrival time d (x) for arriving customers of product j Ton (x).
6: if "nmm((] 2 8 log(J2/4TT) for (x) then
7: Continue.
8: end if
9: end for
Compute and update UCB for all prices as defined in
11: Learning Phase:
for m 1,..., M do
13: Choose X,, argmaxxexx U 1
Offer x, in batch m. i.e., for Im periods.
Record inter-arrival time d (xm) for arriving customers of product j E Ton (xm).
16:
Compute and update UCB of xm as defined in (
17: end for
4.2 RNRM-TS
Considering the firm holds prior information about the rates, then we can add the Bayesian assumption
to this RNRM problem. By the conjugate prior theory (see, e.g., Minton et al. 1962 Diaconis and
Ylvisaker 1979), we assume that RNRM-TS holds Gamma priors on (x) product E (x). Vx X and the posteriors updated by the end of batch m, Vm 1,... M. Specifically,
7

---

After observing one arrival time interval (x) of product j while offering price x, the posterior distribution of ax(x) is computed as Gamma(77 (x) + 1, (x,, + dx)(x)). To implement RNRM-TS, at the beginning of batch m, sample parameters à; (x) for product E Jon(x), Vx X, following the updated posterior distributions. Then we offer the price with the maximum sampled stationary network revenue rate
set the prior distribution of (x) as Gamma(y) (
(8,(()).
r(āx, x) = Ejea.(x) Xx)r(x). We present the algorithmic details of RNRM-TS in Algorithm
Algorithm 2 RNRM-TS.
1: Input: T, X. service network, turn-off prices, 172,(0), gaz(x), Vj E [on(,), Vx E X.
2: Initialize: L, T. Im M, m = 0.
3: Warm-up Phase:
4: for x X' do
5: Offer x, record inter-arrival time d (x) for arriving customers of product j E Jon (x)(
6: if "nmmm(x) 8 (og((I/)T)) for j E Ton (x) then
7: Continue.
8: end if
9: end for
10: Update 177)(x), (x,(xx, Vj E [xn(x), Vx E X.
Learning Phase:
12: for m = l,..., M. do
Sample d, (x) Gamma (1705(0), (x)( for product E Jxn(x), Vx
14: Choose Xm = argmax xEx x (ūxx x).
Offer Xm. in batch m, i... for IMLT LT periods.
Record inter-arrival time d,r (Xm) for arriving customers of product j E Jam (Xm).
17: Compute and update 1 (a,(xm), Vj [xn().).
18:
end for
Performance Analysis
5.1 High Probability Bound for Mixing Time
When the firm starts service from an empty state, i.e., zero customers in the network service system, or switches to another price from the currently offered price, the service (queueing network) system enters a transient state and needs a certain amount of time to reach the steady-state again (referred to as the mixing time). Recall that the service system can be reduced to a Jackson Network under specifically offered price vector, upon completion of existing customers under the previously posted price. Therefore, we evaluate how quickly a Jackson Network can reach the steady-state. To the best of our knowledge, this the first result giving finite-time high probability bound on mixing times of Jackson Network system (upon action changes). Technically, develop between this target system and a virtual system starting from a state sampled from the steady-state distribution and maintaining the steady-state thereafter.
coupling argument
Poisson arrival and departure under steady-state. Under the steady-state of M/M/c queue (if exists, i.e., A/cμ 1), then the process following which the customers leave the system is also Poisson process with rate X. Therefore, one can easily derive that the arrival as well the departure processes of each type of resource (each node in the network representation) are Poisson processes with the same rate X; under the steady-state (see the celebrated Burke's Theorem Burke 1956).
Jia et al. (2020) is the only work for studying finite-time bounds on the mixing time for an M/M/c queue. However, their results cannot be directly applied here because (i) the arrival process of each resource is not well-defined Poisson process and (ii) the starting point of the later queues is not zero state nor steady-state of old system parameters. Even with these two challenges tackled, this approach will induce a mixing time which is linear on the number of resources. This result is not desired for systems with multiple (especially large) resources. We develop a new mixing time analysis for Jackson Network. We divide the resources of the service network into layers and derive high-pne high-probability mixing time that only linear on the number of layers.

---

We divide the nodes (types of servers) into layers indexed by the maximum number of previously occupied nodes (including the virtual source node) along the service routes of all products. For example, Nodes I and 2 of the illustrative example (see Figure 2 is Layer-I nodes, and Node 3 is a Layer-2 node. We denote the number of layers by I. and the set of Layer-l nodes as It-
Definition 3.
Proposition 3. (Coupling probability of a Jackson Network starting from empty state) Define A to be the event in which the Jackson Network reaches the steady-state by time L. For i 2 Lt, where T = (log T)2 we have (P(A.) 2
21
T
Proof Sketch. We use the aforementioned Poisson arrival and departure property of the nodes in a Jackson Network bound the mixing time of the nodes layer by layer. We define events Ar {all layer-I nodes reach the steady-state by time t'} and A; {the node reaches the steady-state by time t'}. By treating the nodes in the same layer together,
P(A.) P(ALr, AL LL 2 P(A..)) II P( A AQ-1)71-1).
We then prove that P( AlA11 A.-.A.....AA------ coupling argument between the target queue (with the help of an artificially constructed alternative queue) and a virtual queue starting from a state sampled from the steady-state distribution and
(2T)/T², where 1 = [T,], by establishing
maintaining the steady-state thereafter. The detailed proof is provided in Appendix E
In addition, the transient state of the Jackson Network, well as each resource queue (or each node), can be induced not only by starting from empty state but also by changing the price from the previously posted price. It is possible that when new price is posted, the customers who arrived under the previously posted price still remain in the system. Therefore we also need to ensure that the coupling also occurs with high probability when price changes.
Proposition 4. (Coupling probability of Jackson Network starting from steady-state of the previous price.) Define B, to be the event in which the Jackson Network reaches the steady-state by time L. For t 2 2Tr,, where = (log T)2, we have (P.),) 2
41
T
We define B and Bj, similarly and bound P(B B2r.1 ... (2(1-11,,-11 2 I A.s by decomposing the scenarios 7
Proof Sketch. This proposition derived based on Proposition 3 and Assumption 5
by how the arrival and service rates are changing when considering each resource queue.
5.2 Regret Bounds of RNRM-UCB and RNRM-TS
The high probability bounds for mixing time of Jackson Network developed in $5.1 help bound the loss due to the nonstationarity, and thus we are ready to carry out the regret analysis of RNRM-UCB.
Theorem 1. The T-period cumulative regret of RNRM-UCB is bounded by Ô (JVXT).
Note that the regret lower bound for nominal MAB (where J 1) is R(VXT) (see, e.g., Theorem 2.1 in Slivkins (2019), which suggests that our regret bound is tight, if the system size J is fixed.
Proof Sketch. The regret of the Warm-up phase is at most linear on the length of the Warm-up Phase, i.c., O(X lo4(J)/4T)) We decompose the relaxed regret in the Learning Phase into two parts. The first part is called loss of nonstationarity and it represents the revenue loss induced by the transient performance when changing the price. For batch m, we can derive that the expected revenue collected under the selected price Xm. as r(āx.., Xm In The second part represents the loss of suboptimality, which is induced by not offering the optimal state-independent price in certain time periods. This part can be further rewritten as A (xx))..
O(T)) with Proposition 4
A(x,)) V Lo and
A A(xm. = (r(0z, x) Um (X)) + (X.. - T.m (x..)) + (Iam (xm) (a0))-(xxx_.. r(āx... these three terms separately based on Proposition and Lemma Combine all results together, we reach an Õ(JVXT) regret bound. We provided detailed proof in Appendix E
Xm.). We bound
We use Bayesian regret as the performance measure of RNRM-TS, which is typically used for the Bayesian setting and is computed as the expected regret of the instance in expectation over all problem instances. Similarly, we define relaxed Bayesian regret.
Definition 4. Denoting all the events before period by Fr, Vt O, we define the relaxed Bayesian regret of policy π by period T as
BR( Eso, (x))hi
[B|y"r Y Frl].
9

---

The relaxed Bayesian regret bound of RNRM-TS is in the same order as RNRM-UCB (Appendix E
Theorem 2. The T-perior cumulative Bayesian regret of RNRM-TS is bounded by ((JXT).
Numerical Results
We consider T 2000, / = 2 with capacity 0 02 2, = with product-resource orders and X = (11 2, 2.3 [2. (2, We set the underlying arrival rates of candidate
(1,2, - 2), prices ([4,2, [3, 4,3, [2.5, 2.5]] and uniform service rates [5 4.5) for all prices. We adopt the blind network revenue management algorithm proposed in Besbes and Zeevi (2012) to our setting as benchmark. This benchmark algorithm tries each price for 0T/X periods and then selects the price with the highest revenue for the rest of the periods. We set 0 as 0.22, 0.1, and 0.05 in three Besbes and Zeevi 2012) benchmarks, respectively (the same as the settings Table I in the original paper [Bsbbes and Zeevi 2012). To conclude, we implement five pricing algorithms: RNRM-UCB, RNRM-TS, and three benchmark policies with different values of 9.
Figure Ta shows the offered price over periods of each algorithm and Figure Tb depicts the cumulative For all algorithms (except "OPT"), the revenue collected from the simulation where the system starts with customers at time O. We observe
time-average relaxed regret, i.e., = - -Y
that both RNRM-UCB and RNRM-TS identify the best price (P1) through the learning process and
the time average regret shrinks to zero very quickly.
3.0
2.5
2.0
1.0
RNRMITS
OPT
Benchmark 0.05
Bendhmark 3.05
Benchmark 0.1
Benchmare-0.1
0.0
Bendhmank-33 2.22
OPT
1.00
200
400
500
700
250
500
750
10000
1250
1500
1750
2000
Perlods
Porlods
(a) The offered prices.
(b) The time-average cumulative regret.
Figure 1: Offered price and time-average cumulative regret of policies. Note that the price selections keep the same after Period 750 and therefore we only plot for Periods 750 in subfigure (a).
7 Conclusion and Broader Impacts
We proposed two new batch bandit algorithms for RNRM problems with multiple products and multiple reusable resources. We established optimal regret upper bounds and demonstrated superior computational results. This work solves an important practical problem and we believe that our approach will open many doors to learning more complex stochastic systems (especially in network settings). There are two immediate future research questions: (1) how we can accommodate con- tinuous price space; and (2) how directions would need significant methodological innovations to be developed.
extend arrivals and services general distributions. Both
Acknowledgments and Disclosure of Funding
The authors would like to thank anonymous reviewers for their detailed and helpful comments, which have helped improve the content and exposition of this paper. This research partially supported by an Amazon research award and Department of Energy award #DE-SC0018018.
10

---

References
Agrawal S, Devanur N (2016) Linear contextual bandits with knapsacks. Lec DD, Sugiyama M. eds., Advances
Neural Information Processing Systems, volume 29, 3458-3467 (Red Hook, NY, USA: Curran Associates Inc.).
Auer P. Cesa-Biande N, Fischer P (2002) Finite-time analysis of the multiarmed bandit problem. Machine
Learning 47(2):235-256.
Auer P. Ortner R (2010) Ucb revisited: Improved regret bounds for the stochastic multi-armed bandit problem.
Periodica Mathematica Hungarica 61(1-2)555-65
Badanidiyuru A. Kleinberg R. Slivkins (2018) Bandits with knapsacks. Journal of the ACM 65(3):1-55.
Besbes O, Zeevi A (2012) Blind network revenue management. Operations Research 60(6):1537-1555 -5500.
Boucheron S. Lugosi G. Massart P (2013) Concentration inequalities: A nonasympiotic theory of independence
(Oxford, UK: Oxford University Press).
Burke PJ (1956) The output of queuing system. Operations Research 4(6):699-704.
Cosa-Bianchi N, Dekel O, Shamir O (2013) Online learning with switching costs and other adaptive adversaries.
Bottou L, Burges CJ, cds., Advances Neural Information Processing Systems, 1660-166 (Red Hook,
NY, USA: Curran Associates Inc.).
Chen Q. Jasin S. Duenyas I (2019) Nonparametric self-adjusting control for joint learning and optimization of multiproduct pricing with finite resource capacity. Mathematics of Operations Research 44(2):601-631,
Chen X. Liu Y, Hong G (2020) An online learning approach to dynamic pricing and capacity sizing in service systems. Technical report, Chinese University of Hong Kong. Shenzhen, China. Available arXiv:2009,025 02911.
Chen Y, Shi (2019) Network revenue management with online inverse batch gradient descent method. Technical report, Forthcoming in Productions and Operations Management. Available at SSRN 3331939.
Cheung WC, Simchi-LLevi D, Wang H (2017) Dynamic pricing and demand learning with limited price experi- mentation. Operations Research (5(6):1722-173)
Diaconis P. Ylvisaker D (1979) Conjugate priors for exponential families. The Annals of Statistics 269-281
Ferreira KJ, Simchi-Levi D. Wang H (2018) Online network revenue management using Thompson sampling. Operations Research 1666)1155-6
Gallego G, Van Ryzin G (1997) A multiproduct dynamic pricing problem and its applications to network yield management. Operations Research 45(1):24411
Gao Z, Han Y, Ren Z, Zhou Z (2019) Batched multi-armed bandits problem. Wallach H, Larochelle H, Beygelz- imer A, d' Alché Buc F, Fox E, Garnett R. eds., Advances in Neural Information Processing Systems, volume 32, 503-513 (Red Hook, NY, USA: Curran Associates Inc.).
Jackson JR (1957) Networks of waiting lines. Operations Research 5(4):518 1211
Jackson JR (1963) Jobshop-like queueing systems. Management Science 10(1):131-142.
Jia H. Shi C. Shen S (2020) Online learning and pricing for service systems with reusable resources. Technical report, Forthcoming in Operations Research. Available at SSRN 3755902.
Jia H. Shi C. Shen S (2022) Online learning and pricing with reusable resources: Linear bandits with sub- exponential rewards. Chaudhuri K. Jegelka S. Song Szepesvari C, Niu G. Sabato S, eds.. Proceedings of the 39th International Conference on Machine Learning, 10135-10160 (The Cloud: JMr.R.org).
Kaewpuang R. Niyato D. Wang P. Hossain (2013) A framework for cooperative resource management in mobile cloud computing. IEEE Journal on Selected Areas in Communications 31((2))2685 2700.
Kelton WD, Law AM (1985) The transient behavior of the M/M/s queue, with implications for steady-state simulation. Operations Research 33(2):378-39
Lei Y, Jasin S (2020) Real-time dynamic pricing for revenue management with reusable resources, advance reservation, and deterministic service time requirements, Operations Research 6873):676-6855
Massey WA (1984) An operator-analytic approach the jackson network. Journal of Applied Probability 21(2):379-33 333333.
Massey WA (1986) A family of bounds for the transient behavior of a jackson network. Journal of Applied Probability 23(2):543-5k) 549.
Massey WA (1987) Stochastic orderings for markov processes partially ordered spaces. Mathematics of Operations Research 12(2):35-3367.
Miao Wang Y (2021) Network revenue management with nonparametric demand learning: \sqrt (sqit(T)-rege -reegret and polynomial dimension dependency. Technical report, McGill University, Canada. Available at SSRN 3948140.
Minton P. Raiffa H. Schlaifer R (1962) Applied statistical decision theory. American Mathematical Monthly 69:72.
11

---

Mohamed AM, Lipsky L. Ammar R (2003) Transient model for jackson networks and its approximation. International Conference On Principles Of Distributed Systems, 198-209, Springer (The Cloud: Lecture Notes in Computer Science).
Mohamed AM, Lipsky I,, Ammar (2005) Modeling parallel and distributed systems with finite workloads. Performance Evaluation 60(1-4)3333-355
Owen Z, Simchi-Levi D (2018) Price and assortment optimization for reusable resources. Technical report, Massachusetts Institute of Technology. Cambridge, MA. Available SSRN 3070625.
Özer Ô Phillips (2012) The Oxford Handbook of Pricing Management (Oxford. UK: Oxford University Press).
Perchet V, Rigollet P. Chassang S, Snowberg E (2016) Batched bandit problems. The Annals of Statistics 44(2):600-611.
Püschel T, Schryen G, Hristova D. Neumann D (2015) Revenue management for cloud computing providers:
Decision models for service admission control under non-probabilistic uncertainty. European Journal of Operational Research 244(2):637-647,
Rusmevichientong P, Sumida M, Topaloglu H (2020) Dynamic assortment optimization for reusable products with random usage durations. Management Science 66(7):2820-2844.
Simchi-Levi D. Xu Y (2019) Phase transitions and cyclic phenomena bandits with switching constraints.
Wallach H. Larochelle H. Beygelzimer A. d'Alché-Bue F, Fox E, Garnett R, eds., Advances in Neural Information Processing Systems, volume 32, 7523-7532 (Red Hook, NY, USA: Curran Associates, Inc.).
Slivkins A (2019) Introduction to multi-armed bandits. Foundations and Trends in Machine Learning 12(1-2):1- 286.
Talluri KT, Van Ryzin GJ (2006) The Theory and Practice of Revenue Management (New York, NY: Springer Science & Business Media).
Williamson EL (1992) Airline network seal inventory control: Methodologies and revenue impacts. Ph.D. thesis, Massachusetts Institute of Technology.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See Section T.2
(b) Did you describe the limitations of your work? [Yes] We consider a specific service system that can be reduced a Jackson Network.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] No potential negative societal impacts.
(d) Have you read the ethies review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
(b) Did you include complete proofs of all theoretical results? [Yes] We provide proof
sketch in the main body of the paper and provide detailed proof in the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] We include detailed experiment setup in the appendix.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] We are not comparing the running time and thus these information is not relevant.
4. If you using existing assets (e.g., code, data, models) curating/releasing assets....
(a) If your work uses existing assets, did you cite the creators? [Yes] We cite existing lemmas. For example, see Lemma in Appendix F.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "qIy41C_POTx", "reviewer": "Reviewer_dRYY", "summary": "The paper addresses the general problem of setting product prices in a multi-resource and multi-product service environment so that these prices result in nearly optimal total revenue that is generated, assuming rapid adjustment of demand in response to service price changes.  In this generality, and as stated in the abstract and in the introductory sections, the model is applicable to a host of different settings ranging from computing clouds, manufacturing, and several other service platforms, both virtual and physical, also listed in the introduction.  A solution is provided via a bandit process which minimizes regret, that is the gap between what is achieved and the optimal prescient solution.  The methodology crucially depends on fitting the model to Jackson networks and along the way not only sophisticated results (such as finite-time mixing time of Jackson networks) are derived, proved and used but several difficult theorems also stated and proved.  A numerical example is provided at the end to demonstrate applicability of the results in practice.", "questions": "\nThere is some difficulty in understanding the process of demand-price the author(s) have in mind.  Are prices computed for \"resources\" and then advertised for \"services\" which use these resources in a linear fashion? Also the following statements need clarification.\n\nLine 68: In the first interval, the system completes serving the previous customers and reaches the steady-state under the new price.\n69.\nQ:  Only those customers?  Any new customer arriving in the next interval are queued or are they rejected and cleared from the system until new prices are advertised?\n\nLine 69: In the second interval, the system maintains the steady-state (exploiting the new price).\nQ: By \"maintain\" the author(s) mean the customers for the next batch wait long enough for the system go past the transient phase and enter equilibrium?  What happens during this time to newly arriving customers?  What prices are advertised during this time?\n\nLine 70: This batched framework not only allows for system stabilization (under new prices) but also allows for infrequent O(log T) price changes, which is more implementable in practical settings.\n\nQ: Why is price change not O(T) if T is selected to be the time during which prices don't change?\n\nLine 133: Customers arrive following a price-dependent multivariate Poisson process with a total rate alpha(x), which is unknown to the decision maker a priori.\n\nQ: Has demand-price being multivariate Poisson been observed in any real setting?  Otherwise is this is just for mathematical convenience?  This reviewer has not seen demand-price to be a Poisson-process before unless the mean demand value of the Poisson process is some (elastic/inelastic) function of resource price.  Btw, demand is going to be a function of *service* price and not resource price and the relationship between service price and resource price has not been discussed, as far as this reviewer can see.\n\nLine 141: We use a J-dimensional vector.\nQ: An I-dimensional vector?\n\nLine 144: \\pi (y; t) in \\Xi for period t when there are y customers in the system at the beginning of period t, to maximize the expected cumulative revenue Y^\\pi.\nQ: Why is price only a function of state (y in R^+I) at the *beginning* of each period? Does demand for each period arrive instantaneously at the beginning when resource (should be service) prices are announced and no more demand arrives till the next time period?  Also, prices are stated to be for resources but customers ask for services so is the price of service/product simply sum of resource used?  This is of course true of costs but need not hold for prices. If so, this needs to be explicitly mentioned.\n", "limitations": "\nThe biggest hurdle this reviewer sees is in the list of 5 assumptions.  Let's review these together.\n\nAssumption 2. This is not really justifiable.  Many cloud or manufacturing tasks require specific order of processes which are task/service dependent and cannot be ordered the same way for all services.  There is huge loss of generality in making this assumption.\n\nAssumption 3. Like assumption 2, this one is also extremely restrictive.  If we list each service and its resources, then we see a clear dependence between use of resources by services.  The use of the term \"customer\" is misleading here since customers ask for services and services have a specific set/sequence of resources which are interdependent.\n\nIt is very clear that assumptions 2 and 3 are leveraged to make the Jackson Network solution applicable to this problem and not because the problem even by some stretch of the imagination happens to satisfy the said assumptions.  If there are specific services (cloud/manufacturing) for which these assumptions are not restrictive, then these should be explicitly stated.\n\nAssumption 4.  This assumption is unnatural but unlike assumptions 2 and 3, this one can be remedies by saying that resource prices are selected to be sufficiently high so that all resulting queues remain stable.  This is not unreasonable.  It just puts lower bounds on prices.  \nThe statement \"is stable under any price\" should therefore be qualified.\n\nAssumption 5.  This one even reads like a technical requirement not justified by any known services. Unless of course, the author(s) give specific examples from real cases.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nThe problem setting considered in this submission is very broad, the quality of writing and the clarify of the discussion is also very high.  This paper would furnish a major advance in understanding multi-resource revenue management if the applicability of the results were as high as initially aimed for.  But despite derivation of advanced, original and complex theorems, the claims envisioned in the early part of this submission are unfortunately not realized.  This is primarily because a series of progressively untenable assumptions are made in Section 2 and these are so restrictive and so targeted to make the model fit a Jacksonian framework that it is highly doubtful if the bandit-based heuristic solution is useful for *any* of the many settings the author(s) described in the introduction.  This reviewer perfectly understand the nearly unsurmountable difficulties which would be encountered without making some simplifying assumptions in such a context.  But on the other hand, the restrictiveness of the underlying assumptions are too broad for the model to be tenable.  These issues are discussed in detail below.  The only way out of this dilemma is for the author(s) to show that the methodology works reasonably well or better than existing solutions *despite* the restrictiveness of the assumptions, ie demonstrate some kind of insensitivity to the restrictive assumptions made for analytical tractability.  If there is evidence for this, then this paper represents a significant contribution to the literature on network revenue management.  But Section 6 is too terse and too brief to convince this reviewer of this possibility.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "g1r7UrBNSLC", "reviewer": "Reviewer_orv1", "summary": "The authors study the network revenue management problem with reusable resources where the price-dependent arrival rates of all products are unknown and need to be learned. They propose UCB and TS-based batched algorithms that separate the time horizon into successive batches and select a price for each batch. The batch design helps bound the loss due to the nonstationarity in Jackson Network. Based on that, they provide instance-independent regret bounds for the proposed algorithms. Numerical experiments validate the performance of proposed algorithms.", "questions": "See Weaknesses.", "limitations": "See Weaknesses.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1) The online NRM problem where multiple products share multiple resources is new. The connection between this problem and the Jackson Network is also interesting.\n2) To bound the loss due to nonstationarity, which is a unique challenge in this problem, the authors propose batched algorithms. The regret analysis of proposed algorithms relies on a finite-time high probability bound on mixing times of the Jackson Network system, which is one of the main technical contributions of this paper.\n\nWeaknesses\n1) One of my main concerns is Assumption 5, which is essential for the proof of Proposition 4 and the regret analysis. First, there is no explanation of “utilization factor” $\\rho_1, \\rho_2$. Second, it is unclear why the difference in arrival rates between two prices can be bounded by a function of only $\\rho_1$. In which case this is not true? \n2) There is no lower bound result in this paper, so it is hard to say whether the regret bound is tight, especially for $J$. Also, in lines 73-74, it said “we need to ensure that the regret scales sublinearly in the number of products”, however, the final regret is actually $O(J\\sqrt{XT})$, which seems to be inconsistent.\n3) The design of the batched UCB and TS algorithms is somewhat standard, so IMHO, the main technical contribution is how to bound the loss of nonstationarity.\n\nMinor Comment\n1) It is hard to see how the prices of UCB and TS change in Figure 1(a). Maybe a logarithmic x-axis could help.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "dHAIQIFvuvo", "reviewer": "Reviewer_Upo2", "summary": "This paper designs a batched bandit algorithm for the network revenue management problem with reusable resources. Given $I$ resources (or servers) with fixed capacities, some requests for $J$ types of products arrive one by one, and each product needs to be processed by a sequence of product-dependent servers. The arrival rate of customers and the service rate of each server depend on the posted prices of\nusing each server, but the mapping between the rates and posted prices is unknown. The goal is to determine the posted prices to minimize the regret between the revenue of online algorithms and that of dynamic optimal policy.\n\n", "questions": "Please respond to two major issues mentioned in the weaknesses section. ", "limitations": "n/a", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n1) The paper studies a practically relevant and challenging online learning problem for network revenue management with reusable resources. \n\n2) The theoretical results are solid and significant (the regret results for both UCB and TS are near-optimal). \n\n3) The analysis is nontrivial and presented clearly.\n\n**Weaknesses:**\n1) The key contribution of this paper is to consider the reusable resources in the network revenue management setting. However, there is a lack of characterization and discussions about the impact of learning the unknown service rate (related to the reusable resources). In fact, there is no procedure to learn the service rate in the proposed algorithm and the numerical results just use a fixed given service rate. Thus, please provide a clear explanation of why there is no need to learn the service rate for this problem. If it is due to the assumptions (e.g., memoryless customer flow and stability) that oversimplify the current problem and the authors should provide formal discussions\non this to clarify the contribution of this paper.\n\n2) In real-world applications, the price of a product is usually proportional to the duration of using resources. Thus, the authors should provide a concrete application example that can fit the proposed model (each customer needs to sequentially go through product-specified resources; the customer can wait when the resource is unavailable without costs; the price of the product is independent of the duration of using resources).\n\n**Minor comments:**\n1) In the problem formulation, there seems to be a default assumption that each product only requests one unit of its requested resource. Could this assumption be relaxed?\n\n2) The regret result (in Theorem 1) is linear in the number of product types J. Could the authors provide any remarks on the optimality of the regret in terms of J?\n\n3) Typo: line 141, page 3, J-dimensional vector -> I-dimensional vector", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "cUreP8Tc-uZ", "reviewer": "Reviewer_ThAu", "summary": "This paper looks at a setting where a firm offers products that require a sequence of reusable resources to be used in order for a customer to obtain the product. More specifically, the set of $J$ products is given by $\\mathcal{J}$, the set of resources $I$ is given by $\\mathcal{I}$, where each resource $i \\in \\mathcal{I}$ has a capacity (in terms of customers it can service at a given time) given by $c_i$. Customers are serviced for resources at exponentially distributd times, and there is assumed to be a topological ordering of resource dependencies for all products (so that customers can enter the overall system to be serviced in an ordered fashion irrespective of the product desired). Most importantly, the designer can assign prices $x \\in \\mathcal{X}$ to each product, paid for by customers as a lump sum before being serviced, and such that the prices define the Poisson processes that dictate demand for each product, as well as internal transitions between resource types for customers. \n\nGiven this context, the system designer is faced with the objective of maximizing the cumulative revenue of the system, wherein they can choose to dictate prices for goods at any given time period. However, the designer does not know the dependencies on demand and internal resource transitions beforehand, therefore a problem of balancing exploration of good prices and exploiting prices found to be good historically is faced. The main benchmark for performance used is regret, which is natural for this setting, and hence the algorithms provided by the authors are in the nature of those used for multi-armed bandits (UCB and Thompson sampling).\n\nTo prepare the setting for these algorithms, the authors first provide a proxy for regret given by an LP relaxation of the optimal policy in hindsight (relaxed regret), and furthermore, since both their variants on UCB and Thomspon sampling require changing price over different time batches, it is important to bound the mixing time of the underlying Markov chain governing product demand and resource usage. The authors do this for the setting of the paper, and can bound the regret accrued when the underlying chain mixes between price changes. \n\nFinally, the authors provide corresponding regret guarantees, and provide empirical evidence in line with their theoretical results.", "questions": "Are there natural functional relationships between prices and demand that can give rise to better regret guarantees? ", "limitations": "The largest limitation is the lack of distinction with existing paper (as per the weaknesses section)", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n-The model at hand is well-justified as a natural extension of existing work\n-The coupling argument is novel, as mentioned in the paper, especially in the context of mixing times for Jackson networks more generally\n\nWeaknesses:\n-The biggest weakness in my opinion is the fact that the authors have not spent enough time clearly distinguishing the results of this paper to that of \"Online Learning and Pricing for Service Systems with Reusable Resources\" (https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3755902). The setting and techniques (and overall writing) of the paper are very similar, albeit the paper is for the single resource scenario. I do believe that there are interesting differences to be highlighted (such as in the coupling argument for example), but this needs to be much more clear in the paper. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept