Paper Info
Title
The Bayesian Prophet: A Low-Regret Framework For Online Decision Making
Abstract
We develop a new framework for designing online policies given access to an oracle providing statistical information about an off-line benchmark. Having access to such prediction oracles enables simple and natural Bayesian selection policies and raises the question as to how these policies perform in different settings. Our work makes two important contributions toward this question: First, we develop a general technique we call compensated coupling, which can be used to derive bounds on the expected regret (i.e., additive loss with respect to a benchmark) for any online policy and off- line benchmark. Second, using this technique, we show that a natural greedy policy, which we call the Bayes selector, has constant expected regret (i.e., independent of the number of arrivals and resource levels) for a large class of problems we refer to as "online allocation with finite types," which includes widely studied online packing and online matching problems. Our results generalize and simplify several existing results for online packing and online matching and suggest a promising pathway for obtaining oracle-driven policies for other online decision-making settings.
Year
DOI
Venue
2021
10.1287/mnsc.2020.3624
MANAGEMENT SCIENCE
Keywords
DocType
Volume
stochastic optimization, prophet inequalities, approximate dynamic programming, revenue management, online allocation, online packing, online matching
Journal
67
Issue
ISSN
Citations 
3
0025-1909
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Alberto Vera100.68
Siddhartha Banerjee218522.85