Setting prices for reusable resources—such as rental cars, cloud computing slots, or hotel rooms—is a sophisticated challenge in revenue management. The difficulty compounds when a business does not know exactly how customers will react to those prices.
This paper introduces BLinUCB, the first rate-optimal algorithm for dynamic pricing with reusable resources where demand and service rates are unknown linear functions of price features. By elegantly handling transient queueing delays and the heavy-tailed "sub-exponential" rewards inherent in service systems, the algorithm achieves a near-optimal regret bound of $\tilde{O}(d_f \sqrt{T})$.
The Core Challenge: Reusable vs. Perishable Goods
Most classic revenue management research focuses on perishable goods: once a seat on a flight is sold, it’s gone. Reusable resources are fundamentally different. A customer rents a car, uses it for a random amount of time, and then returns it to the pool. This creates a queueing system (specifically an M/M/c queue) where the available inventory fluctuates stochastically.
Managing this system introduces a two-fold challenge:
- The Learning-Exploitation Tradeoff: The firm must experiment with different prices to learn the underlying demand and service rate functions, while simultaneously trying to maximize revenue.
- Transient Dynamics: When a price changes, the system doesn't instantly reach a new "steady state." It continues to process "old" customers who arrived under previous prices. This non-stationarity causes standard bandit algorithms to fail or perform poorly.
The BLinUCB Algorithm
To overcome these hurdles, the authors propose the Batch Linear Confidence Bound (BLinUCB) algorithm. Its design features several clever departures from standard linear bandit approaches:
- Batched Learning: Instead of updating after every single customer, the algorithm operates in successive batches of increasing length. This reduces the frequency of price changes, which is both practical for businesses and essential for the theoretical analysis.
- The Two-Interval Batch: Each batch is split into two parts. The first interval allows the queueing system to "settle" into its new steady state and helps eliminate the heavy-tailed effects of service time observations. Data for updating the model is only collected during the second, stable interval.
- Coupling Analysis: To prove their regret bounds, the authors use a "coupling argument." They compare the actual system (which is in a messy transient state after a price change) to a virtual system that starts in a steady state. This allows them to mathematically bound the revenue lost during transitions.
- Sub-Exponential Rewards: Most bandit literature assumes "sub-Gaussian" (thin-tailed) noise. However, service times are often exponentially distributed, leading to "sub-exponential" (heavier-tailed) rewards. The authors generalize linear bandit theory to handle these more realistic, volatile observations using Bernstein-type concentration inequalities.
Experimental Setup
The paper relies on synthetic numerical experiments to validate the theory. The authors simulate three distinct scenarios (Instances #1, #2, and #3) representing different system utilization levels: low, moderate, and high. The parameters for these instances, including the unknown linear coefficients ($\theta_\lambda, \theta_\mu$), are detailed below.
Key Insights and Results
- Theoretical Optimality: The authors prove a cumulative regret bound of $\tilde{O}(d_f \sqrt{T})$, where $d_f$ is the dimension of the price features. This matches the known theoretical lower bound for linear bandits, meaning the algorithm is "rate-optimal."
- Transient States are the Real Enemy: The analysis highlights that you cannot ignore the "mixing time" of the queue. Changing prices too frequently prevents the system from reaching a steady state, making the collected data too noisy to learn from effectively.
- Static Benchmarks are Powerful: A surprising finding is that a single, static optimal price serves as an incredibly strong benchmark. The gap between the best static price and a complex, state-dependent optimal policy is only $O(\log T)$, which is negligible compared to the $\sqrt{T}$ regret caused by learning.
- Superior Empirical Performance: In simulations, BLinUCB consistently outperformed standard $\epsilon$-greedy benchmarks. It identifies the optimal price much faster and maintains a significantly lower time-average regret across all utilization levels.
Limitations and Future Work
While this work represents a major step forward, the authors acknowledge several areas for future growth:
- Multi-Product Settings: The current model handles a single pool of homogeneous resources. Real-world platforms often manage multiple types of resources (e.g., different car classes) simultaneously.
- General Distributions: The analysis assumes Poisson arrivals and exponential service times. Extending this to general (G/G/c) distributions would require even more complex coupling arguments.
- Non-Stationary Environments: The paper assumes the underlying market response is fixed. Future research could investigate "drifting" demand where customer preferences change over time.
Summary updated