Competitive Analysis Meets Stochastic Input: Secretary Problems And Prophet Inequalities

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=-C8sGqSoydQ


Duration: 1:13:45
712 views
0

Shuchi Chawla (UT Austin)
https://simons.berkeley.edu/talks/competitive-analysis-meets-stochastic-input-secretary-problems-and-prophet-inequalities
Data-Driven Decision Processes Boot Camp

In this talk we will discuss online decision-making problems where the input is partly adversarial and partly stochastic. In keeping with the theme of competitive analysis, we will compare the performance of the online algorithm against a hindsight optimum that observes the entire input before making decisions. I will survey techniques and results for the two dominant paradigms for these settings, namely secretary problems and prophet inequalities.



Other Videos By Simons Institute for the Theory of Computing


2022-08-27Reflections of David Blackwell on the Work of David Blackwell
2022-08-27Understanding, Simplicity, And Decision Trees
2022-08-27The Blackwell-Rao Theorem
2022-08-27Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
2022-08-26Blackwell’s Approachability Theorem
2022-08-26Multi-Distribution Learning, for Robustness, Fairness, and Collaboration
2022-08-26Multicalibration: Towards Fair Decision Making
2022-08-26Mechanism Design with Limited Commitment
2022-08-25(Sequential) Information Design
2022-08-25Machine Learning For Algorithm Design
2022-08-25Competitive Analysis Meets Stochastic Input: Secretary Problems And Prophet Inequalities
2022-08-25Competitive Analysis of Online Algorithms (Part 2)
2022-08-24Competitive Analysis of Online Algorithms (Part 1)
2022-08-24Online Reinforcement Learning and Regret
2022-08-24Foundations of RL
2022-08-24Foundations of RL
2022-08-23Fundamentals of Markov Decision Processes
2022-08-23Bridging Stochastic and Adversarial Bandits
2022-08-23Adversarial Bandits: Theory and Algorithms
2022-08-23Stochastic Bandits: Foundations and Current Perspectives
2022-08-22Stochastic Bandits: Foundations and Current Perspectives


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Data-Driven Decision Processes Boot Camp
Shuchi Chawla