Text

Online Allocation and Pricing : Constant Regret via Bellman Inequalities

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.

Ketersediaan

Informasi Detail

Judul Seri

OPERATIONS RESEARCH; Vol.69 No.3 May-June 2021

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 821 - 840

Bahasa

English

ISBN/ISSN

-

Klasifikasi

-

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

DYNAMIC PRICING
STOCHASTIC OPTIMIZATION
APPROXIMATE DYNAMIC PROGRAMMING
NETWORK REVENUE MANAGEMENT
ONLINE RESOURCE ALLOCATION
ONLINE PACKING

Info Detail Spesifik

https://doi.org/10.1287/opre.2020.2061

Pernyataan Tanggungjawab

Alberto Vera, Siddhartha Banerjee, Itai Gurvich

Versi lain/terkait

Lampiran Berkas

Komentar