Robust Algorithms for Uncertain Environments

We consider designing algorithms that function in the presence of uncertainty: either the inputs to the algorithm or the algorithm's actions have some degree of uncertainty.

For example: there are algorithms for the (stochastic) multi-armed bandit problem in online learning and the secretary problem in online optimization that assume a probabilistic model on the inputs, and achieve a good performance when the data is drawn from these models. However, they tend to over-fit to these models: they perform poorly when the data can be slightly corrupted by an adversary. In this talk, we discuss how to model these adversarial corruptions, and how to get good algorithms that are robust to them.

The talk will be self-contained, and is based on works with Domagoj Bradac, Sahil Singla, and Goran Zuzic, and with Tomer Koren and Kunal Talwar.