Sequential Bayesian Search

30th International Conference on Machine Learning

Zheng Wen [e-mail] ; Technicolor Research Center ; 735 Emerson St ; Palo Alto ; CA 94301 ; USA ; Technicolor Research Center ; 735 Emerson St ; Palo Alto ; CA 94301 ; USA

PID  :  118058

来源: CEUR

【 摘 要 】

Millions of people search daily for movies, music, and books on the Internet. Unfortu nately, nonpersonalized 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 pro pose an efficient learning algorithm for solv ing the problem, sequential Bayesian search (SBS), and prove that it is Bayesian optimal. We also analyze the algorithm from the fre quentist point of view and show that its re gret 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