Artificial Intelligence Seminar

We will introduce the problem of online model selection where a learner is to select among a set of online algorithms to solve a specific problem instance. We would like to design algorithms that allow such a learner to select in an online fashion the best algorithm without incurring much regret. This problem is challenging because in contrast with for example multi armed bandits, the algorithms' rewards -due to the algorithm's own learning process- may be non-stationary. We will introduce the principle of regret balancing, a simple, practical and effective model selection algorithmic design technique that allows for online selection of the best among multiple (base) algorithms in a fully blackbox fashion. Regret balancing solves the problem of non-stationarity by introducing an elegant misspecification test' that can efficiently detect when a base algorithm is not appropriate for the problem at hand.