Algorithms & Randomness Center (ARC)
Rohan Ghuge (University of Michigan)
February 13, 2023
Pettit Microelectronics Building, Room 102 A&B - 2:00 pm
Title: The Power of Adaptivity for Decision-Making under Uncertainty
Abstract: In this talk, we discuss the role of adaptivity in decision-making problems under uncertainty. The first part of the talk focuses on stochastic combinatorial optimization problems, while the second part deals with the K-armed dueling bandits problem.
Combinatorial optimization captures many natural decision-making problems such as matching, assortment optimization, 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 few adaptive rounds approximate fully-adaptive solutions? We study (and answer) this question for the stochastic submodular cover problem, where one needs to select a subset of stochastic items to cover a submodular function at minimum expected cost. This model captures 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 for the stochastic submodular cover problem. We study both independent and correlated settings, proving smooth tradeoffs between the number of adaptive rounds and the solution quality. We also present experimental results demonstrating that a few rounds of adaptivity suffice to obtain high-quality solutions in practice.
In the second part of the talk, we discuss the K-armed dueling bandits problem, a variation of the multi-armed bandit problem where the feedback is in the form of noisy pairwise comparisons. This problem 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 learning 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, for which we design algorithms with a smooth trade-off between the number of batches and regret. Our regret bounds match the best known sequential regret bounds (up to poly-logarithmic factors), using only a logarithmic number (in the time horizon) of batches.
---------------------------------------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836 and http://arc.gatech.edu/node/121
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
