Online Allocation and Pricing: Constant Regret via Bellman Inequalities

Alberto Vera (), Siddhartha Banerjee () and Itai Gurvich ()
Additional contact information
Alberto Vera: School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
Siddhartha Banerjee: School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
Itai Gurvich: Kellogg School of Management, Northwestern University, Evanston, Illinois 60208

Operations Research, 2021, vol. 69, issue 3, 821-840

Abstract: We develop a framework for designing simple and efficient policies for a family of online allocation and pricing problems that includes online packing, budget-constrained probing, dynamic pricing, and online contextual bandits with knapsacks. In each case, we evaluate the performance of our policies in terms of their regret (i.e., additive gap) relative to an offline controller that is endowed with more information than the online controller. Our framework is based on Bellman inequalities, which decompose the loss of an algorithm into two distinct sources of error: (1) arising from computational tractability issues, and (2) arising from estimation/prediction of random trajectories. Balancing these errors guides the choice of benchmarks, and leads to policies that are both tractable and have strong performance guarantees. In particular, in all our examples, we demonstrate constant-regret policies that only require resolving a linear program in each period, followed by a simple greedy action-selection rule; thus, our policies are practical as well as provably near optimal.

Keywords: dynamic programming/optimal control; applications, Revenue Management and Market Analytics, stochastic optimization, approximate dynamic programming, online resource allocation, dynamic pricing, online packing, network revenue management (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2020.2061 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:69:y:2021:i:3:p:821-840

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().