Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: Strengths
1) The online NRM problem where multiple products share multiple resources is new. The connection between this problem and the Jackson Network is also interesting.
2) 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.

Weaknesses
1) 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? 
2) 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.
3) 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.

Minor Comment
1) It is hard to see how the prices of UCB and TS change in Figure 1(a). Maybe a logarithmic x-axis could help.


questions: See Weaknesses.
limitations: See Weaknesses.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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. 

Given 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).

To 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. 

Finally, the authors provide corresponding regret guarantees, and provide empirical evidence in line with their theoretical results.
strengths_and_weaknesses: Strengths: 
-The model at hand is well-justified as a natural extension of existing work
-The coupling argument is novel, as mentioned in the paper, especially in the context of mixing times for Jackson networks more generally

Weaknesses:
-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. 

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)
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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
using 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.


strengths_and_weaknesses: **Strengths:**
1) The paper studies a practically relevant and challenging online learning problem for network revenue management with reusable resources. 

2) The theoretical results are solid and significant (the regret results for both UCB and TS are near-optimal). 

3) The analysis is nontrivial and presented clearly.

**Weaknesses:**
1) 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
on this to clarify the contribution of this paper.

2) 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).

**Minor comments:**
1) 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?

2) 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?

3) Typo: line 141, page 3, J-dimensional vector -> I-dimensional vector
questions: Please respond to two major issues mentioned in the weaknesses section. 
limitations: n/a
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: 
The 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.
questions: 
There 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.

Line 68: In the first interval, the system completes serving the previous customers and reaches the steady-state under the new price.
69.
Q:  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?

Line 69: In the second interval, the system maintains the steady-state (exploiting the new price).
Q: 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?

Line 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.

Q: Why is price change not O(T) if T is selected to be the time during which prices don't change?

Line 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.

Q: 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.

Line 141: We use a J-dimensional vector.
Q: An I-dimensional vector?

Line 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.
Q: 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.

limitations: 
The biggest hurdle this reviewer sees is in the list of 5 assumptions.  Let's review these together.

Assumption 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.

Assumption 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.

It 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.

Assumption 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.  
The statement "is stable under any price" should therefore be qualified.

Assumption 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.
review_title: null

Meta-review: metareview: Executive summary:

The paper studies a price-based network revenue management problem with multiple products and multiple reusable resources, with an apriori unknown price-demand function. The authors approach this as a batched bandit learning problem, and their main result is an algorithm with cumulative regret \tilde{O}(J \sqrt(XT)) where J is the number of products, X is the number of prices, and T is the number of rounds. The dependence on X and T is best possible.

Discussion and recommendation:

This paper is a bit out of my comfort zone, so I am relying on the reviews for the decision. It seems that all reviewers appreciated the general model and the the theoretical results and experimental evaluation. Questions were raised regarding the various (seemingly) strong assumptions, but these were addressed in the rebuttal.

Weak accept.
confidence: Less certain
Decision: Accept