We have developed a method which learns to schedule internet banner advertisements so as to maximize the average click-through rate, while adhering to the requirements imposed by contracts with the advertisers such as a minimum guaranteed numberof impressions. We focus on the problem of adaptively scheduling advertisement display probabilities as a function of a single attribute such as a search keyword. Our learning algorithm is based on an efficient solution of a special class of linearprogramming problems called the 'transportation problem', and also embodies a number of measures to address the exploration-exploitation trade-off and an efficient attribute clustering method to help reduce the dimensionality. Our experimental resultsverify the advantage of our linear programming based approach, as well as the effect of various additional measures we incorporate into our method.
展开▼