The Bayesian Prophet: A Low-Regret Framework for Online Decision Making
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.
Code (1)
Tasks
Decision MakingSimilar Papers 제목 키워드 기반
Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret
We study the repeated optimal stopping problem, in which the same optimal stopping instance with an unknown distribution is solved repeatedly over $T$ rounds. We aim to simultaneously achieve strong per-round performance…
Bandit Algorithms for Prophet Inequality and Pandora's Box
The Prophet Inequality and Pandora's Box problems are fundamental stochastic problem with applications in Mechanism Design, Online Algorithms, Stochastic Optimization, Optimal Stopping, and Operations Research. A usual a…
Multi-Armed BanditsStochastic OptimizationImproved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality
We study the Pandora's Box problem in an online learning setting with semi-bandit feedback. In each round, the learner sequentially pays to open up to $n$ boxes with unknown reward distributions, observes rewards upon op…
Learning Markov Decision Processes under Fully Bandit Feedback
A standard assumption in Reinforcement Learning is that the agent observes every visited state-action pair in the associated Markov Decision Process (MDP), along with the per-step rewards. Strong theoretical results are …
Stochastic OptimizationReinforcement LearningOnline Bayesian Risk-Averse Reinforcement Learning
In this paper, we study the Bayesian risk-averse formulation in reinforcement learning (RL). To address the epistemic uncertainty due to a lack of data, we adopt the Bayesian Risk Markov Decision Process (BRMDP) to accou…
Reinforcement Learning