Semibandit Learning for Monotone Stochastic Optimization
TL;DR
Firms can improve decisions as data arrive without pausing operations for a separate data-gathering phase, and even with partial, censored, or yes-or-no feedback, the cumulative performance gap grows essentially at the square root rate.
Abstract
Learning When Demand Is Unknown Airlines launching new routes cannot wait for years of historical data before deciding how many seats to offer at each fare or what prices to charge. They must learn when operating, often from incomplete feedback: selling 30 economy plus seats does not reveal whether demand was 30, 40, or more. In the accepted Operations Research paper “Semibandit Learning for Monotone Stochastic Optimization,” Rohan Ghuge, Zhengjia Zhuo, Arpit Agarwal, and Viswanath Nagarajan develop a general framework for such decisions. They identify a basic property, monotonicity, that allows an optimization method built for known demand distributions to become a learning algorithm for unknown distributions. The framework applies to airline and hotel revenue management, sequential posted pricing, and optimal-stopping problems. Even with partial, censored, or yes-or-no feedback, its cumulative performance gap grows essentially at the square root rate, best possible up to logarithmic factors. Firms can, therefore, improve decisions as data arrive without pausing operations for a separate data-gathering phase.