Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization

on YouTube ↗41m

" summary

Framework converts offline greedy procedures into online learners for NP‑hard combinatorial rewards by treating each greedy stage as a Blackwell game and running per‑stage Blackwell algorithms; it produces a provable sqrt(T) regret in full‑information and T^{2/3} (discrete bandit) or T^{4/5} (continuous bandit) rates, matches or improves prior bounds, and yields a 1/2 approximation for continuous DR‑submodular cases. Key requirements are extended robustness of the greedy routine and Blackwell approachability reducibility of each subproblem.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 1:41Decision-making in Marketplaces Marketplaces have to make certain decisions repeatedly over time
3. 4:49Research Questions
4. 6:04Preliminary: Offline Problem
5. 7:12Greedy Algorithm for the Offline Problem
6. 8:26Preliminary: Online Problem
7. 10:52Contributions and Main Results
8. 14:36Related Work
9. 16:23Revisiting the Greedy Algorithm
10. 19:11Greedy Algorithm is Robust to Local Errors
11. 21:09That Is Not All! Greedy is Extended Robust Consider noisy run of the algorithm over Trounds. Then, if for every subproblemi
12. 24:26Blackwell Sequential Games
13. 25:24Not Every Target Set Is Approachable
14. 26:14Blackwell Algorithms Handle Subproblems Pl is algorithm that returns
15. 27:06Blackwell Algorithms Coordination and Regre
16. 27:47Full Information: Beyond Assortment Plannir Theorem 1 Full-information offline-to-online transformation Suppose that an offline algorithm . is an extended robust approximation algorithm, and • Blackwell reducible. Then, in the full information setting, there exists an online algorithm that runs in polynomial time and satisfies
17. 29:03Takeaway

" related talks

• 43mOnline Learning via Offline Greedy Algorithms: Applications in Market Design and OptimizationNegin Golrezaei · Data-Driven Decision Processes Boot Camp 2022
• 35mOnline Optimization and Learning Under Long-Term Convex Constraints and ObjectivesNikhil Devanur · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)
• 01h 00mContinuous Methods 4Maryam Fazel, Lorenzo Orecchia, Stefanie Jegelka, Reza Eghbali · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 58mMemory-Regret Tradeoff for Online LearningAviad Rubinstein, Binghui Peng · Sketching and Algorithm Design 2023
• 44mParsimonious Learning-Augmented AlgorithmsRavi Kumar · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 35mOnline Learning with A Lot of Batch DataShie Mannor · Reinforcement Learning from Batch Data and Simulation
• 48mA Simple Condition for Constant Regret in Online Decision-MakingDaniel Freund · Matching and Objectives
• 43mContextual Inverse Optimization: Offline and Online LearningIlan Lobel · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond