Online Allocation and Pricing: Constant Regret via Bellman Inequalities: Regret Is at Most the Information Loss Plus the Bellman LossResearch Paper
An online allocator must commit to an action after each arrival, although later arrivals can change which actions would have been best. Revenue management and online resource allocation use regret to measure the expected reward lost against a benchmark. If the benchmark sees too much future information, this gap can grow with the horizon even when the…