Adversarially robust stochastic multi-armed bandits<\/p>\n
Multi-armed bandits are a fundamental problem in sequential decision making with applications in optimal experimental design, online advertisement, recommender systems and much more. In multi-armed bandits, an agent has to repeatedly choose an action from a finite set of options.<\/p>\n
After each action, the agent receives and observes a reward. For example, the action might be to prescribe a certain drug and the reward is the outcome of the patient’s treatment. The goal of the agent is to maximise its cumulative reward. It is commonly assumed that the rewards are drawn from i.i.d. distributions that only depend on the agent’s action. This assumption allows algorithms with provably fast learning to be derived. However, minor violations of this assumption can prevent these algorithms from learning anything at all.<\/p>\n
Another line of research aims at maximal robustness. These algorithms have performance guarantees even in the absence of any stochastic model. The drawback is that learning happens significantly slower.<\/p>\n
Naturally the question arises if a combination of both properties is achievable. Are there robust algorithms that also adapt automatically to easier, i.e. stochastic, environments? This question has remained open for 7 years. Its conclusion is the major contribution of this thesis.<\/p>\n
We derive an algorithm that is maximally robust and also achieves optimal rates in the stochastic setting. Furthermore, it is optimal in several intermediate regimes and we extend these results to problems beyond multi-armed bandits.<\/p>\n
Chairperson: Professor Christian Igel, Department of Computer Science, University of Copenhagen, Denmark
\nProfessor Alexandra Carpentier, Otto-von-Guericke-Universit\u00e4t Magdeburg, Germany
\nProfessor Nicol\u00f2 Cesa-Bianchi, Universit\u00e0 degli Studi di Milano, Italy
\nAcademic supervisors
\nAssociate professor Yevgeny Seldin, Department of Computer Science, University of Copenhagen
\nProfessor Christina Lioma, Department of Computer Science, University of Copenhagen<\/p>\n
For an electronic copy of the thesis, please contact\u00a0phdadmin@di.ku.dk<\/em><\/p>\n","protected":false},"excerpt":{"rendered":" Title Adversarially robust stochastic multi-armed bandits Abstract Multi-armed bandits are a fundamental problem in sequential decision making with applications in optimal experimental design, online advertisement, recommender systems and much more. In multi-armed bandits, an agent has to repeatedly choose an action from a finite set of options. After each action, the agent receives and observes […]<\/p>\n","protected":false},"author":0,"featured_media":102917,"template":"","class_list":["post-102916","event","type-event","status-publish","has-post-thumbnail","hentry","event_category-phd"],"acf":[],"yoast_head":"\n