Sequential Bayesian Search

Zheng Wen, Branislav Kveton, Brian Eriksson, Sandilya Bhamidipati
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(2):226-234, 2013.

Abstract

Millions of people search daily for movies, music, and books on the Internet. Unfortunately, non-personalized exploration of items can result in an infeasible number of costly interaction steps. We study the problem of efficient, repeated interactive search. In this problem, the user is navigated to the items of interest through a series of options and our objective is to learn a better search policy from past interactions with the user. We propose an efficient learning algorithm for solving the problem, sequential Bayesian search (SBS), and prove that it is Bayesian optimal. We also analyze the algorithm from the frequentist point of view and show that its regret is sublinear in the number of searches. Finally, we evaluate our method on a real-world movie discovery problem and show that it performs nearly optimally as the number of searches increases.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-wen13, title = {Sequential {B}ayesian Search}, author = {Wen, Zheng and Kveton, Branislav and Eriksson, Brian and Bhamidipati, Sandilya}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {226--234}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/wen13.pdf}, url = {https://proceedings.mlr.press/v28/wen13.html}, abstract = {Millions of people search daily for movies, music, and books on the Internet. Unfortunately, non-personalized exploration of items can result in an infeasible number of costly interaction steps. We study the problem of efficient, repeated interactive search. In this problem, the user is navigated to the items of interest through a series of options and our objective is to learn a better search policy from past interactions with the user. We propose an efficient learning algorithm for solving the problem, sequential Bayesian search (SBS), and prove that it is Bayesian optimal. We also analyze the algorithm from the frequentist point of view and show that its regret is sublinear in the number of searches. Finally, we evaluate our method on a real-world movie discovery problem and show that it performs nearly optimally as the number of searches increases.} }
Endnote
%0 Conference Paper %T Sequential Bayesian Search %A Zheng Wen %A Branislav Kveton %A Brian Eriksson %A Sandilya Bhamidipati %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-wen13 %I PMLR %P 226--234 %U https://proceedings.mlr.press/v28/wen13.html %V 28 %N 2 %X Millions of people search daily for movies, music, and books on the Internet. Unfortunately, non-personalized exploration of items can result in an infeasible number of costly interaction steps. We study the problem of efficient, repeated interactive search. In this problem, the user is navigated to the items of interest through a series of options and our objective is to learn a better search policy from past interactions with the user. We propose an efficient learning algorithm for solving the problem, sequential Bayesian search (SBS), and prove that it is Bayesian optimal. We also analyze the algorithm from the frequentist point of view and show that its regret is sublinear in the number of searches. Finally, we evaluate our method on a real-world movie discovery problem and show that it performs nearly optimally as the number of searches increases.
RIS
TY - CPAPER TI - Sequential Bayesian Search AU - Zheng Wen AU - Branislav Kveton AU - Brian Eriksson AU - Sandilya Bhamidipati BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/05/13 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-wen13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 2 SP - 226 EP - 234 L1 - http://proceedings.mlr.press/v28/wen13.pdf UR - https://proceedings.mlr.press/v28/wen13.html AB - Millions of people search daily for movies, music, and books on the Internet. Unfortunately, non-personalized exploration of items can result in an infeasible number of costly interaction steps. We study the problem of efficient, repeated interactive search. In this problem, the user is navigated to the items of interest through a series of options and our objective is to learn a better search policy from past interactions with the user. We propose an efficient learning algorithm for solving the problem, sequential Bayesian search (SBS), and prove that it is Bayesian optimal. We also analyze the algorithm from the frequentist point of view and show that its regret is sublinear in the number of searches. Finally, we evaluate our method on a real-world movie discovery problem and show that it performs nearly optimally as the number of searches increases. ER -
APA
Wen, Z., Kveton, B., Eriksson, B. & Bhamidipati, S.. (2013). Sequential Bayesian Search. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(2):226-234 Available from https://proceedings.mlr.press/v28/wen13.html.

Related Material