A Bayesian Approach to Online Resource Allocation
summary
Claims a simple policy that queries a black‑box simulator for the probability that accepting the current arrival reduces the offline optimum and then thresholds that probability at 0.5; this policy achieves constant regret independent of the horizon and budget levels (under mild tail bounds) and tolerates time‑varying or correlated arrivals. Proof uses a new compensated coupling that forces the offline to follow the online plan and pays compensations, producing closed‑form regret bounds by showing disagreement probabilities are exponentially small and summable.
AI-written summary · about
chapters (3)
related talks
48mA Simple Condition for Constant Regret in Online Decision-Making
43mOnline Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
31mAvoiding Cascading Failures for Time-of-Use Pricing
31mLearning to Control Unknown Systems
35mOnline Learning with A Lot of Batch Data
55mWhat Are the Statistical Limits of Offline Reinforcement Learning With Function Approximation?
41mOnline Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
30mOnline Paging with a Vanishing Regret