Internship: Policy properties for greedy adaptive submodular maximization

Dr. Sivan Sabato, Department of Computing and Software, McMaster University

Adaptive combinatorial maximization is a problem in which the algorithm iteratively selects elements from a given set and observes their states. The reward depends on a utility function, which specifies the reward for each possible selected set based on the states of the elements. This problem is useful in many applications, including active learning, sensor placement, and many others. It has been shown that if a set function is adaptive submodular, then greedy policies for selecting elements can obtain a nearly-optimal utility. In recent work, we have found that it is possible to provide similar guarantees even for policies that are not greedy. In this internship, the student will study what properties are necessary and sufficient to provide such approximation guarantees for policies. A successful internship may lead to an offer for a PhD position.
I am looking for an intern who likes to be challenged by theory and to think about abstract problems. Strong background in discrete mathematics is required. Funding may be available.