A Simple Condition for Constant Regret in Online Decision-Making
summary
Claims a simple sufficient condition that guarantees uniform loss independent of T for stochastic online decision problems (examples: bin packing, network revenue management, online job allocation). Uses concentration bounds on type counts and a Lipschitz continuity condition on the offline optimum under arrival perturbations. Builds a resolving-style algorithm that replaces randomized routing with a threshold instead of randomization (pick the max action); shows disagreements with the clairvoyant are exponentially unlikely so additive regret stays bounded by a constant.
AI-written summary · about
chapters (21)
- 0:00Intro
- 0:30Online Bin Packing
- 0:47Online Network Revenue Management
- 3:28Uniform Loss
- 4:42Landsacpe
- 9:37Related Work
- 15:58Re-solving heuristic (Adaptive)
- 23:04Rewriting Loss
- 25:42Defining Disagreement
- 28:30Resolving and OFF(t)
- 29:23Bounding the Probability of a Disagreement
- 32:33Resolving heuristic (Adaptive)
- 34:09Bounding Regret
- 34:22Appropriate Skepticism: Benchmarks
- 37:39Generalize: what properties did we use?
- 39:44A Sufficient Condition for Constant Regret
- 40:57Proof of Sufficiency
- 41:49Examples: Linear Programs
- 43:13Scheduling (minimize makespan)
- 43:26Extensions
- 44:55Conclusion
related talks
40mA Bayesian Approach to Online Resource Allocation
58mMemory-Regret Tradeoff for Online Learning
46mDynamic Regret Minimization for Bandits without Prior Knowledge
49mFast Rates for No-Regret Learning in General Games
35mOnline Optimization and Learning Under Long-Term Convex Constraints and Objectives
31mRegret Minimization for Stochastic Shortest Paths
43mOnline Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
42mBypassing the Impossibility of Online Learning Thresholds: Unbounded Losses and Transductive Priors