Robust Algorithms for Secretaries and Bandits
summary
Algorithm works on a red/green model where an unknown fraction of items are adversarially timed and values are arbitrary while the rest arrive uniformly at random; algorithm assumes a polynomial approximation to the green optimum. For selecting k items, bucketing by powers of two, splitting time into ~log intervals and using optimistic budgets that “slip down” yields a (1−ε) approximation when k is large (k = Ω(1/ε^2) up to minor losses). For one item an iterative refinement over value levels gives a Θ(1/log n) guarantee. Bandit extensions show regret grows with corruption c* plus the usual stochastic term.
AI-written summary · about
chapters (14)
- 0:00Intro
- 2:29the secretary problem
- 6:50the adversarial setting
- 9:19"byzantine" world
- 10:34what's the right benchmark!
- 11:56our results: robust secretary
- 14:25single item: iterative improvement
- 16:08first step: a little better
- 19:24single item: iterative-improvement
- 20:30robust secretary results
- 21:33idea: optimistically estimate, but check
- 27:04works even with adversarial items
- 28:26wrapping up algo...
- 31:29the 2BARs algo
related talks
40mApproximation Algorithms for Optimization under Uncertainty
01h 14mCompetitive Analysis Meets Stochastic Input: Secretary Problems And Prophet Inequalities
01h 21mAdversarial Bandits: Theory and Algorithms
01h 15mBridging Stochastic and Adversarial Bandits
01h 01mStochastic Bandits: Foundations and Current Perspectives
46mDynamic Regret Minimization for Bandits without Prior Knowledge
44mBandit Learning under Differential Privacy
22mOnline Learning and Bandits with Queried Hints