Seminars
View all Seminars | Download ICal for this eventStudies in Decision-Making: Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem and Algorithmic Interventions for Escaping Pessimism Traps
Series: Bangalore Theory Seminars
Speaker: Kavya Ravichandran, Ph.D student, Toyota Technological Institute, Chicago
Date/Time: Nov 21 16:00:00
Location: CSA Auditorium, (Room No. 104, Ground Floor)
Abstract:
We study decision-making under uncertainty in two settings: first, we give nearly-tight upper and lower bounds for the improving multi-armed bandits problem. An instance of this problem has $k$ arms, each of whose reward function is a concave and increasing function of the number of times that arm has been pulled so far. We show that for any randomized online algorithm, there exists an instance on which it must suffer at least an $Omega(sqrt{k})$ approximation factor relative to the optimal reward. We then provide a randomized online algorithm that guarantees an $O(sqrt{k})$ approximation factor, if it is told the maximum reward achievable by the optimal arm in advance. Finally, we show how to remove this assumption at the cost of an extra $O(log k)$ approximation factor, achieving an overall $O(sqrt{k} log k)$ approximation relative to optimal. This work studies decision-making in the presence of structured rewards. Secondly, I will also talk about our work on escaping pessimism traps -- a phenomenon in which agents are influenced by their predecessors to engage in less-ambitious ends. We provide a mathematical formalism in which to study this concept that was first isolated by philosophers. Then, we provide an algorithmic intervention to sustainably shift communities out of these traps.
Based on joint work with Avrim Blum, Emily Diana, and Alexander Tolbert.
Microsoft teams link:
Link
We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series
Hosts: Rameesh Paul, KVN Sreenivas, Rahul Madhavan, Debajyoti Kar