Technical Note—An Improved Analysis of LP-Based Control for Revenue Management
研究了基于线性规划的自适应算法在数量型网络收入管理问题中的遗憾上界，发现非退化情形下遗憾与时间无关，退化情形下遗憾为T log(T)量级且与下界匹配。
Bounded Regret for LP-Based Revenue-Management Problems In “An Improved Analysis of LP-Based Control for Revenue Management,” Chen, Li, and Ye study a class of quantity-based network revenue-management problems. The authors consider a stochastic setting where all the orders are i.i.d. sampled and the customers are of finite type. They focus on the classic LP-based adaptive algorithm and consider regret as the performance measure. They found that when the underlying LP is nondegenerate, the algorithm achieves a problem-dependent regret upper bound that is independent of the horizon/number of time periods T; when the underlying LP is degenerate, the algorithm achieves a tight regret upper bound that scales on the order of T log(T) and matches the lower bound up to a logarithmic order.