Efficient Approximate Thompson Sampling for Search Query Recommendation

Query suggestions have been a valuable feature for e-commerce sites in helping shoppers refine their search intent. In this paper, we develop an algorithm that helps e-commerce sites like eBay mingle the output of different recommendation al-gorithms. Our algorithm is based on “Thompson Sampling” — a technique designed for solving multi-arm bandit prob-lems where the best results are not known in advance but instead are tried out to gather feedback. Our approach is to treat query suggestions as a competition among data re-sources: we have many query suggestion candidates compet-ing for limited space on the search results page. An “arm” is played when a query suggestion candidate is chosen for display, and our goal is to maximize the expected reward (user clicks on a suggestion). Our experiments have shown promising results in using the click-based user feedback to drive success by enhancing the quality of query suggestions