Exploitation vs. exploration: Choosing keywords for search-based advertising services

Search-based advertising services provided by search engines enable companies to promote their products to internet users based on their queries is now a major online advertising channel. In most search based advertising services, a company sets a budget, selects keywords, bid for each keyword and pay for each click received. Thus the profit of the company highly lies on the reward of each keyword, i.e. conversion rate. With many keywords available and uncertain conversion rate associated with the ad for each keyword, identifying the most profitable keywords becomes challenge for companies. In this research, we consider the challenge as the exploitation and exploration trade-off problem which advertisers must choose between maximizing its expected reward according to its current knowledge about the keywords and trying to learn more knowledge about other keywords, since this might find keywords with higher reward. We first show the similarity of the keyword problem to the multi-armed bandit problem and use Gittins indices to solve the problem with 1-keyword per stage. We also propose four policies for the problem with multiple keywords per stage and suggest the best policy for different context by simulation.