6 papers
Algorithmic Approaches to Sequential Decision-Making and Social Epistemology
Kavya Ravichandran
As humans, we face many decisions that require us to choose between sticking to something and giving up. This thesis uses algorithmic tools to derive insights about such decision-m…
Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problem
Avrim Blum, Marten Garicano, Kavya Ravichandran +1
The improving multi-armed bandits problem is a formal model for allocating effort under uncertainty, motivated by scenarios such as investing research effort into new technologies,…
A Theoretical Model for Grit in Pursuing Ambitious Ends
Avrim Blum, Emily Diana, Kavya Ravichandran +1
Ambition and risk-taking have been heralded as important ways for marginalized communities to get out of cycles of poverty. As a result, educational messaging often encourages indi…
A Model for Combinatorial Dictionary Learning and Inference
Avrim Blum, Kavya Ravichandran
We are often interested in decomposing complex, structured data into simple components that explain the data. The linear version of this problem is well-studied as dictionary learn…
Pessimism Traps and Algorithmic Interventions
Avrim Blum, Emily Diana, Kavya Ravichandran +1
In this paper, we relate the philosophical literature on pessimism traps to information cascades, a formal model derived from the economics and mathematics literature. A pessimism…
Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem
Avrim Blum, Kavya Ravichandran
We give nearly-tight upper and lower bounds for the improving multi-armed bandits problem. An instance of this problem has arms, each of whose reward function is a concave and…