Learning to Overbook Safely: Chance-Constrained Revenue Management with Selected Show-Up Feedback
TL;DR
The joint-pivotal safe Poisson-binomial upper confidence bound (JP-SPB-UCB) policy combines exact risk evaluation with certified, batched exploration, and linear-program rounding constructs a safe exploration schedule within K episodes of a lower bound valid for adaptive randomized schedules.
Abstract
Overbooking offsets no-shows, but learning attendance from accepted customers can expose service providers to unsafe decisions. We study finite-menu overbooking under selected show-up feedback and an episodewise overload chance constraint. The joint-pivotal safe Poisson-binomial upper confidence bound (JP-SPB-UCB) policy combines exact risk evaluation with certified, batched exploration. Linear-program rounding constructs a safe exploration schedule within K episodes of a lower bound valid for adaptive randomized schedules. With probability at least 1−δ, every deployed profile has true overload probability at most α; realized overloads remain possible. Under joint reward–safety identifiability, pseudo-regret against the exact safe oracle admits O(TlogT) and O(logT) bounds for each fixed finite-menu instance when δ=T−2; the constants depend on that instance. Lower bounds establish inverse-square near-boundary certification costs and linear regret at fragile boundary optima. On the original balanced instance, JP-SPB-UCB achieves lower terminal pseudo-regret than the two global-certificate baselines. An expanded study of 58 configurations, including reference controls, examines stronger comparisons, parameter sensitivity, boundary censoring, computational costs, and assumption violations without extending the theoretical guarantees to misspecified models.