CaltechAUTHORS
  A Caltech Library Service

Hierarchical Exploration for Accelerating Contextual Bandits

Yue, Yisong and Hong, Sue Ann and Guestrin, Carlos (2012) Hierarchical Exploration for Accelerating Contextual Bandits. In: ICML'12 Proceedings of the 29th International Coference on International Conference on Machine Learning. International Machine Learning Society , Madison, WI, pp. 979-986. ISBN 978-1-4503-1285-1. https://resolver.caltech.edu/CaltechAUTHORS:20190327-085835163

[img] PDF - Published Version
See Usage Policy.

1MB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190327-085835163

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://icml.cc/2012/papers/933.pdfPublisherArticle
https://arxiv.org/abs/1206.6454arXivArticle
ORCID:
AuthorORCID
Yue, Yisong0000-0001-9127-1989
Additional Information:© 2012 by the author(s)/owner(s). The authors thank the anonymous reviewers for their helpful comments. The authors also thank Khalid El-Arini for help with data collection and processing. This work was supported in part by ONR (PECASE) N000141010672, ONR Young Investigator Program N00014-08-1-0752, and by the Intel Science and Technology Center for Embedded Computing.
Funders:
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-10-1-0672
Office of Naval Research (ONR)N00014-08-1-0752
Intel Science and Technology Center for Embedded ComputingUNSPECIFIED
Record Number:CaltechAUTHORS:20190327-085835163
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190327-085835163
Official Citation:Yisong Yue, Sue Ann Hong, and Carlos Guestrin. 2012. Hierarchical exploration for accelerating contextual bandits. In Proceedings of the 29th International Coference on International Conference on Machine Learning (ICML'12). Omnipress, , USA, 979-986.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:94188
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:27 Mar 2019 23:03
Last Modified:03 Oct 2019 21:01

Repository Staff Only: item control page