The Power of Adaptivity for Decision-Making under Uncertainty

Abstract

In this thesis, we study the role of adaptivity in decision-making problems under uncertainty. The first part of the thesis focuses on combinatorial problems, while the second part of the thesis deals with the $K$-armed dueling bandits problem. Combinatorial optimization captures many natural decision-making problems such as matching, load balancing, assortment optimization, network design, and submodular optimization. In many practical settings, we have to solve such combinatorial problems under uncertainty; specifically when we only have partial knowledge about the input. Solutions to such problems are sequential decision processes that make decisions one by one “adaptively” (depending on prior observations). While such adaptive solutions achieve the best objective, the inherently sequential nature makes them undesirable in many applications. Specifically, we ask: how well can solutions with only a few adaptive rounds approximate fully adaptive solutions?

(1) We study (and answer) the above question for the stochastic submodular cover and scenario submodular cover problems. These models capture many problems such as sensor placement with unreliable sensors, optimal decision tree, stochastic set cover, and correlated knapsack cover. We show how to obtain solutions that approximate fully-adaptive solutions using only a few “rounds” of adaptivity.

(2) We also study the stochastic score classification problem. We provide the first constant-factor approximation algorithm for this problem, which improves over the previously-known logarithmic approximation ratio. Moreover, our algorithm is non adaptive: it just involves performing tests in a fixed order until the class is identified.

(3) For both problems, we present experimental results demonstrating the practical efficacy of our algorithms. We find that a few rounds of adaptivity suffice to obtain high-quality solutions in practice.

In the second part of the thesis, we study the K-armed dueling bandits problem, which has applications in a wide-variety of domains like search ranking, recommendation systems and sports ranking where eliciting qualitative feedback is easy while real-valued feedback is not easily interpretable; thus, it has been a popular topic of research in the machine learning community. Previous works have only focused on the sequential setting where the policy adapts after every comparison. However, in many applications such as search ranking and recommendation systems, it is preferable to perform comparisons in a limited number of {parallel} batches. We {introduce} and study the {batched dueling bandits} problem under two standard settings: (i) existence of a Condorcet winner, and (ii) strong stochastic transitivity and stochastic triangle inequality. For both settings, we obtain algorithms with a smooth trade-off between the number of batches and regret. We complement our regret analysis with a nearly-matching lower bound. Finally, in experiments over a variety of real-world datasets, we observe that our algorithm using only a logarithmic number of rounds achieves almost the same performance as fully sequential algorithms (that use T rounds).