Some extended excerpts:
When a user visits a page, the systems task is to pick a certain ad topic, and from that ad topic pick a certain ad to show. The objective is to maximize click rate over some period of time.Targeting advertisements requires matching millions of ads to millions of users on billions of web pages.
We could ... [treat this as a] ... Bayesian formulation of the n-armed bandit problem ... and figure out which arms work best for that person.
A major problem we face with this approach is the problem of sparsity: there may be many ad topics available (thousands and beyond) ... the number of interactions we may get from a single user ... may be very small ... The average baseline click rate ... is very low (e.g., below one percent).
Information about user behavior and potential user and arm similarities that can ... help the choice of displayed arms.
When we want to select ads to display to a single user ... the problem is very similar to recommendation problems and involves many similar issues: users ... with similar tastes, missing values, and our choice of the columns/items to show.
Several recommender solutions methods, in particular collaborative filtering approaches, as well as techniques such as dimensionality reduction and clustering, nearest neighbors and other machine learning methods, apply ... as well.
The challenge here is how to do exploration and exploitation with the understanding that information obtained about a single user can help the whole community of users, and information about the community can help better serve a single user.
We are not aware of prior research that addresses exploration and exploitation in such large dimensional spaces, taking community (collaborative filtering effects) into account.
Data is extremely sparse on which ads are most effective for specific people and pages. Overcoming the sparse data will require combining contextual information about the ads and pages with knowledge of user interests and behavior to determine similar ads, people, and pages.
The problem then becomes a recommendation problem. For a specific user seeing a specific page, the most relevant ads most likely will be similar to ads that similar users found relevant on similar pages.
The combination of ads we pick will depend on whether we are exploring, learning more about how well some ads work for some pages and some users, or exploiting, seeking to maximize revenue based on the data we already have.