Topics in Applied Probability:Tempered Stable Distributions, Ad Placement, and Turing's Formula. Lecture 4

Lecture 4: Applications of stochastic knapsack and multi-armed bandit problems to internet ad placement. Abstract: One of the most important questions for internet companies is how to choose which ad to display in order to maximize their revenue. In this lecture we discuss two situations. In the first we must guarantee a certain number of clicks by a prespecified time before we get paid. We formulate this as a stochastic knapsack problem and give several strategies. The second is the situation where we know nothing about the ads. We must find a balance between gaining new information and exploiting our knowledge. This is formulated as a multiarmed bandit problem and we give several strategies for doing this.