Search Machine Learning Repository:
Large-Scale Bandit Problems and KWIK Learning
Authors: Kareem Amin, Michael Kearns, Moez Draief and Jacob D. Abernethy
Conference: Proceedings of the 30th International Conference on Machine Learning (ICML-13)
Abstract: We show that parametric multi-armed bandit (MAB) problems with large state and action spaces can be algorithmically reduced to the supervised learning model known as Knows What It Knows or KWIK learning. We give matching impossibility results showing that the KWIK learnability requirement cannot be replaced by weaker supervised learning assumptions. We provide such results in both the standard parametric MAB setting, as well as for a new model in which the action space is finite but growing with time.
authors venues years
Suggest Changes to this paper.
Brought to you by the WUSTL Machine Learning Group. We have open faculty positions (tenured and tenure-track).