Papers › The Bayesian Prophet: A Low-Regret Framework for Online Decision Making
The Bayesian Prophet: A Low-Regret Framework for Online Decision Making
Alberto Vera, Siddhartha Banerjee
We develop a new framework for designing online policies given access to an oracle providing statistical information about an offline 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 towards 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 offline 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.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections