Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
summary
Presents a concrete offline-to-online reduction that Blackwell approachability converts greedy, locally robust offline algorithms into online learners; requires two checkable conditions: robustness to local errors and Blackwell locality. Claims O(T^{1/2}) approximate regret under full information and introduces Bandit Blackwell approachability to get O(T^{2/3}) in bandit feedback. Applies to product ranking, reserve price optimization and submodular maximization, yields polynomial-time online policies with K·√T-type losses and simulations showing sometimes negative cumulative approximate regret.
AI-written summary · about
chapters (11)
- 0:00Introduction and motivation
- 1:36Marketplace examples
- 5:55Assortment planning problem
- 10:47Generic transformation tool
- 13:33Greedy algorithms and regret
- 16:17Blackwell approachability
- 21:58Transformation framework
- 26:40Performance and results
- 30:27Blackwell game implementation
- 38:02Extensions and limitations
- 41:26Summary and conclusion
related talks
41mOnline Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
35mOnline Optimization and Learning Under Long-Term Convex Constraints and Objectives
35mOnline Learning with A Lot of Batch Data
44mParsimonious Learning-Augmented Algorithms
48mA Simple Condition for Constant Regret in Online Decision-Making
40mA Bayesian Approach to Online Resource Allocation
43mContextual Inverse Optimization: Offline and Online Learning
22mOnline Learning and Bandits with Queried Hints