Select Lab Publications

Hierarchical Exploration for Accelerating Contextual Bandits (2012)

By: Yisong Yue, Sue Ann Hong, and Carlos Guestrin

Abstract: Contextual bandit learning is an increasingly popular approach to optimizing recommender systems via user feedback, but can be slow to converge in practice due to the need for exploring a large feature space. In this paper, we propose a coarse-to-fine hierarchical approach for encoding prior knowledge that drastically reduces the amount of exploration required. Intuitively, user preferences can be reasonably embedded in a coarse low-dimensional feature space that can be explored efficiently, requiring exploration in the high-dimensional space only as necessary. We introduce a bandit algorithm that explores within this coarse-to-fine spectrum, and prove performance guarantees that depend on how well the coarse space captures the user's preferences. We demonstrate substantial improvement over conventional bandit algorithms through extensive simulation as well as a live user study in the setting of personalized news recommendation.

Download Information
Yisong Yue, Sue Ann Hong, and Carlos Guestrin (2012). "Hierarchical Exploration for Accelerating Contextual Bandits." International Conference on Machine Learning (ICML). pdf long talk poster  
BibTeX citation

author = {Yisong Yue and Sue Ann Hong and Carlos Guestrin},
title = {Hierarchical Exploration for Accelerating Contextual Bandits},
booktitle = {International Conference on Machine Learning (ICML)},
year = 2012,
wwwtopic = {Online Learning},
wwwfilebase = {icml2012-yue-hong-guestrin},

full list