We managed to grab one of our friends, Michal Valko, during his visit to Amsterdam to give a talk on some of his recent work. It is quite a bit on a short notice, but that doesn't make you any less welcome to join :)
PLEASE NOTE: Being an ad-hoc talk (on a short notice and during office hours) we won't be offering the usual pizzas and drinks; but you're still very welcome to join if you can! Also, please be respectful of the people working in the office and try to be here at 16:00 sharp. If you arrive too early, we'd suggest to enjoy a relaxing walk in Vliegenbos (otherwise we'll have to seat you in the lobby, and that's no fun).
In this talk, we investigate the structural properties of certain sequential decision-making problems with limited feedback (bandits) in order to bring the known algorithmic solutions closer to a practical use including, online influence maximization or sequential recommender systems. To address these structured settings, we can always ignore the graph and use known algorithms for multi-armed bandits. However, their performance scales unfavorably with the number of nodes N, which is undesirable when N means a thousand of sensors or a million of movies. We describe several graph bandit problems and show how to use their graph structure to design new algorithms with faster learning rates, scaling not with N but with graph-dependent quantities, often much smaller than N in real-world graphs.