Pandora’s Box: Learning to Leverage Costly Information
19Shuchi Chawla (University of Texas at Austin)
https://simons.berkeley.edu/events/richard-m-karp-distinguished-lecture-shuchi-chawla
Richard M. Karp Distinguished Lecture
Many decision-making settings exhibit a trade-off between obtaining extra information to improve the outcome of the process and the cost of obtaining such information. The Pandora’s box problem of Weitzman (1979) is a classical model formalizing this trade-off. The algorithm is presented with a number of boxes containing unknown (stochastic) rewards, and it can select and keep one of the rewards. Boxes can be opened at a fixed cost to reveal their rewards. The problem is to determine which boxes to open, in what order, and which reward to choose, so as to maximize the reward obtained minus the costs paid. Weitzman presented a simple and elegant index-based policy for solving this problem under certain assumptions. In this talk, Shuchi Chawla will examine settings where Weitzman’s assumptions do not hold and his approach fails. She will focus, in particular, on settings where the rewards in boxes are correlated, and will present different ways of formalizing and attacking the problem. En route, she will examine issues that often arise in online decision-making, such as the trade-off between learning and optimization and benchmark choice.
===================================================================
Shuchi Chawla holds an endowed professorship in computer science at the University of Texas at Austin and is an Amazon Scholar. Shuchi is a theoretical computer scientist specializing in the areas of algorithm design, and economics and computation. Prior to joining UT Austin, she spent 15 years as a professor of CS at the University of Wisconsin-Madison. She has also previously held visiting positions at the University of Washington and Microsoft Research. Chawla has received several awards for her research and teaching, including a Sloan fellowship and the Chancellor’s Teaching Innovation Award at UW-Madison. She recently served as the PC chair of SODA20 and PC co-chair of EC’21, and currently serves on the editorial boards of ACM Transactions on Algorithms and ACM Transactions on Economics and Computation.