Online Learning and Pricing for Network Revenue Management with Reusable Resources

Huiwen Jia, Cong Shi, Siqian Shen

Introduction: The Challenge of Reusable Resources Traditional Network Revenue Management (NRM) typically deals with perishable goods—such as airline tickets or hotel rooms—that vanish once a specific date passes. However, modern applications like cloud computing (e.g., AWS EC2 instances) and project management rely heavily on reusable resources. In these settings, customers request products that occupy a sequence of resources for a specific duration, after which the resources are freed up for the next user.

The core challenge arises when a firm does not know the underlying price-demand function and must learn it dynamically. If the firm changes prices to observe demand, arrival rates change immediately. However, the system is still processing "old" customers who arrived under the previous price. This overlap creates a highly complex transient state in the queueing network. While prior work has explored single-product or single-resource settings, multi-product and multi-resource networks have remained mathematically daunting due to sequential resource usage and continuously evolving capacities.

Methodology: Batched Bandit Learning To tackle this, the researchers model the service system as a Jackson Network (a network of M/M/c queues) and frame the pricing challenge as a Multi-Armed Bandit (MAB) problem, where the "arms" represent candidate price vectors.

To handle the chaotic transient states caused by price changes, the authors introduce two novel batched bandit algorithms: RNRM-UCB (Upper Confidence Bound) and RNRM-TS (Thompson Sampling). Instead of constantly adjusting prices, these algorithms divide the time horizon into batches with exponentially increasing lengths, fixing a single price for each batch.

Crucially, each batch is split into two phases:

  1. Mixing Phase: The system waits for the network to flush out old customers and reach a steady state under the new price.
  2. Exploitation Phase: The system reaps the steady-state revenue.

Key Theoretical Breakthroughs A major theoretical contribution of this paper is providing the first finite-time mixing analysis for Jackson Networks. Previously an open question in queueing theory, proving that an open queueing network reaches a steady state in a bounded amount of time after a system change is essential for demonstrating that reinforcement learning and bandit algorithms can succeed in these environments.

To prove this, the authors developed a novel nested coupling argument. Applying standard coupling arguments to every resource in a network simultaneously causes the probability of system stabilization to scale exponentially with the number of products. By decomposing the network into topological layers—based on the sequence of resources that products use—the authors achieved a coupling probability that scales linearly, successfully beating the curse of dimensionality and making the mathematics tractable.

Results and Practical Implications The proposed algorithms achieve a near-optimal cumulative regret bound of $\tilde{O}(J\sqrt{XT})$, where $J$ is the number of products, $X$ is the number of candidate prices, and $T$ is the number of time periods. This matches the theoretical lower bound for $X$ and $T$ up to logarithmic factors.

Empirically, through synthetic numerical simulations (modeling a network with 2 resource types and 3 product types over 2,000 time periods), both RNRM-UCB and RNRM-TS successfully identify the optimal price and rapidly drive the time-average regret to zero. They significantly outperform adapted benchmark policies, which typically struggle to balance exploration and exploitation in reusable resource settings.

Furthermore, the batched approach restricts price changes to only $O(\log T)$ times. While mathematically necessary to control the revenue lost while the system stabilizes, this is also highly practical: real-world businesses generally prefer infrequent price updates over chaotic, minute-by-minute fluctuations.

Limitations and Future Directions The current model assumes a finite, discrete set of candidate prices, and the authors suggest extending the framework to accommodate continuous price spaces. Additionally, the theoretical guarantees rely heavily on Markovian assumptions (Poisson arrivals and exponential service times) to reduce the system to a Jackson Network. Extending this work to handle general, non-exponential arrival and service distributions will require significant methodological innovations in future research.

Summary updated

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.
BibTeX
@inproceedings{jia2022online,
  author = {Huiwen Jia and Cong Shi and Siqian Shen},
  title = {{Online Learning and Pricing for Network Revenue Management with Reusable Resources}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=O9zOGFIfk0},
}
Figure